🔢 mathematics

Online Linear Programming for Multi-Objective Routing in LLM Serving

This paper proposes a science-based online linear programming framework with bid-price control and warm-started dual updates to optimize multi-objective routing in LLM serving, demonstrating superior latency and throughput performance compared to traditional heuristic approaches.

Original authors: Zixi Chen, Yinyu Ye, Zijie Zhou

Published 2026-07-07

📖 5 min read🧠 Deep dive

CC BY 4.0

Original authors: Zixi Chen, Yinyu Ye, Zijie Zhou

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

Imagine you are running a busy, high-end restaurant kitchen. This kitchen has several parallel cooking stations (the GPUs), and customers (the AI requests) are arriving one by one.

In a normal kitchen, you might just send the next order to the first empty chef. But in this specific "AI restaurant," things are tricky:

The Orders are Weird: Some orders are quick appetizers (short text), while others are massive, complex meals that take a long time to cook (long text generation). You don't know exactly how long an order will take until it's already being cooked.
The Space is Tight: Each chef has a limited counter space (memory) and can only hold a certain number of plates on their stove at once (batch size). If you put too many plates on one stove, the whole station crashes.
The Customers are Picky: Some customers want their food immediately (low latency), while others just want to know the kitchen is busy and efficient (high throughput). Sometimes, you have to choose: do you serve one customer super fast, or serve ten customers a little slower?

The Problem with Old Methods
Most kitchens today use simple rules, like "send the order to the chef with the shortest line" or "send it to the chef who is currently free." The paper argues these rules are like using a hammer to fix a watch. They don't understand the value of the order or the cost of the space it takes up. They can't easily balance the need for speed against the need to keep the kitchen running smoothly.

The New Solution: The "Smart Price Tag" System
The authors propose a new way to run the kitchen using a concept called Online Linear Programming. Think of this as a "Smart Price Tag" system for every inch of counter space and every minute of a chef's time.

Here is how it works, step-by-step:

1. The Shadow Price (The "Opportunity Cost")

Imagine every spot on a chef's stove has a hidden "price tag" attached to it. This isn't money; it's a Shadow Price.

If a stove is crowded and running out of space, the price tag goes up. This tells the router: "Be careful! Using this space now might mean we can't cook a huge, important meal later."
If a stove is empty, the price tag is low. It's cheap to use right now.

2. The Decision (Benefit vs. Cost)

When a new customer order arrives, the router doesn't just look at who is free. It does a quick math check:

