# 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.

Source: https://www.mlfoundry.in/learn/constrained-decoding  
Section: Generative AI › Decoding and Generation Control  
Level: advanced · 8 min read · updated 2026-10-21

**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

$$
\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}
$$

- $z_v$: the model's logit for token $v$ after any other logit processors
- $q_t$: the automaton state reached by the text generated so far
- $\sigma(q)$: the set of tokens allowed in state $q$; end-of-sequence is in it only if $q$ is accepting
- $\tilde p$: equal to $p$ restricted to $\sigma(q_t)$ and divided by the kept mass $\sum_{v\in\sigma(q_t)}p(v)$

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

$$
\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)$: the character string of token $v$
- $\delta^*$: $\delta$ applied character by character; undefined if any character leads to the dead state

Building the index costs $|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.

> Figure: 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 $\tilde p(y)=\prod_t p(y_t\mid y_{<t})/Z_t$, where $Z_t$ is the kept mass at step $t$. This is not $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.

> Figure: 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:

Kept mass Σ p over allowed tokens = 0.4462, so p̃ = p / 0.4462

| 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 $\sigma(10)$ contains only `}`. The next step is forced regardless of the logits, and then only end-of-sequence is allowed.

```python
import numpy as np

def build_index(step, n_states, vocab, accept, eos):
    """sigma[q] = boolean mask over the vocabulary; nxt[q][v] = state after token v."""
    sigma = np.zeros((n_states, len(vocab)), dtype=bool)
    nxt = np.full((n_states, len(vocab)), -1)
    for q in range(n_states):
        for v, tok in enumerate(vocab):
            if v == eos:
                ok, s = q in accept, q
            else:
                s = q
                for ch in tok:              # a token may cross several grammar symbols
                    s = step(s, ch)
                    if s < 0:
                        break
                ok = s >= 0
            sigma[q, v], nxt[q, v] = ok, s
    return sigma, nxt

def constrained_greedy(logits_fn, sigma, nxt, eos, max_new=32):
    q, out = 0, []
    for _ in range(max_new):
        z = logits_fn(out).astype(float)
        z[~sigma[q]] = -np.inf             # the mask: one vector op per step
        v = int(np.argmax(z))
        if v == eos:
            return out
        out.append(v)
        q = nxt[q, v]
    raise RuntimeError("budget exhausted before an accepting state")

# Regex [0-9]+ over a toy vocabulary
vocab = ["7", "42", "4a", " ", "<eos>"]
step = lambda q, ch: 1 if ch.isdigit() else -1
sigma, nxt = build_index(step, 2, vocab, accept={1}, eos=4)
print(sigma.astype(int))   # [[1 1 0 0 0] [1 1 0 0 1]]
fake = lambda out: np.array([0.1, 0.5, 2.0, 1.0, 3.0 if out else -9])  # prefers "4a", then EOS
print([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

> **Valid is not correct:** The mask guarantees syntax, not content. A model forced into `"age": ` when the document gives no age will still write a number. Add nullable fields or an explicit "unknown" enum so the model has an honest valid option. Watch the per-step removed mass too: when it is large, the constraint is fighting the model, and the output is often wrong even though it parses.

> **Let it think, then constrain:** Format restrictions can hurt reasoning: Tam et al. (2024, "Let Me Speak Freely?") report lower accuracy on reasoning tasks under strict JSON formats. A common fix is a schema whose first field is free text ("reasoning") and whose final fields are constrained, or two calls: one free, one constrained extraction.

**Strengths**

- 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.

**Limitations**

- 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.

**Question:** Why does the FSM index walk each token's full character string instead of mapping each grammar terminal to a token?

- A. Because DFAs cannot represent single characters
- B. Because one token can span several grammar symbols (e.g. `": `) or stop partway through one, so validity depends on the whole string
- C. Because the tokenizer is applied after decoding
- D. To make the mask differentiable

**Answer:** B. Because one token can span several grammar symbols (e.g. `": `) or stop partway through one, so validity depends on the whole string — Tokens are learned from data and ignore grammar boundaries. `": ` closes a key, adds a colon and a space in one step. `100` passes two digit transitions and dies on the third character. Only walking the characters through $\delta$ tells you which state a token leads to, or that it leads nowhere.

**Question:** At some step the mask removes 90% of the probability mass. What does that suggest?

- A. Nothing: renormalisation fixes it
- B. The model's preferred continuation conflicts with the schema, so check the prompt, the schema or the data for a mismatch
- C. The temperature is too low
- D. The DFA has too many states

**Answer:** B. The model's preferred continuation conflicts with the schema, so check the prompt, the schema or the data for a mismatch — $\tilde p$ is always a valid distribution, but a small kept mass means the allowed tokens were all unlikely under the model. In the toy, step 5 removes 0.761 because the model wanted to write " years" after the number. Large removed mass is a useful diagnostic for prompts and schemas that disagree.

**Key points**

- Mask: $m_v=-\infty$ for $v\notin\sigma(q_t)$, renormalise, sample; EOS only in accepting states.
- FSM index (Willard & Louf, 2023): $|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\mid y\in L)$; large removed mass signals a schema–model conflict.

---

From MLFoundry (https://www.mlfoundry.in). The web page adds interactive figures and diagrams.
