Research map / Large language models / Reasoning and chain of thought

Online Linear Programming for Multi-Objective Routing in LLM Serving

ICML 2026 · Large language models › Reasoning and chain of thought · approach: Efficient LLM serving · 0 citations (OpenAlex)

Read the paperCheck your idea against 108,967 papers

AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.

Formulates LLM request routing across decode workers as an online linear program with time-coupled batch and KV-cache constraints, and uses bid-price control with warm-started projected subgradient dual price updates, evaluated in the Vidur simulator.

Problem

Routing requests to parallel decode workers under batch-size and KV-cache constraints while balancing multiple SLOs (throughput, EEL, TTFT, tail latency); existing heuristics (round-robin, LOR, power-of-2, random) are not derived from explicit objectives and offer limited trade-off control.

Approach

Model routing as an online LP with time-coupled per-device, per-period batch and memory constraints and a weighted multi-SLO reward decomposed per request; compute bid prices from the dual via SAA, updated online by warm-started projected subgradient steps instead of solving an LP each step, then admit highest-margin actions greedily.

Key results

• With noisy decode-length prediction (20%), the proposed router improves average EEL by 45.75%, P95 EEL by 42.49%, and P99 EEL by 25.85% over Round Robin, versus under 7% for LOR and Power-of-2.
• Under a non-stationary rate shift (0.4 to 0.6), the router achieves 44.81% average EEL improvement and 1.93% throughput gain over Round Robin, versus 1.48% for LOR.
• Per-step routing computation takes about 1-2 ms on an Intel i9-13980HX CPU, compared with a 10-30 ms A100 decode iteration (claimed).

Surprising findings

• Throughput gains over Round Robin are small (under 2%) for all methods, while latency gains are large.

Limitations

• Validated only in the Vidur simulator; no real serving-engine deployment, and no GPU experiments.
• Assumes homogeneous request priorities and does not model fairness across users or classes.
• Ignores preemption and KV-cache swapping.

Experimental setup

Datasets: LMSYS-Chat-1M synthetic requests with P/D ratios 1:4 and 4:1

Benchmarks: Vidur simulator workloads (LMSYS-Chat-1M, synthetic P/D ratios)

Metrics: average end-to-end latency P95 EEL P99 EEL throughput TTFT tail TTFT SLO violation

Baselines: Round Robin Least Outstanding Request Random Power-of-2 Choices

Builds on: bid-price control online linear programming Vidur

Closest papers by meaning

• Efficient Training-Free Online Routing for High-Volume Multi-LLM Serving (NeurIPS 2025 · similarity 0.89)
• TokenRouter: Efficient Serving System for Token-Level LLM Routing (NeurIPS 2026 · similarity 0.87)
• Tackling the Data-Parallel Load Balancing Bottleneck in LLM Serving: Practical Online Routing at Scale (NeurIPS 2026 · similarity 0.87)
• MESS+: Dynamically Learned Inference-Time LLM Routing in Model Zoos with Service Level Guarantees (NeurIPS 2025 · similarity 0.87)
• R2-Router: A New Paradigm for LLM Routing with Reasoning (ICML 2026 · similarity 0.85)
• RACER: Risk-Aware Calibrated Efficient Routing for Large Language Models (ICML 2026 · similarity 0.85)