PaperlayerView exact revision on arXiv

Source-linked AI summary

Constrained Decoding for Fill-in-the-Middle Code Language Models via Efficient Left and Right Quotienting of Context-Sensitive Grammars

Daniel Melcer, Nathan Fulton, Sanjay Krishna Gouda, Haifeng Qian

arXiv:2402.17988v2cs.PLcs.LGcs.SE

TL;DR

Language models can produce syntactically incorrect code, and FIM completion must also connect generated text to a right context. This paper extends Earley parsing for quotient languages and context-sensitive language features, then evaluates constrained Python 3 generation. Across both datasets, the method performs significantly better than unconstrained generation.

  • Problem

    FIM generation must connect generated code to a right context, while existing methods do not support FIM and may miss real-language complexities such as context-sensitive lexing.

    Source: §I · p. 2

  • Method

    The paper extends Earley parsing for quotient languages and handles context-sensitive features in an incremental parser used for constrained Python 3 generation.

    Source: §I · p. 2

  • Results

    On both datasets, the method performs significantly better than unconstrained generation, while checked unconstrained generation fixes some cases and constrained generation still performs slightly better.

    Source: C. Results & Discussion · p. 9

  • Takeaways & Limitations

    The Python 3 system generates valid code in cases where unconstrained generation fails.

    Source: §I · p. 2

    The implementation is a research prototype, so its performance results may differ considerably from a production-quality implementation, likely by several orders of magnitude.

    Source: D. Runtime Performance · p. 9

Abstract

from arXiv · show

Large Language Models are powerful tools for program synthesis and advanced auto-completion, but come with no guarantee that their output code is syntactically correct. This paper contributes an incremental parser that allows early rejection of syntactically incorrect code, as well as efficient detection of complete programs for fill-in-the-middle (FIM) tasks. We extend the Earley parsing algorithm to allow for left and right quotients of context-free grammars, and develop methods to handle quotienting of several context-sensitive features present in the grammars of many common programming languages. The result of these contributions is an efficient, general, and well-grounded method for left and right quotient parsing. To validate our theoretical contributions -- and the effectiveness of certain design decisions -- we evaluate our method on the particularly difficult case of FIM completion for Python 3, with syntax-correctness constraints. Our results demonstrate that constrained generation can significantly reduce the incidence of syntax errors in recommended code.

I. INTRODUCTION

Code-generation models can produce syntactically invalid code, and fill-in-the-middle completion must connect generated text to a right context that may not be valid on its own. The paper presents constrained FIM generation for Python 3 using quotient parsing and methods for context-sensitive language features.

I. INTRODUCTION

  • Because language models treat code as unstructured text, they may produce incorrect syntax; constrained generation tests proposed tokens against program structure.The approach selects from tokens that keep the generation a prefix of a valid program.Source: §I · p. 1
  • FIM completion must connect generated code to a right context even when neither context is valid as a program on its own.Existing methods described here do not support FIM and may not account for context-sensitive lexing.Source: §I · pp. 1–2
  • The paper extends Earley parsing for quotienting and adapts quotienting and incremental parsing to context-sensitive features, then evaluates constrained generation for Python 3.The experiments compare syntax-constrained generation with unconstrained generation.Source: §I · p. 2

A. Automata and Regular Languages

  • A regular language is one accepted by a nondeterministic finite automaton (NFA).The passage defines an NFA using states, an alphabet, an initial state, transitions, and final states.Source: A. Automata and Regular Languages · p. 2

B. Context-Free Grammars and Languages

A context-free grammar generates a language by expanding nonterminals from a start symbol. For constrained generation, the parser must recognize complete programs and determine whether proposed text can still be completed, including when a right context is fixed.

B. Context-Free Grammars and Languages

  • A context-free grammar (CFG) consists of nonterminals, terminals, production rules, and a start symbol; it generates strings by recursively expanding nonterminals.A language is context-free when some CFG represents all its strings.Source: B. Context-Free Grammars and Languages · p. 2

