Learning to Combine Per-Example Solutions for Neural Program Synthesis
Authors: Disha Shrivastava
Hugo Larochelle
Daniel Tarlow
Venue: NeurIPS 2021 Poster (2021)
Keywords: program synthesis
neural program synthesis
program induction
program understanding and generation
multi-head attention
programming by example

Abstract: The goal of program synthesis from examples is to find a computer program that is consistent with a given set of input-output examples. Most learning-based approaches try to find a program that satisfies all examples at once. Our work, by contrast, considers an approach that breaks the problem into two stages: (a) find programs that satisfy only one example, and (b) leverage these per-example solutions to yield a program that satisfies all examples. We introduce the Cross Aggregator neural network module based on a multi-head attention mechanism that learns to combine the cues present in these per-example solutions to synthesize a global solution. Evaluation across programs of different lengths and under two different experimental settings reveal that when given the same time budget, our technique significantly improves the success rate over PCCoder [Zohar et. al 2018] and other ablation baselines.

Learning to Combine Per-Example Solutions for Neural Program Synthesis
Disha Shrivastava
Hugo Larochelle
Daniel Tarlow Mila, McGill University Google Research
Mila, Université de Montréal Google Research
Mila, Université de Montréal Google Research
CIFAR Fellow
Abstract
The goal of program synthesis from examples is to find a computer program that is consistent with a given set of input-output examples. Most learning- based approaches try to find a program that satisfies all examples at once. Our work, by contrast, considers an approach that breaks the problem into two stages: (a) find programs that satisfy only one example, and (b) leverage these per-example solutions to yield program that satisfies all examples. We introduce the Cross multi-head attention mechanism
Aggregator neural network module based that learns to combine the cues present in these per-example solutions to synthesize global solution. Evaluation across programs of different lengths and under two different experimental settings reveal that when given the same time budget, our technique significantly improves the success rate over PCCoder [30] and other ablation baselines. The code, data and trained models for our work can be found at: https: //ggttttuub com/ shr wwwtavadisaaaa--Paaa...
1 Introduction
Program synthesis from examples tackles the problem of coming up with a computer program that satisfies a given set of exhaustive search can be extremely time-consuming. Therefore, development of systems for program synthesis that come up with solution (program satisfying the given IO examples) within limited time, such that it is practical for real-world applications, is a challenging task.
(IO) examples. Since the space of possible programs is large,
Neural-guided program synthesis systems [4, 30] try to expedite the search by using neural network conditioned on the IO examples as a learned heuristic for the search procedure. In these systems, a neural network outputs probabilities over programs properties of programs (e.g. functions). These probabilities are then utilized to guide a search like depth-firs or beam search. These systems try to find program that satisfies all IO examples simultaneously, which under most of the settings can hard. What if instead, we try to find this program in parts? To understand this motivation, imagine process wherein programmer is asked write program that satisfies set of unit test cases. They may begin by figuring out program that satisfies a subset of unit test cases first, and later modifying the program to incorporate other corner cases. Shi al. [26] uses this intuition to iteratively refine a program by mining fragments Java code from partial solutions, based on a set of rules and predefined heuristics. Gupta et al. [12] also uses the same intuition, but different application for program repair.
In this work, consider breaking the complex problem of finding program that satisfies all N given 10 examples (called the global solution) into smaller, easy to solve sub- sub-problems, where each sub- beob-problem involves finding program satisfying only one 10 example (called per-example
"ooreeponndecce to: <dishu.909 @ gomi
35th Conference on Neural Information Processing Systems (NcurIPS 2021).

---

1154, 228.
138,
150) 22400
[-
Sue OUgUi
106,
1338 1228,
17)
COUNT (+9)
1140 158. -211. (66 111000001100000 -74]
DROP C
A5: [87. -115 52) (177. 193,
(*-1)
FILTER (c0)
sirper bosn Weerc
PE Searches
Cross Aggregator
Nitiooy?
Cross Aggregator
Pormsted mnt
Pi
19T
ITAT
LIST
Hells (11 Mello
1: d- COUNT (000)
1: FILTER (HR)
COUNT (+8)
2: MAP (*-1) i
Halley (31
Ha(e)
Works for al, 03
Works for #2, 44
Disareg FC 533 entraddigg
Malbe
Malbe/M1..0 71,30
P-00)
My 0.4
U2
Works
Rells
H(daw)
P100)
Figure I: Idea of N-PEPS: (Left) Illustrating the two stages of N-PEPS with an example; (Right) Synthesizing line 2 of Py using contributions from CA and GPS, with details of how query, keys, values and relation scores are formed. White box shows an example of obtaining PE state embedding.
solution). The cues present in these per-example (PE) solutions are then combined to provide useful signals that can help guide the search for the global solution effectively. As motivating example, consider the left part of Figure 1, where five IO examples are given as a specification (green box) and we need to find global solution Pg (red box) that satisfies these five examples. The first stage of our approach consists of performing per-example searches to find a program p: conditioned on the i-th 10 example. our example, we start from I0 example #1 and find program P1. addition, we also check if P1 satisfies any other examples (#3 in figure). Iterating through the examples in this way results set programs (P1, P2: P3) that, taken together, in the ideal scenario, would satisfy all five I0 examples. Looking closely at the discovered PE solutions, we see that they contain fragments of the global solution. This brings us to the second stage of our approach that addresses the challenge of how best to aggregate these PE solutions to produce global solution. Towards that goal, we propose a neural network based architecture, which we refer to as Cross Aggregator (CA). It designed to learn to combine the cues present in these PE solutions, in way that helps guide the search for Pa We model this aggregation using a multi-head cross-attention mechanism, which leverages the state of step-wise execution of the PE solutions and the synthesized global solution so far (see Section 3.2 for details). Our key contributions can be listed as follows:
We consider breaking the standard program synthesis pipeline into two stages: (a) discovering PE solutions, and (b) aggregating the PE solutions such that it leads to global solution. We refer our approach that uses neural networks at both these stages Neural Per-Fxample Program Synthesis (N-PEPS).
We propose neural network based multi-head attention architecture called Cross Aggregator (CA) that makes use of step-wise execution information to learn to combine the PE cues such that it helps guide the search for the global solution.
We demonstrate via experiments with programs of different lengths and under two different evaluation settings that when given the same time budget, our formulation shows significant improvements in success rate when compared to PCCoder [30] (one of the leading techniques for neural-guided program synthesis) and other ablation basclines.
2 Background
= = [r:) of N I0 examples and our task is to come up with program Py that satisfies these examples. The i-th 10 example r; consists of a pair of input Ji; and output ye- The program consists of T lines (excluding lines with input variable declarations), i... Py ip To be practically mcaningful, we impose the constraint that P, has to be found
Suppose we are given a set X ((x, -

---

8² ,d .0?
Get ground-rruth
[iot]
[in]]
FILTER (8G--0))
< FILTER (5(2=0))+
+ MAP 1/2)
MAP
Iree u12, a. (91c1: (6. 18)
State Emb
S
SORT
DropExec
Siot: [12.4] 4)
Bw2 (B. 18)
Embed
after
d
LAST
Soct [6.2]
executing
Pg
Oumin
Cuppuc
Ha
line
State alter execuling lires
[12,
Impui:
Impui:
jaen 2?. R,
seit (s,
State Emb
Lingar
82
Outjuc
Output
Sw2:: (2.4 4]
Skit (9, Ia
Embed
after
Linear
d
Outse
executing
6²
line
Linear
Intiaal State
State efter executing line
Hg
W
Figure 2: (Left):: Sample program along with two 10 examples that forms the program state at t = 0;
(Right): Block Diagram explaining the training of PCCoder line 2 of the program.
within a given time budget, specified by a fimeout value. The syntax and semantics of Py are governed by a domain-specific language (DSL). We use the DSL provided by Balog et al. [4], which contains
first-order functions (e.g. SORT, REVERSE ) and higher-order functions (e.g. MAP, F FILTER ) that can take lambda functions (e.g. (*4), (<0) as input. The inputs and outputs can be either an integer or list of integers (see Appendix F of Balog al. [4] for more details about the DSL). The Predict and Collect Coder (PCCoder) [30] provides state-of-art results for this DSL and is illustrative of methods that directly solve for all available 10 examples once. We refer to these methods Global Program Search (GPS). We will be building on PCCoder to propose our per-example approach.
2.1 PCCoder
PCCoder synthesizes programs one line at a time, through a model based on the notion of a program
state. The program state is a two-dimensional memory of size N (v + 1) obtained during the set of N inputs. This means that for each IO example
exccution of t lines (steps) of a program Tú, there are up to y slots for storing the input and intermediate program variables, with an additional slot for storing the output (see Appendix A.2 for more details). Note that the initial state at t 0 consists of only the IO examples (see left part of Figure 2).
PCCoder consists of two learnable components (i.e. neural networks), Ha and W g. with parameters A and Φb HG obtains the embedding of the current program state by average-poolle poooleg-pooigggg the representation of the v + 1 slots corresponding to individual examples (white boxes inside the state in Figure 2) into a vector of fixed size in 2R22 ; where Z denotes the embedding size (see Appendix A.2 for details of how these representations of slots are obtained). Wa maps this state embedding to predictions of three quantities of interest for the next line in the program: (a) the next operator O' (or function e.g. MAP ); (b) the next statement s (operator along with its arguments e.g. MAP b ); and (c)
next drop vector d' which represents positions of variables that can be dropped from the state. The dropping is desirable as it creates slots for storing new variables, which in turn allows for synthesizing longer programs. There is a module called DropErec which executes a given line of the program against an example r; and stores the resulting variable G; in the next available slot in the state. If all slots in the state are filled, a variable is dropped from one of the slots using the drop vector and is stored there. The updated state can then be used for predicting the next line (see right part of Figure 2). Next, we provide details of how training and inference is done in PCCoder.
For training He and Wo, several instances of specification X and the ground program Py are provided. Given an instance and line of the program, training operates by obtaining the ground-truth values of statements (s'), operator (o*) and drop vector (d'). The statement and operator values are represented as one-hot vectors of size equal and number of operators (n.)), respectively in the DSL. The drop vector is multi-hot vector of size v with ones at positions corresponding to the variables in the program that can be dropped, i.e. variables that don't it appear in subsequent lines in the program. The step-wise loss L is the sum of cross-entropy losses between the actual and predicted statement and operator, and the binary cross entropy loss between each position in the actual and predicted drop vector. The task of predicting the
Training:
the number of statements (n.)
3

---

operator is an auxiliary task, i.. it is used only during training and not at inference time, and is found to improve the training performance. During training, obtain the updated state, the Exep module chooses the drop-index to be random entry from those positions in the drop vector d' that are ones. The right part of Figure 2 illustrates the process of training at step
Inference is done using complete anytime beam search (CAB) [29] where the time for search upper bounded by the timeout value. The CAB algorithm operates by performing different beam searches repeatedly in an outer loop. The pruning conditions of the beam search (i.e., beam size, expansion size) are weakened with each iteration of the outer loop, until a solution found. The inner loop consists of different steps of single beam search. At each step, the beam consists of the most promising program prefixes, with each prefix represented as a tuple of the current program state, synthesized program until now and the product of the probabilities of the statements in the synthesized program. To synthesize the next line of the program, prefixes are expanded by executing the statements in decreasing order of statement probabilities and taking the argmax of the drop vector probabilities. The statement and drop vector probabilities are obtained using the trained neural networks He and Ws. The search terminates if we find candidate program prefix that satisfies all N 10 examples. The corresponding program is the synthesized global solution Pg. Note that the search may fail and not discover global solution within the specified timeout. Appendix A gives details of training and inference procedures, and modules of PCCoder.
Inference:
3 Neural Per-Example Program Synthesis (N-PEPS)
As stated in Section 1, in this work, we decide break the complex problem of finding global solution Py that satisfies all N IO examples, into N smaller sub cuo--roobems... Each sub-probe sub-problem aims to find a program y3 that will satisfy only the I0 example r,, The cues present in these PF solutions are then aggregated to help guide the search for Pg- We constrain the process of breaking and combining to fit within the specified timeout value. The distribution of total timeout between these stages is treated as a hyperparameter. In this section, we discuss our process of finding PE solutions and follow it with a description of our neural network module that learns to combine the PE solutions.
3.1 Per Example Program Synthesis
We refer to the general framework of finding PE, solutions first and later aggregating the PE cues to find a global solution, as Per-Exanpe Example Program Synthesis (PEPS). We call the module that finds PE solutions as the PE Searches module. To train the PE Searches module, we use the PCCoder model as it is, except that it is trained to take a single I0 example as input as opposed to all the examples in X. We will call this trained model as the PE model. We allocate fixed value of PEPS timeout, which is the maximum time given to find each PE solution. The sum of PEPS timeouts across all PE solutions should be less than the total timeout, so that there is some time left for the CA module to aggregate the PE cues (i.e.. Nx x PEPS Timeout < Total Timeout). We start from the first example, and using the PE model, try to find a solution that satisfies it. Once found, we also check if this solution satisfies other examples in X. We record the fraction of 10 examples satisfied by pt. and call it the PE solution score ut. If p: satisfies all examples in X (i.e. u4 1.0), we stop and return P. = as the global solution. Otherwise, we proceed to find the next PE solution (based on the order of examples given in X). Note that is possible that for certain examples in X, we fail find a PE solution within the PEPS timeout. Once we have our list of M PE solutions (0 < M < N), which ideally satisfies all N examples but may not necessarily, we proceed to aggregating them. Note that when comparison with baselines is not requirement, we can increase speedup by finding PE solutions in parallel (see Appendix D.1 for more details).
3.2 Cross Aggregator
Notation: To formulate the program state, we define basic unit called an execution tuple (ET). An ET e = (p,S,t S,t) is tuple consisting of a program p, a subset S of example indices in X and a step number t. Executing the first t steps (lines) of a program on every example r, for i E S yields program state which we note as X Like PCCoder, we pool the representation of slots of the state corresponding to each example for i E S to obtain state embedding (see Section 2.1), hence making its size independent of the size of S. To represent different combinations of programs executed against different sets of examples at different time steps, we define list of such execution

---

tuples, with its size denoted by L. (P1, (1),0) 0) and (ps. (2) in the bottom right of Figure 1 are examples of such combinations. We then execute each entry to get a list of states Xe) This is followed by embedding each entry in states (()) using Ho to yield tensor of state embeddings H( (e)) E RR (henceforth referred to as (e) for simplicity). The white box towards the bottom of Figure 1 shows an example of obtaining a single entry of PE state embedding.
Motivation: To explain the motivation behind CA, let's look at Figure 1, which illustrates the process of synthesizing line 2 of Pg. Intuitively, at this step, we will want our aggregation mechanism to have more contribution from line 2 of P1 and Pa (i.e.. DROP solutions can be to take the sum or mean of the PE one-hot statement vectors (these form our ablation baselines detailed in Section 4.2). However, this strategy will fail for scenarios that require taking a non-trivial combination of the PE solution statements or cases where the global solution requires the generation of new statement that is not found in the PE solutions.
A simple way of aggregating the PE
In this work, we propose another way of anticipating what line of Pg comes next, that makes use of the execution information of the programs. The idea is to compare the state embedding obtained before executing line of P3 with the PE state embeddings corresponding to each step of execution of the PE solutions. Then, based on the learned relevance of these state embeddings, their corresponding next PE program statements can form valuable cues for synthesizing the next line. In other words, if particular PE program state has high relevance with the global program state at a given step, then the following PE program line is likely to be useful in synthesizing the next line of pg. We measure this relevance by employing cross-attention mechanism, with the query formed by the global program state embedding at step t, a key formed by the PE program state embedding at step t and the corresponding value formed by the PE program statement at t + 1. We take a set of such keys and values to form the key matrix K and the value matrix V, respectively.
For synthesizing line ++1 of Pg. the query Q is formed from the global state embedding at step t, denoted by H (e(equrry) E IIIZ, where qqerry = [[pg. {1, 2.. NN. },tt) t)]. The keys K E 22x2 are formed from the state embeddings (ekoy))) of the PE solutions. Let P denote the list of M discovered PE solutions, then the list of execution tuples @kys = [(Pme ()), where Pm P.j E (1, I E (0, 1, 1.-mm - 1}, making I, = M x N x Σ Ipml The corresponding PE solution statements form the values V E Lx (more details on how values are obtained is given later). In addition, we have the relation scores U __x1 obtained by taking the PE solution score Um corresponding to Pm that is part of each ET in ekeys. Note that entries in Ui are dependent only on the program part in the ET, and independent of the subset of example indices and the time index.
Model:
We add position encodings (depending on the time step value of each ET) to Q, K and V. This is followed by multiheaded relative attention between keys, values and query as described in Equation 3. For each head, we perform a scaled dot-product attention [28](Euation 1) and a form of relative attention i.e. taking mean of the relation scores and attention scores before normalizing with softmax and multiplying with values (Equation 2).
AH(Q, QKT Vih
(1)
1 + Att(Q,
RelAi( K, V)- softmax
V
(2)
2
M MultiHeadd Had Q, V) concat(head,, headz, ... head, heachead,,,.ddd.....
(3)
where head, = RelAtt(QW? KW.K vw.)
In the equations above, dg is the dimension of the key, W.O W.K. W. are the query, key and value projection matrices, T is the number of heads and W is the linear projection that combines the heads. The output from Equation is fed to positionwise cully-coneected feedforward network. We employ a residual connection [13] followed by layer normalization [3] before and after the feedforward network. The resulting encoding is then linearly projected and softmax is applied to get the prediction
of the statement for line t + 1 of Py- We see that our model resembles one layer of the transformer
Note that our formulation of relative attention differs from the formulation used in Shaw et al. [25]. Hellendoom et al. [14], where the relation scores added either to the query or values.
5

---

encoder block [28]. Since the keys and query come from different sources, we refer to our model as cross aggregator. Like standard transformers, we can stack multiple blocks of CA. However, since we are operating on low timeout (5s), we opted for a simple network consisting of only one layer. Details of model parameters can be found in Appendix D.3.
For a key corresponding to an ET consisting of the PE solution pm and having step index f, the value is associated with the statement vector (one-hot vector of size n2)) for step + 1 of Pm. Putting together the statement vectors for all execution tuples that are part of ekeys, we get tensor Pvalues of size L X ng. Embedding each entry in this tensor using an embedding layer Fr gives us V )(Pvalues of size L x Z. This is then fed as input to the model described above. The output from the model is then linearly projected to give the logits for the statement predictions E R=, for step t + 1 of the global program Pg- In addition to the statement predictions, we can also obtain the operator predictions E RRT,, starting from the operator vector (one-hot vector of size n.)) and following a process similar to the statements, except that we use a different embedding and final projection layer. The right of Figure shows an example of how query (top) is combined with keys, values and relation scores (bottom) for our model.
Obtaining V:
3.3
Training
The two main components of N-PEPS, the PE Searches module and the Cross-Aggregator, are trained separately. To create samples for training the PE model, we take one data point (XX = {ra}/=1 and Po) from the GPS approach and create N data points out of it. Since we do not have supervision for the PE solutions, for every example r; in X, we use Ps as a proxy for ground-truth PE solution. We believe that using Py as proxy supervision even though not being entirely correct, forces the PE search component to avoid overfitting to a single example and hence is more likely to produce PE solutions that generalize to examples outside the ones given as specification (see Appendix D.2 for more details).
For training the CA module, generate data points that we call aggregator instances. Each aggregator instance consists of X, a list Y of tuples of PE solutions p; and corresponding PE solution scores Ug and global program Pg- The p, 's and u, 's are generated via CAB from trained PE model (more details on how they are generated in Appendix C.2). Given X and Y as input, the objective is learn the parameters of the CA module such that the output is the wise statement and operator predictions corresponding to Pg. The net loss at step / is the sum of two terms: (a) cross entropy loss between the predicted statement 3 (obtained from CA) and the actual statement vector s' (obtained from p)): (b) cross entropy loss between the predicted operator o' and the actual operator vector o'. Like PCCoder, the operator loss is used as an auxiliary loss improve training. Note that for each aggregator instance, since we have X and Y to begin with, we need to compute the keys and values only once. However, the computation of query has to done each step of the global program execution. While training, since Py is known, we can use teacher forcing and increase efficiency by batching, where an element in the batch corresponds of one step of execution of Pg-
3.4 Inference
The process of inference in PEPS is the same as in PCCoder (see Section 2. 2)1,, except that in addition to the contribution from GPS, add another term that accounts for the contribution from CA. The contribution from GPS is obtained by using a GPS model that is trained as in standard PCCoder. The net value of the predicted statement at step is then obtained by taking a weighted contribution from the statement predictions from the trained GPS model 84_a and the statement prediction from the trained CA module S For predicting the drop vector d', we take contributions only from GPS. When a = O, our approach becomes equivalent to GPS.
s' s = 8 + == df
(1 a)) * +1-a
(4)
We perform CAB until we find a global solution or we exceed the specified timeout. The right part of Figure illustrates an example of the steps involved in synthesizing step 2 of pg-

---

4 Experiments and Results
Following prior work [4, 30]', we generate programs for training and testing, with each program consisting of five I0 example pairs, i.c., N = 5. The data generation process ensures that there is no overlap between the training and test programs, with programs being functionally von-equivalent to programs of shorter or equivalent lengths (see Appendix C.1 for more details), In the first set of experiments (henceforth referred to as E1). we generated 105036 training programs of length up to 4 (i.e., consisting of lengths 1, 2, 3, 4). For the second set of experiments (henceforth referred to as E2), we generated 189328 training programs of length up to 12. 10% of the training data was used for validation. To ensure robustness and reproducibility of results, for each method, we carry out experiments over 30 different test splits, where each split contains 500 programs of a specific length. For E1, we generate test programs of length 4, and for E2 we generate programs of lengths 5, 8, 10, 12 and 14. We learn separate GPS models and PE models for El and E2. All GPS results were obtained using the original PCCoder implementation' i A notable difference in our experiments from PCCoder [30] is that we consider a short timeout of 5s (in both E1 and E2. all methods), instead of 5000s and 10000s. This choice is representative of the timeout required for satisfactory user experience in program synthesis systems used in real-world interactive use-cases (such as FlashFill feature in Microsoft Excel [II]- Given a particular timeout value, record the Success Ratio, which is the fraction of test samples that succeeded in finding a global solution.
4.1 Initial Experiment: Analysis of PE Solutions
The promise of PEPS is rooted in the assumption that it is much easier to find PE solutions than finding a global solution. In order to test this hypothesis and get an idea the types of cues discovered by PEPS. we performed set of analysis experiments using data from E1. Using the trained PE model to find PE solutions, we consider two variants. The first variant called tot(k) is similar to the strategy of finding PE solutions that we use in PEPS (Section 3.1), where search for PE solutions sequentially (in the order of examples in X) until the discovered PE solutions taken together satisfy k examples in X (where l < 5). This helps us understand how much the coverage (= k)) from a list of PE solutions can be. In the second variant called (k), we record success by searching for PE solutions sequentially until we find an individual PE solution that satisfies & out of N examples in X. Here, the success ratio helps us assess how good a single PE solution is. In other words, can we rely solely on individual solutions do we need aggregate them? For the initial experiment, since no aggregation is done, we divide the timeout of 5s evenly amongst PE searches, i.e., each PE search gets 5 1s as the timeout value. For GPS, we use the trained GPS model with timeout of 5s.
Table 1: Success ratio of GPS, ind and tot for different values of & for test programs of length 4. i1)(1)
GPS
i2)(2)
in)(3)
ind(4)
ind(5)
tot(1)
tut(2)
tut(3)
tot(4)
tot(5)
77.0
99.2
95.4
85.4
70.4
43.2
99.2
97.6
97.0
94.8
82.4
gives the results of these analysis experiments on one of test splits for programs of length 4. Note that in tot, we are not aggregating the cues find global program. Hence, the value given under (5) is not directly comparable to GPS. We make a few observations. First, the success ratio increases with decreasing value of k. Therefore, as speculated, it is easier to find solutions that satisfy examples partially. Second, we see that even though the numbers for ind are encouraging, they are less than the corresponding values (for same k) for tot. This suggests that aggregating PE solutions is better than dealing with them individually. Third, the success ratio of tot(5) is better than GPS. This suggests there is potential in thinking of an architecture that can learn to combine these solutions. Even for cases where we couldn't 't find PE solutions that satisfy all 5 examples, we can hope to make use of the rich partial cues (indicated by high success ratios) coming from tot < 5).
Table
4.2 Methods
In addition to the standard GPS baseline (PCCoder [30]), we experimented with three ablation baselines that represent simple ways of aggregating the PE solutions without making use of the program state. Hence, they help us understand the role of PE cues alone. These baselines are: (i)
We used the implementation from PCCoder [30], at http://giitubbooo//att////CCCCC (MIT License) for data generation and obtaining results for PCCoder.
7

