Constrained decoding is a technique that manipulates a language model’s token generation process to guarantee that outputs conform to a specified structure — JSON, XML, SQL, function calls, or any format that can be described by a formal grammar. Instead of hoping the model produces valid output and then parsing (or retrying on failure), constrained decoding makes it mathematically impossible for the model to generate structurally invalid tokens.
This is a foundational technique for AI engineering because most production LLM applications need structured output. An agent that calls functions needs valid JSON arguments. A data extraction pipeline needs parseable output. A code generator needs syntactically valid code. Without constrained decoding, you’re left with fragile regex parsing, retry loops, and output validation that adds latency and cost while still occasionally failing.
Constrained decoding has become a first-class feature in modern inference engines (vLLM, SGLang, TensorRT-LLM) and is the mechanism behind “Structured Outputs” features offered by OpenAI, Anthropic, and Google. Understanding how it works under the hood helps you design better schemas, debug generation issues, and choose the right approach for your use case.
At each step of autoregressive generation, an LLM produces a probability distribution over its entire vocabulary (typically 32,000-128,000 tokens). Normally, any token with non-zero probability can be selected. Constrained decoding introduces a mask that sets the probability of invalid tokens to zero (or equivalently, their logits to negative infinity) before sampling occurs.
Given the model’s raw logit vector L and a binary mask vector M (where 1 = valid, 0 = invalid), the constrained logits are: L' = L + (1 - M) × (-∞). After softmax, all masked tokens have probability 0. The model can only select from structurally valid continuations.
The critical question is: how do you determine which tokens are valid at each generation step? This is where formal grammars and finite state machines come in.
The most common implementation compiles the output constraint (JSON schema, regex, grammar) into a finite state machine (FSM) or finite state automaton (FSA). Each state in the FSM represents a position within the valid output structure, and transitions between states correspond to valid tokens.
# Conceptual FSM for JSON boolean field: {"active": true|false}
# States track position in the output structure
State 0: START → valid tokens: '{'
State 1: AFTER_BRACE → valid tokens: '"'
State 2: IN_KEY → valid tokens: 'a','c','t','i','v','e'
State 3: AFTER_KEY → valid tokens: '"'
State 4: BEFORE_COLON → valid tokens: ':'
State 5: BEFORE_VALUE → valid tokens: 't','f' (start of true/false)
State 6: IN_TRUE → valid tokens: 'r','u','e' (completing "true")
State 7: IN_FALSE → valid tokens: 'a','l','s','e' (completing "false")
State 8: AFTER_VALUE → valid tokens: '}'
State 9: END → generation completeAt each generation step, the FSM’s current state determines which tokens are valid. The inference engine looks up the set of valid tokens for the current state, creates a mask, and applies it to the logits before sampling. After a token is selected, the FSM transitions to the next state.
A major implementation challenge is that LLM tokenizers don’t operate on individual characters. The token "true" might be a single token, or it might be split into "tr" + "ue", or "t" + "rue", depending on the tokenizer and context. The FSM must account for all possible tokenizations of valid strings.
The FSM operates at the character level (defining valid character sequences), but masking happens at the token level (blocking or allowing multi-character tokens). The constraint engine must precompute, for each FSM state, which vocabulary tokens produce character sequences that keep the FSM in a valid state. This precomputation (called “index building”) is the most expensive part of constrained decoding setup, but it only needs to happen once per schema.
For JSON Schema — the most common constraint type in production — the process works as follows:
# Using Outlines library for JSON-constrained generation
from outlines import models, generate
from pydantic import BaseModel
class PropertyInfo(BaseModel):
name: str
city: str
rooms: int
rating: float
amenities: list[str]
# Load model
model = models.transformers("mistralai/Mistral-7B-v0.3")
# Create constrained generator from Pydantic schema
generator = generate.json(model, PropertyInfo)
# Generate — output is GUARANTEED to be valid PropertyInfo JSON
result = generator("Extract property info: The Grand Hotel in Paris has 250 rooms...")
print(result)
# {"name": "The Grand Hotel", "city": "Paris", "rooms": 250,
# "rating": 4.5, "amenities": ["spa", "restaurant", "pool"]}For simpler constraints, regular expressions provide a lightweight alternative to full JSON Schema. A regex like [0-9]{4}-[0-9]{2}-[0-9]{2} constrains the model to output a valid date format. Regex constraints compile directly to FSMs without the intermediate CFG step, making them faster to set up.
# Regex-constrained generation with Outlines
from outlines import models, generate
model = models.transformers("mistralai/Mistral-7B-v0.3")
# Constrain to ISO date format
date_generator = generate.regex(model, r"[0-9]{4}-[0-9]{2}-[0-9]{2}")
date = date_generator("Today's date is")
# "2026-04-02" — guaranteed to match the pattern
# Constrain to email format
email_generator = generate.regex(model, r"[a-zA-Z0-9._%+-]+@[a-zA-Z0-9.-]+\.[a-zA-Z]{2,}")
email = email_generator("Contact email:")For complex formats that can’t be expressed as regular expressions — like nested JSON, recursive data structures, or programming language syntax — context-free grammars provide the necessary expressiveness. CFGs can describe recursive structures (like nested objects or arrays) that regular expressions fundamentally cannot.
Libraries like llguidance (from the Guidance team) and XGrammar (used in SGLang and vLLM) implement efficient CFG-constrained decoding with optimizations like compressed finite state machines that reduce memory usage and lookup time.
Constrained decoding adds overhead at each generation step for the mask lookup operation. With precomputed index structures, this lookup is typically O(1) — a hash table lookup from FSM state to a precomputed token mask. The Outlines library, for example, compiles JSON schemas into index structures that enable constant-time valid token lookup per step.
The setup cost (compiling schema to FSM and precomputing token masks) can be significant for complex schemas — potentially several seconds. But this is a one-time cost that can be cached and reused across requests. For high-throughput serving, the per-token overhead is negligible (typically <1ms per step).
When an LLM needs to call tools or functions, constrained decoding ensures the output is always a valid function call with correct argument types. This eliminates parsing errors that would otherwise require retry logic. Modern inference engines like vLLM and SGLang use constrained decoding internally to implement tool-calling features.
For extracting structured information from unstructured text (emails, documents, web pages), constrained decoding guarantees that the output can always be parsed into your target schema. This is critical for production pipelines where a single malformed JSON response can break downstream processing.
Constrained decoding has an important limitation: the model’s internal probability computation does not account for the constraints. The model generates logits as if it were producing free-form text, and the mask is applied afterward. This means the model may “want” to generate text that doesn’t fit the schema, leading to lower-quality content being forced into the constrained format.
In practice, this matters most when the schema is very restrictive (e.g., forcing an enum choice when the model’s natural response would be something else) or when the model hasn’t been trained/prompted to produce the target format. Using models that have been fine-tuned for structured output (like recent versions of GPT-4, Claude, and Llama) significantly reduces this issue because the model’s natural distribution already aligns well with structured formats.
Use constrained decoding when you need 100% structural validity — when even a single malformed response causes a pipeline failure. Use prompt engineering alone when approximate structure is acceptable and you can tolerate occasional parsing failures with retry logic. In practice, the best approach combines both: prompt the model to produce the desired format (so the probability distribution is already well-aligned), then apply constrained decoding as a guarantee.
Outlines, llguidance, XGrammar. Key engines with built-in support: vLLM, SGLang, TensorRT-LLM.