Grammars, Stacks, and Making It Free

The previous lesson ended at a ceiling: finite automata cannot count without bound, so genuinely recursive formats are out of reach.

The next class up is the context-free languages, recognised by a pushdown automaton. A pushdown automaton is a finite automaton with one addition: a stack it can push to and pop from.

That single addition is enough. To validate nesting, push a marker on every opening brace and pop on every closing one. A closing brace is legal exactly when the stack is non-empty and its top matches. At the end, the input is complete exactly when the stack is empty.

Context-free grammars are the notation for describing these languages, written as production rules: a value is an object or an array or a string or a number; an object is a brace, then members, then a brace. The rules may refer to themselves, which is precisely what regular expressions cannot do.

This covers what people actually want to constrain: arbitrary JSON, SQL dialects, programming languages, arithmetic expressions, and any domain-specific format with nested structure.

The stack buys expressiveness and immediately destroys the optimisation that made the previous lesson work.

The index relied on the automaton's state being a complete summary of the prefix. With a pushdown automaton that is false. The machine's configuration is a state plus the entire stack contents, and the stack is unbounded.

The practical consequence is direct. Whether a closing brace is permissible depends on what is on the stack, which depends on the whole history of nesting. You cannot precompute a mask for a configuration when there are infinitely many configurations.

Worse, a single token can contain several structural characters, so processing one token may push and pop the stack multiple times, and whether it is legal depends on the stack depth at entry.

The naive fallback is to walk the stack machine over every vocabulary entry at every step, which returns you to the 64 million checks per response the index was built to avoid.

So grammar-constrained decoding needs a different idea than pure precomputation, and the shape of that idea is a split.

The insight behind XGrammar, from the MLC team, is an empirical observation about which tokens are actually ambiguous.

Split the vocabulary in two. Context-independent tokens are those whose legality can be decided from the grammar position alone, without consulting the stack. Context-dependent tokens are those where the stack decides.

The token for the word temperature, appearing in the middle of a string field, is context-independent: it is a run of ordinary characters, legal or not regardless of nesting depth. The overwhelming majority of a vocabulary optimised for natural text is like this.

The token consisting of a closing brace, or a closing brace followed by a comma, is context-dependent. Whether it is legal depends entirely on what is open.

Because the first group is large and the second is small, you can precompute the first exactly as in the previous lesson, and pay the expensive stack-walking cost only on the small remainder.

That is the whole trick, and it turns an intractable per-step cost into a small one.

Two further mechanisms make the remaining work cheap, and both are worth knowing because they explain the observed performance.

The first is a persistent execution stack. Checking a context-dependent token means simulating the machine over its characters, which alters the stack, and then undoing that to try the next candidate. Rebuilding the stack per candidate is wasteful, since candidates share long common prefixes. A persistent structure lets branches share their common portion and be discarded cheaply, so exploring many candidates costs far less than doing each independently.

The second is a cache over token masks. Grammar positions recur constantly: every string field in every object reaches structurally identical positions. Caching the computed mask keyed by grammar configuration means the expensive computation happens on first encounter and is a lookup thereafter. In steady state on a repeated schema, most steps hit the cache.

The reported result is more than an order of magnitude faster than prior structured generation implementations, and XGrammar is now the default structured output backend across the major serving stacks, including vLLM, SGLang, TensorRT-LLM and MLC-LLM.

The final optimisation is a systems one rather than an algorithmic one, and it is the reason the overhead can approach zero rather than merely becoming small.

Notice what the two halves of a decoding step need. The model forward pass runs on the accelerator and needs the previously sampled token. Computing the mask for the next step runs on the host processor and also needs only the previously sampled token.

Neither depends on the other's output. They are independent given the same input, so they can run at the same time.

So the mask for step k plus one is computed on the CPU while the GPU is still executing the forward pass for step k. When the logits arrive, the mask is already waiting, and applying it is a single elementwise operation on the accelerator.

Correctly overlapped, grammar computation contributes nothing to wall-clock latency. It happens in time that was already being spent.

