Structured Generation: How Constrained Decoding Actually Works
Every production LLM pipeline eventually hits the same wall: the model emits text, but the next stage needs JSON. Or a SQL query. Or a Python expression. Or a string matching ^\d{4}-\d{2}-\d{2}$. And no matter how good your prompt is — temperature zero, three-shot examples, "ALWAYS respond with valid JSON" in caps — a fraction of outputs come back with a missing comma, a hallucinated key, a stray "Sure, here's your JSON:" preamble. Structured generation fixes this at the decoding layer: at each step, you mask the tokens that would break the format, leaving the model no choice but to emit something valid.
Learning Objectives
After this lesson, you will be able to:
Explain why prompting alone never gets you to 100% schema-valid output, and why constrained decoding does
Walk through the FSM / PDA mechanics that turn a regex or JSON schema into a per-step token mask
Compare ahead-of-time approaches (Outlines, xgrammar) against runtime approaches (lm-format-enforcer) and pick the right one
Diagnose when structured generation hurts output quality, and apply mitigations (soft constraints, mixed prompting, two-pass)
See that tool-calling APIs from every major provider are just structured generation with a fixed schema
The single biggest mental shift in this lesson: structured generation is not a clever prompt or a post-processing step. It happens inside the decoder, between the softmax and the sampler, and that is the only place it can actually guarantee anything.
Look at the email line. The closing quote is missing. Your JSON.parse() throws. The ticket fails. Multiply this by 50,000 tickets a day and you have a real engineering problem.
Type errors: the schema wanted a number but the model returned "142.50" as a string.
Hallucinated keys: the model invents "customer_id" because that's what training data looked like, even though your schema doesn't include it.
Prefix junk:"Sure, here is the extracted JSON:\n\n{...}" — the entire response is unparseable because the model is being conversational.
Trailing junk: the JSON is fine, then the model adds "Let me know if you need anything else!" after the closing brace.
Even on a state-of-the-art model with a clear schema, you will see all five categories in a sample of a few thousand outputs. The base rate is small but non-zero, and small-but-non-zero compounds catastrophically when you chain LLM calls.
What Do You Think?
You ask GPT-4 to return valid JSON, set temperature to 0, give three example outputs, and add 'ALWAYS respond with strict JSON, no preamble' to the system prompt. What is the realistic floor for schema-violation rate on a moderately complex schema across 10,000 calls?
The intuitive engineering reaction is to keep tightening the prompt. People try, roughly in this order:
Add "Respond with valid JSON only." to the system prompt.
Add few-shot examples of correctly-formatted outputs.
Lower the temperature to 0.
Add a JSON schema in the system prompt and say "match this exactly."
Add a retry loop: on JSON.parse failure, re-run with the parse error appended.
Switch to a bigger model.
Every one of those reduces the error rate. None of them eliminate it. Even GPT-4 with temperature 0, three-shot examples, and an explicit schema produces invalid JSON at a measurable rate on complex schemas. The retry loop usually saves you, but it doubles your cost and latency on the unlucky percentage, and on agents that chain ten LLM calls the compound failure rate is brutal.
The deeper reason: the model's probability distribution just doesn't put zero mass on the invalid completions. As long as P(invalid_token) > 0, sampling — even temperature-zero argmax sampling — can hit the bad path. The only way to make the bad path impossible is to make it literally unreachable. That is what constrained decoding does.
Strip away all the engineering and the core algorithm is six lines:
state = initial_state_of_grammar
output = []
while not finished:
logits = LLM.forward(output) # shape (V,)
valid_mask = grammar.valid_tokens(state) # shape (V,) of booleans
logits[~valid_mask] = -inf
token = sample(softmax(logits))
state = grammar.advance(state, token)
output.append(token)
That is the entire idea. Everything else in this lesson is about making the two grammar calls — valid_tokens(state) and advance(state, token) — fast enough and general enough to use in production.
There are three flavors of "grammar" worth knowing:
Regex. For things like phone numbers, dates, hex colors, classification labels. The grammar is a finite state machine (FSM).
JSON schema. For structured outputs with nested objects and arrays. The grammar is context-free; you compile it to a pushdown automaton (PDA) or use an Earley parser.
Arbitrary CFG. For emitting Python, SQL, or a domain-specific language. Same machinery as JSON, just a different grammar input.
For the rest of this lesson, we will walk through the FSM case in detail (it is the cleanest), then build up to PDA/CFG, then compare the implementations.
A regex compiles to an FSM. States are nodes, characters are edges. The FSM is in one state at any time; reading a character either moves it to a new state (valid transition) or fails (invalid character).
For constrained decoding, we want a slightly different question: given the current FSM state, which tokens (not characters) are valid? That is the only difference from textbook regex matching.
Now, here is the wrinkle. The LLM doesn't emit characters — it emits tokens. With a BPE tokenizer, "2024" might be one token, or it might be "20" + "24", or "2" + "02" + "4". The mask we need is not "which characters are valid?" — it is "which tokens, expanded to character sequences, would leave us in a state from which the rest of the regex is still satisfiable?"
That last condition matters. A token like "-12" (dash, one, two) might be perfectly fine to emit from state q_4 (the model is at the first dash), because reading it walks the FSM q_4 → q_5 → q_6 → q_7, all valid. So "-12" is a valid token even though it contains three characters at once.
This is why the precomputation step in Outlines walks every token in the vocabulary, simulates the FSM, and records the result: Allowed[state][token_id] = True if and only if that token's full character string forms a valid transition path from that state.
Loading visualization...
What you should notice when you run the playground:
From state 0 (we just started), the valid tokens are digit-only chunks: "0", "2", "20", "2024", etc. The token "-" is forbidden — emitting a dash here would break the regex immediately.
From state 4 (we have emitted four digits), only "-", "-01", "-12", "01-15"-style tokens are valid — anything that starts with a dash, possibly followed by digits and another dash.
The "junk" tokens — "Sure", "the", "{", " " — are forbidden from every state. The model cannot accidentally drift into English no matter what its logits say.
This is the whole trick. The model still produces logits over 100k tokens. We zero out the forbidden ones, and what's left is guaranteed to advance the FSM.
#JSON-Schema Constrained Sampling: From FSM to PDA
JSON is not regular. The language {"a": {"b": {"c": ...}}} allows arbitrarily deep nesting, and no finite-state machine can match unboundedly nested brackets — you need a pushdown automaton (PDA), which is an FSM plus a stack.
The standard trick: every time you enter a {, push "expecting a }" onto the stack. Every time you enter [, push "expecting a ]". When you see } or ], pop and check it matches. This is exactly how a CFG parser works.
For constrained sampling, the state is now (grammar_state, stack) rather than just grammar_state. Otherwise the algorithm is identical:
state = (initial_grammar_state, [])
while not finished:
logits = LLM.forward(output)
valid_mask = grammar.valid_tokens(state) # now considers the stack
logits[~valid_mask] = -inf
token = sample(softmax(logits))
state = grammar.advance(state, token)
output.append(token)
A JSON schema adds an additional layer: it not only enforces JSON syntax, it enforces a specific structure. The schema {"type": "object", "properties": {"name": {"type": "string"}, "age": {"type": "integer"}}, "required": ["name", "age"]} is compiled into a grammar that, at the point right after {"name": "...",, can only emit "age":. The schema-aware grammar fuses the JSON CFG with the property-name DFA.
What Do You Think?
You configure your inference server with JSON mode (any valid JSON allowed) vs JSON-schema mode (must match a specific schema). Which is more restrictive — and therefore which is more likely to suppress useful model output?
Walking the full JSON CFG is intricate, but the core algorithm is small enough to play with directly. Let's build one for a fixed schema with two keys.
Loading visualization...
Run it once, then change the seed to random.seed(42), then random.seed(0). The fake LLM's "preferences" change completely. The "top unconstrained" column will be wildly different on each row. But the picked column always produces {"name": "...", "age": ...} — because the mask forbids every other path.
This is a toy linear grammar, but the same idea scales: a real JSON-schema PDA tracks (grammar_state, parser_stack, schema_position) and walks the same logit-mask-sample loop. The mask is bigger, the bookkeeping is more involved, but the algorithm is unchanged.
#Two Implementation Camps: Ahead-of-Time vs. Runtime
Once you accept the core algorithm, the only engineering question is when do you compute the mask?
Ahead-of-time (Outlines, xgrammar)
Compile the grammar to an FSM/PDA.
For every (state, token) pair, precompute whether the token is valid.
Store the result as a fast lookup table.
At inference, the mask is an O(1) table read per step.
Pros: essentially zero per-token overhead. Best fit for high-throughput serving.
Cons: compilation can be slow (seconds to tens of seconds for complex schemas). Table can be megabytes. New schemas need re-compilation.
Runtime (lm-format-enforcer, llguidance partly)
Keep the grammar as a parser data structure.
At each step, walk the parser forward with each candidate token to see if it succeeds.
Build the mask on the fly.
Pros: No compile cost. Handles dynamic grammars (regex generated per request). Lower memory.
Cons: Higher per-token CPU cost. Less amenable to GPU acceleration.
Hybrid (xgrammar, llguidance)
Precompute as much of the grammar trace as possible.
Handle the BPE-token-to-grammar-token alignment inside a CUDA kernel that fuses with the softmax.
Pros: approaches zero overhead even for huge schemas.
Cons: the implementation is genuinely intricate; not all inference servers support it yet.
What Do You Think?
You measure inference throughput with Outlines-style precomputed masking on a vLLM-served Llama-3-8B, comparing constrained vs unconstrained generation. The schema is a moderately nested JSON object. What is the realistic throughput overhead in tokens/sec?
Quick check
A team wants to constrain output to valid Python expressions (full Python grammar, with arbitrary nesting). Which is the correct fit?
If you're calling an inference API rather than implementing this yourself, you'll see four distinct modes — each is a different grammar input feeding the same underlying constrained-decoding engine.
Mode
Grammar input
What it guarantees
Example use
JSON mode
Any-valid-JSON CFG
Output parses as JSON
"Give me a JSON response" without specifying schema
JSON-schema mode
Specific JSON schema
Output matches a typed, keyed structure
Tool calls, structured extraction, form filling
Regex mode
Arbitrary regex
Output matches the regex character-by-character
Phone numbers, ISO dates, classification labels
Grammar mode
Arbitrary CFG (e.g., Lark, EBNF)
Output is in the formal language
Emit valid SQL, Python, custom DSLs
OpenAI's "Structured Outputs" (Aug 2024) is JSON-schema mode. Anthropic's tool_use is JSON-schema mode with a fixed envelope. Google's responseSchema in Gemini is JSON-schema mode. vLLM and TGI expose all four. Outlines and xgrammar expose all four when used directly.
The reason all four are the same machinery: every one of them compiles to either an FSM (regex) or a PDA (the rest), feeds into a valid_tokens(state) function, and the rest of the algorithm is identical.
Structured generation is not free of side effects on output quality. The constraint is hard, but the model is not always happy about it.
Failure 1: Forced low-probability tokens. The grammar says you must emit } right now. The model's top-100 candidates are all other tokens — maybe it was about to write , "extra_field": "..." because that's what training data suggested. The valid token } had probability 1e-7 before masking. After masking, it has probability 1.0 — but only because everything else is -inf. The output is valid but the next step's context now starts from an unusual place. Quality can degrade noticeably.
Failure 2: Capability bleed. If you force JSON-only output starting from the first token, you've stripped the model of its chain-of-thought. There's no room to "think out loud" before producing the structured answer. For reasoning-heavy tasks, this can drop accuracy by 5–15 percentage points. It is a real, measurable effect.
Failure 3: Schema impossibility / deadlock. Some JSON schemas, particularly ones using oneOf without a discriminator, can put the parser into a state where the model has emitted a prefix that matches multiple branches but no branch is yet determined — and the next token must commit. If the model's high-probability tokens don't disambiguate, the parser stalls or makes a bad arbitrary choice. Practical fix: always use anyOf with a discriminator field, or use oneOf only when one branch is clearly distinguished by its first key.
What Do You Think?
Mid-generation, the schema says the next token MUST be ']' (we are closing an array of integers). But the model's top-1 unconstrained candidate was the digit '5' — it wanted to keep generating numbers. Constrained decoding forces ']'. What happens to the quality of the rest of the output?
#Mitigations: Getting Structure Without Sacrificing Quality
The fact that constraints can degrade quality is a real engineering problem, and the field has converged on a small set of mitigations.
Mitigation 1: Soft constraints (logit bias). Instead of -inf on forbidden tokens, add a large negative bias (e.g., -10). At temperature > 0, the model can still emit a "forbidden" token if its logit was overwhelmingly high — but in practice almost never does. This is mostly useful when you want to strongly prefer a structure but tolerate occasional drift, e.g., for creative tasks.
Mitigation 2: Mixed prompting. Split the output into "free-form thinking" and "structured answer" regions. Use a tag like <thinking>...</thinking><answer>{...}</answer>. Apply constraints only inside the <answer> block; let the <thinking> block be unconstrained. This is how Anthropic's tool_use and OpenAI's reasoning models preserve chain-of-thought while still emitting strict tool-call JSON. The grammar is essentially: <thinking>.*</thinking><answer>SCHEMA</answer>.
Mitigation 3: Two-pass generation. First pass: generate free-form natural-language output (no constraints). Second pass: ask a smaller, cheaper model to extract the structured fields from the first output, with constrained decoding on the extractor. This is great for high-stakes outputs where quality matters more than latency, and where the structured shape is a thin "post-processing" layer over the reasoning.
Mitigation 4: Schema design. Many failures come from schemas that put the constraint in a position the model wouldn't naturally arrive at. Concrete tactics: put high-information keys first; avoid required-but-rarely-relevant fields; use enums with the natural-language-preferred option first; allow optional fields rather than forcing the model to invent values.
Quick check
Your team wants reliable JSON output from a reasoning task. Output quality with hard JSON-from-step-1 constraints is noticeably worse than unconstrained. When does using soft constraints (logit bias instead of -inf) actually help?
#Tool-Calling Is Just Structured Generation Wearing a Hat
Once you understand the underlying mechanics, every "tool use" or "function calling" API across providers reveals itself as the same trick with a fixed outer schema.
When you write:
json
{
"tools": [{
"name": "get_weather",
"description": "Get the current weather in a city",
"parameters": {
"type": "object",
"properties": {
"city": {"type": "string"},
"unit": {"type": "string", "enum": ["celsius", "fahrenheit"]}
},
"required": ["city"]
}
}]
}
The provider's server compiles this into a JSON-schema grammar of approximately:
It then applies constrained decoding on the model's output, masking every token that wouldn't fit this template. That is why tool-calling outputs from OpenAI's Structured Outputs, Anthropic's tool_use, and Google's function calling are 100% schema-valid — they aren't "the model got better at JSON," they're constrained decoded under the hood.
Three useful corollaries:
The token-overhead cost of tool-calling is approximately the cost of the schema compilation amortized across requests — small in steady state.
Tool-calling failures you still see in production (unit: "celcius" is a real spelling, but not in your enum) are typically schema design issues, not LLM failures — your enum allowed a misspelled member, or the model "successfully" matched a too-permissive type.
The same mechanism makes "force the model to choose one of these tools and never refuse" possible: just constrain the very first key to "name" and the value to your enum of tool names. The model literally cannot emit anything else.
Putting it all together, here is the configuration that ships well in 2026:
Use constrained decoding for any output that downstream code parses. Not "sometimes," not "with a retry loop" — by default.
Use mixed prompting for any task with reasoning content: <thinking>...</thinking><answer>STRUCTURED</answer>. Apply the schema only inside the answer block.
Prefer xgrammar or Outlines at the inference layer if you control the server; prefer the provider's native Structured Outputs / tool_use if you don't.
Design schemas for the model, not just for downstream code. High-information keys first, enums ordered by frequency, optional rather than required fields where defensible, discriminator fields on every oneOf.
Measure both validity and quality. Validity should be 100%. Quality should be compared head-to-head with unconstrained output on a real eval set; if it dropped, look at your schema and your mixed-prompting setup before blaming the technique.
Recap
Key Takeaways
1Prompting alone cannot reach 100% schema validity — there is always residual mass on invalid token sequences. Constrained decoding is the only known fix.
2The core algorithm is six lines: at each step, compute valid_tokens(state), mask invalid logits to -inf, sample, advance the state machine.
3Regex constraints compile to FSMs; JSON-schema and arbitrary grammars compile to PDAs. The decoding loop is identical; only valid_tokens differs.
4Ahead-of-time approaches (Outlines, xgrammar) precompute Allowed[state][token] tables for ~0 inference overhead. Runtime approaches (lm-format-enforcer) trade speed for flexibility.
6Tool-calling APIs across OpenAI, Anthropic, Google are all constrained decoding with a fixed envelope schema — same machinery, different presentation layer.