📊 statistics

Throughput-Optimal Scheduling Algorithms for LLM Inference and AI Agents

本文建立了大语言模型推理的数学排队论基础，证明了工作守恒调度算法能为个体和 AI 智能体工作负载实现最大吞吐量，同时通过评估现实世界系统证实了 Orca 和 Sarathi-Serve 的最优性，并警示了 FasterTransformer 和原生 vLLM 的不稳定性。

原作者： J. G. Dai, Tianze Deng, Yueying Li, Tianyi Peng

发布于 2026-05-19

📖 1 分钟阅读☕ 轻松阅读

CC BY 4.0

原作者： J. G. Dai, Tianze Deng, Yueying Li, Tianyi Peng

原始论文采用 CC BY 4.0 许可（http://creativecommons.org/licenses/by/4.0/）。 ✨ 这是对下方论文的AI生成解释。它不是由作者撰写或认可的。如需技术准确性，请参阅原始论文。阅读完整免责声明

想象你经营着一家高速工厂，专门制造定制机器人。在这家工厂里，每个订单（即“请求”）都要经过两个截然不同的阶段：

准备阶段（Prefill）：你阅读蓝图并收集所有必要的零件。这是一项繁重的体力活，需要大量的脑力（计算资源），但是一次性完成的。
组装阶段（Decode）：你开始组装机器人，一次添加一个零件，逐个进行。这是一项较慢、内存占用较高的工作，需要一步步完成。

你的工厂拥有一只巨大且超高速的机械臂（GPU），它可以同时处理多个订单。然而，这只机械臂有一个限制：它的夹爪一次只能承受特定总重量的零件（即Token 预算）。

你提供的这篇论文是一项数学研究，探讨如何组织订单，以确保你的工厂永不停工，并在不造成堵塞的情况下生产出尽可能多的机器人。

以下是他们研究发现的分解，使用了简单的类比：

1. 黄金法则：“不要让机械臂闲置”

这篇论文最重要的发现是一个被称为**“工作守恒”（Work-Conserving）**的概念。

想象你的机械臂准备抓取零件。

糟糕的做法：你只允许机械臂抓取“准备”阶段的零件，前提是只有“准备”阶段的订单在等待。如果“组装”阶段的订单在等待，即使机械臂有空位，你也忽略它们。或者，你只允许它抓取“组装”阶段的零件，前提是只有“组装”阶段的订单在等待。
- 结果：机械臂半空闲置，等待特定类型的订单，而另一类订单堆积如山。工厂速度变慢甚至崩溃。
好的做法（工作守恒）：如果机械臂有空位，你就用任何可用的东西填满它。你在同一个批次中混合“准备”零件和“组装”零件。只要有工作要做，你绝不让机械臂闲置。

论文的声明：遵循这种“填满桶”规则（如 Orca 和 Sarathi-Serve）的算法，在数学上被证明是最有效的。它们能够在系统不崩溃的情况下处理最大可能的工作量。

2. “旧”与“新”的工厂经理

作者测试了四种流行的“经理”（调度算法），看看谁遵循了黄金法则：

FasterTransformer & Vanilla vLLM（严格的经理）：这些经理太挑剔了。
- FasterTransformer 只抓取“组装”阶段的零件。如果没有“组装”订单，即使机械臂是空的，它也会忽略排队等待的“准备”订单。
- Vanilla vLLM 只抓取“准备”阶段的零件。如果没有“准备”订单，它会忽略“组装”订单。
- 裁决：这些不是最优的。在重负载下，它们会导致工厂堵塞且不稳定。
Orca & Sarathi-Serve（灵活的经理）：这些经理混合了两种类型的工作。它们用任何能装下的东西填满机械臂。
- 裁决：这些是最优的。它们让工厂以最大速度平稳运行。

3. "AI 代理”工厂（复杂工作流）

有时，一个订单不仅仅是一个机器人，而是一整组协同工作的机器人团队。

DAG（有向无环图）：想象一个工作流，其中订单 A 流向站点 1，然后站点 2，然后站点 3，并且绝不返回。
- 发现：只要工作流是直线（无循环），“不要让机械臂闲置”的规则在所有站点上仍然完美适用。
分叉 - 汇合（Fork-Join）：想象订单 A 分裂成三个子任务，分别送往三个不同的站点，它们必须全部完成后，最后一步才能开始。
- 发现：“不要让机械臂闲置”的规则在这里也依然有效。
循环（The Trap）：想象订单 A 从站点 1 流向站点 2，但订单 B 从站点 2 返回站点 1。它们在圆圈里互相追逐。
- 发现：在这里，“不要让机械臂闲置”的规则可能会失效。即使经理们尽了最大努力，循环交通也可能导致永远无法清除的交通堵塞。论文表明，如果你的工厂存在这些循环回路，你需要一个更聪明、更谨慎的经理，而不仅仅是一个“填满桶”的经理。

