Global Relational Models of Source Code

Vincent J. Hellendoorn, Charles Sutton, Rishabh Singh, Petros Maniatis, David Bieber

TL;DR

This paper bridges the gap between "local" graph-based models and "global" sequence-based models for source code representation. By introducing Graph Sandwiches and the GREAT transformer, the authors demonstrate that combining structural code information with global attention leads to state-of-the-art performance on program repair tasks, all while training faster and using fewer parameters.

The Problem: Local vs. Global Context

Source code is unique because it is simultaneously a linear sequence of tokens and a highly structured mathematical object (represented by Abstract Syntax Trees, data flow, and control flow).

Historically, researchers have chosen one of two paths to model code:

  1. Graph Neural Networks (GNNs): These excel at capturing structural relationships (e.g., "this variable is used here") but are inherently "local." They require many expensive "message-passing" steps to move information between distant parts of a program.
  2. Transformers/RNNs: These are "global." They can look at the entire file at once but treat code like plain text, ignoring the rich structural "hints" available in the compiler's representation.

The authors challenge this dichotomy, asking: Can we build a model that is both globally aware and structurally informed?

Proposed Methods

The authors propose two novel hybrid architectures to solve this problem:

  • Graph Sandwiches: These models alternate between different types of layers. For example, an RNN layer (global sequence flow) is followed by several GNN layers (structural message passing), and capped with another RNN layer. This "sandwich" allows information to zip across the file via the sequence layers and then refine itself through the code's actual logic via the graph layers.
  • GREAT (Graph Relational Embedding Attention Transformer): This is a modification of the standard Transformer. In a normal Transformer, the "attention" between two tokens is based only on their content and position. GREAT adds a relational bias to the attention mechanism. If two tokens are connected in the program graph (e.g., via a "data-flow" edge), the model is explicitly biased to pay more attention to that connection.
  • Leaves-Only Graphs: To make these models efficient, the authors propose a "leaves-only" graph representation. Instead of including every internal node of a complex syntax tree, they move all semantic edges (like control flow) down to the actual code tokens (the "leaves"). This makes the graphs 2–3x smaller and much faster to process.

Datasets

The models were evaluated on the VarMisuse task, which involves identifying and fixing the use of the wrong variable in a program.

  • Synthetic Dataset: Derived from the ETH Py150 dataset (GitHub Python code). It contains ~2M training samples and 755K test samples, where bugs were synthetically introduced by swapping variable names.
  • Real-World Bugs: A hand-curated set of 161 real variable misuse bugs (322 paired samples) mined from actual GitHub commits to test how the models handle "wild" code.

Key Insights

  • Structure is a powerful shortcut: Even a basic GNN outperformed the previous state-of-the-art sequence model by 20%. Explicitly telling the model how data flows is vastly superior to making the model guess.
  • The "Global" advantage: Pure GNNs struggle as functions get longer because they cannot easily "see" far enough. Hybrid models maintain high accuracy even on functions with 1,000+ tokens because the sequence/Transformer components provide a global "highway" for information.
  • Efficiency through Bias: GREAT achieves better results than pure Transformers because it doesn't have to "learn" the structure of code from scratch—the structure is baked into the attention mechanism. This allows it to reach higher accuracy with fewer parameters.

Key Results

Performance comparison of baseline models against proposed hybrid architectures
  • Accuracy Boost: The proposed hybrid models (GREAT and Sandwiches) improved upon a strong GNN baseline by an additional 10–15%.
  • Training Speed: The hybrid models trained significantly faster than pure GNNs. For instance, the RNN Sandwich reached peak performance in roughly half the time of a deep GGNN.
  • Generalization: On the "Real Bugs" dataset, the RNN Sandwich was the standout performer, achieving a precision of 28.6% at a much higher recall than standard models, proving that these hybrids aren't just memorizing synthetic patterns.
  • Parameter Efficiency: GREAT achieved state-of-the-art results using only 7.9M parameters, compared to the 12.6M required by the best Sandwich model.

Limitations and Future Work

  • Quadratic Complexity: While the "leaves-only" graph helps, the underlying Transformer architecture still faces quadratic scaling issues with very long sequences, which the authors mitigated with smaller batch sizes.
  • Task Specificity: The paper focuses heavily on the VarMisuse task. While this is a standard benchmark, future work is needed to see if these hybrid "Sandwiches" translate as effectively to code summarization, translation, or generation.
  • AST Nuance: By moving to a "leaves-only" representation, some fine-grained syntactic information contained in the internal nodes of the Abstract Syntax Tree might be lost, though the results suggest the trade-off is well worth it for efficiency.

Summary updated

Abstract

Models of code can learn distributed representations of a program's syntax and semantics to predict many non-trivial properties of a program. Recent state-of-the-art models leverage highly structured representations of programs, such as trees, graphs and paths therein (e.g. data-flow relations), which are precise and abundantly available for code. This provides a strong inductive bias towards semantically meaningful relations, yielding more generalizable representations than classical sequence-based models. Unfortunately, these models primarily rely on graph-based message passing to represent relations in code, which makes them de facto local due to the high cost of message-passing steps, quite in contrast to modern, global sequence-based models, such as the Transformer. In this work, we bridge this divide between global and structured models by introducing two new hybrid model families that are both global and incorporate structural bias: Graph Sandwiches, which wrap traditional (gated) graph message-passing layers in sequential message-passing layers; and Graph Relational Embedding Attention Transformers (GREAT for short), which bias traditional Transformers with relational information from graph edge types. By studying a popular, non-trivial program repair task, variable-misuse identification, we explore the relative merits of traditional and hybrid model families for code representation. Starting with a graph-based model that already improves upon the prior state-of-the-art for this task by 20%, we show that our proposed hybrid models improve an additional 10-15%, while training both faster and using fewer parameters.
BibTeX
@inproceedings{hellendoorn2020global,
  author = {Vincent J. Hellendoorn and Charles Sutton and Rishabh Singh and Petros Maniatis and David Bieber},
  title = {{Global Relational Models of Source Code}},
  booktitle = {International Conference on Learning Representations},
  year = {2020},
}
Figure