LLM服务中多目标路由的在线线性规划

# 面向大模型服务中多目标路由的在线线性规划 来源：https://arxiv.org/html/2607.03948 ###### 摘要 本文研究大语言模型服务中的在线路由问题，请求顺序到达，必须在严格的批处理大小和KV缓存约束下分发到并行的解码工作节点。与广泛使用的、未与明确服务级别目标（SLO）挂钩且对延迟–吞吐量权衡控制有限的路由启发式方法不同，我们引入了一个多目标优化框架，将路由问题形式化为具有可解释决策奖励的在线线性规划。我们基于在线线性规划应用了一种高效的出价控制策略，当请求的SLO加权收益超过其影子价格时，就接纳该请求。为了满足毫秒级决策要求，我们开发了一种热启动的投影一阶更新方法，能够在线追踪演化的对偶影子价格，且运行时间可预测。我们将该路由器集成到 Vidur 模拟器中，并在多个 SLO 场景下展示了对标准基线的显著改进，包括端到端延迟、首字符生成时间、吞吐量和尾部性能。我们的结果揭示了一个大图景：基于科学的方法优于基于启发式的其他方法。  
LLM Serving, Online Linear Programming  

## 1 引言  
近年来，大语言模型（LLM）服务的需求急剧增长，每天处理数十亿条请求（Roth，2025 (https://arxiv.org/html/2607.03948#bib.bib21)）。随着这一需求的持续增长，优化 LLM 服务系统的效率已成为一个日益关键的挑战（Kwon et al., 2023 (https://arxiv.org/html/2607.03948#bib.bib9); Pope et al., 2023 (https://arxiv.org/html/2607.03948#bib.bib24); Sheng et al., 2023 (https://arxiv.org/html/2607.03948#bib.bib25); Agrawal et al., 2024b (https://arxiv.org/html/2607.03948#bib.bib23)）。LLM 服务对每个请求包含两个关键阶段：(i) 预填充阶段，生成输入的键值对（KV），以及 (ii) 解码阶段，模型自回归地生成输出令牌。由于请求量巨大且计算资源有限，无法同时处理所有请求。本文着重优化*路由器*，它将传入的请求分派给并行的计算工作节点（Jain et al., 2024 (https://arxiv.org/html/2607.03948#bib.bib30); Wu and Silwal, 2025 (https://arxiv.org/html/2607.03948#bib.bib28); Mei et al., 2025 (https://arxiv.org/html/2607.03948#bib.bib29)），并将该控制问题归结为一个通用的在线资源分配任务，包含时变耦合约束，专门针对解码侧的 LLM 服务。

优化路由器需要明确系统应优化*什么*性能，但实际的 LLM 服务在异构的服务级别目标（SLO）下运行。例如，实时语音翻译和交互式代理优先考虑响应速度，通常用首字符生成时间来衡量；而聊天机器人则强调端到端延迟，因为用户关心收到完整响应的时间；同时，系统运维人员也追踪吞吐量，作为容量和成本效率的代理指标。这些目标本质上相互冲突：提高吞吐量通常需要更大或更激进的批处理以及更高的设备利用率，这会增加排队延迟并加剧延迟；而优先考虑低延迟则往往迫使使用更小的批处理或保留容量，从而降低整体吞吐量和利用率。由于不同产品需要不同的指标组合和权衡，服务栈经常需要针对每次部署重新调整甚至重新设计路由启发式方法，这促使我们构建一个通用的多目标控制框架，能够通过调整目标权重灵活地适应路由行为，而不是改变路由器的结构。

许多生产级服务栈（例如 vLLM（Kwon et al., 2023 (https://arxiv.org/html/2607.03948#bib.bib9)））和模拟器（例如 Vidur（Agrawal et al., 2024a (https://arxiv.org/html/2607.03948#bib.bib22)））采用简单的路由启发式方法，这些方法可分为两大类：*贪婪负载均衡*规则和*随机化*规则。代表性的贪婪策略包括最短队列连接和 dd 次随机选择。虽然在经典的并行服务器环境中有效，但这些规则是为作业大小已知或同质的场景设计的。然而，在 LLM 服务中，相关工作负载由异构且不确定的解码长度驱动：具有相同请求数量的两个队列可能对应着截然不同的剩余工作量。最近的工作探索了解码长度预测（Fu et al., 2024 (https://arxiv.org/html/2607.03948#bib.bib12); Zheng et al., 2023b (https://arxiv.org/html/2607.03948#bib.bib10); Qiu et al., 2024 (https://arxiv.org/html/2607.03948#bib.bib11); Shahout et al., 2024 (https://arxiv.org/html/2607.03948#bib.bib14)）、工作负载感知调度（Jain et al., 2024 (https://arxiv.org/html/2607.03948#bib.bib30)）和多 LLM 路由（Wu and Silwal, 2025 (https://arxiv.org/html/2607.03948#bib.bib28); Mei et al., 2025 (https://arxiv.org/html/2607.03948#bib.bib29)），但大多数已部署的系统仍然依赖启发式方法，这些方法对 SLO 权衡的控制有限。随机化基线如轮询和均匀路由避免了依赖不完美的工作量估计，但它们忽略了系统的瞬时状态，无法适应拥塞。更根本的是，这两类方法都不是从明确的优化目标中推导出来的，在竞争性 SLO 之间的权衡方面提供有限且不透明的控制——而这正是多目标服务所需的灵活性。

在不确定性下将请求分派到容量受限资源的挑战是运筹学中的一个经典问题，在在线线性规划（LP）（Agrawal et al., 2014 (https://arxiv.org/html/2607.03948#bib.bib20); Li et al., 2020 (https://arxiv.org/html/2607.03948#bib.bib34); Li and Ye, 2022 (https://arxiv.org/html/2607.03948#bib.bib17)）和收益管理中的出价控制（Talluri and Van Ryzin, 1998 (https://arxiv.org/html/2607.03948#bib.bib15); Akan and Ata, 2009 (https://arxiv.org/html/2607.03948#bib.bib16)）框架下得到了广泛研究。该领域的一个重要见解是，良好的在线决策应该在*服务请求的即时收益*与*消耗可能被未来到达请求需要的稀缺容量的机会成本*之间取得平衡。LP（Luenberger et al., 1984 (https://arxiv.org/html/2607.03948#bib.bib31)）对偶性提供了通过*影子价格*量化这些机会成本的原则性方法。在 LLM 服务中，稀缺资源是每个设备上未来时间步的批处理槽位和 KV 缓存内存——这些资源是*时变耦合*的，因为现在接纳的请求在其整个解码持续时间内都会占用容量。除了约束条件之外，*目标*本身也需要精心设计：诸如尾部延迟之类的聚合 SLO 是统计属性，不能直接分解为每个请求的奖励。我们工作的一个关键建模贡献是设计了一种奖励结构，将这些聚合指标转换为每请求激励，同时确保调度通常是有益的。这种时变耦合约束与 SLO 可分解目标的组合促使我们采用在线 LP 框架。据我们所知，之前没有工作为 LLM 路由提供一个多目标优化框架，该框架能够 (i) 明确建模自回归解码固有的时变耦合 KV 缓存和批处理大小约束，(ii) 将聚合 SLO（包括尾部延迟）分解为适用于在线优化的每请求奖励，以及 (iii) 推导出基于 LP 对偶性的计算高效策略。我们的工作通过将运筹学方法引入 LLM 服务来填补这一空白。具体来说，我们做出以下贡献：

1. 1. 多目标优化框架。我们将 LLM 路由形式化为一个具有时变耦合批处理和 KV 缓存约束的在线线性规划。目标函数通过可解释的权重明确纳入多个 SLO——吞吐量、端到端延迟、首字符生成时间和尾部延迟——运维人员可以调整这些权重以匹配产品需求。
2. 2. 高效出价控制算法。我们推导出一种出价策略，其中每个路由决策将请求的 SLO 加权收益与其影子价格成本进行比较。为了满足毫秒级决策延迟要求，我们开发了热启动的投影梯度更新方法，能够在线追踪演化的对偶价格，而无需在每一步求解 LP。
3. 3. 可解释的权衡控制。通过 LP 形式化，运维人员可以获得对 SLO 权衡的透明控制：调整目标权重会在帕累托前沿上系统地改变性能，而影子价格则揭示了不同工作负载下哪些资源（批处理槽位 vs. KV 缓存）是瓶颈。

我们通过使用 Vidur 模拟器（Agrawal et al., 2024a (https://arxiv.org/html/2607.03948#bib.bib22)）进行广泛的仿真实验来验证我们的框架，展示了在多个 SLO 场景下相对于标准路由启发式方法的显著改进。虽然完全集成到生产服务系统中仍是未来的工作，但我们的结果确立了基于优化的路由的潜力，并为系统社区提供了一个原则性的基础。我们还讨论了从优化视角审视 LLM 路由所得到的结构洞见——这些洞见即使超越我们的具体算法，也可能指导未来的系统设计。

## 2 数学模型  
本节中，我们给出一个在*预填充/解码（PD）分离*（Zhong et al., 2024 (https://arxiv.org/html/2607.03948#bib.bib27)）和*连续批处理*下的多工作节点 LLM 服务的数学模型。关于模型和算法如何在 PD 混合场景下调整的讨论，推迟到附录 A (https://arxiv.org/html/2607.03948#A1)。  
#### 时间、设备和请求。  
我们考虑一个有限时域，由离散周期 k=1,...,T 和一个由 g∈[G] 索引的解码设备集合组成。一个周期对应设备上一个批处理解码核的一次解码迭代。请求实例 J 在时域内顺序到达。每个请求 j∈J 在其预填充阶段完成后，于时间 t_j∈{1,...,T} 到达，并具有：(i) 已知的预填充占用 s_j（例如，预填充已物化的 KV 缓存令牌槽数），以及 (ii) 未知的解码长度 o_j（完成响应所需的解码令牌数）。在实际中，o_j 可以使用已有技术进行预测（例如，(Zheng et al., 2023b (https://arxiv.org/html/2607.03948#bib.bib10); Qiu et al., 2024 (https://arxiv.org/html/2607.03948#bib.bib11); Fu et al., 2024 (https://arxiv.org/html/2607.03948#bib.bib12); Chen et al., 2024 (https://arxiv.org/html/2607.03948#bib.bib13); Shahout et al., 2024 (https://arxiv.org/html/2607.03948#bib.bib14)））；我们将预测的解码长度记作 o^_j，它可能不准确。  
#### 路由器侧缓冲。  
完成预填充后，每个请求 j 在时间 t_j 进入一个*中央路由器队列*。在每个周期 k 开始时，路由器观察每个解码设备的当前状态，并可能*释放*一部分排队请求到设备。此设计得到了最近版本 vLLM 引擎的支持，该引擎实现了路由器侧缓冲（vLLM Project, 2025 (https://arxiv.org/html/2607.03948#bib.bib36); vLLM Roadmap, 2025 (https://arxiv.org/html/2607.03948#bib.bib35)）。本文中，我们专注于一种*可启动时立即释放*的设计：路由器仅当请求能在同一周期内被接纳到该设备的活跃解码批处理中时，才将其分派给该设备。在实现中，仍然可以为每个设备维护一个短小的 FIFO 队列，但在我们的策略下，这些队列将保持较小。  
#### 路由和接纳决策。  
对于每个请求 j∈J、设备 g∈[G] 和周期 τ∈{t_j,...,T}，我们定义一个路由/接纳决策变量 x_{j,g,τ}∈[0,1]，解释为：“请求 j 在周期 τ 开始时从路由器队列中释放并接纳到设备 g”。在整数调度中，x_{j,g,τ}∈{0,1}，并且对于每个请求最多选择一个 (g,τ) 对：  
∑_{g∈[G]} ∑_{τ=t_j}^{T} x_{j,g,τ} ≤ 1, ∀ j∈J。  
#### 解码设备内的连续批处理。  
在每个解码设备内部，我们对 vLLM 使用的经典连续批处理机制进行建模（Kwon et al., 2023 (https://arxiv.org/html/2607.03948#bib.bib9)）。在每个周期，设备 g 执行一次批处理解码迭代，处理其批次中每个*活跃*请求的*一个令牌*。请求 j 需要 o_j 次这样的迭代来完成。一旦一个活跃请求完成，该设备可以在后续迭代中接纳新的请求进入批处理，从而维持一个持续更新的批次（见图 1 (https://arxiv.org/html/2607.03948#S2.F1)）。  
(图示说明)  
图 1：预填充/解码（P/D）分离与连续批处理的示意图。每个小方块代表一个令牌，颜色表示不同的请求。在解码工作节点内部，活跃请求在一个持续更新的批次中被逐令牌处理，完成的请求被新接纳的请求替换。  
#### KV 缓存内存记账。  
在解码过程中，请求 j 的 KV 缓存占用大致每解码一个令牌增加一个令牌槽。我们用核函数 m_j^{mem}(θ) 表示请求 j 在解码了 θ 个令牌后的 KV 缓存使用量：  
m_j^{mem}(θ) = { s_j + θ + 1, 0≤θ<o_j; 0, θ=o_j }。  
#### 设备容量约束。  
每个设备 g 在每个周期 k 具有有限的批处理容量 B_g（最大活跃请求数）和有限的 KV 缓存容量 C_g（最大令牌槽数）。设备 g 在周期 k 的批处理占用等于在周期 k 处于活跃状态的请求集合的基数。设备 g 在周期 k 的 KV 缓存占用等于这些活跃请求在周期 k 的累积缓存大小。这些容量约束限制了路由器可以做出的调度决策。  
#### 目标函数。  
目标函数旨在最大化加权 SLO 的净值。对于每个请求 j，我们根据其预测的解码长度分配一个奖励 r_j，该奖励反映了其对吞吐量、延迟和尾部性能的贡献。具体地，令 r_j = w_througput + w_latency * (1 / (1 + predicted_completion_time)) + w_tail * indicator(completion_time > threshold)。权重 w 由运维人员设定，以体现不同 SLO 的相对重要性。  
#### 在线 LP 形式化。  
将上述所有元素组合起来，我们得到一个在线线性规划：  
最大化 ∑_{j, g, τ} r_j * x_{j,g,τ}  
满足：  
- 每个请求最多被分配一次：∑_{g, τ} x_{j,g,τ} ≤ 1, ∀ j  
- 每个设备 g 在每个周期 k 的批处理容量：∑_{j:τ≤k<τ+o_j} x_{j,g,τ} ≤ B_g, ∀ g, k  
- 每个设备 g 在每个周期 k 的 KV 缓存容量：∑_{j:τ≤k≤τ+o_j} (s_j + (k-τ)) * x_{j,g,τ} ≤ C_g, ∀ g, k  
- x_{j,g,τ} ∈ [0,1]  
该规划在请求序列到达时逐步求解，其中 o_j 用其预测值 o^_j 代替。

## 3 在线算法与出价控制  
我们提出一个基于出价控制策略的求解算法，该策略源于 (7) 的对偶性。我们在每个决策时刻维护一个对偶价格向量 p，其维度等于约束数量。对于每个候选的分配 (j, g, τ)，我们计算其影子价格成本为 a^T p，其中 a 是请求 j 在设备 g 上从周期 τ 开始所消耗资源的系数向量。然后，如果 r_j > a^T p，则接纳该请求；否则拒绝。  
#### 对偶价格更新。  
我们使用热启动的投影随机次梯度方法迭代更新对偶价格。在每一步 k，我们从历史行为中采样一个小批量 B_k，并执行 K 次投影梯度步：  
p^(0) = p_{k-1}  
p^(s+1) = Π_{R_+^{|I|}} [ p^(s) + η_k * (1/|B_k|) * ∑_{(r,a)∈B_k} 1{ r - a^T p^(s) > 0 } * a ]  
最终输出 p_k = p^(K)。这里 Π_{R_+^{|I|}} 表示到非负象限的投影，逐元素实现为 (·)_+。这种一阶更新具有短且可预测的运行时间（由 K 和 |B_k| 控制），并且避免了重复求解 (7)。  
#### 实现细节。  
在我们的 LLM 服务实例化中，约束索引 i = (g, k, u) 产生一个结构化的价格向量，包含两个张量（批处理占用和内存），定义在 (g, k) 上。我们通过仅使用每个候选列的活跃时间槽来高效计算 a^T p。我们还应用适度的归一化，使 hinge 损失梯度在数值上保持稳定。详细信息见附录 B (https://arxiv.org/html/2607.03948#A2)。  
#### 计算开销与扩展。  
在线路由路径不需要在任何步骤求解完整的原始 LP。每个周期，对偶变量的维度为 2GT，但更新具有高度结构化的特点。每个路由步骤仅执行 K 次热启动投影梯度更新，更新基于从历史动作中采样的小批量，并且任意候选列的 a^T p 点积仅涉及该请求的*活跃*未来槽，因此每步成本与活跃候选数乘以其平均解码长度成正比，而不是完整的 GT 时域。状态本身由 O(GT) 内存概括，每步的时间复杂度为 O。(此处原文不完整，推测为 O(K * |B_k| * 平均活跃时间))