Online Linear Programming for LLM Serving: Bid-Price Router

Zixi Chen, Yinyu Ye and Zijie Zhou submitted a paper titled "Online Linear Programming for Multi-Objective Routing in LLM Serving" to arXiv on 4 Jul 2026 (arXiv:2607.03948). The paper formulates request routing in LLM serving as an online linear program and implements a bid-price control policy that admits requests when their SLO-weighted benefit exceeds shadow prices.

How does the online linear programming router work?

The router formulates routing as an online linear program, using interpretable decision rewards and dual shadow prices to accept or reject requests. Requests arrive sequentially and must be dispatched to parallel decode workers under tight batch-size and KV-cache constraints, so the authors apply a bid-price control policy: admit a request when its SLO-weighted benefit exceeds the corresponding shadow price. To meet millisecond decision requirements the system uses warm-started, projected first-order updates that track evolving dual shadow prices online with predictable runtime.

The paper positions this method against widely used routing heuristics, arguing those heuristics are not tied to explicit service-level objectives and give limited control over latency-throughput trade-offs. By contrast, the online linear programming framework makes objectives explicit and produces shadow prices that guide per-request admission decisions.

How did it perform in the Vidur simulator?

The authors integrated their router into the Vidur simulator and report substantial improvements over standard baselines across multiple SLO regimes. The evaluation shows gains in end-to-end latency, time-to-first-token, throughput, and tail performance when compared to standard heuristic baselines. The paper emphasizes that the warm-started, projected first-order dual updates meet the paper’s millisecond decision requirement while tracking evolving constraints and benefits.

The experimental setup centers on sequential arrivals, parallel decode workers, and hard constraints such as batch-size limits and KV-cache usage; that context frames why a lightweight online dual update is necessary for runtime feasibility. The arXiv abstract summarizes the empirical result as a science-based approach outperforming heuristic approaches across these SLOs.

Why it matters

Routing decisions are the gating factor for latency and throughput in large-scale LLM serving, because requests must be batched and served from limited KV-cache resources across parallel decoders. The paper supplies a transparent, SLO-linked decision mechanism: shadow prices convert resource scarcity and SLO weights into admission thresholds. That makes trade-offs explicit rather than hidden inside heuristics, and gives operators a direct lever to prioritize end-to-end latency, time-to-first-token, throughput, or tail metrics depending on objectives.

Operationally, the addition of warm-started projected first-order updates addresses a real constraint: decisions must happen within milliseconds. The paper ties an optimization formulation to a practical update rule and an implementation in the Vidur simulator, which strengthens the claim that the approach is viable at runtime rather than purely theoretical.

What to watch

Look for code, datasets, or follow-up experiments linked from the arXiv entry that reproduce the Vidur simulator results and clarify the baselines and workloads used. Also watch for extensions that apply the same online LP plus bid-price control to different caching regimes, decoder architectures, or real production traces.

Paper reference and metadata: arXiv:2607.03948, submitted 4 Jul 2026, authors Zixi Chen, Yinyu Ye, Zijie Zhou. The paper’s abstract lists primary claimed gains in end-to-end latency, time-to-first-token, throughput, and tail performance when the router is integrated into Vidur.