Structured output and constrained decoding
An agent is only as useful as the program that reads its output. Constrained decoding guarantees the shape of that output by masking the sampler at every step, so an invalid token simply has zero probability. This part follows the machinery from a regular expression to a finite-state machine to the per-state bitmask applied over a 150K-wide vocabulary — and prices what the guarantee costs.
What it guarantees and what it does not
The contract, precisely stated
Constrained decoding guarantees syntactic validity: every emitted token sequence is accepted by a grammar, regex, or schema. It does not guarantee semantic correctness. A model can produce perfectly valid JSON whose numbers are hallucinated, whose enum value is the wrong one, or whose required field is filled with an empty string. It also does not guarantee termination — a grammar that permits unbounded strings can loop — and it does not make the model faster or smarter; it makes an invalid sample impossible.
- Every prefix parses under the grammar.
- Required fields and enum sets are respected exactly.
- Malformed output is unreachable, not merely unlikely.
- A downstream parser never needs a repair pass.
- That the values are true or useful.
- That generation terminates within your token budget.
- That quality is unchanged — masking reshapes the distribution.
- That the tokenizer can express the grammar cleanly.
This is the serving-side partner to tool calling and agents: the training guide covers why a model is taught to emit structured calls, and everything below is how the serving stack makes the shape of those calls a hard constraint rather than a hope. It is also the mechanism behind every "JSON mode" and function-calling endpoint you have used.
Regex to FSM to per-state masks
The mask is just the transition set
A regular expression compiles to a finite-state machine: states, and transitions labelled with the input that moves between them. At generation time the decoder is in exactly one state, and the allowed next tokens are precisely the tokens that label an outgoing transition. Everything else is masked to negative infinity. The engine does not "understand" the grammar per token — it looks up a precomputed set.
Pick a pattern, then step. The highlighted state determines the allowed tokens.
Why JSON needs a pushdown automaton
A regular expression cannot count
JSON is not regular. The set of valid JSON documents requires matching nested braces and brackets to arbitrary depth, and a finite-state machine cannot count unboundedly. The standard fix is a pushdown automaton: an FSM plus a stack, where entering { or [ pushes a context and the matching close pops it. The mask at each step depends on both the current parser state and the top of the stack — which is why JSON-schema engines are described as grammar-constrained and not merely regex-constrained.
Bright cells are tokens the schema permits right now. Take steps and watch the stack grow when an array opens.
Compiling a schema and caching the precompute
Pay once, not per token
The expensive part of constrained decoding is not applying the mask; it is building the parser and the token-indexed transition table. A naive engine runs the grammar over the vocabulary at every step — that is where the 40–150 microsecond overhead band comes from and why early implementations were unusable. Production engines compile the grammar once, then precompute, for each parser state, a bitmask over the vocabulary. Applying a step becomes a lookup plus a boolean AND.
Applying a 150K-wide bitmask per token
The bandwidth of a boolean
The mask is a bit vector as wide as the vocabulary. For a 128K-token vocabulary plus special tokens, that is roughly a 150K-wide mask — about 18 KB in packed form. Masking is a single fused subtraction of a large constant from the logits or an addition of negative infinity, executed on the GPU with the sampling kernel. The arithmetic is trivial; the engineering is alignment. The mask must be generated on the host or in a way that does not force a device synchronization in the middle of the decode loop, because a stall on every token would cost more than the mask itself.
Jump-forward decoding
When the grammar leaves no choice, skip the forward passes
If the current state has exactly one allowed token, the model does not need to run a forward pass to discover it — the grammar already knows. Jump-forward decoding emits the entire deterministic span in one step. Consider a partial key: after {"na the grammar forces me":, so the engine emits that whole chunk at once instead of spending a forward pass per character. The gain is proportional to how much of the schema is deterministic, which is why it is largest for JSON, function calls and templates, and near zero for free-form prose.
Each marker is a model forward pass. Jump-forward collapses deterministic runs.
The constraint tax
A per-sequence mask does not amortise
Here is the subtlety that bites at scale. Engines batch many sequences into one decode step, and almost every other per-sequence cost — the KV read, the attention — is shared or amortised across the batch. A grammar mask is not, because each sequence sits at its own parser state and therefore needs its own bitmask. At batch 1 the mask is a rounding error; at batch 256 the mask work has grown linearly while the step time grew more slowly, so its share of the step rises instead of falling. Some engines claw this back by batching sequences that share a parser state into one mask, but that only helps when states happen to coincide.
Mask compute as a share of the decode step, per-sequence versus state-shared, across batch size.
Tokenizer-alignment traps
The grammar is over characters; the model emits tokens
This is the deepest practical hazard. A grammar is usually defined over characters or bytes, but the model emits tokens that may span several characters and may be partially inside a grammar rule. A correct system must know, for each token, the set of parser states reachable when that token is appended — the mask is a union over all token continuations, not a character-at-a-time check. Get it wrong and you either block valid tokens (a schema that can never complete) or allow invalid ones (a guaranteed-valid claim that is false).
- A token that contains both a legal and an illegal continuations must be unioned, not judged on its first character.
- Whitespace inside a JSON string is content; outside it is formatting. A schema that ignores this over-constrains.
- Escape sequences mean the raw bytes and the parsed characters differ — the grammar must run on one consistent view.
- Unicode combining marks and multi-byte characters can split across tokens.
- Precompute a token-to-state-transition table at compile time, over bytes, once.
- Use byte-level grammars so tokenization cannot hide a byte.
- Test every schema against the actual tokenizer before shipping, not just against the regex.
- Keep a validated fallback parser for the rare path where the grammar cannot terminate.
Outlines, XGrammar, LLGuidance
The current engine landscape
Outlines introduced the finite-state-machine indexing approach that made guided generation cheap enough to use in practice, and jump-forward decoding follows from it. XGrammar is the context-free-grammar engine built for production throughput; its paper reports up to 100× acceleration over prior solutions and near-zero end-to-end overhead when mask generation is overlapped with GPU execution, which is the property that lets vLLM and SGLang expose structured output as a default rather than a penalty. LLGuidance is the newer Rust implementation oriented at low-latency JSON-schema and grammar constraints. The trends are consistent: push the per-token work off the critical path, compile aggressively, and cache the state-indexed masks.
Relative per-token mask cost, normalised to the naive re-derive-every-step baseline.
Failure gallery
| Failure | What goes wrong | Fix |
|---|---|---|
| Schema that can never complete | Current prefix plus every vocabulary token leads to a dead state; sampler has no legal move and emits EOS or garbage. | Validate reachability at compile time; raise, do not silently unconstrain. |
| Tokenizer-boundary escape | A multi-character token jumps over a required character, so the mask admits a token that invalidates the parse. | Union transitions over all token continuations; prefer byte-level grammars. |
| Over-constrained JSON | Whitespace and key ordering forced to one canonical form; model quality drops because the natural distribution is masked away. | Permit whitespace and optional keys; constrain structure, not style. |
| Infinite string | Grammar allows an unbounded string; generation never terminates and never hits EOS. | Add max length or a stop condition in the grammar, and enforce an output-token budget. |
| Recursive schema stack growth | Self-referential schema with unbounded nesting grows the PDA stack without limit. | Depth-limit the recursion in the compiled grammar. |
| oneOf ambiguity | A union of subschemas splits the mask so thinly that the model's preferred continuation is excluded. | Flatten to a discriminated union with a literal tag; avoid overlapping branches. |
| Mask/logits device sync | Host-side mask generation forces a synchronize every token, adding latency and draining the pipeline. | Generate masks on-device or overlap with the previous step; batch by parser state. |
| Unsatisfiable required field | Required field is unreachable given the model's tokenizer or the prompt; output loops trying. | Validate the schema against the tokenizer at deploy time; test with real prompts. |
Cheat sheet
| Piece | What it does | Operational note |
|---|---|---|
| Guarantee | Syntax only | Values can still be wrong; termination is not guaranteed |
| Regex → FSM | Allowed tokens = outgoing transitions of the current state | Precompute per-state masks once |
| JSON / CFG → PDA | FSM plus a stack for nesting | Mask depends on state and stack top |
| Token mask | Vocab-wide bit vector (~18 KB at 150K tokens) | Build it without a device sync per step |
| Jump-forward | Emit forced spans without forward passes | Big win for JSON and templates, ~0 for prose |
| Batch cost | One mask per sequence state | Mask share of the step rises with batch |
| Token alignment | Tokens straddle grammar boundaries | Test every schema against the real tokenizer |
Further reading
- Willard & Louf, "Efficient Guided Generation for Large Language Models" (2023) — Outlines and FSM indexing.
- Dong et al., "XGrammar: Flexible and Efficient Structured Generation Engine for Large Language Models" (MLSys 2025).
- Beurer-Kellner et al., "Guiding LLMs The Right Way: Fast, Non-Invasive Constrained Generation" (2024).
- Microsoft, LLGuidance (open source).
- Geng et al., "Grammar-Aligned Decoding" (NeurIPS 2024) — the quality cost of masking.