Constrained Decoding: Architecture for Guaranteed-Valid LLM Output (2026)

Every engineer who has shipped an LLM feature into a pipeline has met the same 3 a.m. incident: the model returned JSON that was almost valid. A trailing comma, an unescaped quote, a field named total_ammount, a stray sentence of apology before the opening brace. Downstream, a parser threw, a queue backed up, and a retry storm began. Constrained decoding removes that entire failure class not by asking the model to try harder, but by making invalid output physically impossible to generate. It operates at the logit level, one token at a time, filtering the model’s vocabulary against a formal grammar so that only tokens which keep the output syntactically valid are ever sampled.

The catch — and the reason this post exists — is that “syntactically valid” is a much smaller promise than “correct.” Understanding exactly where that line falls is the difference between a robust extraction service and a subtle data-corruption bug that ships to production.

What this covers: the logit-level mechanism of token masking, how grammars and JSON schemas compile to finite-state and pushdown automata, the tokenizer-alignment problem, the 2026 tool landscape (Outlines, XGrammar, llguidance, llama.cpp GBNF, vLLM, lm-format-enforcer, OpenAI and Anthropic structured outputs), and the failure modes that make validate-and-retry sometimes the better call.

Context and Background

The naive way to get structured output is to ask for it in the prompt — “respond only with JSON matching this schema” — and hope. This works most of the time with a strong model, which is exactly what makes it dangerous: a 2–5% failure rate is invisible in a demo and catastrophic at a million calls a day. The first mitigation was JSON mode, a coarse constraint that guarantees the output is some valid JSON object but says nothing about your schema. It stops the trailing-comma class of bug while doing nothing about missing or misnamed fields.

The distinction between these mechanisms is stark once you attach numbers to it. Prompt-only requests and JSON mode both leave a residual failure rate — the model is trying to comply, and mostly succeeds, but “mostly” over high volume means real incidents. OpenAI’s own figures put plain function calling at roughly 86% schema adherence, which is to say one in seven calls could deviate. Constrained decoding closes that gap to zero for syntax because compliance is no longer a behavior the model attempts; it is a property the decoder enforces. That shift — from “the model usually returns valid output” to “the model cannot return invalid output” — is the entire reason the technique earns its complexity budget.

Constrained decoding is the strong form of the same idea. Instead of constraining after the fact or coarsely, it intervenes inside the decoding loop. The technique traces to work like Willard and Louf’s Outlines (2023), which framed regex- and schema-guided generation as walking a finite-state machine over the token vocabulary, and to grammar-constrained decoding in llama.cpp’s GBNF. By 2026 the idea is mainstream infrastructure: OpenAI’s Structured Outputs, per its own documentation, uses constrained decoding under the hood so that the decoder “physically cannot emit tokens that violate your schema,” reporting 100% schema compliance in its evaluations versus roughly 86% for plain function calling (OpenAI Structured Outputs guide). The open ecosystem converged on the same primitive, which we unpack next. For the complementary discipline of checking output you cannot constrain, see our companion piece on LLM output validation and guardrails.

The Logit-Level Mechanism: Masking the Vocabulary

Constrained decoding works by computing, at every decoding step, a boolean mask over the entire token vocabulary and setting the logits of all disallowed tokens to negative infinity before sampling. Because a token with logit −∞ has probability zero after the softmax, it can never be selected — under greedy argmax or any temperature. The grammar decides which tokens are legal given everything generated so far, so validity is enforced token by token rather than checked at the end.

Figure 1: The per-step constrained decoding loop — the model produces raw logits, the grammar engine emits a bitmask for the current automaton state, invalid logits are set to negative infinity, a token is sampled, and the automaton advances before the next forward pass.

Figure 1 shows the loop closing on itself. The model’s forward pass produces a logit vector of size V (the vocabulary, typically 32k–256k entries). In parallel, a grammar engine holds a state machine positioned at exactly where the partial output currently sits. From that state it computes the set of tokens that could legally come next, expressed as a bitmask of V bits. That mask is applied to the logits, one token is chosen, the automaton advances to its next state, and the token is appended to the KV cache for the next step. The model never sees a smaller vocabulary; it always emits full logits, and the constraint layer sits between logits and sampler.

