$ cat ai-engineering/constrained-decoding.md

Constrained Decoding: Grammars, Regex, and FSMs

How vocabulary masks, finite-state machines, grammars, and schema compilation constrain model output.

Jatin Bansal@blog:~/ai-engineering$ open constrained-decoding

Constrained decoding masks tokens that would violate a schema or grammar before sampling. It can eliminate syntactically invalid JSON, but the mask also changes the output distribution. Tight constraints on open-ended fields can reduce answer quality even when every response validates.

Vocabulary masks at decode time

Constrained decoding is sampling with a per-step vocabulary mask. At every decode step, before the sampler picks a token, an external automaton; usually a finite-state machine for regex/JSON schema, or a pushdown automaton for full context-free grammars; is consulted: “given the tokens we’ve emitted so far, which of the 200,000 tokens in the vocabulary are legal next?” Every illegal token has its logit set to -inf, the softmax assigns it zero probability, and the sampler can no longer pick it.

The update is logits := logits + mask, where mask[i] ∈ {0, -inf}. Logit biasing uses a constant mask. JSON Schema can compile to an FSM whose state changes the mask at each step. Context-free grammars require stack state, usually represented with a pushdown automaton.

The LLM inference fundamentals article framed sampling as softmax(logits / T) with optional top-k or top-p truncation. Constrained decoding is that same step with a third truncation: a structural one applied before temperature kicks in. The model still chooses among legal tokens by probability; constrained decoding does not select for you, it only forbids the impossible.

Constraint mechanisms

Logit bias (constant mask). The oldest and weakest form. You pass a token-ID-to-bias map; the provider adds the bias to the matching logits on every step. Set bias to -100 to effectively forbid a token, +10 to strongly encourage one. OpenAI exposes logit_bias on the chat and completions APIs. Anthropic does not. The mechanism is too coarse to enforce structure; you can ban “I cannot” or force the model toward “yes” or “no”, but you cannot express “must be a valid date” because that requires the mask to change depending on what’s been emitted so far. Logit bias is still useful: profanity blocklists, A/B-test answer keys, banning a known hallucination pattern. It is not constrained decoding in the structural sense; it is structural decoding’s degenerate one-state case.

FSM-based constraint (regex / JSON Schema). A regular expression compiles to a deterministic finite automaton: a finite set of states, a transition function state × character → state, an accept set. JSON Schema in strict mode (objects with fixed properties, enums, format validators, primitive types) is regular too; you can compile a strict schema to a single regex and from there to an FSM. The trick that makes this fast at LLM serving time is a precomputed index: for every state of the FSM and every token in the vocabulary, you precompute “if I’m in state s and I emit token t, am I still in the language? and what state do I land in?” Store the result as a sparse matrix and the per-token cost becomes a constant-time lookup plus a vocabulary-sized mask write. Outlines was the canonical implementation of this idea; the Rust core outlines-core ships the FSM compiler with worst-case microsecond-per-token overhead.

Pushdown automaton (context-free grammars). Regex isn’t powerful enough for full JSON (nested objects of arbitrary depth) or any real programming-language grammar. Context-free grammars are. The corresponding machine is a pushdown automaton: an FSM plus a stack. To match { "a": { "b": [...] } } the automaton pushes a frame for each { or [ and pops it on the matching } or ]. Compiling a grammar to a PDA and then masking the vocabulary per step is the technique XGrammar pioneered, now integrated into vLLM, SGLang, and TensorRT-LLM. llama.cpp’s GBNF grammars and guidance-ai’s llguidance implement the same primitive with different syntax. The “G” in GBNF is “GGML”; the BNF is real BNF; same notation that defines C and SQL grammars. You can constrain a model’s output to literally any context-free language. That’s the killer feature: SQL queries, valid Python ASTs, formal proof languages, custom DSLs.

The relationship between these three is a Chomsky hierarchy: every regular language is context-free, every context-free language permits pushdown recognition. Pick the cheapest tool that expresses your constraint. Don’t reach for a grammar to enforce ["USD", "EUR", "GBP"]; an FSM-backed enum is faster and trivially equivalent.

Compile JSON Schema into a mask

Walk through one concrete pipeline end to end.

Schema → regex (or pseudo-regex): A strict JSON Schema is compiled into a structural regex: \{ followed by "name": followed by [A-Za-z0-9 ]{1,32} followed by ,"age": followed by \d{1,3} followed by \}. Real implementations don’t emit literal regex strings; they emit an intermediate AST that gets compiled to an FSM directly. But thinking of it as a regex is the right mental model.
Regex → FSM: Standard Thompson/Glushkov construction. Each character class becomes a transition; each {n,m} repetition becomes a counter; the final state is the accept set.
FSM × vocabulary → mask index: For every state s in the FSM and every token t in the vocabulary, compute whether the byte sequence of t can be appended to a string that ends in state s and still potentially complete to a string in the language. If yes, store the resulting next-state; if no, mark (s, t) as forbidden. This is the expensive precomputation step; for a 100k-token vocabulary and a moderately complex schema, it takes 50–500ms on first compile. Most production stacks cache the result keyed on (schema_hash, tokenizer_hash).
At decode time: The runtime tracks the current FSM state. Before sampling, it looks up the row for that state in the mask index and adds -inf to every forbidden token’s logit. The sampler picks a legal token; the runtime advances the FSM state; repeat until the accept state is reached or max_tokens exhausts.

