Beyond Accuracy and Cost: Latency-Aware LLM Query Routing for Dynamic Workloads

# Latency-Aware LLM Query Routing for Dynamic Workloads
Source: [https://arxiv.org/html/2607.18253](https://arxiv.org/html/2607.18253)
\\NAT@set@cites

## Beyond Accuracy and Cost: Latency\-Aware LLM Query Routing for Dynamic Workloads

Akaash R\. Parthasarathy\*Carnegie Mellon UniversityAnkur MallickMicrosoftGauri JoshiCarnegie Mellon University

###### Abstract

Modern language query routers improve inference efficiency by assigning each query to a model that balances response quality and monetary cost\. However, current query routers are largely latency\-agnostic and do not consider the generation latency experienced by queries at model instances\. In practice, latency is often controlled by load\-balancing policies such as round\-robin or join\-the\-shortest\-queue, which do not account for model accuracy or inference cost\. Incorporating query latency into routing is challenging as it depends not only on the query’s prompt length, but also on the current prefill and decode workload at the model instance and the scheduling and batching policy of the serving framework\. We design a lightweight latency estimator that simulates autoregressive token batch processing in the serving framework and estimates the time\-to\-first\-token \(TTFT\) of queries\. We incorporate this latency estimator into*a latency\-aware router that jointly optimizes latency, accuracy, and cost when assigning queries to model instances*\. Our experimental results indicate that this joint optimization yields up to40%40\\%improvement in accuracy–cost utility while maintaining the same latencies as standard load\-balancing approaches\.

## 1 Introduction

Routing user queries across a pool of large language models \(LLMs\) is a promising solution towards efficient utilization of LLMs\. Given a prompt or a query, a language query router selects a model instance to maximize expected response quality while controlling monetary cost \(the price per token charged to the user\)\. For instance, easier queries are sent to smaller and cheaper models, while harder queries are sent to larger and more expensive models\. A substantial body of work\[[24](https://arxiv.org/html/2607.18253#bib.bib15),[36](https://arxiv.org/html/2607.18253#bib.bib12),[11](https://arxiv.org/html/2607.18253#bib.bib11),[12](https://arxiv.org/html/2607.18253#bib.bib17),[38](https://arxiv.org/html/2607.18253#bib.bib14)\]studies query routing to strike a good accuracy–cost tradeoff using calibrated correctness and cost predictors that are trained on query evaluations on models in the pool\.

#### Need for latency\-aware query routing\.

In addition to balancing accuracy and cost, response generation should also meet*latency constraints*based on downstream usage or service\-level objectives \(SLOs\)\. Most existing query routers\[[36](https://arxiv.org/html/2607.18253#bib.bib12),[11](https://arxiv.org/html/2607.18253#bib.bib11),[24](https://arxiv.org/html/2607.18253#bib.bib15),[12](https://arxiv.org/html/2607.18253#bib.bib17),[38](https://arxiv.org/html/2607.18253#bib.bib14),[10](https://arxiv.org/html/2607.18253#bib.bib16)\]perform model selection based on accuracy and cost, but are latency\-agnostic\. Therefore, they may route queries to overloaded model instances, causing long queueing delays and latency constraint violations\. Latency optimization via load\-balancing of queries across model instances is generally left to the underlying systems layer\. System\-level latency optimization considers a fixed choice of language model for a query and focuses on assigning queries to replicas of the same language model\. Works such as\[[23](https://arxiv.org/html/2607.18253#bib.bib25),[45](https://arxiv.org/html/2607.18253#bib.bib28),[9](https://arxiv.org/html/2607.18253#bib.bib45)\]perform load balancing of requests across model deployments on heterogeneous hardware\. Other works design scheduling policies that prioritize requests based on latency constraints, predicted output lengths, or remaining decode work at the model instance\[[20](https://arxiv.org/html/2607.18253#bib.bib30),[41](https://arxiv.org/html/2607.18253#bib.bib31),[15](https://arxiv.org/html/2607.18253#bib.bib32),[43](https://arxiv.org/html/2607.18253#bib.bib33),[39](https://arxiv.org/html/2607.18253#bib.bib29)\]\. These system\-level routing methods improve latency and resource utilization, but they operate under a fixed query\-to\-model assignment and thus are accuracy\- and cost\-agnostic\. In this work, we aim to bridge the gap between accuracy\-aware and cost\-aware routing, which is latency\-agnostic, and system\-level latency optimization, which is accuracy\- and cost\-agnostic\.*We design a routing framework based on joint accuracy–cost–latency optimization\.*

#### Challenges in latency estimation\.

Extending accuracy–cost routing to*latency\-aware*routing is not straightforward\. While existing query routers\[[24](https://arxiv.org/html/2607.18253#bib.bib15),[38](https://arxiv.org/html/2607.18253#bib.bib14),[11](https://arxiv.org/html/2607.18253#bib.bib11)\]provide reliable accuracy and cost estimates, latency\-aware routing requires reliable estimates of the latency that will be experienced by an incoming query when assigned to a model instance\. Unlike cost \(the amount charged to the user, which is often a deterministic function of token counts\) or accuracy \(which can be learned from historical query–model evaluations\),*generation latency depends on the workload of queries that are currently being served at a model instance*\. Modern LLM serving frameworks \(e\.g\., vLLM\[[26](https://arxiv.org/html/2607.18253#bib.bib1)\], Sarathi\-Serve\[[2](https://arxiv.org/html/2607.18253#bib.bib2)\]\) execute*many requests concurrently*using continuous batching, resulting in simultaneous processing of sequences in the prompt token KV\-cache computation stage \(prefill stage\), and the sequential decode token generation stage \(decode stage\)\. The response generation rate and latencies experienced by queries at a model instance depend on \(i\) the hardware specifications and language model architecture, \(ii\) the current prefill versus decode workload composition of queries, and \(iii\) the batching and scheduling policy of the serving framework\.

#### Our latency\-aware routing framework\.

We propose a routing framework that estimates query latencies and makes routing decisions by incorporating information about the query workload at each model instance, and the scheduling policies used by the underlying serving framework\. Our proposed Serving Framework Simulation \(SFS\) based*time\-to\-first\-token*\(TTFT\) latency estimator simulates the evolution of token batch composition during autoregressive generation at model instances, and predicts latencies incurred by new queries\. Experiments show that our latency\-aware routing framework strikes a favorable accuracy–cost–latency tradeoff, and outperforms existing latency\-agnostic routers as well as accuracy\- and cost\-agnostic load balancing methods\. The closest prior work to our setting is\[[27](https://arxiv.org/html/2607.18253#bib.bib35)\], which considers an output\-length\-based latency estimator and jointly optimizes response quality and generation latency\. However, it does not account for varying prefill and decode compositions, serving framework policies, and the present workload at model instances\. We provide a more detailed discussion of prior work in[Appendix˜A](https://arxiv.org/html/2607.18253#A1)\.

#### Paper organization\.

The remainder of the paper is organized as follows:[Section˜2](https://arxiv.org/html/2607.18253#S2)introduces relevant background on autoregressive generation and serving frameworks,[Section˜3](https://arxiv.org/html/2607.18253#S3)formally presents our routing objective and notation,[Section˜4](https://arxiv.org/html/2607.18253#S4)proposes our latency estimation approach,[Section˜5](https://arxiv.org/html/2607.18253#S5)presents an empirical evaluation of the latency\-aware router, and[Section˜6](https://arxiv.org/html/2607.18253#S6)concludes our work and discusses future directions\.

## 2 Background on LLM serving frameworks

#### Autoregressive generation\.

Most transformer\-based language models generate sequences autoregressively, predicting each token from the input prompt and all previously generated tokens through attention\[[47](https://arxiv.org/html/2607.18253#bib.bib55)\]\. Computationally, generation consists of two phases\[[40](https://arxiv.org/html/2607.18253#bib.bib56)\]: the*prefill*phase, where the input prompt tokens are processed in parallel to compute the key\-value states and initialize the KV cache; and the*decode*phase, where output tokens are generated sequentially, with new key\-value states appended to the cache for future attention computations\. The prefill phase is typically compute\-bound since prompt tokens can be processed in parallel, whereas the decode phase is typically memory\-bound since each step reads the cached key\-value states for previous tokens\[[2](https://arxiv.org/html/2607.18253#bib.bib2),[26](https://arxiv.org/html/2607.18253#bib.bib1)\]\. While other generation paradigms exist, including diffusion\-based generation and non\-autoregressive refinement\[[18](https://arxiv.org/html/2607.18253#bib.bib59),[28](https://arxiv.org/html/2607.18253#bib.bib58),[30](https://arxiv.org/html/2607.18253#bib.bib57)\], our analysis focuses on the popular attention\-based autoregressive setting\.

#### Batch composition and generation throughput\.

Batching of computational workload for generating responses to queries is a crucial aspect of utilizing the parallel computation capacity of GPUs\. Naive sequence\-level batching collects queries and generates new tokens for each query in the batch until completion\. This leads to inefficient hardware utilization as shorter sequences in the batch need to wait for longer sequences to finish generation\. To overcome this, modern serving frameworks utilize continuous batching \(ORCA\[[50](https://arxiv.org/html/2607.18253#bib.bib7)\], vLLM\[[26](https://arxiv.org/html/2607.18253#bib.bib1)\], etc\.\), where new prompts are admitted in the generation stage at token iteration \(often simply denoted as “token batch”\) boundaries, unlike sequence\-level batch boundaries in naive batching\. This implies that autoregressive generation for a new sequence can begin while other sequences are still being generated\. Continuous batching leads to better hardware utilization and higher throughput\.

#### Memory and scheduling mechanisms in serving frameworks\.

Continuous batching demands careful management of the varied composition of prefill and decode tokens in sequences, making memory allocation crucial to ensure efficient compute utilization\. Early solutions, such as ORCA\[[50](https://arxiv.org/html/2607.18253#bib.bib7)\], reserve memory for the KV cache up to the maximum possible context length of each sequence being served\. This leads to over\-provisioning since most sequences do not achieve the maximum context length, resulting in suboptimal hardware utilization and reduced throughput\. PagedAttention \(used in vLLM\)\[[26](https://arxiv.org/html/2607.18253#bib.bib1)\]applies virtual memory\-style paging to the KV cache, avoiding large contiguous pre\-allocation and instead allocating fixed\-size KV cache blocks to sequences dynamically as generation proceeds\. The heterogeneous compute and memory requirements of the prefill and decode stages allow further refinement of the batching policy\. Chunked prefills\[[2](https://arxiv.org/html/2607.18253#bib.bib2)\]balance prefill and decode work within a token batch by splitting long prefills into smaller chunks, improving hardware utilization and throughput while avoiding decode stalls\. Our latency estimator factors in these aspects to produce accurate TTFT estimates for queries\.

## 3 Problem formulation

#### System model and notation\.

We refer to each deployed LLM, together with its associated hardware allocation and serving framework, as a*model instance*, indexed byj∈𝒥j\\in\\mathcal\{J\}\. For each newly arriving queryqiq\_\{i\}, the router estimates the accuracy, cost, and time\-to\-first\-token \(TTFT\) latency associated with each candidate model instance, and selects an instancem​\(i\)∈𝒥m\(i\)\\in\\mathcal\{J\}according to the desired routing objective\. We consider TTFT latency as it captures the responsiveness perceived by users and interactive applications\.

![Refer to caption](https://arxiv.org/html/2607.18253v1/x1.png)Figure 1:TTFT \(time\-to\-first\-token\) for autoregressive generation\.A new sequence \(query\)qiq\_\{i\}arrives at timettto model instancejj\(*left*\), its prefill computation begins at timet\+Wi,jt\\\!\+\\\!W\_\{i,j\}\(*center*\), and the first decode token is generated at timet\+Wi,j\+Pi,jt\\\!\+\\\!W\_\{i,j\}\\\!\+\\\!P\_\{i,j\}\(*right*\)\. New sequences are queued until the memory at the model instance is released by sequences already being generated\.
#### Generation latency\.

The time between a sequence \(query\) arriving in the system and completing generation \(by either generating an<eos\>token or reaching the model’s context length limit\) comprises three stages: queueing delay, prefill time, and decode time\. Queueing delay, or waiting time, is the idle period before a query’s prefill computation begins, during which it waits for compute and memory resources occupied by preceding queries to become available\. Prefill time denotes the time required for query processing and populating the KV cache, and decode time denotes the autoregressive generation time\. We examine time\-to\-first\-token \(TTFT\), which denotes the time from query arrival to first output\-token generation\. Thus for queryqiq\_\{i\}at model instancejj, TTFT can be represented as

Li,jttft=Wi,j\+Pi,j\\displaystyle L^\{\\text\{ttft\}\}\_\{i,j\}\\;=\\;W\_\{i,j\}\\;\+\\;P\_\{i,j\}\(1\)whereWi,jW\_\{i,j\}represents the waiting time spent in the queue andPi,jP\_\{i,j\}is the prefill and first decode token computation time\. We illustrate the latency decomposition in[Figure˜1](https://arxiv.org/html/2607.18253#S3.F1)for continuous batching policies\. Estimates \(L^i,jttft\\widehat\{L\}^\{\\text\{ttft\}\}\_\{i,j\}\) of TTFT for a given queryqiq\_\{i\}at each model instancejjare required to perform latency\-aware routing decisions across model instances\.

#### Accuracy and cost estimators\.

Using historical evaluations of queries on language models, we train estimators for the response quality and serving cost of previously unseen queries \(details presented in[Section˜B\.4](https://arxiv.org/html/2607.18253#A2.SS4)\)\. For each queryqiq\_\{i\}and model instancejj, we produce an accuracy estimateacc^i,j\\widehat\{\\textrm\{acc\}\}\_\{i,j\}and a cost estimatecost^i,j\\widehat\{\\textrm\{cost\}\}\_\{i,j\}\. Response accuracy refers broadly to a task\-dependent quality measure \(such as correctness, ROUGE\[[32](https://arxiv.org/html/2607.18253#bib.bib49)\], or BARTScore\[[51](https://arxiv.org/html/2607.18253#bib.bib50)\]\)\. We utilize a normalized LLM\-as\-a\-judge\[[29](https://arxiv.org/html/2607.18253#bib.bib42)\]quality score in\[0,1\]\[0,1\]for our analysis\. We compute generation cost using the per\-token pricing of each model\. We define the accuracy–cost utility\[[24](https://arxiv.org/html/2607.18253#bib.bib15),[38](https://arxiv.org/html/2607.18253#bib.bib14),[19](https://arxiv.org/html/2607.18253#bib.bib13)\]as:

U^i,j​\(λ\)=acc^i,j−λ​cost^i,j,\\displaystyle\\widehat\{U\}\_\{i,j\}\(\\lambda\)\\;=\\;\\widehat\{\\textrm\{acc\}\}\_\{i,j\}\-\\lambda\\widehat\{\\textrm\{cost\}\}\_\{i,j\},\(2\)whereλ≥0\\lambda\\geq 0governs the tradeoff between response quality and monetary cost\.

#### Routing objectives and evaluation protocols\.

In practical deployments, queries are subject to generation latency requirements based on downstream tasks\. We therefore define the primary routing objective as maximizing the accuracy–cost utilityU^i,j\\widehat\{U\}\_\{i,j\}, while satisfying a per\-query time\-to\-first\-token \(TTFT\) constraint\. Letτi\\tau\_\{i\}denote the TTFT target for queryqiq\_\{i\}, and define the estimated feasible set of model instances as𝒥​\(i\)=\{j∈𝒥:L^i,jttft​\(t\)≤τi\}\\mathcal\{J\}\(i\)=\\\{j\\in\\mathcal\{J\}:\\widehat\{L\}^\{\\textrm\{ttft\}\}\_\{i,j\}\(t\)\\leq\\tau\_\{i\}\\\}\. The router selects the feasible model instance with the highest estimated utility \(if𝒥​\(i\)=ϕ\\mathcal\{J\}\(i\)=\\phi, select the instance with the least estimated latency\):

m​\(i\)←arg​maxj∈𝒥:L^i,jttft​\(t\)≤τi⁡U^i,j​\(λ\)\.m\(i\)\\leftarrow\\operatorname\*\{arg\\,max\}\_\{\\begin\{subarray\}\{c\}j\\in\\mathcal\{J\}:\\,\\,\\widehat\{L\}^\{\\textrm\{ttft\}\}\_\{i,j\}\(t\)\\leq\\tau\_\{i\}\\end\{subarray\}\}\\widehat\{U\}\_\{i,j\}\(\\lambda\)\.\(3\)To evaluate this constrained routing objective, we report the average utility achieved by the routed model instances on queries, assigning zero utility to queries that violate their latency constraints\. We refer to this metric as*OnTimeUtility*, capturing the average accuracy–cost utility over latency\-constraint satisfying responses \(whereNNdenotes the total number of queries evaluated\):

OnTimeUtility​\(λ\)=1N​∑i=1NUi,m​\(i\)​\(λ\)​1​\{Li,m​\(i\)ttft≤τi\},\\textrm\{OnTimeUtility\}\(\\lambda\)=\\frac\{1\}\{N\}\\sum\_\{i=1\}^\{N\}U\_\{i,m\(i\)\}\(\\lambda\)\\,\\mathbf\{1\}\\\!\\left\\\{L^\{\\textrm\{ttft\}\}\_\{i,m\(i\)\}\\leq\\tau\_\{i\}\\right\\\},\(4\)whereUi,m​\(i\)​\(λ\)U\_\{i,m\(i\)\}\(\\lambda\)andLi,m​\(i\)ttftL^\{\\textrm\{ttft\}\}\_\{i,m\(i\)\}denote the realized utility and TTFT after routing, and𝟏​\{⋅\}\\mathbf\{1\}\\left\\\{\\cdot\\right\\\}denotes the indicator function\. We also characterize the underlying tradeoff between utility and latency by considering a Lagrangian relaxation of the constrained objective in[eq\.˜3](https://arxiv.org/html/2607.18253#S3.E3):

m​\(i\)←arg​maxj∈𝒥⁡\(U^i,j​\(λ\)−δ​L^i,jttft​\(t\)\),\\displaystyle m\(i\)\\;\\leftarrow\\;\\operatorname\*\{arg\\,max\}\_\{j\\in\\mathcal\{J\}\}\\Big\(\\widehat\{U\}\_\{i,j\}\(\\lambda\)\-\\delta\\,\\widehat\{L\}^\{\\textrm\{ttft\}\}\_\{i,j\}\(t\)\\Big\),\(5\)whereδ≥0\\delta\\geq 0controls the relative emphasis placed on latency\. By varyingδ\\delta, we obtain a utility–latency tradeoff curve in terms of\(𝔼​\[Ui,m​\(i\)​\(λ\)\],𝔼​\[Li,m​\(i\)ttft\]\)\(\\mathbb\{E\}\[U\_\{i,m\(i\)\}\(\\lambda\)\],\\mathbb\{E\}\[L^\{\\textrm\{ttft\}\}\_\{i,m\(i\)\}\]\)\. This enables a characterization of the router’s ability to trade off utility and latency independently of per\-query service\-level objectives\. A better router attains higher utility at the same average latency, or equivalently achieves lower latency while preserving the same accuracy–cost utility\.

## 4 Estimating query latencies across model instances

Accurate estimates of*time\-to\-first\-token*\(TTFT\) latencies are essential for routing queries across language models for generating responses while satisfying latency constraints\. Over\-estimating latencies leads to under\-utilization of model instances, whereas under\-estimating can cause frequent constraint violations\. In this section, we introduce our proposed*Serving Framework Simulation*\(SFS\)\-based latency estimator\. SFS uses query workload information at model instances to simulate token batch composition according to the serving framework’s batching and scheduling policies\. We design a token\-batch processing time estimator that leverages the resulting token batch compositions until first decode token of the new query to estimate TTFT latencies\. Our proposed latency estimator is accurate and computationally efficient, achieving<5%<\\\!5\\%mean absolute percentage error on TTFT predictions with sub\-millisecond test\-time overhead\. We also present a queueing\-theoretic analysis of autoregressive generation to estimate average latencies at model instances in cases where real\-time workload information is unavailable to the router\.

#### Setup\.

Let𝒬j​\(t\)\\mathcal\{Q\}\_\{j\}\(t\)denote the set of requests queued at model instancejjat timett, i\.e\., requests assigned to the instance whose prefill processing has not yet begun\. Let𝒜j​\(t\)\\mathcal\{A\}\_\{j\}\(t\)denote the set of active requests currently being served, either in the prefill or decode stage\. We define the resident set of requests at model instancejjas

ℛj​\(t\)≜𝒬j​\(t\)∪𝒜j​\(t\)\.\\mathcal\{R\}\_\{j\}\(t\)\\triangleq\\mathcal\{Q\}\_\{j\}\(t\)\\cup\\mathcal\{A\}\_\{j\}\(t\)\.For each resident requestq∈ℛj​\(t\)q\\in\\mathcal\{R\}\_\{j\}\(t\), lettokq,jpre​\(t\)\\textrm\{tok\}^\{\\textrm\{pre\}\}\_\{q,j\}\(t\)andtokq,jdec​\(t\)\\textrm\{tok\}^\{\\textrm\{dec\}\}\_\{q,j\}\(t\)denote the remaining number of prefill tokens to be processed and decode tokens to be generated at timett, respectively\. For a new queryqiq\_\{i\}arriving at timett, the goal of our latency estimator is to compute the TTFT estimateL^i,jttft​\(t\)\\widehat\{L\}^\{\\text\{ttft\}\}\_\{i,j\}\(t\)for each model instancejj\.

### 4\.1 Serving Framework Simulation \(SFS\) for latency estimation

We propose*Serving Framework Simulation*\(SFS\), a latency estimator that simulates the serving framework’s batching and scheduling policies at each candidate model instance using the remaining prefill workload and estimated decode workload of resident sequences\. SFS accumulates the predicted processing times of successive token batches until the incoming queryqiq\_\{i\}produces its first decode token, resulting in the TTFT estimateL^i,jttft​\(t\)\\widehat\{L\}^\{\\textrm\{ttft\}\}\_\{i,j\}\(t\)\. We first motivate this design by presenting a simple throughput\-based latency predictor and highlighting its limitations\. We then elaborate how SFS incorporates predicted decode lengths together with a calibrated token\-batch processing time model\.

#### Throughput\-based latency estimator\.

An elementary approach to TTFT estimation for incoming queries computes the remaining prefill workload at each model instance and utilizes the prefill throughput of the model instance to predict latencies\. For each model instancejj, we define the prefill throughputθjpre\\theta^\{\\textrm\{pre\}\}\_\{j\}, measured in tokens per second, as the ratio of the number of prefill tokens processed in a token batch containing a prefill chunk to the time required to process that batch\. We also computeT¯jdec\\bar\{T\}^\{\\textrm\{dec\}\}\_\{j\}, the average decode token batch processing time, which approximates the first decode computation time forqiq\_\{i\}\. At model instancejj, the throughput\-based TTFT estimate \([eq\.˜1](https://arxiv.org/html/2607.18253#S3.E1)\) for a queryqiq\_\{i\}arriving at timettis

L^i,jttft​\(t\)=∑q∈ℛj​\(t\)tokq,jpre​\(t\)θjpre⏟Waiting time​W^i,j​\(t\)\+tokqi,jpre​\(t\)θjpre\+T¯jdec⏟Prefill and first\-token time​P^i,j​\(t\),\\displaystyle\\widehat\{L\}\_\{i,j\}^\{\\textrm\{ttft\}\}\(t\)=\\underbrace\{\\frac\{\\sum\_\{q\\in\\mathcal\{R\}\_\{j\}\(t\)\}\\textrm\{tok\}^\{\\textrm\{pre\}\}\_\{q,j\}\(t\)\}\{\\theta^\{\\textrm\{pre\}\}\_\{j\}\}\}\_\{\\text\{Waiting time \}\\widehat\{W\}\_\{i,j\}\(t\)\}\\quad\+\\\!\\underbrace\{\\frac\{\\textrm\{tok\}^\{\\textrm\{pre\}\}\_\{q\_\{i\},j\}\(t\)\}\{\\theta^\{\\textrm\{pre\}\}\_\{j\}\}\+\\bar\{T\}^\{\\textrm\{dec\}\}\_\{j\}\}\_\{\\text\{Prefill and first\-token time \}\\widehat\{P\}\_\{i,j\}\(t\)\},\(6\)
![Refer to caption](https://arxiv.org/html/2607.18253v1/x2.png)
![Refer to caption](https://arxiv.org/html/2607.18253v1/x3.png)

Figure 2:TTFT estimation using the prefill\-throughput estimator*\(left\)*and the proposed Serving Framework Simulation \(SFS\) estimator*\(right\)*for Qwen3\-0\.6B \(hosted on one H100 GPU\)\. The prefill throughput estimator does not consider decode interference, while SFS simulates autoregressive generation to calculate latencies\.where the estimated waiting timeW^i,j​\(t\)\\widehat\{W\}\_\{i,j\}\(t\)is the sum of the remaining prefill tokens of resident queries at model instancejj, divided by the prefill throughputθjpre\\theta^\{\\textrm\{pre\}\}\_\{j\}, andP^i,j​\(t\)\\widehat\{P\}\_\{i,j\}\(t\)is the estimated prefill computation time plus first decode token generation time for queryqiq\_\{i\}\.

The prefill\-throughput\-based estimator approximates the experienced TTFT latencies using the prefill workload at the model instance\. This approximation aligns with prefill\-prioritizing and prefill\-chunk\-based serving frameworks, where either prefills are computed eagerly upon query arrivals\[[50](https://arxiv.org/html/2607.18253#bib.bib7),[26](https://arxiv.org/html/2607.18253#bib.bib1)\], or chunks of prefill tokens\[[2](https://arxiv.org/html/2607.18253#bib.bib2)\]are interleaved with decode computations to improve hardware utilization\. However, this estimator does not account for decode\-workload interference and its impact on memory and compute utilization at model instances\. Consequently, as shown in[Figure˜2](https://arxiv.org/html/2607.18253#S4.F2)*\(left plot\)*, the throughput\-based estimator suffers bias when the evaluation\-time prefill\-decode workload distribution differs from the throughput profiling workload \(note that the few outliers in both plots in[Figure˜2](https://arxiv.org/html/2607.18253#S4.F2)arise from CPU and kernel overheads\)\.

#### Serving Framework Simulation \(SFS\)\.

To improve beyond the throughput\-based latency estimator described above, we propose the*Serving Framework Simulation*\(SFS\) estimator, which jointly considers the prefill and decode workloads at model instances\. SFS considers the remaining prefill workload\{tokq,jpre​\(t\)\}q∈ℛj​\(t\)\\\{\\textrm\{tok\}^\{\\textrm\{pre\}\}\_\{q,j\}\(t\)\\\}\_\{q\\in\\mathcal\{R\}\_\{j\}\(t\)\}for queries in the current resident setℛj​\(t\)\\mathcal\{R\}\_\{j\}\(t\)at model instancejj, and estimates the remaining decode workload\{tok^q,jdec​\(t\)\}q∈ℛj​\(t\)\\\{\\widehat\{\\textrm\{tok\}\}^\{\\textrm\{dec\}\}\_\{q,j\}\(t\)\\\}\_\{q\\in\\mathcal\{R\}\_\{j\}\(t\)\}by using a decode length estimator \([Section˜B\.4](https://arxiv.org/html/2607.18253#A2.SS4)\)\. The workload of the resident query set is augmented with prefill token length, and decode length estimates\(tokqi,jpre​\(t\),tok^qi,jdec​\(t\)\)\\left\(\\textrm\{tok\}^\{\\textrm\{pre\}\}\_\{q\_\{i\},j\}\(t\),\\widehat\{\\textrm\{tok\}\}^\{\\textrm\{dec\}\}\_\{q\_\{i\},j\}\(t\)\\right\)for the new queryqiq\_\{i\}\. Subsequently, the latency predictor simulates the serving framework’s batching and scheduling policies until the first decode token for sequenceqiq\_\{i\}is generated\. Concretely, when estimating TTFT generation latency at model instancejjfor the arrival of queryqiq\_\{i\}at timett, SFS forms the augmented workload

𝒳i,j​\(t\)=\{\(tokq,jpre​\(t\),tok^q,jdec​\(t\)\):q∈ℛj​\(t\)\}∪\{\(tokqi,jpre​\(t\),tok^qi,jdec​\(t\)\)\}\.\\displaystyle\\mathcal\{X\}\_\{i,j\}\(t\)=\\left\\\{\\left\(\\textrm\{tok\}^\{\\textrm\{pre\}\}\_\{q,j\}\(t\),\\widehat\{\\textrm\{tok\}\}^\{\\textrm\{dec\}\}\_\{q,j\}\(t\)\\right\)\\;:\\;q\\in\\mathcal\{R\}\_\{j\}\(t\)\\right\\\}\\cup\\left\\\{\\left\(\\textrm\{tok\}^\{\\textrm\{pre\}\}\_\{q\_\{i\},j\}\(t\),\\widehat\{\\textrm\{tok\}\}^\{\\textrm\{dec\}\}\_\{q\_\{i\},j\}\(t\)\\right\)\\right\\\}\.Using𝒳i,j​\(t\)\\mathcal\{X\}\_\{i,j\}\(t\), the estimator then deterministically simulates the serving framework, resulting in consecutive token batches for autoregressive generation\. Here, a*token batch*refers to the set of token computations to be performed, consisting of at most one decode token per active decode sequence and possibly a prefill chunk for one or more sequences\[[2](https://arxiv.org/html/2607.18253#bib.bib2)\]\.

Letℬj\(ℓ\)​\(t\)\\mathcal\{B\}^\{\(\\ell\)\}\_\{j\}\(t\)denote theℓth\\ell^\{\\textrm\{th\}\}token batch from timettat model instancejj\. For each sequenceqqbeing processed inℬj\(ℓ\)​\(t\)\\mathcal\{B\}^\{\(\\ell\)\}\_\{j\}\(t\), lettokq,jpre​\(t,ℓ\)\\textrm\{tok\}^\{\\textrm\{pre\}\}\_\{q,j\}\(t,\\ell\)be the number of prefill tokens processed, and lettokq,jdec​\(t,ℓ\)\\textrm\{tok\}^\{\\textrm\{dec\}\}\_\{q,j\}\(t,\\ell\)be the number of decode tokens generated\. In the standard autoregressive generation setting, each sequence produces at most one decode token per batch, sotokq,jdec​\(t,ℓ\)∈\{0,1\}\\textrm\{tok\}^\{\\textrm\{dec\}\}\_\{q,j\}\(t,\\ell\)\\in\\\{0,1\\\}\. The decode stage for a sequence begins only after all prefill tokens have been processed\. Thus, we define the first decode token generation batch of queryqiq\_\{i\}as

ℓjTTFT​\(t,i\)≜min⁡\{ℓ:tokqi,jdec​\(t,ℓ\)=1\}\.\\ell^\{\\textrm\{TTFT\}\}\_\{j\}\(t,i\)\\triangleq\\min\\left\\\{\\ell:\\textrm\{tok\}^\{\\textrm\{dec\}\}\_\{q\_\{i\},j\}\(t,\\ell\)=1\\right\\\}\.\(7\)[Figure˜1](https://arxiv.org/html/2607.18253#S3.F1)illustrates the model instance state and token\-batch composition when a new sequenceqiq\_\{i\}arrives \(*left*\), when its prefill computation begins \(*center*\), and when its first decode token is generated \(*right*\), marking the TTFT forqiq\_\{i\}\. SFS estimates TTFT by summing the predicted processing times of the simulated token batches up to and including the first decode token generation forqiq\_\{i\}:

L^i,jSFS​\(t\)≜∑ℓ=1ℓjTTFT​\(t,i\)T^j\(ℓ\)​\(t\),\\widehat\{L\}^\{\\textrm\{SFS\}\}\_\{i,j\}\(t\)\\triangleq\\sum\_\{\\ell=1\}^\{\\ell^\{\\textrm\{TTFT\}\}\_\{j\}\(t,i\)\}\\widehat\{T\}^\{\(\\ell\)\}\_\{j\}\(t\),\(8\)whereT^j\(ℓ\)​\(t\)\\widehat\{T\}^\{\(\\ell\)\}\_\{j\}\(t\)\(defined next\) denotes the time required to process the token batchℬj\(ℓ\)​\(t\)\\mathcal\{B\}^\{\(\\ell\)\}\_\{j\}\(t\)\. Unlike the prefill\-throughput estimate in[eq\.˜6](https://arxiv.org/html/2607.18253#S4.E6), SFS does not separately approximate waiting, prefill, and first decode token computation using model instance throughputs, instead capturing these components directly via the simulated token batches\.[Figure˜2](https://arxiv.org/html/2607.18253#S4.F2)demonstrates that SFS generates better estimates of TTFT latency compared to the prefill throughput\-based estimator \(5%5\\%vs85%85\\%mean absolute percentage error\) by jointly considering prefill and decode workloads and modeling autoregressive generation at model instances\.

#### Token\-batch processing time estimatorT^j\(ℓ\)​\(t\)\\widehat\{T\}^\{\(\\ell\)\}\_\{j\}\(t\)\.

Processing a token batch at a model instance primarily involves MLP\-layer computation, attention computation, and KV\-cache memory reads\. Modeling each low\-level kernel and memory transfer separately is fragile and difficult to generalize across serving workloads\. We therefore design a higher\-level estimator based on token batch composition\. For each sequenceq∈ℬj\(ℓ\)​\(t\)q\\in\\mathcal\{B\}^\{\(\\ell\)\}\_\{j\}\(t\), letcq,j​\(t,ℓ\)c\_\{q,j\}\(t,\\ell\)denote the context length of sequenceqqbefore token batchℓ\\ellis processed\. We estimate the processing time of token batchℬj\(ℓ\)​\(t\)\\mathcal\{B\}^\{\(\\ell\)\}\_\{j\}\(t\)as

T^j\(ℓ\)​\(t\)=β0,j\\displaystyle\\widehat\{T\}^\{\(\\ell\)\}\_\{j\}\(t\)=\\beta\_\{0,j\}\+β1,j​∑q∈ℬj\(ℓ\)​\(t\)\(tokq,jpre​\(t,ℓ\)\+tokq,jdec​\(t,ℓ\)\)\+β2,j​∑q∈ℬj\(ℓ\)​\(t\)cq,j​\(t,ℓ\)​tokq,jdec​\(t,ℓ\)\\displaystyle\+\\beta\_\{1,j\}\\sum\_\{q\\in\\mathcal\{B\}^\{\(\\ell\)\}\_\{j\}\(t\)\}\\left\(\\textrm\{tok\}^\{\\textrm\{pre\}\}\_\{q,j\}\(t,\\ell\)\+\\textrm\{tok\}^\{\\textrm\{dec\}\}\_\{q,j\}\(t,\\ell\)\\right\)\+\\beta\_\{2,j\}\\sum\_\{q\\in\\mathcal\{B\}^\{\(\\ell\)\}\_\{j\}\(t\)\}c\_\{q,j\}\(t,\\ell\)\\,\\textrm\{tok\}^\{\\textrm\{dec\}\}\_\{q,j\}\(t,\\ell\)\+β3,j​∑q∈ℬj\(ℓ\)​\(t\)\(tokq,jpre​\(t,ℓ\)​cq,j​\(t,ℓ\)\+tokq,jpre​\(t,ℓ\)​\(tokq,jpre​\(t,ℓ\)\+1\)2\)\.\\displaystyle\+\\beta\_\{3,j\}\\sum\_\{q\\in\\mathcal\{B\}^\{\(\\ell\)\}\_\{j\}\(t\)\}\\left\(\\textrm\{tok\}^\{\\textrm\{pre\}\}\_\{q,j\}\(t,\\ell\)c\_\{q,j\}\(t,\\ell\)\+\\frac\{\\textrm\{tok\}^\{\\textrm\{pre\}\}\_\{q,j\}\(t,\\ell\)\\left\(\\textrm\{tok\}^\{\\textrm\{pre\}\}\_\{q,j\}\(t,\\ell\)\+1\\right\)\}\{2\}\\right\)\.\(9\)
![Refer to caption](https://arxiv.org/html/2607.18253v1/x4.png)Figure 3:Token\-batch processing time estimator\.The estimator in[eq\.˜9](https://arxiv.org/html/2607.18253#S4.E9)closely matches observed batch times, with≈4%\\approx\\\!4\\%mean absolute percentage error across token\-batch compositions \(for Qwen3\-0\.6B hosted on one H100 GPU\)\.The intercept term \(β0,j\\beta\_\{0,j\}\) captures fixed per\-batch overheads\. The first workload term \(with coeff\.β1,j\\beta\_\{1,j\}\) captures token\-wise dense\-layer computation, which scales linearly with the number of tokens in a batch\. The second term \(with coeff\.β2,j\\beta\_\{2,j\}\) accounts for the attention computation and KV\-cache reads for each decode sequence, which scales linearly with increasing context\. The third term \(with coeff\.β3,j\\beta\_\{3,j\}\) models prefill attention cost: each prefill token attends both to the existing context and to the preceding tokens within the same prefill chunk, yielding a contribution that grows with the product of the prefill chunk size and prior context length, plus the quadratic attention cost within the chunk\.

The coefficients\(β0,j,β1,j,β2,j,β3,j\)\(\\beta\_\{0,j\},\\beta\_\{1,j\},\\beta\_\{2,j\},\\beta\_\{3,j\}\)are calibrated for each model instance using observed token\-batch processing times\.[Figure˜3](https://arxiv.org/html/2607.18253#S4.F3)shows the estimated token\-batch processing time from[eq\.˜9](https://arxiv.org/html/2607.18253#S4.E9)against the observed batch processing time, demonstrating high accuracy with≈4%\\approx\\\!4\\%mean absolute percentage error\.

SFS is also robust to moderate errors in predicted remaining decode lengths\. The TTFT estimation only requires simulating the autoregressive serving process up to the token batch in which the new query generates its first decode token, rather than until all resident sequences finish generation\. Since each active sequence contributes at most one decode token per token batch, the number of active decode sequences is more important for TTFT estimation than the exact remaining decode length of every resident sequence\.

### 4\.2 Average\-case TTFT estimation without real\-time workload information

In many practical deployments, for example, when an enterprise is routing queries to third\-party cloud servers, the router may not have access to real\-time query workload information, such as the number of resident queries at each model instance and their prefill and decode token composition\. In this scenario, routing decisions need to rely on time\-average quantities such as query arrival rates and model instance service capacities instead of real\-time workload knowledge at model instances\. We therefore construct an average\-case estimator based on a queueing\-theoretic abstraction of model instances and autoregressive generation\.

Modern serving frameworks leverage hardware parallelism via continuous batching\[[50](https://arxiv.org/html/2607.18253#bib.bib7)\], enabling multiple sequences to be served concurrently \(refer[Section˜2](https://arxiv.org/html/2607.18253#S2)\)\. However, this concurrency is limited by memory and hardware constraints and is often controlled as a hyperparameter\[[26](https://arxiv.org/html/2607.18253#bib.bib1)\]\. We model this behavior using the Limited Processor Sharing \(LPS\) queueing system model\[[52](https://arxiv.org/html/2607.18253#bib.bib5)\], where up tokkqueries can be served in parallel by the server, and the rest are placed in a first\-come\-first\-serve \(FCFS\) queue behind thekkqueries until one of them is served\. Because compute capacity is shared equally among active queries, lighter workloads yield faster per\-query processing\. This abstraction is consistent with autoregressive generation on GPUs, where fewer concurrent queries generally result in faster token generation\[[2](https://arxiv.org/html/2607.18253#bib.bib2)\]\.

![Refer to caption](https://arxiv.org/html/2607.18253v1/x5.png)Figure 4:Observed TTFT for sequence generation on Qwen3\-0\.6B \(on single H100 GPU\) compared with theoretical TTFT under the Limited Processor Sharing \(LPS\) model wherekkqueries can be served in parallel\.We estimate the service capacityμj\\mu\_\{j\}\(in queries per second\) of model instancejjfrom its peak generation output throughput\. Consider the average arrival rateαj\\alpha\_\{j\}queries per second, withρj=αj/μj<1\\rho\_\{j\}=\\alpha\_\{j\}/\\mu\_\{j\}<1\. Under Poisson arrivals and assuming memorylessness property of workload distribution across sequences, the expected waiting time under the LPS scheme is

W^i,javg=𝔼​\[Wi,j\]=\(αj/μj\)kμj−αj\.\\widehat\{W\}^\{\\textrm\{avg\}\}\_\{i,j\}=\\mathbb\{E\}\[W\_\{i,j\}\]=\\frac\{\(\\alpha\_\{j\}/\\mu\_\{j\}\)^\{k\}\}\{\\mu\_\{j\}\-\\alpha\_\{j\}\}\.\(10\)The corresponding average\-case TTFT estimator includes the query’s prefill computation time and the average first decode token generation time:

L^i,javg=W^i,javg\+tokqi,jpreθjpre\+T¯jdec\.\\widehat\{L\}^\{\\textrm\{avg\}\}\_\{i,j\}=\\widehat\{W\}^\{\\textrm\{avg\}\}\_\{i,j\}\+\\frac\{\\textrm\{tok\}^\{\\textrm\{pre\}\}\_\{q\_\{i\},j\}\}\{\\theta^\{\\textrm\{pre\}\}\_\{j\}\}\+\\bar\{T\}^\{\\textrm\{dec\}\}\_\{j\}\.\(11\)We defer the derivation to[Appendix˜E](https://arxiv.org/html/2607.18253#A5)\.[Figure˜4](https://arxiv.org/html/2607.18253#S4.F4)shows that this abstraction captures the qualitative growth of waiting time with load and that the observed system behavior is consistent with a finite\-parallelism serving model \(the observed time average parallelism for the setup in[Figure˜4](https://arxiv.org/html/2607.18253#S4.F4)isk≈25k\\\!\\approx\\\!25\)\.

## 5 Experiments

#### Experimental setup\.

In our analysis, we sample queries from four tasks:Alpaca\[[46](https://arxiv.org/html/2607.18253#bib.bib37)\],HotpotQA\[[49](https://arxiv.org/html/2607.18253#bib.bib36)\],GovReport\-Summarization\[[21](https://arxiv.org/html/2607.18253#bib.bib38)\], andWritingPrompts\[[13](https://arxiv.org/html/2607.18253#bib.bib39)\]\. The four tasks represent varying \(input, output\) token length distributions for queries, with \(short, short\), \(long, short\), \(long, long\), and \(short, long\) types, respectively\. We sample2\.52\.5K queries from each task to estimate per\-instance prefill throughput, calibrate the token\-batch processing time estimators, and train output length and response quality predictors\. We simulate query arrivals based on a Poisson process \([Figures˜5](https://arxiv.org/html/2607.18253#S5.F5)and[6](https://arxiv.org/html/2607.18253#S5.F6)\), and also generalize to bursty arrivals based on a Markov\-Modulated Poisson process \([Figure˜8](https://arxiv.org/html/2607.18253#S5.F8)\)\.

We consider three language models:Qwen3\-0\.6B,Qwen3\-8B, andQwen3\-32Bfrom the Qwen3 family\[[42](https://arxiv.org/html/2607.18253#bib.bib40)\], covering a range of sizes and capabilities\. We deploy Qwen3\-0\.6B and Qwen3\-8B on one H100 GPU\[[35](https://arxiv.org/html/2607.18253#bib.bib41)\]each, and Qwen3\-32B on two H100 GPUs \(using tensor parallelism\), characterizing three model instances\. We use the vLLM\[[26](https://arxiv.org/html/2607.18253#bib.bib1)\]serving framework for our experiments; however, our presented latency estimators can be easily extended to other serving frameworks as well\. We evaluate the responses generated by models on queries via LLM\-as\-a\-judge\[[29](https://arxiv.org/html/2607.18253#bib.bib42)\]using Gemini 3\.1 Pro Preview\[[16](https://arxiv.org/html/2607.18253#bib.bib9)\]\(evaluation prompt provided in[Appendix˜D](https://arxiv.org/html/2607.18253#A4)\)\. We discuss further experimental details in[Appendix˜B](https://arxiv.org/html/2607.18253#A2)\.

#### Baselines\.

We compare the proposed latency\-aware router, using the*Serving Framework Simulation \(SFS\)*based TTFT estimator against three baselines\.*Round Robin*policy assigns queries cyclically across model instances, independent of workload, utility, or latency\. The*Shortest Queue*policy routes each incoming query to the instance with the fewest resident requests, explicitly targeting low workload to minimize generation latencies\. Finally, the*Latency\-Agnostic*policy routes solely based on maximum utility, ignoring generation latencies\.

![Refer to caption](https://arxiv.org/html/2607.18253v1/x6.png)Figure 5:OnTimeUtility across varying arrival rate \(in qps\)\. Latency\-aware routing \(SFS\) balances utility and latency to maintain high OnTimeUtility, demonstrating33%33\\%higher AUC\.
#### Overview of results\.

We examine latency\-aware routing from two complementary perspectives\. First, we vary the offered query load under the latency\-constrained routing objective in[eq\.˜3](https://arxiv.org/html/2607.18253#S3.E3)\. Second, we vary the latency penalty parameterδ\\deltaunder the Lagrangian relaxation of latency\-constrained routing \([eq\.˜5](https://arxiv.org/html/2607.18253#S3.E5)\)\. For both these scenarios, we keep the cost coefficientλ\\lambdafixed \(at5×10−45\\\!\\times\\\!10^\{\-4\}\) and defer sweeps overλ\\lambdato[Appendix˜G](https://arxiv.org/html/2607.18253#A7)\. We further present the performance of our approach across bursty query arrivals and comment on the overhead introduced by the serving framework simulation\-based latency estimation\.

#### Varying offered load\.

As the arrival rate of queries increases, the model instances become saturated and the feasible set of instances that satisfy queries’ latency constraints shrinks\. In such scenarios, a better router will yield a higher*OnTimeUtility*value \([eq\.˜4](https://arxiv.org/html/2607.18253#S3.E4)\) for latency\-constrained routing \([eq\.˜3](https://arxiv.org/html/2607.18253#S3.E3)\) across a wide range of query workloads\.[Figure˜5](https://arxiv.org/html/2607.18253#S5.F5)shows that our proposed Serving Framework Simulation \(SFS\) for latency estimation achieves the highest*OnTimeUtility*across all query workloads, yielding a𝟑𝟑%\\mathbf\{33\\%\}gainin terms of area\-under\-the\-curve \(AUC\) over the best baseline, and𝟒𝟔%\\mathbf\{46\\%\}improvementin OnTimeUtility \(at5\\\!5qps\)\. The*Shortest Queue*policy achieves low latencies, but it is agnostic to the query’s model preferences\. The*Round Robin*policy is oblivious to both model instance saturation and query preferences\.*Latency\-Agnostic*routing prioritizes query preferences and yields high utility when desired model instances are available, but its performance degrades with increasing workloads\.

![Refer to caption](https://arxiv.org/html/2607.18253v1/x7.png)Figure 6:Utilities plotted against TTFT latencies by varyingδ\\deltain[eq\.˜5](https://arxiv.org/html/2607.18253#S3.E5)\. Latency\-aware routing provides a controllable utility–latency tradeoff\.
#### Varying latency emphasis\.

To analyze the trade\-off between utility and latency, we varyδ\\deltavalues in[eq\.˜5](https://arxiv.org/html/2607.18253#S3.E5)and obtain average utility and latency values for queries \(following the Poisson arrival process with rate=8=\\\!8qps\)\.[Figure˜6](https://arxiv.org/html/2607.18253#S5.F6)shows that our proposed approach consistently improves the utility–latency performance over the baselines, resulting in𝟒𝟎%\\mathbf\{40\\%\}higher utilitythan*Shortest Queue*policy, and importantly, provides a controllable tradeoff which can be set by choosing the correspondingδ\\deltavalue\. Settingδ=0\\delta\\\!=\\\!0recovers the*Latency\-Agnostic*routing policy\. The*Round Robin*and*Shortest Queue*baselines balance model instance workload in some regimes but do not exploit the heterogeneous accuracy–cost structure of the model instance pool and therefore attain substantially worse realized utility than our method for comparable latency values\.

![Refer to caption](https://arxiv.org/html/2607.18253v1/x8.png)Figure 7:OnTimeUtility for routers under query arrivals from a Markov\-modulated Poisson process with high\-to\-low arrival\-rate ratior=3,6r\\\!=\\\!3,6\. Our proposed approach improves OnTimeUtility across query arrival processes\.
![Refer to caption](https://arxiv.org/html/2607.18253v1/x9.png)Figure 8:Wall\-clock overhead of the SFS \(ours\) latency estimator\. Mean simulation latency of≈10−4\\approx\\\!10^\{\-4\}s indicates negligible routing\-time overhead for latency estimation \([Section˜4\.1](https://arxiv.org/html/2607.18253#S4.SS1)\)\.

#### Evaluation across arrival processes\.

In practical deployments, query arrivals are often correlated and bursty, which may not be captured well by the standard Poisson arrival process\. We extend our analysis to query arrivals based on a two\-state Markov Modulated Poisson Process \(MMPP\-2\)\[[14](https://arxiv.org/html/2607.18253#bib.bib52)\]\([Appendix˜C](https://arxiv.org/html/2607.18253#A3)\), where the low\-state denotes standard query arrivals \(rateλL\\lambda\_\{L\}\) and a high\-state indicates a duration of heavy workload \(with arrival rateλH\\lambda\_\{H\}\)\. The ratio of the high\- and low\-state arrival rates indicates the level of burstiness in query arrivals\.[Figure˜8](https://arxiv.org/html/2607.18253#S5.F8)illustrates consistently higher performance of our approach across arrival processes and average arrival rates\.

#### Estimator overhead\.

Since estimating latencies for queries at model instances lies on the critical path of routing, latency estimators should not induce high computational overhead\. Our proposed SFS latency estimator simulates batching policies from the current workload state \(including the newly arrived query\) and halts at the token batch corresponding to first token generation for this new sequence\. This avoids full simulation till completion of all resident requests at the model instance\.[Figure˜8](https://arxiv.org/html/2607.18253#S5.F8)depicts an average latency estimationtime overhead of≈𝟏𝟎−𝟒\\mathbf\{\\approx\\\!10^\{\-4\}\}s, which is negligible relative to query generation TTFTs \(usually in seconds\[[26](https://arxiv.org/html/2607.18253#bib.bib1)\]\)\. Further implementation details of the SFS estimator are provided in[Appendix˜F](https://arxiv.org/html/2607.18253#A6)\.

## 6 Concluding remarks

Most existing language query routers optimize the accuracy–cost trade\-off, but do not account for latencies experienced by queries\. We proposed a latency\-aware routing framework that jointly optimizes accuracy, cost, and time\-to\-first\-token \(TTFT\) latency\. The core component of our approach is a lightweight Serving Framework Simulation \(SFS\) latency estimator that predicts TTFT by simulating prefill and decode token batches under the serving framework’s policies\. By incorporating these estimates into routing decisions, our approach avoids overloaded instances while preserving strong accuracy–cost performance\. Our experiments show that joint accuracy–cost–latency optimization can substantially improve utility \(by over𝟒𝟎%\\mathbf\{40\\%\}\) as compared to standard load\-balancing baselines at comparable latencies\. Future directions include joint optimization of routing and model placement, and studying the interactions between routers that independently send queries to shared model instances\.

## Acknowledgments

This work was partially supported by NSF grants CCF 2045694, CNS\-2112471, CPS\-2111751, CCF\-2428569, ONR grant N00014\-23\-1\-2149, an AI2C Seed grant, and a Gemini Academic Program Award\. This work used Bridges\-2 GPU at the Pittsburgh Supercomputing Center through allocation CIS250429 from the Advanced Cyberinfrastructure Coordination Ecosystem: Services & Support \(ACCESS\) program, which is supported by NSF grants \#2138259, \#2138286, \#2138307, \#2137603, and \#2138296\[[6](https://arxiv.org/html/2607.18253#bib.bib43)\]\.

## References

- \[1\]A\. Agrawal, N\. Kedia, J\. Mohan, A\. Panwar, N\. Kwatra, B\. S\. Gulavani, R\. Ramjee, and A\. Tumanov\(2024\-05\)VIDUR: a large\-scale simulation framework for llm inference\.InMLSys,Cited by:[Appendix A](https://arxiv.org/html/2607.18253#A1.SS0.SSS0.Px3.p1.1)\.
- \[2\]A\. Agrawal, N\. Kedia, A\. Panwar, J\. Mohan, N\. Kwatra, B\. S\. Gulavani, A\. Tumanov, and R\. Ramjee\(2024\)Taming throughput\-latency tradeoff in llm inference with sarathi\-serve\.InProceedings of the 18th USENIX Conference on Operating Systems Design and Implementation,OSDI’24,USA\.External Links:ISBN 978\-1\-939133\-40\-3Cited by:[Appendix E](https://arxiv.org/html/2607.18253#A5.p1.4),[§1](https://arxiv.org/html/2607.18253#S1.SS0.SSS0.Px2.p1.1),[§2](https://arxiv.org/html/2607.18253#S2.SS0.SSS0.Px1.p1.1),[§2](https://arxiv.org/html/2607.18253#S2.SS0.SSS0.Px3.p1.1),[§4\.1](https://arxiv.org/html/2607.18253#S4.SS1.SSS0.Px1.p3.1),[§4\.1](https://arxiv.org/html/2607.18253#S4.SS1.SSS0.Px2.p1.11),[§4\.2](https://arxiv.org/html/2607.18253#S4.SS2.p2.2)\.
- \[3\]Alibaba Cloud\(2026\)Alibaba cloud model studio: model invocation pricing\.Note:Alibaba Cloud Documentation Center, accessed Apr\. 17, 2026External Links:[Link](https://www.alibabacloud.com/help/en/model-studio/model-pricing)Cited by:[Table 1](https://arxiv.org/html/2607.18253#A2.T1),[Table 1](https://arxiv.org/html/2607.18253#A2.T1.3.2)\.
- \[4\]B\. Askin, S\. Patel, A\. Nayak, A\. Vigano, J\. Woo, G\. Joshi, and C\. Joe\-Wong\(2026\)Federate the router: learning language model routers with sparse and decentralized evaluations\.External Links:2601\.22318,[Link](https://arxiv.org/abs/2601.22318)Cited by:[Appendix A](https://arxiv.org/html/2607.18253#A1.SS0.SSS0.Px1.p1.1)\.
- \[5\]A\. Bari, P\. Hegde, and G\. de Veciana\(2025\-12\)Optimal scheduling algorithms for llm inference: theory and practice\.Proc\. ACM Meas\. Anal\. Comput\. Syst\.9\(3\)\.External Links:[Link](https://doi.org/10.1145/3771574),[Document](https://dx.doi.org/10.1145/3771574)Cited by:[Appendix A](https://arxiv.org/html/2607.18253#A1.SS0.SSS0.Px2.p1.1)\.
- \[6\]T\. J\. Boerner, S\. Deems, T\. R\. Furlani, S\. L\. Knuth, and J\. Towns\(2023\)ACCESS: advancing innovation: nsf’s advanced cyberinfrastructure coordination ecosystem: services & support\.InPractice and Experience in Advanced Research Computing 2023: Computing for the Common Good,PEARC ’23,New York, NY, USA,pp\. 173–176\.External Links:ISBN 9781450399852,[Link](https://doi.org/10.1145/3569951.3597559),[Document](https://dx.doi.org/10.1145/3569951.3597559)Cited by:[Acknowledgments](https://arxiv.org/html/2607.18253#Sx1.p1.1)\.
- \[7\]J\. Chen, C\. Wang, G\. Zhang, P\. Ye, L\. Bai, W\. Hu, Y\. Qu, and S\. Hu\(2025\)Learning compact representations of llm abilities via item response theory\.External Links:2510\.00844,[Link](https://arxiv.org/abs/2510.00844)Cited by:[Appendix A](https://arxiv.org/html/2607.18253#A1.SS0.SSS0.Px1.p1.1)\.
- \[8\]L\. Chen, M\. Zaharia, and J\. Zou\(2024\)FrugalGPT: how to use large language models while reducing cost and improving performance\.Transactions on Machine Learning Research\.Cited by:[Appendix A](https://arxiv.org/html/2607.18253#A1.SS0.SSS0.Px1.p1.1)\.
- \[9\]W\. Da and E\. Kalyvianaki\(2025\)Block: balancing load in llm serving with context, knowledge and predictive scheduling\.External Links:2508\.03611,[Link](https://arxiv.org/abs/2508.03611)Cited by:[Appendix A](https://arxiv.org/html/2607.18253#A1.SS0.SSS0.Px4.p1.1),[§1](https://arxiv.org/html/2607.18253#S1.SS0.SSS0.Px1.p1.1)\.
- \[10\]J\. Dekoninck, M\. Baader, and M\. Vechev\(2025\)A unified approach to routing and cascading for LLMs\.InForty\-second International Conference on Machine Learning,Cited by:[Appendix A](https://arxiv.org/html/2607.18253#A1.SS0.SSS0.Px1.p1.1),[§1](https://arxiv.org/html/2607.18253#S1.SS0.SSS0.Px1.p1.1)\.
- \[11\]D\. Ding, A\. Mallick, C\. Wang, R\. Sim, S\. Mukherjee, V\. Rühle, L\. V\. S\. Lakshmanan, and A\. H\. Awadallah\(2024\)Hybrid LLM: cost\-efficient and quality\-aware query routing\.InThe Twelfth International Conference on Learning Representations,Cited by:[Appendix A](https://arxiv.org/html/2607.18253#A1.SS0.SSS0.Px1.p1.1),[§1](https://arxiv.org/html/2607.18253#S1.SS0.SSS0.Px1.p1.1),[§1](https://arxiv.org/html/2607.18253#S1.SS0.SSS0.Px2.p1.1),[§1](https://arxiv.org/html/2607.18253#S1.p1.1)\.
- \[12\]D\. Ding, A\. Mallick, S\. Zhang, C\. Wang, D\. Madrigal, M\. D\. C\. H\. Garcia, M\. Xia, L\. V\. S\. Lakshmanan, Q\. Wu, and V\. Rühle\(2025\)BEST\-route: adaptive LLM routing with test\-time optimal compute\.InForty\-second International Conference on Machine Learning,Cited by:[Appendix A](https://arxiv.org/html/2607.18253#A1.SS0.SSS0.Px1.p1.1),[§1](https://arxiv.org/html/2607.18253#S1.SS0.SSS0.Px1.p1.1),[§1](https://arxiv.org/html/2607.18253#S1.p1.1)\.
- \[13\]A\. Fan, M\. Lewis, and Y\. Dauphin\(2018\-07\)Hierarchical neural story generation\.InProceedings of the 56th Annual Meeting of the Association for Computational Linguistics \(Volume 1: Long Papers\),I\. Gurevych and Y\. Miyao \(Eds\.\),Melbourne, Australia,pp\. 889–898\.External Links:[Link](https://aclanthology.org/P18-1082/),[Document](https://dx.doi.org/10.18653/v1/P18-1082)Cited by:[Figure 9](https://arxiv.org/html/2607.18253#A2.F9),[Figure 9](https://arxiv.org/html/2607.18253#A2.F9.2.1),[Table 2](https://arxiv.org/html/2607.18253#A2.T2),[Table 2](https://arxiv.org/html/2607.18253#A2.T2.3.2),[§5](https://arxiv.org/html/2607.18253#S5.SS0.SSS0.Px1.p1.1)\.
- \[14\]W\. Fischer and K\. Meier\-Hellstern\(1993\)The markov\-modulated poisson process \(mmpp\) cookbook\.Performance Evaluation18\(2\),pp\. 149–171\.External Links:ISSN 0166\-5316,[Document](https://dx.doi.org/https%3A//doi.org/10.1016/0166-5316%2893%2990035-S),[Link](https://www.sciencedirect.com/science/article/pii/016653169390035S)Cited by:[Appendix C](https://arxiv.org/html/2607.18253#A3.p1.7),[§5](https://arxiv.org/html/2607.18253#S5.SS0.SSS0.Px6.p1.2)\.
- \[15\]Y\. Fu, S\. Zhu, R\. Su, A\. Qiao, I\. Stoica, and H\. Zhang\(2024\)Efficient LLM scheduling by learning to rank\.InThe Thirty\-eighth Annual Conference on Neural Information Processing Systems,External Links:[Link](https://openreview.net/forum?id=wlLjYl0Gi6)Cited by:[Appendix A](https://arxiv.org/html/2607.18253#A1.SS0.SSS0.Px4.p1.1),[§1](https://arxiv.org/html/2607.18253#S1.SS0.SSS0.Px1.p1.1)\.
- \[16\]Gemini Team\(2025\)Gemini: a family of highly capable multimodal models\.External Links:2312\.11805,[Link](https://arxiv.org/abs/2312.11805)Cited by:[Appendix D](https://arxiv.org/html/2607.18253#A4.p1.1),[§5](https://arxiv.org/html/2607.18253#S5.SS0.SSS0.Px1.p2.1)\.
- \[17\]R\. Gong, S\. Bai, S\. Wu, Y\. Fan, Z\. Wang, X\. Li, H\. Yang, and X\. Liu\(2025\)Past\-future scheduler for llm serving under sla guarantees\.InProceedings of the 30th ACM International Conference on Architectural Support for Programming Languages and Operating Systems, Volume 2,ASPLOS ’25,New York, NY, USA,pp\. 798–813\.External Links:ISBN 9798400710797,[Link](https://doi.org/10.1145/3676641.3716011),[Document](https://dx.doi.org/10.1145/3676641.3716011)Cited by:[Appendix A](https://arxiv.org/html/2607.18253#A1.SS0.SSS0.Px4.p1.1)\.
- \[18\]J\. Gu, J\. Bradbury, C\. Xiong, V\. O\.K\. Li, and R\. Socher\(2018\)Non\-autoregressive neural machine translation\.InInternational Conference on Learning Representations,External Links:[Link](https://openreview.net/forum?id=B1l8BtlCb)Cited by:[§2](https://arxiv.org/html/2607.18253#S2.SS0.SSS0.Px1.p1.1)\.
- \[19\]Q\. J\. Hu, J\. Bieker, X\. Li, N\. Jiang, B\. Keigwin, G\. Ranganath, K\. Keutzer, and S\. K\. Upadhyay\(2024\)RouterBench: a benchmark for multi\-LLM routing system\.InAgentic Markets Workshop at ICML 2024,External Links:[Link](https://openreview.net/forum?id=IVXmV8Uxwh)Cited by:[Appendix A](https://arxiv.org/html/2607.18253#A1.SS0.SSS0.Px1.p1.1),[§3](https://arxiv.org/html/2607.18253#S3.SS0.SSS0.Px3.p1.5)\.
- \[20\]J\. Huang, Y\. Xiong, X\. Yu, W\. Huang, E\. Li, L\. Zeng, and X\. Chen\(2025\)SLO\-aware scheduling for large language model inferences\.External Links:2504\.14966,[Link](https://arxiv.org/abs/2504.14966)Cited by:[Appendix A](https://arxiv.org/html/2607.18253#A1.SS0.SSS0.Px2.p1.1),[§1](https://arxiv.org/html/2607.18253#S1.SS0.SSS0.Px1.p1.1)\.
- \[21\]L\. Huang, S\. Cao, N\. Parulian, H\. Ji, and L\. Wang\(2021\-06\)Efficient attentions for long document summarization\.InProceedings of the 2021 Conference of the North American Chapter of the Association for Computational Linguistics: Human Language Technologies,K\. Toutanova, A\. Rumshisky, L\. Zettlemoyer, D\. Hakkani\-Tur, I\. Beltagy, S\. Bethard, R\. Cotterell, T\. Chakraborty, and Y\. Zhou \(Eds\.\),Online,pp\. 1419–1436\.External Links:[Link](https://aclanthology.org/2021.naacl-main.112/),[Document](https://dx.doi.org/10.18653/v1/2021.naacl-main.112)Cited by:[Figure 9](https://arxiv.org/html/2607.18253#A2.F9),[Figure 9](https://arxiv.org/html/2607.18253#A2.F9.2.1),[Table 2](https://arxiv.org/html/2607.18253#A2.T2),[Table 2](https://arxiv.org/html/2607.18253#A2.T2.3.2),[§5](https://arxiv.org/html/2607.18253#S5.SS0.SSS0.Px1.p1.1)\.
- \[22\]S\. Imai, R\. Nakazawa, M\. Amaral, S\. Choochotkaew, and T\. Chiba\(2024\)Predicting llm inference latency: a roofline\-driven ml method\.InML for Systems Workshop, Annual Conference on Neural Information Processing Systems,Cited by:[Appendix A](https://arxiv.org/html/2607.18253#A1.SS0.SSS0.Px3.p1.1)\.
- \[23\]K\. Jain, A\. Parayil, A\. Mallick, E\. Choukse, X\. Qin, J\. Zhang, Í\. Goiri, R\. Wang, C\. Bansal, V\. Rühle, A\. Kulkarni, S\. Kofsky, and S\. Rajmohan\(2025\)Performance aware llm load balancer for mixed workloads\.InProceedings of the 5th Workshop on Machine Learning and Systems,EuroMLSys ’25,New York, NY, USA,pp\. 19–30\.External Links:ISBN 9798400715389,[Link](https://doi.org/10.1145/3721146.3721947),[Document](https://dx.doi.org/10.1145/3721146.3721947)Cited by:[Appendix A](https://arxiv.org/html/2607.18253#A1.SS0.SSS0.Px3.p1.1),[§1](https://arxiv.org/html/2607.18253#S1.SS0.SSS0.Px1.p1.1)\.
- \[24\]W\. Jitkrittum, H\. Narasimhan, A\. S\. Rawat, J\. Juneja, C\. Wang, Z\. Wang, A\. Go, C\. Lee, P\. Shenoy, R\. Panigrahy, A\. K\. Menon, and S\. Kumar\(2026\)Universal model routing for efficient LLM inference\.InThe Fourteenth International Conference on Learning Representations,Cited by:[Appendix A](https://arxiv.org/html/2607.18253#A1.SS0.SSS0.Px1.p1.1),[§1](https://arxiv.org/html/2607.18253#S1.SS0.SSS0.Px1.p1.1),[§1](https://arxiv.org/html/2607.18253#S1.SS0.SSS0.Px2.p1.1),[§1](https://arxiv.org/html/2607.18253#S1.p1.1),[§3](https://arxiv.org/html/2607.18253#S3.SS0.SSS0.Px3.p1.5)\.
- \[25\]G\. Ke, Q\. Meng, T\. Finley, T\. Wang, W\. Chen, W\. Ma, Q\. Ye, and T\. Liu\(2017\)LightGBM: a highly efficient gradient boosting decision tree\.InAdvances in Neural Information Processing Systems,I\. Guyon, U\. V\. Luxburg, S\. Bengio, H\. Wallach, R\. Fergus, S\. Vishwanathan, and R\. Garnett \(Eds\.\),Vol\.30,pp\.\.External Links:[Link](https://proceedings.neurips.cc/paper_files/paper/2017/file/6449f44a102fde848669bdd9eb6b76fa-Paper.pdf)Cited by:[§B\.4](https://arxiv.org/html/2607.18253#A2.SS4.p1.1),[§B\.4](https://arxiv.org/html/2607.18253#A2.SS4.p2.1)\.
- \[26\]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,SOSP ’23,New York, NY, USA,pp\. 611–626\.External Links:ISBN 9798400702297,[Link](https://doi.org/10.1145/3600006.3613165),[Document](https://dx.doi.org/10.1145/3600006.3613165)Cited by:[Appendix E](https://arxiv.org/html/2607.18253#A5.p1.4),[§1](https://arxiv.org/html/2607.18253#S1.SS0.SSS0.Px2.p1.1),[§2](https://arxiv.org/html/2607.18253#S2.SS0.SSS0.Px1.p1.1),[§2](https://arxiv.org/html/2607.18253#S2.SS0.SSS0.Px2.p1.1),[§2](https://arxiv.org/html/2607.18253#S2.SS0.SSS0.Px3.p1.1),[§4\.1](https://arxiv.org/html/2607.18253#S4.SS1.SSS0.Px1.p3.1),[§4\.2](https://arxiv.org/html/2607.18253#S4.SS2.p2.2),[§5](https://arxiv.org/html/2607.18253#S5.SS0.SSS0.Px1.p2.1),[§5](https://arxiv.org/html/2607.18253#S5.SS0.SSS0.Px7.p1.1)\.
- \[27\]J\. Lakha, M\. Yu, and R\. Shahout\(2025\)Faster, cheaper, just as good: cost\- and latency constrained routing for llms\.InSparsity in LLMs \(SLLM\): Deep Dive into Mixture of Experts, Quantization, Hardware, and Inference,External Links:[Link](https://openreview.net/forum?id=pZFJLsIY2m)Cited by:[Appendix A](https://arxiv.org/html/2607.18253#A1.SS0.SSS0.Px3.p1.1),[§1](https://arxiv.org/html/2607.18253#S1.SS0.SSS0.Px3.p1.1)\.
- \[28\]J\. Lee, E\. Mansimov, and K\. Cho\(2018\-October\-November\)Deterministic non\-autoregressive neural sequence modeling by iterative refinement\.InProceedings of the 2018 Conference on Empirical Methods in Natural Language Processing,E\. Riloff, D\. Chiang, J\. Hockenmaier, and J\. Tsujii \(Eds\.\),Brussels, Belgium,pp\. 1173–1182\.External Links:[Link](https://aclanthology.org/D18-1149/),[Document](https://dx.doi.org/10.18653/v1/D18-1149)Cited by:[§2](https://arxiv.org/html/2607.18253#S2.SS0.SSS0.Px1.p1.1)\.
- \[29\]D\. Li, B\. Jiang, L\. Huang, A\. Beigi, C\. Zhao, Z\. Tan, A\. Bhattacharjee, Y\. Jiang, C\. Chen, T\. Wu, K\. Shu, L\. Cheng, and H\. Liu\(2025\-11\)From generation to judgment: opportunities and challenges of LLM\-as\-a\-judge\.InProceedings of the 2025 Conference on Empirical Methods in Natural Language Processing,C\. Christodoulopoulos, T\. Chakraborty, C\. Rose, and V\. Peng \(Eds\.\),Suzhou, China,pp\. 2757–2791\.External Links:[Link](https://aclanthology.org/2025.emnlp-main.138/),[Document](https://dx.doi.org/10.18653/v1/2025.emnlp-main.138),ISBN 979\-8\-89176\-332\-6Cited by:[§B\.1](https://arxiv.org/html/2607.18253#A2.SS1.p1.1),[Table 2](https://arxiv.org/html/2607.18253#A2.T2),[Table 2](https://arxiv.org/html/2607.18253#A2.T2.3.2),[§3](https://arxiv.org/html/2607.18253#S3.SS0.SSS0.Px3.p1.5),[§5](https://arxiv.org/html/2607.18253#S5.SS0.SSS0.Px1.p2.1)\.
- \[30\]X\. L\. Li, J\. Thickstun, I\. Gulrajani, P\. Liang, and T\. Hashimoto\(2022\)Diffusion\-LM improves controllable text generation\.InAdvances in Neural Information Processing Systems,A\. H\. Oh, A\. Agarwal, D\. Belgrave, and K\. Cho \(Eds\.\),External Links:[Link](https://openreview.net/forum?id=3s9IrEsjLyk)Cited by:[§2](https://arxiv.org/html/2607.18253#S2.SS0.SSS0.Px1.p1.1)\.
- \[31\]Y\. Li, J\. Dai, and T\. Peng\(2025\)Throughput\-optimal scheduling algorithms for llm inference and ai agents\.External Links:2504\.07347,[Link](https://arxiv.org/abs/2504.07347)Cited by:[Appendix A](https://arxiv.org/html/2607.18253#A1.SS0.SSS0.Px2.p1.1)\.
- \[32\]C\. Lin\(2004\-07\)ROUGE: a package for automatic evaluation of summaries\.InText Summarization Branches Out,Barcelona, Spain,pp\. 74–81\.External Links:[Link](https://aclanthology.org/W04-1013/)Cited by:[§3](https://arxiv.org/html/2607.18253#S3.SS0.SSS0.Px3.p1.5)\.
- \[33\]M\. Mitzenmacher and R\. Shahout\(2025\)Queueing, predictions, and llms: challenges and open problems\.External Links:2503\.07545,[Link](https://arxiv.org/abs/2503.07545)Cited by:[Appendix A](https://arxiv.org/html/2607.18253#A1.SS0.SSS0.Px2.p1.1)\.
- \[34\]M\. Mohanty, G\. Bolar, P\. Patil, U\. Devi, F\. George, P\. Moogi, and P\. Parag\(2025\)Deferred prefill for throughput maximization in llm inference\.InProceedings of the 5th Workshop on Machine Learning and Systems,EuroMLSys ’25,New York, NY, USA,pp\. 100–106\.External Links:ISBN 9798400715389,[Link](https://doi.org/10.1145/3721146.3721962),[Document](https://dx.doi.org/10.1145/3721146.3721962)Cited by:[item 2](https://arxiv.org/html/2607.18253#A5.I1.i2.p1.1)\.
- \[35\]NVIDIA Corporation\(2022\-09\)NVIDIA h100 pcie gpu — product brief\.Technical reportTechnical ReportPB\-11133\-001,NVIDIA\.External Links:[Link](https://www.nvidia.com/content/dam/en-zz/Solutions/gtcs22/data-center/h100/PB-11133-001_v01.pdf)Cited by:[§5](https://arxiv.org/html/2607.18253#S5.SS0.SSS0.Px1.p2.1)\.
- \[36\]I\. Ong, A\. Almahairi, V\. Wu, W\. Chiang, T\. Wu, J\. E\. Gonzalez, M\. W\. Kadous, and I\. Stoica\(2025\)RouteLLM: learning to route LLMs from preference data\.InThe Thirteenth International Conference on Learning Representations,Cited by:[Appendix A](https://arxiv.org/html/2607.18253#A1.SS0.SSS0.Px1.p1.1),[§1](https://arxiv.org/html/2607.18253#S1.SS0.SSS0.Px1.p1.1),[§1](https://arxiv.org/html/2607.18253#S1.p1.1)\.
- \[37\]S\. Patel, W\. Cocke, and G\. Joshi\(2026\)LOCUS: low\-dimensional model embeddings for efficient model exploration, comparison, and selection\.External Links:2601\.21082,[Link](https://arxiv.org/abs/2601.21082)Cited by:[Appendix A](https://arxiv.org/html/2607.18253#A1.SS0.SSS0.Px1.p1.1)\.
- \[38\]S\. Patel, N\. Jali, A\. Mallick, and G\. Joshi\(2025\)ProxRouter: proximity\-weighted llm query routing for improved robustness to outliers\.External Links:2510\.09852,[Link](https://arxiv.org/abs/2510.09852)Cited by:[Appendix A](https://arxiv.org/html/2607.18253#A1.SS0.SSS0.Px1.p1.1),[§1](https://arxiv.org/html/2607.18253#S1.SS0.SSS0.Px1.p1.1),[§1](https://arxiv.org/html/2607.18253#S1.SS0.SSS0.Px2.p1.1),[§1](https://arxiv.org/html/2607.18253#S1.p1.1),[§3](https://arxiv.org/html/2607.18253#S3.SS0.SSS0.Px3.p1.5)\.
- \[39\]A\. Patke, D\. Reddy, S\. Jha, H\. Qiu, C\. Pinto, C\. Narayanaswami, Z\. Kalbarczyk, and R\. Iyer\(2024\)Queue management for slo\-oriented large language model serving\.InProceedings of the 2024 ACM Symposium on Cloud Computing,SoCC ’24,New York, NY, USA,pp\. 18–35\.External Links:ISBN 9798400712869,[Link](https://doi.org/10.1145/3698038.3698523),[Document](https://dx.doi.org/10.1145/3698038.3698523)Cited by:[Appendix A](https://arxiv.org/html/2607.18253#A1.SS0.SSS0.Px2.p1.1),[§1](https://arxiv.org/html/2607.18253#S1.SS0.SSS0.Px1.p1.1)\.
- \[40\]R\. Pope, S\. Douglas, A\. Chowdhery, J\. Devlin, J\. Bradbury, J\. Heek, K\. Xiao, S\. Agrawal, and J\. Dean\(2023\)Efficiently scaling transformer inference\.InProceedings of Machine Learning and Systems,D\. Song, M\. Carbin, and T\. Chen \(Eds\.\),Vol\.5,pp\. 606–624\.External Links:[Link](https://proceedings.mlsys.org/paper_files/paper/2023/file/c4be71ab8d24cdfb45e3d06dbfca2780-Paper-mlsys2023.pdf)Cited by:[§2](https://arxiv.org/html/2607.18253#S2.SS0.SSS0.Px1.p1.1)\.
- \[41\]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\.InThe 5th International Workshop on Cloud Intelligence / AIOps at ASPLOS 2024,Vol\.5,San Diego, CA, USA,pp\. 1–7\.Cited by:[Appendix A](https://arxiv.org/html/2607.18253#A1.SS0.SSS0.Px4.p1.1),[§1](https://arxiv.org/html/2607.18253#S1.SS0.SSS0.Px1.p1.1)\.
- \[42\]Qwen\(2025\)Qwen3 technical report\.External Links:2505\.09388,[Link](https://arxiv.org/abs/2505.09388)Cited by:[Figure 10](https://arxiv.org/html/2607.18253#A2.F10),[Figure 10](https://arxiv.org/html/2607.18253#A2.F10.2.1),[Table 2](https://arxiv.org/html/2607.18253#A2.T2),[Table 2](https://arxiv.org/html/2607.18253#A2.T2.3.2),[§5](https://arxiv.org/html/2607.18253#S5.SS0.SSS0.Px1.p2.1)\.
- \[43\]R\. Shahout, eran malach, C\. Liu, W\. Jiang, M\. Yu, and M\. Mitzenmacher\(2025\)Don’t stop me now: embedding based scheduling for llms\.InThe Thirteenth International Conference on Learning Representations,External Links:[Link](https://openreview.net/forum?id=7JhGdZvW4T)Cited by:[Appendix A](https://arxiv.org/html/2607.18253#A1.SS0.SSS0.Px4.p1.1),[§1](https://arxiv.org/html/2607.18253#S1.SS0.SSS0.Px1.p1.1)\.
- \[44\]W\. Song, Z\. Huang, C\. Cheng, W\. Gao, B\. Xu, G\. Zhao, F\. Wang, and R\. Wu\(2025\-07\)IRT\-router: effective and interpretable multi\-LLM routing via item response theory\.InProceedings of the 63rd Annual Meeting of the Association for Computational Linguistics \(Volume 1: Long Papers\),W\. Che, J\. Nabende, E\. Shutova, and M\. T\. Pilehvar \(Eds\.\),Vienna, Austria,pp\. 15629–15644\.External Links:[Link](https://aclanthology.org/2025.acl-long.761/),[Document](https://dx.doi.org/10.18653/v1/2025.acl-long.761),ISBN 979\-8\-89176\-251\-0Cited by:[Appendix A](https://arxiv.org/html/2607.18253#A1.SS0.SSS0.Px1.p1.1)\.
- \[45\]B\. Sun, Z\. Huang, H\. Zhao, W\. Xiao, X\. Zhang, Y\. Li, and W\. Lin\(2024\)Llumnix: dynamic scheduling for large language model serving\.InProceedings of the 18th USENIX Conference on Operating Systems Design and Implementation,OSDI’24,USA\.External Links:ISBN 978\-1\-939133\-40\-3Cited by:[Appendix A](https://arxiv.org/html/2607.18253#A1.SS0.SSS0.Px2.p1.1),[§1](https://arxiv.org/html/2607.18253#S1.SS0.SSS0.Px1.p1.1)\.
- \[46\]R\. Taori, I\. Gulrajani, T\. Zhang, Y\. Dubois, X\. Li, C\. Guestrin, P\. Liang, and T\. B\. Hashimoto\(2023\)Stanford alpaca: an instruction\-following llama model\.GitHub\.Note:[https://github\.com/tatsu\-lab/stanford\_alpaca](https://github.com/tatsu-lab/stanford_alpaca)Cited by:[Figure 9](https://arxiv.org/html/2607.18253#A2.F9),[Figure 9](https://arxiv.org/html/2607.18253#A2.F9.2.1),[Table 2](https://arxiv.org/html/2607.18253#A2.T2),[Table 2](https://arxiv.org/html/2607.18253#A2.T2.3.2),[§5](https://arxiv.org/html/2607.18253#S5.SS0.SSS0.Px1.p1.1)\.
- \[47\]A\. Vaswani, N\. Shazeer, N\. Parmar, J\. Uszkoreit, L\. Jones, A\. N\. Gomez, Ł\. Kaiser, and I\. Polosukhin\(2017\)Attention is all you need\.InAdvances in Neural Information Processing Systems,I\. Guyon, U\. V\. Luxburg, S\. Bengio, H\. Wallach, R\. Fergus, S\. Vishwanathan, and R\. Garnett \(Eds\.\),Vol\.30,pp\.\.External Links:[Link](https://proceedings.neurips.cc/paper_files/paper/2017/file/3f5ee243547dee91fbd053c1c4a845aa-Paper.pdf)Cited by:[§2](https://arxiv.org/html/2607.18253#S2.SS0.SSS0.Px1.p1.1)\.
- \[48\]R\. W\. Wolff\(1982\)Poisson arrivals see time averages\.Operations Research30\(2\),pp\. 223–231\.External Links:ISSN 0030364X, 15265463,[Link](http://www.jstor.org/stable/170165)Cited by:[Appendix E](https://arxiv.org/html/2607.18253#A5.SS0.SSS0.Px4.p1.5)\.
- \[49\]Z\. Yang, P\. Qi, S\. Zhang, Y\. Bengio, W\. W\. Cohen, R\. Salakhutdinov, and C\. D\. Manning\(2018\)HotpotQA: a dataset for diverse, explainable multi\-hop question answering\.InConference on Empirical Methods in Natural Language Processing \(EMNLP\),Cited by:[Figure 9](https://arxiv.org/html/2607.18253#A2.F9),[Figure 9](https://arxiv.org/html/2607.18253#A2.F9.2.1),[Table 2](https://arxiv.org/html/2607.18253#A2.T2),[Table 2](https://arxiv.org/html/2607.18253#A2.T2.3.2),[§5](https://arxiv.org/html/2607.18253#S5.SS0.SSS0.Px1.p1.1)\.
- \[50\]G\. Yu, J\. S\. Jeong, G\. Kim, S\. Kim, and B\. Chun\(2022\-07\)Orca: a distributed serving system for Transformer\-Based generative models\.In16th USENIX Symposium on Operating Systems Design and Implementation \(OSDI 22\),Carlsbad, CA,pp\. 521–538\.External Links:ISBN 978\-1\-939133\-28\-1,[Link](https://www.usenix.org/conference/osdi22/presentation/yu)Cited by:[§2](https://arxiv.org/html/2607.18253#S2.SS0.SSS0.Px2.p1.1),[§2](https://arxiv.org/html/2607.18253#S2.SS0.SSS0.Px3.p1.1),[§4\.1](https://arxiv.org/html/2607.18253#S4.SS1.SSS0.Px1.p3.1),[§4\.2](https://arxiv.org/html/2607.18253#S4.SS2.p2.2)\.
- \[51\]W\. Yuan, G\. Neubig, and P\. Liu\(2021\)BARTScore: evaluating generated text as text generation\.InAdvances in Neural Information Processing Systems,A\. Beygelzimer, Y\. Dauphin, P\. Liang, and J\. W\. Vaughan \(Eds\.\),External Links:[Link](https://openreview.net/forum?id=5Ya8PbvpZ9)Cited by:[§3](https://arxiv.org/html/2607.18253#S3.SS0.SSS0.Px3.p1.5)\.
- \[52\]J\. Zhang\(2009\-08\)Limited processor sharing queues and multi\-server queues\.Ph\.D\. Thesis,Georgia Institute of Technology\.External Links:[Link](https://people.orie.cornell.edu/jdai/thesis/Jiheng_Zhang_Thesis.pdf)Cited by:[Figure 11](https://arxiv.org/html/2607.18253#A5.F11.2.2),[Figure 11](https://arxiv.org/html/2607.18253#A5.F11.4.2),[Appendix E](https://arxiv.org/html/2607.18253#A5.p1.4),[§4\.2](https://arxiv.org/html/2607.18253#S4.SS2.p2.2)\.
- \[53\]R\. Zhuang, T\. Wu, Z\. Wen, A\. Li, J\. Jiao, and K\. Ramchandran\(2025\)EmbedLLM: learning compact representations of large language models\.InThe Thirteenth International Conference on Learning Representations,Cited by:[Appendix A](https://arxiv.org/html/2607.18253#A1.SS0.SSS0.Px1.p1.1)\.

## Appendix ARelated Works

A broad range of research directions tackle efficient response generation from varying perspectives\. Language Query Routing considers utilizing a pool of language models for extracting collective capabilities to balance performance and cost for query response generation\. The most suitable model for generating a response to a query is chosen based on a desired tradeoff, through a router that maps queries to suitable models\. Multiple response aggregation, dynamic test\-time resource allocation, and online feedback\-driven model routing form promising extensions of the model selection setting\. Additionally, systems\-driven works emphasize latency\-constrained response generation through scheduling, workload\-aware load balancing, autoscaling, and queue management\. Crucially, these directions do not provide a structured understanding of balancing response accuracy\-cost performance along with generation latency, which is of practical interest in a wide range of scenarios\. In our work, we explicitly bridge this gap and present practical latency estimators that are lightweight, accurate, and interpretable, and that integrate latency into routing decisions\. Below, we elaborate on related works across concurrent directions of research\.

#### LLM routing for quality–cost trade\-offs\.

Early work on model selection uses historical model behavior on queries to estimate task\-specific model abilities, allowing new queries to be routed to suitable models based on a desired quality–cost trade\-off\. FrugalGPT\[[8](https://arxiv.org/html/2607.18253#bib.bib10)\]introduced rule\-based selection and cascading across language models, demonstrating quality gains\. HybridLLM\[[11](https://arxiv.org/html/2607.18253#bib.bib11)\]proposed routing between a large and a small language model, using thresholds on model\-correctness estimates to maintain response quality while reducing cost\. RouteLLM\[[36](https://arxiv.org/html/2607.18253#bib.bib12)\]introduced human\-preference\-based routing over generated responses to choose the preferred model for response generation\. Simple nonparametric routing approaches, such as clustering and nearest neighbors, were formally examined by\[[24](https://arxiv.org/html/2607.18253#bib.bib15),[19](https://arxiv.org/html/2607.18253#bib.bib13)\], and extended in\[[38](https://arxiv.org/html/2607.18253#bib.bib14)\]to generalize across query distributions\. Additional approaches include interpretable routing mechanisms\[[44](https://arxiv.org/html/2607.18253#bib.bib18),[7](https://arxiv.org/html/2607.18253#bib.bib20)\], multi\-response aggregation\[[12](https://arxiv.org/html/2607.18253#bib.bib17)\], cascading language models\[[10](https://arxiv.org/html/2607.18253#bib.bib16)\], and methods that learn compact model representations through embeddings\[[53](https://arxiv.org/html/2607.18253#bib.bib19),[37](https://arxiv.org/html/2607.18253#bib.bib21)\]\. Practical aspects such as sample efficiency and distributed training have also been studied\[[4](https://arxiv.org/html/2607.18253#bib.bib23)\]\.

#### Dynamic scheduling and queue management\.

Response generation for queries with heterogeneous latency constraints requires moving beyond the usual first\-come\-first\-served \(FCFS\) scheduling policy toward priority\-based scheduling that can meet constraints and improve throughput\[[20](https://arxiv.org/html/2607.18253#bib.bib30)\]\. Model switching and query\-group scheduling across instances\[[39](https://arxiv.org/html/2607.18253#bib.bib29)\]allow resource orchestration to improve generation latency by solving a linear program that minimizes latency violations\. Llumnix\[[45](https://arxiv.org/html/2607.18253#bib.bib28)\]explores runtime query scheduling for improved load balancing and isolation of response generation across model instances, mitigating resource fragmentation and improving throughput\. Other works examine scheduling algorithms from a queueing\-theoretic perspective and highlight open problems\[[31](https://arxiv.org/html/2607.18253#bib.bib48),[5](https://arxiv.org/html/2607.18253#bib.bib46),[33](https://arxiv.org/html/2607.18253#bib.bib47)\]\.

#### Workload\-aware routing and latency modeling\.

Load balancing and workload routing across model instances of the same LLM can reduce experienced latency and improve hardware utilization\.\[[23](https://arxiv.org/html/2607.18253#bib.bib25)\]propose a reinforcement\-learning\-based router for workload\- and query\-distribution\-aware scheduling\. For optimizing deployment hyperparameters for model serving, Vidur\[[1](https://arxiv.org/html/2607.18253#bib.bib26)\]estimates operator\-level computation times and memory latencies, modeling GPU generation through a CPU simulator\. Analytical roofline estimators\[[22](https://arxiv.org/html/2607.18253#bib.bib27)\]also provide lightweight operator\-level latency models for LLM generation\. Thus, latency modeling can be studied at varying levels of hardware abstraction; in our work, we propose lightweight estimators across different workload\-observability scenarios\.\[[27](https://arxiv.org/html/2607.18253#bib.bib35)\]examine a latency\-aware routing objective with an output\-length predictor and subsequent cost and latency estimator, demonstrating improved response quality while respecting latency constraints\.

#### Output\-length prediction and size\-aware scheduling\.

Since autoregressive generation latency depends on the number of generated response tokens, predicted response lengths can provide valuable signals for designing non\-FCFS scheduling policies\.\[[41](https://arxiv.org/html/2607.18253#bib.bib31)\]propose speculative shortest job first, which uses a lightweight response\-length predictor to estimate output sequence lengths\. Learning to rank relative output lengths of queries in a batch provides a similar shortest\-job\-first scheduler when exact output\-length predictions are unavailable\[[15](https://arxiv.org/html/2607.18253#bib.bib32)\]\.\[[43](https://arxiv.org/html/2607.18253#bib.bib33)\]use internal LLM embeddings to predict the remaining number of decode tokens, eliminating the need for precomputed response lengths, which may be inaccurate and lead to suboptimal scheduling\.\[[17](https://arxiv.org/html/2607.18253#bib.bib34)\]predict output\-length distributions and future memory requirements based on historical query\-length observations to improve latency\-oriented serving\.\[[9](https://arxiv.org/html/2607.18253#bib.bib45)\]present a distributed scheduling framework for load balancing and auto\-provisioning across model instances\.

## Appendix BQuery and Language Model Details

### B\.1 Model inference costs and average performance

[Table˜1](https://arxiv.org/html/2607.18253#A2.T1)reports the tokenwise input and output costs for the language models used in our analysis\.[Table˜2](https://arxiv.org/html/2607.18253#A2.T2)presents the average performance of models across the tasks under consideration, evaluated using the LLM\-as\-a\-judge scheme\[[29](https://arxiv.org/html/2607.18253#bib.bib42)\]\.

Table 1:Pricing for Qwen3 models \(non\-thinking mode\) in USD per Million tokens on Alibaba Cloud Model Studio\[[3](https://arxiv.org/html/2607.18253#bib.bib44)\]\.Table 2:Per\-query task average scores as percentage \(using LLM\-as\-judge\[[29](https://arxiv.org/html/2607.18253#bib.bib42)\]\) for Qwen3\-0\.6B/8B/32B models\[[42](https://arxiv.org/html/2607.18253#bib.bib40)\]across Alpaca\[[46](https://arxiv.org/html/2607.18253#bib.bib37)\], Govreport\-Summarization\[[21](https://arxiv.org/html/2607.18253#bib.bib38)\], HotpotQA\[[49](https://arxiv.org/html/2607.18253#bib.bib36)\], WritingPrompts\[[13](https://arxiv.org/html/2607.18253#bib.bib39)\]tasks\.
### B\.2 TTFT latency assignment for queries

For evaluations under the hard\-constrained routing setting \([eq\.˜3](https://arxiv.org/html/2607.18253#S3.E3)\), each requestiiis assigned a TTFT targetτi\\tau\_\{i\}\. We choose realistic and practically achievable TTFT constraints based on our experimental setup, including language models and hardware\. The chosen constraints are a simple linear function of the prompt lengthpip\_\{i\}and include a small amount of random variation\. Specifically, we sampleui∼Unif​\(1​ms,5​ms\)u\_\{i\}\\sim\\textrm\{Unif\}\(1\\textrm\{ms\},5\\textrm\{ms\}\)andvi∼Unif​\(0\.98,1\.02\)v\_\{i\}\\sim\\textrm\{Unif\}\(0\.98,1\.02\), and set

τi=min⁡\{1120​ms,max⁡\{150​ms,ui\+\(155\+3\.5×10−3​pi\)​vi\}\}\.\\tau\_\{i\}=\\min\\\!\\Bigl\\\{1120\\textrm\{ms\},\\max\\\!\\bigl\\\{150\\textrm\{ms\},u\_\{i\}\+\\bigl\(155\+3\.5\\times 10^\{\-3\}p\_\{i\}\\bigr\)v\_\{i\}\\bigr\\\}\\Bigr\\\}\.Under this parameterization, the expected unclipped target is approximately

𝔼​\[τi\]≈158\+3\.5×10−3​pi​ms\.\\mathbb\{E\}\[\\tau\_\{i\}\]\\approx 158\+3\.5\\times 10^\{\-3\}p\_\{i\}\\text\{ ms\}\.All TTFT targets are generated using a seeded pseudorandom number generator for reproducibility\.

### B\.3 Prompt \(prefill\) and Response \(decode\) Length Distributions

We present the query token length distributions across the tasks in[Figure˜9](https://arxiv.org/html/2607.18253#A2.F9), and the model response length distributions in[Figure˜10](https://arxiv.org/html/2607.18253#A2.F10)\. The examined tasks and their responses present a wide range of workloads for a comprehensive evaluation of the presented latency estimators and routing scheme\.

![Refer to caption](https://arxiv.org/html/2607.18253v1/x10.png)Figure 9:Query token length distributions across the tasks in our evaluations\. Alpaca\[[46](https://arxiv.org/html/2607.18253#bib.bib37)\], GovReport\-Summarization\[[21](https://arxiv.org/html/2607.18253#bib.bib38)\], HotpotQA\[[49](https://arxiv.org/html/2607.18253#bib.bib36)\], and WritingPrompts\[[13](https://arxiv.org/html/2607.18253#bib.bib39)\]tasks present a diverse range of input lengths \(∼10​to​104\\sim 10\\text\{ to \}10^\{4\}tokens\), simulating real workloads and a comprehensive evaluation of our routing scheme and latency estimator\.![Refer to caption](https://arxiv.org/html/2607.18253v1/x11.png)Figure 10:Response token lengths for examined Qwen3\-0\.6B/8B/32B language models\[[42](https://arxiv.org/html/2607.18253#bib.bib40)\]across tasks\. Response lengths vary based on the nature of the task \(creative generation, summarization, etc\.\), covering a broad range of∼102​to​103\\sim 10^\{2\}\\text\{ to \}10^\{3\}tokens\.
### B\.4 Accuracy, Cost, and Output Length Predictors

We utilize lightweight predictors for estimating model accuracy and output length for queries on arrival\. We use LightGBM\[[25](https://arxiv.org/html/2607.18253#bib.bib54)\]regressors over features that can be computed directly from the prompt, without requiring additional sentence embedding models, to capture query semantics in a fixed\-dimensional space\. We rely on prompt tokens, and map them into a 512\-dimensional signed hashing vector, normalize by token count, and project the vector to 16 dimensions using PCA down\-projection calibrated on prompts from the initial modeling phase\. These PCA components are concatenated with prompt\-derived features such as prompt token count, character count, sentence count, average characters per token, length\-constraint indicators, and task\-type indicators \(such as list, summarize, or explain\)\.

The feature vector for the accuracy estimator contains the prompt features, a categorical model\-id feature, and model characteristics such as logarithm of number of model parameters and maximum context length\. We train a LightGBM\[[25](https://arxiv.org/html/2607.18253#bib.bib54)\]Huber regressor on quality scores generated by an LLM judge as described in[Appendix˜D](https://arxiv.org/html/2607.18253#A4)\. The output\-length predictor estimates the expected number of tokens in the generated responsetok^i,jdec\\widehat\{\\textrm\{tok\}\}^\{\\textrm\{dec\}\}\_\{i,j\}using the same prompt features and categorical model\-id feature as the accuracy predictor\. We train a LightGBM mean head directly on completion\-token counts, and the runtime predictor uses this mean estimate for routing and cost prediction\.

Given per\-model prompt\-token and output\-token pricescostjin\\text\{cost\}^\{\\textrm\{in\}\}\_\{j\}andcostjout\\text\{cost\}^\{\\textrm\{out\}\}\_\{j\}in[Table˜1](https://arxiv.org/html/2607.18253#A2.T1), the predicted request cost is derived from the output\-length prediction:

cost^i,j=tokqi,jpre⋅costjin\+tok^qi,jdec⋅costjout,\\widehat\{\\text\{cost\}\}\_\{i,j\}=\\textrm\{tok\}^\{\\textrm\{pre\}\}\_\{q\_\{i\},j\}\\cdot\\text\{cost\}^\{\\textrm\{in\}\}\_\{j\}\+\\widehat\{\\textrm\{tok\}\}^\{\\textrm\{dec\}\}\_\{q\_\{i\},j\}\\cdot\\text\{cost\}^\{\\textrm\{out\}\}\_\{j\},wheretokqi,jpre\\textrm\{tok\}^\{\\textrm\{pre\}\}\_\{q\_\{i\},j\}denotes the number of prefill tokens based on tokenization scheme at model instancejj\. These estimates are used for calculating utility in[eq\.˜2](https://arxiv.org/html/2607.18253#S3.E2)\.

## Appendix CModeling Correlated Query Arrivals

We evaluate robustness to correlated/bursty query arrivals using a two\-state Markov\-modulated Poisson process \(MMPP\-2\)\. In an MMPP\-2, arrivals are Poisson conditioned on a latent continuous\-time Markov stateZ​\(t\)∈\{L,H\}Z\(t\)\\in\\\{L,H\\\}, whereLLis a low\-rate state andHHis a high\-rate burst state\[[14](https://arxiv.org/html/2607.18253#bib.bib52)\]\. This model preserves a fixed long\-run mean arrival rate while introducing temporally correlated periods of low and high load, making it suitable for bursty, time\-varying request traffic\. For each average arrival rateα¯∈\{6,7,8\}\\bar\{\\alpha\}\\in\\\{6,7,8\\\}qps, we parameterize the MMPP\-2 by the rate ratior=αH/αLr=\\alpha\_\{H\}/\\alpha\_\{L\}, the high\-state fractionpH=0\.2p\_\{H\}=0\.2, and correlation timeτ=2\\tau=2s\. Thus,

αL=α¯\(1−pH\)\+pH​r,αH=r​αL\.\\alpha\_\{L\}=\\frac\{\\bar\{\\alpha\}\}\{\(1\-p\_\{H\}\)\+p\_\{H\}r\},\\qquad\\alpha\_\{H\}=r\\alpha\_\{L\}\.The Markov transition rates arezL→H=0\.1z\_\{L\\rightarrow H\}=0\.1andzH→L=0\.4z\_\{H\\rightarrow L\}=0\.4per second, so the process spends 80% of time in the low\-rate state and 20% in the high\-rate state\. We use homogeneous Poisson arrivals as a low\-burstiness baseline, MMPP\-2 withr=3r=3as moderate burstiness, and MMPP\-2 withr=6r=6as high burstiness\.[Figure˜8](https://arxiv.org/html/2607.18253#S5.F8)shows the performance of our proposed latency\-aware routing policy utilizing Serving Framework Simulation based latency estimator, against examined baselines\.

Table 3:MMPP\-2 arrival rates used in the arrival distribution ablation\.
## Appendix DResponse Evaluation using LLM\-as\-a\-judge

We utilize the Gemini 3\.1 Pro Preview\[[16](https://arxiv.org/html/2607.18253#bib.bib9)\]LLM via the Gemini API to evaluate the responses generated by the models in[Section˜5](https://arxiv.org/html/2607.18253#S5)\. The evaluation prompt is provided below\. We obtain raw scores in the 0\-10 range and normalize them to\[0,1\]\[0,1\]\.

You are a strict evaluator\.Evaluate each candidate response against the REFERENCE RESPONSE for the given PROMPT\.Multiple candidate responses are provided for the same prompt\. Score each one independently, but use the other candidates as comparison context to better calibrate quality differences\.Focus on correctness and completeness\. Ignore style, tone, and phrasing unless they affect meaning, accuracy, or instruction\-following\.Penalize contradictions, hallucinations, unsupported claims, and missing key points\.Use the full 0 to 10 scale and assign scores granularly across the range to capture meaningful differences in quality\.Do not bunch most responses into a narrow band\.Use decimals when useful\.Scoring anchors:0 = completely wrong, irrelevant, or unusable2 = mostly wrong with very little useful content4 = partially correct but with major mistakes or omissions6 = substantially correct but missing important details or containing minor errors8 = strong, correct, and mostly complete with only small gaps10 = fully correct, complete, and faithful to the prompt and referenceChoose any value from 0 to 10, including decimal values, based on where each response falls between these anchors\.Scores should reflect absolute quality while preserving real differences between candidates answering the same prompt\.If two responses are extremely similar in quality, their scores may be close or equal\.If one response is clearly better or worse, reflect that in the scores\.Return ONLY valid JSON\.The JSON must contain exactly one top\-level key,"scores"\.The"scores"object must contain exactly these keys:"A","B", and"C"\.Use this exact structure:\{"scores": \{"A": number from 0 to 10,"B": number from 0 to 10,"C": number from 0 to 10\}\}DO NOT return any other text since this is for an evaluation task\.

## Appendix ELimited Processor Sharing Abstraction for Autoregressive Generation

![Refer to caption](https://arxiv.org/html/2607.18253v1/x12.png)Figure 11:Limited Processor Sharing Scheme\[[52](https://arxiv.org/html/2607.18253#bib.bib5)\]\. A new job directly begins serving by the processor if fewer thankkjobs were already present, otherwise queued \(in FCFS manner\) until the number of preceding jobs at the server drops belowkk\.This appendix derives the queueing\-delay estimator used in[Section˜4\.2](https://arxiv.org/html/2607.18253#S4.SS2)\. We use a*limited processor sharing*\(LPS\) abstraction from queueing theory\[[52](https://arxiv.org/html/2607.18253#bib.bib5)\], in which at mostkkjobs are served simultaneously, and any additional jobs wait in a FIFO buffer\. This model provides a close approximation for autoregressive response generation\. Modern serving engines employ iteration\-level or continuous batching, so multiple sequences can be decoded concurrently; however, the number of concurrent sequences is constrained by KV\-cache memory, token budget, and hardware capacity\. Moreover, when fewer sequences are active, each sequence typically experiences higher kernel parallelism, resulting in higher per\-sequence throughput, whereas under heavier load this throughput is divided across more active sequences\[[2](https://arxiv.org/html/2607.18253#bib.bib2),[26](https://arxiv.org/html/2607.18253#bib.bib1)\]\. Thus, a single model instancej∈𝒥j\\in\\mathcal\{J\}can be viewed as a server of total capacityμj\\mu\_\{j\}whose service is shared among up tokkactive sequences, with any excess arrivals queued until capacity becomes available\.

#### Limited processor sharing model\.

Consider a model instancej∈𝒥j\\in\\mathcal\{J\}\. Queries arrive according to a Poisson process of rateαj\\alpha\_\{j\}queries/sec\. Let\|ℛj​\(t\)\|\|\\mathcal\{R\}\_\{j\}\(t\)\|denote the number of queries currently present/residing in the system \(waiting or actively decoding\), and let\|𝒜j​\(t\)\|\|\\mathcal\{A\}\_\{j\}\(t\)\|denote the queries that are being actively decoded\. Under LPS with parallelism capkk, the first\|𝒜j​\(t\)\|=min⁡\{\|ℛj​\(t\)\|,k\}\|\\mathcal\{A\}\_\{j\}\(t\)\|\\\!=\\\!\\min\\\{\|\\mathcal\{R\}\_\{j\}\(t\)\|,k\\\}jobs are in service and share the server equally; any additional jobs wait in a FIFO queue\. Each active job experiences an instantaneous service rate

μjmin⁡\{\|ℛj​\(t\)\|,k\},\\frac\{\\mu\_\{j\}\}\{\\min\\\{\|\\mathcal\{R\}\_\{j\}\(t\)\|,k\\\}\},implying that the*aggregate*service rate remainsμj\\mu\_\{j\}whenever the system is nonempty\.

#### Assumptions\.

The derivation of the waiting time estimate uses the following assumptions\.

1. 1\.Poisson arrivals:query arrivals form a Poisson process of rateαj\\alpha\_\{j\}queries per second\.
2. 2\.Memoryless service requirement:each query has an exponential service requirement, with mean as1/μj1/\\mu\_\{j\}in the time average sense\. Alternatively, generation work for queries follows the memoryless distribution\[[34](https://arxiv.org/html/2607.18253#bib.bib6)\]\.
3. 3\.Limited parallelism:at mostkkqueries can be served simultaneously, and the remaining queries wait in a FIFO queue\.
4. 4\.Saturated aggregate capacity:whenever the active decode batch is nonempty, the instance provides approximately constant aggregate service rateμ\\mu, while this rate is shared across active sequences\.
5. 5\.Stability condition:incoming rate of queries does not exceed the service capacity, i\.e\., the utilizationρj=αj/μj<1\\rho\_\{j\}=\\alpha\_\{j\}/\\mu\_\{j\}<1\.

#### State process and stationary distribution\.

Queries arrive according to a Poisson process of rateαj\\alpha\_\{j\}, so whenever a new query arrives, the state\|ℛj​\(t\)\|\|\\mathcal\{R\}\_\{j\}\(t\)\|increases by one\. For\|ℛj​\(t\)\|\|\\mathcal\{R\}\_\{j\}\(t\)\|resident queries in the system, with\|𝒜j​\(t\)\|\|\\mathcal\{A\}\_\{j\}\(t\)\|active queries, the total service capacityμj\\mu\_\{j\}is shared equally among those active queries\. Thus, the process\{\|ℛj​\(t\)\|\}t≥0\\\{\|\\mathcal\{R\}\_\{j\}\(t\)\|\\\}\_\{t\\geq 0\}behaves as a birth–death chain with upward transition rateαj\\alpha\_\{j\}and downward transition rateμj\\mu\_\{j\}for every nonzero state\. Hence, the stationary distribution of\{\|ℛj​\(t\)\|\}t≥0\\\{\|\\mathcal\{R\}\_\{j\}\(t\)\|\\\}\_\{t\\geq 0\}is the same as that of anM/M/1M/M/1queue:

πn≜Pr⁡\(\|ℛj\|=n\)=\(1−ρj\)​ρjn,n=0,1,2,…,\\pi\_\{n\}\\triangleq\\Pr\(\|\\mathcal\{R\}\_\{j\}\|=n\)=\(1\-\\rho\_\{j\}\)\\rho\_\{j\}^\{n\},\\qquad n=0,1,2,\\ldots,whereρj=αj/μj<1\\rho\_\{j\}=\\alpha\_\{j\}/\\mu\_\{j\}<1\.

#### Queueing delay of an arriving query\.

LetWi,jW\_\{i,j\}denote the queueing delay, i\.e\., the time from arrival until the queryqiq\_\{i\}first enters the active set at model instancejj\. By PASTA \(Poisson Arrivals See Time Averages\)\[[48](https://arxiv.org/html/2607.18253#bib.bib8)\], an arrival sees state\|ℛj\|=n\|\\mathcal\{R\}\_\{j\}\|=nwith probabilityπn\\pi\_\{n\}\.

If the query arrives and seesn<kn<k, it enters service immediately, hence

𝔼\[Wi,j\|\|ℛj\(t\)\|=n\]=0,n<k\.\\mathbb\{E\}\[W\_\{i,j\}\\bigm\|\|\\mathcal\{R\}\_\{j\}\(t\)\|=n\]=0,\\qquad n<k\.If it seesn≥kn\\geq k, thenkkjobs are already active, andn−kn\-kjobs are already waiting\. Since the new queryqiq\_\{i\}joins the tail of the FIFO queue, it must wait forn−k\+1n\-k\+1service completions before entering service\. While the query is waiting, the server always haskkactive jobs, so completions occur as a Poisson process of rateμj\\mu\_\{j\}\. Hence

𝔼\[Wi,j\|\|ℛj\(t\)\|=n\]=n−k\+1μj,n≥k\.\\mathbb\{E\}\\left\[W\_\{i,j\}\\bigm\|\|\\mathcal\{R\}\_\{j\}\(t\)\|=n\\right\]=\\frac\{n\-k\+1\}\{\\mu\_\{j\}\},\\qquad n\\geq k\.Averaging over the stationary state seen by arrivals gives

𝔼​\[Wi,j\]\\displaystyle\\mathbb\{E\}\[W\_\{i,j\}\]=∑n=0∞πn𝔼\[Wi,j\|\|ℛj\(t\)\|=n\]=∑n=k∞\(1−ρj\)ρjnn−k\+1μj\\displaystyle=\\sum\_\{n=0\}^\{\\infty\}\\pi\_\{n\}\\,\\mathbb\{E\}\[W\_\{i,j\}\\bigm\|\|\\mathcal\{R\}\_\{j\}\(t\)\|=n\]=\\sum\_\{n=k\}^\{\\infty\}\(1\-\\rho\_\{j\}\)\\rho\_\{j\}^\{n\}\\frac\{n\-k\+1\}\{\\mu\_\{j\}\}=\(1−ρj\)​ρjkμj​∑m=0∞ρjm​\(m\+1\)=\(1−ρj\)​ρjkμj⋅1\(1−ρj\)2\\displaystyle=\\frac\{\(1\-\\rho\_\{j\}\)\\rho\_\{j\}^\{k\}\}\{\\mu\_\{j\}\}\\sum\_\{m=0\}^\{\\infty\}\\rho\_\{j\}^\{m\}\(m\+1\)=\\frac\{\(1\-\\rho\_\{j\}\)\\rho\_\{j\}^\{k\}\}\{\\mu\_\{j\}\}\\cdot\\frac\{1\}\{\(1\-\\rho\_\{j\}\)^\{2\}\}=ρjkμj​\(1−ρj\)=\(αj/μj\)kμj−αj\.\\displaystyle=\\frac\{\\rho\_\{j\}^\{k\}\}\{\\mu\_\{j\}\(1\-\\rho\_\{j\}\)\}=\\frac\{\(\\alpha\_\{j\}/\\mu\_\{j\}\)^\{k\}\}\{\\mu\_\{j\}\-\\alpha\_\{j\}\}\.Thus, under the Poisson \+ memoryless\-service LPS model,

𝔼​\[Wi,j\]=\(αj/μj\)kμj−αj\\boxed\{\\mathbb\{E\}\[W\_\{i,j\}\]=\\frac\{\(\\alpha\_\{j\}/\\mu\_\{j\}\)^\{k\}\}\{\\mu\_\{j\}\-\\alpha\_\{j\}\}\}\(12\)providedαj<μj\\alpha\_\{j\}<\\mu\_\{j\}\.

#### Interpretation\.

[Equation˜12](https://arxiv.org/html/2607.18253#A5.E12)has the expected limiting behavior\. Fork=1k=1, LPS reduces to ordinaryM/M/1M/M/1, yielding𝔼​\[Wq\]=ρj/\(μj−αj\)\\mathbb\{E\}\[W\_\{q\}\]=\\rho\_\{j\}/\(\\mu\_\{j\}\-\\alpha\_\{j\}\), the usual FCFS waiting time\. Ask→∞k\\rightarrow\\infty, the waiting time vanishes: every query enters service immediately, which matches ordinary processor sharing\. For fixedρj<1\\rho\_\{j\}<1, the queueing delay decays geometrically inkkthrough the factorρjk\\rho\_\{j\}^\{k\}, reflecting the fact that waiting occurs only when allkkactive slots are already occupied\.

#### Connection to TTFT estimation\.

In[eq\.˜1](https://arxiv.org/html/2607.18253#S3.E1), TTFT is decomposed as queueing delay plus prefill computation and first decode token generation time\. If queryiihas prompt lengthtokqi,jpre\\textrm\{tok\}^\{\\textrm\{pre\}\}\_\{q\_\{i\},j\}and instancejjhas prefill throughputθjpre\\theta\_\{j\}^\{\\textrm\{pre\}\}tokens/sec, and average decode token batch processing timeT¯jdec\\bar\{T\}^\{\\textrm\{dec\}\}\_\{j\}, then

P^i,j=tokqi,jpreθjpre\+T¯jdec\.\\widehat\{P\}\_\{i,j\}=\\frac\{\\textrm\{tok\}^\{\\textrm\{pre\}\}\_\{q\_\{i\},j\}\}\{\\theta\_\{j\}^\{\\textrm\{pre\}\}\}\+\\bar\{T\}^\{\\textrm\{dec\}\}\_\{j\}\.Combining this with \([12](https://arxiv.org/html/2607.18253#A5.E12)\) gives the estimator

L^i,jttft=W^i,j\+P^i,j=\(αj/μj\)kμj−αj\+tokqi,jpreθjpre\+T¯jdec\.\\widehat\{L\}^\{\\textrm\{ttft\}\}\_\{i,j\}=\\widehat\{W\}\_\{i,j\}\+\\widehat\{P\}\_\{i,j\}=\\frac\{\(\\alpha\_\{j\}/\\mu\_\{j\}\)^\{k\}\}\{\\mu\_\{j\}\-\\alpha\_\{j\}\}\+\\frac\{\\textrm\{tok\}^\{\\textrm\{pre\}\}\_\{q\_\{i\},j\}\}\{\\theta\_\{j\}^\{\\textrm\{pre\}\}\}\+\\bar\{T\}^\{\\textrm\{dec\}\}\_\{j\}\.

#### Beyond Poisson arrivals and exponential/geometric service\.

For general response generation time distributions, the time until the next admission into generation depends on the*residual*decode sequence lengths of thekkactive jobs, requiring additional analysis beyond the standard Poisson Arrivals and exponentially distributed per query workload \(i\.e\., geometrically distributed sequence length\)\. The Limited Processor Sharing waiting time expression above admits a useful variability\-corrected approximation\. LetQQdenote the per\-query service requirement, with mean𝔼​\[Q\]\\mathbb\{E\}\[Q\], and letρj=αj​𝔼​\[Q\]\\rho\_\{j\}=\\alpha\_\{j\}\\mathbb\{E\}\[Q\], squared coefficients of variation of inter\-arrival times and service requirement asca2c\_\{a\}^\{2\}andcs2c\_\{s\}^\{2\}respectively\. A simple approximation that is exact in the important special casesk=1k=1and Poisson\+exponential service is

𝔼​\[Wi,j\]≈ca2\+cs22⋅ρjk​𝔼​\[Q\]1−ρj\.\\mathbb\{E\}\[W\_\{i,j\}\]\\approx\\frac\{c\_\{a\}^\{2\}\+c\_\{s\}^\{2\}\}\{2\}\\cdot\\frac\{\\rho\_\{j\}^\{k\}\\,\\mathbb\{E\}\[Q\]\}\{1\-\\rho\_\{j\}\}\.\(13\)Whenk=1k=1, this reduces to the standardG/G/1G/G/1waiting\-time approximation, and for Poisson arrivals with exponential service \(ca2=cs2=1c\_\{a\}^\{2\}=c\_\{s\}^\{2\}=1\) it recovers \([12](https://arxiv.org/html/2607.18253#A5.E12)\)\. Hence, \([13](https://arxiv.org/html/2607.18253#A5.E13)\) can be viewed as a first\-order extension of the exact LPS formula that accounts for arrival and service variability\. In settings where the output\-length distribution is strongly heavy\-tailed or the arrival process is bursty, a more accurate alternative is to estimate queueing delay by direct simulation or by fitting more complex analytical representations of per query service requirement\.

## Appendix FImplementation of the SFS Latency Estimator

We describe the implementation of the Serving Framework Simulation \(SFS\) latency estimator in[Section˜4\.1](https://arxiv.org/html/2607.18253#S4.SS1)\. Estimation is initiated by the router and uses periodically published query workload snapshots from model instances to predict the time\-to\-first\-token \(TTFT\) latency a new request would experience at each candidate model instance\. A desirable estimator should be computationally efficient and should not induce significant overhead for query routing\.

#### Query workload snapshots\.

Each model instance captures and conveys to the router a compact summary of its current query computation workload after each token iteration through shared memory for computational efficiency\. This snapshot contains the information utilized by the latency simulator at the router: the resident requests at the instance, their remaining prefill computation workload, predicted decode work, and the scheduler state needed for constructing token batches\.

#### Robustness to incomplete snapshots\.

Since query workload snapshots are updated without pausing autoregressive generation at model instances, the router must avoid using partially written snapshots for simulation\. We use a simple consistency mechanism in which each snapshot update is marked as either in\-progress or complete\. The router accepts a snapshot only when it observes that the update has completed and that the snapshot was not modified during the read\. This allows the router to obtain a valid view of the instance state without blocking the serving engine\. The router maintains a local cached copy of the most recent complete snapshot from each model instance, which is utilized for latency estimation upon arrival of new queries\.

#### Latency estimation\.

When a new requestqiq\_\{i\}arrives, the router evaluates each candidate model instancejjby simulating the batching and scheduling policies of the serving engine given the current workload, along with the new query\. The resulting sequence of batches until the first output token generation of the new query \([eq\.˜7](https://arxiv.org/html/2607.18253#S4.E7)\) determines the TTFT forqiq\_\{i\}\. We utilize a calibrated estimator \([eq\.˜9](https://arxiv.org/html/2607.18253#S4.E9)\) to compute batch processing times, yielding the TTFT estimator \([eq\.˜8](https://arxiv.org/html/2607.18253#S4.E8)\)\. This simulation accounts for queue order, admission limits, token\-budget constraints, context limits, KV\-cache allocation state, and preemption behavior when applicable\.

#### Code structure\.

The implementation separates three components: the serving engine, workload snapshot collection, and routing\-time evaluation\. Each model instance periodically records its current query workload, and the router keeps a cached copy of the latest snapshot from each instance, using them for TTFT latency simulation when a new request arrives\. The main routing logic, request dispatch, and policy evaluation are implemented using Python\. Critical components such as snapshot parsing and batching policy simulation are implemented in C\+\+ and exposed to Python endpoints\. The simulation overhead \(involving a loop over request states for construction of each token batch\) for latency estimation is minimized through our C\+\+ implementation\.

The system consists of≈3\.6\\approx\\\!3\.6K lines of Python and C\+\+\. In particular, the token batch construction loop for the serving engine is implemented in≈300\\approx\\\!300lines of C\+\+ code\. Adapting the estimator to a different serving engine or scheduling policy only requires modifying this batching simulation logic with minor modifications to router integration\.

## Appendix GAdditional Experimental Results

#### Varyingλ\\lambdain utility[eq\.˜2](https://arxiv.org/html/2607.18253#S3.E2)\.

[Figure˜13](https://arxiv.org/html/2607.18253#A7.F13)denotes the OnTimeUtility of our approach as compared to*Latency\-Agnostic*policy \(*Shortest Queue*and*Round Robin*do not haveλ\\lambdaparameter to control the accuracy–cost tradeoff\)\. We observe that across different choices ofλ\\lambdavalues, our approach maintains higher performance\. Note that the utility values naturally reduce asλ\\lambdaincreases in[eq\.˜2](https://arxiv.org/html/2607.18253#S3.E2)\.

![Refer to caption](https://arxiv.org/html/2607.18253v1/x13.png)Figure 12:OnTimeUtility with varying accuracy–cost balance \(λ\\lambda\) for our approach and latency agnostic routing\. Consistent improvement across varying accuracy–cost balances indicates the generalizability of our approach\.
![Refer to caption](https://arxiv.org/html/2607.18253v1/x14.png)Figure 13:Latency constraint \(SLO\) attainment vs\. query arrival rate\. Our approach makes reliable latency estimates for queries across model instances, resulting in higher latency constraint satisfaction across baselines\.

#### Query latency constraint attainment\.

We present the query latency attainment in[Figure˜13](https://arxiv.org/html/2607.18253#A7.F13), which denotes that our approach maintains high SLO attainment for queries through accurate estimates of latencies across model instances that match with observed latencies\. Combined with improved accuracy–cost utility, our approach shows the highest OnTimeUtility across all baselines as demonstrated in[Figure˜5](https://arxiv.org/html/2607.18253#S5.F5)\.

![Refer to caption](https://arxiv.org/html/2607.18253v1/x15.png)Figure 14:Fraction of queries routed to different model instances across approaches\.*Shortest Queue*and*Round Robin*do not consider the accuracy–cost heterogeneity of models across queries while making routing decisions, hence routing composition is identical across each task\.*Shortest Queue*routes more queries to smaller models as their faster throughputs result in smaller queues\. In contrast,*SFS*jointly accounts for latency, accuracy, and cost, producing task\-dependent routing decisions by assigning longer or latency\-sensitive queries to faster models while still using larger models when their quality gains justify the cost\.
#### Routing composition across model instances\.

[Figure˜14](https://arxiv.org/html/2607.18253#A7.F14)shows the fraction of queries from each task routed to each model instance for our approach and the examined baselines\.