Venue: ICLR 2022 Conference

Reviews:

final_score: rating: 8: accept, good paper
review_content: summary_of_the_paper: This paper presents a novel approach to complete code via sketches, i.e., the proposed model can opt to leave a "hole" in the prediction whenever it is highly uncertain about the output. The experiments provide convincing arguments on why it is worth to adopt Grammformer when the prediction accuracy in the generated code is the main priority.
main_review: I really enjoyed reading this paper, and I think the authors devised a very promising approach to overcome the fundamental limitations of left-to-right LMC. Additionally, the paper is very well-written, and the discussion of related work is exhaustive.

STRENGTHS:
- the motivation in Fig. 1 is crystal clear, as it highlights a fundamental limitation of left-to-right LMC on generative tasks. The provided context is not enough to make a reliable prediction of the identifier name, so the model seeks the user input. This is both an effective and elegant solution which I hope will be adopted by future AI-driven autocompleters.
- to my knowledge, Grammformer is the first grammar-guided model that can generate code around "holes" that are added to the sequence in order to skip tokens with high uncertainty
- the combination of RL and a novel metric (RegexAcc) to overcome the lack of supervised data

WEAKNESSES:
- my main concern is about the runtime performance. As the author states in 2.2 "Computational Cost", there is an additional computational cost compared to a standard transfomer encoder-decoder model. From my understanding (which should be stated explicitly in the text), the inference cost grows linearly with the length of the predicted sequence, thus making this approach possibly unsuitable for autocompletion in the IDE (as the latency would be unacceptable for the user).
Rather than leaving this exercise to the reader, the paper should report clearly what are the runtime performance tradeoffs of Grammformer vs other approaches (especially considering the fact that GitHub copilot is among the compared systems).

- to exacerbate the aforementioned issue, it is worth noticing that the accuracy improvement brought by Grammformer is not astounding (hence the performance tradeoff could be considered even more disadvantageous). On a similar note, the pre-trained only version of Grammformer performs almost as good as the full-fledged model, but with potentially a much lower computational cost.

MINOR ISSUES:
- CoPilot appears in several figures, but it is not referred at all in the text. Please fix accordingly.
- I can't understand the sentence "x is the 200 terminal tokens" on page 6. Please clarify.
summary_of_the_review: Grammformer is a thoughtful combination of novel contributions and familiar insights in the ML4code field.
While the runtime performance is unclear, the proposed approach can still deeply impact the future of LMC (especially for generative tasks), therefore I recommend this paper for appearing at ICLR in order to get the exposure it deserves.
review_title: null

final_score: rating: 5: marginally below the acceptance threshold
review_content: summary_of_the_paper: The problem of code completion is often hard because some intermediate strings might be difficult to predict while the nearby tokens might still be easy to predict. To exploit this observation, this paper presents Grammformer, a transformer-based model for generating code completions with "holes" inserted in places where the model is uncertain.
main_review: Strengths
------------ 
- Explores an interesting and potentially useful variant of code completion
- The evaluation shows that the proposed method outperforms simple baselines like the unmodified transformer.

Weaknesses
------------------
- The gain in performance over the standard transformer is small according to Table 1
- it is not clear how much computational overhead Grammformer adds over the standard transformer during inference. I could not find any experimental results showing the overhead.
- I also do not quite follow why metrics like ROUGE and REGEXACC are good fits for code completion tasks. The authors provide no evidence that these metrics derived from natural language tasks are meaningful for programming languages too.

Overall, I find the idea of sketch generation to be potentially useful. The authors described the proposed algorithm clearly. However, my main concern with this paper is that the empirical evidence demonstrating the quality/usefulness of the generated sketches (for programming language-related tasks) is rather thin. For example, what are the downstream tasks the authors envision the generated sketches to be useful for? If it is to help the developers by providing coding templates, it is not clear to me that ROGUE or REGEXACC are the right metrics to measure the usefulness of the sketches. I think an end-to-end evaluation of the usefulness of the sketches for a specific application would have been much more convincing. 


