在线线性规划优化大模型服务多目标路由
速览
该研究针对大语言模型服务中请求顺序到达的路由问题，现有启发式方法难以平衡延迟与吞吐量。作者提出多目标优化框架，将路由建模为在线线性规划，并采用基于SLO加权收益与影子价格的bid-price控制策略。通过暖启动投影一阶更新实时追踪对偶影子价格，满足毫秒级决策。在Vidur模拟器中，该方法在多SLO指标（端到端延迟、首token时间、吞吐量、尾延迟）上均显著优于标准基线，验证了科学方法优于经验启发式。
AI 深度解读
背景
随着大语言模型（LLM）服务的广泛部署，请求以在线流的形式到达，系统需要将这些请求实时路由到多个并行的解码工作节点（decode workers）上进行处理。实际部署中面临两个关键约束：批处理大小（batch-size）上限和 KV-cache 容量限制。传统的路由策略多基于启发式规则（heuristics），例如轮询、最小负载等。这些启发式方法虽然简单高效，但并未显式地与服务水平目标（SLO）挂钩，因此难以在延迟和吞吐量之间进行可控的权衡。例如，某些请求可能需要更低的时延（如交互式应用），而另一些请求则更关注吞吐量（如批量离线处理）。现有方法无法根据这些差异化需求动态调整路由决策。
核心内容
该论文将在线路由问题形式化为一个多目标优化框架，并引入可解释的决策奖励（interpretable decision rewards），将路由建模为在线线性规划（Online Linear Programming, OLP）。具体而言，每个到来的请求都有一个 SLO 加权收益（SLO-weighted benefit），表示接受该请求能为系统带来的效用。系统需要决定是否接受该请求并路由到哪个 worker，同时满足 worker 的批处理大小和 KV-cache 容量约束。
核心算法是一种基于 bid-price control 的在线策略：请求的 SLO 加权收益若超过其影子价格（shadow price），则接受该请求；否则拒绝。影子价格反映了在当前系统状态下接纳该请求的机会成本，通过在线求解对偶问题动态更新。为了满足毫秒级的决策时间要求，作者提出了一种热启动的投影一阶更新方法（warm-started, projected first-order updates），能够在线追踪不断变化的对偶影子价格，并且计算时间可预测（predictable runtime）。
作者将该路由模块集成到 Vidur 模拟器中，并在多种 SLO 场景下与标准基线进行了对比实验。标准基线包括常见的启发式路由策略（如 Round Robin、Least Load 等）。实验结果表明，该科学驱动的路由方法在端到端延迟（end-to-end latency）、首词延迟（time-to-first-token）、吞吐量（throughput）以及尾延迟（tail performance）等指标上均有显著提升。论文总结了一个宏观结论：基于科学（即优化理论）的方法优于基于启发式的方法。
关键要点
- 问题定义：LLM 服务中的在线路由问题，请求顺序到达，需满足批处理和 KV-cache 资源约束。
- 方法创新：将路由建模为多目标在线线性规划，引入 SLO 加权收益和影子价格，采用 bid-price control 策略。
- 算法实现：提出热启动的投影一阶更新方法，实现在线对偶变量追踪，满足毫秒级决策时间要求。
- 实验验证：集成至 Vidur 模拟器，在多个 SLO 场景下对比基线，显著改善延迟、首词时间、吞吐量和尾性能。
- 核心结论：基于科学优化的路由方法（显式建模目标和约束）普遍优于依赖启发式的传统方法。
意义与影响
这项研究为 LLM 服务的在线路由提供了理论驱动的全新范式。传统启发式路由方法虽然简单，但无法适应动态负载和差异化 SLO 需求。论文首次将在线线性规划与 bid-price 控制引入 LLM 推理系统的调度层，实现了可解释、可调优、可泛化的路由机制。其意义在于：
- 可解释性：通过影子价格和 SLO 收益，决策过程透明，便于运维人员理解系统行为。
- 可控性：显式支持多目标（延迟、吞吐量、尾延迟等）权衡，可根据业务需求调整奖励权重。
- 实用性：提出的热启动一阶更新方法兼顾精度和速度，满足实际部署中毫秒级响应的要求。
- 可迁移性：该框架不仅适用于路由，还可推广到 LLM 服务中其他资源分配问题（如加载模型副本、缓存管理）。
论文的结论“科学方法优于启发式方法”虽不令人意外，但通过严格的实验验证，为 LLM 系统设计者提供了坚实的理论依据和实用工具。未来工作可进一步扩展至多模态服务、混合精度推理等场景。