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

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

论文试图解决大型语言模型在生成结构化输出时面临的效率问题，特别是当使用上下文无关文法（CFG）进行约束解码时带来的运行时开销。这是一个重要的问题，因为随着LLM应用的复杂性和多样性增加，对结构化输出的需求也在增长。

论文提出了一种名为XGrammar的灵活高效的结构生成引擎。XGrammar通过将词汇表分为上下文无关和上下文相关的标记，并预先检查上下文无关标记，减少了运行时开销。此外，还引入了语法转换以扩展语法上下文，减少上下文无关标记的数量，并构建了一个高效的持久栈来加速上下文相关标记的检查。最后，XGrammar与LLM推理引擎协同设计，以重叠语法计算和GPU执行，从而实现高效生成。

论文通过一系列实验展示了XGrammar的有效性，包括高达100倍的速度提升。实验设计包括与现有解决方案的对比，使用了多种数据集进行验证，并且提供了开源代码。未来的研究可以进一步探索XGrammar在不同应用场景中的表现，特别是在大规模实时服务中的性能。

近期在这个领域的一些相关研究包括： 1. "Efficient Context-Free Grammar Parsing with Neural Networks" - 探索了神经网络在CFG解析中的应用。 2. "Grammar-Guided Generation for Large Language Models" - 提出了一种基于语法指导的生成方法。 3. "Optimizing Structured Output Generation in LLMs" - 研究了如何优化LLM中的结构化输出生成。