Chapter 5.6 β€” Structured Output: From Grammars to Constrained Decoding

Contents

  1. Why "please output valid JSON" isn't enough
  2. Constrained decoding: masking invalid tokens at each step
  3. From regular expressions to finite-state grammars
  4. The tokenization mismatch problem, and the FSM-index trick
  5. Beyond regular languages: context-free grammars and JSON
  6. What constrained decoding costs β€” latency and quality tradeoffs
  7. The alternative: training models to natively emit structure
  8. Interview angle
  9. Self-check questions
  10. Sources

1. Why "please output valid JSON" isn't enough

Chapter 5.5 was about telling whether a model's claimed capabilities hold up under honest measurement. This chapter turns to a narrower, more mechanical question that cuts across all of those capabilities at once: however good a model is at reasoning, retrieving, perceiving, or calling tools (Chapter 5.4), its output still has to arrive as something a program can parse β€” a JSON object with the right keys, an SQL query with balanced parentheses, a function signature with arguments in the right order and type. The obvious first approach is to just ask: put "respond only with valid JSON matching this schema" in the prompt and hope the model complies. It mostly works, which is exactly what makes it dangerous to rely on at scale β€” a next-token-prediction model, however well instruction-tuned, is sampling from a learned distribution over plausible text, not running a parser, and nothing in that sampling process mechanically prevents a stray comma, an unclosed brace, a hallucinated extra field, or a string where the schema demanded a number. At the scale of a single demo this is a rare annoyance you retry past; at the scale of a production pipeline processing thousands of requests a minute, a validity rate of 98% is a steady stream of failed parses, and the obvious mitigations β€” regex-based cleanup, a second LLM call to "fix" the output, retry-on-failure loops β€” all add latency and cost to paper over a problem that a next-token sampler was never actually going to solve reliably on its own.

The rest of this chapter is about a different strategy: instead of hoping the model's free-form sampling happens to produce valid structure, constrain the sampling process itself so that it's mechanically impossible to produce anything else. This moves the guarantee from "usually right, checked after the fact" to "always right, by construction" β€” at some engineering cost, which is worth understanding precisely rather than treating the whole area as a black box a library handles for you.

2. Constrained decoding: masking invalid tokens at each step

Recall from Chapter 1.1 that at every decoding step, the model produces a probability distribution over its entire vocabulary β€” tens of thousands of candidate next tokens β€” and ordinary sampling picks one according to that distribution, however it's been reshaped by temperature or top-p. Constrained decoding intervenes exactly at that point: before sampling, it computes a mask over the vocabulary β€” which of the possible next tokens would keep the output on track to satisfy some formal constraint β€” and sets the logits of every token outside that set to $-\infty$ (equivalently, zeroes their probability after the softmax), so that whatever sampling strategy runs afterward can only ever select from the tokens that are actually valid continuations. The model still contributes exactly the same relative preferences among the valid tokens that it always would; what's removed is only the probability mass on tokens that would break the constraint outright.

The formal constraint is typically expressed as a grammar β€” a JSON Schema, a regular expression, a context-free grammar in a format like GBNF (used by llama.cpp) β€” and the generation process tracks, alongside the usual model state, a parser state for that grammar: which characters are valid next, given everything generated so far and the grammar's rules. Each step, that parser state determines the mask; each accepted token advances the parser state the same way a character-by-character parser would advance after consuming those characters. The output is now guaranteed syntactically valid by construction β€” not because the model got better at following instructions, but because the sampling procedure was never given the option to produce anything else.

3. From regular expressions to finite-state grammars

The simplest and cheapest case is a regular expression: dates in YYYY-MM-DD format, US phone numbers, enum-valued fields with a small fixed set of allowed strings. A regular expression compiles to a finite-state automaton β€” a fixed, finite set of states with transitions labeled by the characters that move you from one state to another β€” and constrained decoding against a regex means tracking which automaton state you're in and, at each step, only allowing tokens whose characters correspond to valid transitions out of that state. A field like "status": "active" where status can only be "active", "pending", or "closed" is exactly this case: a small automaton with a handful of states, cheap to build and cheap to track.