Why validity is guaranteed but correctness is not

There is a useful way to see why the guarantee is airtight. A language model without constraints defines a probability distribution over every possible token sequence — including the vast majority that are syntactically broken. Constrained decoding does not change that distribution’s shape; it changes its support. By zeroing the probability mass of every token that would leave the automaton in an invalid state, it restricts the reachable sequences to exactly the language the grammar accepts. The model can still express any preference it has within that language, but it has been given no vocabulary with which to leave it. That is a set-theoretic guarantee, not a statistical one, and it is why the failure rate for syntax is not “low” but zero.

The guarantee is precise and worth stating carefully. If the grammar is a faithful encoding of your target format, then any string the constrained decoder can produce is a member of the language that grammar defines. A JSON schema compiled correctly cannot yield a missing required field or a wrong type, because the automaton would have no legal transition into that state. This is a hard guarantee, not a probabilistic one — it holds at temperature 2.0 with a badly tuned model just as it holds at temperature 0.

What the grammar cannot see is meaning. The automaton for a schema with an email string field will happily accept "not-an-email" unless you also compiled an email regex into that field, and even a regex only checks shape, not whether the address exists. A quantity: integer field is guaranteed to contain an integer and guaranteed to contain the wrong integer just as easily as the right one. Constrained decoding moves the failure surface from syntax to semantics: you will never again parse-fail, and you will still hallucinate values. Treat it as a type system for output, not a correctness proof.

The renormalization step and its subtle cost

After masking, the surviving logits are renormalized by the softmax over just the legal tokens. This is where a quieter problem hides. The renormalized distribution is not the same distribution the model would have produced had it been trained to always obey the grammar. Masking-then-renormalizing greedily commits to locally-legal tokens without accounting for whether that choice leads to a high-probability complete sequence. Research on grammar-aligned decoding calls this distribution distortion, and shows that the constrained distribution can diverge measurably from the ideal rejection-sampling distribution (Grammar-Aligned Decoding, arXiv 2405.21047). In practice this means constrained output can be subtly less fluent or less accurate than free output — a real trade-off we return to in the gotchas section.

Compiling Grammars to Automata: FSAs, Pushdown, and Earley

A schema or grammar is human-facing; the decoder needs something it can execute in microseconds per token. The bridge is compilation to an automaton whose states know, cheaply, which tokens are legal. The choice of automaton class determines what you can express and how fast you can enforce it.

Figure 2: Compilation paths — regex compiles to a deterministic finite automaton, a context-free grammar to a pushdown automaton, and richer grammars to an Earley parser; all resolve to token-level index tables split into precomputed context-independent masks and per-step context-dependent masks.

Figure 2 lays out the three families. Regular languages (anything a regex can match) compile to a deterministic finite automaton (DFA). This is the Outlines approach: it converts a character-level DFA that tests whether a string matches a regex into a token-level DFA, so that a single lookup per step returns the set of legal next tokens. JSON schemas whose structure is bounded can be flattened into regex and handled this way, giving O(1) valid-token lookup at generation time in exchange for a compile step up front.

But JSON is not regular. Arbitrarily nested objects and arrays require counting — matching an arbitrary depth of braces and brackets — and no finite automaton can count. That needs a context-free grammar (CFG) and a pushdown automaton (PDA), which augments a state machine with a stack. XGrammar takes exactly this route: it models constrained decoding as a batch of pushdown automata, where a PDA is, in effect, a collection of finite-state machines coordinated by a stack (XGrammar, arXiv 2411.15100). The stack is what lets it remember it is three arrays deep and still owes three closing brackets.

The third family handles grammars that are awkward for a plain PDA. llguidance, the engine now underneath Microsoft’s Guidance library, uses a Rust-based Earley parser, a general context-free parsing algorithm that handles ambiguous and left-recursive grammars a simpler LL/LR parser would choke on. It computes token masks on the fly at roughly 50 microseconds of CPU time per token for a 128k-token vocabulary, with essentially no startup cost (llguidance repository).

The context-independent / context-dependent split

