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

arXiv: https://arxiv.org/abs/2607.18253 · HTML: https://mlsanity.com/paper/2607.18253/

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- Builds on 36 of its 52 references that are in the map.
- First posted on arXiv 13 May 2026.

## Builds on (most cited first, 30 of 36)

- [Attention Is All You Need](https://mlsanity.com/paper/1706.03762/) (2017)
- [Efficient Memory Management for Large Language Model Serving with PagedAttention](https://mlsanity.com/paper/2309.06180/) (2023)
- [HotpotQA: A Dataset for Diverse, Explainable Multi-hop Question Answering](https://mlsanity.com/paper/1809.09600/) (2018)
- [Hierarchical Neural Story Generation](https://mlsanity.com/paper/1805.04833/) (2018)
- [Diffusion-LM Improves Controllable Text Generation](https://mlsanity.com/paper/2205.14217/) (2022)
- [FrugalGPT: How to Use Large Language Models While Reducing Cost and Improving Performance](https://mlsanity.com/paper/2305.05176/) (2023)
- [BARTScore: Evaluating Generated Text as Text Generation](https://mlsanity.com/paper/2106.11520/) (2021)
- [RouteLLM: Learning to Route LLMs with Preference Data](https://mlsanity.com/paper/2406.18665/) (2024)
- [Efficiently Scaling Transformer Inference](https://mlsanity.com/paper/2211.05102/) (2022)
- [Taming Throughput-Latency Tradeoff in LLM Inference with Sarathi-Serve](https://mlsanity.com/paper/2403.02310/) (2024)
- [From Generation to Judgment: Opportunities and Challenges of LLM-as-a-judge](https://mlsanity.com/paper/2411.16594/) (2024)
- [Non-Autoregressive Neural Machine Translation](https://mlsanity.com/paper/1711.02281/) (2017)
- [Hybrid LLM: Cost-Efficient and Quality-Aware Query Routing](https://mlsanity.com/paper/2404.14618/) (2024)
- [Efficient Attentions for Long Document Summarization](https://mlsanity.com/paper/2104.02112/) (2021)
- [RouterBench: A Benchmark for Multi-LLM Routing System](https://mlsanity.com/paper/2403.12031/) (2024)
- [Deterministic Non-Autoregressive Neural Sequence Modeling by Iterative Refinement](https://mlsanity.com/paper/1802.06901/) (2018)
- [Llumnix: Dynamic Scheduling for Large Language Model Serving](https://mlsanity.com/paper/2406.03243/) (2024)
- [Vidur: A Large-Scale Simulation Framework For LLM Inference](https://mlsanity.com/paper/2405.05465/) (2024)
- [Universal Model Routing for Efficient LLM Inference](https://mlsanity.com/paper/2502.08773/) (2025)
- [Efficient LLM Scheduling by Learning to Rank](https://mlsanity.com/paper/2408.15792/) (2024)
- [A Unified Approach to Routing and Cascading for LLMs](https://mlsanity.com/paper/2410.10347/) (2024)
- [BEST-Route: Adaptive LLM Routing with Test-Time Optimal Compute](https://mlsanity.com/paper/2506.22716/) (2025)
- [Efficient Interactive LLM Serving with Proxy Model-based Sequence Length Prediction](https://mlsanity.com/paper/2404.08509/) (2024)
- [EmbedLLM: Learning Compact Representations of Large Language Models](https://mlsanity.com/paper/2410.02223/) (2024)
- [IRT-Router: Effective and Interpretable Multi-LLM Routing via Item Response Theory](https://mlsanity.com/paper/2506.01048/) (2025)
- [Queue management for slo-oriented large language model serving](https://mlsanity.com/paper/2407.00047/) (2024)
- [Don't Stop Me Now: Embedding Based Scheduling for LLMs](https://mlsanity.com/paper/2410.01035/) (2024)
- [Past-Future Scheduler for LLM Serving under SLA Guarantees](https://mlsanity.com/paper/2507.10150/) (2025)
- [Throughput-Optimal Scheduling Algorithms for LLM Inference and AI Agents](https://mlsanity.com/paper/2504.07347/) (2025)
- [Learning Compact Representations of LLM Abilities via Item Response Theory](https://mlsanity.com/paper/2510.00844/) (2025)

## Built on by (most cited first, 1 of 1)

- [JOVE: Joint Execution and Verification for Resource-Aware LLM Task Graphs](https://mlsanity.com/paper/2610.03296/) (2026)

## Abstract (arXiv)

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.