TL/DR（太长不看）:

  • 结构化解码允许精确控制 LLM 输出格式
  • vLLM 现在支持 outlines 和 XGrammar 后端，用于结构化解码
  • 最近 XGrammar 的集成使每个输出 token 的时间 (TPOT) 在负载下提高了 5 倍
  • 即将发布的 v1 版本专注于增强性能和混合请求批处理支持的计划级掩码广播

vLLM 是用于运行大型语言模型 (LLM) 的高吞吐量和高效推理引擎。在这篇文章中，我们将探讨语言模型的注释历史，描述 vLLM 中结构化解码的当前状态，以及最近与 XGrammar 的集成，以及 分享我们对未来改进的初步路线图。

我们还邀请用户从哲学的角度看待这篇博文，并在此过程中尝试假设结构化解码代表了我们思考 LLM 输出方式的根本转变。它在构建复杂的代理系统中也起着重要作用。

有关 vLLM 的更多信息，请查看我们的文档。

语言模型：简要的历史背景

1950 年，艾伦·图灵提出，一台高速数字计算机，如果用规则编程，可以表现出智能的<0xE2><0x80><0xAF>涌现行为<0xE2><0x80><0xAF>（图灵，1950 年）。这导致了人工智能发展的两种主要方法

  1. 传统人工智能 (GOFAI)：20 世纪 50 年代，研究人员迅速兴起了一种范式，即专家系统被设计用来复制人类专家的决策能力1，（或符号<0xE2><0x80><0xAF>推理<0xE2><0x80><0xAF>系统），Haugland 将其称为传统人工智能 (GOFAI)<0xE2><0x80><0xAF>(Haugeland, 1997)。然而，由于其语义表示无法扩展到通用任务（也称为“人工智能寒冬”<0xE2><0x80><0xAF>(Hendler, 2008)），它很快就遇到了资金问题。

  2. 新潮人工智能 (NFAI)：与此同时，唐纳德·诺曼的并行分布式处理<0xE2><0x80><0xAF>(Rumelhart et al., 1986)<0xE2><0x80><0xAF>小组研究了罗森布拉特的感知<0xE2><0x80><0xAF>(Rosenblatt, 1958)<0xE2><0x80><0xAF>的变体，他们提出在网络中除了输入和输出之外，还要设置隐藏层，以便根据训练过程中学到的内容推断出适当的响应。这些连接主义网络通常建立在统计方法之上2。鉴于数据的丰富性和摩尔定律3<0xE2><0x80><0xAF>导致了前所未有的计算量，我们看到连接主义网络在研究和生产用例中都占据了完全的主导地位，最值得注意的是<0xE2><0x80><0xAF>仅解码器<0xE2><0x80><0xAF>转换器的变体4<0xE2><0x80><0xAF>用于<0xE2><0x80><0xAF>文本生成<0xE2><0x80><0xAF>任务。因此，大多数现代转换器变体都被认为是 NFAI 系统。

总结

  • GOFAI 是确定性的和基于规则的，因为它的意图是通过显式编程注入的
  • NFAI 通常被认为是“黑盒”模型（输入：输入 - 输出：一些输出），数据驱动的，因为其内部表示的网络复杂性

为什么我们需要结构化解码？

Shogoth 作为 GPT。从某种意义上说，RLHF 或任何后训练方法都是将规则（GOFAI 系统）注入到任何大型复合 AI 系统中

LLM 在以下启发式方法中表现出色：给定一段文本，模型将生成一段连续的文本，它预测该文本是最有可能的 token。例如，如果您给它一篇维基百科文章，模型应该生成与该文章其余部分一致的文本。

在以下假设下，这些模型运行良好：输入提示必须是连贯且结构良好的，围绕用户想要实现的给定问题。换句话说，当您需要特定格式的输出时，LLM 可能是不可预测的。想想让模型生成 JSON——如果没有指导，它可能会生成有效的文本，但会破坏 JSON 规范5。

