Constrained & structured decoding

What it is (intuition first)

A language model emits a probability distribution over its whole vocabulary at every step, then samples one token. Left to itself it will happily produce {"temperature": 22, and then — one token later — a chatty "sure, here you go!" that breaks the JSON. Constrained decoding removes that freedom on purpose: at each step, before sampling, you compute which tokens could legally come next under some formal constraint (a regular expression, a JSON Schema, a context-free grammar) and you set the logits of every illegal token to -∞. After softmax those tokens have probability zero, so the model is physically incapable of emitting them.

The mental model that makes it click:

The model still chooses which valid token; the constraint decides which tokens are valid at all. You are not steering the model — you are deleting the wrong exits at every fork.

This is a hard guarantee, not a request. Prompting ("respond only in JSON, no prose") is a soft constraint the model can ignore under distribution shift; constrained decoding is a structural one enforced by the sampler. If the grammar says a string must close with " before a , can appear, no sampled trajectory can violate it — the output is parseable by construction. The catch, which the rest of this article keeps returning to, is that deleting exits changes the distribution the model was trained on, and that can quietly cost you reasoning quality.

Two names for two scopes you'll see used loosely:

Structured output — the goal: text that conforms to a schema (a JSON object, a function-call payload, a SQL statement). Vendors ship this as a product feature ("JSON mode", "Structured Outputs", "tool calling").
Constrained / guided / grammar-based decoding — the mechanism most engines use to deliver that goal at the token level. (A schema can also be enforced after generation by re-prompting on parse failure — cheaper to build, no guarantee, more retries.)

Why it matters

It's the load-bearing layer under every agent. [[tool-use-function-calling]] only works if the model's tool-call payload actually parses against the function schema; an [[agentic-loops]] harness that has to retry on malformed JSON burns iterations and latency. Constrained decoding turns "the model usually produces valid args" into "the model always does."
It collapses a class of failures to zero. Unparseable output, missing required fields, hallucinated enum values, trailing prose after the closing brace — all become unreachable states, not bugs you catch in production. This is why it pairs naturally with [[generative-verifiers]] and any pipeline that feeds model output into a downstream parser.
It's a real speed and cost lever, in both directions. Done well, it can reduce end-to-end latency (the model can't waste tokens on prose, and engines like vLLM report large throughput wins). Done naively, the per-token mask computation becomes the bottleneck — character-level rejection sampling can dominate the forward pass.
It has a measurable downside on reasoning. Forcing structure too early demonstrably hurts math and multi-hop tasks (see caveats). The state of the art is not "constrain everything" — it's "let the model reason freely, then constrain only the final answer."

How it works (real mechanics)

1. The base operation: a per-step logit mask

Every method below reduces to the same primitive. Given the tokens generated so far, compute a boolean mask over the vocabulary (True = this token keeps the output valid), then:

logits = model.forward(prefix)            # shape [vocab_size]
logits[~valid_mask(state, prefix)] = -1e9 # forbid illegal tokens
next_token = sample(softmax(logits))      # now provably valid
state = advance(state, next_token)        # move the constraint automaton forward

The entire engineering problem is making valid_mask cheap — it runs once per generated token, against a 32k–256k-token vocabulary, so a naive implementation that re-parses every candidate string is hopeless. The clever part is precomputation.

2. FSM indexing — the Outlines approach (regex / regular constraints)

Willard & Louf's Efficient Guided Generation (arXiv:2307.09702) reframes generation as transitions over a finite-state machine. A regex (and a JSON Schema, lowered to a regex over its surface syntax) compiles to an FSM. The key trick: instead of checking tokens against the FSM at runtime, they build an index once, mapping each FSM state to the set of vocabulary tokens that are valid in that state. At generation time, "what's allowed next?" becomes a dictionary lookup keyed by the current state — the paper's headline claim is that this makes the per-token cost roughly O(1) in the size of the vocabulary (amortized after the index is built), versus the naive cost that scales with vocabulary size. The method is model-agnostic and "adds little overhead to the token sequence generation process." This is the design now embedded in Outlines and integrated into serving stacks.

