PaperlayerView exact revision on arXiv

Source-linked AI summary

Learning to Complete Code with Sketches

Daya Guo, Alexey Svyatkovskiy, Jian Yin, Nan Duan, Marc Brockschmidt, Miltiadis Allamanis

arXiv:2106.10158v2cs.LGcs.SE

TL;DR

Code language models can generate plausible but incorrect code, and some completion content is uncertain from context. Grammformer uses grammar-guided generation to produce sketches with holes; it outperforms baseline methods on REGEXACC for Python and C#.

  • Problem

    Code language models can produce plausible but incorrect code, while context may not make the user's intended names or content clear.

    Source: §1 · p. 1

  • Method

    Grammformer generates code sketches by expanding grammar non-terminals and can leave them as holes when a prediction is uncertain.

    Source: §2 · p. 2, §2.2 · p. 4

  • Results

    Grammformer outperforms baseline methods on REGEXACC for both Python and C# and generates substantially longer suggestions for complex targets.

    Source: §3 · p. 7

  • Takeaways & Limitations

    Code sketches with holes are presented as a step toward better collaboration between machine-learning models and human users.

    Source: §5 · p. 10

    Pure language modeling cannot predict user-defined types and rare APIs whose names are unavailable during training.

    Source: §3.1 · p. 9

Abstract

from arXiv · show

Code completion is usually cast as a language modelling problem, i.e., continuing an input in a left-to-right fashion. However, in practice, some parts of the completion (e.g., string literals) may be very hard to predict, whereas subsequent parts directly follow from the context. To handle this, we instead consider the scenario of generating code completions with "holes" inserted in places where a model is uncertain. We develop Grammformer, a Transformer-based model that guides code generation by the programming language grammar, and compare it to a variety of more standard sequence models. We train the models on code completion for C# and Python given partial code context. To evaluate models, we consider both ROUGE as well as a new metric RegexAcc that measures success of generating completions matching long outputs with as few holes as possible. In our experiments, Grammformer generates 10-50% more accurate completions compared to traditional generative models and 37-50% longer sketches compared to sketch-generating baselines trained with similar techniques.

1 INTRODUCTION

Code language models can generate plausible but incorrect code, while intent and names may be unclear from the context. The paper proposes grammar-guided code sketches with holes to mark uncertainty and evaluates them against conventional models.

1 INTRODUCTION

  • Guiding language models toward a specific goal can be difficult when intent is complex or costly to express.Source: §1 · p. 1
  • Code language models can hallucinate plausible but incorrect content, and small code mistakes can be hard to debug or introduce vulnerabilities.Source: §1 · p. 1
  • When context leaves a name unclear, a concrete completion may overcommit, whereas a hole signals where user input is needed.Source: §1 · pp. 1–2
  • Standard left-to-right models are not trained to continue after a hole token, making hole-based generation difficult to train directly.Source: §1 · p. 2
  • Grammformer generates grammar-based partial syntax trees and can leave non-terminals as holes, with a reward favoring long predictions and few holes while avoiding errors.Source: §1 · p. 2
  • The paper introduces REGEXACC to evaluate predictions with holes and evaluates Grammformer on Python and C# against baseline methods.Source: §1 · p. 2

2 METHOD

The method represents code completions as sketches containing predicted tokens and holes, and evaluates both matchability and precision. It contrasts reinforcement-trained sequence models with GRAMMFORMER, which expands selected grammar non-terminals while leaving others as holes.

2 METHOD

  • Sketches mix code tokens with holes; REGEXACC rewards sketches that match the target while predicting as many terminal tokens as possible, and ROUGE gives partial credit after holes are removed.A hole stands for an arbitrary non-empty sequence; the method also considers ROUGE F1 on the sketch with holes erased.Source: §2 · pp. 2–3

2.1 LINEAR CODE SKETCH GENERATION

  • Because standard generative models lack supervised examples containing holes, the sequence baseline adds a hole token and uses reinforcement learning with a reward averaging REGEXACC and ROUGE.It first pretrains on targets with randomly replaced AST non-terminals, then fine-tunes using the reward.Source: §2.1 · p. 3