---

Model
Success Ratio
POCoder [30]
77.75 = 0.38
9
Sum PEPS
82.71 +: 0.32
Mean PEPS
82.68 1: 0.33
Mcan-PEPS-23
82.70 +
N-PEPS
86.22 = 0.25
Maa P515
LAET
6.A. LM
N-PEPS++0
87.07 +: 0.28
N-PeP5
Tim Takeo G1
Figure 3: Results for E1: (Left) Success Ratio with standard error for all models (top row = GPS); (Center) Success Ratio vs. time taken; (Right) Visualization of attention scores for N-PEPS-
Sum-PEPS: Replacing the contribution from CA module in Equation 4 by module that combines
the PE solutions by taking the sum of all PE one-hot statement vectors; (ii) Mean-PEPS: Same (i) except that sum is replaced by mean; (iii) Mean-PEPS+ZZ: Same as (ii) except that the one-hot PE statement vectors are multiplied by their corresponding solution scores before taking the mean. To understand the benefit of aggregating with our proposed CA architecture
top of the value brought
by the PE cues, we experimented with the following variations: (i) N-PEPS: Our neural model of PEPS described in Section 3.2 with U being zero tensor; (ii) N-PEPS +u: Same (i) but with U included. Complete details of hyperparameters for all methods can be found in Appendix D.
4.3 Results
For each test data point, record either success failure (based whether within 5s, find global solution or not) and the actual time taken to find a global solution. As described in Section 1. for all PEPS methods, we start by allocating PEPS timeout value that is less than Is (= N total timeout). We sum the actual time (< PEPS timeout) taken for finding individual PE solutions. The residual times (if any) left out is added and used for aggregation and global inference. Note that PEPS timeout and a are treated as hyperparameters that are chosen using the validation set.
To provide fair comparison across all methods, each test split is run using single core and single CPU thread with a timeout of 5s. To account for variability across machines, we chose to run test split on machine chosen randomly from collection of 7 machines of similar configuration (Google Cloud instances with 120GB RAM cach)". We report standard error across the 30 test runs.
The left and center parts of Figure 3 show the success ratio and success ratio vs. time taken (average of the actual time taken) plots, respectively, for test programs of length when trained on programs up to length 4 (EI). The left part of Figure 4 shows the success ratio for test programs of lengths 5, 8, 10, 12 and 14, when trained on programs up to length 12 (E2). In both these settings, we observe that performance of the ablation baselines is better than GPS, illustrating the promise in the quality of PE solutions. When we use our CA module to aggregate these cues instead, we see that the performance improves even further. We used the default value of v = 11 used in PCCoder, which means that for programs of length > 8, certain variables will be dropped from the program state. Also, note that the results for test length 14 represent a case of length generalization. We show that in both these scenarios, our proposed method is quite advantageous", In addition, we compare the performance of N-PEPS with GPS for the cases of intent generalization, i.e., generalization of the synthesized program to examples other than those given as part of X (Appendix F.2) and when given longer timeout of 1000s (Appendix F.1). In both these settings, N-PEPS shows superior performance, highlighting its generality.
Main result:
The right part of Figure 3 shows a visualization of attention scores at / /= 2 and = 3 obtained from our best model under El for the example shown in Figure 1. This example represents case from the test set where N-PEPS succeeds in finding global solution, whereas other methods fail. As can be seen, the actual statement of p is DROP and our model indeed
Attention visualization:
'We additionally verify that different runs on the same machine produce similar results (Appendix D.6) 'See Appendix B for success cases of N-PEPS & Appendix F.3 and Appendix F.4 for empirical analysis of synthesized programs.
8