The single most important performance trick — the reason XGrammar can hit sub-40-microsecond token masks — is recognizing that most of the vocabulary’s legality does not depend on grammar context. XGrammar splits tokens into context-independent and context-dependent sets. Roughly 99% of the vocabulary falls into the context-independent bucket, whose legality can be fully precomputed into bitmask tables at compile time. Only the small remaining set of context-dependent tokens — those near a grammar boundary, where the same characters might or might not be legal depending on the stack — must be checked at each step. This is what turns a naive per-step scan of a 200k vocabulary into a table lookup plus a tiny live computation.

The compile step and its latency

None of this is free. Building the automaton and its index tables is a real compute cost paid before the first token. For a fixed schema reused across many requests this amortizes to nothing — you compile once and cache. But for a service that accepts arbitrary per-request schemas, cold-start compilation can add tens to hundreds of milliseconds to the first token’s latency, sometimes exceeding the generation time for short outputs. Production systems cache compiled grammars keyed on the schema hash, and warm the cache for known schemas at deploy time. When you benchmark a constrained-decoding library, measure compile latency and steady-state per-token overhead separately; they have completely different operational profiles.

The Tokenizer-Alignment Problem and Jump-Forward Decoding

Here is the deep, uncomfortable detail that separates a toy implementation from a correct one. Grammars are defined over characters (or bytes). Language models emit tokens, and a single token is usually several characters — subword units chosen by byte-pair encoding to compress common sequences. The boundaries almost never line up. A grammar says “the next character must be }“; the model’s vocabulary has no } token in isolation but has a } glued to a newline, a } glued to trailing whitespace, and a }" used inside strings. Deciding which tokens are legal means asking, for every candidate token, whether every character it contributes keeps the automaton in a valid state.

This mapping is genuinely tricky. The model may prefer to combine several characters into one token, and a token that straddles a grammar boundary — legal for its first two characters, illegal for its third — must be masked out even though a naive character-level check would pass its prefix. Getting this wrong produces one of two bugs: either you illegally forbid a valid token (the model can never emit }\n where the grammar wanted }), degrading output, or you illegally permit an invalid one, breaking the guarantee you were paying for. Correct implementations walk each candidate token character by character through the automaton; this is precisely why the context-dependent token set exists and why it cannot be fully precomputed.

Figure 3: Jump-forward decoding — when the grammar makes the next several bytes deterministic, the engine tokenizes and injects them directly instead of running a model forward pass for each, then resumes masked sampling.

