XGrammar-2: Dynamic and Efficient Structured Generation Engine for Agentic LLMs
XGrammar-2 introduces TagDispatch and cross-grammar cache, achieving 6× faster structured generation for dynamic agent workloads.
Key Findings
Methodology
This paper proposes XGrammar-2, a structured generation engine designed for dynamic agent workloads. It features TagDispatch, a mechanism enabling intra-request structure switching triggered by tags, and a cross-grammar cache that reuses shared substructures across different requests. The system leverages Earley parsing to handle non-deterministic grammars, combined with adaptive token mask caching, JIT compilation, and repetition compression to optimize runtime efficiency. TagDispatch employs a deterministic automaton (AC automaton) for multi-tag matching, facilitating seamless transitions between free-form text and structured sub-grammars. The cross-grammar cache utilizes FSM hashing to identify and reuse identical substructures, significantly reducing compilation overhead. The entire architecture is integrated into modern LLM inference systems, demonstrating over 6× speedup in tool calling scenarios with negligible latency overhead.
Key Results
- XGrammar-2 achieves over 6-fold acceleration in tool calling compilation speed compared to prior static grammar engines, reducing request processing time substantially, especially in environments with extensive and variable tool sets.
- In multi-model, multi-task settings, the end-to-end latency remains nearly unaffected, confirming its suitability for real-time deployment in industrial systems.
- The introduction of TagDispatch allows dynamic switching within a single request, improving the expressiveness and accuracy of generated responses, and enabling models to adapt to complex response protocols effectively.
Significance
This work addresses a critical bottleneck in deploying large language models for complex, dynamic tasks involving tool invocation and response protocols. By innovatively combining tag-triggered structure switching and substructure reuse, XGrammar-2 significantly enhances the efficiency and flexibility of structured generation. Its ability to handle request-level variability and intra-request structure switching paves the way for more intelligent, adaptable AI agents. The techniques developed here have broad implications for industry applications such as conversational AI, automated customer service, and interactive systems, where responsiveness and correctness are paramount. Furthermore, the system's modular design facilitates integration with existing inference frameworks, promoting widespread adoption and further innovation.
Technical Contribution
The key technical contributions include: 1) TagDispatch, a first-class grammar construct supporting intra-request structure switching based on tags; 2) a hierarchical FSM hashing algorithm for identifying and reusing shared substructures across grammars, addressing inter-request dynamism; 3) an adaptive token mask cache built on Earley parsing, improving efficiency for complex, non-deterministic grammars; 4) a JIT compilation framework that amortizes grammar compilation costs over runtime, reducing initial overhead; 5) a repetition state compression algorithm that enhances robustness and reduces runtime overhead for recurring grammar patterns. These innovations collectively enable high-speed, flexible structured generation compatible with modern LLM inference pipelines.
Novelty
This work is the first to integrate TagDispatch with cross-grammar FSM hashing for dynamic structured generation. Unlike prior static grammar-based approaches, XGrammar-2 dynamically switches structures within requests and reuses substructures across requests, addressing the limitations of traditional constrained decoding. Its combination of Earley parser-based adaptive caching and JIT compilation introduces a new paradigm for efficient, flexible grammar handling in large-scale language models. This approach significantly advances the state-of-the-art by enabling real-time, dynamic structure switching without sacrificing speed or accuracy, setting a new benchmark in structured generation technology.
Limitations
- Despite its efficiency, XGrammar-2's performance may degrade with extremely large or highly complex grammar sets, where hash collisions or cache management overhead become significant.
- The system relies on well-designed tags and protocols; poorly structured or inconsistent tags could impair structure switching accuracy and efficiency.
- In resource-constrained environments, the overhead of JIT compilation and cache maintenance might introduce latency, limiting real-time performance in some scenarios.
Future Work
Future research will explore integrating multi-modal inputs (images, audio) to extend TagDispatch capabilities, supporting richer interaction protocols. Additionally, optimizing FSM hashing algorithms for even larger and more complex grammars, possibly through learned hashing or neural approximations, is a key direction. The authors also plan to develop distributed cache management strategies to handle large-scale, multi-user environments, enhancing scalability. Further, combining this framework with reinforcement learning to optimize structure switching policies could improve adaptability and response quality in dynamic contexts.
AI Executive Summary
In recent years, large language models (LLMs) have revolutionized natural language understanding and generation, powering applications from chatbots to automated assistants. However, as these systems are increasingly deployed in complex, real-world scenarios, their ability to generate structured, protocol-compliant responses dynamically becomes critical. Traditional constrained decoding methods rely on static grammars, which are insufficient when the response structures vary significantly across requests or within a single interaction.
This challenge is particularly evident in agent-based applications, where models invoke tools, follow response protocols, and switch between different output formats based on context. Existing engines struggle to efficiently handle such dynamism, often resorting to costly per-request preprocessing or static rule sets that limit flexibility. Recognizing this gap, the authors introduce XGrammar-2, a novel structured generation engine designed specifically for dynamic workloads.
XGrammar-2's core innovation lies in its dual mechanisms: TagDispatch and cross-grammar cache. TagDispatch enables intra-request structure switching triggered by tags embedded in the output, allowing models to seamlessly transition between free text and structured sub-grammars. This is achieved through a deterministic automaton that matches tags in real-time, ensuring fast and accurate dispatching. On the other hand, the cross-grammar cache leverages FSM hashing techniques to identify and reuse shared substructures across different requests, significantly reducing the overhead of repeated grammar compilation.
To support these mechanisms, the system incorporates an adaptive token mask cache based on the Earley parser, which efficiently handles non-deterministic and recursive grammars. Coupled with JIT compilation, this approach amortizes the cost of grammar processing over runtime, minimizing latency. Additionally, a repetition state compression algorithm further enhances robustness and efficiency when recurring patterns are present.
Extensive experiments demonstrate that XGrammar-2 outperforms prior state-of-the-art engines by over six times in compilation speed, with negligible impact on overall latency. It has been integrated into open-source inference frameworks like vLLM and SGLang, confirming its practicality for industrial deployment. The results highlight its potential to enable more responsive, flexible, and protocol-compliant AI agents, capable of handling complex tool invocation and dynamic response protocols in real-time.
Looking ahead, the authors plan to extend the framework to multi-modal inputs, optimize hashing algorithms for larger grammars, and develop distributed cache management strategies. These advancements aim to further improve scalability, adaptability, and efficiency, paving the way for next-generation intelligent systems capable of sophisticated, protocol-driven interactions. Overall, XGrammar-2 represents a significant step forward in structured generation technology, addressing fundamental challenges with innovative solutions that blend theoretical rigor and engineering practicality.
Deep Dive
Abstract
Modern LLM agents increasingly rely on dynamic structured generation, such as tool calling and response protocols. Unlike traditional structured generation with static structures, these workloads vary both across requests and within a request, posing new challenges to existing engines. We present XGrammar-2, a structured generation engine for dynamic agentic workloads. Our design is based on two key ideas: first-class support for tag-triggered structure switching, and fine-grained reuse across requests with different output structures. Concretely, XGrammar-2 introduces TagDispatch for dynamic structural dispatching and Cross-Grammar Cache for substructure-level cache reuse across grammars. It further improves efficiency with an Earley-based adaptive token mask cache, just-in-time compilation, and repetition state compression. Experiments show that XGrammar-2 achieves over 6x faster compilation than prior structured generation engines, and incurs near-zero end-to-end overhead in modern LLM serving systems.
References (20)
Synchromesh: Reliable code generation from pre-trained language models
Gabriel Poesia, Oleksandr Polozov, Vu Le et al.
Training Stochastic Model Recognition Algorithms as Networks can Lead to Maximum Mutual Information Estimation of Parameters
J. Bridle
Singularity
S. Weber
The Berkeley Function Calling Leaderboard (BFCL): From Tool Use to Agentic Evaluation of Large Language Models
Shishir G. Patil, Huanzhi Mao, Fanjia Yan et al.
Three models for the description of language
N. Chomsky
An efficient context-free parsing algorithm
J. Earley
Efficient string matching
A. Aho, M. J. Corasick
May the source be with you.
S. Mathieson
A General-Purpose Algorithm for Constrained Sequential Inference
Daniel Deutsch, Shyam Upadhyay, Dan Roth
PICARD: Parsing Incrementally for Constrained Auto-Regressive Decoding from Language Models
Torsten Scholak, Nathan Schucher, Dzmitry Bahdanau
WGRAMMAR: Leverage Prior Knowledge to Accelerate Structured Decoding
Ran Wang, Xiaoxuan Liu, Hao Ren et al.
Validating Large Language Models with ReLM
Michael Kuchnik, V. Smith, George Amvrosiadis
Generative Agents: Interactive Simulacra of Human Behavior
J. Park, Joseph O'Brien, Carrie J. Cai et al.
Grammar Prompting for Domain-Specific Language Generation with Large Language Models
Bailin Wang, Zi Wang, Xuezhi Wang et al.
Efficient Semiring-Weighted Earley Parsing
Andreas Opedal, Ran Zmigrod, Tim Vieira et al.
Code Llama: Open Foundation Models for Code
Baptiste Rozière, Jonas Gehring, Fabian Gloeckle et al.
Efficient Memory Management for Large Language Model Serving with PagedAttention
Woosuk Kwon, Zhuohan Li, Siyuan Zhuang et al.
XGrammar: Flexible and Efficient Structured Generation Engine for Large Language Models
Yixin Dong, Charlie F. Ruan, Yaxing Cai et al.
FlashInfer: Efficient and Customizable Attention Engine for LLM Inference Serving
Zihao Ye, Lequn Chen, Ruihang Lai et al.
Cited By (5)
Parser States Already Know: Structure-Conditioned KV Persistence for Structured Generation
Neurosymbolic Embodied Agents
Accelerating Constrained Decoding with Token Space Compression
Future Validity is the Missing Statistic: From Impossibility to Φ-Estimation for Grammar-Faithful Speculative Decoding
VibeServe: Can AI Agents Build Bespoke LLM Serving Systems?