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

arXiv:2607.18253 · cs.AI · Submitted 2026-05-13 · Read on arXiv

Listen

Transcript

Introduction to the show: ident: AI Radio. Generated commentary on the latest Artificial Intelligence papers.

Tom: I'm Tom.

Jane: And I'm Jane, here with Lu, Meng and our in-house large language model, Lalam.

Tom: Today's paper: "Mind the Delay".

Jane: The gist The proposed latency-aware routing framework jointly optimizes accuracy, cost, and time-to-first-token (TTFT) latency when assigning queries to heterogeneous Large Language Model instances.

Tom: First, who's behind it and why it matters.

Title and authors: Tom: So, let's talk about who wrote this. The authors are Shivam Patel, Akaash R. Parthasarathy, Ankur Mallick, and Gauri Joshi from Carnegie Mellon University and Microsoft Research. They’ve clearly put a lot of effort into figuring out this latency problem.

Jane: And the title itself 'Mind the Delay: Latency-aware Query Routing for Heterogeneous LLM pools' really tells you what they are tackling. It’s not just about picking a model based on quality or price anymore; it’s about timing the response.

Lu: What's interesting is that they acknowledge that incorporating this latency information into routing is hard because it depends on several things, like the query length, the current prefill and decode workload at each instance, and even how the serving framework is batching things together.

Meng: I guess what they are saying plainly is that you can't just use a static rule for routing anymore; you have to know what's happening inside the serving layer before you make a decision about which model gets your query next.

Lalam: They propose a lightweight latency estimator based on Serving Framework Simulation, or SFS, which simulates the autoregressive token batch processing to estimate TTFT. It’s their core mechanism for getting that latency information without needing perfect real-time knowledge of everything.

The paper's summary: Tom: So, what's the actual mechanism they put forward? They introduce this SFS based time-to-first-token latency estimator. It simulates the evolution of token batch composition during autoregressive generation at each candidate model instance to predict how long it will take for a new query to get its first decode token.

Jane: That simulation is designed to be accurate and computationally efficient, achieving less than five percent mean absolute percentage error on those TTFT predictions with very little overhead at test time, which is important when you're running high volume traffic.

Lu: The notation they use is pretty specific; they define a model instance indexed by j in J, and for each new query qi arriving at time t, they estimate the accuracy, cost, and TTFT latency associated with each candidate model instance.

Meng: The simulation itself focuses on the prefill computation starting at time t plus Wi,j, which is when the new sequence begins its prefill stage before any decode tokens are generated.

Lalam: They show a diagram illustrating this: a new sequence arrives at time t, prefill computation starts at time t plus Wi,j in the center of the diagram, and the first decode token is generated at time t plus Wi,j plus Pi,j on the right. It maps out exactly how they calculate that TTFT estimate.

The paper's improvements: Tom: Their main improvement is putting this SFS estimator into a latency-aware router that makes routing decisions by combining accuracy and cost utility with a per-query TTFT constraint. It’s not just picking the best model; it’s picking the best model that meets your required response time.

Jane: They formulate the objective as selecting an instance m(i) from J according to the desired routing objective, which is basically maximizing accuracy cost utility while satisfying a per-query time-to-first-token latency constraint.

Lu: They do this by using a Lagrangian relaxation of the constrained objective, which involves adding a term that penalizes TTFT latency—Lbttft i,j (t)—controlled by a parameter delta.

Meng: That delta parameter is key; it lets you control the trade-off. If delta is zero, it reverts to the old latency-agnostic routing policy where you just pick the instance with the lowest estimated latency. If you set a positive delta, you are explicitly telling the system to prioritize meeting that time constraint.

Lalam: They also introduce an evaluation protocol called OnTimeUtility, which only considers queries that meet their latency constraints when calculating utility, ensuring that only timely responses contribute positively to the score.

Conclusion: Tom: So, summing up this 'Mind the Delay: Latency-aware Query Routing for Heterogeneous LLM pools' paper, it’s about jointly optimizing accuracy and cost utility while enforcing strict time-to-first-token latency constraints on heterogeneous LLM pools.

Jane: The core contribution is that they use a lightweight Serving Framework Simulation, SFS, to predict TTFT by simulating token batch composition under the serving framework’s policies, which lets you avoid overloaded instances while keeping strong accuracy and cost performance.

Lu: What this means for the world is that we can finally move beyond simply picking the best model based on static metrics and instead tailor the routing to meet real user expectations for responsiveness.

Meng: For deployment, it suggests a way to manage resource contention better because it directly addresses how a query gets its first token in a system with continuous batching.

Lalam: I think the next steps they suggest are joint optimization of routing and model placement, and studying how routers interact when they all send queries to the same shared model instances.

Tom: Yeah, that sounds like where the real engineering challenge lies next. That's all for this paper.

Carnegie Mellon University · Microsoft

