Structured Output

Valid JSON is not a prompting problem. Compile the schema to a state machine and mask every logit the grammar forbids.

FSM / pushdown automaton
logit masking
token-level grammars
jump-forward decoding

Motivation

The problem

You need the model to return JSON matching a schema, because a program is going to parse it. The usual approach is to ask nicely in the prompt and retry on failure. It works most of the time, and on a production data path "most of the time" is exactly what you cannot afford.

Retrying wastes a full generation, and it does not converge: a model that is confused about the schema stays confused. The failure mode is also silent. A missing field parses fine and breaks something three services downstream.

Core idea

The solution

Stop asking. The sampler already decides which token comes next, and you already know which tokens the grammar permits at this point. Intersect the two: set the logits of every illegal token to −∞ before the softmax, and the model cannot produce invalid output.

constrained samplingpython

def constrained_sample(logits, fsm_state, fsm, tokenizer, params):
    # Which token ids can legally follow, given where the automaton is?
    allowed = fsm.allowed_token_ids(fsm_state)          # precomputed per state

    mask = np.full_like(logits, -np.inf)
    mask[allowed] = 0.0
    logits = logits + mask                              # that is the whole mechanism

    token = sample(logits, **params)
    return token, fsm.advance(fsm_state, token)

Two properties worth noticing. The model's preferences are preserved among the legal tokens: you remove options without overriding its judgement. And the cost is one vector add, which is free relative to the forward pass that produced the logits.

Grammars are over characters; sampling is over tokens

The automaton is the easy part. The difficulty is that a single token like ": {" can carry a string terminator, a colon, a space and an object open, crossing four state transitions at once, so you cannot mask per character. For each automaton state you must precompute the set of token ids whose full character expansion keeps the automaton in a valid state. Libraries like Outlines and XGrammar exist to do that precomputation.

Mechanics

How it works

Diagramschema to automaton to logit mask

Compilation happens once per schema and is cached. At generation time the cost is a state lookup and a vector add.

Regular is not enough: JSON needs a stack

A finite-state machine can express regular languages, which covers a phone number, a date, or a fixed enum. JSON is not regular: nested objects and arrays require matched brackets to arbitrary depth, and no finite state set can track that.

So general grammar-constrained decoding uses a pushdown automaton: a state machine plus a stack. XGrammar and llguidance both do this, with one optimisation that matters. Most tokens do not affect the stack, so they split the vocabulary into context-independent tokens (checkable with a precomputed bitmask) and the small context-dependent remainder.

Jump-forward decoding: the free lunch

After { in a schema with one required key, the next several characters are determined: quote, the key name, quote, colon. The model has no choice to make.

So do not ask it. When the automaton admits exactly one continuation, emit the whole forced span and advance; no sampling decision is needed. In a real engine the forced tokens still need forward passes to fill the KV cache, but many sequential decode steps collapse into one batched extend over the span, which is far cheaper. (This chapter's toy model keeps no KV cache, so it skips the pass outright.) On schema-heavy output this eliminates a large fraction of all sequential decode steps. Constrained generation frequently runs faster than unconstrained generation of the same text, not slower.

What it cannot fix

Constrained decoding guarantees syntactic validity, not semantic correctness. A schema requiring a country field will get one; nothing forces it to be the right country. And over-constraining can hurt: if the model wants to explain that it cannot answer, and the grammar only permits a completed object, you have forced a confident fabrication.

The practical mitigation is to include a refusal shape in the schema, a union with {"error": string}, so the model has a legal way to say no.

Explore

Try it

Simulatorgrammar-constrained JSONrun it, then turn the constraint off

step 0

schema being enforced

{ "name": string, "age": number, "active": boolean }

output so far

(nothing yet)

FSM state: expect object open
tokens allowed: 1/28
free jump-forwards: 0
parses as JSON: incomplete

expect object open. Only the highlighted tokens can be sampled; the rest have their logits set to −∞ before the softmax. Invalid output is not discouraged, it is impossible.

vocabulary mask · step 0

{}":,␣nameageactivetruefalsenull012379AdaLinKimReythecatsat[]-

allowed by the FSM
masked to −∞

⚡ jump-forward: exactly one token is legal, so the engine emits it without running a forward pass at all. Structured output can be faster than unstructured.

Run it with the constraint on. Every seed produces valid JSON matching the schema, and the ⚡ marker shows the steps where no forward pass was needed. Turn the constraint off and run again: the sampler wanders immediately, because nothing is stopping it. The "model" here is uniform random, a fair stand-in for a real model faced with a schema it has not internalised.

Build it

Implementation

The compilation step maps each automaton state to a token-id bitmask. That is the whole cost, and the reason you cache it per schema.

code/s15_structured_output.py (excerpt)python

def compile_masks(fsm, tokenizer):
    """For every state, which token ids keep us inside the grammar?"""
    masks = {}

    for state in fsm.states:
        allowed = []
        for token_id, token_str in tokenizer.vocab.items():
            # Feed the token's characters through the automaton one at a
            # time. A token is legal only if EVERY character is accepted.
            s = state
            if all((s := fsm.step(s, ch)) is not None for ch in token_str):
                allowed.append(token_id)
        masks[state] = np.array(allowed, dtype=np.int32)

    return masks     # cache this per (schema, tokenizer) pair

Compilation is O(states × vocab) and vocab is 130,000

A naive compile over a large schema can take seconds, and once per request if you forget to cache. Production libraries cache by schema hash, compile lazily per state as it is reached, and store masks as bitsets rather than index lists. If constrained decoding is mysteriously slow, look at the compiler before the forward pass.

Run it locally

Compiles a JSON schema to a token-level automaton, generates constrained output from a toy model, asserts every sample parses and validates against the schema, and measures how many decode steps were skipped by jump-forward.

$ python code/s15_structured_output.py

Expect: 200/200 schema-valid samples, roughly 62% of decode steps skipped by jump-forward, and an unconstrained baseline showing that even a model which picks a legal token 99% of the time still emits a valid object only ~84% of the time.

Only NumPy is required — setup instructions.

Production notes

In production

Outlines — regex and JSON-schema constrained generation; popularised the precompiled FSM approach.
XGrammar — pushdown automaton with a context-independent/dependent token split; the current default backend in vLLM.
llguidance — the backend behind Guidance, with similar goals and a fast Rust implementation.
SGLang — implements jump-forward decoding explicitly and reports large speedups on schema-heavy workloads.
picoLM — a minimal version of this idea in ~175 lines of C: pre-analyses the vocabulary and masks logits to enforce JSON structure, with no dependencies.

Exercises

1
Extend the automaton to support nested objects using an explicit stack, and verify that unbalanced brackets become unreachable.
2
Implement jump-forward and measure the fraction of decode steps skipped for a wide schema versus a deep one.
3
Add a union type so the model can emit {"error": "..."} instead of a fabricated answer, then construct a prompt where the unconstrained model refuses and the over-constrained one confabulates.

Continue

What's next

One more architectural technique before we distribute the engine. S16 covers mixture-of-experts inference, where the model activates 5% of its parameters per token while the whole of it still has to sit in memory.

Check yourself

Questions

Answer before you look. A wrong answer tells you more than a right one, because the explanation points at the part of the chapter to reread.

Check yourselfQuestion 1 of 6

Why can't grammar constraints be applied one character at a time?

Score 0/6