Constrained decoding makes a local agent scan the vocabulary twice per token
Discuss on XAn agent’s tool call is worth exactly nothing if it does not parse. The model can pick the right tool and reason its way to the right arguments, and if the closing brace lands in the wrong place or a key comes out unquoted, the harness rejects the call and the entire decode turn is wasted. On a single local card that is not a rounding error. It is tens of seconds of decode thrown away because one of a few hundred tokens was structurally wrong.
Grammar-constrained decoding is the standard fix, and it is a good one. You describe the legal output as a grammar, usually derived from the tool’s JSON schema, and at every step the sampler masks out every token that would violate it. The model literally cannot emit a broken tool call, because the tokens that would break it have been set to negative infinity before sampling. The JSON is valid by construction.
The part that gets glossed over is what that mask costs. To decide which tokens are legal right now, the naive implementation checks the grammar against every token in the vocabulary, one at a time, on the CPU, while the GPU sits idle waiting for the next input. For Qwen3.5-9B that is 151,936 checks per token generated. It is a second pass over the whole vocabulary, the same width as the LM head that the GPU just finished, and it lands directly on the critical path of a decode token that is already too slow.
The tool schema is the grammar
Start with why an agent needs this at all. A tool is defined by a JSON schema: a name, a set of arguments, their types, which ones are required. When the model wants to call it, it has to produce a JSON object that matches. Free-form generation gets this right most of the time and wrong often enough to matter, and “often enough to matter” is fatal in a loop where a rejected call means the agent stalls or retries.
llama.cpp handles this with GBNF, its own grammar format, and it will convert a JSON schema into a grammar for you. The GBNF guide shows the machinery: hand it a schema with a name string and an age integer, and it emits production rules that force a leading brace, then the quoted key "name", then a colon, then a string, and so on, down to the ranges of digits an integer may contain. Any token that does not fit the current position in that grammar is masked. The output cannot be anything but a matching object.
This is the right default for agents, and both major serving stacks ship it. The approach goes back to reformulating generation as walking a finite-state machine, which is the framing in Willard and Louf’s Efficient Guided Generation for Large Language Models, the paper behind the Outlines library. Their insight was that you can build an index over the vocabulary keyed by FSM state, so guiding generation with a regex or grammar “adds little overhead to the token sequence generation process.” That last clause is the whole game, and whether it holds depends entirely on how the mask is computed.
The mask is the size of the LM head
Here is the cost the FSM framing is trying to avoid. A context-free grammar, the kind you need for nested JSON, is not a flat state machine. Executing it means tracking a stack, and to decide whether a given token is legal you may have to walk several stack states. The XGrammar authors put the problem plainly in their paper: executing a context-free grammar “requires going through several stack states over all tokens in vocabulary during runtime, bringing non-negligible overhead for structured generation.”
Over all tokens in the vocabulary. That is the phrase that matters on a local card. For every single token the agent decodes, the naive grammar engine iterates the entire 151,936-token vocabulary and, for each token, asks the grammar whether it is currently allowed. llama.cpp does exactly this: its grammar sampler walks the candidate set and sets the logit to negative infinity for any token that would violate the current grammar state. The GBNF guide even links its own performance issue, noting that grammars “currently have performance gotchas.”
Put that next to what a decode token already costs. On one RX 9070 XT, a Qwen3.5-9B decode token is about 25.2 ms, and the LM head over the 151k-row output embedding plus sampling is roughly 1.5 ms of it. The LM head is a single dense pass over the vocabulary on the GPU. A naive grammar mask is a single pass over the same vocabulary on the CPU, with per-token stack work instead of a dot product. It is the same shape and the same width, running on slower silicon, and it cannot overlap the GPU because the GPU needs its result before it can sample. When people say constrained decoding “slowed everything down,” this is what they hit.
The bars are a model, not a profiler trace, and the compile bar is deliberately off the per-token axis because it is paid once. The point does not rest on whether the naive walk is 2.4 ms or 1.8. It rests on the walk being the width of the vocabulary, which is arithmetic, and the vocabulary being the same one the LM head just scanned, which is the observation. A per-token cost on the order of the LM head, hidden inside the sampler, is worth removing.
Most of the vocabulary never changes its mind
The fix is to notice that the naive walk asks the same question 151,936 times when it only needs to ask it a few hundred. XGrammar’s central move is to split the vocabulary into two classes. Context-independent tokens are ones whose legality does not depend on the grammar’s current stack state at all. A raw byte in the middle of a long string, a token that can never appear inside a JSON structure, a token that is always illegal here: its answer is fixed the moment the grammar is compiled. Context-dependent tokens are the small remainder whose legality genuinely turns on where you are in the parse.
The context-independent tokens, which are the overwhelming majority, get precomputed into a mask cache at grammar-compile time. At decode time the engine looks them up instead of re-deriving them, and only the small context-dependent set is walked live. XGrammar layers a persistent stack to make those live checks cheap and overlaps the grammar computation with the GPU. The measured result is up to a 100x speedup over the walk-everything approach and, once folded into a serving engine, “near-zero overhead structure generation.”
The table is the same story the FSM index tells, from the other direction. Outlines precomputes a per-state map from FSM state to the set of allowed tokens, so guiding generation is a lookup rather than a scan. XGrammar generalizes that to the stack machine a context-free grammar needs. Either way the expensive work moves off the per-token path and onto a one-time compile.
| Per token, Qwen3.5-9B decode | Tokens examined at runtime | Where it runs | Modeled cost |
|---|---|---|---|
| LM head + sampling (measured) | 151,936 | GPU | 1.5 ms |
| Naive grammar walk | 151,936 | CPU | ~2.4 ms |
| XGrammar context-split | a few hundred | CPU | ~0.05 ms |
Read the middle row against the top. The naive grammar walk does the same amount of vocabulary work as the LM head, off the GPU, on the critical path, every token. The bottom row is what happens when you refuse to redo the settled part of that work on every step. The compile cost that buys the cache is real, on the order of milliseconds per schema, but it is paid once when the agent’s tool set is registered, not once per token.
The swarm makes the cache cheaper, not more expensive
There is a version of this cost that looks worse at first for a local agent swarm and turns out to be better. Eight agents decoding at once means eight grammar states advancing in parallel, which sounds like eight times the masking work. It is, per token, but the expensive part is not the per-token check. It is the compile, and the eight agents launched from one harness almost always share the same tool schemas.
Same schemas mean the same grammar, which means one compiled grammar and one context-independent mask cache serving all eight agents. This is the same shape as the shared system prompt: the thing every agent has in common gets built once and reused, instead of paid for N times. The per-token context-dependent checks stay per-agent because each agent is at a different point in its own JSON, but those are the cheap part once the cache exists. The costly compile amortizes across the whole swarm.
That reframes constrained decoding for a local box. On a server it is a feature you weigh against throughput. On a single-user card running an agent loop it is closer to mandatory, because the alternative is a decode turn that does not parse, and it is affordable precisely when it is naive-free, because the swarm shares the one artifact that is expensive to build.
What I am building toward
ZINC does not have a grammar engine yet, and the shape of the one it needs is now clear. It has to convert a tool schema to a grammar the way llama.cpp does, and then it has to mask like XGrammar rather than like the naive sampler, because a full-vocabulary CPU walk per token would give back a good chunk of the decode overhead the last few posts have been trying to claw out of the token. The context-independent split is the whole difference between a mask that costs an LM head and a mask that costs nothing.
The swarm angle is the part that makes it worth doing well rather than doing minimally. Compile the grammar once per distinct tool set, share the mask cache across every agent that uses it, and keep only the tiny context-dependent check per sequence. Structured that way, guaranteeing that every one of eight agents emits valid JSON on every tool call costs a one-time compile and a bitmask lookup per token. The correctness is free by construction. The trick is making the correctness cheap by construction too.