Mind the Delay: Latency-aware Query Routing for Heterogeneous LLM pools

Shivam Patel; Akaash R. Parthasarathy; Akash Dhasade; Ankur Mallick; Gauri Joshi

cs.AIMay 13, 2026

Mind the Delay: Latency-aware Query Routing for Heterogeneous LLM pools

Authors: Shivam Patel, Akaash R. Parthasarathy, Akash Dhasade, Ankur Mallick, Gauri Joshi

Organizations: Carnegie Mellon University · Microsoft

Abstract

Large language model (LLM) query routers typically assign each query to a suitable model that balances response accuracy and monetary cost. Subsequently, separate system-level load balancers based on policies such as join-the-shortest-queue or round-robin distribute the queries across replicas of each model to reduce latency. However, decoupling accuracy-cost and latency considerations can lead to suboptimal routing decisions. We introduce the Batch Evolution Aware (BEA) estimator to provide a fine-grained estimate of the latency, that is, the time-to-first-token (TTFT) experienced by an arriving query. Unlike existing load balancers that rely on coarse signals such as queue lengths, per-model processing rates, or historical average latencies, BEA replays the serving framework's token-batch formation using a snapshot of an instance's current workload, stopping when the incoming query's first token is generated. Taking into account the compute and memory requirements of the prefill and decode phases of language queries as well as the contention between multiple queries that are served in the same batch, BEA predicts TTFT within an error of approximately 5%. Each prediction takes about 0.1 ms, which is fast enough to run on the critical routing path. We also design an analytical framework for a model instance under a limited processor-sharing scheme that calculates expected TTFT in closed form and captures the qualitative trend of latencies as the load increases. The TTFT estimates produced by BEA are then used in our latency-aware router, BEAR, which simultaneously balances accuracy, cost, and latency to select the best model instance from a heterogeneous pool of LLMs. Against seven baselines, BEAR improves the utility of responses delivered within their targets by 63% on average over existing latency-aware routers, and by 30.5% over the best baseline at each arrival rate.

Figures & tables

Figure 1. Routing composition and TTFT target attainment across arrival rates. Solid and hatched portions denote queries that meet and miss their TTFT targets, i.e., their service level objectives (SLOs). BEAR adapts model assignments as load grows, meeting most targets while still using the capable model instances. Shortest Queue also meets most targets but relies heavily on smaller model instances, whereas Latency-Agnostic and Round Robin keep nearly constant allocations and miss targets more often.

Figure 2. Latency-aware routing with BEAR. Upon receiving a user query $q_{i}$ , the expected accuracy, cost and TTFT latency are estimated for each model instance. Our BEA estimator predicts TTFT by replaying the serving framework’s token-batch formation using a snapshot of the current workload, i.e., waiting ( $\mathcal{Q}_{j}(t)$ ) and active ( $\mathcal{A}_{j}(t)$ ) requests. Our router, BEAR, then selects the model instance with the highest predicted accuracy–cost utility among the feasible set of model instances that satisfy the query’s TTFT constraints.

Figure 3. TTFT (time-to-first-token) for autoregressive generation. A new sequence (query)

q_{i}

arrives at time

t

to model instance

j

( left ), its prefill computation begins at time

t\!+\!W_{i,j}

( center ), and the first output token is generated at time

t\!+\!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.

Panel of Figure 4 — Figure 4. Comparing prefill throughput-based latency estimator (left) vs. the proposed BEA estimator (right) for Qwen3-0.6B (hosted on one H100 GPU). The prefill throughput-based latency estimator does not explicitly account for decode interference while the BEA estimator simulates autoregressive generation to capture it.

Figure 5. Token-batch processing time in the BEA estimator. Batch processing times predicted by eq. 12 closely match observed batch times, with $\approx\!4\%$ mean absolute percentage error across token-batch compositions (Qwen3-0.6B on one H100 GPU).

Figure 6. Limited processor sharing (LPS) model ( Zhang, 2009 ) . Up to

k

jobs (actively decoded queries) share the processor (the compute of a model instance) equally. A new job begins service immediately if fewer than

k

jobs are present, and otherwise waits in a first-come-first-served (FCFS) queue until an active job completes.

