The tokeniser does not know your grammar

The one-sentence explanation of grammar-constrained decoding is that a parser sits beside the model and, at each step, masks out every token that would break the grammar. It is a good sentence and it hides the whole difficulty. The parser reads characters. The model emits subword tokens, and the tokeniser that made those tokens was trained on text frequencies with no knowledge that a JSON string ends at a quote or that a key is followed by a colon. So the units the model chooses from do not line up with the units the grammar is written in, and every real engine's cost and correctness come down to how it handles the tokens that cross a boundary. Those tokens are a computable set, and its size, not the rule count of the grammar, is what predicts the per-token overhead.

Two segmentations of one string

Take the smallest JSON object that has anything in it. A grammar sees nine terminals: an opening brace, a quoted key, a colon, a quoted value, a comma, a second key, a colon, a number and a closing brace. A byte-pair tokeniser sees something else. Run through the cl100k vocabulary used by a generation of OpenAI models, via the public tiktoken library, the same object becomes nine tokens too, but they are not the same nine: the first token is the brace fused with the opening quote of the key, the third is the closing quote, the colon and the opening quote of the value fused into one, and the fifth is a quote, a comma and a quote. Four of the nine tokens span a boundary the grammar cares about.

The straddling tokens are the problem. A token that lies entirely inside one terminal is easy to judge: it is valid if the terminal accepts those characters. A token that crosses a boundary can only be judged by advancing the parser through the first part, checking that the terminal has ended where the token says it has, and continuing into whatever comes next, which may involve leaving the current grammar rule and consulting the rules above it. Every engine does that work somewhere; the question is how often and for how many tokens.

The straddle set

For a grammar and a vocabulary, define the straddle set as the tokens whose byte string crosses at least one terminal boundary of the grammar. For JSON the dominant boundaries are the quotes that begin and end every string, so a good first approximation is the set of vocabulary tokens that contain a quote character together with at least one other byte. Computed over the two public OpenAI vocabularies, that set is 1,342 tokens of the 100,277 in cl100k, about 1.3 percent, and 1,140 of the 200,019 in o200k, about 0.6 percent. The figure lines up with what the XGrammar authors report for a different tokeniser: for JSON with Llama 3.1's 128k vocabulary, they count 1,134 context-dependent tokens, under one percent, and their engine's central trick is that the other 99 percent can be judged once, at grammar compile time, and stored as a bitmask per parser state.

That is why the XGrammar paper can report mask generation under 40 microseconds per token for JSON schemas against roughly 150 for Outlines and over 800 for lm-format-enforcer, and its 2026 successor can claim near-zero end-to-end overhead while compiling grammars six times faster for workloads where the grammar changes from request to request. The per-token cost that remains is almost entirely the straddle set: the tokens that have to be run through the parser at decode time because their validity depends on where in the grammar you are.

One percent of the vocabulary, one in eight of the output

The straddle set is small as a share of the vocabulary and that is not the number that matters at decode time. What matters is how often the model actually emits a straddling token, and for JSON the answer is: at every string boundary, which is twice per string. I measured it on two JSON documents with both tokenisers. On a document of long prose-like strings averaging seventeen tokens each, 6.2 percent of all emitted tokens were straddling tokens. On a package lockfile, whose strings are short names and versions averaging seven or eight tokens, the share was 13 to 14 percent. One token in sixteen, or one in eight, is a token the engine cannot judge from the precomputed mask, and that ratio is set by the shape of the output, not by the grammar's rule count.

The measurement suggests a simple predictor for constrained-decoding overhead that has nothing to do with the grammar's size: the number of string boundaries per emitted token. A schema that produces many short strings, identifiers, enum values, version numbers, will spend a larger share of its decode steps in the expensive path than a schema that produces a few long ones, whatever the rule count. The grammar's rules affect compile time; the straddle rate affects every token.

Why a microsecond is a budget

The reason to care about tens of microseconds is that serving is a per-token business. During my internship I tuned batching and quantisation for served Llama and Mistral models against latency targets, and the arithmetic of that job is unforgiving: a decode step for a batch has a budget of a few milliseconds, the mask has to be ready before the sampler runs, and anything on the critical path is multiplied by every token of every request. A mask that costs a millisecond is a real cost; at a few hundred tokens per response it is a few hundred milliseconds of added latency, or a batch that cannot be made larger. The engines that got the overhead under a few tens of microseconds did it by moving the work off the critical path, and the work that could not be moved is exactly the straddle set.

There is a second consequence that is about correctness rather than speed, and the paper titled Lost in Space documents it under the name token misalignment: because the model's preferred tokenisation of a string is not the only tokenisation that spells it, a constrained decoder that forces the grammar's boundaries can push the model onto token sequences it never saw in training, where its predictions are poor. The straddle set is where that happens, because a straddling token is precisely one whose natural use spans a boundary the constraint may forbid. An engine that handles the set well is not only faster; it lets the model write the way it learned to.

What to take from it

If you are choosing an engine, the number to ask for is the per-token mask time on your schema, not the grammar's expressiveness, and the number to measure on your own traffic is the straddle rate: the share of emitted tokens that cross a string boundary. If you are designing a schema, longer strings and fewer of them are cheaper to constrain than many short ones, which is the opposite of what tidy schema design usually produces. And if you are explaining constrained decoding to someone, the one-sentence version is fine as long as the second sentence follows it: the parser reads characters, the model emits tokens, and the tokens that straddle the boundary between the two are where the cost lives.