PaperlayerView exact revision on arXiv

Source-linked AI summary

CodeFill: Multi-token Code Completion by Jointly Learning from Structure and Naming Sequences

Maliheh Izadi, Roberta Gismondi, Georgios Gousios

arXiv:2202.06689v1cs.SEcs.LG

TL;DR

Code completion systems can miss code context or structure, and ordinary masked-token evaluation does not reflect where developers request completions. CodeFill combines token names and types with token- and statement-level training, outperforming baselines across the reported tasks. Its authors identify validation on other programming languages as future work.

  • Problem

    Masked-token accuracy does not reflect that developers request completions at specific syntactic points, and code models may miss code structure and naming context.

    Source: §1 · pp. 1–2

  • Method

    CodeFill jointly learns from source-code token names and types using Transformer models trained for token-value, token-type, and multi-token statement prediction.

    Source: §1 · p. 2, §8 · p. 11

  • Results

    CodeFill outperforms all baselines across the reported scenarios, reaching 80.6% accuracy and 81.7% MRR in basic token prediction and over 70% accuracy for statements up to four tokens.

    Source: §8 · p. 11

  • Takeaways & Limitations

    The authors conclude that statement completion of up to four tokens is practical to offer as an IDE feature.

    Source: §8 · p. 11

    The evaluation uses Python datasets, and further studies are needed to validate and generalize the findings to other programming languages.

    Source: §7 · p. 11

Abstract

from arXiv · show

Code completion is an essential feature of IDEs, yet current autocompleters are restricted to either grammar-based or NLP-based single token completions. Both approaches have significant drawbacks: grammar-based autocompletion is restricted in dynamically-typed language environments, whereas NLP-based autocompleters struggle to understand the semantics of the programming language and the developer's code context. In this work, we present CodeFill, a language model for autocompletion that combines learned structure and naming information. Using a parallel Transformer architecture and multi-task learning, CodeFill consumes sequences of source code token names and their equivalent AST token types. Uniquely, CodeFill is trained both for single-token and multi-token (statement) prediction, which enables it to learn long-range dependencies among grammatical and naming elements. We train CodeFill on two datasets, consisting of 29M and 425M lines of code, respectively. To make the evaluation more realistic, we develop a method to automatically infer points in the source code at which completion matters. We compare CodeFill against four baselines and two state-of-the-art models, GPT-C and TravTrans+.CodeFill surpasses all baselines in single token prediction (MRR: 70.9% vs. 66.2% and 67.8%) and outperforms the state of the art for multi-token prediction (ROUGE-L: 63.7% vs. 52.4% and 59.2%, for n=4 tokens). We publicly release our source code and datasets.

1 INTRODUCTION

Rule-based completion can lack context and type information, while text-based models miss code structure and face open-ended identifier vocabularies. CodeFill combines token names and types, predicts tokens and statements, and outperforms competing approaches in the reported tasks.

1 INTRODUCTION

  • Rule-based suggestions can neglect code context, and dynamically typed languages provide less type information for accurate recommendations.Text-based learning models also miss code structure and face very large prediction spaces because developers invent identifier names.Source: §1 · p. 1
  • CodeFill jointly models token names and AST token types, and trains on both next-token and multi-token statement prediction.The approach uses Byte-Pair Encoding for names and re-ranks suggestions using context visible at the completion point.Source: §1 · p. 2
  • The evaluation compares CodeFill with four baselines and two state-of-the-art approaches across token- and statement-level tasks, including automatically identified syntactic completion points.The work also reports releasing its Python implementation and datasets.Source: §1 · p. 2
  • CodeFill outperforms all competing approaches across TPL-A, TPL-B, TPL-C, and TPL-D, achieving state-of-the-art MRRs of 81.7%, 87.2%, 69.5%, and 70.2%, versus TravTrans+ at 79.4%, 83.6%, 63.8%, and 66.2%, respectively.Source: §1 · p. 2
  • CodeFill obtains 70.2% on METEOR and 63.8% on ROUGE-L, significantly surpassing TravTrans+, which records 64.5% and 52.4% on the respective metrics.Source: §1 · p. 2

2 BACKGROUND AND RELATED WORK

This section reviews background work related to the approach and introduces autocompletion approaches, including the comparison baselines.

2 BACKGROUND AND RELATED WORK

  • The section reviews relevant background and autocompletion approaches, including the models used as baselines.Source: §2 · p. 2

2.1 Language Models and Transformers

The section introduces statistical and neural language modeling, then describes Transformers and GPT-2 as background for the paper’s approach.

