Where does grammar-constrained decoding's runtime overhead actually come from?

## Two costs, not one People asking "is constrained decoding slow?" usually have one number in mind. There are two, with different shapes. **Compile cost** is one-off per schema: parse the schema or grammar, build the recogniser, and build the index that maps each automaton state to the set of vocabulary tokens legal from it. That index is the expensive artefact, because it is a function of the *tokenizer*, not just the grammar — every one of ~100k–260k tokens must be classified against each reachable state, or classified lazily and memoised. **Per-step cost** is paid on every generated token of every request: determine the current state, obtain its allowed-token set, and apply the mask to the logit vector before sampling. ## Why compile cost must be cached Compilation depends only on (schema, tokenizer) — never on the prompt, the user, or the sampled text. That makes it trivially cacheable, and caching it is the single biggest practical difference between a fast and a slow deployment. Keyed by a hash of the schema plus the tokenizer identity, a warm cache reduces the cost to a lookup. What goes wrong in production is **cache-miss storms**: a service that generates schemas dynamically — per tenant, per document type, with a field list assembled at runtime — produces a fresh cache key on nearly every call and pays compilation each time. That shows up as inflated first-token latency and a p99 far worse than the median. The fixes are to stabilise the schema set (a fixed record for all tenants, with tenant-specific rules moved into the validator), and to pre-warm the cache for known schemas at startup. Size matters here too. A 200-key schema with nested objects has many more reachable states than a five-field flat record, and permissive regex patterns can blow the automaton up. Both compile time and index memory grow with grammar complexity, which is another reason flat, tight schemas are the production shape. ## Why per-step cost is usually small — and when it is not The naive implementation is the one to avoid: re-parse the partial output, work out what is legal, and scan the whole vocabulary, every step. That is genuinely expensive relative to a forward pass on a small model. Mature implementations do three things instead. They keep the automaton state incrementally, advancing it with each accepted token rather than re-deriving it. They precompute and cache masks per state, so a step is a lookup plus a bitwise apply. And they exploit the fact that most steps have large, stable allowed sets, storing masks compactly and applying them on the accelerator alongside the rest of the sampling pipeline. With those, reported overhead on structured workloads is a small single-digit percentage or less, and the mask work overlaps with the forward pass. Where it still hurts: - **Batching.** Each sequence in a batch occupies a different automaton state, so you cannot share one mask across the batch — masking becomes a per-sequence operation, and the more heterogeneous the schemas in flight, the less amortisation you get. - **Small models.** The mask cost is roughly independent of model size, so as a fraction of step time it matters far more for a small extraction model than for a frontier one. - **Pathological grammars.** Unanchored or heavily alternating regexes, deep nesting, and large unions produce big indices and more state churn. ## The savings side, which is often forgotten Constrained decoding also *removes* work: - **Fewer output tokens.** No preamble, no markdown fence, no closing commentary. On a short record that can be a third of the output. - **Fast-forwarding.** When only one continuation is legal for a stretch — the fixed characters of a key name, a closing bracket — some implementations emit those tokens without a forward pass. - **No retry tail.** Unconstrained extraction pays a full extra generation on every malformed response, and those retries dominate p99 latency far more than any per-step mask. So the honest answer to "what does it cost?" is often "less than the unconstrained pipeline it replaces", once retries are counted. ## How to measure it Don't argue from first principles; run the comparison on your own workload: - output tokens per second, constrained versus unconstrained, at equal batch size, - time to first token on a **cold** schema versus a warm one — this isolates compile cost, - p50 and p99 end-to-end latency with retries included on the unconstrained arm, since that is the real baseline, - total tokens per record, which is where the savings show up, and - the distinct-schema rate in production, as the leading indicator of cache-miss storms. The deciding metric is cost and latency per *valid* record, not per request.