Ask an LLM for JSON and you will usually get JSON. “Usually” is the word that ruins your week. One missing brace at token 400, one unquoted string, one hallucinated enum value, and the whole response is garbage that your parser has to reject. Retry loops, validation libraries, and “please return valid JSON” prompting all treat the symptom. The actual fix is to make invalid output impossible at the token level, and that is what constrained decoding does.
This post walks through how constrained decoding actually works, why naive implementations are too slow for production serving, and how the current generation of engines — with XGrammar and its 2026 upgrade XGrammar-2 as the reference design — made structured output effectively free. If you run vLLM, SGLang, or TensorRT-LLM in production, this is the machinery sitting under every response_format parameter you pass.
Token masks: making invalid output impossible
An LLM generates text one token at a time. At each step the model produces a probability distribution over the entire vocabulary — every token gets some probability mass, and the sampler picks one. Nothing in that distribution knows anything about JSON syntax, regex patterns, or your Pydantic schema.
Constrained decoding intervenes between the model and the sampler. Given a target structure — a JSON schema, a context-free grammar, a regular expression — the engine compiles it into a state machine, tracks which states are reachable given the tokens generated so far, and computes a token mask: a binary (or bitwise-packed) vector over the vocabulary where every token that would violate the structure gets its probability set to zero. The model can still decide which valid token to produce, but it physically cannot produce an invalid one. Output correctness stops being a probabilistic claim and becomes a structural guarantee.
One important nuance: constraints limit format, not meaning. A grammar can force the model to emit a city string, but it cannot force that string to be a real city. In practice this distinction matters less than you would expect — format errors were masking genuine capability, and once format failures are eliminated, measured task accuracy on tool-calling benchmarks typically goes up, because no responses are thrown away for parse failures.
Why naive constrained decoding is slow
The straightforward implementation is expensive. Executing a context-free grammar against every token in the vocabulary requires walking stack states across tens or hundreds of thousands of tokens, on every decoding step, for every request. Do that per step and the grammar check can cost more than the transformer forward pass itself.
The XGrammar paper (MLSys 2025) attacked this with a few ideas that now show up in most serving engines:
- Vocabulary partitioning. Most tokens are “context-independent” — whether they are legal depends only on the current grammar state, not on the surrounding parse context. These can be pre-checked once at compile time. Only the smaller set of context-dependent tokens needs runtime interpretation.
- Grammar expansion. Transformations rewrite the grammar to push more tokens into the context-independent category before compilation.
- A persistent stack. Context-dependent checks reuse parse stack states across steps instead of recomputing them, which turns repeated work into cheap backtracking.
- Engine co-design. Mask construction overlaps with GPU execution, so grammar work hides behind the forward pass instead of serializing with it.
The combined effect was reported as up to a 100x speedup over prior approaches, which is what moved constrained decoding from “research demo” to “default backend” in vLLM, SGLang, TensorRT-LLM, and MLC-LLM.
Plain JSON schemas hit a wall in agent workloads
A single JSON schema per request is the easy case. Agents broke it. A modern agent turn is not one structure — it is free-form reasoning, then possibly a tool call in some model-specific wire format, then more free text, then another tool call, with different formats for every model family. OpenAI-style models emit “harmony”-style channels; open-weight models each carry their own tool-call dialect, often XML-flavored, often undocumented at the edges.
XGrammar-2 (released May 2026) addressed this with Structural Tag, a composable JSON protocol for describing these mixed structures. Instead of “the whole response must match this schema”, you describe a sequence: free text until a marker, then a triggered structure whose arguments follow a JSON schema, and so on. A minimal example that forces an <answer> section to contain schema-conforming JSON looks like this:
{
"type": "structural_tag",
"format": {
"type": "tag",
"begin": "<answer>",
"content": {
"type": "json_schema",
"json_schema": {
"type": "object",
"properties": {
"status": { "type": "string" },
"message": { "type": "string" }
},
"required": ["status", "message"]
}
},
"end": "</answer>"
}
}Tags compose: sequences chain sections, triggered tags let the model emit free text until it chooses to start a tool call, and atomic types — JSON schema fragments, regexes, literal strings, token IDs — nest inside each other. The engine ships built-in structural tags for common model formats, so serving layers do not have to hand-maintain a parser per model family.
Agent-scale workloads also exposed an efficiency problem: an agent session can carry dozens or hundreds of tool schemas, and most of them share substructures (every object schema contains the same string-field machinery). XGrammar-2’s cross-grammar cache compiles shared substructures once and reuses them, and repetition-state compression plus batching support keep overhead near zero even for very large grammars. The project reports up to an 80x efficiency gain over its own first release, with 100% schema conformance on tool-calling tasks.
What this looks like from the serving API
You rarely touch XGrammar directly. Engines expose it through their OpenAI-compatible APIs. In vLLM, structured output is controlled via response_format or guided-decoding parameters — see the structured outputs documentation. With an OpenAI-compatible client against a vLLM or SGLang server, passing a structural tag through the extra-body field looks like:
response = client.chat.completions.create(
model="my-model",
messages=messages,
extra_body={
"response_format": {
"type": "structural_tag",
"format": {
"type": "tag",
"begin": "<answer>",
"content": {
"type": "json_schema",
"json_schema": schema_dict,
},
"end": "</answer>",
},
}
},
)On the client-side and local-inference side, libraries like Outlines take a friendlier angle: you pass a Python type — a Literal for classification, an int, or a Pydantic model for complex objects — and the library translates it into the same class of token-mask machinery. The pattern is worth adopting regardless of stack: express the output contract as a type, not as a prompt instruction followed by a parser with a retry loop.
Practical guidance
A few things worth knowing before you constrain everything:
- Keep schemas lean. Deeply nested unions and huge enums still cost compile time and can over-constrain the model into degenerate outputs. If the model has to satisfy an absurd schema, it will satisfy it badly.
- Constrain the format, prompt for the content. The mask guarantees structure; examples in the prompt still drive quality of the content inside it.
- Cache compilation across requests. Serving engines do this for you (that is the cross-grammar cache), but if you build schemas dynamically per request — embedding timestamps or user IDs into schemas — you defeat the cache. Keep the schema stable and put variable data in the prompt.
- Watch for “satisfied but wrong”. A 100% parse rate is not a 100% correctness rate. Keep validating semantics downstream; you are just no longer spending retries on syntax.
The takeaway
Structured output used to be a post-processing problem: generate, parse, fail, retry. The constrained decoding stack — grammar compilation, token masks, and engine integration — moved it into the sampler, where invalid output simply cannot be produced and the overhead has been driven to near zero. If your stack still treats LLM output as unreliable text to be cleaned up after the fact, the fix is no longer a better regex. It is a flag on the request.