Constrained Decoding: How Schema Enforcement Actually Works

Schema enforcement is not the model trying harder. It is a filter between the model and the sampler that deletes every token which cannot legally come next. Nothing about the model changes; the set it may draw from does.

Where the mask goes

A normal decoding step produces one logit per vocabulary entry, and the sampler turns those into a choice. Constrained decoding inserts one step:

  prompt + tokens so far
          |
          v
   [ forward pass ]  ->  logits, one per vocab entry  (|V| ~ 100k-200k)
          |
          v
   [ constraint  ]  <---- automaton state, advanced by the last token
   [ token mask  ]        legal tokens keep their logit
          |               everything else is set to -inf
          v
   [ sampler ]  temperature / top-p / top-k
          |
          v
      chosen token  ----> advance automaton state ----> next step

The automaton is compiled once from your schema. At each step it knows which characters may come next, and therefore which vocabulary entries may come next. Everything else gets -inf, which survives the softmax as probability zero. An illegal token is not improbable. It cannot be drawn.

One token, step by step

Take the schema {"type":"object","properties":{"ok":{"type":"boolean"}}} and follow the generation:

step  emitted so far     automaton says next may be     tokens left unmasked
1     (nothing)          '{'                            {  {"  {"o  ...
2     {                  '"' or '}'                     "  "ok  "}   ...
3     {"ok               '"'                            "  ":  ":t   ...
4     {"ok":             't' or 'f'                     true  tr  fa  false
5     {"ok":true         '}'                            }
6     {"ok":true}        end                            <eos>

Two things in that table matter more than the rest. At step 4, every token beginning with a digit, a quote or a letter other than t/f has been deleted from the vocabulary — the model cannot answer "yes" even if that is what it wanted. And at step 5, exactly one token survives, so no sampling decision is being made at all; some engines skip the forward pass entirely when the mask leaves a single option, which is where the speedups reported for constrained decoding come from.

Why it is not slow

The obvious objection is that checking a hundred thousand tokens against a grammar at every step would dominate the forward pass. The published engines answer it by not doing the check at run time.

Willard and Louf’s Efficient Guided Generation for Large Language Models (arXiv:2307.09702), the paper behind Outlines, reformulates the problem as indexing: build a finite-state machine from the regular expression or schema, then precompute, per state, the set of vocabulary tokens that advance it. The per-step work becomes a lookup rather than a scan. XGrammar (arXiv:2411.15100) extends the same idea to context-free grammars with a persistent pushdown stack and an adaptive mask cache, splitting the vocabulary into tokens that can be decided ahead of time and the smaller set that must be checked live.

The practical consequence for a caller: the cost is paid at schema compile time, not per token. Sending the same schema repeatedly is cheap. Generating a new schema per request — dynamic enum values, a field list assembled at run time — pays the compile every call, and on a busy service that is the version of this you will actually feel. Where a provider documents a first-request latency penalty for a new schema, this is what it refers to, and the mitigation is to keep your schemas finite in number rather than to make them smaller.

The mask also has to live somewhere, and that somewhere is the serving stack. This is why constrained decoding is a property of who runs the model rather than of the model: the weights have nothing to do with it, and an open-weights model behind two inference servers gets whatever each server implements. It is also why you cannot add schema enforcement from the client side. A wrapper library that validates the response and retries on failure is doing something genuinely different and strictly weaker — it converts an invalid document into a second call rather than into an impossibility, and its guarantee is probabilistic where a mask’s is not.

The tokenizer problem

The grammar is defined over characters; the model emits tokens, and tokens straddle character boundaries. If the legal next character is " then the token "ok": is legal too — it starts with a quote — and accepting it commits to three grammar decisions at once. Engines that handle this well are said to “coalesce”; engines that handle it badly force the model onto unusual token boundaries it never saw in training, which is one real mechanism by which constraints can shift output quality.

This is also why a constraint that looks harmless can misbehave. Fixing an enum member to "NO" when the natural tokenisation of the model’s answer is " No" with a leading space puts the decoder somewhere it has little training signal.

Does it hurt quality?

This is contested and you should know that it is. Tam et al., Let Me Speak Freely? A Study on the Impact of Format Restrictions on Performance of Large Language Models (arXiv:2408.02442), reported that requiring structured formats degraded performance on reasoning tasks relative to free-form answers. The finding was challenged on methodology — critics argued the comparison conflated format enforcement with prompt phrasing and with denying the model room to reason — and later work reports smaller or absent effects. Treat it as an open question, not a settled one.

The design response is uncontroversial either way, and costs nothing: give the model a place to think inside the schema. A leading reasoning string field, generated before the answer fields, restores the room that a bare answer schema takes away, because decoding is left to right and later fields are conditioned on earlier ones. Field order is a design tool, not a formatting detail.