Structured Generation: How Constrained Decoding Actually Works

#The Problem: LLMs Hallucinate JSON

You ship a feature that asks the model to extract customer name, email, and order total from a support email. The model returns:

{
  "name": "Sarah Chen",
  "email": "sarah@example.com,
  "order_total": "$142.50"
}

The failure modes are surprisingly diverse:

• Syntactic errors: missing comma, trailing comma, unbalanced brace, broken string escape.
• 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.

#"Just Prompt Better" Does Not Work

The intuitive engineering reaction is to keep tightening the prompt. People try, roughly in this order:

1. Add "Respond with valid JSON only." to the system prompt.
2. Add few-shot examples of correctly-formatted outputs.
3. Lower the temperature to 0.
4. Add a JSON schema in the system prompt and say "match this exactly."
5. Add a retry loop: on JSON.parse failure, re-run with the parse error appended.
6. 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 Constrained Decoding Idea

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)

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.

#Regex-Constrained Sampling: The FSM Case

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).

#A Concrete Walkthrough: Dates

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

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 Tiny JSON Masker

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.

#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 Modes Do Inference Servers Actually Expose?

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.

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.

#Failure Modes: When Constraints Hurt Quality

Structured generation is not free of side effects on output quality. The constraint is hard, but the model is not always happy about it.

#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.

#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:

{
  "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:

{"name": "get_weather", "arguments": {"city": <string>, "unit": <"celsius" | "fahrenheit">}}

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:

1. The token-overhead cost of tool-calling is approximately the cost of the schema compilation amortized across requests — small in steady state.
2. 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.
3. 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.

#A Pragmatic Recipe for Production

Putting it all together, here is the configuration that ships well in 2026:

1. Use constrained decoding for any output that downstream code parses. Not "sometimes," not "with a retry loop" — by default.
2. Use mixed prompting for any task with reasoning content: <thinking>...</thinking><answer>STRUCTURED</answer>. Apply the schema only inside the answer block.
3. 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.
4. 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.
5. 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.