cs.AI

Submitted: 2026-05-13

Updated: 2026-10-15

Code: https://github.com/akaashrp/sfs

License: http://creativecommons.org/licenses/by/4.0/

Importance score: 92/100

The gist: The gist The proposed latency-aware routing framework jointly optimizes accuracy, cost, and time-to-first-token (TTFT) latency when assigning queries to heterogeneous Large Language Model instances.

Key concepts

Batch Evolution Aware (BEA) Estimator: This is a lightweight estimator that predicts the time-to-first-token (TTFT) for an incoming query. Instead of using simple metrics like queue length, BEA replays the serving framework's token batch formation using a snapshot of the current workload and stops when the first token of the new query is generated. It accounts for prefill and decode phase requirements.
Serving Framework Simulation (SFS): SFS simulates how a serving framework processes tokens in batches at each model instance. It tracks predicted processing times for successive token batches until it determines when the incoming query's first decode token will appear. This simulation is crucial for estimating the actual TTFT experienced by a query.
Time-to-First-Token (TTFT): TTFT measures the latency from when a user submits a query until they receive the very first token of the model's response. Optimizing TTFT is vital because users perceive slow initial responses as poor performance, and this paper focuses on predicting this specific delay.
Utility Maximization with Latency Constraint: The routing objective balances maximizing the accuracy-cost utility while ensuring that the selected model instance meets a predefined TTFT constraint. The framework selects the highest utility model among those that satisfy the latency requirements, ensuring both quality and acceptable response speed.

Terminology

Accuracy — 3× in this paper · explained in 1 episode
Decode — 1× in this paper · explained in 2 episodes

Summary

The gist The proposed latency-aware routing framework jointly optimizes accuracy, cost, and time-to-first-token (TTFT) latency when assigning queries to heterogeneous Large Language Model instances.

Need for Latency-Aware Query Routing

Current query routers are largely latency-agnostic and do not consider the generation latency experienced by queries at model instances because 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 The need for latency optimization via load-balancing of queries across model instances is generally left to the underlying systems layer because system-level routing methods operate under a fixed queryto-model assignment and thus are accuracy- and cost-agnostic

Our Latency-Aware Routing Framework

The proposed framework 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 We propose a Serving Framework Simulation (SFS) based time-to-first-token (TTFT) latency estimator that simulates autoregressive token batch processing in the serving framework and estimates the time-to-first-token (TTFT) of queries Our proposed latency estimator is accurate and computationally efficient, achieving <5% mean absolute percentage error on TTFT predictions with sub-millisecond test-time overhead

Latency Estimation via SFS

The Serving Framework Simulation (SFS) 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 query qi produces its first decode token, resulting in the TTFT estimate LbSFS i,j (t) 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

Routing Objectives and Evaluation Protocols

The primary routing objective is maximizing the accuracy–cost utility Ubi,j (λ) while satisfying a per-query time-to-first-token (TTFT) constraint The router selects the feasible model instance with the highest estimated utility if J (i) = ϕ, select the instance with the least estimated latency 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

Experimental Results

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 Our proposed approach achieves the highest OnTimeUtility across all query workloads, yielding a 33% gain in terms of area-under-the-curve (AUC) over the best baseline, and 46% improvement in OnTimeUtility (at 5qps) Setting δ = 0 recovers the Latency-Agnostic routing policy

Conclusion

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 Future directions include joint optimization of routing and model placement, and studying the interactions between routers that independently send queries to shared model instances

Improvements for AI systems

We propose a latency-aware router that jointly optimizes latency, accuracy, and cost when assigning queries to model instances, which can yield up to 40% improvement in accuracy–cost utility while maintaining the same latencies as standard load-balancing approaches. This improved system can route queries based on the objective: m(i) ← arg max j∈J: Lbttft i,j (t)≤τi Ubi,j (λ), ensuring that generated responses meet strict Service Level Objectives (SLOs).
The 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, allowing the system to estimate TTFT even when real-time workload information is unavailable. This enables routing decisions based on predicted latency rather than just static load balancing.
The router can select instances based on a Lagrangian relaxation of the constrained objective: m(i) ← arg max j∈J Ubi,j (λ) − δ Lbttft i,j (t), where δ ≥ 0 controls the relative emphasis placed on latency. This allows users or applications to control the trade-off between response quality and latency by adjusting the parameter δ.
The system can achieve task-dependent routing decisions by evaluating OnTimeUtility(λ) = 1/N X N i=1 Ui,m(i)(λ) 1 n Lbttft i,m(i) ≤ τi, ensuring that only queries meeting their latency constraints are considered for utility maximization.
The system can adapt to bursty query arrivals by using a two-state Markov Modulated Poisson Process (MMPP-2) model, allowing it to maintain high performance across varying traffic patterns, as demonstrated by the improvement of OnTimeUtility across query arrival processes.

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.