This work introduces a multi-objective optimization framework that formulates routing as an online linear programming with interpretable decision rewards and applies an efficient bid-price control policy based on the online linear programming that admits requests when their SLO-weighted benefit exceeds their shadow prices.
Abstract
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.
INTRODUCTION: Disaggregated large language model (LLM) serving separates the compute-bound prefill phase from the memory-bound decode phase and is increasingly deployed across heterogeneous multi-cloud and edge-adjacent fleets serving geographically distributed (including IoT and edge) clients. The key-value (KV) cache that couples the two phases raises a stateful routing problem—migrate, recompute, or partially ship the cache across inter-cloud links of varying bandwidth, on hardware of varying capability, under spot prices that change every few minutes—that, to our knowledge, no published framework fully addresses.
OBJECTIVES: To jointly optimize prefill placement, decode placement, KV-cache transport policy, and slow-timescale pool sizing across clouds with heterogeneous link bandwidths, GPU capabilities, and volatile spot prices, with explicit provable guarantees.
METHODS: We present Janus, an online scheduler that formulates per-request scheduling as a constrained graph-routing problem with stateful edges and decomposes it into a monotone-submodular prefix-aware placement subproblem and a Lyapunov drift-plus-penalty control subproblem, with four KV-transport policies including a hybrid layer-pipelined policy admitting a closed-form layer-split optimum. A 17.1K-line prototype implements the scheduling logic; evaluation uses a trace-driven, discrete-event simulator whose timing and cost models are calibrated against measured single-pod microbenchmarks, configured to model a 96-pod (512-GPU) three-cloud, six-region fleet.
RESULTS: We prove a (1 1/e) approximation for prefix reuse under continuous greedy (with a 1/2 guarantee for the deployed combinatorial greedy under slack capacity, degrading to 1/3 when heterogeneous KV capacity binds), an O(1/V ) gap to the best policy in the decomposed class with O(V ) queue bound stated with its explicit additive constants, a sample-path robustness guarantee under adversarially time-varying prices and bandwidth, and a hybrid-transport optimality theorem. In simulation, versus the strongest multi-cloud baseline we construct, Janus attains 3.8 median and 4.6 P99 time-to-first-token reduction, 2.1 goodput, a 71% reuse-capture rate, and 38% cost reduction, with graceful degradation under spot-preemption, WAN-bandwidth-collapse, and region-failure scenarios.
CONCLUSION: Janus is, to our knowledge, the first scheduler to treat the KV-transport decision as a first-class scheduling variable jointly with prefill and decode routing across heterogeneous multi-cloud fleets, with provable guarantees; physical multi-cloud deployment and hardware validation of the simulated results are explicitly left as future work.
K. B. Aruna, V. Kaliraj, I. Sudha et al.· EAI Endorsed Transactions on...· 0 citations
This work proposes Double-Channel Graph Attention (DCGA), an end-to-end reinforcement learning framework that isolates network reachability and demand-service logic into separate graph channels and constructs valid routes using a simulator-coupled, constraint-informed decoder.
Empirical results on RouterBench and SWE-Bench demonstrate that WR-Offline surpasses existing baselines in performance under a fixed budget and adheres more closely to budget constraints, and WR-Online achieves comparable performance to the baselines, while using substantially less exploration data.
We study the Service-Aware Multi-Commodity Flow (SAMCF) problem, in which demand is elastic and governed by a logit choice model while routing is subject to hard capacity constraints. In a centralized, system-optimal setting, the network operator jointly determines how much demand to serve and how to route it. We formulate the SAMCF as a nonlinear program and propose an iterative fixed-point heuristic that alternates between solving an inelastic MCF via column generation and updating demand from the resulting service levels. Two linear approximations based on piecewise-linear demand functions and McCormick envelopes serve as benchmarks, while a piecewise-linear outer-approximation of the demand function is used to provide valid lower bounds. Computational experiments on public transport instances show that the heuristic finds near-optimal solutions in under two seconds - orders of magnitude faster than the benchmark methods - while matching their solution quality on all instances they can solve within a ten-minute time limit.
This paper studies a resource-allocation inefficiency in batched large language model (LLM) serving: heterogeneous requests that share a decode batch impose max-driven computational costs on one another. Because the wall-clock cost of a batch step is largely governed by the largest active KV-cache footprint, a short request co-batched with a long request can experience latency and GPU-resource consumption disproportionate to its own token workload. We formalize this phenomenon as a resource-fair scheduling problem. We develop a mathematical scheduling model that connects within-batch resource fairness to system throughput. The proposed fairness constraint bounds the disparity in decode progress, equivalently KV-cache footprint, among co-batched requests. Based on this model, we design the Insert-Short-Jobs-with-Limit (ISJL) algorithm, a parameterized hybrid batching policy. We prove that ISJL achieves a global competitive-ratio lower bound of $3/4$. We further examine the profit implications of resource-fair scheduling under the token-metered pricing convention used by commercial LLM APIs. Numerical experiments show that ISJL occupies a favorable middle ground between FCFS, which has large batching externalities, and LJF, which is cost-aligned but sacrifices batching flexibility. Thus, ISJL provides a bi-criterion scheduling policy: it maintains high throughput while aligning max-driven batch cost with token-metered revenue.
Serving a stream of requests across large language models (LLMs) of differing cost and quality is an online allocation problem, usually framed as multi-armed bandits. We frame it as feedback control: a direct-acting Proportional–Integral–Derivative (PID) controller whose setpoint is the running fleet- average performance and whose bounded output adjusts each model’s allocation share, with requests routed by weighted sampling over the allocation vector. This work contributes (i) a stability analysis ofthe closed loop — bounded-input bounded-output behaviour by anti-windup, exponential convergence of the performance estimates via a Lyapunov function, and a persistent-excitation condition guaranteeing recoverability after a regime change; (ii) a closed-form, analysis-grounded automatic tuning rule requiring no per-dataset search; and (iii) an honest head-to-head against static, round-robin, random, epsilon-greedy, UCB1, Thompson sampling, and the non-stationary bandits Sliding-Window UCB and Discounted UCB, on GSM8K with a checkable exact-match reward, reporting inference cost and request latency alongside quality. Under transient drift the auto-tuned controller is statistically tied with the best non-stationary bandit at lower cost; under a persistent regime shift it significantly outperforms both (p < 0.03). We further show the integral term helps only under a persistent shift — a proportional controller suffices for transient drift — and evaluate robustness to noisy rewards. The result is an interpretable, stability-analyzed, auto-tuned routing controller competitive with or superior to non- stationary bandits at lower cost.
Harshil Lodhiya· Journal of Computer Science...· 0 citations