4. “桶大小”的意外

工厂还有第二个限制：批次大小（Batch Size）。这是机械臂能容纳的订单数量上限，无论它们有多重。

意外：作者发现，有时将机械臂填满至其绝对最大重量限制（Token 预算）实际上是一个坏主意。
类比：想象你有一个能装 100 磅的桶。你有 100 颗小鹅卵石（准备阶段）和 100 块重砖（组装阶段）。
- 如果你试图用砖块将桶装满到 100 磅，你可能只能装进 5 块砖。提起这沉重负载所需的时间很长。
- 但如果你停在 50 磅（较轻的负载），你可能能更快地提起它，从而每小时能完成更多次运输。
发现：在特定情况下，最高效的策略是在桶装满之前停止填充，以保持处理速度。这意味着，即使“好经理”（工作守恒）也会失败，如果工厂规则（批次大小限制）过于严格，且订单组合恰好会导致堵塞。

总结

这篇论文告诉我们：

混合你的工作：不要将“准备”和“组装”任务分开。将它们混合在同一个批次中，以保持 GPU 忙碌。
Orca 和 Sarathi-Serve 是赢家：它们遵循“混合并填满”的规则，使其成为大多数情况下最稳定、最高效的选择。
警惕循环：如果你的 AI 代理在服务器之间循环发送任务，简单的“填满桶”规则可能不起作用；你需要特殊的交通控制。
满并不总是最好：有时，在批次中留一点空位比将其填满更明智，这取决于单个任务的大小。

所有这些数学的目标是帮助工程师构建 AI 系统，使其在数百万人同时提问时不会崩溃。

技术摘要：面向大语言模型推理与 AI 智能体的吞吐量最优调度算法

问题陈述

随着大语言模型（LLM）和 AI 智能体的需求增长，优化推理系统以提高效率至关重要。尽管大量的工程努力集中在系统层面的改进上，但缺乏一个连贯的数学建模和排队论框架来评估调度算法。具体而言，本文旨在解决一个根本性问题：LLM 推理系统的最大吞吐量率是多少，以及哪些类别的调度算法可以达到这一极限？

与经典排队系统相比，LLM 推理呈现出独特的挑战：

双相处理：请求经历计算受限的**预填充（prefill）阶段（处理输入令牌以构建 KV 缓存），随后是内存 I/O 受限的解码（decode）**阶段（自回归令牌生成）。
批处理约束：为了最大化 GPU 利用率，请求被批处理。然而，混合预填充令牌和解码令牌会产生干扰，且硬件施加了**令牌预算（ $b_{max}$ ）以及通常的批大小（ $k_{max}$ ）**约束。
AI 智能体工作负载：现代应用涉及处理复杂智能体任务的 LLM 服务器网络，这些任务可能遵循有向无环图（DAG）拓扑、分叉 - 连接（fork-join）模式，或包含循环路由。

现有系统采用多种策略（例如 FasterTransformer、vLLM、Orca、Sarathi-Serve），具有不同的优先级（优先预填充 vs. 优先解码）和批处理能力（混合批处理 vs. 分离批处理）。从业者目前依赖成本高昂的、特定于工作负载的基准测试来选择系统，缺乏关于稳定性或吞吐量最优性的理论保证。

方法论

作者开发了一个严格的排队论框架来建模 LLM 推理系统。

1. 随机建模

基本模型：系统将建模为表示两类批服务队列的离散时间马尔可夫链（DTMC）。
- 类别：请求存在于预填充队列或解码队列中。
- 批处理：服务器同时处理来自两个队列的令牌批，受令牌预算 $b_{max}$ 限制。
- 不对称性：单个请求的预填充令牌可以批量处理，而解码令牌是严格串行的（每批每个请求一个）。
处理时间模型：利用经验轨迹，批处理时间 $t_b$ 近似为依赖于令牌负载 $b$ 的分段常数函数：
$t_b = c + a \cdot \lceil b/b_0 \rceil$
其中 $c$ 是基础成本， $a$ 是每 $b_0$ 个令牌块的单位边际成本。该模型捕捉了 LLM 推理中线性层计算的主导地位。

2. 分析框架

流体极限技术：作者采用流体极限框架（Dai 1995, Stolyar 1995）来分析稳定性。他们证明，在特定条件下，缩放后的随机过程收敛于确定性流体模型。
稳定性定义：如果未处理令牌的总数在时间趋于无穷大时不发散，则系统是稳定的（正递归的）。
调度类别：分析聚焦于工作守恒（work-conserving）算法（即在可能时尽可能将批处理填满至容量 $b_{max}$ 的算法），并引入K-FCFS条件（具有有限越界的首到先服务）来处理混合批处理的复杂性。

