Structured Output and Constrained Decoding

Reject and retry is a bet, and you pay for the losses

Level 11's eval and guardrail lesson later formalizes this, and the short version is that the standard answer to a malformed JSON response is a validator that rejects it and a retry that tries again. That answer works, and it has a price with three parts: you pay for the tokens of the generation that failed, you pay again for the generation that replaces it, and the request's latency is now a coin flip instead of a distribution. Put numbers on it before deciding whether the price is acceptable, because the number that matters is not the failure rate, it is the failure rate multiplied by your traffic.

The mechanism: a mask over the logits

Constrained decoding removes the bet. At every decoding step the model produces a logit for each token in its vocabulary and a sampler picks one from that distribution. Constrained decoding inserts one operation between those two: a grammar compiled from your schema reports which tokens could legally come next given everything emitted so far, and the logit of every other token is set to negative infinity before the sampler runs. The illegal token is not rejected after the fact. It has no probability of being sampled at all.

schema  { "name": string, "age": integer }
emitted { "name": "ada", "age":
grammar state: expecting the first character of an integer

vocabulary (a toy 8 tokens)      logit     legal here?     masked logit
  the token 0                      2.1        yes              2.1
  the token 1                      3.4        yes              3.4
  the token 9                      1.2        yes              1.2
  the token -                      0.7        yes              0.7
  a single space                   4.9        yes              4.9
  a double quote                   5.8        no              -inf
  a closing brace                  4.1        no              -inf
  the token ' null'                3.9        no              -inf

the model WANTED the double quote: 5.8 was the highest logit in the set.
it cannot have it, because that token is no longer in the distribution the
sampler sees. no validator ran, no output was parsed, nothing was retried.

Why the naive implementation is too slow, and what fixed it

A vocabulary is on the order of 128,000 tokens. Testing each one against the grammar at each step is the obvious implementation and it is quadratic in all the wrong places: the test runs once per generated token, for every sequence in the batch, on the path between the forward pass and the sampler.

Outlines' contribution is to move that work offline. Compile the schema into a finite state machine, then precompute, for each state of that machine, the set of vocabulary tokens legal from it. At decode time the engine looks up the current state and receives the allowed set, so the average per-step cost is a lookup rather than a scan.

one decoding step, vocabulary of ~128,000 tokens

naive
  for each of 128,000 tokens: would the grammar accept it here?
  128,000 grammar tests per generated token, per sequence in the batch
  runs between the forward pass and the sampler, so it is on the critical path

precomputed index (the Outlines approach)
  build time  for each FSM state, store the set of token ids legal from it
  decode time look up the current state, take the set. constant on average
  the work has moved into build time and into memory

what changed is not the total work. it is WHERE the work is, and an index
built once per schema is amortized across every token of every request that
uses that schema. which is why a compiled-schema cache is part of the design

The measured result is that a good engine is not the bottleneck. llguidance reports on the order of 50 microseconds of CPU per token on a 128k tokenizer, against roughly 1.5ms for a full unoptimized JSON-schema mask, and states that it can sustain batch sizes in the thousands against a 10ms forward pass without becoming the limiting factor. The design consequence is worth stating plainly: a well-built grammar engine disappears into the noise, and a badly built one becomes your serving bottleneck, so this is a component you benchmark rather than assume.

FSM, pushdown, and the problem with subword tokens

A regular expression compiles to a finite state machine, and so does a flat schema with fixed keys and typed values. Nesting does not. Matching arbitrarily deep objects and arrays means counting how many braces are open, and counting is exactly what a finite state machine cannot do, so a nested schema needs a pushdown automaton: a state machine plus a stack. That is why engines differ in which schema features they accept. A feature list is really a statement about which class of automaton the engine implements.

Then the problem that makes this harder than it looks on paper. The grammar is defined over characters, and the model emits tokens, and one token can span a grammar boundary. A tokenizer will happily contain a single token for the two characters that close a string and open the next key. The compiler therefore cannot map grammar transitions onto tokens one for one; it has to treat each token as a short string that drives the automaton through several transitions at once, and exclude any token whose character sequence would drive it into a dead end partway through.

Who pays for compilation

Compiling a schema into an automaton and its token index is real work, and where that work happens changes the architecture. A service with five fixed schemas compiles at startup, caches the indexes forever, and never thinks about it again. A service with thousands of tenant-defined schemas that change daily has moved compilation onto the request path for every schema it has not seen before.

Table

Same technique, two different systems. The right-hand column is a caching and admission-control problem wearing a structured-output costume, which is why schema validation at save time belongs in the design.

Question	Five fixed schemas	Thousands of tenant schemas
When does compilation happen	Once, at process start	On first sight of a schema, on the request path
Where does the index live	Memory, for the life of the process	An LRU cache with a memory bound and an eviction policy
What does a cold start cost	Nothing a user sees	The p95 you will be asked to defend
What do you monitor	Very little	Compile time, cache hit rate, index memory per schema
What does neglect look like	Not applicable	One tenant saves a pathological schema and stalls a serving node

Hosted providers solve the same problem on their side of the API, which is why Anthropic documents a cache of compiled schemas held for twenty-four hours.

The engine default that is not an engine

vLLM's default structured-output backend is auto, and auto is a dispatcher rather than an implementation. It tries XGrammar first, falls back to llguidance, and routes to Outlines for specific cases such as certain tokenizers and schema features the faster engines do not support. So "vLLM uses XGrammar" is wrong as a flat statement, and the documentation says the dispatch behavior may change between releases.

The transferable lesson is about defaults in general. A dispatching default exists for compatibility, which means it optimizes for your request succeeding rather than for it succeeding the same way twice. If you need reproducible latency or a fixed answer to "which schema features do we support", pin the backend explicitly and treat a change to it as a release event.

Quality effects, and the bridge to tool calling

Constraining the output shape is not neutral with respect to the content. Forcing the model to begin emitting structure immediately takes away the free-text span it would otherwise use to work through the problem, and the standard mitigation is to let it reason in an unconstrained span and constrain only the final answer span. That costs tokens and buys accuracy on anything that needs a chain of steps before the answer.

A tool call is this same mechanism behind a different API. The provider compiles your tool's argument schema and constrains generation against it, which is exactly why a well-formed tool call is guaranteed and a correct one is not.

Interview nuance: name the forcing controls and their side effects, because those are what an interviewer probes next. Forcing a specific tool suppresses the natural-language preamble the model would otherwise produce, which matters if anything downstream was reading it. Turning parallel tool calls off guarantees at most one call per turn, which simplifies your executor and serializes work that could have run together. Both are behavior changes disguised as configuration.

Recap: reject-and-retry pays for the bad generation, the replacement, and a tail, and never reaches zero; constrained decoding masks every illegal token at each step so malformed output cannot be sampled; the naive mask is a scan of a 128k vocabulary per token, and precomputing an index per automaton state is what moved that cost offline; nested schemas need a pushdown automaton and subword tokens straddle grammar boundaries; compilation cost is a caching problem once schemas are tenant-defined; pin the backend if you need reproducibility; and well-formed is not correct.

Sources: Outlines: efficient guided generation · XGrammar · llguidance · vLLM structured outputs