Venue: ICLR 2021 Conference

Reviews:

final_score: rating: 5: Marginally below acceptance threshold
review_content: The main idea of the paper is using neural networks to provide "starting hints" to a program synthesizer that is based on genetic programming. Specifically, the network predicts one or two lines that must be present in the desired program given the I/O examples for the task. These lines are used to initialize the GP process instead of an empty program.

The core idea resembles DeepCoder, with two (important) differences: (a) the network predicts a code fragment of 1-2 lines instead of a distribution over operators, (b) the subsequent synthesis algorithm is a GP process rather than symbolic search. However, there's no comparison with the DeepCoder approach, either on this paper's DSL/dataset, or on DeepCoder's. I appreciate the authors' argument that the two DSLs significantly differ in expressiveness. However, most programs in this dataset have <10 lines, and comparison with enumerative or neural-guided synthesis approaches would be both feasible and informative for them.

In fact, the only baseline comparison is with vanilla GP. As such, the paper is definitely valuable for the GP program synthesis community, but less valuable to the ICLR neural program synthesis community at large.
I also some questions regarding the validity of experimental setup and suggestions on the presentation clarity (see below). All of these prevent me from raising the score above acceptance at this time even though I find the main idea promising and the end-to-end evaluation results impressive.

### Evaluation questions

The experimental setup is a bit unorthodox. The authors present individual components of their approach simultaneously as both (a) ablation experiments and (b) stages of their end-to-end pipeline. According to this presentation, the end-to-end pipeline operates as follows:
1. Start with a subset of easy tasks. Identify 10 best code fragments that, if provided, increase the find rate of GP (via brute force enumeration of all fragments).
2. Generate a synthetic train/test set for the classification problem "IO -> Fragment Presence" for each fragment.
3. Train a classification NN for each fragment.
4. For all tasks (including the ones from step 1), use the trained NNs to select the code fragments to provide as hints to GP. Measure the find rate of GP.

The pipeline view would be better appreciated in the beginning of Section 3, as a high-level overview of the whole system. Without it, different experiments now clearly map to different research questions:
- Experiment 3 is the "main" end-to-end performance/generalization evaluation.
- Experiment 1 is the "oracle" version of it where the fragment prediction component is replaced by brute-force enumeration of all valid fragments from ground truth ("How good we could possibly get?").
- Experiment 2 is the evaluation of classification accuracy of that individual component.

After this perspective on evaluation is better established, two questions arise.

First, the inclusion of Experiment 1 tasks into the final measurement is odd - they are indirectly part of the "training" data in this setup because they influence the selection of useful fragments. It's unclear which of the newly-solved problems are "training" and which are "testing" without inspecting Tables 26-27 line-by-line. If Experiment 3 did not involve any tasks from Experiment 1, the new average find rate would better inform the reader how the hint fragments - and the approach as a whole - generalizes across tasks. Which is the main goal of this end-to-end experiment.

Second, when comparing Tables 26-27 in the appendix with the corresponding "oracle" numbers in Table 1, I get confused. For example, the Append task reaches a maximum of 27% find rate for the best-performing fragment in Table 1. However, the paper's approach predicts a fragment that facilitates a find rate of 47%. If Experiment 1 evaluated every possible valid fragment from the ground truth program, how could the approach find a fragment that's better than the best one? I'm probably misunderstanding something in the experimental setup.

### Presentation questions

In addition to Section 4 advice above, I suggest restructuring the technical sections of the paper (i) from high-level to low-level, (ii) with motivating examples, (iii) with a system overview figure in the beginning. As written, Section 3 presents a lot of technical detail and high-level motivations are hard to notice and appreciate until one reads the entire paper.
In contrast, So & Oh, whose tasks the authors re-use in this work, start with task/program examples and give a much more formal presentation of the entire synthesis system.

Sections 3.2-3.3 are quite dense. They describe almost the entire system in prose, with quite a bit of technical detail. Instead, this section would benefit from presenting it as two algorithms in pseudocode - one for the GP synthesis and one for the end-to-end system for training NN for fragment classification and using its predictions to drive GP.

review_title: Good idea, impressive synthesis results, but lacks non-GP baselines and some evaluation details unclear

final_score: rating: 5: Marginally below acceptance threshold
review_content: Summary:

This work considers training neural networks to provide "hints" (suggested lines of code) as a way of augmenting genetic programming systems. At test time, a neural network conditions on input-output examples and learns to predict 1-2 lines of code which are present in a program satisfying those input-outputs. At train time, the system learns in a self supervised manner by bootstrapping off previously discovered programs, augmenting them to produce a large corpus of similar problems, and then training the network to predict lines of code present in this augmented data set, similar to DeepCoder.

Overall the method is sound, but I have two objections which caused me to lean toward reject:

+ First, the experiments seem small-scale, and even on these small domains the absolute performance gain is modest (for one-dimensional array manipulation, their method solves 55% vs 38% with vanilla genetic programming, as measured on 40 synthesis problems). This is at odds with the claim that the "approache is scalable to the search space of Turing-complete languages" - why not try on a standard benchmark, such as SyGuS? The promise of the proposed method hinges on its raw performance as well as its general applicability, and at present the experiments do not highlight these two factors.
+ Second, there is prior work on using deep learning to accelerate stochastic search over program spaces, indeed even over spaces as rich as arbitrary assembly code, e.g. "Learning to superoptimize programs" (ICLR 2017). How does your method compare? This prior work showed compelling results on a challenging standard benchmark - can your method do the same?

