🤖 AI

Geometry-Aware Online Scheduling for LLM Serving: From Theoretical Bound to System Practice

本文提出了一种具有几何感知能力的在线调度框架，其包含最小体积优先（Smallest Volume First, SVF）和 1-bit SVF 算法，这些算法通过比传统的以时间为中心的启发式算法更有效地解决键值（Key-Value）缓存的动态二维内存占用问题，在理论上提升了竞争比，并在实践中增强了大语言模型（LLM）的推理性能。

原作者： Li Kong, Qi Qi, Yinyu Ye, Zijie Zhou

发布于 2026-06-23

📖 1 分钟阅读☕ 轻松阅读

CC BY 4.0

原作者： Li Kong, Qi Qi, Yinyu Ye, Zijie Zhou

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

想象一下你正在经营一家繁忙的咖啡店。这不仅仅是任何一家普通的咖啡店；这是一个高科技咖啡店，你制作的每一杯饮品都需要消耗特定的柜台空间（内存），而且随着制作时间的延长，所需的空间也会不断增加。

在大型语言模型（LLM）的世界里，这种“柜台空间”被称为 KV Cache。每当 AI 生成一个词（token）时，它都需要额外的内存来记住刚刚说过的话，以便让对话持续进行。如果你用完了柜台空间，整个店铺就必须停工。

问题所在：“最短作业优先”的错误

长期以来，计算机系统一直使用一种叫做 最短作业优先（Shortest Job First, SJF） 的规则来管理这些请求。其逻辑很简单：“如果有人点了一杯快速制作的浓缩咖啡，就让他们先走，因为很快。如果有人点了一杯复杂的、需要 20 分钟才能做好的拿铁，就让他们等着。”

该论文指出，在 AI 世界里，这个规则其实是失效的。原因如下：

陷阱： 在普通的商店里，一个短订单只会占用很短时间的空间。但在 AI 咖啡店里，即使是一个“短”请求，如果顾客要求讲一个长篇故事，也可能需要巨大的柜台空间。
二维现实： 论文指出，我们需要从两个维度来看待问题：时间（需要多久）和空间（随着增长会消耗多少内存）。旧规则只考虑了时间。
结果： 通过仅优先处理“快”的任务，系统经常会被那些起步很快但会吃掉所有内存的请求所堵塞，从而阻塞了其他所有人。这就像是让一位顾客点了一杯极小的浓缩咖啡，但随后这位顾客决定在柜台旁坐上一小时，挡住了咖啡师为其他人制作饮品。

解决方案：“最小总体积优先”（SVF）

作者提出了一种新的规则，叫做 最小总体积优先（Smallest Volume First, SVF）。他们不再问：“这个任务有多快？”而是问：“这个请求在其整个生命周期内总共会占用多少柜台空间？”

把这想象成在装载一辆搬家卡车：

旧方法 (SJF)： 你先装载最小的箱子，希望它们能塞进去。
新方法 (SVF)： 你计算每一个物品的总“体积”（高 × 宽 × 深），然后优先装载那些总空间占用最小的物品。

通过这样做，系统可以快速清理掉那些“体积小”的请求。这为更大的请求腾出了空间，让它们能更早地开始运行，防止整个系统陷入停滞。

“一位元”技巧 (1-bit SVF)

准确预测一段对话会持续多久是非常困难的。这就像试图猜测一位顾客在停止说话之前到底会说多少个字。论文引入了一个聪明的捷径，叫做 1-bit SVF。

系统并不试图预测精确的单词数量，而只是问一个简单的问题：“这是一个短请求还是一个长请求？”（是/否）。

它使用极少量的信息（仅仅一个“位元/bit”）来对请求进行分类。
出人意料的是，论文表明这种简单的猜测几乎与复杂的预测一样有效。这就像咖啡师只需问一句：“您是要喝快餐咖啡还是长饮？”并根据这个简单的答案做出决策。这节省了大量的脑力（计算能力），同时仍能保持排队的顺畅流动。

这篇论文证明了什么

作者不仅是凭直觉猜测这行得通，他们还通过数学进行了证明：

数学证明： 他们展示了在最坏情况下（例如突发的人流高峰），他们的新方法保证比旧有的“最短作业优先”方法表现更好。他们将数学保证从可能比完美情况差 48 倍，收窄到了仅差 5 倍。
测试： 他们在真实的 AI 模型（Llama-3.1）上使用了一个流行的系统 called vLLM 进行了测试。
- 结果： 新方法让所有人的 AI 响应都变快了，尤其是减少了“尾部延迟”（即最慢请求的等待时间）。
- 效率： “1-bit”版本非常轻量化，在保持出色表现的同时，几乎没有给系统带来额外的延迟。

总结

简单来说，这篇论文告诉我们：不要仅仅根据 AI 请求完成的速度来评判它们。要根据它们在运行时占用了多少“内存空间”来评判。 通过转向“最小总体积优先”策略，甚至使用一种超级简单的“长短”判断，我们可以让 AI 聊天机器人变得更快、更流畅，并且不易在重载下崩溃。

技术摘要：面向 LLM 推理的几何感知在线调度

问题陈述

在大语言模型（LLM）的交互式场景部署中，面临着一个关键瓶颈：键值（KV）缓存动态内存占用管理。与任务规模固定的传统调度问题不同，LLM 推理展现出一种独特的二维时空几何增长特性：

