Learning to Complete Code with Sketches
Authors: Daya Guo
Alexey Svyatkovskiy
Jian Yin
Nan Duan
Marc Brockschmidt
Miltiadis Allamanis
Venue: ICLR 2022 Poster (2022)
Keywords: sketch
generative model
ml4code

Abstract: Code completion is usually cast as a language modelling problem, i.e., continuing an input in a left-to-right fashion. However, in practice, some parts of the completion (e.g., string literals) may be very hard to predict, whereas subsequent parts directly follow from the context.
To handle this, we instead consider the scenario of generating code completions with "holes" inserted in places where a model is uncertain. We develop Grammformer, a Transformer-based model that guides the code generation by the programming language grammar, and compare it to a variety of more standard sequence models.

We train the models on code completion for C# and Python given partial code context. To evaluate models, we consider both ROUGE as well as a new metric RegexAcc that measures success of generating completions matching long outputs with as few holes as possible.
In our experiments, Grammformer generates 10-50% more accurate completions compared to traditional generative models and 37-50% longer sketches compared to sketch-generating baselines trained with similar techniques.

Published as a conference paper at ICLR 2022
LEARNING TO COMPLETE CODE WITH SKETCHES
Daya Guo
Alexey Svyatkovskiy
School of Computer Science and Engineering Sun Yat-sen University, China
Microsoft
Redmond, WA, USA
guody5 sysu. edu.
alsvyatkemicrosofet
Jian Yin
Nan Duan
School of Computer Science and Engineering Sun Yat-sen University, China
Microsoft Research
Beijing, China
iss jy iemmmmaii 1. sysu. edu. cn
Mare Brockschmidt, Miltiadis Allamanis Microsoft Research
Cambridge, UK (mabrocks, mia lama) ) @mi crosoft.com
ABSTRACT
Code completion is usually cast as a language modelling problem, i.e., contin- uing input in a left-to-right fashion. However, in practice, some parts of the completion (e.g., string literals) may be very hard to predict, whereas subsequent parts directly follow from the context. To handle this, instead consider the scenario of generating code completions with "holes" inserted in places where a model is uncertain. We develop GRAMMFORMER, Transformer-base model that guides code generation by the programming language grammar, and compare it to variety of more standard sequence models.
We train the models code completion for C# and Python given partial code context. To evaluate models, we consider both ROUGE as well as new metric REGEXACC that measures success of generating completions matching long out- puts with as few holes as possible. In our experiments, GRAMMFORMER gener- ates 10-50% more accurate completions compared traditional generative mod- els and 37-50% longer sketches compared to sketch-generating baselines trained with similar techniques.
INTRODUCTION
Recent high-capacity language models (LM) have shown that machine learning models able generate coherent, realistic text, but it is often hard to guide them towards specific goal, especially when describing the intent is complex or more costly than manually generating the target output.
One such scenario are LMs of source code (LMC). Since Hindle et al. (2012) increasingly sophis- ticated LMCs have been built, including transformer-based ones, such those of [Svyatkovskiy
et al. (2020); Feng et al.] (2020); Chen et al. (2021) and various similar unpublished models such as TabNine and SourceAl These models generate full sequences of code tokens left-to-right with any prefix acting as the (partial) user intent. While LMs generate realistic-looking outputs, they are known occasionally "hallucinate" (Puduppully et al. 2019) Malmi et al.) 2019; Maynez et al. 2020 Liu et al., 2021), i.e. generate plausible but incorrect content. This particularly problematic in generating source code, where small mistakes can lead to erroneous code that is very hard to debug introduces vulnerabilities (Pearce al. 202T).
In this work, we investigate models that can decline to make predictions in places where there is high uncertainty (e.g., where the user should choose name), but continue generating around these "holes". For example, in.F Ileft) a developer has typed some code and is about to type the next line. A likely completion to consume more command line arguments, but their name is unclear

---

