CrossBeam: Learning to Search in Bottom-Up Program Synthesis
Authors: Kensen Shi
Hanjun Dai
Kevin Ellis
Charles Sutton
Venue: ICLR 2022 Poster (2022)
Keywords: Program Synthesis
Bottom-Up Search

Abstract: Many approaches to program synthesis perform a search within an enormous space of programs to find one that satisfies a given specification. Prior works have used neural models to guide combinatorial search algorithms, but such approaches still explore a huge portion of the search space and quickly become intractable as the size of the desired program increases. To tame the search space blowup, we propose training a neural model to learn a hands-on search policy for bottom-up synthesis, instead of relying on a combinatorial search algorithm. Our approach, called CrossBeam, uses the neural model to choose how to combine previously-explored programs into new programs, taking into account the search history and partial program executions. Motivated by work in structured prediction on learning to search, CrossBeam is trained on-policy using data extracted from its own bottom-up searches on training tasks. We evaluate CrossBeam in two very different domains, string manipulation and logic programming. We observe that CrossBeam learns to search efficiently, exploring much smaller portions of the program space compared to the state-of-the-art.


Published as a conference paper at ICLR 2022
CROSSBEAM: LEARNING TO SEARCH IN BOTTOM-UP PROGRAM SYNTHESIS
Kensen Shi
Hanjun Dai
Kevin Ellis Cornell University
Google Research ksh @goog el com com
Google Research hada @egoogllee.co... com
1 iiscoorneell.. .dd:
Charles Sutton Google Research charleesuttonn@gogle..coo com
ABSTRACT
Many approaches to program synthesis perform search within an enormous space of programs to find one that satisfies a given specification. Prior works have used neural models guide combinatorial search algorithms, but such approaches still explore a huge portion of the search space and quickly become intractable as the size of the desired program increases. To tame the search space blowup, we propose training a neural model to learn a hands-on search policy for bottom-up combinatorial search algorithm. Our approach,
synthesis, instead of relying called CROSsBEAM, uses the neural model to choose how to combine previously- explored programs into new programs, taking into account the search history and partial program executions. Motivated by work in structured prediction on learn- ing to search, CROSsBEAM trained on-policy using data extracted from its own bottom-up searches on training tasks. We evaluate CROSSBEAM in two very dif- ferent domains, string manipulation and logic programming. We observe that CROSSBEAM learns search efficiently, exploring much smaller portions of the program space compared state-of-the-art.
INTRODUCTION
Program synthesis is the problem of automatically constructing source code from specification of
what that code should do (Manna & Waldinger] [971 Gulwani et al. 2017). Program synthesis has been long dogged by the combinatorial search for a program satisfying the wheiification-hille is easy to write down input-output examples of what a program should do, actually finding such a program requires exploring the exponentially large, discrete space of code. Thus, natural first instinct is to learn to guide these combinatorial searches, which has been successful for other discrete search spaces such as game trees and integer linear programs (Anthony et al. 2017 Nair al. 2020).
This work proposes and evaluates a new neural network approach for learning to search for pro- grams, called CROSsBEAM based on several hypotheses. First, learning to search works best when it exploits the symbolic scaffolding of existing search algorithms already proven useful for the problem domain. For example, AlphaGo exploits Monte Carlo Tree Search (Silver et al. 2016), while NGDS exploits top-down deductive search (Kalyan et al.) 2018 We engineer CROSSBEAM around bottom-up enumerative search (Udupa et al. 20133), backbone several successful recent program synthesis algorithms (Shi et al. 2020a Odena et al. 2021 Barke al. 2020). Bottom- up search is particularly appealing because captures the intuition that a programmer can write small subprograms first and then combine them get the desired solution. Essentially, model can learn to do soft version of a divide-and-conen -onnuuue strategy for synthesis. Furthermore, bottom-up search enables execution of subprograms during search, which much more difficult in top-down approach where partial programs may have unsynthesized portions that impede execution.
"qqual contribution.
I Equal contribution. thub. httpps///giithhbb.ccm/////// hww.:/oggge..eeeeeaeceocorrrooo

---