内存-时间耦合：在自回归解码过程中，执行时间与内存扩张呈线性耦合；每生成一个 token，KV 缓存的占用量就会增加。
连续批处理动态性：现代推理引擎（如 vLLM）使用连续批处理（continuous batching），其中并发批次大小在每次解码步骤后都会随着请求的完成和新请求的进入而动态波动。

现有的调度启发式算法主要基于最短作业优先（SJF），其根植于经典的以时间为中心的建模。这些算法未能捕捉到 LLM 推理的几何现实。近期的理论研究 [10] 表明，在这些特定的几何约束下，SJF 会产生无界的最差情况竞争比，这在经典的调度理论与现代 LLM 推理的物理现实之间造成了根本性的鸿沟。

方法论

作者提出了一种几何感知在线调度框架，将优先级度量指标从一维执行时间转向二维内存体积。

核心算法：最小体积优先 (SVF)

SVF 不仅仅隔离执行时间，而是评估一个请求在整个生命周期内的内存消耗积分。对于一个提示词长度为 $s_i$ 、输出长度为 $o_i$ 的请求 $r_i$ ，其体积 $v_i$ 定义为：
$v_i = s_i \cdot o_i + \frac{o_i^2 + o_i}{2}$
该公式量化了请求所占据的“内存-时间”总面积。SVF 作为一个严格的贪心策略，按 $v_i$ 的升序对请求进行排序。其实现被解耦为两个过程：一个用于批量查询输出长度的后台预测器，以及一个负责将最高优先级（最小体积）的请求纳入门控批次的调度器，直到达到 KV 缓存容量上限。

轻量化变体：1-bit SVF

为了最小化计算开销，作者引入了 1-bit SVF。该变体使用二分类器取代精确长度预测，将请求分类为“短”（ $m=0$ ）或“长”（ $m=1$ ）。

它为每一类分配一个全局代理长度 $O_m$ 。
代理体积计算为 $\hat{v}_i = s_i \cdot O_m + \frac{O_m^2 + O_m}{2}$ 。
这种设计仅提取单比特的信息，同时保留了核心的时空调度保证。

理论贡献

本文提供了严密的数学基础，超越了经验性的试错法，提供了形式化保证：

收紧最差情况界限（突发到达）：
- 对于在已知输出长度下的 SVF，在突发到达模型下，作者证明其最差情况竞争比（CR）满足 CR $\le$ 5。这显著收紧了先前文献 [10] 中发现的 CR $\le$ 48 的界限。
- 该证明利用了一种新颖的“宏观证书（macroscopic certificate）”方法，表明每一次阻塞步骤都意味着活跃内存质量 $> M/2$ ，从而直接将算法的等待时间与最优离线调度的下界对齐。
- 对于 1-bit SVF，其竞争比被限制在 $O(T)$ 内（其中 $T$ 是最大模型长度），证明了即使在信息极少的情况下，系统在极端负载下仍能保持稳定。
随机界限（泊松到达）：
- 在泊松到达过程中，本文推导了期望竞争比。
- SVF 实现了 $E[CR] \le 1 + \frac{4}{(1-\mu)(1-\rho)}$ ，其中 $\mu$ 与长度的几何分布相关， $\rho$ 为系统利用率。
- 1-bit SVF 的性能退化受“体积失真惩罚（volumetric distortion penalty）” $\epsilon$ 控制，该惩罚随分类阈值呈指数级衰减，确保了长期稳定性。

实验结果

该方法作为插件式层集成在 vLLM 中，并在 Llama-3.1-8B 和 Llama-3.1-70B 模型上使用 LMSYS-Chat 和 LongBench 工作负载进行了评估。

延迟降低：在所有基准测试中，SVF 始终实现了最低的平均延迟和尾部延迟（P95），在内存密集型场景（LongBench）中甚至优于 FCFS、SJF 以及具备完美未来长度知识的 Oracle-SJF。
吞吐量：SVF 保持了比 SJF 更高的吞吐量。1-bit SVF 实现了具有竞争力的吞吐量和延迟，其尾部延迟指标通常优于 SJF。
开销：预测开销可以忽略不计。全长预测器对端到端延迟的消耗最多为 0.06%，而 1-bit 分类器的消耗 $\le$ 0.01%。
公平性：与会导致长任务饥饿的经典贪心启发式算法不同，SVF 的几何感知贪婪性能够迅速释放受限的 KV 缓存内存，从而打破全局队头阻塞（head-of-line blocking），并提升了大型请求的公平性。

意义与主张

本文声称建立了一种具有理论依据且经过实证验证的方法，用于解决现代 LLM 部署中的内存受限调度问题。其主要意义在于：

范式转移：它将领域从传统的 1D 以时间为中心的启发式算法转向 2D 几何感知优先级排序，解决了经典调度理论与 LLM 推理机制之间的根本性不匹配。
理论进展：通过将竞争比从 48 压缩至 5 并引入新颖的证明方法，它提供了在任意及对抗性工作负载分布下均成立的通用结构化保证。
实际可行性：该调度器的“即插即用”特性，结合 1-bit 变体的极高效率，证明了严密的数学优化可以无缝集成到高性能推理引擎中，而不会带来沉重的计算负担。

作者总结道，这种几何感知方法不仅优化了系统效率，也为减少大规模推理所需的计算资源和碳足迹、实现可持续的 AI 部署提供了启示。