🤖 AI

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

This paper proposes a latency-aware query routing system that integrates a lightweight estimator for time-to-first-token with a joint optimization strategy for accuracy, cost, and latency, achieving up to a 40% improvement in accuracy-cost utility without increasing response times compared to standard load-balancing methods.

Original authors: Shivam Patel, Akaash R. Parthasarathy, Ankur Mallick, Gauri Joshi

Published 2026-07-22

📖 5 min read🧠 Deep dive

CC BY 4.0

Original authors: Shivam Patel, Akaash R. Parthasarathy, Ankur Mallick, Gauri Joshi

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

Imagine a world where you have a team of chefs, each with a different skill level and price tag. Some are master chefs who can whip up a Michelin-star meal but charge a fortune and take a long time. Others are quick, affordable line cooks who can make a decent burger in a flash. In the world of artificial intelligence, these "chefs" are Large Language Models (LLMs)—the brains behind chatbots that write stories, solve math problems, or summarize news. When you ask a question, a "router" decides which chef gets the job. The goal is simple: get the best answer for the lowest price.

But there's a catch that most routers have been ignoring until now: the line. Even if you pick the perfect chef, if they are already swamped with other orders, your food might sit in the kitchen for ages. In the AI world, this waiting time is called "latency." If you ask a chatbot a question while it's busy, you might stare at a spinning cursor for minutes. This is a problem because sometimes you need an answer now, not just a good one. The big question researchers are trying to solve is: How do we pick the right chef to get a great answer quickly, without breaking the bank, even when the kitchen is chaotic?

Enter a new study by researchers from Carnegie Mellon University and Microsoft that tries to fix this exact problem. They realized that current systems are great at balancing quality and cost, but they are "latency-agnostic," meaning they are blind to how long the line actually is. To fix this, the team built a clever, lightweight "simulator" that acts like a digital crystal ball. Instead of just guessing how busy a server is, this simulator watches the kitchen in real-time. It looks at how many orders are waiting, how long the current dishes take to cook, and even how the kitchen staff batches their work. It then predicts exactly how long it will take for your specific order to get its first bite of food (a metric they call "Time-to-First-Token").

By feeding this prediction into their routing system, the researchers created a smart dispatcher that doesn't just look at the menu price or the chef's reputation; it looks at the wait time, too. They tested this system with different types of questions and varying levels of kitchen chaos. The results were promising: their new method managed to improve the overall "value" of the answers (balancing quality, cost, and speed) by up to 40% compared to standard methods, all while keeping the wait times just as low as the best existing load-balancing tricks. In short, they found a way to make AI chatbots faster, cheaper, and smarter by finally paying attention to the line.

The core of their innovation is a tool they call "Serving Framework Simulation" (SFS). Think of it like a traffic controller for a busy highway. Old methods might just count how many cars are on the road and guess the travel time. But SFS is smarter; it simulates the actual driving conditions. It knows that some cars are fast but heavy (like long, complex questions), while others are light but numerous. It also knows that the highway has specific rules about how cars merge and how fast they can go. By simulating these rules, SFS can predict exactly when a new car will reach the exit ramp.

The researchers found that simply guessing based on how many cars are on the road (a method they call "throughput-based estimation") often leads to bad predictions. If the highway is clogged with slow, heavy trucks, a new car might get stuck even if the total number of cars isn't huge. Their simulation, however, accounts for this "traffic jam" effect. They tested their system on a variety of tasks, from writing short stories to summarizing long reports, and found that it consistently outperformed older methods. In their simulations, their approach improved the "OnTimeUtility"—a score that measures how good the answer was, how much it cost, and whether it arrived on time—by 33% to 40% over the best existing baselines.

One of the most interesting findings is how this system handles "bursty" traffic. Imagine a sudden rush of orders coming in all at once, like a lunchtime crowd. Older systems often get overwhelmed and send everyone to the cheapest, slowest chef, causing massive delays. The new system, however, dynamically shifts the load. It might send a simple question to a fast, cheap model because the line is short, while sending a complex, urgent question to a powerful model that has a slightly longer line but can finish the job faster overall. This flexibility allows it to maintain high performance even when the demand spikes.

The team also showed that their simulator is incredibly fast itself. It takes less than a millisecond to run the simulation and make a decision, which means it doesn't slow down the system it's trying to help. This is crucial because if the router takes too long to decide, it defeats the purpose of trying to save time. They verified that their predictions were accurate, with an error rate of less than 5% in their tests, which is a significant improvement over the 85% error rate they saw with older, simpler guessing methods.

Ultimately, this paper suggests that the future of efficient AI isn't just about building bigger models or finding cheaper ones; it's about being a better traffic manager. By combining the wisdom of "which model is best" with the reality of "how long the line is," we can create systems that feel instant and responsive, even under heavy load. While the results come from simulations and controlled experiments, the authors believe this approach offers a practical path forward for making AI services more reliable and user-friendly in the real world.

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

Problem Statement

Modern language query routers optimize the trade-off between response quality (accuracy) and monetary cost by assigning queries to different Large Language Model (LLM) instances. However, existing routers are largely latency-agnostic. They select models based on accuracy and cost predictors but ignore the generation latency a query will experience at a specific model instance.

In practice, latency is determined by system-level load-balancing policies (e.g., round-robin, join-the-shortest-queue) which do not account for model accuracy or inference cost. Conversely, system-level latency optimization assumes a fixed query-to-model assignment and ignores accuracy-cost trade-offs. This creates a gap: current routers may route queries to overloaded instances, causing long queueing delays and violating Service Level Objectives (SLOs), while system-level optimizers cannot leverage the heterogeneous accuracy-cost capabilities of a model pool.

