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

arXiv: https://arxiv.org/abs/2411.15100 · HTML: https://mlsanity.com/paper/2411.15100/

## Key facts

- Cited by 75 papers in the map (data through 14 Oct 2026).
- Placed in General LLM agent frameworks and benchmarks, one of 16 directions in LLM agents and tool use.
- Builds on 17 of its 49 references that are in the map.
- First posted on arXiv 22 Nov 2024.

## Placed in

- LLM agents and tool use / [General LLM agent frameworks and benchmarks](https://mlsanity.com/agents/general-llm-agent-frameworks-and-benchmarks/)
- Efficient LLM inference and serving / [Serving systems and request scheduling](https://mlsanity.com/inference/serving-systems-and-request-scheduling/)

## Builds on (most cited first, 17 of 17)

- [The Llama 3 Herd of Models](https://mlsanity.com/paper/2407.21783/) (2024)
- [Evaluating Large Language Models Trained on Code](https://mlsanity.com/paper/2107.03374/) (2021)
- [Efficient Memory Management for Large Language Model Serving with PagedAttention](https://mlsanity.com/paper/2309.06180/) (2023)
- [Tree of Thoughts: Deliberate Problem Solving with Large Language Models](https://mlsanity.com/paper/2305.10601/) (2023)
- [Qwen2 Technical Report](https://mlsanity.com/paper/2407.10671/) (2024)
- [SGLang: Efficient Execution of Structured Language Model Programs](https://mlsanity.com/paper/2312.07104/) (2023)
- [CodeT5: Identifier-aware Unified Pre-trained Encoder-Decoder Models for Code Understanding and Generation](https://mlsanity.com/paper/2109.00859/) (2021)
- [LLM+P: Empowering Large Language Models with Optimal Planning Proficiency](https://mlsanity.com/paper/2304.11477/) (2023)
- [PICARD: Parsing Incrementally for Constrained Auto-Regressive Decoding from Language Models](https://mlsanity.com/paper/2109.05093/) (2021)
- [SpecInfer: Accelerating Generative Large Language Model Serving with Tree-based Speculative Inference and Verification](https://mlsanity.com/paper/2305.09781/) (2023)
- [Synchromesh: Reliable code generation from pre-trained language models](https://mlsanity.com/paper/2201.11227/) (2022)
- [Neural Machine Translation with Byte-Level Subwords](https://mlsanity.com/paper/1909.03341/) (2019)
- [Examining Zero-Shot Vulnerability Repair with Large Language Models](https://mlsanity.com/paper/2112.02125/) (2021)
- [Reading Between the Lines: Modeling User Behavior and Costs in AI-Assisted Programming](https://mlsanity.com/paper/2210.14306/) (2022)
- [Grammar Prompting for Domain-Specific Language Generation with Large Language Models](https://mlsanity.com/paper/2305.19234/) (2023)
- [Automata-based constraints for language model decoding](https://mlsanity.com/paper/2407.08103/) (2024)
- [Validating Large Language Models with ReLM](https://mlsanity.com/paper/2211.15458/) (2022)

## Built on by (most cited first, 30 of 75)

- [ReMA: Learning to Meta-think for LLMs with Multi-Agent Reinforcement Learning](https://mlsanity.com/paper/2503.09501/) (2025)
- [JSONSchemaBench: A Rigorous Benchmark of Structured Outputs for Language Models](https://mlsanity.com/paper/2501.10868/) (2025)
- [Enforcing Temporal Constraints for LLM Agents](https://mlsanity.com/paper/2512.23738/) (2025)
- [Fast Controlled Generation from Language Models with Adaptive Weighted Rejection Sampling](https://mlsanity.com/paper/2504.05410/) (2025)
- [PrefillOnly: An Inference Engine for Prefill-only Workloads in Large Language Model Applications](https://mlsanity.com/paper/2505.07203/) (2025)
- [Think Inside the JSON: Reinforcement Strategy for Strict LLM Schema Adherence](https://mlsanity.com/paper/2502.14905/) (2025)
- [DINGO: Constrained Inference for Diffusion LLMs](https://mlsanity.com/paper/2505.23061/) (2025)
- [Social World Models](https://mlsanity.com/paper/2509.00559/) (2025)
- [WebLLM: A High-Performance In-Browser LLM Inference Engine](https://mlsanity.com/paper/2412.15803/) (2024)
- [Quantifying the Utility of User Simulators for Building Collaborative LLM Assistants](https://mlsanity.com/paper/2605.09808/) (2026)
- [Surfer-H Meets Holo1: Cost-Efficient Web Agent Powered by Open Weights](https://mlsanity.com/paper/2506.02865/) (2025)
- [Mitigating Bias in Locally Constrained Decoding via Tractable Proposals](https://mlsanity.com/paper/2606.01926/) (2026)
- [Correctness-Guaranteed Code Generation via Constrained Decoding](https://mlsanity.com/paper/2508.15866/) (2025)
- [XGrammar-2: Dynamic and Efficient Structured Generation Engine for Agentic LLMs](https://mlsanity.com/paper/2601.04426/) (2026)
- [The Hidden Cost of Structured Generation in LLMs: Draft-Conditioned Constrained Decoding](https://mlsanity.com/paper/2603.03305/) (2026)
- [In Agents We Trust, but Who Do Agents Trust? Latent Source Preferences Steer LLM Generations](https://mlsanity.com/paper/2602.15456/) (2026)
- [RefineStat: Efficient Exploration for Probabilistic Program Synthesis](https://mlsanity.com/paper/2509.01082/) (2025)
- [Orchestrating Dual-Boundaries: An Arithmetic Intensity Inspired Acceleration Framework for Diffusion Language Models](https://mlsanity.com/paper/2511.21759/) (2025)
- [Thinking Before Constraining: A Unified Decoding Framework for Large Language Models](https://mlsanity.com/paper/2601.07525/) (2026)
- [Constrained Decoding for Diffusion Language Models via Efficient Inference over Finite Automata](https://mlsanity.com/paper/2607.07026/) (2026)
- [Metamodel-Guided Model Generation with Layered Constraints](https://mlsanity.com/paper/2510.25890/) (2025)
- [CaveAgent: Transforming LLMs into Stateful Runtime Operators](https://mlsanity.com/paper/2601.01569/) (2026)
- [Token-Oriented Object Notation vs JSON: A Benchmark of Plain and Constrained Decoding Generation](https://mlsanity.com/paper/2603.03306/) (2026)
- [Typed Decision Models: An Early Evidence Audit and Evaluation Checklist](https://mlsanity.com/paper/2609.32160/) (2026)
- [WGRAMMAR: Leverage Prior Knowledge to Accelerate Structured Decoding](https://mlsanity.com/paper/2507.16768/) (2025)
- [Training-Free Multimodal Large Language Model Orchestration](https://mlsanity.com/paper/2508.10016/) (2025)
- [DICE: Structured Reasoning in LLMs through SLM-Guided Chain-of-Thought Correction](https://mlsanity.com/paper/2510.09211/) (2025)
- [NoReGeo: Non-Reasoning Geometry Benchmark](https://mlsanity.com/paper/2601.10254/) (2026)
- [Future Validity is the Missing Statistic: From Impossibility to Phi-Estimation for Grammar-Faithful Speculative Decoding](https://mlsanity.com/paper/2605.07698/) (2026)
- [The Extrapolation Cliff in On-Policy Distillation of Near-Deterministic Structured Outputs](https://mlsanity.com/paper/2605.08737/) (2026)

## Abstract (arXiv)

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.