Venue: NeurIPS 2021 Conference

Reviews:

final_score: rating: 4: Ok but not good enough - rejection
review_content: summary: This work improves neural program synthesis of imperative programs with limited control-flow (conditionals and loops)
from input-output examples. It extends the established pipelines for the Karel task – recurrent program decoder with
attention over partial output and example encodings – with modeling of a latent variable that represents a possible
execution state of the program at that location. The latent variable is supervised at the end to match the desired
output state. The authors test the approach on Karel (with mixed results), and on a randomly generated dataset of C
programs of similar complexity (where it substantially outperforms the baselines).
main_review: 
The key motivation of this work is to generalize execution-guided neural program synthesis to settings where step-wise
interpretation to retrieve actual program state is hard. Modeling expected program state as a latent variable,
predicting it with a recurrent model, and supervising to match the real state when known (in case of synthesis, the
desired output) is a promising and natural step towards that goal. However, the way the work presents its argument,
evaluates it, and compares against baselines falls short of its stated goal.

## Dataset
The key dataset that demonstrates the strength of LaSynth "beyond domain-specific languages" is a new dataset of
randomly-generated C programs. Its strengths include:
- A clever generation technique that leverages Csmith, a well-known random program generator for compiler fuzzing;
- Focus on challenging control flow, including for loops over integer lists, local variables, and arithmetic conditionals.

However, the sole fact that the generated programs are in C does not make it "unlike DSLs". The generated programs are
in a limited subset of C, de-facto unifying features of two existing DSLs: Karel and DeepCoder. They take loops and
conditionals from Karel, and variables, lists, and arithmetic from DeepCoder. As a result, the programs really do not
highlight the challenges by which the work is motivated. While C is compiled rather than interpreted, tracing partial
programs in this subset (to implement e.g. [6] or [22]) only requires one to close all outstanding blocks (to make the
program complete) and dump variable states at the location of interest.

Some challenging program synthesis datasets already satisfy the authors' requirements of (a) real programming language,
(b) input-output examples, (c) complex control flow. For instance:
- SPoC: https://sumith1896.github.io/spoc/
- APPS: https://github.com/hendrycks/apps

What is the reasonable upper bound of performance on the C dataset? For instance, how often is it the case that example
inputs have less that 100% coverage of the ground-truth program, and thus do not fully specify the intent?


## Baselines

The most natural baseline for this work would be [22], motivated by the similar goal of representing semantics of
partial programs as a latent variables. However, the authors do not provide any experimental evaluation, stating that
"per-line execution of partial C programs is infeasible" (L81). While generally true, this is definitely untrue for the
authors' dataset (e.g., via [CompCert Interpreter](https://compcert.org/man/manual004.html) or an ad-hoc one – see
above). As such, _conceptual_ comparison of two approaches is feasible. It is also warranted, given that LaSynth does
not compare nearly as favorably to explicit execution-guided synthesizers [28] and [6] on Karel.

Generalizing the point above, the fact that no baseline is shared between Karel and C evaluations makes it difficult to
appreciate the contribution of LaSynth. It clearly outperforms syntax-only synthesizers, but its comparison to the space
of execution-guided synthesizers (latent or explicit) is yet unclear.

What are the standard errors in Tables 2 and 3? How many runs were trained?

## Arithmetic modeling

The operation predictor is, in short, a lookup table for arithmetic operations that relies on the fact that only small
integers are used in the C dataset. Its inclusion is puzzling for many reasons:
- It is a domain-specific optimization that only works for small-number arithmetic, yet presented as part of the generic
  program architecture (Section 3.2). What is its instantiation for Karel?
- Table 1 claims that LaSynth has "no domain-specific features", yet operation predictor for arithmetic between -4 and 4
  that works because the dataset only contains these numbers is _most assuredly_ a domain-specific feature.
- It boosts accuracy on the C dataset by less than 2% – likely statistically significant but clearly orthogonal to the
  main contribution of the paper.

## Miscellaneous

More related work:
- Some research on task-oriented dialog requires the learned conversational system to model the latent "state" of the
  dialog, see e.g. [Min et al. 2020; Zhang et al. 2020]. (Usually the belief state is non-latent and labeled with some
  logical forms., thus more analogous to [6]).
- Predicting the next state after execution of the next instruction has also appeared in robotics [Paxton et al. 2019].

The "Iterative Retraining" trick is neat in the context of program synthesis. More broadly it can be likened to classic
_bootstrapping_ of ML models, where previous-iteration model is used to produce labels for an unsupervised dataset to
train the next-iteration model. Here the model is generative yet multiple "correct" labels for the same instance exist,
so this version of bootstrapping can re-label existing data instead. Worth exploring the connection in Related Work.  
The fact that this bootstrapping brings to light that many Karel programs permit equivalent simpler implementations is a
very interesting discovery, worthy of preview in the Introduction.

