大型语言模型 (LLM) 代理的应用日益复杂多样，对可解析为代码、结构化函数调用和具身代理命令的结构化输出的需求也日益增长。这些发展对 LLM 推理中的结构化生成提出了重大需求。上下文无关文法是一种灵活的方法，可以通过约束解码来实现结构化生成。然而，上下文无关文法的执行需要在运行时遍历词汇表中所有标记的多个堆栈状态，这给结构化生成带来了不可忽略的开销。本文提出了一种用于大型语言模型的灵活高效的结构生成引擎 XGrammar。XGrammar 通过将词汇表划分为可预先检查的上下文无关标记和需要在运行时解释的上下文相关标记来加速上下文无关文法的执行。我们进一步构建转换以扩展语法上下文并减少上下文无关标记的数量。此外，我们构建了一个高效的持久堆栈来加速上下文相关标记的检查。最后，我们将语法引擎与 LLM 推理引擎共同设计，以使语法计算与 GPU 执行重叠。评估结果表明，XGrammar 与现有解决方案相比，速度最多可提升 100 倍。结合 LLM 推理引擎，它可以在端到端低 LLM 服务中实现近乎零开销的结构化生成。