III. PROBLEM STATEMENT

  • A proposed EOS token is acceptable only when the generated text is a complete program; other tokens are acceptable when the result remains completable.This distinguishes a membership query for EOS from a check for possible completion after another token.Source: §III · p. 2
  • For a fixed right context, the problem is to build an incremental recognizer and membership query for the language's right quotient by that context.The right quotient contains left strings that can be followed by some string in the right-context language to form a member of the original language.Source: §III · p. 2
  • The recognizer and membership queries should reuse work across strings sharing a prefix and right context, ideally with constant-time overhead per generated token.The stated target is linear time in generation length.Source: §III · pp. 2–3

A. Why Not Just Run The Parser?

Checked unconstrained generation reruns a parser on the assembled input, but cannot reject uncompletable prefixes early and has unfavorable complexity. The paper instead modifies Earley parsing to incrementally track parser states and test completion.

A. Why Not Just Run The Parser?

  • Checked unconstrained generation cannot test incremental parsability, so it may generate code with no possible completion.It is limited to checking whether the generated text is valid when EOS is proposed.Source: A. Why Not Just Run The Parser? · p. 3
  • Parsing the entire input for each character costs linear time per generated token and quadratic time in generation length.This repeated full-input parsing conflicts with the stated efficiency requirement.Source: A. Why Not Just Run The Parser? · p. 3

IV. EARLEY PARSING

  • The paper modifies Earley parsing to calculate a CFG for the language right-quotiented by a regular language.Earley charts hold items representing partial parses; the initial chart contains items for the start-symbol productions.Source: §IV · p. 3
  • Earley scanning advances items when the next input symbol matches, while prediction and completion add items for expansions and completed constituents.A complete start-symbol item recognizes the input; scannable terminals also identify valid prefixes and possible next symbols.Source: §IV · p. 3

A. Earley Algorithm Applied to NFAs

The method represents Earley charts as states in a transition system, allowing parsing against regular languages rather than only fixed strings. Bookkeeping over item creation then supports extraction of quotient grammars, including the right quotient.

A. Earley Algorithm Applied to NFAs

  • Earley charts can be represented as states in a nondeterministic transition system, with the scanner following its transitions while prediction and completion reach a fixpoint.This transition system matches the NFA for the input string; more complex systems let the algorithm test whether the CFG intersects a regular language.Source: A. Earley Algorithm Applied to NFAs · p. 3

B. Quotient Extraction

  • Tracking how Earley items were created lets the charts implicitly represent a left quotient, which an extraction algorithm turns into an explicit CFG.Creation methods for duplicate items must also be retained for correct extraction.Source: B. Quotient Extraction · p. 3
  • The right quotient is obtained by reversing the regular language and CFG, taking the left quotient, and reversing the result.The passage gives this construction as REVERSE(REVERSE(R) \ REVERSE(L(G))).Source: B. Quotient Extraction · p. 3

Example:

  • In the incomplete-call example, the algorithm works backward through Earley item creation to identify how open nonterminals can be completed.For instance, it traces an open argument continuation through the enclosing arguments and call items.Source: Example · p. 4

V. LEXED CONTEXT-FREE LANGUAGES

Real programming languages combine context-free grammars with lexer behavior, including context-sensitive lexing and maximal-munch rules. The section extracts quotient grammars by tracing how Earley items are created.

V. LEXED CONTEXT-FREE LANGUAGES

  • Lexers recognize regular-language lexemes and commonly handle whitespace and comments specially, adding behavior beyond a context-free grammar.The section treats these features as factors in quotienting lexed languages.Source: §V · p. 4
  • The extraction algorithm computes, for each chart and nonterminal, a grammar describing how to complete Earley items originating in that chart.It traverses Earley item creation methods.Source: Figure 2 · p. 4
  • Under maximal munch, the lexer accepts the longest prefix matching any lexeme, then repeats on the remaining source text.The passage notes that some real languages do not follow this rule.Source: §V · p. 4

A. Incremental Lexing

Incremental lexing lacks lookahead to determine whether a partial symbol should end or continue. The method branches over both possibilities and uses parser feedback and guards to discard inconsistent branches.

