PaperlayerView exact revision on arXiv

Source-linked AI summary

Flexible and Efficient Grammar-Constrained Decoding

Kanghee Park, Timothy Zhou, Loris D'Antoni

arXiv:2502.05111v2cs.CLcs.AI

TL;DR

Grammar-constrained decoding must align LLM subword tokens with grammar terminals, a challenging part of efficient masking. The paper introduces GREATGRAMMA, which uses a lexer-state-dependent data structure to support token masking. It reports 17.71x faster offline preprocessing than related approaches while maintaining state-of-the-art online masking efficiency.

  • Problem

    LLM subword tokens may span or fragment grammar terminals, making token-to-terminal alignment a central challenge for grammar-constrained decoding.

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

  • Method

    GREATGRAMMA precomputes a data structure for terminal sequences realizable by LLM tokens in each lexer state, then uses it to help generate decoding masks.

    Source: §1 · p. 1, §7 · p. 9

  • Results

    17.71x average offline preprocessing speedup over related approaches (Ugare et al., 2024), while maintaining state-of-the-art online masking efficiency at 5-32ms per token.

    Source: §1 · p. 1

  • Takeaways & Limitations

    The approach combines low offline preprocessing overhead with state-of-the-art online masking efficiency for grammar-constrained decoding.

    Source: §1 · p. 1, §7 · p. 9

    The current implementation assumes maximal-munch and 1-lookahead lexing, so it does not support lexing requiring more lookahead or parsing-context-dependent tokenization.

    Source: §5 · p. 8

Abstract

from arXiv · show

Large Language Models (LLMs) are often asked to generate structured outputs that obey precise syntactic rules, such as code snippets or formatted data. Grammar-constrained decoding (GCD) can guarantee that LLM outputs matches such rules by masking out tokens that will provably lead to outputs that do not belong to a specified context-free grammar (CFG). To guarantee soundness, GCD algorithms have to compute how a given LLM subword tokenizer can align with the tokens used by a given context-free grammar and compute token masks based on this information. Doing so efficiently is challenging and existing GCD algorithms require tens of minutes to preprocess common grammars. We present a new GCD algorithm together with an implementation that offers 17.71x faster offline preprocessing than existing approaches while preserving state-of-the-art efficiency in online mask computation.

1. Introduction

Grammar-constrained decoding masks LLM tokens that cannot lead to outputs accepted by a specified grammar, but aligning LLM subword tokens with grammar terminals makes efficient decoding difficult. The paper introduces a flexible, efficient approach and GREATGRAMMA, reporting faster offline preprocessing while retaining low online masking overhead.

1. Introduction

  • GCD uses parsing to mask tokens that would provably lead to outputs outside the specified grammar.It can, for example, constrain generated programs to use only a specified set of function names.Source: §1 · p. 1
  • LLM subword tokens do not align with parser terminals, complicating GCD implementations and requiring token-to-terminal alignment for sound decoding.Existing approaches either incur over 1 second per token in online masking or over 30 minutes of offline preprocessing; these costs make them impractical when grammars change frequently.Source: §1 · p. 1
  • The approach combines analysis of the LLM vocabulary and CFG terminals to precompute a lexer-state-dependent mapping used to identify valid tokens during decoding.It avoids processing token combinations that are not realizable in the vocabulary.Source: §1 · p. 1
  • 17.71x faster offline preprocessing than related approaches (Ugare et al., 2024), with state-of-the-art online masking at 5-32ms per token.The evaluation also found soundness bugs in existing published implementations, including invalid masking and nontermination on simple grammars.Source: §1 · p. 1
  • The paper contributes a flexible, low-offline-overhead algorithm and GREATGRAMMA, an implementation designed to retain low online token-masking overhead.The approach is intended for settings such as program synthesis and grammar prompting, where grammars may change frequently.Source: §1 · pp. 1–2

2. Approach Overview

