Latent Programmer: Discrete Latent Codes for Program Synthesis
Authors: Joey Hong
David Dohan
Rishabh Singh
Charles Sutton
Manzil Zaheer
Venue:  (2021)

Abstract: In many sequence learning tasks, such as program synthesis and document summarization, a key problem is searching over a large space of possible output sequences. We propose to learn representations of the outputs that is specifically meant for search: rich enough to specify the desired output but compact enough to make search more efficient. An appealing realization of such representation are discrete latent codes, as this naturally allows sophisticated combinatorial search strategies. The latent codes are learned using a self-supervised learning principle, in which first a discrete autoencoder is trained on the output sequences, and then the resulting latent codes are used as intermediate targets for the end-to-end sequence prediction task. Based on these insights, we introduce the Latent Programmer, a program synthesis method that first predicts a discrete latent codes from input/output examples, and then generates the program in the target language. We  evaluate the Latent Programmer on two domains: synthesis of string transformation programs, and generation of programs from natural language descriptions. We demonstrate that the discrete latent representation significantly improves synthesis accuracy.

Under review as a conference paper at ICLR 2021
LATENT PROGRAMMER: DISCRETE LATENT CODES FOR PROGRAM SYNTHESIS
Anonymous authors Paper under double-blind review
ABSTRACT
In many sequence learning tasks, such as program synthesis and document sum- marization, key problem is searching over large space of possible output se- quences. We propose to learn representations of the outputs that are specifically meant for search: rich enough specify the desired output but compact enough make search more efficient. Discrete latent codes are appealing for this purpose, as they naturally allow sophisticated combinatorial search strategies. The latent codes are learned using self-superviser learning principle, in which first dis- crete autoencoder is trained on the output sequences, and then the resulting latent codes are used as intermediate targets for the end-to-end sequence prediction task. Based on these insights, we introduce the Latent Programmer, a program synthe- sis method that first predicts discrete latent code from input/output examples, and then generates the program in the target language. We evaluate the Latent Programmer on two domains: synthesis of string transformation programs, and generation of programs from natural language descriptions. We demonstrate that the discrete latent representation significantly improves synthesis accuracy.
INTRODUCTION
Our focus in this paper is program synthesis, one of the longstanding grand challenges of artificial intelligence research (Manna & Waldinger [177]] Summmers] 1977). The objective of program syn- thesis is to automatically write a program given specification of its intended behavior, such a natural language description or small set of input-output examples. Search is an especially diffi- cult challenge within program synthesis (Alur et al., 2013) Gu Gulwani et al. 2017), and many different methods have been explored, including top-down scarch (Lee et al.) (2088). bottom up search (Udupa ct al. 2013), beam scarch (Devlin et al., 2017). and many others (see Section 2b.
We take a different philosophy: Can learn representation of programs specifically to help search? A natural way of representing a program is as a sequence of source code tokens, but the synthesis task requires searching over this representation, which can be difficult for longer, more complex programs. A programmer often starts by specifying high-level components of a program as plan, then fills in the details of each component i.e. in string editing, plan could be extract the first name, then the last initial. We propose to use a sequence of latent variable tokens, called discrete latent codes, represent such plans. Instead of having fixed dictionary of codes, we let model discover and learn what latent codes are useful and how to infer them from specification.
Our hypothesis is that discrete latent code sequence of discrete latent variables can be useful representation for search (van den Oord et al., 2017 Roy et al., 2018 Kaiser et al.) 2018). This is because we can employ standard methods from discrete search, such as beam search, over compact space of high-level plans and then over programs conditioned on the plan, in a two-level procedure. We posit that the high-level search can help to organize the search over programs. In the string editing example earlier, model could be confident that it needs to extract the last initial, but less sure about whether it needs to extract a first name. By changing one token in the latent code, two-level search can explore alternative programs that do different things in the beginning. Whereas in traditional single-level search, the model would need to change multi-token prefixes of the alternatives, which is difficult to achieve in limited budget search.
We propose the Latent Programmer, a program synthesis method that uses learned discrete repre- sentations guide search via two-level synthesis. The Latent Programmer is trained by a self-

---

Under review as a conference paper at ICLR 2021
Inputs
Outputs
Program
"Mason Smith"
"Smith M"
"Henry Myers"
"Myers H"
GetToken PROP _R0P__AS_22 2
Const (" ")
"Barry Underwood"
"Undewwood B"
GetToken_ A
"Sandy Jones"
"Jones S"
Figure 1: A string transformation task with 4 input-output examples possible program in the string transformation DSL that is consistent with the examples.
supervised learning principle. First a discrete autoencoder is trained on set of programs to learn discrete latent codes, and then an encoder is trained to map the specification the synthesis task to these latent codes. Finally, inference time, Latent Programmer uses two-level search. Given the specification, the model first produces L-best list of latent codes from the latent predictor. and uses them to synthesize potential programs. On two different program synthesis domains, find empir- ically that the Latent Programmer improves synthesis accuracy by over 10% compared to standard sequence-to-sene to-seqeence baselines as RobustFill (Devlin et al. (017). We also find that our method improves diversity of predictions, as well as accuracy on long programs.
2 BACKGROUND
Problem Setup The goal in program synthesis is to find a program a given language that is consistent with a specification. Formally, we are given a domain specific language (DSL) which defines space y of programs. The task is described by a specification X E X' and is solved by some, possibly multiple, unknown program(s) Y Y. For example, each specification can be a set of input/output (I/O) examples denoted X {(I1, O1),... (IN. ON)}. Then, we say that we have solved specification X we found a program Y which correctly solves all the examples: Y(I,) O,, Vi 1..... N. As another example, each specification can be a natural language description of task, and the corresponding program implements said task. An example string transformation synthesis task with four I/O examples together with a potential correct program in the string transformation DSL is shown in Figure
Vector Quantization Traditionally, neural program synthesis techniques process the input specifi- cation as a set of sequences and predicts the output program token-by-token (Devlin et al. 2017). In this work, we present new approach for synthesis that performs structured planning latent space using a discrete code. We conjecture that programs have an underlying discrete structure; specif- ically, programs are compositional and modular with components that get reused across different problems. Our approach leverages this structure to guide the search over large program spaces. Fol- lowing works in computer vision (van den Oord et al.) 2017 Roy et al.) 2018), we discover such discrete structure by using Vector Quantized Variational Autoencoder (VQ-VAB). VQ-VAEs work by feeding the intermediate representation of an autoencoder through discretization bottleneck van den Oord et al., 2017). For completeness, we provide background on VQ-VAEs below.
In VQ-VAE, latent codes are drawn from a discrete set of learned vectors c E KxD, or codebook. Each element in the codebook can be viewed as either a token with id k [K] as embedding O E RR,. To generate the discrete codes, the continuous autoencoder output e is quantized via nearest-neighbor lookup into the codebook. Formally, the token id qk(e) and quantized embedding go(e) are defined as
ge(e) Cgk(e) where (e(e) arg min
||e-cxl12- kE[K]
For input x, the training loss for a VQ- VAE consists of: a reconstruction loss for the encoder-decoder weights, codebook loss that encourages codebook embeddings to be close to the continuous vectors which are quantized to them, and commitment loss that encourages the encoded input ec(ar) to "commit" to codes i.e. not switch which discrete code is quantized to. The loss given by,
L(c, 0, Φ) = log pe (xr (c(ec;(x))) + [|sg(ec,(x))) c)ll + B]|sg(c) (c)
(2)
where 8, Ø are the parameters of the decoder and encoder, respectively. sg(-) is the stop gradient operator that fixes the operand from being updated by gradients, and 3 controls the strength of the commitment loss. To stabilize training, van den Oord et al.] (2017) also proposed removing the codebook loss and set the codebook to exponential moving average (EMA) of encoded inputs.
2

---