A. Incremental Lexing

  • Without lookahead, an incremental lexer cannot know whether a matched lexeme is complete or whether more input would form a longer symbol.This uncertainty arises while a symbol is still in progress.Source: A. Incremental Lexing · p. 4
  • The lexer branches between extending the symbol-in-progress and treating the received character as its end, then removes branches inconsistent with later text.A branch is deleted if its symbol-in-progress ceases to prefix any lexeme or a longer match violates its guard.Source: A. Incremental Lexing · pp. 4–5
  • The branch guards prevent exponential growth because the condition that creates a further extension branch also deletes the competing completed-symbol branch.The figure illustrates lexer actions and parser interaction for the string “ore(”.Source: A. Incremental Lexing · p. 5, Figure 4 · p. 5
  • For Python, checking whether a symbol can extend into a higher-priority non-scannable lexeme did not require a regular-language subset test.The passage says that more exotic lexeme-priority structures likely would require one.Source: A. Incremental Lexing · p. 5
  • Whitespace and comments may remain scannable whenever other scannable terminals exist, but matched whitespace is not passed to the parser.Source: A. Incremental Lexing · p. 5

B. Right Quotient of Lexed Languages

Right quotienting must account for right-context prefixes that may continue a symbol from the generated quotient text. The method branches over feasible continuation points, constrains each branch, and connects it to the remaining context.

B. Right Quotient of Lexed Languages

  • Python's observed lexing behavior limits the implementation to two branches, although leftmost-longest matching can briefly allow the second branch to branch further.The implementation deletes the first branch unless the second immediately branches again.Source: B. Right Quotient of Lexed Languages · p. 5
  • The algorithm creates a branch for each feasible right-context index, then parses the text after that index.It first guesses how many initial right-context characters continue the last quotient-text symbol.Source: B. Right Quotient of Lexed Languages · p. 6
  • For a branch that leaves a right-context quote unaccounted for, the quotient grammar requires the quotient text to end in a string and prevents its final symbol from capturing past that quote.The lexer constrains the final symbol to capture exactly the first character of the right context.Source: B. Right Quotient of Lexed Languages · p. 6
  • A median of 5 unique starting indices and a maximum of 10, including index 0, were found for right-context branches.Each feasible index represents a possible point where a symbol continued from the quotient text ends.Source: B. Right Quotient of Lexed Languages · p. 6
  • The algorithm computes possible NFA states at each index, and its sparse representation of F_g remains bounded by |Q| per step, giving O(n) runtime.The state sets support connecting the quotient text to the right context.Source: B. Right Quotient of Lexed Languages · p. 7

VI. WHITESPACE-SENSITIVE LANGUAGES

Whitespace-sensitive behavior is handled in the lexer rather than the parser. For Python indentation, the lexer emits INDENT and DEDENT symbols while tracking indentation and parentheses nesting.

VI. WHITESPACE-SENSITIVE LANGUAGES

  • The lexer counts leading spaces on eligible lines and emits INDENT or DEDENT symbols as indentation levels change.If no prior indentation level matches, it emits a syntax error; indentation is ignored after line continuation or within parentheses.Source: §VI · p. 7
  • Identical text on the last two lines can produce significantly different lexer output.Source: Figure 9 · p. 7
  • For incremental parsing, indentation leaves a valid completion: more whitespace can extend too-low indentation, while a newline can end too-high indentation.The lexer also tracks parentheses nesting depth.Source: §VI · p. 7

A. Right-quotienting with whitespace sensitivity

Right quotienting handles uncertain indentation by representing possible lexer outputs as a regular language. The method balances completeness, soundness, and complexity because indentation lengths vary.

A. Right-quotienting with whitespace sensitivity

  • The lexer represents possible right-context outputs as a regular language, then computes a quotient grammar accepting strings matching the context’s indentation.At the first newline it allows INDENT or DEDENT*, and tracks possible lowest indentation levels for later DEDENT ranges.Source: A. Right-quotienting with whitespace… · p. 7

B. A Completeness-Soundness-Complexity Tradeoff

C. Parentheses in the Right Context

The parser handles parentheses in the right context by branching over possible nesting levels and filtering inconsistent branches. The evaluation uses synthetic completion tasks built from Python files.

C. Parentheses in the Right Context

  • A simpler nesting count requires an additional full lexer pass because parentheses inside comments and strings must be excluded.Source: C. Parentheses in the Right Context · p. 8
  • The lexer guesses whether the insertion point is inside parentheses, processes indentation differently in each branch, and removes branches inconsistent with the right context.At the end of the right context, surviving branches must have zero nesting change and match the current nesting level.Source: C. Parentheses in the Right Context · p. 8

VII. EXPERIMENTS

  • The evaluation implements a proof-of-concept incremental right-quotient parser for Python 3 and tests constrained generation in simulated code completion.Source: §VII · p. 8

A. Datasets

  • The base dataset contains 9,539 Python files after excluding 459 files rejected by Python 3.9’s ast.parse and two files using unimplemented features.Source: A. Datasets · p. 8
  • STACK-BOUNDARY removes text and part of a symbol between same-indentation symbols, while STACK-RANDSPAN deletes random spans at ten insertion points per file.STACK-BOUNDARY uses ten random symbol pairs per file; STACK-RANDSPAN deletions are capped at 100 characters, 20% of the file, or the file end.Source: A. Datasets · pp. 8–9

B. Experimental Setup

Constrained generation performs better than unconstrained generation on both evaluated datasets. The experiments use simulated completions and analyze parser and model-related failures separately.

B. Experimental Setup

  • Each experiment uses SantaCoder with a FIM task, and the quotient language is computed from contexts that may differ from the LLM input after truncation.Source: B. Experimental Setup · p. 9
  • Generation uses greedy sampling, tests up to 50 token candidates, stops at 500 tokens, and counts success when ast.parse accepts the result.If no candidate passes, generation stops; checked unconstrained generation instead tests prefixes in context with ast.parse.Source: B. Experimental Setup · p. 9

C. Results & Discussion

1) Failure Analysis:

  • Of 4,725 unsuccessful STACK-BOUNDARY generations, 29 involved parser-accepted quotient matches rejected by Python; unconstrained generation succeeded in one case and checked unconstrained in 22 more.Source: 1) Failure Analysis · p. 9
  • In 4,696 other STACK-BOUNDARY failures, the model did not connect to the right context before cutoff; unconstrained generation succeeded in 10 cases and checked unconstrained in 72 more.Some cases require steering toward finite grammar branches or allowing valid tokens beyond the top 50.Source: 1) Failure Analysis · p. 9

