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

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

Speakers: Yixin Dong, Carnegie Mellon University; Charlie F. Ruan; Yaxing Cai; Ziyi Xu; Tianqi Chen

Conference: MLSys 2025

YouTube: https://www.youtube.com/watch?v=None

Overview

The XGrammar project introduces a novel and highly efficient engine for structured generation by Large Language Models (LLMs), addressing a critical need in modern AI applications. Presented by Yixin Dong from Carnegie Mellon University, this work, a collaborative effort including researchers from Shanghai Jiao Tong University, UC Berkeley, and Nvidia, tackles the dual challenges of flexibility and efficiency in constrained decoding. As LLMs are increasingly deployed in agentic systems, the ability to reliably produce outputs adhering to specific formats—such as JSON schemas, regular expressions, or programming language grammars—becomes paramount. XGrammar offers a robust solution that guarantees 100% structural correctness without imposing significant performance overhead.

The core innovation of XGrammar lies in its use of Context-Free Grammar (CFG) as a universal representation for various structural constraints, coupled with sophisticated optimizations for runtime efficiency. By employing a pushdown automaton (PDA) for parsing and an adaptive token mask cache that leverages insights into token dependency, XGrammar dramatically reduces the computational cost associated with generating valid tokens. Furthermore, its co-design with LLM serving engines allows for seamless integration and overlapping of grammar operations with LLM inference, ultimately achieving near-zero overhead for constrained decoding in practical scenarios. This breakthrough enables developers to build more reliable and accurate LLM-powered applications that demand precise output formats, from function calling to code generation.

The significance of XGrammar extends to the broader ML systems community by providing an open-source, highly performant solution that has already seen widespread adoption. Its ability to maintain structural integrity while preserving inference speed is a game-changer for deploying LLMs in production environments where both reliability and latency are critical. The project's success underscores the importance of foundational systems research in unlocking the full potential of large language models for complex, real-world tasks.

Background

▶ Watch: Introduction to XGrammar and structured generation problem (0:00)

In the rapidly evolving landscape of AI, Large Language Models (LLMs) are central to a growing array of agentic applications. These applications frequently require LLMs to generate outputs that conform to predefined structures, such as JSON schemas for API interactions, regular expressions for data extraction, or the grammars of specific programming languages for code generation. While LLMs excel at generating natural language, their inherent probabilistic nature means they can sometimes produce outputs that are syntactically incorrect or fail to adhere to specified formats. This lack of structural correctness can lead to downstream errors, system failures, and a degraded user experience.

To address this, constrained decoding emerged as a critical technique. The workflow for constrained decoding involves augmenting the standard LLM decoding process with an additional step: token masking. In each step of LLM inference, after the model predicts token probabilities, a token mask is applied. This mask identifies and invalidates tokens that would violate the specified structure at that particular point in the generation sequence, leaving only structurally valid tokens available for sampling. By consistently applying this mask, constrained decoding guarantees 100% structural correctness of the generated output. Empirical evidence, particularly in function calling tasks, has shown that constrained decoding not only ensures perfect structural adherence but also significantly boosts end-to-end accuracy, as the model is guided towards valid and meaningful outputs.

Despite its clear benefits, the practical implementation of constrained decoding faces two primary challenges:

1. Flexibility: The need to support a diverse array of output structures is paramount. These can range from simple regex patterns to complex JSON objects with nested fields, or even the intricate grammars of programming languages like Python or Rust. Developing a unified framework that can express and enforce such varied constraints without requiring custom solutions for each type of structure is a significant hurdle.
2. Efficiency: The process of generating the token mask at each decoding step can be computationally intensive. For a typical LLM vocabulary size of, for example, 128,000 tokens, validating each potential token against the current structural constraint can introduce substantial overhead. If this validation process takes too long (e.g., 600 milliseconds per step), it can become the bottleneck for LLM inference, which might otherwise complete in a mere 30 milliseconds. This performance penalty can render constrained decoding impractical for real-time or high-throughput applications.

XGrammar was developed precisely to overcome these flexibility and efficiency challenges, aiming to make constrained decoding a universally applicable and performant technique for LLM-powered systems.

Key Findings

▶ Watch: XGrammar's solution: CFG for flexibility, near-zero overhead (3:00)

XGrammar introduces a comprehensive solution that fundamentally redefines the flexibility and efficiency of structured generation for LLMs. Its key findings and contributions address the core challenges of constrained decoding:

