A grammar masks all but seven of GPT-2's 50,257 tokens to force valid output

The guarantee holds because the tokens are gone

A model decoding one token at a time produces a distribution over its whole vocabulary at each step. Constrained decoding adds a grammar that tracks which tokens could legally come next, and sets the logits of every other token to negative infinity before the softmax, so the sampler can only draw a token that keeps the output valid.¹ That one layer, added to the distribution and nothing to the model, is what lets OpenAI's Structured Outputs promise it will "always generate responses that adhere to your supplied JSON Schema."² The word "always" is not a claim about the prompt. It is enforced by deletion.

Compile a grammar that permits only the JSON value true or false, run it against the real 50,257-token GPT-2 vocabulary, and at the first step exactly seven tokens survive. The other 50,250 have their probability driven to zero, no matter what the model wanted. Building that machine from the grammar up, in runnable Python, exposes the three bills the naive version hides: the index it must precompute, the gap between a grammar that counts characters and a model that emits tokens, and the places where forcing structure changes what the model says.

A grammar is a machine you can walk

Willard and Louf's contribution, the method behind the Outlines library, is to reduce guided generation to walking a finite-state machine: the grammar becomes states and transitions, and generating a valid string is nothing more than following transitions that exist.¹ For a regular language the machine is small enough to write by hand. Take the grammar true | false. Ten states, one transition per character, two accepting states where a complete word ends.

# grammar as a DFA over characters: the JSON value  true | false
# state -1 is the implicit dead state; accepting states are 5 and 9.
DELTA = {
    (0, "t"): 1, (1, "r"): 3, (3, "u"): 4, (4, "e"): 5,
    (0, "f"): 2, (2, "a"): 6, (6, "l"): 7, (7, "s"): 8, (8, "e"): 9,
}
ACCEPT, START = {5, 9}, 0

def step(state, ch):
    return DELTA.get((state, ch), -1)

def walk(state, s):
    for ch in s:
        state = step(state, ch)
        if state == -1:
            return -1
    return state

The reference implementation, outlines-core, exposes exactly this shape around a real tokenizer: build a Vocabulary from a pretrained model, combine it with a regular expression into an Index, and read off allowed_tokens(state) and next_state(state, token) at each step.³ The hand-written machine above is the toy version of that Index. What is missing is the bridge from character transitions to whole tokens, and building that bridge is the first real cost.

The cost hides in the one-time compile

The masking step runs once per generated token, so it has to be cheap. The naive way to enforce a grammar is, at each step, to loop over the whole vocabulary and test each token against the machine. Willard and Louf call this out as "a fixed O(N) cost for each token generated, where N is the size of the LLM's vocabulary."¹ Their fix is to precompute, for every state, the set of tokens that keep the output legal from that state. With that map in hand the per-step work is a single lookup: "using a hash-map for σ can make the m step in Algorithm 2 cost only O(1) on average."¹

from tokenizers import Tokenizer

tok = Tokenizer.from_pretrained("gpt2")           # the real GPT-2 tokenizer
V = tok.get_vocab_size()                          # 50257
STRINGS = [tok.decode([i]) for i in range(V)]     # every token's literal text

def build_index():
    # for each reachable state, the token ids whose whole string stays legal.
    states = {START} | set(DELTA.values())
    return {q: {i for i in range(V) if STRINGS[i] and walk(q, STRINGS[i]) != -1}
            for q in states}

index = build_index()
print(len(index[START]), "of", V, "tokens legal at the start state")

7 of 50257 tokens legal at the start state

The O(1)-versus-O(N) trade is bought with a one-time preprocessing pass, and that pass is where the bill lands. Willard and Louf describe their construction, Algorithm 4, as building "a map from FSM states to subsets of V" whose "run-time cost is effectively irrelevant, although it theoretically requires memory equal to the number of states in the FSM."¹ For a ten-state boolean the map is tiny. For a real JSON Schema it is not free, and the independent JSONSchemaBench measured the gap: compiling a schema into an index took Outlines about 3.5 seconds, against roughly 0 milliseconds for Guidance's incremental approach on the same schemas.⁴ Hosted systems pay the same cost and hide it behind a cache. OpenAI states plainly that "the first request you make with any schema will have additional latency as our API processes the schema, but subsequent requests with the same schema will not."² The mask is cheap; the compile that makes it cheap is what you schedule around.

The grammar counts characters, the model emits tokens

Here is the joint where it is tempting to wave a hand, so slow down and ask the plain question. The machine has transitions on single characters: t, then r, then u. The model does not emit characters. It emits tokens, and a token is a string of one or more characters chosen by the tokenizer. So which states does a single token move the machine through, and how does the index know?

for s in ["true", "tr", "t", " true"]:
    tid = tok.encode(s, add_special_tokens=False).ids[0]
    print(f"{s!r:>7}  id {tid:>5}  start state to state {walk(START, s)}")

 'true'  id  7942  start state to state 5
   'tr'  id  2213  start state to state 3
    't'  id    83  start state to state 1
' true'  id  2081  start state to state -1

The answer to the childlike question is that the index does not map characters to states. It maps each state to the tokens whose entire string can be consumed from there. Willard and Louf's Algorithm 3 finds, for a token string, "the states through which the FSM would traverses [sic] when accepting the provided string," and Algorithm 4 stores that per state.¹ So true is a legal one-step move, while  true, with a leading space, is a different id and dies at once, because the machine has no space transition. That is the alignment tax in miniature: the mask has to be computed in the model's token alphabet, not the grammar's character alphabet, and the two do not line up.