summary_of_the_review: Interesting idea and well-written paper. However, without end-to-end evaluation on specific tasks, it is hard for me to judge the usefulness of the generated code sketches.
review_title: null

final_score: rating: 6: marginally above the acceptance threshold
review_content: summary_of_the_paper: This work proposes, GRAMMAFORMER, a transformer model for generating code with "holes" inserted in places where a model is uncertain. GRAMMAFORMER is trained on code completion task for C# and Python. The model generates 10-50% more accurate completions and 37-50% longer sketches.
main_review: **Strengths**

* The problem is very relevant from usability perspective of code completion. If the model is uncertain about certain code fragments, it makes sense to seek input from the user. The paper has nicely motivated the problem with a good example in Fig. 1.

* The idea of generating program sketches has been explored in literature in different contexts. ([2, 3] already mentioned in the paper. Also see[1]). However, to my knowledge, this is the first work where sketch generation is used in the context of code completion to prevent generation of code with low certainty.

* The formulation is interesting and quite different from the way language models are usually used to generate code. Instead of directly generating the code, language models are used to expand a non-terminal in the code. A separate model built to identify the non-terminal to expand. RL is employed as it is difficult to generate supervised data for this setting.

* The paper introduces REGEXACC measure. This is quite strict measure as its value of zero for all the sketches that can not be expanded to the ground truth. This measure can however be used in conjunction with other measures (as done in this paper).

**Weaknesses/Suggestions/Questions**

* Has other measures apart from ROUGE been considered for evaluating the sketch? There are several other measures that have been used to approximate the notion of program equivalence. (e.g. [1] uses Jaccard distance and various AST based measures). It would be nice to discuss these measures and contrast them with ROUGE and REGEXACC.

* Section 2.2 says, "simple extended sequence model from above do not perform well ...hole tokens would not replace semantically meaningful subsequences" This is a bit surprising considering the success of language models in generating grammatically correct sentences. The pretraining as described in the paper replaces AST non-terminals of target output by holes. The poor performance can be due to lack of sufficient data though.

* pg 4. "P_e is not directly constrained to follow the production rules." I am wondering why you didn't choose to train a probability distribution over the grammar rules. This will improve the results since the model will always generate syntactically correct programs. Is it for handling non-terminals like strings literals? (Could you possibly use a language model only for expanding non-terminals like String Literals.)

* Fig 1 has a row for CoPilot, but the it is not discussed in the main paper.

* "Evaluation > Baselines" says "we consider two transformer baselines ...". However, the Table 1 as well as the Fig. 4  have three transformer based baselines. "L -> R with holes" is not described in the paper. The "result" paragraph also talks only about "L -> R with stop policy". It would be nice to summarize all the baselines at one place. 

* GRAMMAFORMER improves only marginally over GRAMMAFORMER (pre-trained only). This makes me wonder if it is worth brining in RL. I would like the authors to comment on this.

* [1] Murali, Vijayaraghavan, et al. "Neural Sketch Learning for Conditional Program Generation." International Conference on Learning Representations. 2018.
* [2] Li Dong and Mirella Lapata. Coarse-to-fine decoding for neural semantic parsing. In Proceedings of the 56th Annual Meeting of the Association for Computational Linguistics (ACL), 2018.
* [3] Nye, M., Hewitt, L., Tenenbaum, J., and Solar-Lezama, A. Learning to infer program sketches. In International Conference on Machine Learning, pp. 4861–4870, 2019.
summary_of_the_review: This work brings in the several techniques (Grammar based program synthesis, Language models over partial programs, separate model for non-terminal selection, etc ) to solve the problem of code completion with sketches. I would rate the paper medium on novelty as many of these techniques have been already explored in the literature in different contexts. However, to me, the important contribution of this paper is the problem setting. In my opinion, Keeping placeholders in place of low-probability program fragments can improve the utility of code completion tools to a great extent.
review_title: null

