🤖 AI

XGrammar-2: Efficient Dynamic Structured Generation Engine for Agentic LLMs

XGrammar-2 is a high-efficiency structured generation engine designed for dynamic agentic LLM workloads, featuring tag-triggered structure switching and cross-grammar cache reuse to achieve over 6x faster compilation and near-zero end-to-end overhead compared to prior systems.

Original authors: Linzhang Li, Yixin Dong, Guanjie Wang, Ziyi Xu, Alexander Jiang, Tianqi Chen

Published 2026-05-27

📖 5 min read🧠 Deep dive

CC BY 4.0

Original authors: Linzhang Li, Yixin Dong, Guanjie Wang, Ziyi Xu, Alexander Jiang, Tianqi Chen

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

Imagine you are a chef (the AI) trying to follow a very strict recipe. Sometimes, the recipe is simple: "Make a sandwich." But in the world of AI agents, the recipe is often a complex, shifting set of instructions like: "Write a sentence, then switch to a JSON code block to call a weather tool, then switch back to writing a sentence, then switch to a specific format for a database query."

The problem is that traditional "kitchens" (AI engines) are great at following one fixed recipe, but they struggle when the recipe changes on the fly or when the chef has to switch between dozens of different complex formats instantly. They often have to stop, rewrite the whole recipe book from scratch before they can start cooking, which makes everything slow.

XGrammar-2 is a new, super-efficient kitchen engine designed specifically for these chaotic, dynamic cooking scenarios. Here is how it works, using simple analogies:

1. The "Magic Switch" (TagDispatch)

The Problem: Imagine a recipe that says, "Keep writing normally until you see the word 'STOP', then switch to a math mode, then switch back." Doing this with old methods is like trying to write a massive, tangled instruction manual where every possible word leads to a different page. It gets messy and huge.

The XGrammar-2 Solution: They introduced a feature called TagDispatch. Think of this as a magic switch or a traffic light.

The AI writes normally (green light).
The moment it sees a specific trigger (like a tag <function=weather>), the light instantly turns red, and the engine knows exactly which "sub-recipe" (the JSON format for weather) to switch to.
Once that sub-recipe is done, the light turns green again, and the AI goes back to writing normally.
Why it's cool: Instead of writing a giant, confusing manual, the engine just follows the traffic lights. It makes switching between free-flowing text and strict code instant and easy.

2. The "Shared Library" (Cross-Grammar Cache)

The Problem: Imagine you are cooking 100 different meals. 90 of them use the exact same "chopping onions" step, but the old engine treats every meal as a brand-new task. It re-learns how to chop onions from scratch for every single meal. This is a waste of time.

The XGrammar-2 Solution: They built a Shared Library (Cross-Grammar Cache).

Even if the final dishes (the full grammar) are different, the ingredients and steps (sub-structures) are often the same.
XGrammar-2 looks at the steps. If it sees, "Oh, I've already figured out how to chop onions for a similar dish," it doesn't re-calculate. It just grabs the pre-chopped onions from the library.
Why it's cool: It stops the engine from doing the same math over and over again. It reuses the "work" it has already done, even if the overall request is different.

3. The "Just-in-Time" Chef (JIT Compilation)

The Problem: In the old days, before you could cook a single bite, the engine had to read the entire recipe book for every single request. If the recipe was huge (like a tool-calling request with 500 possible tools), the engine would sit there for seconds just reading the book before cooking started.

The XGrammar-2 Solution: They use a Just-in-Time (JIT) approach.

Instead of reading the whole book first, the chef only reads the page they need right now.
While the AI is thinking about the first few words (the "prefill" phase), the engine is quietly preparing the next few pages of the recipe.
Why it's cool: It hides the preparation time. By the time the AI is ready to speak the next word, the engine has already prepped the next step. This makes the "first word" appear almost instantly, even for complex tasks.

4. The "Compressed Map" (Repetition State Compression)

