Constrained and structured decoding (grammars, JSON schemas), explained

Constrained decoding (also called structured generation or grammar-constrained decoding) forces a language model's output to belong to a formal language: a regular expression, a context-free grammar, or a JSON schema compiled to one of those. At every decoding step the engine computes which tokens could still lead to a valid output, sets the logits of all other tokens to minus infinity, and samples from what remains. The output is then guaranteed to parse. Every major open-source serving engine supports it (vLLM through XGrammar or llguidance, SGLang through XGrammar and its own compressed automata, llama.cpp through GBNF grammars), and it is the mechanism behind "JSON mode" and tool-call formatting. It interacts with post-training in two directions: a fine-tune can teach the format so that the constraint rarely binds, and the constraint can quietly shift the distribution your fine-tune learned. This article covers the mechanism, the math of that shift, the costs, and the tricks that make it fast.

Where it came from#

Constraining decoders to a grammar predates LLMs; for language models the modern line starts with PICARD (Scholak, Schucher and Bahdanau, 2021), which rejected inadmissible tokens via incremental SQL parsing and turned fine-tuned T5 models into state-of-the-art text-to-SQL systems. Geng, Josifoski, Peyrard and West (2023) argued that grammar-constrained decoding is a general framework for structured NLP tasks and introduced input-dependent grammars. The efficiency breakthrough was Willard and Louf (2023), the paper behind the Outlines library: compile a regular expression into a finite-state machine over characters, then precompute, for every state, which vocabulary tokens are allowed and which state each leads to. Per-step masking becomes a dictionary lookup instead of a scan over the vocabulary.

The following two years were about speed and correctness. SGLang (Zheng et al., 2023) compressed runs of single-transition states so that forced text is emitted without a model step, which its authors' blog post (Yin, Sheng and Zheng, 2024) reported cut latency by up to 2 times and raised throughput by up to 2.5 times for JSON decoding. SynCode (Ugare et al., 2024) and Koo, Liu and He (2024) gave sound treatments of tokenization against grammars. XGrammar (Dong et al., 2024) made context-free grammars fast by splitting the vocabulary into tokens whose validity can be precomputed and the rare ones that need the parser's stack, reporting up to 100 times faster mask generation than earlier engines and near-zero end-to-end overhead. On the correctness side, DOMINO (Beurer-Kellner, Fischer and Vechev, 2024) showed that constraints misaligned with subword boundaries can hurt accuracy, Park et al. (2024) showed that masking distorts the model's distribution, and JSONSchemaBench (Geng et al., 2025) measured how much of real-world JSON Schema each engine actually supports.

How it works#

Let $L$ be the target language over characters and $\mathcal{V}$ the token vocabulary, each token a character string. A prefix $s$ is viable if some completion puts it in $L$. At step $t$, with generated text $y_{<t}$, the mask is

For a regular language, viability is a state in a deterministic finite automaton (DFA), so the engine tracks one state per sequence and needs, for each state $\sigma$, the set $\{x:{\delta }^{\ast }(\sigma ,\mathrm{str}(x))\text{ is defined}\}$, where ${\delta }^{\ast }$ runs the DFA over the token's characters. The Outlines index precomputes exactly this table, so each step costs a lookup proportional to the number of allowed tokens. JSON Schemas with bounded nesting compile to regular expressions; recursive schemas and programming-language grammars need a context-free grammar, where viability depends on a stack and the table cannot be precomputed per state. That is the case XGrammar targets: it found that for a JSON grammar with the Llama-3.1 vocabulary about 99% of tokens are context-independent (decidable from the automaton position alone), leaving 1,134 that need the stack, reduced to 120 by expanding grammar context.

def constrained_step(logits, state, index, tokenizer_strings):
    allowed = index[state]                      # {token_id: next_state}, precomputed per automaton state
    mask = torch.full_like(logits, float("-inf"))
    mask[list(allowed)] = 0.0
    x = sample(logits + mask)                   # renormalisation is implicit in softmax
    return x, allowed[x]                        # advance the automaton

Toy run: what the mask costs to compute#

We wrote the automaton for {"name": "[A-Za-z ]+", "age": [0-9]{1,3}} by hand (26 states) and built a 32,000-token vocabulary: 33 useful JSON fragments plus random strings of 1 to 6 characters from letters, digits and JSON punctuation, roughly the size of a Llama-2-class vocabulary. Pure Python, single thread, seeded.

