🔢 mathematics

Online Linear Programming for Multi-Objective Routing in LLM Serving

本文提出了一种基于科学的在线线性规划框架，通过出价价格控制（bid-price control）和热启动对偶更新（warm-started dual updates）来优化大语言模型（LLM）服务中的多目标路由，证明了其相比于传统启发式方法在延迟和吞吐量性能方面的优越性。

原作者： Zixi Chen, Yinyu Ye, Zijie Zhou

发布于 2026-07-07

📖 1 分钟阅读🧠 深度阅读

CC BY 4.0

原作者： Zixi Chen, Yinyu Ye, Zijie Zhou

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

想象一下你正在经营一家繁忙的高端餐厅厨房。这个厨房拥有多个并行的烹饪工作站（即 GPU），而顾客（即 AI 请求）正一个接一个地到来。

在普通的厨房里，你可能只是把下一个订单发给第一个空闲的厨师。但在这个特殊的“AI 餐厅”里，情况变得很棘手：

订单很奇特： 有些订单是快速的小吃（短文本），而有些则是极其庞大、复杂的正餐，需要很长时间来烹饪（长文本生成）。在订单开始烹饪之前，你无法确切知道它需要多长时间。
空间很紧凑： 每位厨师都有有限的台面空间（内存），并且在灶台上同时只能摆放一定数量的盘子（批处理大小/Batch Size）。如果你在一个灶台上放了太多的盘子，整个工作站就会崩溃。
顾客很挑剔： 有些顾客希望食物能“立即”送到（低延迟），而另一些人则只关心厨房是否运行得既忙碌又高效（高吞吐量）。有时，你必须做出选择：是为一名顾客提供极速服务，还是为十名顾客提供稍慢一点的服务？

旧方法的缺陷
如今大多数厨房使用简单的规则，比如“将订单发送给排队最短的厨师”或者“发送给当前空闲的厨师”。论文指出，这些规则就像是用锤子去修理手表。它们并不理解订单的“价值”或其占用空间的“成本”。它们无法轻松地平衡速度需求与保持厨房平稳运行之间的关系。

新解决方案：“智能价格标签”系统
作者提出了一种通过 在线线性规划（Online Linear Programming） 概念来运行厨房的新方法。你可以把它想象成一个为每一寸台面空间和每一分钟厨师时间都贴上了“智能价格标签”的系统。

它是这样运作的，分步骤如下：

1. 影子价格（“机会成本”）

想象一下，每位厨师灶台上的每个位置都附带了一个隐藏的“价格标签”。这不是金钱，而是 影子价格（Shadow Price）。

如果一个灶台非常拥挤且即将耗尽空间，价格标签就会上升。这是在告诉调度器：“小心！现在使用这个空间，可能会意味着我们稍后无法烹饪大型的重要餐点。”
如果一个灶台是空的，价格标签就很低。现在使用它很便宜。

2. 决策（收益 vs. 成本）

当一个新的客户订单到达时，调度器不仅仅是查看谁是空闲的。它会进行一次快速的数学检查：

收益： 这位顾客会多么满意？（他们能快速拿到食物吗？这是否有助于提高厨房的整体效率？）
成本： 这个订单所需的空间之“影子价格”总和是多少？

规则： 如果收益高于成本，调度器就会说：“好的，开始烹饪！”如果成本太高（现在的灶台太贵了），调度器可能会说：“在队列中等待”，或者将其发送到另一个更便宜的灶台。

3. 实时学习（“热启动”）

厨房是混乱的。随着新订单的进入和旧订单的完成，“价格标签”每秒钟都在变化。

旧方法会尝试在每个新订单到达时都重新计算完美的计划。这太慢了（就像在食物烧焦之前试图解开一个巨大的拼图）。
这种新方法使用 智能更新。它记得上一秒的价格，并根据刚刚发生的情况进行微小的、快速的调整（即“热启动”）。这就像一位了解厨房整体节奏的厨师，只需根据新订单稍微调整自己的动作，而不是每次烹饪时都重新学习如何做菜。

