Definition
Constrained decoding (also guided or grammar-constrained generation) restricts each decoding step to tokens that keep the output a valid prefix of a formal language: a regular expression, a context-free grammar, or a JSON Schema compiled to one of them. Disallowed tokens get logit and the remaining probabilities are renormalised. Willard and Louf ("Efficient Guided Generation for Large Language Models", 2023, the Outlines library) showed how to precompute the masks from a finite-state machine so that each step costs a lookup instead of a scan of the vocabulary.
A prompt that says "reply with JSON" is a request, not a guarantee. The model may add a preamble, quote a number, invent a field or stop mid-object, and the parser downstream fails. Constrained decoding moves the format from the prompt into the sampler: invalid output cannot be produced, whatever the model prefers.
It sits between the logits and the sampler, after any Temperature sampling, Top-k and top-p sampling or Logit bias processing. The model itself is unchanged. That is why the same technique powers JSON-schema response formats in hosted APIs (see Structured output (JSON mode) for the API side), grammar files in local runtimes, and SQL-only decoding for Text-to-SQL.
The mask
- the model's logit for token after any other logit processors
- the automaton state reached by the text generated so far
- the set of tokens allowed in state ; end-of-sequence is in it only if is accepting
- equal to restricted to and divided by the kept mass
The hard part is computing . A naive implementation decodes all token strings at every step and checks each against a parser. With (Llama 3) that is 128,256 checks per generated token.
The FSM index
Willard and Louf compile the regex into a character-level deterministic finite automaton (DFA) with states , transition and accepting set . They then walk every vocabulary token's characters from every state, once, before decoding starts:
- the character string of token
- applied character by character; undefined if any character leads to the dead state
Building the index costs walks, which is paid once per schema and can be cached. During generation, each step is a table lookup for the mask and another for the next state. One token can cross several grammar symbols: ": moves the automaton through three states. That is why the index works on token strings, not on grammar terminals.
Grammars and JSON Schema
A bounded JSON Schema (fixed keys, enums, string patterns, numbers) can be translated to a regex, and Outlines does exactly that. Nested or recursive structures (arbitrary JSON, SQL, programming languages) need a context-free grammar. A grammar has a stack, so the allowed set depends on more than a finite state and cannot be fully precomputed. Outlines combines the index with an incremental LALR parser. PICARD (Scholak, Schucher and Bahdanau, EMNLP 2021) rejected tokens that broke an incremental SQL parse on Spider. llama.cpp accepts GBNF grammar files. XGrammar (Dong et al., 2024) precomputes the tokens whose validity does not depend on the stack and checks only the rest at run time.
Reference points
- Willard & Louf (2023)
- regex → DFA → state-to-token index; CFG support through an incremental LALR parser; released as Outlines
- PICARD (2021)
- constrained beam search for text-to-SQL with T5, rejecting tokens that fail an incremental parse
- Grammar-aligned decoding (Park et al., NeurIPS 2024)
- shows that per-step masking distorts the distribution relative to the model conditioned on validity, and proposes a correction
- Hosted APIs
- OpenAI's Structured Outputs (August 2024) enforce a supplied JSON Schema with constrained decoding; other providers offer similar schema modes
- Serving engines (as of 2025)
- vLLM and SGLang expose regex, JSON-schema and grammar guidance with pluggable backends such as Outlines and XGrammar
Token boundaries
Tokens and grammar symbols do not line up, and three problems follow. First, many token sequences spell the same string: {" or { + ". The mask allows both, so the model may be pushed into a non-canonical split it rarely saw in training (see Tokenization algorithms).
Second, the prompt boundary. If a template ends in "answer": ", the model would normally have produced " merged with the next word. Forcing the split puts it off-distribution. Token healing, introduced in Microsoft's Guidance library, removes the last prompt token and constrains the first generated token to start with its text. Beurer-Kellner et al. (DOMINO, ICML 2024) study this misalignment and align constraints to subword tokens.
Third, the mask is local. Each step renormalises over what is allowed now, so , where is the kept mass at step . This is not . A path whose early tokens were likely but that later needs heavily masked steps keeps its early credit. In the toy below, masked sampling gives {"age": 42} probability 0.9906; the exact conditional, computed over all 225 valid token paths, is 0.9997.
Worked example: one masked step
State 8 is reached after {"age": . The toy model's probabilities and each token's walk from state 8:
| Token | Walk from state 8 | Allowed | p | p̃ |
|---|---|---|---|---|
"4 | " → dead | no | 0.2998 | 0 |
42 | 4 → 9, 2 → 10 | yes | 0.2500 | 0.5602 |
" | " → dead | no | 0.2335 | 0 |
4 | 4 → 9 | yes | 0.1947 | 0.4363 |
1, 2 | → 9 | yes | 0.0008 each | 0.0017 each |
100 | 1 → 9, 0 → 10, 0 → dead | no | 0.0013 | 0 |
42 | space → dead (one space already used) | no | 0.0013 | 0 |
Greedy picks 42 and moves to state 10, where contains only }. The next step is forced regardless of the logits, and then only end-of-sequence is allowed.
1import numpy as np23def build_index(step, n_states, vocab, accept, eos):4 """sigma[q] = boolean mask over the vocabulary; nxt[q][v] = state after token v."""5 sigma = np.zeros((n_states, len(vocab)), dtype=bool)6 nxt = np.full((n_states, len(vocab)), -1)7 for q in range(n_states):8 for v, tok in enumerate(vocab):9 if v == eos:10 ok, s = q in accept, q11 else:12 s = q13 for ch in tok: # a token may cross several grammar symbols14 s = step(s, ch)15 if s < 0:16 break17 ok = s >= 018 sigma[q, v], nxt[q, v] = ok, s19 return sigma, nxt2021def constrained_greedy(logits_fn, sigma, nxt, eos, max_new=32):22 q, out = 0, []23 for _ in range(max_new):24 z = logits_fn(out).astype(float)25 z[~sigma[q]] = -np.inf # the mask: one vector op per step26 v = int(np.argmax(z))27 if v == eos:28 return out29 out.append(v)30 q = nxt[q, v]31 raise RuntimeError("budget exhausted before an accepting state")3233# Regex [0-9]+ over a toy vocabulary34vocab = ["7", "42", "4a", " ", "<eos>"]35step = lambda q, ch: 1 if ch.isdigit() else -136sigma, nxt = build_index(step, 2, vocab, accept={1}, eos=4)37print(sigma.astype(int)) # [[1 1 0 0 0] [1 1 0 0 1]]38fake = lambda out: np.array([0.1, 0.5, 2.0, 1.0, 3.0 if out else -9]) # prefers "4a", then EOS39print([vocab[v] for v in constrained_greedy(fake, sigma, nxt, eos=4)]) # ['42']Use when
- +Output always parses: no retry loop for format errors.
- +Forced tokens (single-member σ) can skip sampling, and some engines emit several in one step.
- +Works with any model whose logits you control; no fine-tuning.
Avoid when
- −Index compilation for a large schema and a 128k vocabulary can take noticeable time; cache it per schema.
- −Local renormalisation distorts the distribution and can force non-canonical tokenisations.
- −Recursive grammars need a stack, so masks cannot be fully precomputed.
- −Hosted APIs that do not expose logits support only the schemas the provider implements.
Check yourself
Why does the FSM index walk each token's full character string instead of mapping each grammar terminal to a token?
Check yourself
At some step the mask removes 90% of the probability mass. What does that suggest?
Remember
- ✓Mask: for , renormalise, sample; EOS only in accepting states.
- ✓FSM index (Willard & Louf, 2023): token walks once, then O(1) lookups per step.
- ✓Grammars (SQL, recursive JSON) need a stack: incremental parsers (PICARD, Outlines) or partly precomputed masks (XGrammar).
- ✓Token boundaries matter: tokens cross symbols, prompts end mid-token (token healing), and non-canonical splits are possible.
- ✓Per-step renormalisation is not ; large removed mass signals a schema–model conflict.