3. 扩展

该框架扩展至：

并行服务器：具有负载均衡（随机或加入最短队列）的系统。
多类网络：单个服务器处理多个请求类别（例如，不同的智能体步骤）。
网络拓扑：具有 DAG 路由和分叉 - 连接同步的多服务器网络。
循环路由：具有反馈回路（Rybko–Stolyar 类型）的网络分析。
批大小约束：受令牌预算（ $b_{max}$ ）和最大批大小（ $k_{max}$ ）双重约束的系统分析。

主要贡献与结果

1. 工作守恒调度的吞吐量最优性

本文确立了一个基本设计原则：工作守恒调度算法可实现单服务器 LLM 推理及具有 DAG 或分叉 - 连接拓扑的网络的最大吞吐量。

定理 2：对于单服务器，如果到达负载 $\lambda(m_p + m_d)$ 小于最大处理率 $b_{max}/t_{b_{max}}$ ，则任何工作守恒的 K-FCFS 算法都能使系统稳定。反之，如果负载超过此阈值，则任何算法下系统都不稳定。
推论：这提供了一个理论上限（ $b_{max}/t_{b_{max}}$ ），并验证了行业向工作守恒调度器转变的趋势。

2. 现有系统的评估

将理论框架应用于现实世界算法产生了清晰的分类：

吞吐量最优（工作守恒）：
- Orca：支持混合批处理（预填充 + 解码），具有预填充优先级。
- Sarathi-Serve：支持分块预填充，具有解码优先级和混合批处理。
- 最新 vLLM（带分块预填充）：工作守恒。
次优/不稳定（非工作守恒）：
- FasterTransformer：优先解码但禁止混合批处理。当解码请求不足以填满批处理时，即使有预填充请求在等待，它也会让 GPU 空闲。
- 原生 vLLM：优先预填充但禁止混合批处理。它在处理仅预填充的批处理时，会让解码请求等待。
实验验证：现实世界轨迹证实，非工作守恒算法（FasterTransformer、原生 vLLM）在中等负载下变得不稳定（队列爆炸），而工作守恒算法（Sarathi-Serve、Orca）保持稳定。

3. AI 智能体工作负载与网络拓扑

DAG 与分叉 - 连接：本文证明，只要每个服务器的负载条件成立，工作守恒调度对于按 DAG 或分叉 - 连接拓扑排列的 LLM 服务器网络仍然是吞吐量最优的。
循环路由（Rybko–Stolyar 反例）：作者证明，工作守恒调度不足以处理具有循环路由的网络。他们构建了一个双服务器网络，其中在工作守恒策略下特定的优先级分配会导致不稳定，即使总负载低于容量。这凸显了在循环拓扑中需要仔细设计优先级或采用非工作守恒策略（例如背压）。

4. 批大小约束的影响

当在令牌预算（ $b_{max}$ ）之外施加最大批大小约束（ $k_{max}$ ）时：

稳定区域在 $(\lambda_{prefill}, \lambda_{decode})$ 平面上变为二维凸包，而不是简单的标量阈值。
反直觉发现：在某些机制下（特别是涉及混合批处理的稳定区域顶点附近），始终填满至 $b_{max}$ 的严格工作守恒算法可能无法使系统稳定。最优稳定性可能需要以较低的令牌负载（例如 $b_0$ ）运行，以平衡预填充和解码令牌的处理速率。这表明在严格的批大小约束下，需要自适应调度策略。

意义与主张

本文声称提供了 LLM 推理调度的首个严格排队论基础。其意义在于：

设计原则：它确定了“工作守恒”作为从业者关键的设计原则，从理论上保证 Sarathi-Serve 和 Orca 等算法是吞吐量最优的，同时警告避免 FasterTransformer 和原生 vLLM 等非混合批处理方法。
** bridging 社区**：通过提供一个形式化模型来捕捉 LLM 独特的双相和批处理特征，它降低了排队论社区为 LLM 系统做出贡献的门槛。
AI 智能体指导：它将稳定性分析扩展到 AI 智能体工作负载，揭示了虽然 DAG 拓扑具有鲁棒性，但循环拓扑需要比简单工作守恒策略更复杂的调度。
细微约束：它揭示了批大小限制等实际约束可以根本性地改变稳定区域，挑战了“填满批处理”总是最优的假设。

作者总结道，虽然他们的工作确立了吞吐量最优性的基准，但未来的工作必须解决延迟优化、更丰富的处理时间模型（纳入注意力层），以及针对复杂约束和网络拓扑的自适应算法设计。