Source-linked AI summary
LongCoder: A Long-Range Pre-trained Language Model for Code Completion
Daya Guo, Canwen Xu, Nan Duan, Jian Yin, Julian McAuley
TL;DR
LongCoder addresses the difficulty of code completion with long inputs, where standard attention becomes computationally expensive. It combines sliding-window attention with bridge and memory tokens to retain local and globally important code information, and it achieves superior completion performance with comparable inference resources. Its evaluation is limited by small model size, small-scale pretraining, and possible test-set overlap in large-scale pretrained models.
Problem
Long-context code completion remains challenging because standard Transformer attention grows quadratically with input length, despite longer context potentially improving completion.
Method
LongCoder combines sliding-window attention with bridge tokens for local aggregation and memory tokens for global access to imports and code definitions.
Results
LongCoder achieves superior performance on long and regular code completion with comparable computational resources.
Takeaways & Limitations
The approach supports using longer code context while retaining linear attention complexity and comparable inference efficiency.
Takeaways & Limitations
LongCoder is limited by its small model size and small-scale CodeSearchNet pretraining, leaving scaling sparse attention with more data open.
Abstract
from arXiv · showhide
In this paper, we introduce a new task for code completion that focuses on handling long code input and propose a sparse Transformer model, called LongCoder, to address this task. LongCoder employs a sliding window mechanism for self-attention and introduces two types of globally accessible tokens - bridge tokens and memory tokens - to improve performance and efficiency. Bridge tokens are inserted throughout the input sequence to aggregate local information and facilitate global interaction, while memory tokens are included to highlight important statements that may be invoked later and need to be memorized, such as package imports and definitions of classes, functions, or structures. We conduct experiments on a newly constructed dataset that contains longer code context and the publicly available CodeXGLUE benchmark. Experimental results demonstrate that LongCoder achieves superior performance on code completion tasks compared to previous models while maintaining comparable efficiency in terms of computational resources during inference. All the codes and data are available at https://github.com/microsoft/CodeBERT.
1. Introduction
LongCoder targets long-context code completion, where standard Transformer costs grow quadratically with input length. It combines sparse local attention with bridge and memory tokens, and reports superior performance with comparable computational costs.
- Long code context may improve completion accuracy and support file- or project-level applications, but standard Transformer computation grows quadratically with input length.
- LongCoder uses sliding-window self-attention with bridge and memory tokens to retain local information and access globally important code statements.Bridge tokens aggregate fixed-length local context, while memory tokens expose imports and class, function, or structure definitions globally.
- LCC contains code examples averaging 5× the length of existing datasets and evaluates models under longer-context conditions.
- The paper contributes a long-code benchmark and two sparse-attention types motivated by existing attention patterns and programming practice.
- LongCoder achieves superior performance on long and regular code completion with comparable computational resources.
2. Related Work
Prior code-completion systems include statistical methods and decoder-only pretrained Transformers, while long-context Transformers reduce attention costs through sparse patterns. LongCoder is positioned as a sparse Transformer for file-level context without comparable inference-resource growth.
- Earlier code-completion work used n-gram, probabilistic grammar, and decoder-only pretrained Transformer approaches.
- Large code models achieve strong code-generation performance, but expanding their context windows is impractical because attention complexity grows quadratically with input length.
- Fixed-length context extraction can omit important class and function definitions, while increasing the window length adds computational overhead.
- LongCoder differs by using the entire file-level code context while maintaining comparable inference computational efficiency.
- Long-range Transformer research reduces quadratic attention costs with sparse query-key patterns and local mechanisms such as dilated sliding windows.
3. Long Code Completion
Existing public benchmarks emphasize short code contexts even though real source files are often longer and contain more dependencies. The LCC benchmark addresses this gap with long Python, Java, and C# completion examples and per-line evaluation.
- Existing test contexts average 478 tokens for Python and 365 tokens for Java, whereas tokenized GitHub Python files average 2,090 tokens.
- 41% of Python files exceed 1,024 tokens and 24% exceed 2,048 tokens, highlighting the need to model longer code sequences.
- LCC is a long-code completion benchmark covering Python, Java, and C#, constructed from the github-code2 dataset.
- LCC construction removes highly similar or unparsable files and filters examples by tokenized code length to focus on long contexts.
- The benchmark samples 100k training examples and 10k development and test examples per programming language, with development and test contexts exceeding 512 code tokens.
- Performance is evaluated per line using Exact Match and Edit Similarity.
4. LongCoder
LongCoder combines linear-complexity sliding-window attention with bridge and memory mechanisms to model long code while retaining local and globally important information. Its attention patterns address local dependencies, long-range access, and globally scoped code elements.
- Overview: LongCoder reduces self-attention complexity from quadratic to linear using window, bridge, and global attention.The model combines three complementary attention types for long-code modeling.
- 4.1. Window Attention: Window attention restricts each token to a local window of size w, giving O(n × w) complexity and an N × w receptive field after N layers.This exploits the observation that code completion largely relies on local context.
- 4.2. Bridge Attention: Bridge tokens aggregate local code slices and let subsequent tokens access preceding information with at most two hops at O(m × n) ≈ O(n) complexity.They provide a learned representation of local code while enabling efficient long-range interaction.
- 4.3. Global Attention: Memory tokens expose globally scoped statements, including package imports and class or function definitions, that local windows may miss.LongCoder identifies these statements through code structure and injects them into attention as reusable global information.
- 4.3. Global Attention: Global attention has O(kn) ≈ O(n) complexity because the number of memory tokens k is much smaller than sequence length n.Unlike fixed-length extraction, it can reuse previously encoded hidden states.
5. Experiments
Experiments evaluate LongCoder against pretrained code-generation baselines on long-context LCC, shorter-context CodeXGLUE, and cross-file RepoBench settings. LongCoder improves completion quality while preserving comparable inference efficiency, with ablations and case studies supporting its sparse-attention design.
- Experimental Settings: LongCoder is evaluated against GPT-2, CodeGPT, UniXcoder, LongFormer, BigBird, and Codex on code-completion benchmarks.The evaluation reports parameters, inference memory, runtime, Exact Match, and Edit Similarity.
- Experimental Settings: LCC contains substantially longer contexts than CodeXGLUE, whose test inputs are about five times shorter and only partly require long-sequence modeling.LCC focuses on long code context, while CodeXGLUE provides Python and Java line-level completion datasets.
- Experimental Results: Sparse models outperform non-sparse models on LCC in Exact Match and Edit Similarity while maintaining similar inference speed.The sliding-window mechanism enlarges the receptive field without reducing inference efficiency in the reported comparison.
- Ablation Study: Removing memory tokens lowers average Exact Match by approximately 1%, while removing bridge tokens lowers average Edit Similarity by about 3%.Memory tokens support globally scoped identifiers, whereas bridge tokens help represent code-context semantics and patterns.
- Case Study: In Python and Java case studies, LongCoder and Codex-2048 produce correct completions by accessing imports or function definitions beyond a short context window.LongCoder achieves this through memory attention while retaining comparable inference resource efficiency.
6. Discussion
The discussion identifies limitations in LongCoder’s model scale and training data, and in the reliability of evaluation datasets because GitHub code may overlap with pretraining data. It also points to future extensions across multiple project files and new applications.
- Limitations: LongCoder is small and was pretrained on the small-scale CodeSearchNet corpus, so its scaling with more data remains untested.The authors could not train a model comparable to Codex because of resource constraints.
- Limitations: Evaluation reliability is constrained because existing datasets and LCC can share GitHub source code with pretraining data.This overlap may be especially consequential for models pretrained at larger scale.
- Limitations: Codex may have an advantage on GitHub-derived tests because it was trained on GitHub repositories that include most or all test data in several benchmarks.The authors describe this as evaluating Codex on its own input and call for clean datasets from private projects.
- Future Work: Future work could extend LongCoder across multiple project files for code completion and applications such as extracting package requirements, generating build files, and refactoring projects.The paper frames these as new research opportunities enabled by broader project-level context.