Figure 7. Measured delay for Qwen3-0.6B on a single H100 GPU across arrival workloads, compared with the analytical predictions of the limited processor sharing model ( eqs. 13 and 14 ). The measured latencies closely follow the predicted latencies with concurrency level

k\!=\!25

, consistent with the observed average of

25.7

active sequences during generation.

Figure 8. OnTimeUtility across varying arrival rate (in qps). BEAR achieves 30.5% higher OnTimeUtility on average than the best baseline at each arrival rate.

Figure 9. Varying

\delta

in eq. 7 . Latency-aware routing provides a controllable utility–latency tradeoff.

Appendix figures & tables10 assets

Supplementary material from the paper’s appendix.

Appendix

Model	Prompt	Response
Qwen3-0.6B	0.044	0.173
Qwen3-8B	0.072	0.287
Qwen3-32B	0.287	0.640

Appendix

Table 1. Pricing for Qwen3 models (non-thinking mode) in USD per Million tokens on Alibaba Cloud Model Studio ( Alibaba Cloud, 2026 ) .

Query Task	Qwen3-0.6B	Qwen3-8B	Qwen3-32B
Alpaca	53.49%	82.67%	88.85%
GovReport-Summarization	29.02%	86.62%	95.93%
HotpotQA (distractor)	40.98%	88.28%	92.69%
WritingPrompts	17.73%	57.47%	80.69%
Aggregate	35.31%	78.76%	89.54%

Appendix

Table 2. Per-query task average scores (using LLM-as-judge ( Li et al., 2025a ) ) for Qwen3-0.6B/8B/32B models ( Qwen, 2025 ) across Alpaca ( Taori et al., 2023 ) , Govreport-Summarization ( Huang et al., 2021 ) , HotpotQA ( Yang et al., 2018 ) , WritingPrompts ( Fan et al., 2018 ) tasks.

Figure 12. Query token length distributions across the tasks in our evaluations. Alpaca ( Taori et al., 2023 ) , GovReport-Summarization ( Huang et al., 2021 ) , HotpotQA ( Yang et al., 2018 ) , and WritingPrompts ( Fan et al., 2018 ) tasks present a diverse range of input lengths (

\sim 10\text{ to }10^{4}

tokens), simulating real workloads and a comprehensive evaluation of our routing scheme and latency estimator.

Figure 13. Response token lengths for examined Qwen3-0.6B/8B/32B language models ( Qwen, 2025 ) across tasks. Response lengths vary based on the nature of the task (creative generation, summarization, etc.), covering a broad range of

\sim 10^{2}\text{ to }10^{3}

tokens.

Mean QPS $\bar{\alpha}$	Arrival setting	Low-state QPS $\alpha_{L}$	High-state QPS $\alpha_{H}$
6	$r=3$	4.29	12.86
7	$r=3$	5.00	15.00
8	$r=3$	5.71	17.14
6	$r=6$	3.00	18.00
7	$r=6$	3.50	21.00
8	$r=6$	4.00	24.00

Appendix

Table 3. MMPP-2 arrival rates used in the arrival distribution ablation.

Figure 14. Robustness to workload snapshot staleness. OnTimeUtility of BEAR under snapshot delays, simulating delayed communication between model instances and the router. OnTimeUtility performance remains close to the zero-staleness value for delays up to

400

ms, with only a

7\%

decrease at

1000

ms.

Figure 15. Sensitivity of response-quality scores to judge choice. Gemini 3.1 Pro and Gemini 2.5 Flash preserve the aggregate model ordering, with model-wise mean scores annotated in each panel. Across query evaluations, the judges agree on pairwise model ordering in

83.19\%

of cases and share the top-scoring model for

86.64\%

of queries.

Figure 16. Latency-estimator ablation for latency-constrained routing. Both variants use identical response-quality and cost predictors and the same routing rule, differing only in the TTFT estimator. The BEA estimator achieves higher OnTimeUtility than the prefill throughput-based latency estimator as load increases, with a higher advantage at increasing query arrival rates.