JSON Schema's simpler constructs β€” string fields, enums, fixed-format numbers β€” reduce to regular languages this way without much trouble. The complication starts with the parts of JSON that are recursive: an object whose values can themselves be objects, an array whose elements can themselves be arrays, arbitrarily deep. Finite-state automata, by definition, have no memory beyond which single state they're currently in β€” they cannot count "how many braces are still open" for arbitrarily deep nesting, because that would require unboundedly many states. That's a genuine expressiveness limit, not an engineering inconvenience, and it's what section 5 comes back to.

4. The tokenization mismatch problem, and the FSM-index trick

There's a structural mismatch that makes all of this harder than "just check each token against the automaton": the automaton's transitions are defined over individual characters, but the model doesn't generate characters β€” it generates subword tokens (Chapter 4.1), and a single token can span multiple characters, span a token boundary the automaton wasn't expecting, or even span a partial UTF-8 byte sequence. Naively checking, at every decoding step, whether each of the model's tens of thousands of vocabulary tokens is a valid continuation from the current automaton state β€” by walking that token's characters through the automaton one at a time β€” would add a real, repeated cost to every single step of generation, for every request.

Outlines, introduced by Willard and Louf, solves this by moving that cost out of the decoding loop entirely. Given a grammar, it precomputes an index mapping every automaton state to the specific subset of the model's vocabulary that is a valid continuation from that state β€” walking each vocabulary token against the automaton once, up front, for the finitely many states the grammar has, rather than once per token per generation step. At actual decoding time, producing the mask for a given step is a cheap lookup into this precomputed index by the current automaton state, not a fresh linear scan over the vocabulary β€” the expensive part of the problem is paid once per grammar (which can then be reused across every generation that grammar constrains), not once per generated token.

5. Beyond regular languages: context-free grammars and JSON

JSON's arbitrary nesting depth is a context-free language, not a regular one, which means constraining full, unbounded JSON structurally requires a pushdown automaton β€” a finite-state automaton augmented with a stack that can track open braces and brackets to unbounded depth, popping one off for every closing character and refusing to accept a closer when the stack is empty. Grammar-constrained decoding frameworks that support full context-free grammars β€” llama.cpp's GBNF format, and the approach described by Geng et al. for grammar-constrained decoding of structured outputs more generally β€” extend the same masking idea to this richer automaton: the "current state" that determines the valid-token mask now includes the stack's contents, not just a single finite-automaton state, and advancing the parser after accepting a token means pushing or popping the stack according to the grammar's production rules, not just moving to a new state.