The Problem: Some recipes have repetitive steps, like "Repeat this action 1,000 times." Old engines would try to draw a map with 1,000 separate dots for each step. This map becomes huge and slows everything down.

The XGrammar-2 Solution: They use Repetition State Compression.

Instead of drawing 1,000 dots, they draw one big "loop" arrow and say, "Go around here 1,000 times."
Why it's cool: It keeps the map small and simple, no matter how many times the AI has to repeat a step. This prevents the engine from getting bogged down by long lists or loops.

The Results: What Did They Find?

The paper tested this new engine against the current best methods:

Speed: It compiles the "recipe" (the grammar) 6 times faster than previous engines.
Efficiency: It adds almost zero delay to the AI's response time. It's so fast that the AI doesn't even notice it's there.
Compatibility: It works seamlessly with popular AI systems (like SGLang and vLLM) and handles complex tasks like calling tools or following strict response formats without breaking a sweat.

In short, XGrammar-2 is like upgrading an AI's brain from a slow, rigid librarian who has to re-shelve every book before answering a question, to a super-fast, flexible assistant who knows exactly where to find the answer, reuses previous knowledge, and switches topics instantly without missing a beat.

Technical Summary: XGrammar-2

Problem Statement

Modern Large Language Model (LLM) agents increasingly rely on dynamic structured generation, particularly for tool calling and response protocols. Unlike traditional structured generation tasks where the output schema is static and known in advance, agentic workloads exhibit significant structural dynamism:

Inter-request Dynamism: Each request may expose a different set of tools and schemas (often with per-tool access control), leading to a combinatorially large space of possible output grammars. Existing engines that cache entire grammars at the request level become ineffective, forcing expensive per-request preprocessing and increasing Time-to-First-Token (TTFT).
Intra-request Dynamism: Within a single request, the model must switch between free-form text and structured sub-grammars based on triggers (e.g., a specific tool name or channel tag). Expressing these conditional switches using standard Backus-Naur Form (BNF) or Extended BNF (EBNF) is cumbersome, inefficient, and scales poorly with the number of tools.

Existing constrained decoding methods (e.g., XGrammar, Outlines, llguidance) struggle with these dynamics. They either require full grammar compilation upfront (prohibitive for dynamic tool sets) or lack efficient mechanisms to handle the interleaving of free text and structured constraints within a single generation stream.

Methodology

XGrammar-2 is a structured generation engine designed specifically for dynamic agentic workloads. Its architecture is built upon two core design principles: first-class support for tag-triggered structure switching and fine-grained reuse across requests with different output structures.

1. TagDispatch: Dynamic Dispatch Semantics

To address intra-request dynamism, XGrammar-2 introduces TagDispatch, a grammar intrinsic that allows for efficient switching between free-form text and structured sub-grammars.

Mechanism: TagDispatch is parameterized by a list of tag–grammar pairs $(t_i, G_i)$ and a set of stop strings.
Operation: The engine operates in two modes:
- Dispatching Mode: The engine accepts ordinary text while using an Aho–Corasick (AC) automaton to incrementally match registered tags against the generated text.
- Dispatched Mode: Upon matching a tag, the engine switches to the corresponding sub-grammar $G_i$ . Once $G_i$ completes, control returns to the dispatching mode.
Advantage: This avoids the need to encode complex conditional logic into massive EBNF rules, significantly reducing grammar size and compilation complexity.

2. Cross-Grammar Cache

To address inter-request dynamism, XGrammar-2 implements a Cross-Grammar Cache to reuse token mask caches across different grammars that share common sub-structures.

Challenge: Determining if two Finite State Machines (FSMs) are equivalent is difficult when they contain rule references and cycles. Furthermore, token mask caches depend not just on the FSM structure but also on how that FSM is referenced (context expansion).
Solution: The system uses a hierarchical hashing algorithm:
- It constructs an FSM reference graph.
- For acyclic portions, it computes structural hashes bottom-up, incorporating the hashes of referenced FSMs.
- For cyclic references, it uses provisional hashes followed by cycle-hash refinement to ensure unique structural identifiers.
Reuse Strategy: When a new grammar state is encountered, the system checks the global cache pool. If a perfect match (same FSM and lookahead) is found, the cache is reused. If only a partial match exists (same FSM, different lookahead), the system re-checks uncertain tokens and updates the cache.