The core challenge is that generation latency is non-deterministic and depends on:

Hardware specifications and model architecture.
The current composition of the workload (prefill vs. decode stages) at the instance.
The specific batching and scheduling policies of the serving framework (e.g., vLLM, Sarathi-Serve).

Accurately estimating the Time-to-First-Token (TTFT) for an incoming query is difficult because it requires simulating how the serving framework will batch the new query with existing resident sequences, considering both prefill (compute-bound) and decode (memory-bound) interference.

Methodology

The authors propose a routing framework that jointly optimizes accuracy, cost, and latency. The system consists of three main components:

1. Routing Objective

The router selects a model instance $m(i)$ for a query $q_i$ to maximize the accuracy-cost utility ( $\hat{U}_{i,j}$ ) while satisfying a TTFT constraint ( $\tau_i$ ).

Utility: $\hat{U}_{i,j}(\lambda) = \hat{acc}_{i,j} - \lambda \cdot \hat{cost}_{i,j}$ , where $\lambda$ balances quality and cost.
Constraint: The selected instance must satisfy $\hat{L}^{ttft}_{i,j}(t) \leq \tau_i$ . If no instance satisfies the constraint, the router selects the one with the minimum estimated latency.
Evaluation: Performance is measured via OnTimeUtility, which averages the utility of queries that meet their latency constraints (assigning zero utility to those that violate them).

2. Serving Framework Simulation (SFS) Latency Estimator

To predict TTFT accurately without real-time execution, the authors design a lightweight estimator that simulates the serving framework's behavior.

Input: The estimator uses the current state of the model instance, including the set of resident requests ( $R_j(t)$ ), their remaining prefill tokens, and predicted decode lengths.
Simulation Process:
1. It constructs an augmented workload including the new query and all resident queries.
2. It deterministically simulates the serving framework's continuous batching and scheduling policies to form token batches.
3. It iterates through these batches until the new query generates its first decode token.
Token-Batch Processing Time Model: Instead of simulating low-level kernels, the estimator uses a calibrated linear model (Eq. 9) to predict the time for each token batch. This model accounts for:
- Fixed overheads.
- Token-wise dense-layer computation (linear with batch size).
- Attention computation and KV-cache reads (linear with context length for decode).
- Prefill attention costs (quadratic within the prefill chunk).
Output: The sum of predicted processing times for all simulated batches up to the first decode token yields the TTFT estimate.

3. Average-Case Estimation (No Real-Time Data)

In scenarios where real-time workload snapshots are unavailable (e.g., routing to third-party clouds), the authors propose a queueing-theoretic abstraction using a Limited Processor Sharing (LPS) model. This models the instance as a server sharing capacity among up to $k$ concurrent queries, with others waiting in a FIFO queue. This allows for estimating average waiting times based on arrival rates and service capacities.

Key Contributions

Joint Optimization Framework: The paper bridges the gap between accuracy-cost routing and system-level latency optimization by designing a router that makes routing decisions based on all three metrics simultaneously.
Lightweight SFS Estimator: The authors introduce a novel latency estimator that simulates autoregressive token batch processing. It captures the complex interplay between prefill and decode workloads and serving framework policies (like chunked prefills) without requiring full execution.
High Accuracy and Low Overhead: The SFS estimator achieves a Mean Absolute Percentage Error (MAPE) of <5% on TTFT predictions with a test-time overhead of approximately 0.14 ms (sub-millisecond), making it suitable for the critical path of routing.
Robustness: The framework is evaluated under both standard Poisson arrivals and bursty Markov-Modulated Poisson Process (MMPP) arrivals, demonstrating consistent performance improvements.

Experimental Results

The authors evaluated their approach using three Qwen3 models (0.6B, 8B, 32B) deployed on H100 GPUs with the vLLM serving framework. They compared their SFS-based router against three baselines:

Round Robin: Cyclic assignment ignoring workload.
Shortest Queue: Assigns to the instance with the fewest requests (latency-focused, accuracy-agnostic).
Latency-Agnostic: Maximizes utility ignoring latency.

Key Findings:

Utility Improvement: The proposed method yields up to 40% improvement in accuracy-cost utility compared to standard load-balancing baselines (like Shortest Queue) while maintaining the same latency constraints.
OnTimeUtility: Across varying query arrival rates, the SFS router achieved a 33% higher Area Under the Curve (AUC) for OnTimeUtility compared to the best baseline.
Trade-off Control: By varying the latency penalty parameter $\delta$ in the Lagrangian relaxation, the router provides a controllable trade-off curve between utility and latency, outperforming baselines that cannot balance these metrics effectively.
Estimator Performance: The throughput-based baseline (which ignores decode interference) showed a 85% MAPE, whereas the SFS estimator reduced this to 5%, highlighting the necessity of simulating the full serving framework dynamics.

Significance and Claims

The paper claims that joint optimization of accuracy, cost, and latency is essential for efficient LLM deployment in dynamic workloads. The authors argue that existing routers fail because they treat latency as a system-level concern separate from model selection, leading to suboptimal resource utilization and SLO violations.

By integrating a lightweight, simulation-based latency estimator directly into the routing decision, the proposed framework avoids overloaded instances while preserving strong accuracy-cost performance. The work demonstrates that it is possible to achieve significant gains in utility (up to 40%) without sacrificing latency constraints, effectively unifying the previously siloed goals of "smart routing" (accuracy/cost) and "load balancing" (latency). The authors position this as a practical solution for real-world deployments where query workloads are dynamic and SLOs are strict.