# Flexible and Efficient Grammar-Constrained Decoding

arXiv: https://arxiv.org/abs/2502.05111 · HTML: https://mlsanity.com/paper/2502.05111/

## Key facts

- Cited by 43 papers in the map (data through 14 Oct 2026).
- Builds on 9 of its 15 references that are in the map.
- First posted on arXiv 7 Feb 2025.

## Builds on (most cited first, 9 of 9)

- [Efficient Guided Generation for Large Language Models](https://mlsanity.com/paper/2307.09702/) (2023)
- [Grammar-Constrained Decoding for Structured NLP Tasks without Finetuning](https://mlsanity.com/paper/2305.13971/) (2023)
- [Synchromesh: Reliable code generation from pre-trained language models](https://mlsanity.com/paper/2201.11227/) (2022)
- [Guiding LLMs The Right Way: Fast, Non-Invasive Constrained Generation](https://mlsanity.com/paper/2403.06988/) (2024)
- [Let Me Speak Freely? A Study on the Impact of Format Restrictions on Performance of Large Language Models](https://mlsanity.com/paper/2408.02442/) (2024)
- [JSONSchemaBench: A Rigorous Benchmark of Structured Outputs for Language Models](https://mlsanity.com/paper/2501.10868/) (2025)
- [Grammar Prompting for Domain-Specific Language Generation with Large Language Models](https://mlsanity.com/paper/2305.19234/) (2023)
- [Grammar-Aligned Decoding](https://mlsanity.com/paper/2405.21047/) (2024)
- [Automata-based constraints for language model decoding](https://mlsanity.com/paper/2407.08103/) (2024)

## Built on by (most cited first, 30 of 43)

- [Grounding Multimodal LLMs to Embodied Agents that Ask for Help with Reinforcement Learning](https://mlsanity.com/paper/2504.00907/) (2025)
- [Fast Controlled Generation from Language Models with Adaptive Weighted Rejection Sampling](https://mlsanity.com/paper/2504.05410/) (2025)
- [Constrained Sampling for Language Models Should Be Easy: An MCMC Perspective](https://mlsanity.com/paper/2506.05754/) (2025)
- [Pre3: Enabling Deterministic Pushdown Automata for Faster Structured LLM Generation](https://mlsanity.com/paper/2506.03887/) (2025)
- [Mitigating Bias in Locally Constrained Decoding via Tractable Proposals](https://mlsanity.com/paper/2606.01926/) (2026)
- [Lookahead-then-Verify: Reliable Constrained Decoding for Diffusion LLMs under Context-Free Grammars](https://mlsanity.com/paper/2602.00612/) (2026)
- [The Hidden Cost of Structured Generation in LLMs: Draft-Conditioned Constrained Decoding](https://mlsanity.com/paper/2603.03305/) (2026)
- [XML Prompting as Grammar-Constrained Interaction: Fixed-Point Semantics, Convergence Guarantees, and Human-AI Protocols](https://mlsanity.com/paper/2509.08182/) (2025)
- [ToolPRM: Fine-Grained Inference Scaling of Structured Outputs for Function Calling](https://mlsanity.com/paper/2510.14703/) (2025)
- [Constrained Decoding for Diffusion Language Models via Efficient Inference over Finite Automata](https://mlsanity.com/paper/2607.07026/) (2026)
- [Constrained Adaptive Rejection Sampling](https://mlsanity.com/paper/2510.01902/) (2025)
- [The Format Tax](https://mlsanity.com/paper/2604.03616/) (2026)
- [A DbC Inspired Neurosymbolic Layer for Trustworthy Agent Design](https://mlsanity.com/paper/2508.03665/) (2025)
- [Grounded Misunderstandings in Asymmetric Dialogue: A Perspectivist Annotation Scheme for MapTask](https://mlsanity.com/paper/2511.03718/) (2025)
- [Schema-Key Wording as an Instruction Channel in Structured Generation under Constrained Decoding](https://mlsanity.com/paper/2604.14862/) (2026)
- [MDP-GRPO: Stabilized Group Relative Policy Optimization for Multi-Constraint Instruction Following](https://mlsanity.com/paper/2606.06058/) (2026)
- [Bootstrapping Fuzzers for Compilers of Low-Resource Language Dialects Using Language Models](https://mlsanity.com/paper/2512.05887/) (2025)
- [Autoregressive, Yet Revisable: In Decoding Revision for Secure Code Generation](https://mlsanity.com/paper/2602.01187/) (2026)
- [TruncProof: A Guardrail for LLM-based JSON Generation under Token-Length Constraints](https://mlsanity.com/paper/2605.13076/) (2026)
- [EPIC: Efficient and Parallel Inference under CFG Constraints for Diffusion Language Models](https://mlsanity.com/paper/2606.00722/) (2026)
- [The Alignment Problem in Constrained Code Generation](https://mlsanity.com/paper/2606.21619/) (2026)
- [Large Databases Need Small, Open-Weight Language Models](https://mlsanity.com/paper/2606.31808/) (2026)
- [Stay Within Your Bounds: Distance-Guided Decoding for Guaranteed Context-Free Grammar Compliance](https://mlsanity.com/paper/2608.28229/) (2026)
- [Play by the Type Rules: Inferring Constraints for LLM Functions in Declarative Programs](https://mlsanity.com/paper/2509.20208/) (2025)
- [Position: Vibe Coding Needs Vibe Reasoning: Improving Vibe Coding with Formal Verification](https://mlsanity.com/paper/2511.00202/) (2025)
- [Orthographic Constraint Satisfaction and Human Difficulty Alignment in Large Language Models](https://mlsanity.com/paper/2511.21086/) (2025)
- [LLMs + Security = Trouble](https://mlsanity.com/paper/2602.08422/) (2026)
- [Continuous Diffusion Models Can Obey Formal Syntax](https://mlsanity.com/paper/2602.12468/) (2026)
- [Precise Robot Command Understanding Using Grammar-Constrained Large Language Models](https://mlsanity.com/paper/2604.04233/) (2026)
- [Syntax Is Easy, Semantics Is Hard: Evaluating LLMs for LTL Translation](https://mlsanity.com/paper/2604.07321/) (2026)

## Abstract (arXiv)

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.