Published as a conference paper at ICLR 2022
Search Context
Beamn search Uriqueeanndrriieer
Input / Output Examples
CroesBeam Model
Argument Lists
Repeatedly loop operations
DSL
Operation
Main Synthesis Loop
Inputs,
Set of Explored
f(+)
Constants
Values
Execute candidate programs
Figure 1: An overview of CROSSBEAM. The search builds a set of explored values, starting with the inputs and constants. It repeatedly loops over all DSL operations, and for each operation, the model takes the search context and produces argument lists for that operation, choosing among the previously-explored values. Executing the operation on the argument lists produces new values.
Second, the learned model should take a "hands-on" role during search, meaning that the learned model should be extensively queried to provide guidance. This allows the search to maximally ex- ploit the learned heuristics, thus reducing the effective branching factor and the exponential blowup. This is in contrast to previous methods that run the model only once per problem (Shi et al.) [2020a) Balog et al. 2017), or repeatedly but at lower frequency (Barke et al. (020).
Third, learning methods should take the global search context into account. When the model is choosing which part of the search space to explore further, its decision should depend not only on recent decisions, but on the full history of what programs have already been explored and their exe- cution results. This is in contrast to hill-climbing or genetic programming approaches that only keep the "best" candidate programs found far (Schkufza al. 2013 Shi et al., 2019). or approaches that prune or downweight individual candidate programs without larger search context (Zobar & Wolf 2018: Odena al.) 202T). Search context can be powerful because one subprogram of the solution may not seem useful initially, but its utility may become more apparent after other use- ful subprograms are discovered, enabling them to be combined. Additionally, the model can learn context-specific heuristics, for example, to combine smaller expressions for more breadth earlier in the search, and combining larger expressions when the model predicts that it is closer to a solution.
Combining these ideas yields CROSSBEAM, bottom-up search method for programming by ex- ample (Figure I]. At every iteration, the algorithm maintains a search context that contains all of the programs considered so far during search, as well as their execution results. New programs generated by combining meviously-exxpoore
programs chosen by a pointer network (Vinyals et al., 2015). The model is trained on-policy using beam-aware training (Negrinho et al.) [018] 2020), i.e., the training algorithm actually runs the CROSsBEAM search, and the loss function encourages the model to progress towards the correct program instead of other candidates proposed by the model. This avoids the potential problems of distribution shift that can arise if the search model is trained off-policy, as in previous works for leamning-base based synthesis (Devlin et al. 2017 Odena et al., 202T
On two different domains, we find that CROSsBEAS EAM significantly improves over ttate-of-the-art methods. In the string manipulation domain, CROSSBEAM solves 62% more tasks within 50K candidate expressions than BUSTLE (Odena et al. 2021) on the same test sets used in the BUSTLE paper. In inductive logic programming. CROSSBEAM achieves nearly 100% success rate on tasks with large enough solutions that prior state-of-the-art art has 0% success rate.
2 CROSSBEAM OVERVIEW
In this section we provide an overview of CROSSBEAM, leaving model and training details to Sec- tion In our task of program synthesis from input/output examples, we have a domain speciiii language (DSL) C describing space of programs, and a set of example inputs I = = {T,,.... IN and corresponding outputs
(Oi,.... ON}. The goal to find a program P(L) O, for all i E {1 {1...N} J... The DSL L describes atomic values (constants and input vari- ables) and operations that can be applied to arguments to produce new values. Programs in L are arbitrarilynnested compositions of operations applied to atomic values other such compositions.
E such that
Bottom-Up Enumerative Search. CROSsBEAM extends a basic bottom-up enumerative search algorithm, originally from Udupa et al. (2013) and recently used in other synthesis works (Shi et al.) 2020a; Barke et al.) 2020; Odena et al. 202I This basic enumeration considers programs in order of increasing size (number of nodes in the abstract syntax tree), starting from the input variables
2

---

Published as a conference paper at ICLR 2022
Algorithm The CROSSBEAM algorithm, with training data generation in blue
Input: Input-output examples (Z, O), DSL C describing constants Consts and operations Ops, and (during training) a ground-truth trace T
Output: A program P E L consistent with the examples, and (during training) training data Dr
Auxiliary Data: A model M trained as described in Secciinn 3 and beam size K
1: S - Consts UI
> A set of explored values, initially with constants and input variables A set of training datapoints (during training)
2: Dr +-0
3: repeat until search budget exhausted
4:
for all op E Ops do M op, O),
5:
A <
Draw K argument lists from the model D [a1..... On is an argument list b Evaluate the candidate program The value has not been encountered before D Store execution history
6:
for all [a1..... .a.....,ayy an) E A do
7:
V t EXECUTE(OP, [a1..... anl)
8:
i & S then
9:
V.op < op, V.rrylist +- [u1, (01,...;0 Unn
10:
S (V)
11:
V = O then return P EXXPESSIONO()). Dr
Solution found
12:
13:
if Is Training A T = op then
DT t DT U ( op, I. O), T),T (0)..ragarit)) if lrrllit & A then
Save model inputs and ground-truth If beam search did not generate the ground-truth Continue as we did generate the ground-truth
15:
S SUSUU {T[O]} (.pop(0)
17:
and DSL constants. For each program, the algorithm stores the value that results from executing the program on the inputs. Then, at each iteration of search, enumerates all programs of the given target size, which amounts to enumerating all ways of choosing DSL operation and choosing its arguments from previously-explored values, such that the resulting program typechecks and has the target size. Each candidate program results in new value, which is added to the set of explored values if it is not semantically equivalent (with respect to the I/O examples) to an existing value. Values constructed in this way store the operation and argument list used. Once we encounter a value that is semantically equivalent to the example outputs, we have found a solution and can recursively reconstruct its code representation. This search algorithm is complete, but the search space grows exponentially so it quickly becomes intractable as the size of the solution program grows.
CROSSBEAM Algorithm. To combat the exponential blowup of the search space, the CROSSBEAM approach (Figure 1 Algorithm 1) uses a neural model in place of complete enumeration in the basic bottom-up up search. We still build a set of explored values, but we no longer enumerate all argument lists nor consider programs strictly in order of expression size. Instead, the model determines which programs to explore next, that is, which previously-explon the next candidate program. More specifically, we repeatedly loop over all operations in the DSL. For each operation, the model takes as input the entire search context, including the I/O examples, the current operation, and the set S of previously-exploree values. The model defines distribution over argument lists for the operation, in the form of pointers to existing values in S. From this distribution, we can draw argument lists from the model using sampling or beam search, to produce candidate programs. Finally, we execute each of the candidate programs and add the resulting values S. with pruning of cemantically-equiaallee continues until a solution is found or the search budget is exhausted.
values to combine order to generate
values as in the basic bottom-up search. The search
Randomeen We use beam search to draw argument lists from the model during training. Because the model may choose the same argument list for the same operation in different itcrations of search, the search algorithm may stall if no new values are explored. This is especially problem- atic during evaluation, where we may search for long time. Therefore, during evaluation, instead of beam search we use UniqueRandomizer (Shi et al. 2020b), which draws distinct samples from sequence model incrementally by storing the previous samples in a trie so as to avoid duplicates. Using Unique
we draw distinct samples (argument lists) until we produce values that have not been seen yet, up to budget of X K samples per operation per iteration, where K is the "beam size" and À is a hyperparameter describing how hard we should try to produce K new values. During evaluation in our experiments, we set K A 10.
3

---

Published as a conference paper at ICLR 2022
Arguient
Ocamiton
Selector Module
Pg Pb
F
D PLg
Find cattry ate, int)
See Exploned Villans
Pp
Type Checking
Type Checking
Type Chasking
Weight
Es (value embecdings)
Vi
Po
-1
35
MMBCCC*, "1222"1
Potl
LSTM
soccific
Outrut Vatuee
encoders
Embedding Lookup
Embedding
Lookup
Search
Contoxt
Inout Valluns
Surmary
(search
vart var2
Modulo
context summaryy
Ex. (hansey
Search Contest
Model
Oubbut
Figure 2: Model that proposes candidate programs during search. Each new candidate program consists of an operation and an argument list. Each argument in the list is a pointer to a value produced from a previously explored program.
3 MODEL DETAILS
Our neural model for CROSSBEAM is policy for bottom-up search. It takes input an operation the DSL and a search context, and outputs a distribution over argument lists for the operation, in the form of pointers to previously-epploeed values. The model has four components (Figure 2): (1) the I/O module, (2) the value module, (3) the search context summary module and (4) the argument selector module. For different domains can make different design choices for these modules. For example, in the string manipulation domain, we leverage property signatures (Odena & Sutton 2020) in the same way as in BUSTLE (Odeaa et al. 2021), and for the logic programming domain, we propose two variants based on the MLP or GREAT Transformer (Hellendoorn et al. (019) architectures. Below we present the generic design of these modules; for details, see Appenndi
I/O module. The I/O module takes the input-output examples (I, as input and produces a d-dimensional vector representation eso E Rd that summarizes the specification. Depending on the application domain, one can use RNNs (Devlin et al., (017). property signatures (Odena & Sutton 2020), or other domain-specific approaches embed the I/O example into eso.
Value module. The value module embeds the set of explored values S into matrix Es E RR The i-th row of the matrix, Es,, is the embedding of the i-th explored value Vi E S. Each value embedding Ess, 8t + z; sums up two components. First, 8; is domain-specifii embedding that can be implemented differently for different domains, but likely using similar techniques as the I/O module. Second, a size embedding z; makes the search procedure aware of the "cost" of the value V,, To implement this, we compute min{ size(V,) V2), m, } and look it up in an embedding matrix in Rim,xe xd to get the size embedding 2,, where m, a maximum size cutoff for embedding purposes.
Search context summary module. This module summarizes the search context, which includes the set explored values S. the I/O examples (I, O), and the current operation op, into vector representation E Rd The search context summary e, would then be given to the argument selector module. Since the cardinality of S changes during the search procedure, and it should be ionnutation-ivvariant by nature, we
approach like DeepSets (Zaheer et al. (017)) to get a summary e, for Es. In particular, we set e, to be the max-poolle max-pooling over Es across the values. We then obtain e MLP MLLPop((e, ([c., elol) via operation-specine MLP top of the concatenation of the value embedding summary e, and the I/O embedding e1o-
Argument selector module. With all of the context provided above, the argument selector module is designed to pick the most likely sequences of arguments in the combinatorially large space of size |S] op.arity, where op.ority is the arity of the currently chosen operation. Since the arity of each op-
4

---

Published as a conference paper at ICLR 2022
eration is typically small, to approximately output the argument list with maximum likelihood with O((S) x op.arity) cost. This also allows to perform beam search to approximately select the K most likely combinations of arguments. Our LSTM uses the search context summary e, as the initial hidden state. At each argument selection step & E (1..... op.ority) we the LSTM's output gate h4 E Rd to select the argument from S. Unlike in the language modeling case where the decoding space is given by fixed vocabulary, here we have a growing vocabulary S. Inspired by pointer networks (Vinyals al.,
an autoregressive model (in our case autoregressive LSTM)
exp(h] Es,) Since 2015), we model the output distribution at the t-th step as p(V; he, S) = Eز exp(h? Esy)
not all values are type compatible for the 1-th argument of operation op, we mask out infeasible values before computing p(V; Se. After the model selects a certain argument de S at step t, the LSTM updates the hidden states with the embedding Es., and proceeds with the next step if t < op.arity. or stops if we have obtained an entire argument list for op.
Training. Unlike typical supervised learning, our model uses context that results from searching according to the model. One approach is provide supervision for how the model should proceed given a sandomly-generater search context. However, the resulting distribution shift could lead to inferior generalization. Thus, we instead train the model on-policy, where we run the model in search to produce realistic search contexts for training. Because the training data includes the model's 's previous decisions the search context, the model learns to correctly continue the search, e.g., extending promising search directions or recovering from mistakes.
The overall training algorithm can be found in Algorithm I, during training and collect supervised training examples for the model as it searches. Given task specified by (I,O) with a ground -round-truth program P. we create a trace T, which is a list of steps the search should take to construct P in bottom-up fashion. Each element T[:] E T contains an operation oop and an argument list T[i] arglist that builds one node of the abstract syntax tree for P. Then, in each search step with context S where we considering the operation Mil..op, we collect a training example with input (S, Tip..op I, O) and target T[i aryliss.. Note that we do not make a separate copy of for each training example, but rather we record the current size of S and refer to the final S for each task, since |S| grows monotonically during the search. During the search we also add [ to S, so that we may construct correct argument lists involving T[i in future steps. We use collected training examples to train the model using standard maximum likelihood training.
The main idea is that we run search
Note that T is not necessarily unique for given program P, because the syntax tree for P could be linearized in different orders. In this case, we sample ground-truth trace randomly from the possible orderings. We denote = P if T is possible trace of P. We then formulate the training loss as the expectation of the negative log-likelihood of the ground-truth argument lists under the corresponding search context and current model parameters 6:
((P.I.0:0) = EETT=
1 |Drl
Σ
log pl arglist S,op.I.
(I)
We take gradient descent steps in between searches on the training tasks, so that the model improves over time while producing better-quality data for gradient descent. To generate training tasks, we use a technique from prior work (Shi et al. 2020a; Odena et al., (02T) where we run the bottom-up enumerative search starting from different random inputs, randomly selecting explored values to serve as target outputs. Even though CROSsBEAM is trained using aandomly-generatee experiments show that it still performs well realistic test tasks. We train CROSSBEAM with distributed synchronized Adam optimizer on 8 V100 GPUs, with gradient accumulation of 4 for an effective batch size of 32. We generate 10M training tasks for string manipulation and IM for logic programming. The models train for at most 500K steps or 5 days, whichever limit is reached first. We use K 10 and learning rate 10-4 during training. After every 10K training steps, we evaluate on synthetic validation tasks to choose the best model.
tasks, our
4 EXPERIMENTS
Our experiments compare CROSSBEAM to state-of-the- art methods in two very different domains, string manipulation and inductive logic programming.
5

---

Published as a conference paper at ICLR 2022
on 38 Tasks
Results BUSTLE's SyGuS
30
Prog aate s0thoo000
-00
Contbean
Grostcoo (oomping evalutiont
Croueoon fundon sunngg
Grereeur (oemm scerth endlaiionn
BUSTLE
DeepCrter promeso seloctonn
Randiie boftriug search
Number
candidalle progperra
Figure 3: Results on the two sets of benchmark tasks used in the BUSTLE paper. For non- deterministic CROSsBEAM variations, we plot the mean over 5 trials with shading between the min- imum and maximum results over those 5 trials. CROSsBEAM is 15.9x (left) or 25.5x (right) more efficient than BUSTLE, in terms of the number of candidate programs needed reach BUSTLE'S 15 solves (left) or 44 solves (right). Overall, CROSS BOSSSBAAK BEAM solves 62% more tasks than BUSTLE.
4.1 STRING MANIPULATION
For the string manipulation domain, the same DSL, success criteria (satisfying the I/O amples), training task generation procedure, and test tasks as used in BUSTLE (Odena et al. 2021) See[Appendix B for details. The BUSTLE approach extends the same enumerative bottom-up search as CROSSBEAM, but BUSTLE trains a neural model to predict how useful values are (i.e., whether value subexpression of a solution) and prioritizes values during the search accordingly. BuS- TLEE is still a complete enumerative search and will eventually explore the entire space of programs in the DSL, and thus it still suffers from the issue of search space blowup, albeit much lesser degree than plain enumeration. In contrast, CROSsBEAM trades off completeness for exploration efficiency, as we have no guarantee that the model will eventually explore the entire search space.
We run CROSSBEAM on both sets of test tasks used to evaluate BUSTLE, with a search budget of 50,000 candidate programs. Every value obtained by applying an operation to an argument list, including those pruned due to semantic equivalence, is "candidate program." Figure 3 shows the number of programs synthesized as a function the number of candidate programs considered. Because CROSSBEAM is not deterministic due sampling argument lists with UniqueRandomizer, we run it times and plot the mean, minimum, and maximum performance.
We borrow the following comparisons and results from the BUSTLE paper. (1) BUSTLE refers to the best approach in the paper, i.e., using both the model and heuristics. (2) The baseline bottom-up enumerative search is the same as described in [Section 2] (3) RobustFill (Devlin al. 2017) is an LSTM that predicts end-to-end from the I/O examples to the program tokens. For RobustFill, "candidate program" is one unique sample from the generative model, obtained via beam search and ordered by decreasing likelihood. (4) DeepCoder-style (Balog et al. 2017) premise selection uses a neural model predict which DSL operations will be used given the I/O examples. The least likely operations according to the model are removed, and then the baseline bottom up search is run.
Figure shows that CROSSBEAM significantly outperforms the other methods on both sets of bench- marks, on average solving 36.4 more problems in total compared to BUSTLE (an improvement of 62%). In fact, in order to match BUSTLE'S performance after 50,000 candidate programs, CROSS- BEAM considers about 20x fewer candidate programs. CROSSBEAM still outperforms BUSTLE when using a much larger budget of million candidate programs (Appendix C). Thus, we con- clude that CROSsBEAM explores the search space much more efficiently than the prior approaches.
Ablations. We perform an ablation study to quantify the effects of training the model on- on-policy and using UniqueRandomizer during evaluation. We try the following 3 variations of CROssBEAM:
Random training: instead of using beam search on the model to produce argument lists A during training, we instead obtain argument lists by randomly sampling values from the set S of explored values. As the search progresses, the search context (specifically the set 5) diverges from what the model would produce during evaluation. Hence, this variation trains the model off-policy.

---

Published as a conference paper at ICLR 2022
A P(X,Y) = 32 3 2) Ar(Z,))
JOIN TRANSPOSE
P(X,Y) = X)
P(X) = v(X)Vr(X)
} DISJUNCT
p(X) = p(X,Y)) V Y)
6(X)
: ((X ,
U) AT(U
} RECURSE
= = VE, ((X,U))A(X,)))) P(U.V)
P(X) = xX
CAST2-1
A Y) = (())A(())))) (V)
CASTI -22
zero(X) = (X = 0)
(primitive)
succ [x Y) = (X +1)) suce
(primitive)
eq(X, = YX=
(primitive)
B
Program in DSL
Translation to Prolog
RECURSE(
both zero (X, :- zero (X), zero (Y)
TRANSPOSF((er01--2)
subl (x, Y) :- succ (Y, X)
TRANSSPOSE(SUCeeSOO)))
add2 (X, Y) :- suce (X,2), succ (7, Y)
TRANSPOSE(
add3 (X, Y) :- succ (X, 2) add2 (2, Y)
JoIN(successor,
sub3 (X, Y) :- add3 (Y,X).
JoIN(successor,
(X, Y) :- bothh_zere (X, Y)
successor)))
p (X, X) :- subl (x, U) sub3 V), p VV,
Figure 4: A. (Top) Our four operators for building logic programs. Each operator builds new predicate p from smaller predicates (q. r, b). The disjunct and recursion operators automatically have different forms depending on the arity of their arguments. (Middle) We assume each predicate has arity 1 or 2, and automatically cast the arity of input predicates as needed using CAST2->1 1 and C2 (Bottom) The three primitive relations given to the system. B. Example program for the relation 3r = A cast from arity I to arity 2 (zero)-12) is performed automatically. This size 11 program represents recursive Prolog routine with clauses and 5 invented predicates, equivalent to saying that the relation 3r = y holds for (0, 0) and that it holds for (z. y) if it holds for (æ (z-11 1, y --3).
2. Beam search evaluation: instead of using UnnqueRand to draw argument lists A during evaluation, we simply perform beam search with the same beam size K = 10. Note that the beam search is deterministic, so the search is prone stalling if all argument lists result in values that are semantically equivalent to values already explored, leading to repeated looping without progress. This stalling behavior is quite apparent in experimental results.
Sampling evaluation: instead of using UniqueRandomizer to draw argument lists during evalua- tion, we sample K 10 argument lists according to the distribution given by the model. This leads to more randomness in the argument lists and less stalling, but some stalling can still oceur if the high-probability argument lists all produce values semantically equivalent to ones already explored. This motivates our use of UniqueRandomizer in normal CROSSBEAM, where we sam- ple up X K argument lists without replacement in search for semantically different values.
As shown in Figure 3. all of these ablations perform worse than normal CROssBEAM but better than all prior approaches. Interestingly, using beam search or sampling for evaluation results in the method being much more efficient when there are few candidate programs considered (i.e., when the search has not yet stalled), but using UniqueRandomizer allows normal CROssBEAM to reach higher performance later as the search continues to explore thousands of candidates.
Wallclock Time. Despite CROSsBEAM's impressive performance when controlling for the number of expressions considered, CROSSBEAM does not quite beat BUSTLE when we control for wallclock time (but it does outperform the baseline bottom-up search). However, this comparison is not com- pletely fair to CROSSBEAM. We compare to the BUSTLE implementation from the original authors, but this is an optimized Java implementation and was designed to enable easy batching of the model predictions. In contrast, CROSSBEAM is implemented in Python, and batching model predictions for all operations in an iteration and batching the UniqueRandomizer sampling are both feasible but challenging engineering hurdles that would lead to speedups, but are currently not implemented. In AAppeddx D. we discuss this comparison further with quantitative experimental results.
7

---

Published as a conference paper at ICLR 2022
Success Rate Random Logic Tasks of Varying Size
Success Rate (%)
60
CrossBeam (Transtormer)
CrossBeam (MLP)
Bottom--U
Melagol (Our DSL)
*
Metagol (README DSL.
Popper (Pred.
Popper (No Pred. Inv.
8
9
10
11
12
13
14
15
16
17
18
19
Task
Figure 5: Success rate of different methods on randomly-generate logic tasks in 30 seconds. CROSsBEAM maintains very high success rates the more difficult tasks where prior works fail.
4.2 INDUCTIVE LOGIC PROGRAMMING
Inductive Logic Programming or ILP (Cropper et al. 2021 is the program synthesis problem of learning logical relations (predicates) from examples, which we specify with truth tables. Here, these predicates are represented by logic programs (Prolog or Datalog; see Bratko (raako expressing first-order logical statements with quantified variables and recursion. ILP systems have been used to make inferences over large knowledge graphs (Muggleton & Lin 2013), do programming-by- example (Lin al. 2014), and perform common sense reasoning (Katz et al. 2008).
Search in ILP is especially difficult when the learned programs can be recursive, and when they can define auxiliary "invented" predicates (analogous to defining helper subroutines). As such, most ILP systems limit themselves to learning handful of logical clauses, and many forego either recursion or predicate invention. We apply CROSSBEAM to ILP with the goal of synthesizing larger programs with both recursion and predicate invention. We first define DSL over predicates (Figure 4) that works by building larger predicates out of smaller ones, starting from primitive predicates computing successorship, equality, and the "zero" predicate. Because CROSSBEAM executes every partially- constructed program, we think of each predicate as evaluating to the set of tuples of entities for which the predicate true. To ensure this set remains small, we bound the arity of synthesized predicates (arity S 2) and work with entities in relatively small domain of numbers in {0. (O.....)) .9).
We study CROSsBEAM's ILP abilities by synthesizing both handomly-generalee and handcrafted predicates from examples, with the goal of answering the questions of whether the system can per- form predicate invention, whether it can learn recursive programs, and how compares state-of- the-art ILP systems. Our synthetic test set contains tasks of varying size, i.e., the minimum number of nodes in the expression tree of a solution. For each size (5...., 19), we randomly select 50 tasks among all possible tasks of that size, excluding those appearing in the training dataset Our handcrafted test set, inspired by Peano arithmetic, comprises 30 common mathematical relation- ships, e.g., whether number is even, if number is greater than another. For each synthesis task, the system is given every positive/negative example for numbers in (O....,9) 9} as a truth table.
We run CROSSBEAT with either MLP- Transformer-basee value encoder for predicates (see Appendix A.2p. We compare with the classic Metagol (Muggleton & Lin 2013), a tate-of-the-aa system Popper (Cropper & Morel 2021a), and the basic bottom-up enumerative search. We run all methods for a time limit of 30 seconds per task. CROSSBEAM significantly outperforms all of the other methods in both test sets. We summarize our findings here with more details in Appendix E
Figure 5 shows the results on the randomly-generated test set, where CROSsBEAM achieves close 100% success rate tasks up to size 16 and over 50% success rate on tasks up size 19, while the success rates of all other methods drop to 0% by size 13. This is evidence that CROSS- BEAM is major forward step in tackling the issue of search space explosion. For the handcrafted tasks, CROSSBEAM achieves 93% success rate, versus a 60% success rate for Metagol and Popper Figure in in Appendix F.. CROSSBEAM also does not appear to struggle with recursion (every hand- crafted task can only be solved with recursion) and consistently solves problems requiring predicate
"W ran the bottom-up search to exhaustively explore all distinct values up to size 19 inclusive, which takes about hours. We sampled million of those values to serve training tasks. For sizes 5 and 6, there were fewer than 50 tasks used in training, included all such tasks in our synthetic
8

---

Published as a conference paper at ICLR 2022
invention (Popper without predicate invention solves 37%, which serves guide to what fraction of the problems require defining auxiliary predicates).
To our surprise, the baseline bottom-up enumeration also outperforms Metagol and Popper, least on our test sets where the domain of the predicates is small. To our knowledge, bottom-up enumer- ation (and pruning based on observational equivalence) has never been tried for ILP before.
5 RELATED WORK
Machine learning for program synthesis has been an active area (Gottschlich et al. 2018 Gulwani jet al. 2017 Allamanis et al. 2018). For example, DeepCoder (Balog et al. (017)) uses a learned model to select useful operations once at the beginning of search. Although this idea is pragmatic, the disadvantage is that once the search has started, the model can give no further feedback. Odena
& Sutton 2020) use property signatures within DeepCoder-stylee model for premise selection.
Many learning based approaches to synthesis can be viewed as using learning to guide search. Some methods employ models that emit programs token-by-token (Bunel et al.. 2018 Devlin et al. 2017 Parisotto et al. 2017). which can be interpreted as using learning to guide beam search. Recent
versions of this idea large pretrained language models generate programs (Chen et al. 2021
Austin et al. [021]. Rubin & Berant (202T) builds a semiiautooeerressive bottom-up generative model for semantic parsing, where the beam decoding is embedded in the model decoding to achieve logarithmic runtime. Alternately, top-down search can be guided by learning with a syntax guided al. 2018). Another line of work uses learning to guide a two-level search by first generating a sketch of the program (Nye et al. [201]] Murali et al.] 2018) or latent representation (Hong et al. (02T). None of this work uses execution information to guide the search, or uses the rich information from the search context, as CROSSBEAM does.
search over programs (Yin Neubig, 2017; Lee Lee
Execution-guidel neural synthesis methods use the results of executing partial programs to guide search, which is powerful source of information. Zohar & Wolf (2018) learns to write straight- line code line-by-line, and to ignore ("garbage collect") lines deemed irrelevant to further search. A similar approach is to rewrite a programming language so that it can be evaluated "left-to-right," allowing values to be used to prioritize a tree search in a reinforcement learning framework (Ellis et al. 2019). Similarly, [Cenn et al. (2019) use intermediate values while synthesizing program ing a neural encoder-decoder model, but again this work proceeds in a variant of left-to-right search that is modified handle conditionals and loops. To illustrate the potential differences between left-to-right and bottom-up methods, imagine that the correct program is f (A, B), where A and are arbitrary subprograms. Then if left-to-right search makes mistake in generating A, that search branch will never recover. In contrast, because bottom-up search maintains a population of many partial programs, it can build up subprograms A and B roughly independently. While all these execution guided methods have "hands-on" neural models, our approach differs by looking at the global search context-and learns to do so effectively because it learns on-policy.
Our string domain is inspired by the symbolic synthesizer FlashFill (Gulwani 2011 1) and subsequent work on sarring-basedd synthesis for string manipulation (Menon al. 2013] [Odena et al., 2021). |213]Oddeaa
Our use of imitation to guide search is inspired by work in learning to search (Daumé III al. 2009
Ross et al. 2011: Chang et al. (0155) and beam-aware training (Negrinho et al. 2018 2020).
6 CONCLUSION
CROSSBEAM combines several powerful ideas for learning- guided program synthesis. First, bottom-up search provides symbolic scaffolding that enables execution of subprograms during search, which provides an important source of information for the model. Second, the learned model takes "hands-on" role during search, having sufficient freedom to manage the effective branching factor of search. Third, the model takes the search context into account, building a continuous rep- resentation of the results of all programs generated so far. Finally, training examples are generated on-policy during search, so that the model learns correct followups for its previous decisions. Our experiments show that this is an effective combination: in the string manipulation domain, CROSS- BEAM solves 62% more tasks than B BUSTLE, and in the logic domain, CRossBEAM achieves nearly 100% success rate difficult tasks where prior methods have a 0% success rate.
9

---

Published as a conference paper at ICLR 2022
ACKNOWLEDGMENTS
The authors would like to thank Rishabh Singh and the anonymous reviewers for their helpful com- ments.
REFERENCES
Miltiadis Allamanis, Earl T Barr, Premkumar Devanbu, and Charles Sutton. A survey of machine learning for big code and naturalness. ACM Computing Surveys (CSUR), 51(4), 2018.
Thomas Anthony, Zheng Tian, and David Barber. Thinking fast and slow with deep learning and tree search. In Advances in Neural Information Processing Systems (NIPS), 2017.
Jacob Austin, Augustus Odena, Maxwell Nye, Maarten Bosma, Henryk Michalewski, David Dohan, Ellen Jiang, Carrie J. Cai, Michael Terry, Quoc V. Le, and Charles Sutton. Program synthesis with large language models. arXiv preprint 2rX1v:2108.07732, 2021. htttts:ssssaiiiit..///
abs/21000 2tt./2108.077733
Matej Balog, Alexander I. Gaunt, Mare Brockschmidt, Sebastian Nowozin, and Daniel Tarlow. DeepCoder: Learning to write programs. In International Conference Learning Represen- tations (ICLR), 2017.
Shraddha Barke, Hila Peleg, and Nadia Polikarpova. Just-in-time learning for bottom-up enumera- tive synthesis. In Object-Oriented Programming. Systems, Languages, and Applications (OOP. SLA), 2020.
Ivan Bratko. Prolog Programming for Artificial Intelligence. Pearson Education, 2001.
Rudy Bunel, Matthew Hausknecht, Jacob Devlin, Rishabh Singh, and Pushmeet Kohli. Leveraging grammar and reinforcement learning for neural program synthesis. International Conference on Learning Representations (ICLR), 2018.
Kai-Wei Chang, Akshay Krishnamurthy, Alekh Agarwal, Hal Daumé III, and John Langford. Learn- ing to search better than your teacher. In International Conference on Machine Learning (ICML), 2015.
Mark Chen, Jerry Tworek, Heewoo Jun, Qiming Yuan, Henrique Ponde, Jared Kaplan, Harri Ed- wards, Yura 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 Win- ter, Philippe Tillet, Felipe Such, Dave Cummings, Matthias Plappert, Fotios Chantzis, Eliz- abeth Barnes, Ariel Herbert-Voss. Will Guss, Alex Nichol, Igor Babuschkin, Suchir Balaji, Shantanu Jain, Andrew Carr, Jan Leike, Josh 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 Wojciech Zaremba. Evalu- ating large language models trained on code. arXiv preprint arXhv:2107.03374 2021. URL ht.t:s:: httpps///xxiiii o
Xinyun Chen, Chang Liu, and Dawn Song. Execution-guided neural program synthesis. In Interna- fional Conference on Learning Representations (ICLR), 2019.
Andrew Cropper and Rolf Morel. Learning programs by learning from failures. Machine Learning, 110(4), 2021a.
Andrew Cropper and Rolf Morel. Predicate invention by learning from failures. arXiv preprint arXiv:2104.14426 14426, 2021b. ReL[:tttpp///axivvoorgg http:///p/aaaaaaaaaa/a////// 14426]
Andrew Cropper, Sebastijan Dumančić, and Stephen Muggleton. Turning 30: New ideas ductive logic programming. In International Joint Conferences on Artificial Intelligence (IJCAI), 2021.
Hal Daumé III. John Langford, and Daniel Marcu. Search-based structured prediction. Machine Learning, 75(3), 2009.
10

---

Foundations and Published as a conference paper at ICLR 2022
Jacob Devlin, Jonathan Uesato, Surya Bhupatiraju, Rishabh Singh, Abdel-Rahman Mohamed, and Pushmeet Kohli. RobustFill: Neural program learning under noisy I/O. In International Confer- on Machine Learning (ICML), 2017.
Kevin Ellis, Maxwell Nye. Yewen Pu, Felix Sosa, Josh Tenenbaum, and Armando Solar- Write, execute, assess: Program synthesis with REPL. In Advances in Neural Information Processing Systems (NeurIPS), 2019.
Justin Gottschlich, Armando LezaraLezama, Nesime Tatbul, Michael Carbin, Martin Rinard, Regina Barzilay, Saman Amarasinghe, Joshua B Tenenbaum, and Tim Mattson. The three pillars of machine programming. In International Workshop on Machine Learning and Programming Lan- guages (MAPL. af PLDI), 2018
Sumit Gulwani. Automating string processing in spreadsheets using input-output examples. In Symposium on Principles of Programming Languages (POPL), 2011.
Sumit Gulwani, Oleksandr Polozov, and Rishabh Singh. Program synthesis.
Trends in Programming Languages, 4(1-2), 2017.
Vincent Hellendoorn, Charles Sutton, Rishabh Singh, Petros Maniatis, and David Bieber. Global re- lational models of source code. International Conference on Learning Representations (ICLR), 2019.
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.
Ashwin Kalyan, Abhishek Mohta, Oleksandr Polozov, Dhruv Batra, Prateek Jain, and Sumit Gul- wani. Neural-guided deductive search for real-time program synthesis from examples. Interna- tional Conference on Learning Representations (ICLR), 2018.
Yarden Katz, Noah D Goodman, Kristian Kersting, Charles Kemp, and Joshua B Tenenbaum. Mod- eling semantic cognition logical dimensionality reduction. In Proceedings of the Annual Meet- ing of the Cognitive Science Society (CogSci), 2008.
Woosuk Lee, Kihong Heo, Rajeev Alur, and Mayur Naik. Accelerating search-based program syn- thesis using learned probabilistic models. Conference on Programming Language Design and Implementation (PLDI), 2018.
Dianhuan Lin, Eyal Dechter, Kevin Ellis, Joshua Tenenbaum, and Stephen H Muggleton. Bias reformulation for one-shot function induction. In European Conference on Artificial Intelligence (ECAI), 2014.
Zohar Manna and Richard J Waldinger: Toward automatic program synthesis. Communications of the ACM, 14(3):151-16,, 1971. U
10..1...115533225 362568
Aditya Menon, Omer Tamuz, Sumit Gulwani, Butler Lampson, and Adam Kalai. A machine learn- ing framework for programming by example. In International Conference on Machine Learning (ICML). 2013.
Stephen Muggleton and Dianhuan Lin. Meta-interpretive learning of higher-order dyadic Datalog: Predicate invention revisited. In International Joint Conference Artificial Intelligence (ICCAI), 2013.
Vijayaraghavan Murali, Letao Qi, Swarat Chaudhuri, and Chris Jermaine. Neural sketch learning for conditional program generation. In International Conference on Learning Representations (ICLR), 2018.
Vinod Nair, Sergey Bartunov, Felix Gimeno, Ingrid von Glehn, Pawel Lichocki, Ivan Lobov, Bren- dan O'Donoguue, Nicolas Sonnerat, Christian Tjandraatmadja, Pengming Wang, Ravichandra Addanki, Tharindi Hapuarachehi, Thomas Keck, James Keeling, Pushmeet Kohli, Ira Ktena, Yu- jia Li, Oriol Vinyals, and Yori Zwols. Solving mixed integer programs using neural networks. arXiv preprint 13/ 2020. URI iv org abs / 2233211111113992

---

Published as a conference paper at ICLR 2022
Renato Negrinho, Matthew Gormley, and Geoffrey Gordon. Learning beam search policies via imitation learning. In Advances Neural Information Processing Systems (NeurIPS), 2018.
Renato Negrinho, Matthew Gormley, and Geoffrey Gordon. An empirical investigation of beam- aware training in supertagging. In Findings of the Association for Computational Linguistics: EMNLP, 2020.
Maxwell Nye, Luke Hewitt, Joshua Tenenbaum, and Armando Solar-Lezama. Learning to infer program sketches. In International Conference Machine Learning (ICML), 2019.
Augustus Odena and Charles Sutton. Learning to represent programs with property signatures. In International Conference on Learning Representations (ICLR), 2020.
Augustus Odena, Kensen Shi, David Bieber, Rishabh Singh, Charles Sutton, and Hanjun Dai. BUS- TLE: Bottom-up program synthesis through rearning-guided exploration. In International Con- ference on Learning Representations (ICLR), 2021.
Emilio Parisotto, Abdel-rahman Mohamed, Rishabh Singh, Lihong Li, Dengyong Zhou, and Push- meet Kohli. Neuro-symbolic program synthesis. In International Conference on Learning Rep- resentations (ICLR), 2017.
Stephane Ross, Geoffrey Gordon, and Drew Bagnell, reduction of imitation learning and struc- tured prediction to no-regret online learning. In Conference on Artificial Intelligence and Statistics (AISTATS), 2011.
Ohad Rubin and Jonathan Berant. SmBoP: Semi-autoregresssive bottom-up semantic parsing. In Conference of the North American Chapter of the Association for Computational Linguistics: Human Language Technologies (NAACL-HLT)), 2021.
Eric Schkufza, Rahul Sharma, and Alex Aiken. Stochastic superoptimization. In International Con- ference on Architectural Support for Programming Languages and Operating Systems (ASPLOS), 2013.
Kensen Shi, Jacob Steinhardt, and Percy Liang. FrAngel: Component- -basdd synthesis with control structures. Proceedings of the ACM on Programming Languages, 3(POLL) 2019.
Kensen Shi, David Bieber, and Rishabh Singh. TF-Coder: Program synthesis for tensor manipu- lations, arXiv preprint 2xXi::2003.09040 2020a. URL httppp///aax...oorgrbbb/////////
09040
Kensen Shi, David Bieber, and Charles Sutton. Incremental sampling without replacement for se- quence models. In International Conference on Machine Learning (ICML), 2020b.
David Silver, Aja Huang, Chris J Maddison, Arthur Guez, Laurent Sifre. George van den Driessche, Julian Schrittiieser, loannis Antonoglou, Veda Panneershelvam, Mare Lanctot, Sander Dieleman, Dominik Grewe, John Nham, Nal Kalchbrenner, Ilya Sutskever, Timothy Lillicrap, Madeleine Leach, Koray Kavukeuoglu, Thore Graepel, and Demis Hassabis. Mastering the game of Go with deep neural networks and tree search. Nature, 529(7587), 2016.
Abhishek Udupa, Arun Raghavan, Jyotirmoy V Deshmukh, Sela Mador-Haie Milo M K Martin, and Rajeev Alur. TRANSIT: Specifying protocols with concolic snippets. In Conference on Programming Language Design and Implementation (PLDI), 2013.
Oriol Vinyals, Meire Fortunato, and Navdeep Jaitly. Pointer networks. In Advances in Neural Information Processing Systems (NIPS), 2015.
Pengcheng Yin and Graham Neubig. A syntactic neural model for general-purpose code generation. In Assocation for Computational Linguistics (ACL), 2017.
Manzil Zaheer, Satwik Kottur, Siamak Ravanbakhsh, Barnabas Poczos, Russ R Salakhutdinov, and Alexander Smola. Deep sets. In Advances in Neural Information Processing Systems (NIPS), 2017.
Amit Zohar and Lior Wolf. Automatic program synthesis of long programs with a learned garbage collector. In Advances in Neural Information Processing Systems (NeurIPS), 2018.
12

---

Published as a conference paper at ICLR 2022
Appendix
A DETAILS OF MODEL ARCHITECTURES
A.1 MODEL DESIGN FOR STRING MANIPULATION
We follow the BUSTLE paper (Odena et al. 2021) in using property signatures (Odena & Sutton 2020) to featurize individual values and relationships between two values, using properties such as does the string contain digits," "is the integer negative," " and "is the first string a substring of the second." We use the same set of properties as used in BUSTLE. Given set of properties and one or two values to featurize, we can compute whether that property is always true across examples, always false across examples, sometimes true and sometimes false, or not applicable (due type mismatch). By evaluating all properties on a value and its relationship to the target output, we obtain a property signature used in the I/O module and the value module.
1/O module. As in BUSTLE, we use property signatures to featurize all of the input variables and the output, as well as the relationships between each input variable and the output. The result is a feature vector ("property signature") f1o E C where C' = {true. mixed, N/AA is the set of possible results for single property, and L1O the length of the property signature for the entire 1/O example. We project each element of C' into a 2-dimensional embedding, pass each signature element fro, E C through this embedding, and project the concatenation of the embeddings into ero using multilayer perceptron MLP
Value module. Here we again follow BUSTLE and compute the property signature fv; E Chhual, where Lea is the length of a property signature when we featurize V individually and compared to the output O. As in the 1/O module, we pass fv. through a 2-dimensional embedding followed by a multilayer perceptron MLP to obtain the signature embedding s..
A.2 MODEL DESIGN FOR LOGIC PROGRAMMING
In the logic programming domain, every program is a predicate with arity 1 or over the domain of entities (0, ........9 9). We think of each such predicate as computing binary-valued tensor with shape (10, ) for arity-l predicates, or (10, 10) for arity-2 predicates. Both the I/O specification and program values are modeled tensors of these shapes. For the I/O module and the value module, we consider two different architectures for encoding these tensors.
MLP Encoder. This encoder flattens the binary tensor representing the predicate, pads with zeros to have length 100 (as binary relations can have size 10 x 10 = 100), and prepends a single binary variable indicating the arity of the relation. The resulting 101-dimensional object processed by 4-layer MIP with 512 hidden units and ReLU activations.
Relational Transformer. This encoder embeds each element of the domain of entities (the numbers (O...., ,)) and then applies relational transformer to these entities. Our relational transformer is based on GREAT (Hellendoorn et al. 2019 Each layer of self-attention modulated by the truth- are encoding. Concretely, the unnormalized attention coefficient
value judgment of the predicate between entity and entity j in layer of the transformer, written a/j- is a function of the key k/. the query g/, and the embedding of the relation between those entities, written r/g:
o (af r
The relation embedding rly is a function of the predicate we are encoding, written p. The intuition is that we want different valuations of p(i), p(j), p(i,j), and p(j, i) be embedded different vector representations. We also want the relation to be a function of whether we are encoding a value or the specification (written "spec"). We define the following function, which assigns unique integer from 0 to 15 to every unique relation on < 2 inputs:
= 1 p(t) + p(j) + 4 [p has arity 2] UNIQUEID(P, (,
+ p(.j) + +.ppp.... i) + 8 [p spec]
The model differs from GREAT only in that the relation modulates attention coefficients via vector rather than scalar.
13

---

Published as a conference paper at ICLR 2022
Expression S 1
String expression == Concat S2) (eft(S,1) Right((, Substr h1,12
Replace((5)) /1 /2, S2) [Tim(()) Repeat(S, /ubbst itussttt Sa)
SubstituteeSi..S.. S2, 5s, [oText([) LowerCase(S) UpperCase(S)
Integer expression 1 |roperCase(S)
II
f2 Find(S1, S2) Find(Si,
Len(S)
Boolean expression = Rauual 1 s (S1. Greater lhan (71, , I2) | T2)
String constants 7' = "" [[(" "}" "-" "+" "_" "_"|"/" 1/" "=s" "#" ":" "," "3" "g" "O"
"." "!!" "?"" [" ")" "[" """ "<" ">"
"?"
striing constants extracted from I/O examples
Integer constants
0 99
Input X = 01 x
Figure 6: The string manipulation DSL used our experiments, taken from Odena et al. (2021).
We then compute the modulating effect of the relation upon the attention coefficient, rly.
T R' (OMBED(UNIQUEDDE)) i,)))
where EMBED is a learned embedding of the sixteen possible values of UNIQUEID, and R is weight matrix that depends on the transformer layer I. We use four of these relational transformer layers with an embedding size of 512, hidden size of 2048, and attention heads. After running the transformer we have 10 x 512 tensor (number of entities by embedding dimension). We flatten this tensor and linearly project to 512 tensor to produce the final embedding the relation we are encoding.
B STRING MANIPULATION DSL
Our string manipulation DSL comes from BUSTLE (Odena et al. (222)) and is shown in Figure 6 involves standard string manipulation operations, basic integer arithmetic, and if-then-else con- structs with boolean conditionals. As an example, to compute two-letter acronym, where we want transform "product area" into "PA" and "Vice president" into "VP", we could use the program Upper (Concatenate (leeft nin0, 1), Mid (ino, Add (Fi nd ", in0), 1), 1))).
BUSTLE extracts long preeatedly-appeariig substrings of the I/O examples to use as constants, and we use this heuristic in CROSsBEAM as well for fair comparison.
C EFFECT OF LARGER SEARCH BUDGET IN THE STRING DOMAIN
In our main string manipulation experiments (Section 4.1 we use budget of 50,000 candidate programs compare approaches. As shown Figure 3 CROSsBEAM outperforms BUSTLE:
BUSTLE solves 15 /8 of their new tasks, and 44 / 89 of the SyGuS tasks, or 59 / 127 tasks total.
CROssBEAM solves 28.8 of their new tasks, and 66.6 89 of the SyGuS tasks, or 95.4 127 tasks total (averaged over 5 runs).
We repeat this experiment with a budget of million candidates:
BUSTLE solves 24 /38 of their new tasks, and 70/ 89 of the SyGuS tasks, or 94 / 127 tasks total.
CROSsBEAM solves 31.6 / 38 of their new tasks, and 73.0 89 of the SyGuS tasks, or 104.6 / 127 tasks total (averaged over runs).
CROSsBEAM again outperforms BUSTLE. It is encouraging to see that CROssBEAM continues to provide significant benefits for very difficult problems requiring large amount of search.
14

---

Published as a conference paper at ICLR 2022
String manipulation results versus wallclock time, attempting to adjust time limits to count for different implementation languages.
Table 1:
Time limit (8)
38 New Tasks
89 SyGuS Tasks
127 Total Tasks
CROSSBEAM (Python) Baseline enum (Python)
30
26.6
65.2
91.8
30
20
54
74
Baseline enum (Java)
3,4
21
53
74
BUSTLE (Java)
3.4
29
72
101
Baseline enum (Java)
30
26
65
91
BUSTLE (Java)
30
32
80
112
D WALLCLOCK TIME COMPARISON THE STRING DOMAIN
Despite CROSSBEAM's impressive performance when controlling for the number of expressions considered, CROSSBEAM does not quite beat BUSTLE when we control for wallclock time. Note that CROSSBEAM implemented in Python, while for BUSTLE tation, which is faster in general than Python. To get a rough sense of the impact, we implemented the baseline bottom-up search in Python and found that it obtains very similar synthesis performance as the Java implementation from BUSTLE when controlling for the number of candidate programs considered, but the Python version about 9x slower than the Java one: our Python baseline solves 74 total tasks within 30 seconds. and the Java baseline solves 74 tasks within 3.4 seconds (but 73 in 3.3 seconds, and 75 in 3.5 seconds). This serves as a reference point for the difference in speed between the languages, but since no neural models are involved in the baselines, it is not di- rectly applicable to the CROSSBEAM versus BUSTLE time comparison which does involve models. Nevertheless, Table I compares Python implementations with 30 second time limit versus Java implementations with a 3.4 second time limit.
the authors' Java implemen-
Even when do our best to adjust the time limits fairly, BUSTLE still solves more tasks than CROSSBEAM. However, the original BUSTLE implementation has other optimizations: the BUSTLE model has simple and small architecture, the method was designed to enable batching of the model predictions, operations in the string manipulation domain are extremely quick to execute, and the entire system is implemented in Java. In contrast, CROSsBEAM implemented in Python, and our work as whole is more focused on searching efficiently in terms of candidate programs explored instead of wallclock time, favoring improvements in deep learning methodology and ease of iteration on modeling ideas over runtime speed. In CROSSBEAM, batching model predictions for all operations in an iteration and batching the UniqueRandomizer sampling are both feasible but challenging engineering hurdles that would lead to speedups, but are currently not implemented.
E ADDITIONAL INDUCTIVE LOGIC PROGRAMMING RESULTS
For the IIP experiments, we compare CROSsBEAM, the baseline bottom-up enumerative search, two variations of Metagol (using metarules corresponding to our logic programming DSL., or using the 6 metarules suggested in the official repo's 's README), and two variations of Popper (with and without predicate invention (Cropper & Morel 2021b)).
To test the ability of our model to learn arithmetic relations, handcrafted small corpus of 30 arithmetic problems. These problems were removed from the training data. For the methods being compared,
measure whether a program implementing the target relation can be found within 30 second time limit. The results are shown in Figure and we see that CROSsBEAM solves the most tasks among all methods considered.
Additionally, on the sallomly-generateed test set, we observed that CROSSBEAM usually solves problems incredibly quickly (in under 2 seconds) not all within 30 seconds, while the other approaches, especially the baseline enumerative search, can take much longer to find solutions. This illustrated in Figure 8] which shows the gap between CROSSBEAM and other methods increasing as the time limit decreases from 30 seconds to second.
15

---

Published as a conference paper at ICLR 2022
Relation
CROSsBEAM
Enum
Metagol
Metagol?
Popper'
Popperinv'
Popper2
Popperiny?
x
y
2
= 3
X
x
X
y
X
X
X
X
x
Y 5
X
X
X
y 6
X
X
X
y 7
X
X
X
X
X
r mode
mod 3
X
X
r mod =
2 y
I + 3 = Y
2+6 y
I + 5 =
y
2 = y
y
4 = y
T = y
6 y
x/2 = Y
r/3 Y
r/4- = Y
x*2 y
I c*3
x*4 Y/
I<
x V
S
X
X
Total Solved
28
23
12
11
12
15
Figure 7: Testing 30 unseen handcrafted test problems. We report whether each system can synthesize logic program implementing the target relation, given a 30 second time limit. CROSS- BEAM uses the Transformer architecture from Appendix [A.2 (the MLP architecture solves fewer task), Metagol uses metarules corresponding to our logic programming DSL, while Metagol? uses the 6 metarules suggested in the official repo's 's README] PopperInv uses predicate invention while Popper does not. Popper2 and PopperInv2 have access to the same primitive predicates that CROSS- BEAM does (iszero, successor, and isequal) while Popper' and Popperiny' only have access to iszero and successor. In principle, logic programs can implement equality by reuse of variables, so we ran both with and without isequal predicate.
16

---

Published as a conference paper at ICLR 2022
Success Rate on Random Logic Tasks (30 Seconds)
Sucoess Rate (10)
80
(Trarsformer)
CrosuBeary (MLF)
Baseline Bottom Search
Metagol (Our DGL)
(README
20
Popper (Pied, Imc)
Popper (No Pred. Imv)
10
15
16
17
18
18
Task Size
Success Rate Random Logic Tasks (10 Seconds)
80
Sucdeds Rate (%)
CrossBeart [Iranstormer)
CrossBearn (MLP)
Beseline Bellom-Up Search
Meteggal (Our (8L))
Metagel (README DSL)
20
Popper (Pred, Inv)
Poppor (No Inw.
15
16
17
18
Success Rate on Random Logic Taskss (5 Seconds)
100
Siccees Kata (%)
Grosstlear (Traraformer)
CrossBeart (MLP)
Baseline Bettom Up Search
Metaagal (Cur nSL)
X
Metagal (README DSL)
Popper
Popper (No Pred. lnm.
Task Size
Success Rate Random Logic Tasks Seconds)
80
Slicsess Rttte (56
CrossBearr (Trarsformer)
+
CresiBeam (MLP) Search
Metagol (Our DGL)
Motegol (REAUME
20
Preper (Phed Imv)
Popper
8
10
11
12
14
15
16
17
18
19
Success Rate on Random Logic Tasks (1 Second)
100
Success Rale (%)
CrossBeum (Transforme)
CrossReam (MLF)
40
Unsetim Usltom-Up Search
Metagol
Metagol ('CLAUE USI))
Papper
Papper (Nc Predi Inv)
Task Size
Figure 8: Results on the mondomly-generade logic tasks, for different time limits, the time limit gets shorter, the gap between CROSSBEAM and other methods increases.
17


Reviews:
[{"review_id": "zoaHGRBkub9", "reviewer": "Reviewer_tHmt", "summary": "", "questions": "", "limitations": "", "rating": 8, "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": "Strengths:\n- A novel and interesting approach to neural program synthesis, based on a combination of existing techniques from the literature such as bottom-up program synthesis, on-policy beam aware training, UniqueRandomizer, and pointer networks.\n- Thorough experimental analysis shows very promising results across two important benchmarks from the literature (string manipulation and inductive logic programming). The ablation study help demonstrate the importance of the different components.\n\nWeaknesses (Minor):\n- The wall clock comparison does not exhibit similar improvement over baseline (BUSTLE) as the number of expressions due to lack of batching. While the authors claim batching is feasible and would lead to speed up, there is no experimental evidence of that.\n- Some details about the experiments are not entirely clear (see questions below).\n\n\nQuestion: \n1) Comparison to RobustFill: It is not clear to me how are the results compared? What does it mean that RobustFill considered 50,000 candidate programs? Are these generated them using a beam search with a beam width of 50,000?\n2) Random training ablation: \"obtain argument lists by randomly sampling values from the set S of explored values\" - sample uniformly? \n3) What is in the set Consts?\n4) Current approach iterates over all operators in each iteration. Did you consider also learning to select/prioritize operators based on the specification and the pool of existing subprograms?\n", "summary_of_the_paper": "The paper presents crossbeam, a bottom-up program synthesis with neural-guided search. For each of the supported operators in the DSL, a deep neural network is trained to predict which subset of previously computed subprograms (argument lists) to combine using the operator. Using UniqueRandomizer (that allows sampling sequences incrementally and without replacement), a K new unique subprograms are generated and added to the pool of subprograms that can later be combined again until a solution that satisfy the input-output specification is found. Training is done on-policy using beam-aware training.", "summary_of_the_review": "Overall, I think the paper presents a novel and interesting approach that shows significant improvement, however there are still engineering challenges related to batching.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "4: The contributions are significant, and do not exist in prior works.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "n-nzA00Fft", "reviewer": "Reviewer_Q8M3", "summary": "", "questions": "", "limitations": "", "rating": 8, "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": "Strengths\n- The empirical results are quite strong and show clear improvements on prior work. There is a blemish in that the wall-clock performance is not as good compared to BUSTLE, so it is unclear whether the proposed method will actually end up being more practically useful. Nevertheless it doesn't seem unreasonable to compare on the basis of the number of candidate programs.\n- The paper contains useful ablation experiments that control for various aspects of the method.\n- The presentation is very clear. The paper contains easy to understand diagrams and Algorithm 1 was particularly helpful for understanding the training and inference procedure (and how they relate to each other).\n\nWeaknesses\n- A more comprehensive presentation of related methods would have been helpful, for example in a tabular format. The current presentation in Section 5 mostly emphasizes one or two differences of this work compared to various previous works. I believe it would be more useful to readers if the section can explain how all the works relate to each other.\n- Unlike other neural program synthesis methods, in particular RobustFill, the method cannot handle any mistakes made in the input-output specification.\n\nQuestions\n- In general, there will be many programs that can satisfy the input-output examples, but only some of them may accurately reflect the user's intent. How do we expect the proposed method to be able to find such programs, either based on some prior (simpler programs are better) or some inferences possible from the examples chosen by the user (e.g. similar to pragmatics in human communication)?\n", "summary_of_the_paper": "The paper proposes a method for program synthesis from input-output examples using a bottom-up search method. Unlike previous works based on bottom-up enumerative search, which follow a strict ordering for exploring expressions based on their size, and eventually enumerates all possible programs up to a given size, this paper learns an entirely neural policy for the search procedure. This policy uses all of the available information at each step of the search, including the sub-programs identified so far, to decide which sub-program to explore next. It is trained using on-policy learning based on action traces created from randomly generated programs and inputs. The authors evaluate the method on string manipulation and  inductive logic programming benchmarks, and show strong empirical results compared to prior work.", "summary_of_the_review": "I vote to accept the paper considering the strong empirical results and the interesting method.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "Not applicable"}, "extra_text": {}}, {"review_id": "iBWaI5pRU6r", "reviewer": "Reviewer_D2Hc", "summary": "", "questions": "", "limitations": "", "rating": 8, "confidence": 5, "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": "This paper makes a step in the right direction to advance the state of the art in learning systems for solving program synthesis problems. Namely, CrossBeam leverages the search context to decide which program to evaluate next in search. Previous methods used functions for guiding the bottom-up synthesis (e.g., Bustle and Probe) that accounted only for a program in isolation (i.e., is this program likely to used as part of a solution?). \n\nCrossBeam has two major weaknesses, however. One of the weaknesses is fully discussed in the paper, while the other is only partially discussed. \n\nThe first weakness of CrossBeam is the system's running time. The paper does a good job explaining that CrossBeam is much slower than Bustle, a bottom-up search competitor that uses a much simpler model to guide the search. If CrossBeam and Bustle are compared in terms of programs evaluated, then CrossBeam is more effective. If the systems are evaluated in terms of running time, then Bustle is more effective. I understand the authors argument that they are seeking to advance our understanding of how neural models can be used to aid the synthesis process. I agree with the authors and also see value in the kind of work that is presented in this paper. \n\nOther research areas such as Classical Planning have dealt with similar issue for many years. The basic evaluation metric in that community is running time. The solution that that community found was to accept papers that present novel ideas and that do not necessarily advance the state of the art. I think this is what we should do here, accept this paper for presenting an interesting idea. I would have liked the paper better if it was written with the angle of presenting a novel idea that doesn't necessarily advance the state of the art. \n\nThis discussion leads me to the second weakness of CrossBeam. The search algorithm CrossBeam uses isn't ideal because it is incomplete and its search can stall. The paper has an interesting discussion around this issue, on how Beam Search as a decoding system for CrossBeam's model can cause the search to stall. The solution used in the paper is the use UniqueRandomizer by Shi et al. to attempt to see different programs as the search progresses. CrossBeam with the UniqueRandomizer indeed performs better than CrossBeam with Beam Search. However, what isn't clear and isn't discussed in the paper is whether the UniqueRandomizer solves the stalling issue CrossBeam faces. \n\nThe lack of information on whether UniqueRandomizer solves the stalling issue is troublesome because the experiments on the string synthesis problems use a suspiciously low search budget: 50,000 programs. Such a small search budget allows for the solution of only the easier problems from the problem set. What happens when we increase the search budget to millions, so we can also solve the harder instances in the set? Does CrossBeam's search eventually stall even with the UniqueRandomizer method? \n\nMy last concern is that it might be hard to reproduce the results presented in the paper. It isn't clear if the source code will eventually be made available to the research community. When it comes to reproducing the results of the paper, the paper misses important information. For example, it isn't clear how the embedding z_i is defined.", "summary_of_the_paper": "This paper introduces CrossBeam, a method for guiding the synthesis of bottom-up search for solving program synthesis problems. The main novelty of CrossBeam is a neural architecture that leverages the search context to decide which program to evaluate next in the bottom-up search. Empirical results in string synthesis problems and ILP show that CrossBeam is superior to other search methods in terms of number of programs evaluated. ", "summary_of_the_review": "The paper presents an interesting neural architecture that allows the search to account for the search state while deciding which program to evaluate next. The paper has two main weaknesses: the proposed method is much slower than other methods from the literature and the search algorithm can stall during search and not make progress, despite being allowed more computational time. The experiments possibly miss the fact that CrossBeam might suffer from getting stuck even when using the UniqueRandomizer. This is because the search budget allowed to the systems is suspiciously small. ", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "08FWLkYSlE", "reviewer": "Reviewer_cqKb", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 3, "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": "Overcoming exponential search complexity in program synthesis is an important problem. Reducing search complexity could significantly improve synthesis accuracy and enable practical applications. The paper is well-written and relatively easy to follow. \n\nTaking into account the full search history can potential be bottleneck if applied to general-purpose programming languages or DSLs with larger number of ops. Intuitively, not all previously searched programs would make good candidates. Have you considered pruning away previously searched programs that could not make a subprogram (perhaps a non-subexpressions)? Have you analyzed computational complexity of CrossBeam as a function of number of ops in a DSL, the number of I/O examples? This could help understand if including the full search history as part of context can lead to bottlenecks of that kind.\n\nIn the value module, what are the typical values of |S|? How does it scale with number of ops in a DSL?\n\nI believe the search history can be maintained with left-to-right models. It would be interesting to see this as an ablation study. One can think of a beam search algorithm with backtracking where for a target expression f(A, B) the search could recover from mistakes in predicting A, and continue to search the optimal solution. This could enable applications of variants of CrossBeam for language models like Codex. \n\nWhat is the loss function utilized during training? \n\nGiven the correct ground truth program can be reached by combining previously explored programs in various orders, this might have a significant impact on the runtime. Can a penalty be introduced as part of loss function to favor smaller depth of search?\n\nIt would be interesting to compare CrossBeam beam-aware training to an RL based on-policy training method like e.g. proximal policy optimization (PPO) method. RL allows to construct a reward function to optimize for a specific target evaluation metric. Because indeed, even though it uses samples generated by model the optimization objective is not that used during testing. An RL approach could further reduce discrepancy between training and test setting although not absolutely necessary.\n\nIs teacher forcing used during model training?\n\nWallclock time comparison does not makes sense if you compare implementations in different programming languages (Java and Python). The differences in execution speeds maybe significant. It is better to compare FLOPs or a metric independent on programming language. \n\nMinor:\n\"autoregressive model like an LSTM\" - an LSTM model can follow an autoregressive formulation/be trained autoregressively, but does not have to be in general case.\n\nFigure2 is confusing and needs more explanation.  ", "summary_of_the_paper": "The paper introduces CrossBeam – a variant of bottom-up enumerative search algorithm for program synthesis guided by a pointer network. The neural network is trained on-policy, utilizing search histories and intermediate program executions as context. The neural network aims to help choose how to combine previously explored subprograms and subsequently reduce the search complexity. Specifically, given a DSL op, I/O examples, and search histories the neural network models a distribution of argument lists from which K most likely argument lists are sampled during CrossBeam search, and an op is executed with these arguments list to verify correctness on I/O examples.\n\nThe method is evaluated on the program synthesis task (programming by example setting) in two different domains: string manipulation and logic programming. CrossBeam significantly reduces program search space compared to state of the art, and improves accuracy compared to previous art. \n\n", "summary_of_the_review": "An interesting and well written paper that suggests a solution to a long standing problem in program synthesis from input/output examples. Some machine learning design decisions appear overly complex, although motivated. It would strengthen the paper if authors could rethink the ML design having general purpose programming languages in mind or different DSLs (would including an entire search history as context still scale?). An ablation study connecting this approach to the left-to-right models (e.g. use beam search with backtracking) could give ideas about feasibility of practical applications of such models.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}]

Author rebuttal:

Meta-review: This paper addresses the problem of program synthesis given input/output examples and a domain-specific language using a bottom-up approach. The paper proposes the use of a neural architecture that exploits the search context (all the programs considered so far and their execution results) to decide which program to evaluate next. The model is trained on-policy using beam-aware training and the method is evaluated on string manipulation and inductive logic programming benchmarks. The results show that the proposed method outperforms previous work in terms of the number of programs evaluated and accuracy.  

Overall, the reviewers found the paper to be well-written and the idea proposed to be significantly novel and interesting to be presented at the conference and I agree. Several limitations were pointed out by the reviewers in terms of (i) actual run-time performance, (ii) the incompleteness of the search algorithm and the (iii) reproducibility of the approach. I believe the authors have addressed these points satisfactorily in their comments.
Decision: Accept (Poster)