2.1 Language Models and Transformers

  • A statistical language model predicts subsequent tokens from preceding context, and programming languages have learnable statistical properties.The passage distinguishes shorter contexts in simpler models from sentences or paragraphs in larger ones.Source: §2.1 · p. 2
  • Neural language models represent words as learned vectors, supporting generalization and scaling to code vocabularies with arbitrary identifiers.The passage contrasts this generalization with traditional statistical language models.Source: §2.1 · p. 2
  • Transformers use attention to focus on selective input parts; GPT-2 is a generative Transformer language model trained on eight million web pages.The passage notes Transformer performance improvements over RNNs and LSTMs across multiple NLP tasks.Source: §2.1 · p. 2
  • GPT-2 has been used for NLP and source-code analysis tasks.Source: §2.1 · p. 3

2.2 Multi-Task Learning

The section defines multi-task learning and distinguishes hard-parameter sharing from soft-parameter sharing and its training strategies.

2.2 Multi-Task Learning

  • Multi-task learning combines related tasks with a joint loss to maximize performance on one or more tasks.The passage describes knowledge transfer and generalization through domain-specific signals from related tasks.Source: §2.2 · p. 3
  • Hard-parameter sharing uses common hidden layers with task-specific output layers, whereas soft-parameter sharing keeps separate model parameters and regularizes their distance.Source: §2.2 · p. 3
  • Soft-parameter sharing can train tasks sequentially, one per training round, or alternatively, one task per epoch.Source: §2.2 · p. 3

2.3 Related Work

Autocompletion research has moved from heuristic and grammar-based systems toward statistical and neural models, while extending from single-token prediction to multi-token completion and multi-task learning.

2.3.1 Conventional Autocompletion.

  • Traditional autocompleters use rules, static types, similar code examples, or program history to suggest completions.Examples include type-checked names ordered alphabetically or by usage frequency.Source: §2.3.1 · p. 3

2.3.2 Statistical LMs and Grammar-based Models.

  • Statistical language models and grammar-based methods model source code with n-grams, caches, scopes, decision trees, or probabilistic grammars.These approaches capture locality and syntactic structure in different ways.Source: §2.3.2 · p. 3
  • Neural code models include pointer mixtures for OOV handling, open-vocabulary language models, and Transformers that incorporate syntactic structure.Li et al. [29] train separate type and token LSTMs; Karampatsis et al. [24] use BPE, beam search, and caching; Kim et al. [25] incorporate tree syntax.Source: §2.3.3 · p. 3

2.3.3 Deep Learning for Autocompletion.

  • Multi-token approaches include methods for completing statements, lines, or methods using intermediate representations, program analysis, GPT-2, or mined implementation patterns.Examples include PCC, AUTOSC [36], GPT-C [49], and FeaRS [54].Source: §2.3.4 · p. 3

2.3.4 Multi-token Autocompletion.

  • MTL autocompletion models combine token-type and token-value prediction or pre-train with code-understanding and code-generation objectives before fine-tuning.Liu et al. [32] use Transformer-XL and an RNN with AST-path encoders; Liu et al. [33] use hybrid pre-training and fine-tuning objectives.Source: §2.3.5 · p. 3

2.3.5 MTL for Autocompletion.

  • Real-world code distributions, statement-level generation, IDE deployment, and memory-speed-accuracy trade-offs are also examined in recent autocompletion work.Examples include internal-data training [7], IntelliCode Compose [49], and neural models evaluated for resource trade-offs [50].Source: §2.3.6 · p. 3

2.4 Baselines

The evaluation uses replicated recent models as baselines, adapting their output layers for statement-level prediction and retaining settings from their respective studies where available.

2.4 Baselines

  • Six recent models are included, using author-provided replication packages and reported parameters where available.For statement prediction, the baseline output layers were modified to continue through the end of a statement.Source: §2.4 · p. 3
  • N-gram plus LSTM combines an n-gram model and an LSTM, which its authors report outperformed their other models.Hellendoorn et al. argued that a well-engineered n-gram approach can outperform more complex neural models.Source: §2.4 · pp. 3–4
  • Pointer Mixture trains separate token-type and token-value models to address the out-of-vocabulary problem.Li et al. [29] also sought to incorporate structural information through the separate models.Source: §2.4 · p. 4
  • The T-XL plus Bi-LSTM baseline uses Transformer-XL and a Bi-LSTM for token and AST-path prediction in dynamically typed languages.The authors compare against the first of Liu et al.'s [32] [33] models because it most closely matches their setup.Source: §2.4 · p. 4
  • OpenVocab uses BPE to address OOV tokens but was included despite not being tuned for autocompletion.Karampatsis et al. [24] present it as a BPE-based language model.Source: §2.4 · p. 4
  • IntelliCode Compose is a GPT-2-based multilingual statement-completion system, while TravTrans+ is a Transformer model using AST paths.The study trains its own Python GPT-2 model because IntelliCode Compose source code is unavailable, and uses Kim et al.'s [25] best TravTrans+ model as the state-of-the-art baseline.Source: §2.4 · p. 4