The whole machine runs entirely on the host side of the inference loop; no model retraining, no architectural change, no quality cost from the structural constraint itself (we’ll get to the behavioral cost later). XGrammar’s contribution was figuring out how to do the per-step PDA computation in <40 microseconds even for grammars with hundreds of productions; its trick is overlapping the mask computation with the GPU’s logit computation so the structural overhead becomes invisible at the throughput level.

Code: Python with Outlines on a self-hosted model

Outlines is the workhorse on the Python side for local-model constrained decoding. It supports JSON Schema, regex, and context-free grammars (EBNF / Lark) through a unified surface. Install: pip install outlines transformers torch.

python

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
# pip install outlines transformers torch
import outlines
from transformers import AutoModelForCausalLM, AutoTokenizer
from pydantic import BaseModel, Field
from typing import Literal

MODEL_NAME = "Qwen/Qwen3-4B-Instruct"

model = outlines.from_transformers(
    AutoModelForCausalLM.from_pretrained(MODEL_NAME),
    AutoTokenizer.from_pretrained(MODEL_NAME),
)

# 1) JSON Schema constraint via Pydantic
class Triage(BaseModel):
    category: Literal["billing", "technical", "account", "other"]
    severity: Literal["low", "medium", "high", "critical"]
    needs_human: bool
    summary: str = Field(min_length=10, max_length=200)

prompt = "Customer email: 'My card was charged twice for the same order #4421. Refund please.'"
result = model(prompt, Triage)
print(result.model_dump())  # guaranteed-conforming Triage object

# 2) Regex constraint — phone number in a specific format
phone_regex = r"\+\d{1,3}-\d{3}-\d{3}-\d{4}"
prompt = "Extract the phone number from: 'Call us at +1-415-555-2671'"
phone = model(prompt, outlines.Regex(phone_regex))
print(phone)  # +1-415-555-2671 — pattern is enforced at decode time

# 3) Context-free grammar — a tiny arithmetic-expression language
arithmetic_grammar = """
?start: expr
?expr: term (("+" | "-") term)*
?term: factor (("*" | "/") factor)*
?factor: NUMBER | "(" expr ")"
NUMBER: /[0-9]+/
%ignore " "
"""
prompt = "Write an arithmetic expression that evaluates to about 100, using only +,-,*,/,(),digits:"
expr = model(prompt, outlines.CFG(arithmetic_grammar))
print(expr)  # always parses as a valid expression in our grammar

Use the Pydantic path for ordinary structured records, Regex for bounded string formats, and a CFG for nested or language-like output. These constraints guarantee syntax accepted by the selected recognizer; they do not guarantee semantic correctness or safe execution.

A small wrinkle the Outlines docs call out: the model’s reasoning quality tends to be best when the schema is loose where reasoning happens and tight where structure matters. If you’re using a summary field that the model needs to think into, don’t max_length: 30 it; give it room to breathe. The format tax (below) is real but mostly avoidable.

Provider-side constrained decoding vs running it yourself

The cloud frontier providers expose constrained decoding through the strict-schema modes covered in the structured-output article; OpenAI’s response_format: {type: "json_schema", strict: true}, Anthropic’s strict tool use, Gemini’s response_schema. These are FSM-based JSON Schema constraints behind a managed API; you don’t see the FSM, you don’t get to pick the backend, you can’t supply a custom grammar. They cover the 80% case (typed objects, enums, structured payloads) and are the right default whenever you’re calling a hosted model.

You drop down to a self-hosted stack; Outlines, vLLM + XGrammar, llama.cpp + GBNF, llguidance; when you need one of:

Arbitrary CFGs: SQL, custom DSLs, programming-language ASTs. The hosted strict modes only accept JSON Schema.
Open-weights models: Llama, Qwen, Mistral, DeepSeek. The model lives on your hardware; the constraint engine lives next to it.
Cost-sensitive bulk extraction: A 100M-document extraction pass against a 4B-parameter model on your own GPUs can be an order of magnitude cheaper than the same workload through a frontier API, and constrained decoding lets you eat the quality gap on structure.
Determinism and reproducibility: Frontier providers occasionally update their strict-mode compilers; self-hosting pins the constraint behavior to a specific software version, useful for compliance-relevant pipelines.

The line between the two is moving fast. As of mid-2026 XGrammar-2 has been adopted by leading frontier labs in their products, so the engine behind “strict mode” on hosted APIs is increasingly the same code you’d run yourself. The decision boundary is operational (hosted vs self-hosted), not algorithmic.