XGrammar: Flexible and Efficient Structured Generation Engine for Large Language Models
XGrammar accelerates CFG-based structured decoding with adaptive caching and persistent stacks, reaching up to 100x lower latency.
Key Findings
Methodology
XGrammar compiles a context-free grammar into a byte-level pushdown automaton (PDA) and splits the vocabulary into context-independent tokens, which can be prechecked from the top-of-stack state, and context-dependent tokens, which require full-stack interpretation. It builds an adaptive token mask cache for the former, applies context expansion to prune many of the latter offline, and uses a persistent execution stack to support branching and rollback efficiently. Finally, grammar computation is overlapped with GPU inference to hide overhead.
Key Results
- On Llama-3.1 with a JSON grammar and a 128k vocabulary, only 1,134 tokens are context-dependent, and context expansion reduces this to 120, a 90% reduction.
- Adaptive storage shrinks the JSON grammar mask cache from 160 MB to 0.46 MB, i.e., 0.2% of the original size; preprocessing character checks drop to 30% of the vocabulary-wide total.
- End-to-end serving with an integrated LLM engine on H100 achieves up to 80x speedup for structured output, while per-token CFG latency improves by up to 100x over existing solutions.
Significance
This paper turns structured generation from a costly add-on into a near-invisible systems primitive. For research, it shows that CFG expressiveness need not imply high runtime cost if token filtering, stack representation, and inference scheduling are co-designed. For industry, it directly lowers the cost of function calling, JSON emission, SQL generation, and robotic command interfaces, making correctness constraints compatible with high-throughput serving.
Technical Contribution
The contribution is architectural rather than incremental: (1) an adaptive token mask cache moves most legality checks offline; (2) context expansion uses parent-rule context to eliminate many doomed context-dependent tokens before runtime; (3) a persistent execution stack enables O(1) rollback and cheap branching by sharing stack history in a tree; and (4) co-design with the LLM engine overlaps grammar work with GPU computation. Compared with brute-force per-token, per-stack validation, this dramatically reduces the active state space at decode time.
Novelty
The novelty lies in explicitly decomposing CFG execution into context-independent and context-dependent tokens and then designing cache, pruning, and stack mechanisms around that decomposition. Unlike prior constrained decoding approaches that mostly add syntax checks or shallow caching, XGrammar unifies grammar analysis, data structures, and serving-time scheduling into one high-performance engine.
Limitations
- The strongest evidence is on JSON grammar and Llama-3.1; the paper does not yet establish how the gains transfer to highly ambiguous, deeply recursive, or rapidly changing grammars, where preprocessing may be less amortizable.
- Context expansion and cache construction introduce offline complexity. For user-defined or frequently updated grammars, the engineering burden and preprocessing latency may become more noticeable.
- The overlap strategy is most beneficial when GPU inference leaves enough slack. In extremely small-batch or ultra-low-latency single-request settings, the hidden overhead may be harder to mask.
Future Work
Natural next steps include extending the engine to broader grammar families, dynamic or editable DSLs, and multi-step agent planning. The authors also point toward deeper integration into major open-source LLM frameworks. Open directions include better handling of ambiguous grammars, cache reuse across requests, and scheduling strategies for larger vocabularies and multi-modal instruction streams.
AI Executive Summary
Large language models are increasingly expected not just to write fluent text, but to emit outputs that can be parsed, executed, and trusted: JSON objects, SQL queries, function calls, and robot commands. That demand has made structured generation a first-class systems problem. Yet the standard way to enforce structure during decoding—scanning the entire vocabulary at each step and checking every token against a grammar—creates substantial latency, especially when the vocabulary reaches the 128k scale of Llama-3.1.
XGrammar addresses this bottleneck by rethinking how context-free grammar (CFG) execution should be organized. It compiles CFG into a byte-level pushdown automaton and divides tokens into two groups: context-independent tokens that can be decided from the local stack-top state, and context-dependent tokens that require full-stack inspection. The first group is precomputed into an adaptive token mask cache; the second is handled at runtime by a persistent execution stack. A further optimization, context expansion, exploits parent-rule context to reject many tokens before runtime, reducing the slow path even more.
The engineering insight is that grammar checking should behave less like repeated full parsing and more like a layered filter. Most tokens are resolved from cached information tied to a PDA node; only a minority need expensive interpretation. The persistent stack organizes current and historical matching states into a shared tree, enabling fast branching and constant-time rollback. This matters because many tokens share prefixes, so the engine can roll back to the last common prefix instead of rechecking repeated characters. In the JSON setting, this lowers preprocessing checks to 30% of the vocabulary-wide work and cuts the mask cache from 160 MB to 0.46 MB.
The results are striking. On Llama-3.1 with JSON grammar, context-dependent tokens drop from 1,134 to 120 after context expansion, a 90% reduction. End-to-end structured serving on H100 reaches up to 80x speedup, while per-token CFG latency improves by up to 100x over existing solutions. Crucially, these gains come without giving up CFG’s expressive power: recursive structures, nested formats, and DSL-like patterns remain supported, which is precisely where regular-expression-based systems fall short.
Broader impact follows naturally. If structure checks become almost free, then LLM agents can produce parseable outputs without paying a heavy latency tax. That unlocks more reliable tool use, safer downstream automation, and more robust interactive systems. XGrammar also points to a larger systems trend: the next leap in LLM serving may come not only from bigger models or faster GPUs, but from better co-design of grammars, data structures, and inference scheduling.
The work is not the final word. Its strongest evidence is on JSON and Llama-3.1, so the behavior on highly ambiguous, deeply recursive, or rapidly changing grammars still needs broader study. Offline preprocessing also introduces complexity, and ultra-small-batch or ultra-low-latency scenarios may leave less room to hide overhead. Still, XGrammar establishes a compelling path toward near-zero-overhead structured generation and makes that goal look practically achievable rather than aspirational.
Deep Analysis
Background
LLM applications have expanded from open-ended chat to code generation, debugging, function calling, SQL synthesis, and robotic control, all of which require outputs that are both fluent and structurally valid. Regular-expression constraints are too limited for nested or recursive formats, while CFGs can express JSON, SQL, and domain-specific languages. PDA-based execution is the standard formal machinery for CFGs, but naive constrained decoding is expensive because it must inspect a large vocabulary at every step, manage potentially many stack states, and handle tokens that cross grammar boundaries.
Core Problem
The core problem is how to preserve CFG flexibility while making legality checking fast enough for serving. The difficulty comes from three sources: large vocabularies such as 128k tokens; an unbounded stack space that prevents exhaustive precomputation of all states; and multi-character tokens that may straddle rule boundaries, forcing runtime backtracking into parent rules. Without a better design, structured generation becomes a major inference bottleneck.
Innovation
XGrammar’s innovations are tightly coupled. First, it classifies tokens by whether validity depends only on the current stack top or on the full stack. Second, it uses an adaptive token mask cache to precompute the common case. Third, context expansion extracts an "expanded suffix" automaton for each rule, allowing offline rejection of many tokens that would fail in higher-level contexts. Fourth, the persistent execution stack shares stack history across time steps and branches, enabling cheap rollback and branching. Fifth, grammar work is overlapped with GPU inference so the structured decoder can stay mostly off the critical path.
Methodology
- �� CFG to byte-level PDA: grammar rules are compiled into a pushdown automaton whose character edges may span multiple bytes, allowing irregular token boundaries and sub-UTF8 fragments.
- �� Adaptive token mask cache: for each PDA node, legality of context-independent tokens is precomputed. At runtime, the cache provides most of the mask immediately, while only a small residual set of context-dependent tokens requires full-stack execution.
- �� Adaptive storage: each node stores either accepted tokens, rejected tokens, or a bitset depending on whether the node is accept-heavy, reject-heavy, or balanced. This minimizes memory footprint.
- �� Algorithm 1 mask merging: when multiple parallel stacks exist due to grammar ambiguity, the final token mask is computed by efficient set operations over the small stored subsets rather than over the full vocabulary.
- �� Context expansion: Algorithm 2 extracts an expanded-suffix FSA for every rule by traversing reachable character-only subgraphs after rule references. A context-dependent token is rejected if its remaining suffix cannot match any expanded suffix.
- �� Persistent execution stack: all active and historical stacks are organized as a shared tree, with stack tops represented as node pointers. Branching copies only the affected branch; rollback is a constant-time pointer switch.
- �� Compute overlap: mask generation and LLM forward computation are co-scheduled so grammar overhead is hidden under GPU execution whenever possible.
Experiments
The evaluation centers on Llama-3.1 and JSON grammar, with a 128k vocabulary as the main stress case. The paper measures per-token decoding latency, mask-generation overhead, cache memory usage, the number of context-dependent tokens, the proportion of character checks needed during preprocessing, and end-to-end structured-serving performance on H100. It also studies the effect of context expansion and the persistent stack on preprocessing and runtime execution. The comparison is against existing structured-generation solutions under the same constrained-decoding setting.
Results
The headline result is a combined speed and memory win: per-token CFG latency is reduced by up to 100x, and end-to-end structured serving on H100 improves by up to 80x. For JSON grammar, context-dependent tokens fall from 1,134 out of 128k to 120 after context expansion, a 90% cut. Preprocessing work drops substantially too, with character checks reduced to 30% of the vocabulary-wide total. Memory usage is compressed from 160 MB to 0.46 MB, or 0.2% of the original footprint.
Applications
The most immediate use case is function calling and schema-constrained APIs, where outputs must be machine-parseable and failures are costly. A second direct use case is code, SQL, and DSL generation, where recursive syntax makes CFG-based constraints especially valuable. The same engine can also support agent planning, tree-structured search, rollback-based decoding, and other workflows where output correctness and fast iteration both matter.
Limitations & Outlook
The method assumes the grammar can be compiled into a CFG/PDA form and that offline preprocessing is worthwhile. If the grammar changes frequently or is generated on the fly, the advantage of caching and context expansion may shrink. Highly ambiguous or deeply recursive languages may still leave a nontrivial residual set of context-dependent tokens, so broader benchmarking is needed. Finally, very small-batch serving may offer less room to hide grammar computation behind GPU work.
Plain Language Accessible to non-experts
Think of XGrammar as a super-fast quality inspector for a factory that produces sentences. In the old setup, the inspector had to re-read the entire rulebook every time the factory added one new piece to a sentence. That is like checking a product by starting from page one of a giant manual for every tiny screw—slow and wasteful.
XGrammar reorganizes the manual. First, it puts easy rules on sticky notes: if a new piece clearly fits or clearly does not fit based on the current position, the inspector can decide immediately. Only a small number of tricky cases need the full manual. Second, it keeps a shared notebook of what has already been checked, so if two new pieces start the same way, the inspector does not redo the same work again and again.
It also has a smart trick for looking ahead. If the next part of a sentence can only continue in a few ways, XGrammar uses that clue to throw out bad choices early. And while the model is thinking, the inspector can work in parallel instead of waiting. The result is that the factory keeps moving quickly, while the products still follow the rules exactly.
ELI14 Explained like you're 14
Imagine you’re playing a game where every message you send has to follow super-strict rules, like "write your name first, then your score, then your item list." Old-school rule checking was kind of like a teacher re-reading the whole textbook every single time you typed one word. That’s insanely slow, right?
XGrammar is basically the "smart cheat sheet" version of that teacher. Most of the time, it can tell right away whether a word is allowed just by looking at the current spot in the rulebook. Only the tricky cases need a deeper check. So instead of checking every possible word from scratch, it filters out tons of bad choices early.
There’s another cool trick: lots of words share the same beginning, like "read," "ready," and "reader." XGrammar remembers what it already checked for the shared beginning, so it doesn’t start over each time. That saves a ton of effort, especially when the word list is huge.
Why should you care? Because this means an AI can generate things that must be correct—like app commands, code, or forms—without getting super slow. It’s like making a robot that can both follow rules and stay fast. Pretty awesome, right?
Glossary
Context-Free Grammar (CFG)
A rule system for describing structured strings, including recursive and nested patterns. In technical terms, it is more expressive than regular expressions and is suitable for JSON, SQL, and DSLs.
Used as the formal specification for constrained generation.
Pushdown Automaton (PDA)
An automaton with a stack that can recognize languages generated by CFGs. The stack records nested expansions and returns to parent rules when a subrule finishes.
XGrammar compiles CFGs into a byte-level PDA for execution.
Token Mask
A per-step filter that marks which vocabulary tokens are allowed and which must be blocked by setting their logits to -inf. It is the core object in constrained decoding.
XGrammar focuses on generating this mask efficiently at runtime.
Adaptive Token Mask Cache
A cache that stores legality information for context-independent tokens at each PDA node, choosing a compact storage format automatically. It avoids scanning the full vocabulary at runtime.
Introduced in §3.1 as the main acceleration mechanism.
Context Expansion
An offline pruning method that extracts what strings can follow a rule in its parent context, represented as an expanded-suffix FSA. Tokens whose remaining suffix cannot match are rejected early.
Used in §3.2 to reduce context-dependent tokens.
Persistent Execution Stack
A shared tree structure that stores multiple current and historical stacks, enabling constant-time rollback and cheap branching. It avoids copying whole stacks when paths share prefixes.
Used in §3.3 for both runtime execution and preprocessing.
Open Questions Unanswered questions from this research
- 1 How robust are the gains across very different grammars, especially highly ambiguous, deeply recursive, or rapidly changing user-defined languages? The paper’s strongest evidence is JSON, so the full transfer curve is still open.
- 2 What is the best strategy for dynamic or multi-tenant serving, where grammar definitions may change frequently and offline preprocessing must be amortized carefully? The balance between latency, memory, and cache reuse remains unresolved.
Applications
Immediate Applications
Function calling and schema-constrained APIs
Teams building tool-use agents can use XGrammar to ensure outputs conform to JSON schemas or API signatures. The main requirement is a grammar or schema description; the expected outcome is fewer parsing failures and lower retry overhead.
Code, SQL, and DSL generation
Developers can compile language syntax into CFG constraints to keep generated code or queries syntactically valid. This is especially useful for autocomplete, assistants, and automated workflow generation.
Long-term Vision
Near-zero-overhead structured agents
The long-term vision is agent systems that always generate parseable, executable, and rollback-friendly outputs without visible latency penalties. The main obstacles are grammar diversity, dynamic updates, and integration into large serving stacks, but the direction is clear.
Abstract
The applications of LLM Agents are becoming increasingly complex and diverse, leading to a high demand for structured outputs that can be parsed into code, structured function calls, and embodied agent commands. These developments bring significant demands for structured generation in LLM inference. Context-free grammar is a flexible approach to enable structured generation via constrained decoding. However, executing context-free grammar requires going through several stack states over all tokens in vocabulary during runtime, bringing non-negligible overhead for structured generation. In this paper, we propose XGrammar, a flexible and efficient structure generation engine for large language models. XGrammar accelerates context-free grammar execution by dividing the vocabulary into context-independent tokens that can be prechecked and context-dependent tokens that need to be interpreted during runtime. We further build transformations to expand the grammar context and reduce the number of context-independent tokens. Additionally, we build an efficient persistent stack to accelerate the context-dependent token checks. Finally, we co-design the grammar engine with LLM inference engine to overlap grammar computation with GPU executions. Evaluation results show that XGrammar can achieve up to 100x speedup over existing solutions. Combined with an LLM inference engine, it can generate near-zero overhead structure generation in end-to-end low-LLM serving.