2.2 GRAMMAR-BASED CODE SKETCH GENERATION

  • GRAMMFORMER iteratively chooses any non-terminal to expand or stops, then can return unexpanded non-terminals as holes.Its selector chooses where to expand, while its expansion model determines the replacement; this separates choosing a hole from generating an expansion.Source: §2.2 · p. 4
  • A shared Transformer encoder represents the input, while a relational Transformer decoder generates expansions and attends to the selected non-terminal.The relational attention connects each token to the non-terminal being expanded.Source: §2.2 · pp. 4–5
  • GRAMMFORMER uses reinforcement learning with the sketch reward and pretrains its expansion model on supervised expansions before training its selector and fine-tuning both models end-to-end.The pretraining samples non-terminals uniformly, amortizes encoding across candidate expansions, and avoids sampling during expansion-model pretraining.Source: §2.2 · p. 5
  • Grammar flattening replaces selected non-terminals with their possible expansions to avoid tedious intermediate rewrites; flattening all but the start symbol would reduce GRAMMFORMER to a standard encoder-decoder.Source: §2.2 · p. 5
  • At test time, two-step beam search ranks candidate non-terminal positions and expansions together, retaining the top-k combined results.For each beam state it considers top-m positions and top-n expansions for each position.Source: §2.2 · p. 6
  • GRAMMFORMER incurs extra computation because its encoder-decoder must be recomputed after each partial-sequence expansion, unlike left-to-right generation with reusable intermediate results.Source: §2.2 · p. 6

3 EVALUATION

GRAMMFORMER produces better-matching sketches than the baselines in Python and C#, with longer suggestions on complex targets. Ablations and qualitative examples show the roles of learned selection and grammar-guided decoding, while also exposing cases where predictions remain too conservative or lack needed API information.

3 EVALUATION

  • Evaluation uses 318K C# and 362K Python examples, each with the preceding 200 terminal tokens as context; ROUGE and REGEXACC are measured on generated output only.Examples are sampled from SimpleStatement syntax-tree nodes in parsed, deduplicated GitHub repositories.Source: §3 · p. 6
  • GRAMMFORMER outperforms baselines on REGEXACC for both Python and C#, while L→R can match or exceed its ROUGE score; fine-tuning further improves GRAMMFORMER.L→R’s sketches can contain errors despite their ROUGE scores, whereas fine-tuning is associated with joint adaptation of the selector and expander.Source: Table 1 · p. 7, §3 · p. 7
  • On complex targets, GRAMMFORMER generates substantially longer suggestions than other models, while model differences are small for short targets.L →R + ⦸ generates very short suggestions because it stops when uncertain about the next token.Source: Figure 3 · p. 7, §3 · p. 7
  • Among models producing longer suggestions, GRAMMFORMER is more often correct, with its advantage increasing for longer targets; L →R + ⦸ is most often correct overall.The latter’s short predictions are less determined, reflecting the trade-off captured by REGEXACC.Source: §3 · p. 7, Figure 4 · p. 8
  • The C# selector and reward ablations show that learned selection performs best, while optimizing only one reward metric improves that metric at substantial cost to the other.REGEXACC-only training yields shorter predictions; its strict match requirement produces sparse rewards and more conservative expansion.Source: Table 2 · p. 8, §3 · p. 8
  • Grammar-guided decoding yields longer and more correct predictions than a variant that cannot introduce holes.The comparison is against a variant that continues expansion until no non-terminals remain.Source: §3 · pp. 8–9

3.1 QUALITATIVE EVALUATION

  • Qualitative examples illustrate that sketches can offer more informative suggestions when the code context does not specify the user’s intent.GRAMMFORMER can also be too conservative, producing holes where L →R gives concrete completions.Source: §3.1 · p. 9
  • Pure language modeling cannot predict user-defined types or rare API names unavailable during training; static-analysis information and additional context may help.Source: §3.1 · p. 9

4 RELATED WORK

Prior grammar-based code generators target complete programs, while sketch-generating approaches use supervised sketches suited to simpler domains. Grammformer differs by generating code sketches and by following the programming-language grammar rather than generating full text without a defined grammar.

4 RELATED WORK

5 DISCUSSION & CONCLUSIONS

The paper presents GRAMMFORMER as a code generator that produces sketches with holes. It identifies human evaluation, natural-language corpora, and code semantics as directions for further work.

5 DISCUSSION & CONCLUSIONS

  • GRAMMFORMER generates code sketches with holes beyond standard left-to-right generation, an ability the authors frame as relevant to human–model collaboration.They report better sketch-generation performance than alternatives, while noting that improvement opportunities remain.Source: §5 · p. 10
  • Human studies are needed to assess the correctness–concreteness trade-off measured by REGEXACC and could inform reward functions and user experience.The authors also expect larger transformer models to improve results.Source: §5 · p. 10
  • The experiments focus on programming languages; natural-language modeling would require large parsed-text corpora, and representing code as terminal and non-terminal sequences omits data- and control-flow structure.The authors suggest that explicitly providing deterministic code structure may improve GRAMMFORMER’s performance.Source: §5 · p. 10

