In the context of large language model (LLM) serving, we study the online routing problem where requests arrive sequentially and must be dispatched to parallel decoding workers under strict batch size and KV-cache constraints. Unlike widely used routing heuristics that are not bound by explicit service-level objectives (SLOs) and provide limited control over latency-throughput trade-offs, we introduce a multi-objective optimization framework that formulates routing as an online linear programming problem with interpretable decision rewards.
We apply an efficient bid-price control policy based on 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 update method that tracks 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. Our results indicate that a science-based approach outperforms others based on heuristics.
Blogger's Review: This paper effectively enhances routing efficiency in LLM serving by introducing online linear programming, showcasing significant advantages in multi-objective optimization. The researchers utilize interpretable decision rewards and an efficient control strategy, achieving high throughput and low latency while meeting strict SLOs, offering substantial practical application value.