Grammar-Constrained Decoding

At every step, work out which tokens could still lead to a valid output and set the probability of all the others to zero. The model can then only produce something the grammar accepts — not usually, but always, because the invalid continuations were never on the table.

The implementation is a mask over the logits, computed from a parser's state. Doing it naively costs a grammar check per vocabulary entry per step, which is why the useful work here has been on precomputation — compiling the grammar to an automaton whose state indexes directly into a precomputed mask, so the per-step cost stops depending on the vocabulary size. Constrained Decoding is the general idea; this is the version where the constraint is a formal grammar and the guarantee is total.

The mask does something to the distribution that is worth being precise about: it renormalises over the allowed set, so the relative probabilities among survivors are preserved but the sequence-level distribution is not the model's. A continuation the model strongly preferred can be removed at step one, and everything downstream is then conditioned on a prefix the model would rarely have chosen. That is why constrained output can be well-formed and worse — the guarantee is on the shape, never on the content.