Research map / Large language models / Language, safety and interpretability
Flexible and Efficient Grammar-Constrained Decoding
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Presents GreatGramma, a grammar-constrained decoding algorithm built on a token spanner table over lexer states and realizable terminal sequences, achieving 17.71x faster offline preprocessing than SynCode while keeping low online masking overhead.
Problem
Grammar-constrained decoding must align LLM subword tokens with CFG terminals; existing methods either have high online per-token masking overhead or tens of minutes of offline preprocessing for common grammars.
Approach
Combine lexer and LLM vocabulary analysis into a token spanner table that maps (lexer state, LLM token) to realizable terminal sequences, then preprocess the parser against only these realizable sequences, using always-accepted tokens and context-dependent sequences at decoding time.
Key results
- Offline preprocessing is 17.71x faster than SynCode on geomean, but 30.01x slower than Outlines.
- Online masking is 2.73x faster than SynCode and 550.57x faster than Outlines on geomean; GreatGramma achieves 5-32 ms per token.
- XGrammar failed on all grammars (Java compile failure; infinite loop or segfault on Python and Go).
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use GreatGramma's realizable-terminal-sequence preprocessing instead of SynCode's bounded speculative unrolling | Grammar-constrained decoding · Go, Java, and Python grammars with Llama, Llama-3, and Qwen-2 tokenizers | offline preprocessing time: 17.71x faster | Helped |
| Use GreatGramma's context-dependent-sequence checks and inverse token spanner table instead of checking all terminal sequences | Grammar-constrained decoding · Go, Java, and Python grammars; remaining data points | online masking time: 2.73x faster than SynCode; 550.57x faster than Outlines | Helped |
| Use GreatGramma instead of Outlines | Grammar-constrained decoding · Go, Java, and Python grammars with the evaluated tokenizers | offline preprocessing time: 30.01x slower | Hurt |
| Use SynCode's bounded future-terminal unrolling | SynCode · Certain terminal sequences | token-mask soundness | Hurt |
Surprising findings
- SynCode incorrectly masked valid tokens for certain terminal sequences, likely due to its fixed unrolling bound k.
- XGrammar errored during preprocessing or decoding for all evaluated grammars.
Limitations
- Supports only maximal munch and 1-lookahead lexing; cannot handle context-dependent lexing (e.g., Java generics >>).
- Slower offline preprocessing than Outlines (30x on geomean).
- Requires manual translation of grammars between tool formats; evaluated on only three grammars.
Experimental setup
Datasets: simplified Go grammar simplified Java grammar simplified Python grammar (from SynCode benchmark)
Benchmarks: Go, Java, Python grammars offline/online timing
Metrics: offline preprocessing time (seconds) online per-token masking overhead (milliseconds) geomean speedup
Baselines: Outlines SynCode XGrammar
Builds on: SynCode Lark Outlines
Closest papers by meaning
- Grammar-Aligned Decoding (NeurIPS 2024 · similarity 0.92)
- Earley-Driven Dynamic Pruning for Efficient Structured Decoding (ICML 2025 · similarity 0.86)
- Guiding LLMs The Right Way: Fast, Non-Invasive Constrained Generation (ICML 2024 · similarity 0.85)
- Approximately Aligned Decoding (NeurIPS 2025 · similarity 0.85)
- CRANE: Reasoning with constrained LLM generation (ICML 2025 · similarity 0.84)
- Unlocking Tokens as Data Points for Generalization Bounds on Larger Language Models (NeurIPS 2024 · similarity 0.84)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.