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

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.