The overview explains how lexers turn text into terminals for parsing, then how a parser can guide constrained decoding despite the mismatch between parser terminals and LLM subword tokens. GREATGRAMMA addresses that mismatch with a token spanner table built offline and consulted online to produce decoding masks.

2.1. Lexing and Parsing

  • A lexer groups text matching terminal regular expressions, allowing the grammar and parser to operate on terminal sequences rather than individual characters.The example grammar accepts sequences of terminals in the form BCBCBC..., and a parser automaton accepts or rejects such sequences.Source: §2.1 · p. 2

2.2. Using Parsing for Constrained Decoding

  • Constrained decoding uses a parser-based checker to mask next tokens that cannot lead to a constraint-satisfying completion, but LLM subword tokens may span or fragment parser terminals.This token misalignment is identified as the chief source of complexity for GCD implementations.Source: §2.2 · p. 2

2.3. Our Approach

  • The token spanner table records which terminal sequences a lexer could emit for each LLM token in a given lexer state.The offline phase takes the LLM vocabulary and terminal regexes to construct a lexer automaton and table entries keyed by lexer state and LLM token.Source: §2.3 · pp. 2–3
  • During decoding, GREATGRAMMA tracks lexer and parser states, then consults the table to determine which LLM tokens to mask or keep.The table is constructed offline and used online to generate token masks.Source: §2.3 · pp. 2–3

3. Offline Token Preprocessing

Offline preprocessing builds token-to-terminal and inverse lookup structures, then preprocesses the parser to identify terminal sequences that can be handled without checking the stack. The combined lexer–parser preprocessing supports efficient token-mask computation.

3.1. Lexer Preprocessing

  • The lexer transducer models maximal-munch tokenization with one-character lookahead, emitting a terminal when the next character cannot advance the current lexer state.The described greedy behavior can stop when a scanned prefix cannot be tokenized as a single terminal.Source: §3.1 · pp. 3–4
  • Composing the character-to-terminal lexer with a detokenizing transducer yields a determinized token-level transducer for efficient lookups.The detokenizing transducer maps LLM tokens to characters, and shared token prefixes reuse trie-like computation.Source: §3.1 · p. 4

3.2. Realizable Terminal Sequences

  • The inverse token spanner table maps lexer states and realizable terminal sequences to generating tokens, while producibility checks use the lexer under the assumption that the vocabulary contains every character.The preprocessing identifies sequences formed by a token path followed by a producible terminal; the character-coverage assumption allows reachability checks in the lexer instead of the combined transducer.Source: §3.2 · p. 5

3.3. Parser Preprocessing

  • Composing the realizable terminal sequences with the parser produces a pushdown automaton over terminal sequences, enabling lexer and parser preprocessing in tandem.The authors identify this tandem preprocessing as a distinction from prior work.Source: §3.3 · p. 6
  • Many transducer transitions produce the same terminal sequence, making the realizable-sequence set smaller than the vocabulary or transition set and enabling efficient precomputation.This reduces the terminal sequences the parser must consider.Source: §3.3 · p. 6

4. Online Token Masking

At each decoding step, the algorithm uses the lexer and parser states and stack configuration to determine allowed LLM tokens. It avoids PDA traversal when possible and consults the inverse token spanner table for context-dependent sequences.

4. Online Token Masking

  • At each decoding step, the algorithm uses the lexer state, parser state, and stack configuration to compute exactly the LLM tokens that can lead to a grammar-accepted sequence.The output is the set of allowed tokens.Source: §4 · p. 6
  • The algorithm starts with always-accepted tokens and traverses the PDA only for context-dependent terminal sequences, avoiding costly stack-specific reachability checks when possible.Using the combined PDA at decoding time would require reachability computation under different stack configurations.Source: §4 · p. 6
  • For each grammar-accepted terminal sequence, the decoder looks up the tokens that can produce it from the current lexer state in the inverse token spanner table.The table is preprocessed alongside always-accepted tokens and context-dependent sequences.Source: §4 · p. 6

5. Experiments

