Learning to Extend Program Graphs to Work-in-Progress Code

Xuechen Li, Chris J. Maddison, Daniel TarlowarXiv 2021 · OpenReview

Abstract

Source code spends most of its time in a broken or incomplete state during software development. This presents a challenge to machine learning for code, since high-performing models typically rely on graph structured representations of programs derived from traditional program analyses. Such analyses may be undefined for broken or incomplete code. We extend the notion of program graphs to work-in-progress code by learning to predict edge relations between tokens, training on well-formed code before transferring to work-in-progress code. We consider the tasks of code completion and localizing and repairing variable misuse in a work-in-process scenario. We demonstrate that training relation-aware models with fine-tuned edges consistently leads to improved performance on both tasks.

Introduction

Modern machine learning models for code often rely on "program graphs"—representations like data-flow or control-flow—to understand the underlying logic of a script. However, these graphs typically require perfectly compilable code to generate. In a real-world development environment, code is frequently in a "work-in-progress" (WIP) state: half-written functions, missing brackets, or invalid indentation.

Example of program graph edges (e.g., LastRead, ComputedFrom) overlaid on a Python function.

Traditional static analysis tools are "picky"; if the code doesn't compile, the analysis fails, and the model loses its structural "map." This creates a catch-22 where ML is most needed to help write code, but requires valid code to be effective. This paper introduces a method to predict these structural edges directly from raw text, allowing advanced models to function on broken or incomplete code.

Methods

The authors propose a two-stage approach to bridge the gap between raw text and structured program graphs.

1. Edge Prediction Model

The first stage involves a Transformer-based model trained to predict 10 types of semantic edges (such as LastRead, ComputedFrom, or CFGNext) between tokens. This is framed as a multi-label classification problem. The model is initially trained on "well-formed" code where ground-truth edges can be reliably generated by standard static analysis tools.

The proposed model architecture, featuring a Transformer encoder with relative positional encoding and GRU-based edge prediction.

2. Relation-Aware Downstream Models

The predicted edges are then fed into "relation-aware" Transformers designed for specific downstream tasks like code completion or variable misuse repair.

3. Fine-tuning through Discrete Edges

A key innovation is allowing the edge predictor to be fine-tuned during the downstream task. Because edges are discrete (binary existence), the authors utilize a Straight-Through Estimator. This allows gradients to flow back from the final task into the edge prediction model, enabling the model to "hallucinate" the most useful structural relations for the task at hand, even when the code is syntactically invalid.

Experimental Setup

The approach was evaluated on two primary Python-based benchmarks:

  • Code Completion: A large Python corpus containing nearly 1 million files.
  • Variable Misuse: A dataset focused on localizing and repairing incorrect variable usage.

To simulate real-world "broken" code, the researchers created "WIP Perturbations" by artificially corrupting these datasets with random keyword changes, token deletions, punctuation errors, and invalid indentation.

Results and Discussion

The experiments yielded several key insights:

  • Generalization to Broken Code: Surprisingly, a model trained on perfect code generalizes well to code with syntax errors. It can often "see" the intended data flow through the noise of a typo or missing bracket.
  • The Necessity of Fine-tuning: While a fixed, pre-trained edge predictor provides benefits, the most significant gains come from fine-tuning the edge model alongside the task model.
  • Impact of "Hard" Edges: Performance improvements in code completion are primarily driven by "hard-to-predict" edges—those derived from deep logic rather than simple sequence relations.
  • Performance Metrics: On the Python code completion task, the "Aware-tuned" model achieved a Top-1 accuracy of 80.7%, outperforming the relation-agnostic baseline (79.7%). In variable misuse scenarios with high corruption (5 errors per file), localization accuracy reached 78.4% compared to 72.6% for the baseline.

Conclusion

While the fine-tuned edges significantly improve performance, they occasionally drift from their original semantic definitions to optimize for the specific task, which can reduce interpretability. Additionally, while this study focused on Python, the methodology is generalizable. Future work may explore more complex relational structures and improve the explainability of these adapted relations across different programming languages.

Summary updated

Abstract

Source code spends most of its time in a broken or incomplete state during software development. This presents a challenge to machine learning for code, since high-performing models typically rely on graph structured representations of programs derived from traditional program analyses. Such analyses may be undefined for broken or incomplete code. We extend the notion of program graphs to work-in-progress code by learning to predict edge relations between tokens, training on well-formed code before transferring to work-in-progress code. We consider the tasks of code completion and localizing and repairing variable misuse in a work-in-process scenario. We demonstrate that training relation-aware models with fine-tuned edges consistently leads to improved performance on both tasks.
BibTeX
@misc{li2021learning,
  author = {Xuechen Li and Chris J. Maddison and Daniel Tarlow},
  title = {{Learning to Extend Program Graphs to Work-in-Progress Code}},
  year = {2021},
  eprint = {2105.14038},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2105.14038},
}
Figure