Optimal Neural Program Synthesis from Multimodal Specifications
Authors: Xi Ye
Qiaochu Chen
Isil Dillig
Greg Durrett
Venue:  (2021)
Keywords: program synthesis

Abstract: Multimodal program synthesis, which leverages different types of user input to synthesize a desired program, is an attractive way to scale program synthesis to challenging settings; however, it requires integrating noisy signals from the user (like natural language) with hard constraints on the program's behavior. This paper proposes an optimal neural synthesis approach where the goal is to find a program that satisfies user-provided constraints while also maximizing the program's score with respect to a neural model. Specifically, we focus on multimodal synthesis tasks in which the user intent is expressed using combination of natural language (NL) and input-output examples. At the core of our method is a top-down recurrent neural model that places distributions over abstract syntax trees conditioned on the NL input. This model not only allows for efficient search over the space of syntactically valid programs, but it allows us to leverage automated program analysis techniques for pruning the search space based on infeasibility of partial programs with respect to the user's constraints. The experimental results on a multimodal synthesis dataset (StructuredRegex) show that our method substantially outperforms prior state-of-the-art techniques in terms of accuracy and explores fewer states during search.

Under review as a conference paper at ICLR 2021
OPTIMAL NEURAL PROGRAM SYNTHESIS FROM MULTIMODAL SPECIFICATIONS
Anonymous authors
Paper under double-blind review
ABSTRACT
Multimodal program synthesis, which leverages different types of user input to synthesize desired program, is an attractive way to scale program synthesis challenging settings; however, it requires integrating noisy signals from the user (like natural language) with hard constraints on the program's 's behavior. This paper proposes an optimal neural synthesis approach where the goal is to find program that satisfies user-pr aser-provided constraints while also maximizing the program's score with respect to neural model. Specifically, we focus multimodal synthesis tasks in which the user intent is expressed using combination of natural language (NL) and input-output examples. At the core of our method is a top-down recurrent neural model that places distributions over abstract syntax trees conditioned on the NL input. This model not only allows for efficient search over the space of syntactically valid programs, but it allows us to leverage automated program analysis techniques for pruning the search space based on infeasibility of partial programs with respect to the user's s constraints. The experimental results on multimodal synthesis dataset (STRUCTUREDREGEX) show that our method substantially outperforms prior state- state-of-thh of-the-art art techniques in terms of accuracy and explores fewer states during search.
INTRODUCTION
In recent years, there has been a revolution in machine learning based program synthesis techniques
for automatically generating programs from high-level expressions of user intent, such as input-output
examples (Balog et al., 2017: Chen al., 2019a Devlin et al. 2017 Ellis et al.) 2019 Kalyan et al.
2018, [Shin S0in et al. 2018) and natural language Yaghmazadeh et al 20 Dong & Lapata 2016
Rabinovich et al.
2017 Yin & Neubig 2017 Desai et al. 2016 Wang et al. 2018). Many these
techniques use deep neural networks to consume specifications and then perform model-guided search to find a program that satisfies the user. However, because the user's s specification can be inherently ambiguous (Devlin al., [2177] Yin al. 2018). recent thread of work multimodal synthesis attempts to combine different types of cues, such as natural language and examples, to allow program synthesis effectively scale more complex problems. Critically, this setting introduces new challenge: how do we efficiently synthesize programs with a combination of hard and soft constraints from distinct sources?
In this paper, we formulate multimodal synthesis as an optimal synthesis task and propose an optimal synthesis algorithm to solve it. The goal of optimal synthesis is generate a program that satisfies any hard constraints provided by the user while also maximizing the score under a learned neural network model that captures noisy information, like that from natural language. practice, there are many programs that satisfy the hard constraints, so this maximization is crucial to finding the program that actually meets the user's expectations: if our neural model is well-calibrated, a program that maximizes the score under the neural model is more likely to be the user's intended program.
Our optimal neural synthesis algorithm takes as input multimodal user guidance. In our setting, we train neural model to take natural language input that can be used to guide the search for program consistent with some user-proy provided examples. Because our search procedure enumerates programs according their score, the first enumerated program satisfying the examples is guaranteed to be optimal according to the model. central feature of our approach is the use tree-structured neural model, namely the abstract syntax network (ASN) (Rabinovich et al. 2017), for constructing

---