The naive mask alone took twice as long as the 6.5 ms decode step of an 8B model in our serving model, which is why early integrations visibly slowed generation. Indexing reduced it 42-fold even in Python; production engines in C++ and Rust go much further, with XGrammar reporting under 40 microseconds per token for JSON schemas. The remaining costs are compilation (paid once per new schema, so cache compiled grammars) and per-sequence state in a batch. Note also the literal states: even text the schema fully determines admits several tokenizations, which is the source of the tokenization problems discussed below.

The speed cost, and the tricks that remove it#

Per decoding step the engine does a GPU forward pass taking $t_{\text{gpu}}$ and, for each of $b$ constrained sequences, a mask computation taking $t_{\text{mask}}$ on the CPU. If the two run serially the step takes $t_{\text{gpu}}+b{t}_{\text{mask}}/n_{\text{threads}}$. If the mask for step $t+1$ is computed while the GPU runs step $t+1$'s forward pass (possible because the automaton state after step $t$ is known once its token is sampled), only the excess is visible:

With $t_{\text{mask}}$ in tens of microseconds and $t_{\text{gpu}}$ in milliseconds, overlap makes constraints effectively free; this is XGrammar's co-design with the serving engine. Two further tricks make constrained decoding faster than unconstrained decoding.

Jump-forward decoding. When the automaton has a single path for the next $k$ characters (keys, quotes, colons, closing braces), the engine appends that text directly, then runs one prefill-style pass over the appended tokens instead of $k$ decode steps. If a fraction $f$ of output characters is forced and forced runs average $\bar{k}$ tokens, the number of decode steps drops roughly by a factor $1-f(1-1/\bar{k})$. In our example 56% of characters are forced, so schemas with long keys and short values benefit most. The catch is tokenization: the forced text might be tokenized differently from how the model would have produced it, and the boundary between forced and free text can split a token the model would have used. SGLang's fix is to re-tokenize the whole text after jumping, at an overhead its authors measured at about 4%.

Speculation for free. Forced tokens are drafts with acceptance probability 1, so constrained decoding composes naturally with speculative decoding; DOMINO uses precomputation and speculation to reach up to almost 2 times the speed of unconstrained decoding in some settings.

The quality cost: masking changes the distribution#

What you want is a sample from the model conditioned on producing valid output, $p(y\mid y\in L)=p(y)1[y\in L]/Z$ with $Z={\sum }_{y\in L}p(y)$. What token-by-token masking produces is different. Write $M_t(y_{<t})={\sum }_{x}p(x\mid y_{<t})m_t(x)$ for the probability mass the mask keeps at step $t$. Then the masked sampler generates $y$ with probability

Outputs that pass through prefixes where the model wanted to go somewhere invalid (small $M_t$) are boosted. The exact conditional would instead weight each step by the probability of eventually completing a valid string, $p(y_t\mid y_{<t},y\in L)\propto p(y_t\mid y_{<t})\mathrm{Pr}[y\in L\mid y_{\le t}]$, which masking replaces with a 0/1 viability check. Park et al. (2024) call the fix grammar-aligned decoding and approximate the expected future grammaticality from previous samples (ASAp).

Worked example. A model outputs two symbols from {a, b}. It strongly prefers a first, $p(a)=0.9$, and after either symbol strongly prefers a, $p(a\mid \cdot )=0.99$. The grammar allows only "ab" and "ba". Exactly: $p(ab)=0.9\times 0.01=0.009$, $p(ba)=0.1\times 0.99=0.099$, so $p(ab\mid L)=0.009/0.108=0.083$. With masking, step 1 allows both symbols (each has a valid continuation), so a is chosen with probability 0.9 and step 2 is then forced to b: $q(ab)=0.9$. The formula agrees: $M_1=1$, $M_2(a)=0.01$, so $q(ab)=0.009/0.01=0.9$. Sampling 100,000 times in our script gave 0.900 for "ab" against the true conditional 0.083: masking picked the answer the model considered eleven times less likely.

The real-world analogue is a model that wants to answer in prose ("The answer is...") being forced to open a JSON object, or wanting to write a field it was not given. The constraint is satisfied, but the content may come from the model's low-probability tail.