The limitation is structural: FSMs recognize regular languages. Plain regexes can't count matched brackets, so deeply nested or recursive structures (arbitrary JSON, code) strain the pure-FSM approach.

3. Pushdown automata + mask caching — the XGrammar approach (context-free grammars)

JSON, programming languages, and recursive schemas are context-free, not regular — you need a stack. XGrammar (Dong et al., arXiv:2411.15100) enforces a context-free grammar by simulating a pushdown automaton with a tree-structured stack. Its central optimization is splitting the vocabulary into two classes:

context-independent tokens — their validity depends only on the current grammar production, not on the full parse stack. These can be precomputed and cached (the adaptive token mask cache).
context-dependent tokens — a small remainder that must be checked against the live stack at runtime.

By caching the large context-independent majority and only doing live work on the small remainder, XGrammar reports ~100× faster per-token mask generation than a naive baseline, and end-to-end structured-generation speedups of up to ~80× (against engines without these optimizations) in their evaluation — fast enough to overlap mask computation with GPU forward passes so structure adds near-zero latency. (Speedup magnitudes are the authors' own benchmarks; treat exact multipliers as workload-dependent.) Independent comparisons also report XGrammar handling complex nested schemas more accurately than FSM-only engines on hard cases — one cited figure: 97.1% vs 76.4% schema accuracy on a nested GitHub-issues schema with Qwen-2.5-32B — though such head-to-head numbers come from third-party benchmarks and shift with engine versions, so flag them as comparative, not absolute.

4. The serving-engine view

In a real inference server (vLLM, TensorRT-LLM, SGLang) the constraint backend is a pluggable component sitting between the logits and the sampler. The vLLM team's write-up describes integrating both Outlines and XGrammar as guided-decoding backends and reports up to ~5× time-per-output-token (TPOT) speedups under load from the optimized path versus an unoptimized one. The hard engineering constraints at this layer are: the mask must be computed per request in a batch (different requests are at different grammar states), and it must not stall the GPU — hence the obsession with caching and CPU/GPU overlap.

5. The vendor-API view (and what "guaranteed" really means)

OpenAI's Structured Outputs states the model "will always generate responses that adhere to your supplied JSON Schema." Practically important caveats from the docs themselves: it supports only a subset of JSON Schema ("some features are unavailable for performance or technical reasons" — e.g. typically requiring additionalProperties: false and that all properties be required, with various keyword restrictions), and the first request with a new schema incurs extra latency while the schema is processed/compiled, with subsequent requests cached. So even the vendor guarantee is "guaranteed within a restricted schema dialect, with a one-time compile cost" — the same FSM/grammar machinery as the open-source engines, wrapped as a product. Anthropic and others expose the equivalent through tool calling: declaring a tool with an input schema is the structured-output channel, and the same constrained-generation guarantees (and dialect limits) apply to the tool-call args.

Key ideas & tradeoffs

Hard guarantee vs. soft prompt. Constrained decoding makes invalid output impossible; prompting makes it unlikely. Choose hard guarantees when a parser is downstream and a single malformed token breaks the pipeline; choose prompting when the format is loose or the constraint would distort reasoning.
Regular (FSM) vs. context-free (PDA). FSM indexing (Outlines) is fast and great for flat/regex-shaped constraints; pushdown automata (XGrammar) handle recursion and nesting but carry parse-state machinery. Most production JSON/code work wants the CFG path.
Precompute or die. The whole field is about moving work out of the per-token hot loop — index construction (Outlines) and mask caching (XGrammar) are the same idea: pay once at compile time so runtime is a lookup.
Constrain late, not early. The single most important design rule, from CRANE (below): keep the reasoning free-form and apply the constraint only to the final answer field. A "scratchpad + validated final_answer" schema captures most of the structure benefit with little of the reasoning cost.
The schema is part of the prompt budget. A large schema consumes context and (per OpenAI) a first-call compile cost; over-specified schemas with deep nesting raise both latency and the odds of forcing the model into an awkward token path.

Honest caveats & open questions

Constraints can degrade reasoning — this is measured, not hypothetical. Let Me Speak Freely? (Tam et al., EMNLP 2024, arXiv:2408.02442) finds that stricter format restrictions generally cause larger performance drops on reasoning-heavy tasks (e.g. GSM8K math, multi-hop QA), while sometimes helping on classification/slot-filling. The mechanism: greedily masking tokens that don't lead to a valid string distorts the model's output distribution, cutting off the natural-language scratch space the model uses to think. Their recommended mitigation is the hybrid scratchpad-plus-validated-field schema. (Note: this paper has been actively debated — some argue careful schema design recovers much of the gap, so treat "constraints always hurt reasoning" as contested, not settled.)
CRANE shows the fix is interleaving, not abandoning constraints. Reasoning with constrained LLM generation (Banerjee et al., 2025, arXiv:2502.09061) argues theoretically that fully constrained decoding restricts the model's intermediate-reasoning expressivity, and proposes alternating unconstrained reasoning with constrained output phases. It reports up to ~10% accuracy improvement over both standard constrained decoding and unconstrained decoding on symbolic-reasoning benchmarks. (Authors' own numbers; benchmark-specific.)
A valid object is not a correct object. Constrained decoding guarantees syntax, never semantics. The model can emit perfectly-schema-valid JSON with the wrong values, a fabricated enum that happens to be in the allowed set, or a confidently incorrect tool argument. Schema-adherence metrics measure parseability, not truth — pair structure with a verifier ([[generative-verifiers]]).
Distribution distortion is subtle. Masking renormalizes over the surviving tokens, which is not the same as conditioning on validity — it's a greedy local approximation. Whether a given mask makes the model "lie" to satisfy the grammar is hard to predict and an open research question.
Tokenization mismatch is a real bug source. Grammars are defined over characters/bytes but masking happens over BPE tokens; a token can straddle a grammar boundary, and getting this right (token healing, byte-level grammars) is where engines historically diverged and broke on edge cases (Unicode, whitespace, partial tokens). See [[tokenization]].
Speedup claims are vendor/engine benchmarks. The 80×/100×/5× figures above are each authors' own measurements on chosen workloads and engine versions; they are directionally real (precompute + cache beats naive rejection sampling) but should not be quoted as universal constants.