3 APPROACH

CodeFill combines token names and AST token types in a multi-task Transformer pipeline, then re-ranks suggestions using visible scope. Its training spans token-level and statement-level completion.

3 APPROACH

  • CodeFill has preprocessing and training phases, with pre-training on token type, token name, and statement tasks and fine-tuning on name and statement completion.At evaluation, recommendations are re-ordered using token type and visible context.Source: §3 · p. 4

3.1 Pre-processing

  • Preprocessing converts source code into corresponding token-name and token-type sequences while preserving token values, types, line and position, and variable visibility.It removes comments and blank lines, extracts module and library aliases, and replaces their occurrences with type labels; literals are normalized and indentation is represented with special markers.Source: §3.1 · p. 4

3.2 Model Training

  • Training uses three GPT-2-based Transformers and soft-parameter sharing, with alternative task selection to reduce catastrophic forgetting.Pre-training minimizes among the TVP, TTP, and SC losses; fine-tuning uses TVP and SC because the limited type vocabulary is learned quickly.Source: §3.2 · p. 5

3.2.1 Token Value Prediction Task (TVP).

  • TVP predicts the next token value from left-side context using token-value sequences.The task is trained as masked unidirectional prediction within the multi-task framework.Source: §3.2.1 · p. 5

3.2.2 Token Type Prediction Task (TTP).

  • TTP predicts the next token type from corresponding token-type sequences, allowing type information to inform token-value prediction.It is trained jointly with TVP as left-to-right masked unidirectional prediction.Source: §3.2.2 · p. 5

3.2.3 Statement Completion Task (SC).

  • Statement completion generates token names until an end-of-statement marker, extending suggestions beyond the next token.A special EOS token marks the statement boundary; beam search uses width 5 as a balance of accuracy and speed.Source: §3.2.3 · p. 6, §3.2.4 · p. 6

3.3 Post-processing

  • Post-processing adjusts probabilities for the top ten predictions when an identifier is already visible, using its predicted type and declaration scope.The scope hierarchy is closest function, class, then file; the authors identify automatic learning of the re-ranking weights as future work.Source: §3.3 · pp. 6–7

4 EXPERIMENTAL SETUP

The experimental setup evaluates CodeFill on single-token and statement completion, using token-type, leaf-node, and likely-trigger-point tests alongside deduplicated Python datasets.

4.1 Evaluation Tasks

  • The evaluation covers token-level and statement-level prediction, with statement completion tested for next-n lengths from 2 to 8.The PY117K statement completions average 4.2 tokens (median 4; maximum 13).Source: §4.1 · p. 7, §4.1.1 · p. 7, §4.1.2 · p. 7

4.1.1 Token-Level Prediction.

  • Token-level tests include any-token prediction, AST token-type prediction, leaf-node prediction, and completions at likely autocompletion trigger points.Trigger points are inferred from punctuation and keywords using bigram frequencies, after filtering common, unpredictable, or impractical completions.Source: §4.1.1 · p. 7

4.1.2 Statement Level Prediction (SLP).

  • Statement-level prediction evaluates completion of the next n tokens, using METEOR and ROUGE-L.ROUGE-L scores longest common subsequences and reflects sentence-level word order.Source: §4.1.2 · pp. 7–8

4.2 Datasets

  • The datasets comprise ETH 150K Python and a CodeFill collection of non-forked Python repositories with more than 20 stars; deduplication produced disjoint PY117K and PY1690K sets.ETH 150K was collected from GitHub and filtered for duplicates, forks, parsing, AST size, obfuscation, and license conditions.Source: §4.2 · p. 8
  • CodeFill is evaluated on two Python datasets, with PY1690K for pre-training and a PY117K split for fine-tuning and evaluation.PY1690K and PY117K contain no common files.Source: §4.2 · p. 8

4.3 Implementation and Configuration

  • Implementation uses Python AST, Tokenize, and DIS libraries, with a learning rate of 0.00001, sequence length 2048, and 100 training epochs.Experiments ran on two GeForce GTX 1080 Ti GPUs with 128G RAM.Source: §4.3 · p. 8

5 RESULTS AND DISCUSSION

