Grammar-Constrained Decoding

Overview

The field studies how to combine language models with formal grammars so generated sequences follow languages and formats such as JSON, SQL, programming languages, and domain-specific commands. Common approaches use parser- or automaton-state token masks, context-free grammar parsing, and increasingly lookahead, grammar refinement, probability correction, or parallel decoding to improve completion and speed. These constraints support reliable structured generation, executable queries, and policy enforcement, but syntactic validity alone does not guarantee correct meaning or safe behavior. A central tension is that hard masking can distort the model’s conditional distribution or block good outputs when grammars are incomplete, while richer checks and more faithful sampling add computational cost.

Latest papers

32 papers4 papers in the last four weeks, against 2 the four weeks before. 0.0% of all new papers.

Mar 4, 2026

Attention Meets Reachability: Structural Equivalence and Efficiency in Grammar-Constrained LLM Decoding

We study grammar-constrained decoding (GCD) as a coupling between an autoregressive next-token distribution and a reachability oracle over a pushdown system compiled from a context-free grammar (CFG). We prove an oracle invariance theorem: language-equivalent grammars induce identical admissible next-token sets for every prefix, hence identical logit masks, yet can yield provably different compiled state spaces and online ambiguity costs. We give exact control-state blowup counts for the canonical anbna^n b^n language under redundant nonterminal delegation, and introduce a left-to-right structural ambiguity cost (SAC) measuring incremental packed-parse-forest growth per token. For two equivalent grammars over all finite strings, SAC is O(1)O(1) per token under right-recursion but Θ(t2)Θ(t^2) per token and Θ(n3)Θ(n^3) cumulatively under concatenation. We establish engine-independent lower bounds: any sound, retrieval-efficient, parse-preserving online masking engine must incur Ω(t2)Ω(t^2) work per token on a specific constant-size CFG family, unconditionally within this model. We define decoding-cost equivalence classes of grammars and prove existence of minimal-SAC representatives within bounded rewrite families. Finally, we characterize the true conditional sampler via a Doob hh-transform and derive sharp one-step KL and total-variation distortion bounds for hard-masked decoding in terms of survival-probability spread among admissible next tokens. We integrate these results with Transformer and Mixture-of-Experts architectures, derive latency envelopes in terms of vocabulary size, active state sets, and beam width, and connect SAC to instrumentation-based predictive performance models and automated grammar optimization.
May 31, 2024

Grammar-Aligned Decoding

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.