Figure 19. Latency estimates for BEA and examined baselines across Qwen3-0.6B, Qwen3-8B, and Qwen3-32B models. BEA uses batch processing-time estimates that account for varying prefill–decode compositions, enabling accurate latency predictions as serving workloads evolve.

LLM Serving

Large language model serving studies how to deliver model responses with low latency, high throughput, and efficient use of compute and memory.

See all 207 papers

Mar 25, 2026

Robust Batch-Level Query Routing for Large Language Models under Cost and Capacity Constraints

We study the problem of routing queries to large language models (LLMs) under cost, GPU resources, and concurrency constraints. Prior per-query routing methods often fail to control batch-level cost, especially under non-uniform or adversarial batching. To address this, we propose a batch-level, resource-aware routing framework that jointly optimizes model assignment for each batch while respecting cost and model capacity limits. We further introduce a robust variant that accounts for uncertainty in predicted LLM performance, along with an offline instance allocation procedure that balances quality and throughput across multiple models. Experiments on two multi-task LLM benchmarks show that robustness improves accuracy by 1-14% over non-robust counterparts (depending on the performance estimator), batch-level routing outperforms per-query methods by up to 24% under adversarial batching, and optimized instance allocation yields additional gains of up to 3% compared to a non-optimized allocation, all while strictly controlling cost and GPU resource constraints.

Jelena Markovic-Voronov, Kayhan Behdin, Yuanda Xu +3

LinkedIn · MIT

LLM Routing LLM Inference Scheduling Cost-Aware Inference Robust Optimization

Ask PDF

Oct 2, 2026

Dynamic LLM Routers are Often Misguided

Dynamic LLM routers promise to cut inference costs by sending each query to the cheapest model that can answer it correctly. We analyze six commercial routers across 14 settings on a diverse benchmark spanning eight task categories, finding that none of them outperforms a router that randomly selects between two well-chosen models at matched cost. Some underperform by more than 10 percentage points. We trace this gap to four patterns prevalent across routers: difficulty blindness, length reversal, semantic matching, and roster suboptimality. We show that the first three are what the standard objective rewards: cost-accuracy Pareto efficiency on realized costs favors escalating moderately hard queries over the hardest ones, shorter queries over longer ones, and routing by a query's source over its difficulty. We also argue that the two assumptions that would justify large rosters, model granularity and model specialization, do not hold empirically. We propose an alternative evaluation methodology that does not reward these patterns, and as a proof of concept, we design a simple two-model router that avoids all four. Nevertheless, its gain over random routing is limited, because a well-chosen roster leaves little to route.

Sam Wang, Julia White, Sahibzada Allahyar +3

Fastino Labs

LLM Routing Cost-Aware Inference LLM Evaluation

Ask PDF

Aug 7, 2026

LLMRouter: Unified Infrastructure for Developing, Evaluating, and Deploying LLM Routers

No single large language model (LLM) is optimal across all queries and budget constraints, making model routing essential for cost-effective deployment. Existing routers adopt diverse formulations and implementations, making fair comparison and extension difficult. We present a unified formulation of LLM routing as a sequential decision process characterized by five components: context encoders, model encoders, scoring functions, decision rules, and learning signals, covering single-turn, multi-turn, and personalized routing. Based on this formulation, we develop an automated pipeline for constructing routing supervision and evaluating routers jointly on response quality and inference cost. The resulting benchmark, xRouteBench, spans generic LLM, memory-augmented, vision, time-series, and personalized routing tasks. We further introduce LLMRouter, an open-source modular infrastructure with more than 16 representative routers. Our empirical study shows that learned routers outperform the strongest fixed-model baseline by 14.6% relatively, lightweight routers become more competitive under tight cost constraints, and user-conditioned routing consistently improves personalization.

Tao Feng, Fangxu Yu, Haozhen Zhang +9

University of Illinois Urbana-Champaign · University of Maryland, College Park · 3Nanyang Technological University +2

LLM Evaluation LLM Routing

Ask PDF

Abstract

LLM Serving

Explore similar work

Robust Batch-Level Query Routing for Large Language Models under Cost and Capacity Constraints

Dynamic LLM Routers are Often Misguided

LLMRouter: Unified Infrastructure for Developing, Evaluating, and Deploying LLM Routers