4. 多目标菜单

最棒的部分是，厨房经理可以瞬间改变目标的“菜单”，而无需重建厨房。

需要速度？ 经理调高“等待时间”的价格。调度器将优先保证食物快速送出，即使这会导致厨房变得拥挤。
需要效率？ 经理调高“浪费空间”的价格。调度器会将订单紧凑地打包在一起以完成更多工作，即使这会让某些顾客等待稍久一点。
需要解决最慢的客户问题？ 经理可以指示系统专门保护“尾部”（最后 1% 的订单），确保没有人被落下。

结果

作者在模拟一个大规模 AI 厨房的过程中测试了这个“智能价格标签”系统。他们将其与旧有的“最短排队”规则进行了对比。

结果： 新系统在权衡取舍方面表现得更好。它可以根据经理的需求，在实现更快或更高效之间进行切换，且不会破坏系统。
大局观： 论文声称，使用这种基于“科学”的数学方法优于目前大多数 AI 系统中使用的“试错法”启发式算法。它赋予了系统一个能够理解资源真实成本的“大脑”，而不仅仅是遵循一条简单的规则。

简而言之： 这个系统不再盲目地将订单发送给第一个可用的厨师，而是像一位聪明的经理，深知每一秒的时间和每一寸的台面空间价值几何，从而确保无论在多么疯狂的忙碌时刻，厨房都能完美运转。

技术摘要：面向 LLM 服务中多目标路由的在线线性规划

1. 问题陈述

本文探讨了大型语言模型（LLM）服务系统中在线请求路由的挑战。在这些系统中，传入的请求必须在严格的约束条件下分发到并行解码工作负载（workers）中：

时间耦合约束： 请求在整个解码持续期间持续消耗资源（批处理槽位和 KV-cache 内存）。在时间 $t$ 被接收的请求会一直占用容量直到其完成，这产生了一个复杂的、随时间变化的资源分配问题。
多目标权衡： 系统必须平衡相互竞争的服务水平目标（SLO），包括吞吐量、端到端延迟（EEL）、首字时间（TTFT）以及尾部延迟（例如第 99 百分位数）。这些目标通常是冲突的；例如，通过激进批处理来最大化吞吐量的做法往往会降低延迟。
现有启发式方法的局限性： 现有的生产系统（如 vLLM）和模拟器（如 Vidur）依赖于诸如轮询（Round-Robin）、最短队列优先（LOR）或 $d$ 次方选择（Power-of- $d$ ）等启发式方法。这些方法缺乏明确的优化目标，对 SLO 权衡的控制能力有限，且未能考虑到 LLM 解码长度的异构性和不确定性。

2. 方法论

作者提出了一个将 LLM 路由建模为**在线线性规划（OLP）**问题的框架，利用运筹学技术推导出一种计算高效的控制策略。

A. 数学建模

模型： 系统被建模为具有并行解码设备的离散时间时界。请求按顺序到达，具有已知的 Prefill 足迹和预测的（但可能不准确的）解码长度。
约束： 该公式为每个设备在每个时间步强制执行两个关键约束：
1. 批处理大小： 最大活跃请求数（ $B$ ）。
2. KV-Cache 容量： 活跃请求的最大内存预算（ $M$ ）。
目标函数： 作者为每个路由决策 $(j, g, k)$ $(j, g, k)$ （将请求 $j$ $j$ 分配给设备 $g$ $g$ 在时间 $k$ $k$ ）定义了一个线性奖励函数。该奖励是以下各项的加权和：
- 吞吐量（处理的 token 数）。
- 负延迟（最小化 EEL 和 TTFT）。
- 每秒查询数（QPS）。
- 尾部指标（通过用于满足特定延迟边界的指示函数进行建模）。
- 核心洞察： 聚合指标（如尾部延迟）被分解为单个请求的激励，从而允许它们在保持线性框架内进行优化。

