Constrained decoding

Constrained decoding sets the logit of every token that cannot extend a valid prefix of a regex, grammar or JSON Schema to −∞; with an FSM index (Willard & Louf, 2023) the per-step mask is a table lookup.

8 min read858 wordsadvanced0 viewsupdated 2026-10-21

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 −∞-\infty 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

p~(v∣x<t)=exp⁡(zv+mv)∑u∈Vexp⁡(zu+mu),mv={0v∈σ(qt)−∞otherwise\tilde p(v\mid x_{<t})=\frac{\exp(z_v+m_v)}{\sum_{u\in V}\exp(z_u+m_u)},\qquad m_v=\begin{cases}0 & v\in\sigma(q_t)\\-\infty & \text{otherwise}\end{cases}
zvz_v
the model's logit for token vv after any other logit processors
qtq_t
the automaton state reached by the text generated so far
σ(q)\sigma(q)
the set of tokens allowed in state qq; end-of-sequence is in it only if qq is accepting
p~\tilde p
equal to pp restricted to σ(qt)\sigma(q_t) and divided by the kept mass ∑v∈σ(qt)p(v)\sum_{v\in\sigma(q_t)}p(v)

The hard part is computing σ(qt)\sigma(q_t). A naive implementation decodes all ∣V∣|V| token strings at every step and checks each against a parser. With ∣V∣=128,256|V|=128{,}256 (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 QQ, transition δ\delta and accepting set FF. They then walk every vocabulary token's characters from every state, once, before decoding starts:

σ(q)={ v∈V: δ∗(q, s(v)) is defined },qt+1=δ∗(qt, s(vt))\sigma(q)=\{\,v\in V:\ \delta^*(q,\,s(v))\ \text{is defined}\,\},\qquad q_{t+1}=\delta^*\big(q_t,\,s(v_t)\big)
s(v)s(v)
the character string of token vv
δ∗\delta^*
δ\delta applied character by character; undefined if any character leads to the dead state

Building the index costs ∣Q∣⋅∣V∣|Q|\cdot|V| 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.

1 · compile the constraint once: regex \{"age": ?[1-9][0-9]?\} → character DFA1-9}{"age":␣1-90-9}01234567891011state 11 accepts (⟨eos⟩ allowed only there) · ␣ = space · any other character → dead2 · build the index σ(q): walk every token's characters from every state (12 × 24 walks)":␣5 →" 6 →: 7 →␣ 8∈ σone token, three grammar symbols428 →4 9 →2 10∈ σtwo digits in one token1008 →1 9 →0 10 →0 dead∉ σfails on its last character"48 →" dead∉ σa string where an integer must goσ(8) ={1, 4, 2, 42}4 of 24 tokens;lookup O(1)3 · each step: logits + mask, renormalise, pick, advance (state 8, after {"age":␣)tokenmodel pmask mp̃ ∝ p·1[v∈σ(8)]"40.300−∞0420.25000.560"0.233−∞040.19500.4361, 20.001 each00.002 eachkept mass 0.446argmax p̃ → 42q ← δ*(8, 42) = 10σ(10) = only }numbers from the toy model in the interactive figure below
fig.The regex \{"age": ?[1-9][0-9]?\} becomes a 12-state character DFA (top). Walking each of the 24 toy tokens from each state gives the index: ": takes state 5 to 8, 42 takes 8 to 10, while 100 dies on its last character and "4 dies at once, so σ(8) = {1, 4, 2, 42}. At state 8 the model's favourite token "4 (p = 0.300) is masked; the kept mass is 0.446, and 42 is chosen with p̃ = 0.250 / 0.446 = 0.560.

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 p~(y)=∏tp(yt∣y<t)/Zt\tilde p(y)=\prod_t p(y_t\mid y_{<t})/Z_t, where ZtZ_t is the kept mass at step tt. This is not p(y∣y∈L)p(y\mid y\in L). 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.

regex \{"age": ?[1-9][0-9]?\} · greedymask off✗{"age":␣"42"}⟨eos⟩mask on✓{"age":␣42}⟨eos⟩step 4: DFA state 8 · top 8 of 24 tokens■ model p■ sampled-from p̃after “{"age":␣”"40.300 → masked420.250 → 0.560"0.233 → masked40.195 → 0.436␣years0.003 → maskedSure0.002 → masked"age0.002 → maskedage0.001 → maskedindex: allowed tokens σ(q)q |σ| tokens (built once) 02{ {" 12" "age 21age 30— (only via longer tokens) 40— (only via longer tokens) 53" ": ":␣ 61: 77␣ 1 4 2 42 ␣4 ␣42 841 4 2 42 941 4 2 }101}111⟨eos⟩chosen 42 · p̃ = 0.560 · mass removed by the mask = 0.554output “{"age":␣42}” · matches · log p = -4.928400 seeded samples: mask off → 7.2% match the regex; mask on → 100%✗ = output fails the regex · ␣ = space · rose line = token blocked in this state
inspectdecoding
fig.A 24-token toy model that likes chatty or quoted answers, decoded with the DFA mask off and on. Greedy, mask off: {"age": "42"}, valid JSON but not the regex. Mask on: {"age": 42}. Step 4 (state 8) removes 0.554 of the mass: "4 (0.300) and " (0.233) are blocked and 42 goes from 0.250 to 0.560. Step 5 removes 0.761 because the model wanted " years" (0.558). Over 400 seeded samples, 29 (7.2%) match with the mask off and all 400 with it on.

Worked example: one masked step

State 8 is reached after {"age": . The toy model's probabilities and each token's walk from state 8:

TokenWalk from state 8Allowedpp̃
"4" → deadno0.29980
424 → 9, 2 → 10yes0.25000.5602
"" → deadno0.23350
44 → 9yes0.19470.4363
1, 2→ 9yes0.0008 each0.0017 each
1001 → 9, 0 → 10, 0 → deadno0.00130
42space → dead (one space already used)no0.00130
Kept mass Σ p over allowed tokens = 0.4462, so p̃ = p / 0.4462

Greedy picks 42 and moves to state 10, where σ(10)\sigma(10) contains only }. The next step is forced regardless of the logits, and then only end-of-sequence is allowed.

python
1import numpy as np
2
3def 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, q
11 else:
12 s = q
13 for ch in tok: # a token may cross several grammar symbols
14 s = step(s, ch)
15 if s < 0:
16 break
17 ok = s >= 0
18 sigma[q, v], nxt[q, v] = ok, s
19 return sigma, nxt
20
21def 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 step
26 v = int(np.argmax(z))
27 if v == eos:
28 return out
29 out.append(v)
30 q = nxt[q, v]
31 raise RuntimeError("budget exhausted before an accepting state")
32
33# Regex [0-9]+ over a toy vocabulary
34vocab = ["7", "42", "4a", " ", "<eos>"]
35step = lambda q, ch: 1 if ch.isdigit() else -1
36sigma, 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 EOS
39print([vocab[v] for v in constrained_greedy(fake, sigma, nxt, eos=4)]) # ['42']
Build the index from any character-level DFA and run masked greedy decoding (numpy, runs as is). Real libraries derive the DFA from the regex and decode token strings with the tokenizer's own byte mapping

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: mv=−∞m_v=-\infty for v∉σ(qt)v\notin\sigma(q_t), renormalise, sample; EOS only in accepting states.
  • ✓FSM index (Willard & Louf, 2023): ∣Q∣⋅∣V∣|Q|\cdot|V| 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 p(y∣y∈L)p(y\mid y\in L); large removed mass signals a schema–model conflict.
← back to Generative AI roadmap