---

Model
Langth 5
Length 8
Length 10
Length 12
Length=
POCoder [30]
70.91
0.35
44.17 1: 0.45
28.18 i 0.33
19.69 0.34
14.71 1: 0.23
Sum PEPS
76,45
43.4 4: 0.56
28,96
0.27
20,94 0.32
15.67
0.32
Mcan-PEPS
75.79 = 0.31
44,42 + 0.51
29.55
= 0.29
21.45
0.27
16.35
= 0:27
Mcan-PEPS++3
75.99
0.32
44.49
+ 0.52
29.75 = 0.25
21.74 = 0.30
16.45
= 0.33
N-PEPS
79.18
0.31
47.23
1 0.49
32.3
+ 0.34
23.34 0.28
17.35
1: 0.31
N-PEPS+2
79.19 0.30
46,31
= 0.61
31.84 = 0.36
22.71 0.28
16.68 # 0.21
Figure 4: Results for E2: (Left) Success Ratio with standard error for all models (top row = GPS); (Right) Variation of success ratio with PEPS Timeout (top) and (below) for N-PEPS
gives relatively higher attention scores to of and pš. both of which correspond to the same statement. Similarly at é = 3, our model gives more attention to p. MAP (+-1) d Pg.
Variation with PEPS timeout and a: There is non trivial tradeoff in the division of the total timeout into the time given to find PE solutions and the time given to the CA module. A higher PEPS timeout results in better chances of discovering rich PE cues. This means that there may be less or almost no time needed for aggregation. On the other hand, if we start with a low PEPS timeout, the cues from PE solutions may not be good, but we have more time to perform aggregation. Also, there is a question of how much contribution should be taken from CA and how much from GPS, which is determined by the value of a. The right part of Figure 4 analyzes this tradeoff. In the top, we show the variation of success ratio with PEPS timeout and in the bottom, we have the variation with a, for the validation set under E2. We see that the performance improves with increase in PEPS timeout with slight decrease towards the end. Also, we see that generally higher values of a are better indicating that the contribution from CA is more important than the contribution from GPS.
Variants of K: In addition to obtaining H ((ekeys) in the way described in Section 3.2, we tried two other ways of composing the keys by vary- ing the set S in the execution tuple against which the PE solutions are executed.
Table 2: Performance of variants of K for E1
the first variant, PE solution Pm from the list P of M discovered PE solutions is executed against the global set X, i.e., @kays - [Pm {1, N..N. }, t)] where Pm E P and & E {0, 1pm 1}. We denote this variant as N-PEPS-PG (PG PF-global ET). the second variant, Pm is executed against the set S. consisting only of
Variant
Success Ratio
N.PEPS.PG
85.19
N-PEPS-PG-L
85,94 = 0.26
N.PEPS-PP PP
85.97 + 0.26
N-PEPS-PP4M
86.21 0.27
examples indices that Pm satisfies, i.e., 6 kkyys = [(mm {j),t) where j E Sm. We call this variant as N-PEPS-PP (PP PE-PE ET). Table 2 shows the test results of these variants for E1 with and without 2. We see that all the variants perform better than GPS and the three ablation baselines (N-PEPS variant used in Section 3.2 was chosen using the validation set). We see similar trend for E2 (see Appendix E).
N-PEPS
86.22 = 0.25
N-PEPS+U4
87.07 0.28
New operator discovery by N-PEPS: We were interested in determining that while synthesizing the global solution how often does N-PEPS rely on copying statements from the PE solutions and how often does generate new operators. We studied this trend for the cases when a 1.0, i.c.. contributions are taken from both CA and GPS as well as when a = 1.0, i.c., contributions are taken only from CA (Appendix G.2). This question important as helps us understand the generalization capabilities of CA outside the statements in the PE solutions. We found that CA alone (with a 1.0) capable of generating new operators. In addition, we found that the new operators are present as part of the nearest neighbours of the PE statements, thereby pointing to an increased likelihood of these being ranked higher in the beam search and hence being present in the global solution (see Appendix G.3 and G.4 for details).
5 Related Work
There have been numerous efforts on using deep learning for program synthesis [4, 6, 9, 15, 8, 17- 19, 21J. However, there is less work that uses the execution of partial programs to assist in synthesis.

---

PCCoder [30] is one such work, which we describe in Section 2.1. BUSTLE [20] reweighs the cub-expressions in bottom-up program synthesis using the intermediate values obtained by execution of sub-expressions along with property signatures. REPI. [10] executes partial programs using learned policy and value networks. Chen et al. [7] uses a neural encoder-decoder architecture to generate program tokens conditioned on intermediate states obtained from execution of partial programs. They work with the Karel DSL [22, 6] that contains loops and conditionals, an attribute missing from the DSL which we work with. Therefore, extending N-PEPS for Karel is interesting future work. Note that all the approaches mentioned above are examples of purely GPS approaches.
Few works use solutions that satisfy examples partially, to aid in program synthesis. Initial motivation for our work comes from FrAngel [26], which is a component-wiss synthesis system that relies on mining fragments of Java code that satisfy examples partially, given target program function signatures and a list of Java libraries. The mining of fragments as well as combination is done using a set of heuristics and predefined rules with no deep learning involved. Assuming that the user provides IO examples in order of increasing difficulty, Perelman et al. [24] iteratively refines a program, with the current program satisfying the sequence of IO examples encountered till now. STUN [1] extends the CEGIS [27] approach by providing domain-specific explicit unification operators for combining partial solutions while Alur et al. [2] uses decision trees for the same. Recently, BESTER [23] and later PROBE [5] perform bottom-up enumeration of programs in a loop by enumerating all programs that satisfy I0 examples partially. This is followed by heuristics-
selection of promising programs. However, as opposed to N-PEPS that automatically learns to aggregate partial solutions producing the global program in one shot, PROBE relies using these programs to iteratively update the weights of useful productions in their probabilistic grammar using a fixed update rule. This update can be viewed similar to our ablation baselines that do not the neural network based learned aggregation. The guided-search component of PROBE provides an interesting alternative to finding PE solutions. One way of incorporating this in our top-down setting might be to start with the CAB search as in GPS and then select promising solutions based on evaluating examples on prefixes of programs obtained during the beam search. It may be useful then aggregate the selected solutions using a neural architecture similar to ours.
6 Conclusions and Future Directions
In this work, we propose N-PEPS, where the idea is to break the problem of finding a program that solves all examples into two stages: (a) finding programs that solve single example (PE solutions) (b) aggregating the PE solutions such that it leads to a program that solves all examples. For aggregation, we propose a neural-network based multi-head attention architecture (CA module) that utilizes the state of program execution to learn to combine the PE cues. We note that program synthesis systems in general should be deployed with caution for use real-world applications. Blind trust on these systems can create chances for potential negative impact, as there might be cases where the generated program contains bugs, especially for unseen examples outside the specification. In the future, we want to work with programs that contain loops and conditionals [22, 7, 6]. Another interesting research direction would be to explore the interaction of N-PEPS with diito--distribution generalization settings like compositional generalization [16].
Acknowledgments and Disclosure of Funding
Hugo Larochelle would like to acknowledge the support of Canada Research Chairs and CIFAR for research funding. The authors would like thank Google Cloud for providing compute resources required for this project. We would like to thank the anonymous reviewers for their valuable comments and thorough engagement during the rebuttal phase that helped us improve our paper. We would also like to extend our vote of thanks to Daniel Johnson, Petros Maniatis. Jacob Austin, Koushik Sen, David Bieber, Sandeep Subramanian, Varsha Embar, Nicolas Gontier and Andreea Deac for feedback and comments on the draft that helped us improve writing. We would also like to acknowledge the quick and helpful response from Amit Zohar and Lior Wolf on queries related to the PCCoder implementation.
10

---

References
[1] Rajeev Alur, Pavol Cerný, and Arjun Radhakrishna. Synthesis through unification. In Interna- tional Conference on Computer Aided Verification, pages 163-179. Springer, 2015.
[2] Rajeev Alur, Arjun Radhakrishna, and Abhishek Udupa. Scaling enumerative program synthesis via divide and conquer. In TACAS, 2017.
[3] Jimmy Lei Ba, Jamie Ryan Kiros, and Geoffrey E. Hinton. Layer normalization, 2016.
[4] Matej Balog, Alexander L Gaunt, Mare Brockschmidt, Sebastian Nowozin, and Daniel Tarlow. Deepcoder: Learning to write programs. In International Conference on Learning Representa- tions, 2016.
[5] Shraddha Barke, Hila Peleg, and Nadia Polikarpova. Just-in- time learning for bottom-up enumerative synthesis. Proceedings of the ACM on Programming Languages, 4(0OPSIA)): 1 1-29, 2020.
[6] Rudy Bunel, Matthew Hausknecht, Jacob Devlin, Rishabh Singh, and Pushmeet Kohli. Lever- aging grammar and reinforcement learning for neural program synthesis. In International Conference on Learning Representations, 2018.
[7] Xinyun Chen, Chang Liu, and Dawn Song. Execution-guided neural program synthesis. In International Conference Learning Representations, 2018.
[8] Jacob Devlin, Rudy R Bunel, Rishabh Singh, Matthew Hausknecht, and Pushmeet Kohli. Neural Program Meta-Induction. In I Guyon, U V Luxburg, S Bengio, H Wallach, R Fergus, S Vishwanathan, and R Garnett, editors. Advances in Neural Information Processing Systems, volume 30. Curran Associates, Inc., 2017.
[9] Jacob Devlin, Jonathan Uesato. Surya Bhupatiraju, Rishabh Singh, Abdel-rahman Mohamed, and Pushmeet Kohli. Robustfill: Neural program learning under noisy i/o. In Proceedings of the 34th International Conference on Machine Learning Volume 70, ICML' 17, page 990-998. JMLR.org, 2017.
[10] Kevin Ellis, Maxwell Nye, Yewen Pu, Felix Sosa, Josh Tenenbaum, and Armando Solar- Lezama. Write, execute, assess: Program synthesis with a repl. In H. Wallach, H. Larochelle, A. Beygelzimer, d'Alchéé Buché-Bue,Ja E. Fox, and R. Garnett, editors, Advances in Neural Information Processing Systems, volume 32. Curran Associates, Inc., 2019.
[11] Sumit Gulwani. Automating string processing in spreadsheets using input-output examples. In Proceedings of the 38th Annual ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages, POPL '11, page 317-330, New York, NY, USA, 201 1. Association for Computing Machinery. ISBN 978 1784453349900. doi: 14144//92338511224423.
[12] Kavi Gupta, Peter Ebert Christensen, Xinyun Chen, and Dawn Song. Synthesize, execute and debug: Learning to repair for neural program synthesis. In H. Larochelle, M. Ranzato, R. Hadsell, M. F. Balcan, and H. Lin, editors, Advances in Neural Information Processing Systems, volume 33, pages 17685-17695. Curran Associates, Inc., 2020.
[13] Kaiming He, Xiangyu Zhang, Shaoqing Ren, and Jian Sun. Deep residual learning for image recognition. In Proceedings of the IEEE conference on computer vision and pattern recognition, pages 770-778, 2016.
[14] Vincent J. Hellendoom, Charles Sutton, Rishabh Singh, Petros Maniatis, and David Bieber. Global relational models of source code. In International Conference on Learning Representa- lions, 2020.
[15] Ashwin Kalyan, Abhishek Mohta, Oleksandr Polozov, Dhruv Batra, Prateek Jain, and Sumit Gulwani. Neural-guided deductive search for real-time program synthesis from examples. In International Conference Learning Representations, 2018.
11

---

[16] Brenden Lake and Marco Baroni. Generalization without systematicity: On the compositional skills of sequence-to-seve to-ueunence recurrent networks. In Jennifer Dy and Andreas Krause, edi- tors, Proceedings of the 35th International Conference on Machine Learning, volume 80 of Proceedings of Machine Learning Research, pages 2873-2882. PMIR, 10-15 Jul 2018.
[17] Woosuk Lee, Kihong Heo, Rajeev Alur, and Mayur Naik. Accelerating search-based program synthesis using learned probabilistic models. In Proceedings of the 39th ACM SIGPLAN Conference on Programming Language Design and Implementation. PLDI 2018, page 436-449. New York, NY, USA. 2018. Association for Computing Machinery. ISBN 9781450356985. doi: 141144//192336.3194441
[18] Maxwell Nye, Luke Hewitt, Joshua Tenenbaum, and Armando Solar-Lezamal Learning infer program sketches. In Kamalika Chaudhuri and Ruslan Salakhutdinov, editors, Proceedings of the 36th International Conference on Machine Learning, volume 97 of Proceedings of Machine Learning Research, pages 4861-4870. PMLR, 09-15 Jun 2019.
[19] Augustus Odena and Charles Sutton. Learning to represent programs with property signatures. In International Conference on Learning Representations, 2020.
[20] Augustus Odena, Kensen Shi, David Bieber, Rishabh Singh, Charles Sutton, and Hanjun Dai. (BUSTLE): Bottom-up program synthesis through learning-guni guiiiiggggdeddeeeee exploration. In International Conference on Learning Representations, 2021.
[21] Emilio Parisotto, Abdel rahman Mohamed, Rishabh Singh, Lihong Li, Dengyong Zhou, and Pushmeet Kohli. syurolyymbolic program synthesis, 2016.
[22] Richard E. Pattis. Karel the Robot: A Gentle Introduction to the Art of Programming. John Wiley Sons, Inc., USA, 2nd edition, 1994. ISBN 0471 107026.
[23] Hila Peleg and Nadia Polikarpova. Perfect is the enemy of good: Best-effort program synthesis. In 34th European Conference on Object-Oriented Programming (ECOOP 2020). Schloss Dugstubl-Leibniz- Zentuni-Zziz- für Informatik, 2020.
[24] Daniel Perelman, Sumit Gulwani, Dan Grossman, and Peter Provost. Test-driven synthesis. ACM Sigplan Notices, 49(6):408-411 2014.
[25] Peter Shaw, Jakob Uszkoreit, and Ashish Vaswani. Self-attention with relative position rep- resentations. In Proceedings of the 2018 Conference of the North American Chapter of the Association for Computational Linguistics: Human Language Technologies, Volume 2 (Short Papers), pages 464-468, New Orleans, Louisiana, June 2018, Association for Computational Linguistics, doi: 10.18653/v 1/N10-201111224
[26] Kensen Shi, Jacob Steinhardt, and Percy Liang. Frangel: component-base based synthesis with control structures. Proceedings of the ACM on Programming Languages, 3PPOPI.: 2019.
[27] Armando Solar-Lezama, Liviu Tancau, Rastislav Bodik, Sanjit A. Seshia, and Vijay A. Saraswat. Combinatorial sketching for finite programs. John Paul Shen and Margaret Martonosi, editors, Proceedings of the 12th International Conference on Architectural Support for Programming Languages and Operating Systems. ASPLOS 2006, San Jose, CA, USA, October 21-25, 2006, pages 404-415. ACM, 2006. doi: 1 168457711777
[28] Ashish Vaswani, Noam Shazeer, Niki Parmar, Jakob Uszkoreit, Llion Jones, Aidan N. Gomez, undefinedukasz Kaiser, and Illia Polosukhin. Attention all you need. In Proceedings of the 1 International Conference on Neural Information Processing Systems, NIPS' 17, page 6010, Red Hook, NY, USA, 2017. Curran Associates Inc. ISBN 9781577860999
[29] Weixiong Zhang. Complete anytime beam search. In Proceedings of the Fifteenth National/Tenth Conference on Artificial Inteligeecce/nnovatiy Applications of Artificial Intelligence, AAAI '98/IA1 '98, page 425 430. USA, 1998. American Association for Artificial Intelligence. ISBN 0262510987.
[30] Amit Zohar and Lior Wolf. Automatic program synthesis of long programs with a learned garbage collector. In Advances in Neural Information Processing Systems, pages 2094-2103, 2018.
12

---

Checklist
For all authors...
(a) Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope? [Yes]
(b) Did you describe the limitations of your work? [Yes] See first paragraph of Section 5.
(c) Did you discuss any potential negative societal impacts of your work? [Yes] See Section 6.
(d) Have you read the ethics review guidelines and ensured that your paper conforms to them? [Yes]
2. If you including theoretical results...
(a) Did you state the full set of assumptions of all theoretical results? [N/A]
(b) Did you include complete proof' of all theoretical results? [N/A]
3. If you ran experiments..
(a) Did you include the code. data, and instructions needed reproduce the main ex- perimental results (either in the supplemental material or as a URL)? [Yes] We re- lease the code, data, trained models and instructions needed reproduce the main experimental results as a public repository on GitHub at https :/g::////ii// /github, com/ thrivastavadiee sha/N-aaaaPSSS The values of hyperparameters and all implementation details are provided in the supplementary.
(b) Did you specify all the training details (e.g., data splits, hyperparameters, how they were chosen)? [Yes] Complete details present in Appendix C and D.
(c) Did you report error bars (e.g.. with respect the random seed after running experi- ments multiple times)? [Yes] See first paragraph of Section 4 and first paragraph of Section 4.3 for details of how error bars were calculated and for the actual numbers. In addition, we also report variations on different runs on the same machine in Appendix D.6.
(d) Did you include the total amount of compute and the type of resources used (e.g., type of GPUs, internal cluster, or cloud provider)? [Yes] See first paragraph of Section 4.3 as well as first paragraph of Appendix D.
4. If you using existing assets (e.g., code, data, models) curating/releasing assets...
(a) your work uses existing assets, did you cite the creators? [Yes] See footnote on page
6.
(b) Did you mention the license of the assets? [Yes] See footnote on page
(c) Did you include any new assets either in the supplemental material or as URL? [Yes] We release the code, data, trained models and instructions needed to reproduce the main experimental results as public repository on GitHub at : com/
shrivastavddi NEPSS...
(d) Did you discuss whether and how consent was obtained from people whose data you're using/curating? [N/A]
(e) Did you discuss whether the data you are using/curating contains personally identifiable information or offensive content? [N/A]
5. If you used crowdsourcing or conducted research with human subjects...
(a) Did you include the full text of instructions given to participants and screenshots, if applicable? [N/A]
(b) Did you describe any potential participant risks, with links to Institutional Review
Board (IRB) approvals, applicable? [N/A]
(c) Did you include the estimated hourly wage paid to participants and the total amount spent on participant compensation? [N/A]
13


Reviews:
[{"review_id": "DDyfC-jsMo", "reviewer": "Reviewer_Jkzr", "summary": "This paper addresses the problem of learning to synthesize a program that describes a sequence of array operations to realize the transformation between given input/output (I/O) examples. While most existing learning frameworks are designed to find a program that satisfies all I/O examples at once, sometimes it can be inefficient to consider all the examples at every iteration. This paper aims to improve the efficiency of a synthesizing program by aggregating multiple programs that are separately synthesized considering only one example. Specifically, the paper proposes a framework that first (1) finds N per-example programs where each of them satisfies only one of the N examples, and then (2) yields a program that satisfies all examples by combining all per-example programs using a proposed neural network with a multi-head cross-attention mechanism. The experiments show that the proposed framework outperforms a baseline (PCCoder) that considers all examples at once when given a tight time budget. Ablation studies verify the effectiveness of the proposed cross attention scheme. I believe this work studies a promising problem -- building a more efficient neural program synthesis framework and proposes an effective framework to address the problem with sufficient evaluation. Yet, I still have some concerns such as the limited scope and design choices (see below). Currently, I am slightly leaning toward accepting this paper and look forward to the authors' rebuttal.", "questions": "", "limitations": "", "rating": 6, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "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": "", "main_review": "## Paper strengths and contributions\n\n**Motivation and intuition**\nThe motivation for devising a more efficient neural program synthesis framework is convincing.\n\n**Novelty**\nTo the best of my knowledge, synthesizing per-example programs first and then learning to aggregate them to form a global solution is novel in the field of neural program synthesis.\n\n**Technical contribution**\n- The proposed multi-head cross-attention mechanism for aggregating per-example programs seems effective.\n- This work provides insights on neural program synthesis methods working under a limited time budget.\n\n**Parallel execution**\nWhile the proposed framework considers the total time consumed as $\\sum_{i}\\  the\\ time\\ of\\ finding\\ a\\ program\\ for\\ the\\ i\\text{-}th\\ I/O\\ pair + the\\ time\\ of\\ aggregating\\ them\\ programs$, I believe the proposed framework can potentially be extended to even reduce the running time via parallel execution. If I understand correctly, the process of finding per-example programs can run in parallel (while some per-example programs can be applied to more than one I/O pair) so that the execution time could be the summation of $\\max_{i}\\ the\\ time\\ of\\ finding\\ a\\ program\\ for\\ the\\ i\\text{-}th\\ I/O\\ pair + the\\ time\\ of\\ aggregating\\ all\\ programs$. \n\n**Clarity**\nThe overall writing is clear. The authors utilize figures well to illustrate the ideas.\n\n**Initial experiment**\nThe goal of the initial experiment is to analyze how per-example programs perform compared to a solution found by a global program synthesis baseline. I like the concept of this experiment, which aims to motivate the proposed framework, while I am not fully convinced by the way how results are interpreted (see below).\n\n**Ablation study**\n- Different variations of aggregating per-example programs such as taking summation or mean are evaluated (the table in Figure 3), suggesting the effectiveness of the proposed cross attention mechanism.\n- The trade-off analysis on dividing the total timeout into the time given to find PE solutions and the time given to the CA module is informative. This result seems to suggest that the CA module does not need much time. It seems that 5-0.8*5=1 sec for the CA module yields the best performance, which is surprisingly low.\n- Different variations of composing the keys by varying the set S in the execution tuple against which per-example programs are executed are evaluated, verifying the effectiveness of the proposed method.\n\n**Experimental results**\n- The presentation of the experimental results is clear and easy to follow.\n- The experimental results in the tables in Figure 3 and Figure 4demonstrate that the proposed framework outperforms a global program synthesis baseline (PCCoder) in terms of success ratio on test samples with varying lengths when the timeout is set to 5 seconds.\n- The success ratio vs. time taken result shown in Figure 3 shows that the proposed framework consistently outperforms PCCoder when taking more than 1 second of computation.\n- The attention visualization provides some insights into what the CA module learns.\n\n**Reproducibility**\nThe code is provided, which helps understand the details of the proposed framework.\n\n## Paper weaknesses & questions\n\n**Limited scope**\nWhile the proposed framework is interesting and inspiring, the evaluations are only limited to array transformation programs. I believe this paper would be much stronger and more convincing if the proposed framework was also evaluated in other popular program synthesis domains such as Karel and string transformation.\n\n**Clarity**\nThe writing of the method section is not easy to follow. I feel the authors try too hard to be precise by explaining all the details including the dimensions of all the representations and introduce too many notations, which actually stops the flow and makes it hard to read. Revising the section by balancing between giving high-level intuitions and important details would make it easier to follow.\n\n**Pairwise aggregation**\nThis work proposes to aggregate all the per-example programs at once. I wonder if it is possible to instead perform a sequence of pairwise aggregation to recursively produce the final global solution. It is also possible that the pairwise aggregation can run in parallel to save time. This also aligns well with the high-level idea of this work -- conquering sub-problems first for better efficiency.\n\n**Multiple blocks of CA**\nThe proposed framework work employs only one block of CA. As models with stacked attention modules have achieved exciting results in a wide range of domains, it would be interesting to see if stacking multiple blocks of CA would yield superior performance even it needs to take some extra time to compute, especially since CA does not need much time it seems (from Figure 4).\n\n**Programs with branching conditions and loops**\nIt seems to me that both PCCoder and the proposed framework can only synthesize programs consisting of a seq of operations. Yet, programs for many real-world applications often include branching conditions (e.g. if-else) and loops (e.g. while, for). I would like to hear the authors' opinion on how it can be extended to deal with those.\n\n**Combing the predicted statements of GPS and PEPS**\nI wonder what the intuition is for combining the predicted statements from both GPS and PEPS. It seems that, from Figure 4 bottom right curve, setting $\\alpha=1$ yields the best result, meaning that completely using the predicted statements from PEPS is enough.\n\n**Longer timeout**\nWhile there are definitely some applications that require methods with a tight time budget, there are still other applications that value accuracy more than efficiency. I would like to know how the proposed framework performs with a much longer timeout such as 1000 seconds compared to PCCoder.\n\n**Initial experiment**\nWhile I like the idea of employing this initial experiment to motivate the proposed framework, I am not entirely convinced by the way the result is interpreted. I believe tot(5) and GPS are not directly comparable. Imagine we are solving a hard optimization problem with many constraints. Saying tot(5) (i.e. solve the optimization with some constraints removed) can solve the optimization problem in more cases compared to GPS (i.e. actually solve the problem) does not make much sense because solutions found by tot(5) might not even be meaningful at all. That being said, tot(5) does not tell anything how possible the PE solutions can be combined.\n\n**Supervision of PE**\nThe paper states \"we use $p_g$ as a proxy for ground-truth PE solution\".\nIsn't this actually \"wrong\" supervision since $p_g$ might contain some redundant operations that do not need to be applied to some \"simpler\" I/O pairs?\n\n**Missing related works**\nI believe some prior works can be incorporated to make the related work section more comprehensive:\n- Synthetic Datasets for Neural Program Synthesis\n- Improving Neural Program Synthesis with Inferred Execution Traces\n- Neural Program Synthesis from Diverse Demonstration Videos \n- Neural Scene De-rendering \n- Learning to Describe Scenes with Programs\n- Learning to Infer and Execute 3D Shape Programs\n\n**Minor bugs in code**\nIt is great to include the code so that reviewers can understand the paper better even by just tracing the code. However, it is also encouraged to make sure the code is runnable so that the results can be reproduced, The provided code has several bugs and it took me a long while to make it runnable. These are just some of the minor bugs that I ran into when trying to reproduce the results (I lost track in the middle because there are many): \n- missing dependencies: numpy\n- Code/scripts/solve_problems.py line 24: a line break is missing\n- Code/scripts/solve_problems.py line 269: duplicated `help`\n- Code/scripts/gen_train_programs does not run with line 264 `range(min_len, args.max_train_len + 1)` and only works when setting it to start from `min_len+1`. It can't generate program with length equal to zero.\n- Code/scripts/gen_train_programs.py line 294: should also `mkdir` when the dir does not exist\n- Code/scripts/gen_agg_instances.py: inconsistent use of tabs and spaces in indentation\n\n\n## Other metrics\n\n### Relevance and significance\n- Reasonable contribution to a minor problem\n\n### Novelty\n- One idea that surprised me by its originality, solid contributions otherwise\n\n### Technical quality\n- Technically adequate for its area, solid results\n\n### Experimental evaluation\n- Sufficient evaluation w.r.t. most criteria\n\n### Clarity\n- It is mostly clear, but improvements are needed, as recommended in the detailed comments.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Described in the main review section.", "review_text": "", "extra_scores": {"ethical_concerns": "I currently do not recognize any potential negative impact or ethical concerns for this work.", "needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "17"}, "extra_text": {}}, {"review_id": "9L5zeBhx49T", "reviewer": "Reviewer_syaz", "summary": "This paper proposes a new approach for neural program synthesis by first searching for per-example solutions and then learn to combine them into a global solution. The paper uses PCCoder for synthesizing the per-example solutions, and uses an aggregation model based on cross-attention mechanisms. The aggregation model attends to the partially executed program states by the per-example programs in order to choose the next program token. The proposed technique is evaluated on a DSL involving computation on integers and list of integers, and is shown to achieve better performance than PCCoder. ", "questions": "", "limitations": "", "rating": 7, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "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": "", "main_review": "Overall, the idea of first synthesizing per-example programs and then combining them in neural program synthesis is interesting and worth exploring. The paper considers and evaluates many different design choices in their approach, which is a plus. The writing of the paper is clear and easy to follow (except too many abbreviations). However, I have some concerns on how generally applicable the proposed approach is, therefore its significance. Please see the following questions for more details.\n\nQuestions for authors:\n- It seems that the way the proposed aggregation model operates is by choosing one of the next operators from the per-example programs as the next operator in the global program. This can only generate global programs that are stitches of the per-example programs. For a lot of domains this is not likely to work, and more complex ways to join the per-example solutions might be necessary (e.g. adding conditionals). How often does the proposed method generate mere stitches of the PE programs, and how often does it generate programs that contains new operators? \n\n- Is there any examples of non-trivial combination of PE solutions performed by the proposed approach? It's not clear whether the current approach is going to be helpful for other domains where non-trivial combination is required. So experiment on another domain would also be helpful.\n\n- With alpha being a hyperparameter, the proposed approach is using global program search (GPS) as part of itself. If we fix alpha=1, what are the results over all evaluation settings? This way, the comparison will be cleaner. \n\n- What is the takeaway from the N-PEPS variants? They all seems to have a similar performance. Which option does the author recommend?\n\n- The authors might want to include a discussion on the literature on version space algebra used in program synthesis in the related work, since that approach is on combining per-example solutions to a global solution.\n\n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "The limitations and potential societal impacts are addressed in the conclusions.\n", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "4.5"}, "extra_text": {}}, {"review_id": "4KL-zFNyp0d", "reviewer": "Reviewer_vnpm", "summary": "The paper proposes a method for neural synthesis of straight-line programs from I/O examples that works by learning\ncandidate solutions for individual examples and then combining their instructions into an overall solution using a\nseparate model. They build upon prior work on the DeepCoder dataset (PCCoder) that remains SOTA for neural-guided search\non these programs, and extend it with a second search procedure to assemble lines from per-example candidate solutions\ninto an overall solution. The resulting search significantly outperforms the PCCoder baseline with roughly the same loss\nof generalization to longer programs.", "questions": "", "limitations": "", "rating": 7, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "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": "", "main_review": "\nStrengths:\n- An original idea for straight-line synthesis – use programs satisfying individual examples as a vocabulary of\n  possibly-useful instructions, and learn to aggregate them into a global solution.\n- Strong empirical results with investigation of attention and limited generalization.\n- Well-described and rigorous evaluation setup.\n- Decent overview of related work.\n\nWeaknesses:\n- Some choices in the architecture could be better motivated or investigated. The authors already compare to several\n  ablations, but they come too late in Section 4. The paper lacks a high-level description of the current encoding\n  process and its explored alternatives somewhere around page 5. Currently, the brief \"Motivation\" paragraph sets up\n  _why_ PEPS looks at per-example program states and lines as clues, but then stops just short of explaining _what_ PEPS\n  could do with those states/lines at an equally high level.\n- Generalization experiments are lacking. The only one presented is length generalization from 12 to 14 lines, which is\n  not even particularly ambitious (of course, that still drops every model's performance by ~26%). In contrast, prior\n  work on by-example synthesis such as PCCoder, Flash*, RobustFill is also concerned with example overfitting in\n  addition to length or compositional overfitting. Specifically:\n  - The best model of PCCoder is trained to embed 10 examples but only presented with 5 examples at test time. How would\n    an equivalent version of PEPS's cross-aggregator model perform? As presented, it should be able to aggregate any\n    variable number of programs that was found in the first phase, but it learns its cues based on the set of available\n    keys (program states/lines), which at training time is induced by available I/O examples. Would a bigger set of keys\n    yield a stronger cross-aggregator (thanks to a richer sample of state features) or a weaker one (thanks to reliance\n    on the higher chance of better-matching PE program being there)?\n  - Flash*, RobustFill, Karel, and many other program synthesis settings value _intent generalization_: whether the\n    found program satisfies not only the given examples but also a hidden one (in assumption that the given 5\n    sufficiently define the intent). DeepCoder and PCCoder do not measure it, presumably because their search methods\n    are not amenable to that objective (the trained models optimize correctness w.r.t. the given 5 examples). But PEPS\n    is much more powerful! In a sense, it already optimizes example generalization – the whole point of\n    cross-aggregation is to use programs that satisfy _some_ examples as building blocks or cues to the program that\n    satisfies _more_ examples. We might discover that this method learns to synthesize a _more generalizable_ program,\n    even for examples not shown to the aggregator model. That would be a very significant finding for the field.\n\n\n## Opportunities for improvement\n\nRelated work might discuss connections to learning of decision trees and older set-cover driven techniques to synthesize\nif-else chains in programming by examples. They also take programs that satisfy a subset of examples, and delegate\nsatisfaction of the remaining ones recursively to the program in the \"alternative\" branch. In contrast to PEPS, they use\nall learned programs as independent branches at test time - not an option for this DSL.\n1. Alur, R., Radhakrishna, A., & Udupa, A. (2017, April). Scaling enumerative program synthesis via divide and conquer.\n   In International Conference on Tools and Algorithms for the Construction and Analysis of Systems (pp. 319-336).\n   Springer, Berlin, Heidelberg.\n2. FlashFill and FlashMeta: algorithms for learning If/ElseIf/Else chains.\n\nThe current matching process is based on similarity of _the current program state_ with _the state of each candidate\nprogram right before the line of interest_. Counter-intuitively, it does not consider whether relying on that line would\nbring the program state \"closer\" to desired output. In fact, the \"final output\" part of the state seems underutilized\nand might even be superfluous. As such, the aggregator network does not rely on instruction _semantics_, only on its\nsyntax and its proximity to the current state.  \nPossible concrete suggestions: split Equations 1-3 into two attention blocks, one against keys={states before each line} and one\nagainst keys={states after each line}. Or concatenate them before embedding the key matrix. Or max-pool from each\n(before, after) pair to form the key matrix – there are many architectural options.\n\nHow often is the synthesized line has the same operator, or even identical to the lines the aggregator attends to? It\nseems to be the case for most of the examples. Would a copy mechanism for $o_t$, or even $s_t$ perform just as well?\nEven if it makes occasional mistakes, it might cut down inference time a little, which would free up search budget.\n\n## Clarity\n\nMost parts of the paper are clear, and include much-appreciated diagrams for the search process and model pipeline. Some\nenhancements:\n- High-level description of cross-aggregation and its ablations (see Weaknesses above).\n- Usage of the term \"GPS\" as a substitute for \"baseline PCCoder\" is confusing, especially in Section 4 when they are\n  used interchangeably and inconsistently. There seems to be no need to introduce a new, more general term, if the paper\n  explores exactly one baseline instantiation of it.\n- Equation 4 does not type-check (at least in my brain).  \n  First, the predicted statement $\\hat{s}^t$ is multiplied by a\n  real scalar. Previously, $s^t$ was defined as a one-hot vector (L97), and $\\hat{s}^t$ as its estimate (L214). I\n  suppose in practice $\\hat{s}^t$ likely means predicted logits and thus Equation 4 is meant to be interpreted\n  literally, but that was never properly defined in the paper 🙂  \n  Second, using real-valued subscripts $\\alpha$ and $1-\\alpha$ to obscurely denote \"from cross-aggregation\" and \"from\n  program search\" respectively does not make much notational sense.\n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "\nA brief note on impact is included in Section 6, likely sufficient for the paper's topic area.\nI did not find any explicit discussion of limitations anywhere.\n", "review_text": "", "extra_scores": {"ethical_concerns": "\nNo issues or concerns.\n\n", "needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "6"}, "extra_text": {}}]

Author rebuttal:

Meta-review: The paper presents a new technique for synthesizing straight-line programs from input-output examples. The core novelty in the technique is that rather than trying to synthesize a program that works correctly for all available examples, the algorithm first finds separate programs that work for each individual example and then uses a cross aggregator to merge the individually working programs into a program that works correctly on all inputs. 

As the authors point out in their related work section, there is precedent for this idea in the program synthesis community, but this has never been done before in a neural setting. 

The authors addressed many of the questions and concerns raised in the reviews and provided a very thorough rebuttal. I think the main open question is the generality of the technique, since it is only evaluated on an important but limited domain, and it is not clear how to generalize it to more complex settings. 

That said, this paper presents an interesting and novel contribution and should be accepted.


Decision: Accept (Poster)