Non-autoregressive Model for Full-line Code Completion

To verify our conjecture of left-to-right is not always the optimal order for code completion, we conduct an experiment to analyze the impact of different generation orders. We employ standard auto-regressive Transformer architecture to perform full-line code completion using two reverse orders: left-to-right (Transformer-L2R) and right-to-left (Transformer-R2L). Table 1 presents the results. For most of the cases, the performances of the L2R model and R2L model are comparable. For Python language, 2.65% and 2.47% of programs can only be correctly generated by L2R and R2L, respectively; 6.57% and 7.21% of the programs can only be approximately generated (edit similarity >50%) by L2R and R2L, respectively. For Java programs, we can also get similar results. Therefore, we conclude that left-to-right is not always the optimal order for code completion. Thus generating code in parallel (non-autoregressively) could be a better choice.

In this section, we measure the quantitative dependency among the generated tokens by attention density and compare the dependency among code tokens against that among natural language tokens (in NMT tasks). NMT task is selected for comparison because NAR models have been successfully applied to it.

To characterize and quantify the target-token dependency, inspired by Ren et al. (2020), we build Dependency-Analysis-Model (DAM) to measure the dependency among target tokens using the ratio of the attention weights on target context over that on full (both source and target) context when predicting a target token, where a bigger ratio indicates a larger dependency among target tokens. Specifically, we use masked language modeling task (Devlin et al., 2019) to train DAM. We employ mix-attention (He et al., 2018) to calculate the attention weights, where source tokens can only attend to source tokens with self-attention and target tokens can attend to all source and target tokens with mix-attention. During training, we randomly mask the tokens on the target side, and the model is trained to predict the original value of these tokens. After the model has been trained, we can measure the target token dependency based on the ratio of attention weights $\alpha_{i}$ on target context over that on full context when predicting a specific target token $y_{i}$, which is defined as:

We conclude based on the preceding analysis that it is potentially practical to predict code tokens in parallel.

In this section, we present our model SANAR in detail. We build SANAR to perform full-line code completion in parallel, which uses conditional independent factorization for the target tokens. Specifically, given the contextual code sequence $X=\{x_{1},x_{2},...,x_{m}\}$, the non-autoregressive full-line code completion task is to predict a sequence of tokens $Y=\{y_{1},y_{2},...,y_{n}\}$ that form a complete statement in a non-autoregressive way:

Figure 2 shows the architecture and the trainig procedure of our model. SANAR adopts the encoder-decoder transformer architecture: a context encoder that does self-attention, and a generated-code decoder that has one set of attention heads over the encoder’s output and another set (self-attention) for the generated code. During the training procedure, we propose an adaptive syntax-aware sampling strategy, which enable SANAR to generate target code sequences in a single-pass during inference procedure by gradual training.

During training, SANAR adopts an adaptive Syntax-Aware Sampling (SAS) strategy to dynamically glance code snippets from the target sequence depending on its difficulty and the tokens’ syntax types, aiming to incorporate the explicit syntactic information of the program. To achieve the sampling strategy, SANAR performs decoding twice during training. As shown in Figure 2, the first decoding is performed in a fully-NAR way, where the input to the decoder $H=\{h_{1},h_{2},...,h_{n}\}$ are copied from the encoder output using soft-copy (Wei et al., 2019), which maps the encoder embeddings $S=\{s_{1},s_{2},...,s_{m}\}$ into target length $H=\{h_{1},h_{2},...,h_{n}\}$ depending on the distance relationship between the source position $i$ and the target position $j$. The initial predicted tokens $\hat{Y}$ are predicted as:

The training objective is to maximize the following:

Syntax-Aware Sampling (SAS) strategy is an important component of SANAR, which adaptively selects the positions of tokens from the target sequence depending on its difficulty and the syntax types of the tokens. The selected tokens can provide “correct” information from the ground-truth target, thus can reduce the burden of decoder to predict the rest non-selected tokens in the training phase. SAS samples more tokens for SANAR to glance at the beginning, and then reduces the sampling number gradually, which helps SANAR to learn, eventually, how to predict the whole line code snippet without seeing any ground truth tokens in one pass.

Formally, given the context code sequence $X$, its predicted token sentence $\hat{Y}$, the ground truth $Y$, and the token’s syntax type sequence of the target $T$, the goal of SAS strategy $\mathbb{SAS}(Y,\hat{Y},T)$ is to obtain a subset of tokens sampled from $Y$. Specifically, there are two steps:

To capture the syntactic information of the code during the sampling procedure, we present a Hybrid-Syntax-Guided (HSG) sampling strategy. Specifically, $1-p$ of the time, the sampling is performed randomly, where the tokens are randomly selected from the target sequence; and $p$ of the time, tokens are selected depending on their syntax-types¹¹1$p$ is a hyper-parameter to control the probability of syntax-guided sampling, the best setting is $p=30\%$, we randomly select $K\leq N/2$ keywords, $I\leq N/4$ identifiers, and $O\leq N/4$ operators from $Y$, where $K+I+O\leq N$²²2The number of these specific tokens might be not enough. The reason for introducing randomness (randomly sampling for $1-p$ of the time) in the sampling process is to enable SANAR to explore more interdependency among target tokens. Compared with the totally randomly sampling strategy in Qian et al. (2021), our Hybrid-Syntax-Guided sampling strategy can increase the probability of glancing the keyword, operators, and identifiers, which can help the SANAR capture the program’s syntactic and semantic information better.