3. Earley-Based Adaptive Token Mask Cache

Moving away from Pushdown Automata (PDA) used in previous versions, XGrammar-2 utilizes an Earley parser for its adaptive token mask cache.

Rationale: PDA states can grow exponentially in non-deterministic grammars. The Earley parser maintains a set of partial parsing states (frontier) that is more efficient for complex context-free grammars.
Implementation: The cache is built only for scannable states (where the next symbol is a terminal). Non-scannable states are expanded via prediction and completion operations at runtime. Tokens are categorized as accepted, rejected, or context-dependent, with the latter requiring runtime context checks.

4. Just-In-Time (JIT) Compilation

To mitigate the high compilation cost of large, dynamic grammars:

Strategy: Instead of materializing the full token mask cache upfront, XGrammar-2 employs a configurable JIT system.
Execution: During the prefilling phase, the system estimates the cost of generating caches for specific states. It prioritizes compiling the $K$ most time-consuming states during prefilling, overlapping compilation with prefilling. The remaining states are compiled on-demand during the decoding phase, overlapping mask generation with decoding. This aims to hide compilation latency.

5. Repetition State Compression

To handle repetition structures common in JSON schemas (e.g., MinLength, MaxItems):

Problem: Naive expansion of repetition rules leads to a linear increase in grammar states relative to the repetition count.
Solution: The engine compresses repetition states. For large repetition ranges, it transforms the structure into a sequence of a base rule repeated $t$ times, followed by a compressed state representing the remaining range. This bounds the number of states to a constant regardless of the repetition limit, significantly reducing cache size and uncertainty.

Key Results

Experiments were conducted using datasets like BFCL-v3 and JSONSchemaBench, comparing XGrammar-2 against state-of-the-art engines (XGrammar, llguidance, Outlines) on various models (Qwen, Llama series).

Compilation Speed: XGrammar-2 achieves over 6× faster compilation compared to prior structured generation engines in dynamic settings. For example, while XGrammar required >1000ms to compile dynamic grammars, XGrammar-2 achieved ~10ms.
End-to-End Overhead: The system incurs near-zero end-to-end overhead in modern LLM serving systems. In function calling scenarios, the latency gap between constrained generation (XGrammar-2) and unconstrained generation was less than 6%.
Throughput: XGrammar-2 demonstrated superior token throughput compared to XGrammar across different batch sizes and model scales (e.g., 2.5× throughput improvement on Llama-3.2-1B with batch size 16).
Scalability: The cross-grammar cache memory overhead remains low and scales with the total number of unique tools used rather than the number of requests, preventing memory explosion in dynamic environments.
Ablation: Removing JIT increased preprocessing time by 8.1×; removing Cross-Grammar Cache increased mask generation time significantly; Repetition State Compression reduced preprocessing time by 99.6× for long-tail repetition cases.

Significance and Claims

The paper claims that XGrammar-2 provides a necessary evolution for LLM serving systems to support agentic applications. By decoupling the handling of dynamic tool sets from static grammar compilation, it enables:

Reliability: Strict enforcement of structural validity (e.g., OpenAI Harmony Response Format, tool calling schemas) without relying on post-hoc correction.
Efficiency: The ability to serve dynamic workloads with compilation and runtime costs comparable to static workloads.
Adoption: The engine has been integrated into open-source frameworks like SGLang and vLLM, demonstrating its practical viability in production-grade inference systems.

The authors position XGrammar-2 not as a replacement for model training techniques but as a complementary inference-time engine that can be combined with existing fine-tuning or prompting strategies to ensure robust, structured output in complex agent scenarios.