ExeDec: Execution Decomposition for Compositional Generalization in Neural Program Synthesis
Authors: Kensen Shi
Joey Hong
Yinlin Deng
Pengcheng Yin
Manzil Zaheer
Charles Sutton
Venue: ICLR 2024 oral (2024)
Keywords: Program Synthesis
Programming By Example
Generalization
Compositional Generalization
Primary area: generative models
TL;DR: We describe different forms of compositional generalization that are desirable in program synthesis, and present a decomposition-based approach to synthesis achieving higher compositional generalization on two domains compared to prior approaches.

Abstract: When writing programs, people have the ability to tackle a new complex task by decomposing it into smaller and more familiar subtasks. While it is difficult to measure whether neural program synthesis methods have similar capabilities, we can measure whether they compositionally generalize, that is, whether a model that has been trained on the simpler subtasks is subsequently able to solve more complex tasks. In this paper, we characterize several different forms of compositional generalization that are desirable in program synthesis, forming a meta-benchmark which we use to create generalization tasks for two popular datasets, RobustFill and DeepCoder. We then propose ExeDec, a novel decomposition-based synthesis strategy that predicts execution subgoals to solve problems step-by-step informed by program execution at each step. When used with Transformer models trained from scratch, ExeDec has better synthesis performance and greatly improved compositional generalization ability compared to baselines. Finally, we use our benchmarks to demonstrate that LLMs struggle to compositionally generalize when asked to do programming-by-example in a few-shot setting, but an ExeDec-style prompting approach can improve the generalization ability and overall performance.

Published as a conference paper at ICLR 2024
EXEDEC: EXECUTION DECOMPOSITION FOR COMPOSITIONAL GENERALIZATION IN NEURAL PROGRAM SYNTHESIS
Kensen Shi
Joey Hong
Yinlin Deng
Google DeepMind kshi (aniiggoole.cco com
UC Berkeley
University of Illinois
joey.honggberzkeley, edu
Urbana- Champaann
yinlind288 www.nniiiiiinise..
Pengcheng Yin Google DeepMind pcyinggeogle.com com
Manzil Zaheer Google DeepMind manz Meazell www.aaheeerrrggg....o.oooooooooe
Charles Sutton Google DeepMind
charlessuttcon@google.ccoo
ABSTRACT
When writing programs, people have the ability to tackle a new complex task by decomposing into smaller and more familiar subtasks. While it is difficult to measure whether neural program synthesis methods have similar capabilities, we measure whether they compositionally generalize, that is, whether a model that has been trained on the simpler subtasks is subsequently able to solve more complex tasks. In this paper, we characterize several different forms of compositional generalization that are desirable in program synthesis, forming a meta- benchmarkk which we use to create generalization tasks for two popular datasets, RobustFill and DeepCoder. We then propose ExeDec, a novel decomposition- strategy that predicts execution subgoals to solve problems step-by- informed by program execution at each step. When used with Transformer models trained from scratch, ExeDec has better synthesis performance and greatly improved compositional generalization ability compared to baselines. Finally, use our benchmarks to demonstrate that LLMs struggle to compositionally generalize when asked to do programming- seaaiinnn----eeeeee by-example in few-shot setting, but an ExeDec-style prompting approach can improve the generalization ability and overall performance.
synthesis
INTRODUCTION
Program synthesis aims to assist programmers by automatically producing code according to user's specification of what the code should do (Gulwani al., 2017). Program synthesis systems, such as programming by example (PBE) systems, have been effective for tasks such as string manipulation (Gulwani, 2011; Devlin et al., 2017; Shi et al., 2022b), writing short Java functions (Shi et al., 2019), and tensor manipulation (Shi et al., 2022a). Neural program synthesizers, especially those based on large language models (Chen et al., 2021a; Austin et al., 2021; Li et al., 2022), have been particularly successful at generating code functions and blocks across variety of general- purpose programming languages.
An essential capability of human programmers is their ability generalize by recombining parts of prior knowledge to solve new tasks. For example, a capable programmer can quickly adapt to new concepts and APIs, and compose different code idioms in unseen ways solve novel problems. These skills are instances of compositional generalization, which is the ability to generalize to test examples consisting of different compositions of components individually seen during training (Keysers et al., 2020). While compositionality has been studied in natural language processing (Chomsky, 1957; Lake & Baroni, 2018; Gu et al., 2021), has been studied deeply the context of programming by example. This problem is potentially fruitful not only because it might help to build more robust program synthesizers, but also as an example of how more general problem-solving compositional.
'These authors contributed during internships Google DeepMind.

---

Published as a conference paper at ICLR 2024
To build neural synthesis systems that are better compositional generalization, we propose designing systems that learn to decompose a complex task into a list of simpler subtasks. Each subtask is defined by goal, the process of decomposing task is essentially planning. Indeed, decomposition is skill so fundamental to software engineering that the first programming course at Stanford University introduces decomposition within the first week (Parlante, 2022). This can enable compositional generalization because subtasks seen during training can be combined in different ways at test time.
Based on this intuition, we propose ExeDec, a novel search method for neural program synthesis that performs decomposition within the execution space. A PBE task defines a program by pairs of program inputs with their desired outputs. Thus, it is natural describe a subgoal by the desired intermediate state, i.e., values of local variables, for the next subtask. To describe the intuition in another way, we imagine that human programmer does not decide on what code to write one token at time, but rather thinks about what the result of the next code block should be, and then writes code to accomplish that. Specifically, ExeDec uses two neural models, a subgoal model that predicts the desired program state for the next part of the program, and a synthesizer model that attempts to generate a program that reaches that subgoal from the prior state. We interleave neural prediction with program execution within a beam search that enables exploring different predicted decompositions.
To evaluate this approach, we introduce a new meta- bett-bennchark for measuring the compositional generalization abilities of program synthesizers. Given a standard program synthesis benchmark containing a domain-specific language and a distribution over target programs, our meta-henchmark describes train-test splits for 5 different types of compositional generalization, such as length gener- alization or composing API functions in different combinations in the training and test sets. While ExeDec has slightly better performance than Transformer baseline in the i.i.d. setting, ExeDec also achieves a 2x to 4x accuracy increase in the compositional generalization setting. Additionally, ExeDec improves upon an ablation that does not explicitly propose subgoals, showing the importance of reasoning about execution subgoals instead of directly predicting code.
Interestingly, similar approach can be applied to explore compositional generalization in large language models (LLMs). We explore whether the LLM can solve PBE tasks that compositionally generalize beyond those in a few-shot prompt. We similarly find that the LLM performs significantly worse when compositional generalization is required, and that an adaptation of ExeDec to the few-shot prompting setup increases the LLM's performance overall, including in compositional generalization. Even so, compositional generalization during program generation in LLMs remains challenge.
2 COMPOSITIONAL. GENERALIZATION IN PROGRAMMING
The goal in program synthesis is to find a program in a given language that is consistent with a specification. Formally, we are given a domain specific language (DSL) which defines a set P of programs. Elements in the DSL. include functions (which we call operations), identifiers, constants, and so on. In programming by example (PBE), the desired program is specified by a set of input/output (I/O) examples denoted X = O.)........ ........ (In, }. Then, solving specification X means finding a program P E P that correctly solves all of the examples: P(4) O,, Vi. A robust program synthesizer should generalize to programs not in the training set. Regardless of the programming language or DSL, programs are nearly always built from smaller parts, which we call subprograms, such as lines and blocks of code, functions, and so on. For compositional generalization, we are interested in whether the synthesizer can combine subprograms in new ways from the training set.
We design our benchmark around five compositional generalization tasks applicable to program synthesis (Figure 1). These tasks measure whether synthesizers can generalize to longer programs or programs that use concepts, such as API methods, in different compositional ways. These concepts partition the DSL operations into groups.' In this section, we describe the generalization tasks abstractly, forming a meta- benchmark that can be applied in future work to construct new compositional generalization benchmarks using existing datasets or DSLs. Then, in Section 3, we concretize the tasks for specific DSLs for our experiments. The five generalization tasks are:
1. Length-Generalization Can a model produce longer code than seen in training, when necessary? Here, "length" counts the number of subprograms and not the number of tokens, so there is more
'Ideally operations within group should have meaningful commonalities that form one concept, and each concept should have roughly equal semantic complexity, but these are not strictly required.
2

---

Published as a conference paper at ICLR 2024
Length Generalization
Compose Different Concepts
Switch Concept Order
Compose Operation
Add Operation Functionality
O
Train
O0
0000
Test
Figure 1: Our five compositional generalization tasks. Circles represent subprograms that join to form programs train test examples, colored circles represent subprograms of particular concept or operation, and bold outlines represent analogous functionality of different operations.
emphasis on generalizing to more complex compositional patterns. For this task, we train problems lengths to n and test on lengths n + to m (where m > n)) Cimppose-DiferenttCCnceep
Can model use concepts in different combinations than seen in training? Specifically, train the model on compositions of operations from the same concept, and test on compositions from different concepts, For example, if two concepts consist of operations {A1, .2....} and B1, B2.... ... }. then the training programs have the form A, o Aj and B, Bj. and the testing programs have the form A, Bj and B; Aj (and similarly for compositions of or more operations). real-world example might be training on program containing only TensorFlow only NumPy, but synthesizing code at test time using both libraries.
3. Crftch-Conneet-OOe
Can model compose concepts in different orders than seen in training? We train on compositions of operations drawn from one sequence of concepts and test on a different sequence of concepts, e.g., train A; Bj and test B, Aj- As real-world example, in the training data a function might be validating inputs at the beginning of the code, but we want to use the function in different context, e.g., validate results the end.
Can a model learn to use a new isolated operation within larger composition? In this task, we train on the isolated operation and compositions without the operation, and test on compositions using the operation. A real- world example of this kind of generalization would be composing new function with others in larger solution, after seeing examples the function used in isolation.
Compose-New-Operatte
Add-Operation- unctionality: Can a model extend its understanding of an operation by drawing on parallels other operations? We omit from the training data some functionality of operation that could be inferred from other context, and test on programs using that functionalityy This task occur when a library function upgraded with new parameter whose behavior can be inferred from analogous parameters in other functions.
These five tasks can be grouped into three themes: (a) length generalization; (b) mix and match concepts (tasks 2 and 3): compose concepts in ways that were not during training; and (c) apply general principles (tasks and 5): adapt to new, updated, or custom APIs.
BENCHMARK CREATION
While Section 2 focused on the netaabbenchmar describing five compositional generalization tasks, this section describes our instantiation of those tasks into compositional generalization datasets for two popular synthesis domains, RobustFill (Devlin al., 2017) and DeepCoder (Balog et al., 2017).
RobustFill. In the RobustFill domain, the objective is to synthesize sequence of string manip- ulation operations from I/O examples, where each example's input a single string. RobustFill program is concatenation of expressions. There are 4 categories of expressions: operations that ex- tract substring from the input (e.g., GetToken (regex, index) ), operations that return a modified version of the input (e.g., ToCase (case)) ), special Compose operation (applying modification operation to the result of another operation), or constant string character. For example, the program GetFromm (* Const ('.") Compose (ToCase (PROPKR), Get oken (WORD, () is

---