What the measurements say

Tam et al. (2024), in "Let Me Speak Freely?", found a significant decline in reasoning ability under format restrictions, and larger declines for stricter formats. JSONSchemaBench (Geng et al., 2025) found the opposite direction on its tasks: with Llama-3.1-8B-Instruct, constrained decoding with Guidance improved accuracy over unconstrained generation on GSM8K (80.1% to 83.8%), Last Letter (50.7% to 54.0%) and Shuffle Objects (52.6% to 55.9%), and every framework it tested matched or beat the unconstrained baseline on all three tasks; it attributed Guidance's lead to careful handling of token boundaries ("token healing"). The two are compatible: constraints hurt when they prevent the model from reasoning before answering, and help when they only remove formatting failures. Put a free-text reasoning field before the answer fields in the schema, or let the model reason unconstrained and constrain only the final block.

JSONSchemaBench also shows that "supports JSON Schema" means different things. On its hardest real-world schema sets, the fraction of schemas an engine could handle while producing compliant output ranged widely across the open-source engines tested (for its GitHub-Hard schemas with Llama-3.2-1B, from 3% to 41%), and Outlines' compilation took seconds per schema against fractions of a second for the others. Test your actual schemas, especially oneOf, $ref, pattern properties and numeric bounds.

Interaction with fine-tuned and post-trained models#

Fine-tuning and constraints are complements. SFT on examples of the target format makes the model put most of its mass on valid outputs, so $M_t\approx 1$ at every step and, by the formula above, masked sampling coincides with the true conditional. The constraint then only catches rare failures. Conversely, constraining a model that was never trained on the format maximises distortion. If you rely on a schema in production, include it in your fine-tuning data exactly as it will be enforced, including key order and whitespace.

Tokenizer and template changes. Constraint engines build their index from the tokenizer's vocabulary strings. A fine-tune that adds special tokens (tool-call delimiters, thinking tags) must expose them correctly to the grammar engine, or the engine will either forbid them or treat them as literal text. The mask is applied to the whole vocabulary including padding rows of the embedding matrix; engines handle this, custom code often does not.

RL with constraints. If you generate GRPO or RLVR rollouts under a grammar, the sampled tokens come from $\tilde{p}$, not $p$. The policy-gradient update uses $\log p$ of the trained model, so the importance ratio between sampler and learner is off by the mask normaliser $M_t$ at every constrained step. Either compute log-probabilities under the same mask in the trainer, or train without constraints and reward format validity, then constrain only at serving time.

Evaluation. Evaluate fine-tuned checkpoints with the same constraint configuration as production. A checkpoint that looks better unconstrained can look worse constrained if it learned a format the schema disallows (for example, a reasoning preamble).

Adapters. With many LoRA adapters, schemas are usually per adapter or per request; compiled-grammar caches keyed by schema make this cheap.

Tuning knobs and tricks#

Failure modes and how to spot them#

Valid but wrong. Outputs always parse but accuracy drops relative to unconstrained generation followed by parsing. Compare both on a labelled set; if constrained is worse, look for reasoning being cut off or for schema fields the model would not naturally produce.

Runaway strings. A free string field with no length bound lets a model ramble until max_tokens, leaving the JSON unterminated. Add maxLength or a pattern, and monitor finish reason.

Whitespace loops. Grammars that allow arbitrary whitespace let some models emit newlines indefinitely. Restrict whitespace in the grammar.

Unsupported schema features. Silent fallbacks or compile errors on $ref, recursion or regex features. Check engine logs and run your schemas through a coverage test before launch.

Throughput drop at high batch. Mask computation scaling with batch size outruns the GPU step. Watch CPU utilisation of the serving process; use a backend with parallel, overlapped mask generation.

Tokenization artefacts. Odd spacing or broken words at the boundary between forced and free text, the problem DOMINO and token healing address. Inspect raw token sequences, not just decoded text.

When to use it, and what to use instead#

Implementation sketch#

In vLLM, structured outputs are a sampling parameter, with XGrammar or guidance as backends:

from vllm import LLM, SamplingParams
from vllm.sampling_params import StructuredOutputsParams

