# Constrained Decoding: Grammars, Regex, and FSMs

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

- Author: Jatin Bansal (https://jatinbansal.com/)
- Published: 2026-05-18
- Canonical: https://jatinbansal.com/ai-engineering/constrained-decoding/
- Topic: AI Engineering

---

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](/ai-engineering/llm-inference-fundamentals/) 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`](https://help.openai.com/en/articles/5247780-using-logit-bias-to-alter-token-probability-with-the-openai-api) 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](https://en.wikipedia.org/wiki/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](https://dottxt-ai.github.io/outlines/latest/) was the canonical implementation of this idea; the Rust core [outlines-core](https://github.com/dottxt-ai/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](https://en.wikipedia.org/wiki/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](https://github.com/mlc-ai/xgrammar) pioneered, [now integrated into vLLM, SGLang, and TensorRT-LLM](https://blog.mlc.ai/2026/05/04/xgrammar-2-fast-customizable-structured-generation). [llama.cpp's GBNF grammars](https://github.com/ggml-org/llama.cpp/blob/master/grammars/README.md) and [guidance-ai's llguidance](https://github.com/guidance-ai/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.

1. 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.
2. 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.
3. 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)`.
4. 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](https://dottxt-ai.github.io/outlines/latest/) 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
# 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](/ai-engineering/structured-output/); OpenAI's `response_format: {type: "json_schema", strict: true}`, [Anthropic's strict tool use](https://platform.claude.com/docs/en/agents-and-tools/tool-use/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](https://github.com/guidance-ai/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](https://blog.mlc.ai/2026/05/04/xgrammar-2-fast-customizable-structured-generation), 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.

## Further reading

- [Aidan Cooper, A Guide to Structured Outputs Using Constrained Decoding](https://www.aidancooper.co.uk/constrained-decoding/); an explanation of the FSM-over-vocabulary technique with worked examples.
- [MLC; XGrammar-2 announcement](https://blog.mlc.ai/2026/05/04/xgrammar-2-fast-customizable-structured-generation); the May 2026 release post for the engine now powering structured outputs across vLLM, SGLang, TensorRT-LLM, and several frontier-lab products. Covers PDA-based grammar batching and cross-grammar caching.
- [llama.cpp GBNF README](https://github.com/ggml-org/llama.cpp/blob/master/grammars/README.md); the canonical reference for the GBNF dialect, which is the de-facto standard for open-weights grammar-constrained generation. Short, dense, useful.
- [OpenAI cookbook; Introducing Structured Outputs](https://openai.com/index/introducing-structured-outputs-in-the-api/); the August 2024 launch piece for hosted strict mode. Worth re-reading for the strict-subset rules that the rest of the industry has converged on.