Across the evaluated grammars and tokenizers, GREATGRAMMA preprocesses faster than SYNCODE but slower than OUTLINES, while achieving the lowest online masking overhead. The experiments also report failures in XGRAMMAR and describe implementation boundaries tied to the lexer assumptions.

Experimental setup

  • Experiments paired three tokenizers with simplified Go, Java, and Python grammars, timing preprocessing and per-token masks; downstream tasks were omitted because GCD approaches theoretically produce the same masks.Five manually built programs per grammar supplied token sequences for measuring online overhead.Source: §5 · p. 7

Results

  • XGRAMMAR was excluded because it failed to compile Java and entered an infinite loop or segfaulted while decoding Python and Go grammars.Source: §5 · p. 7

Discussion

  • OUTLINES has the lowest offline preprocessing overhead, but its seconds-per-token online overhead is attributed to runtime CFG checks for each token.Source: §5 · p. 7
  • GREATGRAMMA's slight online improvement over SYNCODE is attributed to consulting the PDA only for context-dependent sequences, unlike SYNCODE's bounded checks across all terminal sequences.Source: §5 · p. 7

Results

  • 17.71x faster offline than SYNCODE but 30.01x slower than OUTLINES; online geomean is 2.73x faster than SYNCODE and 550.57x faster than OUTLINES on remaining data points.The online comparison excludes terminal sequences where SYNCODE incorrectly masked a valid token.Source: §5 · p. 7, Table 1 · p. 8

Limitations

  • The implementation assumes maximal-munch, 1-lookahead lexing and does not support lexing that needs greater lookahead or depends on parsing context.The authors describe nondeterministic tokenization as a possible fix for practical ambiguities that do not require arbitrary lookahead.Source: §5 · p. 8
  • Supporting k-lookahead by combining lexer state with lookahead can significantly enlarge the resulting transducer.Source: §5 · p. 8
  • The algorithm can be adapted to nondeterministic PDAs without ϵ-transition loops that push stack symbols by computing each active state's allowed tokens and taking their union.Source: §5 · p. 8

6. Related Work

The paper compares GREATGRAMMA with prior GCD tools designed for realistic grammars and relates its design to their parsing and preprocessing strategies. It also notes mixed findings on constrained decoding's output quality and a newer tool that could not be compared on the evaluated grammars.

SYNCODE

  • SYNCODE is the only compared tool with low online overhead for the evaluated large grammars; it precomputes sequences up to a fixed bound, whereas GREATGRAMMA's table contains realizable sequences.The paper reports that GREATGRAMMA computes its table significantly faster.Source: §6 · p. 8

DOMINO

  • DOMINO traverses its terminal-sequence tree at decoding because realizable sequences vary by lexer state; GREATGRAMMA instead uses one global set and reports 25–35s preprocessing for 353–520-rule grammars versus DOMINO's reported 20s for a roughly 70-rule C grammar.DOMINO's reported online overhead for that simplified grammar is 22%, using the smaller Llama tokenizer.Source: §6 · pp. 8–9

XGRAMMAR

  • GREATGRAMMA combines context-independent token caching with a separate lexer and uses FSA overapproximation to identify more always-rejected sequences than XGRAMMAR's expanded suffix analysis.Source: §6 · p. 9

Effectiveness of constrained decoding

  • Studies report mixed effects of GCD on downstream output quality, and the paper describes its approach as orthogonal to methods proposed to mitigate negative effects.It names approaches by Park et al. (2024) and Banerjee et al. (2025) as possible integrations.Source: §6 · p. 9

LLGUIDANCE

  • LLGUIDANCE appeared after the paper was completed and shares a compositional approach, but uses derivative-based parsing; comparison was not possible because it reported ParserTooComplex on the evaluated grammars.The paper notes that some LLGUIDANCE optimizations might also benefit GREATGRAMMA.Source: §6 · p. 9

7. Conclusion

GREATGRAMMA uses a compact precomputed structure to support grammar-constrained decoding with low offline and online overhead.