这就是结构化解码的用武之地。它使 LLM 能够生成遵循所需结构的输出，同时保留系统的非确定性性质。

像 OpenAI 这样的公司已经认识到这种需求，并实施了诸如 JSON 模式 等功能来约束6 输出格式。如果您之前使用过这些功能（例如代理工作流、函数调用、编码助手），那么您很可能正在使用底层结构化解码。

引导解码对于 LLM 就像 验证 对于 API 一样——它保证输出与您的期望相符。引导解码确保结构完整性，使开发人员能够轻松地将 LLM 集成到他们的应用程序中！

结构化解码和 vLLM

简单来说，结构化解码为 LLM 提供了一个要遵循的“模板”。用户提供一个“影响”模型输出的模式，确保符合所需的结构

top level view of structure decoding

从技术角度来看，推理引擎可以通过为任何给定模式的所有 token 应用偏差（通常通过 logits 掩码）来修改下一个 token 的概率分布。为了应用这些偏差，outlines 提出了通过有限状态机 (FSM) 为任何给定模式进行引导生成<0xE2><0x80><0xAF>(Willard & Louf, 2023)。这使我们能够在解码期间跟踪当前状态，并通过对输出应用 logits 偏差来过滤掉无效 token。

由 LMSys, 2024 提供。

在 vLLM 中，您可以通过将 JSON 模式传递给采样参数（通过 Python SDK 或 HTTP 请求）来使用它。

注意：在某些情况下，它甚至可以提高 LLM 的原生解码性能！

vLLM 之前的限制

当前 vLLM 对 Outlines 后端的支持存在一些限制

  1. 解码速度慢：FSM 必须在 token 级别构建，这意味着它每步只能转换一个 token 的状态。因此，它一次只能解码一个 token，导致解码速度缓慢。
  2. 批处理瓶颈：vLLM 中的实现严重依赖 logits 处理器7。因此，这是采样过程的关键路径。在批处理用例中，为每个请求编译 FSM 以及同步计算掩码意味着任何给定批次中的所有请求都将被阻止，从而导致较高的首个 token 时间 (TTFT) 和较低的吞吐量。
    • 我们发现编译 FSM 被证明是一项相对昂贵的任务，使其成为 TTFT 增加的重要因素。
  3. CFG 模式下的性能问题：通过 outlines 集成，虽然 JSON 模式相对较快，但 CFG 模式运行速度明显较慢，并且偶尔会崩溃引擎。
  4. 有限的高级功能支持：像 jump-forward decoding 这样的技术目前在 logits 处理器方法中是不可行的。它需要预填充一组 k-next token，而对于 logits 处理器，我们只能处理下一个 token。

与 XGrammar 集成

XGrammar 引入了一种新技术，通过下推自动机 (PDA) 批量约束解码。您可以将 PDA 视为“FSM 的集合，每个 FSM 代表一个上下文无关文法 (CFG)”。PDA 的一个显着优势是其递归性质，允许我们执行多个状态转换。它们还包括额外的优化（对于那些感兴趣的人）以减少文法编译开销。

这项进步通过将文法编译从 Python 移至 C，利用 pthread，解决了限制 (1)。此外，XGrammar 为解决未来版本中的限制 (4) 奠定了基础。以下是 XGrammar 和 Outlines 后端之间的性能比较

由 Michael Goin (Red Hat) 提供。

在 vLLM 的 v0 架构中，我们将 XGrammar 实现为 logits 处理器，并通过缓存 tokenizer 数据对其进行优化。虽然性能改进令人鼓舞，但我们相信仍有很大的优化空间。

在 XGrammar v0 集成中，仍然存在一些可用性问题，无法与所有用例的功能对等

  • 它尚不支持 GBNF 格式以外的文法（vLLM 上的 PR：github）
  • 它尚不支持正则表达式
  • 它尚不支持使用正则表达式模式或数值范围的复杂 JSON