Please clarify whether Equation 6 is computed in symbolic space or (as $\hat{I}_T$ might suggest) in representation
space and consequently, what exactly is the used loss.

$\mathit{EXEC}_t$ in Figure 2c is only defined in the Appendix.

L302: "we make the first attempt of synthesizing C code from input-output examples for list manipulation" is unfair. It
is obvious untrue for non-neural synthesizers, but even for neural synthesis it neglects e.g. SPoC [Kulal et al. 2019]
and very recently (for Python rather than C) Codex [Chen et al. 2021]. 


## References
1. Min, Qingkai, et al. "Dialogue State Induction Using Neural Latent Variable Models." IJCAI 2020.
2. Zhang, Yichi, et al. "A Probabilistic End-To-End Task-Oriented Dialog Model with Latent Belief States towards Semi-Supervised Learning." EMNLP 2020.
3. Paxton, Chris, et al. "Prospection: Interpretable plans from language by predicting the future." ICRA 2019.
4. Kulal, Sumith, et al. "SPoC: Search-based Pseudocode to Code." NeurIPS 2019.
5. Chen, Mark, et al. "Evaluating Large Language Models Trained on Code." arXiv preprint arXiv:2107.03374 (2021).

limitations_and_societal_impact: No explicit limitations considered. The authors might consider discussing:
- what are the limits of "non-domain-specific" language constructs that latent execution might model successfully;
- the applicability of operation predictors;
- how might one generalize state embedding to settings where the state "type signature" is not uniform.
review_title: null

final_score: rating: 7: Good paper, accept
review_content: summary: This paper presents a neural program synthesis system, called LaSynth, that aims to generate programs in non-domain specific languages (DSLs) unlike much of the prior work. In particular, this paper focuses on using LaSynth for the C programming language. A core reason prior work in program synthesis has been generally restricted to DSLs is, as the authors note (and I agree with), because of the linguistic complexity of general-purpose languages and the computational intractability that is often associated with synthesizing programs in such languages.

A core novelty of LaSynth is that it uses two forms of conjoined/parallel representations, one of which uses a hypothetical input to help determine the remaining partial program to execute to get the desired output. This somewhat resembles BUSTLE’s approach of breaking down components into small pieces and then assembling them for a larger program (ICLR ’21), but the actual system-level approach in LaSynth, in my mind, is notably different from BUSTLE and other prior works that I’m familiar (some of which the authors seem to have missed in the prior work – NetSyn (Mandal et al., MLSys ’21), REPL (Ellis et al., NeurIPS ’20), etc.), but we'll get to that later.

main_review: Overall, I’m positive about this paper, even though I think it has some weaknesses (most are simple things that can be addressed in revising the paper). What I like the most about this paper is the authors intentionally move away from DSLs and toy languages (like Karel) and instead targeting program synthesis for real-world programming languages, like C, which is the primary target language for this paper. By migrating to such real-world languages, many challenges emerge (e.g., syntax correctness, computational complexity, multiple correct synthesized programs for the same problem, etc.). This complexity has historically been a major restriction in program synthesis research. A core reason for this is that each additional language token can result in upwards of an order of magnitude increase in the computational search space for the program synthesizer, amongst many other core challenges.

The authors address this computational tractability problem by using partial programs and hypothesized intermediate state IO representations to help the synthesizer (the Latest Execution Trace (LaET)). In my opinion, the core novelty of the work is in the LaET. An additional novelty is in the construction of the synthesizer system design, which uses parallel representations and iterative retraining to help prune unnecessary instructions and reduce the synthesized programs to programs that “work” to programs that “a human might write” (see Figure 1’s code transformation from the top left to the top right).

A weakness in the paper is they only seem to compare their results to two other systems (outside of variants of their own): Property Signatures and RobustFill. Both systems are fairly relevant and new-ish. However, newer systems include REPL (NeurIPS ’20), BUSTLE (ICLR ’21), and NetSyn (MLSys ’21). I don’t think it’s a showstopper for that this paper doesn’t include these systems as perhaps there wasn’t enough time to get access to them. However, there should probably be at least some footnote somewhere explaining why these systems weren’t include (e.g., code not available, published after the submission, generally different approach, etc.). I hope the authors update the paper accordingly here.

Please fix this: there is a *plethora* of work that utilize execution traces for ML outside of that being used in Karel, which is a toy programming language and are the only three papers you cite for this space, all of which come from Dawn Song’s research group at Berkeley. Examples of others that use execution traces for machine programming, just off the top of my head: NetSyn (MLSys ’21), REPL (NeurIPS ’20), AutoPerf (NeurIPS ’19), Ithemal (ICML ‘19). When I saw that the only works cited for program traces was all came from the same group at Berkeley, I was rather disappointed (especially seeing that the authors seem to be well-versed in the literature). I strongly recommend you not singularly cite *one* researcher’s group in an area as broad as program traces for ML that being covered by dozens of research groups. By doing this – citing three papers (and only three) all from the same group all around the same (toy) language – it creates a perception that either you are from this group and you are self-citing or you are not informed about the state-of-the-art. Either case is poor research acumen, unbefitting of a tier-1 venue like NeurIPS, in my opinion.