7. Conclusion

  • GREATGRAMMA stores only terminal sequences realizable by LLM tokens in a given lexer state.Its precomputed structure is described as succinct and easy to generate.Source: §7 · p. 9
  • The structure speeds online masking by reducing the number of parser inputs checked during decoding.Source: §7 · p. 9
  • The implementation uses parsing-library primitives and consists of 800 lines of Python.The authors say its simplicity makes it easier to test and may support future work, including PDA-stack precomputation and GPU decoding.Source: §7 · p. 9

A. Algorithms

The algorithms formalize constrained decoding and the preprocessing steps that connect lexer, tokenizer, and parser behavior.

A. Algorithms

  • Algorithm 1 gives the abstract algorithm for general constrained decoding.Source: A. Algorithms · p. 11
  • Algorithm 2 builds a lexing transducer from a lexing automaton represented as a finite-state automaton.Source: A. Algorithms · p. 11
  • Algorithm 3 constructs a detokenizing transducer that converts token sequences into their character sequences.Source: A. Algorithms · p. 11
  • Algorithm 5 preprocesses the parser to build always-accepted-token and context-dependent-sequence tables.Source: A. Algorithms · p. 11

B. Formal Definitions

The appendix defines the automata and grammars used to formalize how strings are recognized, transformed, and accepted.

B.1. Finite-State Automata

  • A finite-state automaton is a tuple of input alphabet, states, initial state, transitions, and accepting states.A transition reads a symbol and moves from one state to another.Source: §B.1 · p. 11
  • Parser preprocessing takes a PDA, realizable sequences, an FSA, and an inverse token-spanner table to produce two lookup tables.Source: §B.1 · p. 12
  • The extended transition relation covers strings, and a string is accepted when a transition reaches an accepting state.Source: §B.1 · p. 12
  • The paper uses “accepted in state q” more broadly than standard acceptance, defining it through a transition from q.Source: §B.1 · p. 12

B.2. Context-Free Grammar

  • A context-free grammar specifies terminals, nonterminals, a start symbol, and production rules that derive strings of terminals.Source: §B.2 · p. 12
  • The grammar’s prefix language contains every prefix of a sentence in its language.Source: §B.2 · p. 12

B.3. Finite State Transducer

  • A finite-state transducer resembles an automaton but its transitions can also output sequences of symbols.Source: §B.3 · p. 12

B.4. Pushdown Automata

  • A pushdown automaton adds a stack whose top symbols can be matched and replaced during transitions.Source: §B.4 · p. 12

C. Formalizations and Proofs

The formalizations specify how lexer behavior, token-to-terminal mappings, and grammar prefixes determine which token sequences are valid.

C.1. Lexer

  • The lexer specification pairs automata with terminal symbols and defines a partial lexer that processes characters with one-symbol lookahead.The lexer either extends a token prefix, completes a token, or returns failure.Source: §C.1 · pp. 12–13
  • The lexing automaton is the product of the automata in the lexer definition.Source: §C.1 · p. 13
  • The lexing-transducer correctness result assumes no lexer automaton accepts the empty string and none has dead states.Under those assumptions, its transitions correspond to the partial lexer’s output and remaining input.Source: §C.1 · p. 13

C.2. Inverse Token Spanner Table

  • The inverse token-spanner table records which tokens correspond to terminal sequences from a given transducer state.Source: §C.2 · p. 13

C.3. Parser

  • With a separate lexer, a token sequence is a sentence when it lexes to derivable terminals ending in EOS.The corresponding language consists of token strings whose lexed terminal sequence is a grammar sentence.Source: §C.3 · p. 13
  • The lexer-realizable prefix language contains prefixes of token sequences that lex to grammar sentences.Source: §C.3 · p. 13
  • A token is left unmasked when appending it keeps the sequence within the lexer-realizable grammar prefix language.The proof fragments give both the sufficient and necessary directions for this allowed-token condition.Source: §C.3 · p. 14

Related papers

Loading 2502.05111v2…