Under review as a conference paper at ICLR 2021
Space
Latent Predictor 1p!0)
Beamt Search
Fi
Oly
Latent Program 1/7 X)
X
Program Enoodier
Quantize
tralo only
Figure 2: High-level architecture for the Latent Programmer system. The latent predictor generates probabilities over latent sequences, which can be decoded into a predicted latent sequence Z'. Z' is fitted to ground-truth latent sequence Z generated by a program encoder, and used during decoding to by the latent program decoder to generate programs.
SYNTHESIS WITH DISCRETE LATENT VARIABLES
We propose a two-level hierarchical approach to program synthesis that first performs high-level planning over intermediate sequence, which is then used for fine-grained generation of the pro- gram. In our approach, a top-level module first infers a latent code, which gets used by a low-level module to generate the final program.
3.1 HIERARCHY OF TWO TRANSFORMERS
Our proposed Latent Programmer (LP) architecture consists of two Transformers in two-level structure. The architecture comprises of two modules: a latent predictor which produces a latent code, which can be interpreted as course sketch of the program, and latent program decoder, which generates program conditioned on the code. The latent code consists of discrete latent variables as tokens, which we arbitrarily denote TOK_I,.... TOK_ K, whose meanings are as- signed during training. Both components use Transformer architecture due to their impressive performance on natural language tasks (Vaswani et al. (017).
To help the model assign useful meanings to the latents, we also leverage program encoder, which only used during training. The program encoder ec(Y) encodes the true program Y [yi, 1/2...., yT] into shorter sequence of discrete latent variables Z = [21, #2, ...,. Es], represented as codebook entries; that is, each 2, e RD is one K entries in a codebook c. The latent sequence serves the ground-truth high-level plan for the task. The function ec(Y) is Transformer encoder, followed by a stack of convolutions stride 2, each halving the size of the sequence. We apply the convolution & times, which reduces T-length program to latent sequence of length [T/2*]. This provides temporal abstraction, since the high-level planning actions are made only every 2 steps. In summary, the program encoder is given by
eY - h4i hm + Conv(hm-- for m E I...6; tn + Transformer
(3)
Here TransformerEncodeer applies a stack of self-attention and feed-forward units on input em- beddings via residual path, described in detail by Vaswani al. (017)) This will be used, along with the latent program decoder, as an autoencoder during training (see SSctionn 3.2)
The latent predictor Ip(X) autoregressively predicts coarse latent code Ip(X) RSSK con- ditioned on the program specification X. The latent predictor outputs sequence of probabilities, which can be decoded using search algorithms such as beam search generate predicted latent code Z'. This is different than the program encoder, which outputs single sequence Z, because we use the latent predictor organize search over latent codes; at test time, we will obtain I--best list of latent token sequences from Ip(X). The latent predictor is given by stack of Transformer blocks with the specification X as inputs.
Similarly, the latent program decoder X) defines autoregressive distribution over program tokens given the specification X and the coarse plan E R K represented as codebook entries. The decoder is Transformer that jointly attends to the latent sequence and program specification. This is performed via two separate attention modules, whose outputs are concatenated into the hid- den unit. Formally, given partially generated program Y' [VL V/2 -. v/- and the encoded
3

---

Under review as a conference paper at ICLR 2021
specification E Transformer/Eccooe(((() the latent program decoder performs
he Concat ("ransformeerDecodee(("" E),-1, IransformeerDeeoddrry" Z):-1), (4)
where TransformerDeccode(((,,, denotes Transformer decoder applied to outputs y while at- tending to inputs encoding æ, and the subscript indexes an entry in the resulting output sequence. Finally, the distribution over output token & is given by de Z, X) moft (W (he)), where W is a learned parameter matrix. Finally, the latent program decoder defines a distribution over programs autoregressively as p(Y|zz X) II. plyllyee, Z, X), where p(y: WW-c, Z, X) (Z, X). When X is multiple I/O examples, each example is encoded as E; TranssormeeDDcodeerr.
O.). Then, separate hidden state per I/O is computed following equation 4 followed by a late max-pool to get the final hidden state. Note that the program encoder and latent program decoder make up VQ- VQE model of programs, with additional conditioning on the specification.
The complete LP architecture is summarized in Figure 2 and an end-to-end example run of our architecture shown in Figure
3.2 TRAINING
Our LP performs program synthesis using a two-level search, first over latent sequences then over programs. Given program specification, we want to train our latent predictor to produce an informa- tive latent sequence from which our latent program decoder accurately predict the true program. Our training loss for the LP model consists of three supervised objectives.
The autoencoder loss ensures that the latent codes contain information about the program. It is summation of the reconstruction loss between the autoencoder output d((ce(Y), X) and true program Y, as well as a commitment loss to train the encoder output ec (Y) to be close codebook c. Like in Roy et al. (2018), codebook is not trained but set to the EMA of encoder outputs. This loss is similar the loss function of VQ- IQ-VAE as in @ but also depends on specification X. This objective trains the latent tokens in the codebook so that they correspond to informative high-level actions, as well as make sure our latent program decoder can accurately recover true program given the specification and plan comprising of such actions.
The latent prediction loss ensures that latent codes can be predicted from specifications. a re- construction loss between the distribution over latents predicted from the specification Ip( and the autoencoded latents qk gee) from the ground-truth program. This is a self-supervised approach that treats the autoencoded latent sequence the ground- couundtruthh high-level plan, and trains the latent predictor to generate the plan using just the program specification X. Note that the program encoder only used in training, as at test time ec ec(Y) is unknown, the I.P model uses Ip(X) X) instead.
Finally, the end-to-end loss ensures that programs can be predicted from specifications. This is especially important because in the reconstruction loss, the latent program decoder receives input latent codes from the autoencoded latent sequences ec(Y), whereas at test time, the decoder receives latent code from the latent predictor lp()). This can result in mistakes in the generated program since the decoder has never been exposed to noisy results from the latent predictor. The end-to-en end loss alleviates this issue. The end-to-end loss probability of the correct program Y when predicted from a soft-qua oftt-quantzzed latent code, given by Ip(X)" c. This has the added benefit of allowing gradient to flow through the latent predictor, training an end-to-end way.
In summary, the full loss for training instance is
L(c,0, v) = log (Y qo(ecs (Y)), x) + 3l|s((c) ecs (Y)
autoencoder
+ log p (qk(ec= (Y)) (
+ log po (Y (x) (5)
prediction
end-to-end
where explicitly list out 0, o, and s representing the parameters of the latent program decoder, program encoder, and latent decoder respectively.
Furthermore, for the first 10K steps of training, give embeddings of the ground-truth program Y, averaged over every 2 tokens, as the latent sequence instead of eY)... This pre-training ensures that initially, the latent code carries some information about the program so that the attention the code
4

---

Under review as a conference paper at ICLR 2021
has reasonable gradients that can then to propagated to the program encoder afterward pre- pre-training. Doing this was empirically shown to prevent the bypassing phenomenon where the latent code is ignored during decoding (Bahuleyan et al. 2017).
3.3 INFERENCE
During inference, we use multi-level variant of beam search to decode the output probabilities of our LP model. Standard beam search with beam B will generate the top- most likely programs ac- cording the model, and find the first one (if any) that is consistent with the specification (Parisotto eet al. 2017 Devlin et al., 2017). In our case, we first perform beam search for L latent beams, then for B programs per latent sequence. Note that during inference, the latent predictor will continue to generate latent tokens until an end-of -ee-uene token is produced. This means that the generated latent sequence does not necessarily satisfy having length [T/2*] as during training; however, we found the latent sequence lengths during training and evaluation to be close in practice.
Setting B allows for the maximum exploration of the latent space, while setting L = 1 reduces our method to standard beam search, exploitation of the most likely latent decoding. We choose == VB in our experiments, but explore the effect of various choices of L in Section 5.2
4 RELATED WORK
Program Synthesis Our work deals with program synthexis, which involves combinatorial search for programs that match specification. Many different search methods have been explored within program synthesis, including search within a version-space algebra (Gulwani 2011). bottom-up enumerative search (Udupa al. 2013), stochastic search (Schkufza al. 2013) & genetic program-
ming (Koza] 1994), or reducing the synthesis problem to logical satisfiability (Solar-Lezama et al.)
2006 Neural program synthesis involves learning neural networks to predict function distributions t0 guide a synthesizer (Balog et al. 2017). or the program autoregressively in an end-to-end fashion Parisotto et al. 2017 Devlin et al. 2017). SketchAdapt (Nye al.] 2019) combined these ap- proaches by first generating program sketch with holes, and then filling holes using conventional synthesizer. Related to our work, DreamCoder (Ellis et al. 2020) iteratively builds a sketches us- ing progressively more complicated primitives though a wake-sleep algorithm. Our work is closely related in spirit but fundamentally differs in two ways: (1) our sketches are comprised a general latent vocabulary that is learned in simple, self-supervised fashion, and (2) our method avoids enumerative search, which is prohibitively expensive for large program spaces. There is also a line of work that deals with learning to process partial programs in addition to the specification. In execution- guided program synthesis, the model guides iterative extensions of the partial programs until matching one is found (Zohar & Wolf 2018: Chen et al. 2019 Ellis et al. 2019). Balog al.) (2020) of late proposed a differentiable fixer that is trained to iteratively edit incorrect programs. We treat these works as complementary, and can be combined with ours to refine predictions.
Discrete Latent Bottlenecks Variational autoencoders (VAE) were first introduced using contin- uous latent representations (Kingma & Welling, [014]] Rezende et al., 2014). Several promising approaches were proposed use discrete bottlenecks instead, such as continuous relaxations of cat- egorical distributions i.e. the Gumbel-Softmax reparametrization trick (Jang et al. 2017 Maddison ctt al. 2017). Recently, VQ-VAEs using nearest-neighhoor search on a learned codebook (see [Sec- tion for more details) achieved impressive results almost matching continuous VAEs (van den Oord et al. 2017 Roy et al. 2018).. Discrete bottlenecks have also been used for sentence com- pression (Miao & Blunsom 2016) and text generation (Puduppully et al.. 2019). but these works does not learn the semantics of the latent codes, like ours does. Within the domain of synthesis Bombarell et al. (2018) have applied Bayesian optimization within a continuous latent space to guide this structured prediction problem. Learning to search has also been considered in the structured prediction literature (Daumé et al., 2009; Chang al. 2013 Ross et al. 2011), but to our knowledge. these works do not consider the problem of learning a discrete representation for search. Notably, VQ-VAE methods have been successfully used to encode natural language into discrete codes for faster decoding in machine translation (Kaiser et al.) 2018). Our work similarly uses VQ- to learn a discrete code, but we use the learned code in a two-level search that improves accuracy. To do so, we propose model that is autoregressive on both the la- tent and program space, and perform two-level beam search on latent codes and programs. The key novelty behind our work is that first searching over a learned discrete latent space can assist search over the complex program space; using a VQ VQ-VAE as Kaiser et al. (2018) did enables us to do so.
of chemical molecules,
5