B. 算法设计：出价控制（Bid-Price Control）

求解完整的 OLP 在每毫秒执行一次在计算上是不可行的。相反，作者基于 LP 对偶理论推导出了一个出价控制策略：

对偶变量（影子价格）： 对偶变量 $p_i$ 代表了资源的“影子价格”或机会成本（即特定时间和设备的批处理槽位和 KV-cache 的成本）。高影子价格表示预期的拥塞。
决策规则： 如果一个请求的 SLO 加权收益超过其推算的资源成本（计算为资源使用向量与当前影子价格的点积），则准许该请求进入。
在线学习（SAA）： 为了处理到达过程和预测的不确定性，影子价格使用**样本平均近似（SAA）**方法进行在线学习。通过观察到的历史动作来最小化对偶目标。
高效更新： 为了满足毫秒级的决策延迟，作者采用了热启动、投影小批量梯度下降。算法不是从头开始求解对偶问题，而是根据一小批历史数据增量地更新价格向量。这确保了可预测的运行时间（在 CPU 上每周期 1–2 毫秒）。

3. 核心贡献

多目标优化框架： 首个将 LLM 路由建模为具有显式时间耦合批处理和 KV-cache 约束的 OLP 框架。它将聚合 SLO（包括尾部延迟）分解为适用于在线优化的单请求奖励。
高效的出价算法： 一种计算可行的策略，能够在线追踪不断演变的对偶影子价格，而无需在每一步都求解完整的 LP，从而满足 LLM 服务严格的延迟要求。
可解释的权衡控制： 该框架为操作员提供了透明的“旋钮”（目标权重），使其能够系统地沿着帕累托前沿移动性能。影子价格也可作为诊断工具，用以识别当前的瓶颈是批处理槽位还是 KV-cache。

4. 实验结果

作者将他们的路由器集成到 Vidur 模拟器中，并在各种工作负载（真实的 LMSYS-Chat-1M 数据和合成的 P/D 比率）下将其与标准基准（轮询、LOR、随机、Power-of-2）进行了对比评估。

性能提升： 所提方法在多种 SLO 机制下均表现出优于基准方法的显著改进。
- 在存在噪声预测（20% 误差）的场景中，该算法相比轮询实现了 45.75% 的平均 EEL 降低和 42.49% 的 P95 EEL 降低。
- 它在尾部延迟指标（P99 EEL 和 TTFT）方面显著优于启发式方法。
鲁棒性： 由于在线价格更新能够适应估计误差，该策略即使在解码长度预测不准确的情况下依然有效。
适应性： 在非平稳工作负载（突发负载激增）中，该路由器通过使用滚动窗口机制进行历史更新，能够快速适应并保持卓越性能。
权重调节： 实验证实，通过调整目标权重，操作员可以以可预测的结果来优先考虑特定指标（例如，最小化平均延迟 vs. 严格控制尾部延迟）。

5. 重要性与声明

论文声称，基于科学的优化方法在 LLM 服务中优于基于启发式的路由。

桥接领域： 它在运筹学社区（在线资源分配、出价控制）与 LLM 系统社区之间建立了原则性的桥梁。
系统设计洞察： 该框架揭示了结构性见解，例如使用影子价格来诊断资源瓶颈（批处理 vs. 内存），以及在过载期间实现 SLO 感知的准入控制。
实际应用性： 虽然提到与生产环境的完整集成仍是未来的工作，但结果表明，基于优化的路由在毫秒级规模上是可行的，并为系统性的策略设计提供了基础。

作者对于立即投入生产部署保持谨慎，承认了在集成到服务端引擎（如 vLLM）、处理抢占以及分布式设置下的协调等方面存在的挑战。然而，他们断言该框架为研究优化理论与机器学习系统之间的交叉领域提供了必要的基石。