Structured output

A language model writes one token at a time, and each token is a draw from a probability distribution (see primer.ml.inference). Most of the time you want free text. Sometimes a program is going to read the answer: a tool call's arguments, a row for a database, a label from a fixed list. Then the answer must have an exact shape, such as a JSON object with an integer field called age, and one stray character breaks it.

Structured output is the family of techniques that make the shape certain. The main one, constrained decoding, is surprisingly small: before each token is drawn, find every token that could not possibly continue a valid answer, and forbid it. This lesson builds that from scratch: first for simple patterns, with a finite-state machine, then for nested JSON, with a stack.

Everyday picture You read a form aloud over the phone to a friend and ask them to type it in exactly. They are careful and mostly right. But now and then they add "Sure, here you go!" before the form, or they forget the last bracket, or a finger slips. A person reading the result shrugs it off. A program reading it stops dead: one wrong character and the whole thing is rejected.

Tiny worked example This lesson's toy model, ToyModel, has mostly learned to answer {"age": 42}. It is a pretend model, a few lines of NumPy, that copies that answer with some noise on every choice and a habit of opening with "Sure". Asked 200 times, with nothing but the request to guide it, it writes the exact answer 133 times (66.5%). The other 67 look like this:

Nothing here is a big mistake. Each one is a single bad token.

flowchart LR
  P["Prompt: reply with JSON"] --> M[Model draws one token]
  M --> T[Append it to the answer]
  T -->|not finished| M
  T -->|finished| J{Parser}
  J -->|every token right| OK[Valid JSON]
  J -->|one token wrong| ERR[Parse error:<br/>the whole answer is lost]

That is why failures pile up with length. If each token is right with chance , and the chances are roughly independent, the whole answer is right only when every token is:

# p: chance one token is right; n: tokens in the answer
p, n = 0.98, 10
# p^n: all n tokens right
round(p ** n, 3)  # → 0.817
# a ten times longer answer
round(p ** 100, 3)  # → 0.133

In code: ToyModel is the pretend model, sample_answer draws one answer token by token, and chance_all_valid is the formula.

Why it matters in practice. A program that calls a model a million times a day and fails 1% of the time fails ten thousand times a day. Long answers, nested objects and small models make it worse. Prompting and examples help, but they only move you to a better curve. To get to 100% you have to change how tokens are chosen.

Everyday picture Picture a keyboard whose keys lock and unlock as you type. You still decide what to write. But at every keystroke, any key that would make the text break the form is locked for that one keystroke. You cannot make the mistake, because the key isn't there.