1. Unified Representation with Context-Free Grammar (CFG): XGrammar successfully employs Context-Free Grammar (CFG) as a general and powerful representation for a wide spectrum of structural constraints. CFG serves as a superset for commonly used formats like JSON schema, regular expressions, and the grammars of programming languages. This unified approach eliminates the need for ad-hoc solutions for different structures, providing unparalleled flexibility in defining output formats.
2. Near-Zero Overhead Constraint Decoding: A paramount achievement of XGrammar is its ability to enable constrained decoding with near-zero overhead, particularly demonstrated in JSON generation tasks. Measurements on serving engines like SG long show that the time per output token with XGrammar's constrained decoding is virtually identical to that without any constraints. This breakthrough means that users can leverage the benefits of 100% structural correctness without incurring a noticeable performance penalty, making it viable for production-grade, latency-sensitive applications.
3. Adaptive Token Mask Cache for Efficiency: The project introduces an innovative adaptive token mask cache that dramatically accelerates the mask generation process. Recognizing that not all parsing states require full stack context, XGrammar observes that over 99% of tokens can be validated based solely on the stack top element of the pushdown automaton. These "context-independent" tokens are pre-computed and cached. Only the remaining less than 1% of "context-dependent" tokens, which require the full stack for validation, are computed on-the-fly. This intelligent caching strategy minimizes redundant computations and is crucial for achieving high efficiency.
4. Co-design with LLM Engine for Overlapping Operations: XGrammar achieves further efficiency gains through a strategic co-design with LLM serving engines. It intelligently overlaps grammar-related computations with LLM inference stages. Specifically, grammar compilation can be performed concurrently with LLM pre-filling, and mask generation can be overlapped with LLM decoding. This parallel execution effectively hides the computational latency of constraint enforcement, contributing significantly to the near-zero end-to-end overhead.
5. Robust End-to-End Performance and Adoption: Beyond mask generation, XGrammar integrates additional optimizations such as context expansion (analyzing the PDA to improve cache hit rates) and pushdown automaton optimizations (persistent stack, state merging, inlining). These contribute to significant speedups in both mask generation time and overall end-to-end inference speed compared to existing baselines. The project has been integrated into multiple popular LLM serving engines, including SG long and vLLM (implied by LLM C L L M), demonstrating its practical utility and robustness.
6. Open-Source and Industry Collaboration: XGrammar is an open-source project that has garnered substantial community and industry support, evidenced by 8 million downloads and adoption by numerous LLM serving engines. This widespread acceptance underscores its value and impact in the AI ecosystem, making advanced structured generation accessible to a broad developer base.

Technical Deep Dive

▶ Watch: Understanding Context-Free Grammar as a unified language (4:00)

XGrammar's technical prowess stems from a sophisticated combination of formal language theory and system-level optimizations. At its foundation, it leverages Context-Free Grammar (CFG) as the universal language for defining structural constraints.

A Context-Free Grammar is a formal grammar in which every production rule is of the form A -> β, where A is a single nonterminal symbol, and β is a string of terminal and/or nonterminal symbols. This structure allows for the description of recursive and nested data structures, making it highly suitable for diverse formats. For instance, to describe an array that can contain strings and can be arbitrarily nested, a CFG might define rules like:

• Root -> Array
• Array -> '[' (String | Array)* ']'
• String -> '"' Letter* '"'

Where Letter represents any alphanumeric character. These rules demonstrate how non-terminals (like Array and String) can refer to each other and even themselves, enabling the definition of complex, recursive structures.

To parse and validate strings against a CFG, XGrammar employs a Pushdown Automaton (PDA). A PDA is an extension of a finite automaton that includes a stack. This stack allows the PDA to "remember" the context of parsing, which is crucial for handling context-free languages. In XGrammar's design, each rule within the CFG is converted into a corresponding finite automaton within the PDA. For a grammar with three rules, there would be three such finite automata. The PDA then parses an input string by attempting to expand rules starting from the root rule, with the stack recording the ongoing expansion process.