Minor nit: the citations are not properly capitalized (e.g., “Deepcoder: Learning to write programs” -> “DeepCoder: Learning to Write Programs”, “Imagenet: A large-scale hierarchical image database” -> “ImageNet: a Large-Scale Hierarchical Image Database”, “Bustle: …” -> “BUSTLE: …”, etc.). Please fix these minor grammatical errors for subsequent revisions of the paper.

limitations_and_societal_impact: None.
review_title: null

final_score: rating: 6: Marginally above the acceptance threshold
review_content: summary: This paper introduces LaSynth, a novel neural architecture that jointly learns to synthesize programs and perform a kind of targeted latent program execution. LaSynth is applied to synthesize Karel programs and list processing programs in the C programming language. The paper also finds that one to two iterations of dataset refinement and iterative retraining can improve the dataset quality and model performance. The LaSynth approach, with iterative retraining, is found to outperform baselines both in the Karel and C domains.
main_review: This work draws inspiration from and combines ideas from prior works using execution traces for program synthesis, and performing neural execution in latent space. It combines the core ideas of RobustFill for program generation with latent program execution to learn a latent program trace. This novel combination of ideas allows LaSynth to achieve strong results in two domains and outperform RobustFill and a Property Signature-based approach.

Beyond being a novel combination of ideas, the use of this kind of latent program execution from program synthesis is novel too. The latent states in the latent executor represent an abstraction both of (1) the result of the execution so far and (2) what the remainder of the program would need to be in order to achieve the target output.

The paper builds on a rich body of work on execution-guided program synthesis. Overall, it frames itself well within this literature. However, for the part of the paper on dataset refinement, this is lacking. I encourage the authors to put their dataset refinement contribution in the context of existing literature. Data augmentation is a rich field and has been used for program synthesis [1], and noisy student training [2] bears resemblance to your iterative approach.

The paper backs up its claims about the newly proposed approach LaSynth and about iterative dataset refinement through clear experimental evidence. It finds in the Karel domain that LaSynth (both with and without dataset refinement) outperforms the baselines considered, which do an adequate job of covering the space of modern approaches to the tasks.

How are the approaches made comparable? Are they given equal total compute or wall clock time, or are an equal number of samples drawn from each? How would an enumerative search approach compare?

The paper further finds that one (sometimes two) iterations of dataset refinement improve performance further. There is a rich body of existing work on data augmentation and self-training methods, which this paper does not mention. I suggest investigating his line of work and placing your dataset refinement contributions (which, to my knowledge, are novel for program synthesis) in the context of this body of existing work. See e.g. "noisy student training" [2].

The paper is overall clear in is explanation of its contributions, the method details, and the experiments. The paper states the latent executor hidden states represent the hypothetical input to the remaining program to produce the target output. This intuition bears elaboration. A concern I have is that the remaining partial program during latent execution could be the second half of a loop body, which in traditional code does not have a single input, nor can it be executed in isolation. Explaining the intuition of the hidden states more clearly would benefit the paper.

Program synthesis is an important problem lately of increasing interest to the NeurIPS community. Increasing the complexity of the languages in which synthesis is applicable is important, and the approach in this paper does just that. I do find the importance of the claim that this is the first time C code to be less significant than it likely sounds, however. Though technically a correct claim, this paper is looking at a narrow domain of programs, such that the complexity of working with C programs is comparable to working in a DSL for the domain. Particularly the significance is diminished (relative to the broader language of the claim) because of the restricted space of values considered, which includes only lists of the integers in $[-4, 4]$.

This limitation in the C domain manifests in the method with the following concern. The operation predictor uses a pre-computed table of all integer and subtraction operations. This is only possible due to the restricted domain of values, and prohibits the method as is from being used for even modestly broader domains.

Could you clarify what is meant by "we compute the property value per element in input-output pairs" at line 273?

---

Typo: "an associate memory structure" should be "associative"

---

[1] Guiding Program Synthesis by Learning to Generate Examples https://openreview.net/pdf?id=BJl07ySKvS

[2] Self-training with Noisy Student improves ImageNet classification https://arxiv.org/abs/1911.04252

limitations_and_societal_impact: The authors describe the main technical limitation of the work, the limited scope of the C language that it can handle. The authors do not discuss potential societal impact, indicating in the checklist they don't anticipate any such negative impact.
review_title: null