A GENERATED SAMPLES

The examples show GRAMMFORMER’s generation process and include both desired and mistaken outputs. One C# example matches the ground-truth expansion while leaving a dictionary key as a hole.

A GENERATED SAMPLES

  • Figures 5 and 6 pair dataset examples with ground truth and GRAMMFORMER’s expansion sequence; Figures 7–13 compare model generations, and Figures 15–17 illustrate mistakes.The baseline L →R + ⦸ uses a special <suffix> non-terminal to mark a hole at the end of left-to-right generation.Source: A GENERATED SAMPLES · p. 13
  • Figure 5 shows successive generation states for a C# sketch that matches the ground-truth expansion but leaves the dictionary key as a hole instead of predicting a low-likelihood string literal.Figures 7–13 show examples from GRAMMFORMER and two baselines, while Figures 15–17 show GRAMMFORMER mistakes.Source: Figure 5 · p. 13, A GENERATED SAMPLES · p. 13

B DATASET STATISTICS

The section directs readers to Table 3 for statistics on the datasets used in the work.

B DATASET STATISTICS

  • Table 3 presents statistics about the datasets used throughout the work.The passage does not report the table’s values.Source: B DATASET STATISTICS · p. 13

C FLATTENED NON-TERMINALS

Flattening fixed-rule non-terminals reduces tree depth and the number of generation loops. In an example, Grammformer places a hole where the variable name is difficult to predict and generates a matching sketch.

C FLATTENED NON-TERMINALS

  • Flattening non-terminals with fixed children reduces tree depth and therefore the number of loops needed in Algorithm 1.Most such non-terminals represent a single CFG rule.Source: C FLATTENED NON-TERMINALS · p. 13
  • When a target variable name is impossible to predict from context, Grammformer places a hole there and generates a matching sketch.The example concerns reading a second argument and storing it in a variable.Source: Figure 6 · p. 14
  • Table 3 reports statistics for the datasets used.Source: Table 3 · p. 14

D UNDERSTANDING REGEXACC

Deterministic hole placement illustrates how REGEXACC scores sketches with different levels of specificity; the examples report a better score for C# than Python when identifiers and literals are replaced.

D UNDERSTANDING REGEXACC

  • Replacing all string and numeric literals with holes yields a high REGEXACC, while replacing identifiers as well gives an easy lower bound.The supplied passage does not specify the numerical scores.Source: D UNDERSTANDING REGEXACC · pp. 14–15
  • A C# example shows Grammformer identifying a method call on exchangeActivity without predicting the concrete method; static-analysis information about the type is suggested as a possible extension.Source: Figure 7 · p. 15
  • C# achieves a better score than Python when both identifiers and literals are replaced, which leaves punctuation such as parentheses, brackets, and dots.Source: D UNDERSTANDING REGEXACC · p. 15

E BEAM SEARCH

Beam search expands incomplete Grammformer generations and prunes candidates; the examples show both successful sketches and cases where grammar constraints or unavailable API information limit predictions.

E BEAM SEARCH

  • Grammformer places a hole for an unpredictable expected value in an AreEqual assertion, producing a correct line-level sketch while L → R is wrong and L → R + ⦸ is shorter.Source: Figure 8 · p. 16
  • Beam search initializes with the input, expands incomplete candidates, and retains the top-k candidates until generations are complete.The algorithm selects top-m non-terminal positions and top-n expansions before pruning.Source: E BEAM SEARCH · p. 16
  • In other examples, both L → R and Grammformer predict the full line correctly, and a constructor’s uncertain string argument is represented with a hole.Source: Figure 9 · p. 17, Figure 10 · p. 18
  • When the first token is impossible to guess, L → R and L → R + ⦸ fail to generate correct sketches, while Grammformer produces a correct sketch with two holes.Source: Figure 12 · p. 20, Figure 13 · p. 21
  • Grammformer can produce an almost-right C# completion without a needed hole, and a grammar-limited integer literal cannot expand to int.Parse(args[2]).Source: Figure 14 · p. 21, Figure 15 · p. 22
  • Other examples show a correct but unhelpful sketch and models failing to invoke the correct library API; external class definitions are suggested as a possible remedy.Source: Figure 16 · p. 22, Figure 17 · p. 23
Loading 2106.10158v2…