XGrammar: Flexible and Efficient Structured Generation Engine for Large Language Models

• XGrammar targets structured outputs for code generation, debugging, function calling, and robotic control, where downstream systems consume format-conforming LLM outputs.Source: §1 · p. 1
• CFG-based constrained decoding is flexible but costly because it interprets every vocabulary token against stack-dependent grammar states at each step.The vocabulary can reach 128k tokens, while recursive stack patterns prevent complete precomputation and caching.Source: §1 · p. 1
• XGrammar classifies tokens by context dependence, precomputes context-independent validity in an adaptive mask cache, and uses context expansion to reduce runtime checks.Context-dependent tokens still require runtime interpretation using the grammar stack.Source: §1 · p. 2
• Up to 100x lower per-token CFG latency and up to 80x faster end-to-end structured-output serving are reported for the integrated Llama-3.1 engine on H100 GPUs.Source: §1 · p. 2
• XGrammar uses a persistent execution stack for fast branching and rollback during context-dependent token processing.Source: §1 · p. 2
• The grammar engine is co-designed with LLM serving to overlap grammar computation with GPU execution and minimize structured-generation overhead.Source: §1 · p. 2

2.1 LLM Constrained Generation

• LLMs produce logits over vocabulary tokens autoregressively, but tokens may split semantic units or Unicode characters, complicating structured text generation.Source: §2.1 · pp. 2–3
• Constrained decoding sets invalid-token logits to −∞ at each step, ensuring that only structurally valid tokens can be sampled.Efficient mask generation directly affects generation speed.Source: §2.1 · p. 3, Figure 2 · p. 3

2.2 Context-free Grammar and Pushdown Automata

