ExeDec: Execution Decomposition for Compositional Generalization in Neural Program Synthesis

Thank you for your review! We are grateful for the opportunity to work with you to improve our paper.

The benchmark introduced in Sections 2 and 3 is claimed as a novel contribution ... However, it is very hard to tell from these descriptions the actual contents and novelty of the benchmark. I was ultimately able to get a better understanding from reading the evaluation and Appendix B, but in isolation the clarity of these sections are very low.

Thank you for the feedback. We are glad to hear that you were able to get a better understanding from reading the evaluation and Appendix B, not that information was missing entirely. Perhaps some rearranging of information could be done to improve the flow.

To help us take action on this, could you please let us know what information from the evaluation and Appendix B was most helpful to improving your understanding, so we can move that information to Sections 2 and 3? It would also be super helpful to hear suggestions for what other information in the paper is not as important and can be moved away to an appendix, to make space.

Please keep in mind that we are already at the limit of 9 pages exactly, we will have even less space in the camera ready (due to the author list and no additional pages allowed), and we tried our best to partition the most-information in the main text from the less-important information in the appendices (14 additional pages of information).

What happens if the loop in Algorithm 1 never terminates?

In our experiments, we impose a maximum number of steps, after which we declare that the method fails to solve that problem. This is described in Appendix C, where the beam search checks for beam states where “some computation limit such as a maximum number of steps is reached”.

For the models trained from scratch:

• For RobustFill, we have a limit of 20 steps, but we almost never reach that limit because we also require that each subprogram makes correct progress with respect to the desired output. Most of the time, if a subprogram prediction is wrong, incorrect progress will be made (which we cannot recover from due to the concatenation structure of RobustFill programs) and the beam state will be marked as invalid and removed from the beam search.
• For DeepCoder, we have a limit of using 10 variables in the entire program (including variables used for the inputs), where each step uses a fresh variable.

For the LLM experiments: we use a limit of 3 steps.

My reading of the results in 5.2 (specifically, Table 1) is that I should divide all numbers by 200 to compare them with the results in 5.1 (Figure 2). Is this correct?

In Table 1, dividing the numbers by 200 results in percentages of problems solved. However, those percentages are not comparable with those in Figure 2 because the problems in the LLM experiments are easier, as explained in Section 5.2 and Footnote 4.

What is the comparison in FLOPs between the ExeDec models and the baseline models?

The loop in our step-by-step synthesis approaches does not lead to more “power”, because our step-by-step approaches predict multiple shorter subprograms, while the Transformer baseline and Latent Programmer predict the entire long program at once. If we assume that subprograms, a set of subgoals for each example, and I/O specifications all have an equal number of tokens, then ExeDec-Small and the No-Subgoal Ablation use roughly the same number of FLOPs, or slightly more FLOPs than the Transformer baseline and Latent Programmer (only because those approaches don’t need to encode the step-by-step execution information).

How do models perform on generalization tasks that they were not trained for?

The best way to answer this question may be to use the models trained without generalization, tested on the various generalization datasets. Our results for “test on training distribution” (i.e., the no-generalization case) can be seen as a combination of this for all generalization tasks, since the no-generalization distribution contains all of the generalization train and test distributions. But, the exact test problems themselves are different. We will investigate this and include the numbers in the revised paper.

Thank you for your review!

The middle ground of finetuning a pre-trained LLM would be interesting to see.

This would be interesting but we figured that, if we had to fine-tune the LLM 18 times (3 DSL settings, 6 generalization settings), this experiment would become prohibitively expensive.

You might be suggesting that we fine-tune the LLM 3 times, once for each of the DSL settings (RobustFill, DeepCoder, and DeepCoder-Pythonic), using the training distribution from the no-generalization setting. This is still expensive, and we thought this experimental setup would lead to less interpretable results, since we’d be testing on a distribution of programs that were seen during fine-tuning but are absent from the few-shot examples. We also weren’t sure how such a setup might mirror a real-life scenario, as typically one does not have a large finetuning dataset comprising all of the generalization patterns seen at test time.

It'd be interesting to see how the Transformer baseline performs when it also has access to [execution traces]

This is also an interesting suggestion. We assume you mean that we should “pause” the Transformer baseline’s program prediction after each line, collect the execution trace, inject the trace into the decoding, and then “unpause” the prediction to get the next line. As a step-by-step program generation procedure with program execution between steps, this is already quite similar to the No-Subgoal Ablation.

If we then consider that the Transformer baseline has no way of “backtracking” to change its prior prediction, and we already have a setup where we can specify all remaining work for the problem in the form of I/O examples, it would make sense that each step should not care about what prior predictions or execution traces led to the current state. In fact, conditioning on the prior steps could actually be distracting to the model, teaching it about spurious patterns that harm the generalization performance. If we treat each subprogram as a fresh prediction that is not conditioned on the previous steps, we arrive (at least in spirit) to the No-Subgoal Ablation.