The caveat is that this only works while mask computation is faster than the forward pass. A pathological grammar that takes longer than a forward pass becomes the critical path, and the overlap silently stops helping.

The architecture is easiest to hold as a split with three exits, and the proportions matter as much as the structure.

At each step the vocabulary divides. The large context-independent portion is answered from the precomputed table, exactly as in the finite automaton case, at no runtime cost.

The small context-dependent portion goes to the stack machine, which simulates each candidate over the persistent stack. Before that happens, the mask cache is consulted, and on a repeated grammar position the whole computation is skipped.

The two results combine into one mask, which is applied to the logits.

Running alongside, on different hardware, is the model's forward pass. The diagram places it in parallel because that is the point: the left branch is host work, the right branch is accelerator work, and they meet only at the moment the mask is applied.

The cost of the technique is therefore not the sum of its parts. It is whichever branch is slower, and on a reasonable grammar that is always the forward pass.

Grammar-constrained decoding needs a grammar, usually written in a variant of Backus-Naur form. Two habits separate grammars that work from grammars that cause trouble.

Be specific where you can. A grammar that says a value is any string is barely a constraint. One that says a value is one of four literals, or matches a date pattern, or is an integer between bounded digit counts, removes far more of the failure surface.

Be permissive where you must. A grammar tighter than reality forces the model into contortions. If a field is genuinely free text, constraining its content to a pattern you guessed at will produce awkward output that satisfies the pattern.

The common failure is a grammar with no escape hatch. If every branch requires a value the model may not have, it will produce one. Adding an explicit null alternative or an unknown literal gives the model a legal way to decline, and that alternative has to be in the grammar, because anything not in the grammar cannot be emitted no matter how much the model wants to.

Whitespace is the other recurring bug: forget to allow it and the model has no legal way to produce readable output.

A production server does not decode one sequence at a time. It runs continuous batching, with dozens of sequences at different positions in different requests, each potentially under a different grammar.

That changes the shape of the problem. Every sequence in the batch needs its own mask, computed from its own grammar at its own position, and all of them must be ready when the batch's logits arrive.

Three consequences follow for anyone operating this.

Mask computation must be parallel across the batch on the host, or it becomes the bottleneck precisely when throughput matters most.

Grammar compilation must be cached across requests, since a server receiving the same schema hundreds of times per second cannot compile it hundreds of times per second.

And one pathological grammar degrades the whole batch. Because the batch advances in lockstep, a request whose mask computation is slow holds up every other request sharing that step, in the same way a straggler holds up a collective.

So grammar complexity is a shared resource in a multi-tenant service, and accepting arbitrary caller-supplied grammars without limits is a denial-of-service surface.

Constrained decoding does not sit alone in a serving stack, and its interactions with the other optimisations are worth knowing before they surprise you.

Speculative decoding proposes several tokens at once with a small model and verifies them with the large one. Under a grammar, every proposed token must also be checked for legality, and a proposal that violates the grammar is rejected regardless of what the large model thought. The two techniques compose, with a lower acceptance rate than either suggests alone, since the grammar is a second filter.

Prefix caching reuses the KV cache for a shared prompt prefix. That is unaffected by grammars, since the grammar governs output rather than input, and the two are orthogonal.

Beam search and sampling parameters continue to work, over a restricted support. Temperature still spreads probability among the legal tokens, and in a state with exactly one legal token, temperature has no effect at all.

The general rule is that constrained decoding composes with anything operating on logits or on cache, and interacts with anything that predicts tokens ahead of the model.

Three levels of expressiveness exist, and picking the weakest one that does the job is the right instinct, because each level costs more at runtime.

In practice most structured output needs the middle row, because a concrete schema with fixed nesting depth is a regular language, and the index approach handles it with near-zero runtime cost.

The top row is genuinely underused. If the output is one of five categories, you do not need a grammar engine; a five-way constraint is simpler, faster and easier to reason about.

The bottom row is necessary for recursive formats and is where the engineering in this lesson earns its keep.