Grammars at
Token Speed

Ask a model for JSON and you will get almost-JSON: a trailing comma here, an unescaped quote there, a chatty preamble your parser chokes on. Constrained decoding deletes the "almost". A grammar — a JSON schema, a regex, or a full context-free grammar — is compiled to an automaton that rides along with the sampler. At every decode step it computes exactly which tokens may legally come next, and every other logit is set to negative infinity before sampling. The output is never parsed after the fact. It cannot be invalid in the first place.

01 The problem with almost-JSON

Why post-hoc parsing fails, in arithmetic.

The default pipeline is generate-then-pray: prompt the model with "respond in JSON", take the completion, run it through a parser, and on failure retry. This is rejection sampling, and it has the cost structure of rejection sampling. Let p be the probability that one generation is valid. The expected number of generations per request is 1/p, and every failed attempt's tokens are billed, generated, and thrown away. At p = 0.9 — generous for a good instruction-tuned model on a simple schema — one request in ten costs double. Worse, the number of retries is geometrically distributed, which means there is no finite worst case: your p99 latency is set by the retry tail, not by the model. Put numbers on it: 1 billion constrained output tokens a month at $3 per million is $3,000; a 10% retry rate turns $300 of that into pure waste, and the waste scales with schema complexity while your SLOs quietly rot.

And that math assumes failure is detectable. The nastier failure is valid JSON against the wrong shape: the parse succeeds, a required key is missing, a field has the wrong type, and the corruption flows downstream into whatever consumed it. Rejection sampling cannot fix what parsing cannot see. You can add schema validation to the retry loop, but now you have built a slow, expensive, still-unbounded approximation of the thing constrained decoding does exactly.

The product requirement that actually forces the issue is agentic tool calling. A tool call is a JSON object against a schema, and an agent issues dozens per task. If each call is valid with probability 0.99 — excellent by language-model standards — then a 50-call task succeeds end-to-end with probability 0.99⁵⁰ ≈ 0.61. Nearly two tasks in five hit at least one malformed call, and each one costs a full extra model round-trip plus the agent's own recovery reasoning to repair. This is why "JSON mode" exists as a serving feature rather than a prompting trick: reliability compounds multiplicatively, and anything below certainty at the single-call level is a broken product at the task level.

The guarantee is stronger than "the output parses". Constrained decoding maintains an invariant at every step: every prefix of the output is a valid prefix of the grammar's language. Not just the final string — every intermediate prefix could still be completed into a valid string. That prefix property is what makes streaming safe: a downstream consumer can start acting on partial output (more on that in section 06) because no prefix is ever a dead end.

02 The automaton

Grammars become state machines — and JSON needs a stack.

There are two compilation routes, and which one you take determines what you can express. A regex compiles to a finite-state machine: Thompson's construction builds an NFA, subset construction determinizes it to a DFA, and each state is a position in the pattern. This is the Outlines route — it converts a JSON schema into a regex, then into an FSM. It works, with a hard ceiling: regular languages cannot count. No finite automaton can match arbitrarily nested brackets — that is the pumping lemma in one sentence — so a regex-derived machine handles nesting only by bounding it, unrolling the recursion to some fixed depth. Depth-10 nesting unrolled into an FSM is a state explosion; the same structure as a pushdown automaton is a handful of states plus a stack. This is why the serious engines go the second route.

