Schema-constrained decoding

Asking for structure through prompt engineering offers the model a suggestion: "answer in this format." The model usually obliges, but there is no guarantee. A single unclosed brace, one extra comma, a stray explanatory sentence makes the output unparseable. OpenAI draws the line explicitly: raw JSON mode can produce syntactic JSON, but constraining output against a schema (Structured Outputs, strict: true) is a separate decoding-time guarantee.

Constrained decoding turns the suggestion into a rule. A mask is applied to the model's logit vector: every token the grammar cannot accept right now gets a score of negative infinity, so its probability after softmax is exactly zero. The model may assign that token a high logit, it does not matter; sampling can never select it.

Below, the same step is shown twice. On the left, free decoding occasionally picks an invalid token and the structure breaks. On the right, the same logits pass through a mask: invalid options go dark, only grammar-valid ones stay lit.

What produces the mask is a constraint state: a memory that knows where the partial output sits in the grammar so far. After each token, this state is advanced, and the valid tokens for the next step are computed by looking at this state.

The simplest form is a finite-state machine (FSM): a finite set of states and transitions between them. As a character is appended to the output, the machine walks from one state to another. Only certain transitions are defined in a state; any token that would lead to an undefined transition is masked. Outlines does exactly this and compiles regex constraints into an FSM.

Below, a tiny automaton walks the shell of {"id":...}. As the cursor moves from state to state, the single valid character leaving that state lights up; the rest stay dim. An invalid character cannot fire any transition, so it cannot be produced.

A developer writes a JSON Schema: which fields are required, what the types are, which values are accepted. This schema cannot be handed to the decoder directly; it is first compiled into an automaton. Every part of the schema becomes a piece of constraint: required fields impose an order, types impose character classes, enums impose finite option sets.

Here is the critical distinction. Flat, non-nested structures are expressed easily with an FSM. But JSON is a recursive language: an object can contain other objects, arrays inside arrays, with depth unknown in advance. A finite number of states cannot capture this. That is why OpenAI says they moved to context-free grammar (CFG) for nested and recursive schemas.

Below, a small schema decomposes left to right into pieces of constraint: a required field, a type rule, an enum, and a recursive sub-object. Each piece lights up in turn, building the combined constraint state.

The picture so far assumed the model produces character by character. It does not. LLMs produce subword tokens: {" can be one token, name": another. The grammar, meanwhile, is defined at the character or grammar-token level. A single LLM token can cross several grammar units, and this misalignment makes naive masking wrong.

Koo et al. put this at the core of the problem: subword tokenizers are ambiguous and not aligned with formal grammars. Their solution is to model detokenization with a finite-state transducer and recast the constraint in automata-theoretic terms. Correctly counting different token sequences that yield the same output is exactly this layer's job.

Below, the same {"id" text is produced with two different tokenizations. On top, single characters; below, merged subword tokens. Both yield the same character string; a correct constrained decoder must accept both paths.

Finding which tokens are valid at each step means, in principle, scanning the whole vocabulary. In Llama 3.1 that is 128,000 tokens; rescanning from scratch at every decoding step is a heavy load. The trick is to precompute or cache this scan.

Outlines solves it with an index: a map from FSM states to the set of tokens valid in that state, built ahead of time, so finding valid tokens at runtime is O(1) on average rather than an O(N) scan per step. XGrammar goes further: it splits the vocabulary into context-independent tokens (precheckable and cacheable) and context-dependent tokens (which must be interpreted with a stack at runtime).

Below, two ways of doing one step sit side by side. On top, the naive path scans all 128K of the vocabulary one by one. Below, the indexed path reaches the precompiled set in a single look. The cursor crawls through the naive scan while the index resolves instantly.

Recursion is the FSM's wall. An FSM has no memory: it cannot count how many braces it has opened, so it cannot enforce "every opening brace must close." Nested languages like JSON, SQL, and code require exactly this. The answer is a pushdown automaton (PDA): an FSM with a stack added.

The stack remembers opened structures. Every { pushes a record onto the stack, every } pops it. Which tokens are valid next now depends not only on the current state but also on the top of the stack. XGrammar treats CFG-constrained decoding as exactly a PDA execution and uses a persistent structure to keep this stack fast.

Below, the stack grows and shrinks live as nested JSON is produced. Every opening brace pushes a record, every closing pops it. The output cannot end until the stack empties: that is the guarantee of recursive structure.

Constrained decoding makes a strong but bounded promise. The only thing it guarantees is membership in the implemented grammar. It does not guarantee semantic truth, task success, or even full JSON Schema equivalence. JSONSchemaBench measures this clearly: an over-constrained engine rejects valid instances, an under-constrained one allows invalid ones. "Schema supported" is not a binary feature; it must be read as coverage plus compliance.

So the guarantee depends on the correctness of the grammar-tokenizer mapping, not merely on a grammar existing. On the other hand, constraint does not only fix syntax: PICARD, on text-to-SQL, prunes invalid continuations to keep search inside the valid region and improves task metrics like exact match too. So constraint sometimes raises not just parseability but correctness.

Below, two failure modes sit side by side. An over-constrained engine wrongly rejects a valid instance; an under-constrained engine wrongly accepts an invalid one. The ideal is the middle region that tracks the full schema semantics.

This field splits into two layers. On top, the interface layer: LMQL and Guidance let you write the constraint like a programming language. LMQL turns a prompt into a query, generates token masks from declarative constraints, and reports 26-85% cost savings in its measurements. Guidance combines regex-constrained gen, list-choice select, CFG composition, and JSON-from-schema generation with ordinary Python control flow.

Below, the engine layer: Outlines (FSM indexing), automata methods (Koo et al., ~7,000x faster constraint compilation than prior approaches), and XGrammar (PDA execution, under 40 µs per-token mask generation, up to 100x speedup on CFG). The two layers complement each other: the interface expresses the constraint, the engine runs it fast and correctly. As JSONSchemaBench finds, the right engine can support about twice as many schemas as the worst, and constrained decoding sometimes speeds generation by about 50%.

Below, the stack layer by layer: developer intent on top, interface layer, engine layer, and the token-level mask at the bottom. Each layer passes the constraint to the one below.

Asking for valid JSON is a hope; constraining the decoder is a proof.

A prompt suggests structure, and the model usually complies. Constrained decoding gives an invalid token probability zero: structure is no longer a hope but a guarantee coming from the generation mechanism itself. Its cost is tokenization correctness and engine engineering, and that cost has now largely been paid.