Do you have an insight into why the no-subgoal ablation performs better on some generalization benchmarks?

This may be related to the kind of spurious pattern involved in the compositional generalization split. Specifically:

• For Length-Generalization and Switch-Concept-Order, the index of the current subprogram carries major implications in the training distribution, i.e., “the problem should be almost solved by now” or “we must use this category of operation”. However, those implications are drastically changed in the test distribution. The Transformer baseline is aware of the length of the prediction so far, so it can be easily confused by the distribution shift -- and indeed, it performs particularly poorly on these tasks. On the other hand, both ExeDec and the No-Subgoal Ablation are less aware of the current index of the subprogram, since the prior subprograms are only indirectly provided to the models through the program state. For these tasks, the No-Subgoal Ablation sometimes outperforms ExeDec slightly.
• For Compose-Different-Concepts and Compose-New-Operation, the spurious pattern arises from comparison to what work needs to be done outside the current subprogram: “this subprogram uses the same category of operation as the other subprograms” or “this subprogram can only use operation X if there are no other subprograms”. Again, these patterns are changed between the train and test distributions. The No-Subgoal Ablation is susceptible to overfitting on these patterns because it sees the I/O specification for the current subprogram composed with all future subprograms. On the other hand, ExeDec is shielded from these spurious patterns because its SynthesizerModel only sees the I/O specification for the current subprogram (provided that the SubgoalModel predicts the correct subgoals), which may explain the larger performance gap.
• For Add-Operation-Functionality, actually the spurious pattern is within an individual subprogram, i.e., some subprograms in test problems are outside the distribution of subprograms seen during training. None of the compared approaches are well-shielded from this form of spurious pattern, leading to the relatively low performance of our methods on this generalization task for RobustFill. (For DeepCoder, the trend is less clear since some problems may be solved using longer programs outside the test distribution.)

We’d be happy to add this discussion to the paper. Thanks for bringing it up! (Reviewer hCQX also asked a similar question, and the discussion above is copy/pasted in our responses to both of you.)

Thank you for your review and thoughtful questions and comments!

I/O-based specifications are not easy to construct

This is certainly true in general, but I/O specifications are still a common and intuitive way of specifying programs. Indeed, in unit tests, educational or competitive programming challenges, and on forums like StackOverflow, I/O examples are often expected. Of course, they may be combined with other forms of specification like natural language, but developing approaches that reason about I/O examples is still an important aspect of program synthesis overall.

Both DSLs seem simple straight-line code, and there are no recursion, loops, or if-else conditions, all of which are important components to construct a realistic large program.

In general-purpose programming languages, these control flow constructs are definitely important. Extending the ExeDec approach to handle these is important future work. That said, we note that many important programming libraries do not rely on these explicit control flow constructs. For example, matrix or tensor manipulation with TensorFlow / PyTorch / Numpy for machine learning and scientific computing, exploratory data analysis with Pandas, plotting with Matplotlib, spreadsheet formulas in Excel, and MapReduce pipelines are all typically expressed with a sequence or composition of library operations, usually without explicit control flow structures from the underlying programming language. In this sense, developing techniques that work well for straight-line code is still an important research direction.

Particularly, there are many valid solutions, which may have quite different intermediate sub-goals. Supervising only one specific solution would be problematic.

If there are multiple routes to a solution, in theory we would like to teach the model about all “good” (e.g., minimal-weight) solutions. In a hypothetical infinite-training-data regime, this is equivalent to selecting a random “good” solution independently for each training example. Then in practice, with some care in implementation, one can approximate this ideal by choosing uniformly random minimal-weight solutions when generating fresh random training data for every training step. (Our code does not yet select among minimal-weight solutions uniformly, but we do generate fresh training data for each training step.)

How to process different numbers of I/O examples (the size of which may also vary) in transformer models?

In our model (Section 4.2), a Transformer encoder turns each I/O example $X_i$ into an encoding $\\phi_i$, which has fixed length regardless of the example’s size. To combine these $\\phi_i$ across examples, we simply concatenate them which does assume (as in our experiments) that every problem is specified with a constant number of examples.

More generally, to handle any number of I/O examples, one can instead pool across examples, $\\phi_{\\text{pool}} \\gets \\operatorname{Pool}(\\{\\phi_i\\})$. Then, when predicting a subgoal for example $X_i$, the SubgoalModel may use a concatenation of $\\phi_{\\text{pool}}$ (encoding the overall problem) and $\\phi_i$ (encoding the specific example for which we need a subgoal), passed to a Transformer decoder which predicts the desired subgoal. The SynthesizerModel can directly apply a Transformer decoder to $\\phi_{\\text{pool}}$ to predict a subprogram.

Straight-line code can be split arbitrarily, how to decide which snippets form a proper sub-goal?

