Online Linear Programming for Multi-Objective Routing in LLM Serving

# Online Linear Programming for Multi-Objective Routing in LLM Serving
Source: [https://arxiv.org/html/2607.03948](https://arxiv.org/html/2607.03948)
###### 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\.

LLM Serving, Online Linear Programming

## 1Introduction

The demand for large language model \(LLM\) services has surged dramatically in recent years, with billions of requests being processed daily\(Roth,[2025](https://arxiv.org/html/2607.03948#bib.bib21)\)\. As this demand continues to grow, optimizing the efficiency of LLM serving systems has become an increasingly critical challenge\(Kwonet al\.,[2023](https://arxiv.org/html/2607.03948#bib.bib9); Popeet al\.,[2023](https://arxiv.org/html/2607.03948#bib.bib24); Shenget al\.,[2023](https://arxiv.org/html/2607.03948#bib.bib25); Agrawalet al\.,[2024b](https://arxiv.org/html/2607.03948#bib.bib23)\)\. LLM serving consists of two key stages for each request: \(i\) the prefill stage, where the key\-value \(KV\) pairs of the input are generated, and \(ii\) the decode stage, where the model autoregressively generates output tokens\. Due to the massive volume of requests and limited computational resources, it is impossible to process all requests simultaneously\. In this paper, we focus on optimizing the*router*, which dispatches incoming requests to parallel computational workers\(Jainet al\.,[2024](https://arxiv.org/html/2607.03948#bib.bib30); Wu and Silwal,[2025](https://arxiv.org/html/2607.03948#bib.bib28); Meiet al\.,[2025](https://arxiv.org/html/2607.03948#bib.bib29)\), and we cast this control problem as a general online resource allocation task with time\-coupled constraints, specialized to decode\-side LLM serving\.

Optimizing the router requires specifying*what*performance the system should optimize, yet real LLM services operate under heterogeneous service\-level objectives \(SLOs\)\. For instance, real\-time voice translation and interactive agents prioritize responsiveness, often measured by time\-to\-first\-token, whereas chatbots emphasize end\-to\-end latency because users care about the time to receive a complete response; meanwhile, system operators also track throughput as a proxy for capacity and cost efficiency\. These objectives are intrinsically in tension: increasing throughput typically relies on larger or more aggressive batching and higher device utilization, which raises queueing delays and degrades latencies, while prioritizing low latency often forces smaller batches or reserved capacity, reducing overall throughput and utilization\. Because different products require different metric combinations and trade\-offs, serving stacks frequently resort to retuning or even redesigning routing heuristics per deployment, motivating a general multi\-objective control framework that can flexibly adapt routing behavior by adjusting objective weights rather than changing the router’s structure\.

Many production serving stacks \(e\.g\., vLLM\(Kwonet al\.,[2023](https://arxiv.org/html/2607.03948#bib.bib9)\)\) and simulators \(e\.g\., Vidur\(Agrawalet al\.,[2024a](https://arxiv.org/html/2607.03948#bib.bib22)\)\) adopt simple routing heuristics that fall into two broad families:*greedy load\-based*rules and*randomized*rules\. Representative greedy policies include join\-shortest\-queue and power\-of\-ddchoices\. While effective in classical parallel\-server settings, these rules were designed for environments where job sizes are either known or homogeneous\. In LLM serving, however, the relevant workload is driven by heterogeneous and uncertain decode lengths: two queues with the same number of requests can correspond to vastly different remaining work\. Recent work has explored decode\-length prediction\(Fuet al\.,[2024](https://arxiv.org/html/2607.03948#bib.bib12); Zhenget al\.,[2023b](https://arxiv.org/html/2607.03948#bib.bib10); Qiuet al\.,[2024](https://arxiv.org/html/2607.03948#bib.bib11); Shahoutet al\.,[2024](https://arxiv.org/html/2607.03948#bib.bib14)\), workload\-aware scheduling\(Jainet al\.,[2024](https://arxiv.org/html/2607.03948#bib.bib30)\), and multi\-LLM routing\(Wu and Silwal,[2025](https://arxiv.org/html/2607.03948#bib.bib28); Meiet al\.,[2025](https://arxiv.org/html/2607.03948#bib.bib29)\), yet most deployed systems still rely on heuristics that provide limited control over SLO trade\-offs\. Randomized baselines such as round\-robin and uniform routing avoid relying on imperfect workload estimates, but they ignore the instantaneous system state and cannot adapt to congestion\. More fundamentally, neither family is derived from an explicit optimization objective, providing limited and non\-transparent control over trade\-offs among competing SLOs—precisely the flexibility required for multi\-objective serving\.

The challenge of dispatching requests to capacity\-constrained resources under uncertainty is a classical problem in operations research, studied extensively under the framework of online linear programming \(LP\)\(Agrawalet al\.,[2014](https://arxiv.org/html/2607.03948#bib.bib20); Liet al\.,[2020](https://arxiv.org/html/2607.03948#bib.bib34); Li and Ye,[2022](https://arxiv.org/html/2607.03948#bib.bib17)\)and bid\-price control in revenue management\(Talluri and Van Ryzin,[1998](https://arxiv.org/html/2607.03948#bib.bib15); Akan and Ata,[2009](https://arxiv.org/html/2607.03948#bib.bib16)\)\. A key insight from this literature is that good online decisions should balance the*immediate benefit*of serving a request against the*opportunity cost*of consuming scarce capacity that may be needed for future arrivals\. LP\(Luenbergeret al\.,[1984](https://arxiv.org/html/2607.03948#bib.bib31)\)duality provides a principled way to quantify these opportunity costs through*shadow prices*\. In LLM serving, the scarce resources are batch slots and KV\-cache memory on each device across future time steps—resources that are*time\-coupled*because a request admitted now occupies capacity throughout its decode duration\. Beyond constraints, the*objectives*themselves require careful design: aggregate SLOs such as tail latency are statistical properties that do not directly decompose into per\-request rewards\. A key modeling contribution of our work is a reward structure that converts these aggregate metrics into per\-request incentives while ensuring that scheduling is usually beneficial\. This combination of time\-coupled constraints and SLO\-decomposable objectives motivates our online LP framework\.

To our knowledge, no prior work provides a multi\-objective optimization framework for LLM routing that \(i\) explicitly models time\-coupled KV\-cache and batch\-size constraints inherent to autoregressive decoding, \(ii\) decomposes aggregate SLOs—including tail latency—into per\-request rewards suitable for online optimization, and \(iii\) derives computationally efficient policies grounded in LP duality\. Our work bridges this gap by bringing operations research methodology to LLM serving\. Specifically, we make the following contributions:

1. 1\.Multi\-objective optimization framework\.We formulate LLM routing as an online linear program with time\-coupled batch and KV\-cache constraints\. The objective function explicitly incorporates multiple SLOs—throughput, end\-to\-end latency, time\-to\-first\-token, and tail latency—through interpretable weights that operators can adjust to match product requirements\.
2. 2\.Efficient bid\-price control algorithm\.We derive a bid\-price policy where each routing decision compares the request’s SLO\-weighted benefit against its shadow\-price cost\. To meet millisecond decision latency requirements, we develop warm\-started projected gradient updates that track evolving dual prices online without solving an LP at each step\.
3. 3\.Interpretable trade\-off control\.Through the LP formulation, operators gain transparent control over SLO trade\-offs: adjusting objective weights systematically shifts performance along the Pareto frontier, and shadow prices reveal which resources \(batch slots vs\. KV\-cache\) are bottlenecks under different workloads\.

We validate our framework through extensive simulation experiments using the Vidur simulator\(Agrawalet al\.,[2024a](https://arxiv.org/html/2607.03948#bib.bib22)\), demonstrating substantial improvements over standard routing heuristics across multiple SLO regimes\. While full integration into production serving systems remains future work, our results establish the potential of optimization\-based routing and provide a principled foundation for the systems community\. We also discuss the structural insights that emerge from viewing LLM routing through an optimization lens—insights that may guide future system design even beyond our specific algorithm\.

## 2Mathematical Model

In this section, we present a mathematical model for multi\-worker LLM serving under*Prefill/Decode \(PD\) disaggregation*\(Zhonget al\.,[2024](https://arxiv.org/html/2607.03948#bib.bib27)\)and*continuous batching*\. A discussion of how the model and algorithms are adapted under PD mixing is deferred to Appendix[A](https://arxiv.org/html/2607.03948#A1)\.

#### Time, devices, and requests\.

We consider a finite horizon of discrete periodsk=1,…,Tk=1,\\dots,Tand a set of decode devices indexed byg∈\[G\]g\\in\[G\]\. One period corresponds to one decode iteration of a batched decode kernel on a device\. An instance of requests𝒥\\mathcal\{J\}arrives sequentially over the horizon\. Each requestj∈𝒥j\\in\\mathcal\{J\}completes its prefill stage and arrives at timetj∈\{1,…,T\}t\_\{j\}\\in\\\{1,\\dots,T\\\}with: \(i\) a known prefill footprintsjs\_\{j\}\(e\.g\., the number of KV\-cache token slots already materialized by prefill\), and \(ii\) an unknown decode lengthojo\_\{j\}\(the number of decode tokens required to complete the response\)\. In practice,ojo\_\{j\}can be predicted using established techniques \(e\.g\.,\(Zhenget al\.,[2023b](https://arxiv.org/html/2607.03948#bib.bib10); Qiuet al\.,[2024](https://arxiv.org/html/2607.03948#bib.bib11); Fuet al\.,[2024](https://arxiv.org/html/2607.03948#bib.bib12); Chenet al\.,[2024](https://arxiv.org/html/2607.03948#bib.bib13); Shahoutet al\.,[2024](https://arxiv.org/html/2607.03948#bib.bib14)\)\); we denote the predicted decode length byo^j\\hat\{o\}\_\{j\}, which may be inaccurate\.

#### Router\-side buffering\.

After completing prefill, each requestjjenters a*central router queue*at timetjt\_\{j\}\. At the beginning of each periodkk, the router observes the current state of each decode device, and may*release*a subset of queued requests to devices\. This design is supported by recent versions of the vLLM engine, which implement router\-side buffering\(vLLM Project,[2025](https://arxiv.org/html/2607.03948#bib.bib36); vLLM Roadmap,[2025](https://arxiv.org/html/2607.03948#bib.bib35)\)\.

In this paper, we focus on a*release\-when\-startable*design: the router dispatches a request to a device only if the request can be admitted into that device’s active decode batch in the same period\. In implementation, one may still maintain short per\-device FIFO queues, but under our policy these queues remain small\.

#### Routing and admission decisions\.

For each requestj∈𝒥j\\in\\mathcal\{J\}, deviceg∈\[G\]g\\in\[G\], and periodτ∈\{tj,…,T\}\\tau\\in\\\{t\_\{j\},\\dots,T\\\}, we define arouting/admission decision variable

xj,g,τ∈\[0,1\],x\_\{j,g,\\tau\}\\in\[0,1\],interpreted as: “requestjjis released from the router queue and admitted to deviceggat the beginning of periodτ\\tau\.” In an integral schedule,xj,g,τ∈\{0,1\}x\_\{j,g,\\tau\}\\in\\\{0,1\\\}and at most one pair\(g,τ\)\(g,\\tau\)is selected for each request:∑g∈\[G\]∑τ=tjTxj,g,τ≤1,∀j∈𝒥\\sum\_\{g\\in\[G\]\}\\sum\_\{\\tau=t\_\{j\}\}^\{T\}x\_\{j,g,\\tau\}\\ \\leq\\ 1,\\forall j\\in\\mathcal\{J\}\.

#### Continuous batching within a decode device\.

Within each decode device, we model the classical continuous batching mechanism used by vLLM\(Kwonet al\.,[2023](https://arxiv.org/html/2607.03948#bib.bib9)\)\. At each period, deviceggexecutes one batched decode iteration that processes*one token*for every*active*request currently in its batch\. A requestjjrequiresojo\_\{j\}such iterations to complete\. As soon as an active request finishes, the device can admit new requests into the batch in subsequent iterations, thereby maintaining a continuously updated batch \(see Figure[1](https://arxiv.org/html/2607.03948#S2.F1)\)\.

![Refer to caption](https://arxiv.org/html/2607.03948v1/Figure1.jpg)Figure 1:Illustration of Prefill/Decode \(P/D\) disaggregation with continuous batching\. Each small box denotes a token, and colors indicate distinct requests\. Within each decode worker, active requests are processed token\-by\-token in a continuously updated batch as completed requests are replaced by newly admitted ones\.
#### KV\-cache memory accounting\.

During decoding, the KV\-cache footprint of requestjjincreases by \(approximately\) one token slot per decoded token\. We represent the KV\-cache usage of requestjjafterθ\\thetadecoded tokens by the kernelmjmem​\(θ\)m^\{\\text\{mem\}\}\_\{j\}\(\\theta\):

mjmem​\(θ\)=\{sj\+θ\+1,0≤θ<oj,0,otherwise,m^\{\\text\{mem\}\}\_\{j\}\(\\theta\)=\\begin\{cases\}s\_\{j\}\+\\theta\+1,&0\\leq\\theta<o\_\{j\},\\\\ 0,&\\text\{otherwise\},\\end\{cases\}\(1\)whereθ\\thetais the number of decode tokens already generated for requestjj\. \(Equivalently, whilejjis active, its memory footprint equals its prefill footprint plus its current decoded length\.\)

#### Device feasibility constraints\.

A device cannot batch arbitrarily many requests due to two common constraints:

1. \(i\)Batch\-size constraint:at any period, each decode device can host at mostBBactive requests in the batch\.
2. \(ii\)KV\-cache capacity:at any period, the total KV\-cache usage of all active requests on a decode device cannot exceed a budgetMM; otherwise, the system must swap requests out and stall compute\. In our model, we enforce routing/scheduling decisions that respect this capacity\.

Here, treating one decode iteration as one time period is reasonable since under PD disaggregation, decode workers process only decode iterations, eliminating the primary source of iteration\-time variability identified in non\-disaggregated systems\. In a decode\-only regime, each iteration is memory\-bandwidth\-bound: the dominant cost is loading model weights, which is constant regardless of batch composition\. The attention component grows linearly with the total cached KV tokens, but profiling reported byJainet al\.\([2024](https://arxiv.org/html/2607.03948#bib.bib30)\)shows this slope is roughly10×10\\timessmaller than the corresponding prefill slope, indicating that decode iteration time varies slowly with batch state\.

Objective Metrics\.LLM serving is naturally multi\-objective\. We consider the following standard performance metrics\.

#### Service\-level metrics\.

1. \(1\)Average/Tail end\-to\-end latency \(EEL\):Letcjc\_\{j\}denote the period when requestjjcompletes \(i\.e\., its final token is processed\)\. The end\-to\-end latency of requestjjiscj−tjc\_\{j\}\-t\_\{j\}\. The average EEL is 1\|𝒥\|​∑j∈𝒥\(cj−tj\)\.\\frac\{1\}\{\|\\mathcal\{J\}\|\}\\sum\_\{j\\in\\mathcal\{J\}\}\(c\_\{j\}\-t\_\{j\}\)\.For a tail levelx%x\\%, thex%x\\%tail EEL is thex%x\\%quantile of the multiset\{cj−tj:j∈𝒥\}\\\{\\,c\_\{j\}\-t\_\{j\}:j\\in\\mathcal\{J\}\\,\\\}\.
2. \(2\)Average/Tail time\-to\-first\-token \(TTFT\):Letτj\\tau\_\{j\}denote the period when requestjjstarts decoding, i\.e\., when its*first*output token is generated\. The TTFT of requestjjisτj−tj\\tau\_\{j\}\-t\_\{j\}\. The average TTFT is 1\|𝒥\|​∑j∈𝒥\(τj−tj\),\\frac\{1\}\{\|\\mathcal\{J\}\|\}\\sum\_\{j\\in\\mathcal\{J\}\}\(\\tau\_\{j\}\-t\_\{j\}\),and thex%x\\%tail TTFT is thex%x\\%quantile of\{τj−tj:j∈𝒥\}\\\{\\,\\tau\_\{j\}\-t\_\{j\}:j\\in\\mathcal\{J\}\\,\\\}\.

#### System\-level metrics\.

1. \(3\)Throughput:LetNtok​\(T\)N^\{\\text\{tok\}\}\(T\)be the total number of decode tokens processed over periods1,…,T1,\\dots,Tacross all devices\. The \(average\) token throughput over the horizon is Ntok​\(T\)/T\.N^\{\\text\{tok\}\}\(T\)/T\.
2. \(4\)Queries\-per\-second \(QPS\):LetNreq​\(T\)N^\{\\text\{req\}\}\(T\)be the number of requests that complete by timeTT\. The \(average\) QPS over the horizon is Nreq​\(T\)/T\.N^\{\\text\{req\}\}\(T\)/T\.

## 3Methodology and Algorithm Design

In this section, we present an online linear programming\-based algorithm designed to optimize multiple objectives in the LLM serving process\.

### 3\.1Online Linear Programming Formulation

At each decoding stepk∈\{1,2,…,T\}k\\in\\\{1,2,\\dots,T\\\}, we define the set of requests that have not yet started decoding \(i\.e\., they are waiting in the queue\) as𝒥k\(w​a​i​t\)\\mathcal\{J\}^\{\(wait\)\}\_\{k\}\. The activity indicator for decoding steps is defined asaj​\(θ\)=𝟏​\{0≤θ<o^j\}a\_\{j\}\(\\theta\)=\\mathbf\{1\}\\\{0\\leq\\theta<\\hat\{o\}\_\{j\}\\\}, whereθ\\thetarepresents the number of decoding steps processed by requestjjsince its start time\. If a request starts at timeτ\\tau, thenaj​\(k−τ\)a\_\{j\}\(k\-\\tau\)indicates whether the request is currently being processed at timekk\(taking values 1 or 0 depending on whether it is active and within the batch size limit\)\. The memory usage of the request follows the kernelmjmem​\(θ\)m^\{\\text\{mem\}\}\_\{j\}\(\\theta\)defined in \([1](https://arxiv.org/html/2607.03948#S2.E1)\)\.

Given that each worker is subject to both a batch size constraint and a memory usage constraint, we define a constraint\-type indexu∈\{bat,mem\}u\\in\\\{\\textsf\{bat\},\\textsf\{mem\}\\\}, where:

- •batrepresents the per\-period batch size constraint;
- •memrepresents the per\-period memory usage constraint\.

We define the set of device\-time\-constraint coordinates as

ℐ:=\[G\]×\[T\]×\{bat,mem\},i=\(g,k,u\)∈ℐ\.\\mathcal\{I\}:=\[G\]\\times\[T\]\\times\\\{\\textsf\{bat\},\\textsf\{mem\}\\\},\\quad i=\(g,k,u\)\\in\\mathcal\{I\}\.For each device\-time\-constraint coordinatei=\(g,k,u\)∈ℐi=\(g,k,u\)\\in\\mathcal\{I\}and requestjj, the scheduling action column coefficient is defined as

ai,\(j,g′,τ\)=\{aj​\(k−τ\),if​u=bat,g′=g,mjmem​\(k−τ\),if​u=mem,g′=g,0,otherwise\.a\_\{i,\(j,g^\{\\prime\},\\tau\)\}=\\begin\{cases\}a\_\{j\}\(k\-\\tau\),&\\text\{if \}u=\\textsf\{bat\},~g^\{\\prime\}=g,\\\\ m^\{\\text\{mem\}\}\_\{j\}\(k\-\\tau\),&\\text\{if \}u=\\textsf\{mem\},~g^\{\\prime\}=g,\\\\ 0,&\\text\{otherwise\}\.\\end\{cases\}For each device\-time\-constraint coordinatei=\(g,k,u\)i=\(g,k,u\), we set

b\(g,k,bat\)=Bg,k,b\(g,k,mem\)=Mg,k,b\_\{\(g,k,\\textsf\{bat\}\)\}=B\_\{g,k\},\\quad b\_\{\(g,k,\\textsf\{mem\}\)\}=M\_\{g,k\},whereBg,kB\_\{g,k\}represents the remaining batch size capacity \(i\.e\., the difference between the total batch size limitBBand the number of active requests\) of deviceggat timekk, andMg,kM\_\{g,k\}represents the remaining KV memory usage capacity of deviceggat timekk\. At decision stepk∈\[T\]k\\in\[T\], only requests that have not yet started \(i\.e\., those in𝒥k\(w​a​i​t\)\\mathcal\{J\}^\{\(wait\)\}\_\{k\}\) can be scheduled\. We define the action \(column\) set as

𝒜k:=\{\(j,g,k\):j∈𝒥k\(w​a​i​t\),g∈\[G\]\}\.\\mathcal\{A\}\_\{k\}:=\\\{\(j,g,k\):j\\in\\mathcal\{J\}^\{\(wait\)\}\_\{k\},g\\in\[G\]\\\}\.The system\-level constraints for each deviceggat timekkcan be written as

∑\(j,g,k\)∈𝒜kai,\(j,g,k\)​xj,g,k≤bi,∀i=\(g,k,u\)∈ℐ\.\\sum\_\{\(j,g,k\)\\in\\mathcal\{A\}\_\{k\}\}a\_\{i,\(j,g,k\)\}x\_\{j,g,k\}\\leq b\_\{i\},\\quad\\forall i=\(g,k,u\)\\in\\mathcal\{I\}\.At stepkk, we make decisions only for the waiting requestsj∈𝒥k\(w​a​i​t\)j\\in\\mathcal\{J\}^\{\(wait\)\}\_\{k\}about which device and time to start processing\. Althoughxj,g,kx\_\{j,g,k\}represents a one\-time start decision, it induces resource usage across multiple future stepst≥kt\\geq kthrough the age\-dependent kernels:aj​\(t−k\)a\_\{j\}\(t\-k\)for batch occupancy andmjmem​\(t−k\)m^\{\\text\{mem\}\}\_\{j\}\(t\-k\)for KV memory usage\. A request automatically stops contributing to the resource constraints once it finishes decoding, asaj​\(θ\)=0a\_\{j\}\(\\theta\)=0andmjmem​\(θ\)=0m^\{\\text\{mem\}\}\_\{j\}\(\\theta\)=0whenθ≥o^j\\theta\\geq\\hat\{o\}\_\{j\}\. The right\-hand sidebib\_\{i\}represents the remaining capacity after subtracting the load of previously started requests, ensuring that newly admitted requests do not violate batch size or memory constraints on any device at any future decoding step\.

#### Linear Multiple Objective and Decision Reward

To formulate this problem as a linear program, we assign a reward to each decision\(j,g,k\)\(j,g,k\), corresponding to assigning requestjjto deviceggat timekk\. The reward function is given by

rj,g,k\\displaystyle r\_\{j,g,k\}\\;=α⋅Thrj,g,k⏟throughput−β⋅EELj,g,k⏟average end\-to\-end latency\\displaystyle=\\;\\underbrace\{\\alpha\\cdot\\texttt\{Thr\}\_\{j,g,k\}\}\_\{\\text\{throughput\}\}\-\\underbrace\{\\beta\\cdot\\texttt\{EEL\}\_\{j,g,k\}\}\_\{\\text\{average end\-to\-end latency\}\}−γ⋅TTFTj,g,k⏟average TTFT\+σ⋅QPSj,g,k⏟queries per second\\displaystyle\\quad\-\\underbrace\{\\gamma\\cdot\\texttt\{TTFT\}\_\{j,g,k\}\}\_\{\\text\{average TTFT\}\}\+\\underbrace\{\\sigma\\cdot\\texttt\{QPS\}\_\{j,g,k\}\}\_\{\\text\{queries per second\}\}−ζ1⋅Tail EELj,g,k⏟tail end\-to\-end latency−ζ2⋅Tail TTFTj,g,k⏟tail TTFT,\\displaystyle\\quad\-\\underbrace\{\\zeta\_\{1\}\\cdot\\texttt\{Tail EEL\}\_\{j,g,k\}\}\_\{\\text\{tail end\-to\-end latency\}\}\-\\underbrace\{\\zeta\_\{2\}\\cdot\\texttt\{Tail TTFT\}\_\{j,g,k\}\}\_\{\\text\{tail TTFT\}\},whereα,β,γ,σ,ζ1,ζ2≥0\\alpha,\\beta,\\gamma,\\sigma,\\zeta\_\{1\},\\zeta\_\{2\}\\geq 0are parameters representing the relative importance of each objective\. These parameters should be selected according to the specific product and its purpose, as different products may prioritize different metrics\.

Next, we decompose each term in the reward to better understand how the metrics contribute to the overall decision\.

For system\-level metrics, the throughput contribution of an action is given by the number of tokens processed during the time horizon\[0,T\]\[0,T\]\. If a request is assigned, its true contribution to throughput is the minimum of its predicted decode length and the remaining time steps:Thrj,g,k=min⁡\{o^j,T−k\+1\}\\texttt\{Thr\}\_\{j,g,k\}=\\min\\\{\\hat\{o\}\_\{j\},T\-k\+1\\\}\. For QPS, the contribution of an action is simply 1, as each assigned request contributes one processed query:QPSj,g,k=1\\texttt\{QPS\}\_\{j,g,k\}=1\.

For service\-level metrics, consider the contribution of each action to the average latency\. Over the time horizon\[0,T\]\[0,T\], we have:

EELj,g,k=min⁡\{k\+o^j,T\+1\}−tj,TTFTj,g,k=k−tj\.\\texttt\{EEL\}\_\{j,g,k\}=\\min\\\{k\+\\hat\{o\}\_\{j\},T\+1\\\}\-t\_\{j\},\\quad\\texttt\{TTFT\}\_\{j,g,k\}=k\-t\_\{j\}\.However, although we seek to minimize latency, wecannot allow it to become negative\. If we provide negative penalties for latency, the router may choose not to assign requests in order to avoid incurring a penalty, especially as the time horizonTTapproaches its end\. To avoid this issue, we observe that both end\-to\-end latency and TTFT can be written as:

∑s=tjT𝟏​\{not finished by​s\}=\(T−tj\+1\)−\(T−\(k\+o^j−1\)\)\+,\\sum\_\{s=t\_\{j\}\}^\{T\}\\mathbf\{1\}\\\{\\text\{not finished by \}s\\\}=\(T\-t\_\{j\}\+1\)\-\\bigl\(T\-\(k\+\\hat\{o\}\_\{j\}\-1\)\\bigr\)\_\{\+\},\(2\)and

∑s=tjT𝟏​\{not started by​s\}=\(T−tj\+1\)−\(T−k\+1\),\\sum\_\{s=t\_\{j\}\}^\{T\}\\mathbf\{1\}\\\{\\text\{not started by \}s\\\}=\(T\-t\_\{j\}\+1\)\-\(T\-k\+1\),\(3\)respectively\. In both \([2](https://arxiv.org/html/2607.03948#S3.E2)\) and \([3](https://arxiv.org/html/2607.03948#S3.E3)\), the term\(T−tj\+1\)\(T\-t\_\{j\}\+1\)is independent of the decision process, and we can eliminate this term\. The only penalty related to the decision is−\(T−\(k\+o^j−1\)\)\+\-\\bigl\(T\-\(k\+\\hat\{o\}\_\{j\}\-1\)\\bigr\)\_\{\+\}and−\(T−k\+1\)\-\(T\-k\+1\), which makes the penalties negative and the reward positive\.

We also introduce an interesting and simple method to decompose statistical tail latency into an instant reward for the action\. Taking tail TTFT as an example, suppose the service\-level constraint is that the tail TTFT must be bounded byt′t^\{\\prime\}\. We define an indicator reward as

Tail TTFTj,g,k=𝟏​\{k−tj<t′\}\.\\texttt\{Tail TTFT\}\_\{j,g,k\}=\\mathbf\{1\}\\\{k\-t\_\{j\}<t^\{\\prime\}\\\}\.This guarantees that if the TTFT of a request is within the desired boundt′t^\{\\prime\}, a reward of 1 unit is added\. To enforce a stricter tail TTFT requirement \(e\.g\., the 99th percentile\), we set a larger weight forζ2\\zeta\_\{2\}, which increases the weight on tail TTFT in the reward and drives decisions to prioritize it\. Thus, the weights associated with the tail latency metrics,ζ1\\zeta\_\{1\}andζ2\\zeta\_\{2\}, not only determine the relative importance of tail latency in comparison to other objectives, but also directly map the target quantiles for the tail latency\. A detailed guideline on how to select these parameters will be provided in Section[4](https://arxiv.org/html/2607.03948#S4)\.

Finally, the overall positive reward for action\(j,g,k\)\(j,g,k\)is written as:

rj,g,k\\displaystyle r\_\{j,g,k\}\\;=α⋅min⁡\{o^j,T−k\+1\}⏟throughput\+β⋅\(T−\(k\+o^j−1\)\)\+⏟end\-to\-end latency ”saved steps”\\displaystyle=\\;\\underbrace\{\\alpha\\cdot\\min\\\{\\hat\{o\}\_\{j\},T\-k\+1\\\}\}\_\{\\text\{throughput\}\}\+\\underbrace\{\\beta\\cdot\\bigl\(T\-\(k\+\\hat\{o\}\_\{j\}\-1\)\\bigr\)\_\{\+\}\}\_\{\\text\{end\-to\-end latency "saved steps"\}\}\+γ⋅\(T−k\+1\)⏟first\-token ”saved steps”\+σ⏟queries per second\\displaystyle\\quad\+\\underbrace\{\\gamma\\cdot\(T\-k\+1\)\}\_\{\\text\{first\-token "saved steps"\}\}\+\\underbrace\{\\sigma\}\_\{\\text\{queries per second\}\}\+ζ1⋅𝟏​\{k\+o^j−tj<t1′\}⏟indicator reward for tail EEL\+ζ2⋅𝟏​\{k−tj<t2′\}⏟indicator reward for tail TTFT\.\\displaystyle\\quad\+\\underbrace\{\\zeta\_\{1\}\\cdot\\mathbf\{1\}\\\{k\+\\hat\{o\}\_\{j\}\-t\_\{j\}<t\_\{1\}^\{\\prime\}\\\}\}\_\{\\text\{indicator reward for tail EEL\}\}\+\\underbrace\{\\zeta\_\{2\}\\cdot\\mathbf\{1\}\\\{k\-t\_\{j\}<t\_\{2\}^\{\\prime\}\\\}\}\_\{\\text\{indicator reward for tail TTFT\}\}\.The corresponding online linear programming formulation at timekkis:

maxx\\displaystyle\\max\_\{x\}\\quad∑\(j,g,k\)∈𝒜krj,g,k​xj,g,k\\displaystyle\\sum\_\{\(j,g,k\)\\in\\mathcal\{A\}\_\{k\}\}r\_\{j,g,k\}x\_\{j,g,k\}s\.t\.∑\(j,g,k\)∈𝒜kai,\(j,g,k\)​xj,g,k≤bi,∀i∈ℐ,\\displaystyle\\sum\_\{\(j,g,k\)\\in\\mathcal\{A\}\_\{k\}\}a\_\{i,\(j,g,k\)\}x\_\{j,g,k\}\\leq b\_\{i\},\\quad\\forall i\\in\\mathcal\{I\},\(4\)∑g∈\[G\]xj,g,k≤1,∀j∈𝒥k\(w​a​i​t\)\.\\displaystyle\\sum\_\{g\\in\[G\]\}x\_\{j,g,k\}\\leq 1,\\quad\\forall j\\in\\mathcal\{J\}^\{\(wait\)\}\_\{k\}\.\(5\)

### 3\.2Duality, Bid\-Price Control, and Stochastic Program

The per\-step LP provides a clean abstraction of the routing decision at timekk\. However, in an LLM serving system the decision loop must operate at millisecond scale, so repeatedly solving an LP to optimality at every step is impractical\. We therefore leverage LP duality to derive a*bid\-price control*rule\(Talluri and Van Ryzin,[1998](https://arxiv.org/html/2607.03948#bib.bib15); Akan and Ata,[2009](https://arxiv.org/html/2607.03948#bib.bib16); Agrawalet al\.,[2014](https://arxiv.org/html/2607.03948#bib.bib20); Li and Ye,[2022](https://arxiv.org/html/2607.03948#bib.bib17)\): instead of re\-optimizing from scratch, we update the dual prices \(resource shadow costs\) and make decisions by comparing each request’s reward against its implied resource cost\.

#### Dual formulation and bid prices\.

Introduce dual variablespi≥0p\_\{i\}\\geq 0for the packing constraints \([4](https://arxiv.org/html/2607.03948#S3.E4)\) andyj≥0y\_\{j\}\\geq 0for the per\-request constraint \([5](https://arxiv.org/html/2607.03948#S3.E5)\)\. For the per\-step LP at timekk, the standard dual is

minp≥0,y≥0\\displaystyle\\min\_\{p\\geq 0,\\,y\\geq 0\}\\quad∑i∈ℐbi​pi\+∑j∈𝒥k\(w​a​i​t\)yj\\displaystyle\\sum\_\{i\\in\\mathcal\{I\}\}b\_\{i\}\\,p\_\{i\}\\;\+\\;\\sum\_\{j\\in\\mathcal\{J\}^\{\(wait\)\}\_\{k\}\}y\_\{j\}s\.t\.∑i∈ℐai,\(j,g,k\)​pi\+yj≥rj,g,k,∀\(j,g,k\)∈𝒜k\.\\displaystyle\\sum\_\{i\\in\\mathcal\{I\}\}a\_\{i,\(j,g,k\)\}\\,p\_\{i\}\\;\+\\;y\_\{j\}\\;\\geq\\;r\_\{j,g,k\},\\ \\forall\(j,g,k\)\\in\\mathcal\{A\}\_\{k\}\.The dual variables admit concrete operational meaning\. For each resource\-time coordinatei=\(g,k,u\)∈ℐi=\(g,k,u\)\\in\\mathcal\{I\}, the dual variablepip\_\{i\}represents the*shadow price*of resource typeuuon deviceggat timekk: it quantifies the marginal value of one additional unit of batch capacity \(whenu=𝖻𝖺𝗍u=\\mathsf\{bat\}\) or KV\-cache memory \(whenu=𝗆𝖾𝗆u=\\mathsf\{mem\}\)\. High shadow prices indicate anticipated congestion on that resource, while low prices indicate spare capacity\. For each requestjj, the dual variableyjy\_\{j\}represents the*option value*of requestjj—the maximum net benefit \(SLO reward minus imputed resource cost\) achievable by routingjjto its best device\.

For a fixed price vectorpp, the optimal slack variable is

yj∗​\(p\)=\[maxg∈\[G\]⁡\{rj,g,k−∑i∈ℐai,\(j,g,k\)​pi\}\]\+\.y\_\{j\}^\{\*\}\(p\)=\\Bigg\[\\ \\max\_\{g\\in\[G\]\}\\ \\Big\\\{\\,r\_\{j,g,k\}\-\\sum\_\{i\\in\\mathcal\{I\}\}a\_\{i,\(j,g,k\)\}\\,p\_\{i\}\\,\\Big\\\}\\ \\Bigg\]\_\{\+\}\.Substitutingy∗​\(p\)y^\{\*\}\(p\)yields the reduced dual objective

minp≥0∑i∈ℐbi​pi\+∑j∈𝒥k\(w​a​i​t\)\[maxg∈\[G\]⁡\{rj,g,k−a\(j,g,k\)⊤​p\}\]\+,\\min\_\{p\\geq 0\}\\quad\\sum\_\{i\\in\\mathcal\{I\}\}b\_\{i\}p\_\{i\}\\;\+\\;\\sum\_\{j\\in\\mathcal\{J\}^\{\(wait\)\}\_\{k\}\}\\Bigg\[\\ \\max\_\{g\\in\[G\]\}\\ \\Big\\\{\\,r\_\{j,g,k\}\-a\_\{\(j,g,k\)\}^\{\\top\}p\\,\\Big\\\}\\ \\Bigg\]\_\{\+\},wherea\(j,g,k\)⊤​p:=∑i∈ℐai,\(j,g,k\)​pia\_\{\(j,g,k\)\}^\{\\top\}p:=\\sum\_\{i\\in\\mathcal\{I\}\}a\_\{i,\(j,g,k\)\}p\_\{i\}anda\(j,g,k\):=\(ai,\(j,g,k\)\)i∈ℐ∈ℝ\+\|ℐ\|a\_\{\(j,g,k\)\}:=\(a\_\{i,\(j,g,k\)\}\)\_\{i\\in\\mathcal\{I\}\}\\in\\mathbb\{R\}^\{\|\\mathcal\{I\}\|\}\_\{\+\}\. The quantitya\(j,g,k\)⊤​pa\_\{\(j,g,k\)\}^\{\\top\}pis the*imputed resource cost*of admitting\(j,g,k\)\(j,g,k\)under shadow pricespp\. Accordingly, the*bid\-price margin*

Δj​\(g\):=rj,g,k−a\(j,g,k\)⊤​p\\Delta\_\{j\}\(g\)\\;:=\\;r\_\{j,g,k\}\-a\_\{\(j,g,k\)\}^\{\\top\}pmeasures the net benefit of assigning requestjjto deviceggat timekkafter accounting for resource opportunity costs\.

#### Sample\-Average Approximation \(SAA\)\-style price learning\.

The reduced dual objective depends on the random stream of arrivals and on predicted decode length profiles\. We therefore viewppas the solution to an underlying stochastic program and estimate it from historical observations\. Let𝖧𝗂𝗌𝗍\\mathsf\{Hist\}denote a history set of previously observed pairs\(r⋆,a⋆\)\(r^\{\\star\},a^\{\\star\}\), where each\(r⋆,a⋆\)\(r^\{\\star\},a^\{\\star\}\)corresponds to a candidate action generated in the past\. At decision stepkk, we compute prices by minimizing the SAA:

fk​\(p\)=dk⊤​p\+1max⁡\{1,\|𝖧𝗂𝗌𝗍\|\}​∑\(r⋆,a⋆\)∈𝖧𝗂𝗌𝗍\(r⋆−\(a⋆\)⊤​p\)\+,f\_\{k\}\(p\)\\;=\\;d\_\{k\}^\{\\top\}p\\;\+\\;\\frac\{1\}\{\\max\\\{1,\|\\mathsf\{Hist\}\|\\\}\}\\sum\_\{\(r^\{\\star\},a^\{\\star\}\)\\in\\mathsf\{Hist\}\}\\bigl\(r^\{\\star\}\-\(a^\{\\star\}\)^\{\\top\}p\\bigr\)\_\{\+\},\(6\)wheredk:=b\(k−1\)max⁡\{1,n^remain​\(k\)\}\.d\_\{k\}:=\\frac\{b^\{\(k\-1\)\}\}\{\\max\\\{1,\\widehat\{n\}\_\{\\mathrm\{remain\}\}\(k\)\\\}\}\.Here, to simplify the notation, we denoteb\(k\):=\(bi\(k\)\)i∈ℐ∈ℝ\+\|ℐ\|,b^\{\(k\)\}\\;:=\\;\\bigl\(b^\{\(k\)\}\_\{i\}\\bigr\)\_\{i\\in\\mathcal\{I\}\}\\in\\mathbb\{R\}^\{\|\\mathcal\{I\}\|\}\_\{\+\},andb\(k−1\)b^\{\(k\-1\)\}is the residual\-capacity vector before making decisions at stepkk, andn^remain​\(k\)\\widehat\{n\}\_\{\\mathrm\{remain\}\}\(k\)is an forecast of the expected number of remaining admission opportunities\.

#### Bid\-price control online decision\.

Given the price vectorpkp\_\{k\}learned from history, a natural bid\-price rule is to accept a requestjjif its best margin,Δj​\(g\):=rj,g,k−a\(j,g,k\)⊤​pk\\Delta\_\{j\}\(g\):=r\_\{j,g,k\}\-a\_\{\(j,g,k\)\}^\{\\top\}p\_\{k\}, is positive\. However, at a single stepkkthere may be many waiting requests, and admitting*all*actions with positive margins can violate residual constraints\. Moreover, rewards and resource profiles are based on predictions \(e\.g\.,o^j\\hat\{o\}\_\{j\}\), which introduces estimation error\. To robustly enforce feasibility, we \(i\) compute bid price margins for all candidates, \(ii\) rank candidates by margin, and \(iii\) greedily admit the highest\-margin actions subject to the residual constraints and the one\-assignment\-per\-request rule\. The pseudocode can be found in Algorithm[1](https://arxiv.org/html/2607.03948#alg1)in Appendix[B\.1](https://arxiv.org/html/2607.03948#A2.SS1)\.

### 3\.3Projected Online Dual Gradient Descent

Algorithm[1](https://arxiv.org/html/2607.03948#alg1)computes bid prices by solving the convex dual subproblem:

pk∈arg⁡minp≥0⁡fk​\(p\),p\_\{k\}\\in\\arg\\min\_\{p\\geq 0\}\\ f\_\{k\}\(p\),\(7\)wherefk​\(p\)f\_\{k\}\(p\)is defined in Equation \([6](https://arxiv.org/html/2607.03948#S3.E6)\)\. While \([7](https://arxiv.org/html/2607.03948#S3.E7)\) is substantially smaller than the primal LP, solving it to optimality at every decision step can still be nontrivial at millisecond\-scale latency\. We therefore suggest a method based on online gradient descent\(Zinkevich,[2003](https://arxiv.org/html/2607.03948#bib.bib18); Sunet al\.,[2020](https://arxiv.org/html/2607.03948#bib.bib19)\)that updatespkp\_\{k\}frompk−1p\_\{k\-1\}\. This is motivated by the fact that the dual objective evolves smoothly over time: between stepsk−1k\-1andkk, the history set and resource capacities change incrementally\.

#### Warm\-started projected mini\-batch updates\.

At stepkk, we initializep\(0\)←pk−1p^\{\(0\)\}\\leftarrow p\_\{k\-1\}and perform a small fixed numberKKof projected subgradient steps using a mini\-batchℬk⊆𝖧𝗂𝗌𝗍k\\mathcal\{B\}\_\{k\}\\subseteq\\mathsf\{Hist\}\_\{k\}sampled uniformly without replacement:

p\(s\+1\)←Πℝ\+\|ℐ\|​\(p\(s\)−ηk​g^k​\(p\(s\)\)\),p^\{\(s\+1\)\}\\leftarrow\\Pi\_\{\\mathbb\{R\}^\{\|\\mathcal\{I\}\|\}\_\{\+\}\}\\\!\\Big\(p^\{\(s\)\}\-\\eta\_\{k\}\\,\\widehat\{g\}\_\{k\}\(p^\{\(s\)\}\)\\Big\),\(8\)where

g^k​\(p\):=dk−1\|ℬk\|​∑\(r,a\)∈ℬk𝟏​\{r−a⊤​p\>0\}​a,\\widehat\{g\}\_\{k\}\(p\):=d\_\{k\}\-\\frac\{1\}\{\|\\mathcal\{B\}\_\{k\}\|\}\\sum\_\{\(r,a\)\\in\\mathcal\{B\}\_\{k\}\}\\mathbf\{1\}\\\{r\-a^\{\\top\}p\>0\\\}\\,a,fors=0,1,…,K−1s=0,1,\\dots,K\{\-\}1, and outputpk:=p\(K\)p\_\{k\}:=p^\{\(K\)\}\. HereΠℝ\+\|ℐ\|\\Pi\_\{\\mathbb\{R\}^\{\|\\mathcal\{I\}\|\}\_\{\+\}\}denotes projection onto the nonnegative orthant, implemented entrywise as\(⋅\)\+\(\\cdot\)\_\{\+\}\. This first\-order update has short and predictable runtime \(controlled byKKand\|ℬk\|\|\\mathcal\{B\}\_\{k\}\|\) and avoids repeatedly solving \([7](https://arxiv.org/html/2607.03948#S3.E7)\)\.

#### Implementation details\.

In our LLM serving instantiation, the constraint indexi=\(g,k,u\)i=\(g,k,u\)induces a structured price vector with two tensors \(batch\-occupancy and memory\) over\(g,k\)\(g,k\), and we computea⊤​pa^\{\\top\}pefficiently using only the active time slots of each candidate column\. We also apply mild normalization to keep the hinge\-loss gradients numerically stable\. The details are provided in Appendix[B](https://arxiv.org/html/2607.03948#A2)\.

#### Computational overhead and scaling\.

The online routing path does not require solving a full primal LP at any step\. At each period, the dual variable has dimension2​G​T2GT, but updates are highly structured\. Each routing step performs onlyKKwarm\-started projected gradient updates over a mini\-batch sampled from the action history, and the dot product𝐚⊤​𝐩\\mathbf\{a\}^\{\\top\}\\mathbf\{p\}for any candidate column touches only the*active*future slots of that request, so the per\-step cost scales with the number of active candidates times their average decode length rather than the fullG​TGThorizon\. The state itself is summarized byO​\(G​T\)O\(GT\)memory, and the per\-step time complexity isO​\(K​G​H\)O\(KGH\)whereHHis the effective look\-ahead horizon\. Both quantities are linear in cluster size, so the method scales gracefully to larger deployments—each worker’s price tensor can also be updated in parallel since they are decoupled in the gradient step\. In our current implementation, on an Intel i9\-13980HX CPU, the routing computation takes approximately11–22ms per period, comfortably within the1010–3030ms wall\-clock time of a single decode iteration on an A100 GPU\. This confirms that the method meets the millisecond\-scale decision requirements of online LLM serving and is unlikely to be the bottleneck even at6464\+ workers\.

## 4Numerical Experiments

In this section, we present the results of our numerical experiments\. Due to lack of GPU resources, we conducted our experiments using the Vidur simulator\(Agrawalet al\.,[2024a](https://arxiv.org/html/2607.03948#bib.bib22)\), which models realistic LLM serving behavior including continuous batching and KV\-cache management\. While simulation cannot capture all aspects of real deployments, it allows controlled study of routing policies across diverse scenarios\. Our routing algorithm has been integrated into the Vidur simulator, and the code is available at[https://github\.com/qqwetidx/Online\-Linear\-Programming\-for\-Vidur](https://github.com/qqwetidx/Online-Linear-Programming-for-Vidur)\.

### 4\.1Experimental Setup

We simulate a scenario with four parallel NVIDIA A100 GPUs\. To evaluate the performance of our proposed routing algorithm, we consider two types of request distributions:

- •Real Data:We test on a conversational dataset provided by\(Zhenget al\.,[2023a](https://arxiv.org/html/2607.03948#bib.bib33)\), which is publicly available at[https://huggingface\.co/datasets/lmsys/lmsys\-chat\-1m](https://huggingface.co/datasets/lmsys/lmsys-chat-1m)\. The real\-world results are summarized in the main text, with additional experiments available in Appendix[C\.1](https://arxiv.org/html/2607.03948#A3.SS1)\.
- •Synthetic Data:We also simulate requests with varying prefill\-to\-decode \(P/D\) ratios, specifically: \(i\) P/D ratio 1:4 \(more prefill than decode\); \(ii\) P/D ratio 4:1 \(more decode than prefill\)\. These settings simulate different workload patterns, ranging from long prefill phases to long decoding phases\. The results for this synthetic dataset are presented in Appendix[C\.2](https://arxiv.org/html/2607.03948#A3.SS2)\.

For the real dataset, the request arrival process is modeled as a stationary Poisson process, with an arrival rateλ∈\{0\.4,0\.5\}\\lambda\\in\\\{0\.4,0\.5\\\}\. We observe that a rate ofλ=0\.4\\lambda=0\.4ensures system stability, whileλ=0\.5\\lambda=0\.5leads to a slight overload\. Each arriving request is randomly sampled from the dataset\.

### 4\.2Baseline Algorithms and Parameter Settings

We compare the performance of our algorithm against all routing heuristics which are default in the Vidur simulator: \(i\)Round Robin:Requests are cyclically assigned to the GPUs in a fixed order, regardless of the current system state\. \(ii\)Least Outstanding Request \(LOR\):This policy assigns requests to the GPU with the shortest queue\. \(iii\)Random:Requests are randomly assigned to any of the four GPUs with equal probability1/41/4\. \(iv\)Power\-of\-2 Choices:For each incoming request, two GPUs are sampled uniformly at random and the request is assigned to the one with fewer outstanding requests\. This is a widely used randomized load\-balancing heuristic known to improve over both Random and pure shortest\-queue rules in classical parallel\-server settings\.

For our routing algorithm, we conduct experiments with various configurations to examine the effects of prediction accuracy and different objective weightings:

- •Prediction Accuracy:We explore two scenarios for the predicted decode lengtho^j\\hat\{o\}\_\{j\}: \(i\) Perfect Prediction: In some experiments, we assume perfect prediction, whereo^j=oj\\hat\{o\}\_\{j\}=o\_\{j\}\. \(ii\) Imperfect Prediction: In other experiments, we model a more realistic scenario with 20% prediction error, whereo^j∼Unif​\(0\.8⋅oj,1\.2⋅oj\)\\hat\{o\}\_\{j\}\\sim\\text\{Unif\}\(0\.8\\cdot o\_\{j\},1\.2\\cdot o\_\{j\}\)\.
- •Objective Weights:We vary the weightsα,β,γ,σ,ζ1,ζ2\\alpha,\\beta,\\gamma,\\sigma,\\zeta\_\{1\},\\zeta\_\{2\}for the different service\-level objectives \(SLOs\) to observe the algorithm’s performance under different priorities\.

### 4\.3Results

We report sample results on the real\-data setting described in Section[4](https://arxiv.org/html/2607.03948#S4)\. Additional experiments across parameter combinations are deferred to Appendix[C\.1](https://arxiv.org/html/2607.03948#A3.SS1)\.

Table 1:Relative improvement \(%\) over Round\-Robin with noisy decode\-length predictiono^j∼Unif​\(0\.8​oj,1\.2​oj\)\\hat\{o\}\_\{j\}\\sim\\text\{Unif\}\(0\.8o\_\{j\},1\.2o\_\{j\}\)\.#### Real\-data performance under representative multi\-objective settings\.

Figure[2](https://arxiv.org/html/2607.03948#S4.F2)presents two representative configurations: one with perfect decode\-length prediction \(o^j=oj\\hat\{o\}\_\{j\}=o\_\{j\}\) and one with noisy prediction\. In both cases, we choose a relatively large QPS weightσ\\sigmato discourage idling and sustain throughput under load, and we set\(ζ1,ζ2\)\(\\zeta\_\{1\},\\zeta\_\{2\}\)large to emphasize tail\-latency control\. Across both prediction regimes, our router achieves substantially smaller TTFT and tail TTFT than all baselines\. Importantly, from Table[1](https://arxiv.org/html/2607.03948#S4.T1), the advantage persists under noisyo^j\\hat\{o\}\_\{j\}, indicating that the policy is robust to moderate prediction error\.

![Refer to caption](https://arxiv.org/html/2607.03948v1/x1.png)\(a\)λ=0\.4\\lambda=0\.4;\(α,β,γ,σ,ζ1,ζ2\)=\(1135,1400,1400,1,1,1\)\\left\(\\alpha,\\beta,\\gamma,\\sigma,\\zeta\_\{1\},\\zeta\_\{2\}\\right\)=\\left\(\\frac\{1\}\{135\},\\frac\{1\}\{400\},\\frac\{1\}\{400\},1,1,1\\right\);o^j=oj\\hat\{o\}\_\{j\}=o\_\{j\}
![Refer to caption](https://arxiv.org/html/2607.03948v1/x2.png)\(b\)λ=0\.4\\lambda=0\.4;\(α,β,γ,σ,ζ1,ζ2\)=\(127,12048,12048,5,1,1\)\\left\(\\alpha,\\beta,\\gamma,\\sigma,\\zeta\_\{1\},\\zeta\_\{2\}\\right\)=\\left\(\\frac\{1\}\{27\},\\frac\{1\}\{2048\},\\frac\{1\}\{2048\},5,1,1\\right\);o^j∼Unif​\(0\.8​oj,1\.2​oj\)\\hat\{o\}\_\{j\}\\sim\\text\{Unif\}\(0\.8o\_\{j\},1\.2o\_\{j\}\)

Figure 2:Real\-data comparison between routing policies under two representative multi\-objective settings\.
#### Controlling trade\-offs by adjusting objective weights\.

A central advantage of our LP\-based formulation is that it exposes an explicit, interpretable knob for trading off competing SLOs\. Figure[3](https://arxiv.org/html/2607.03948#S4.F3)illustrates this effect by considering two extreme weight choices\. In the first setting, we emphasize average latency by setting\(α,β,γ,σ,ζ1,ζ2\)=\(0,1,1,0,0,0\)\(\\alpha,\\beta,\\gamma,\\sigma,\\zeta\_\{1\},\\zeta\_\{2\}\)=\(0,1,1,0,0,0\), which substantially reduces average end\-to\-end latency and average TTFT, but can worsen tail metrics because the policy is not incentivized to protect the slowest requests\. In the second setting, we emphasize tail control via\(α,β,γ,σ,ζ1,ζ2\)=\(0,0,0,0,1,1\)\(\\alpha,\\beta,\\gamma,\\sigma,\\zeta\_\{1\},\\zeta\_\{2\}\)=\(0,0,0,0,1,1\), which markedly improves tail end\-to\-end latency and tail TTFT\.

![Refer to caption](https://arxiv.org/html/2607.03948v1/x3.png)\(a\)λ=0\.5\\lambda=0\.5;\(α,β,γ,σ,ζ1,ζ2\)=\(0,1,1,0,0,0\)\\left\(\\alpha,\\beta,\\gamma,\\sigma,\\zeta\_\{1\},\\zeta\_\{2\}\\right\)=\(0,1,1,0,0,0\);o^j=oj\\hat\{o\}\_\{j\}=o\_\{j\}
![Refer to caption](https://arxiv.org/html/2607.03948v1/x4.png)\(b\)λ=0\.4\\lambda=0\.4;\(α,β,γ,σ,ζ1,ζ2\)=\(0,0,0,0,1,1\)\\left\(\\alpha,\\beta,\\gamma,\\sigma,\\zeta\_\{1\},\\zeta\_\{2\}\\right\)=\(0,0,0,0,1,1\);o^j∼Unif​\(0\.8​oj,1\.2​oj\)\\hat\{o\}\_\{j\}\\sim\\text\{Unif\}\(0\.8o\_\{j\},1\.2o\_\{j\}\)

Figure 3:Real\-data comparison illustrating how objective weights shift performance trade\-offs\.
#### Robustness to non\-stationary workloads\.

A natural concern with any router that learns from historical arrivals is whether it can adapt when the workload distribution shifts\. To stress\-test our policy, we run a rate\-shift experiment in which the Poisson arrival rate switches fromλ=0\.4\\lambda=0\.4toλ=0\.6\\lambda=0\.6at the simulation midpoint, simulating a sudden load spike\. The router is*not*informed of either the shift point or the new rate\. To handle this online, we equip the SAA\-style price update with a simple rolling\-window mechanism: we monitor the empirical arrival rate over a sliding window and, when a statistically significant increase is detected, we discard stale history samples and re\-estimate using only recent observations\. This integrates naturally with the warm\-started projected gradient descent, since the dual prices are already updated incrementally rather than recomputed from scratch\. Table[2](https://arxiv.org/html/2607.03948#S4.T2)reports the relative improvement of each method over Round Robin under this non\-stationary protocol with noisy decode\-length prediction\.

Table 2:Relative improvement \(%\) over Round Robin under a non\-stationary rate\-shift workload \(Poisson rate switches fromλ=0\.4\\lambda=0\.4toλ=0\.6\\lambda=0\.6at the midpoint; router uninformed of the shift\)\. Decode lengths are noisy:o^j∼Unif​\(0\.8​oj,1\.2​oj\)\\hat\{o\}\_\{j\}\\sim\\text\{Unif\}\(0\.8o\_\{j\},1\.2o\_\{j\}\)\.

## 5Discussion

Beyond algorithmic improvements, our LP framework provides structural insights about LLM routing and suggests directions for future system design\.

#### What the framework reveals\.

First, shadow prices serve as*congestion signals*: they reveal which resources—batch slots versus KV\-cache memory—are bottlenecks under different workloads\. In decode\-heavy scenarios with long output sequences, memory prices dominate; in high\-arrival\-rate scenarios, batch prices dominate\. This diagnostic information is unavailable from heuristic routers\. Second, the framework exposes the*trade\-off structure*between competing SLOs: varying objective weights traces the Pareto frontier between throughput and latency, enabling systematic capacity planning rather than ad\-hoc tuning\. Third, our experiments demonstrate*robustness to prediction error*: the bid\-price mechanism degrades gracefully under inaccurate decode\-length predictions because prices adapt online, whereas fixed heuristics cannot adjust to prediction errors\.

#### Implications for system design\.

Our framework suggests several directions for practitioners\. The shadow\-price mechanism could be integrated with real\-time telemetry \(queue depths, memory utilization\) for adaptive routing that responds to transient congestion\. During overload, the framework naturally supports SLO\-aware admission control: requests whose SLO contribution falls below their resource cost can be delayed or rejected, prioritizing high\-value traffic\. The formulation also extends naturally to heterogeneous GPU fleets by specifying device\-specific capacity constraints\(Bg,Mg\)\(B\_\{g\},M\_\{g\}\), enabling unified routing across mixed hardware\.

#### When does optimization help most?

Our experiments suggest the framework provides the largest benefits when \(i\) decode lengths are long and variable, so time\-coupled constraints bind; \(ii\) multiple SLOs are genuinely in tension; and \(iii\) the system operates near full capacity\. For light loads or very short decodes, simple heuristics often suffice—a regime our framework identifies through near\-zero shadow prices\. This characterization helps practitioners decide when optimization\-based routing is worth the added complexity\.

## 6Limitations and Future Directions

Our validation relies on simulation using the Vidur framework; real system implementation would face additional challenges including integration with serving engines \(e\.g\., vLLM\), handling of preemption and KV\-cache swapping, and coordination overhead in distributed deployments\. Addressing these engineering challenges and validating performance on production workloads is an important direction for future work\.

The current framework also assumes homogeneous request priorities and does not explicitly model fairness across users or request classes\. Extending the objective to incorporate priority tiers, fairness constraints, and load\-balancing considerations—while preserving computational efficiency—is a natural next step\. More broadly, we hope this work demonstrates the value of bringing principled optimization methodology to LLM serving and provides a foundation for future research at the intersection of operations research and machine learning systems\.

## Impact Statement

From a methodological perspective, our work establishes the first multi\-objective optimization framework for LLM request routing, formulating the problem as online linear programming with time\-coupled capacity constraints\. This provides a principled bridge between the operations research community—where online resource allocation and bid\-price control are well\-studied—and the LLM serving systems community, where routing decisions have largely relied on heuristics designed for classical settings\. Beyond any specific algorithmic improvements, the framework offers interpretable tools for systematic policy design: objective weights that transparently control SLO trade\-offs, and shadow prices that diagnose capacity bottlenecks\. We hope this work demonstrates the value of bringing optimization methodology to emerging LLM systems challenges and provides a foundation for future research at this intersection\.

## References

- A\. Agrawal, N\. Kedia, J\. Mohan, A\. Panwar, N\. Kwatra, B\. Gulavani, R\. Ramjee, and A\. Tumanov \(2024a\)Vidur: a large\-scale simulation framework for LLM inference\.Proceedings of Machine Learning and Systems6,pp\. 351–366\.Cited by:[§1](https://arxiv.org/html/2607.03948#S1.p3.1),[§1](https://arxiv.org/html/2607.03948#S1.p6.1),[§4](https://arxiv.org/html/2607.03948#S4.p1.1)\.
- A\. Agrawal, N\. Kedia, A\. Panwar, J\. Mohan, N\. Kwatra, B\. S\. Gulavani, A\. Tumanov, and R\. Ramjee \(2024b\)Taming throughput\-latency tradeoff in LLM inference with Sarathi\-Serve\.arXiv preprint arXiv:2403\.02310\.Cited by:[§1](https://arxiv.org/html/2607.03948#S1.p1.1)\.
- S\. Agrawal, Z\. Wang, and Y\. Ye \(2014\)A dynamic near\-optimal algorithm for online linear programming\.Operations Research62\(4\),pp\. 876–890\.Cited by:[§1](https://arxiv.org/html/2607.03948#S1.p4.1),[§3\.2](https://arxiv.org/html/2607.03948#S3.SS2.p1.1)\.
- M\. Akan and B\. Ata \(2009\)Bid\-price controls for network revenue management: martingale characterization of optimal bid prices\.Mathematics of Operations Research34\(4\),pp\. 912–936\.Cited by:[§1](https://arxiv.org/html/2607.03948#S1.p4.1),[§3\.2](https://arxiv.org/html/2607.03948#S3.SS2.p1.1)\.
- S\. Chen, R\. Jiang, D\. Yu, J\. Xu, M\. Chao, F\. Meng, C\. Jiang, W\. Xu, and H\. Liu \(2024\)KVDirect: distributed disaggregated llm inference\.arXiv preprint arXiv:2501\.14743\.Cited by:[§2](https://arxiv.org/html/2607.03948#S2.SS0.SSS0.Px1.p1.9)\.
- Y\. Fu, S\. Zhu, R\. Su, A\. Qiao, I\. Stoica, and H\. Zhang \(2024\)Efficient llm scheduling by learning to rank\.arXiv preprint arXiv:2408\.15792\.Cited by:[§1](https://arxiv.org/html/2607.03948#S1.p3.1),[§2](https://arxiv.org/html/2607.03948#S2.SS0.SSS0.Px1.p1.9)\.
- K\. Jain, A\. Parayil, A\. Mallick, E\. Choukse, X\. Qin, J\. Zhang, Í\. Goiri, R\. Wang, C\. Bansal, V\. Rühle,et al\.\(2024\)Intelligent router for llm workloads: improving performance through workload\-aware scheduling\.arXiv preprint arXiv:2408\.13510\.Cited by:[§1](https://arxiv.org/html/2607.03948#S1.p1.1),[§1](https://arxiv.org/html/2607.03948#S1.p3.1),[§2](https://arxiv.org/html/2607.03948#S2.SS0.SSS0.Px6.p2.1)\.
- W\. Kwon, Z\. Li, S\. Zhuang, Y\. Sheng, L\. Zheng, C\. H\. Yu, J\. Gonzalez, H\. Zhang, and I\. Stoica \(2023\)Efficient memory management for large language model serving with pagedattention\.InProceedings of the 29th Symposium on Operating Systems Principles,pp\. 611–626\.Cited by:[§1](https://arxiv.org/html/2607.03948#S1.p1.1),[§1](https://arxiv.org/html/2607.03948#S1.p3.1),[§2](https://arxiv.org/html/2607.03948#S2.SS0.SSS0.Px4.p1.3)\.
- P\. Langley \(2000\)Crafting papers on machine learning\.InProceedings of the 17th International Conference on Machine Learning \(ICML 2000\),P\. Langley \(Ed\.\),Stanford, CA,pp\. 1207–1216\.Cited by:[§C\.2](https://arxiv.org/html/2607.03948#A3.SS2.SSS0.Px2.p2.1)\.
- X\. Li, C\. Sun, and Y\. Ye \(2020\)Simple and fast algorithm for binary integer and online linear programming\.Advances in Neural Information Processing Systems33,pp\. 9412–9421\.Cited by:[§1](https://arxiv.org/html/2607.03948#S1.p4.1)\.
- X\. Li and Y\. Ye \(2022\)Online linear programming: dual convergence, new algorithms, and regret bounds\.Operations Research70\(5\),pp\. 2948–2966\.Cited by:[§1](https://arxiv.org/html/2607.03948#S1.p4.1),[§3\.2](https://arxiv.org/html/2607.03948#S3.SS2.p1.1)\.
- D\. G\. Luenberger, Y\. Ye,et al\.\(1984\)Linear and nonlinear programming\.Vol\.2,Springer\.Cited by:[§1](https://arxiv.org/html/2607.03948#S1.p4.1)\.
- K\. Mei, W\. Xu, M\. Guo, S\. Lin, and Y\. Zhang \(2025\)Omnirouter: budget and performance controllable multi\-llm routing\.ACM SIGKDD Explorations Newsletter27\(2\),pp\. 107–116\.Cited by:[§1](https://arxiv.org/html/2607.03948#S1.p1.1),[§1](https://arxiv.org/html/2607.03948#S1.p3.1)\.
- R\. Pope, S\. Douglas, A\. Chowdhery, J\. Devlin, J\. Bradbury, J\. Heek, K\. Xiao, S\. Agrawal, and J\. Dean \(2023\)Efficiently scaling transformer inference\.Proceedings of Machine Learning and Systems5,pp\. 606–624\.Cited by:[§1](https://arxiv.org/html/2607.03948#S1.p1.1)\.
- H\. Qiu, W\. Mao, A\. Patke, S\. Cui, S\. Jha, C\. Wang, H\. Franke, Z\. T\. Kalbarczyk, T\. Başar, and R\. K\. Iyer \(2024\)Efficient interactive llm serving with proxy model\-based sequence length prediction\.arXiv preprint arXiv:2404\.08509\.Cited by:[§1](https://arxiv.org/html/2607.03948#S1.p3.1),[§2](https://arxiv.org/html/2607.03948#S2.SS0.SSS0.Px1.p1.9)\.
- E\. Roth \(2025\)OpenAI says chatgpt users send over 2\.5 billion prompts every day\.https://www\.theverge\.com/news/710867/openai\-chatgpt\-daily\-prompts\-2\-billionutmsource=chatgpt\.com\.External Links:[Link](https://www.theverge.com/news/710867/openai-chatgpt-daily-prompts-2-billion?utm_source=chatgpt.com)Cited by:[§1](https://arxiv.org/html/2607.03948#S1.p1.1)\.
- R\. Shahout, E\. Malach, C\. Liu, W\. Jiang, M\. Yu, and M\. Mitzenmacher \(2024\)Don’t stop me now: embedding based scheduling for llms\.arXiv preprint arXiv:2410\.01035\.Cited by:[§1](https://arxiv.org/html/2607.03948#S1.p3.1),[§2](https://arxiv.org/html/2607.03948#S2.SS0.SSS0.Px1.p1.9)\.
- Y\. Sheng, L\. Zheng, B\. Yuan, Z\. Li, M\. Ryabinin, B\. Chen, P\. Liang, C\. Ré, I\. Stoica, and C\. Zhang \(2023\)Flexgen: high\-throughput generative inference of large language models with a single GPU\.InInternational Conference on Machine Learning,pp\. 31094–31116\.Cited by:[§1](https://arxiv.org/html/2607.03948#S1.p1.1)\.
- R\. Sun, X\. Wang, and Z\. Zhou \(2020\)Near\-optimal primal\-dual algorithms for quantity\-based network revenue management\.arXiv preprint arXiv:2011\.06327\.Cited by:[§3\.3](https://arxiv.org/html/2607.03948#S3.SS3.p1.5)\.
- K\. Talluri and G\. Van Ryzin \(1998\)An analysis of bid\-price controls for network revenue management\.Management science44\(11\-part\-1\),pp\. 1577–1593\.Cited by:[§1](https://arxiv.org/html/2607.03948#S1.p4.1),[§3\.2](https://arxiv.org/html/2607.03948#S3.SS2.p1.1)\.
- vLLM Project \(2025\)Data Parallel Deployment \(internal load balancing\)\.Note:vLLM Documentation \(latest developer preview\)Page shows date Dec 13, 2025\. Accessed: 2026\-01\-18External Links:[Link](https://docs.vllm.ai/en/latest/serving/data_parallel_deployment/#internal-load-balancing)Cited by:[§2](https://arxiv.org/html/2607.03948#S2.SS0.SSS0.Px2.p1.3)\.
- vLLM Roadmap \(2025\)\[Roadmap\] vLLM Production Stack roadmap for 2025 Q2 \(issue \#300\)\.Note:GitHub issue, vllm\-project/production\-stackOpened Mar 17, 2025\. Accessed: 2026\-01\-18External Links:[Link](https://github.com/vllm-project/production-stack/issues/300)Cited by:[§2](https://arxiv.org/html/2607.03948#S2.SS0.SSS0.Px2.p1.3)\.
- F\. Wu and S\. Silwal \(2025\)Efficient training\-free online routing for high\-volume multi\-llm serving\.arXiv preprint arXiv:2509\.02718\.Cited by:[§1](https://arxiv.org/html/2607.03948#S1.p1.1),[§1](https://arxiv.org/html/2607.03948#S1.p3.1)\.
- L\. Zheng, W\. Chiang, Y\. Sheng, T\. Li, S\. Zhuang, Z\. Wu, Y\. Zhuang, Z\. Li, Z\. Lin, E\. Xing,et al\.\(2023a\)LMSYS\-Chat\-1M: a large\-scale real\-world LLM conversation dataset\.arXiv preprint arXiv:2309\.11998\.Cited by:[1st item](https://arxiv.org/html/2607.03948#S4.I1.i1.p1.1)\.
- Z\. Zheng, X\. Ren, F\. Xue, Y\. Luo, X\. Jiang, and Y\. You \(2023b\)Response length perception and sequence scheduling: an llm\-empowered llm inference pipeline\.Advances in Neural Information Processing Systems36,pp\. 65517–65530\.Cited by:[§1](https://arxiv.org/html/2607.03948#S1.p3.1),[§2](https://arxiv.org/html/2607.03948#S2.SS0.SSS0.Px1.p1.9)\.
- Y\. Zhong, S\. Liu, J\. Chen, J\. Hu, Y\. Zhu, X\. Liu, X\. Jin, and H\. Zhang \(2024\)Distserve: disaggregating prefill and decoding for goodput\-optimized large language model serving\.arXiv preprint arXiv:2401\.09670\.Cited by:[§2](https://arxiv.org/html/2607.03948#S2.p1.1)\.
- M\. Zinkevich \(2003\)Online convex programming and generalized infinitesimal gradient ascent\.InProceedings of the 20th international conference on machine learning \(icml\-03\),pp\. 928–936\.Cited by:[§3\.3](https://arxiv.org/html/2607.03948#S3.SS3.p1.5)\.

## Appendix ASupplementary Materials for Section[2](https://arxiv.org/html/2607.03948#S2)

#### Overview\.

Section[2](https://arxiv.org/html/2607.03948#S2)considers PD disaggregation: prefill is completed upstream and each decode device only performs decoding\. We now sketch an extension to*PD mixing*, where each device may process both prefill and decode and continuous batching interleaves them within the same iteration\.

#### Requests and routing\.

Requests arrive at timestjt\_\{j\}with known prompt lengthsjs\_\{j\}and unknown decode lengthojo\_\{j\}\(with predictiono^j\\hat\{o\}\_\{j\}\)\. The router selects a deviceggand a dispatch periodτ≥tj\\tau\\geq t\_\{j\}using the same decision variablexj,g,τx\_\{j,g,\\tau\}\.

#### Mixed service discipline\.

After dispatch, requestjjjoins the FIFO queue of devicegg\. When admitted into the active batch, it first undergoes a prefill step \(materializing KV states for the prompt\) and then executesojo\_\{j\}decode steps\. In a PD\-mixing engine, a batch at a given period may contain requests in their prefill step and requests in decoding; we treat one such engine iteration as one time period in the model\.

#### KV\-cache memory accounting\.

Letθ\\thetadenote the service step index of requestjjsince it becomes active on a device, whereθ=0\\theta=0corresponds to its prefill step andθ=1,…,oj\\theta=1,\\dots,o\_\{j\}correspond to its decode steps \(generating theθ\\thetath output token\)\. We approximate that the prefill step allocates the full prompt KV\-cache footprint at once\. The resulting memory\-usage kernel becomes

mjmem​\(θ\)=\{sj,θ=0,sj\+θ,1≤θ≤oj,0,otherwise\.m^\{\\text\{mem\}\}\_\{j\}\(\\theta\)=\\begin\{cases\}s\_\{j\},&\\theta=0,\\\\ s\_\{j\}\+\\theta,&1\\leq\\theta\\leq o\_\{j\},\\\\ 0,&\\text\{otherwise\}\.\\end\{cases\}Compared with Section[2](https://arxiv.org/html/2607.03948#S2), the only change is the additional prefill stepθ=0\\theta=0, whose memory cost issjs\_\{j\}\. \(A finer\-grained*chunked prefill*model can be obtained by splitting prefill into multiple steps, but we use the above abstraction for clarity\.\)

#### Feasibility constraints\.

The same constraints apply to mixed batches: at any period, each device hosts at mostBBactive requests \(counting both prefill and decode\), and the total KV\-cache usage of active requests must not exceedMM\.

#### Token accounting\.

In Section[2](https://arxiv.org/html/2607.03948#S2), all processed tokens are decode tokens\. Under PD mixing, devices also process prompt tokens during prefill\. When reporting throughput, one may either count only generated \(decode\) tokens, or count both prompt and generated tokens; both conventions appear in practice\. Our formulations and algorithms apply under either convention once the corresponding token count is used consistently\.

#### Latency metrics under mixing\.

Under PD mixing, TTFT and TEL naturally include both prefill and decode waiting/processing time, because the first output token cannot be produced until the request completes its prefill step and begins decoding\. The definitions in Section[2](https://arxiv.org/html/2607.03948#S2)remain valid iftjt\_\{j\}is interpreted as the original request arrival time before prefill andτj\\tau\_\{j\}as the period when the first output token is generated\.

#### Algorithmic adjustments\.

All changes to the online LP algorithm are conceptual substitutions of the decode\-only model components by their mixed counterparts\. Under the above abstraction, each request consumes\(1\+o^j\)\(1\+\\hat\{o\}\_\{j\}\)service steps on its assigned device \(one prefill step pluso^j\\hat\{o\}\_\{j\}predicted decode steps\), and all per\-device capacity constraints are enforced using the modified memory kernelmjmem​\(⋅\)m^\{\\text\{mem\}\}\_\{j\}\(\\cdot\)\.

#### Batch\-time variability and implications\.

A key difference from PD disaggregation is that the wall\-clock duration of a mixed batch iteration is input\-dependent: it varies with the composition of prefill versus decode work and with prompt lengths\. Consequently, it is difficult to map the period\-indexed model to real time with a single, accurate conversion factor\. Our online LP algorithm can still be applied by treating each iteration as one abstract period and using workload predictions \(e\.g\.,o^j\\hat\{o\}\_\{j\}andsjs\_\{j\}\) for planning; however, because the per\-iteration runtime is harder to quantify under PD mixing, the realized performance may be less stable\.

## Appendix BSupplementary Materials for Section[3](https://arxiv.org/html/2607.03948#S3)

### B\.1Vectorization: batch\-occupancy and memory prices

In this part, we provide the pseudocode of our algorithm\.

Algorithm 1Action\-History\-Dependent \(AHD\) Bid Price Control Router1:Input:initial resource capacities

b\(0\)∈ℝ\+\|ℐ\|b^\{\(0\)\}\\in\\mathbb\{R\}^\{\|\\mathcal\{I\}\|\}\_\{\+\}indexed by

i=\(g,s,u\)∈ℐi=\(g,s,u\)\\in\\mathcal\{I\}; horizon

TT; reward/column generator for

\(rj,g,k,a\(j,g,k\)\)\(r\_\{j,g,k\},a\_\{\(j,g,k\)\}\); weights

\(α,β,γ,σ,ζ1,ζ2\)\(\\alpha,\\beta,\\gamma,\\sigma,\\zeta\_\{1\},\\zeta\_\{2\}\)\.

2:Output:decisions

\{xj,g,k\}k∈\[T\],j,g\\\{x\_\{j,g,k\}\\\}\_\{k\\in\[T\],\\,j,\\,g\}\.

3:Initialize history

𝖧𝗂𝗌𝗍←∅\\mathsf\{Hist\}\\leftarrow\\emptysetand waiting queue

𝒥1\(w​a​i​t\)←∅\\mathcal\{J\}^\{\(wait\)\}\_\{1\}\\leftarrow\\emptyset\.

4:for

k=1,2,…,Tk=1,2,\\dots,Tdo

5:Update waiting set

𝒥k\(w​a​i​t\)\\mathcal\{J\}^\{\(wait\)\}\_\{k\}by adding new arrivals at time

kkand removing any requests started at time

k−1k\{\-\}1\.

6:Define action set

𝒜k←\{\(j,g,k\):j∈𝒥k\(w​a​i​t\),g∈\[G\]\}\\mathcal\{A\}\_\{k\}\\leftarrow\\\{\(j,g,k\):j\\in\\mathcal\{J\}^\{\(wait\)\}\_\{k\},\\ g\\in\[G\]\\\}and initialize

xj,g,k←0x\_\{j,g,k\}\\leftarrow 0for all

\(j,g,k\)∈𝒜k\(j,g,k\)\\in\\mathcal\{A\}\_\{k\}\.

7:Dual price update \(SAA over history\):

pk∈arg⁡minp≥0⁡fk​\(p\),p\_\{k\}\\in\\arg\\min\_\{p\\geq 0\}\\ f\_\{k\}\(p\),\(9\)where

fk​\(p\)f\_\{k\}\(p\)is defined in Equation \([6](https://arxiv.org/html/2607.03948#S3.E6)\)\.

8:Bid\-price margins:For all

\(j,g,k\)∈𝒜k\(j,g,k\)\\in\\mathcal\{A\}\_\{k\}, compute

Δj​\(g\)←rj,g,k−a\(j,g,k\)⊤​pk\\Delta\_\{j\}\(g\)\\leftarrow r\_\{j,g,k\}\-a\_\{\(j,g,k\)\}^\{\\top\}p\_\{k\}\.

9:Update record for next\-step learning:if

𝒜k≠∅\\mathcal\{A\}\_\{k\}\\neq\\emptyset, pick

\(j⋆,g⋆\)∈arg⁡max\(j,g,k\)∈𝒜k⁡Δj​\(g\)\(j^\{\\star\},g^\{\\star\}\)\\in\\arg\\max\_\{\(j,g,k\)\\in\\mathcal\{A\}\_\{k\}\}\\Delta\_\{j\}\(g\)and set

𝖧𝗂𝗌𝗍←𝖧𝗂𝗌𝗍∪\{\(rj⋆,g⋆,k,a\(j⋆,g⋆,k\)\)\}\\mathsf\{Hist\}\\leftarrow\\mathsf\{Hist\}\\cup\\\{\(r\_\{j^\{\\star\},g^\{\\star\},k\},a\_\{\(j^\{\\star\},g^\{\\star\},k\)\}\)\\\}\.

10:Greedy admission \(bid\-price control\):initialize working residuals

b\(k\)←b\(k−1\)b^\{\(k\)\}\\leftarrow b^\{\(k\-1\)\}\.

11:Let

𝒞k←\{\(j,g,k\)∈𝒜k:Δj​\(g\)\>0\}\\mathcal\{C\}\_\{k\}\\leftarrow\\\{\(j,g,k\)\\in\\mathcal\{A\}\_\{k\}:\\ \\Delta\_\{j\}\(g\)\>0\\\}sorted by decreasing

Δj​\(g\)\\Delta\_\{j\}\(g\)\.

12:foreach

\(j,g,k\)∈𝒞k\(j,g,k\)\\in\\mathcal\{C\}\_\{k\}\(in sorted order\)do

13:if

ai,\(j,g,k\)≤bi\(k\)a\_\{i,\(j,g,k\)\}\\leq b^\{\(k\)\}\_\{i\}for all

i∈ℐi\\in\\mathcal\{I\}then

14:set

xj,g,k←1x\_\{j,g,k\}\\leftarrow 1and update

b\(k\)←b\(k\)−a\(⋅,\(j,g,k\)\)b^\{\(k\)\}\\leftarrow b^\{\(k\)\}\-a\_\{\(\\cdot,\(j,g,k\)\)\}\.

15:end if

16:endfor

17:endfor

### B\.2Vectorization: batch\-occupancy and memory prices

In the fixed\-horizon LLM instantiation, constraints are indexed by deviceg∈\[G\]g\\in\[G\], time slotk∈\[T\]k\\in\[T\], and typeu∈\{bat,mem\}u\\in\\\{\\textsf\{bat\},\\textsf\{mem\}\\\}\. Accordingly, we maintain two nonnegative price tensors

pg,kbat≥0,pg,kmem≥0,p^\{\\textsf\{bat\}\}\_\{g,k\}\\geq 0,\\qquad p^\{\\textsf\{mem\}\}\_\{g,k\}\\geq 0,and flatten them into a single vector

p≡vec​\(pbat,pmem\)∈ℝ\+2​G​T≡ℝ\+\|ℐ\|\.p\\equiv\\mathrm\{vec\}\\\!\\big\(p^\{\\textsf\{bat\}\},p^\{\\textsf\{mem\}\}\\big\)\\in\\mathbb\{R\}^\{2GT\}\_\{\+\}\\equiv\\mathbb\{R\}^\{\|\\mathcal\{I\}\|\}\_\{\+\}\.
#### Efficient evaluation ofa⊤​pa^\{\\top\}pfor a candidate column\.

Consider a candidate action\(j,g,k\)\(j,g,k\)\(start requestjjon deviceggat decision stepkk\)\. Its column vectora\(j,g,k\)a\_\{\(j,g,k\)\}has nonzeros only on indices with the same deviceggand future time slotsk′≥kk^\{\\prime\}\\geq kwhere the request is active\. Let

𝒦j,k:=\{k′∈\[T\]:aj​\(k′−k\)=1\}\\mathcal\{K\}\_\{j,k\}:=\\\{\\,k^\{\\prime\}\\in\[T\]:a\_\{j\}\(k^\{\\prime\}\-k\)=1\\,\\\}denote the active slots of requestjjif started atkk\. Then the dot product decomposes as

a\(j,g,k\)⊤​p=∑k′∈𝒦j,kpg,k′bat\+∑k′∈𝒦j,kpg,k′mem⋅m~j​\(k′−k\),a\_\{\(j,g,k\)\}^\{\\top\}p\\;=\\;\\sum\_\{k^\{\\prime\}\\in\\mathcal\{K\}\_\{j,k\}\}p^\{\\textsf\{bat\}\}\_\{g,k^\{\\prime\}\}\\;\+\\;\\sum\_\{k^\{\\prime\}\\in\\mathcal\{K\}\_\{j,k\}\}p^\{\\textsf\{mem\}\}\_\{g,k^\{\\prime\}\}\\cdot\\widetilde\{m\}\_\{j\}\(k^\{\\prime\}\-k\),\(10\)wherem~j​\(⋅\)\\widetilde\{m\}\_\{j\}\(\\cdot\)is a per\-slot memory multiplier derived frommjmem​\(⋅\)m^\{\\text\{mem\}\}\_\{j\}\(\\cdot\)\. In code, we store the active index set𝒦j,k\\mathcal\{K\}\_\{j,k\}and the corresponding memory multipliers to avoid materializing the full2​G​T2GT\-dimensional column\.

#### Reward and memory scaling\.

To stabilize hinge gradients, the implementation may apply \(i\) reward normalization and \(ii\) memory scaling:

rnorm:=min⁡\{rreward\_normalizer,1\},m~j​\(⋅\):=mem\_scale⋅mjmem​\(⋅\),r^\{\\textsf\{norm\}\}\\;:=\\;\\min\\Big\\\{\\frac\{r\}\{\\texttt\{reward\\\_normalizer\}\},\\,1\\Big\\\},\\qquad\\widetilde\{m\}\_\{j\}\(\\cdot\)\\;:=\\;\\texttt\{mem\\\_scale\}\\cdot m^\{\\text\{mem\}\}\_\{j\}\(\\cdot\),wheremem\_scaleis a fixed constant \(e\.g\., proportional to1/maxg,s⁡Mg,s1/\\max\_\{g,s\}M\_\{g,s\}\) to keep the two resource types commensurate\.

#### Constructing the scarcity vectordkd\_\{k\}\.

At decision stepkk, we form remaining capacities per device and slot:

remainbat:=\(B−occbat\)\+,remainmem:=\(M−occmem\)\+,\\mathrm\{remain\}^\{\\textsf\{bat\}\}:=\\big\(B\-\\mathrm\{occ\}^\{\\textsf\{bat\}\}\\big\)\_\{\+\},\\qquad\\mathrm\{remain\}^\{\\textsf\{mem\}\}:=\\big\(M\-\\mathrm\{occ\}^\{\\textsf\{mem\}\}\\big\)\_\{\+\},divide by an estimate of remaining arrivalsn^remain​\(k\)\\widehat\{n\}\_\{\\mathrm\{remain\}\}\(k\), and flatten:

dk=1max⁡\{1,n^remain​\(k\)\}​vec​\(remainbat,mem\_scale⋅remainmem\),d\_\{k\}\\;=\\;\\frac\{1\}\{\\max\\\{1,\\widehat\{n\}\_\{\\mathrm\{remain\}\}\(k\)\\\}\}\\,\\mathrm\{vec\}\\\!\\Big\(\\mathrm\{remain\}^\{\\textsf\{bat\}\},\\ \\texttt\{mem\\\_scale\}\\cdot\\mathrm\{remain\}^\{\\textsf\{mem\}\}\\Big\),\(11\)\(optionally with the samereward\_normalizerscaling applied as above\)\.

### B\.3Projected mini\-batch subgradient routine for the price update

Algorithm 2ResolveDualPrices\(dk,𝖧𝗂𝗌𝗍k,pk−1\)\(d\_\{k\},\\mathsf\{Hist\}\_\{k\},p\_\{k\-1\}\): projected mini\-batch subgradient for \([6](https://arxiv.org/html/2607.03948#S3.E6)\)1:Input:scarcity vector

dk∈ℝ\+\|ℐ\|d\_\{k\}\\in\\mathbb\{R\}^\{\|\\mathcal\{I\}\|\}\_\{\+\}; history

𝖧𝗂𝗌𝗍k=\{\(rℓ,aℓ\)\}ℓ=1Nk\\mathsf\{Hist\}\_\{k\}=\\\{\(r\_\{\\ell\},a\_\{\\ell\}\)\\\}\_\{\\ell=1\}^\{N\_\{k\}\}; warm start

pk−1∈ℝ\+\|ℐ\|p\_\{k\-1\}\\in\\mathbb\{R\}^\{\|\\mathcal\{I\}\|\}\_\{\+\}; step size

ηk\>0\\eta\_\{k\}\>0; steps

KK; batch size

BB\.

2:Output:updated dual prices

pk∈ℝ\+\|ℐ\|p\_\{k\}\\in\\mathbb\{R\}^\{\|\\mathcal\{I\}\|\}\_\{\+\}\.

3:if

Nk=0N\_\{k\}=0then

4:

pk←0p\_\{k\}\\leftarrow 0\.

5:return\.

6:endif

7:

B←min⁡\{B,Nk\}B\\leftarrow\\min\\\{B,N\_\{k\}\\\}\.

8:

p←pk−1p\\leftarrow p\_\{k\-1\}\.

9:for

s=1,2,…,Ks=1,2,\\dots,Kdo

10:Sample

ℬ⊆\{1,…,Nk\}\\mathcal\{B\}\\subseteq\\\{1,\\dots,N\_\{k\}\\\}uniformly without replacement,

\|ℬ\|=B\|\\mathcal\{B\}\|=B\.

11:

g^←dk\\widehat\{g\}\\leftarrow d\_\{k\}\.

12:foreach

ℓ∈ℬ\\ell\\in\\mathcal\{B\}do

13:Compute margin

Δℓ←rℓ−aℓ⊤​p\\Delta\_\{\\ell\}\\leftarrow r\_\{\\ell\}\-a\_\{\\ell\}^\{\\top\}p\(via \([10](https://arxiv.org/html/2607.03948#A2.E10)\)\)\.

14:if

Δℓ\>0\\Delta\_\{\\ell\}\>0then

15:

g^←g^−1B​aℓ\\widehat\{g\}\\leftarrow\\widehat\{g\}\-\\frac\{1\}\{B\}\\,a\_\{\\ell\}\.

16:endif

17:endfor

18:

p←\(p−ηk​g^\)\+p\\leftarrow\(p\-\\eta\_\{k\}\\,\\widehat\{g\}\)\_\{\+\}\{projection onto

ℝ\+\|ℐ\|\\mathbb\{R\}^\{\|\\mathcal\{I\}\|\}\_\{\+\}\}

19:endfor

20:

pk←pp\_\{k\}\\leftarrow p\.

21:return\.

### B\.4How samples enter𝖧𝗂𝗌𝗍k\\mathsf\{Hist\}\_\{k\}in the online loop

To keep the history compact, we record a small number of informative columns per decision step\. A simple choice \(used in our simulator\) is to record one column corresponding to the largest instantaneous margin under current prices:

\(j⋆,g⋆\)∈arg⁡max\(j,g,k\)∈𝒜k⁡\{rj,g,k−a\(j,g,k\)⊤​pk\},𝖧𝗂𝗌𝗍k\+1←𝖧𝗂𝗌𝗍k∪\{\(rj⋆,g⋆,k,a\(j⋆,g⋆,k\)\)\}\.\(j^\{\\star\},g^\{\\star\}\)\\in\\arg\\max\_\{\(j,g,k\)\\in\\mathcal\{A\}\_\{k\}\}\\ \\Big\\\{\\,r\_\{j,g,k\}\-a\_\{\(j,g,k\)\}^\{\\top\}p\_\{k\}\\Big\\\},\\qquad\\mathsf\{Hist\}\_\{k\+1\}\\leftarrow\\mathsf\{Hist\}\_\{k\}\\cup\\\{\(r\_\{j^\{\\star\},g^\{\\star\},k\},a\_\{\(j^\{\\star\},g^\{\\star\},k\)\}\)\\\}\.This design focuses the dual updates on the most competitive placement options under the current price vector while keeping the per\-step learning overhead small\.

## Appendix CSupplementary Materials for Section[4](https://arxiv.org/html/2607.03948#S4)

### C\.1Experiments on Real Dataset

#### Results under perfect decode\-length prediction\.

Figures[4](https://arxiv.org/html/2607.03948#A3.F4),[5](https://arxiv.org/html/2607.03948#A3.F5),[6](https://arxiv.org/html/2607.03948#A3.F6)report comparisons between our router and the baseline policies under a stable arrival rate \(λ=0\.4\\lambda=0\.4\), with objective weights chosen to emphasize \(respectively\) average latencies, tail latencies, and throughput\. Figures[7](https://arxiv.org/html/2607.03948#A3.F7),[8](https://arxiv.org/html/2607.03948#A3.F8),[9](https://arxiv.org/html/2607.03948#A3.F9)report the analogous experiments under a mildly overloaded regime \(λ=0\.5\\lambda=0\.5\)\. Across these settings, we make three consistent observations\.

1. 1\.Targeted improvements:when the objective weights emphasize a particular metric family \(average latency, tail latency, or throughput\), our policy achieves the best performance on that targeted metric compared to all baselines\.
2. 2\.Trade\-offs are explicit and predictable:when we set the weights of non\-target metrics to zero, the targeted metric typically improves further, but non\-target metrics may degrade because they are no longer optimized\.
3. 3\.Overload amplifies tail effects:underλ=0\.5\\lambda=0\.5, tail latencies can deteriorate if tail objectives are assigned insufficient weight\. This reinforces the practical importance of explicitly controlling tail\-latency terms in overloaded regimes\.

![Refer to caption](https://arxiv.org/html/2607.03948v1/x5.png)\(a\)λ=0\.4\\lambda=0\.4;\(α,β,γ,σ,ζ1,ζ2\)=\(1135,1,1,1,1400,1400\)\\left\(\\alpha,\\beta,\\gamma,\\sigma,\\zeta\_\{1\},\\zeta\_\{2\}\\right\)=\\left\(\\frac\{1\}\{135\},1,1,1,\\frac\{1\}\{400\},\\frac\{1\}\{400\}\\right\);o^j=oj\\hat\{o\}\_\{j\}=o\_\{j\}
![Refer to caption](https://arxiv.org/html/2607.03948v1/x6.png)\(b\)λ=0\.4\\lambda=0\.4;\(α,β,γ,σ,ζ1,ζ2\)=\(0,1,1,0,0,0\)\\left\(\\alpha,\\beta,\\gamma,\\sigma,\\zeta\_\{1\},\\zeta\_\{2\}\\right\)=\\left\(0,1,1,0,0,0\\right\);o^j=oj\\hat\{o\}\_\{j\}=o\_\{j\}

Figure 4:Real\-data comparison between routing policies under stable arrival processλ=0\.4\\lambda=0\.4, with a focus on average latency\.![Refer to caption](https://arxiv.org/html/2607.03948v1/x7.png)\(a\)λ=0\.4\\lambda=0\.4;\(α,β,γ,σ,ζ1,ζ2\)=\(1135,1400,1400,1,1,1\)\\left\(\\alpha,\\beta,\\gamma,\\sigma,\\zeta\_\{1\},\\zeta\_\{2\}\\right\)=\\left\(\\frac\{1\}\{135\},\\frac\{1\}\{400\},\\frac\{1\}\{400\},1,1,1\\right\);o^j=oj\\hat\{o\}\_\{j\}=o\_\{j\}
![Refer to caption](https://arxiv.org/html/2607.03948v1/x8.png)\(b\)λ=0\.4\\lambda=0\.4;\(α,β,γ,σ,ζ1,ζ2\)=\(0,0,0,0,1,1\)\\left\(\\alpha,\\beta,\\gamma,\\sigma,\\zeta\_\{1\},\\zeta\_\{2\}\\right\)=\\left\(0,0,0,0,1,1\\right\);o^j=oj\\hat\{o\}\_\{j\}=o\_\{j\}

Figure 5:Real\-data comparison between routing policies under stable arrival processλ=0\.4\\lambda=0\.4, with a focus on tail latency\.![Refer to caption](https://arxiv.org/html/2607.03948v1/x9.png)\(a\)λ=0\.4\\lambda=0\.4;\(α,β,γ,σ,ζ1,ζ2\)=\(1,1400,1400,1,1400,1400\)\\left\(\\alpha,\\beta,\\gamma,\\sigma,\\zeta\_\{1\},\\zeta\_\{2\}\\right\)=\\left\(1,\\frac\{1\}\{400\},\\frac\{1\}\{400\},1,\\frac\{1\}\{400\},\\frac\{1\}\{400\}\\right\);o^j=oj\\hat\{o\}\_\{j\}=o\_\{j\}
![Refer to caption](https://arxiv.org/html/2607.03948v1/x10.png)\(b\)λ=0\.4\\lambda=0\.4;\(α,β,γ,σ,ζ1,ζ2\)=\(1,0,0,1,0,0\)\\left\(\\alpha,\\beta,\\gamma,\\sigma,\\zeta\_\{1\},\\zeta\_\{2\}\\right\)=\\left\(1,0,0,1,0,0\\right\);o^j=oj\\hat\{o\}\_\{j\}=o\_\{j\}

Figure 6:Real\-data comparison between routing policies under stable arrival processλ=0\.4\\lambda=0\.4, with a focus on throughput\.![Refer to caption](https://arxiv.org/html/2607.03948v1/x11.png)\(a\)λ=0\.5\\lambda=0\.5;\(α,β,γ,σ,ζ1,ζ2\)=\(1135,1,1,1,1400,1400\)\\left\(\\alpha,\\beta,\\gamma,\\sigma,\\zeta\_\{1\},\\zeta\_\{2\}\\right\)=\\left\(\\frac\{1\}\{135\},1,1,1,\\frac\{1\}\{400\},\\frac\{1\}\{400\}\\right\);o^j=oj\\hat\{o\}\_\{j\}=o\_\{j\}
![Refer to caption](https://arxiv.org/html/2607.03948v1/x12.png)\(b\)λ=0\.5\\lambda=0\.5;\(α,β,γ,σ,ζ1,ζ2\)=\(0,1,1,0,0,0\)\\left\(\\alpha,\\beta,\\gamma,\\sigma,\\zeta\_\{1\},\\zeta\_\{2\}\\right\)=\\left\(0,1,1,0,0,0\\right\);o^j=oj\\hat\{o\}\_\{j\}=o\_\{j\}

Figure 7:Real\-data comparison between routing policies under overloaded arrival processλ=0\.5\\lambda=0\.5, with a focus on average latency\.![Refer to caption](https://arxiv.org/html/2607.03948v1/x13.png)\(a\)λ=0\.5\\lambda=0\.5;\(α,β,γ,σ,ζ1,ζ2\)=\(1135,1400,1400,1,1,1\)\\left\(\\alpha,\\beta,\\gamma,\\sigma,\\zeta\_\{1\},\\zeta\_\{2\}\\right\)=\\left\(\\frac\{1\}\{135\},\\frac\{1\}\{400\},\\frac\{1\}\{400\},1,1,1\\right\);o^j=oj\\hat\{o\}\_\{j\}=o\_\{j\}
![Refer to caption](https://arxiv.org/html/2607.03948v1/x14.png)\(b\)λ=0\.5\\lambda=0\.5;\(α,β,γ,σ,ζ1,ζ2\)=\(0,0,0,0,1,1\)\\left\(\\alpha,\\beta,\\gamma,\\sigma,\\zeta\_\{1\},\\zeta\_\{2\}\\right\)=\\left\(0,0,0,0,1,1\\right\);o^j=oj\\hat\{o\}\_\{j\}=o\_\{j\}

Figure 8:Real\-data comparison between routing policies under overloaded arrival processλ=0\.5\\lambda=0\.5, with a focus on tail latency\.![Refer to caption](https://arxiv.org/html/2607.03948v1/x15.png)\(a\)λ=0\.5\\lambda=0\.5;\(α,β,γ,σ,ζ1,ζ2\)=\(1,1400,1400,1,1400,1400\)\\left\(\\alpha,\\beta,\\gamma,\\sigma,\\zeta\_\{1\},\\zeta\_\{2\}\\right\)=\\left\(1,\\frac\{1\}\{400\},\\frac\{1\}\{400\},1,\\frac\{1\}\{400\},\\frac\{1\}\{400\}\\right\);o^j=oj\\hat\{o\}\_\{j\}=o\_\{j\}
![Refer to caption](https://arxiv.org/html/2607.03948v1/x16.png)\(b\)λ=0\.5\\lambda=0\.5;\(α,β,γ,σ,ζ1,ζ2\)=\(1,0,0,1,0,0\)\\left\(\\alpha,\\beta,\\gamma,\\sigma,\\zeta\_\{1\},\\zeta\_\{2\}\\right\)=\\left\(1,0,0,1,0,0\\right\);o^j=oj\\hat\{o\}\_\{j\}=o\_\{j\}

Figure 9:Real\-data comparison between routing policies under overloaded arrival processλ=0\.5\\lambda=0\.5, with a focus on throughput\.
#### Results under noisy decode\-length prediction\.

We next evaluate robustness to prediction error by perturbing decode\-length estimates viao^j∼Unif​\(0\.8​oj,1\.2​oj\)\\hat\{o\}\_\{j\}\\sim\\text\{Unif\}\(0\.8\\,o\_\{j\},\\,1\.2\\,o\_\{j\}\)\. Figures[10](https://arxiv.org/html/2607.03948#A3.F10),[11](https://arxiv.org/html/2607.03948#A3.F11),[12](https://arxiv.org/html/2607.03948#A3.F12)present results for the stable regime \(λ=0\.4\\lambda=0\.4\), and Figures[14](https://arxiv.org/html/2607.03948#A3.F14),[15](https://arxiv.org/html/2607.03948#A3.F15),[16](https://arxiv.org/html/2607.03948#A3.F16)present results for the overloaded regime \(λ=0\.5\\lambda=0\.5\), again with objective weights emphasizing average latencies, tail latencies, and throughput\. The qualitative conclusions mirror the perfect\-prediction case: the policy continues to improve the metrics it is asked to optimize, exhibits clear trade\-offs when objectives are reweighted, and benefits from explicitly weighting tail terms under overload\. Overall, these experiments indicate that the proposed router is robust to moderate decode\-length prediction noise\.

![Refer to caption](https://arxiv.org/html/2607.03948v1/x17.png)\(a\)λ=0\.4\\lambda=0\.4;\(α,β,γ,σ,ζ1,ζ2\)=\(1135,1,1,1,1400,1400\)\\left\(\\alpha,\\beta,\\gamma,\\sigma,\\zeta\_\{1\},\\zeta\_\{2\}\\right\)=\\left\(\\frac\{1\}\{135\},1,1,1,\\frac\{1\}\{400\},\\frac\{1\}\{400\}\\right\);o^j∼Unif​\(0\.8⋅oj,1\.2⋅oj\)\\hat\{o\}\_\{j\}\\sim\\text\{Unif\}\(0\.8\\cdot o\_\{j\},1\.2\\cdot o\_\{j\}\)
![Refer to caption](https://arxiv.org/html/2607.03948v1/x18.png)\(b\)λ=0\.4\\lambda=0\.4;\(α,β,γ,σ,ζ1,ζ2\)=\(0,1,1,0,0,0\)\\left\(\\alpha,\\beta,\\gamma,\\sigma,\\zeta\_\{1\},\\zeta\_\{2\}\\right\)=\\left\(0,1,1,0,0,0\\right\);o^j∼Unif​\(0\.8⋅oj,1\.2⋅oj\)\\hat\{o\}\_\{j\}\\sim\\text\{Unif\}\(0\.8\\cdot o\_\{j\},1\.2\\cdot o\_\{j\}\)

Figure 10:Real\-data comparison between routing policies with noisy decode length prediction under stable arrival processλ=0\.4\\lambda=0\.4, with a focus on average latency\.![Refer to caption](https://arxiv.org/html/2607.03948v1/x19.png)\(a\)λ=0\.4\\lambda=0\.4;\(α,β,γ,σ,ζ1,ζ2\)=\(1135,1400,1400,1,1,1\)\\left\(\\alpha,\\beta,\\gamma,\\sigma,\\zeta\_\{1\},\\zeta\_\{2\}\\right\)=\\left\(\\frac\{1\}\{135\},\\frac\{1\}\{400\},\\frac\{1\}\{400\},1,1,1\\right\);o^j∼Unif​\(0\.8⋅oj,1\.2⋅oj\)\\hat\{o\}\_\{j\}\\sim\\text\{Unif\}\(0\.8\\cdot o\_\{j\},1\.2\\cdot o\_\{j\}\)
![Refer to caption](https://arxiv.org/html/2607.03948v1/x20.png)\(b\)λ=0\.4\\lambda=0\.4;\(α,β,γ,σ,ζ1,ζ2\)=\(0,0,0,0,1,1\)\\left\(\\alpha,\\beta,\\gamma,\\sigma,\\zeta\_\{1\},\\zeta\_\{2\}\\right\)=\\left\(0,0,0,0,1,1\\right\);o^j∼Unif​\(0\.8⋅oj,1\.2⋅oj\)\\hat\{o\}\_\{j\}\\sim\\text\{Unif\}\(0\.8\\cdot o\_\{j\},1\.2\\cdot o\_\{j\}\)

Figure 11:Real\-data comparison between routing policies with noisy decode length prediction under stable arrival processλ=0\.4\\lambda=0\.4, with a focus on tail latency\.![Refer to caption](https://arxiv.org/html/2607.03948v1/x21.png)\(a\)λ=0\.4\\lambda=0\.4;\(α,β,γ,σ,ζ1,ζ2\)=\(1,1400,1400,1,1400,1400\)\\left\(\\alpha,\\beta,\\gamma,\\sigma,\\zeta\_\{1\},\\zeta\_\{2\}\\right\)=\\left\(1,\\frac\{1\}\{400\},\\frac\{1\}\{400\},1,\\frac\{1\}\{400\},\\frac\{1\}\{400\}\\right\);o^j∼Unif​\(0\.8⋅oj,1\.2⋅oj\)\\hat\{o\}\_\{j\}\\sim\\text\{Unif\}\(0\.8\\cdot o\_\{j\},1\.2\\cdot o\_\{j\}\)
![Refer to caption](https://arxiv.org/html/2607.03948v1/x22.png)\(b\)λ=0\.4\\lambda=0\.4;\(α,β,γ,σ,ζ1,ζ2\)=\(1,0,0,1,0,0\)\\left\(\\alpha,\\beta,\\gamma,\\sigma,\\zeta\_\{1\},\\zeta\_\{2\}\\right\)=\\left\(1,0,0,1,0,0\\right\);o^j∼Unif​\(0\.8⋅oj,1\.2⋅oj\)\\hat\{o\}\_\{j\}\\sim\\text\{Unif\}\(0\.8\\cdot o\_\{j\},1\.2\\cdot o\_\{j\}\)

Figure 12:Real\-data comparison between routing policies with noisy decode length prediction under stable arrival processλ=0\.4\\lambda=0\.4, with a focus on throughput\.
#### Tail weights and the achieved tail quantile\.

As discussed in Section[3\.1](https://arxiv.org/html/2607.03948#S3.SS1), the tail weights\(ζ1,ζ2\)\(\\zeta\_\{1\},\\zeta\_\{2\}\)do more than rescale objectives: they directly influence how aggressively the router prioritizes meeting a tail objective\. To make this explicit, Figure[13](https://arxiv.org/html/2607.03948#A3.F13)fixes all parameters exceptζ2\\zeta\_\{2\}, fixes a TTFT thresholdt2′=49t\_\{2\}^\{\\prime\}=49, and reports the empirical*satisfaction rate*q​\(ζ2\):=1\|ℐ\|​∑j∈ℐ𝟏​\{TTFTj≤t2′\}q\(\\zeta\_\{2\}\)\\;:=\\;\\frac\{1\}\{\|\\mathcal\{I\}\|\}\\sum\_\{j\\in\\mathcal\{I\}\}\\mathbf\{1\}\\\{\\mathrm\{TTFT\}\_\{j\}\\leq t\_\{2\}^\{\\prime\}\\\}, which can be interpreted as the quantile level at which the TTFT thresholdt2′t\_\{2\}^\{\\prime\}is attained\. Asζ2\\zeta\_\{2\}increases,q​\(ζ2\)q\(\\zeta\_\{2\}\)increases on average \(up to simulation noise\), confirming that larger tail weights systematically push the policy toward satisfying a stricter tail requirement for a larger fraction of requests\.

![Refer to caption](https://arxiv.org/html/2607.03948v1/x23.png)Figure 13:TTFT satisfaction rate as a function of the tail weightζ2\\zeta\_\{2\}\.![Refer to caption](https://arxiv.org/html/2607.03948v1/x24.png)\(a\)λ=0\.5\\lambda=0\.5;\(α,β,γ,σ,ζ1,ζ2\)=\(1135,1,1,1,1400,1400\)\\left\(\\alpha,\\beta,\\gamma,\\sigma,\\zeta\_\{1\},\\zeta\_\{2\}\\right\)=\\left\(\\frac\{1\}\{135\},1,1,1,\\frac\{1\}\{400\},\\frac\{1\}\{400\}\\right\);o^j∼Unif​\(0\.8⋅oj,1\.2⋅oj\)\\hat\{o\}\_\{j\}\\sim\\text\{Unif\}\(0\.8\\cdot o\_\{j\},1\.2\\cdot o\_\{j\}\)
![Refer to caption](https://arxiv.org/html/2607.03948v1/x25.png)\(b\)λ=0\.5\\lambda=0\.5;\(α,β,γ,σ,ζ1,ζ2\)=\(0,1,1,0,0,0\)\\left\(\\alpha,\\beta,\\gamma,\\sigma,\\zeta\_\{1\},\\zeta\_\{2\}\\right\)=\\left\(0,1,1,0,0,0\\right\);o^j∼Unif​\(0\.8⋅oj,1\.2⋅oj\)\\hat\{o\}\_\{j\}\\sim\\text\{Unif\}\(0\.8\\cdot o\_\{j\},1\.2\\cdot o\_\{j\}\)

Figure 14:Real\-data comparison between routing policies with noisy decode length prediction under overloaded arrival processλ=0\.5\\lambda=0\.5, with a focus on average latency\.![Refer to caption](https://arxiv.org/html/2607.03948v1/x26.png)\(a\)λ=0\.5\\lambda=0\.5;\(α,β,γ,σ,ζ1,ζ2\)=\(1135,1400,1400,1,1,1\)\\left\(\\alpha,\\beta,\\gamma,\\sigma,\\zeta\_\{1\},\\zeta\_\{2\}\\right\)=\\left\(\\frac\{1\}\{135\},\\frac\{1\}\{400\},\\frac\{1\}\{400\},1,1,1\\right\);o^j∼Unif​\(0\.8⋅oj,1\.2⋅oj\)\\hat\{o\}\_\{j\}\\sim\\text\{Unif\}\(0\.8\\cdot o\_\{j\},1\.2\\cdot o\_\{j\}\)
![Refer to caption](https://arxiv.org/html/2607.03948v1/x27.png)\(b\)λ=0\.5\\lambda=0\.5;\(α,β,γ,σ,ζ1,ζ2\)=\(0,0,0,0,1,1\)\\left\(\\alpha,\\beta,\\gamma,\\sigma,\\zeta\_\{1\},\\zeta\_\{2\}\\right\)=\\left\(0,0,0,0,1,1\\right\);o^j∼Unif​\(0\.8⋅oj,1\.2⋅oj\)\\hat\{o\}\_\{j\}\\sim\\text\{Unif\}\(0\.8\\cdot o\_\{j\},1\.2\\cdot o\_\{j\}\)

Figure 15:Real\-data comparison between routing policies with noisy decode length prediction under overloaded arrival processλ=0\.5\\lambda=0\.5, with a focus on tail latency\.![Refer to caption](https://arxiv.org/html/2607.03948v1/x28.png)\(a\)λ=0\.5\\lambda=0\.5;\(α,β,γ,σ,ζ1,ζ2\)=\(1,1400,1400,1,1400,1400\)\\left\(\\alpha,\\beta,\\gamma,\\sigma,\\zeta\_\{1\},\\zeta\_\{2\}\\right\)=\\left\(1,\\frac\{1\}\{400\},\\frac\{1\}\{400\},1,\\frac\{1\}\{400\},\\frac\{1\}\{400\}\\right\);o^j∼Unif​\(0\.8⋅oj,1\.2⋅oj\)\\hat\{o\}\_\{j\}\\sim\\text\{Unif\}\(0\.8\\cdot o\_\{j\},1\.2\\cdot o\_\{j\}\)
![Refer to caption](https://arxiv.org/html/2607.03948v1/x29.png)\(b\)λ=0\.5\\lambda=0\.5;\(α,β,γ,σ,ζ1,ζ2\)=\(1,0,0,1,0,0\)\\left\(\\alpha,\\beta,\\gamma,\\sigma,\\zeta\_\{1\},\\zeta\_\{2\}\\right\)=\\left\(1,0,0,1,0,0\\right\);o^j∼Unif​\(0\.8⋅oj,1\.2⋅oj\)\\hat\{o\}\_\{j\}\\sim\\text\{Unif\}\(0\.8\\cdot o\_\{j\},1\.2\\cdot o\_\{j\}\)

Figure 16:Real\-data comparison between routing policies with noisy decode length prediction under overloaded arrival processλ=0\.5\\lambda=0\.5, with a focus on throughput\.

### C\.2Experiments on Synthetic Dataset

We complement the real\-data experiments with synthetic workloads that control the prefill\-to\-decode \(P/D\) ratio, allowing us to stress\-test the router under qualitatively different compute/memory regimes\. In all cases, we compare against the same baseline policies as in the main text and report results under both perfect and noisy decode\-length prediction\.

#### P/D ratio1:41\{:\}4\(decode\-heavy\)\.

Figures[17](https://arxiv.org/html/2607.03948#A3.F17)and[18](https://arxiv.org/html/2607.03948#A3.F18)report comparisons under a stable arrival rate for decode\-heavy requests \(P/D=1:4=1\{:\}4\), with objective weights chosen to emphasize \(respectively\) average latencies and tail latencies\. Figures[19](https://arxiv.org/html/2607.03948#A3.F19)and[20](https://arxiv.org/html/2607.03948#A3.F20)report the corresponding experiments under20%20\\%decode\-length prediction noise\. The qualitative conclusions align with the real\-data setting: \(i\) when the objective weights emphasize a particular metric family, our policy consistently improves that targeted metric relative to the baselines; \(ii\) reweighting objectives produces predictable trade\-offs between average and tail performance; and \(iii\) the performance advantages persist under moderate prediction noise, indicating robustness of the bid\-price control mechanism\.

![Refer to caption](https://arxiv.org/html/2607.03948v1/x30.png)\(a\)λ=0\.4\\lambda=0\.4;\(α,β,γ,σ,ζ1,ζ2\)=\(1135,1,1,1,1400,1400\)\\left\(\\alpha,\\beta,\\gamma,\\sigma,\\zeta\_\{1\},\\zeta\_\{2\}\\right\)=\\left\(\\frac\{1\}\{135\},1,1,1,\\frac\{1\}\{400\},\\frac\{1\}\{400\}\\right\);o^j=oj\\hat\{o\}\_\{j\}=o\_\{j\}
![Refer to caption](https://arxiv.org/html/2607.03948v1/x31.png)\(b\)λ=0\.4\\lambda=0\.4;\(α,β,γ,σ,ζ1,ζ2\)=\(0,1,1,0,0,0\)\\left\(\\alpha,\\beta,\\gamma,\\sigma,\\zeta\_\{1\},\\zeta\_\{2\}\\right\)=\\left\(0,1,1,0,0,0\\right\);o^j=oj\\hat\{o\}\_\{j\}=o\_\{j\}

Figure 17:Synthetic data \(P/D ratio1:41:4\) comparison between routing policies under stable arrival process, with a focus on average latency\.![Refer to caption](https://arxiv.org/html/2607.03948v1/x32.png)\(a\)λ=0\.4\\lambda=0\.4;\(α,β,γ,σ,ζ1,ζ2\)=\(1135,1400,1400,1,1,1\)\\left\(\\alpha,\\beta,\\gamma,\\sigma,\\zeta\_\{1\},\\zeta\_\{2\}\\right\)=\\left\(\\frac\{1\}\{135\},\\frac\{1\}\{400\},\\frac\{1\}\{400\},1,1,1\\right\);o^j=oj\\hat\{o\}\_\{j\}=o\_\{j\}
![Refer to caption](https://arxiv.org/html/2607.03948v1/x33.png)\(b\)λ=0\.5\\lambda=0\.5;\(α,β,γ,σ,ζ1,ζ2\)=\(0,0,0,0,1,1\)\\left\(\\alpha,\\beta,\\gamma,\\sigma,\\zeta\_\{1\},\\zeta\_\{2\}\\right\)=\\left\(0,0,0,0,1,1\\right\);o^j=oj\\hat\{o\}\_\{j\}=o\_\{j\}

Figure 18:Synthetic data \(P/D ratio1:41:4\) comparison between routing policies under stable arrival process, with a focus on tail latency\.![Refer to caption](https://arxiv.org/html/2607.03948v1/x34.png)\(a\)λ=0\.4\\lambda=0\.4;\(α,β,γ,σ,ζ1,ζ2\)=\(1135,1,1,1,1400,1400\)\\left\(\\alpha,\\beta,\\gamma,\\sigma,\\zeta\_\{1\},\\zeta\_\{2\}\\right\)=\\left\(\\frac\{1\}\{135\},1,1,1,\\frac\{1\}\{400\},\\frac\{1\}\{400\}\\right\);o^j∼Unif​\(0\.8⋅oj,1\.2⋅oj\)\\hat\{o\}\_\{j\}\\sim\\text\{Unif\}\(0\.8\\cdot o\_\{j\},1\.2\\cdot o\_\{j\}\)
![Refer to caption](https://arxiv.org/html/2607.03948v1/x35.png)\(b\)λ=0\.4\\lambda=0\.4;\(α,β,γ,σ,ζ1,ζ2\)=\(0,1,1,0,0,0\)\\left\(\\alpha,\\beta,\\gamma,\\sigma,\\zeta\_\{1\},\\zeta\_\{2\}\\right\)=\\left\(0,1,1,0,0,0\\right\);o^j∼Unif​\(0\.8⋅oj,1\.2⋅oj\)\\hat\{o\}\_\{j\}\\sim\\text\{Unif\}\(0\.8\\cdot o\_\{j\},1\.2\\cdot o\_\{j\}\)

Figure 19:Synthetic data \(P/D ratio1:41:4\) comparison between routing policies with noisy decode length prediction under stable arrival process, with a focus on average latency\.![Refer to caption](https://arxiv.org/html/2607.03948v1/x36.png)\(a\)λ=0\.4\\lambda=0\.4;\(α,β,γ,σ,ζ1,ζ2\)=\(1135,1400,1400,1,1,1\)\\left\(\\alpha,\\beta,\\gamma,\\sigma,\\zeta\_\{1\},\\zeta\_\{2\}\\right\)=\\left\(\\frac\{1\}\{135\},\\frac\{1\}\{400\},\\frac\{1\}\{400\},1,1,1\\right\);o^j∼Unif​\(0\.8⋅oj,1\.2⋅oj\)\\hat\{o\}\_\{j\}\\sim\\text\{Unif\}\(0\.8\\cdot o\_\{j\},1\.2\\cdot o\_\{j\}\)
![Refer to caption](https://arxiv.org/html/2607.03948v1/x37.png)\(b\)λ=0\.5\\lambda=0\.5;\(α,β,γ,σ,ζ1,ζ2\)=\(0,0,0,0,1,1\)\\left\(\\alpha,\\beta,\\gamma,\\sigma,\\zeta\_\{1\},\\zeta\_\{2\}\\right\)=\\left\(0,0,0,0,1,1\\right\);o^j∼Unif​\(0\.8⋅oj,1\.2⋅oj\)\\hat\{o\}\_\{j\}\\sim\\text\{Unif\}\(0\.8\\cdot o\_\{j\},1\.2\\cdot o\_\{j\}\)

Figure 20:Synthetic data \(P/D ratio1:41:4\) comparison between routing policies with noisy decode length prediction under stable arrival process, with a focus on tail latency\.
#### P/D ratio4:14\{:\}1\(prefill\-heavy / decode\-light\)\.

Figures[21](https://arxiv.org/html/2607.03948#A3.F21)and[22](https://arxiv.org/html/2607.03948#A3.F22)report the analogous comparisons for prefill\-heavy requests \(P/D=4:1=4\{:\}1\), again emphasizing \(respectively\) average and tail latency objectives, with Figures[23](https://arxiv.org/html/2607.03948#A3.F23)and[24](https://arxiv.org/html/2607.03948#A3.F24)showing the corresponding noisy\-prediction results\. In this regime, decode workloads are relatively short, so decode\-side batch and KV constraints are less likely to become binding; as a result, small changes in objective weights often lead to smaller changes in observed performance\. This highlights an important practical point: the proposed router is most impactful when decode\-side congestion is substantial \(e\.g\., long or highly variable decode lengths\), where time\-coupled batch/KV constraints meaningfully shape the feasible set and where objective\-aware admission decisions provide the largest benefit\.

![Refer to caption](https://arxiv.org/html/2607.03948v1/x38.png)\(a\)λ=0\.4\\lambda=0\.4;\(α,β,γ,σ,ζ1,ζ2\)=\(1135,1,1,1,1400,1400\)\\left\(\\alpha,\\beta,\\gamma,\\sigma,\\zeta\_\{1\},\\zeta\_\{2\}\\right\)=\\left\(\\frac\{1\}\{135\},1,1,1,\\frac\{1\}\{400\},\\frac\{1\}\{400\}\\right\);o^j=oj\\hat\{o\}\_\{j\}=o\_\{j\}
![Refer to caption](https://arxiv.org/html/2607.03948v1/x39.png)\(b\)λ=0\.4\\lambda=0\.4;\(α,β,γ,σ,ζ1,ζ2\)=\(0,1,1,0,0,0\)\\left\(\\alpha,\\beta,\\gamma,\\sigma,\\zeta\_\{1\},\\zeta\_\{2\}\\right\)=\\left\(0,1,1,0,0,0\\right\);o^j=oj\\hat\{o\}\_\{j\}=o\_\{j\}

Figure 21:Synthetic data \(P/D ratio4:14:1\) comparison between routing policies under stable arrival process, with a focus on average latency\.![Refer to caption](https://arxiv.org/html/2607.03948v1/x40.png)\(a\)λ=0\.4\\lambda=0\.4;\(α,β,γ,σ,ζ1,ζ2\)=\(1135,1400,1400,1,1,1\)\\left\(\\alpha,\\beta,\\gamma,\\sigma,\\zeta\_\{1\},\\zeta\_\{2\}\\right\)=\\left\(\\frac\{1\}\{135\},\\frac\{1\}\{400\},\\frac\{1\}\{400\},1,1,1\\right\);o^j=oj\\hat\{o\}\_\{j\}=o\_\{j\}
![Refer to caption](https://arxiv.org/html/2607.03948v1/x41.png)\(b\)λ=0\.5\\lambda=0\.5;\(α,β,γ,σ,ζ1,ζ2\)=\(0,0,0,0,1,1\)\\left\(\\alpha,\\beta,\\gamma,\\sigma,\\zeta\_\{1\},\\zeta\_\{2\}\\right\)=\\left\(0,0,0,0,1,1\\right\);o^j=oj\\hat\{o\}\_\{j\}=o\_\{j\}

Figure 22:Synthetic data \(P/D ratio4:14:1\) comparison between routing policies under stable arrival process, with a focus on tail latency\.![Refer to caption](https://arxiv.org/html/2607.03948v1/x42.png)\(a\)λ=0\.4\\lambda=0\.4;\(α,β,γ,σ,ζ1,ζ2\)=\(1135,1,1,1,1400,1400\)\\left\(\\alpha,\\beta,\\gamma,\\sigma,\\zeta\_\{1\},\\zeta\_\{2\}\\right\)=\\left\(\\frac\{1\}\{135\},1,1,1,\\frac\{1\}\{400\},\\frac\{1\}\{400\}\\right\);o^j∼Unif​\(0\.8⋅oj,1\.2⋅oj\)\\hat\{o\}\_\{j\}\\sim\\text\{Unif\}\(0\.8\\cdot o\_\{j\},1\.2\\cdot o\_\{j\}\)
![Refer to caption](https://arxiv.org/html/2607.03948v1/x43.png)\(b\)λ=0\.4\\lambda=0\.4;\(α,β,γ,σ,ζ1,ζ2\)=\(0,1,1,0,0,0\)\\left\(\\alpha,\\beta,\\gamma,\\sigma,\\zeta\_\{1\},\\zeta\_\{2\}\\right\)=\\left\(0,1,1,0,0,0\\right\);o^j∼Unif​\(0\.8⋅oj,1\.2⋅oj\)\\hat\{o\}\_\{j\}\\sim\\text\{Unif\}\(0\.8\\cdot o\_\{j\},1\.2\\cdot o\_\{j\}\)

Figure 23:Synthetic data \(P/D ratio4:14:1\) comparison between routing policies with noisy decode length prediction under stable arrival process, with a focus on average latency\.![Refer to caption](https://arxiv.org/html/2607.03948v1/x44.png)\(a\)λ=0\.4\\lambda=0\.4;\(α,β,γ,σ,ζ1,ζ2\)=\(1135,1400,1400,1,1,1\)\\left\(\\alpha,\\beta,\\gamma,\\sigma,\\zeta\_\{1\},\\zeta\_\{2\}\\right\)=\\left\(\\frac\{1\}\{135\},\\frac\{1\}\{400\},\\frac\{1\}\{400\},1,1,1\\right\);o^j∼Unif​\(0\.8⋅oj,1\.2⋅oj\)\\hat\{o\}\_\{j\}\\sim\\text\{Unif\}\(0\.8\\cdot o\_\{j\},1\.2\\cdot o\_\{j\}\)
![Refer to caption](https://arxiv.org/html/2607.03948v1/x45.png)\(b\)λ=0\.5\\lambda=0\.5;\(α,β,γ,σ,ζ1,ζ2\)=\(0,0,0,0,1,1\)\\left\(\\alpha,\\beta,\\gamma,\\sigma,\\zeta\_\{1\},\\zeta\_\{2\}\\right\)=\\left\(0,0,0,0,1,1\\right\);o^j∼Unif​\(0\.8⋅oj,1\.2⋅oj\)\\hat\{o\}\_\{j\}\\sim\\text\{Unif\}\(0\.8\\cdot o\_\{j\},1\.2\\cdot o\_\{j\}\)

Figure 24:Synthetic data \(P/D ratio4:14:1\) comparison between routing policies with noisy decode length prediction under stable arrival process, with a focus on tail latency\.