final_score: rating: 8: accept, good paper
review_content: summary_of_the_paper: The paper presents a new model for code completion which allows the model to completions with “holes” that are inserted in places where the model is uncertain. The idea of generating “holes” to enable skipping over “hard parts” of the prediction is novel and interesting. To realize this idea, the authors present a model that generates partial syntax trees where some of the non-terminals may be left without further expansion. 
The model is evaluated on C# and Python programs and is shown to outperform existing techniques. The also paper presents a thorough ablation study.

main_review: All three contributions of this paper are strong and interesting:
Grammformer - a model that can predict code but has the escape hatch of predicting a “hole token” whenever it is uncertain. 
RegexAcc - a metric for evaluating the fit of predictions with holes. This is an important metric for the evaluation of code completion techniques in general. It is definitely not perfect, even for this task, but it is an interesting perspective going beyond simply matching tokens. 
The evaluation shows that the approach outperforms existing techniques for code completion. It contains both quantitative and qualitative evaluation.

* You are using two separate models for non-terminal selection and non-terminal expansion but partially share their parameters, did you try it with completely separate models first? Can you report what was the impact of that? Is that even possible given that the pretraining scheme of P_s uses the weights from the shared encoder?

* In grammar flattening, can you comment on the avg/max depth of a tree before/after flattening? From table 4 it is hard to understand the magnitude of the flattening. Also, how important is this part in practice?

* In Table 2, the performance of L->R and Grammformer with no “stop expansion” is actually quite good, and generates avg length of 8.2 for the latter. I guess that because it does not use the P_s model, it can also run more efficiently? Isn’t that by itself a good practical compromise? 

* Can you share any data about the location of “holes” in generated examples? How often is the “hole” in the first parts of the sentence, and how often is it close to the end? I think it would be interesting to see the ability of Grammformer to recover from “early holes”.

* Is Grammformer with no “stop expansion” conceptually equivalent to AnyCodeGen by Alon et. al. (ICML 2020)? 

* Do you have any hypothesis on cases where the model is able to recover despite having holes early in the generation process? Does it require some “synch” symbol that breaks the sentence and allows the model to resynch with a sub-sentence distribution, as common in error recovery of parsers for example? Your qualitative evaluation seems to hint towards that, where generation after holes benefits from “synch” symbols such as “=” that break a statement. 

* If recovery after holes depends on some “synch” symbols being present, it is reasonable to assume that L->R with masking of holes (that you suggest as a baseline) would perform better. It would help if you can show some cases where L->R with holes is not able to recover but Grammformer recovers properly.

*  Are matches like the one in figure 16 counted in “top k” match score? I guess they are, as there is 1 terminal present. How much of the overall Grammformer score is obtained with trivial expansions as in Figure 16? What happens if you exclude this kind of trivial expansion from being counted?

* Inference with this model seems rather expensive. Can you share some data on the inference times of the different models used in the paper? 

Minor:
Table 4 was rather hard to find in the appendix 

Some missing related work: 
* Rabinovich, M., Stern, M., and Klein, D. Abstract syntax networks for code generation and semantic parsing, ACL 2017
* Brockschmidt et al., Generative Code Modeling with Graphs, ICLR 2019
* Amodio et al., Neural attribute machines for program generation, 2017
* Murali et al., Neural sketch learning for conditional program generation, ICLR 2018
* Chen et al., Tree-to-tree neural networks for program translation, NeurIPS 2018

summary_of_the_review: The paper presents an original approach to code completion which allows to predict “holes” where the model is not certain about the prediction and keep prediction going after the “hole”. Training a model that is able to generate completions past “hole tokens” is challenging, and the authors present an elegant and clever technique for doing that, based on reinforcement learning.
Overall, a nice original idea and nice execution. I think this paper should be accepted.
review_title: null

Meta-review: The paper proposes a transformer model of code that leaves "holes" at points of generation at which the model is uncertain. The model is evaluated on C# and Python programs and outperforms existing techniques. 

The reviewers found the Grammformer model and the RegexAcc evaluation metric to be useful and interesting. The experimental results are also compelling. Given this, I recommend acceptance. Please make sure to incorporate the feedback in the reviews and the additional experimental results into the final version.
Decision: Accept (Poster)