vLLM 现在默认基本支持 XGrammar。在我们知道 XGrammar 不足以满足请求的情况下，我们会回退到 Outlines。

请注意，vLLM 还包括对 lm-format-enforcer 的支持。但是，从我们的测试中，我们发现，在某些长上下文测试用例中，lm-format-enforcer 无法强制执行正确的输出，并且在性能方面不如 Outlines。

v1 的初步计划

随着 v1 即将发布，我们正在制定结构化解码的初步计划

  1. 将引导解码转移到调度器级别
    • 原因：我们在调度器级别有更多关于哪些请求使用结构化解码的上下文，因此它不应阻止批处理中的其他请求（初步解决限制 (2)）。从某种意义上说，这会将引导解码移出关键路径。
    • 这将允许与 jump-forward decoding 更自然的垂直集成（解决限制 (4)）。
  2. 允许在一个进程中而不是每个 GPU 工作人员中进行位掩码计算
    • 原因：我们可以将此位掩码广播到每个 GPU 工作人员，而不是为每个 GPU 工作人员重复此过程。
    • 我们将仔细分析对每个使用引导解码的请求的每个样本广播掩码的带宽影响。
  3. 推测性解码和工具使用的良好基线
    • 原因：XGrammar 包括支持工具使用的计划，这样我们就可以摆脱 Python 的 tool parser。
    • 推测性解码中的树评分然后可以使用与 jump-forward decoding 相同的 API（这取决于引导解码在调度器级别的集成）。

注意：如果您有任何更多建议，我们非常乐意考虑。考虑通过 #feat-structured-output 加入 vLLM slack。

致谢

我们要感谢 vLLM 团队、XGrammar 团队、Aaron Pham (BentoML)、Michael Goin (Red Hat)、Chendi Xue (Intel) 和 Russell Bryant (Red Hat) 在将 XGrammar 引入 vLLM 以及不断努力改进 vLLM 中的结构化解码方面的宝贵反馈和协作。