The tax is small but not zero, and it does not fully vanish into the precomputed index. XGrammar measured it on a production vocabulary: for Llama-3.1's 128k tokens under a JSON grammar, the tokens whose legality depends on runtime context "account for only a minor proportion, amounting to less than 1% (1134 out of 128k)."⁵ Those 1,134 tokens are the ones a static state-to-token map cannot fully settle in advance, and they have to be rechecked as generation proceeds.

Read the change off one step

With the index built, the per-step mask is four lines: copy the logits, set every token not in the current state's allowed set to negative infinity, and let the softmax do the rest. The claim to check is that the mask alone changes the distribution. Take one concrete step and print the vector.

import numpy as np

def mask(logits, state):
    out = logits.copy()
    out[[i for i in range(len(logits)) if i not in index[state]]] = -np.inf
    return out

def softmax(x):
    x = x - x.max(); e = np.exp(x); return e / e.sum()

# one concrete step: the model, asked for a boolean, scores these tokens.
# " maybe" is its favourite, but the grammar forbids it here.
scores = {" maybe": 8.2, "true": 7.9, " yes": 6.4,
          "false": 6.1, "tr": 3.0, " I": 2.5}
logits = np.full(V, -30.0)
for s, v in scores.items():
    logits[tok.encode(s, add_special_tokens=False).ids[0]] = v

before, after = softmax(logits), softmax(mask(logits, START))
for s in scores:
    i = tok.encode(s, add_special_tokens=False).ids[0]
    lg = "-inf" if i not in index[START] else f"{logits[i]:.1f}"
    print(f"{s!r:>8}  logit {lg:>4}  p_before {before[i]:.4f}  p_after {after[i]:.4f}")

' maybe'  logit -inf  p_before 0.4908  p_after 0.0000
  'true'  logit  7.9  p_before 0.3636  p_after 0.8527
  ' yes'  logit -inf  p_before 0.0811  p_after 0.0000
 'false'  logit  6.1  p_before 0.0601  p_after 0.1410
    'tr'  logit  3.0  p_before 0.0027  p_after 0.0063
    ' I'  logit -inf  p_before 0.0016  p_after 0.0000

Read the first line. Before the mask, the model's most likely next token is  maybe at probability 0.49, the kind of hedge that would break a boolean field. It is not in the seven legal tokens, its logit becomes negative infinity, and after the softmax its probability is 0.0000. The token true, second before the mask at 0.36, absorbs most of the freed mass and comes out at 0.85. The mask never reorders the legal tokens, so true stays ahead of false; it only removes options.

This runs in production, not only in a paper. llama.cpp ships grammar-constrained sampling in its GBNF format, "a format for defining formal grammars to constrain model outputs," applying the same per-step mask inside a local inference engine.⁶ The per-step cost, done well, is nearly invisible. XGrammar reports masking latency "less than 40us" per token and up to a 100x reduction against Outlines v1.0 and llama.cpp, and its end-to-end overhead against unconstrained generation is close to nothing: per-output-token latency of 6.2 milliseconds without constraint versus 6.3 with it at batch size one, 9.0 versus 9.1 at batch size 16.⁵ The mask itself is cheap. What is not free is what the mask can do to the content underneath the shape.

When the shape bends the answer

The mask guarantees shape. The uncomfortable question is whether forcing the shape changes what the model would have said, and here the evidence genuinely conflicts. Tam and colleagues, in "Let Me Speak Freely?", measured "a significant decline in LLMs' reasoning abilities under format restrictions."⁷ On GSM8K grade-school math with GPT-3.5-turbo, accuracy fell from 75.99% in free-form natural language to 49.25% under a constrained JSON mode. On a last-letter-concatenation task, LLaMA-3-8B dropped from 70.07% to 28.00%.⁷ Taken alone, that is a case against ever reaching for the mask on a task that requires thinking.

It should not be taken alone. Two independent re-runs, holding the prompt fixed, found the opposite. The Outlines vendor dottxt, a party with a stake, argued the original study "uses different prompts for structured generation and unstructured generation" and conflated true masked decoding with a fine-tuned "JSON-mode" that "has no guarantees about the returned value." With matched prompts their re-run showed structured generation edging ahead, GSM8K moving from 0.77 to 0.78.⁸ The neutral referee agrees. JSONSchemaBench, built by neither the Outlines nor the OpenAI team, reports that "the constrained decoding, regardless of the framework, achieves higher performance than the unconstrained setting," with Guidance at 83.8% on GSM8K against an unconstrained 80.1%.⁴

The two results reconcile, and the reconciliation is the practical rule. The mask changes content only when the legal set at a step excludes the token the model needed to reason well. Force a schema that puts the answer field before any room to work, and the model must commit before it has thought, which is the failure Tam's constrained runs mostly measure. Give it a schema with a place to reason first, or match the prompt, and the measured harm disappears. The degradation tracks the schema and the prompt, not the logit mask.

One more honesty check sits underneath the word "guarantee." The guarantee is validity against the grammar the engine actually compiled, which is not always the schema you wrote. OpenAI concedes that "while Structured Outputs supports much of JSON Schema, some features are unavailable either for performance or technical reasons."² JSONSchemaBench makes the limit quantitative: on a set of hard real-world GitHub schemas, empirical coverage fell to 41% for Guidance, 39% for llama.cpp, 28% for XGrammar, and 3% for Outlines, the last mostly to timeouts.⁴ A schema the engine cannot compile is either reduced to one it can or refused; the mask keeps its promise only over the grammar it built.

A grammar becomes a machine, the machine becomes a per-state token index, and the index becomes a mask that deletes the illegal options before the model draws. It buys guaranteed structure for a one-time compile, a one-percent alignment tax handled at runtime, and the discipline to write a schema that lets the model reason before it commits. Reach for it when a downstream parser must never fail. Design the schema, not just the type, when the answer needs thought before shape.¹