Published as a conference paper at ICLR 2022
Code Context:
Suggested Code Completions:
1 import sys
- R
target Larget.replee ("\", "/")
2 target sys.
L - R + - +
target
3 I
print (target) (No suggestion) sys argv
Ground-Trute
Copilot GRAMMFORMER
ID ars
Figure I:
sample snippet (left; abbreviated from Fig. 12 in Appx. Aj. A developer has just typed
the code and their cursor (in blue) is at line 3. Code completions provided by a number of models are shown on the right, where R a standard LMC and GRAMMFORMER our new model.
from the context. A traditional generative model (e.g. Fig. top right) may choose to provide a completion that exists in the training data, but is not clearly called for here. On the other hand, model able to explicitly mark where it is uncertain (Fi.. bottom right) makes it clear to a user where further input is required.
However, creating such models is not trivial. A simple first attempt may be to use standard LMC, but output "hole token" whenever the model is uncertain about the next output token. However, continuing after the then becomes infeasible, as the LMC was not trained on such data. Hence, a suitable training dataset and objective need to devised. As large datasets with holes exist, we instead choose to use a reinforcement learning approach in which our reward function encourages the model to make "long" predictions with as few tokens as possible, but to avoid making incorrect predictions. We found that standard left-to-right sequence models perform poorly on this task, Hence, we developed PEMMMFORRMRR model that construct suggestions by generating (partial) syntax tree, but which has the option of leaving non-terminals in its output.
Contributions (I) We present GRAMMFORMER, a transformer-based model that generates code based the programming language grammar and can predict hole tokens rather than output it is uncertain about. (2) We develop REGEXACC, a metric that evaluates the quality predictions with holes. (3) We evaluate GRAMMFORMER Python and C# code and show that GRAMMFORMER makes longer and more precise statement-level sketch completions compared to baselines.
2
METHOD
Our aim to predict code completions sketches, a mix of actual tokens and "holes" which are meant to signify that the model is unable to make a useful prediction within the given context and further user input required. Formally, we consider models that take a context sequence x of tokens as input and have to produce an output sequence y; intuitively, x is what the user typed so far, and y is the suggestion presented to the user. In our setting, y sketch, a mix of tokens from the programming language and the special token signifying "hole" that could be filled by an arbitrary sequence tokens. For example, t foo is sketch corresponding to assigning the return value of function foo to variable but leaves the arguments of the function call undetermined.
Metric A good sketch is that (a) can be completed into the correct output and (b) is precise as possible. To measure how successful a method is in doing so, we define new metric REGEXACC. For (a), all holes with the wildcard matching any non-empty sequence (*.+" +" Perl Compatible Regular Expression syntax). If the regex matches the ground truth, matches (t,") returns a score of otherwise it returns O. To implement (b), we scale this result by the proportion of terminal tokens predicted, by defining nTokens(()) as the function that returns the number of non-hole symbols in y. More formally, assume an output sketch ý and a ground-true sequence y" where does not contain any tokens. REGEX AcC then defined as
toRegex(ý) to turn predicted code sketch ý into regular expression by replacing
nTokens())
REGEXACC($, ("))) mmttches(toRegexx(... "Tooken(y"))
Beyond REGEXACC, we also consider ROUGE (Lin 2004). since a sketch can be thought as a form of "summary" of the target text. For this, we use helper function ERASEHOLES(ý) that simply
2

---

Published as a conference paper at ICLR 2022
200
(Expr)
(00 -33
209
r
[Expr)
(ParenthesizedExpp) (Expr)
x99
Expr)
((4
x9)
Expr)
Expr)
EXpr)
(00
X4)
I
Expr)
Expr) (Identifier)
(ArgList)
(4)
29)
r
Expr)
Expr) foo
AArgList)
(6) 10
Expr)
Expr) foo
(Identifer)
(
Expr)
Expr) foo
args
(77)
(deetifier)
[Eppr) foo
args
(88
(Expr) foo
args
(00)
Figure 2: Progress of grammar-based code generation of the sketch x
foo (args)) by GRAMMFORMER. Each line represents consecutive ( in Alg. Terminal
tokens are shown in monospace blue font. The underlined non-terminal at position (()) se-
lected by P. and its expansion is generated by Pe. Le. the output underneath the selected (under- lined) non-terminal. Fig. and Fig. i Appx. show real example generation sequences from our datasets.
drops all tokens, and then consider ROUGEpt (ERAsEHOLES(s), ROUGE is more lenient to errors than REGEXACC and gives partial credit to matching but plausible sketches.
2.1 LINEAR CODE SKETCH GENERATION
First, we consider the idea of generating code sketches using standard generative model for lan- guage. To this end, we simply extend the vocabulary with the special token. An obvious problem is that while have plenty of training data for standard generative model, we do not have training data for outputs y that contain the token. Consequently, we cannot train the model in fully supervised fashion, and instead turn to reinforcement learning. Concretely, we devise reward function r(.) that averages REGEXACC and ROUGE, i.e. for predicted output sketch ý and ground truth output (without tokens) y" * we define
r = [REGEXACC($,3 + ROUGE R (BRASEOOHHHHHSHHSS
(1)
Using the combination of ROUGE (which does not consider holes) and REGEXACC is crucial here, as ROUGE much "smoother" compared to REGEX ACC, which is 0 for all but very few predictions, allowing us measure partial improvement. We use our reward function from Eq. to evaluate the quality of the output of the full model and compute a loss. Inspired by Paullus et al. (2017) we use self-critical policy gradient training (Rennie et al. 2017) and for prediction y we minimise
((x,y") (r(ý.y") F(x)) Egen (x, y)
Here, F(x) is the reward achieved by the prediction from the snapshots of the model that achieved the best score so far and Eyen is the loss of the generative model. Intuitively, this objective rewards models that improve upon the previous best policy with respect to r.
To model this in practice, we use a standard encoder/decoder Transformer model Vaswani et al. (2017); Radford al. (2019), "translating" the context into the output y using separate encoder and decoder models. We additionally also consider the language modelling case, iee. a model that conditioned predicts token Yo, conditioned Yo predicts token y1, etc..
Pretraining In practice, we found that directly training a sequence model to maximise Eq. is very slow and does not converge useful model. Instead, we heuristically generate dataset suitable for supervised pretraining. We replace random AST non-terminals of the target output by and generate target sequences. These contain terminals and zero or more We then pretrain the model on this dataset to convergence, and then fine-tune it using the reward of Eq.
2.2 GRAMMAR-BASE CODE SKETCH GENERATION
In experiments, we found the simple extended sequence model from above to not perform well, in particular, tokens would not replace semantically meaningful subsequences (e.g. "szconv.
3

---

production rule of Published as a conference paper at ICLR 2022
Algorithm GRAMMFORMER generative process, given input sequence x
for t 0, 1, do
(0) P. (ilx() ))x
D sample non-terminal position from N(x to expand
( o then
D x() does not contain non-terminals or none was selected by P.
break
> stop generation
(n)
u x²) (()))
> sample expansion of non-terminal at position ((t)
0,19) Pa
(1+1)
(9)
(1)
create x ((+1)) by replacing non-terminal at ( by u (eg())
(e)
2000
return NONTERMINALSTOHOLEE
convert remaining non-terminals to holes and return
does not contain left parenthesis and requires the user fill it in.). To resolve this, we developed GRAMMFORMER a grammar-guided model. It generates code by following the structure of the context-free grammar (CFG) defining the programming language syntax, iteratively expanding non- terminal symbols. Crucially, it can choose to not expand some non-terminal symbols, which can then be presented as to users. In traditional grammar- based generation text (Cohen et al. 2012) or code (Maddison & Tarlow 2014 Yin & Neubig 2017 Allamanis & Sutton 2014 Bielik et al. 2016). the CFG is followed by sequentially expanding the left-most, bottom-most non-terminal symbol, using one of the production rules of the grammar. GRAMMFORMER changes this and instead selects the non-terminal symbol to expand, if any. An example generation is shown in Fig. 2
Probabilistic Model A CFG is defined as tuple (E, S, R)) where > is a set of terminal sym- bols. .N is set of non-terminal symbols, S E N is the root symbol and R is a set of production rules. We denote non-terminals (NonTerminalNNmme) GRAMMFORMER can be viewed a sequence- to-sequence model transforming x = Xo. X .... X,, into a new sequence in which one non-terne -on-mnain symbol z; has been replaced by a new sequence of new symbols, according the grammar. Examples of such sequences and rewrites are shown in Fig. 2
GR GRAMMFORMER does this rewriting in two steps. First, a non-terminal selector model Ps selects a non-terminal in x to expand and then the non-terminal expansion model Pe determines how to expand it. To define Ps. let (x) = {il x; E [NJ((O} denote the set of non-terminal positions in x and special "stop expansion" @ symbol. Conditioned on P. produces a probability distribution over (x). In turn, P. is conditioned on x and a position i E N(x) and models a probability distribution over expansion sequences u E (Σ N Note that factorising GRAMMFORMER into two models P3 and Pa is an important modelling decision: how to best expand a non-terminal is entirely separated from predicting whether hole should be introduced. These concepts are intermixed in standard (sequence) decoders. In practice, we define both models using neural architectures with partially shared parameters, as discussed below.
Alg. shows a high-level description of GRAMMFORMER, in which P. and Pa are used repeatedly to select and expand non-terminals (not necessarily the left-most one), until none are left or the P, indicates that expansion should stop. Here, SENTERMINALSTOHE non-terminal symbols with hole Note that GRAMMFORMER is not context-free free, taking into account the whole input sequence when expanding a non-terminal. Second, in contrast to many grammar-bass methods (Yin & Neubig, [017] Bielik et al.) 2016), any non-terminal can be ex- panded at each step. Finally, P. is not directly constrained to follow the production rule set R, but can generate any sequence. In practice, it learns to follow to the rules of R from the data, but this flexibility is important for handling string literals and argument tuples of variable length.
replaces all remaining
Neural Model To implement P. and Pa. we use a shared encoder module that computes rep-
resentation of the input sequence x = Xo....,X, as vectors cg.... Cy. C; E R,, where D is a hyperparameter. Our encoder module is Transformer (Vaswani et al., (017). given the impressive results of transformer-bee based models in NLP and code (Feng et al. [2020). Other architectures (RNNs, ID-CNNs, Transformer variants) would be suitable, but we leave their study for future work.
P. is implemented similar to a pointer network on top of this encoder module, i.e.
Pi x) softmax (f(e.))
iEN(x)
4

---

Published as a conference paper at ICLR 2022
where f is a learnable feed-forward neural network. For purposes, define Co the repre- sentation of the special start symbol [CLS] used in our Transformer encoder.
The expansion model P. follows standard autoregressive decoder formulation, i.e.
(u xx
1 (dec( |oo co.-..,, ,o....,,,,.. Ucj)-
We implement Paece as (causal) relational Transformer decoder, similar to Wang et al. (2019) Relational transformers augment the attention mechanism by incorporating predefined relationships among elements; attention scores are then biased by learnable weights for each relation. In GRAMM- FORMER, we only use a single relation, connecting each token to the expanded non-terminal token X;, to help the model focus on the token it needs to generate an expansion for.
Objective Due to the lack of supervised data, we employ reinforcement learning to train GRAMM- FORMER. We use our reward function from Eq. T to evaluate the quality of the output of the full model. We use self-critical policy gradient training as in Eq. and minimise
= -
Σ (-log log Ps (100 ()) 1(:00 0) log log Pa " xx(0) (0) ())) 2-0
Here, F(x) is the reward achieved by the snapshots P. and P. that achieved the best score so far. The rest of the objective follows the iterations of the loop in AAlA. I where is the iteration index, y is the predicted sketch, y" is the ground-truth sequence of terminals, and I(-) is the indicator function.
Pretraining As in the sequence model, directly training with the RL objective Eq. is computa- tionally intensive due to the sampling requirement. We again train P. to expand every non-terminal, independently of the expansion order learned by P.. To do this, use the input training examples and follow Alg. 1 but instead of sampling from P.(-),
pretraining strategy. First,
sample (*) from a uniform distribution over the non-terminals in x!") N(xx") = (i x; E N). This yields sequences of intermediate sketches (*) for each example. Furthermore, for each (")
we compute the ground-trufe -tuth expansion (u for all non-terminals E N((x(*)). We can then pretrain Pe using the supervised objective
frr,, (x"), (EN)))))
Σ llo Pe ((u )0 1 .)).
[N(((())
(x)(x)))
Lee the negative log- ligllike of the correct expansion for all non-terminals in x (1) This computa- tion more computationally efficient compared to the one in Eq. since the cost encoding (t) is amortised across all potential expansions and no sampling is required. Once Pe is pretrained, we pretrain P.. For this, we fix the weights of the shared encoder module, and optimise only the re- maining parameters of Ps through Eq. Once we have pretrained both models, we then fine-tune all model weights end-to-end, using Eq.
Optimisation: Grammar Flattening Following the formal grammar of a programming language commonly introduces tedious expansions. For example, the Python non-terminal (Call) always expanded to (Expr) ( (ArgumentListt), and the C# non-terminal (NotEqualOp) is always panded to the terminal !-. We "flatten" the grammar by replacing non-terminals such as (Call) and (NotEqualOp) with all their possible expansions. In Appx. C we provide the list of the flat- tened non-terminals. Note that if we repeated this process for all non-terminals except from the starting symbol S, GRAMMFORMER would degenerate into standard encoder-decoder model.
Beam Search At test time, we employ a two-step beam search, and replace sampling from P. and P. with their top-ı outputs, keeping beam of size k. First, for each x in the beam, compute P, and select the top-m non-terminal positions to expand. For each of those m positions, sample the top-n expansions from P. using standard beam search. We compute the likelihood of all l n m results, and then keep only the top-k. This process (detailed in im|Apx. E) is similar to standard beam search but takes into account that two submodels are used.
5

---

Published as a conference paper at ICLR 2022
Computational Cost GRAMMFORMER'S 's ability to predict sketches comes with additional com- putational cost compared to standard transformer encoder-decoders: at each iteration of the loop in Alg. (t) changes, P. and P. must be recomputed. This means that the encoder-decoder runs once on each partial sequence, in contrast to left-to-right causal generation, in which intermediate results can be re-used. Future work may consider selecting more than one element to expand from [(x (*) at each step, reducing the expansion steps, similar to Welleck et al. (2019); ) Stern et al. (2019).
EVALUATION
To empirically evaluate our model's ability to predict useful completions, we use REGEXACC and ROUGE. Note that we measure these on the generated sequence, i.e. we ignore the context tokens.
Datasets To collect a dataset, we clone all non-fork repositories with more than 20 stars on GitHub that have C# Python as their top language. Then, we deduplicate the corpus using the method of Allamaniss (019): Lopes et al. (2017). Finally, we parse all files into a syntax tree using Tree- sitter ignoring any files that cannot be parsed using the v0.19.0 grammar definitions. Finally, we To create eyraiitranning examples, i.e. inputs to Alg. 1 we search the syntax tree of each file and for each ( (SimpleStatement) non-terminal create an example. The syntax tree rooted at the (SimpleStatement) non-terminal is then used to get the ground-truth expansions during pre-training and the ground-trume expansion y". For our test set, randomly sample (SimpleStatement) non-terminal for each file to evaluate and obtain 318K (resp. 362K) examples for C# (resp. Python). For each example, x is the 200 terminal tokens before the (SimpleStatement) non-terminal. More details about the dataset can be found in Appx. B
split the files into 70-10-20 10-20 train- setn---aldaiionteeee
Baselines Since we are not aware of any prior model that targets code completion with sketches, setting using separate encoder and decoder models (Vaswani et al. [017] as well as the language modelling setting (where there is no distinction between encoder and decoder). We refer to these as "I. R" and "LM". We use "L R" to denote standard Transformer encoder-decoder model (Vaswani tasks. Additionally, we consider "L - R @" and
we consider two Transformer-base
baselines. We consider both the requence-to-sequees
jet al. 2017) used in sequence-to-sequene "LM + + which are trained to stop generation by inserting final token that captures any suffix. Note that this models can only generate sketches that are prefixes of the target completion, iee. corresponds to standard token-level generative model with a learnable stopping ability. To train this model, we use self-critical policy gradient training (as in Eq. 2).
Model Training We provide the training details for all experiments. Most of our models use a 6-layer Transformer as encoder and 6-layer Transformer as decoder, each with a hidden dimension of 768 and 12 attention heads, with the exception of the LM model (and variations), which uses a single 12-layer Transformer, to match the number of parameters of the other models. We set the intermediate dimension of each Transformer layer as 3072 and use 3 fully-connected layers with 3072, 768 and I hidden sizes as the feed-forward neural network in the selector model P.. The vocabulary is constructed using byte-pair encoding (Sennrich et al. 2015) and the vocabulary size is 25 000. We set max length of input and output sequences as 512 and 64, respectively. We train the model with Adam optimiser using a learning rate of 2e-5 and batch size 4 096. We used automatic mix precision. Training used 64 NVIDIA Tesla P100 with 16GB memory for 10 days. For beam search we use l = 5, n = 1 and m = oo, í.e. we consider all non-terminals in each (*) We selected these during early experiments as reasonable trade-off between speed and predictive performance.
Results Tbl. 1 shows the results for all considered models. For both Python and C#. GRAMM- FORMER outperforms the baseline methods in terms of REGEXACC, showing that the grammar- based generation can create better sketches compared to simpler methods. Note that although L R has a comparable or better ROUGE score, it does substantially worse than GRAMMFORMER with re- spect to REGEXACC, meaning that the predictions are "similar" but the sketches contain errors (i.e. do not match the ground-truth). This means that a code completion system suggested the full output of L + R, the user would have to pause and correct the suggestion more frequently. On the other hand, L + R + O improves over L + R in terms of REGEXACC but has a worse ROUGE and generates significantly shorter suggestions (5.3 vs. 7.5 tokens-long for C#). This is expected since

---

Published as a conference paper at ICLR 2022
Table I: Performance of GRAMMFORMER compared to basclines for Python and C#.
C#
Python
REGEXACC
ROUGE
Avg
REGEXACC
ROUGE
Avg
Top 1
Top 5
Len
Top
Top 5
Len
LM
0.42
0.52
75.7
8.0
0.18
0.24
$1.0
8.6
L R
0.42
0.47
77.0
7.1
0.17
0.20
53.2
5.8
LM
0,42
0.49
70.9
6.8
0.19
0.25
49.5
7.3
R
0.45
0.54
69.1
5.3
0.20
0,29
39.3
3,0
LM +
0.44
0.54
73.3
6.3
0,20
0.27
53.9
6.6
L R
0,45
0.55
73.5
5.8
0.18
0.22
48.9
4.7
GRAMMFORMER (pre-trained only)
0.45
0.57
77.0
7.2
0.20
0.29
50.2
5.7
GRAMMFORMER
0.47
0.59
77.4
7.5
0.21
0.30
51.6
6.1
20.0
Loft
20.0
with Stop Policy
15.0
Sketch leneth
15.0
12.5
12.5
10.0
7.5
7.5
5.0
0.0
8 10 12 14 181928
0.0
9 10 1211 15 1511//109220
Around-Rruth length
Ground-truth length
(a) C#
(b) Python
Figure 3: Sketch length vs. ground-truth length
- R S is trained to be more "conservative" (i.e. avoid incorrect suggestions) but is also unable introduce holes beyond the last generated token. Finally, we can see that while GRAMMFORMER already performs well after our pre-training procedure, we can further improve its performance with our fine-tuning technique. We believe that this is because when Pg and Pe are trained jointly, they co-adapt: some of the capacity of the shared encoder module that is used to make predictions for hard-to-expand non-terminals is "freed" since P, learns to not expand them.
Fig. shows how the length of the generated code sketch relates the length of the ground truth expression. While the differences between models are small for short target sequences, GRAMM- FORMER generates substantially longer suggestions than other models when more complex sugges- tions are required. In particular, the L - R + @ model generates very short suggestions, as is trained stop generation whenever it reaches a point which it uncertain about the token.
Fig. in turn shows how often the suggested sketch was correct dependent on the length of the ground truth token sequence. Here, - R+ @ does best because it generates the shortest (iee., least determined) predictions, which is exactly the trade-off captured by our REGEXACC metric. Of the models that generate longer suggestions, GRAMMFORMER clearly does best, with the improvement becoming more pronounced with the length of the target sequence. Note that the performance of the models on C# generally better compared the performance in Python. We believe that this has to do with the grammar of each language and the patterns it induces within the developer's is code. Casalnuovo et al. (2019); Karampatsis al. (2020) have observed similar phenomenon on the perplexity across (standard left-to-right) language models for different programming languages.
Ablations Next, we look into ablations of GRAMMFORMER and reason about how components perform. To this end, 2 shows the performance of different model variants the C# dataset. First, we analyse the effect the selector model P.. To this end, we consider two ablations. The first is the "random expansion" model, in which the non-terminal token to expand is sampled uniformly at random from the full set of non-terminal symbols, and which hence does not stop expansion as long any holes remaining. This is effectively GRAMMFORMER after pre-training procedure for P.. This model achieves the best ROUGE score, but relatively bad REGEXACC. as is forced generate prediction when it is very uncertain. The second ablation, "fixed threshold"

---

Published as a conference paper at ICLR 2022
1.0
Lock with Sisp Pulcy
LoA
Stp Pallyy
0.8
Lock with Holes
Grammrormme
0.8
Males Grammnfeemn
Accuracy
accuracy
0.6
0.6
0.4
0.4
0.2
0.0
9 1011 12 Ground-truth length
181920
0.0
2
8 10131223 1516 15161718198
Ground-trutie length
(a) C#
(b) Python
Figure 4: Percent Correct (i.e., matching) sketches (top-1 generated sketch) vs. ground-truth length
Table 2: Performance for GRAMMFORMER ablations (C#), for different P. and reward functions.
REGEXACC
ROUGE
Avg Length
Top
Top 5
GRAMMFORMER
0.47
0.59
77.4
7.5
Random expansion,
0.42
0.54
78.3
8.1
Random expansion, @ at fixed threshold
0.45
0.57
71.6
5.8
GRAMMFORMER, r(-) ROUGE GRAMMFORMER, r(-) = REGEXACC
0.42
0.54
78.2
8.1
0.51
0.62
70.8
5.8
R GRAMMFORMER, no O
0.42
0.47
77.0
0.42
0.55
78.1
8.2
model is similar to our first ablation, but stops expansion when the probability of the generated x falls below a threshold. We choose this threshold on the validation set. This model makes shorter, but more accurate sketch predictions compared to the "random expansion", ", but is worse than GRAMMFORMER. These two ablations demonstrate that our learned P, is useful.
Second, we consider the effect of using different reward functions r(.) in the training of GRAMM- FORMER. Concretely, whereas we use the mean of REGEXACC and ROUGE GRAMMFORMER, we now consider using only a single of these two metrics. As expected, the results on the correspond- ing metric improve, with a substantial cost in the other metric. Concretely, using only REGEXACC leads to significantly shorter predictions with a low ROUGE score. We believe that this is because REGEXACC is strict metric, returning the sketch does not match, which leads to sparse rewards and makes the resulting model more conservative at expanding non-terminals.
Finally, to evaluate the benefit of hrammar-guidee decoder, we consider a variant of GRAMM- FORMER that does not allow the introduction of and instead has continue expansion until no non-terminals exist anymore. This variant can be compared to L - R. which also cannot stop or introduce tokens. Our ablation shows that there is substantial benefit in using grammar-guided decoding, leading both to longer predictions as well as more correct ones.
3.1 QUALITATIVE EVALUATION
Having observed the quantitative results, we now turn our attention to a qualitative look at the results and show some cherry-picked examples that illustrate desired and undesired behaviours of GRAMMFORMER and the baselines, where we also include the suggestions of the GitHub Copilot
system GitHub (222)) Fig. shows example and eleven more are shown in Appx. A Fig. illustrates the importance generating sketches instead of concrete sequences of terminal tokens: oftentimes, the code context does not provide sufficient information about the user's intent. Sketch- generating models can offer more informative suggestions given the partial intent.
Of course, GRAMMFORMER also makes mistakes. For example, GRAMMFORMER and L R+ are sometimes "too" conservative (e.g. Fig. 15 15]in|Appx. A) generating holes where L generates fully concrete completions. This suggests future research opportunities for better calibration of P..
8

---

Published as a conference paper at ICLR 2022
Finally, a pure language modelling approach to code completion will always be insufficient. For example, user-defined types and rare APIs cannot be predicted by a language model, since" the APIs cannot be known during training (Fig. 7 and Fig. 17 in Appx. A). Researching methods to scalably introduce information from static analyses and additional context may alleviate this.
RELATED WORK
One of the successful applications of LMCs is code completion (Svyatkovskiy et al. 2019 Karam-
patsis et al. 2020). Transformer LMs have shown exceptional performance at the task being able
to predict relatively long code sequences (Svyatkovskiy et al. 20200 Chen et al. (2021). Grammar-
based code completion and generation has been researched with neural (Maddison Tarlow 2014]
Yin & Neubig 2017: Kim al., 2021) and non-neural models (Bielik et al.J (016)) always panding the left-most, bottom-most non-terminal. In contrast to GRAMMFORMERS, all these mod-
els target the generation of complete code without the ability create sketches. R3NN (Parisotto et al. 2017) generates only complete programs of a simple string transformation DSL but expands the non-terminal with the highest confidence, instead of the left-most, bottom-most most one, similar to GRAMMFORMER. In contrast to the aforementioned models, GRAMMFORMER does not maintain an explicit tree representation but instead uses the sequences of leaves the generation tree.
Sketch-like ideas appear in NLP such the coarse-to-fine semantic parsing of Dong & Lapata (2018) and chat-bots of [Shum et al. (209).. However, sketches are extracted deterministically to create a supervised dataset. Similarly, SketchAdapt (Nye et al.) 2019) uses a sequence model to generate sketches for small functional programs simple DSL towards speeding-up enumerative program synthesis from input-output examples. SketchAdapt is also trained as a supervised sketch generator. A supervised corpus is created by enumerating all possible sketches and selecting the one with the highest-probabliie and within heuristically computed time budget. In GRAMMFORMER domain, enumerating all sketches is computationally intractable due to the complexity of general- purpose programming languages while no similar heuristic exists for code completion.
Recently, sequence generation approaches beyond the left-to-right paradigm have been pro- posed (Welleck al.) 2019; Stern et al., 2019: Gu et al. 2019 Ford al.) 2018 Lee et al. 2018 Shah et al. 2018). usually by considering generation as an procedure that iteratively changes or extends sequence. These models often aim in speeding-up inference or allowing models to figure a better order for full sentence generation. However, since these models focus natural language and since its grammar not defined priori, these methods do not follow a grammar that limits the space for sketch generation. Additionally, these generate full utterances of text, rather than sketches.
related concept is learning abstain (Ziyin al. 2019) where a model learns to predict "don't 't know". This resembles the stop symbol 3 with the difference that GRAMMFORMER employs RL to learn Pa for sequential problem rather than learning to abstain for a single-step classification.
DISCUSSION & CONCLUSIONS
In this work, we presented GRAMMFORMER. a generative model of code that goes beyond standard left-to-right generation and is able generate sketches, i.e. snippets of code with holes. Design- ing generative machine learning models with such abilities is important towards facilitating better collaboration between machine learning models and their human users.
While we showed that GRAMMFORMER performs better than alternatives in sketch generation, there are still many research opportunities. First, larger transformers will most probably yield better results, as shown in the literature. Second, although we used REGEXACC as an evaluation metric, human studies to evaluate it are needed. Such studies, similar to those in machine translation and summarization, can yield more informed r(.) and improved user experiences. Second, although focused on programming languages, modelling natural language also seems possible. Finally, we treated programming languages as sequence of terminals and non-terminals, ignoring the structure imposed by code's semantics, e.g. data and control flow. Explicitly providing x x'the code 's structure, e.g. with relational transformers ( (Hellendoom al. 2019) may further improve GRAMMFORMER.

---

Published as a conference paper at ICLR 2022
ACKNOWLEDGMENTS
The authors would like to thank Alex Polozov for useful discussions. We also thank Patrick Fer- nandes, Szymon Malik, and Guilherme Ilunga for working on earlier modeling ideas on sketch generation. Although those were unsuccessful, they provided the inspiration for this work.
REFERENCES
Miltiadis Allamanis. The adverse effects code duplication in machine learning models of code. In Proceedings of the 2019 ACM SIGPLAN International Symposium New Ideas. New Paradigms, and Reflections on Programming and Software, pp. 143-153, 2019.
Miltiadis Allamanis and Charles Sutton. Mining idioms from source code. In Proceedings of the International Symposium on Foundations of Software Engineering (FSE), 2014.
Pavol Bielik, Veselin Raychev, and Martin Vechev. PHOG: Probabilistic model for code. In Pro- ceedings of the International Conference on Machine Learning (ICML), 2016.
Casey Casalnuovo, Kenji Sagae, and Prem Devanbu. Studying the difference between natural and programming language corpora. Empirical Software Engineering, 24(4):1823-186) 2019.
Mark Chen, Jerry Tworek, Heewoo Jun, Qiming Yuan, Henrique Ponde de Oliveira Pinto, Jared
Kaplan, Harrison Edwards, Yuri Burda, Nicholas Joseph, Greg Brockman, Alex Ray, Raul Puri, Gretchen Krueger, Michael Petrov, Heidy Khlaaf, Girish Sastry, Pamela Mishkin, Brooke Chan, Scott Gray, Nick Ryder, Mikhail Pavlov, Alethea Power, Lukasz Kaiser, Mohammad Bavarian, Clemens Winter, Philippe Tillet, Felipe Petroski Such, Dave Cummings, Matthias Plappert, Fo- tios Chantzis, Elizabeth Barnes, Ariel Herbert-Voss, William Hebgen Guss, Alex Nichol, Alex Paino. Nikolas Tezak, Jie Tang, Igor Babuschkin, Suchir Balaji, Shantanu Jain, William Saunders, Christopher Hesse, Andrew N. Carr, Jan Leike, Joshua Achiam, Vedant Misra, Evan Morikawa, Alec Radford, Matthew Knight, Miles Brundage, Mira Murati, Katie Mayer, Peter Welinder, Bob McGrew, Dario Amodei, Sam McCandlish, Ilya Sutskever, and Wojeiech Zaremba. Evaluating large language models trained on code. arXiv preprint urXiv:2107.088 107.03374. 2021.
Shay B Cohen, Karl Stratos, Michael Collins, Dean Foster, and Lyle Ungar. Spectral learning of latent-variable PCFGs. In Proceedings of the 50th Annual Meeting of the Association for Computational Linguisties (Volume Long Papers), pp. 223 231, 2012.
Li Dong and Mirella Lapata. Coarse-to-fie decoding for neural semantic parsing. arXiv preprint arXiv:1805.00 04793, 2018.
Zhangyin Feng, Daya Guo, Duyu Tang, Nan Duan, Xiaocheng Feng, Ming Gong, Linjun Shou, Bing Qin, Ting Liu, Daxin Jiang, al. CodeBERT: A pre-trained model for programming and natural languages. arXiv preprint arXiv:2002.08155, 2020.
Nicolas Ford, Daniel Duckworth, Mohammad Norouzi, and George E Dahl. The importance of generation order in language modeling. arXiv preprint arXiv: 079100 2018.
GitHub. Copilot - your ai pair programmer. http:::://oolloo.gitttoo
2021.
Jiatao Gu. Changhan Wang, and Jake Zhao.
Levenshtein transformer.
arXiv preprint
arXiv:190S.11000 2019.
Vincent J Hellendoom, Charles Sutton, Rishabh Singh, Petros Maniatis, and David Bieber. Global relational models of source code. In International conference on learning representations, 2019.
Abram Hindle, Earl T Barr, Zhendong Su, Mark Gabel, and Premkumar Devanbu. On the natu- ralness of software. In Proceedings of the International Conference Software Engineering (ICSE), 2012.
Rafael-Michael Karampatsis, Hlib Babii, Romain Robbes, Charles Sutton, and Andrea Janes. Big code!= big vocabulary: Open- vocabulary models for source code. In Proceedings of the Interna- fional Conference on Software Engineering (ICSE), 2020.
10

---

Published as a conference paper at ICLR 2022
Seohyun Kim, Jinman Zhao, Yuchi Tian, and Satish Chandra. Code prediction by feeding trees to transformers. In Proceedings of the International Conference on Software Engineering (ICSE), pp. 150-162. IEEE, 2021.
Jason Lee, Elman Mansimov, and Kyunghyun Cho. Deterministic aon-auuoreeressive neural quence modeling by iterative refinement. arXiv preprint arXiv:/882.06901, 2018.
Chin-Yews Lin. ROUGE: A package for automatic evaluation of summaries. In Text summarization branches out, pp. 74 71, 2004.
Tianyu Liu, Yizhe Zhang, Chris Brockett, Yi Mao, Zhifang Sui, Weizhu Chen, and Bill Dolan. A token-level reference- free hallucination detection benchmark for free-form text generation. arXiv preprint arXiv:2 087008704, 2021.
Cristina V Lopes, Petr Maj, Pedro Martins, Vaibhav Saini, Di Yang, Jakub Zitny, Hitesh Sajnani. and Jan Vitek. Déjävu: a map of code duplicates on github. Proceedings of the ACM on Programming Languages, ((0PSSLA)884, 2017.
Chris Maddison and Daniel Tarlow. Structured generative models of natural source code. In Pro- ceedings of the International Conference on Machine Learning (ICML), 2014.
Eric Malmi, Sebastian Krause, Sascha Rothe, Daniil Mirylenka, and Aliaksei Severyn. Encode, tag, realize: High-precision text editing. arXiv preprint arXiv: 1909, 0/ 187, 2019.
Joshua Maynez, Shashi Narayan, Bernd Bohnet, and Ryan McDonald. On faithfulness and factuality in abstractive summarization. arXiv preprint arXiv:2005.00661 2020.
Maxwell Nye, Luke Hewitt, Joshua Tenenbaum, and Armando Solar-Lezama. Learning to infer program sketches. In International Conference Machine Learning, pp. 4861 6871- PMLR, 2019.
Emilio Parisotto, Abdel-rahman Mohamed, Rishabh Singh, Lihong Li, Dengyong Zhou, and Push- meet Kohli. Neuro-symbolic program synthesis. In Proceedings of the International Conference on Learning Representations (ICLR), 2017.
Romain Paulus, Caiming Xiong, and Richard Socher. A deep reinforced model for abstractive summarization. arXiv preprint arXiv: 170500770 04304, 2017.
Hammond Pearce, Baleegh Ahmad, Benjamin Tan, Brendan Dolan-Gavin and Ramesh Karri. An empirical cybersecurity evaluation of github copilot's code contributions. arXiv preprint crXiv:2208.000 09293, 2021.
Ratish Puduppully, Li Dong, and Mirella Lapata. Data-to-text generation with content selection and planning. In Proceedings of the AAAI conference on artificial intelligence, volume 33, pp. 6908-6915, 2019.
Alec Radford, Jeff Wu, Rewon Child, David Luan, Dario Amodei, and Ilya Sutskever. Language models are unsupervised multitask learners. 2019.
Steven Rennie, Etienne Marcheret, Youssef Mrouch, Jerret Ross, and Vaibhava Goel. Self-critical sequence training for image captioning. In Proceedings of the IEEE Conference Computer Vision and Pattern Recognition, pp. 7008-7024, 2017.
Rico Sennrich, Barry Haddow, and Alexandra Birch. Neural machine translation of rare words with subword units. arXiv preprint arXiv: /00.::550000055 07909, 2015.
Harshil Shah, Bowen Zheng, and David Barber. Generating sentences using dynamic canvas. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 32, 2018.
Michael Shum, Stephan Zheng, Wojeiech Kryšcińskii, Caiming Xiong, and Richard Socher. Sketch- Fill-AR: A persona-grounded chit-chat generation framework. arXiv preprint /910. 2019.
Mitchell Stern, William Chan, Jamie Kiros, and Jakob Uszkoreit. Insertion transformer: Flexible sequence generation via insertion operations. arXiv preprint arXiv: arXiv: /902.032999 2019.
11

---

Published as a conference paper at ICLR 2022
Alexey Svyatkovskiy, Ying Zhao, Shengyu Fu, and Neel Sundaresan. Pythia: Al-assisted code com- pletion system. In Proceedings of the 25th ACM SIGKDD International Conference on Knowl- edge Discovery & Data Mining, pp. 2727-2735 2019.
Alexey Svyatkovskiy, Shao Kun Deng, Shengyu Fu, and Neel Sundaresan. IntelliCode Compose: Code generation using transformer. In Proceedings of the 28th ACM Joint Meeting on European Software Engineering Conference and Symposium the Foundations of Software Engineering, pp. 1433-1443, 2020.
Ashish Vaswani, Noam Shazeer, Niki Parmar, Jakob Uszkoreit, Llion Jones, Aidan N Gomez, Eukasz Kaiser, and Illia Polosukhin. Attention all you need. In Advances Neural Infor- mation Processing Systems, pp. 5998-6008, 2017.
Bailin Wang, Richard Shin, Xiaodong Liu, Oleksandr Polozov, and Matthew Richardson. RAT- SQL: Relation-aware schema encoding and linking for text-to-SQL parsers. arXiv preprint arXiv:1911.04992. 2019.
Sean Welleck, Kianté Brantley, Hal Daumé III, and Kyunghyun Cho. Non-monotonic sequential text generation. arXiv preprint arXiv: 2019.
Pengcheng Yin and Graham Neubig. A syntactic neural model for general-purpost code generation. 2017.
Liu Ziyin, Zhikang Wang, Paul Pu Liang, Ruslan Salakhutdinov, Louis-Philippe Morency, and Masahito Ueda. Deep gamblers: Learning to abstain with portfolio theory. arXiv preprint 197.00990,.00208, 2019.
12

---

Published as a conference paper at ICLR 2022
A GENERATED SAMPLES
Fig. 5 and Fig. 6jshow two examples from our dataset along with the ground-truti and the sequence of expansions performed by GRAMMFORMER, Fig. 7313 show example generations by GRAMM- FORMER and the baseline models I, R and T.
@. The parentheses red indicate the REGEXACC score for each suggestion. For the 1, - R @ baseline the special non-terminal <suffix> is added to indicate that a hole is introduced at the end of the left-to left-to-right generation. Finally Fig. 17 show example generations where GRAMMFORMER make mistakes, A discussion for each of those sample is found at the caption each figure.
Context:
using System. Coltemicollc
using "ystem.colllectionss.eeeeett
using UnityEngine;
public class BottleFlipAcadem:: A
public float MaxDistance;
public floatt MinScale;
public bool IsRandomDirection;
public override void AcademyReset())
MaxDistance resetParameters "
Ground Truth:
MinScale = reserPPrramtterrsmmmmi_ccsse
Prediction:
MinScale = restrfaranteerr(ttttrigggiittili
Generation Process:
poporession_statemeee
<left> bossignment_operatoon <right>
<left> = <right> ;
<identifier> <right> ;
cidentifier> = cexpression> [ <argument>>> ] ;
<identifier> <identifier> <argument> <argument>> ]
<identifier> = resetParameters [
<identifier> resetParameterss <string literal> ]
<string_literal
MinScale resetParameters Eetring_literaee
An example GRAMMFORMER generation for C#. Each line the generation process shows subsequent states of in Alg. 1] Here, GRAMMFORMER predicts sketch that matches the ground-truth expansion, but places hole at the key of the dictionary lookup, instead of predicting a low-likelihood string literal.
Figure 5:
B DATASET STATISTICS
Some statistics about the datasets used throughout this work are shown in Tbl. 3
C FLATTENED NON-TERMINALS
The non-terminals in Tbl. are always expanded and are not considered as non-terminals. Most of these non-terminals have always the same children (terminals non-terminals), representing a single CFG rule. By flattening those non-terminals the depth of tree reduced (and hence the number of loops needed in Alg.
13

---

Published as a conference paper at ICLR 2022
Context:
import sys
import
import platform
platform. system() "Linux":
os. system) clear')
elif platform.system. == "Windows":
"...ssteemmccss
target = sys. sys..rgase argv[1]
<expression_s sttsssettttettt>
Ground Truth:
ID sys.
Prediction:
<identifier> sys.argv[2]
Generation Process:
<left> <right>
<left> <subscript>
<left> = <value> [ <subscript> ]
<identifier> <value> [ <subscript>
<identifier> <attribute> <subscript> ]
<identifier> <object> <attribute> <subscript> ]
<identifier> <object>> <identifier>
[ <subscript>
<identifier> <object>> argv [ <subscript>
<identifier> <object> argv [ <integer>
<identifier> <object> argv [ 2 <identifier> cidentifier> argv 2
<identifier> sys argv [ 2
Figure 6: An example GRAMMFORMER generation for Python. Each line in the generation process shows subsequent states of x, in Alg. GRAMMFORMER here predicts that the user's intent is to read-in second argument and store it in variable. However, within the current context, the name of the variable storing the second argument would be impossible to predict. GRAMMFORMER- reasonably places hole at the given location and generates matching sketch. In this example, any traditional left-to-right model would need to first predict an accurate target variable name (which seems unlikely in the given context) before predicting the right-hand side of the assignment.
Python
C#
Num Training Files/Trees
1973400
1948516
Num Validation files/Trees
218398
216299
Num Test Files/Trees
460874
480166
Avg num tokens of x,
194.5
201.4
Median num tokens of X,
205
206
99 percentile num tokens of x,
250
260
Avg num tokens of Median num tokens of 99 percentile num tokens of y
1.9
1.9
Table 3: Statistics of the datasets used.
D UNDERSTANDING REGEXACC
Since REGEXACC is new metric, we include two deterministic ways of introducing sketches in Tbl. First, if all literals (strings, numeric) replaced with hole, we that high REGEXACC
14

---

Published as a conference paper at ICLR 2022
Context:
ExchangeActivity
(ExchangeActiviity)
CON_WEAL__TPPE.CON_WEEE BBEe:/CCCWWWELLLEEEEE EXCHANGE,
COM [rM_WEAL__TvVL COLL__TYE...CMM___
msg higg:sihgggaaasssteeeellcaaagree dwWlellID
if
exchangeActtivity != null {
(int) msg. msg www.sskkbbaaa.tteaaalaaeeeaeeeee http://assseelllllcccnneeeeee.se dubrawaw )
exxpressio__statemmett
Ground Truth: oxhhaggaccivuly..ppattvvwvw//
Prediction:
L- R:
(0.00) (0.000)
L L- R+ Singleton<<<sufii>> (0.000)
--
exchangenctivtty.ccooeeeC (); (0.833)
CoPilot:
} (0.000)
GrammFormer:
scchngeatiiityy.ceeenfffeee (); (0.833)
Figure 7: A C# example and completion outputs from different models. REGEXACC score re- ported in red. Here, GRAMMFORMER correctly identifies that method should be invoked on exchangeActivitty but does not predict the concrete method. If GRAMMFORMER was ex- tended with information from static analysis about the wwwcchnneActiviitt. (potentially user- defined type) then an accurate suggestion could have potential been made.
is achieved. In contrast, replacing both identifiers and literals (leaving "just" parentheses, brackets, dots, etc.) we get an easy "lower-bound". Note how C# which syntactically more verbose achieves a better score, compared to Python. In Tbl. 6 we show some example sketches and their associated REGEXACC score.
E
BEAM SEARCH
Alg. presents the beam search used in GRAMMFORMER.
15

---

Published as a conference paper at ICLR 2022
Context:
[Test] public void CanPassTwoProviders( {
// arrange
var expectedLength 198;
input1 Test5amm)eeProvddeer44411,, 50);
input2 TestSamp1aProvicer(44100) 2, 50);
var concatenator new (tt.:e/eenennsaaeeeeeeieeeeeeeee var buffer new float[2000];
input2]))
read concatenator (bafffrr,,,, 0, buffer.Length).
Assert.AreEqual (expectedLengthh, read, "read expectedlength");
Assert.AreEqual (49, b4ffer(49]);
Ground Truth: Assert.AreEqual(e, buffer(50]);
Prediction:
L R: Areeul..re buffer(50]); (0.000)
L - R Q: Assert. AsstttAArEquul (0.333)
- R Assert. CeeertAArctuuleeeeeccceeeeeett read); (0.00)
CoPilot:
A.sert.AreEualle buffer(50]); (0.000)
GrammFormer:
Assert. www.euuaaaaaaguuueaaaa buffer(5e]); (0.917)
Figure 8: A C# example and completion outputs from different models. REGEXACC score reported in red. Here, GRAMMFORMER correctly predicts that an AreEqual assert statement should be made, checking the value of buffer [50]. However, within this context, the correct concrete expected value (0) would be hard to predict, even for human. GRAMMFORMER places a hole there and generates a correct line-level sketch. In contrast, and L R + @ creates correct, but much shorter sketch.
R introduces a wrong completion
Algorithm 2 GRAMMFORMER beam search, given input sequence Xp-
{(x,, 0, false))
> Initialize Beam (state, logprob, isDone)
while 3(x,p, p, isnonee with isne false do generations
> While beam contains incomplete
)'-(0
for (x, p. Done)) E b do if isDone then
D For each sample in beam If suggestion complete
b'- b' u {(x, p. ioDe))
No operation, beam is complete
continue
for E TOPM(P, (i|x, N(x))) do
Get top-mn non-terminal positions
P, log P. (i|x, N(x)
i then
b' ((x. Ps. true))
> Stop Expansion
else
for y TOPN (P. (yl i)) do
Beam search y yields candidates
Pe - i.(y(x,
6' - : p P. + Pas false)}
> Expand x;
6- (b))))
> Prune Candidates and keep top
return b
16

---

Published as a conference paper at ICLR 2022
Context:
namespace S19664053.Pruebee
public class Dataí public int Miíget; set;}
public string M2{get; set;)
public Data(int m1, string m2) = m1; m2;}
[Databbject(true)] public class DataSource(
public Data[] Retrieve( )
Data[] data = new Data[10]; for (int 0; i<10; i++){
iiteessiionsstttmmntts
Ground Truth:
data[i] new Data(1, 1. Tostriinng)))
Prediction:
- R:
data[i] Data( ); (0.000)
O:
data[i] new Data( ) (0.000)
--RU
data[i] = new Data( ) (0.000)
CoPilot:
data[i] Data(i, "Data" 1); (0.000)
GrammFormer:
data[i] new Data(i, astring_literal.) (0.706)
Figure 9: A C# example and completion outputs from different models. REGEXACC in red. While all models predict that an assignment needs to be made to each dat [i], the exact form of the constructor is hard predict. GRAMMFORMER seems to be looking at the constructor definition and predicts that some (StringLiteral) needs to be used as the second argument, although is uncertain about its concrete form, hence introducing hole.
reported
17

---

Published as a conference paper at ICLR 2022
Context:
# Provides character-based width estimate when simple tags
# such as <b> and <i> are present in a multi-line,
# \"break("-delimited string. Very approximate, but useful # default.
def htmlwidth(sIIn):
iBr = index0fBr(sIIn)
if (-1 iBr):
$ sIn else:
sIn[: neetrn_sttatements
Ground Truth: return len(s)
Prediction:
L- R:
return len(s) (1.000)
R-R+0 Q:
return <suffix> (0.200)
R-RUP
return s (0.000)
CoPilot: s s.replace ") (0.000)
FrammFormer:
return len(s) (1.000)
Figure 10: A Python example and completion outputs from different models. REGEXACC score reported red. Here both and GRAMMFORMER predict the full line correctly, but L R + @ seems to return more conservative (but correct) sketch.
18

---

Published as a conference paper at ICLR 2022
Context:
#l/usr/bin/env python2
from future
import print_function
import argparse
import
import subprocess
import sys
ap argparse. ArgumentParrerr(
ap.add_argument _rggument""-rreeesss", action "store_ti "oure_
action = "store_true")
cexpression sttossiionsstttmettt
Ground Truth:
ap.add argument("--xxxerrientta action "store_true")
Prediction:
L R: args ap.parse_args() (0.000)
Q: args = ap.parse_args() (0.000)
L- RU:: args ap. ap.add (cholme (0.000)
CoPilot:
action "store_true") (0.000)
GrammFormer:
ap.add_argument argument(<stringg, action "store_ttuee) (0.833)
Figure 11: A Python example and completion outputs from different models. REGEXACC score reported in red. See main text in the introduction for a description.
Python block, tuple, and, or, +, /,
/1, 8, name, ==, /-, //=, @=, 6-, 14, call, unary_operaton * binary_operator, for_in_clause, truc, not_operator, none, false, booloan_sperator, augumentedL.sssiimment, awalt, >>, pair, I, parameters, <<, htw.:/maarryycopppeeseeeoo ellipsis, arguments, assignment, ".-
C#
block, tuple, and, +-, --, *-, /-, //-, 8-, 8-, 6-, -, **, >>, 1 <<, assignment_expressi.oom
6, 11. 1/, 3 0,
invocation_exprsse arguments, aaabbe__acccas_xxpeeseeoo
try_statement,, catch_clause, cond = array_type,
rank, base_ exse_sxpre,s,,n, initializer, niterll
himmberr_biddin__exeeesss.. >,
alement_access_expreese
subscript. ??,
this_expression, cast_expression, 15 66.
variable_declaratiion local
implicit_type, as,
as_expression,
bbal@eclaraiioosttttemnn
if_statement, default_eepressionn binary_expression, brackereed_argunnnt_llaa objett_creationneexrresssoo avait_expressionn,
throw_expression
pattern, is_pattern_eppression name,
Table 4: Non-terminals that are always expanded in the Tree-Sitter grammar for the two languages considered.
19

---

Published as a conference paper at ICLR 2022
Context: import sys import os import platform if platform. os. os. ossssseem("clear)
sesorrmmmsssemm)))mmm "Linux":
elif platform.systeme == "Windows":
system(ccc
target sys.
cexpression_ saiinn_tttttttttttee
Ground Truth:
ID sys.argv[2]
Prediction:
L - R: target target..eepaace""111 "/") (0.000)
L- + +: target <suffix> (0.000)
L-RUE: print(target) (0.000)
CoPilot: No Suggestion (0.000)
GrammFormer:
<identifier> argv]]] (0.875)
Figure 12: A Python example and completion outputs from different models. REGEX AcC score reported red. Generation steps of GRAMMFORMER shown Fig. 6) R and T, R + o cannot generate correct sketches since the first token would be impossible to guess within this code context.
C#
Python
Replace all literals with holes
0.865
0.608
Replace all literals and identifiers with holes
0.126
0.060
Table 5: REGEXACC when deterministically introducing holes at specific location.
Table 6: Example REGEXACC scores for variety of sketches.
Ground-truth
ap.add_argument (" ixpeeeeeemmmm action= "sttien"stoor__rruee
REGEXACC
ap. a_____argggnntt act Action="storo_true""
0.9
ap. aelaaddarrgueent
apd_ad_argument action=
0.8
0.6
ap.add_argument action="stte fioo=sstore_falsee
0.0
ap.add_argmmmnt requi red
0.0
20

---

Published as a conference paper at ICLR 2022
Context:
...
console. (Lgggeeg
log. ggg.additaddeercconssee
moving if os os..ath.isfile (arsslleeersscccoeeeeellll
contigs (scaffolds) misc dir
shutil.nove( mwweearggs.crreetteee args.assembled)
tmp_dir_foot fiir_for_com cor_rcectoor os.path.join fargs.output_dir, "mismatch__orrretoor, args.assembly
# correcting
filename os.path.join(tmp sirr_ddrfrrrrrrrree tar_rfooooocooooo "corrected_conte
<expression statteenntt
Ground Truth:
dst_configs os, path. hatt./oootttn_diffoooooooooe "configs")
Prediction:
L R:
coault_ccoreecedffasteet = os po.pett..odineerss.ouuuuu... sepreeced_ffata""s (0.000)
L R Desult_corracted_aats fasta <suffix> (0.800)
---UU sesult_corrected_r filenane chole> (8.000)
CoPilot: ts.path.isfileetmpppp. dir
cerrleettt__dd_ffo_oorreeettttt for_coreectorr: (0.000)
GrammFormer:
cidentifier> http://iiiittm_tii_foooorerreee <string>) (0.769)
Figure 13: A Python example and completion outputs from different models. REGEXACC score reported red. GRAMMFORMER completes the line creating a correct sketch with two holes at locations avoiding to make the mistakes that - R and L R makes.
Context:
...
left right = new Rect(0, 0, borde,,,, height); right.x
config, borderSize;
top botton new Rect(config, bordersize, 0, width-config, www.-coonii.bborrrrstteeee borderSize"2, border:)ord:))zze); botton.y height-config, borderieordes))ze;]
Color32 previoustolor;
public override OnGUI())
1f(Iprops.wron prrogss.rrnngattiossoooaaaa
return;
previousColor GUI.color;
GUI.color config. borderColo;:
GUI, Drawfextureeleft, config. texture::
GUI, www.Drrrtxxturrrightt config.texture))
<expression staieeentttttttttt
Ground Truth: GUI Du..DraTTeture(top, config.texture);
Prediction:
L R:
GUI.color previouscolor; (0.000)
1. R+ O: GUI.color previouscolor; (0.000)
1. RUm: GUI.color Color.white; (0.000)
CoPilot: GUI. D...Draatexturettop.
(1.000)
GrammFormer:
GUI. (botuttn texture); (0.000)
A C# example and incorrect completion outputs from different models. REGEXACC score reported in red. The prediction from GRAMMFORMER is almost right but should have created a hole at the first argument for the user to fill-in. This shows that improved methods for training the policy network may improve results in the future.
Figure 14:
21

---

Published as a conference paper at ICLR 2022
Context:
nanespace agplittticcoordeeffommanee
public class Progran(
public static Nain(string[] args)
try
string urlBase "http:///occahoot:5666777
threadCount 1;
var iterattonsPerThreedd 50;
if (args?.Length {
urlBase args[0];
threadCount int.Parse(args((1))
pntrression_satteennte
Ground Truth: sterationsPerThread i
Prediction:
L- R:
sterationsPerThread int.Parse(args(2)) (1.098)
iterationsPerThread (nt.Parse(args((1)) (1.898)
RUR
iterationsPerThreade int.Parse(argss())) (1.809)
CoPilot:
sterationsPerThread Int.Parse(args(()); (1.088)
FrummFormer: sterationsPerthread linteger_ (8.250)
Figure 15: A C# example and completion outputs from different models. REGEXACC score reported in red. GRAMMFORMER suggests correct sketch but the right-hand side of the assignment has to stop expansion since (IntegerLiteral) cannot generate int Parse (args [2]). ) This suggests some of the limitations that the grammar-bast baaeed generation of GRAMMFORMER may have, especially for shorter sequences.
Context: import multipracessing from import getenv bind "127.0.0.1:800
Ground Truth:
workers muttiprocessing.cpp.cmmm
Prediction:
> R:
workers (0.000)
- R-++G)
workers <suffix> (0.222)
workers (0.000)
CoPilot: workers multiprocessing.cuu.ccom cop_ccnnt)) (8.000)
GrammFormmr:
<identifier> <string> (0.111)
Figure 16: A Python example and completion outputs from different models. REGEXACC score reported in red. Although the sketch of the prediction from GRAMMFORMER is typically correct, not useful. Researching better evaluation metrics may improve GRAMMFORMER.
22

---

Published as a conference paper at ICLR 2022
Context:
import python modules
inport random
inport time
import osc
Connect to SuperCollider's internal port Exppressio__statement>>>>
Ground Truth:
OSCCCleee))
Prediction:
L-
osc. ConneceectCll)) (0.000)
csu.fuufi (0.800)
---
OSC.connect() (0.800)
Copilot:
client osc. osc.occclient() (0.000)
Grammformer:
conn OSC. connect() (0.900)
A Python example and completion outputs from different models. REGEX ACC score reported in red. All model fail to invoke the correct API of the library. A potential future direction to mitigate the problem is incorporate definitions of the external system classes.
Figure 17:
23


Reviews:
[{"review_id": "shjO2yD-kro", "reviewer": "Reviewer_suKF", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "**Strengths**\n\n* 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.\n\n* 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.\n\n* 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.\n\n* 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).\n\n**Weaknesses/Suggestions/Questions**\n\n* 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.\n\n* 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.\n\n* 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.)\n\n* Fig 1 has a row for CoPilot, but the it is not discussed in the main paper.\n\n* \"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. \n\n* 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.\n\n* [1] Murali, Vijayaraghavan, et al. \"Neural Sketch Learning for Conditional Program Generation.\" International Conference on Learning Representations. 2018.\n* [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.\n* [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_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.", "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.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "MhoTisT6CD", "reviewer": "Reviewer_Arrw", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "Strengths\n------------ \n- Explores an interesting and potentially useful variant of code completion\n- The evaluation shows that the proposed method outperforms simple baselines like the unmodified transformer.\n\nWeaknesses\n------------------\n- The gain in performance over the standard transformer is small according to Table 1\n- 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.\n- 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.\n\nOverall, 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. \n\n", "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.", "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. ", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "JzQ6kQQjF-_", "reviewer": "Reviewer_aRD4", "summary": "", "questions": "", "limitations": "", "rating": 8, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "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.\n\nSTRENGTHS:\n- 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.\n- 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\n- the combination of RL and a novel metric (RegexAcc) to overcome the lack of supervised data\n\nWEAKNESSES:\n- 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).\nRather 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).\n\n- 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.\n\nMINOR ISSUES:\n- CoPilot appears in several figures, but it is not referred at all in the text. Please fix accordingly.\n- I can't understand the sentence \"x is the 200 terminal tokens\" on page 6. Please clarify.", "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.", "summary_of_the_review": "Grammformer is a thoughtful combination of novel contributions and familiar insights in the ML4code field.\nWhile 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.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "GgHel11VrZ_", "reviewer": "Reviewer_Qkek", "summary": "", "questions": "", "limitations": "", "rating": 8, "confidence": 5, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "All three contributions of this paper are strong and interesting:\nGrammformer - a model that can predict code but has the escape hatch of predicting a “hole token” whenever it is uncertain. \nRegexAcc - 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. \nThe evaluation shows that the approach outperforms existing techniques for code completion. It contains both quantitative and qualitative evaluation.\n\n* 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?\n\n* 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?\n\n* 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? \n\n* 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”.\n\n* Is Grammformer with no “stop expansion” conceptually equivalent to AnyCodeGen by Alon et. al. (ICML 2020)? \n\n* 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. \n\n* 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.\n\n*  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?\n\n* Inference with this model seems rather expensive. Can you share some data on the inference times of the different models used in the paper? \n\nMinor:\nTable 4 was rather hard to find in the appendix \n\nSome missing related work: \n* Rabinovich, M., Stern, M., and Klein, D. Abstract syntax networks for code generation and semantic parsing, ACL 2017\n* Brockschmidt et al., Generative Code Modeling with Graphs, ICLR 2019\n* Amodio et al., Neural attribute machines for program generation, 2017\n* Murali et al., Neural sketch learning for conditional program generation, ICLR 2018\n* Chen et al., Tree-to-tree neural networks for program translation, NeurIPS 2018\n", "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. \nThe model is evaluated on C# and Python programs and is shown to outperform existing techniques. The also paper presents a thorough ablation study.\n", "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.\nOverall, a nice original idea and nice execution. I think this paper should be accepted. \n", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}]

Author rebuttal:

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)