To be clear, not every paper has to beat standard benchmarks --- new good ideas that are carefully investigated are also good, and Experiments 1-2 do a great job of showing experimentally the different elements of the approach in action. But there is enough existing work (see "missing citations") in the conceptual neighborhood of this submission that I really think they should compare on some standard-ish benchmarks, because the approach on its own seems too similar to prior works.

minor concerns:
- page 2: what do you mean by neural synthesis either drawing from the target language by "sampling at a uniform interval or at random"?
- how sensitive is the performance of the algorithm to the small details of the genetic programming set up?

missing citations:
- "Learning to superoptimize programs" (ICLR 2017 - see above)
- "Augmenting Genetic Algorithms with Deep Neural Networks for Exploring the Chemical Space" (ICLR 2020)
- "Learning Fitness Functions for Genetic Algorithms" (2019 - could this be combined synergistically with your work? where you learn the best fragments to include and they learn the fitness function?)
- "Write, Execute, Assess: program synthesis with a REPL" (NeurIPS 2019 - can this also be combined, whereby a mutation policy and fitness value function are learned through RL?)

review_title: Interesting work, but should have more compelling experiments given the background of related work

final_score: rating: 4: Ok but not good enough - rejection
review_content: This paper proposes a genetic programming approach for programming-by-example systems, where the genetic search is seeded with fragments that are predicted by a neural network to be relevant to the input-output examples. This is shown to solve more synthesis problems compared to un-aided genetic programming for array-to-array programs and canvas drawing programs.

The neural network is a classifier that given a set of input-output examples and a program fragment predicts whether the fragment could occur in the solution to the synthesis problem. The fragments above a threshold are used for seeding the genetic search and candidates that do not include them are penalized during the search. An initial genetic search is performed on simpler problems to prepare the training set for the classifier. I found the description of the process for generating the training set quite vague. From what I understand, the useful fragments from candidates generated during the initial genetic search are identified manually and then it is augmented with a further set of manually chosen fragment. Some noisy fragments are then added randomly to prepare negative examples. The extent of the manual efforts here is substantial and requires domain knowledge from the developer. In contrast, many neural models for synthesis work entirely off of randomly sampled programs.

The experimentation is not explained clearly. The term "find rates" is used without defining. It appears from Table 1 that it is some way of measuring the success of genetic search (but what and how it computed is not clear). In Section 4.2, it is said that "all programs with a 90% find rate or better ..." are used. What is the find rate of a program and how does it relate to the find rate of the search procedures?

Experiment 3 shows the benefits of using the classifier to seed the search. What is the relation between the problems whose fragments are used for training the classifier and the problems used in this experiment? Is the former a subset of the latter?

From the applicability point of view, what is the time take by a successful genetic search across the problems? The rarest preferred fragment assumes existence of other problems to rank order the fragments. This is an impractical requirement to the user, who would be interested in only her problem and cannot be expected to supply related problems for ranking purposes.

From the point of view of baselines, there are two types of baselines missing. One is a neural method for straightforward program generation from examples; any suitable one from the cited papers can be used. Another is a non-neural selection method for fragments; a simple mining method can be applied to the data from the correct programs from the initial genetic search. These will help properly understand the benefits of the respective contributions.

Please label the sub-tables in Table 1 and 2. Can you spell out how the distance D for identifying repulsors is computed, for instance, if some edit distance is used then which one?
review_title: A possibly useful idea, requires better explanations and experiments

Meta-review: There are some interesting ideas in this paper, but I agree with reviewers that without a comparison to existing work, it is hard to place this work in its proper context. The authors make several arguments in dismissing the need for side-by-side comparisons, but I do not find these arguments convincing. 
* First, the authors argue that there are no suitable benchmarks for them to compare, and that in particular SyGuS benchmarks would not be suitable because they are dealing with a different problem. I disagree. There are 2 tracks in SyGuS specifically for programming-by-example problems, one for string manipulations and one for bit-vector programs. I think the string manipulation problems would be a good match for this technique. 
* The authors also argue that their technique is so much more general than prior techniques that a side-by-side comparison would be unfair. However, their most complex benchmark, sorting, has been somewhat of a standard benchmark in the program synthesis community for about a decade now. And while a lot of recent synthesis work has focused on domain specific languages, many systems starting with Sketch and continuing with Myrth and Synquid were turning complete. Turing completeness can make a big difference if you are trying to synthesize verified code, but in the context of programming-by-example, turning completeness does not really present any fundamental challenges.

I am willing to believe that this technique is more scalable than existing techniques, so that while existing techniques may do better than this technique when synthesizing for small languages, this technique would surpass them when applied to a bigger language. But if that's the argument that the authors want to make I would like to see some evidence, and ideally some quantitative data as to how big a language would have to be before this technique wins out.
Decision: Reject