arXiv:2411.15100v3 公告类型: 替换交叉 摘要：LLM代理的应用变得越来越复杂和多样化，这导致对结构化输出需求的增加，这些结构化输出可以解析为代码、结构化的函数调用和实体化代理命令。这些发展带来了对LLM推理中结构化生成的显著需求。上下文无关文法是一种通过受约束解码来实现结构化生成的灵活方法。然而，在运行时，执行上下文无关文法规则需要遍历词汇表中所有标记的多个堆状态，这在结构化生成中带来了不可忽略的开销。本文中，我们提出了XGrammar，这是一种灵活高效的大型语言模型结构生成引擎。XGrammar通过将词汇表分为不受上下文影响的标记和需要在运行时解释的受上下文影响的标记来加速上下文无关文法规则的执行。我们进一步构建了变换以扩展文法规则的上下文并减少不受上下文影响的标记的数量。此外，我们构建了一个高效的持久性堆栈以加速受上下文影响的标记检查。最后，我们与LLM推理引擎进行协同设计，以重叠语法计算与GPU执行。评价结果显示，XGrammar相对于现有解决方案可以实现高达100倍的加速。结合LLM推理引擎，它可以在端到端低LLM服务中实现接近零开销的结构化生成。