---

Under review as a conference paper at ICLR 2021
5 EXPERIMENTS
We now present the results of evaluating our Latent Programmer model in two test domains: syn- thesis of string transformation programs from examples and code generation from natural language descriptions. We compare our LP model against several strong baselines.
RobustFill [LSTM] is seq-to-seq LSTM with attention the input specification, and trained to autoregressively predict the true program. The architecture comparable to the RobustFill model designed originally for the string transformation tasks in our first domain (Devlin et al. 2017). but easily generalizes to all program synthesis domains. We detail the architecture in Appendix A
RobustFill [Trrasformerr] alternatively uses Transformer architecture, equivalent in architecture to the latent planner in our LP model. also trained to autoregressively predict the program. Trans- formers were found to perform much better than LSTMs in language tasks because they process the entire input as a whole, and have no risk of forgetting past dependencies (Vaswani et al. (017). This baseline can be also be considered of an ablation of our LP model without any latent codes.
The central novelty of our work is in realizing that by learning a discrete representation, we can perform structured search on two levels. We introduce two ablative baselines, which replace the VQ-VAE with either a generic autoencoder or a VAE. In both cases the latent space is continuous, and well-known combinatorial search algorithms such as beam search cannot search over the space.
Latent RobustFill [A replaces the VQ-VAE component of our LP model with generic autoen- coder. This makes the latent code a sequence of continuous embeddings. The latent prediction loss in equation 5 is simply replaced by squared error between the output of the autoencoder and the latent predictor. Performing beam search over the continuous latent space is intractable, so during inference generate only one latent sequence per task; this is equivalent two-level beam search described earlier with L = 1. In addition, because we cannot define an end-of-sequence token in the latent space, this baseline must be given knowledge of the true program length even during inference, and always generates a latent sequence of length [T/2"].
Latent RobustFill [VAE] substitutes the VQ-VAE component with a VAE (Kingma & Welling 2014). This again produces continuous latent space, but regularized to be distributed approximately as a standard Gaussian. Performing beam search is still intractable, but we can sample L latent sequences from the Gaussians determined by the VAE, and perform beam search on the programs afterwards. Again, we assume that the true program length is known during inference.
5.1 STRING TRANSFORMATION
The first test domain is string transformation DSL frequently studied in the program synthesis literature [Parisotto et al. 2017 Devlin et al. 2017 Balog et al. 2020). Tasks in this domain involve finding program which maps set of input strings corresponding set of outputs. Programs in
the DSL are a concatenation of expressions that perform regex-based string transformations (see Appendix for the full DSL).
We perform experiments on a syn- thetic dataset generated by sampling programs from the DSL. then the cor- responding I/O examples using an heuristic similar to the one used in NSPS (Parisotto al., 2017) and Ro- bustFill (Devlin et al. (2177) to en- sure nonempty output for each input.
Accuracy
Method
B
10
100
RobustFill [LSTM]
45%
49%
61%
RobustFill [Transformer]
47%
51%
61%
Latent RobustFill [AE]
47%
50%
60%
Latent RobustFill [VAE]
46%
51%
62%
Latent Programmer
51%
57%
68%
We consider programs comprising of a concatenation of up to 10 expres- sions and limit the lengths of strings in the I/O to be at most 100 characters. All models have an embedding size 128 and hidden size
Table I:
Accuracy on string transformation domain.
of 512, and the attention layers consist of 3 stacked layers with 4 heads each. For the LP model, we used a latent compression factor = 2 and vocabulary size = 40. The models are trained on roughly 25M tasks, and evaluated on 1K held-out ones.
In Table I we report the accuracy- the number of time a program was found conforming to the I/O examples-of of our method against the baselines. Across all beam sizes, L.P model performed 5-7

---

Under review as a conference paper at ICLR 2021
Length
RobustFill Acc.
LP Acc.
10 Accuracy
0.58
94.5%
94.0%
0.56
83.9%
84.6%
72.8%
72.2%
4
63.1%
66.1%
47.1%
49.8%
0.52
6
40.6%
43.0%
30.2%
34.6%
0.50
8
22.7%
28.4%
2e6
4e6
1e7
2e7
18.6%
27.0%
Trainable Parameters
10
14.4%
25.6%
Robustrill [LSTM]
RobustFill [Transformer]
Latent Programmer
(b)
(a)
Figure 3: (a): Influence of hidden size on beam-10 10 accuracy, (b): Beam- 10 accuracy of baseline transformer and LP by ground truth program length.
percentage points better (over 10% of baseline accuracy) than the next best model. From our ablative study, we see that having two-level using discrete latent codes was important, as the basclines over continuous latent spaces performed comparably to the traditional RobustFill model.
Recently, SketchAdapt also proposed two-level search (Nye et al., 22019) but in the top-level, beam search over program space aug- mented with a HOLE token. In con- strast, our method searches over learned, general latent space. During low-level search, SketchAdapt merates partial programs to co-opt the HOLE tokens using learned syn- thesizer similar to DeepCoder (Balog et al. 2017). whereas we again perform beam search. To compare the two, we evaluate our LP model on samples generated according to Nye et al. (2019). which slightly modifies the DSL to increase the performance of synthesizers, and report results Table 2, Since enumeration can be done more quickly than beam search, we let SketchAdapt synthesize 3, 0000 programs using B top-level beams, whereas our LP model can only generate B programs. Our LP model is able to outperform SketchAdapt even in the modified DSL..
Accuracy
Method
performs
B=50
100
SketchAdapt (yye al. 2019
63%
64%
Latent Programmer
64%
67%
Table 2: Accuracy on string transformation domain of Nye
al. 2019). SketchAdapt results are from Nye et al. (2019)
with 3, 000 synthesized programs (similar wall clock time).
5.2 ANALYSIS
We conduct extensive analysis to better understand our LP model in terms of learning, the ability to generate long programs, and diversity in the beams. All results are reported with beam size B 10.
Model Size Our LP model uses an additional latent code for decoding, which introduces additional parameters into the model than the baseline RobustFill model. To make fair comparison, we vary the embedding and hidden dimension of all of our evaluated methods, and compare the effect of the number trainable parameters on the accuracy. Figure 3/a) shows that all methods respond well to an increase in model size. Nevertheless, we see that even when normalized for size, our L.P model outperforms baselines by significant margin.
Program Length Prior work has shown that program length is reasonable proxy measure of problem difficulty. We hypothesize that using latent codes is most beneficial when generating long programs. |Figure 3)b) shows how ground-truth program length affects the accuracy of our LP model compared to RobustFill, which lacks latent codes. As expected, accuracy decreases with problem complexity. Perhaps surprisingly, though, we see large improvement in our LP model's ability to handle more complex problems. In Figure 4 we also show an illustrative example where our LP model found valid program whereas the RobustFill model did not. In this example, the ground-trutt program was long but had repetitive underlying structure. Our LP model correctly detected this structure, evidenced by the predicted latent sequence. We show additional examples
the domain

---

Under review as a conference paper at ICLR 2021
Inputs
Outputs
Program
Haacob,Ethan,,hee 11"
"11:J.E.J."
GetToken 1
Const (:)
Eelijah,DanielAidee 3162"
"3162:E.D.A"
GetTooke__Al__CAPS__
Const (.)
26"
"26:R.O.M."
GetToxen_AAL__CASS__
Const (-)
Sam 510"
"510:M.B.S." GetToken_ALL_CAPS_55
Const (.)
RobustFill
Const (:)
GetToken_AAi_COPE__2 | Const (.)
LP
GetAl1_NUMBHS Const (:)
Const (.)
GetToken ALLL _ 2 Const (.) GetToken ALL __P____AP________________ -1 Const (.)
LP Latent
14 36 TOK_ 36 366_
Figure 4: Illustrative string transformation problem where the ground-truth program was long but had repetitive structure. The baseline Transformer was unable to generate the program but our LP model, which first predicts coarse latent sequence, was able to.
2
Accuracy
Distinct n- G-aara
Latent Beam Size
Accuracy
2
52%
n
3
55%
8
49%
=
52%
0.13
0.23
0.26
0.28
2
55%
0.13
0.24
0.26
0.28
K
Accuracy
3
57%
0.14
0.25
0.28
0.31
5
57%
0.14
0.26
0.29
0.32
10
48%
10
56%
0.14
0.26
0.30
0.33
40
55%
100
51%
(a)
(b)
Figure 5: (a): Effect of latent beam size on beam-10 accuracy and number of distinct n-grams (normalized by total number of tokens). (b): Effect of latent length compression & and vocabulary size K on beam-10 accuracy.
is important to note that our method allows tokens in the discrete latent code to have arbitrary meaning, yielding rich and expressive latent representations. However, the trade-off is that because the latent codes were not grounded, it difficult objectively interpret the latent codes. Grounding the latent space to induce interpretability is an avenue for future work.
Figure of AAppnndix B]
Latent Beam Size In multi-level beam search of beam size B, first L latent beams are decoded, then [B/L] programs per latent sequence. The latent beam size controls how much search is performed over latent space. We theorize that higher will produce more diverse beams; however, too high L can be harmful in missing programs with high joint log-probability. We show the effect of latent beam size on both the beam- 10 accuracy and a proxy measure for diversity. Following prior work, we measure diversity by counting the number of distinct n-grams in the beams, normalized by the total number of tokens to bias against long programs (Vijayakumar et al.] 2018). We report the results varying L for B = 10 in Figure 5ja). As expected, increasing the latent beam size improves diversity of output programs, but excessively large L harms the final accuracy. An important observation is that the L case, where one latent code is used to decode all programs, performs similarly to bascline RobustFill. In this extreme, no search is performed over the latent space, and our proposed two-level search reduces only searching over programs; this is further evidence that explicitly having two-level search is critical to the I.P model's improved performance.
Latent Length and Vocabulary Size Since the discretization bottleneck is critical component in generating latent codes our LP model, we also investigate its performance conjunction with different settings of hyperparameters. Two important variables for the VQ are the latent length compression factor c, and size of latent vocabulary K. If c is too small, the latent space becomes too mean individual latent tokens cannot encoded the
large to search; the other hard, too large information needed to reconstruct the program. Similarly, we expect that too small of a vocabulary K can limit the expressiveness of the latent space, but too large K can make predicting the correct latent code too difficult. We confirm this in our evaluations in Figure 5)b) and Figure 5)c).
8