Consider the parsing of an input like [ "A". The process would begin from the Root rule. Upon encountering the [ token, the PDA identifies it as the start of an Array. It then "pushes" the Array rule onto the stack and transitions to the state corresponding to the Array rule. Next, seeing the " token, it recognizes the start of a String within the Array. The String rule is then pushed onto the stack. Finally, A is processed as part of the String, and the current state within the String automaton is pushed. The stack thus maintains a history of the active grammar rules and their current parsing positions, enabling precise validation.

The primary efficiency challenge arises from the need to generate a token mask for a large vocabulary (e.g., 128,000 tokens) at every decoding step. A naive approach would involve running the PDA parsing logic for each of these 128,000 tokens to determine its validity. If each token validation takes 5 microseconds, this sums up to 640 milliseconds per step, which is significantly slower than typical LLM inference times (around 30 milliseconds). This makes the naive approach infeasible.

XGrammar's solution to this is the Adaptive Token Mask Cache. The key insight is that while the full PDA state (including the entire stack) can be infinitely long, the validity of most tokens can be determined by only a small portion of this state—specifically, the stack top. The team found that over 99% of potential tokens are context-independent, meaning their validity (or invalidity) can be definitively established by inspecting only the topmost element of the PDA's stack. These tokens can be pre-computed and cached for each possible stack-top state. For the remaining less than 1% of tokens, termed context-dependent, the full stack context is indeed necessary for validation. These tokens are computed on-the-fly, as they depend on the deeper parsing history. This adaptive caching strategy drastically reduces the average computation time for mask generation.

Further eliminating overhead, XGrammar implements a co-design with the LLM serving engine. This involves intelligently overlapping the grammar-related operations with the LLM's inference pipeline:

• Grammar compilation, which involves converting the CFG into the PDA and preparing initial cache entries, is overlapped with the LLM's pre-filling stage (processing the prompt).
• Mask generation, the process of determining valid tokens for the next step, is overlapped with the LLM's decoding stage (generating subsequent tokens).

By executing these tasks concurrently, XGrammar effectively hides much of the computational latency associated with constrained decoding, leading to its advertised near-zero overhead.

Beyond these core innovations, XGrammar incorporates several other optimizations to enhance end-to-end efficiency:

• Context Expansion: This technique involves analyzing the PDA structure to predict future parsing states and expand the cache's awareness, thereby increasing the hit rate for the adaptive token mask cache.
• Pushdown Automaton Optimizations: These include low-level system design choices like using a persistent stack to avoid frequent memory allocations, state merging to reduce the number of distinct PDA states, and inlining of common grammar patterns to simplify the automaton and speed up transitions.

Collectively, these technical advancements allow XGrammar to provide a robust, flexible, and highly efficient solution for structured generation, making it a powerful tool for deploying LLMs in complex, constraint-driven applications.

Experimental Setup & Results

▶ Watch: Efficiency bottleneck: Parsing all tokens for mask generation (7:00)

The evaluation of XGrammar rigorously focused on demonstrating its efficiency and effectiveness across various dimensions, particularly in comparison to existing baselines. While specific baseline names were not exhaustively detailed in the talk, the implicit comparison is against conventional or less optimized constrained decoding methods.

Metrics:

The primary metrics used to assess XGrammar's performance were:

1. Mask Generation Time: The time taken to compute the valid token mask for the entire vocabulary at a single decoding step. This directly measures the overhead introduced by the constraint enforcement mechanism.
2. End-to-End Inference Speed (Time per Output Token): This metric measures the total time required to generate each token, including both LLM inference and mask generation, providing a holistic view of performance in real-world scenarios.
3. Structural Correctness: A binary metric indicating whether the generated output strictly adheres to the specified grammar.
4. End-to-End Accuracy: For function calling tasks, this measures whether the generated output is not only structurally correct but also semantically accurate (e.g., correctly calls the intended function with valid arguments).

Experimental Setup:

XGrammar was integrated into multiple popular LLM serving engines to validate its performance in practical deployment environments. The speaker explicitly mentioned integration with SG long and LLM C L L M (likely referring to vLLM, a widely used high-throughput serving engine for LLMs). This integration allowed for direct benchmarking of XGrammar's performance within production-ready inference pipelines.

Supported Structures and Models:

While JSON was a primary focus for demonstrating efficiency gains, the Q&A session clarified that XGrammar has been tested with other complex structures, including XML and a Python Domain-Specific Language (DSL). The talk also briefly referenced different model sizes, such as "Q1 2.5, 72B," when discussing accuracy differences.

Headline Results:

1. Mask Generation Time: XGrammar achieved a significant speedup in mask generation time compared to all evaluated baselines. This directly validates the effectiveness of the adaptive token mask cache and PDA optimizations.
2. Near-Zero End-to-End Overhead: For JSON tasks on SG long, XGrammar demonstrated that the time per output token with constrained decoding was the same as without constrained decoding. This is a critical result, indicating that the co-design and overlapping of grammar operations effectively hide the constraint enforcement latency, making XGrammar's overhead virtually negligible.
3. 100% Structural Correctness: Across function calling tasks, XGrammar consistently ensured 100% structural correctness of the generated outputs, eliminating common LLM errors related to malformed JSON or invalid syntax.
4. Increased End-to-End Accuracy: Beyond structural correctness, constrained decoding with XGrammar was shown to significantly increase end-to-end accuracy in function calling tasks. This highlights its ability to guide the LLM towards more semantically correct and usable outputs.
5. Robustness Across Models: While accuracy differences might be marginal for very large, well-trained models (e.g., Q1 2.5, 72B), XGrammar proves particularly beneficial for less well-trained models or for function calls that were not explicitly present in the training data. This positions it as a training-free method to enhance reliability.

The experimental results robustly confirm XGrammar's claims of both high flexibility and exceptional efficiency, making it a transformative tool for structured generation with LLMs.

Practical Implications

▶ Watch: Adaptive Token Mask Cache for improved mask generation efficiency (8:10)

XGrammar's advancements have profound practical implications for a wide range of stakeholders in the AI/ML ecosystem, from individual practitioners to large infrastructure teams.

For Practitioners and Model Builders:

• Reliable Agentic AI: XGrammar is a cornerstone for building robust agentic AI systems. In scenarios where LLMs interact with external tools, APIs, or databases, the output must strictly adhere to predefined formats (e.g., JSON for API calls, SQL for database queries). XGrammar guarantees this structural correctness, drastically reducing runtime errors and improving the reliability of autonomous agents.
• Enhanced Function Calling: For function calling and tool use, XGrammar ensures that the LLM always generates valid function signatures and arguments, even for complex or nested data structures. This directly translates to higher end-to-end accuracy and a more seamless integration of LLMs into software workflows.
• Code Generation and DSLs: When generating code or interacting with Domain-Specific Languages (DSLs), XGrammar can enforce syntactic correctness according to the language's grammar. This capability is invaluable for tasks like generating configuration files, scripting, or even full program snippets, ensuring the output is immediately runnable.
• Training-Free Accuracy Boost: For models that may not be extensively fine-tuned on specific structured generation tasks, or for novel function calls not seen during training, XGrammar offers a training-free method to significantly improve output quality and accuracy. This reduces the need for expensive retraining or extensive data augmentation.

For Infrastructure Teams and Deployers:

• Near-Zero Latency Impact: The most critical implication for infrastructure teams is the near-zero performance overhead. This means that constrained decoding can be deployed in production environments without introducing significant latency, making it viable for real-time applications where every millisecond counts. This removes a major barrier to adopting structurally correct LLM outputs at scale.
• Resource Efficiency: By intelligently caching and overlapping operations, XGrammar minimizes the additional computational resources required for constraint enforcement. This translates to more efficient utilization of GPUs and other hardware, leading to cost savings in deployment.
• Simplified Deployment: As an open-source project with integrations into popular LLM serving engines like vLLM, XGrammar simplifies the deployment of advanced structured generation capabilities. Teams can leverage existing infrastructure and easily incorporate XGrammar without extensive custom development.

Tradeoffs and Limitations:

While XGrammar offers significant benefits, it's important to acknowledge certain tradeoffs and current limitations:

• Complexity of Grammars: While CFG is highly flexible, defining extremely complex grammars, such as the full grammar of a major programming language like Rust or parsing the full nuances of natural language, remains an active area of research. The talk acknowledged that supporting "full JSON or full Rust is still quite an open question."
• Natural Language Nuances: While CFGs originated to describe natural languages, capturing all the subtleties and ambiguities of human language (e.g., semantic constraints, pragmatic rules) with a pure CFG approach is exceptionally challenging. XGrammar is primarily designed for formal, well-defined structures, not the full breadth of natural language.
• Marginal Gains for Highly Capable Models: For very large, extensively trained LLMs that are already proficient at generating specific structured outputs (e.g., JSON), the additional accuracy benefits of constrained decoding might be marginal. However, even in these cases, the 100% guarantee of structural correctness remains valuable for robust system design.

In essence, XGrammar democratizes the ability to generate structurally perfect outputs from LLMs, transforming them into more reliable and precise tools for a new generation of AI applications.

Key Takeaways

• XGrammar addresses the critical need for flexible and efficient structured generation from LLMs in agentic applications and function calling tasks.
• It achieves 100% structural correctness for LLM outputs by applying constraint decoding, significantly boosting end-to-end accuracy.
• The system uses Context-Free Grammar (CFG) as a unified representation, supporting diverse structures like JSON, regex, XML, and programming language DSLs.
• XGrammar achieves near-zero overhead for constrained decoding, notably for JSON tasks, by leveraging an adaptive token mask cache and co-design with LLM serving engines to overlap grammar operations with LLM inference.
• The adaptive token mask cache efficiently validates tokens by primarily relying on the stack top (for >99% context-independent tokens), computing only a small fraction on-the-fly.
• XGrammar is an open-source project that has seen widespread adoption (8 million downloads) and integration into major LLM serving engines like SG long and vLLM.

About the Speaker(s)

The talk was presented by Yixin Dong from Carnegie Mellon University. This work is a joint collaboration involving researchers from multiple prestigious institutions and industry leaders, including Carnegie Mellon University, Shanghai Jiao Tong University, UC Berkeley, and Nvidia. The team's collective expertise spans deep learning, systems design, and natural language processing, enabling the development of a highly optimized and impactful solution for LLM structured generation.