# Grammar-Aligned Decoding

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

## Key facts

- Cited by 54 papers in the map (data through 14 Oct 2026).
- Builds on 14 of its 28 references that are in the map.
- First posted on arXiv 31 May 2024.

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

- [Diffusion-LM Improves Controllable Text Generation](https://mlsanity.com/paper/2205.14217/) (2022)
- [PICARD: Parsing Incrementally for Constrained Auto-Regressive Decoding from Language Models](https://mlsanity.com/paper/2109.05093/) (2021)
- [Lexically Constrained Decoding for Sequence Generation Using Grid Beam Search](https://mlsanity.com/paper/1704.07138/) (2017)
- [Grammar-Constrained Decoding for Structured NLP Tasks without Finetuning](https://mlsanity.com/paper/2305.13971/) (2023)
- [Fast Lexically Constrained Decoding with Dynamic Beam Allocation for Neural Machine Translation](https://mlsanity.com/paper/1804.06609/) (2018)
- [Constrained Language Models Yield Few-Shot Semantic Parsers](https://mlsanity.com/paper/2104.08768/) (2021)
- [COLD Decoding: Energy-based Constrained Text Generation with Langevin Dynamics](https://mlsanity.com/paper/2202.11705/) (2022)
- [NeuroLogic A*esque Decoding: Constrained Text Generation with Lookahead Heuristics](https://mlsanity.com/paper/2112.08726/) (2021)
- [NeuroLogic Decoding: (Un)supervised Neural Text Generation with Predicate Logic Constraints](https://mlsanity.com/paper/2010.12884/) (2020)
- [Guided Open Vocabulary Image Captioning with Constrained Beam Search](https://mlsanity.com/paper/1612.00576/) (2016)
- [Gradient-Based Constrained Sampling from Language Models](https://mlsanity.com/paper/2205.12558/) (2022)
- [Zero and Few-shot Semantic Parsing with Ambiguous Inputs](https://mlsanity.com/paper/2306.00824/) (2023)
- [CodePAD: Sequence-based Code Generation with Pushdown Automaton](https://mlsanity.com/paper/2211.00818/) (2022)
- [On the Challenges of Fuzzing Techniques via Large Language Models](https://mlsanity.com/paper/2402.00350/) (2024)

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

- [Syntactic and Semantic Control of Large Language Models via Sequential Monte Carlo](https://mlsanity.com/paper/2504.13139/) (2025)
- [Flexible and Efficient Grammar-Constrained Decoding](https://mlsanity.com/paper/2502.05111/) (2025)
- [CRANE: Reasoning with constrained LLM generation](https://mlsanity.com/paper/2502.09061/) (2025)
- [Fast Controlled Generation from Language Models with Adaptive Weighted Rejection Sampling](https://mlsanity.com/paper/2504.05410/) (2025)
- [DINGO: Constrained Inference for Diffusion LLMs](https://mlsanity.com/paper/2505.23061/) (2025)
- [Self-Steering Language Models](https://mlsanity.com/paper/2504.07081/) (2025)
- [Controllable Generation via Locally Constrained Resampling](https://mlsanity.com/paper/2410.13111/) (2024)
- [SEVerA: Verified Synthesis of Self-Evolving Agents](https://mlsanity.com/paper/2603.25111/) (2026)
- [Mitigating Bias in Locally Constrained Decoding via Tractable Proposals](https://mlsanity.com/paper/2606.01926/) (2026)
- [Grammar-based Game Description Generation using Large Language Models](https://mlsanity.com/paper/2407.17404/) (2024)
- [Mind the Data Gap: Bridging LLMs to Enterprise Data Integration](https://mlsanity.com/paper/2412.20331/) (2024)
- [Correctness-Guaranteed Code Generation via Constrained Decoding](https://mlsanity.com/paper/2508.15866/) (2025)
- [Using a Feedback Loop for LLM-based Infrastructure as Code Generation](https://mlsanity.com/paper/2411.19043/) (2024)
- [Constrained Decoding for Safe Robot Navigation Foundation Models](https://mlsanity.com/paper/2509.01728/) (2025)
- [TreeCoder: Systematic Exploration and Optimisation of Decoding and Constraints for LLM Code Generation](https://mlsanity.com/paper/2511.22277/) (2025)
- [Sampling for Quality: Training-Free Reward-Guided LLM Decoding via Sequential Monte Carlo](https://mlsanity.com/paper/2604.16453/) (2026)
- [XML Prompting as Grammar-Constrained Interaction: Fixed-Point Semantics, Convergence Guarantees, and Human-AI Protocols](https://mlsanity.com/paper/2509.08182/) (2025)
- [The Future of Generative AI in Software Engineering: A Vision from Industry and Academia in the European GENIUS Project](https://mlsanity.com/paper/2511.01348/) (2025)
- [Approximately Aligned Decoding](https://mlsanity.com/paper/2410.01103/) (2024)
- [Constrained Adaptive Rejection Sampling](https://mlsanity.com/paper/2510.01902/) (2025)
- [Metamodel-Guided Model Generation with Layered Constraints](https://mlsanity.com/paper/2510.25890/) (2025)
- [Hard Constraints Meet Soft Generation: Guaranteed Feasibility for LLM-based Combinatorial Optimization](https://mlsanity.com/paper/2602.01090/) (2026)
- [Semantic Layers for Reliable LLM-Powered Data Analytics: A Paired Benchmark of Accuracy and Hallucination Across Three Frontier Models](https://mlsanity.com/paper/2604.25149/) (2026)
- [The Structured Output Benchmark: A Multi-Source Benchmark for Evaluating Structured Output Quality in Large Language Models](https://mlsanity.com/paper/2604.25359/) (2026)
- [Typed Decision Models: An Early Evidence Audit and Evaluation Checklist](https://mlsanity.com/paper/2609.32160/) (2026)
- [Positional Fragility in LLMs: How Offset Effects Reshape Our Understanding of Memorization Risks](https://mlsanity.com/paper/2505.13171/) (2025)
- [Future Validity is the Missing Statistic: From Impossibility to Phi-Estimation for Grammar-Faithful Speculative Decoding](https://mlsanity.com/paper/2605.07698/) (2026)
- [Naive Prompt Optimization: Rethinking the Need for Complex Prompt Search](https://mlsanity.com/paper/2608.27266/) (2026)
- [Bootstrapping Fuzzers for Compilers of Low-Resource Language Dialects Using Language Models](https://mlsanity.com/paper/2512.05887/) (2025)
- [SEAR: Schema-Based Evaluation and Routing for LLM Gateways](https://mlsanity.com/paper/2603.26728/) (2026)

## Abstract (arXiv)

Large Language Models (LLMs) struggle with reliably generating highly structured outputs, such as program code, mathematical formulas, or well-formed markup. Constrained decoding approaches mitigate this problem by greedily restricting what tokens an LLM can output at each step to guarantee that the output matches a given constraint. Specifically, in grammar-constrained decoding (GCD), the LLM's output must follow a given grammar. In this paper, we demonstrate that GCD techniques (and in general constrained decoding techniques) can distort the LLM's distribution, leading to outputs that are grammatical but appear with likelihoods that are not proportional to the ones given by the LLM, and so ultimately are low-quality. We call the problem of aligning sampling with a grammar constraint, grammar-aligned decoding (GAD), and propose adaptive sampling with approximate expected futures (ASAp), a decoding algorithm that guarantees the output to be grammatical while provably producing outputs that match the conditional probability of the LLM's distribution conditioned on the given grammar constraint. Our algorithm uses prior sample outputs to soundly overapproximate the future grammaticality of different output prefixes. Our evaluation on code generation and structured NLP tasks shows how ASAp often produces outputs with higher likelihood (according to the LLM's distribution) than existing GCD techniques, while still enforcing the desired grammatical constraints.