schema = {
    "type": "object",
    "properties": {
        "reasoning": {"type": "string", "maxLength": 800},   # let the model think first
        "label": {"enum": ["refund", "exchange", "escalate"]},
        "order_id": {"type": "string", "pattern": "^[A-Z]{2}[0-9]{6}$"},
    },
    "required": ["reasoning", "label", "order_id"],
}
llm = LLM(model="path/to/finetuned-support-model")
params = SamplingParams(temperature=0.0, max_tokens=1024,
                        structured_outputs=StructuredOutputsParams(json=schema))
print(llm.generate(["Customer message: ..."], params)[0].outputs[0].text)

Through the OpenAI-compatible server the same schema goes in the response_format or a structured_outputs field. SGLang accepts json_schema, regex or EBNF grammars per request. In POFE, when a fine-tuning dataset specifies an output schema, the same schema is used to constrain evaluation and serving, so the model is trained, measured and deployed under one format.

Further reading#

Willard and Louf (2023) for the indexing idea; Dong et al. (2024) for fast context-free grammars; Park et al. (2024) for the distribution distortion and its fix; Beurer-Kellner et al. (2024) for subword alignment; Geng et al. (2025) for an engine-by-engine benchmark; Tam et al. (2024) for the effect of format restrictions on reasoning.

Frequently asked questions#

References#

1. Brandon T. Willard, Rémi Louf (2023). Efficient Guided Generation for Large Language Models. arxiv.org/abs/2307.09702
2. Yixin Dong, Charlie F. Ruan, Yaxing Cai, Ruihang Lai, Ziyi Xu, Yilong Zhao, Tianqi Chen (2024). XGrammar: Flexible and Efficient Structured Generation Engine for Large Language Models. arxiv.org/abs/2411.15100
3. Torsten Scholak, Nathan Schucher, Dzmitry Bahdanau (2021). PICARD: Parsing Incrementally for Constrained Auto-Regressive Decoding from Language Models. arxiv.org/abs/2109.05093
4. Saibo Geng, Martin Josifoski, Maxime Peyrard, Robert West (2023). Grammar-Constrained Decoding for Structured NLP Tasks without Finetuning. arxiv.org/abs/2305.13971
5. Lianmin Zheng, Liangsheng Yin, Zhiqiang Xie, Chuyue Sun, Jeff Huang, Cody Hao Yu, Shiyi Cao, Christos Kozyrakis, et al. (2023). SGLang: Efficient Execution of Structured Language Model Programs. arxiv.org/abs/2312.07104
6. Liangsheng Yin, Ying Sheng, Lianmin Zheng (2024). Fast JSON Decoding for Local LLMs with Compressed Finite State Machine. lmsys.org/blog/2024-02-05-compressed-fsm/
7. Shubham Ugare, Tarun Suresh, Hangoo Kang, Sasa Misailovic, Gagandeep Singh (2024). SynCode: LLM Generation with Grammar Augmentation. arxiv.org/abs/2403.01632
8. Terry Koo, Frederick Liu, Luheng He (2024). Automata-based constraints for language model decoding. arxiv.org/abs/2407.08103
9. Luca Beurer-Kellner, Marc Fischer, Martin Vechev (2024). Guiding LLMs The Right Way: Fast, Non-Invasive Constrained Generation. arxiv.org/abs/2403.06988
10. Kanghee Park, Jiayu Wang, Taylor Berg-Kirkpatrick, Nadia Polikarpova, Loris D'Antoni (2024). Grammar-Aligned Decoding. arxiv.org/abs/2405.21047
11. Saibo Geng, Hudson Cooper, Michał Moskal, Samuel Jenkins, Julian Berman, Nathan Ranchin, Robert West, Eric Horvitz, Harsha Nori (2025). JSONSchemaBench: A Rigorous Benchmark of Structured Outputs for Language Models. arxiv.org/abs/2501.10868
12. Zhi Rui Tam, Cheng-Kuang Wu, Yi-Lin Tsai, Chieh-Yen Lin, Hung-yi Lee, Yun-Nung Chen (2024). Let Me Speak Freely? A Study on the Impact of Format Restrictions on Performance of Large Language Models. arxiv.org/abs/2408.02442
13. vLLM project (2025). vLLM documentation: Structured Outputs. docs.vllm.ai/en/latest/features/structured_outputs.html

Related reading