The Benefit: How happy will this customer be? (Will they get their food fast? Will it help the kitchen's overall efficiency?)
The Cost: What is the sum of the "Shadow Prices" of the space this order needs?

The Rule: If the Benefit is higher than the Cost, the router says, "Yes, cook this!" If the Cost is too high (the stove is too expensive right now), the router might say, "Wait in line," or send it to a different, cheaper stove.

3. Learning on the Fly (The "Warm Start")

The kitchen is chaotic. The "price tags" change every second as new orders come in and old ones finish.

Old methods would try to recalculate the perfect plan from scratch every time a new order arrives. That takes too long (like trying to solve a giant puzzle while the food burns).
This new method uses a Smart Update. It remembers the prices from the last second and makes a tiny, quick adjustment (a "warm start") based on what just happened. It's like a chef who knows the general rhythm of the kitchen and just tweaks their movements slightly for the new order, rather than relearning how to cook every time.

4. The Multi-Goal Menu

The best part is that the kitchen manager can change the "menu" of goals instantly without rebuilding the kitchen.

Need speed? The manager turns up the "price" of waiting time. The router will prioritize getting food out fast, even if the kitchen gets a bit crowded.
Need efficiency? The manager turns up the "price" of wasted space. The router will pack orders tightly to get more done, even if some customers wait a tiny bit longer.
Need to fix the slowest customers? The manager can tell the system to specifically protect the "tail" (the slowest 1% of orders) so no one gets left behind.

The Results

The authors tested this "Smart Price Tag" system in a simulation of a massive AI kitchen. They compared it to the old "shortest line" rules.

The Result: The new system was much better at balancing the trade-offs. It could make the kitchen faster or more efficient depending on what the manager wanted, without breaking the system.
The Big Picture: The paper claims that using this "science-based" math approach is superior to the "guess-and-check" heuristics currently used in most AI systems. It gives the system a brain that understands the true cost of resources, rather than just following a simple rule.

In short: Instead of blindly sending orders to the first available chef, this system acts like a smart manager who knows exactly how much every second of time and every inch of counter space is worth, ensuring the kitchen runs perfectly no matter how crazy the rush gets.

Technical Summary: Online Linear Programming for Multi-Objective Routing in LLM Serving

1. Problem Statement

The paper addresses the challenge of online request routing in Large Language Model (LLM) serving systems. In these systems, incoming requests must be dispatched to parallel decode workers under strict constraints:

Time-Coupled Constraints: Requests consume resources (batch slots and KV-cache memory) continuously over their entire decode duration. A request admitted at time $t$ occupies capacity until it completes, creating a complex, time-dependent resource allocation problem.
Multi-Objective Trade-offs: Systems must balance competing Service-Level Objectives (SLOs), including throughput, end-to-end latency (EEL), time-to-first-token (TTFT), and tail latency (e.g., 99th percentile). These objectives are often in tension; for instance, maximizing throughput via aggressive batching often degrades latency.
Limitations of Current Heuristics: Existing production systems (e.g., vLLM) and simulators (e.g., Vidur) rely on heuristics like Round-Robin, Join-Shortest-Queue (LOR), or Power-of- $d$ choices. These methods lack explicit optimization objectives, offer limited control over SLO trade-offs, and do not account for the heterogeneous and uncertain nature of LLM decode lengths.

2. Methodology

The authors propose a framework that formulates LLM routing as an Online Linear Programming (OLP) problem, leveraging operations research techniques to derive a computationally efficient control policy.

A. Mathematical Formulation

Model: The system is modeled over a discrete time horizon with parallel decode devices. Requests arrive sequentially with known prefill footprints and predicted (but potentially inaccurate) decode lengths.
Constraints: The formulation enforces two critical constraints per device per time step:
1. Batch Size: A maximum number of active requests ( $B$ ).
2. KV-Cache Capacity: A maximum memory budget ( $M$ ) for active requests.
Objective Function: The authors define a linear reward function for each routing decision $(j, g, k)$ $(j, g, k)$ (assigning request $j$ $j$ to device $g$ $g$ at time $k$ $k$ ). This reward is a weighted sum of:
- Throughput (tokens processed).
- Negative latency (minimizing EEL and TTFT).
- Queries Per Second (QPS).
- Tail metrics (modeled via indicator rewards for requests meeting specific latency bounds).
- Key Insight: Aggregate metrics like tail latency are decomposed into per-request incentives using indicator functions, allowing them to be optimized within a linear framework.

B. Algorithm Design: Bid-Price Control

Solving the full OLP at every millisecond is computationally infeasible. Instead, the authors derive a Bid-Price Control policy based on LP duality:

Dual Variables (Shadow Prices): The dual variables $p_i$ represent the "shadow price" or opportunity cost of resources (batch slots and KV-cache) at specific times and devices. High shadow prices indicate anticipated congestion.
Decision Rule: A request is admitted if its SLO-weighted benefit exceeds its imputed resource cost (calculated as the dot product of the resource usage vector and the current shadow prices).
Online Learning (SAA): To handle the stochastic nature of arrivals and predictions, the shadow prices are learned online using a Sample-Average Approximation (SAA) approach. The dual objective is minimized over a history of observed actions.
Efficient Updates: To meet millisecond decision latencies, the authors employ warm-started, projected mini-batch gradient descent. Instead of solving the dual problem from scratch, the algorithm updates the price vector incrementally based on a small batch of historical data. This ensures predictable runtime (1–2ms per period on a CPU).

3. Key Contributions

Multi-Objective Optimization Framework: The first framework to formulate LLM routing as an OLP with explicit, time-coupled batch and KV-cache constraints. It decomposes aggregate SLOs (including tail latency) into per-request rewards suitable for online optimization.
Efficient Bid-Price Algorithm: A computationally tractable policy that tracks evolving dual shadow prices online without solving a full LP at each step, meeting the strict latency requirements of LLM serving.
Interpretable Trade-off Control: The framework provides operators with transparent "knobs" (objective weights) to systematically shift performance along the Pareto frontier. Shadow prices also serve as diagnostic tools to identify whether batch slots or KV-cache are the current bottlenecks.

4. Experimental Results

The authors integrated their router into the Vidur simulator and evaluated it against standard baselines (Round-Robin, LOR, Random, Power-of-2) under various workloads (real-world LMSYS-Chat-1M data and synthetic P/D ratios).

Performance Gains: The proposed method demonstrated substantial improvements over baselines across multiple SLO regimes.
- In noisy prediction scenarios (20% error), the algorithm achieved a 45.75% reduction in average EEL and 42.49% reduction in P95 EEL compared to Round-Robin.
- It significantly outperformed heuristics in tail latency metrics (P99 EEL and TTFT).
Robustness: The policy remained effective even with imperfect decode-length predictions, as the online price updates adapt to estimation errors.
Adaptability: In non-stationary workloads (sudden load spikes), the router adapted quickly using a rolling-window mechanism for history updates, maintaining superior performance.
Weight Tuning: Experiments confirmed that adjusting objective weights allows operators to prioritize specific metrics (e.g., minimizing average latency vs. strictly controlling tail latency) with predictable outcomes.

5. Significance and Claims

The paper claims that a science-based optimization approach outperforms heuristic-based routing in LLM serving.

Bridging Communities: It establishes a principled bridge between the operations research community (online resource allocation, bid-price control) and the LLM systems community.
System Design Insights: The framework reveals structural insights, such as using shadow prices to diagnose resource bottlenecks (batch vs. memory) and enabling SLO-aware admission control during overload.
Practical Applicability: While full production integration is noted as future work, the results demonstrate that optimization-based routing is feasible at millisecond scales and provides a foundation for systematic policy design rather than ad-hoc tuning.

The authors remain modest regarding immediate production deployment, acknowledging challenges like integration with serving engines (e.g., vLLM), handling preemption, and coordination in distributed settings. However, they assert that the framework provides a necessary foundation for future research at the intersection of operations research and machine learning systems.