In our experiments, we make initial progress by simply using a subgoal after every line (with one DSL operation per line). Future work may investigate our ideas on more realistic code, where there are other signals that may identify plausible subgoals. For instance, blank lines, comments, and logging statements often break up real code into logical steps which we can use as subgoals. Even if the ground-truth code does not contain any such signals, one may prompt a code language model to guess where blank lines might be added, to receive a suggestion based on the language model’s ability to pattern-match to other code. Applying these ideas to real code would be very exciting to explore in future work, made possible by our initial findings on synthetic code.

It is a bit surprising that No-subgoal Ablation performs pretty well. Shouldn't it behave like the Transformer baseline?

There are two main difference between these approaches. First (and most importantly), the No-Subgoal Ablation receives program execution information after every predicted subprogram, so it can change its solution on the fly depending on the current program state, while the Transformer Baseline receives no execution information at all. Second, the No-Subgoal Ablation is trained on individual subprograms, while the Transformer Baseline was not explicitly shown how entire programs are composed of individual subprograms. In our view, these differences make the relative comparison expected.

Thank you for the in-depth review and your encouraging comments! Due to the character limit per message, we respond in two messages.

Just adding those citations in the appropriate places would strengthen this.

You’re absolutely right, we will revise the text and add the citations. Thank you for suggesting this!

How often are proposed subgoals actually achieved?

We measured a related metric of “single-step accuracy” for the SubgoalModel and SynthesizerModel. That is, for a single step in a trajectory that matches the ground-truth so far, how often does the SubgoalModel predict subgoals exactly matching the ground-truth ones (for all I/O examples) with a single greedy decoding? And, how often does the SynthesizerModel predict a program whose behavior matches the ground-truth subgoal?

For RobustFill, the SubgoalModel gets 90% - 98% single-step accuracy for the different generalization tasks, while the SynthesizerModel gets 84% on Add-Operation-Functionality and 94% - 99% on the other tasks.

For DeepCoder, the SubgoalModel gets 56% accuracy for no-generalization and 16% - 41% on the generalization tasks, while the SynthesizerModel gets 99% on no-generalization, 60% on Add-Operation-Functionality, 78% on Switch-Concept-Order, and 91 - 96% on the other tasks.

Note that our “single-step accuracy” metric is particularly low for the SubgoalModel on DeepCoder because there are potentially many correct ways of solving the problem, and this metric only considers the single ground-truth solution. In fact, the SubgoalModel does not need to have super high accuracy in order to achieve good end-to-end results, because the SynthesizerModel can ignore slight errors in the subgoals and still produce a program that behaves as closely as possible while only using 1 DSL operation. We have seen many concrete cases of the SynthesizerModel being given a slightly-incorrect subgoal and then producing the correct subprogram anyway, which disagrees with the subgoal but correctly makes progress overall.

In Figure 2, why do you think that ExeDec improves over the No-Subgoal ablation primarily in the Compose New Operation and Compose Different Concepts settings, and not in the other settings?

This may be related to the kind of spurious pattern involved in the compositional generalization split. Specifically:

• For Length-Generalization and Switch-Concept-Order, the index of the current subprogram carries major implications in the training distribution, i.e., “the problem should be almost solved by now” or “we must use this category of operation”. However, those implications are drastically changed in the test distribution. The Transformer baseline is aware of the length of the prediction so far, so it can be easily confused by the distribution shift -- and indeed, it performs particularly poorly on these tasks. On the other hand, both ExeDec and the No-Subgoal Ablation are less aware of the current index of the subprogram, since the prior subprograms are only indirectly provided to the models through the program state. For these tasks, the No-Subgoal Ablation sometimes outperforms ExeDec slightly.
• For Compose-Different-Concepts and Compose-New-Operation, the spurious pattern arises from comparison to what work needs to be done outside the current subprogram: “this subprogram uses the same category of operation as the other subprograms” or “this subprogram can only use operation X if there are no other subprograms”. Again, these patterns are changed between the train and test distributions. The No-Subgoal Ablation is susceptible to overfitting on these patterns because it sees the I/O specification for the current subprogram composed with all future subprograms. On the other hand, ExeDec is shielded from these spurious patterns because its SynthesizerModel only sees the I/O specification for the current subprogram (provided that the SubgoalModel predicts the correct subgoals), which may explain the larger performance gap.
• For Add-Operation-Functionality, actually the spurious pattern is within an individual subprogram, i.e., some subprograms in test problems are outside the distribution of subprograms seen during training. None of the compared approaches are well-shielded from this form of spurious pattern, leading to the relatively low performance of our methods on this generalization task for RobustFill. (For DeepCoder, the trend is less clear since some problems may be solved using longer programs outside the test distribution.)

We’d be happy to add this discussion to the paper. Thanks for bringing it up! (Reviewer iTFM also asked a similar question, and the discussion above is copy/pasted in our responses to both of you.)