constrained-decoding

Constrained decoding guarantees syntax and can degrade reasoning. Published work found strict formats hurt reasoning tasks while helping classification, because a schema demanding the answer first denies the model room to derive it. This lesson covers where the damage comes from, why field order is thinking order, the enum trap that manufactures confident errors, and how to measure the cost.

Recursive formats need a machine with a stack, and a stack breaks the precomputed index because the mask now depends on context. This lesson covers context-free grammars and pushdown automata, XGrammar's split between context-independent and context-dependent tokens, why overlapping grammar work with the GPU makes overhead near zero, and how this interacts with batching and speculative decoding.

The naive mask costs 64 million validity checks per response. The trick that made constrained decoding practical is to notice that the answer depends only on the automaton's current state, so it can be computed once per state and looked up thereafter. This lesson builds that idea: regex to DFA, why the state is a sufficient summary, how JSON Schema compiles down, and what the index costs.

Prompting for a format gives a high success rate, and a high success rate is not a guarantee. This lesson locates the one place in the decoding loop where a guarantee is possible, shows what masking logits does to the probability distribution, works through why a 5 percent failure rate destroys tail latency rather than average latency, and separates the three families of structured output.