Venue: ICLR 2021 Conference

Reviews:

final_score: rating: 7: Good paper, accept
review_content: Edit: I have increased my score to 7.


This 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.

Strengths:

-The paper is relatively clear.

-The approach is novel.

-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).

-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.

Weaknesses:

I 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.

Unless 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?

Similarly, 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?

I think that disentangling these factors would really strengthen the paper, and could also be of large value to the neural program synthesis community.

Summary:

I 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.
review_title: Promising neural program synthesis approach. 

final_score: rating: 7: Good paper, accept
review_content: 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. 

Quality: The paper presents a novel program synthesis idea and the evaluation is promising and convincing.

Clarity: The writing provides enough background and explains the main idea in a very clear manner.

Originality: The application of Vector Quantized Variational Autoencoder for a two-level hierarchical synthesis is quite novel. 

Significance: This work shows that a promising hierarchical learning approach for program synthesis. Its effectiveness motivates many future explorations in this direction.
  

Questions: 

Q1: Why Python Code generation tasks use BLEU as the metric, rather than functional correctness?

Q2: Latent codes are motivated as a "high-level plan"? Do you observe certain interpretability of latent codes?

Q3: 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?

review_title: Interesting idea and convincing results

final_score: rating: 4: Ok but not good enough - rejection
review_content: 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. 

Experimental results show that the model outperforms three baseline systems on two tasks. 

---
I have major concerns on the nature of the VQ-VAE model. 


1) 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. 

However, 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?  

The current writing shows that this paper has a heavy development on the model, when in fact, it's mostly taken from previous work. 

2) The author claims that VQ-VAE serves as a discrete bottleneck. However, I strongly disagree with this. 

The decoder in this paper is well aware of the input by "TransformerDecoder(Y', E)" in Eq 4, where the E = TransformerEncoder(X). 

So, 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.

This is known as the "bypassing phenomenon" in previous work:

Bahuleyan et al., Variational attention for sequence-to-sequence models, 2018. 

The authors may want to explain why their VQ-VAE would not suffer from the bypassing phenomenon. 

Note: 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. 

3) 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. 

Note: 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. 

4) 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?

5) 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.

 
---

I also have major concerns on experiments.

6) 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? 

The BLEU is computed by the best BLEU score among the output beams, but increasing the beam size may not improve top-beam performance.

7) 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)?

In 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. 

---

Minor: 

The exponential moving average is not proposed in Roy et al. (2018). It's proposed in Appendix A of the original VQ-VAE paper. 

---

In short, the discrete latent space beam search appears to be some interesting idea. But I have concerns on the soundness of this paper. 

It is also noted that there's no code or output available. 



review_title: nature of VQ-VAE?

final_score: rating: 3: Clear rejection
review_content: ### Summary ###
The paper addresses the problem of program synthesis from examples, and also evaluates on program synthesis from natural language descriptions.
The 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.
The evaluation shows improved results over straightforward LSTM and Transformer baselines.

Overall, 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. 

### Strengths ###
+ The proposed approach is a first application of VQ-VAE to program synthesis.
+ The models outperforms LSTMs and Transformers

### Weaknesses ###
- The paper is very unclear and difficult to follow
- It is unclear **why** the approach works
- It is unclear whether this is a direct application of VQ-VAE to program synthesis, or is there any novel insight.
- The evaluation is lacking comparison to additional baselines and datasets.

**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.

The 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.
Only 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?). 

Additionally, 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?

**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.

**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.
For 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.

Another 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?
Further, is the focus the VQ-VAE really needed, or can a standard VAE work as well (or even an AE)?

**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?

* 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?
In NL->code, I am sure that there are other baselines other than Wei et al., 2019. For example:

1. Iyer et al., Mapping Language to Code in Programmatic Context, 2018
2. Iyer et al., Learning Programmatic Idioms for Scalable Semantic Parsing, 2019
3. Yin et al., "TRANX ..", 2018
4. Shin et al., "Program Synthesis and Semantic Parsing with Learned Code Idioms", 2019

and other semantic parsing papers.

* 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?
In the code generation task, aren't there any other datasets, with hopefully more than 11K examples?

* 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.

### Questions to Authors ###
1. How can two Transformers have only 15M parameters? What would happen if RobustFill-Transformer used a full-sized Transformer-base?
2. 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.
3. 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?
4. 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?

### Minor questions and comments ###
* Related work, paragraph2: "these works does not" -> "these works do not"
* It would help following if Figure 2 was in the same page that it is referenced
* 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.

====== Post discussion comments ======

After 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.

I 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.

My main concerns:

1. Is it possible that the 2-stage search simply increases the diversity of solutions? 
If 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.

Further, 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).

I 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.

2. 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.

If the authors claim that their approach allows "high-level planning", I would expect to see that it works across different models / tasks / datasets / settings.

Minor: I do not agree with the authors that this is self-supervised. I think that the paper uses the term "self-supervised" incorrectly.


review_title: Interesting paper, but very unclear and evaluation is lacking

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