Vol. XXII · Decoding Plate 5 of 8constrained decoding, structured output, JSON, grammar, logit masking, function callingAE

Structured Output.

Mask every token that would break the format. The output is then valid by construction.

Programs that call a language model usually need output they can parse: JSON matching a schema, a function call with typed arguments, a value from a fixed list. Prompting for the format works most of the time; the remainder breaks the program. Constrained decoding fixes it at the sampler: at each step, compute which tokens keep the output a valid prefix of the format — using a grammar or a regular expression compiled into an automaton over the vocabulary — set every other token’s probability to zero, renormalise and sample. Libraries such as Outlines and XGrammar and the structured-output modes of the main APIs work this way.

The course model micro (1.8 million parameters, four layers, trained on this course’s own plates in English and Chinese; plate I.9) runs in the page. micro was never trained to produce JSON. The workshop asks it for an object of the form {"name": "…", "age": N} with and without the constraint and measures validity and how much probability the constraint had to remove at each step.

Below: the text sampled with or without the constraint, for the chosen seed; readouts give validity over eight seeds and the mean share of probability removed per step.

What you will learn
Workshop
micro, prompt “Answer in JSON: ”, temperature 1, up to 32 tokens. Format: {"name": "up to 12 letters and spaces", "age": one to three digits}. Valid: the output matches the format exactly. Removed: probability of tokens masked at each step, averaged over steps and seeds.

Valid by construction, right by training

Unconstrained, micro produced the format in 0% of eight samples: it continues the prompt with course prose, as it was trained to. With the constraint 100% are valid, after about 23 tokens each — and the mask removed 80% of the probability at an average step. That share is the measure of how much the format was imposed rather than chosen: the sampler did the work the model could not.

For a model trained on JSON the removed share is small, and constrained decoding only catches the rare slip. For a model far from the format, the output is valid and meaningless — here, a name assembled from whatever letters micro found least unlikely. A constraint guarantees syntax; correct content still comes from training (plate XVII.1), and studies have found that forcing a strict format can lower accuracy on reasoning tasks when it leaves no room to think first, which is why many systems let the model reason freely and constrain only the final answer.

The hard engineering is speed: checking every vocabulary token against the grammar at every step is too slow, so libraries precompile the grammar into token-level automata and cache the masks.

Terms

Constrained decoding
Masking tokens that would break a format before sampling.
Grammar
Rules defining the valid strings, such as a JSON schema.
Valid prefix
A partial output that can still be completed into a valid one.
Function calling
Output that is a typed call to a tool, often produced under a constraint.
Constrained decoding makes output valid by construction; the probability it removes says how far the model was from the format, and validity is not correctness.

Sources

  1. Willard and Louf, “Efficient Guided Generation for Large Language Models”, arXiv:2307.09702, 2023 (Outlines).
  2. Dong et al., “XGrammar: Flexible and Efficient Structured Generation Engine for Large Language Models”, arXiv:2411.15100, 2024.
  3. Tam et al., “Let Me Speak Freely? A Study on the Impact of Format Restrictions on Performance of Large Language Models”, arXiv:2408.02442, 2024.