Online Linear Programming for Multi-Objective Routing in LLM Serving

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 an 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.

Every day, AI chatbots like ChatGPT and Claude answer billions of questions. Behind each conversation, a software "traffic controller" called a router decides which computer in a large data center will generate the response. Today's routers use simple rules (like sending each request to the computer with the shortest line) that work in many situations but cannot easily balance competing goals. For example, a voice assistant needs to start replying within milliseconds, while a long writing tool cares more about finishing the whole answer quickly, and operators also want to serve as many users as possible without buying more hardware. Different products need different priorities, and current routers offer no clean way to express what matters most. We borrowed an idea from operations research (the same kind of math airlines use to decide which seats to sell at which price) and turned routing into an optimization problem. Each computer's limited memory and capacity is treated as a scarce resource with a "shadow price" that rises when demand approaches the limit, and the router admits a request only when its value exceeds this price. Operators can dial in priorities by adjusting weights — favoring fast first responses, lower worst-case delays, or higher overall throughput — without rewriting the system. In simulations, our approach delivered 25–45% better latency and tail performance than standard routing rules, while making decisions in just 1–2 milliseconds. The work shows that a principled, science-based approach can replace the patchwork of hand-tuned heuristics used today, helping make AI services faster, more predictable, and more efficient at scale.