Tiny worked example At the very first step the model scores four tokens (these scores are logits: raw preferences, before softmax turns them into probabilities; see primer.ml.attention for softmax from zero). Only { and [ can start a JSON value, so the other two are locked:

Before the mask the model put 79% of its belief on chatter. After the mask, the chatter has a chance of exactly zero, and the two allowed tokens share everything. They keep their odds against each other: { was 1.65 times as likely as [ before, and it still is.

flowchart LR
  A[Answer so far] --> M[Model: a logit<br/>for every token]
  A --> C[Constraint: which tokens<br/>can still lead to a valid answer?]
  M --> K[Set forbidden logits to minus infinity]
  C --> K
  K --> S[Softmax over what is left<br/>then sample]
  S --> N{End token?}
  N -->|no| A2[Append the token] --> A
  N -->|yes| D[Done: valid by construction]

The mask as a formula is softmax with a 0-or-1 switch on every term:

import math
# Sure, " Here", "{", "["
z = [2.0, 1.0, 0.5, 0.0]
# m_i: 1 if the token may come next
m = [0, 0, 1, 1]
# m_i e^(z_i): forbidden tokens contribute nothing
kept = [m_i * math.exp(z_i) for m_i, z_i in zip(m, z)]
[round(k, 3) for k in kept]  # → [0.0, 0.0, 1.649, 1.0]
# Σ_j m_j e^(z_j)
total = sum(kept)
round(total, 3)  # → 2.649
[round(k / total, 3) for k in kept]  # → [0.0, 0.0, 0.622, 0.378]
# without the mask, most of the belief went to chatter
e = [math.exp(z_i) for z_i in z]
[round(x / sum(e), 3) for x in e]  # → [0.579, 0.213, 0.129, 0.078]

Setting a logit to minus infinity does the same thing, because : it is the trick the causal mask uses in primer.ml.attention. After masking, temperature, top-k and top-p from primer.ml.inference work exactly as before, on the tokens that are left.

Why 100% by construction. The checker keeps one promise: every answer so far can still be finished validly. It holds at the start (the empty answer can be finished). Each step only allows a token that keeps it. The end token is allowed only when the answer is already complete. So every answer that ends is valid. No luck is involved.

In code: masked_softmax applies the mask, sample_answer takes an optional constraint and masks every step, and validity_experiment produces the bars above.

Why it matters in practice. Constrained decoding changes nothing about the model: no retraining, same weights. It only changes which tokens may be drawn, which is why it can be added to any open model at serving time. The hard part is the checker: answering "which of 100,000 tokens could still lead to a valid answer?" fast, at every step. The next two sections build it.

Everyday picture A subway map. You stand at a station. Each line leaving it is labelled with one character. To write a character, you ride the line with that label; if no line from your station has it, that character is impossible here. Some stations are marked "you may stop here". That map is a finite-state machine: a fixed set of states (stations) and one move per character. A regular expression, the pattern language behind [0-9]+ and cat|car|dog, can always be drawn as one.

Tiny worked example The pattern cat|car|dog (one of three words) becomes this machine:

stateDiagram-v2
  [*] --> S0
  S0 --> S1: c
  S0 --> S2: d
  S1 --> S3: a
  S2 --> S4: o
  S3 --> S5: r
  S3 --> S6: t
  S4 --> S7: g
  S5 --> [*]
  S6 --> [*]
  S7 --> [*]

Tokens are not characters. A model writes tokens, and one token can hold several characters. The rule: a token is allowed if the machine can swallow all of its characters, one after another, without getting stuck. With a vocabulary of 13 tokens:

cat is allowed at the start even though no single line reads "cat": the machine rides c, then a, then t. at is part of a real word and still never allowed at the start, because S0 has no "a" line.

The end token joins only when is an accepting state (S5, S6 or S7 here), because only there is the text complete.

In words: "to see whether a token fits, walk its characters through the machine one at a time; the allowed tokens are the ones that never get stuck."

With the numbers: , so cat is in . is undefined, so at is not.

In Python:

# the cat|car|dog machine: state -> {character: next state}
delta = {0: {"c": 1, "d": 2}, 1: {"a": 3}, 2: {"o": 4}, 3: {"r": 5, "t": 6}, 4: {"g": 7}, 5: {}, 6: {}, 7: {}}
accepting = {5, 6, 7}
def walk(s, token):
    # δ*: one δ per character; None means stuck
    for ch in token:
        s = delta[s].get(ch) if s is not None else None
    return s
walk(0, "cat")  # → 6
walk(0, "at")  # → None
V = ["c", "a", "t", "r", "d", "o", "g", "ca", "cat", "do", "dog", "at", "og"]
# A(0): every token the machine can swallow whole from the start
[t for t in V if walk(0, t) is not None]  # → ['c', 'd', 'ca', 'cat', 'do', 'dog']
# A(3), after "ca"
[t for t in V if walk(3, t) is not None]  # → ['t', 'r']
# the end token only where the text is complete
walk(0, "cat") in accepting  # → True

How a pattern becomes a machine. Two classic steps, both in the code:

flowchart LR
  P["Pattern<br/>cat|car|dog"] --> T[Thompson's construction:<br/>one small machine per piece,<br/>glued with free jumps]
  T --> N[NFA: may be in<br/>several states at once]
  N --> D[Subset construction:<br/>each new state is a set<br/>of NFA states]
  D --> F[DFA: exactly one<br/>state at a time]
  F --> TB[Table: for every state,<br/>which tokens are allowed]

The pattern -?[0-9]+ (an optional minus sign, then digits) compiles to just three states: the start, "saw a minus", and "saw at least one digit", the only accepting one. The lesson's running example, \{"age": [0-9]+\}, compiles to 11.

In code: compile_pattern runs both constructions and returns a DFA; DFA.walk follows text through it; allowed_tokens is , and mask_table precomputes it for every state. RegexConstraint plugs the table into sample_answer.

Why it matters in practice. Integers, dates, enums, phone numbers and fixed-key objects are all patterns. Reframing generation as moving between the states of a machine, with the allowed tokens indexed per state, is the idea of Willard and Louf (2023) behind the open-source Outlines library, and it makes each step's mask a single lookup.

Everyday picture A stack of plates. Each time you open something, a bracket, a brace or a quote, you put a plate on the stack with a note: "an array is open", "an object is open". To close something, you may only take the top plate: close the most recent thing first. When the stack is empty, you're done.

A subway map can't do this job. JSON can nest as deep as you like: [[[[...]]]]. A machine with, say, 50 states can't tell 50 open brackets from 51, so it can't know how many closers it still owes. Counting without limit needs memory without limit. A finite-state machine plus a stack is called a pushdown automaton, and it is exactly enough for nested formats such as JSON, SQL and most programming languages.

Tiny worked example Read {"a": [1, {"b": one character at a time.

flowchart LR
  S1["after {<br/>stack: object"] --> S2["after [<br/>stack: object, array"]
  S2 --> S3["after the inner {<br/>stack: object, array, object"]
  S3 --> S4["after 2}<br/>stack: object, array"]
  S4 --> S5["after ]}<br/>stack: empty, done"]

The checker answers one question about any prefix: can it still be finished?

The schema steers every character. A JSON Schema (see primer.agents.tools) names the fields and their types. This lesson's person schema allows name (a string), age (an integer) and pets (an array of "cat" or "dog"); name and age are required and nothing else is allowed. The checker enforces each rule at the first character that breaks it:

Inside one frame, a small state machine does the work. Here is an object's:

stateDiagram-v2
  [*] --> open: {
  open --> key: quote, if a field may be added
  key --> key: a letter that still spells an unused field
  key --> colon: closing quote, if the key is complete
  colon --> value: colon, then at most one space
  value --> after_value: the value's own frame is pushed and later popped
  after_value --> key: comma, space, quote
  after_value --> [*]: }, only if every required field is present
  open --> [*]: }, only if nothing is required

The leaves of JSON (numbers, true, false, null) are regular patterns, so the checker reads numbers with the machines from section 3. Real engines split the work the same way: patterns for the small pieces, a stack for the nesting.

One rule here is deliberate: at most one space after : and ,. JSON allows any amount of whitespace, and a constrained model that has lost its way can pad with spaces until the budget runs out. Real engines limit whitespace for the same reason.

In code: SchemaChecker.step reads one character and returns the new stack (a tuple of Frame entries), or nothing when the prefix is dead; SchemaChecker.status answers open, dead or complete for a prefix; SchemaChecker.open_containers shows the stack; SchemaConstraint tries every token against the stack at each step.

Why it matters in practice. This is how a schema becomes a guarantee: compile the schema into grammar rules, run them as a pushdown automaton, and mask every token that would kill it. Geng et al. (2023) showed the approach works for structured tasks without any fine-tuning, and PICARD (Scholak et al., 2021) did the same for SQL by parsing incrementally. The stack has a cost: it can grow without limit, so the masks can't all be tabled in advance as they were for a pattern. Section 5 comes back to that.

Constrained decoding guarantees the shape. It does not guarantee a good answer, and it isn't free.

The mask changes what the model says

Everyday picture A satellite navigation system that only forbids illegal turns, one junction at a time, and never looks ahead. It happily takes the motorway because the motorway looks fastest right now, and only at the end discovers that the one legal exit is a long detour. A driver who could see the whole map would have taken the side road from the start.

Tiny worked example 1: forced to invent. The model is asked for a person's age, but the text never says it. The model's honest belief for the next token:

The mask throws away 80% of the model's belief, and the answer is a made-up age, delivered as confidently as a real one. The toy model does this too: told to write the person schema while it "wants" to write only a name, it is forced to add an age, and invents numbers such as 9700. The fix is in the schema, not the decoder: allow null ("type": ["integer", "null"]), or add a field for "not stated". A related finding (Tam et al., 2024): forcing a strict format from the first token can hurt a model's reasoning, so let the model reason in free text first, or put a reasoning field before the answer field.

Tiny worked example 2: locally tempting, globally wrong. A two-token model. Valid answers must end in "y".

flowchart LR
  S[start] -->|A 0.9| A[A]
  S -->|B 0.1| B[B]
  A -->|x 0.99| AX["Ax: invalid"]
  A -->|y 0.01| AY["Ay: valid, 0.9 × 0.01 = 0.009"]
  B -->|x 0.1| BX["Bx: invalid"]
  B -->|y 0.9| BY["By: valid, 0.1 × 0.9 = 0.09"]

first = {"A": 0.9, "B": 0.1}
second = {"A": {"x": 0.99, "y": 0.01}, "B": {"x": 0.1, "y": 0.9}}
# P(y) for each valid answer: the model's token chances multiplied
P = {a + "y": first[a] * second[a]["y"] for a in first}
{k: round(v, 3) for k, v in P.items()}  # → {'Ay': 0.009, 'By': 0.09}
# P(y | valid): divide by the total over valid answers
total = sum(P.values())
{k: round(v / total, 3) for k, v in P.items()}  # → {'Ay': 0.091, 'By': 0.909}
# P_mask: step 1 keeps both, step 2 renormalises "y" to 1
{a + "y": first[a] * (second[a]["y"] / second[a]["y"]) for a in first}  # → {'Ay': 0.9, 'By': 0.1}

The toy model shows the everyday version: once noise knocks it off its answer, the mask keeps it legal but not sensible, and it writes digits until the closing brace happens to win, as in {"age": 4174209}.

In code: forced_choice renormalises a belief over the allowed tokens and reports the share thrown away; NULLABLE_AGE_SCHEMA is the fix; distortion_example computes both distributions above.

Token boundaries

Everyday picture You can say "forty-two", or spell it "four, two". Both arrive at the same text, but only one is how you would naturally say it.

Tiny worked example The toy vocabulary has a 42 token and single digits, so "42" can be written two ways: 42, or 4 then 2. The whole answer {"age": 42} can be spelled 16 ways, and the person answer 1,536 ways. The mask allows every one of them, but a trained model has almost only ever seen the first, its tokenizer's usual spelling (see primer.ml.tokenization). When the mask forces it onto an unusual spelling, it is in unfamiliar territory and its next choices get worse.

flowchart LR
  S["after the space"] -->|42, the usual token| E[before the brace]
  S -->|4| M[after the 4]
  M -->|2| E

Two more boundary effects follow from the same fact. A single token can cross several structural boundaries at once, such as "} closing a string and an object together; walking the token character by character, as allowed_tokens does, handles that. And if the prompt ends in the middle of what would normally be one token (a prompt ending in {"age": when the model would usually write ": as one token), the natural token is no longer available. Some engines back up one token and let the model rewrite it, which is called token healing.

In code: tokenizations lists every way a vocabulary can spell a text.

The speed of computing masks

Everyday picture Before every keystroke, a proofreader checks every word in the dictionary against the rules: slow. Or: a card for every station, printed once, listing which words fit there: fast, once the cards exist.

Tiny worked example A real vocabulary has around 128,000 tokens. Say they average 4 characters, the answer is 200 tokens long, and the pattern's machine has 50 states. Checking every token at every step walks 200 × 128,000 × 4 = 102.4 million characters for one answer. Building the table walks 50 × 128,000 × 4 = 25.6 million characters once; after that, each step only reads one row of 128,000 yes-or-no entries.

n, V, L_bar, S = 200, 128_000, 4, 50
# W_naive = n · |V| · L̄
n * V * L_bar  # → 102400000
# W_table = S · |V| · L̄ + n · |V|
S * V * L_bar + n * V  # → 51200000
# ten answers: the table's build cost is paid once
10 * n * V * L_bar, S * V * L_bar + 10 * n * V  # → (1024000000, 281600000)

For a schema with nesting, the stack can grow without limit, so no table can cover every situation. XGrammar (Dong et al., 2024) splits the vocabulary: most tokens are context-independent (whether they fit depends only on the current grammar position, not on what is deeper in the stack), and those are prechecked into tables; only the few context-dependent ones are checked against the stack at run time.

In code: mask_cost is the formula; mask_table builds the table once and RegexConstraint reads a row per step, while SchemaConstraint walks every token against the stack at every step, the naive way.

When validating and retrying is enough

Everyday picture Instead of a form that can't be filled in wrong, you let people fill in a blank sheet, check it, and hand it back with a note when it is wrong. Fine if most people get it right first time; miserable if most don't.

Tiny worked example The toy model writes a valid age answer 66.5% of the time. Retrying until it succeeds takes 1 / 0.665 = 1.50 attempts on average, and three tries in a row all fail only 0.335³ = 3.8% of the time. For the longer person object, valid 18% of the time, it takes 5.56 attempts on average: slow and expensive.

flowchart LR
  A[Ask the model] --> V{Validate}
  V -->|valid| D[Use it]
  V -->|invalid| E[Send back the<br/>validator's message] --> A
  E -.->|too many tries| F[Give up or<br/>fall back]

# the toy model's unconstrained rate on the age answer
p = 0.665
# E[attempts] = 1 / p
round(1 / p, 2)  # → 1.5
# (1 - p)^k: three tries, all invalid
round((1 - p) ** 3, 4)  # → 0.0376
# the longer person answer, valid 18% of the time
round(1 / 0.18, 2)  # → 5.56

Validate and retry when: you can't change the decoder (a hosted model without a structured-output option), the model is already right nearly every time, or the rule can't be expressed as a grammar. Constrain when answers are long or nested, the model is small, or latency matters. Either way, keep the validator: a grammar enforces shape, not rules such as minimum, and never truth.

In code: expected_attempts and chance_still_failing are the two formulas.

Everyday picture Two paper forms. One only insists that you write in block capitals: whatever you write is readable, but nothing says what goes where. The other has a labelled box for each field, and tick boxes where only certain answers are allowed. The first is JSON mode; the second is a strict schema.

Tiny worked example Give the toy model a reference answer that leaves out the age, {"name": "Ada"}, and ask 50 times. With JSON mode (the empty schema {}, which allows any JSON value) every finished answer parses: 44 copies of {"name": "Ada"} with the required age missing, one {"name": 42628} whose name is a number, and one bare false. All valid JSON; not one valid person. (The other 3 ran out of budget.) With the person schema, every one of the 37 answers that finish has an age, because the closing brace stays locked until one is written. Since the model had no age to give, it invents one, such as {"name": "Ada","age": 9700,"pets": []}: section 5's warning in action. The other 13 show a second cost of forcing a model off its path: it loses its way and wanders, legally, until the token budget runs out.

A tool call is the same thing with a name attached: the model's arguments are a JSON object that must fit the tool's input_schema (see primer.agents.tools and primer.agents.llm).

sequenceDiagram
  participant App as Your code
  participant API as Model server
  participant G as Grammar engine
  App->>API: messages + tool with a strict JSON Schema
  API->>G: compile the schema (cached for next time)
  loop every token
    G-->>API: mask of allowed tokens
    API->>API: mask, softmax, sample
  end
  API-->>App: tool_use with arguments that fit the schema
  App->>App: business rules: does customer C-999 exist? is the amount above the minimum?

In code: SchemaConstraint with the schema {} is JSON mode, and with PERSON_SCHEMA it is a strict schema; primer.agents.tools.ToolRegistry.definitions shows how a strict tool definition is sent.

Why it matters in practice. You now have three tools and know what each buys. JSON mode guarantees something parseable. A strict schema guarantees the shape your code expects, so the parsing and type-checking code disappears. Validation after the fact still catches what only your program knows. Hosted APIs (for example Claude's structured outputs and strict tool use) and open engines (Outlines, llama.cpp grammars, XGrammar) all run the mechanism built in this lesson: a checker that masks the logits before every draw.

Answer each one out loud or on paper before you open it. If you can explain it, you know it.