Under review as a conference paper at ICLR 2021
So
Vi
1/2 + <0>
cat
M
Co v
m0g
<Dx
M
<0>
corty.
<1>
coat(Vi, Vi)
<0>
<00
V
v
Figure 1: Example grammar for simple language.
Figure Example of an AST deriva- tion of cat (cat (<0>, <<0),,1>>,,>>> <0>). Blue boxes represent symbols and yellow boxes represent productions.
Figure 3: Example of partial pro- gram. n4 is leaf node with non- terminal symbol V1.
syntactically valid programs in top-down manner. The structure of the ASN model restricts search to programs that are syntactically correct, thereby avoiding the need to deal with program syntax errors (Kulal et al.] 2019), and it allows us to search over programs in a flexible way, without constraining a left-to-right generation order like seq2seq models do. More importantly, the use of top-down search allows us to more effectively leverage automated program analysis techniques for proving infeasibility of partial ASTs. As a result, our synthesizer can prune the search space more aggressively than prior work and significantly speed up search. While network structure and pruning techique are adapted from prior work, we combine them and generalize them to this optimal neural synthesis setting in new way, and show that our general approach leads to substantial improvements over previous synthesis approaches.
We implement our method in synthesizer called OPSYNTH and evaluate it the challenging STRUCTUREDREGEX dataset (Ye et al. (020aa) for synthesizing regular expressions from linguisti- cally diverse natural language descriptions and positive/negative examples. We compare our approach against a range of approaches from prior work and ablations of our own method. OPSYNTH achieves substantial gain over past work by solving 59.8% (resp. 46.9 46.9%) of the programs of Test (resp. Test-E) set in EGX by exploring on average 560 (resp. 810) states, which surpasses previous state-of-the-aar by 11.7% (resp. 10.9%) with 23x (resp. 18x) fewer states.
2 PROBLEM FORMULATION
Context-free grammar. In this work, we assume that the syntax of the target programming lan- guage L is specified as a context-free grammar G = (V, Σ, R. Sy) where V is a of non-terminals, Σ is the set of terminal symbols, R is a set of productions, and Sp is the start symbol. We use the notation to denote any symbol in VU The grammar in Figure [ Taas two nonterminals (S, and Vi) and three terminals (cat, <0>, and <1>). To simplify presentation in the rest of the paper, assume that each grammar production of the form v > f(s0: ......... 8n) where f is a language construct (c.g., constant like 0 or built-in function/operator like cat, +, etc.).
We represent programs in terms of their abstract syntax trees (AST). We assume that every node n in an abstract syntax tree is labeled with grammar symbol (denoted S(n)), and that every node is labeled with a production r E R (denoted R(n)) that indicates which CFG production was used to assign a terminal symbol for that node (if applicable). Figure shows AST representation of the program ca cat sat(cct(<00))) <1>), <0>) generated using the simple grammar shown in Figure |
Partial programs. For the purposes of this paper, a partial program is an AST which some the nodes are labeled with non- non-terminal symbols in the grammar (see Figure 3 For complete program, all node labels are terminal symbols. We use the notation EXPAND P, I, to denote replacing leaf I with production r, which adds n nodes $1...., Sn to the tree corresponding the yield of r.
Consistency with examples. In this paper, we focus multimodal synthesis problems where the user provides a logical specification ó in addition to a natural language description. More concretely, focus on logical specifications that program behavior. Each example is a pair (æ, y) such that, for a positive example, we have P(x) for the target program P, and for negative example, we have P(x:) y. Given set of examples
in the form of positive and negative examples the
2

---

Under review as a conference paper at ICLR 2021
E= =+ U and program P. write P F E, if we have P(x) y for every positive example in Ex and we have P(x) # y for every negative example in E If P is partial program, P J ø indicates that there is no completion of P that satisfies the specification ø.
Optimal multimodal synthesis problem. A second input to our multimodal synthesis problem is a natural language description of the task. We define a model (P [N) that yields the probability of given program conditioned on the natural language description (described in Section 3 Given programming language L specified by its context-free grammar, a logical specification ø (c.g. a set of positive and negative examples), natural language description N and model Mg. goal is to find the most likely program in the language satisfying the constraints:
arg max M3 NN) PEL A P=Φ
(1)
3 OPTIMAL NEURAL SYNTHESIS ALGORITHM
We consider a class of models Mo that admit efficient optimal synthesis. Any model with the properties described in this section can be plugged into our synthesis algorithm (Section B.2).
Definition 3.1. (AST Path) Given node n a partial program P. we define the AST path (P. = ((11,d1), ii)..... (Mg, ix)) to be a sequence of pairs (ny. 1y) where (1) AST node nj+1 is the 2 'thh child of AST node n, and (2) the ig 'th child of ng n. For instance, for the partial program in Figure 3 we have TPP, = ((nI, 1), (122 1)).
Definition 3.2. (Concrete/Inconcree nodes) Given a partial program P, we define the concrete nodes of P as C(P) to be the nodes which have production rules assigned them. The inconerete nodes I(P) are the non-terminal leaf nodes whose production rules haven't been determined and need to be fill in order to form a complete program.
Given partial program P. we define the probability of generating P as the product of the probabilities of applying the productions labeling each node in the AST. There are number of possible ways we could factor and parameterize this distribution, including PCFGs, where the distribution depends only
on the parent, or as sequence models over a pre-order traversal of the tree (Dong & Lapata| [2016] Yin & Neubig, 2017 Polosukhin Skidanov 2018). We choose the following factorization, similar to that used in Abstract Syntax Networks (ASN) (Rabinovich et al. 2017), where a production rule depends on the derivation path leading to that nonterminal:
(P N)
II nEC(P)
po (R((m) ((P.n),
(2)
The chief advantage of this factorization is that the score of a partial program is invariant to the derivation order of that program: two derivations of the same tree P that differ only in the order that branches were generated are still assigned the same probability, allowing for flexibility in the search process. Second, for partial program P. the distribution over rules of every unexpanded non-terminal leaf node does not depend on the others', which allows the estimation of the upper bound (maximum possible probability) of the complete programs that can be derived from P. Specifically, we define the upper bound of the complete programs that can possibly be derived from a partial program P as:
u6 (PI NN (P
N) II maxpolr ((P.)), nEZ(P)
This bound incorporates the known probabilities of concrete nodes as well as the minimum cost of filling inconcrete non-terminals, and thus more accurately estimates the cost of the optimal complete program given this partial program. A sequence model traversing the tree with a fixed order cannot estimate such an upper bound as the probabilities of inconcrete nodes not known.
3.1 NEURAL MODEL
We instantiate the neural model defined above using a simplified version of ASN (Rabinovich et al.) 2017), which respects the po Po (R(n) T [[P, n), N) factorization for the production of each node in the tree. Figure 4 illusstrates how ASN recursively computes the probability of labeling node n as R(n).
3

---

Under review as a conference paper at ICLR 2021
Repard the wn phi wapeeaaloggrnnn
CAT(
LITMM ftlf LIST
Compeicnnk spláo sirce
Andlyaor
mnttstarseeth $3,5)
catc5.5)
FFNN + Attention
LITT
ontrreps 0.18
digit thon
LSTM
cat (not(
(S)
0.00
Coepus: wwshaaaeeooeeeeecc..... niko
Synthesis (Section 1.3)
Model (Section
Figure 4: Left: our neural model. A vector h; associated with a nonterminal is used to predict distribution over grammar rules. Each rule instantiates new nonterminals which receive updated vectors based on LSTMs. Right: partial programs are taken from the worklist, analyzed, and expanded, then the new partial programs are added to the worklist.
Algorithm Synthesis Algorithm
I: procedure OrSYNTH(G, o. .N Ma)
input: A CFG & = (V; 2 Rt, So). specification é. natural language N and model Ms output: Complete program 1' with highest probability under Me that satisfies é, or 1
2 ((So, 1)}: while + do do (P. Q.dequeue);
4:
upper bound associated with the partial program P
5:
if Infeasible(P,@d Φ) then continue;
6:
if IIIConcr)) then return P; SeLettLaaf()) for E
8:
E Supp(Ma (T(P,)),N) do : Expand P. I,r) Q.add((P' us (PP)NN)
9:
10:
11:
return 1;
Consider the partial program cat(S(n)). S(n2)); we need to define the probability distribution over legal productions on the first node nı: po (R(n)) (), = p=(R((n)) {(cat,
We encode the AST path using LSTM(ho,(r,,44)) to be an LSTM with initial state ho and which, at each timestep, consumes a tuple consisting of a node ny and a parent-child index i, (i.e., an element in T(P.n) n)) We embed each tuple (g) by WR(ng),is where W is specialized hoot LSTM(N) and h2 LSTM(hioce 7 T(P,)) where LSTM(N) denotes an encoding of the natural language. The hidden state ft encodes both the user's NL specification as well as where we are in the parse tree, allowing us to model which grammar symbol should be likely at this position.
LSTM (Hochreiter & Schmidhuber 1997). Define
the rule and position. Then:
Given this hidden state hn the probability for each production rule at node is computed using feedforward neural network (FFNN) module and attention over the NL input:
(- (P. n). softmax (atimaxxFFNN((h... Attn(h,, LSTM(N))))
During search, each Expand operation instantiates a node with each possible rule according to the probabilities above, then computes the hidden states for any new nonterminals using the L.TTM.
3.2 SYNTHESIS
In this section, we describe search algorithm solve the optimal neural synthesis problem defined in Equation [] The key idea is to maintain a priority list Q of partial programs, ranked according to the upper bound (ug (P)) probability of the complete programs that can be derived from this partial program. Then, in each iteration of the search procedure, we pick the highest upper bound partial
"Thi abstraction allows our L.STM to implement the hidden state computation of the "constructor" module from Rahinovich al. (2077) Our production rule model follows the "primitive" and "composite type" modules.
4

---

Under review as a conference paper at ICLR 2021
Root = S(n) E EV
(a)
P + = 1
Root (P)
E Children P) Subtree P. m.) (1), (v. x), W/ (v.x))
(b)
P (3z. (S(n)) A A, v5 (2///l) ( (S(m))) A. 2.7 [2//u])
P4 (16 (v, xx)
UNSAT (ALOEEE+ 3 [//) A ABaess - [o/u.i/x))
(c)
P (E+
Figure 5: Inference rules describing procedure INFEASIBLE(P, σ) for specification ø consisting of positive examples Ex and negative examples E Rules (a)-(b) of the form P - (ø+ generate a pair of logical formulas over- and under- approximating the semantics of partial program P. The notation [=//v] denotes substituting variable y with z in formula v..
program in 2, check its feasibility using program analysis, and if it is feasible, expand one of the non-terminals in P using the applicable CFG productions. Since complete programs are dequeued from Q decreasing order of their probability according to Mg. the first complete program that satisfies & is guaranteed to be optimal under My (Proof in the in Appendix); thus, our algorithm is guaranteed to return an optimal program a solution exists.
Infeasibility pruning Our top-down search allows us to exploit program analysis techniques to prune the search space, by determining whether P is infeasible with respect to the user's hard constraints. common way of doing this is to use well-known abstruct interpretation techniques from the programming languages literature to approximate program semantics (Cousot & Cousot 1977 Nielson et al. 2015). In particular, given a partial program P. the idea behind the feasibility checking procedure is to generate a pair of logical formulas (+++, xb) over- and andrr-approximmaing P's semantics respectively.
there is any positive example et E g that inconsistent with ++, then the partial program is infeasible. Similarly, if there is any negative example e E E- that satisfies x we can again conclude that P must be infeasible.
Figure 5 describes our feasibility checking procedure in terms of inference rules, where rules (a) and (b) generate pair of over- and under-approximattinn of the program, and rule (c) checks feasibility of these approximations with respect the provided examples. Here, free variables in the formula represent program inputs, and free variable represents the program output. The existentially quantified variables z corresponds to values of sub-expressions. The first rule states that "holes" (i.e., con-terminals) in the partial program are aperxippro using y = T meaning the sub-program can return anything, and they are under-apprroimmted using = 1, meaning that the sub-program returns nothing. The second rule is used to (recursively) construct an approximation of a sub-AST rooted at node n. This rule utilizes a pair of mappings Ø Φ where & (resp. & gives over-approximating (resp. under- andrxxapproximatnng) semantics for each language construct. In rule (b), each child formula v.r N,,T must be satisficd as well as the parent formula, and these are unified by shared set of new ceistentially-quaniinn
variables.
The final rule uses the generated over- and andrraaaproossaasonn of the partial program to check feasibility. In particular, conclude that the partial program is infeasible if there any positive example et E g+ that is inconsistent with ti or any negative example e- E E- that satisfies *-
4 EXPERIMENTAL SETUP
We evaluate our synthesizer on the STRUCTUREDREGEX dataset for multimodal synthesis of regular expressions. This dataset contains 3520 labeled examples, including an NL description, posi- tive/negative examples, and the target regex. We choose this dataset for our evaluation because (1) only the dataset containing both examples and NL where the NL description is written by humans, and (2) this dataset is quite challenging, with existing techniques achieving under 50% accuracy.
Implementation Details As stated in Section 3.1 our model is an Abstract Syntax Network tailored to fit the regex DSL used in STRUCTUREDREGEX. We train neural model to maximize the log
5

---

Under review as a conference paper at ICLR 2021
likelihood of generating ground truth regexes given the NL using the Adam optimizer (Kingma & Ba 2013), stopping when the performance on dev set converges. More details are in the Appendix.
We implement the infcasibility checking procedure for regex DSL by encoding the semantics of each operator in the theory of strings (Liang et al. 2014). Since all existentially quantified variables in the resulting formula can be eliminated through substitution, the resulting constraints are of the form $ E R (or $ É R) where 8 is a string constant and R is a regular expression. Thus, we can check the satisfiability of these formulas using the Bricks library (Møller) 2017). The supplementary material describes both the semantics of the DSL constructs as well as an example showing how to generate the encoding for a given partial program.
Because of our infeasibility check, the order of expanding oon-terminals can impact the efficiency of our search. We experimented with several methods of selecting leaf node to expand, including pre-order traversal, choosing high-level nodes first, and choosing lowest-entropy nodes first. Pre-order traversal seemed to work best; more details about the expansion order can be found in Appendix.
Baselines We compare our method against three programming -e-.iiipg----x-llleee. (PBE-only) baselines. ALPHAREGEX (Lee et al., 2016), DEEPCODER (Balog al.] (2017). and ROBUSTFILL (Devlin et al. 2017). ALPHAREGEX is an enumerative regex synthesizer that uses breadth-firs search to find regexes that are consistent with the examples. Both DEEPCODER and ROBUSTFILL, are neural program synthesis approaches. DEEPCODER places distribution over constructs and terminals based on examples, and uses this distribution to carry out DFS search, whereas ROBUSTFILL uses beam search to autoregressively build programs.
We further compare our method against prior multimodal program synthesis techniques, SKETCH (Ye et al.] (2200) and TREESEARCH (Polosukhin & Skidanov 2018) with appropriate tuning of the hyperparameters and the SKETCH synthesizer for this setting. We do not compare against SKETCHADAPT (Nye al. 2019) because it relies on the assumption that every program consistent with examples is the gold program, which does not hold in our setting.
We also consider two NL-to-code models, Seq2Seq and TranX (Yin & Neubig 2017), which modify to filter out complete programs that are inconsistent with the examples (Chen et al.) 2020 Polosukhin & Skidanov 2018). A more sophisticated baseline (Ye et al. (2220)) uses example-guided pruning by filtering the beam at every timestep during search. We adopt these more sophisticated baselines proposed in Ye et al. (2020a) allow fair comparison. Implementation details of all our baselines are in the Appendix.
We refer our Optimal Synthesis approach as OPSYNTH. We also show ablations: ASN+P (ASN with our pruning during beam search), and OPSYNTH to further demonstrate the benefits of our approach over models like (Plooskhii & Skidanov (2018) that do not use such pruning. Finally, we also consider an extension denoted as OPSYNTH* which extends OPSYNTH with the ATTENTION MODEL from ROBUSTFILL (Devlin et al., 2017), which encodes the examples & using another set of LSTM layers. To combine these signals, we define the probability of applying rule on as: Pe (r P, N) softmax (FFNN(h,; Att(hhn, context(N):: Attn(nn, co))
5 RESULTS AND ANALYSIS
In the following experiments, we evaluate our approach based on two criteria: (1) accuracy, defindd as the fraction of solved synthesis tasks, and (2) efficiency, defined in terms of the number of partial programs searched. Note that we define efficiency in this way because the bottleneck is applying the EXPAND function on partial programs and symbolic evaluation of these partial programs rather than the neural net computation.
Main Results Our main results shown in Table 1 STRUCTUREDREGEX: Test-E is annotated by a distinct set of annotators from the training set.
We report results two test sets from
As shown in the top part of Table I pure PBE approaches (top) do poorly on this dataset due to not utilizing NL. These approaches either fail to find regex consistent with the examples within a time limit of 90 seconds the synthesized regex is semantically different from the target one. Thus, the comparison against PBE-only approaches demonstrates the importance of using a model that places distributions over programs conditioned on the NI description.

---

Under review as a conference paper at ICLR 2021
Table 1: Fraction of solved benchmarks (%Sol), fraction benchmarks where find I/O-consistent program (&Conn)) average number of states explored (#St), and average time used in seconds (Time).
Test
Test-E
Approach
%ool
%cCon
#St
Time
%Sol
%Cons
#St
Time
AlphaRegex
3.6
51.8
1.4
51.0
3.5
49.6
1.4
53.8
DeepCoder
6.2
7.4 lot
84.7
1.3
6.0
6.8 6.8 10
86.2
RobustFill
3.5
39.4
1.9 10²
21.1
3.5
38.4
2.0
22.1
SKETCH
45.2
75.4
18.4
29.8
62.8
3.5
21.5
TREESEARCH
48.7
69.8
13.2
31,1
56.1
19.1
Seq2Seq* +P
48.2
78.2
1.3 1o"
66.5
36.0
64.3
1.5 10
76.8
TranX**
53.1
87.8
5.
31.4
38.1
77.4
6.4
36.1
ASN
58.0
87.8
1.3
45.8
78.2
1.4
15.1
OPSYNTH
59.8
83.9
5.6
6.5
46.9
75.5
8.1 10a
9.6
OPSYNTH
55.3
74.7
8.4
43.1
62.7
11.5
OPSYNTH* 58.0
82.1
5.7
6.8
44.1
74.8
8.2
9.8
The second and third part of I shows results from prior multimodal neural synthesis approaches and NL-to-code models augmented with example-based pruning (Ye et al. (2200)). SKETCH slightly outperforms TREESEARCES solving 45% and 30% of the Test and Test-E set respectively. Seq2Seq and TranX*P, which perform beam search guided by the Seq2Seq and TranX models but also check feasibility of partial programs before adding them the beam, outperform these other techniques: TranX outperforms Seq2Seq" *P and solves 53% of the benchmarks on Test and 38% for Test-E.
The last part of Table provides results about OPSYNTH and its ablations. OPSYNTH achieves substantial improvement over TranX-P and is able to solve approximately 60% of benchmarks in Test and 47% Test-E. In addition solving more benchmarks, OPSYNTH also explores only fraction of the states explored by TranX+? which translates into improving synthesis time by roughly an order of magnitude.
We now compare OPSYNTH against three of its ablations. OPSYNTHI does not use program analysis to prune infeasible partial programs (hence, we do not report explored states as a measure of runtime), and ASN+P is similar to OPSyNTH except that it uses beam search (with beam size 20) combined with example-based pruning. Both the program analysis component and optimal search are important: without these, observe both reduction in accuracy and an increase in the number of states explored. The last row Table T shows an extension of OPSYNTH described in Section where we incorporate the ROBUSTFILL model. We find that ROBUSTFILL is ineffective on its own, and incorporating it into our base synthesizer actually decreases performance. While such neural-guided PBE approaches (DEEPCoDER (Balog et al. 2017) and ROBUSTFILL (Devlin et al.) (017]) have been successful in prior work, they do not appear to be effective on this challenging task, or not necessary in the presence of strong natural language hints. Additionally, these models both rely on millions of synthetic examples in the original reported settings.
Optimality and efficiency. We now explore the benefits of optimal neural synthesis in more detail. Specifically, Table compares OPS YNTH with its ablations that perform beam search with varying beam sizes for Test-E. For the purposes of this experiment, we terminate OPSYNTH'S 's search after it has explored maximum of 2500 states. For the beam-search-basee ablations, we terminate search when the beam is filled up with complete programs or the size of partial programs in the beam exceeds a specified threshold.
In Table 2 the column labeled "% Opt" shows the percentage of optimal programs found by the search algorithm. We also show the gap (difference of log probability) between the best programs found by each approach and the optimal programs; this is reported in the column labeled "Gap". Finally, the last three columns show the fraction of solved problems (accuracy). the fraction of programs consistent with the examples, and the number of explored states respectively.
As seen in Table 2 our optimal synthesizer can find the optimal program in 75.5% of cases and solves 46.9% problems after exploring 810 states on average. Beam search with beam size of 20
7

---

Under review as a conference paper at ICLR 2021
S6 SgEquiv Programs
0.45
0.4-
0.3
0.35
0.2
OpSynth
0.30
B5 10
0toptmmali
13
34
4.6
79
0.25
BS
Gap
BS-20
Figure Fraction of programs equivalent to target regex based on score gap with the model-optimal program.
1000
Fraction of solved programs versus the number of explored states.
Figure 7:
can only find 66.2% optimal programs, and it solves fewer problems (45.8%) despite exploring 1.8x more states, Although larger beams explore more states than OPSYNTHI and find more 1/O-consistent programs, they solve fewer problems overall.
We further evaluate the benefit of finding model-optimal programs in Figure Here, we focus only on those programs that consistent with the input-output examples. The x-axis shows the distance from the optimal program, and the y-axis shows the % of programs that are functionally equivalent to the desired regex. As shown in Figure 6 62% of optimal programs equivalent to the target regex, whereas only around 30% of the non-optimal programs match the ground truth functionally.
Finally, Figure 7 plots the fraction of solved prob- lems with respect to the number of states explored. OPSyNTH consistently solves more problems than the other methods given the same budget. Addi- tionally, also does not require specifying beam size.
Table 2: Comparison between OPSYNTII and Slum-search-basee ablations.
SUpt
Gap
Coos
Beam
50.4
1.11
39.0
65.1
290
Beam 10
59.4
1,08
42.8
72.2
660
Beam 15
63.2
0.84
44.1
76.8
1040
RELATED WORK
Beam 20
66.2
0.69
45.8
78.2
1430
OpSynth 75.5
0.0
46.9
75.5
810
Natural Language to Logical Forms Seman-
tic parsing (translating NL to executable logical forms) has been long-standing research problem
in the NLP community (Zelle & Mooney 1996 Price 1990). Traditional grammar-based semantic
parsers can construct database queries Zellc & Mooney 1996 Price 1990), lambda calculus ex-
pressions (Zettlemoyer & Collins 2005) and programs other DSLs (Kushman & Barzilay 2013
Wang et 20155). Recent advances in deep learning have explored seq2seq (Jia & Liang 2016
or seq2tree models (Dong & Lapata 2016) that directly translate the NI. into a logical form, and syntax-based models (Yin & Neubig, 2017) can also inject syntactic constraints. Our approach relies on similar neural modeling to predict the distribution of target programs from NL. However, search much more complex in our example-guided synthesis setting, whereas prior neural semantic parsers approximate the best solution using beam search (Dong & Lapata 2016 Yin Neubig 2017).
Optimal Synthesis with Examples Prior work on PBE considers various notions of optimality using cost functions (Bornholt et al.) 2016 Feser et al., 2015 Schkufza et al. 2013) and machine learning (Menon et al. | 2013). The first line of work allows users specify the desired properties of the synthesized program; for instance, smaller program size, lower execution time, or more efficient memory usage. Menon al. (2013) define optimality as the most likely constructs given set of examples under a probabilistic context free grammar: In this work, we focus on new setting where we guarantee the optimality with respect a neural modal, which can encode specifications such as natural language that are hard to formulate as simple cost functions.
Multimodal Program Synthesis There has been recent interest in synthesizing programs using a
combination of natural language and examples (Polosukhin & Skidanov 2018 Chen et al. (019bb Nye et al. 2019) Andreas et al. 20188) Raza et 2015). Specifically, Chen et al. (2020) and Ye al. (2020b) parse the natural language into an intermediate representation and then use it to guide enumeration, but they do not have any optimality guarantees with respect to the neural model. Kulal eet al.] (2019) synthesize programs by performing line-by-line translation of pseudocode to code and verify consistency with test cases at the end. However, unlike our approach, their technique enumerates syntactically ill-formed programs, which they address using compiler error localization.
8

---

Under review as a conference paper at ICLR 2021
7 CONCLUSION
In this paper, we presented technique for optimal synthesis from multimodal specifications. On a benchmark of complex regex synthesis problems, we showed that this approach is substantially more accurate than past models, and our synthesis algorithm finds the model-optimal program more frequently compared to beam search. While we have evaluated this method in the context of regular expressions, our technique is also applicable for other synthesis tasks.
REFERENCES
Jacob Andreas, Dan Klein, and Sergey Levine. Learning with Latent Language. In Proceedings of the Conference of the North American Chapter of the Association for Computational Linguistics: Human Language Technologies (NAACL), 2018.
M Balog, AL Gaunt, M Brockschmidt, Nowozin, and D Tarlow. Deepcoder: Learning write programs. In Proceedings of the International Conference on Learning Representations (ICLR), 2017.
James Bornholt, Emina Torlak, Dan Grossman, and Luis Ceze. Optimizing synthesis with metas- ketches. In Proceedings of the 43rd Annual ACM SIGPLAN-SIGACT Symposium Principles of Programming Languages (POPL), 2016.
Qiaochu Chen, Xinyu Wang, Xi Ye, Greg Durrett, and Isil Dillig. Multi-modal synthesis of regular expressions. Proceedings of the ACM SIGPLAN Conference on Programming Language Design and Implementation (PIDI), 2020.
Xinyun Chen, Chang Liu, and Dawn Song. Execution-guiie guiidd neural program synthesis. In Proceed- ings of the International Conference on Learning Representations (ICLR), 2019a.
Yanju Chen, Ruben Martins, and Yu Feng. Maximal multi-layer specification synthesis. In Proceed- ings of the 2019 27th ACM Joint Meeting on European Software Engineering Conference and Symposium the Foundations of Software Engineering (FSE), 2019b.
Patrick Cousot and Radhia Cousot. Abstract interpretation: unified lattice model for static analysis of programs by construction or approximation of fixpoints. In Proceedings of the 4th ACM SIGACT-SIGPLAN Symposium on Principles of Programming Languages (POPL), 1977.
Aditya Desai, Sumit Gulwani, Vineet Hingorani, Nidhi Jain, Amey Karkare, Mark Marron, Sailesh R. and Subhajit Roy. Program synthesis using natural language. In Proceedings of the 38th International Conference on Software Engineering (ICSE), 2016.
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 International Conference on Machine Learning (ICML), 2017.
Li Dong and Mirella Lapata. Language to logical form with neural attention. In Proceedings of the Annual Meeting of the Association for Computational Linguistics (ACL), 2016.
Kevin Ellis, Maxwell Nye. Yewen Pu, Felix Sosa. Josh Tenenbaum, and Armando Solar-Lezama. Write. execute, assess: Program synthesis with a repl. In Proceedings of the Conference on Advances in Neural Information Processing Systems (NeurIPS). 2019.
John K. Feser, Swarat Chaudhuri, and Isil Dillig. Synthesizing data structure transformations from onput-output examples. In Proceedings of the 36th ACM SIGPLAN Conference on Programming Language Design and Implementation (PLDI), 2015.
Sepp Hochreiter and Jürgen Schmidhuber. Long Short-Tere Memory. Neural Comput., 98): 1785- November 1997. ISSN 0899-7667. doi: 10.1162/neco. 1997.9.8 1..7.....777 1.35.. URL https 7/doi. weri.org/iie 10. 11 1162/ 1997. 9...7.99.811.. 1735
Robin Jia and Percy Liang. Data recombination for neural semantic parsing. In Proceedings of the Annual Meeting of the Association for Computational Linguisties (ACI.), 2016.

---

Under review as a conference paper at ICLR 2021
Ashwin Kalyan, Abhishek Mohta, Oleksandr Polozov, Dhruv Batra, Prateck Jain, and Sumit Gulwani. Neural-guided deductive search for real-time program synthesis from examples. In Proceedings of the International Conference on Learning Representations (ICLR), 2018.
Diederik Kingma and Jimmy Ba. Adam: A method for stochastic optimization. In Proceedings of the International Conference on Learning Representations (ICLR), 2015.
Sumith Kulal, Panupong Pasupat, Kartik Chandra, Mina Lee, Oded Padon, Alex Aiken, and Percy Liang. Spoc: Search-based pseudocode to code. In Proceedings of the Conference on Advances in Neural Information Processing Systems (NeurIPS), 2019.
Nate Kushman and Regina Barzilay. Using Semantic Unification to Generate Regular Expressions from Natural Language. In Proceedings of the Conference of the North American Chapter of the Association for Computational Linguistics: Human Language Technologies (NACCL), 2013.
Mina Lee, Sunbeom So, and Hakjoo Oh. Synthesizing Regular Expressions from Examples for Intro- ductory Automata Assignments. In Proceedings of the ACM SIGPLAN International Conference on Generative Programming: Concepts and Experiences (GPCE), 2016.
Tianyi Liang, Andrew Reynolds, Cesare Tinelli, Clark Barrett, and Morgan Deters. A dpll (t) theory solver for a theory of strings and regular expressions. In International Conference on Computer Aided Verification (CAV), pp. 646-662. Springer, 2014.
Thang Luong, Hieu Pham, and Christopher D. Manning. Effective Approaches to Attention-bass based Neural Machine Translation. In Proceedings of the Conference on Empirical Methods in Natural Language Processing (EMNLP), 2015.
Aditya Krishna Menon, Omer Tamuz, Sumit Gulwani, Butler Lampson, and Adam Tauman Kalai. A machine learning framework for programming by example. In Proceedings of the International Conference on Machine Learning (ICML), 2013.
Anders Møller. lkk.brics.automatte http: / brics. dk htt//autmmtooo////
finite-state automata and regular expressions for Java, 2017.
Flemming Nielson, Hanne R Nielson, and Chris Hankin. Principles of program analysis. Springer, 2015.
Maxwell Nye, Luke Hewitt, Joshua Tenenbaum, and Armando Solar-Lezama, Learning to infer program sketches. In Proceedings of the International Conference Machine Learning (ICML), pp. 4861-4870, 2019.
Illia Polosukhin and Alexander Skidanov. Neural program search: Solving programming tasks from description and examples. In Workshop at the International Conference on Learning Representa- tions (ICLR Workshop), 2018.
Patti Price. Evaluation of spoken language systems: The atis domain. In Proceedings of the DARPA Workshop on Speech and Natural Language, 1990.
Maxim Rabinovich, Mitchell Stern, and Dan Klein. Abstract syntax networks for code generation and semantic parsing. In Proceedings of the Annual Meeting of the Association for Computational Linguistics (ACI.), 2017.
Mohammad Raza, Sumit Gulwani, and Natasa Milic-Frayling, Compositional program synthesis from natural language and examples. In Proceedings of the International Joint Conference on Artificial Intelligence (ICCAI), 2015.
Eric Schkufza, Rahul Sharma, and Alex Aiken. Stochastic superoptimization. SIGPLAN Not., 48 (4):305-316, March 2013. ISSN 0340- doi: 10.11457299936822551155. URL https
Eui Chul Shin, Illia Polosukhin, and Dawn Song. Improving neural program synthesis with inferred execution traces. In Proceedings of the Conference on Advances in Neural Information Processing Systems (NeurIPS), pp. 8917-8926. 2018.
10

---

Under review as a conference paper at ICLR 2021
Chenglong Wang, Po-Sen Huang, Alex Polozov, Mare Brockschmidt, and Rishabh Singh. Execution- guided neural program decoding. In the Workshop on Neural Abstract Machines and Program Induction (NAMPI), 2018.
Yushi Wang. Jonathan Berant, and Percy Liang. Building a Semantic Parser Overnight. In Proceedings of the Annual Meeting of the Association for Computational Linguistics (ACL), 2015.
Navid Yaghmazadeh, Yuepeng Wang, Isil Dillig, and Thomas Dillig. SQLizer: Query Synthesis from Natural Language. Proceedings of the ACM SIGPLAN International Conference on Object-Oriented Programming, Systems, Languages, and Applications (OOPSLA), 2017.
Xi Ye, Qiaochu Chen, Isil Dillig, and Greg Durrett. Benchmarking multimodal regex synthesis with complex structures. In Proceedings of the Annual Meeting of the Association for Computational Linguistics (ACL), 2020a.
Xi Ye. Qiaochu Chen, Xinyu Wang. Isil Dillig, and Greg Durrett. Sketch-Driven Regular Expres- sion Generation from Natural Language and Examples. In Transactions of the Association for Computational Linguistics (TACL), 2020b.
Pengcheng Yin and Graham Neubig. A syntactie neural model for general-purpose code generation. In Proceedings of the Annual Meeting of the Association for Computational Linguistics (ACL), 2017.
Pengcheng Yin and Graham Neubig. TRANX: A transition-based neural abstract syntax parser for semantic parsing and code generation. In Proceedings of the Conference Empirical Methods in Natural Language Processing: System Demonstrations (EMNLP), 2018.
Pengcheng Yin, Bowen Deng, Edgar Chen, Bogdan Vasilescu, and Graham Neubig. Learning to mine aligned code and natural language pairs from stack overflow. 2018 IEEF/ACM 15th International Conference Mining Software Repositories (MSR), 2018.
John M. Zelle and Raymond J. Mooney. Learning parse database queries using inductive logic programming. In Proceedings of the Association for the Advancement of Artificial Intelligence (AAAI), 1996.
Luke S. Zettlemoyer and Michael Collins. Learning map sentences logical form: Structured clas- sification with probabilistic categorial grammars. In Proceedings of the Conference on Uncertainty in Artificial Intelligence (UAI), 2005.

---

Under review as a conference paper at ICLR 2021
A GUARANTEE OF OPTIMALITY
Theorem (Guarantee of Optimality), Suppose given a CFG g = (V,E, R. So), specification Φ. natural language N and model Mg. OPSYNTH returns program P Then, for any program P F Ma(P) < M)..").
Proof. Assume pa is the returned program of OPSYNTH(G, é, N, Mb) and there exits a program such that P - é and Ms MP(P)= (P")... Since Ma(P) > Mo(P"). P must have been present in the worklist and considered as a concrete program before the model visited Ps. But then, given that P o, then OPSYNTH will return P rather than P which contradicts the assumption.
B CFG FOR REGULAR EXPRESSIONS
We present the CFG for the regex domain language taken from STRUCTUREDREGEX (Ye et al. 2020a). Its correspondence to the constructions in the standard regular expression shown in the Appendix A of Ye et al. (2000a).
So + Vi
Vi Ti startwith(V)) endwith(Vi) contain(Vi)
not(Vi) and Vi, Vi) (V,,
optional (Vi) st)r(V))
concat
Vi, Vi) repeat(Vi,
(V) reprange(Vi, kr, k2)
Ti c
<let> <cap>
<low>
<num>
<any>
<spec>
<null>
Figure 8: Regex CFG. Here & Z and c is a character class, such as <a>, <1>, etc.
C ENCODING FOR THE INFEASIBLE PROCEDURE FOR REGEX
((t v, (y A (x E =0))
E (startwith, endwith, contain, not, optional, star) $1+. g1+.- 2) = -(y = -=(()))
f (catt, or, repeat, repatleast) ((+.))(f.g) (f.g,z) (y f(E1, 22))
(reprange) (1+.-) (f.g, (y f(21, 22, 23))
Figure 9: + in the regex domain. Here omit the Ti and k case. The encoding for non-terminal symbols is rule (a) in Figure 5 where T star(<any)) and 1 <null>.
We describe our detailed instantiation of the INFEASIBLE procedure described in Section 3.2 in the regex domain. Recall that INFEASIBLE prunes given partial program by checking consistency between the approximated semantics and the given examples. In the regex domain, we encode the semantics of a regex in terms of the set of strings can match. To enable checking consistency between given example and the regex, given string s, as P') to represent whether s the set of strings that can be matched by P. To encode a program P' for consistency checking,
the program InLang(s, P) (denoted
the set of encoding rules presented in Figure 9 to generate its
We concat in the paper.
12

---

Under review as a conference paper at ICLR 2021
over- and under- approximated semantics. In the regex domain, for most of the constructs can model the precise semantics except for the non-terminal symbols in the partial program.
Example. Consider the following partial program P: cat(or(<0>, Vi), <1>). To utilize the positive and negative examples for pruning, we first encode the semantics of the program P": [nLang(z, P) as follows:
(,),,) =3z.y (x 20 A v (0/l))) Fzyy (x 20 A A
-000)))000 -33..y cat 22) v [a A Φ5 /22/ 3z. cat(zi, V (T 15 (22/b))
=(3z.y = or(23, 21) 2s [23, yl A of [2a/ol, or 25 [23, y) A th (za/9])
(W3, .55 -(y <1>, <1>,y=<1>> <1>)
(WF (55 = = <0>,y <0>)
(WT wT) -y = y
We can simplify formulas + + by eliminating the existentially quantified variables: (x+ .- = (y (x cat(or(<0>, T),<1>)), A (z 1)),
Let the positive example be i " "al", = True and let the negative example be "01 0 True. According rule (c) of Figure S
we check if the following formula is unsat:
True ("al" cat(or(<0>,, T), <1>)) (True ("01" cat(or(<0>, 1), <1>)))
Since the ander-approximated semantics of P contains the string "o1", 1o1", this formula indeed unsat and we able to prune this partial program.
D NEURAL MODEL DETAILS
As described in Section 3.1 our neural model resembles an Abstract Syntax Network (Rabinovich cct al.) (017)) tailored to fit the regex DSL used STRUCTUREDREGEX. We show the grammar in Figure As there is no production rule having optional sequential cardinality, we do not include the "constructor field module" from the ASN in our implementation. We encode the NL using a single layer Bi-LSTM encoder with hidden state size of 100. In the decoding phase, set the size of the hidden state in the decoder LSTM as well as the the size of the embedding of R(n ; 1,) to be use the Luong general attention scheme (Luong al. 2015). To
100. To obtain the contexts, prevent overfitting, we apply dropout of 0.3 to the all the embedding, outputs of recurrent modules, and context vectors. Our model is trained using Adam (Kinmma Ba 2015) with a learning rate of 0.003 and a batch size of 25.
E SELECTLEAF FUNCTION DETAILS
The SELECTLEAT function selects one non-terminal leaf node in the partial program to expand. We find that when programmatic constraints are integrated into the search process, the order of choose which non-terminal to expand can impact the cost needed to synthesize the target pro- gram. We give a concrete example of how the way we select non-terminal leaf nodes expand can affect the cost of synthesis. Consider timestep where we obtain the feasible partial pro- gram cat (Vi, V2)) from the queue, where both V1 and V/2 can be expanded to <0> or <1> with probabilities 0.9 and 0.1 respectively. Suppose cat (<0>, 12) is feasible, cat (Vi, <0>) is in- feasible, and the only feasible complete program cat (<1>, <1>).
we choose to expand Vi first, then the search procedure goes as follows: ((cat (<0>, 1/2) V) + (cat (<0>, <0>) .X) + (cat (<0>, <1>) ,x)+ (cat (<1>, V2) xX) (cat (<1>, <0>> <0>),x)=+ x (cat (<1>, <1>),<>>>)) M)) which takes 6 steps. Now, if expand V2 first, the search procedure is: ((cat (Vi, <0>), X) (cat (Vi, <1>> ),) (cat (<0>, <1>) xx). (cat (<1>,<1>), <i>),()); which only takes steps.
We want to find order expand the nodes that leads to most effective pruning. We tested the following ways of selecting leaf nodes: (1) pre-order traversal, (2) choosing the highest-level leaf node, (3) choosing the lowest-entropy leaf node. We found that pre-order traversal worked better
13

---

Under review as a conference paper at ICLR 2021
than the other strategies in most cases. Given the same budget, using per-order traversal solves more programs while exploring less states compared to the other ways. The superiority of pre-order traversal the regex synthesis task be attributed to that our INFEASIBLE function needs concrete terminal leaf nodes to prune effectively, and using pre-order traversal prioritizes deepest nodes and usually yields terminal leaf nodes more quickly than other strategies.
F IMPLEMENTATION DETAILS OF THE BASELINES
ALPHA REGEX We implemented the top-down enumerative synthesizer presented in Lee et al. (016)) Although Lee al.) (216)) only uses <0> and <1> as terminals, here we extended the synthesizer to support most of the ASCII characters.
DEEPCODER We implemented DEEPCODER with few modifications from its original imple- mentation (Balog et al. 2017). First, we assign each token in the examples with a class, and embed the token by both its value and its class. For instance, consider the positive example (ax4, +) of the regex concat (repeat (<low>, 2) repat least (<num>,> 1) (2 lower letters followed by 1 or more digits. We assign "a" and "b" with the "<low>" class, and assign "4" with the "<num>" class. The final embedding of the token "a" is the concatenation of the embedding of the value Emb(a) and the class Emb(< <1ow>>. We use such combined embeddings for better generalizability. Then, we encode the examples with Bi-LSTM encoder. Each example is encoded into a hidden vector, which is later max-pont max-pooled, Finally, we apply a linear layer on the pooled representation for the whole program, and predict the the set of probabilities for each of the constructs in the DSL.
We extended AEGEE to synthesize programs using the probability of constructs obtained from the neural model. In the CERRCCDUUDREEE grammar, we associate each construct with the score returned from the neural network and calculate the score of a partial program by summing up the score of all the constructs that are used in the partial program. We specify the synthesizer to prioritize exploring the partial programs with the highest score so far.
Recall that in Section 5 that DEEPCODER doesn't achieve high performance in the STRUCTUR- BREGEX dataset. Since most of the constructs are recursive in the regex language and DEEPCODER search is essentially doing depth-first search, the synthesizer first needs to exhaustively check all possible programs associated with the highest probability constructs before it can move on to explore those programs with any other constructs. For example, suppose the concat has the highest probability and the synthesizer explores programs up to maximum depth 5, the synthesizer will prior- itize exploring programs like concat (concat (concat (concat (<low>) ) ) and searching in this way does not help the synthesizer to find the ground truth regex.
ROBUSTFILL We implemented the ATTENTION A model from ROBUSTFILL (Devlin et al. 2017 which predicts programs given I/O examples. We encode the I/O with the the same I/O embedding and I/O encoder used in our implementation of DEEPCODER. We replaced the LSTM decoder in the original implementation with our ASN decoder. During decoding, we extract context vector from each the examples provided in the example set, and pool them with max-pooling as the final context vector. The probability distribution over rules for node is then given as:
Attn(/n, context(o) () = MaxPool( (ooiPooo((Atttt context (e)) (r N) = coftmax(FFFNN
Attn h,,, context( o)))
We set the size of value embedding and class embedding to be 50, and the size of hidden state in encoder Bi-LSTM and LSTM in ASN be 100.
TREESEARCH As the code of TREESEARCH (Polosukhin & Skidanov 2018) is not publicly available code, implemented our own version of TREESEARCH top of TRANX which is reported to more powerful than the originally used SEQ2TREE on various datasets (Yin & Neubig 2018 During search, set the threshold to be 10-5, and the max queue size be 100.
OPSYNTH R We naturally combine OPSYNTH and ROBUSTFILL by concatenating the context for the NL encoder the
vectors from NL and examples, as in Section 4 The same as those for the base synthesizer, and the hyper-parameters for the I/O encoder are the same as ROBUSTFILI..
14


Reviews:
[{"review_id": "sa13c2I9Bx9", "reviewer": "AnonReviewer2", "summary": "", "questions": "", "limitations": "", "rating": 6, "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": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "Summary\n-------------\nA method for synthesizing programs from a combination of natural language specifications and formal specificatios (or, more concretely, input/output examples) is presented. It combines a top-down, grammar-based expansion strategy with a deduction component that can help to rule out partial programs that cannot be completed into a correct program. Experiments show small but noticeable improvements over baselines on a dataset of regular expression synthesis benchmarks.\n\nStrong/Weak Points\n-------------\n* (+) Paper attempts to integrate neural and symbolic methods more deeply than just using one as filter for the other.\n* (+) Experiments with relevant baselines seem clean and answer the most important questions.\n* (-) Lack of comparison with highly related work that combines neural generation approaches with deductive methods to simplify the search space. While most of these methods have not been developed for the multi-modal setting. Handling multi-modal specifications would be similarly straightforward as the extension from OpSynth to OpSynth+R described in Appendix E. Examples of relevant work:\n   * \"Neural-guided deductive search for real-time program synthesis from examples\" (Kalyan et al.) uses version space algebras to determine if a partial program can be completed to a correct program and a neural network conditioned on the partial program to select the next most-likely expansion step.\n   * \"Program Synthesis using Conflict-Driven Learning\" (Feng et al) uses a CDCL-like procedure to rule out infeasible parts of the search space with a ML-based heuristic for chosing next expansion steps.\n   * Execution-guided approaches (\"Execution-guided neural program decoding\" (Wang et al.), \"Execution-guided neural program synthesis\" (Chen et al.) which check if the partial program generated so far is compatible with the examples. In the regex space, this is naturally applicable to left-to-right generation approaches by checking if the partial regex generated so far matches a prefix of the input example.\n* (-) For the ICLR audience, Sect. 3.2 may be at a too formal level (and especially, familiarity with the inference rule notation in Fig. 5 should not be assumed). I have doubts that this _helps_ readers to understand and due to the space limitations, it doesn't make things exact either (e.g., it took me a while to understand that $\\Phi^+$/$\\Phi^-$ implicitly consume $\\mathbf{z}$; and the \"definitions\" for $\\Phi^{+,-}$ in Appendix B/Fig. 9 are not precise as they just map to some undefined underlying regular expression language)\n\nRecommendation\n-------------\nI think this is a borderline paper. Overall, it is in a crowded space with many competing approaches and does not do a great job at differentiating itself (see above), which makes it hard to judge its contribution clearly. The experimental results are an indication that the method works, but some questions (e.g., does using ASN instead of a stronger neural generator model make things worse) remain.\n\nQuestions\n-------------\n* [See above re related work that could be compared to]\n* Appendix D states that implementing SelectLeaf using a pre-order traversal works best, which somewhat negates the argument for an approach that is invariant to derivation order (in Sect 3 / 3.1). If pre-order works best anyway, building on top of TranX (or \"Generative Code Modeling with Graphs\" (Brockschmit et al)) would be possible as well, which have shown better results than ASN in generative code modelling. Did you experiment with such models?\n\nDetail Feedback\n-------------\n* Page 3: \"Wwe\" -> \"We\"\n* Fig. 9:  second/third equation are lacking a closing \")\"; \"or\" appears twice in the third equation.", "extra_scores": {}, "extra_text": {}}, {"review_id": "YrvQG5sIqMp", "reviewer": "AnonReviewer1", "summary": "", "questions": "", "limitations": "", "rating": 5, "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": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "The paper shows an interesting and novel combination of neural and constraint-based synthesis that despite using a relatively simple neural model, manages to improve over more involved neural synthesis techniques. This is a significant point in the space of such algorithms and an important research result.\n\nSeveral important systems were compared, including non-neural results. One interesting question is in what cases Sketch found a solution compatible with the input/output examples, but it was not the desired solution for the task.\n\nThere are a few areas for improvement of the paper, but overall it is well written and shows interesting results:\n\n- The technique is described very generally, but there was only one dataset and one task for which it improved the results over the baselines. This task has the advantage that it contains an elaborate “Infeasible” procedure that is usually not present in general DSLs, but it does not seem that this is the main reason why the technique works well. Judging from the ablated results, it seems that the main reason seems to be that the other neural baselines are baselines are a poor fit for this specific task.\n\n- While the approach talks about speed, it only includes the number of steps in its results. Was there any improvement in terms of wall-time say in comparison to Sketch? You seem to be giving 90 seconds to it. How long does it take for OpSynth to run?\n\n- Some improvements in the definitions and the writing are possible:\n\npage 2: In f( s_0 .. s_n) where as later it talks s_1 to s_n\npage 3: Wwe\n\nDefinition 3.1 seems inaccurate and does not imply that a path must start at the root. If it does not, then the function pi cannot be defined. Also n_k is not the same as n_k in the examples.\nDefinition 3.2 defines assigning rules to nodes, but this is not part of a tree or a grammar. It looks like it tries to make applying a production rule in two steps, but it is not clear why this is needed.\nSupp is not defined in the algorithm.\n", "extra_scores": {}, "extra_text": {}}, {"review_id": "Jg3PTr_KmU8", "reviewer": "AnonReviewer3", "summary": "", "questions": "", "limitations": "", "rating": 4, "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": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "## Summary\nThis paper proposes an approach to program synthesis that aims to incorporate information from different modalities, focusing on combining input-output examples with natural language specifications. They formulate it as a form of constrained optimal program synthesis.  The constraints are in the form of positive and negative examples, which the program must satisfy.  The optimality criteria is in the form of maximizing the conditional probability of a program $P$ given a natural language description, as specified by a conditional distribution that is learned from data.\n\n## Overview\n\nOverall:\n- The use of program analysis methods within neural program synthesis is promising.  \n- I found no technical flaws with this paper.\n- The paper needlessly combines different concepts, and doesn’t clearly disambiguate what is it’s contribution.   The main contribution of this paper is in pruning partial programs, but that is obscured under the framing of multimodal learning.\n- Both the benefits and limitations of an abstract interpretation approach are under explored.\n\nIt is difficult to tell exactly what the claims of the paper are, as they are not clearly specified.  Nevertheless, there are three different concepts in this paper that are worth separating:\n\n- The representation of the distribution over expressions that supports enumerating programs in order of decreasing probability.  Consequently the first program in this enumeration that satisfies the positive and negative examples is optimal.\n-  The use of abstract interpretation to prune infesabile partial programs.  This means that conditioning $p_\\theta$ on the fact that $P$ must satisfy positive and negative examples can be done more efficiently than simply rejecting complete programs.\n- The formulation of optimal multimodal program synthesis in these terms.\n\n(please correct me if I am missing something or mischaracterizing the contributions)\n\nThe representation used (Abstract Syntax Networks) is not a contribution of this work.  It is not entirely clear to me whether the authors are claiming the enumeration strategy that produces the most probable program first as a contribution.  If so, there is existing work both in conventional program synthesis (e.g. [1, 2]) and neural program synthesis (e.g.[3]) that enumerates programs in order of probability.  Does this approach present anything new over these?\n\nThe formulation is fine.\n\nGiven all of this, it seems that the primary contribution of this paper is the use of a form of abstract interpretation to prune partial programs.  There is much merit to this idea and approach.  In particular, there are potentially very large gains to be had in efficiency.  I have a number of concerns though:\n\n**Writing:** Given the importance of this section, the abstract interpretation is very poorly explained.  Terms in the derivation tree (e.g. Root, SubTree, Children) are not specified.  Several notations (such as expression substitution) which are likely unfamiliar to a machine learning audience are not explained.\n\nThe authors have also not cited any of the work that uses abstract interpretation for program synthesis (e.g. [4,5,6])\n\n**Imprecision:** one of the major problems in abstract interpretation is imprecision — the over approximation can include too many in feasible solutions, and the under approximation can exclude too many.  Familiarity with abstract interpretation would lead most to have a healthy dose of skepticism that the approach can be used naively for program synthesis, without vary careful selection of the abstract domains.  This is because for most abstract domains in most non-trivial examples, imprecision would lead to an inability to prune virtually any programs.\n\nCarefully choosing abstractions for specific domains can be done in some situations, which is precisely what the regex example has done.  They present an abstract interpretation framework that is parameterized using the $\\psi$ function, but the only example is in terms of regular expressions which permit precise abstractions.\n\nThis is not to say that focusing on restricted applications isn’t worthwhile, but the authors should take a lot more care to both explore and explain the limitations of abstract interpretation and the difficulties that one would face in actually applying their framework to other DSLs.  \n\n**Results** The results are a little hard to interpret.  $\\text{OpSynth}$ solves 5% more (of the total number of) solutions than the ablated $\\text{OpSynth}^{-\\mathcal{P}}$.  However, this ablated version has nothing checking for consistency with the actual data.  In addition to this, the authors should present in Table 1 data for OpSynth with a routine that does check for consistency, such as the beam search approaches.\n\nWhen comparing against different approaches, it is impossible to tell from the data if failures are due to timing out or due to finding a program that doesn’t generalize to the test data.  If it is the former, then the results may look very different with different timeout thresholds.\n\nWall clock time is missing from evaluation, which is as important since neurosymbolic methods can be orders of magnitude slower in real time than conventional methods.\n\nTaking a step back, the primary problem is that the bulk of the work done is in the ASN network, and importance of the pruning cannot be discerned from this.  The advantages in Table 2 of OpSynth may be very much diminished with a greater beam size / threshold.\n\nThis is all to say that I cannot tell from this data that OpSynth has real advantages over ASN combined with simple enumeration.\n\n## Questions\n\n- OpSynth finds 75.5% of the optimal programs.  Is this optimality with respect to the trained model $p_\\theta$?  If so, according to your approach, the remaining 25.5% of failures must be due to timeouts.  Is this correct?\n- What exactly is the “fraction of solved problems”?  How could it be less than the percentage of optimal programs found?  Is this performance on a test set? \n\n## Typo\nWwe -> We\n\n## References\n[1] Lee, Woosuk, et al. \"Accelerating search-based program synthesis using learned probabilistic models.\" ACM SIGPLAN Notices 53.4 (2018): 436-449.\n[2] John K Feser, Swarat Chaudhuri, and Isil Dillig. Synthesizing data structure transformations from input-output examples. In PLDI, 201\n[3] Ellis, Kevin, et al. \"Dreamcoder: Growing generalizable, interpretable knowledge with wake-sleep bayesian program learning.\" arXiv preprint arXiv:2006.08381 (2020).\n[4] Rishabh Singh, Armando Solar-Lezama, Synthesizing data structure manipulations from storyboards, 2011(bibtex)\n[5] Martin T. Vechev, Eran Yahav, Greta Yorsh, Abstraction-guided synthesis of synchronization\n[6] Wang, Xinyu, Isil Dillig, and Rishabh Singh. \"Program synthesis using abstraction refinement.\" Proceedings of the ACM on Programming Languages 2.POPL (2017): 1-30.\n", "extra_scores": {}, "extra_text": {}}, {"review_id": "15LtDozPUVL", "reviewer": "AnonReviewer4", "summary": "", "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": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "The work presents a technique for synthesizing program from a combination of NL and input-output examples. It is guaranteed to find the best-possible program under a trained NL->AST model that satisfies the given examples. The technique assumes a particular kind of NL->AST model from the literature and a pruning mechanism for infeasible partial programs, integrated into best-first search. On a recent dataset of multi-modal regular expression problems, the technique significantly outperforms both purely-neural, purely-symbolic, and prior multi-modal baselines, although it only slightly outperforms its own ablations.\n\n## Strengths & Weaknesses\n\nThe main contribution is using best-first search to guarantee optimality wrt the semantic parsing model, which, in turn, required fixing the model class to ASN. The infeasibility pruning seems to repeat the procedure of Chen et al. (PLDI 2020). Nevertheless, the end-to-end formulation is a valuable contribution to the program synthesis community even if its technical novelty is limited.\n\nAs far as I'm aware, this is the first multi-modal program synthesis method that has an optimality guarantee under a neural model. Other approaches to optimal program synthesis exist, but they focus on manual cost functions. In theory, best-first search could be integrated into other methods, but this is the first work that presents such a method end to end.\n\nThe paper is written clearly and with plethora of examples. One exception are the inference rules for pruning in Figure 5, which introduce a significant abstraction that does not become clearer until Appendix B. However, space constraints are understandable and unavoidable. In absence of space, I would suggest swapping the two and presenting a concrete example of infeasibility (plus perhaps pseudocode) in Section 3 and domain-independent formalism in the Appendix.\nGiven that the paper only evaluates itself on a single application domain, a domain-independent general abstraction of pruning without a regex-related example in the main paper body seems excessive.\n\nThe method clearly outperforms both single-modality and prior multi-modal baselines. The ablation experiments are also quite insightful. Interestingly, best-first search only adds 0.9% of accuracy on Test-E over beam search. The main gains in the approach seem to come from the choice of ASN as a semantic parsing model and the feasibility pruning, not from the best-first formulation.\n\n## Questions/Suggestions\n\n- As stated in the Appendix D, the authors expand the nodes using the pre-order traversal in practice. This is a fixed order of expansion, the same one as TranX. The models, of course, differ - ASN conditions its prediction on the AST path whereas TranX conditions on the expansion path and the parent node. In Table 1, ASN+P outperforms TranX+P by 7.7 points. However, prior works (Yin & Neubig, 2019; Brockschmidt et al., 2019) report an opposite ordering, with TranX-style models outperforming ASN-style models on many different datasets. Do you have any intuition why the performance of these two baselines so drastically flips on your task?\n\n- Could you formally state and prove the statement of optimality wrt the semantic parsing model as a theorem? It is intuitively true, but the paper (otherwise impressively rigorous) currently only posits optimality at a very high level in a single sentence on page 5.\n\n", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Meta-review: The paper proposes a new multimodal neuro-symbolic technique for synthesizing programs. The specification is given in natural language (soft constraints) and input-output examples (hard constraints). The multimodal program synthesis is formulated as a constrained maximization problem where the goal is to find a program maximizing the conditional probability w.r.t. the natural language specification while satisfying the input-output examples. The proposed technique is evaluated on a multimodal synthesis dataset of regular expressions, and significant performance gains are shown w.r.t. the state-of-the-art synthesis methods. Overall this is an important direction of research, and the paper presents significant results in the space of multimodel program synthesis.

I want to thank the authors for actively engaging with the reviewers during the discussion phase. The reviewers generally appreciated the paper's ideas; however, there was quite a bit of spread in the reviewers' assessment of the paper (scores: 4, 5, 6, 7). In summary, this is a borderline paper, and unfortunately, the final decision is a rejection. The reviewers have provided detailed and constructive feedback for improving the paper. In particular, the authors should more clearly describe the paper's primary contributions, compare their technique with related work that combines neural generation approaches with deductive methods, and simplify the presentation of technical sections. This is exciting and potentially impactful work, and we encourage the authors to incorporate the reviewers' feedback when preparing future revisions of the paper.
Decision: Reject