---

Under review as a conference paper at ICLR 2021
Doestring
Program
get an environment variable
def getenv (key, default-None): return enviren. get (key, default)
return list of the words in the string s
def split (s, sep-None, maxsplit=-1); return splpi (sep, maxsplit)
Figure 6: Example problems from the Python code generation dataset.
5.3 PYTHON CODE GENERATION
Our next test domain is Python code generation (CG) task, which involves generating code for function that implements a latural-language specification. The dataset used consists of 111K python examples, which consist of docstring and corresponding code snippet, collected from Github (Wan
et al. 2018). An example docstring and program from the dataset is shown in Figure 6
We used language-independent tokenizer jointly on data (Kudo & Richardson] 2018). and pro- cessed the dataset into a vocabulary of 35K sub-word tokens. Furthermore, following Wei et al. (2019), we the maximum length of the programs be 150 tokens resulting in 85K examples. Across all models, we set the embedding size to be 256 and hidden size to be 512, and the atten- tion layers consist of stacked layers with 16 heads each, similar to in neural machine translation Vaswani et al.] 2017). For the LP model, we used a latent compression factor = 2 and vocabulary size K 400 after hyperparameter search. The models are evaluated on 1K held-out examples.
We initially found that it was difficult for the program encoder to detect latent sequence structure in the ground-truth programs as is due to the noise in variable names. To remedy this, we used an abstract syntax tree (AST) parser on the ground-truth programs to replace the i-th function argument and variable appearing the program with the token ARG_i i and VAR_i, respectively. This was only used in training the program encoder and did not impact evaluation.
We evaluate performance by comput- ing the best BLEU score among the output beams (Papineni et al.] 2002). We computed BLEU as the geometric mean of n-gram matching precision 4. [Table shows that our LP model outperforms the baselines. From the results, it can be seen that this is difficult task, which may be due to the ambiguity speci- fying code from a short doestring de- scription. As evidence, we addition- ally include results from a recent work that proposed seq-to-seq CG models on the same data that performed similar to our baselines (Wei et al, 2019).. These results show that improvements due to the LP model exist even in difficult CG domains. For example docstrings and code generated by the LP Model, refer to Figure in Appendix B
BLEU
Method
B 1
10
100
Base Wei et al.
2019
10.4
Dual
Wei al. 2019
12.1
scores up
RobustFill [LSTM]
11.4
14.8
16.0
RobustFill [Transformer]
12.1
15.5
17.2
Latent Programmer
14.0
18.6
21.3
Table 3: BLEU score on code generation task.
6 CONCLUSION
In this work we proposed the Latent Programmer (LP), a novel neural program synthesis technique that leverages a structured latent sequences to guide search. The LP model consists of a latent predic- tor, which maps the input specification a sequence of discrete latent variables, and latent program decoder that generates a program boken-byttoken while attending to the latent sequence. The latent predictor was trained via suef-ssuee method in which discrete autoencoder of programs was learned using a discrete bottleneck, specifically VQ-VAE (van den Oord et al.) (017). and the latent predictor tries to predict the autoencoded sequence as if were the ground-truth. During in- ference, the LP model first searches in latent space for discrete codes, then conditions on those codes to search over programs. Empirically, we showed that the Latent Programmer outperforms of the-art basclines as Robustfill (Devlin et al.] (017), which ignore latent structure. Exciting future avenues of investigation include achieving better performance by grounding the latent vocabulary and generalizing our method to other tasks in natural language and structured prediction.

---

Under review as a conference paper at ICLR 2021
REFERENCES
Rajeev Alur, Rastislav Bodik, Garvit Juniwal, Milo M. K. Martin, Mukund Raghothaman, Sanjit A. Seshia, Rishabh Singh, Armando Solar-Lezama, Emina Torlak, and Abhishek Udupa. Syntax- guided synthesis. In Formal Methods in Computer-Aided Design, FMCAD 2013, Portland, OR, USA, October 20-23, 2013, pp. 1-8. IEEE, 2013.
Dzmitry Bahdanau, Kyunghyun Cho, and Yoshua Bengio. Neural machine translation by jointly learning align and translate. In International Conference on Learning Representations (ICLR), 2016.
Hareesh Bahuleyan, Lili Mou, Olga Vechtomova, and Pascal Poupart. Variational attention for sequence-to-sequee models. CoRR, abs/1712.08207, 2017.
Matej Balog, Alexander L. Gaunt, Marc Brockschmidt, Sebastian Nowozin, and Daniel Tarlow. Deepcoder: Learning to write programs. In International Conference on Learning Representa- fions (ICLR), 2017.
Matej Balog, Rishabh Singh, Petros Maniatis, and Charles Sutton. Neural program synthesis with differentiable fixer. CoRR, 10s24400.11994, 2020. URL ltttp:://axxi..ror wwwpa/wwwwww....////a/oaaa/ 10924
Kai-Woi Chang, Akshay Krishnamurthy, Alekh Agarwal, Daume III, and John Langford. Learning to search better than your teacher. In International Conference Machine Learning (ICML), 2015.
Xinyun Chen, Chang Liu, and Dawn Song. Execution- guided neural program synthesis. In Interna- tional Conference on Learning Representations (ICLR), 2019.
Hal Daumé, III. John Langford, and Daniel Marcu. Search-based structured prediction. Machine Learning Journal, 2009.
Jacob Devlin, Jonathan Uesato, Surya Bhupatiraju, Rishabh Singh, Abdel-rahman Mohamed, and Pushmeet Kohli. Robustfill: Neural program learning under noisy I/O. CoRR, abs/1 703.0400.,7 2017.
1703. C7469
Kevin Ellis, Maxwell I. Nye, Yewen Pu, Felix Sosa, Josh Tenenbaum, and Armando Solar-Lezama. Write, execute, assess: Program synthesis with REPI.. Neural Information Processing Sys- tems (NeurIPS), 2019.
Kevin Ellis, Catherine Wong. Maxwell Nye, Mathias Sable-Meyer, Luc Cary, Lucas Morales, Luke Hewitt, Armando Solar-Lezama, and Joshua B. Tenenbaum. Dreamcoder: Growing generalizable, interpretable knowledge with wake-sleep bayesian program learning. CoRR, abs/2006.08381, 2020. URL httpt::///axii..rrrrrr abs 20000
Rafael Gómezz-ombarelll, Jennifer N Wei, David Duvenaud, José Miguel Hernández-Looato, Benjamín Sänchez-LLengllngg Dennis Sheberla, Jorge Aguilera- Timothy Hirzel, Ryan P Adams, and Alán Espuru-Guzik Automatic chemical design using a Data-Driven con- tinuous representation of molecules. ACS Cent Sci, 4(2):268-276, February 2018.
Sumit Gulwani. Automating string processing in spreadsheets using input-output examples. In PoPL' I, January 26-28, 20/ 1, Austin, Texas, USA, 2011.
Sumit Gulwani, Oleksandr Polozov, and Rishabh Singh. Program synthesis. Foundations and Trends in Programming Langagges, 4(1-2))1-119, 2017. doi: 10. 10.1561/2500000010. URL https:
Eric Jang, Shixiang Gu, and Ben Poole. Categorical reparameterizzatio with gumbel-softmax. In International Conference on Learning Representations (ICLR), 2017.
Lukasz Kaiser, Aurko Roy, Ashish Vaswani, Niki Parmar, Samy Bengio, Jakob Uszkoreit, and Noam Shazeer. Fast decoding in sequence models using discrete latent variables. In International Con- ference Machine Learning (ICMI.,, 2018.
10

---

Under review as a conference paper at ICLR 2021
Diederik P Kingma and Max Welling, Auto-encoding variational bayes. In International Conference on Learning Representations (ICLR), 2014.
John Koza. Genetic programming means for programming computers by natural selection. Statistics and computing, 4(2):87-112, 1994.
Taku Kudo and John Richardson. SentencePiece: A simple and language independent subword tok- enizer and detokenizer for neural text processing. In Proceedings of the 2018 Conference Em- pirical Methods in Natural Language Processing: System Demonstrations, pp. 66-71, November 2018.
Woosuk Lee, Kihong Heo, Rajeev Alur, and Mayur Naik. Accelerating search-based program syn- thesis using learned probabilistic models. In Conference Programming Language Design and Implementation (PLDI), 436-449, June 2018
Chris Maddison, Andriy Mnih, and Yee Whye Teh. The concrete distribution: A continuous relaxation of discrete random variables. In International Conference on Learning Representations (ICLR), 2017.
Zohar Manna and Richard J. Waldinger. Toward automatic program synthesis. Commun. ACM, 14 (3):151-165, 1971.
Yishu Miao and Phil Blunsom. Language as latent variable: Discrete generative models for sen- tence compression. CoRR, abs/1609.07311,, 2016. URL
07317
Maxwell I. Nye, Luke B. Hewitt, Joshua B. Tenenbaum, and Armando Solar-Lezama. Learning to infer program sketches. International Conference on Machine Learning (ICMI), 2019.
Kishore Papineni, Salim Roukos, Todd Ward, and Wei-Jing Zhu. Bleu: A method for automatic evaluation of machine translation. In Proceedings of the 40th Annual Meeting on Association for Computational Linguistics, pp. 311-318. Association for Computational Linguistics, 2002.
Emilio Parisotto, Abdel-rahman Mohamed, Rishabh Singh, Lihong Li, Dengyong Zhou, and Push- meet Kohli. Neuro-symbolic program synthesis. International Conference on Learning Rep- resentations (ICLR), 2017.
Ratish Puduppully, Li Dong, and Mirella Lapata. Data-to-text generation with content selection and planning. In The Thirty-Third AAAI Conference on Artificial Intelligence, AAAI 2019, The Thirty- First Innovative Applications of Artificial Intelligence Conference, IAAI 2019, The Ninth AAAI
Symposium on Educational Advances in Artificial Intelligence, EAAI 2019, Honolulu, Hawaïi, USA, January 27- February I, 2019, pp. v33101.33016008. URL htt.::t:: / org/ /
AAAI Press, 2019, doi: 10. 10. 1609/aa.... v331 33016908
Danilo Jimenez Rezende, Shakir Mohamed, and Daan Wierstra. Stochastic backpropagation and approximate inference in deep generative models. CoRR, hts/1401.4088 2014. URI. https:
Stephane Ross, Geoffrey Gordon, and Drew Bagnell. reduction of imitation learning and struc- tured prediction to No-Regret online learning. In Geoffrey Gordon, David Dunson, and Miroslav Dudík (eds.), Conference on Artificial Intelligence and Statistics (AISTATS), volume 15 of Pro- ceedings of Machine Learning Research, pp. 627-635, Fort Lauderdale, FL, USA, 2011. PMLR.
Aurko Roy, Ashish Vaswani, Arvind Neelakantan, and Niki Parmar. Theory and experiments on vector quantized autoencoders, arXiv, May 2018
Eric Schkufza, Rahul Sharma, and Alex Aiken. Stochastic superoptimization. In Proceedings of the Eighteenth International Conference on Architectural Support for Programming Languages and Operating Systems, ASPLOS 13,, pp. 305-316, New York, NY, USA, 2013. Association for Computing Machinery. ISBN 9781450318809 doi: 10.1145/24511162455111
https:
7/doi. (i:bi.orgg/1.1110 /tt.:///./....1144/1111........0

---

Under review as a conference paper at ICLR 2021
Armando Solar-Lezama, Liviu Tancau, Rastislav Bodik, Sanjit A. Seshia, and Vijay A. Saraswat. Combinatorial sketching for finite programs. In Conference on Architectural Support for Pro- gramming Languages and Operating Systems, ASPLOS 2006, San Jose, CA, USA, October 21-25, 2006, pp. 404-415. ACM, 2006.
Phillip D Summers. A methodology for lisp program construction from examples. Journal of the ACM (JACM), 24(1):161-175, 1977.
Abhishek Udupa, Arun Raghavan, Jyotirmoy V Deshmukh, Sela Mador Mador-Haim, Milo M K Mar- tin, and Rajeev Alur. TRANSIT: Specifying protocols with concolic snippets. In Conference on Programming Language Design and Implementation (PLDI), pp. 287-296. Association for Computing Machinery, 2013.
Aäron den Oord, Oriol Vinyals, and Koray Kavukcuoglu. Neural discrete representation learn- ing. In Neural Information Processing Systems (NeurIPS), 2017.
Ashish Vaswani, Noam Shazeer, Niki Parmar, Jakob Uszkoreit, Llion Jones, Aidan N. Gomez, Lukasz Kaiser, and Illia Polosukhin. Attention all you need. In Neural Information Processing Systems (NeurIPS), 2017.
Ashwin K. Vijayakumar, Michael Cogswell, Ramprasaath R. Selvaraju, Qing Sun, Stefan Lee, David Crandall, and Dhruv Batra. Diverse beam search: Decoding diverse solutions from neural sequence models. In AAAI, 2018.
Y. Wan, Z. Zhao, M. Yang, G. Xu, H. Ying, J. Wu, and P. S. Yu. Improving automatic source code summarization via deep reinforcement learning. In 2018 33rd IEEE/ACM International Conference on Automated Software Engineering (ASE), pp. 397-407, 2018.
Bolin Wei, Ge Li, Xin Xia, Zhiyi Fu, and Zhi Jin. Code generation as dual task of code summa- rization. In Neural Information Processing Systems (NeurIPS), 2019.
Amit Zohar and Lior Wolf. Automatic program synthesis of long programs with learned garbage collector. In Neural Information Processing Systems (NeurIPS), 2018.
12

---

Under review as a conference paper at ICLR 2021
Program Y
concat(er,ea...)
Expression e = f I mi(22) n(f) conststr(e)
Substring f = SubStr(k1, 12) bn
Nesting (etToken((,i) ToCase(s) Replace((), 62) Trim() GetUpto Get GetFrom(r)
GetFirst((.)) GetAAl(()
Regex
f1 ... t. ... 6m
Type t
= NJMBER WORD ALPHANUM AIPL_CAPS PROP_CASH LOWER DIGIT
CHAR
Case = PROPER ALL CAPS LOWER
Position & = 100
99
1 2
100
Index i
5 4
1
5
Boundary b
START END
Delimiter 8
& x)% 0// $ 5
Character
A a
9 & .2
Figure 7: The DSL for string transformation tasks DDvlin et al. 2017)
A EXTENDED DESCRIPTION OF DSL AND ROBUSTFILL MODEL
The DSL for string transformations we use the same as used RobustFill (Devlin et al. 2017). and is shown in Figure 7| The top-level operator for programs in the DSL is a Concat operator that concatenates a random number (up to 10) of expressions e;. Each expression e can either substring expression f. nesting expression
constant string A substring expression can either return the substring between left 6 and right k2 indices, or between the ii-th occurence of regex and i2-th occurence of regex r2. The nesting expressions also return substrings of the input, such as extracting the i-th occurrence of a regex, but can also be composed with existing substring nesting expressions for more complex string transformations.
RobustFill Model RobustFill (Devlin et al. 2017) is a seq-to-seq neural network that uses encoder-decoder architecture where the encoder computes a representation of the input e(X), and the decoder autoregressively generates the output given the source representation, i.c. conditional likelihood of Y [y1,--. 1.......2 .yr] decomposes as p(Y|X) = P(voleee X)-
In RobustFill, the probability of decoding each token Vt given by p(yeluee X) Softmax (W (h,)) with W being the projection onto logits, unnormalized log probabilities. The hidden representation h2 is an LSTM hidden unit given by,
E. Attention (hy-1,e(X)).
h = LSTM LSTM Eb)
Here e(X) is the sequence of hidden states after processing the specifications with an LSTM en- coder, and Attention (Q, V) denotes the scaled dot-product attention with query Q and key-value sequence (Bahdanau et al. 2016). In the case of X being multiple I/O examples, the RobustFill model of Devlin al. (2017) uses double attention
$ Attention (h--1,e(44))
0
Attention (Concat (h4 ,((:))
h4, LSTM (h Concat (sh,, (.,) V1 SiS
and hidden states are pooled across examples before being fed into the final softmax layer, or h = paxpoolisisN (anh(V(hr..) where V is another projection.
13

---

Under review as a conference paper at ICLR 2021
B EXAMPLES OF GENERATED PROGRAMS AND LATENT CODES
Inputs
Outputs
LP Outputs
"Mason Smith"
"Smith M"
"Smith M"
"Henry Myers"
"Myers H"
"Myers H"
"Barry Underwood"
"Underwood B"
"Underwood B"
"Sandy Jones"
"Jones S
"Jones S"
LP
Get _CAEE_ ConstStr(" ")
BetToken_CHAE (Get (GetToken_PPO
LP Latent
TOK_30 TOK_13
TOK_33 TOK_30
Inputs
Outputs
LP Outputs
"January 15"
"jan 15"
"jan 15"
"febuary 28
"feb 28"
"feb 28"
"march 1"
"mar 1"
"mar 1"
"October 31"
"oct 31"
"oct 31"
LP
ToCase_LowER (Substr (1, 31) ConstStr ")
GeUToken_NUMBER
LP Latent
TOK_11 TOK_26 | TOK_17
Inputs
Outputs
LP Outputs
"(321) 704 3331"
"321.704.3331"
"321.704.3331
"(499) 123 3574"
"499. 123.3574"
"499.123.35744
"(555) 580 8390"
$555.580.8390
3555.580.8390
"(288)225 6116"
"288.225.6116
"288.225.61
LP
GetToken NUMBER Get
ConstStr(.)
Replace_"
"_. (SubStr (-8, -1))
LP Latent
TOK_17
TOK_27
TOK_22
TOK_16
Inputs
Outputs
LP Outputs
"Milk 4, Yoghurt 12, Juice 2, Egg 5"
"M.E."
"M.E."
"US:38 China:35 Russia:27 India:1"
"U.I."
"U.I."
*10 Apple 2 Oranges 13 Bananas 40 Pears" "A.P."
"A.P."
"parul 7 rico 12 wolfram 15 rick 19"
"P.R.""
LP
GetToken_CEAR (GetToken_ CASE_1 SetToken_CHAR_1
1 Const (.)
Const
LP Latent
_OK_39
30
6
TOK_38
TOK_30
Figure 8: Latent codes and programs found by Latent Programmer string transformation tasks. Red denotes I/O where the predicted program mapped input to an incorrect output.
14

---

Under review as a conference paper at ICLR 2021
Docstring
Program
get an environment variable
def sst_key (key, val, key_prefix=Nonee) environ. (key, key_prefix)
return list of the words in the string mean squared error function
def split (s, sep=None, maxsplit=-1); return s.split (sep, maxsplit)
def aaaa__
y_pred)
return tf. reducecuce_man Beetuce_meeaHiieee (tf. squua (y true
y-prod))) )
read python file
def read_file (fname)
f open (fname)
with open (fname, 'r') as f:
f.seek (0)
return f.read
pickle dump
pickle_save (filename, data)
with open (fillnaame,, 'r') as f:
pickle.dump (data, f)
takes timedelta and returns the total number of seconds
def total_seconds (delta): return wtw.elta..ccooccooeee.. + dielta.ddas 24) 3600) (10++6))((10++6))
Figure 9:
Programs found by Latent Programmer in Python code generation dataset. Red denotes ares where the predicted program deviates from human code.
15


Reviews:
[{"review_id": "QyeHzCorz0d", "reviewer": "AnonReviewer3", "summary": "", "questions": "", "limitations": "", "rating": 7, "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": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "Summary: This paper proposes a two-level hierarchical program synthesizer, Latent Programmer, which first predicts a sequence of latent codes from given input-output examples, and then decodes the latent codes into a program.  The sequence of latent codes can be viewed as a high-level synthesis plan, guiding the subsequent low-level synthesis. Latent Programer significantly outperforms RobustFill on string manipulation tasks and achieves state-of-the-art results on Python code generation tasks. \n\nQuality: The paper presents a novel program synthesis idea and the evaluation is promising and convincing.\n\nClarity: The writing provides enough background and explains the main idea in a very clear manner.\n\nOriginality: The application of Vector Quantized Variational Autoencoder for a two-level hierarchical synthesis is quite novel. \n\nSignificance: This work shows that a promising hierarchical learning approach for program synthesis. Its effectiveness motivates many future explorations in this direction.\n  \n\nQuestions: \n\nQ1: Why Python Code generation tasks use BLEU as the metric, rather than functional correctness?\n\nQ2: Latent codes are motivated as a \"high-level plan\"? Do you observe certain interpretability of latent codes?\n\nQ3: Since the lengths of synthesized programs are different for different tasks, it might be good to have a task-specific length of latent codes. The authors do show that varying the length of latent codes could affect performance. Is the length of latent codes (always) proportional to the length of synthesized programs?\n", "extra_scores": {}, "extra_text": {}}, {"review_id": "NibCYzKxZbJ", "reviewer": "AnonReviewer2", "summary": "", "questions": "", "limitations": "", "rating": 3, "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 ###\nThe paper addresses the problem of program synthesis from examples, and also evaluates on program synthesis from natural language descriptions.\nThe paper proposes Latent Programmer, an approach that employs an adapted VQ-VAE to predict a sequence of latent codes, and then generates the output program conditioned on those codes.\nThe evaluation shows improved results over straightforward LSTM and Transformer baselines.\n\nOverall, I think that the approach is interesting, but the paper is very difficult to read and follow, and I am not sure that the evaluation is sufficiently extensive. I am thus voting for rejection at this time. \n\n### Strengths ###\n+ The proposed approach is a first application of VQ-VAE to program synthesis.\n+ The models outperforms LSTMs and Transformers\n\n### Weaknesses ###\n- The paper is very unclear and difficult to follow\n- It is unclear **why** the approach works\n- It is unclear whether this is a direct application of VQ-VAE to program synthesis, or is there any novel insight.\n- The evaluation is lacking comparison to additional baselines and datasets.\n\n**Clarity** - the paper is very difficult to read and follow. For example, the first few pages contain obscure phrases like \"discrete latent codes\", \"our sketches are comprised of a general latent vocabulary\", \"the semantics of the latent codes\", \"stop gradient operator\", \"sequence of tokens in latent space\", \"general vocabulary of discrete latent variables\". While I could understand each individual word, it was unclear what exactly do the authors refer to.\n\nThe related work section is thorough and compares previous approaches to the proposed approach, but at this point in the paper, the reader has no idea what these comparisons refer to.\nOnly by the end of page 4 I had a general idea in mind of what the proposed approach does, and still, I couldn't perfectly match the description to Figure 2 (Was $Z'$ defined anywhere? What *exactly* do the authors mean by quantization and how coarse is it? how are the program and the I/O examples encoded?). \n\nAdditionally, there are plenty of smaller things that make the paper even harder to follow. For example: the caption of Figure 2 is uninformative; Equation (1) and its preceding text could simply say \"nearest neighbor\"; in Equation 2 it isn't even clear what is $x$, and what kind of encoder is $ec$, both architecturally and in terms of representation? Are the two Transformers \"hierarchical\" or just \"two-level\" or \"two modules\" (Section 4.1, all these phrases are used to describe these two transformers); the equations in Equation 3 are written from right-to-left. Section 4.1 says that \"the plan is a sequence of tokens in latent space, denoted <TOK_1>, ..., <TOK_K>\". If these are \"tokens in **latent** space\", can we just call them \"a sequence of vectors\", instead of using the word \"token\" in an unusual way?\n\n**Why it works** - the paper does not give much intuition/explanation to **why** does the proposed approach work. The argument from the Abstract / Introduction that \"discrete latent codes can learn a useful representation for search\" is not very convincing, because eventually, the search is performed in the program space. So, the model does need to generate a sequence of tokens eventually. I think that maybe what the two steps of (1) generating the codes and then (2) generating the program given the codes do is provide more *diversity* of solutions, rather than better search.\n\n**VQ-VAE** - before reading the paper, I was not familiar with VQ-VAE. The background in Section 3 was not sufficient and not clear enough. I understand that explaining a new background concept is challenging, but I still think that Section 3 could be written more clearly *without* taking more space.\nFor example, by saying \"nearest neighbor\" instead of multiple lines and equations, and without citing \"van den Oord et al., 2017\" three times on the same half a page.\n\nAnother issue is that I am not sure whether this paper simply applies VQ-VAE on program synthesis, or is there a novel adaptation following insights about programs?\nFurther, is the focus the VQ-VAE really needed, or can a standard VAE work as well (or even an AE)?\n\n**Evaluation** - the evaluation presents impressive results, mainly compared to LSTMs and Transformers, which is an important comparison that is not always performed in all papers. However, it seems that there are not enough baselines to put the results in context. Additionally, the datasets could have been more standard: why generating a new dataset for string transformation? why taking such a small dataset for NL->python?\n\n* Baselines - aren't there any recent baselines for string transformation, other than RobustFill? There is no other neural or non-neural available model for program synthesis from examples?\nIn NL->code, I am sure that there are other baselines other than Wei et al., 2019. For example:\n\n1. Iyer et al., Mapping Language to Code in Programmatic Context, 2018\n2. Iyer et al., Learning Programmatic Idioms for Scalable Semantic Parsing, 2019\n3. Yin et al., \"TRANX ..\", 2018\n4. Shin et al., \"Program Synthesis and Semantic Parsing with Learned Code Idioms\", 2019\n\nand other semantic parsing papers.\n\n* Datasets - in the program synthesis task, the authors created a new dataset. Can the authors use existing datasets, where previous work already tuned their baselines on?\nIn the code generation task, aren't there any other datasets, with hopefully more than 11K examples?\n\n* Analysis - the authors do perform some analysis in Section 5.2, but it still feels that it is unclear why the model works. For example, can the VQ-VAE be simply VAE or AE? Are all the losses important? What I am looking for is a simpler architecture that achieves similar results using the same general idea.\n\n### Questions to Authors ###\n1. How can two Transformers have only 15M parameters? What would happen if RobustFill-Transformer used a full-sized Transformer-base?\n2. Can we have an additional baseline that improves diversity in RobustFill, to reject the hypothesis that the VQ-VAE simply increases the diversity of solutions? I am not sure how.\n3. The phrase \"self-supervised\" appears 5 times throughout the paper. Is it really self-supervised? The self-supervised part is that the encoding of the I/O examples is compared with the encoding of the program. Aren't the pair (program, specification), in fact, supervision?\n4. Can the approach work with a code generator that does not generate the code as a sequence of tokens, such as Maddison & Tarlow (ICML 2014), Yin & Neubig (ACL 2017), Brockschmidt et al. (ICLR 2019), or Alon et al (ICML 2020)? or is the proposed approach limited to only \"textual\" code generators?\n\n### Minor questions and comments ###\n* Related work, paragraph2: \"these works does not\" -> \"these works do not\"\n* It would help following if Figure 2 was in the same page that it is referenced\n* It would be easier to read the appendix and refer it if the authors could append the appendix after the references, in the same PDF, instead of attaching it as a separate zip.\n\n====== Post discussion comments ======\n\nAfter reading all reviews, responses, and discussions, I still do not see evidence that the model has learned a \"high-level plan\", which is the main claim of the paper.\n\nI agree that most deep learning models are not interpretable, but most papers do provide some qualitative/anecdotal/generality/strong empirical evidence to support their claims. In this paper, I do not see such strong evidence.\n\nMy main concerns:\n\n1. Is it possible that the 2-stage search simply increases the diversity of solutions? \nIf there is an empirical improvement, I would like to understand the simplest explanation (\"Occam's razor\"). If the main contribution is diversity, I would expect the authors to spell it out clearly.\n\nFurther, if the main contribution is diversity, maybe there are much simpler and general ways to achieve diversity (e.g., diversity inducing versions of beam search), that can be applied to different architectures (i.e., not coupled with VQ-VAE).\n\nI feel that my question \"Can we have an additional baseline that improves diversity in RobustFill, to reject the hypothesis that the VQ-VAE simply increases the diversity of solutions?\" was not answered by the authors.\n\n2. The 2-stage search is a general approach, but the paper did not convince me that it is useful to settings beyond the FlashFill task, and for models other than the textual approach where programs are generated as text.\n\nIf the authors claim that their approach allows \"high-level planning\", I would expect to see that it works across different models / tasks / datasets / settings.\n\nMinor: I do not agree with the authors that this is self-supervised. I think that the paper uses the term \"self-supervised\" incorrectly.\n\n", "extra_scores": {}, "extra_text": {}}, {"review_id": "Kuuft1LDVNO", "reviewer": "AnonReviewer1", "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": "This paper proposes a VQ-VAE approach for program synthesis (generating a program from specifications, either input-output pairs or natural language description). Generally speaking, a VQ-VAE learns an autoregressive discrete latent code in addition to traditional Seq2Seq learning, and perform beam search on both latent code and output programs. \n\nExperimental results show that the model outperforms three baseline systems on two tasks. \n\n---\nI have major concerns on the nature of the VQ-VAE model. \n\n\n1) First of all, this paper heavily relies on Kaiser et al. (ICML'2018), except that the decoder of this paper is autoregressive and that this paper proposes beam search on the latent sequential discrete codes. \n\nHowever, this paper has very light citation on Kaiser et al. (2018). The authors should be more honest about previous work and make direct comparison on the difference. What is taken from previous work? What is an adaptation? What is an extension?  \n\nThe current writing shows that this paper has a heavy development on the model, when in fact, it's mostly taken from previous work. \n\n2) The author claims that VQ-VAE serves as a discrete bottleneck. However, I strongly disagree with this. \n\nThe decoder in this paper is well aware of the input by \"TransformerDecoder(Y', E)\" in Eq 4, where the E = TransformerEncoder(X). \n\nSo, the decoder can just learn from the input X and disregard the VQ-VAE space, despite a few semantic losses imposed on the latent code (latent prediction and end-to-end in Eq 5). Since the VQ-VAE latent space is in addition to a traditional Seq2Seq training, it cannot serve as a bottleneck/regularization.\n\nThis is known as the \"bypassing phenomenon\" in previous work:\n\nBahuleyan et al., Variational attention for sequence-to-sequence models, 2018. \n\nThe authors may want to explain why their VQ-VAE would not suffer from the bypassing phenomenon. \n\nNote: the bypassing phenomenon is actually different in  Kaiser et al. (2018). Their decoder is non-autoregressive, so their sequential discrete latent space can provide autoregressive information. But in this work, the decoder is autoregressive, which can simply learn from X directly. \n\n3) What's the real benefit of modeling the discrete latent codes by VQ-VAE? A natural way of having real discrete bottleneck is by reinforcement learning. There lacks comparison and discussion. \n\nNote: we all know RL systems are difficult to learn, but the auxiliary losses is Eq 5 can all applied to RL, too. You may also do pre-training or relaxations for RL. \n\n4) The latent codes are generated in an autoregressive fashion. During training, the number of latent codes is ceiling(T/(2^l)). But how do you know the number of codes during test? Did you include an EOS token for such autoregressive generation? If yes, how easy is it to learn the precise semantics of EOS without direct supervision signal?\n\n5) There is no quantitative analysis on the learned code. While there is an example, it is inadequate. We have no measure on how typical is the shown example.\n\n \n---\n\nI also have major concerns on experiments.\n\n6) The evaluation metrics are peculiar. For example, distance n-grams are used to evaluate diversity. We understand diversity is important for natural language generation, but why do we need diversity for program generation? \n\nThe BLEU is computed by the best BLEU score among the output beams, but increasing the beam size may not improve top-beam performance.\n\n7) Baseline models are inadequate. For the example-to-program generation, the authors only compared with Seq2Seq with LSTM or Transformer. There has been other efforts on search-based program synthesis, for example, Balog et al. (2017, 2020). I'd like to see a comparison, and what's the further improvement when they are combined (as claimed by this paper)?\n\nIn code generation from description, the authors only compared with two models in Wei et al., 2019 and two variants of Seq2Seq. But there could be more benchmarked datasets, like Hearthstone, spider, and other semantic parsing datasets in the old days. \n\n---\n\nMinor: \n\nThe exponential moving average is not proposed in Roy et al. (2018). It's proposed in Appendix A of the original VQ-VAE paper. \n\n---\n\nIn short, the discrete latent space beam search appears to be some interesting idea. But I have concerns on the soundness of this paper. \n\nIt is also noted that there's no code or output available. \n\n\n", "extra_scores": {}, "extra_text": {}}, {"review_id": "GIFzK-Qr4-M", "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": "Edit: I have increased my score to 7.\n\n\nThis paper introduces a novel program synthesis system called the Latent Programmer, which uses discrete latent codes as a representational scheme to solve program synthesis problems in two domains: string transformations from examples and code generation from language descriptions.\n\nStrengths:\n\n-The paper is relatively clear.\n\n-The approach is novel.\n\n-The results seem to support the claim that this model outperforms baselines (although it would help to report the results of multiple runs with standard error).\n\n-The relative simplicity of the approach is a plus; it doesn't seem that it would be terribly difficult for a researcher to adopt this technique to a new problem.\n\nWeaknesses:\n\nI think the baselines/ablations could be more complete. For example, it seems that the gains over the RobustFill baselines could be due to any of 3 factors: 1) use of discrete representations 2) the use of an autoencoding loss, or 3) the ability to search through latent representations at test time.\n\nUnless I'm mistaken, compared to LP, the transformer RobustFill baseline differs in terms of both (1) and (2): RobustFill does not use discrete latent codes, and it does not use the autoencoding or latent prediction losses. As written, the paper seems to assume that (1) is the primary reason for the performance difference (\"[the transformer RobustFill model] can also be considered of an ablation of our LP model without latent codes]\"). However, I think these two factors need to be better disentangled, in order to determine which contributes most to the performance. Can a RobustFill model be trained with an additional auto-encoding loss, so that its loss function is more analogous to LP? Similarly, how might a continuous latent variable model, such as a VAE, perform on the string editing tasks?\n\nSimilarly, it seems there is evidence that (3) is an important factor: in Figure 5, when doing a beam search of size 10, but only searching in the decoder space and keeping the latents fixed (L=1), the performance seems identical to the transformer RobustFill baseline. LP seems to beat baselines with B=1. What are the results for B=100 and L=1?\n\nI think that disentangling these factors would really strengthen the paper, and could also be of large value to the neural program synthesis community.\n\nSummary:\n\nI think this is an interesting line of work with promising results. However, I do think that a baseline which uses an autoencoding loss but does not use discrete latent codes is an important ablation to perform. I therefore recommend a weak accept, and I'd be willing to raise my score if my concerns about baselines were addressed.", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Meta-review: The paper tackles program synthesis using a discrete latent code
approach, enabling two-level beam search decoding. The approach is well
motivated, as program synthesis requires high-level choices that affect long
subsequences of the output, and discrete codes are amenable to heuristic search.
Empirical results show improvements over methods with no latent
variables and methods with continuous latent variables. However, the review process reveals that some of the claims made about the nature and necessity of the discrete latent codes is not sufficiently justified by the current analysis. With borderline assessments in a very competitive venue, *I cannot recommend acceptance*. I would like to encourage the authors to pursue this direction further, shedding more light on the nature of the latent representations learned as an interpretable planning mechanism.

The discussion was rich and surfaced a lot of concerns and issues with
the paper, that I strongly encourage the authors to take into account.  After
the author responses and internal discussion, many initial concerns
were settled, but some remain. The two main concerns raised are: (1) that the
paper makes overly ambitious claims about high-level planning which is not
backed by an analysis of the latent codes themselves, and (2) that the
improvement may be due to increased generation diversity (which could be
possible in continuous LV models too) rather than meaningful
high-level planning. I believe that after clarifying such remaining loose ends, 
this work would be of great interest to both the field of program synthesis as well as the discrete
representation learning community.

Decision: Reject