Learning to select examples for program synthesis
Program synthesis is a class of regression problems where one seeks a solution, in the form of a source-code program, that maps the inputs to their corresponding outputs exactly. Due to its precise and combinatorial nature, it is commonly formulated as a constraint satisfaction problem, where input-output examples are expressed constraints, and solved with a constraint solver. A key challenge of this formulation is that of scalability: While constraint solvers work well with few well-chosen examples, constraining the entire set of example constitutes a significant overhead in both time and memory. In this paper we address this challenge by constructing a representative subset of examples that is both small and is able to constrain the solver sufficiently. We build the subset one example at a time, using a trained discriminator to predict the probability of unchosen input-output examples conditioned on the chosen input-output examples, adding the least probable example to the subset. Experiment on a diagram drawing domain shows our approach produces subset of examples that are small and representative for the constraint solver.
 The paper proposes a method for identifying representative examples for program synthesis to increase the scalability of existing constraint programming solutions. The authors present their approach and evaluate it empirically. The proposed approach is interesting, but I feel that the experimental section does not serve to show its merits for several reasons. First, it does not demonstrate increased scalability. Only 1024 examples are considered, which is by no means large. Even then, the authors approach selects the highest number of examples (figure 4). CEGIS both selects fewer examples and has a shorter median time for complete synthesis. Intuitively, the authors* method should scale better, but they fail to show this -- a missed opportunity to make the paper much more compelling. This is especially true as a more challenging benchmark could be created very easily by simply scaling up the image. Second, there is no analysis of the representativeness of the found sets of constraints. Given that the results are very close to other approaches, it remains unclear whether they are simply due to random variations, or whether the proposed approach actually achieves a non-random improvement. In addition to my concerns about the experimental evaluation, I have concerns about the general approach. It is unclear to me that machine learning is the best approach for modeling and solving this problem. In particular, the selection probability of any particular example could be estimated through a heuristic, for example by simply counting the number of neighbouring examples that have a different color, weighted by whether they are in the set of examples already, to assess its "borderness", with high values being more important to achieve a good program. The border pixels are probably sufficient to learn the program perfectly, and in fact this may be exactly what the neural net is learning. The above heuristic is obviously specific to the domain, but similar heuristics could be easily constructed for other domains. I feel that this is something the authors should at least compare to in the empirical evaluation. Another concern is that the authors* approach assumes that all parameters have the same effect. Even for the example the authors give in section 2, it is unclear that this would be true. The text says that rand+cegis selects 70% of examples of the proposed approach, but figure 4 seems to suggest that the numbers are very close -- is this initial examples only? Overall the paper appears rushed -- the acknowledgements section is left over from the template and there is a reference to figure "blah". There are typos and grammatical mistakes throughout the paper. The reference to "Model counting" is incomplete. In summary, I feel that the paper cannot be accepted in its current form.