The practical upshot for a working engineer is less about building this machinery from scratch β€” mature libraries (Outlines, llama.cpp's grammar support, Guidance) already implement it β€” and more about knowing which of your structural constraints are "just" a regex (cheap, always efficient) versus genuinely context-free (correct, but with a real per-step cost tied to how deep the stack needs to track), so you can reason about why a deeply nested schema might be slower to constrain than a flat one with the same number of fields.

6. What constrained decoding costs β€” latency and quality tradeoffs

Constrained decoding isn't free, and it's worth being precise about where the cost actually sits rather than treating "grammar-constrained" as strictly better than "unconstrained plus retries" in every case. The FSM-index precomputation amortizes the vocabulary-scanning cost across a grammar's reuse, but tracking a pushdown automaton's stack state, computing masks per step, and β€” for very large vocabularies or very permissive grammar states β€” the sheer size of the valid-token set at some steps, all add real overhead relative to unconstrained sampling, even if it's much cheaper than the naive per-token-per-step vocabulary scan section 4 described.

There's also a subtler, less intuitive cost: forcing the model's output through a grammar's token boundaries can interact badly with how the model was actually tokenized during pretraining. Tam et al.'s study of format restrictions found that constraining models to strict JSON output can measurably hurt task accuracy relative to letting the model reason in free-form text and only structuring the final answer afterward, on some reasoning-heavy tasks β€” the hypothesis being that forcing a rigid output format early can suppress the kind of intermediate free-form reasoning (Chapter 5.1) that the task actually needs, and that grammar-forced token boundaries don't always align with the subword boundaries the model's own tokenizer would have chosen naturally. The practical lesson isn't "avoid constrained decoding" β€” it's "constrain the final answer's format, not necessarily every token from the first one," and to treat the reasoning-versus-formatting tradeoff as a real design decision rather than assuming stricter is always safer.

7. The alternative: training models to natively emit structure

Constrained decoding is an inference-time fix: it doesn't require retraining anything, and it works on top of any base model. The complementary approach is a training-time fix: fine-tune (Chapter 4.5) a model specifically on examples of the structured formats it needs to produce, until emitting valid JSON or a correctly-formatted function call becomes close to the model's default behavior rather than something that has to be mechanically enforced. This is essentially what "native function calling" support in commercial model APIs is β€” the model has seen enough training examples of the target call format that it reliably reproduces it unprompted, without the serving stack needing to run a grammar-constrained decoding loop at all (though several providers still layer constrained decoding underneath as a reliability backstop rather than betting purely on training).

The two approaches aren't mutually exclusive, and the honest framing is a spectrum rather than a binary choice: training-time fixes reduce how often the constraint has to bind at all, which reduces both the quality cost from section 6 and the latency cost of running a grammar-constrained decode on every token; inference-time constraints are what give you a hard guarantee even when the training-time fix isn't perfect, or when the schema is generated dynamically at request time and couldn't have been trained on in advance. A production system asking a model to call one of a small, fixed set of well-documented tools leans on the training-time fix; a system where the target schema varies per request, or where a single invalid output is unacceptable regardless of how rare it is, needs the inference-time guarantee regardless of how well-trained the model already is.

Reasoning, retrieval, multimodal perception, tool use, and now reliable, schema-valid output are all, individually, capabilities and guarantees that expand what a language model can be trusted to do. None of them, on its own, says how to combine them into an actual product: which techniques a given system actually needs, how to architect the pipeline that wires them together under real constraints of latency and cost, and how to keep the whole thing reliable once it's running in production rather than merely capable in a demo. That assembly problem β€” bringing everything this part of the book has covered into one working system β€” is where Part VI, starting with Chapter 6.1, "System Design for LLM Products," turns next.

8. Interview angle

A senior LLM interview will rarely ask you to implement a pushdown automaton from scratch, but it will probe whether you understand exactly what constrained decoding guarantees and at what cost, usually through questions like:

  • "Why isn't 'just prompt the model to output valid JSON and validate afterward' good enough for a production pipeline?" β€” a strong answer names the actual failure mode: a next-token sampler has no mechanism preventing an invalid token, so even a high compliance rate produces a steady stream of parse failures at volume, and the usual fixes (retries, a repair pass) add cost and latency to work around a problem constrained decoding removes at the source.
  • "How does constrained decoding actually enforce validity β€” what's being changed about the sampling process?" β€” a strong answer describes masking: computing, from the grammar's current parser state, the subset of vocabulary tokens that are valid continuations, and setting every other token's probability to zero before sampling, so the model's relative preferences among valid tokens are preserved but invalid tokens simply can't be selected.
  • "Why can't you just check each vocabulary token against the grammar at every decoding step, and what does Outlines' FSM-index approach do instead?" β€” a strong answer identifies the cost of a naive per-step, per-token scan over tens of thousands of vocabulary entries, and explains that precomputing a state-to-valid-token-subset index once per grammar turns each step's masking into a cheap lookup rather than a fresh scan.
  • "Is grammar-constrained output strictly better than letting the model reason freely and structure only the final answer?" β€” a strong answer resists the trap of "always constrain everything," citing evidence that forcing rigid structure too early can suppress useful intermediate reasoning, and argues for constraining the final answer's format while leaving room for free-form reasoning beforehand on tasks where that reasoning matters.

The through-line interviewers are checking for is whether you can locate exactly where a guarantee comes from β€” a trained tendency versus a mechanical constraint β€” and reason about the real cost and failure modes of each, rather than treating "structured output" as a solved problem any library makes free.

9. Self-check questions

  1. Why does a next-token-prediction model's own probability distribution offer no guarantee of syntactic validity, even after extensive instruction tuning?
  2. Describe exactly what changes about the sampling process when constrained decoding is applied at a given step.
  3. Why is JSON's arbitrary nesting depth not expressible as a regular language, and what kind of automaton is needed instead?
  4. What specific cost does Outlines' FSM-index precomputation remove from the decoding loop, and when is that cost paid instead?
  5. What did Tam et al.'s study find about forcing strict output formats on reasoning-heavy tasks, and what does it suggest about where to apply constraints?
  6. Contrast constrained decoding and fine-tuning for structured output as two solutions to the same problem β€” what does each cost, and when would you reach for one over the other?

10. Sources

  • Willard, B., & Louf, R. (2023). Efficient Guided Generation for Large Language Models (Outlines). arXiv:2307.09702. https://arxiv.org/abs/2307.09702
  • Geng, S., Josifoski, M., Peyrard, M., & West, R. (2023). Grammar-Constrained Decoding for Structured NLP Tasks without Finetuning. EMNLP 2023. arXiv:2305.13971. https://arxiv.org/abs/2305.13971
  • Beurer-Kellner, L., Fischer, M., & Vechev, M. (2023). Prompting Is Programming: A Query Language for Large Language Models (LMQL). PLDI 2023. arXiv:2212.06094. https://arxiv.org/abs/2212.06094
  • Tam, Z. R., Wu, C.-K., Tsai, Y.-L., Lin, C.-Y., Lee, H.-Y., & Chen, Y.-N. (2024). Let Me Speak Freely? A Study on the Impact of Format Restrictions on Performance of Large Language Models. arXiv:2408.02442. https://arxiv.org/abs/2408.02442

Self-check quiz

Test your understanding of this chapter with a short quiz β€” a mix of concept questions and quick calculations.

Why isn't prompting a model to "output valid JSON" a reliable solution at production scale?

Explanation: The model is sampling from a learned distribution over plausible text, not running a parser β€” nothing mechanically prevents an invalid token, and even 98% validity is a steady stream of failures at volume.

What does constrained decoding actually change about the sampling process at each step?

Explanation: The mask zeroes out invalid tokens' probability entirely β€” the model's relative preferences among valid tokens are preserved, but invalid ones can never be selected.

Why can't a plain finite-state automaton constrain JSON's arbitrary nesting depth?

Explanation: Arbitrary nesting depth is a context-free language; representing it correctly needs a pushdown automaton with a stack, not a fixed finite set of states.

What specific cost does Outlines' FSM-index precomputation remove from the decoding loop?

Explanation: Outlines precomputes a state-to-valid-token-subset index once per grammar, turning per-step masking into a cheap lookup instead of a fresh scan over the whole vocabulary.

What did Tam et al.'s study on format restrictions find about forcing strict JSON output on reasoning-heavy tasks?

Explanation: Forcing rigid structure too early can suppress the kind of intermediate reasoning some tasks need β€” the practical lesson is to constrain the final answer's format rather than every token from the start.

How does grammar-constrained decoding handle a context-free grammar like full JSON, compared to a plain regex?

Explanation: A pushdown automaton tracks open braces/brackets to unbounded depth via a stack; the parser state used for masking now includes that stack, not just a single automaton state.

What is the training-time alternative to inference-time constrained decoding?

Explanation: This is essentially what native function-calling support in commercial APIs is β€” enough training examples that the model reliably reproduces the format unprompted.

When does an inference-time constraint remain necessary even if a model has been well fine-tuned for structured output?

Explanation: Training-time fixes reduce how often the constraint has to bind, but a hard guarantee β€” especially for dynamically generated schemas β€” still requires the inference-time mechanism.

Why does tokenization complicate constrained decoding, specifically?

Explanation: This mismatch is exactly why naively checking each vocabulary token character-by-character against the automaton at every step is expensive, motivating the FSM-index precomputation.

What is the correct way to think about constrained decoding versus fine-tuning for structured output?

Explanation: The two are complementary: a system with a small fixed set of well-documented tools leans on training; one with per-request dynamic schemas needs the inference-time guarantee regardless.

A production pipeline processes 12,000 requests per minute. An unconstrained model achieves a 98% valid-JSON compliance rate. How many failed parses occur per minute?

Explanation: 12,000 Γ— (1 βˆ’ 0.98) = 12,000 Γ— 0.02 = 240 failed parses per minute β€” a steady, costly stream of failures even at a rate that looks good in a demo.

A model's vocabulary has 32,000 tokens, and a grammar's finite-state automaton has 25 distinct states. Building Outlines' FSM-index requires walking each vocabulary token against the automaton once per state. How many total token-state checks does this precomputation require (in thousands)?

Explanation: 32,000 tokens Γ— 25 states = 800,000 checks, i.e. 800 thousand β€” paid once per grammar, not once per generated token during decoding.