CodeFill outperforms competing models across the reported completion tasks. The results also indicate that multi-task training and statement completion contribute to performance, while Transformer model size constrains client deployment.

5.1.1 Any token prediction.

  • CodeFill outperforms all baselines across all metrics in any-token prediction.This task is included for comparison with prior work, though it does not account for prior probabilities of token types.Source: §5.1.1 · p. 8

5.1.2 Token Type Prediction.

  • CodeFill outperforms baselines on token-type prediction for both accuracy and MRR, except that its MRR is on par for keywords and punctuation.Transformer-based approaches predict keywords and punctuation effectively, while identifiers and literals are more challenging across models.Source: §5.1.2 · pp. 8–9, Table 4 · p. 9

5.1.3 Leaf Node Prediction.

  • CodeFill is the best model in accuracy and especially MRR for predicting AST leaf nodes, including function calls, variables, and attribute names.The authors report that name predictions are correct two out of three times and have greater than 70% probability of appearing in top suggestions.Source: Table 5 · p. 9, §5.1.3 · p. 9

5.1 Token-level Prediction (TLP)

5.2 Statement-Level Prediction (SLP)

  • CodeFill improves over all competitors on statement completion, with the margin widening as the number of required tokens increases, especially for ROUGE-L.More than 2 out of 3 statement completions of 4 or fewer tokens are reported correct.Source: §5.2 · p. 9, Figure 6 · p. 10

5.3 Ablation Study

  • Ablations indicate that multi-task learning, soft-parameter sharing, and adding statement completion each improve the model.The authors note that training time increases, but characterize it as a one-time cost that can be reduced with parallel training on multiple GPUs.Source: §5.3 · pp. 9–10, Table 7 · p. 10

5.4 Runtime Characteristics

  • All models have average latency below 100 milliseconds, but Transformer-based model sizes make them impractical to distribute to clients, requiring centralized deployment.CodeFill has more parameters than other baselines because of its architecture specification.Source: §5.4 · p. 10, Table 8 · p. 10

6 CONTRIBUTIONS AND IMPLICATIONS

CodeFill combines name-based and structural information for autocompletion, and its authors report that statement completion and a new structural representation improve recommendations. The paper also introduces evaluation tasks and a large Python dataset.

6 CONTRIBUTIONS AND IMPLICATIONS

  • CodeFill combines name-based sequencing with a structural representation designed to reflect how developers treat source code, and outperforms TravTrans+.Source: §6 · pp. 10–11
  • The authors report that statement completion improves the model, probably by helping it use completion context more effectively.Source: §6 · p. 11
  • The paper proposes cardinal-point and statement-completion evaluation tasks and shares a collected, preprocessed, deduplicated large Python dataset.Source: §6 · p. 11

7 THREATS TO THE VALIDITY

The evaluation faces threats from model parameters and possible baseline implementation errors, dataset quality and generalizability, and the suitability of the evaluation setting and metrics.

7 THREATS TO THE VALIDITY

  • Model performance may be affected by parameter choices and errors in baseline implementations, although the authors used the studies’ replication packages.Source: §7 · p. 11
  • Results are limited to two deduplicated datasets of open-source GitHub Python programs; further studies are needed to validate and generalize findings to other languages.The larger dataset contains approximately 1.7M program files, while the other is a frequently used benchmark.Source: §7 · p. 11
  • Evaluation validity depends on the setting and metrics: token prediction uses Accuracy and MRR, while statement prediction uses ROUGE-L and METEOR.The authors describe these metrics as used in prior literature.Source: §7 · p. 11

8 CONCLUSION AND FUTURE WORK

CodeFill combines token and type context in a Transformer trained on three programming-related tasks, and the authors report strong token-level and statement-completion results. They propose future work on domain-specific knowledge and statement-completion metrics.

8 CONCLUSION AND FUTURE WORK

  • Because code has more structure and a more well-defined grammar but a much larger vocabulary than natural language, NLP models and evaluations need adapting to source code.Source: §8 · p. 11
  • CodeFill jointly trains on next-token type, next-token value, and up to n next-token values using token and type context.The authors also propose cardinal-point prediction and statement-level multi-token prediction as evaluation tasks intended to better reflect practical autocompletion.Source: §8 · p. 11
  • Over 70% accuracy on statements of up to four tokens significantly improves on baselines, supporting statement completion as a practical IDE feature.Source: §8 · p. 11
  • Future work includes adding domain-specific knowledge, limiting context to better capture functions and nested scopes, and investigating statement completion with better metrics.Source: §8 · p. 11
Loading 2202.06689v1…