RouteBalance: Fused Model Routing and Load Balancing for Heterogeneous LLM Serving
Listen
Radio episode about this paper
Transcript
Introduction to the show: ident: Computer Science. The day in computer science: software, systems and theory on arXiv.
Tom: I'm Tom.
Jane: And I'm Jane, here with Lu, Meng and our in-house large language model, Lalam.
Tom: We're looking at the paper: "RouteBalance: Fused Model Routing and Load Balancing for Heterogeneous LLM Serving".
Jane: Here's the gist of the paper. Heterogeneous LLM serving stacks split scheduling into two layers that optimize in isolation: model routers pick a model from quality and cost signals while ignoring instance load, and serving load balancers optimize queues while ignoring quality RouteBalance closes this gap by formulating routing as online assignment over concrete model instances, jointly trading off quality, latency, and cost The Core Problem Addressed Cloud providers increasingly serve large language models (LLMs) on heterogeneous infrastructure, deploying models of different sizes across diverse GPU types to balance cost, latency, and output quality This creates a scheduling question existing systems answer only in pieces: which model instance should serve each request?
Tom: The three factors interact Quality is workload-dependent: larger models are generally better, but on simple queries a small model can match or beat a larger one
5, 8, 38: Cost depends on prompt and output lengths and per-token price; larger models charge more per token but often answer more concisely Latency depends on instance load, model size, lengths, and hardware, so scheduling must price latency at model-selection time—the term existing routers omit The cost of ignoring load is concrete On our cluster, a quality-only router that always picks the nominally best model for each prompt drives mean end-to-end latency from 2.3 s to over 60 s as arrival rate rises to 30 req/s, because it concentrates traffic on a few high-quality replicas while cheaper tiers sit idle Conversely, a load-only balancer that ignores quality forfeits +0.04–0.05 DeepEval quality it could have kept at the same latency Neither layer alone can occupy the good region of the trade-off How the training signal is built RouteBalance solves a weighted quality–latency–cost score over request–instance pairs for each batch, with tunable 3-simplex weights exposing named operating points (Quality, Latency, Cost) The decision is made cheap by amortizing prompt-dependent estimation across a batch—a single CPU-resident embedding feeds a k=10 KNN head returning per-model quality and expected output length—and by in-process per-tier latency heads, while a greedy longest-processing-time (LPT) pass with dead-reckoned instance state avoids herding on stale load signals The components are individually standard (sentence embeddings, KNN, gradient-boosted latency heads, LPT ordering); the contribution is the serving-aware formulation and a causal account, on architecture-controlled and engineering-equalized baselines, of where the benefit comes from Where the gains come from The durable finding is that pricing a latency term in model selection at all is what occupies the frontier: a four-arm isolation (Section 6.3) attributes the gain to this cross-tier mix shift, which a decoupled quality/cost router cannot make Within a tier, reactive queue depth suffices and the learned predictors are calibration and SLO headroom, not load-bearing The wrapper baselines are thresholding routers that either queue-bottleneck or flood tiers based on binary decisions RouteBalance instead picks per-prompt and per-instance jointly, keeping harder prompts on 14B/72B heads while filling 3B/7B capacity with shorter, easier ones (at wq=0.8 mostly 72B; uniform spreads ∼57% 3B / ∼32% 14B) The whole mix comes from a single deployed stack with only the weights changing System Design and Performance RouteBalance schedules in batches, where predictors run once per batch (fixed cost amortized), scoring normalizes latency and cost within the batch as load changes For a batch R B over instances I, each request selects one instance, so the objective decomposes per request and the deployed mechanism is a greedy batched procedure The objective function is maximized by selecting an instance that maximizes S r i = wqual Qˆ r,m(i) + wcost 1 − Cˆ r,i max j Cˆ r,j + wlat 1 − Tˆ r,i max j Tˆ r,j subject to one instance per request The batch supplies the candidate set against which each request’s cost and latency are scaled Evaluation and Robustness The best BEST-Route cell (0.406) and +0.043 above AvengersPro (0.376) The quality of record here is the routing-decision lookup (§4.2), the standard offline-routing basis; re-judging the actual served text of the headline pair under a second judge preserves the same ordering (§6.7) RouteBalance sweeps 16 weight tuples on the simplex, and at wq=0.8 traces a monotone frontier from its cost-priority preset (2.2 s, quality 0.354) through uniform (2.3 s, 0.371) and the mid-band (4.1 s, 0.397) to the quality ceiling at wq=0.8 (5.9 s, 0.419)—+0.013 above The defining property is a single deployed stack reaching every corner by changing only the weights: at wq=0.8 the quality ceiling 0.419 (concentrating on 72B, 5.9 s, low throughput); at uniform weights 2.3–2.8 s across the whole load range; at the cost-priority corner the cheapest cost of any system (1.67×10−5 USD, tying Avengers-Pro) The ordering RouteBalance > BEST-Route > Avengers-Pro is not a single-run artifact RouteBalance fuses model routing and load balancing into a single online assignment over concrete model instances on a quality–latency–cost simplex; one deployed stack spans cheapest-to-highest-quality by changing only the weight vector, and a four-arm decomposition traces the benefit to pricing latency at model-selection time, a decision the decoupled router-then-balancer stack cannot make The gains hold at scale (28 GPUs, 442 configurations, ≈1.5M requests) against engineering-equalized baselines, with judge-, seed-, and cost-model-robust orderings Open directions include a second model family and topology (a Llama/Gemma port is the immediate next step), production-trace arrivals, and an SLOdriven controller over the weights The framework, scripts, and datasets are released for artifact evaluation The paper concludes that the concurrent-scoring path—a contribution of this work, not part of either baseline (§5)—microbatches the in-flight scoring (routing and quality unchanged), after which mean E2E is serving-bound and both coincide at 2.3–2.8 s The engineering that makes rung (iv) work also explains the gap to rung (ii) The paper proves that the quality ceiling, cost tie, and weight family are what RouteBalance wins on, not headline-cell latency References
1: Agrawal, A., Kedia, N., Mohan, J., Panwar, A., Kwatra, N., Gulavani, B.
Jane: S., Ramjee, R., and Tumanov, A.
Tom: Vidur: A large-scale simulation framework for llm inference
2: Ahmad, S., Guan, H., Friedman, B.
Title and authors: Tom: So, we're starting with the paper "RouteBalance: Fused Model Routing and Load Balancing for Heterogeneous LLM Serving," and it’s addressing that core problem of scheduling requests across different models and hardware.
Jane: Right. The authors found that current systems are split into two separate layers; one layer picks a model based only on quality and cost, completely ignoring how busy the servers are, while the other handles server load based on queue depth but ignores which specific model is running.
Lu: That’s exactly what they pointed out was the problem with those separate layers. They introduced RouteBalance as a new serving-aware layer that fuses both of those functions into a single online assignment over concrete model instances, allowing you to trade off quality, latency, and cost all at once using tunable three simplex weights.
Meng: I'm always worried about these combined systems breaking at scale; how do you keep that decision-making cheap enough for production traffic?
Tom: They kept it cheap by using a batched in-process predictor stack and a dead-reckoned instance state, which keeps the joint decision cheap on the request hot path, taking around thirty-two milliseconds when they test it at twelve requests per second <ref:2606.17949#pg1>.
Jane: That speed sounds promising for real-time serving, but what’s actually new here compared to just running those two systems side by side?
Lu: The paper shows that by incorporating a latency term directly into the model selection during routing, you occupy the frontier of the trade-off region, which is something a decoupled quality and cost router just cannot do <ref:2606.17949#pg2>.
Tom: So, the core idea is pricing latency at model selection time so you don't ignore it entirely; it seems like they use this to find a specific sweet spot on that quality, latency, and cost frontier using tunable three simplex weights.
Meng: Tunable weights sound flexible, but I need concrete examples of what those operating points actually look like in practice when we are trying to deploy something live.
Jane: Well, the authors showed how sweeping one weight vector across the three dimensions traces a whole region of trade-offs, showing that you can move from a quality priority setting with a cost focus to a uniform spread across all three factors <ref:2606.17949#pg2>.
Lu: That’s interesting because they show that at one extreme, like when setting the quality weight high at zero point eight, the system concentrates on the largest models, like the 72B model, which has a latency of about five point nine seconds and an estimated quality of zero point four one nine <ref:2606.17949#pg1>.
Tom: And they noted that this specific operating point gives them a quality score of zero point four one nine, which is plus zero point one three over the strongest baseline they tested, and the ordering holds even when you re-score the actual text with a second judge <ref:2606.17949#pg1>.
Jane: That’s good evidence for that extreme setting, but what about when you move toward a cost-priority corner? How does it behave there compared to those other settings?
Lu: At the cost-priority corner, they found an estimated cost of one point six times ten to the negative five US dollars, which ties with another system they tested called Avengers Pro <ref:2606.17949#pg2>.
Meng: Tying with another system is one thing, but I need to know how it handles actual traffic spikes and doesn't just get stuck on a single configuration that might be bad under load.
Tom: To handle that, they use a greedy longest-processing-time pass with dead-reckoned instance state to avoid herding on stale load signals during the batch processing <ref:2606.17949#pg2>.
Jane: That’s important because if you ignore the instance load, you can concentrate all your traffic onto a few high quality replicas while leaving cheaper tiers completely idle, which is what they showed happens when only a quality-only router is used <ref:2606.17949#pg1>.
Lu: The durability of their finding comes from showing that this cross tier mix shift, where model selection accounts for real time instance state, is what actually gives you the gain over those decoupled systems <ref:2606.17949#pg2>.
Meng: So it's not just about making one layer better; it’s about making the core decision-making process aware of everything happening on the cluster simultaneously.
Tom: Exactly. It’s a single deployed stack where you only change the weight vector to span different operating points, and they proved that this single stack reaches every corner of that trade-off frontier <ref:2606.17949#pg1>.
Jane: So, for someone listening just trying to understand what this means practically, it suggests that instead of picking the best model blindly or just balancing the queue blindly, you need a system that thinks about quality, how long it will take to respond, and how much it costs all at once.
The paper's summary: Tom: So we've talked about how RouteBalance takes those two separate systems—the model router and the load balancer—and fuses them into one online assignment layer that balances quality, latency, and cost all at once.
Jane: Right. The big idea here is that instead of having a router pick a model based only on quality and a balancer just worry about the queue depth, you get this single mechanism that trades off those three things dynamically using weights on a three-dimensional score <ref:2606.17949#pg2>.
Lu: What’s interesting is how they build this score over request instance pairs for each batch; they use an amortized prompt estimation, feeding one CPU resident embedding into a ten thousand nearest neighbor head to predict both the quality and the expected output length for every model candidate in that batch call <ref:2606.17949#pg2>.
Meng: That sounds like it keeps the per-request cost low enough not to kill us during serving; what about how they handle the load signals while making these decisions? Does it just ignore them?
Tom: No, they don't ignore them entirely; they use a greedy longest processing time pass with dead-reckoned instance state. This means after one request is assigned, the system updates that instance’s state before considering the next request in the batch <ref:2606.17949#pg2>.
Jane: That’s smart because it stops them from just following stale load signals; they can see how an earlier assignment affects later ones, which makes their greedy pass a much better approximation of what would be a hard matching problem across all models <ref:2606.17949#pg2>.
Lu: The main finding is that pricing a latency term right into the model selection during routing is what actually occupies the frontier; it’s this cross tier mix shift—where you're picking smaller, faster models for easy prompts and larger ones for hard ones—that no decoupled router can achieve alone <ref:2606.17949#pg2>.
Tom: So, if we look at their results, they show that by changing just the weight vector across that three simplex space, they trace a whole region of trade-offs; they aren't stuck on just one setting; you can move from a quality priority setup to a cost priority corner <ref:2606.17949#pg2>.
Jane: And the best part for us as builders is that this single deployed stack reaches every corner of the frontier by just changing those weights, which means we don't need separate systems or complicated logic to switch between quality-focused and cost-focused modes <ref:2606.17949#pg2>.
Meng: That sounds appealing because it reduces the number of moving parts in our production pipeline, but what about the performance on real traffic? Does this complexity add too much overhead to the actual serving path?
Tom: They did test it at scale, with twenty eight GPUs and four different model sizes, and they found that even when you push the quality weight up to zero point eight—where they concentrate on the largest models—the mean end-to-end latency is still around two point three seconds to two point eight seconds <ref:2606.17949#pg1>.
Jane: That means even at that high quality setting, you’re still hitting a serving bound where both routing and quality decisions align with that latency; it shows the system stays stable across the whole range of weights they tested, not just at one extreme <ref:2606.17949#pg1>.
Lu: The paper also points out a budget control integration where they pre-score candidates based on predicted total cost—input tokens plus the KNN predicted output length—to ensure everything stays within a per request budget <ref:2606.17949#pg3>.
Tom: So to wrap up, RouteBalance is this unified online assignment over concrete model instances, and the main takeaway is that pricing latency at model selection time is what actually moves you into that better region of the quality cost throughput frontier <ref:2606.17949#pg1>.
Jane: It’s a single deployed stack where you tune the weights to find exactly what kind of trade-off—quality, speed, or cost—you need for your specific application <ref:2606.17949#pg2>.
Meng: So it’s not just about having a clever algorithm; it's about integrating these different optimization goals into one coherent system that actually runs on hardware.
Tom: Exactly. The engineering that makes the dead reckoning work is what explains why this approach wins over those simpler, decoupled setups under real pressure <ref:2606.17949#pg2>.
Jane: Now, we’ve seen how they handle a single model family, but the next logical step for this research is testing this framework with a different model family to see if these findings generalize to other architectures <ref:2606.17949#pg3>.
The paper's improvements: Tom: So we’re moving from what they did to what they suggest changing next. The paper isn't just showing one setup; it's proposing new ways to make this routing system even better at handling real-world chaos.
Jane: Right. They’re looking at how they can improve the core components of the whole thing, like making those prediction heads more robust, or maybe refining how they handle the load balancing part when things get really busy <ref:2606.17949#pg2>.
Lu: They suggest exploring a second model family or topology, specifically mentioning a Llama or Gemma port as an immediate next step to test if these routing findings generalize beyond just the specific model sizes they used in their experiments <ref:2606.17949#pg3>.
Meng: Testing across different architectures is crucial because what works on one kind of GPU setup doesn't always translate when you move to another vendor or a different model structure <ref:2606.17949#pg3>.
Tom: Exactly. If this framework holds up when you switch from, say, a 72B model to something like a Llama three variant, then it’s less of a specific tuning trick and more of a general serving solution <ref:2606.17949#pg3>.
Jane: And they also mention the possibility of an SLO driven controller over the weights; that would mean the system could automatically adjust its quality-latency-cost trade-off based on what service level you need <ref:2606.17949#pg3>.
Lu: That’s ambitious because it means we move from manually setting those weights to letting a control loop manage them dynamically in response to real traffic conditions <ref:2606.17949#pg3>.
Tom: It makes sense, but we gotta think about the cost of that controller itself; managing that loop adds another layer of complexity on top of the existing batched scoring <ref:2606.17949#pg3>.
Meng: That’s my concern. If you add a whole new control system, what does it cost in terms of latency and computational overhead during request processing; it has to stay fast enough for the serving path <ref:2606.17949#pg3>.
Jane: The authors address that by showing that their current concurrent scoring path, which microbatches the scoring, keeps the mean end-to-end latency serving bound at around two point three seconds across all conditions they tested <ref:2606.17949#pg1>.
Lu: So they’re arguing that even with this new control layer, the fundamental decision-making part remains very fast because it's already done in batches and amortized <ref:2606.17949#pg2>.
Tom: That’s a good point for me; if the core scoring mechanism is already efficient, adding a top-level controller just means you have to make sure that controller doesn't slow down the batch processing itself <ref:2606.17949#pg3>.
Jane: The implication for us is that we don't have to rebuild the entire routing logic from scratch; we can start by tweaking these existing components and seeing where they hit their limits before jumping into a full SLO-driven control system <ref:2606.17949#pg3>.
Lu: And honestly, I think the most important thing is proving that pricing latency at model selection time is the fundamental mechanism that occupies the frontier; that’s what we need to focus on next because that’s where the real architectural shift happens <ref:2606.17949#pg2>.
Conclusion: Tom: So, to wrap up, RouteBalance is this unified online assignment over concrete model instances that lets you tune quality, latency, and cost all at once by changing just a weight vector on a three simplex <ref:2606.17949#pg1>.
Jane: It’s about fusing model routing and load balancing into one layer so you can find the right operating point for your specific workload instead of using two separate systems that only look at one dimension each <ref:2606.17949#pg2>.
Lu: The core contribution is proving that pricing latency at model selection during routing is what actually occupies the frontier, which means this system can trace the upper region of the quality cost throughput frontier on a single deployed stack by just changing those weights <ref:2606.17949#pg2>.
Meng: So, if I’m shipping models to production, what does this mean for my deployment pipeline right now? Does it require a massive overhaul of how we schedule requests?
Tom: It means you can take your existing infrastructure and deploy this stack with only weight changes to get significant gains across the board against engineering equalized baselines <ref:2606.17949#pg1>.
Jane: The implication is that you don't have to completely rewrite your routing logic; you just adjust the weights to find what works best for your traffic mix <ref:2606.17949#pg2>.
Lu: And they showed that the gains hold at scale, with twenty eight GPUs and four model sizes, against different robustness tests, meaning it isn't just a lucky result from one specific configuration <ref:2606.17949#pg1>.
Meng: It’s good to know it’s durable across different setups; I need to see if this stability holds when we introduce real-time traffic spikes that aren't perfectly measured <ref:2606.17949#pg2>.
Tom: The concurrent scoring path they introduced helps keep the mean end-to-end latency serving bound at two point three seconds across all tested conditions, which is a concrete number for performance <ref:2606.17949#pg1>.
Jane: So it gives us a clear benchmark: if you want to optimize for quality, cost, or speed, this framework shows you exactly how those factors interact in practice <ref:2606.17949#pg2>.
Lu: This work sets a new baseline by showing that this unified stack can trace the upper region of the three way quality cost throughput frontier on one system; it’s a big step in how we think about heterogeneous serving <ref:2606.17949#pg1>.
Meng: I still have my reservations about adding a control loop, but seeing the stability across those different model families might make me more willing to test that route <ref:2606.17949#pg3>.
Tom: That’s where things are headed next—testing this framework with a second model family like a Llama or Gemma port is the immediate research direction they’re suggesting <ref:2606.17949#pg3>.
Jane: It seems like the next step is testing if this mechanism works across different model architectures, which would really prove that these findings generalize beyond just the specific model sizes they used in their experiments <ref:2606.17949#pg3>.
Wei Da, Evangelia Kalyvianaki
University of Cambridge
cs.DC
Submitted: 2026-06-16
Updated: 2026-10-31
Comments: 17 pages including appendices, 5 figures. Substantially revised from v1: replaced the learned latency predictor with profiled TPOT estimates, added Gemma 3 and bursty-arrival experiments, and integrated appendices
Code: https://github.com/AKafakA/route-balance
License: http://creativecommons.org/licenses/by/4.0/
Importance score: 98/100
The gist: Heterogeneous LLM serving stacks split scheduling into two layers that optimize in isolation: model routers pick a model from quality and cost signals while ignoring instance load…
Key concepts
- Quality-Latency-Cost Simplex
- This is a mathematical space where every possible model instance combination is plotted based on three competing metrics: output quality, response latency, and operational cost. RouteBalance uses tunable weights to navigate this space, allowing it to find the best balance point—for example, prioritizing high quality or low cost while managing latency constraints.
- Amortized Prompt Estimation
- To make routing fast for every request, the system doesn't calculate complex metrics for every single model. Instead, it uses a single CPU-resident embedding to quickly estimate model quality and expected output length across many models in one batch. This cheap estimation allows the joint decision to be made very quickly on the request path.
- Dead Reckoned Instance State
- When scheduling requests in a batch, the system keeps track of which instances have been used so far. This 'dead reckoning' means it updates its knowledge after each assignment. This prevents it from relying on outdated load information and helps the greedy assignment process make better choices for subsequent requests within that batch.
- Online Assignment over Concrete Instances
- The core mechanism is deciding which specific, physical model instance (e.g., a specific GPU running a 72B model) serves which incoming request online. This is different from routing to a general category; it's making concrete, per-request assignments by solving an optimization problem that balances the three key factors.
Terminology
Summary
Heterogeneous LLM serving stacks split scheduling into two layers that optimize in isolation: model routers pick a model from quality and cost signals while ignoring instance load, and serving load balancers optimize queues while ignoring quality
RouteBalance closes this gap by formulating routing as online assignment over concrete model instances, jointly trading off quality, latency, and cost
The Core Problem Addressed
Cloud providers increasingly serve large language models (LLMs) on heterogeneous infrastructure, deploying models of different sizes across diverse GPU types to balance cost, latency, and output quality This creates a scheduling question existing systems answer only in pieces: which model instance should serve each request? The three factors interact Quality is workload-dependent: larger models are generally better, but on simple queries a small model can match or beat a larger one [5, 8, 38] Cost depends on prompt and output lengths and per-token price; larger models charge more per token but often answer more concisely Latency depends on instance load, model size, lengths, and hardware, so scheduling must price latency at model-selection time—the term existing routers omit The cost of ignoring load is concrete On our cluster, a quality-only router that always picks the nominally best model for each prompt drives mean end-to-end latency from 2. p. 0 Quality is workload-dependent:
larger models are generally better, but on simple queries a
small model can match or beat a larger one [5, 8, 38]. Cost
depends on prompt and output lengths and per-token price;
larger models charge more per token but often answer more
concisely. On our cluster, a
quality-only router that always picks the nominally best
model for each prompt drives mean end-to-end latency from
2. 3 s to over 60 s as arrival rate rises to 30 req/s, because
it concentrates traffic on a few high-quality replicas while
cheaper tiers sit idle; conversely, a load-only balancer that
ignores quality forfeits +0.Where the paper says it
Where the paper says it
How the training signal is built
RouteBalance solves a weighted quality–latency–cost score over request–instance pairs for each batch, with tunable 3-simplex weights exposing named operating points (Quality, Latency, Cost) The decision is made cheap by amortizing prompt-dependent estimation across a batch—a single CPU-resident embedding feeds a k=10 KNN head returning per-model quality and expected output length—and by in-process per-tier latency heads, while a greedy longest-processing-time (LPT) pass with dead-reckoned instance state avoids herding on stale load signals The components are individually standard (sentence embeddings, KNN, gradient-boosted latency heads, LPT ordering); the contribution is the serving-aware formulation and a causal account, on architecture-controlled and engineering-equalized baselines, of where the benefit comes from
Where the gains come from
The durable finding is that pricing a latency term in model selection at all is what occupies the frontier: a four-arm isolation (Section 6.3) attributes the gain to this cross-tier mix shift, which a decoupled quality/cost router cannot make Within a tier, reactive queue depth suffices and the learned predictors are calibration and SLO headroom, not load-bearing The wrapper baselines are thresholding routers that either queue-bottleneck or flood tiers based on binary decisions RouteBalance instead picks per-prompt and per-instance jointly, keeping harder prompts on 14B/72B heads while filling 3B/7B capacity with shorter, easier ones (at wq=0. p. 1 3) attributes the gain to this cross-tier mix shift, which
a decoupled quality/cost router cannot make. Within a tier,
reactive queue depth suffices and the learned predictors are
calibration and SLO headroom, not load-bearing.Where the paper says it
System Design and Performance
RouteBalance schedules in batches, where predictors run once per batch (fixed cost amortized), scoring normalizes latency and cost within the batch as load changes For a batch R B over instances I, each request selects one instance, so the objective decomposes per request and the deployed mechanism is a greedy batched procedure The objective function is maximized by selecting an instance that maximizes S r i = wqual Qˆ r,m(i) + wcost 1 − Cˆ r,i max j Cˆ r,j + wlat 1 − Tˆ r,i max j Tˆ r,j subject to one instance per request The batch supplies the candidate set against which each request’s cost and latency are scaled
Evaluation and Robustness
The best BEST-Route cell (0.406) and +0. p. 6 the best BEST-Route cell (0. 406) and +0. 406) and +0. 043 above AvengersPro (0. 022]; ΔRB−AP=+0. The quality of record here is the routing-decision lookup
(§4. The quality of record here is the routing-decision lookup
(§4. 2), the standard offline-routing basis; re-judging the actual served text of the headline pair under a second judge
preserves the same ordering (§6. 8}), each with round-robin and shortest-queue dispatch,
and a passthrough router with all three dispatchers; vLLM
Semantic-Router [51] runs as a separate-process baseline. RouteBalance sweeps 16 weight tuples on the simplex. 2 The frontier: one stack vs. baselines
Figure 2(a) snapshots 𝜆=12 on the quality–latency plane:
turning only the weight vector, RouteBalance traces a monotone frontier from its cost-priority preset (2. RouteBalance: Fused Model Routing and Load
Balancing for Heterogeneous LLM Serving
Wei Da
University of Cambridge
United Kingdom
Evangelia Kalyvianaki
University of Cambridge
United Kingdom
Abstract
Heterogeneous LLM serving stacks split scheduling into two
layers that optimize in isolation: model routers pick a model
from quality and cost signals while ignoring instance load,
and serving load balancers optimize queues while ignoring quality. We present RouteBalance, a serving-aware
scheduling layer that fuses both into a single online assignment over concrete model instances, jointly trading off quality, latency, and cost. 2 s, quality 0. 354)
through uniform (2. 354)
through uniform (2. 371) and the mid-band (4. 371) and the mid-band (4. 397)
to the quality ceiling at 𝑤𝑞=0. 3) is BEST-Route briefly competitive. The defining property is a single deployed stack reaching every corner by changing only the weights: at 𝑤𝑞=0. 371) and the mid-band (4. 397)
to the quality ceiling at 𝑤𝑞=0. 8
the quality ceiling 0. 419 (concentrating on 72B, 5. 419 (concentrating on 72B, 5. 9 s, low
throughput); at uniform weights 2. 9 s, low
throughput); at uniform weights 2. 8 s across the whole
load range; at the cost-priority corner the cheapest cost of
any system (1.Where the paper says it
Where the paper says it
Where the paper says it
Where the paper says it
Where the paper says it
Where the paper says it
Where the paper says it
Where the paper says it
Where the paper says it
Where the paper says it
Where the paper says it
Where the paper says it
Where the paper says it
Where the paper says it
Where the paper says it
Conclusion
RouteBalance fuses model routing and load balancing into a single online assignment over concrete model instances on a quality–latency–cost simplex; one deployed stack spans cheapest-to-highest-quality by changing only the weight vector, and a four-arm decomposition traces the benefit to pricing latency at model-selection time, a decision the decoupled router-then-balancer stack cannot make The gains hold at scale (28 GPUs, 442 configurations, ≈1.5M requests) against engineering-equalized baselines, with judge-, seed-, and cost-model-robust orderings Open directions include a second model family and topology (a Llama/Gemma port is the immediate next step), production-trace arrivals, and an SLOdriven controller over the weights The framework, scripts, and datasets are released for artifact evaluation The paper concludes that the concurrent-scoring path—a contribution of this work, not part of either baseline (§5)—microbatches the in-flight scoring (routing and quality unchanged), after which mean E2E is serving-bound and both coincide at 2.3–2.8 s The engineering that makes rung (iv) work also explains the gap to rung (ii) The paper proves that the quality ceiling, cost tie, and weight family are what RouteBalance wins on, not headline-cell latency
References
[1] Agrawal, A., Kedia, N., Mohan, J., Panwar, A., Kwatra, N., Gulavani, B. S., Ramjee, R., and Tumanov, A. Vidur: A large-scale simulation framework for llm inference
[2] Ahmad, S., Guan, H., Friedman, B. D., Williams, T., Sitaraman, R. K., and Woo, T. Proteus: A high-throughput inference-serving system with accuracy scaling
[3] Arango, I., Noori, A., Huang, Y., Shahout, R., and Yu, M. Prefix and output length-aware scheduling for efficient online LLM inference
[4] Bao, R., Xue, N., Sun, Y., and Chen, Z. Dynamic quality-latency aware routing for llm inference in wireless edge-device networks
[5] Belcak, P., Heinrich, G., Diao, S., Fu, Y., Dong, X., Muralidharan, S., Lin, Y. C., and Molchanov, P. Small language models are the future of agentic ai
[6] Bin, K., Choi, S., Son, J., Choi, J., Bae, D., Baek, D., Moon, K., Jang, M., and Lee, H. Fineserve: Precision-aware kv slab and two-level scheduling for heterogeneous precision llm serving
[7] Chang, T.-T., and Venkataraman, S. Eva: Cost-efficient cloud-based cluster scheduling
[8] Chen, L., Zaharia, M., and Zou, J. Frugalgpt: How to use large language models while reducing cost and improving performance
[9] Chen, S., Jia, Z., Khan, S., Krishnamurthy, A., and Gibbons, P. B. Slos-serve: Optimized serving of multi-slo llms
[10] Chen, T., and Guestrin, C. Xgboost: A scalable tree boosting system
[11] Cho, J., Kim, M., Choi, H., Heo, G., and Park, J. LLMServingSim: A HW/SW Co-Simulation Infrastructure for LLM Inference Serving at Scale
[12] Cobbe, K., Kosaraju, V., Bavarian, M., Chen, M., Jun, H., Kaiser, L., Plappert, M., Tworek, J., Hilton, J., Nakano, R. Hesse (and others) Training verifiers to solve math word problems
[13] Da. W. and Kalyvianaki E. p. 0 RouteBalance: Fused Model Routing and Load
Balancing for Heterogeneous LLM Serving
Wei Da
University of Cambridge
United Kingdom
Evangelia Kalyvianaki
University of Cambridge
United Kingdom
Abstract
Heterogeneous LLM serving stacks split scheduling into two
layers that optimize in isolation: model routers pick a model
from quality and cost signals while ignoring instance load,
and serving load balancers optimize queues while ignoring quality. We present RouteBalance, a serving-aware
scheduling layer that fuses both into a single online assignment over concrete model instances, jointly trading off quality, latency, and cost.Where the paper says it
[14] Dexter, G., Tang, S., Fatahibaarzi, A., Song, Q., Dharamsi, T., and Gupta, A. LLM query scheduling with prefix reuse and latency constraints
[15] Ding, D., Mallick, A., Zhang, S., Wang, C. Madrigal D. C. H., Xia M. Lakshmanan L. V. S., Wu Q., and Rühle V. BEST-route: Adaptive LLM routing with test-time optimal compute
[16] Douze, M., Guzhva, A., Deng, C., Johnson, J., Szilvasy G., Mazaré P.-E. Lomeli M. Hosseini L. and Jégou H. The faiss library
[17] Duplyakin, D., Ricci, R., Maricq, A., Wong, G., Duerig, J., Eide, E., Stoller, L., Hibler, M., Johnson, D. Webb K. Akella A. Wang K. Ricart G. Landweber L. Elliott C. Zink M. Cecchet E. Kar S.-P Mishra P.: The design and operation of CloudLab
[18] Fan, Q., Zou, A., and Ma, Y. Timebill: Time-budgeted inference for large language models
[19] Fang, J., Shen, Y., Wang, Y., and Chen, L. Improving the end-toend efficiency of offline inference for multi-llm applications based on sampling and simulation
[20] Graham, R. L. Bounds on multiprocessing timing anomalies
[21] Gunasekaran, J. R., Mishra, C. S., Thinakaran, P., Sharma, B., Kandemir, M. T., and Das, C. R. Cocktail: A multidimensional optimization for model serving in cloud
[22] Hu, Q. J., Bieker, J., Li, X., Jiang, N., Keigwin, B., Ranganath G., Keutzer K., and Upadhyay S. Routerbench: A benchmark for multi-llm routing system
[23] Ji, J., Liu, M., Dai, J. Pan X. Beavertails: Towards improved safety alignment of llm via a human-preference dataset
[24] Jiang, D., Ren, X., and Lin, B. Y. Llm-blender: Ensembling large language models with pairwise ranking and generative fusion
[25] JIANG Y., Fu F., Yao X., HE G. Miao X., Klimovic A., CUI B. Yuan B. Demystifying cost-efficiency in LLM serving over heterogeneous GPUs
[26] JIANG Y., Fu F., Yao X., Wang T. CUI B. Klimovic A. and Yoneki E. Thunderserve: High-performance and cost-efficient LLM serving in cloud environments
[27] Jiang, Y., Yan, R., Yao, X., Zhou, Y., Chen B., and Yuan B. Hexgen: generative inference of large language model over heterogeneous environment
[28] JIANG Y., Yan R. and Yuan B. Hexgen-2: Disaggregated generative inference of LLMs in heterogeneous environment
[29] Jitkrittum, W., Narasimhan, H., Rawat, A. S., Juneja J., Wang C., Wang Z., Go A., Lee C.-Y. Shenoy P. Panigrahy R. et al. Universal model routing for efficient llm inference
[30] Jitkrittum, W., Narasimhan, H., Rawat, A. S., Juneja J., Wang C., Wang Z., Go A., Lee C.-Y. Shenoy P. Menon A. K. and Kumar S. Universal model routing for efficient LLM inference
[31] Kraska, T., Beutel, A., Chi, E. H., Dean, J., and Polyzotis N. The case for learned index structures
[32] Kwon, W., Li, Z., Zhuang, S., Sheng Y., Zheng L. Yu C. H. Gonzalez J. Zhang H. and Stoica I. Efficient memory management for large language model serving with pagedattention
[33] Lambert, N., Pyatkin, V., Morrison, J., Miranda, L., Lin B. Y., Chandu K., Dziri N., Kumar S. Zick T. Choi Y. Smith N. A. and Hajishirzi H.: Rewardbench: Evaluating reward models for language modeling
[34] Li, Y. Rethinking predictive LLM routing: When simple KNN beats complex learned routers
[35] Mai, L., et al. Exploiting replication for energy-efficient large-scale parallel batch scheduling
[36] Mei, K., Xu, W., Guo, M., Lin, S., and Zhang, Y. Omnirouter: Budget and performance controllable multi-llm routing
[37] Mei, Y., Zhuang, Y., Miao X., Yang J. Jia Z. and Vinayak R. Helix: 13]
Final Summary
RouteBalance fuses model routing and load balancing into a single online assignment over concrete model instances on a quality–latency–cost simplex one deployed stack spans cheapest-to-highest-quality by changing only the weight vector, and a four-arm decomposition traces the benefit to pricing latency at model-selection time, a decision the decoupled router-then-balancer stack cannot make The gains hold at scale (28 GPUs, 442 configurations, ≈1.5M requests) against engineering-equalized baselines, with judge-, seed-, and cost-model-robust orderings RouteBalance wins or ties every axis against every baseline and is itself never strictly dominated: it strictly dominates the decoupled BEST-Route and dispatcher-only baselines on every axis, and against the strongest baseline, Avengers-Pro, wins quality (+0. p. 4 The same service supports decoupled router/dispatcher baselines: Equation 1 is bypassed, a pluggable estimator first picks a model (AvengersPro 𝑝𝑤-mix, BEST-Route threshold, or passthrough), and a
dispatcher (round-robin, shortest-queue, or random) places
the request within that model’s replica pool. Every baseline
therefore runs inside RouteBalance’s own batching, telemetry, and dispatch path; only the routing logic and dispatcher
differ across rows. each baseline: per-axis best over
the sweep, plus mean E2E under load; bold =best. †Enhanced
rows use our concurrent-scoring (batching), not the baseline
(§6.Where the paper says it
Where the paper says it
Green — the paper says it, and the page is printed. Red — no passage carries it, so treat that sentence as unverified. The same check runs on your own text: check a summary against its source, $5.
Improvements for AI systems
-
Fused Model Routing and Load Balancing: Implement a single online assignment layer that jointly considers quality, latency, and cost by solving a weighted quality-latency-cost score over request-instance pairs. This system can trade off these three factors dynamically based on tunable weights on a 3-simplex to find named operating points like Quality, Latency, and Cost priority corners.
-
Amortized Prompt Estimation: Use an amortized, prompt dependent estimator that feeds a single CPU resident embedding into a k=10 KNN head to return per model quality and expected output length across all candidates in one batch call. This makes the joint decision cheap on the request hot path, keeping it at approximately 32 ms at 12 requests per second.
-
Dead Reckoned Instance State: Employ a dead-reckoned instance state that updates after each dispatch to avoid herding on stale load signals while still allowing later requests in the batch to see the consequences of earlier assignments. This allows the greedy pass to be a good approximation to an NP-hard batch-level matching problem, running in O(RB I).
-
Latency Term Pricing: Incorporate a latency term into model selection during routing decision making, which is what
occupies the frontier.
This allows the system to price latency at model selection time rather than ignoring it, which existing routers omit and which decoupled router-then-balancer stacks cannot achieve. -
Budget Control Integration: Integrate a pre-scoring filter that keeps only candidates whose predicted total cost (input tokens plus KNN predicted output length) fits within a per request budget. This admission filter converts exhaustion into quality by routing to a cheaper model that completes rather than a larger one truncated to near-empty, as shown in the evaluation results.
Abstract
Current heterogeneous LLM serving clusters decouple request scheduling into two independent tiers: learned model routers select a model based on the prompt without visibility into instance-level load, while load balancers assign requests to an instance of that chosen model without cross-model quality or cost awareness. This decoupled hierarchy induces conflicting objectives and severely restricts the global optimization space. For example, a quality-oriented router may stubbornly direct 55% of requests to a 72B model regardless of growing queues, inflating mean latency by 2.4 times under high load. Conversely, a cost-minimizing router over-allocates traffic to the cheapest model, leaving capable instances underutilized and capping aggregate cluster throughput. This paper presents RouteBalance, a serving scheduler that unifies model routing and instance dispatching into a single decision. RouteBalance dynamically batches incoming requests into short, load-adaptive rounds. In each round, it amortizes quality and response-length estimation across candidate models, takes a single snapshot of all instance loads, and solves a normalized assignment problem balancing quality, cost, and estimated latency. On a 28-GPU heterogeneous cluster spanning four Qwen model sizes and diverse GPU architectures, RouteBalance Pareto-dominates 231 of 246 baseline configurations across quality, latency, and cost simultaneously. These baselines comprise combinations of two learned routers with four downstream dispatchers, as well as five standalone dispatchers. At iso-quality, per-rate median reductions across baselines are 23--60% in mean E2E latency and 26--37% in serving cost. Code: https://github.com/AKafakA/route-balance.
Sources
- Vidur: A Large-Scale Simulation Framework For LLM Inference
- Small Language Models are the Future of Agentic AI
- FrugalGPT: How to Use Large Language Models While Reducing Cost and Improving Performance
- RouterBench: A Benchmark for Multi-LLM Routing System
- Universal Model Routing for Efficient LLM Inference
- RouteLLM: Learning to Route LLMs with Preference Data
- Adaptive LLM Routing under Budget Constraints
- When to Reason: Semantic Router for vLLM
- Efficient Training-Free Online Routing for High-Volume Multi-LLM Serving
- CascadeInfer: Length-Aware Scheduling of LLM Serving with Low Latency and Load Balancing
Related papers
- Programmable Probabilistic Computer with 1,000,000 p-bits
- BatchGen: An Architecture for Scalable and Efficient Batch Inference
- Seamless Reconfiguration for DAG-BFT (Technical Report)
- ELDR: Expert-Locality-Aware Decode Routing for PD-Disaggregated MoE Serving
- iScheduler: Reinforcement Learning-Driven Continual Optimization for Large-Scale Resource Investment Problems
- TIRx: A Unified Tile Primitive ML Compiler Across Heterogeneous Backends