Online Linear Programming for Multi-Objective Routing in LLM Serving
On the map: Efficient LLM inference and serving → Serving systems and request scheduling
Abstract (arXiv)
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.
Key facts. No citing papers in the map yet (data through 14 Oct 2026). Placed in Serving systems and request scheduling, one of 12 directions in Efficient LLM inference and serving. Builds on 16 of its 27 references that are in the map. First posted on arXiv 4 Jul 2026.
Builds on
16 of 27 references.
Closest ancestors · 6
Same direction, newest first
- 2025Efficient Training-Free Online Routing for High-Volume Multi-LLM Serving2 Sep
- 2024Efficient LLM Scheduling by Learning to Rank28 Aug
- 2024Efficient Interactive LLM Serving with Proxy Model-based Sequence Length Prediction12 Apr
- 2024Taming Throughput-Latency Tradeoff in LLM Inference with Sarathi-Serve4 Mar
- 2024DistServe: Disaggregating Prefill and Decoding for Goodput-optimized Large Language Model Serving18 Jan
- 2023Response Length Perception and Sequence Scheduling: An LLM-Empowered LLM Inference Pipeline22 May
Other references · 10
- 2023Efficient Memory Management for Large Language Model Serving with PagedAttentioncited by 5,944
- 2023FlexGen: High-Throughput Generative Inference of Large Language Models with a Single GPUcited by 575
- 2022Efficiently Scaling Transformer Inferencecited by 539
- 2023LMSYS-Chat-1M: A Large-Scale Real-World LLM Conversation Datasetcited by 461
- 2024Vidur: A Large-Scale Simulation Framework For LLM Inferencecited by 117
- 2024Don't Stop Me Now: Embedding Based Scheduling for LLMscited by 35
- 2025OmniRouter: Budget and Performance Controllable Multi-LLM Routingcited by 35
- 2019Online Linear Programming: Dual Convergence, New Algorithms, and Regret Boundscited by 32
- 2020Simple and Fast Algorithm for Binary Integer and Online Linear Programmingcited by 27
- 2020Near-Optimal Primal-Dual Algorithms for Quantity-Based Network Revenue Managementcited by 9
Built on by
Not cited yet.
Similar, not cited
Close in wording, no citation either way
- 2026Drift-Aware LLM Routing with Sparse Contexts and Shared Budgets
- 2026Position: LLM Serving Needs Mathematical Optimization and Algorithmic Foundations, Not Just Heuristics
- 2026TokenRouter: Efficient Serving System for Token-Level LLM Routing
- 2026Tackling the Data-Parallel Load Balancing Bottleneck in LLM Serving: Practical Online Routing at Scale
- 2024Intelligent Router for LLM Workloads: Improving Performance Through Workload-Aware Load Balancing
- 2026Cascade: Exploiting SLO-Aware latency budget for fair and high goodput LLM inference serving
- 2026ParetoBandit: Budget-Paced Adaptive Routing for Non-Stationary LLM Serving
- 2025ProServe: Unified Multi-Priority Request Scheduling for LLM Serving