id
flops/constrained-decoding-grammar-mask
Arithmetic intensity
Grammar-mask evaluation is a per-token cost incurred AFTER the logits exist, and it scales with vocabulary size rather than with model size. A naive CFG-constrained decoder, as the XGrammar paper's abstract describes it, 'requires going through several stack states over all tokens in vocabulary during runtime, bringing non-negligible overhead for structured generation' - note that 'over all tokens in vocabulary' is the whole cost model: the work is O(stack_depth * V) per token. The bitmask formulation that efficient implementations use compresses that to V bits = V/8 bytes: for V = 128,256 that is 15.66 KiB per token, written once and read once by the sampler = 31.31 KiB of traffic. Against a Llama-3-8B decode step that reads 2*P = 16.06 GB of weights, the mask is 0.0002% of the step's HBM traffic, and even the O(stack_depth * V) naive form with depth 4 is about 0.0004%. So the answer to 'why is it usually not the bottleneck' is quantitative, not hand-waving: in a memory-bound decode step the weight read is 4 to 5 orders of magnitude larger than the mask. The regime where it IS the bottleneck is narrow and worth naming precisely: (a) SMALL models, where 2*P is small and V is not proportionally smaller - e.g. a sub-1B model with a 32k vocab reads only ~2 GB of weights, bringing the mask to ~0.002%, still small, so this is a weak case; (b) CPU-bound or launch-overhead-bound decoding, where an extra kernel launch per token costs more microseconds than the mask costs bytes - the kernel COUNT is the risk, not the mask size; (c) engines that run the mask on the CPU in Python, where per-token interpreter overhead is milliseconds rather than bytes.
Scales with
vocab_size V (the entire cost model is O(depth*V) naive or O(V/8) bytes as a bitmask: 15.66 KiB/token at V=128256, 3.9 KiB at V=32000)grammar_stack_depth (the naive form's multiplier; a deeply nested JSON schema or a deeply nested tool-call grammar makes this worse)kernel_launch_count (a mask kernel ADDED to an already launch-bound decode step is the real risk - see custom-kernel-launch-overhead)whether the mask runs on GPU or CPU (CPU execution in Python turns a 15 KiB byte operation into a millisecond-scale host operation)model_size (INVERSE: the mask share of a step falls as the model grows, so the risk is highest for small models and lowest for frontier ones)output_structure (JSON with shallow nesting, versus a deeply nested grammar or many alternation branches, directly sets the number of stack states visited)incremental-vs-full recomputation (the incremental case advances a persistent stack and copies it per live parse stack - cost scales with num_grammar_stacks = number of concurrently constrained requests, NOT with vocab; the full-recompute case this record originally described is O(depth*V) per token)trigger_patterns and trigger_buffer length (llama.cpp re-runs every trigger_pattern.find() against the whole accumulated trigger_buffer each token while awaiting a trigger - O(tokens_so_far x num_patterns) over the response, a per-token cost that grows with output length)whether the grammar engine is on device or host (an on-device bitmask engine with a persistent stack is O(V/8) bytes and graphable; a host-side stack machine is per-token host work that cannot be captured in a CUDA graph - see custom-kernel-launch-overhead and detokenization-stop-string-scan)
Workarounds
Split the vocabulary into context-independent tokens that can be prechecked once and context-dependent tokens interpreted at runtime (XGrammar's core idea, arXiv 2411.15100) - this is what turns O(depth*V) into a much smaller runtime setGrammar-mask BITMASK representation (1 bit per token) rather than a boolean vector, cutting the traffic 8x or 16x versus fp32/bf16 masksPersistent grammar stack so context-dependent token checks do not re-walk the parse state from the root each tokenGrammar context expansion to reduce the number of context-independent tokens further, per XGrammarOverlap grammar computation with GPU execution by co-designing the grammar engine with the inference engine - XGrammar reports up to 100x speedup over existing solutions and 'near-zero overhead structure generation' when co-designed, which is the mechanism that actually delivers the 'not the bottleneck' propertyCache grammar masks across decoding steps for unchanged grammar states, so repeated structure (e.g. emitting many array elements of the same shape) reuses masksFuse the mask application into the sampling kernel so the logits are read once and masked in registers, with no intermediate mask buffer in HBMStatic-shape / CUDA Graphs capture so the mask kernel does not add per-token launch overhead in an otherwise graphed decode stepPersistent grammar stack with in-place advancement rather than per-stack copy (llama.cpp's llama_grammar_accept_token copies each live stack per token; an in-place advance removes the allocation)Avoid trigger-based grammars, or make trigger matching incremental on the token ids rather than re-running find() over the accumulated trigger_buffer each token (llama.cpp src/llama-grammar.cpp)One grammar machine per constrained request is unavoidable, but its host cost is per-request: at concurrency C the per-token grammar work is C x (stack copies + pattern finds), which is why structured-output throughput degrades with concurrency
notes
CLASSIFICATION ARGUMENT, since the enum has no constrained-decoding class and this was filed under sampling: grammar masking is the LAST operation applied to the logits before the token is chosen, it consumes the same V-wide tensor the sampler consumes, it runs exactly once per generated token, and it is memory-bound at roughly the same AI as sampling (a few flop/byte, entirely batch-invariant). It is not decode_gemm (no weight read dominates), not custom_kernel (it is a real per-token data operation, not launch overhead), and not norm_softmax (it operates on logits, not on activations). Sampling is the correct home. The decision-relevant conclusion, and the reason this is worth a record despite being 0.0002% of a modern decode step: the per-token cost is negligible but the per-token KERNEL is not. In a decode step that is already launch-overhead-bound at batch 1 - a few hundred to a few thousand kernels for a large model - adding one more dependent kernel on the critical path, plus any host-side grammar evaluation, costs more than its byte count suggests. XGrammar's reported 'up to 100x speedup' and 'near-zero overhead' are therefore statements about the ENGINE CO-DESIGN, not about the arithmetic. That reframes the engineering question: the way to make constrained decoding free is not to shrink the mask (it is already 15 KiB) but to eliminate the synchronization point - fuse it, overlap it, or capture it in a graph. Second-order caveat, from the primitive-work framing: a mask is genuinely useful when the grammar narrows the CANDIDATE SET. If a grammar state admits only C tokens, the engine can restrict the LM head projection to those C rows (2*d*C bytes instead of 2*d*V), which at C = 256 on Llama-3-8B is 2.10 MB instead of 1.051 GB - a 500x reduction of a term worth 6.54% of the step. That is a real optimization of the decode_gemm term enabled by grammar knowledge, and it is a different mechanism from masking logits after the fact. Tool-calling workloads add one more term that is NOT this class: the assistant turn produced by a tool call is re-prefilled on the next call, so an agent loop pays prefill flops per tool invocation. That belongs to prefill, not here. INCREMENTAL CASE (deepened 2026-10-03, sourced from llama.cpp's shipped host-side grammar engine): the record above describes the mask as a single O(V/8)-byte operation. The incremental case is different in three ways, all of which move the cost from '15 KiB of bytes' to 'host work per token that cannot be graphed'. (1) The mask is not computed from scratch; the parse state advances. llama_grammar_accept_impl fetches token_to_piece(token) for the accepted token, llama_grammar_accept_token UTF-8-decodes the piece and advances the state machine - and for each live parse stack it constructs a NEW stack (llama_grammar_stack new_stack(stack.begin(), stack.end() - 1)), so the per-token cost is a stack COPY per stack per token, proportional to the number of live grammar stacks (one per request with a structured-output constraint), not to the vocab. (2) Trigger handling is a regex scan over an ACCUMULATING buffer: while awaiting a trigger, each token appends to trigger_buffer and to a trigger_buffer_positions vector of (token, byte-range) pairs, and every trigger_pattern.find() is re-run against the whole accumulated buffer on every token - so a trigger-capable grammar is O(tokens_so_far x num_patterns) over the response, i.e. a second quadratic. (3) It is all on the host, once per token, which is why the classification argument above lands even harder: the incremental case is not a byte cost that fusion or a bitmask can remove, it is a Python/C++-equivalent loop on the GIL-holding server thread. Cross-reference: the same O(full sequence) per-step host predicate appears in vLLM's structured-output reasoning-end check, which decayed a production deployment from 260 to 170 tok/s at concurrency 50 with ~4.9 ms per decode step at 16k reasoning lengths - see detokenization-stop-string-scan for that record. So the incremental grammar cost has TWO regimes, and the second is the dangerous one: (a) an on-device bitmask engine with a persistent stack, which is the XGrammar design and is genuinely cheap - 15.66 KiB per token at V=128256 is 0.0002% of an 8B decode step's HBM traffic; (b) a host-side stack machine with regex triggers, where the cost is per-token host work with a quadratic term in the trigger case. Which one you have is a config-level fact (llama.cpp's GBNF path is (b); vLLM with an xgrammar/outlines backend is (a)), not a hardware fact, and it is worth checking before blaming the GPU.