参考文献

  • Bahdanau, D., Cho, K., & Bengio, Y. (2016). 通过联合学习对齐和翻译进行神经机器翻译. arXiv 预印本 arXiv:1409.0473
  • Haugeland, J. (1997). 心灵设计 II：哲学、心理学和人工智能. MIT 出版社。 https://doi.org/10.7551/mitpress/4626.001.0001
  • Hendler, J. (2008). 避免另一次人工智能寒冬。 IEEE 智能系统, 23(2), 2–4. https://doi.org/10.1109/MIS.2008.20
  • Hochreiter, S., & Schmidhuber, J. (1997). 长短期记忆。 神经计算。
  • Kaplan, J., McCandlish, S., Henighan, T., Brown, T. B., Chess, B., Child, R., Gray, S., Radford, A., Wu, J., & Amodei, D. (2020). 神经语言模型的缩放定律. arXiv 预印本 arXiv:2001.08361
  • Mikolov, T., Chen, K., Corrado, G., & Dean, J. (2013). 向量空间中词表示的有效估计. arXiv 预印本 arXiv:1301.3781
  • Rosenblatt, F. (1958). 感知器：大脑中信息存储和组织的概率模型。 心理学评论, 65(6), 386–408. https://doi.org/10.1037/h0042519
  • Rumelhart, D. E., McClelland, J. L., & Group, P. R. (1986). 并行分布式处理，第 1 卷：认知微观结构探索：基础. MIT 出版社。 https://doi.org/10.7551/mitpress/5236.001.0001
  • Shortliffe, E. H. (1974). MYCIN：用于为医生提供抗菌治疗选择建议的基于规则的计算机程序 （技术报告 STAN-CS-74-465）。斯坦福大学。
  • 统计机器翻译。(n.d.). IBM 模型. 统计机器翻译调查。 http://www2.statmt.org/survey/Topic/IBMModels
  • Turing, A. M. (1950). i.—计算机械与智能。 心灵, LIX(236), 433–460. https://doi.org/10.1093/mind/LIX.236.433
  • Vaswani, A., Shazeer, N., Parmar, N., Uszkoreit, J., Jones, L., Gomez, A. N., Kaiser, L., & Polosukhin, I. (2023). 注意力机制是你所需要的一切. arXiv 预印本 arXiv:1706.03762
  • Willard, B. T., & Louf, R. (2023). 大型语言模型的高效引导生成. arXiv 预印本 arXiv:2307.09702

  1. 艾伦·纽厄尔和赫伯特·西蒙在兰德公司的工作最初表明，计算机可以模拟智能的重要方面。

    另一个值得注意的应用是在医学领域 (Haugeland, 1997)。MYCIN 是 20 世纪 70 年代在斯坦福大学开发的，用于诊断和推荐血液感染的治疗方法 (Shortliffe, 1974)。MYCIN 的开发者认识到证明建议合理性的重要性，并实施了所谓的“规则追踪”来以人类易于理解的方式解释系统的推理。↩

  2. 在 20 世纪 90 年代，IBM 发布了一系列复杂的统计模型，这些模型经过训练以执行机器翻译 任务（统计机器翻译，n.d.）（另请参阅：康奈尔大学的这份讲义）。

    2001 年，词袋 (BoW) 变体模型在 0.3B token 上进行了训练，当时被认为是 SOTA (Mikolov et al., 2013)。这些早期的工作向研究界证明，考虑到统计建模可以捕获大型文本语料库的一般模式，统计建模优于用于语言处理的符号对应物。↩

  3. 2017 年，具有里程碑意义的论文“注意力机制是你所需要的一切”为神经机器翻译任务引入了 Transformer 架构 (Vaswani et al., 2023)，该架构基于 (Bahdanau et al., 2016) 首次提出的注意力机制。

    然后，OpenAI 引入了神经语言模型的缩放定律 (Kaplan et al., 2020)，这引发了基于基础语言模型构建这些系统的竞赛。↩

  4. 在基于注意力的 Transformer 之前，seq-to-seq 模型使用 RNN，因为它具有更长的上下文长度和更好的内存。但是，与前馈网络相比，它们更容易受到梯度消失/爆炸的影响，因此提出了 LSTM (Hochreiter & Schmidhuber, 1997) 来解决这个问题。然而，LSTM 的主要问题之一是，对于很久以前看到的数据，它们的记忆力往往很差。

    注意力机制论文通过将额外的位置数据编码到输入中来解决这个问题。该论文还额外提出了一种用于翻译任务的编码器-解码器架构，但是，鉴于其在零样本任务中的卓越性能，现在大多数文本生成模型都是仅解码器模型。

    基于注意力的 Transformer 比 LSTM 效果更好的众多原因之一是因为 Transformer 非常可扩展且硬件感知（您不能随意添加更多 LSTM 块并期望获得更好的长期保留）。有关更多信息，请参阅原始论文。↩

  5. 有人可能会争辩说，我们可以通过少样本提示可靠地实现这些，即“给我一个 JSON，它产生用户的地址。示例输出可以是……”。但是，不能保证生成的输出是有效的 JSON。这是因为这些模型是概率系统，因为它们是根据模型训练数据的分布“采样”下一个结果。

    有人可能还会争辩说，应该使用特定的微调模型进行 JSON 输出以执行此类情况。但是，微调通常需要大量的训练和更多的人工来管理数据、监控进度和执行评估，这不是每个人都能负担得起的巨大资源。↩

  6. 请注意，短语“[结构化/约束/引导]解码”可以互换使用，但它们都指的是“使用格式让模型结构化采样输出”的相同机制。↩

  7. 请参阅 HuggingFace 的这篇博文，了解如何使用 logits 处理器来控制生成过程。↩