Published as a conference paper at ICLR 2024
Algorithm 1 ExeDec: synthesis via decomposition in the execution space.
Note, {aa} is short for [#i,,.... Kn] throughout, where n is the number I/O examples.
1: function EXEDEC( 0,)})
2:
t-1
(,," - (4, O,), vi
3:
4:
while True do
5:
{s(0) } + SUBGOALLODEL o0(h) p(t) + SYNTHESIZERODEL
b. Predict the next execution subgoals Predict the next subprogram
(())))
6:
E EXECUTE(P()) 1,"),, vi
7:
8:
if E = 0 then
Is this the last subprogram?
9:
return COMBINGPROOR.MPPRRTSSPPPP ..... ,(!)
Update (17,)) ..!') represent work that is left to be done (domain-specifie)
(1(++1] (11) t UPDATESPPECFIICATION.""" ,0!0 EE Vi
10:
111+1
concatenation of expressions and transforms the input string "TURING, Alan" into the output string "Alan. Turing". See Appendix A for the full RobustFill DSL, which we extended from the original RobustFill paper (Devlin al., 2017) by adding more operations. Appendix B contains further details about our constructed datasets, including the different compositional generalization splits and the process for generating synthetic programming tasks according to those splits.
DeepCoder. The DeepCoder domain involves manipulation of integer lists in line-by-line pro- gramming style. Tasks have one or more inputs which may be integers or integer lists. Each line of a DeepCoder program applies one DSL operation to inputs or previous variables and assigns the result to a new variable. The result of the last line is the program's 's output. Operations include first-order list operations (Sort, Reverse, and various forms of indexing, slicing, and aggregating) and higher-order operations (Haskell-insphee manipulate lists using one of several hardcoded lambda functions. As example, the program INPUT x1 = Map (++2) x0 | x2 - Sort x1 (where "I" denotes a new line) transforms the input list [5, -4] into the output list [9, 16, 25). See Appendix A for the full DeepCoder DSL
Map, Filter, Count, ZipWith, and Scanil) which
and Appendix B for more details about our instantiation in the DeepCoder domain.
Choice of Domains. Both domains allow to generate large amount of synthetic training data with ground-truth truth decompositions into subprograms. For more realistic code in ceneral-purposs. programming languages, such data collection requires more effort, especially if "natural" decomposi- tions are desired. Beyond the difference in string versus list manipulation, RobustFill and DeepCoder are quite different in other important ways, allowing us to study the compositional generalization of various approaches in different scenarios. First, RobustFill gradually builds an output by combining results of subprograms that are mostly independent, while DeepCoder applies operations repeatedly to the same few objects until the output is reached. In this sense, RobustFill is closer to inverse CAD (Ellis et al., 2019), instantiating complex objects with many fields like dataclasses, or other tasks involving several independent analyses, while DeepCoder is closer to tensor manipulation (Shi et al., 2022a), dynamic programming, or other tasks involving sequences of manipulations or updates applied the same objects. Second, RobustFill uses the DeepCoder involves program states that change due to the new variable bindings on each line, making DeepCoder more complex and closer to realistic programs with exccution states changing over time.
input for each subprogram while
4 PROGRAM SYNTHESIS VIA DECOMPOSITION
In this section we describe our proposed program synthesis method based on exccution decomposition, where the model predicts step-by-step execution subgoals and synthesizes subprograms for each step.
Execution Decomposition (ExeDec). The ExeDec strategy outlined in Algorithm aims to reason about the step-by-step execution behavior of program rather than the code tokens. As in Section 2, we assume that the program is a sequence of one or more subprograms that may be combined later. At each step, to synthesize the next subprogram, first call SubgoalModel that takes I/O
4

---

Published as a conference paper at ICLR 2024
examples and predicts the next execution subgoals, i.e., the output of the next subprogram for each example. Because the subgoal is the desired output at this step, predicting the next subprogram is itself PBE task. Thus, we provide the inputs and subgoals to SynthesizerModel which predicts the corresponding subprogram. Finally, we execute the predicted subprogram and compute an updated specification that describes the work that remains to be done by the rest of the program.
This updated specification is maintained throughout the step-by-step synthesis process. Because the overall program is specified by I/O examples, we use I/O examples for the updated specification as well. Intuitively, the inputs in the updated specification will be the current program state, and the outputs will be the output of the overall task, but the details are slightly different because of specifics of the DSLs. We begin with the original I/O examples for the overall synthesis task, and we update them in a domainn-spccife way as subprograms are synthesized (line 10). For instance, in RobustFill the input for each subprogram is the same as the original input, while the output
becomes smaller as we remove -yrthdy--ytthesizedd prefixes of the output: (I (I((+1)) ol!+1) <
(7.", REMOVEPREFX((O"" always concatenation." For DeepCoder, the input is the full program state (i.e., the set of variables and their values for each example) which is expanded with new variables as subprograms are synthesized,
)); this is because the top level operation in RobustFill programs is
while the output remains constant for each example: (1,4+1) ( + (1 U E oft)). If ExeDec synthesizes subprogram that executes the entire remaining output, there are no more subprograms to synthesize, so the subprograms are combined to form the full synthesized program.
Algorithm 1 describes a single synthesis attempt, but we actually perform a search comprising multiple synthesis attempts running efficiently in parallel using a modified beam search where each beam state is partial rollout of the step-by-step synthesis algorithm. Appendix C has more details.
Model Architecture. Recall from Algorithm that ExeDec relies on two models, the Sub- goalModel and SynthesizerModel. We let both be to-euueee (seq2seq) models, which have been shown to be successful on various natural language (Bahdanau et al., 2016; Vaswani et al., 2017) and program synthesis tasks (Devlin et al., 2017). We choose our seq2seq model to be a Trans- former due to its impressive performance natural language tasks over traditional RNNs (Vaswani et al., 2017). We modify the baseline Transformer architecture to account for the fact that we operate on sets of inputs due to having multiple 1/O examples. We call our model Specification- Tariiion--rrnafoommere
For consistent notation for the two models, we let {X;} be the multi-example input to the transformer and Y its output. Formally, X, = (I, O,) for SubgoalModel and (I, S,) for SynthesizerModel. and Y = [S| Sep, Sz, Sep,.. ..., S, for SubgoalModel and Y = P for SynthesizerModel, where Sep is new token added to our vocabulary to partition the subgoals across examples. Note that subgoals S, and subprogram P are sequences of tokens.
consists of two modules. A Transformer encoder receives the speci- fication { and produces an encoding 6. Following Devlin et al. (2017), our encoder performs double attention on the specification. That is, for each example X,, the encoder performs the op- eration o + Transformer Enconerrrnnoee((e. (X,), where the encoder performs self-attention on input I followed by cross-and cross- attention from the output (either O₂ or S,) to I,. Then, the encoding @ is simply the concatenation across examples ó + Concat( (oncca((())) ()))). Next. a Transformer decoder takes the encoding and autoregressively generates the output loken-by-token. Formally, let Y = [U,, 3/2..... Ve-1] be the output (subgoals or subprogram) generated so far. The decoder predicts the next output token as ye + Transformer Decoderreee $). As described by Vaswani et al. (2017), the Transformer en- coder and decoder both apply stack of self-attention and ferd-forward units. For the SubgoalModel, we use Aligned Relative Attention (ARA), a new technique that helps the model output a sequence of sequences (a subgoal for each I/O example, concatenated together); see Appendix D for details.
Our Precifiattio--Tranffooonn
No-Subgoal Ablation. We also experiment with an ablation of ExeDec that performs step-by-step decomposition but without predicting execution subgoals first, instead directly predicting the next subprogram from the 1/O examples. In Algorithm 1, this ablation is achieved by replacing lines 5 and 6 with single line, p(t) t ComBiNEDMoDEL exccution subgoals. This ablation uses the same model architecture (without ARA) and an analogous
)()))) thus skipping the step of predicting
'If the symthesized subprogram does not execute to a prefix of the current output for all examples, this synthesis attempt cannot succeed due to RobustFill's concatenation of subprograms. Such "invalid" subprograms detected and handled during a beam search.
5

---

Published as a conference paper at ICLR 2024
Composilional Generalization Resulls on Robus(Fill
End-to End Test Accuracy (89
100
46.04
37 56
05
86
02 52
ExeDec
40
ExeDec-Small
Subgoal
Transformer Baseline
Programmer
Tast on Tha ning Distribution
Length Genaral
Compose Differett Concepts
Switch Concept Order
Compose New Operation
Add Operation Functionality
Generalization Average
Compositional Generalization Results on DeepCoder
End End Test Test Accuracy (96)
100
60
40
ExeDec-Small
22
21
19
up
22
Subgoal
5535
83.g
1066
Transformer Baseline
Latent Programmer
50.0
Tast Tre ning Distribution
Length Generalization
Conr pese Different Concepts
Switch Concept Order
Compose New Operation
Add Operation Functionality
Generalization Average
Figure 2: Compositional generalization results with beam size 10. Error bars denote 95% confidence intervals the mean across trials. On both datasets, ExeDec generalizes better than the no-subgoal ablation, while both decomposition variations greatly outperform the Transformer baseline.
beam search. Several prior works (Zohar Wolf, 2018; Ellis et al., 2019; Chen al., 2019) perform synthesis step-by-step, providing execution feedback to the synthesizer after each step to inform future predictions. Our ablation captures essence those approaches adapted to our setting.
Model Training. We generate training problems as described in Section 3. We train the FxeDec and ablation models using decomposed data, that is, based on teacher forcing using Algorithm I. Specifically, for each subprogram in the ground-truth solution, collect (A) the updated specifica- tion based on executing the previous ground-truth subprograms, (B) the subprogram's 's execution result on all examples, and (C) the subprogram itself. Then, train the SubgoalModel to predict (B) given (A), the SynthesizerModel to predict (C) given (B) and the example inputs from (A), and the Com- binedModel to predict (C) given (A). Each model type is trained separately for each generalization task. Appendix E contains more training details, including model sizes and hyperparameters.
EXPERIMENTS
We experiment with Transformers trained from scratch and with LLMs using few-shot prompting.
5.1 TRANSFORMERS TRAINED FROM SCRATCH
These experiments compare ExeDec, version with smaller models called ExeDec-Small the subgoal ablation, Transformer baseline without any decomposition, and Latent Programmer (Hong al., 2021). All models use the same hyperparameters and architecture except: (1) ExeDec-Smal and Latent Programmer use smaller models (details and reasoning in Appendix E), (2) ARA only applies to SubgoalModel, and (3) because the baseline Transformer and Latent Programmer trained entire programs instead of subprograms, but the number of training examples is held constant, they actually see more subprograms during training than our models.
Using compositional generalization datasets (Section 3) and models (Section 4), we ran the different approaches and measured their overall success rate on 1000 test examples per generalization task. We repeated the experiments using 5 different random initializations for model training. Figure shows the results when using a beam size of 10, Appendix contains results with beam size 1, and Appendix G analyzes the accuracy of individual steps.

---

all require Published as a conference paper at ICLR 2024
Discussion. On both domains, ExeDec significantly outperforms the Transformer baseline on every generalization task and in the i..d. setting (testing on the training distribution without any compositional generalization). Specifically, ExeDec achieves +44% higher average compositional generalization than the Transformer baseline on RobustFill and + 18% on DeepCoder, a 4.4x higher success rate. But despite the notable improvements, DeepCoder in particular remains difficult domain with deeply nested operation compositions that obscure the intended computation, while RobustFill has more flat compositional structure that is easier to learn.
Our step-by-step decomposition approach introduces important inductive biases into the approach. By training models on the decomposed data, we teach the models that subprograms can be reasoned about separately. regardless of the compositional patterns present in other subprograms. The SubgoalModel does not see any code tokens and only affected by compositional generalization patterns indirectly (since the distribution over programs affects the distribution over execution traces), and the Synthe- sizerModel only sees code tokens for the current subprogram and cannot reference any compositional patterns that appear when comparing to other subprograms. In contrast, the Transformer baseline sees all compositional patterns in the full programs, making it more likely to overfit to those patterns. The decomposition strategy also encourages our models to understand intermediate program states while the Transformer baseline is not trained with such execution information.
Compared to the no-subgoal ablation, ExeDec achieves higher compositional generalization perfor- mance on a majority of generalization tasks across the two domains, averaging +7% improvement on RobustFill (a 34% reduction in failures) and +-% on DeepCoder (a 1.28x multiplicative improve- ment). This supports our hypothesis that predicting execution states is more robust than predicting code in the compositional generalization setting. ExeDec-Small performs slightly worse than ExeDec (1.4% worse on average and up to 3% worse on any individual generalization task) but ExeDec-Small still significantly outperforms the other approaches overall.
Even though ExeDec performs the best in most situations, the no-subgoal variation is slightly better on DeepCoder's training distribution and GeneraiaGenriiiiatonnnnn Appendix H provides some intuition on "spurious patterns" related to this result. In theory, one could combine the two decomposition variations in an ensemble to get the best of both approaches on unknown test distributions. Finally, we observe that in most cases ExeDec has smaller variance across random initializations than the no-subgoal variation, i.e., ExeDee might be more consistent practice.
As case study, we compare ExeDec, the no-subgoal ablation, and the Transformer baseline on example RobustFill and DeepCoder problems in Appendix I. Through these examples, we discuss some behaviors and observations that clarify the advantages to ExcDec's approach.
5.2 LLM EXPERIMENTS
It is fundamentally difficult to measure compositional generalization in LLMs, because compositional generalization is function of the relationship between the training and test distributions, but LLMs it is not easy to control the pretraining data. However, we have more control in a few-shot prompting setup, as long as we focus on program concepts that cannot have occurred in the pretraining data set. Based on this insight, in these experiments, used our benchmarks measure the compositional generalization ability of PaLM 2 Unicorn (Google et al., 2023) during few-shot prompting for PBE. We the same compositional generalization splits for DeepCoder and RobustFill, except that the few-shot examples and test problems have length at most 3. We make the problems easier because LLMs in general perform poorly on program synthesis tasks specified only through I/O examples, compared to natural language specifications. Within each split we balance the distribution of program lengths as much as possible, 3 and use 200 test problems per generalization task. Each prompt contains a description of the DSL including the available functionality, followed by 4 few-shot examples of PBE tasks and solutions drawn from the training split (different tasks are randomly chosen for different test problems), followed by the specification for test problem (see Appendix J).
To make the tasks better suited LLMs, we transform our DSL programs into Python functions that call a hypothetical dsl library to access the DSL functionality. The RobustFill subprogram GetToken (WORD, 1) becomes dal. GetToken (x, dsl, Tipe. Word, 1), and the DeepCoder
and programs of length least 2, so these tasks have 50/50 split between programs of lengths 2 and 3.
For example, Siaiee-Diiffeet-Commee
7

---

Published as a conference paper at ICLR 2024
Table 1: Compositional generalization results for the LLM experiments. Each cell contains the number of solved tasks out of 200 test problems. For approaches, @ means 1 greedy decoding and @5 means using samples with temperature 0.4. For columns, "None" means no generalization, "Gen. Tasks" refers to the 5 compositional generalization tasks in the order given in Section 2 (consistent with the other figures), and "Avg" is the average across the generalization tasks.
RobustFill Gen. Tasks
DeepCoder Gen. Tasks
DeepCoder-Pyliiee
Approach
None
Avg
None
Avg
None
Gen. Tasks
Avg
Baseline @1
4
4 0
1 0
0
1.0
23
0
1
5
2,4
25
0
11
0
4
3.2
Ablation @1
16
4
0
0
1
6
2.2
31
1
2
13
5
4.8
30
4
12
4
4
4.8
ExeDee @1
21
5
0
0
1
6
2.4
36
2
3
11
10
6.0
46
5
8.4
Baseline @5
15
0
1
2
1.8
36
0
13
6.0
34
8
6.2
Ablation @5
29
7
1
0
4
3.8
51
1
4
18
21
10.4
42
10
11
10.4
ExeDec @
32
5
0
0
5
10
4.0
56
2
5
17
17
9.8
59
5
9
25
12
30
16.2
ds1 ds1. .Map R.lss.SQUARR, x1). For DeepCoder, we alternatively try using Pythonic expressions for all DSL functionality except the Scanll operation, which is difficult to inline; the previous example then becomes x2 [x 2 for X in x1].
subprogram x2
Map (**2) x1 becomes x2
By representing DSL programs Python functions in this way, we enable the LLM to draw upon its general understanding of Python from its pretraining data, while requiring the LLM to use a new Python library from only description of the library along with 4 few-shot examples. This setting mirrors realistic use-cases where a user asks about new, custom, or proprietary library that the LLM was not trained on. Appendix J contains examples of our prompts and Python-style programs. The LLM is allowed to use arbitrary Python, although it usually follows the style in the examples.
We experimented with three prompting approaches analogous to the other experiments:
The baseline approach is to predict the entire solution program in one decoding.
2. The Ablation-style approach predicts the program step-by-step. Given the problem specification and history of previous steps, the LLM predicts the next line of code. We then execute the program- so-far and concatenate the predicted line of code along with its execution results into the history portion of the prompt, which will influence future steps. This stepwise process continues until the desired outputs are reached, the program fails to execute, or budget of 3 steps is exhausted.
3. The ExeDec-style approach is similar, except that at each step, the LLM predicts the next execution subgoal followed by line of code for that step (analogous to calling the SubgoalModel and MynthesizerModel),, Note that the LLM's subgoal prediction might be inconsistent with the predicted code, so in the history of previous steps, we replace the predicted subgoals with the actual execution results (analogous to how the specification is updated in ExeDec). Over multiple steps, this process creates prompt almost identical to that of the Ablation-style approach, except that ExeDec-style has the execution results of step before the code for that step. while the Ablation-styl style has the execution results after the code.
The results are in Table 1. The ExeDec-style prompting strategy leads to the best performance for all no-generalization cases, and all but one case for the generalization average. Also, the ExeDec-style approach significantly improves when programs are written in a more natural form (going from DeepCoder to DeepCoder-Py Pythonic). which is promising sign for its general applicability. For SeppCoder-yythoncc the ExeDec-style approach solves between 40% and 75% more tasks than the next-best approach, considering each combination of no-generalization vs. generalization average and greedy decoding vs. p sampling. But despite these improvements, compositional generalization remains difficult for LLMs. Appendix discusses common failure modes in the LLM experiments.
RELATED WORK
Compositional Generalization. Compositional generalization is well-studied in NLP, with estab- lished benchmarks evaluating the understanding of natural language sentences with compositionally novel structures, either constructed by synthesizing examples based predefined generalization patterns similar to this work (Lake & Baroni, 2018; Bahdanau et al., 2019), or by partitioning i..dd. samples into splits with disjoint compositional structures (Finegan- (Finegan-Dollak al., 2018; Keysers
8

---

Published as a conference paper at ICLR 2024
et al., 2020; Shaw et al., 2021). Our benchmark takes inspiration from SCAN (Lake & Baroni, 2018) and COGS (Kim & Linzen, 2020), which define a taxonomy of compositional patterns in natural lan- guage. While some generalization concepts are similar to those in Section 2. we focus measuring compositional generalization of computer programs using 1/O examples without natural language utterances, whose compositional structures quite different from those in natural language.
To improve compositional generalization in natural language understanding, earlier works have proposed specialized task-dependent neural architectures (Russin et al., 2019; Li al., 2019; Liu et al., 2020; Chen et al., 2020; Herzig & Berant, 2020). More generalized approaches include meta- learning (Lake, 2019; Wang et al., 2021a; Conklin et al., 2021) and data augmentation (Andreas, 2020; Oren et al., 2021: Akyürek et al., 2021; Wang et al., 2021b; Qiu et al., 2022). There have also been recent attempts in improving the compositional generalization capabilities of large language models via representation learning (Furrer et al., 2020; Herzig et al., 2021) and in-context learning (Zhou et al., 2023; Drozdov et al., 2023).
In machine learning for code, some works include length generalization results (Bieber et al., 2020; Balog et al., 2017; Ellis et al., 2019), and Nye et al. (2021) use compositional generalization some experiments, but we study compositional generalization in a much more systematic manner.
Programming by Example. Various techniques have been applied to program synthesis (Gulwani et al., 2017), and recently much attention has focused on machine learning for programming by example (Devlin et al., 2017; Parisotto et al., 2017; Ellis et al., 2021). Many methods incorporate learning to guide the search over programs, such as using learned premise selection (Balog et al., 2017; Odena & Sutton, 2020), syntax- -uitx- search (Yin & Neubig, 2017: Lee et al., 2018), bottom-up search (Shi al., 2022a; Barke al., 2020), two-level search (Nye et al., 2019), and execution-guider synthesis methods (Odena et al., 2020; Shi et al., 2022b).
Multi-step Program Synthesis. Exelec is an instance of multi-step program synthesis, which broadly refers to methods involving multiple calls to (potentially different) models. Execntion-guided synthesis a popular form of this, iteratively generating and refining partial programs using execution information (Zohar & Wolf, 2018; Ellis et al., 2019; Chen et al., 2019; Shrivastava et al., 2021), and some approaches do this with latent representations of the program state (Chen et al., 2021b) or execution traces (Shin et al., 2018). Planning is another form of multi-step synthesis that first generates high-level plans of what the program should do (Nye et al., 2019; Murali et al., 2018: 8; Zhang et al., 2023), sometimes with latent representations of plans (Hong et al., 2021). Our method, ExeDec, draws ideas from both avenues of multi-step synthesis, making plans by predicting subgoals and using step-by st-ppp program execution to guide the search.
7 CONCLUSION
We explored the important aspect of compositional generalization in neural program synthesis. The ability to decompose complex tasks into smaller subtasks is a fundamental skill employed by human programmers, and measuring whether neural program synthesis methods exhibit similar capabilities is crucial for assessing their potential. We introduced a meta-henchmark that characterizes 5 forms of compositional generalization in program synthesis, and we instantiated these generalization tasks in the RobustFill and DeepCoder domains. The findings demonstrate that the ExeDec approach of predicting decompositions of program execution, rather than solely focusing on program syntax, leads to significantly improved compositional generalization for both Transformers trained from scratch and LLMs in few-shot setting. This suggests that incorporating information about the step- st--ppp decomposition and leveraging it in the synthesis of programs can enhance the ability of neural models to tackle more complex tasks. Even so, compositional generalization remains challenging for neural program synthesizers, and our meta meeaabbenchmar can help measure continued progress in this area.
Limitations. One limitation of ExeDec is its need for training dataset with ground-truth decom- positions. Our experiments used synthetic programs with line-by-line decomposition, but perhaps better results could be obtained with a dataset containing more natural decompositions. Furthermore, the by-lne decomposition could be a limitation as programmers often think in larger chunks or hierarchically: Appendix L discusses a potential hierarchical formulation of ExeDec to address this limitation in future work. Lastly, our SubgoalModel predicts tokenizations of objects, but to handle more complex objects, more general MaabgoalModel might instead predict abstractions of objects.

---

Published as a conference paper at ICLR 2024
REPRODUCIBILITY STATEMENT
Our code, datasets, and checkpoints for the Transformer models trained from scratch are available https: / / thub com/ goog 1 s-deepmi htdeemmin/eeeeeeeeeeee ed/exedec. Additionally, Appendix E contains details about model hyperparameters and sizes for the models we trained.
ACKNOWLEDGEMENTS
The authors would like to thank Xinyun Chen, Martin Abadi, Rif Saurous, and the anonymous reviewers for their helpful comments.
REFERENCES
Ekin Akyürek, Afra Feyza Akyürek, and Jacob Andreas. Learning recombine and resample data for compositional generalization. In International Conference on Learning Reprexentations (ICLR), 2021.
Jacob Andreas. Good-enough compositional data augmentation. In Assocation for Computational Linguistics (ACL), 2020.
Jacob Austin, Augustus Odena, Maxwell Nye, Maarten Bosma, Henryk Michalewski, David Dohan, Ellen Jiang, Carrie Cai, Michael Terry, Quoe Le, and Charles Sutton. Program synthesis with large language models. arXiv preprint 1787722 2021.
Dzmitry Bahdanau. Kyunghyun Cho, and Yoshua Bengio. Neural machine translation by jointly learning to align and translate. In International Conference on Learning Representations (ICLR), 2016.
Dzmitry Bahdanau, Harm de Vries, Timothy J. O' O'Donnell, Shikhar Murty, Philippe Beaudoin, Yoshua Bengio, and Aaron C. Courville. CLOOSUR:: Assessing systematic generalization of CLEVR models. arXiv preprint arXiv:/912.05700 2019.
Matej Balog, Alexander L Gaunt, Marc Brockschmidt, Sebastian Nowozin, and Daniel Tarlow. DeepCoder: Learning to write programs. In International Conference on Learning Representations (ICLR), 2017.
Shraddha Barke, Hila Peleg, and Nadia Polikarpova. Just-in-time learning for bottom-up enumerative synthesis. In 2020.
Programming, Systems, Languages, and Applications (OOPSLA),
David Bieber, Charles Sutton, Hugo Larochelle, and Daniel Tarlow. Learning to execute programs with instruction pointer attention graph neural networks. In Neural Information Processing Systems (NeurIPS), 2020.
Mark Chen, Jerry Tworek, Heewoo Jun, Qiming Yuan, Henrique Pondé de Oliveira Pinto, Jared Kaplan, Harrison Edwards. Yuri Burda, Nicholas Joseph, Greg Brockman, Alex Ray, Raul Puri, Gretchen Krueger, Michael Petrov, Heidy Khlaaf, Girish Sastry, Pamela Mishkin, Brooke Chan, Scott Gray, Nick Ryder, Mikhail Pavlov, Alethea Power, Lukasz Kaiser, Mohammad Bavarian, Clemens Winter, Philippe Tillet, Felipe Petroski Such, Dave Cummings, Matthias Plappert, Fotios Chantzis, Elizabeth Barnes, Ariel Herbert-Voss William Hebgen Guss, Alex Nichol, Alex Paino, Nikolas Tezak, Jie Tang, Igor Babuschkin, Suchir Balaji, Shantanu Jain, William Saunders, Christopher Hesse, Andrew N. Carr, Jan Leike, Joshua Achiam, Vedant Misra, Evan Morikawa, Alec Radford, Matthew Knight, Miles Brundage, Mira Murati, Katie Mayer, Peter Welinder, Bob McGrew, Dario Amodei, Sam McCandlish, Ilya Sutskever, and Wojeiech Zaremba. Evaluating large language models trained on code. arXiv preprint arXiv:2107.033. 2021a.
Xinyun Chen, Chang Liu, and Dawn Song. Exccution-guided neural program synthesis. In Interna- tional Conference on Learning Representations (ICLR), 2019.
Xinyun Chen, Chen Liang, Adams Wei Yu, D. Song, and Denny Zhou. Compositional generalization via neural-symbolic stack machines. In Neural Information Processing Systems (NeurIPS), 2020.
10

---

Published as a conference paper at ICLR 2024
Xinyun Chen, Dawn Song, and Yuandong Tian. Latent execution for neural program synthesis beyond Nomain-speciffe languages. In Neural Information Processing Systems (NeurIPS), 2021b.
Noam Chomsky, Syntactic Structures. Mouton de Gruyter, 1957.
Henry Conklin, Bailin Wang, Kenny Smith, and Ivan Titov. Meta-learning compositionally generalize. In Association for Computational Linguistics and International Joint Conference on Natural Language Processing (ACL/IJCNLP), 2021.
Róbert Csordás, Kazuki Irie, and Jürgen Schmidhuber. The devil is in the detail: Simple tricks improve systematic generalization of transformers. In Empirical Methods in Natural Language Processing (EMNLP), 2021.
Jacob Devlin, Jonathan Uesato, Surya Bhupatiraju, Rishabh Singh, Abdel-rahman Mohamed, and Pushmeet Kohli. RobustFill: Neural program learning under noisy I/O. In International Conference on Machine Learning (ICML),011)
Andrew Drozdov, Nathanael Schärli, Ekin Akyürek, Nathan Scales, Xinying Song, Xinyun Chen, Olivier Bousquet, and Denny Zhou, Compositional semantic parsing with large language models. In International Conference on Learning Representations (ICI.R), 2023.
Kevin Ellis, Maxwell I. Nye, Yewen Pu, Felix Sosa, Josh Tenenbaum, and Armando Solar-Lezama. Write, execute, assess: Program synthesis with a REPL. In Neural Information Processing Systems (NeurIPS), 2019.
Kevin Ellis, Catherine Wong, Maxwell I. Nye, Mathias Sablé-Meyer, Lucas Morales, Luke B. Hewitt, Luc Cary, Armando Solar-Lezama, and Joshua B. Tenenbaum. DreamCoder: bootstrapping inductive program synthesis with wake-sleep library learning. In Programming Language Design and Implementation (PLDI), 2021.
Catherine Finegan- Dollak, Jonathan K. Kummerfeld, Li Zhang, Karthik Ramanathan, Sesh Sadasivam, Rui Zhang, and Dragomir Radev. Improving text-to-SQL evaluation methodology. In Assocation for Computational Linguistics (ACL), 2018.
Daniel Furrer, Marc van Zee, Nathan Scales, and Nathanael Schärli. Compositional generalization in semantic parsing: Pre-training vs. specialized architectures. arXiv preprint arXiv:2007.0888 08970, 2020.
Google, Rohan Anil, Andrew M. Dai, Orhan Firat, Melvin Johnson, Dmitry Lepikhin, Alexandre Passos, Siamak Shakeri, Emanuel Taropa, Paige Bailey, Zhifeng Chen, Eric Chu, Jonathan H. Clark, Laurent El Shafey, Yanping Huang, Kathy Meier-Hellstern, Gaurav Mishra, Erica Moreira, Mark Omernick, Kevin Robinson, Sebastian Ruder, Yi Tay, Kefan Xiao, Yuanzhong Xu, Yujing Zhang, Gustavo Hernandez Abrego, Junwhan Ahn, Jacob Austin, Paul Barham, Jan Botha, James Bradbury, Siddhartha Brahma, Kevin Brooks, Michele Catasta, Yong Cheng, Colin Cherry, Christopher A. Choquette-Choo, Aakanksha Chowdhery, Clément Crepy. Shachi Dave, Mostafa Dehghani, Sunipa Dev, Jacob Devlin, Mark Díaz, Nan Du Ethan Dyer, Vlad Feinberg, Fangxiaoyu Feng, Vlad Fienber, Markus Freitag, Xavier Garcia, Sebastian Gehrmann, Lucas Gonzalez, Guy Gur-Ari, Steven Hand, Hadi Hashemi, Le Hou, Joshua Howland, Andrea Hu, Jeffrey Hui, Jeremy Hurwitz, Michael Isard, Abe Itycheriihh, Matthew Jagielski, Wenhao Jia, Kathleen Kenealy, Maxim Krikun, Sneha Kudugunta, Chang Lan, Katherine Lee, Benjamin Lee, Eric Li, Music Li, Wei Li, YaGuang Li, Jian Li, Hyeontack Lim, Hanzhao Lin, Zhongtao Liu, Frederick Liu, Marcello Maggioni, Aroma Mahendru, Joshua Maynez, Vedant Misra, Maysam Moussalem. Zachary Nado, John Nham, Eric Ni, Andrew Nystrom, Alicia Parrish, Marie Pellat, Martin Polacek, Alex Polozov, Reiner Pope, Siyuan Qiao, Emily Reif, Bryan Richter, Parker Riley, Alex Castro Ros, Aurko Roy. Brennan Saeta, Rajkumar Samuel, Renee Shelby, Ambrose Slone, Daniel Smilkov, David R. So, Daniel Sohn, Simon Tokumine, Dasha Valter, Vijay Vasudevan, Kiran Vodrahalli, Xuezhi Wang, Pidong Wang, Zirui Wang. Tao Wang, John Wieting, Yuhuai Wu, Kelvin Xu, Yunhan Xu, Linting Xue, Pengcheng Yin, Jiahui Yu, Qiao Zhang, Steven Zheng, Ce Zheng, Weikang Zhou, Denny Zhou, Slay Petrov, and Yonghui Wu. PaLM technical report. arXiv preprint arXiv:2305. 10403, 2023.
11

---

Published as a conference paper at ICLR 2024
Yu Gu, Sue Kase, Michelle Vanni, Brian Sadler, Perey Liang. Xifeng Yan, and Yu Su. Beyond IID: three levels of generalization for question answering on knowledge bases. In The Web Conference (WWW), 2021.
Sumit Gulwani. Automating string processing in spreadsheets using input-output examples. In Principles of Programming Languages (POPL), 2011.
Sumit Gulwani, Oleksandr Polozov, and Rishabh Singh. Program Synthesis, volume 4 of Foundations and Trends in Programming Languages. 2017.
Jonathan Herzig and Jonathan Berant. Span-based semantic parsing for compositional generalization. In Empirical Methods in Natural Language Processing (EMNLP), 2020.
Jonathan Herzig, Peter Shaw, Ming-Wer Wei Chang, Kelvin Guu, Panupong Pasupat, and Yuan Zhang. Unlocking compositional generalization in pre-trained models using intermediate representations. arXiv preprint arXiv:2104.07470 2021.
Joey Hong, David Dohan, Rishabh Singh, Charles Sutton, and Manzil Zaheer. Latent programmer: Discrete latent codes for program synthesis. In International Conference on Machine Learning (ICML), 2021.
Daniel Keysers, Nathanael Schärli, Nathan Scales, H. Buisman, Daniel Furrer, Sergii Kashubin, Nikola Momchev, Danila Sinopalnikov, Lukasz Stafiniak, Tibor Tihon, D. Tsarkov, Xiao Wang, Marc van Zee, and O. Bousquet. Measuring compositional generalization: A comprehensive method on realistic data. In International Conference on Learning Representations (ICLR), 2020.
Najoung Kim and Tal Linzen. COGS: compositional generalization challenge based semantic interpretation. In Empirical Methods in Natural Language Processing (EMNLP), 2020.
Brenden M. Lake. Compositional generalization through meta sequence-to--sqqunce learning. In Neural Information Processing Systems (NeurIPS), 2019.
Brenden M. Lake and Marco Baroni. Generalization without systematicity: On the compositional skills of peuuence-to-sequeeee recurrent networks. In International Conference on Machine Learning (ICML), 2018.
Woosuk Lee, Kihong Heo, Rajeev Alur, and Mayur Naik. Accelerating search-based program synthe- sis using learned probabilistic models. In Programming Language Design and Implementation (PLDI), 2018.
Yuanpeng Li, Liang Zhao, Jian Wang, and Joel Hestness. Compositional generalization for primitive substitutions. In Empirical Methods Natural Language Processing and International Joint Conference on Natural Language Processing (EMNLP-JCNNLP), 2019.
Yujia Li, David H. Choi, Junyoung Chung, Nate Kushman. Julian Schrittwieser, Rémi Leblond, Tom Eccles, James Keeling, Felix Gimeno, Agustin Dal Lago, Thomas Hubert, Peter Choy, Cyprien de Masson d' Autume, Igor Babuschkin, Xinyun Chen, Po-Sen Huang, Johannes Welbl, Sven Gowal, Alexey Cherepanov, James Molloy, Daniel Mankowitz, Esme Sutherland Robson, Pushmeet Kohli, Nando de Freitas, Koray Kavukcuoglu, and Oriol Vinyals. Competition-level 2022.
code generation with AlphaCode. Science,
Qian Liu, Shengnan An, Jianguang Lou, B. Chen, Zeqi Lin, Yan Gao, Bin Zhou, Nanning Zheng, and Dongmei Zhang. Compositional generalization by learning analytical expressions. In Neural Information Processing Systems (NeurIPS), 2020.
Vijayaraghavan Murali, Letao Qi, Swarat Chaudhuri, and Chris Jermaine. Neural sketch learning for conditional program generation. In International Conference on Learning Representations (ICLR), 2018. 8.
Maxwell Nye, Luke Hewitt, Joshua B. Tenenbaum, and Armando Solar-Lezama Learning to infer program sketches. In International Conference Machine Learning (ICML), 2019.
12

---

Published as a conference paper at ICLR 2024
Maxwell Nye, Yewen Pu, Matthew Bowers, Jacob Andreas, Joshua B. Tenenbaum, and Armando Solar-Lezamal Representing partial programs with blended abstract semantics. In International Conference Learning Representations (ICLR), 2021.
Augustus Odena and Charles Sutton. Learning to represent programs with property signatures. In International Conference Learning Representations (ICLR), 2020.
Augustus Odena, Kensen Shi, David Bieber, Rishabh Singh, Charles Sutton, and Hanjun Dai.
BUSTLE: Bottom-up program synthesis through learning-guidee guided exploration. In International Conference on Learning Representations (ICLR), 2020.
Inbar Oren, Jonathan Herzig, and Jonathan Berant. Finding needles in a haystack: Sampling structurally-diverse training sets from synthetic data for compositional generalization. In Empirical Methods in Natural Language Processing (EMNLP), 2021.
Emilio Parisotto, Abdel-rahman Mohamed, Rishabh Singh, Lihong Li, Dengyong Zhou, and Pushmeet Kohli. Neuro-symbolic program synthesis. In International Conference on Learning Representa- tions (ICLR), 2017.
Nick Parlante. CS106A: Programming methodologies. Course at Stanford University, 2022.
Linlu Qiu, Peter Shaw, Panupong Pasupat, Pawel Krzysztof Nowak, Tal Linzen, Fei Sha, and Kristina Toutanova. Improving compositional generalization with latent structure and data augmentation. In North American Chapter of the Association for Computational Linguistics: Human Language Technologies (NAACL-HLT), 2022.
Jake Russin, Jason Jo, Randall O' ReRilly, and Yoshua Bengio. Compositional generalization in a deep seq2seq model by separating syntax and semantics. arXiv preprint arXiv: 2019.
Peter Shaw, Jakob Uszkoreit, and Ashish Vaswani. Self-attention with relative position representations. In North American Chapter of the Association for Computational Linguistics (NAACL), 2018.
Peter Shaw, Ming-Wei Wei Chang, Panupong Pasupat, and Kristina Toutanova. Compositional generaliza- tion and natural language variation: Can a semantic parsing approach handle both? In Association for Computational Linguistics and International Joint Conference on Natural Language Processing (ACL/IJCNLP), 2021.
Kensen Shi, Jacob Steinhardt, and Percy Liang. FrAngel: Component-based synthesis with control structures. Proceedings of the ACM on Programming Languages (PACMPL), 3(P0))))199,, 2019.
Kensen Shi, David Bieber, and Rishabh Singh. TF-Coder: Program synthesis for tensor manipulations. ACM Transactions on Programming Languages and Systems (TÓPLAS), 44(2):1-36, 2022a.
Kensen Shi, Hanjun Dai, Kevin Ellis, and Charles Sutton. CrossBeam: Learning to search in
bottom-up program synthesis. In International Conference on Learning Representations (ICLR), 2022b.
Richard Shin, Illia Polosukhin, and Dawn Song. Improving neural program synthesis with inferred execution traces. In Neural Information Processing Systems (NeurIPS), 2018.
Disha Shrivastava, Hugo Larochelle, and Daniel Tarlow. Learning combine per-example solutions for neural program synthesis. In Neural Information Processing Systems (NeurIPS), 2021.
Ilya Sutskever, Oriol Vinyals, and Quoc V. Le. Sequence to sequence learning with neural networks. In Neural Information Processing Systems (NeurIPS), 2014.
Ashish Vaswani, Noam Shazeer, Niki Parmar, Jakob Uszkoreit, Llion Jones, Aidan N. Gomez, Lukasz Kaiser, and Illia Polosukhin. Attention is all you need. In Neural Information Processing Systems (NeurIPS), 2017.
Bailin Wang, Mirella Lapata, and Ivan Titov. Meta-leariing for domain generalization in semantic parsing. In North American Chapter of the Association for Computational Linguistics: Human Language Technologies (NAACI-HI.T), 2021a
13

---

Published as a conference paper at ICLR 2024
Bailin Wang, Wenpeng Yin, Xi Victoria Lin, and Caiming Xiong. Learning to synthesize data for semantic parsing. In North American Chapter of the Association for Computational Linguistics: Human Language Technologies (NAACL-HLT), 2021b.
Pengcheng Yin and Graham Neubig. A syntactie neural model for general-purpose code generation. In Assocation for Computational Linguistics (ACL), 2017.
Shun Zhang, Zhenfang Chen, Yikang Shen, Mingyu Ding, Joshua B. Tenenbaum, and Chuang Gan. Planning with large language models for code generation. In International Conference on Learning Representations (ICLR), 2023.
Denny Zhou, Nathanael Schärli, Le Hou, Jason Wei, Nathan Scales, Xuezhi Wang, Dale Schuurmans, Claire Cui, Olivier Bousquet, Quoe V. Le, and Ed H. Chi. Least-to-most prompting enables complex reasoning in large language models. In International Conference on Learning Representations (ICLR), 2023.
Amit Zohar and Lior Wolf. Automatic program synthesis of long programs with a learned garbage collector. In Neural Information Processing Systems (NeurIPS), 2018.
14

---

Published as a conference paper at ICLR 2024
Appendices
A ROBUSTFILL AND DEEPCODER DSLS
Figure contains the DSL for the RobustFill experiments. See Devlin et al. (2017) for description of what the operations do. We add the operations Substitute, SubstituteAl1, which replace the Tth occurrence (or all occurrences) of regex with character and Remove, RemoveAll, which remove the 7h occurrence (or occurrences) regex v, to increase expressivity of our DSL.
Figure 4 shows the DSL used for the DeepCoder experiments. The operations are exactly as described Balog et al. (2017).
Program P = Concat(ei, e2....)
Expression e = m | ConstStz(c)
Compose my (mm2 m(s)
Substring SubStr(k, ka) GetSpan(rr.i,, bi, 12, GetToken(r,
(etUpptor)) GetFrom(r)
Modification m
ToCase(a) (eplace((), Trim() GetFirst GetAAl(r)
Suustituteer, Substituteell(f: Remmove i) RemoveAl1(r)
Regex NUMBER WORD ALPHANUM ALL.CAPS PROFER_CASE LOWER DIGIT CEAR
Case ALL.CAPS PROFER_CASE LOWER
Position & = 100 | 99 ... 0 1 2 ... 100
Index = 5 - 4 ... 1 ... 15
Boundary b = START END
Character e = A
Z a
10 1918
Delimiter 5 6, () ():()/
Figure 3: The DSL for string transformation tasks in the RobustFill domain, slightly modified from Devlin et (2017) add more functionality.
Program P = i1; :;;; a2;
Initialization = INPUT
Assignment v / | <- h
First-Order Operation f = Heac(() Last(l) AAcesss(n.I) Minimun(()) Maximum(I)) Sum(l)
Take((, I) Drop(n, Reverse(() (oot (I)
Higher-Order Operation h = Map(X,1) Filter(8,1) Count(3. thtpiithhE,,,1 Scan11
int + int Lambda A
= (+1) (-1) (+2) (/2) (+(-1)) (*+2) (+3) (/3) (+4) (/4)
int bool Lambda 3
(> 0) [ (%2 = 0) (%2 = 1)
(int, int) int Lambda Σ
(+) (+) (min) (max)
Integer Variable n
=
List Variable =
Variable Name v = 21 12
Figure 4: The DSL for integer and list manipulation tasks the DeepCoder domain, originally proposed in Balog et al. (2017).
15

---

Published as a conference paper at ICLR 2024
B ROBUSTFILL AND DEEPCODER BENCHMARK DETAILS
RobustFill. To create task for our RobustFill datasets, we first sample random input strings up to 20 characters, one string for each of 4 examples. We then sample a program according to the train or test distribution for the generalization task (as described below), such that the program executes successfully on the inputs to form the example outputs. Due to the concatenation structure of RobustFill programs, we treat each concatenated expression as a subprogram, and recall that we denote the length of program to be the number of subprograms.
For Length- Generalization, we train on programs of length to 6 inclusive and test on programs of length 7 to 10. For into a substring concept and all of the modification operations plus constant strings as a non non-substring concept (the Compose operation is omitted), using programs of length 2-6 for both train and test. We use the same lengths and concepts for Pritch-Connept-O0 substring concept for the first half of the parts and only the non-substring concept for the latter half, and test tasks have the ordering reversed. For Compose-Newy- New-Operation, 25% of training tasks are length programs containing only a Compose operation, the remainder of the training tasks are length 2-6 programs without Compose, and we test on length 2-6 programs that use Compose. For Add- Operation- Inperation-Functiinn Functionality, all tasks are length 1-6 programs, we train on those where a substring operation is not used within a Compose operation, and we test on programs where substring operation used within a Compose operation.
we group together all of the substring operations
where training tasks use only the
DeepCoder. For DeepCoder, we treat each non-input line subprogram, so the example program above has length? 2. We use 3 I/O examples, at most 2 inputs, lists with at most 5 elements, and integers between -50 and 50 inclusive. For Lenggh-Gennrallizttion I to 4 and test on length 5. For Compose-Different Conceeps and Switch- Concept-Order we use programs of length to 4 and split the operations into a concept containing all first-order operations plus the Map operation, and another concept containing all remaining higher-order operations. For Compose-New- Operation, 25% of training tasks are length programs containing only Scanll Neaposs--ee-OOpeaationn
train programs of length
operation, the remainder of training tasks are length 2-4 programs without Scanl 1, and we test on length 2-4 programs that Scanl1. For Add Opperation-Functioniii
all tasks are length 1-4 programs, Scanil is only used with the lambdas (-) and (min) during training, and we test on tasks where Scanll used with the other lambdas (+), (*), and (max).
The program sampling procedure that we used for RobustFill ensures that the ground-truth program for a test task is within the test distribution over programs. However, the task might actually have a different solution within the train distribution. Then, solving this test task is not necessarily signal of generalization." 4 To address this, we construct the DeepCoder dataset more carefully as follows. We sample random inputs as hefore. Then, we perform an exhaustive enumerative search of all programs in the train distribution up to a maximum length, and similarly for programs in the test distribution. As result, we can identify all minimal- solution programs for a given task (if it is solvable by any program up to the maximum enumerated length). Finally, we sample training tasks among those where there exists minimal- solution program in the train distribution, and test tasks among those where all minimal- length solutions are in the test distribution."
C BEAM SEARCH DURING EXEDEC
Section 4 and Algorithm describe single synthesis attempt, but we design beam search process to run multiple synthesis attempts efficiently in parallel.
Our goal is the same as in traditional beam search (Sutskever et al.. 2014), which to output sequences that maximize a score function. Formally, a candidate sequence C' at step t is a sequence of execution subgoals and subprograms C [[5(") }, p(1) ..... (5(")) }, p(.) As notation, let ((U)) denote the prefix of C' up and including the j-th subprogram p()), The score for candidate
"This issue is far less prevalent in the RobustFill dataset due to the concatenation program structure reducing the number different programs that solve a task. "Note that it is still possible for test task to he solved with longer program in the train distribution, but detecting these cases in general is extremely difficult.
16

---

Published as a conference paper at ICLR 2024
sequence C' is given by
Score(C) Σ
(core((5,))) Score(Pl)) + Valid
j=l
Here, since both Model and SynthesizerModel in ExeDec are autoregressive sequence models (see Section for more details), they can produce token sequences (either set of subgoals or a subprogram) with their corresponding prg-oabbbilitiss which we use as the score function, ie., Score( (5, = log p(5))) {(1,5) H) and Score(P(i) = log (())) {(I,)) s{ By default, VCl) = O unless (0) fails to meet some required conditions. First, we set Valid(C())) -oo if any subgoal or subprogram in CG) is token sequence that does not parse, or if any subprogram does not execute successfully. We also check whether (G) leads to unique program functionality within the beam of k candidate sequences. Note that different candidate sequences can result in the same subprograms even if the subgoals are different, and furthermore, combining different subprograms might result in full programs with the same functionality that are practically equivalent for future steps. Therefore, set (Cli) -co for all candidate sequences in the beam with corresponding program functionality equivalent to that of another higher-scoring candidate sequence in the beam. Finally, domain-specifie checks may determine that the candidate sequence (() is unlikely to result in successful program in later steps, or that some computation limit such as a maximum number of steps is reached. In any case, an "invalid" beam element will drop out of the beam at the next step, freeing space in the beam for expansions of other surviving beam elements.
Note that we do not perform separate beam searches for each call to a model, since an isolated beam search would start with single empty beam element with score O. Instead, we perform single long beam search throughout Algorithm where each beam element is a candidate sequence C' with score Score C'). Model calls can be seen as "extending" the ongoing beam search, adding more tokens to the existing candidate sequences while maintaining their scores.
D ALIGNED RELATIVE ATTENTION FOR THE SUBGOALMODEL
In the Specification- Transformer (Section 4), we use relative attention (Shaw et al., 2018), i.c., representations of relative positions (distances between positions) instead of absolute positions of tokens. This improves Transformer performance, particularly in length generalization (Shaw et al., 2018; Csordás al., 2021). However, unlike the other models, our SubgoalModel actually predicts sequence of sequences, i.e., a subgoal for each I/O example, concatenated together. Thus, the relative position between subgoal S; and I/O encoding & is not consistent for every example index so a naive relative position embedding would not represent consistent information across examples. To remedy this, we propose aligned relative attention (ARA), which alters the "positions" of subgoal tokens in the relative distance calculation. Specifically, we increment the current position by 1 for each token during subgoal prediction as usual, but when starting a new subgoal S we set the current position to the position of o; This ensures that the relative position between the beginnings of S; and 6; is always O. ARA only applies to the SubgoalModel to help it perform the sequence-of prediction, and is not intended to address compositional generalization directly.
E TRAINING DETAILS
For the experiments involving Transformer models trained from scratch (Section 5.1). we performed a small hyperparameter search varying the learning rate and model size, choosing single setting that performed well on training metrics across generalization tasks and model types. We used an embedding dimension of 512, hidden dimension of 1024, 3 layers, and 4 attention heads. For relative attention, we use 32 buckets for relative position embeddings, with bucket boundaries placed logarithmically given the maximum relative distance which is computed based on the lengths of the input and output sequences. We train with the Adam optimizer with a learning rate of 2 x 10-4 with linear warmup for 16,000 steps and square root decay, with a batch size of 128 and 500K training steps, using fresh synthetic training data without repeating examples. Training took about day for RobustFill (or about 5 hours for DeepCoder) with 8 TPU v2 accelerators per model.
In our experiments, some models have different sizes (with the other hyperparameters held constant):
17

---

Published as a conference paper at ICLR 2024
ExeDec, the no-subgoal ablation, and the Transformer baseline all embedding dimension of 512 and hidden dimension of 1024, as selected from the hyperparameter search mentioned above.
FxeDec-Small uses embedding dimension of 360 and hidden dimension of 720, such that the total number of parameters between the SubgoalModee and SynthesizerModel is approximately equal to the number of parameters in the no-subgoal ablation use one model each. ExeDec's ' code solution only comes from the SynthesizerModel, while the SubgoalModel's predictions do not show up anywhere in the solution and only encourage the SynthesizerModel to think about the next subgoal instead of the end goal. Thus, compared to the ablation and baseline, ExeDec holds the SynthesizerModel size constant to compare the two modes of thinking, while ExeDec-Small holds the total number of parameters constant to verify that the improvements not only due extra parameters in the SubgoalModel.
in the bascline, which only
Latent Programmer uses a smaller embedding dimension of 256 and hidden dimension of 512 because ran into out-of-memory issues when using the Latent Programmer's training script which trains two models at once. Our trained Latent Programmer models are still larger than those reported in the Latent Programmer paper leading to corresponding performance increase, reaching 76% accuracy on no-generalization RobustFill compared to 57 % reported in the Latent Programmer paper.
Additionally, for Latent Programmer, we performed a separate hyperparameter search varying the learning rate and number of pretraining steps. We chose a learning rate of 5 x 10 for RobustFill and 10-4 for DeepCoder, and 20,000 pretraining steps for both datasets. We use beam size of 10 and a latent beam size of 3, as in the Latent Programmer paper. (For experiments with beam size of 1, the latent beam size also 1.) All other settings were kept the same as for the other models.
For DeepCoder, the ground-truth training programs have variable names chosen randomly among fixed of possible names. If the variable names were used in a canonical order instead, the models would be unable to predict subprograms using variable names unseen during training, is required for length generalization. When predicting a subprogram, the model only predicts the right hand side of the assignment, which test time is assigned new variable name using canonical ordering.
F BEAM SIZE RESULTS FOR MODELS TRAINED FROM SCRATCH
Figure 2 in Section 5.1 shows detailed results for all generalization tasks, using beam size 10, We also performed experiments with beam size summarized below in Table 2.
Table 2: Results for beam size and beam size 10 (end-to-end test accuracy as percentages). "NoGen" refers to the case where no compositional generalization is required, while "GenAvg" refers to the average across the compositional generalization tasks.
RobustFill
DeepCoder
Beam Size
Beam Size 10 GenAvg
Beam Size
Beam Size 10 NoGen
Approach
NoGen
GenAvg
NoGen
NoGen
GenAvg
GenAvg
ExeDee
81.4
73.1
95.5
87.0
39.1
8.4
61.2
23.1
ExeDec-Small
78.7
71.2
94.4
85.9
36.1
7.7
58.4
21.4
Ablation
79.5
63.8
94.9
80.2
39.9
5.6
64.7
18.1
Transformer
83.7
33.9
90.9
42,4
50.7
4.9
53.6
5.7
Latent Programmer
66.0
26.3
76.1
33.7
40.5
2.4
46.5
3.5
We observe that ExeDec achieves the highest generalization average, for both RobustFill and Deep- Coder and for both beam size and 10. Additionally, for both no-generalization and average generalization, the baseline Transformer's performance does not improve that much going from beam size 1 to 10. On the other hand, ExeDec improves significantly more from beam size to 10, showing the effectiveness of our modified beam search (Appendix C) that enables exploring different solution routes by planning in the execution space.
18

---

Published as a conference paper at ICLR 2024
G SINGLE-STER ACCURACY
To gain more insight into the step-by-step synthesis process, we measured the "single-step accuracy" for ExeDec's SubgoalModel and SynthesizerModel. and the CombinedModel from the no-subgoal ablation. More specifically, for a single step in a trajectory that matches the ground-truth so far, how often does the Sudg predict subgoals exactly matching the ground -ruth ones (for all I/O examples) with single greedy decoding? And, given ground-trute -ruth trajectory so far, how often does the SynthesizerModel ModdinedModel predict program whose behavior matches the ground-truth subprogram? The single-step accuracy results are in Table 3.
Table 3: Single-step accuracy percentages.
RobustFill Synthesizer
DeepCoder Synthesizer
Generalization Task
Subgoal
Combined
Subgoal
Combined
No Generalization
97.7
97.1
94.9
55.8
98.9
64.4
Length-Generalian Generalization
97.2
96.4
94.0
31.6
96.4
41.9
Compose- Diifeeeet--fft------e Different-Concepts
95.3
98.9
90.5
38.0
94.3
40.0
Brach--onncet-OOeee Brappos--ew--peratti Add-Operation--Fune Funciionally
90.8
98.9
87.4
16.4
77.8
17.9
93.9
94.0
84.4
40.8
91.3
44.4
94.0
84.4
82.3
40.3
60.0
41.5
Note that the single-step accuracy metric is particularly low for the SubgoalModel and Combined- Model on DeepCoder hecause 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 need to have super high accuracy in order for ExeDec to achieve good end-to-end results, because the SynthesizerModdl can ignore slight errors in the subgoals and still produce a program that behaves as closely as possible while using only DSL operation. We have seen many concrete cases of the SyndhesizerModel being given a slightly incorrect subgoal and then producing the correct subprogram anyway, which disagrees with the subgoal but correctly makes progress overall.
H INTUITION OF SPURIOUS PATTERNS
In Figure 2, FxeDec sometimes performs worse than the no-subgoal ablation in Gnngh--Genrrlliattion and Switch- Saatchh-Coneet-Orreee while ExeDee performs much better in Drippos-DDiffrentt Compose-Nett Neeusse-ee-ooe Nee-Operation. For Add-Ope add-Operation- O ExeDec and the no-subgoal ablation have a much smaller improvement over the Transformer bascline, especially in RobustFill. These observations may be explained by analyzing the different kinds of "spurious patterns" that arise in the various compositional generalization splits:
and
For Length-Generalizatie Generalization and Switch- Concept- Order, the index of the current subprogram carries major implications in the training distribution, for example, "the problem should be almost solved by now" or "we must use this category of operation". However, these implications are drastically changed in the test distribution, leading to spurious pulterns that may lead to poor performance on the test split. The Transformer bascline is aware of the length of the prediction so far, so can be easily confused by this distribution shift - and indeed, it performs particularly poorly 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 through the program state. For these tasks, ExeDec and the no-subgoal ablation have relatively similar performance but greatly outperform the Transformer baseline.
these
only indirectly provided to the models
For Compose- Diffeeret-fff Different-Concepts and Compose-New- Metee--ppraaton, the spurious patterns arise from comparison to what work needs to be done outside the current subprogram, for example, "this subprogram uses the same category operation as the other subprograms" or "this subprogram can use operation X only 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 more shielded from these spurious patterns because its SynthesizerModel only the I/O specification for the current subprogram (provided
19

---

Published as a conference paper at ICLR 2024
that the Mode predicts the correct subgoals). This difference may explain why ExeDec has a larger performance improvement over the no-subgoal ablation for these generalization tasks. For Add-Operation-FFe intrratioon-unctionalli the spurious pattern is actually 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 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.)
I ALGORITHM COMPARISON CASE STUDY
RobustFill. Figure 5 and Figure 6 compare how ExeDec, the no-subgoal ablation, and the Trans- former baseline perform on two example problems from the RobustFill DSL, under the Compose- New-Operation generalization task where models were not trained on composed programs (other than length-l programs) that use the compose operation. A beam size of (greedy decoding) is used for simplicity. In the figures, subprograms and execution results are colored red if they are incorrect. Portions of the final programs are colored yellow if they do execute correctly but implement the desired functionality suboptimally, i.e., with more subprograms than necessary.
For both example problems, ExeDec successfully solves the problem using a minimal-length program that is within the test distribution of the compositional generalization task, showing successful generalization. However, the no-subgoal ablation does not perform as well. In Figure 5, it uses the Compose operation incorrectly because, due to the Compose-New New-Operation task, it has never been trained to use Compose to produce prefix of the output. This is not an issue for ExeDec because the prefixes are provided by the SubgoalModel. In Figure 6, the ablation predicts a correct but suboptimal program in the training distribution, replacing Compose operation with three separate steps. The Transformer baseline is comparatively the worst, predicting incorrect programs in the training distribution for both problems, showing a clear inability to compositionally generalize.
DoepCoder. Figure 7 shows a similar comparison between the three approaches, this time on a DeepCoder list manipulation problem under the Compose-Diffe Dilfereetff-rrnnie Conccepss generalization task. For this generalization task, we partition the DSL operations into two groups or "concepts" - one concept contains the higher-order operations Scanl1, Filter, Count, and 2ipWith, while the other concept contains all of the first-order operations". The training problems have Homimall-ennghe ground-truth programs that only compose operations within the same concept, while test problems require mixing operations from different concepts to achieve a minimal-length solution program.
The problem in Figure 7 is solved using operations from both concepts: Scanll is higher-order while Take and Sort are first-order operations. The Transformer baseline fails to solve this problem. correctly uses Scanll as the first step but incorrectly continues to use higher-order operations. This behavior makes sense because the model was trained on programs showing similar pattern, and it does not deviate from the pattern because this approach is not compositionally general.
Similarly, the no-subgoal ablation correctly uses Scan-: in the first step but also continues to higher-order operations in subsequent steps until eventually the program fails to typecheck. We observe that, after successfully using Scanll in the first subprogram, the updated specification actually describes a problem with a solution program within the training distribution (using first- order operations Take and Sort from the same concept). So, why is the ablation unable solve the updated specification, even though the SynthesizerModel is not directly conditioned on the previous subprograms like the Transformer baseline is? We hypothesize that the SynthesizerModel recognizes from the specification that x2 was computed by applying a Scan.11 operation to x0, and thus according to patterns seen during training, the model inclined to continue using higher-order operations. This hypothesis is supported by the fact that the ablation, as well as ExeDec and the baseline, all correctly solve a simplified version of this problem where the input x is replaced with the result of the first subprogram, x2 Scanl1 (+) x0, such that the Scanl1 portion is "already computed" but not in a way visible from the specification. other words, the ablation succeeds for the simplified problem because it is now unable to refer to previous subprograms.
'The concept with first-order operations also contains the higher-order operation Map, to better balance the number of different program functionalities obtainable within each concept.
20

---

Published as a conference paper at ICLR 2024
In contrast, ExeDec successfully solves the problem with minimal-length solution that switches between concepts. Note that its Synthesizer.Model cannot directly or indirectly reference previous subprograms. The SubgoalModel can indirectly refer to previous subprograms by examining the specification, but it generally less susceptible to spurious compositional patterns. For example, the ablation's SynthesizerModel might learn the pattern "predict operation in the same concept as previously" which is very easy for a neural model to recognize and implement, whereas it is more difficult for ExeDec's s SubgoalModel to learn the pattern "predict subgoal that is implementable with an operation in the same concept as previously". This provides some intuition for why ExeDec more compositionally general overall.
21

---

Published as a conference paper at ICLR 2024
RobustFill Example Problem 1
Specification:
("alan Turing1 "
TURING, Alan"),
("21 Donaad@knuTT"" "21 KNUTH,, Donald"),
("8:grace, HoppeR&" - "8. HOPPER, Grace") "), ("EDSGER99 DIJKSTRA" - "99..I9I."" DIJKKTRAA,, Edsger") ]
ExeDec
No-Subgoal Ablation
Step 1:
Step 1:
Subgoals: 1*1 "21", "8", '99"]
Subgoals: not predicted
Subprogram: GetAll SretAl1(NUNNH)) (NUMBER)
Subprogram: GetToken (NUMBERR -1)
Execution: [*1", "21", . "8". *99"]
Execution: ["1", "21", "8", "99"]
Updated specification:
Updated specification:
[("alan Turing1"
TURING, Alan") .
[""alan Turingl" = .URING Alan"), ....
Step 2:
Step 2:
Subgoals: [*
Subgoals: not predicted
Subprogram: Const
Subprogram: Const
.')
Execution: |"
"."
Execution: [". ".""""""""""
Updated specification:
Updated specification:
("aalan Turing1" "TURING, Alan "),
("aalan Turing1" - "TURING, Alan"),
Step 3:
Step 3:
Subgoals: ("TURING", "KNUTH", "HOPPER",
Subgoals: not predicted
Subprogram: Compose (ToCase (ALLsseAAL__AARR CAPS),
Subprogram: Compose ToCase (ALL_CAPS))
BetToken(WOR) -1))
GetFrom (',")
Execution: ("TURING", "KNUTH", "HOPPER".
Execution: [" "HOPPER&", ""]
Updated specification:
Updated specification: Invalid
[("alan Turing1" Alan").
No steps: In example #3, the subprogram's output "HOPPER&" not prefix the desired output "HOPPER, Grace".
Step
Subgoals:
Subprogram: Const(
Execution: ["
"1
Synthesis result: Failure
Updated specification:
[("alan Turing1" "Alan"). ...
Transformer Baseline
Step
Prediction:
Subgoals: ["Alan", "Donald", "Grace".
GetToken (NUMBER, -1) I Const(' .') ToCase (ACL,,eAAL_COo (ALL_CAPS) I Const('.')
Subprogram: Compose (ToCase
Got 1))
GetFirs((LOWER Const( ('A')
Execution: [* I'Alan", "Donald", "Grace"....
Updated specification:
Execution:
["1 ALAN TURING1, Aalan",
[("alan Turing1" "")...
"21 21 D.DONALSKNUUT Aonald",
"8. 8 8:GRACE, HOPPER& Agrace",
No more steps: updated specification output is empty for all examples.
*99 EDSGER99
DIJKSTRA, A"]
Synthesis result: Failure
Synthesis result: Success
Final program:
GetAll (NUMBER) Const('.') Compose (roCase(ALL_CAA) CAPS), GetToken(WORG, -1)) Const(', (ampose(ToCase(PROO) GetToken 1))
Figure 5: A comparison of different approaches on the same string manipulation problem in the RobustFill domain, under the Compose-New--pprrtie the problem correctly with length program including two usages of the new operation (Compose). The no-subgoal ablation fails to correctly use the Compose operation in step 3, likely because the model has not seen the Compose operation used to produce prefix of the output. On the other hand, ExeDec succeeds that step because the relevant prefixes are predicted as subgoals first. The Transformer baseline performs poorly this task and does not single Compose operation.
generalization task. ExeDec able to solve
22

---

Published as a conference paper at ICLR 2024
RobustFill Example Problem 2
Specification:
(212.04 1999" '1999/12/04"), ("07/08, 2000" "29"9/07/08"", ("84/12/1995" - "1995/04/12"), ("09.30.22 299.130.0011 - '2881/89/38")
ExeDec
No-Subgoal Ablation
Step 1:
Step 1:
Subgoals: (*1999", "2000", "1995", "2001"]
Subgoals: not predicted
Subprogram: GetToken NUMBER, -1)
Subprogram: GetToken (NUMBER, -1)
Execution: 1'19'"" "2000", "1995", "2001"]
Execution: ["1999", "2000", "1995", "2001"]
Updated specification:
Updated specification:
[(112.04 1999* /12/04").
[("12.84 14 1999* "/12/04"),
Step 2:
Step 2:
Subgoals: [* "/" "/","/""""""
Subgoals: not predicted
Subprogram: Const( /')
Subprogram: Const /')
Execution: |" "/", "/", 1/"
Execution: I"/","/", "/", "/",
"/"1
Updated specification:
Updated specification:
("12.044 1999* "12/04"),
1"112.04 04 1999* - "12/04"),
Step 3:
Step 3:
Subgoals: 121//04, "07/08", "04/12",
Subgoals: not predicted
Subprogram: Compose Compose (Replace( / "
Subprogram: GetUpto
GetUpto (NUMBER)
BerFirst(CHAR, 5))
Execution: ["12". "87", "04". '89"]
"07/08", Execution: '"" "84/12". ...
Updated specification:
Updated specification:
1("12.04 04 1999* - "/04"),
[("12.04 1999* _ "")...
Step 4:
No more steps: The updated specification output is empty for all examples.
Subgoals: not predicted
Subprogram: Const /')
Execution: ["/", "/",""" "1" "/"
Synthesis result: Success
Updated specification:
("112.04 1999" "84") "84"),
Final program:
GetToken NUMBER, -1) Const('/") I Compose Replace(" '/'),
Step 5:
Subgoals: not predicted
GetFirst (CHirRst(CHAR, 5))
Subprogram: GetToken (NUMBER,, -2)
Execution: ["04", "08", "12", "30"]
Transformer Baseline
Updated specification: 14"12.04 1999* ""),
Prediction:
Token TeUTTeEENNMBBR, NUMBER, -1) Const /') I
more steps: The updated specification output empty for all examples.
GetToken (DIGIT, (DIIII 1)
GetSpan (CHAR, 2, START, NUMBER, 1, END)
Const(" /") GetSpan
1, START, CHAR, 5, END)
Synthesis result: Success
Execution: [ (1999/12/12 02".""...""" "2000/07/07/08" '1995/84/84/12", "2001/89/89.30
Final program:
DetTokenNNUMBER -1) | Const(' (') I
GetUpto (NUMBER) Const ('nstt"/") GetToken (NUMBERR, -2)
Synthesis result: Failure
Figure 6: Another comparison on different string manipulation problem. Here, ExeDec finds minimal-length solution using 3 subprograms and Compose operation. Meanwhile, the no-subgoal ablation solves the problem a suboptimal way, replacing the Compose operation with 3 separate steps. The Transformer baseline also used suboptimal approach in the middle of the program and was wrong in the last step.
23

---

Published as a conference paper at ICLR 2024
DeepCoder Example Problem
Specification:
xx [5,-2, x1 = - 5)) x1x0= (7,1,5, x1=4) [7,8, 13] ((x8= = -,,7,, x1=3 ) - [8,4, ]
ExeDec
No-Subgoal Ablation
Step 1:
Step I:
Subgoals: [[5,3,4], [7.8, 13,11,11, 3,
Subgoals: not predicted
Subprogram: x2 Scan11 (+) x0
Subprogram: x2 Scan11 (+) x0
Execution: [[5,3,4] 41, [7,8, 13,
13, 11). [8,4,33181]
Execution: [[5,3, 3,41, 41. [7,8, 13, [8,4,3, 10]]
Updated specification:
Updated specification:
[( x0 [5, 1], =1 x2 [5,344]
[( ( x8 [5, -2, 1], x1 =2, x2 x2= [3,5] ...
[3,5]
Step
Step 2:
Subgoals: [[5, 3], [7, 8, 13, 11], 38]4 Subprogram: x3 Take x1 x2
Subgoals: not predicted
Subprogram: x3 Scan11 (max) x2
Execution: 3]. 13,,,,,, [8]
Execution: [[5, 5, 5]. [7,8, 13, [8, 8,8, 10]]
Updated specification:
Updated specification:
(( [5, -2, =1 (5,3,4),
[ ( x0 [ -2, 11, =1 x2 [5,3,4),
x3 = [5,3] ) [3,5))....
x3 5,, 5, 5] [3,5]). )..
Step
Step 3:
Subgoals: [[3, 5]. [7, 8, 11, 13], [3, 8]8]
Subgoals: not predicted
Suhprogram: Sort
Suhprogram: x4 Filter (>0) x0
Execution: [[3, 5], [7, 11, 13), (3,4,8]
Execution: [[5, 1]. [7,1, 1, 5]. [8,7]]
Updated specification:
Updated specification:
[( ( [5, 1], x1
x2 [5,3,4), x3 [5, x4 [3,5] 5] [3,5] ),
[ ( xe [5, 02,-2,,10 22, x1 2, x2 [5,3, 4], x3 [,, x4 [5,1] [3,5]
No more steps: The updated specification has x4 matching the output for all examples.
Step 4:
Subprogram: x5 Filter (%2==1)
Execution: [[5,3], [7, 13, 11), [3]]
Synthesis result: Success
Step 5:
Final program:
Subprogram: x6 Filter (>0) x3 Execution: [15,5, [7, 13, 13], [8, 10]]
x0 INPUT x1 INPUT |
x2 Scanl1 (+) x8 x3 = Take x1 x2
x4 Sort x3
Step 6:
Subprogram: x7 ZipWith (min) x2
Transformer Baseline
Execution: [[5,3,4], (7,8, 13, 11), 4,,4,3, 10]]
Prediction:
Step 7:
xθ INPUT x1 INPUT |
Subprogram: x8
Drop x2 x7 Execution: TypeError
x2 Scanl1 (+) x8
x3 Filter (%2==1) x2
x4 ZipWith (min) x2 x3
more steps: The subprogram contains an emror because x2 is a list but Drop expects an integer.
Execution: [[5, 3), [7, 8, 11], [3]]
Synthesis result: Failure
Synthesis result: Failure
Figure 7: comparison on DeepCoder list manipulation problem under the Compose-Diffens Concepts generalization task. All three approaches get the first step correct, but the ablation and baseline are unable to continue correctly, erroneously using higher-order operations for subsequent steps according to the compositional pattern in the training data. However, the design of ExeDec makes it less susceptible to overfitting on such patterns, and indeed ExeDec solves this problem using manimal-lengee program from the test distribution.
24

---

Published as a conference paper at ICLR 2024
J PROGRAMS AND PROMPTS FOR LLM EXPERIMENTS
J.1 DSL PROGRAMS AS PYTHON FUNCTIONS
For the LLM experiments, we transform the DSL programs into Python functions that call hypo- thetical ds1 library, enabling the LLM to use its understanding of Python programming while we measure how well generalizes new functionality it has not been trained on.
Compose (ToCase (PROPER), GetToken (WORD, })) transforms the input string "TURING, Alan" into the output string "Alan. Turing". For the LLM experiments, it is written as Python function as follows:
The RobustFill program Get5rom ') Const (*.")
def progzam (x)
parts
dsi GeLLGeeFroolfe "), don.Const ('.'),
dolaTe (dsl. Getroken (x, dsl. Type. "ype.WORD, 1),
PROPER),
return join (parts)
The DeepCoder program x0 = INPUT x1 Map (++2) x0 x2 Sort x1 transforms the input list [5,3, -4] into the output list [9, 16, 25). As a Python function, this would be:
def program (x0)
x1 dal MMp Basl.SQUARN, x0)
x2 dsl.Sor (x1)
x2
also experiment with a "Pythonic" form of DeepCoder programs, for example:
def program (x0):
x1 [x 2 for in xC]
x2 sorted (x1)
return x2
J.2 LLM PROMPTS
We programmatically create prompts for 3 LLM approaches (baseline, ablation, and ExeDec), for kinds datasets (RobustFill, DeepCoder, and DeepCoder-Pythonie)) We provide prompts for a few example combinations in figures:
Figure 8 has Baseline-style prompt for RobustFill,
Figure 9 has an Ablation-style prompt for DeepCoder,
Figure 10 has an ExeDec-style prompt for RobustFill, and
Figure 11 has an ExeDec-style prompt for DeepCoder-Pythonic.
In each figure, the prompt contains only few-shot example for brevity, but experiments used few-shot examples for prompts. Line wrapping is denoted with the + symbol.
Observe that the information contained in the ExeDec-style prompt is the prompt, just with different ordering of the code for a step and its corresponding execution results. Although this difference may slight, leads the improved performance for the ExeDec-style approach.
in the Ablation-style
25

---

Published as a conference paper at ICLR 2024
The "dsl" module is custom library for manipulating strings. It contains the following functions:
Const, SubStr, GetSpan, GetToken, ToCase, Replace, Trim, GetUpto,
4 GetFrom, GetFirst, GetAll, Substitute, SubstituteAll, Remove, 4 RemeveAll
Additionally, the module defines the following constants:
dyl.Type. NUMBER, Tyl.
dsl. Type. ALP_ + dsl. Type.PROP_CASE PROP_CASE, dsl. Typ. LOWER, dsl. TIIe. dsl Type. CHAR, Sal.Case.PROPER dal.Case.AIi CAPS, dsl Case LOWER, dsl Bsl.Boundary.Snee START, dsl.Boundary.
Below are example programming problems using the 'dsl' module, with input-output test cases illustrating their behavier.
Important: All programs begin with "'python and end with ... alone.
[BEGIN PROBLEM]
Input-output test cases:
Case 1. "TURING, Alan" --> "Alan. Turing"
Case 2. "knuth Donald" --> Knuth"
Case 3. "Hopper Grace" --> "Grace "Grace.Hopper" "DIJKSTRA... Edsger" --> "Edsger.Dijkedt Dijjktra"
Program:
python
def program (x)
parts
dsl. Gel.GetFrom ' Const ('.'), '),
dal ToCase (ds1 .et.rroee (x, dal, TORD,WORD, 1), dal Caase. PROPER),
]
return "oooin (parts)
[END PROBLEM]
[BEGIN FROBLEM]
Input-output test cases: Case 1. "apple" --> "Apple!"
Case "banana"
"Banana!"
Case 3. "clementine" --> "Clementine!!
Case 4. "durian" --> "Durian!"
Program:
python
Figure 8: Baseline-style prompt on RobustFill. The LLM's continuation contains its predicted
program as one entire function, terminated with triple backticks.
26

---

Published as a conference paper at ICLR 2024
The "cal" module le 1s custom library for mantpulating Hata of integera. Tt contains the following functions:
Read, Last, Take, prop, Access, Minimum, Kaximum, Reverse, Sort, Sum, Nap, Filter, Count,
4 ZipWith, Scanl1
Additionally, modula defines the follewing
PLUS_ONE, MINUS ONE, TIMES DIV NESSTE, SQUARE, TIMES THREE, TUREE,
4 TIMES_FCUR, DOUR, 28_POSITIVE, NEGNTVVVVE,, 18_EVEN, 18_0DD, ADD, SUBTRACT, MULTIFLY, MIN,
Below are example progzamming problems using the "dal" nodule, with input -utpuu test cases illustrrati the program behavior step-by-step.
Importaat: progrems begin with "'python end with "..
[B3GIN PROBLEM) Input output test cases:
Case
[5, -4] --> [9, 16, 251
Case 2, x0 - [ 2] > [4]
[3,
[L,
Me sclve probl step-by-step.
Step code:
** "python
x1 dal. Kap (ds1. x0)
Step 1 computea:
Case [25, 9, 16]
Case 2. [4]
[9, 49, 1, 16]
Step "'pyhhnn x2 Sell.orrt Ixl)
2 computes:
Case 1. x2 19, 16, 251
Case [4]
Case 3. 11, 16, 49
Putting the "''yyhonn
togethes, the problem is solved with the progran:
program(x0)
x1 = dsi. dsi.Map iQUARR, x0; do). (x1)
retura x2
[END FROBLEM]
[BEGIN BRCBLEM)
Tnpot-output test eases:
Case [1, 71. x1 [3,
Case 2. [2, -4, 1. 51, --> 16, -12, 3, 01
[11],
--> [33]
solve problem step by step.
Step code:
Figure 9: Ablation-style prompt on DeepCoder, For the ablation-style approach, the execution result of each step is shown after the code for that step. The LLM will respond with the first step toward solving the test problem, surrounded by triple backticks. We then execute that code (making some assumptions about its format, e.g., that it assigns to variable) and construct the first step's code and execution results in the history, following the pattern in the few-shot example, so that the LLM's next prediction the second step conditioned the first step.
prompt with
27

---

Published as a conference paper at ICLR 2024
(... Deseription of the "dal" module ...]
[BSGIN (RCBLEM)
Inpot-ootpet test cases:
Case 1. "TURING, Alan" *Blan. Turing"
Case 2. x "knuth Donald" "Donald. Knuth"
"kopper Grace" --> *Grace. Hcpper"
Case 4. x "DIJKSTRA... #dsger" ->> "Edsger.Ds Dijttra"
Wa salve this problem stap-by-stop.
SLep computes:
Case "Alan" so ".Turing" remains
2. "Donald" ". ".Knuth" remains
Case 3. "Grace* so "oopper" remains "Bdsger" ".Dijksiza""
Step code: "pyyhhnn csl.Betsrcmte (x,
SLep computes:
Case 1. "." so "Turing" remains
Case 2, "," 80 "Knuth" zemains
Case "."
"Hopper" remains
Case 4. "." so "Di "Dijkstr"" remoins
Step 2 code: ** "python
con.Conat (!.1) ...
Step 3 computes:
"Turing" "* remaina
Case 2. "Kauth" so zemains "Hopper" "* remains
Case "Dijketzz"" "" zemains
step code:
''yyhhon
doCae (dsL.Get (x, Type. 11, del. PROPER)
Putting the steps Logethes, the problem is solved with the progran:
python
daf program(x)
parts =
(xl.GeLLrom
dsl.Const (1,'),
doCas Getroken (x, dsl.rypa.woRD, 1), FRC.E..
return (pinnss
[END FROBLEM]
[REGIN PRCELEM)
Input-outpet test cases:
Case 1. x "apple" --> "Apple!"
"banana* "Ranana!"
Case 3, x "ClemenL
*Ceementine!**
"durian" "Durian!"
Ma salve probl step-by-step.
Step
computes:
Figure 10: ExeDec-style prompt on RobustFill. For the ExeDec-style approach, the execution result of step comes before the code for that step. This is how get the LLM to perform "execution decomposition" it must predict execution subgoals before predicting code for that step. We extract the predicted code (surrounded this step's code and execution results (ignoring the model's predicted subgoals). The dsl module's description the top of the prompt is omitted for space, but identical that in Figure 8.
triple backticks), run it, and construct
prompt containing
28

---

Published as a conference paper at ICLR 2024
The "dal" module is library for manipulating Hata of integera. containa the + tollowing Functions:
Get Scanll (f, xel:
ys 1]
for i, in erumerate(xs)
== 3:
ya.append (X)
elae:
retura (5..ysl x))
Selow example programming problems using the "dsl" nodule, with input-output test 4 illsstrating the program behavior atop-by-step.
Iaportaat: All progrems begin with ""python and end with slone.
[B2GIN 2RCB122) input-output test cases:
Caae 1. [5, 3, -4] --> (9, 16, 25]
[-
Case 3. x0 [3, 7, 1, 41 --> [1, 9, 16, 491
We sclve this probl em step-by-step.
computes:
Case 1. x1 [25, 9, 16]
[4]
Case 3. xl [9, 49, 1, 161
Step code:
"'python
[x for
Step 2 computes: [9, 16, 25]
Cade
Case 2. [4]
Cade 3. [1, 9, 16, 491
Step 2 code:
.** "python
x2 = corted
...
Putting the staps together, the prohlem ta volved with the program: ... ppython
def progzam (x01
x x0]
x2 sorted
retura x2
(END PROBLEM)
[BEGIN PRCSLEM)
Input-output test cases:
Case
[1, 5, 71. x1
13,
Case 2. [2, -4, 1, 0, 51,
[6, -12,
Case 3, x0 [11], x1 - --> [33]
We sclve this problem step-by-step.
Step computea:
ExeDec-style prompt DeepCoder-Pythonicc For Ceeppoodrr-yythoniee only the Scan11 1 operation remains in the hypothetical dsl library while every other operation and lambda function is written in Pythonic form. Thus, the beginning of the prompt has the library description updated correspondingly. We provide the implementation of Scanli because it's only one function.
Figure 11:
29

---

Published as a conference paper at ICLR 2024
K FAILURE MODES IN LLM EXPERIMENTS
In the LLM experiments, ExeDec's incorrect solution programs encounter a variety of errors. Table lists the specific errors, the number of programs encountering an error considering all generalization tasks (including no generalization), and the proportion of that error among all incorrect programs for that dataset.
Table 4: Error analysis for LLM experiments for ExeDec @ (greedy decoding).
RobustFill
DeepCoder
ChepCoder-Pythomme
(Correct)
33
66
88
AssertionError
2 0.2%
0
0.0%
0
0.0%
Attributekrror
6
0.5%
63
5.6%
0
0.0%
IndexError
0 0.0%
0
0.0%
1.6%
NameError
0 0.0%
0.0%
9
0.8%
SyntaxError
1 0.1%
1
0.1%
0
0.0%
TypeError
234
20.1%
150
13.2%
9
0.8%
ValueError
0 0.0%
0
0.0%
3
0.3%
deroDivisionError
0 0.0%
0.0%
1.3%
Wrong behavior
924
79.2%
920
81.1%
1058
95.1%
For RobustFill, about 20% of failures are TypeErrors caused by using the DSL incorrectly, while about 79% of failures do not encounter runtime error but simply have behavior inconsistent with the I/O specification.
For DeepCoder, At AttributeErres accounts for about 5.6% of failures (when the predicted pro- gram attempts to use a hallucinated function or constant in the DSL), TypeError accounts for about 13% of failures, and about 81% of failures are due wrong behavior. For DeepCoder-Pythonic about 5% of failures are from various runtime eπrrrs, while about 95% are due to wrong behavior.
Overall, the vast majority of failures are due wrong behavior. Although LLMs have seen much success in predicting programs from natural language specifications, they still perform poorly in programming- weatemiinng----eaaee example without natural language hints, especially for synthetic problems.
HIERARCHICAL EXEDEC
The following Python-like pseudocode describing how ExeDec might be extended enable hierarchical decompositions. We leave exploration of this extension to future work.
def ExeDecitierarchiicc.c (inputs, outputs):
difficulty DifficultyModel (inputs, outputs) if difficulty =- 'easy': base case return SynthesizerMode (inputs, outputs)
outputs easy/hard
recursive
subprogzams []
while Truc:
subgoals = SubgoalModel (inputs, outputs)
subprogram RxsDecHierarce cal (inputs, subgoals) # recurse
sulp:rogram..apper (stbapp (subprogram)
execution execution_reaull
execute (subprogram, inputs)
if execution result == outputs:
return CombineProgramFart (subprograms)
(inputs, outputs) IpeateSpecisicationn (inputs, outputs,
execution result)
30


Reviews:
[{"review_id": "bg6wfp7B3S", "reviewer": "Reviewer_2WRW", "summary": "This paper improves the composition generalization of neural program synthesis by introducing execution decomposition. The general idea is to interleave sub-goal predictions with program generation. To evaluate this idea, the authors design five compositional generalization tasks based on two popular datasets used by RobustFill and DeepCoder. All specifications including sub-goals are assumed to be I/O-example based, where the inputs of sub-goals are intermediate program states. The outputs of sub-goals are somewhat complicated depending on the application domain. The evaluation shows that ExeDec outperforms many other baselines that do not (explicitly) predict sub-goals, and LLMs struggle to solve the proposed tasks requiring compositional generalization even when ExeDec-style prompts are provided.", "questions": "How to process different numbers of I/O examples (the size of which may also vary) in transformer models?\n\nStraight-line code can be split arbitrarily, how to decide which snippets form a proper sub-goal?\n\nIt is a bit surprising that No-subgoal Ablation performs pretty well. Shouldn't it behave like the Transformer baseline?", "limitations": "", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 4, "contribution": 2, "strengths": "- Having compositional generalization as an inductive bias in the synthesis algorithm is novel and sounds quite appealing. Compositional generalization should be a key aspect in order to achieve scalable program synthesis. \n- Five different types of compositional generalization tasks are designed and relevant benchmarks are created based on two popular synthesis domains, RobutFill and DeepCoder. \n- The evaluation consists of multiple baselines as well as LLMs, and ExeDec outperforms all of them on the proposed dataset\n- The problem is well-motivated and the related work is discussed in an insightful and thorough manner", "weaknesses": "- The two datasets are small domain-specific tasks, thus the evaluation does not really show the promise of scalability, which is the original motivation.\n- I/O-based specifications are not easy to construct -- both intermediate states and output states may vary significantly from the initial given I/O examples. For instance, intermediate states may involve auxiliary temporary variables, and the output states may have to be adjusted according to the actual application domains. \n- 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.\n- Creating a good training dataset for decomposition tasks can be very challenging. Particularly, there are many valid solutions, which may have quite different intermediate sub-goals. Supervising only one specific solution would be problematic.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "1tXs5T6OLV", "reviewer": "Reviewer_hCQX", "summary": "Summary:\n- This work formalizes several useful notions of generalization, and describes how these can be used to create train-test splits of datasets testing each form of generalization. The classic neural synthesis datasets DeepCoder and RobustFill  are divided up in this way and used for evaluation throughout the paper.\n- The authors then presents a novel architecture called ExeDec for synthesizing sequential programs, where a prefix of a partially constructed program can be executed to get a state-so-far. While prior work conditions next-subprogram generation on the state-so-far and overall output spec, here the authors introduce a subgoal-generating module that produces an output spec for just the next subprogram, then conditions next-subprogram generation on that spec (though regardless of whether the subgoal spec is met, the sampled subprogram is accepted).\n- While performing relatively similar to baselines/ablations on the original datasets, ExeDec performs far better than alternatives at the generalization-focused modified datasets. Additionally, in another set of experiments the authors prompt an LLM to perform ExeDec-style reasoning (predicting outputs of the next line before writing it) and find it boosts performance.", "questions": "- 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? Some added discussion of this would be helpful.\n\n- \"Details omitted for anonymity. This LLM is one of the largest available through an API.\" I don't think anonymizing the LLM if it's available though a public API (eg chatgpt, bard, claude, codex, gpt4, etc) is necessary, and none of the other papers I'm reviewing do this. It'd be helpful to know which LLM this is (unless it's a private API and would actually break anonymity of the authors) in case it raises any other questions/discussion from reviewers.\n\n- I'm a little surprised by how poorly the LLMs do in Table 1. Do you have a sense for the usual failure modes – does it produce code that's valid in terms of the DSL, but isnt correct? Or does it fail to adhere to the DSL? (as an aside, in the non-pythonic setup, if the LLM attempts to write normal python code instead of using the `dsl` library, is this treated as invalid and do you have a sense for how often this happens?)\n\n- To clarify, \"test on training distribution\" in Fig 2 is referring to a heldout test set of problems from the same distribution as the training set, and not testing directly on any of the problems that the models were trained on, right?", "limitations": "", "rating": 8, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "- Formalizing different notions of generalization and suggesting actionable ways of designing benchmarks around this is much-needed work in program synthesis. This is something that I come back to again and again in my own thinking – the scarcity of generalization-centric benchmarks and systematic generalization evaluations, especially beyond just length generalization.\n\n- Evaluations look quite good – ExeDec Performance is far better than the from-scratch transformer and latent programmer baselines, and barely diminishes when using the smaller version of the model. \n\n- The improvements over the No-Subgoal ablation (which is similar to prior work as mentioned in 4.3) are fairly significant (eg 80% -> 87%) and are mainly in the Compose New Operation and Compose Different Concept categories. These aren't extremely strong results but they're enough to justify the relatively straightforward general setup, in my view.\n\n- Showing off and evaluating an analogous algorithm for LLM-based synthesis was a nice touch and shows the generality of the idea. This idea of breaking problems into subgoals is a good one, and I think one that many have thought about but nobody has done well – this work feels like a nice step towards doing it. As discussed in their limitations, something more hierarchical might better capture how programmers often break down problems, however just predicting the results of the next line is a reasonable first step in this direction and seems to empirically be helpful.\n    - In fact, before reading this I actually would not have expected predicting the output of just the next subprogram to be that helpful compared to just predicting the subprogram directly (whereas I would expect predicting outputs to more general hierarchical multi-subprogram subproblems to be helpful) so I appreciate that this paper finds and highlights where even just this single step prediction can be beneficial.", "weaknesses": "- In the intro there's a mention of how compositional generalization \"has not previously been studied in the context of programming by example\" and later in the related work a mention of how there's \"less work on systematic generalization for machine learning for code, although Bieber et al. (2020) studies length generalization\"\n    - While both systematic generalization and specifically compositional generalization are understudied in program synthesis, there are a few other citations that apply to each of these places.\n    - First, the DeepCoder paper (Balog 2017) actually evaluates on length generalization (section 5.2 of that paper).\n    - Nye et al 2021 (\"Representing Partial Programs with Blended Abstract Semantics\") has some compositional generalization evaluation as well, such as the excerpt from section 5.1 \"Tower objects seen during training were composed in previously unseen ways...\"\n    - Ellis et al 2019 Program Synthesis in a REPL (already cited here) also applies for length generalization, eg the line from 4.2 \"Although it was trained on programs whose maximum length was 30 actions and average length approximately 8 actions, during test time we regularly achieved programs with 40 actions or more\"\n    - Just adding those citations in the appropriate places would strengthen this. To be clear, ExeDec's formalization of generalization and range of types of generalization go far beyond any of this prior work, but it's important to acknowledge that there have been some explorations of some of these kinds of generalization in the past.\n    - Aside from this point, I think the related work citations are quite thorough and well done\n\n- How often are proposed subgoals actually achieved? Are they achieved more along a successful synthesis path than an unsuccessful one, on average? Some quantitative insights into these sorts of questions would strengthen the paper.\n\n- The results are decent but not extremely strong – in my opinion they're good enough but of course stronger results would help.\n\n- The idea mentioning in the Limitations section of how subgoals that are not just line-by-line but which could instead correspond to more than one line is one that immediately came to mind. Of course, fully generally doing that kind of generic hierarchical decomposition of a problem into subproblems is something of a holy grail in synthesis, and I think that this fairly limited form of subproblem is a reasonable step, so this is not a huge weakness.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "GlBJga64Pg", "reviewer": "Reviewer_iTFM", "summary": "The paper proposes a method for programming by examples where the goal is to generate a program for given input-output examples. The proposed method first predicts subgoals (which are simply intermediate values during the program execution) and then generates a (sub)program that achieves those subgoals. This is repeated until the subgoals correspond to the target outputs. Additionally, the paper suggests different benchmarks for compositional generalization for programming by examples (e.g., generalizing to longer programs). The proposed method is shown to have better generalization performance than the baselines in both the training from scratch and the pre-trained setting.", "questions": "Do you have an insight into why the no-subgoal ablation performs better on some generalization benchmarks?", "limitations": "", "rating": 8, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "The proposed method for programming mirrors how humans tend to come up with programs for complicated programming tasks: divide them into smaller subproblems and address them individually. In that sense, the method is simple and intuitive, hence I'd expect something similar to work well even in more realistic settings.\n\nThe benchmarks provide valuable insights into the settings under which we would expect a decomposition into subprograms to be important. \n\nIt is interesting to see that the proposed method can also be adapted to work for pre-trained LLMs in the few-shot setting (i.e., without fine-tuning).", "weaknesses": "The main limitations are that the method requires supervision for the sub-goals and that the experiments are limited to synthetic programs, as acknowledged by the authors in the limitations section. I can see that an unsupervised approach to predicting subgoals constitutes its own paper, but I think it'd still be interesting to see how the method fares with different decompositions. For example, picking $n$ lines per subprogram, or randomly grouping multiple lines into a subprogram.\n\nThe experiments cover both the training from scratch scenario and a pre-trained LLM. The middle ground of finetuning a pre-trained LLM would be interesting to see. Here the same LLM could be used for the different models via different prompts (similar to the few-shot setting) and trained like the from-scratch setting. Since the benchmark intends to measure generalization and considering the importance of pre-training on the generalization performance, I believe this is an important additional experiment.\n\nExeDec requires subgoals which are essentially execution traces as supervision. It'd be interesting to see how the Transformer baseline performs when it also has access to them (for example by inserting the variable values after/before each program line). This baseline would further clarify the importance of training with intermediate program states versus decomposing the program into parts that are individually generated.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "ClBKKnbao4", "reviewer": "Reviewer_EB19", "summary": "The paper proposes a set of generalization tasks to measure the ability of a programming by example program synthesis engine to generalize to be able to generate out-of-distribution programs. These tasks measure the ability of the synthesis engine to generalize to programs of different lengths and with different operations in different orderings than observed in the training data. The paper then proposes ExeDec, an iterative synthesis approach in which one model proposes a subgoal, a different model proposes a program to each that subgoal, and the process repeats until the composed program results in the expected output. The paper evaluates ExeDec instantiated with Transformers trained for each generalization task and with LLMs and find that ExeDec improves generalization compared to baselines.", "questions": "* What happens if the loop in Algorithm 1 never terminates?\n* 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?\n* What is the comparison in FLOPs between the ExeDec models and the baseline models?\n* How do models perform on generalization tasks that they were not trained for?\n\nMy score is conditioned on the authors improving the description of the baseline in Sections 2 and 3.", "limitations": "", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 2, "contribution": 3, "strengths": "* The proposed set of generalization tasks are interesting, important, and well described\n* The proposed ExeDec algorithm is also interesting: in particular, it is a general algorithm sketch that can be instantiated either by Transformers trained for this algorithm (Sections 4.2/5.1) or LLMs (Section 5.2)\n* The results, taken at face value (though see the question about FLOPs below) are strong. In particular, they demonstrate that the core idea of predicting the next output improves generalization.", "weaknesses": "* The benchmark introduced in Sections 2 and 3 is claimed as a novel contribution (\"we introduce a new meta-benchmark for measuring the compositional generalization abilities of program synthesizers.\"). 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.\n* The implications of the loop in Algorithm 1 are not sufficiently discussed:\n  * What happens if the loop never terminates?\n  * What is the comparison in FLOPs between the ExeDec models and the baseline models (including the beam search, etc)? Even if the parameter count is the same, the loop in ExeDec could give these models significantly more power than the Transformer / Latent Programmer baselines.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Decision: Accept (oral)