Figure 3 shows the payoff hiding inside this problem. When the grammar state makes the next output deterministic — after {" the schema’s only key is "name", so name":" is forced — there is no decision for the model to make. Jump-forward decoding (also called coalescing) exploits this: when the following bytes can be inferred from the grammar alone, the engine bypasses the model’s forward pass and sampling entirely, tokenizes the forced bytes, and appends them directly to the context (Fast JSON decoding with compressed FSM, LMSYS). For schema-heavy output where much of the structure (keys, braces, quotes, fixed enum values) is forced, this can skip a large fraction of forward passes, turning constrained decoding from a tax into a net speedup over free generation. The technique is orthogonal to the masking itself and composes with it cleanly.

Interaction with speculative decoding and the KV cache

Constrained decoding is not the only thing modifying the decode loop in a 2026 inference stack. It has to coexist with speculative decoding, which proposes several draft tokens per step for the target model to verify in one pass. The interaction is delicate: every drafted token must also satisfy the grammar, or verification wastes work rejecting structurally-illegal drafts. Byte-pair-encoding alignment — forcing each grammar symbol to map to exactly one token so drafts never straddle a boundary — is one route to making the two techniques cooperate rather than fight. Constrained decoding also touches the KV cache: jump-forward injection appends tokens to the cache without a forward pass, so the cache-management code must handle multi-token appends and keep positions consistent, a subtlety that has caused real off-by-one bugs in production integrations.

Runnable Example: Schema-Constrained JSON with vLLM and XGrammar

The following is a minimal, runnable pattern using vLLM’s structured-output API, which by 2026 defaults to the XGrammar backend for JSON-schema constraints. It extracts a typed record and is guaranteed to parse. (Versions move fast — confirm the current API against the vLLM docs before shipping.)

# pip install vllm  (v1 engine; XGrammar is the default structured-output backend)
from vllm import LLM, SamplingParams
from vllm.sampling_params import GuidedDecodingParams
import json

# 1. The schema is the contract. Every field here is guaranteed present and typed.
schema = {
    "type": "object",
    "properties": {
        "customer_name": {"type": "string"},
        "sentiment": {"type": "string", "enum": ["positive", "neutral", "negative"]},
        "priority": {"type": "integer", "minimum": 1, "maximum": 5},
        "needs_human": {"type": "boolean"},
    },
    "required": ["customer_name", "sentiment", "priority", "needs_human"],
    "additionalProperties": False,
}

llm = LLM(model="meta-llama/Llama-3.1-8B-Instruct")

# 2. Attach the schema as a guided-decoding constraint. The grammar is compiled
#    once here and cached; subsequent calls with the same schema pay no compile cost.
guided = GuidedDecodingParams(json=schema)
params = SamplingParams(temperature=0.0, max_tokens=256, guided_decoding=guided)

ticket = ("Subject: still broken. I have emailed three times. "
          "This is Dana Ruiz and I am furious. Fix it today.")
prompt = f"Extract a structured ticket record.\n\nTicket:\n{ticket}\n\nJSON:"

out = llm.generate([prompt], params)[0].outputs[0].text

# 3. This json.loads() cannot raise on malformed JSON — the decoder could not
#    emit invalid syntax. It CAN still contain a wrong sentiment or priority;
#    that is a semantic check you still owe.
record = json.loads(out)
assert record["sentiment"] in {"positive", "neutral", "negative"}  # already guaranteed
print(record)

Two things in that snippet are load-bearing. First, temperature=0.0 does not affect the validity guarantee — masking makes invalid tokens impossible at any temperature — but it does make extraction deterministic, which you usually want. Second, the closing assert is redundant for shape (the enum is enforced by the grammar) but is the right place to add a semantic check the grammar cannot express, such as cross-field consistency. The equivalent in the hosted world is OpenAI’s response_format with a json_schema and strict: true, or a tool/function schema with strict semantics; Anthropic, as of early 2026, expresses the same guarantee through strict tool-call schemas rather than a top-level response-format field. Outlines and lm-format-enforcer offer the same primitive for models you host yourself, and llama.cpp exposes it through GBNF grammar files.

A worked automaton transition

To make the mechanism concrete, trace a few steps of the schema above. The compiled automaton starts in a state whose only legal continuation is the character {. Every token in the vocabulary whose first byte is not { — or which cannot begin an object — is masked to −∞. Suppose the sampler picks the token {". The automaton advances two characters: it has consumed the opening brace and the opening quote of the first key. Now its legal set is exactly the tokens that can begin a required-and-not-yet-emitted key. Because customer_name is the first required property, and the model has emitted no keys, the engine can look ahead and see that the key string is effectively forced; jump-forward decoding may inject customer_name": without a forward pass. Control then returns to the model at the value position, where the schema says a string, so the mask permits " and forbids {, [, digits, and true. Each transition is a table lookup keyed on the current automaton state, which is why steady-state overhead can stay in the tens of microseconds even for a 128k vocabulary.

Notice what the automaton is not doing: it never evaluates whether “Dana Ruiz” is the right name. It only enforces that a string appears where a string is required. Every guarantee it offers is structural, and every structural transition is decided before the model’s semantic preference is even consulted — the model chooses only among options the grammar has already blessed.

Choosing a backend: a 2026 decision matrix

The libraries are not interchangeable; each optimizes a different point in the design space. The table below summarizes the practical trade-offs for the common self-hosted and hosted choices as of mid-2026. Per-token figures are the vendors’ and papers’ own reported numbers on 128k-class tokenizers and are indicative, not a controlled head-to-head benchmark.

Tool	Automaton class	Best for	Reported per-token overhead	Deployment
XGrammar	Pushdown (batched PDA)	JSON schema, general CFG; default in vLLM/SGLang/TensorRT-LLM	under ~40 µs	Self-hosted serving
llguidance	Earley parser (Rust)	Ambiguous/left-recursive CFGs; Guidance, llama.cpp, mistral.rs	~50 µs	Self-hosted, embedded
Outlines	Regex to token-level DFA	Regex, enums, bounded schemas; O(1) lookup	index-lookup dominated	Self-hosted
llama.cpp GBNF	Grammar to per-step mask	Local GGUF models; JSON-Schema-to-GBNF conversion	mask-computation bound	Local/edge
lm-format-enforcer	Token-prefix tree filter	Framework-agnostic JSON/regex enforcement	filter-per-step	Self-hosted
OpenAI Structured Outputs	Hosted constrained decode	Managed strict JSON schema, ~100% compliance	opaque, hosted	API
Anthropic strict tools	Hosted tool-schema constrain	Managed strict tool-call arguments	opaque, hosted	API

The reading of this matrix is not “pick the fastest.” It is: match the automaton class to your grammar’s complexity, and the deployment column to where your model runs. A regex or enum constraint over a bounded schema is best served by Outlines’ DFA; a deeply nested or recursive grammar needs a pushdown or Earley engine; a local GGUF deployment wants GBNF; and a team that does not want to operate an inference stack at all buys the guarantee from a hosted API and pays in vendor lock-in and opacity. lm-format-enforcer occupies a useful middle ground: it filters at the token-prefix level and slots into several frameworks without replacing the sampler wholesale, which makes it a pragmatic choice when you cannot swap backends.

Trade-offs, Gotchas, and What Goes Wrong

Constrained decoding is a sharp tool, and the failure modes are exactly the ones that pass code review and fail in production. The first is the over-tight schema. If you mark a field required and the input genuinely lacks it, the model cannot emit “unknown” or null — the grammar forces it to invent a value. A schema that is stricter than reality manufactures hallucinations by construction. The fix is to model absence explicitly: allow null in the union, add an "unknown" enum member, make optional things optional.

Second is distribution distortion, described earlier. Because masking-and-renormalizing is greedy, forcing structure can pull the model off the answer it would otherwise have given. This is worst when the constraint fights the model’s natural output — for instance forcing a bare enum when the model wanted to reason first. The mitigation is to let the model think in free text (a reasoning field, or a separate unconstrained call) and constrain only the final structured span.

Third is whitespace and tokenization edge cases. Schemas that don’t pin down whitespace let the model burn tokens on indentation, and the “Lost in Space” line of research shows that the exact tokens a grammar permits for structural whitespace measurably affect both speed and quality (Lost in Space, arXiv 2502.14969). A grammar that allows only one whitespace representation where the model’s tokenizer prefers another forces awkward token choices.

Fourth is performance overhead in the wrong regime. For a fixed cached schema with jump-forward enabled, constrained decoding is often faster than free generation. For arbitrary per-request schemas with cold compilation, the compile step can dominate short-output latency. Measure your regime; do not assume.

A fifth, easily-missed failure is the silent guarantee gap at the boundary of the constrained span. Constrained decoding only guarantees what is inside the grammar. If your prompt lets the model emit a preamble before the JSON — “Here is the extracted record:” — and you only attach the grammar to a sub-region, everything outside that region is unconstrained and can still surprise a downstream regex that expected the response to start with {. The fix is to constrain the entire response, not a fragment of it, and to strip or forbid any wrapper text at the grammar level rather than in post-processing. Teams frequently discover this only when a model update changes the preamble wording and a brittle downstream splitter breaks — a failure that looks like a model regression but is really an under-scoped constraint.

A sixth is integration drift between the grammar engine and the served model’s tokenizer. The grammar’s token-level index is built against a specific tokenizer. Swap the model — even to a same-family checkpoint with a different vocabulary — and reuse a stale compiled grammar, and the byte-to-token mapping silently desynchronizes: masks now point at the wrong token IDs. The output can look plausible while quietly violating the intended grammar. Pin the tokenizer alongside the schema in your cache key so a model swap invalidates the compiled grammar rather than silently corrupting it.

Finally, know when not to use it. When the structure is trivial and the model is strong, plain generation plus a validate-and-retry loop can be simpler, cheaper to operate, and — because it never distorts the distribution — occasionally more accurate. Figure 4 gives the decision path.

*Figure 4: A decision flow — route by whether a hard structure guarantee is needed and by schema complexity to the right engine, then reme