How it connects to OpenAlice

OpenAlice's agent core is a hardened tool-loop (run_agentic_loop), and constrained/structured decoding is the invisible layer that keeps that loop from stalling on malformed tool calls:

Tool-call assembly. Atlas indexes accumulate_tool_calls and the add_tools / add_tools_shared path in crates/api-handlers/src/http/routes/chat_tools/agentic_loop.rs and chat_prompt/assembler.rs — the place where tool schemas are declared to the provider and where streamed tool-call deltas are reassembled. This is exactly the [[tool-use-function-calling]] contract whose reliability constrained decoding underwrites; when the provider enforces the args schema, the loop's "execute tool" step can trust the payload parses.
Provider-side enforcement. OpenAlice runs on Codex/OpenAI-family providers (default gpt-5.5), so structured-output and tool-arg validity come through the vendor Structured-Outputs / tool-calling path described above — meaning OpenAlice inherits both the guarantee and the schema-dialect limits and first-call compile cost. Keep tool schemas minimal and flat for latency.
CoT trace as structured output. The AGI track stores a chain-of-thought trace as structured JSON alongside every assistant turn (sessions.jsonl) — a live instance of the "free reasoning, structured final record" pattern CRANE and Let Me Speak Freely? both advocate: the thinking is unconstrained, only the persisted record is schematized.
The house rule already encodes the caveat. OpenAlice's "never trust a sub-agent's self-reported done — re-gate with the real build+test" is the operational form of a valid object is not a correct object: structure (the agent returned well-formed status) is not correctness (the work actually passes), so an independent [[generative-verifiers]]-style gate always follows.

Constrained & structured decoding — making the model's output provably parseable