TL/DR（太长不看）:

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

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

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

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

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

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

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

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

总结

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

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

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

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

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

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

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

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

结构化解码和 vLLM

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

top level view of structure decoding

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

由 LMSys, 2024 提供。

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

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

vLLM 之前的限制

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

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

与 XGrammar 集成

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

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

由 Michael Goin (Red Hat) 提供。

在 vLLM 的 v0 架构中，我们将 XGrammar 实现为 logit 处理器，并使用 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 的 工具解析器。
    • 推测性解码中的树评分可以像 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：哲学、心理学和人工智能。麻省理工学院出版社。 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 卷：认知微观结构探索：基础。麻省理工学院出版社。 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). Attention Is All You Need。 arXiv 预印本 arXiv:1706.03762
  • Willard, B. T., & Louf, R. (2023). 大型语言模型的有效引导生成。 arXiv 预印本 arXiv:2307.09702

  1. Allen Newell 和 Herbert Simon 在 RAND 的工作最初表明，计算机可以模拟智能的重要方面。

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

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

    2001 年，在 0.3B token 上训练的词袋 (BoW) 变体模型被认为是当时最先进的 (SOTA) 模型（Mikolov et al., 2013）。早期的这些工作向研究界证明，对于语言处理而言，统计建模胜过符号对应物，因为它能够捕获大型文本语料库的通用模式。 ↩

  3. 2017 年，具有里程碑意义的论文“Attention is all You Need” 介绍了用于神经机器翻译任务的 Transformer 架构 (Vaswani et al., 2023)，该架构基于 (Bahdanau et al., 2016) 首次提出的注意力机制。

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

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

    Attention 论文通过将额外的位置数据编码到输入中来解决这个问题。该论文还额外提出了一种用于翻译任务的编码器-解码器架构，然而，如今大多数文本生成模型都是仅解码器模型，因为它们在零样本任务中具有卓越的性能。

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

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

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

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

  7. 有关使用 logit 处理器控制生成过程的信息，请参阅 HuggingFace 的这篇博文。 ↩