Finally, we can obtain a subset of words sampled from $Y$:

As SANAR is well-tuned, it will adaptively reduce the percentage of sampling, making sure that the trained model could learn to generate the whole line of code in the single pass. Thus, the inference of SANAR is fully parallel with only a single pass.

In traditional left-to-right code completion, where the target sequence is predicted token by token, the length of the sequence can be determined by predicting a special EOS (end of sentence) token. However, for NAR-based generation where the entire sequence is predicted in parallel, the length of the target sequence must be determined in advance. To achieve this, we follow Ghazvininejad et al. (2019) to add an additional [LENGTH] token to the source input, and the encoder output for the [LENGTH] token is used to predict the length, formed as a max-target-length classification task. We use 1,000 as the max length. The loss is added to the cross-entropy loss from the target sequence.

We use the Python official library tokenizer³³3https://docs.python.org/3/library/tokenize.html and Javalang⁴⁴4https://github.com/c2nes/javalang to split Python and Java programs into lines of tokens, and extract their syntax types. Then we employ a sliding context window of 10-lines to create the data pairs, that is, the context code sequence contains 10-lines of code tokens, and the next line is considered as the target code sequence. The detailed information of the datasets is shown in Table 2.

The main results on Python and Java benchmarks are presented in Table 3 and 4. SANAR significantly improves the full-line code completion quality and outperforms all the baselines on all evaluation metrics. Especially, SANAR outperforms strong AR baseline (Transformer) by a large margin in BLEU. We can observe that the improvements on BLEU and Edit Similarity are more significant than the Exact Match accuracy. As a recommendation tool, code completion add-in serves as developers’ cooperator, and developers can accept to make a few edits to correct the recommended code. Besides, different code snippets can have identical functionality. For example, these two Python return statements have the same functionality: return True if a==0 else False and return False if a!=0 else True. Only evaluating the quality of the generated code by comparing the exact match with the ground truth is not convincing enough. Thus, BLEU and Edit Similarity which calculate the token overlapping and the minimum number of operations required to transform the predicted code sequence into the target sequence can evaluate the generated code more thoroughly. Thus, the significant improvements on BLEU and ES further demonstrate that SANAR can generate the code sequence which meets the developers’ expect more.

It is interesting to note that, most of the NAR models can achieve higher BLEU and ES scores than the AR-based Transformer model, and can achieve better or comparable EM accuracy on all the datasets. These results are quite different from NMT task, where the NAR models can achieve worse or comparable results with the AR model. The results further verify our assumptions in section 2, that is, the non-autoregressive manner can fit code completion better than NMT, and can boost the performance on both efficiency and quality for code completion.

For the inference latency, SANAR can significantly reduce the inference time within $5\sim 6\times$ speedup compared with the AR-based Transformer model. As a fully-NAR model, the inference speed of SANAR is also faster than the iterative-NAR CMLM model. Compared with NMT, the target sequence in full-line code completion is shorter, thus the overall speedup is not as large as in NMT, but is still significant. We also present the latency comparison for completing lines of $\geq 10$ tokens, which account for about 30% of the test set. The results are shown in Table 5. As SANAR can generate tokens in parallel, thus the latency will not be affected by the target lengths, and still keeps comparable with previous results. However, for AR models, as the number of generated tokens increases, the latency increases a lot, and SANAR can achieve $9\times$ speedup. Thus, when completing longer token sequences, the speedup of SANAR will be more significant.

Since Hindle et al. (2016) have shown that source code is highly repetitive and predictable, language models began to be used for source code modeling and code completion (Hindle et al., 2016; Tu et al., 2014; Hellendoorn and Devanbu, 2017; Li et al., 2018; Liu et al., 2020). Most of the LM-based code completion models perform next one token completion (Li et al., 2018; Liu et al., 2020). Wang et al. (2020) propose to use a Transformer-based LM to perform full-line code completion. In full-line code completion, instead of predicting the next single token, the model predicts a sequence of tokens that form a complete statement given a partially complete code context. The experimental results show that Transformer seq2seq architecture can outperform the LM decoder in Wang et al. (2020) with comparable number of parameters. Thus, we use Transformer seq2seq architecture as the AR baseline, and also employ seq2seq architecture for SANAR instead of only using a decoder as Wang et al. (2020). Guo et al. (2021) proposed GRAMMFORMER, a transformer-based grammar-guided code generation model that generates code sketches, i.e. sequences of code tokens with holes. As the generation target is different from our model, we did not compare with them.