D. Runtime Performance

The prototype’s per-token generation overhead is nearly uncorrelated with context size, while setup overhead occurs once per generation. The paper also identifies context escape and other static analyses as future work.

D. Runtime Performance

  • The prototype is written largely in Python with selected Rust subroutines, so its performance may differ from production implementations by several orders of magnitude.Source: D. Runtime Performance · p. 9
  • At ∼10^3 generated tokens, constrained per-token times become faster after one-time parsing overhead; the prototype is competitive with ast.parse for large or repeated contexts (∼10^4).Source: D. Runtime Performance · pp. 9–10, Figure 11 · p. 10

A. Preventing Context Escape

  • Context escape is syntactically valid generation that leaves the user’s likely editing intent, such as closing a function call and starting another.Source: A. Preventing Context Escape · p. 10
  • Context-escape metrics and more complete systems are out of scope, though the explicit quotient CFG may support language-specific heuristics.Source: A. Preventing Context Escape · p. 10

B. Static Analyses Beyond Well-Formedness

  • The parser addresses well-formedness at a single insertion point; applying quotienting to type safety, memory safety, or other static properties remains future work.Source: B. Static Analyses Beyond… · p. 10

IX. CONCLUSION

  • The paper’s conclusion is that modified Earley parsing can incrementally parse quotient languages and support constrained Python generation with higher syntax-correctness rates than unconstrained generation.Source: §IX · p. 10
Loading 2402.17988v2…