A JSON schema (or any context-free grammar) compiles to a pushdown automaton: states plus a stack. XGrammar builds this automaton at the byte level, not the character level, and that choice is load-bearing. Tokens are byte strings — {", "name", ": — multi-byte chunks that straddle whatever boundaries a character-level grammar imagines. A byte-level automaton doesn't care where token boundaries fall; it just consumes bytes. UTF-8 falls out naturally: a "any character except quote or backslash" rule becomes byte-range transitions, and multi-byte characters are consumed as the byte sequences they are.

A concrete compilation makes the mechanics tangible. Take the schema {"type":"object","properties":{"name":{"type":"string"},"age":{"type":"integer"}},"required":["name","age"]}. The compiler emits rules roughly like: root ::= "{" ws "\"name\"" ws ":" ws string ws "," ws "\"age\"" ws ":" ws integer ws "}", with string ::= "\"" ([^"\\] | "\\" .)* "\"" and integer ::= "-"? ("0" | [1-9] [0-9]*). Notice what the schema keywords became: "required" vanished into rule structure — the keys are literals in the rule, so there is no key lookup at runtime; the automaton simply only accepts those keys. And ws — insignificant whitespace — is a real rule referenced a dozen times, which is why the naive per-step simulation in section 03 would re-walk it constantly. One genuine wrinkle compilers must decide: JSON objects are unordered, but a compiled rule fixes an order. Enumerating permutations works for two keys and dies at five (120 orders); most compilers fix a canonical order or bound the permutation. The constraint is therefore slightly stronger than the schema — a semantic edge worth knowing when the model's preferred key order isn't the canonical one.

Now the per-step question, stated exactly. The sampler does not ask "which tokens complete a valid string" — it asks "which tokens keep the automaton alive?" A token t with bytes b₁…b_n is allowed from the current (state, stack) iff feeding those bytes through the PDA consumes all of them without the automaton dying — i.e., there exists a live path, not necessarily an accepting one. Liveness, not acceptance, is the criterion, because the output is a prefix under construction. Two corollaries that implementations get wrong: first, the end-of-sequence token is allowed only in accepting states — forgetting to mask EOS lets the model terminate inside an object, producing a prefix that is valid but a completion that never comes. Second, whitespace: JSON's insignificant whitespace must be explicit skip rules in the grammar, or the mask will forbid the model's perfectly natural ": " spacing and fight the model's priors at every step.

This is where naive implementations break, and the breakage has a name: the token-boundary problem. The same JSON has many tokenizations. {"a":1} might arrive as {" "a" : 1 }, or as { "a" ": 1}, or half a dozen other splits depending on the tokenizer's merge table. The automaton must accept all of them, because the model gets to choose. Naive approach one: only allow tokens that exactly match the next expected literal — at the { position, only the lone-{ token. This rejects tokenizations the model strongly prefers (a fused {" token is extremely common in JSON-heavy distributions), forcing the sampler down a low-probability path — quality degrades — and in the worst case the allowed set is empty and sampling crashes outright. Naive approach two: allow any token sharing a prefix with an expected literal. This admits tokens whose later bytes strand the parser in a dead state — invalid output, the thing you built the machine to prevent. The only correct check is the full one: simulate the token's complete byte string through the PDA from the current state. Which is O(vocabulary) work per step. That cost is the subject of section 03.

What the diagram shows: a JSON-schema object compiled to a pushdown automaton. The top chain is the flat skeleton — states for {, key, colon, value, separator — with example tokens on each edge. The dashed box is the key idea: a nested object does not add states, it re-enters the same sub-automaton while pushing a frame, and the matching } pops back. The stack panel on the right makes it concrete: depth is just how many frames are piled up. The takeaway for the rest of this essay: everything expensive about constrained decoding comes from deciding, per token, what this machine (in this state, with this stack) will accept.

What the diagram shows: the byte string {"a":1} — seven bytes — split two different ways into tokens. Path A fuses the opening brace with the quote; path B fuses the colon with the quote and the digit with the closing brace. A byte-level automaton accepts both, because it never sees tokens at all, only the byte stream they decode to. The takeaway: any mask implementation that reasons about tokens instead of bytes is negotiating with the tokenizer — and the tokenizer always wins the argument eventually.

03 The mask pipeline

128K logits, one bitmask — and where the time goes.

Each decode step is now a four-stage pipeline. One: read the automaton's current (state, stack). Two: build the allowed-token bitmask over the full vocabulary — for Llama-3.1's 128,256 tokens that is 16 KiB of bits. Three: set every disallowed logit to negative infinity and run the sampler. Four: feed the sampled token's bytes back into the automaton to advance the state. Stage three is nearly free — a vectorized compare over 128K floats is microseconds on GPU. Stage two is the entire problem: deciding the mask means answering the liveness question from section 02 for every token in the vocabulary, every step.

Do the naive arithmetic, because the naive version is what ships first and it is instructive. V = 128,256 tokens. Each token averages roughly 4 bytes in a BPE vocabulary. Each byte through the PDA is a couple of array lookups — call it 20 nanoseconds in tight C++, which is optimistic and ignores the stack manipulation. 128,256 × 4 × 20ns ≈ 10 milliseconds per step, on CPU, single-threaded. Now compare against the thing it is attached to: an 8B-class model decoding at batch 1 on an H100 does a step in roughly 8–12 ms (estimate — it varies with kernels and batching, but the order of magnitude is right). The mask doubles the step time. A 70B model at roughly 35–50 ms per step pays a ~25% tax. And notice the scaling: mask cost is O(vocabulary), independent of model size, while step cost grows with parameters. Constrained decoding bites hardest exactly where serving is cheapest — small models, high throughput, tight TPOT SLOs. Without optimization, the mask becomes the model.

The bitmask itself deserves one paragraph, because its layout is the API between the CPU and GPU sides of the pipeline. 128,256 bits is 16 KiB — 2,004 uint64s. Application is a masked fill, logits = where(mask, logits, -inf): one memory-bound kernel over 501 KiB of fp32 logits, microseconds, no overlap needed because there is nothing to hide behind — it is just cheap. The 16 KiB mask lives in pinned host memory per sequence and rides to the device next to the logits; the transfer is noise beside the same step's KV-cache traffic. This is why every serious implementation builds the mask on the CPU but applies it on the GPU after the forward pass: moving 16 KiB of bits is far cheaper than gathering 128K logits on the host. The pipeline in the diagram above is shaped by exactly this asymmetry.

The first optimization everyone reaches for is caching the mask per automaton state: the same (state, stack) recurs constantly — JSON objects have a small set of positions — so memoize. That helps, but the cache key includes the stack, and the stack varies, so hit rates disappoint on nested schemas. XGrammar's contribution, published as "XGrammar: Flexible and Efficient Structured Generation Engine for Large Language Models" (arXiv:2411.15100), was to notice that the stack usually does not matter — and to split the problem along exactly that line.

What the diagram shows: the steady-state loop. The grammar is compiled once, offline, into a byte-level PDA plus a mask cache. Then every step splits across two lanes: the GPU runs the forward pass while the CPU advances the automaton with the just-sampled token, looks up the cached mask, and checks only the context-dependent tokens. The two lanes join when logits return — mask applied, sample taken, token fed back as next step's input. The bracket on the left is the whole trick: tens of microseconds of CPU work hiding inside milliseconds of GPU work.

XGrammar's core is three ideas plus that co-design. Idea one: the adaptive token mask cache. For each automaton node, split the vocabulary into context-independent tokens — accept or reject is decidable from the node alone, no stack needed — and context-dependent tokens, which need the live stack. A token like "Alice" at a string-value node is accepted whatever the stack holds; } at the same node is rejected whatever the stack holds. But a token containing } at a position where a close-brace is legal is context-dependent: the pop is only valid if the stack top is the matching opener. The cache stores, per node, the accepted set, the rejected set, and the small dependent set, in storage formats chosen per node (dense bitmask where most tokens share a verdict, sparse lists where they don't). At runtime the mask is assembled by OR-ing the cached accepted bits and then checking only the dependent minority against the actual stack. The expensive O(vocab) simulation happens once, at compile time, per node — never per step.

Idea two: context expansion. Some tokens are context-dependent only because the automaton is vague at that node — a rule referenced from several places can't commit to what follows it. XGrammar notices that rules referenced exactly once can be inlined with their continuation as lookahead assertions, which converts a chunk of context-dependent tokens into context-independent ones. It is a compile-time grammar rewrite whose only purpose is shrinking the runtime-checked set.

Idea three: the persistent stack. The PDA stack is implemented as an immutable linked list: a push allocates one node pointing at the old top; a pop follows the parent pointer. Checking a context-dependent token means branching the stack, simulating the token's bytes, and either keeping or discarding the branch — each operation O(1), no copying, and rollback is just dropping a reference. This is also what makes the speculative-decoding interaction in section 04 cheap: rewinding the grammar state after a rejected draft is free.

One more detail on the cache, because "adaptive" is doing real work: different automaton nodes have wildly different verdict densities. At a node expecting the literal "name", nearly every token is rejected — storing a dense 16 KiB bitmask there would be pure waste, so the cache keeps a sparse accepted-list. At a node accepting arbitrary string content, the reverse: a sparse rejected-list. The per-node format is chosen for that node's distribution, which is what keeps the whole cache small. The arithmetic: a 2,000-node automaton with dense masks would cost 2,000 × 16 KiB ≈ 31 MiB — tolerable, but lookup would still be a scan; with adaptive formats the cache is a fraction of that and lookup is a pointer dereference plus a short list walk. Compile time buys both memory and steady-state speed.

The paper's reported numbers: up to 100× lower per-token mask latency than prior methods on context-free grammars, and up to 80× end-to-end serving speedup on an H100 running Llama-3.1 with structured output (their benchmark, structured-output-heavy — read it as "the mask stopped being the bottleneck", not as a universal speedup). The honest caveat, and the interesting design tension, is compile time. The other major engine, llguidance (the engine behind the Guidance library), takes the opposite bet: no precomputation at all, lexer automata built lazily, masks computed on the fly. Their published numbers: a full mask for a typical JSON schema at 128K vocabulary costs about 1.5 ms; a "slicer" optimization that skips irrelevant token ranges brings the average under 50 µs across their JSON Schema Bench corpus (2.5M tokens, 10K schemas), with fewer than 1% of masks exceeding 1 ms. XGrammar pays at compile time — llguidance's authors characterize hard-grammar precomputation as running into seconds, sometimes minutes — for single-digit-microsecond cached masks at steady state; llguidance pays per step for zero startup. Which wins depends on schema churn: one schema served a billion times favors the cache; ten thousand ad-hoc schemas an hour favor laziness. There is a follow-up, XGrammar 2 (arXiv:2601.04426), aimed squarely at the dynamic case — runtime grammar compilation for agentic workloads — claiming 6×+ tool-calling performance over prior approaches. The direction of travel is clear: the mask cache was the static answer; the field is now working on making it dynamic.

04 Engine integration

Where the automaton lives in the serving stack.

In vLLM, constraints arrive as sampling parameters: guided_json, guided_regex, guided_choice, and guided_grammar on SamplingParams (the newer API wraps them in GuidedDecodingParams, e.g. GuidedDecodingParams(json=schema)). The engine that enforces them is pluggable: --guided-decoding-backend historically selected outlines (the original default), xgrammar, guidance (the llguidance engine), or the legacy lm-format-enforcer. Recent vLLM releases have been moving toward --structured-outputs-config.backend with auto semantics — try XGrammar first, fall back to llguidance when XGrammar can't handle the request (check your installed version; the flag name has been in flux). SGLang exposes the same choice as --grammar-backend xgrammar|outlines|llguidance, defaulting to XGrammar. llama.cpp takes the local route: GBNF grammars applied inside the sampler chain, which is why --grammar works offline on a laptop — and why, per llguidance's published characterization, its backtracking parser without a lexer is measurably slower than the purpose-built engines. The Guidance library pairs its token-healing frontend with the llguidance engine. Note the degenerate case: guided_choice — "output exactly one of these strings" — compiles to a trie, and its mask is essentially free. If your constraint is a fixed menu, you are already paying nothing.

Outlines, the original vLLM default, takes the regex road end to end, and its architecture shows the trade-offs of that choice. A JSON schema is translated into a regular expression — string fields become character-class repetitions, enums become alternations, objects become sequences of key patterns — and the regex is compiled to a DFA with the interegular library. Then, for every DFA state, the vocabulary mask is precomputed once: which tokens keep the machine alive from here. Steady-state sampling is then pure table lookup, which is why Outlines' per-step cost is low. The bill comes due elsewhere: the schema→regex translation must bound nesting depth (regexes can't count, per section 02), the DFA itself can blow up on complex schemas, and precomputing V masks across S states is an S×V upfront cost in both time and memory. It is the same precompute-versus-runtime trade XGrammar makes, with the regex ceiling added on top: anything needing a true stack — unbounded nesting, recursive schemas — is unreachable by construction, not just slow.

Two interactions deserve precision, because both are easy to get subtly wrong. First, sampling order. The mask is applied before everything else: disallowed logits go to negative infinity, and only then do temperature scaling, top-p / top-k / min-p, and the final sample run. This ordering is what makes the guarantee exact — temperature rescales the valid logits, top-p renormalizes over the valid set, and no sampling hyperparameter can resurrect a forbidden token. Masking composes cleanly with the whole sampler precisely because it is just logit surgery performed first.

Second, speculative decoding. The draft model must be masked with the same grammar state, advanced along the draft. If it isn't, the drafter spends its proposals on tokens the target model will never accept, and the acceptance rate — the entire economic basis of speculative decoding — collapses. And when the target rejects a draft suffix, the grammar state must roll back to the last accepted token. Remember the persistent stack from section 03: rollback is dropping a reference, O(1). Walk it through concretely. The target has emitted {"tool": "search", "arg and the drafter proposes s": "q…. With the grammar state advanced along the draft, the draft logits after "arg are masked to the keys legal in this object — the token completing "args" is allowed, a token starting banana is not — so no proposal is ever wasted on a token the target must reject. The target scores the draft; suppose it rejects at q. The accepted prefix ends at "args": ", the grammar state rewinds to exactly that point — the engine kept the pre-draft stack reference, so the rewind is free — and the next draft starts from a correct (state, stack). Without masking, proposals come from the unconstrained distribution: at a position where only a tiny fraction of 128K tokens are legal, nearly every draft token is invalid, the target rejects everything, and you pay the draft model's compute for zero accepted tokens. Constrained speculative decoding is one of those places where the data structure and the serving optimization turn out to be the same problem.

Now the failure modes, because a guarantee of syntax is not a guarantee of sense. Over-strict grammars fight the model's priors. Forbid the model's preferred continuation and it picks the least-bad valid token; the output is valid and worse. Force a terse enum on a model that was about to explain its reasoning and you get compliant, degraded content. Constrained decoding moves the quality question — it doesn't delete it. Backends disagree on the same schema. A real portability gotcha surfaced in vLLM's tracker: for JSON objects, Outlines and XGrammar default to disallowing additional properties, while the llguidance backend follows the JSON Schema spec default and allows them. Same schema, different accepted languages, depending on a flag. If you switch backends, re-validate your schemas; "JSON schema" is not one semantics, it's three.

Soundness versus coverage is a genuine trade-off curve. A community benchmark on 11,306 real-world schemas (JSONSchemaBench, tabulated in the GRID project's RFC — GRID being a competing engine, so read the table as a trade-off illustration, not a leaderboard) found XGrammar 0.2.3 passing 90.3% with 427 valid schemas wrongly rejected and 627 invalid outputs wrongly accepted — silent errors in both directions — while llguidance 1.7.6 passed 83.9%, declared 1,797 schemas unsupported up front, and accepted zero invalid outputs. One engine buys coverage with silent mistakes; the other buys soundness by refusing schemas it can't handle exactly. For multi-tenant serving, where the schemas arrive from users and may be adversarial, that refusal behavior is a feature, not a gap. Finally, performance cliffs. Deeply nested schemas mean deeper stacks, more context-dependent tokens, and bigger caches; schemas compiled through the regex route can blow up at compile time long before they blow up at runtime. Profile the schema, not just the model.

05 Beyond JSON

The real prize was never JSON.

JSON was the demo. The killer application is function calling: a tool definition is a JSON schema, and section 01's compounding math — 0.99⁵⁰ ≈ 0.61 — is the reason every serious agent stack constrains tool calls rather than praying over them. SQL is next: a grammar for SELECT … FROM … WHERE … turns "almost-SQL" from a warehouse outage into an impossibility; the model can still choose a wrong query, but it cannot choose a non-query. A concrete taste: query ::= "SELECT " collist " FROM " table (" WHERE " cond)? ";", where collist and table are alternations over the actual schema's columns and tables, injected at request time. The model can pick a wrong column only if it appears in the alternation. The grammar becomes a security boundary, not just a format constraint — which cuts both ways: whoever supplies the table list controls what the model can touch, so grammar injection deserves the same scrutiny as prompt injection. Then come DSLs for agents — constrained action languages where the model may only emit operations the surrounding system can actually execute: a robot-control DSL, a query-planner DSL, a test-generation DSL whose outputs compile by construction. This shades into syntax-guided synthesis, the old program-synthesis idea that the search space should be the language of valid programs, now with the LLM as the search heuristic and the grammar as the space.

One paragraph of philosophy, because it matters for architecture: constraints trade model freedom for system composability. An agent is not a chatbot; it is a component in a larger system, and components need interface contracts. The grammar is the contract — the type signature of the model's output. A tool call constrained by a schema is a typed function call; an unconstrained one is a stringly-typed hope. The agentic stack will compose exactly to the extent its components' outputs are machine-checkable, and machine-checkable at generation time is worth an order of magnitude more than machine-checkable after the fact, because the check can never be skipped, forgotten, or applied to the wrong version of the output. The pushdown automaton riding shotgun on the sampler is, in this light, not a restriction on the model. It is the model's API.

06 Open questions

What the field hasn't solved yet.

Learned constraints. Today someone hand-writes the schema, and the schema is always slightly wrong — too strict where the task needs slack, too loose where the downstream parser is picky. Can the grammar be inferred instead? Grammar induction from examples is an old, hard problem, but the practical version is narrower: invert the downstream parser into a generator constraint. You already have a PEG or a pydantic model that defines "valid" — deriving the generating grammar mechanically from the accepting parser would close the loop and delete the most common source of grammar bugs, which is the human translating intent into schema. The strongest version of this already exists in miniature: a pydantic-style model generates both the validator and — via schema compilation — the generator constraint from one source of truth. The open problem is the general case: arbitrary hand-written parsers, legacy validators, binary formats. Whoever cracks "give me your parser, I'll give you your mask" removes the last hand-written artifact in the pipeline.

Streaming partial parsing. The prefix property from section 01 is underexploited: every prefix is a valid prefix, which means a downstream consumer could act before EOS. The moment the generated prefix determines the function name and its required arguments, the tool call could start executing while the model finishes the optional fields. No serving engine exposes incremental parse events today — the mask machinery knows the parse state at every step and then throws it away at the API boundary. The first engine to stream structured events instead of strings gets a full round-trip of latency back on every agentic workflow. The machinery is already there — the mask builder tracks (state, stack) per sequence per step; it just needs an API.

Grammar-aware speculative drafting. Section 04 showed that the draft model must respect the mask, but masking a draft model is damage control, not design. The interesting version: drafters that natively propose structurally valid tokens — a small model fine-tuned on schema-constrained traces, or Medusa-style heads trained to predict valid continuations under the grammar — so acceptance rates stay high because of the constraint rather than despite it. The grammar is information about the future; a drafter that can't see it is drafting blindfolded. Even simpler: use the grammar to shape the draft — at highly constrained positions the valid set is small enough to enumerate, so propose all of them and let the target pick. Speculation becomes search, and the grammar prunes it.