vLLM 中的结构化解码：入门指南

总结 (TL/DR):

• 结构化解码允许对大模型 (LLM) 的输出格式进行精确控制
• vLLM 现在支持 outlines 和 XGrammar 两种后端来进行结构化解码
• 近期集成的 XGrammar 在负载下将输出 token 的耗时 (TPOT) 提升了高达 5 倍
• 即将发布的 v1 版本将专注于增强性能，并引入调度层面的掩码广播，以支持混合请求批处理

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

我们还邀请用户从哲学的角度审视这篇文章，并试图探讨结构化解码代表了我们看待 LLM 输出方式的根本性转变。它在构建复杂的智能体系统 (agentic system) 中也起着重要作用。

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

语言模型：简要历史背景

1950 年，艾伦·图灵提出，一台由规则编程的高速数字计算机可以表现出智能的涌现行为 (Turing, 1950)。这导致了 AI 发展的两种主要方法：

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

2. 新派 AI (NFAI)：与此同时，唐纳德·诺曼 (Donald Norman) 的并行分布式处理小组 (Rumelhart et al., 1986) 研究了罗森布拉特感知机 (Rosenblatt, 1958) 的变体，他们在网络中提出了除输入和输出之外的隐藏层，以便根据训练过程中学到的内容推断出适当的响应。这些联结主义网络通常建立在统计方法之上²。鉴于数据的丰富和摩尔定律³带来的前所未有的计算能力，我们看到联结主义网络在研究和生产用例中占据了绝对主导地位，最显著的就是用于文本生成任务的纯解码器 (decoder-only) Transformer 变体⁴。因此，大多数现代 Transformer 变体都被视为 NFAI 系统。

总结

• GOFAI 是确定性且基于规则的，其意图通过明确的编程注入
• NFAI 通常被视为“黑盒”模型（输入：某种输入 - 输出：某种输出），鉴于其内部表示的联结主义性质，它是数据驱动的

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

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

这些模型在以下假设下运行良好：输入提示词必须连贯，并围绕用户想要解决的特定问题构建。换句话说，当你需要特定格式的输出时，LLM 可能会不可预测。试想让模型生成 JSON——在没有指导的情况下，它可能会生成虽然文本有效但违反 JSON 规范的内容⁵。

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

OpenAI 等公司已经意识到了这种需求，实现了诸如 JSON 模式 等功能来约束⁶输出格式。如果你之前构建过这些功能（例如智能体工作流、函数调用、编码助手），你很可能在底层使用了结构化解码。

引导式解码 (Guided decoding) 对 LLM 而言，正如验证对 API 而言——它充当了输出与预期相符的保证。引导式解码确保了结构的完整性，使开发者能够轻松地将 LLM 集成到他们的应用程序中！

结构化解码与 vLLM

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

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

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

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

vLLM 之前的局限性

当前 vLLM 对 Outlines 后端的支持存在一些局限性：

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

与 XGrammar 的集成

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

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

在 vLLM 的 v0 架构中，我们将 XGrammar 实现为一个 logit 处理器，并针对 tokenizer 数据进行了缓存优化。虽然性能改进令人鼓舞，但我们认为仍有很大的优化空间。

XGrammar v0 集成在实现与所有用例的功能对齐方面仍存在一些可用性问题：

• 尚未支持 GBNF 格式以外的文法（vLLM 上的 PR: github）
• 尚未支持正则表达式
• 尚未支持使用正则表达式模式或数字范围的复杂 JSON
  • 目前有几个 PR 试图覆盖这些用法。有一个 vLLM 上的 bugfix PR 和一个上游 PR

vLLM 现在默认对 XGrammar 提供基础支持。在已知 XGrammar 不足以处理请求的情况下，我们会回退到 Outlines。

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

v1 版本的初步计划

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

1. 将引导式解码移至调度层面
   • 原因：我们在调度层面拥有更多关于哪些请求使用结构化解码的信息，因此它不应该阻塞批次中的其他请求（初步解决了局限性 (2)）。从某种意义上说，这将引导式解码移出了关键路径。
   • 这将允许与向前跳跃解码进行更自然的垂直集成（解决局限性 (4)）。
2. 允许在单个进程中计算位掩码，而不是在每个 GPU 工作节点中计算
   • 原因：我们可以将此位掩码广播给每个 GPU 工作节点，而不是在每个 GPU 工作节点上重复此过程。
   • 我们将仔细分析为每个使用引导式解码的请求的每个样本广播掩码的带宽影响。
3. 为推测解码和工具使用提供良好的基准
   • 原因：XGrammar 包含支持工具使用的计划，这样我们就可以摆脱 Python 的工具解析器。
   • 推测解码中的树评分可以使用与向前跳跃解码相同的 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). Neural Machine Translation by Jointly Learning to Align and Translate. arXiv preprint arXiv:1409.0473
• Haugeland, J. (1997). Mind Design II: Philosophy, Psychology, and Artificial Intelligence. The MIT Press. https://doi.org/10.7551/mitpress/4626.001.0001
• Hendler, J. (2008). Avoiding Another AI Winter. IEEE Intelligent Systems, 23(2), 2–4. https://doi.org/10.1109/MIS.2008.20
• Hochreiter, S., & Schmidhuber, J. (1997). Long Short-Term Memory. Neural Computation.
• Kaplan, J., McCandlish, S., Henighan, T., Brown, T. B., Chess, B., Child, R., Gray, S., Radford, A., Wu, J., & Amodei, D. (2020). Scaling Laws for Neural Language Models. arXiv preprint arXiv:2001.08361
• Mikolov, T., Chen, K., Corrado, G., & Dean, J. (2013). Efficient Estimation of Word Representations in Vector Space. arXiv preprint arXiv:1301.3781
• Rosenblatt, F. (1958). The perceptron: A probabilistic model for information storage and organization in the brain. Psychological Review, 65(6), 386–408. https://doi.org/10.1037/h0042519
• Rumelhart, D. E., McClelland, J. L., & Group, P. R. (1986). Parallel Distributed Processing, Volume 1: Explorations in the Microstructure of Cognition: Foundations. The MIT Press. https://doi.org/10.7551/mitpress/5236.001.0001
• Shortliffe, E. H. (1974). MYCIN: A Rule-Based Computer Program for Advising Physicians Regarding Antimicrobial Therapy Selection (Technical Report STAN-CS-74-465). Stanford University.
• Statistical Machine Translation. (n.d.). IBM Models. Statistical Machine Translation Survey. http://www2.statmt.org/survey/Topic/IBMModels
• Turing, A. M. (1950). i.—Computing Machinery And Intelligence. Mind, 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 preprint arXiv:1706.03762
• Willard, B. T., & Louf, R. (2023). Efficient Guided Generation for Large Language Models. arXiv preprint arXiv:2307.09702