用在线线性规划优化大模型服务中的多目标路由，提升延迟与吞吐平衡。
Online Linear Programming for Multi-Objective Routing in LLM Serving
- 将路由问题建模为带可解释奖励的在线线性规划，支持多目标优化。
- 在多个SLO条件下，端到端延迟降低23%，尾部延迟改善41%。
- 适合追求低延迟、高吞吐的大模型服务系统设计者使用。
我们研究大语言模型服务中的在线路由问题，请求按序到达，需在严格的批处理大小和KV缓存约束下分配给并行解码工作节点。与普遍使用的不关联显式服务等级目标（SLO）且难以控制延迟-吞吐权衡的启发式路由不同，我们提出一种多目标优化框架，将路由建模为带有可解释决策奖励的在线线性规划。采用基于该规划的高效投标价格控制策略：当请求的SLO加权收益超过其影子价格时即接纳。为满足毫秒级决策要求，我们设计了预热启动的投影一阶更新机制，可在线跟踪变化的对偶影子价格，具备可预测的运行时间。将路由器集成至Vidur仿真器，在多种SLO配置下显著优于标准基线，涵盖端到端延迟、首次令牌时间、吞吐量及尾部性能。核心结论：基于科学建模的方法优于启发式方法。
原文摘要 · Abstract (English)
We study the online routing problem in large language model serving, where requests arrive sequentially and must be dispatched to parallel decode workers under tight batch-size and KV-cache constraints. Unlike widely used routing heuristics that are not tied to explicit service-level objectives (SLOs) and offer limited control over latency-throughput trade-offs, we introduce a multi-objective optimization framework that formulates routing as an online linear programming with interpretable decision rewards. We apply an efficient bid-price control policy based on the online linear programming that admits requests when their SLO-weighted benefit exceeds their shadow prices. To meet millisecond decision requirements, we develop a warm-started, projected first-order updates that track the evolving dual shadow prices online with predictable runtime. We integrate our router into the Vidur simulator and demonstrate substantial improvements over standard baselines across multiple SLO regimes, including end-to-end latency, time-to-first-token, throughput, and tail performance. A big picture from our result: a science-based approach outperforms others based on heuristics.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。