final_score: rating: 6: Marginally above the acceptance threshold
review_content: summary: The goal of this paper is to perform program synthesis, taking inspiration from recent advances in execution-guided neural program synthesis in situations where execution of partial programs is not immediately possible.

As stated by the paper, the main contributions are
1) combining two types of representations - one which models the mapping from spec to program tokens, as in RobustFill (and other neural synthesis work), and the other which models the “hypothetical input signal for the remaining partial program to execute to get the desired output”

2) demonstrating that iterative retraining can lead to better modeling of code and improve sample efficiency.

3) showing that short C code can be synthesized from IO examples through the above two techniques.
main_review: Originality & significance:  The technique is original. This work addresses important questions in neural program synthesis; namely, how to adapt the successful execution-guided neural program synthesis to domains where intermediate execution is impossible or infeasible.
This work provides further relaxations from Nye et al. (2021), gaining from an approach inspired by execution-guided synthesis, but without learning neural functions for each DSL element.

Ablations are good, and seem to show that the partial executor is important for performance on the C dataset. 

Iterative retraining seems to have a large effect at small dataset sizes; this effect diminishes at larger dataset sizes. For this reason, I do think the claim about iterative retraining would be stronger if it were evaluated on datasets build from real data, where extending the dataset automatically is not feasible. (See below — the dataset from Alet et al 2021 might be a good candidate). It seems that iterative retraining works because randomly generated programs are often more complicated than they need to be to solve the input-output examples (lines 226-230), but figure 3 and figure 7a seem to show that this mismatch can largely be solved by simply training on more synthetic data (which is always available for synthetic datasets). What would we see if we trained on real programs, where a) there isn’t always more data available but b) there may be less of a mismatch between the training data and the optimal programs?

Clarity:
- The paper is decently written, although there were some places where I was a little confused. In particular, I’m confused about how the latent execution setup works in the Karel domain. An explanation of this seems to be missing from both the main text and the supplement. In the C domain, $\hat{I}_{t,l}$ seems to be defined by a sum over embeddings of possible states. In the Karel domain, you don’t perform a sum over all possible Karel states, correct? Similarly, what is the Karel analog of the precomputed operation table?


- The hand-designed nature of the operation table of possible operations seems like a limitation. How would it scale to a larger set of values and operations? To me this seems to be the biggest limitation of the approach. The paper doesn’t contain much discussion of these limitations; I think adding a limitations section would greatly increase clarity
 For example, here are some other questions that it would be helpful to see answered:
	- I don’t have a clear sense of when this technique is easily applicable vs not applicable. Is the system as implemented only applicable to C programs with a type signature of List —> List, or could other type signature be easily supported? For example, how much engineering would be required to include programs of type (Int, List) —> List or List —> Int?
	- Is the approach computationally tractable when the set of possible intermediate states is too large to enumerate over? What happens when the range of integers is increased from [-4, 4] to [-256, 256] (or even [-2^32, 2^32])? Is that a limitation of this approach, or is there an easy fix? If it’s a limitation, I think that’s fine, but it would be helpful if it were clearly stated.

Overall, I do believe that this is an interesting contribution to neural program synthesis which extends the applicability of the promising line of neural execution-guided synthesis work. I felt like I learned something new reading this paper, although I don’t have a clear sense why this technique works. I would recommend acceptance, but I do think that improving the clarity about the Karel domain and a more clear discussion of limitations is important.


Comments/Questions:  
Here are questions that are not necessary for my vote of acceptance, but things I think would be interesting to explore:

- Is there evidence that the latent execution representations $\hat{I}$ actually predict execution well? Can you accurately predict the actual intermediate state from $\hat{I}$?

- How do these models compare against transformer models pre-trained on language? I’ve seen that pre-trained transformers can achieve good performance when fine-tuned on synthesis tasks. 

  - I’d be very interested to see the results of this system on the new C++ dataset from “A large-scale benchmark for few-shot program induction and synthesis” (Alet et al, ICML 2021). That would be an interesting test of this system on real-world code written by humans. As discussed above, I also think that it would be very useful to test iterative retraining here, to see if the approach has a benefit when the training dataset is derived from real code as opposed to synthetically generated.
 

limitations_and_societal_impact: See discussion of limitations above in main review, which I think do need to be more clearly addressed.

No negative societal impact.
review_title: null

Meta-review: OK, the situation with this paper is a bit unusual, owing to the fact that NeurIPS doesn't allow revisions during the reviewing period.
Basically all of the reviewers agreed that the core idea is good, but many of them had serious concerns with scoping and clarity. 
I am going to recommend acceptance here, but I want to really strongly urge the authors to address the issues brought up by the reviewers in the final version of the paper. I don't actually have any authority to compel that outcome, so I'm relying on trust here - please do make these changes!
Decision: Accept (Poster)