Structural Language Models of Code

Uri Alon, Roy Sadaka, Omer Levy, Eran YahavICML 2020 · OpenReview

TL;DR

Researchers have developed a new approach to "any-code completion" called Structural Language Modeling (SLM). By treating code as a tree structure rather than a flat sequence of text and predicting the next node based on all available paths in that tree, SLM achieves state-of-the-art accuracy in generating unrestricted, complex code snippets in Java and C#.

What Problem Does This Paper Address?

Most of us are familiar with "autocomplete" for text, but code completion is a much harder beast. Traditional approaches usually fall into two camps:

  1. Restricted Completion: These models can only predict simple things, like primitive types (int, string) or a limited set of library calls, often ignoring user-defined functions.
  2. Neural Machine Translation (NMT): These treat code like a natural language (e.g., English to French), using an encoder to read the context and a decoder to write the code. However, code isn't just a sequence of words; it has a strict, nested mathematical structure.
Examples of any-code completion in Java and C# showing SLM's top predictions.

The authors introduce the task of any-code completion: generating any missing piece of source code in a general-purpose program without restrictions on vocabulary or structure. The challenge is reasoning over an unbounded number of possible syntactic structures and user-defined names.

Methods

The core innovation is Structural Language Modeling (SLM). Instead of modeling code as a sequence of tokens, SLM models the Abstract Syntax Tree (AST)—the tree structure that compilers use to understand code.

  • Tree Decomposition: The model breaks down the probability of a whole program into a product of conditional probabilities for each node in the AST, following a depth-first traversal.
  • Path-based Representation: To predict the next node, the model looks at the "context" by considering the set of all paths from every leaf (terminal) in the existing tree to the target node. This allows the model to capture long-range dependencies that a sequential model would miss.
SLM predicts the next node by considering paths from existing leaf nodes in the Abstract Syntax Tree.
  • Neural Architecture:
    • LSTMs encode individual paths.
  • A Transformer aggregates these multiple paths to create a global context.
  • A Syntactic Copy Mechanism allows the model to "copy-paste" variable names or identifiers from the surrounding code, which is essential since many variable names are unique to a specific project.
  • Joint Modeling: Unlike NMT models that use separate encoders and decoders, SLM treats the source and target as parts of the same tree. This "joint modeling" helps the model generalize better because the input and output share the same structural "DNA."

Datasets

The authors evaluated their model on two main benchmarks:

  1. Java-small: A dataset of 1.3 million methods from 11 GitHub projects, re-split to ensure no overlap between training and testing.
  2. C# Restricted Completion: A dataset specifically designed to compare against previous state-of-the-art models (like GNNs), focusing on expressions involving primitive types.

Key Insights and Ideas

  • Paths > Sequences: Representing code as a set of paths is more powerful than a flat sequence. For example, a path can directly link a variable's declaration to its usage, even if they are dozens of lines apart.
  • The Power of Joint Modeling: One of the most surprising findings was that using a single model for both context and generation (joint modeling) significantly outperformed the standard encoder-decoder setup. When the "source" and "target" are the same modality (code), separating them actually hurts performance.
  • Syntax Matters: The model uses a "tree@k" metric, which measures if the structure of the code is correct, even if the specific variable names are wrong. SLM excels here, showing that it truly understands the "grammar" of the programming language.

Key Results

SLM set a new bar for performance across the board:

  • Java Any-Code Completion: Achieved an exact-match accuracy@1 of 18.04%, outperforming the previous best (16.93%) and significantly beating standard Transformer-based NMT models.
  • C# Restricted Completion: Achieved 37.61% accuracy@1, nearly doubling the performance of the previous state-of-the-art Graph Neural Network (GNN) model (15.19%).
  • Ablation Study: Removing the copy mechanism caused a massive drop in accuracy (from 18% to 10%), proving that being able to "point" to existing variables is critical for real-world coding.

Limitations and Future Work

While SLM is a leap forward, it still makes "near-miss" errors—predicting the right structure but the wrong variable name (e.g., predicting value.length() > 0 instead of value.length() > 55).

The authors suggest two main paths for the future:

  1. Compiler Integration: Using a compiler to "post-filter" suggestions. If a suggested completion doesn't compile, the model should automatically move to the next best candidate.
  2. Better Identifier Prediction: Improving how the model chooses between similar-looking variable names in the context.

By moving from "code as text" to "code as structure," SLM provides a blueprint for more reliable and powerful AI programming assistants.

Summary updated

Abstract

We address the problem of any-code completion - generating a missing piece of source code in a given program without any restriction on the vocabulary or structure. We introduce a new approach to a...
BibTeX
@inproceedings{alon2020structural,
  author = {Uri Alon and Roy Sadaka and Omer Levy and Eran Yahav},
  title = {{Structural Language Models of Code}},
  booktitle = {International Conference on Machine Learning},
  year = {2020},
  url = {https://openreview.net/forum?id=3gaGC9ULcLT},
}
Figure