• CFGs define recursively composable structures through rules containing characters or references to other rules, supporting JSON, SQL, and domain-specific languages.Source: §2.2 · p. 3
• Figure 3 maps an array-and-string CFG to a pushdown automaton, with matching stacks representing possible rule expansions for the input string ["a.Source: Figure 3 · p. 3
• The token-mask cache distinguishes context-independent accepted or rejected tokens from context-dependent tokens requiring runtime stack inspection.Source: Figure 4 · p. 4
• Pushdown automata can maintain multiple parallel stacks for alternative paths, but unbounded stack length creates infinitely many possible states and prevents exhaustive token-mask precomputation.Source: §2.2 · p. 4

3.1 Adaptive Token Mask Cache

• XGrammar precomputes context-independent token validity by stack-top node and validates only the remaining context-dependent tokens with the full stack.Parallel-stack masks are merged by taking the union of accepted tokens.Source: §3.1 · p. 4
• 160 MB to 0.46 MB: adaptive storage reduces token-mask memory to 0.2% for Llama-3.1 with JSON grammar.The format stores the smaller token subsets, using rejected tokens in accept-heavy cases, accepted tokens in reject-heavy cases, or a bitset when balanced.Source: §3.1 · pp. 4–5, Figure 5 · p. 5

3.2 Context Expansion

• 90% fewer context-dependent tokens, from 1,134 to 120, after context expansion filters tokens incompatible with higher-level rule contexts.Expanded suffixes represent strings that must follow a completed rule and reject unmatched token remainders.Source: §3.2 · p. 6

3.3 Persistent Execution Stack

• The persistent execution stack stores parallel and previous matching stacks as one tree, reducing memory redundancy and enabling rapid rollback and state branching.Shared deeper stack elements are represented once, while stack pointers identify current states.Source: §3.3 · p. 7
• 30% of the original character checks remain across the vocabulary for Llama-3.1 with JSON grammar by reusing common prefixes and rolling back in constant time.Lexicographic ordering lets tokens such as read, ready, and reader share prefix work.Source: §3.3 · p. 7

3.4 Pushdown Automata Structure Optimizations

• The structure optimizations preserve automaton equivalence while reducing nodes, edges, stacks, and runtime token-checking computation.Rollback also supports structured generation after output-token rollback, including retokenization workflows.Source: §3.3 · p. 7, §3.4 · p. 8

4.1 Mask Generation Efficiency

• Over 100x speedup on CFG and up to 3x on JSON Schema, with under 40 µs per token for JSON Schema and CFG (JSON) and under 200 µs for XML and Python DSL.XGrammar achieves the lowest latency across all evaluated tasks.Source: §4.1 · p. 9, Figure 9 · p. 9

4.2 End-to-End LLM Engine Evaluation

• XGrammar achieves the best TPOT among all baselines for both JSON Schema and CFG in Llama-3.1-8B-Instruct serving.Larger batches particularly pressure CPU-side grammar processing in vLLM, while XGrammar’s system optimizations and serving co-design improve efficiency.Source: §4.2 · p. 9, Table 1 · p. 9
• Across different models, SGLang integrated with XGrammar consistently outperforms its integration with Outlines, showing robustness across model architectures.The comparison uses the same serving engine, isolating the constrained-decoding library integration.Source: §4.2 · p. 9, Table 1 · p. 9
• Enabling XGrammar provides better generation quality with nearly zero TPOT overhead in MLC-LLM.The result is attributed to efficient mask generation and overlap between grammar processing and GPU execution.Source: §4.2 · pp. 9–10, Table 2 · p. 10

4.3 Ablation Study of Optimization Techniques

• The adaptive token mask cache has the greatest ablation speedup, while node merging, rule inlining, and context expansion also improve mask-generation performance.The ablation evaluates progressively added optimizations on CFG unconstrained JSON with Llama-3.1 8B.Source: §4.3 · p. 10, Table 3 · p. 10

4.4 Impact of XGrammar on Structured Generation Tasks

• XGrammar significantly improves structured-generation accuracy by enforcing grammar constraints, including 100% syntactic correctness in the evaluated outputs.Without XGrammar, outputs may include explanations or unexpected JSON types, making them unsuitable for downstream applications.Source: §4.4 · p. 10, Table 4 · p. 10

Structured Generation

• Prior work improves structured generation through character-to-token pushdown automata, prompting, or fine-tuning, and XGrammar is orthogonal to these methods.The paper states that XGrammar can be combined with these approaches.Source: §5 · p. 11

Constrained Decoding

• Regex-based methods cannot handle complex CFGs, while Synchromesh and llama.cpp incur overhead by checking the entire vocabulary at runtime.Outlines instead handles grammar through a lexer and parser-based approach.Source: §5 · p. 11

Structure Declaration

• Guidance, LMQL, and SGLang provide flexible structure-declaration interfaces, whereas XGrammar can serve as a backend engine to speed their execution.The paper characterizes XGrammar as complementary to these improvements.Source: §5 · p. 11

LLM Serving

• LLM serving systems use techniques such as continuous batching and PagedKVCache, while AICI explores CPU-GPU parallel computation for efficient generation.These systems-level efforts provide context for XGrammar’s serving-engine co-design.Source: §5 · p. 11

6 CONCLUSION

• XGrammar separates context-independent and context-dependent tokens, uses an adaptive token mask cache and persistent stack, and overlaps grammar execution with GPU computation.These components target token-mask generation and end-to-end inference overhead.Source: §6 · p. 11
• The system greatly speeds token-mask generation and enables zero-overhead structured generation in end-to-end LLM inference flows.The paper presents this as enabling broader structured generation across platforms.Source: §6 · p. 11

A FORMAL DEFINITION OF THE PDA VARIANT

• The variant PDA is defined from finite grammar rules, a shared input alphabet, rule-specific FSAs, a main start state, and a global transition function.Each rule FSA has states, a start state, accepting states, and transitions labeled by input characters or rule references.Source: A FORMAL DEFINITION OF THE PDA VARIANT · p. 16
• Rule-reference transitions push return information and jump to the called rule’s start state, while character transitions proceed within the current rule automaton.Each stack symbol records the originating rule and return state.Source: A FORMAL DEFINITION OF THE PDA VARIANT · p. 16
• A parsing state contains possible stack-and-state pairs, allowing nondeterministic transitions to represent multiple active parsing stacks.The current state is placed at the top of the stack for simplicity in the paper’s presentation.Source: A FORMAL DEFINITION OF THE PDA VARIANT · p. 16
• The equivalent standard PDA uses the union of rule-automaton states, an initial main-rule state, and a stack alphabet encoding rule-call contexts.Its transitions simulate recursive calls with epsilon-transitions and stack pushes.Source: A FORMAL DEFINITION OF THE PDA VARIANT · p. 16
• When a rule automaton accepts, the standard PDA pops the stored return context and resumes at the saved state; acceptance requires an accepting state with an empty stack.This construction exactly simulates the recursive behavior of the variant PDA.Source: A FORMAL DEFINITION OF THE PDA VARIANT · p. 17

B SYNERGY BETWEEN XGRAMMAR AND JUMP-FORWARD DECODING

• Jump-forward decoding directly tokenizes and appends deterministically inferable output, bypassing LLM decoding and sampling.The technique is orthogonal to XGrammar’s constrained decoding.Source: B SYNERGY BETWEEN XGRAMMAR AND… · p. 17
• XGrammar further supports jump-forward decoding, allowing both methods to be combined to improve end-to-end structured-generation efficiency.The paper frames their combination as leveraging structural constraints for faster generation.Source: B SYNERGY BETWEEN XGRAMMAR AND… · p. 17
• XGrammar consistently outperforms Outlines, with the best efficiency when combined with jump-forward decoding.The comparison uses time per output token for Llama-3.1-8B-Instruct in SGLang at batch size 1.Source: B SYNERGY BETWEEN XGRAMMAR AND… · p. 17

C CROSS-PLATFORM DEPLOYMENT OF XGRAMMAR

• XGrammar is compiled into WebAssembly with a JavaScript binding and integrated with WebLLM for structured generation in client-side browsers.The deployment targets portable devices such as laptops and mobile phones.Source: C CROSS-PLATFORM DEPLOYMENT OF XGRAMMAR · p. 17
• Figure 12 compares end-to-end structured generation with XGrammar against unstructured generation in a browser JavaScript environment.The figure reports comparisons of TTFT and TPOT.Source: Figure 12 · p. 17, C CROSS-PLATFORM DEPLOYMENT OF XGRAMMAR · p. 17
• The browser evaluation uses JSONmode-eval with quantized Llama-3.1-8B-Instruct on a MacBook Pro and quantized Qwen-2.5-0.5B-Instruct on an iPhone.The experiments use Chrome on macOS and Safari on iOS.Source: C CROSS-PLATFORM DEPLOYMENT OF XGRAMMAR · p. 17
• In browser experiments, XGrammar adds close to zero overhead for both time to first token and time per output token.Structured and nonstructured generation are compared with equal numbers of generated tokens.Source: C CROSS-PLATFORM DEPLOYMENT OF XGRAMMAR · p. 17, Figure 12 · p. 17