You are a member of the scientific community tasked with peer review. Review the following paper title and abstract.
### Title + Abstract
Learning to select examples for program synthesis
Program synthesis is a class of regression problems where one seeks a solution, in the form of a source-code program, that maps the inputs to their corresponding outputs exactly. Due to its precise and combinatorial nature, it is commonly formulated as a constraint satisfaction problem, where input-output examples are expressed constraints, and solved with a constraint solver. A key challenge of this formulation is that of scalability: While constraint solvers work well with few well-chosen examples, constraining the entire set of example constitutes a significant overhead in both time and memory. In this paper we address this challenge by constructing a representative subset of examples that is both small and is able to constrain the solver sufficiently. We build the subset one example at a time, using a trained discriminator to predict the probability of unchosen input-output examples conditioned on the chosen input-output examples, adding the least probable example to the subset. Experiment on a diagram drawing domain shows our approach produces subset of examples that are small and representative for the constraint solver.
user
<think>Okay, to do a decent peer review, I should start with summarizing what the work is about. This includes novelty, contributions, clarity, and impact. I might include suggestions to issues that I find critical to the usefulness of the work. Starting with novelty, there are different types of novelty. The first aspect of novelty is scope and scale. Is the work covering a broader perspective than previous works? The second aspect is methodology. Is the proposed methodology novel compared to previous methods? Do they provide any significant advantage over previous methodologies? The third aspect is results. Are the results different compared previous work? Does this lead to any novel theories or an extension of current theories? Next is clarity, I will be reading the work in depth and analyze if any sentences can be potentially ambiguous or misleading. If any sentences are ambiguous, I will state them and give a suggestion on how to rephrase such sentence or how to make more clear to the audience. Lastly, impact is important. I will attempt to predict how such work will impact the scientific community. This might include the applications of such work and how the work might transform the way we study a certain topic. Finally, I will might only mention issues that are critical. This is to keep the review as concise and helpful as possible.</think>



 The paper proposes a method for identifying representative examples for program synthesis to increase the scalability of existing constraint programming solutions. The authors present their approach and evaluate it empirically. The proposed approach is interesting, but I feel that the experimental section does not serve to show its merits for several reasons. First, it does not demonstrate increased scalability. Only 1024 examples are considered, which is by no means large. Even then, the authors approach selects the highest number of examples (figure 4). CEGIS both selects fewer examples and has a shorter median time for complete synthesis. Intuitively, the authors* method should scale better, but they fail to show this -- a missed opportunity to make the paper much more compelling. This is especially true as a more challenging benchmark could be created very easily by simply scaling up the image. Second, there is no analysis of the representativeness of the found sets of constraints. Given that the results are very close to other approaches, it remains unclear whether they are simply due to random variations, or whether the proposed approach actually achieves a non-random improvement. In addition to my concerns about the experimental evaluation, I have concerns about the general approach. It is unclear to me that machine learning is the best approach for modeling and solving this problem. In particular, the selection probability of any particular example could be estimated through a heuristic, for example by simply counting the number of neighbouring examples that have a different color, weighted by whether they are in the set of examples already, to assess its "borderness", with high values being more important to achieve a good program. The border pixels are probably sufficient to learn the program perfectly, and in fact this may be exactly what the neural net is learning. The above heuristic is obviously specific to the domain, but similar heuristics could be easily constructed for other domains. I feel that this is something the authors should at least compare to in the empirical evaluation. Another concern is that the authors* approach assumes that all parameters have the same effect. Even for the example the authors give in section 2, it is unclear that this would be true. The text says that rand+cegis selects 70% of examples of the proposed approach, but figure 4 seems to suggest that the numbers are very close -- is this initial examples only? Overall the paper appears rushed -- the acknowledgements section is left over from the template and there is a reference to figure "blah". There are typos and grammatical mistakes throughout the paper. The reference to "Model counting" is incomplete. In summary, I feel that the paper cannot be accepted in its current form.
assistant
 The paper proposes a method for identifying representative examples for program synthesis to increase the scalability of existing constraint programming solutions. The authors present their approach and evaluate it empirically. The proposed approach is interesting, but I feel that the experimental section does not serve to show its merits for several reasons. First, it does not demonstrate increased scalability. Only 1024 examples are considered, which is by no means large. Even then, the authors approach selects the highest number of examples (figure 4). CEGIS both selects fewer examples and has a shorter median time for complete synthesis. Intuitively, the authors* method should scale better, but they fail to show this -- a missed opportunity to make the paper much more compelling. This is especially true as a more challenging benchmark could be created very easily by simply scaling up the image. Second, there is no analysis of the representativeness of the found sets of constraints. Given that the results are very close to other approaches, it remains unclear whether they are simply due to random variations, or whether the proposed approach actually achieves a non-random improvement. In addition to my concerns about the experimental evaluation, I have concerns about the general approach. It is unclear to me that machine learning is the best approach for modeling and solving this problem. In particular, the selection probability of any particular example could be estimated through a heuristic, for example by simply counting the number of neighbouring examples that have a different color, weighted by whether they are in the set of examples already, to assess its "borderness", with high values being more important to achieve a good program. The border pixels are probably sufficient to learn the program perfectly, and in fact this may be exactly what the neural net is learning. The above heuristic is obviously specific to the domain, but similar heuristics could be easily constructed for other domains. I feel that this is something the authors should at least compare to in the empirical evaluation. Another concern is that the authors* approach assumes that all parameters have the same effect. Even for the example the authors give in section 2, it is unclear that this would be true. The text says that rand+cegis selects 70% of examples of the proposed approach, but figure 4 seems to suggest that the numbers are very close -- is this initial examples only? Overall the paper appears rushed -- the acknowledgements section is left over from the template and there is a reference to figure "blah". There are typos and grammatical mistakes throughout the paper. The reference to "Model counting" is incomplete. In summary, I feel that the paper cannot be accepted in its current form.