Efficient Training-Free Online Routing for High-Volume Multi-LLM Serving
Authors: Fangzhou Wu
Sandeep Silwal
Venue: NeurIPS 2025 poster ()
Keywords: Large Language Models
LLM Routing
Cost-Aware Inference
Online Algorithm
Multi-LLM Serving
Primary area: infrastructure
TL;DR: We propose the first efficient, training-free online routing algorithm for high-volume LLM serving under token budget constraints, achieving significant improvements in both routing performance and cost efficiency.

Abstract: Increasing demand for Large Language Models (LLMs) services imposes substantial deployment and computation costs on providers. 
LLM routing offers a cost-efficient solution by directing queries to the optimal LLM based on model and query features.
However, existing works primarily focus on offline scenarios and struggle to adapt to online settings with high query volume and constrained token budgets.
In this work, we introduce the first training-free algorithm for online routing scenarios.
Our algorithm leverages approximate nearest neighbor search to efficiently estimate the features of queries and performs a one-time optimization over a small set of initial queries to learn a set of routing weights that guide future routing.
We provide a theoretical guarantee that the algorithm achieves a competitive ratio of $1 - o(1)$ under natural assumptions, which is further validated by extensive experiments across 3 benchmark datasets and 8 baselines, showing an average improvement of 3.55$\times$ in performance, 1.85$\times$ in cost efficiency, and nearly 4.25$\times$ in throughput.
Our code is available at https://github.com/fzwark/PORT.

Efficient Training-Free Online Routing for High-Volume Multi-LLM Serving
Fangzhou Wu
Sandeep Silwal University of Wisconsin Madison silwal0cs. risc.edu
University of Wisconsin-Madie fwu890wisc.cm
Abstract
Increasing demand for Large Language Models (LLMs)) services imposes sub- stantial deployment and computation costs on providers. L.LM routing offers a cost-efficient solution by directing queries to the optimal LLM based on model and query features. However, existing works primarily focus on offline scenarios and struggle adapt online settings with high query volume and constrained token budgets. In this work, we introduce the first training-free free algorithm for online routing scenarios. Our algorithm leverages approximate nearest neighbor search to efficiently estimate query features and performs one-time optimiza- tion over a small of initial queries learn routing strategy that guides future routing. We provide theoretical guarantees demonstrating that our algo- rithm achieves a competitive ratio of o1) under natural assumptions, which is further validated by extensive experiments across 3 benchmark datasets and 8 baselines, showing an average improvement of 3.55 in overall performance, 1.85x x in cost efficiency, and nearly 4.25x in throughput. Our code is available at wtt. /wm//fwwark/POTTT
Introduction
The ability of Large Language Models (LLMs) to effectively interpret diverse domain knowledge has rapidly transformed the landscape of automated information processing [17 34 64] growing volume of user queries imposes substantial deployment costs on LLM-serving providers [13] For instance, OpenAl reportedly handles up to 12k user queries per second at peak load [49], while its first Azure supercomputer hosted only around 10k GPUs [41, pushing it to rush in more resources prevent cost spikes (58). As result, improving the overall quality of service, particularly under limited token budget constraints, has become a critical priority for L..M-serving systems.
However, the
One straightforward approach is to route queries with different features to different LLMs while balancing cost and performance 37 23 43.. This idea based on the observation that different LLMs excel in different domains and have varying cost 43,, perfectly aligning with the goal of cost-efficient serving. Existing works typically rely on the model-based predictors 43 complex calculations (e.g., KNN, to route queries to. While effective offline scenarios, these methods face significant limitations in practical online routing. They computationally demanding and introduce additional latency, making them impractical for high- volume, low-latency online environments 43
50
or computationally
ranking) 43
23
predict the optimal LLM
They do not easily generalize dynamic [.LM deployments, where any configuration change incurs costly (66). They are also fundamentally limited in achieving effective online routing under constrained token budgets, they operate under offline assumptions without accounting for the sequential and uncertain nature of real-world query arrivals [4. 47
retraining overhead [50 15
Our work instead proposes the first theoretically grounded online algorithm tailored for high-volume query routing under limited token budget constraints. For each query, we employ Approximate
39th Conference on Neural Information Processing Systems (NcurIPS 2025).

---

Nearest Neighbor Search (ANNS) [25 38 to efficiently estimate its features (performance and cost) for each deployed LLM using historical dataset. This dataset can be easily collected and maintained by L.L.Mgsrving providers from previously served user queries with diverse query types 665. introduces negligible additional deployment overhead, and presents strong adaptivity to different L.LM deployments. The routing problem (see Section 1.1 [.1foo for the formal setup) can be naturally formalized as Mixed-Integer Linear Programming (MILP) that aims to maximize overall performance under token budget constraints. However, solving the global MILP is infeasible in online settings where queries do not arrive simultaneously.
To achieve efficient and pear-optimal routing in the realistic sequential setting, we leverage a key ob- servation by looking at the dual problem: At optimality, the dual objective can be fully parameterized by a single dual variable, which directly yields the optimal routing rule. This further motivates us to treat this dual variable as a set of learnable weights over L.MMs, with the parameterized dual objective serving as the optimization target. Instead of solving the infeasible glohal dual problem, we adapt it to partial optimization over a small set of initial observed queries to estimate these weights, which are then applied to guide the routing decisions for subsequent queries. To improve the generalizability of learned weights to future queries, we adopt a random routing strategy for the observed queries, inspired by ideas from PAC learning [39 [ [10. In addition, we introduce control parameter into the MILP objective that does not affect the optimal solution structure but helps to limit performance deviation on future queries.
Regarding efficiency, our algorithm only performs one-time optimization over a small sample set (i.e., observed queries, typically = 250) and executes practical ANNS per query, making it significantly more computationally efficient than existing methods and well-suited for online routing scenarios. In terms of effectiveness, our theoretical analysis guarantees that the proposed algorithm achieves a competitive ratio 1 - 1 under mild assumptions. This is further supported by extensive experiments, where our method outperforms all 8 baseline methods across diverse routing settings and three benchmark datasets, achieving an average improvement 3.55 in performance, x.85x in cost efficiency, and nearly 4.25x in throughput.
To summarize, our main contributions are:
1. We propose the first training-free online routing algorithm tailored for high-volume multi-LLM, serving under constrained token budgets. Our algorithm estimates query features via efficient ANNS methods, ensuring computational scalability.
Unlike prior work, our method operates directly on the auxiliary dataset without any model training. introducing negligible deployment overhead and enabling deployment scalability across dynamic LLM deployment configurations.
4. Our algorithm performs one-time optimization over small sample set without requiring intensive computational resources, demonstrating high efficiency.
5. We provide formal theoretical guarantees showing that our algorithm achieves competitive ratio of 1 o(1) relative to the offline optimum (which is unknown) under mild assumptions.
6. We conduct extensive experiments on 3 benchmarks against 8 baseline methods, demonstrating that our theoretical guarantees hold in practice and that our algorithm exhibits strong robustness and adaptability across diverse routing environments.
1.1 Background and Formal Problem Setup
LLM Routing, Existing LLM routing research primarily falls into two paradigms. The first
improves response quality while controlling cost, often through ensembling outputs from different
LLMs (26] (55) or cascading strategies that query LLMs sequentially by capability [5] 2 62] 33). These methods incur high latency and cost due multiple model calls per query. The second employs learned model--aseed predictors to estimate the performance or cost for each query and select the optimal LLM [3 [50] 23 B 37 27
LS 20 56). but these approaches introduce nontrivial training overhead. Furthermore, adapting them to varying LLM deployment configurations requires retraining, making them unsuitable for dynamic and resource-constrained online routing. Although recent efforts 47
48 52
42 44 formulate LLM routing as MILP, they struggle in higu-volume online settings, where queries arrive sequentially, rather than simultaneously, making the offline optimal infeasible to compute. We complement these works by introducing the first training-free

---

and efficient online routing method with provable performance guarantees, tailored for high-volume, budget-constrained, and dynamic ALM--eevvng See Appendix [ for extended related work.
Problem Definition. Consider an LLM-serving system deployed with M types of L.MMs. Each LLM type, indexed by E [M] (1, ...-.. M), is allocated a running token budget B; (i.e., representing the limited token budgets available per time unit), with total budget equaling B. Typically, the split of the budget is predetermined before the operation of the system. During each time unit, the system receives a set of queries from various end users, denoted by Q. The goal is to design an online routing strategy z=-) that assigns incoming queries in Q to the available LLMs way that maximizes the overall quality of responses, under the budget constraints.
The offline version of this problem can be naturally formulated as the following MILP (Objective ! where duj denotes the performance score of the response from I.LM query j. and Pij represents the token hudget consumption for L.M processing query j (representing the cost). Specifically, gij can be further decomposed S len(j) S?^ len(ary), ). where S R& and J/ E RM represent fixed costs per token during the prefill and decoding stages for I.IM i, respectively.
max
Σ Σ
diyars [EJM
s.t.
Σ 9ijTh S Bg for dllll i,
(1)
Σ Big S for all
However, solving Objective T (or natural relaxation) directly in practical online settings poses several non-trivial challenges: (i) Inaccessible ground- truth performance and cost: For any query j. the true performance score di and cost By are unavailable without accessing the actual LLMs. (ii) Sequential query arrival under uncertainty: In practice. queries arrive sequentially rather than simultaneously and must be routed without knowledge of future queries. (iii) Computational scalability: High query volume demands routing decisions with low latency and minimal computational overhead. However, methods that rely on solving large-scale MILP or executing computationally intensive model predictors for each incoming query may violate these constraints. (iv) Deployment scalability: L.MM deployment configurations, such as M or the underlying LLMs, may vary across different environments. Thus, the algorithm must be adaptive these variations while minimizing adaptation overhead.
Zig E {0,1
Motivated by these challenges, we study the following online routing algorithmic problem: Given larger set of queries Q arriving in random sequential order, and a predefined token budget constraint, can we design an online routing algorithm that still achieves a near-optimal cumulative
performance? Formally, we aim to ensure Expe 2 1())), where we define Catg := Σ, E, disuts denotes the total performance of the algorithm with routing results Rig. and Copt := E, E, desari denotes the offline MILP optimum with the optimal solution zij--
Cale
2 Methodology
To tackle the challenges, our algorithm estimates the performance scores and costs efficiently using a his- torical dataset (Section2.1] and learns routing strat- egy from small subset of observed queries (of size < <[Q) to guide future query routing (Section 2.2
Algorithm Routing with Learned y*
1: P +cQ (Firet 6-frac. of queries)
2: for j E do
3: Randomly pick wy E (0) [[M]
4: Estimate dij and gis, V E [M]
5: w; > 0 then
2.1 Efficient Performance and Cost Estimation
6: Route to wy-th LLM
7: Compute 7 +- arg min, F(7, P)
Our solution to estimate d and is to leverage a his- torical dataset 1 with a specialized data structure that supports efficient similarity- based retrieval. Specif-
8: Y + Q P
9: for j E Y do
10: Estimate diy and Byy. V [M]
ically, let D = {j. aj, d's 9j ) where a, E RMM represents the response vector generated by the M LLMs for query j. and dy. 9j E R MM denotes the corresponding performance scores and costs.
11: Compute ad:; dunt V E [M]
12: Route to = arg max, (ad,, )
For simplicity, the notation E, denote Eyeq and E, to denote Exepa unless stated otherwise.
3

---

For any incoming query j E Q, we apply classic ANNS method over D in the embedding space, such as DiskANN 225 and HNSW [38], select the most similar data points for estimation. This yields a set of approximate nearest neighbors for j. denoted by R C D. The estimated performance score dej and cost Dig for LLM i are then computed as the mean over these neighbors:
d, = "Tt,EETR, deg. Pig = [R5] EvER, Iig.
One significant advantage of using ANNS compared with other training- approaches is the ease of updating the historical dataset D to adopt various deployment configurations without requiring model retraining. This is particularly advantageous for M---eeri providers, as it incurs almost no additional deployment overhead. Online systems naturally collect and record diverse user queries, which can be directly used to maintain and expand the dataset D. A Although collecting ground-truth performance scores and costs typically requires human or automated evaluation, many providers already integrate such mechanisms (e.g., quality feedback from users) in their systems [7]. Furthermore, widely used ANNS algorithms in practice, such as HNSW@ use graph-based indexing structure, making it substantially more efficient in search complexity (typical Ollog [DI) in practice) compared to traditional instance-baser -bsse methods like exact K-Nearest Neighbor (KNN, O(DD)) 23 achieving significant speedup in search time.
2.2 Online Routing from Observed Queries
With the approximate features di and Йij. we propose an online routing algorithm in Algorithm
Approximate LP with Control Parameter: The first step is to approximate the original MILP using the estimated features di and Øij- In addition, we introduce control parameter a > into the objective, leading to the formulation in Equation (2). The inclusion of a does not affect the optimal solution structure it simply scales the objective value. In fact, a acts as a control parameter to ensure generalizability, which is discussed in Section
Σ
Σ
ad.ymi
max ΣΣ Σ ad.323s
max SEQ (E(M
JEQ
min
BB + Σ Bj
Σ 25 & B., Vi,
s.t. Σ Go S Bi, Vi,
s.t.
iE[M
JEQ
(2)
(3)
(4)
S.L. Bg 2 adj 915%, Vi,j,
Σ mi S 1, Vj.
Σ zy S 1, Vj.
7 2 0, 3, 2 0, Vi,j
Tij {0. 1), Vi,j
Fiy [0, 1]. Vi
Dual LP under Relaxation. Let Smaz denote the max performance score across all queries, and let Copt be the offline upproximate optimum obtained by solving Equation (2) with a removed. When the ratio Copt/ mmaz (or Copt/ 8maz) is sufficiently large as Q grows, which commonly holds in practice, particularly in high-volume settings, the optimal value to the relaxed LP closely approximates that of the original MILP. This is formalized in Lemma 2 and 3 with further discussion in B.1 Based on this observation, we apply LP relaxation to Equation 2 allowing Tay to take fractional values in [0, 1]. This yields the relaxed approximate IP in Equation (3) with its dual given in Equation {
Routing via Learned 7" By complementary slackness, if is the optimal solution Equation (3) and (7. 3) is optimal solution to its dual, then Tij > 0 + 3g max (ad, 7:) This implies that, at optimality, the dual objective can be expressed function parameterized by 7:
F(r) = Σ, Br + Ej max (ady (1)7 (5).
Therefore, ideally, given the offline optimal solution 7, each query j should be routed to the LLM i that maximizes (ad, n.) While it is infeasible to compute such global offline solution in an online setting, this formalization motivates us to treat y as a set of routing weights applied across all LLMs to assist the routing process. Building on this insight, we adapt this idea to the online setting: we learn an estimated set of weights 7 from the first = = queries. The procedure in Algorithm
We note that many other choices are interchangeable here, c.g. see atttps://ann htap:////ammbecccaaakesss www.hmarkc.he.mee.oo com In experiments, the optimality gap between the relaxed LP and the MILP is only 0.016% on SPROUT.

---

reflects this idea exactly where its first stage is to learn an optimal y that minimizes dual objective F(y, P) over the observed queries: F(7, P) < c. B, + ΣEEP max (od.) - 7 (6).
For each query j E P, the estimated features d. and Øij for all models will be calculated and recorded to solve for y". Since this stage requires only a small fraction of the total queries (e < 1), random routing is adopted, which may leave some queries in the waiting queue (lines 3, 5-6 in Algorithm || to improve the generalizability without degrading overall performance. This approach aligns precisely with the core idea of PAC learning [O where uniform and unbiased routing ensures the learned weights 7 generalize to the subsequent routing stage. We formalize this in Lemma and Let the remaining queries be Y = Q \ P. In the second stage, the learned weights 7 are used to route each incoming query j E Y. Specifically, each query is directly assigned to the LLM that maximizes the score (ad.) - ? 9ty) (line 12 in Algorithm [). If the selected LLM has exhausted its budget, the query is placed in a queue to await execution.
Compared to existing methods 43 50 23), which often involve repeated heavy computations, our algorithm is significantly more efficient. It performs optimization only once over a small subset of queries, making it scalable for deployment in high-volume settings.
3 Theoretical Guarantees
In the following main theorem, we show that our algorithm achieves a competitive ratio close to 1 compared to the offline opt Copt, under natural assumptions (see Section B.I for discussion).
Theorem 1. For any given query set Q with random arrival order, Algorithm satisfies Copt
Cate 2
Capt 2 S2( 52 log( (og()1101/e)) where Smaz is the maximum performance score 1 1- + 6) assuming Smaz
(1++) obtained for any query, and t is an e-net defined over all possible routing strategies x+1))
To establish this theorem, we introduce the following necessary but mild assumption (see Section B.I for detailed discussion) and auxiliary lemmas. The key intuition behind approximating features of one query j using a different query j' is that the error between their feature values remains bounded, as long as their embedding representations are close. We formalize this as follows:
Assumption For any query j.y', there exists a value 1j > such that if [[EMB(j) EMB(j'Ill S n. then't V E [M], it holds that (1 ddg < dij < (1 0(8) (1)+ and (1 (60))a S 9ij S (1 + (8))9..', where EMB(-) represents the embedding function of an embedding model.
This approximation strategy naturally introduces estimation errors. Thus, is necessary to quantify the discrepancy between the offline optimum Copt and the offline approximate optimum Copt. We assume that for any query j Q, there exists corresponding feasible set Ry for estimation. This yields the following Lemma? 2 (proof in Section B.22).
Lemma 2. Suppose that Vj E Q, and Vj' E Ríg we have [iEMB(i) - EMB(j')l2 S n) and
that Assumption i holds. Then, the offline approximate optimum Capt satisfies Cape Copt
< 0(8).
Cupt
Algorithm yields the a set of routing results å, from which we define the estimated cumulative performance score Cest E, E, adzz The results & are determined by the learned weights 7 and the budget limitation, and can be represented by x(>²)). Accordingly, Cast can be expressed as Cast = E, min Ex, E, ande).,(77 (7")), where E, represents the maximum feasible contribu- tion under the budget B,, defined as: E. = ΣS adgzm((7)) with argmax ΣS (
s.t. Σ) ())r((1** S B,. We further define the per-LLM estimated performance score Cest, == minf Fr, E, addgann (.")). Analyzing Cest thus provides a way to evaluate the routing decisions x(>"). Unfortunately, directly assessing Cest is challenging as it has a complex step function with discontinuities. To facilitate analysis, we introduce relaxed version C : E,E, addyz% (r"), which removes the step function present in Cest- We further define per- model relaxed estimated performance score Ć Eg addz=)(""); and its counterpart over the observed query set P as Note that for any j E P, we define x,,(7"*) if the index wy
C,(P) := ΣSEP randomly selected in the first stage of the algorithm equals i; otherwise, I.g (7())) 0.
5

---

By removing the discontinuous step function, the analysis becomes tractable. A key requirement for ensuring the performance of the algorithm the generalizability of estimated routing weights 7 on the remaining queries Y. To show this, we first prove that the performance disparity between C(P) and its expected value eC', i.e., (Č(P) cOI, is bounded. Since directly bounding this gap over all possible values of 7 is infeasible due to the infinite parameter space, we use an e-net [60 [1] + (formally defined in Definition D to reduce to a discrete covering set of routing rules, over which we apply union bound. We then extend the analysis to arbitrary 7 values by rounding to T The cumulative error over P is bounded in Lemma (proof in Section B.3p:
Lemma 3. Let 4 be an c-net and assume that Capt 2 C2
a.M (1)))))))) (C S 2/
Smaz
(11+))
then Σ, 2 S 0 212/(1 + C/a)
The following Lemma demonstrates the generalizabilityy of y* on remaining queries Y (proof in Section B.4). This Lemma highlights the role of the control parameter a in our algorithm: it serves as bridge to connect the cost and performance.
Lemma 4. If Vi, it holds that EjEP (e5t)1(7")) - < E,, (( S O(zi, then there exists control parameter o >> O, such that Vi, (1) (I))C - -CO, S zi, and (2) CC. -Eal < Ozz).
This connection further translates the cost constraint (B) to a performance guarantee, which estab- lishes the generalizability of 7" to the remaining queries Y, as formalized in Lemma 5
Lemma 5. Let Tb be an c-net. If Copt 2 22(
a.M lo/eM) ), then Cest (Y) 2 (1 - O(c)
Smaz
((1+4)
Combining the results above, we can prove our main Theorem | (proof in Section [.6).
4 Evaluation
Benchmarks. We use 3 different benchmarks in our experiments: RouterBench (23), SPROUT [50). and Open LLM Leaderboard v2 [16]. RouterBench contains 11 different LLMs, and we randomly sample 10000 queries as the test query dataset and use the remaining data as the historical dataset. Open LLM Leaderboard v2 contains 18 diffcrent LLMs, where we similarly sample 10000 queries for the test dataset and use the rest the historical dataset. SPROUT contains 13 LLMs, and use the training set as the historical dataset, while the validation and test sets are combined to form the test queries. In the main setting, queries embedded using base-base-rrs diversity, we also evaluate with EER-EEbeeddnng-2 2_R [40] and gte-Qwen2-1 1. 5B - instruct [35].
5 (59]. To ensure
Baselines. We compare 8 different routing algorithms, classified into two categories: model-based methods and training-free methods. For model-based methods, following (50) we train two separate Roberta- models [36] to predict generation performance score and cost, yielding: (i) Roberta- perf-routing, routes each query to the model with the highest predicted performance; (ii) Roberta- cost-routing, routes each query to the model with the greatest available budget. Training-fire free methods include: (iv) Random routing: (v) Greedy--pef-routtnng uses ANNS to select the model with the highest predicted performance; (vi) Greedy-coss--outtngg uses ANNS to select the model with the most available budget; (vii) KNN-perf-routing (23), uses KNN to select the model with the highest performance; (vii) KNN-cost-routing 23 uses KNN to select the model with the most available budget; (ix) BatchSplit routing, groups queries into small batches and solves the LP per batch determine routing. We adopt HNSW (38 as the main ANNS algorithm and set the number of candidate neighbors ( R2 to 5 for both ANNS and KNN. For BatchSplit, we use a mini-batch size of 256 balance LP computation cost with the low-latency requirements of online routing.
Metrics.
Three key metrics are used: (1) Performance, the total performance score achieved across all test queries; (2) Performance per Cost, the ratio of total performance to cost, reflecting cost efficiency; (3) Throughput, the total number of queries processed, measuring the processing capacity.
We aim to improve online routing under limited budgets in high-volume settings. To simulate this, we set the total budget to the minimum cost required for a single model to process all test queries, and vary it by a factor from 0.25 to 2 to evaluate robustness. We consider several strategies for splitting the total budget across models. The main setting uses a costteffffieecy-basee split, where the total budget is allocated to each model proportionally to its cost efficiency on the historical dataset D.
Budget.

---

Table I: The main results on RouterBench, SPROUT, and Open LLM Leaderboard v2 are under total budget equal to the cost of the cheapest model, split across models based on cost efficiency. Here, Perf represents the Performance, PPC represents Performance per Cost, Tput represents Throughput, and RP denotes Relative Performance compared with offline approximate optimum (Copt).
RouterBench
SPROUT
Open LLM Leaderboard v2
Algorithm
Port
Cost
PPC
Tput
RP
Perf
Cost
PPC
Tput
RP
Perf
Cost
PPC
Tppt
RP
Random
1384.25
0.427
3243.25
3276 43. 43%
2827.6
0.72 3927.29
4742 47.61% 953.0
0.741 1284.37 2877
49.89%
Groody-Perf
1012.1
0.27
3742.379
1687 31.52%
764.9
0.406
1881.742 742 1083
12.88%
553.0
0,499
1107.91 1189
28.95%
Greedy-Cove Cost
1626.25
0.46
3534.46
4061
50.64%
3934.7
0.849
4630.41
6789
26.25%
1051.0
0,766 1371.30 3164
55.02%
KNN-PPor
1005.1
0.27
3720.58
1677 31.3%
769.6
0.407
1888.46
1084
12.96%
556.0
0.498 1114.29 1194
29.11%
KNN Cost
1592.05
0.46
3454,04
4027 49.58%
3905.1
0.85
4593.37
6709
75%7
991.0
0.766 1293.07
3172 51.88%
BatchSplit
1838.05
0.458
4005.93
3903
57.24%
3975.5
0.83
4784.49
6221
66.94%
1059.0
0.76 1392.07
3009
55.44%
Roberta-Perf
154.5
0.077 2019.00
190 4.81%
458.9
0.283
1621.66
536
7.73%
0.207 738.21
8.01%
Roberta Cost
481.4
0.129 3738.88 1292 14.99%
3996.2
0.848
4709.22
6765
67.29%
1044.0
0,766
1362.53
3173
54.66%
Ours
2718.6
0.447 6075.58 5195 84.66% 4513M05
0.815
5536.74
7475
75.99%
1465.0
0.711 2060.3
3692
76.7%
Offiine Oracle (Algorithm Upper Bounds Reference)
Apprnx
3211.3
0.46 6975. 16 6225 100%. 5938.99
0.85
6986.45
8781
100%
1910.0
0.765
2493.66
4319
100%
Optimumni Coye)
Optinum (Cone) 6376.9 0.46 13865.62 6436 198.5718 11934.4
0.848 14060.34
12336
200.94%5
4688.0
0.763
6143.64 4688 245.44%
Random
Gready Perf
Gready
KNN Cost
BatchSolt
Roberto
Perfor Pefforancc
2000
6000
4000
5000
Throughos
1000
4000
2000
3000
1000
2000
4000
5000
6000
7000
8000
9000
4000
5000
6000
7000
8000
9000
4000
5000
6000
7000
8000
9000
Performance Cost
4000
8000
6000
Performnncs
Throughout
3000
8000
2000
6000
1000
2000
2000
+30
2093
CRE
1003 EOX
<80 2008
1800 L1249 1200
400
920
0000
7200
1000
1O0K 1U00
3000
Performance
1000
Thowuhouu
Performence
1500
2000
1000
1000
4000
5000
6000
7000
8000
9000
4000
5000
6000
7000
8000
9000
4000
5000
6000
7000
8000
9000
Test Querles
Test Queries
#F Test Queries
Figure 1: Results with test query volume varying from 4000 to 9000 (12000). Rows correspond to different datasets: RouterBench (top), SPROUT (middle), and Open LLM Leaderboard v2 (bottom).
To assess robustness, we also consider uniform, random, extreme, cost-based, and performance-basee splits. For the random split, budgets are randomly assigned and averaged over 100 runs. In the extreme split, 80% the budget allocated to the least cost-efficient models (h = 1 to 5), and the remaining 20% to the others. For additional experimental setup details, see Section A
Main Results. Table presents the main results under the benchmarks, using a 0.0001 and e = 0.025 for our algorithm, with the maximum available test queries, and historical data in the evaluation. Our algorithm consistently outperforms all 8 baselines in performance, cost efficiency, and throughput. On average, it exceeds all basclines by 3.55x in performance, 1.85x in cost efficiency, and nearly 4.25 in throughput. Even against the strongest baseline, BatchSplit, our algorithm still achieves with 33 higher performance, 38% better cost efficiency, and 24% higher throughput across all benchmarks. We further compare our method to the offline approximate oracle (Capt). and find that it achieves 75.99% to 84.66% % of the approximate oracle's 's performance. These results align closely with our theoretical guarantees, further validating the effectiveness of our algorithm.
7

---

rerbomaee
4003
4020
2500-
2500
Col
CMN Put
fater Coel
Ous
Sardor
oN Pul
Cal
hotera Pat
Oun
Credd Bet
Cha CR CWN
ON Ca
1090
1000
2000
Botern fubith
Figure 2: Results under 100 random query orders. (Left right): the first three subfigures show results on RouterBench, the next three on SPROUT, and the last three on Open LLM Leaderboard v2.
Rondom
Greedty_Pet Pert
Cosetty_oost
KMB, Perf
BatchSp
Our
10000
2000
Performece
4000
8000
3000
Performance
2000
1000
1000
500
10
14
10
14
16
2
10
14
16
Deployed LLMs
Deplyyed LLMs
Deployed LLMS
Figure Results Open LLM Leaderboard v2 when varying LLM deployment configurations.
Putormnn
5000
1030
5000
100D
2000
2000
Tefumrane Pereeraee
4000
LO00
2000
1000
2000
22000
4000
20004
1000
2000
1000
2000
530
3,000
Pefennaes
2000
4000
Nefemarce
40000
2030
1000
2000-
Rerforaree
2020
1000
1000
2000
4000
Nefoomace
Imreghos
1000
2000
Banstom
Greadh For
KMN Pont
Rast 1od
arbwr Oui
KWN Port
6MN Cool
Rebern Por
Random
Grer Coal
Cod
faterra Crd
Random
Sreads Eod
ENK Port
Bast Bostfoa
Ruboraa Cod
Qurs
Gready Pert
1Wh Pont
Cod
BusToak
Rubaraa full
Qua
Randum
dree Cos
DAN Cod
Rubaria hegg
Neterno Cost
Grouds
Goenty
Figure 4: Results under different budget splitting strategies. Each group subfigures corresponds to one strategy: (a) cost-brr based split (subfigures 1-9), (b) performance- based split (10-18), (c) uniform split (19-27), and (d) random split (28-36). Within each group, first three subfigures correspond to RouterBench, the next three to SPROUT, and the last three to Open L.M Leaderboard v2.
4.1 Robustness
Query Volume. We vary the number of test queries from 4000 to 12000, serving as different traffic volumes. Figure eigure[[eccrrl shows that our method consistently outperforms all baselines across all benchmarks and metrics. It scales gracefully, maintaining the highest performance, cost efficiency, and throughput as the query volume increases from low to extremely high loads. Notably, across all three benchmarks, the performance gap between method and the strongest baseline (BatchSplit) widens with increasing load, reaching about 50% higher performance on RouterBench at maximum volume. These results highlight the strong robustness of our approach under varying query volumes.
We evaluate the robustness of our algorithm under varying query arrival orders. Specifically, we independently shuffle test queries 100 times to simulate realistic, unpredictable online environments. As shown Figure 2 our method consistently outperforms all baselines across metrics and benchmarks under these random permutations, demonstrating strong robustness. We further
Query Arrival Order.

---

Greedy Gieedyy_Com
Beichöplt
Nurformance par Cost
Performance
1000
2000
Throughput
1500
1000
2000
250
Cost-Effective LLNs with Budget
|Least Cost-Effective with Budget
Least Cest-Lffective LLMs with Budget
Figure 5: Results on RouterBench under the extreme budget split.
Gready Porf
KM Cost
BaachSolk
Parf
Roborto
4000
6000
8000
Ieffrmance
3000
5000
Throughout
6000
2000
4000
2000
3000
1000
2000
0.25 0.50 0.75 1.00 1.50 1,75
0.25 0.50 0.75 1.25 1.50 1,75 2,00
0.50 0.75 1,00 1.25 1.50 1.75 2.00
Budget the cheapest
Budget (#cost of cheapest model)
Dudget (xcost the cheapest modell
Figure 6: Results on RouterBench with budget from 0.25 to 2x the cost of the cheapest model.
evaluate a worst-case adversarial setting, where expensive queries arrive first with results provided in Section C.T. showing that our algorithm still maintains strong performance.
Scalability to LLM Deployments. We assess robustness under varying deployment config configurations by randomly selecting 2 to 16 LLMss from the Open LLM Leaderboard v2 and repeating each experiment 10 times for diversity. As shown in Figure 3 our algorithm consistently achieves strong performance across configurations, demonstrating strong robustness and adaptability diverse LLM deployments. Additional results on RouterBench and SPROUT (see Section C.2 further confirm its scalability.
Budget Split. We extend the default cost-efficiency-basee split to five alternative strategies. As shown in Figure[4] our algorithm consistently outperforms all baselines across all benchmarks and metrics under cost-based, performance-bast based, uniform, and random splits. Even under the extreme split scenario (Figure [5) it still achieves strong results. Notably, when 80% of the budget is allocated single model (h- = 1), our algorithm achieves nearly 2x the performance of the strongest baseline (BatchSplit) on RouterBench. Additional results on SPROUT and Open LLM Leaderboard v2 (see Section further highlight its robustness across diverse budget allocation schemes.
Total Budget. We vary the total budget B from 0.25 to 2x the cost of the cheapest model. Results that our algorithm consistently outperforms all baselines across metrics on RouterBench as the budget increases. Even under extremely limited budgets, our algorithm can still achieve the best performance. Additional results SPROUT and Open LLM Leaderboard v2 (see Section CC44 further highlight its robustness and adaptability across diverse budget constraints.
shown in Figure
We evaluate the routing latency of Algorithm ! under varying query volumes. As shown in Appendix Table our method incurs negligible decision overhead compared to existing training-free baselines. To assess robustness to data quality, we further consider a noisy setting with label perturbations and an -iitt---ittiitttion setting with distribution shift. Results in Appendix Table 8 indicate that our algorithm consistently outperforms all baselines both settings. See Section C.5 for detailed results.
Routing Overhead & Quality of Historical Data.
Historical Data & Search Candidates. Further results in Appendix C.6 show that our algorithm
remains robust under varying historical data sizes and different numbers of ANNS/KNN candidates.
4.2 Ablation Studies
(1) Impact of Embedding Models. We evaluate the impact of different embedding models used in ANNS and observe that our algorithm consistently outperforms baselines across all benchmarks (see Appendix Figure 13), demonstrating its robustness to embedding choice. (2) Impact of a and e. We evaluate sensitivity to and as shown in Appendix Figure [4] Performance decreases with
larger a, with the best result at 0.0001, aligned with Lemma[] For e, performance increases initially,
reaches the peak, and then declines with further increase. See Section C.7 for details.

---

5 Limitations & Conclusion
Multi-Factor Routing. In more complex LLM-serving scenarios, additional factors such as query traffic may need to be considered. However, the primary goal of this work is to develop cost-efficient online routing algorithm, a problem that has received growing attention in recent literature 43 23 [5]].
To isolate this core algorithmic problem,
focus solely on two of the most widely studied factors: performance and cost [3 23 [5], without explicitly modeling other routing considerations. Those routing factors can be broadly categorized into two types. (i) Query-intrinsic features, which are independent of time and query order, such as per-model response quality and cost, can be seamlessly incorporated into our algorithm by adding additional constraints to the original MILP formulation. Each added constraint introduces new linear term with a corresponding dual variable in the dual objective, and these dual variables together serve as learnable routing weights for future routing. (ii) In contrast, operational-state features, which depend on dynamic system conditions (e.g., query traffic or system load), fall outside the scope of our current formulation. These factors are more aligned with a related but orthogonal problem: load balancing under traffic constraints. Nonetheless, we believe our algorithm offers natural foundation for future extensions that incorporate such traffic-aware adaptations. Further discussion is provided in Section D
Conclusion. This work presents the first efficient, training-free online routing algorithm for high- volume, budget-constrained L.LM serving. Our algorithm uses ANNS over historical data to efficiently estimate query features and performs one-time optimization on a small set of observed queries to learn routing weights that ensure strong performance and generalizability, and efficiency. We theoretically guarantee competitive ratio of (1) under mild assumptions, validated by extensive experiments on 3 benchmarks against 8 baselines. Our method consistently outperforms all baselines, underscoring strong effectiveness and robustness in diverse online routing scenarios.
References
[1] Gagan Aggarwal, Gagan Goel, Chinmay Karande, and Aranyak Mehta. Online vertex- werght-weighted bipartite matching and single-bid budgeted allocations. In Proceedings of the twenty-second annual ACM-SIAM symposium on Discrete Algorithms, pages 1263-1264. SIAM, 2011. 1.
[2] Pranjal Aggarwal, Aman Madaan, Ankit Anand, Srividya Pranavi Potharaju, Swaroop Mishra, Pei Zhou, Aditya Gupta, Dheeraj Rajagopal, Karthik Kappaganthu, Yiming Yang, et al. Automix: Automatically mixing language models. Advances in Neural Information Processing Systems, 37:131000-13100 2024.
[3] Jacob Austin, Augustus Odena, Maxwell Nye, Maarten Bosma, Henryk Michalewski, David Dohan, Ellen Jiang, Carrie Cai, Michael Terry, Quoe Le, et al. Program synthesis with large language models. arXiv preprini
2021.
[4] Niv Buchbinder, Kamal Jain, and Joseph Naor. Online primal-dual algorithms for maximizing ad-auctions revenue. In Earopean Symposium on Algorithms, pages 253-264. Springer, 2007.
[5] Lingjiao Chen, Matei Zaharia, and James Zou. Frugalgpt: How to use large language models while reducing cost and improving performance. Transactions on Machine Learning Research, 2023.
[6] Ye Chen, Pavel Berkhin, Bo Anderson, and Nikhil R Devanur. Real-time bidding algorithms for performance- display ad allocation. In Proceedings of the 17th ACM SIGKDD international conference on Knowledge discovery and data mining, pages 1307-1315, 2011.
[7] Wei-Lin Chiang, Lianmin Zheng, Ying Sheng, Anastasios Nikolas Angelopoulos, Tianle Li, Dacheng Li, Banghua Zhu, Hao Zhang, Michael Jordan, Joseph E Gonzalez, et al. Chatbot An open platform for evaluating Ilms by human preference. In Forty-firsi International Conference on Machine Learning, 2024.
arena:
[8] Peter Clark, Isaac Cowhey, Oren Etzioni, Tushar Khot, Ashish Sabharwal, Carissa Schoenick, and Oyvind Tafjord. Think you have solved question answering? try are, the ai2 reasoning challenge. arXiv preprint arXiv:1803.00 2018.
10

---

[9] Karl Cobbe, Vineet Kosaraju, Mohammad Bavarian, Mark Chen, Heewoo Jun, Lukasz Kaiser, Matthias Plappert, Jerry Tworek, Jacob Hilton, Reiichiro Nakano, et al. Training verifiers to solve math word problems, 2021. URL htpp:://axxiv. org/abs/21 10.11108,1.1 9, 2021.
[10] François Denis. Pac learning from positive statistical queries. In International conference on algorithmic learning theory, pages 112-126. Springer, 1998.
[11] Nikhil Devanur and Thomas Hayes. The adwords problem: online keyword matching with budgeted bidders under random permutations. In Proceedings of the 10th ACM conference on Electronic commerce, pages 71-78, 2009.
[12] Steven Diamond and Stephen Boyd. Cvxpy: A python-embedded modeling language for convex optimization. Journal of Machine Learning Research, 17(83):1-5, 2016.
[13] Dujian Ding, Ankur Mallick, Chi Wang, Robert Sim, Subhabrata Mukherjee, Victor Rühle, Laks VS Lakshmanan, and Ahmed Hassan Awadallah. Hybrid Ilm: Cost-efficient and quality- aware query routing. In The Twelfth International Conference Learning Representations, 2024.
[14] Jon Feldman, Nitish Korula, Vahab Mirrokni, Shanmugavclayuthan Muthukrishnan, and Martin Pál. Online ad assignment with free disposal. In International workshop on internet and network economics, pages 374-385. Springer, 2009.
[15] Tao Feng, Yanzhen Shen, and Jiaxuan You. Graphrouter: A graph-based router for Ilm selections. In The Thirteenth International Conference Learning Representations, 2024.
[16] C. Fourrier, N. Habib, A. Lozovskaya, K. Szafer, and T. Wolf. Open Ilm leaderboard v2. https /huggingface co wwtp:///pppe-mmmmmmmaraaaaaoaooe open_ 1aaeee_m1___eeddeeeee
2024.
[17] Simon Frieder, Luca Pinchetti, Alexis Chevalier, Ryan-Rhy Griffiths, Tommaso Salvatori, Thomas Lukasiewicz, Philipp Christian Petersen, and Julius Berner. Mathematical capabilities of chatGPT. Thirty-seventh Conference on Neural Information Processing Systems Datasets and Benchmarks Track, 2023.
[18] Robert Friel, Masha Belyi, and Atindriyo Sanyal. Ragbench: Explainable benchmark for retrieval-augmeente generation systems. arXiv preprint 10X1v 2024.
[19] Gagan Goel and Aranyak Mehta. Online budgeted matching in random input models with applications to adwords. In SODA, volume 8, pages 982-991, 2008
[20] Surya Narayanan Hari and Matt Thomson. Tryage: Real-time, intelligent routing of user prompts to large language models. arXiv preprint wxXiv22308.16600 2023.
[21] Dan Hendrycks, Collin Burns, Steven Basart, Andy Zou, Mantas Mazeika, Dawn Song, and Jacob Steinhardt. Measuring massive multitask language understanding. In International Conference on Learning Representations, 2020.
[22] Dan Hendrycks, Collin Burns, Saurav Kadavath, Akul Arora, Steven Basart, Eric Tang, Dawn Song, and Jacob Steinhardt. Measuring mathematical problem solving with the math dataset. In Thirty-fifth Conference on Neural Information Processing Systems Datasets and Benchmarks Track (Round 2), 2021.
[23] Qitian Jason Hu, Jacob Bieker, Xiuyu Li, Nan Jiang. Benjamin Keigwin, Gaurav Ranganath, Kurt Keutzer, and Shriyash Kaustubh Upadhyay. Routerbench: A benchmark for multi-llm routing system. arXiv preprint arXiv:2403. /2031, 2024.
[24] Qi Huangfu and JA Julian Hall. Parallelizing the dual revised simplex method. Mathematical Programming Computation, 10(1):119-142, 2018.
[25] Suhas Jayaram Subramanya, Fnu Devvrit, Harsha Vardhan Simhadri, Ravishankar Krishnawamy, and Rohan Kadekodi. Diskann: Fast accurate billion-point nearest neighbor search on a single node. Advances in neural information processing Systems, 32, 2019.

---

[26] Dongfu Jiang, Xiang Ren, and Bill Yuchen Lin. LIm-blender: Ensembling large language models with pairwise ranking and generative fusion. In Proceedings of the 6l Annual Meeting of the Association for Computational Linguistics (Volume I: Long Papers), pages 14165-14178, 2023.
[27] Wittawat Jitkrittum, Harikrishna Narasimhan, Ankit Singh Rawat, Jeevesh Juneja, Zifeng Wang. Chen- Yu Lee, Pradeep Shenoy, Rina Panigrahy, Aditya Krishna Menon, and Sanjiv Kumar. Universal model routing for efficient Ilm inference. arXiv preprint arXiv:2502.08773 2025.
[28] Bala Kalyanasundaram and Kirk Pruhs. An optimal deterministic algorithm for online b-matching. Theoretical Computer Science, 233(1-2):319-325) 2000.
[29] Michael Kapralov, Ian Post, and Jan Vondrák. Online submodular welfare maximization: Greedy is optimal. In Proceedings of the twenty-fourth annual ACM-SIAM symposium on Discrete algorithms, pages 1216-1225. SIAM, 2013.
[30] Richard M Karp, Umesh V Vazirani, and Vijay V Vazirani. An optimal algorithm for on-line bipartite matching. In Proceedings of the twenty-second annual ACM symposium on Theory of computing, pages 352-358, 1990.
[31] Thomas Kesselheim, Klaus Radke, Andreas Tönnis, and Berthold Vöcking. An optimal online algorithm for weighted bipartite matching and extensions to combinatorial auctions. In European symposium on algorithmss, pages 589-608 Springer, 2013.
[32] Nitish Korula, Vahab Mirrokni, and Morteza Zadimoghaddam. Online submodular welfare maximization: Greedy beats 1/2 in random order. In Proceedings of the forty-seventh annual ACM symposium Theory of computing, pages 889-898, 2015.
[33] Chia-Hsuan Lee, Hao Cheng, and Mari Ostendorf. Orchestrallm: Efficient orchestration of language models for dialogue state tracking. In Proceedings of the 2024 Conference of the North American Chapter of the Association for Computational Linguistics: Human Language Technologies (Volume 1: Long Papers), pages 1434-1445, 2024.
[34] Kay Lehnert. Ai insights into theoretical physics and the swampland program: A journey through the cosmos with chatgpt. arXiv preprint arXiv:2301.08155, 2023.
[35] Zehan Li, Xin Zhang, Yanzhao Zhang, Dingkun Long, Pengjun Xie, and Meishan Zhang. Towards general text embeddings with multi-stage contrastive learning. arXiv preprint arXiv:2308. 03281, 2023.
[36] Yinhan Liu, Myle Ott, Naman Goyal, Jingfei Du Mandar Joshi, Danqi Chen, Omer Levy, Mike Lewis, Luke Zettlemoyer, and Veselin Stoyanov. Roberta: A robustly optimized BERT pretraining approach. CoRR, abs/1907, 1692, 2019.
[37] Keming Lu, Hongyi Yuan, Runji Lin, Junyang Lin, Zheng Yuan, Chang Zhou, and Jingren Zhou. Routing to the expert: Efficient reward-guided ensemble of large language models. In Proceedings of the 2024 Conference of the North Americun Chapter of the Association for Computational Linguistics: Human Language Technologies (Volume 1: Long Papers), pages 1964-1974, 2024.
[38] Yu A Malkov and Dmitry A Yashunin. Efficient and robust approximate nearest neighbor search using hicrarchical navigable small world graphs. IEEE transactions on pattern analysis and machine intelligence, 22(4):824-836 2018.
[39] Aranyak Mchta, Amin Saberi, Umesh Vazirani, and Vijay Vazirani. Adwords and generalized online matching. Journal of the ACM (JACM), 54(5):22-c) 2007.
[40] Rui Meng, Ye Liu, Shafiq Rayhan Joty, Caiming Xiong, Yingho Zhou, and Semih Yavuz. Sfr-embedding-2:: Advanced text embedding with multi-stage training. 2024.
[41] Microsoft News Center. Microsoft unveils a 10 k-gpu azure supercomputer for openai. 2020. 2020.
12

---

[42] Alireza Mohammadshahi, Arshad Rafiq Shaikh, and Majid Yazdani. Routoo: Learning to route to large language models effectively. arXiv preprint arXiv:2401.13979, 2024.
[43] Isaac Ong, Amjad Almahairi, Vincent Wu, Wei-Lin Chiang, Tianhao Wu, Joseph E. Gonzalez, M Waleed Kadous, and Ion Stoica. MouteLLM: Learning to route LLMs from preference data. In The Thirteenth International Conference on Learning Representations, 2025.
[44] Balaji Rama, Kai Mei, and Yongfeng Zhang. Cerebrum (aios sdk): A platform for agent development, deployment, distribution, and discovery. Proceedings of the 2025 Conference of the Nations of the Americas Chapter of the Association for Computational Linguistics: Human Language Technologies (System Demonstrations), pages 135-142, 2025.
[45] David Rein, Betty Li Hou, Asa Cooper Stickland, Jackson Petty, Richard Yuanzhe Pang, Julien Dirani, Julian Michael, and Samuel R Bowman. Gpqa: A graduate-level google-proof q&a benchmark. In First Conference on Language Modeling, 2024.
[46] Keisuke Sakaguchi, Ronan Le Bras, Chandra Bhagavatula, and Yejin Choi. Winogrande: An adversarial winograd schema challenge at scale. Communications of the ACM, 64(9):99-106, 2021.
[47] Marija Sakota, Maxime Peyrard, and Robert West. Fly-swat or cannon? cost-effective language model choice via meta-modeling. In Proceedings of the 17th ACM International Conference on Web Search and Data Mining, pages 606-615, 2024.
[48] Tal Shnitzer, Anthony Ou, Mirian Silva, Kate Soule, Yuekai Sun, Justin Solomon, Neil Thomp- son, and Mikhail Yurochkin. Large language model routing with benchmark datasets. In Annual Conference on Neural Information Processing Systems, 2023.
[49] Shubham Singh. Chatgpt statistics (2025): Dau & mau data worldwide. http://wwwwwwmmmdddeemm/////////
2025.
[50] Seamus Somerstep, Felipe Maia Polo, Allysson Flavio Melo de Oliveira, Prattyush Mangal, Mírian Silva. Onkar Bhardwaj, Mikhail Yurochkin, and Subha Maity. Carrot: cost aware rate optimal router. arXiv preprint arXiv:2502.03266 2025.
[51] Zayne Rea Sprague, Xi Ye, Kaj Bostrom, Swarat Chaudhuri, and Greg Durrett. MuSR: Testing the limits of thhought with multistep soft reasoning. In The Twelfth International Conference on Learning Representations, 2024.
[52] Dimitris Stripelis, Zhaozhuo Xu, Zijian Hu, Alay Diliphhai Shah, Han Jin, Yuhang Yao, Jipeng Zhang, Tong Zhang, Salman Avestimehr, and Chaoyang He. Tensoropera router: A multi-model router for efficient Ilm inference. In Proceedings of the 2024 Conference on Empirical Methods Industry Track, pages 452-462, 2024.
in Natural Language Processing:
(53) Mirac Suzgun, Nathan Scales, Nathanael Schärli, Sebastian Gehrmann, Yi Tay, Hyung Won Chung, Aakanksha Chowdhery, Quoe Le, Ed Chi, Denny Zhou, al. Challenging big-bench tasks and whether chain-of chain-of-thought can solve them. In Findings of the Association for Compu- tational Linguisties: ACL 2023, pages 13003-13051. 2023.
[54] Teknium. Openhermes-2.55
2023.
[55] Hongyi Wang, Felipe Maia Polo, Yuekai Sun, Souvik Kundu, Eric Xing, and Mikhail Yurochkin. Fusing models with complementary expertise. In Annual Conference on Neural Information Processing Systems, 2023.
[56] Xinyuan Wang, Yanchi Liu, Wei Cheng, Xujiang Zhao, Zhengzhang Chen, Wenchao Yu, Yanjie Fu, and Haifeng Chen. Mixllm: Dynamic routing in mixed large language models. In Proceedings of the 2025 Conference of the Nations of the Americas Chapter of the Association for Computational Linguisties: Human Language Technologies (Volume 1: Long Papers), pages 10912-10922, 2025.
[57] Yubo Wang, Xueguang Ma, Ge Zhang, Yuansheng Ni, Abhranil Chandra, Shiguang Guo, Weiming Ren, Aaran Arulraj, Xuan He, Ziyan Jiang, et al. Mmlu-pro: A more robust and challenging multi-task language understanding benchmark. In The Thirty-eight Conference on Neural Information Processing Systems Datasets and Benchmarks Track, 2024.
13

---

[58] Kyle Wiggers. gpus/, 2025.
Openai ceo sam altman says the company is "out of gpus'. -aaaia----------aiaeaeae saeeeaa-say--tte--ommae oouttoff
httpss//ccheruucc..c////2/////21
[59] Shitao Xiao, Zheng Liu, Peitian Zhang, Niklas Muennighoff, Defu Lian, and Jian- Yun Nie. C- pack: Packed resources for general chinese embeddings. In Proceedings of the 47th international ACM SIGIR conference research and development in information retrieval, pages 641-649, 2024.
[60] Haike Xu, Piotr Indyk, and Sandeep Silwal. A bi-metric framework for efficient nearest neighbor search. In The 1st Workshop Vector Databases, 2025.
[61] Weizhe Yuan, Graham Neubig, and Pengfei Liu. Bartscore: Evaluating generated text text generation. Advances in neural information processing systems, 27777777777777 2021.
[62] Murong Yue, Jie Zhao, Min Zhang. Liang Du, and Ziyu Yao. Large language model cascades with mixture of thought representations for cost-efficient reasoning. In The Twelfth International Conference Learning Representations, 2024.
[63] Rowan Zellers, Ari Holtzman, Yonatan Bisk, Ali Farhadi, and Yejin Choi. Hellaswag: Can a machine really finish your sentence? In Proceedings of the 57th Annual Meeting of the Association for Computational Linguistics, pages 4791 48000, 2019.
[64] Qiang Zhang, Keyan Ding, Tianwen Lv, Xinda Wang, Qingyu Yin, Yiwen Zhang, Jing Yu, Yuhao Wang, Xiaotong Li, Zhuoyi Xiang, et al. Scientific large language models: A survey on biological chemical domains. ACM Computing Surveys, 57(6):1-38, 2025.
[65] Lianmin Zheng, Wei-Lin Chiang. Ying Sheng, Siyuan Zhuang, Zhanghao Wu, Yonghao Zhuang. Zi Lin, Zhuohan Li, Dacheng Li, Eric Xing, Hao Zhang, Joseph E Gonzalez, and Ion Stoica. Judging llm-as-a-judge with mt-bench and chatbot arena. In A. Oh, T.. Naumann, Globerson, K. Saenko, M. Hardt, and S. Levine, editors, Advances in Neural Information Processing Systems, volume 36, pages 46595-46623. Curran Associates, Inc., 2023.
[66] Ciyou Zhu, Richard Byrd, Peihuang Lu, and Jorge Nocedal. Algorithm 778: L-bfgs-b: Fortran subroutines for large-scale bound-constrained optimization. ACM Transactions mathematical software (TOMS), 2304)5550-560 1997.
14

---

NeurIPS Paper Checklist
1. Claims
Question: Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Answer: [Yes]
Justification: Yes, the method, theoretical analysis, and experiment sections justify all the claims made in the abstract and introduction. Additional clarifications are also provided in the Appendix.
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made the paper.
The abstract and/or introduction should clearly state the claims made, including the contributions made in the paper and important assumptions and limitations. A No
NA answer to this question will not be perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results can be expected to generalize to other settings.
is fine to include aspirational goals as motivation as long as is clear that these goals not attained by the paper.
2. Limitations
Question:
Does the paper discuss the limitations of the work performed by the authors?
Answer: [Yes]
Justification: Yes, we outline the limitation our method in Section
Guidelines:
The answer NA means that the paper has limitation while the answer No means that the paper has limitations, but those are not discussed in the paper.
The authors are encouraged to create a separate "Limitations" section in their paper.
The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (c.g.. independence assumptions, noiseless settings, model sell-specfiiaatinn asymptotic approximations only holding locally). ). The authors should reflect on how these assumptions might be violated in practice and what the implications would be.
The authors should reflect the scope of the claims made, e.g., if the approach was only tested on few datasets or with few runs. In general, empirical results often depend on implicit assumptions, which should be articulated.
The authors should reflect on the factors that influence the performance of the approach. For example, facial recognition algorithm may perform poorly when image resolution low or images are taken in low lighting. Or speech-to-tex, system might not be used reliably to provide closed captions for online lectures because it fails handle technical jargon.
The authors should discuss the computational efficiency of the proposed algorithms and how they scale with dataset size.
If applicable, the authors should discuss possible limitations of their approach to address problems of privacy and faimesss.
While the authors might fear that complete honesty about limitations might be used by reviewers as grounds for rejection, a worse outcome might be that reviewers discover limitations that aren't 't acknowledged in the paper. The authors should use their best judgment and recognize that individual actions in favor of transparency play an impor- tant role in developing norms that preserve the integrity of the community, Reviewers will be specifically instructed to not penalize honesty concerning limitations.
3. Theory assumptions and proofs
Question: For each theoretical result, does the paper provide the full set of assumptions and complete (and correct) proof?
15

---

Answer: [Yes]
Justification: Yes, we provide the full set of assumptions, lemmas, and the main theorem in Section 3 along with detailed discussions and complete proofs in Section B
Guidelines:
The answer NA means that the paper does not include theoretical results. All the theorems, formulas, and proofs in the paper should be numbered and cross referenced.
All assumptions should be clearly stated or referenced the statement of any theorems.
The proofs can either appear in the main paper or the supplemental material, but they appear in the supplemental material, the authors are encouraged provide short proof sketch to provide intuition.
Inversely, any informal proof provided in the core of the paper should be complemented by formal proofs provided in appendix or supplemental material.
Theorems and Lemmas that the proof relies upon should be properly referenced.
4. Experimental result reproducibility
Does the paper fully disclose all the information needed to reproduce the main ex- perimental results the paper to the extent that affects the main claims and/or conclusions of the paper (regardless of whether the code and data are provided or not)?
Question:
Answer: [Yes]
Justification: Yes, we disclose all information needed to reproduce the main experimental results of the paper in Section 4 and Section
Guidelines:
The answer NA means that the paper does not include experiments.
If the paper includes experiments, a No answer to this question will not be perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not.
If the contribution is dataset and/or model, the authors should describe the steps taken to make their results reproducible or verifiable.
Depending on the contribution, reproducibility can be accomplished in various ways. For example, if the contribution is novel architecture, describing the architecture fully might suffice, or if the contribution a specific model and empirical evaluation, it may be necessary to either make it possible for others to replicate the model with the same dataset, or provide access to the model. In general. releasing code and data is often one good way accomplish this, but reproducibility instructions for how to replicate the results, access to a hosted model (e.g.. in the case of large language model), releasing of a model checkpoint, other means that appropriate to the research performed.
also be provided via detailed
While NeurIPS does not require releasing code, the conference does require all submis- sions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) If the contribution is primarily a new algorithm, the paper should make it clear how to reproduce that algorithm.
(b) the contribution is primarily new model architecture, the paper should describe the architecture clearly and fully.
(c) If the contribution is a new model (e.g., a large language model), then there should either be way to access this model for reproducing the results or way to reproduce the model (e.g., with an open-source dataset or instructions for how to construct the dataset).
(d) We recognize that reprodueibility may be tricky in some cases, in which authors are welcome to describe the particular way they provide for reproducibility. In the case of closed-source models, it may be that access to the model is limited in some way (e.g., to registered users), but it should be possible for other researchers have some path reproducing or verifying the results.
5. Open access to data and code
16

---

Question: Does the paper provide open access to the data and code, with sufficient instruc- tions faithfully reproduce the main experimental results, as described in supplemental material?
Answer: [Yes]
Yes, all the models and datasets work with in the paper open-source, and we have submitted our code the Supplementary Material.
Justification:
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurlPS code and data submission guidelines (https://niis.cc.
aublic/guudees/Codeebbbmsss caapssioooolyyyy for more details.
While encourage the release of code and data, understand that this might not be possible, so "No" is an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (e.g., for new open-source benchmark).
The instructions should contain the exact command and environment needed to run to reproduce the results. See the NeurlPS code and data submission guidelines (https
/ wwtps/cccppplgguuuuaeeeeae
Ctteeee//oSSSSSSSSSS.oeaa www.ssssiicggyooo for more details.
The authors should provide instructions on data access and preparation, including how to access the raw data, preprocessed data, intermediate data, and generated data, etc.
The authors should provide scripts to reproduce all experimental results for the proposed method and baselines. only subset of experiments are reproducible, they should state which ones are omitted from the script and why.
At submission time, to preserve anonymity, the authors should release anonymized versions (if applicable).
Providing as much information as possible in supplemental material (appended the paper) is recommended, but including URLs to data and code is permitted.
6. Experimental setting/details
Question: Does the paper specify all the training and test details (e.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?
Answer: [Yes]
Justification: Yes, all experimental details are clarified in Section 4 and Section A
Guidelines:
The answer NA means that the paper does not include experiments.
The experimental setting should be presented in the core of the paper to a level of detail that is necessary to appreciate the results and make sense of them.
The full details can be provided either with the code, in appendix, as supplemental material.
7. Experiment statistical significance
Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Question:
Answer: [Yes]
Justification: Yes, report error bars in all experiments involving randomness. such as those with randomized query arrival orders, to capture the variability across runs and evaluate the statistical robustness of the results.
Guidelines:
The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results are accompanied by emor bars, confi- dence intervals, or statistical significance tests, least for the experiments that support the main claims of the paper.
17

---

The factors of variability that the error bars are capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, or overall run with given experimental conditions).
The method for calculating the error bars should be explained (closed form formula, call to a library function, bootstrap, etc.)
The assumptions made should be given (e.g.. Normally distributed errors).
It should be clear whether the error bar is the standard deviation or the standard error of the mean.
is OK to report 1-sigma error bars, but one should state it. The authors should preferably report a 2-sigma error bar than state that they have 96% CL, if the hypothesis of Normality of errors is not verified.
For asymmetric distributions, the authors should be careful not to show in tables or figures symmetric error bars that would yield results that out of range (e.g. negative error rates).
If error bars are reported in tables or plots, The authors should explain in the text how they were calculated and reference the corresponding figures or tables in the text.
8. Experiments compute resources
For each experiment, does the paper provide sufficient information on the com- puter resources (type of compute workers, memory, time execution) needed to reproduce the experiments?
Question:
Answer: [Yes]
Justification:
We provide the computer resources needed for all experiments in Section
Guidelines:
The answer NA means that the paper does not include experiments.
The paper should indicate the type of compute workers CPU GPU, internal cluster, or cloud provider, including relevant memory and storage.
The paper should provide the amount of compute required for each of the individual experimental runs as well estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported in the paper (e.g., preliminary failed experiments that didn't make into the paper).
9. Code of ethics
Question: Does the research conducted in the paper conform, in every respect, with the NeurlPS Code of Ethics
Answer:
[Yes]
Justification:
The research conforms with the NeurlPS Code of Ethics.
Guidelines:
The answer NA means that the authors have not reviewed the NeurIPS Code of Ethics.
If the authors answer No. they should explain the special circumstances that require deviation from the Code of Ethics.
The authors should make sure to preserve anonymity (e.g., there a special consid- eration due to laws regulations in their jurisdiction).
10. Broader impacts
Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer: [Yes]
Justification: Yes, the broader impacts of the work are discussed in Section
Guidelines:
The answer NA means that there no societal impact of the work performed.
If the authors answer NA or No, they should explain why their work has no societal impact why the paper does not address societal impact.
18

---

Examples of negative societal impacts include potential malicious unintended uses (e.g., disinformation, generating fake profiles, surveillance), faireess considerations (e.g., deployment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations.
The conference expects that many papers will be foundational research and not tied to particular applications, let alone deployments. However, if there is direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point out that generic algorithm for optimizing neural networks could enable people to train models that generate Deepfakes faster.
The authors should consider possible harms that could arise when the technology is being used intended and functioning correctly, harms that could arise when the technology is being used as intended but gives incorrect results, and harms following from (intentional unintentional) misuse of the technology.
If there are negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition to attacks, mechanisms for monitoring misuse, mechanisms monitor how system learns from feedback over time, improving the efficiency and accessibility of ML).
11. Safeguards
Does the paper deseribe safeguards that have been put in place for responsible release of data or models that have a high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?
Question:
Answer: [NA]
Justification: Our paper does not pose any such risks.
Guidelines:
The answer NA means that the paper poses no such risks.
Released models that have high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by requiring that users adhere to usage guidelines or restrictions to access the model or implementing safety filters.
Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images.
We recognize that providing effective safeguards is challenging, and many papers do not require this, but we encourage authors to take this into account and make best faith effort.
12. Licenses for existing assets
Are the creators or original owners of assets (e.g., code, data, models), used in the paper, properly credited and are the license and terms of use explicitly mentioned and properly respected?
Question:
Answer: [Yes]
Justification: All the existing models and datasets are appropriately cited.
Guidelines:
The answer NA means that the paper does not use existing assets.
The authors should cite the original paper that produced the code package dataset.
The authors should state which version of the asset used and, possible, include URL.
The name of the license (e.g., CC-BY 4.0) should be included for each asset.
For scraped data from a particular source (e.g., website). the copyright and terms of service of that source should be provided.
If assets are released, the license, copyright information, and terms of use in package should be provided. For popular datasets, paperswithcode com/ datasets has curated licenses for some datasets. Their licensing guide can help determine the license of dataset.
19

---

For existing datasets that are re-packaged, both the original license and the license of the derived asset (if has changed) should be provided.
this information is not available online, the authors are encouraged to reach out to the asset's s creators.
13. New assets
Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?
Answer: [Yes]
Justification: We introduce algorithm in the paper and provide its implementation along with detailed documentation to support reproducibility.
Guidelines:
The answer NA means that the paper does not release new assets.
Researchers should communicate the details of the dataset/code/moodl as part of their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent was obtained from people whose asset used.
At submission time, remember to anonymize your assets (if applicable). You can either create anonymized URL or include anonymized zip file.
14. Crowdsourcing and research with human subjects
Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given to participants and screenshots, if applicable, as well details about compensation (if any)?
Answer: [NA]
Justification:
The paper does not involve crowdsourcing nor research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Including this information in the supplemental material is fine, but if the main contribu- tion of the paper involves human subjects, then as much detail as possible should be included the main paper.
According to the NeurIPS Code Ethics, workers involved in data collection, curation, or other labor should be paid at least the minimum wage in the country of the data collector.
15. Institutional review board (IRB) approvals or equivalent for research with human subjects
Question: Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or an equivalent approval/review based on the requirements of your country or institution) were obtained?
Answer[[NA]
Justification:
The paper does not involve crowdsoureing nor research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Depending on the country in which research is conducted, IRB approval (or equivalent) may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper.
We recognize that the procedures for this may vary significantly between institutions and locations, and we expect authors to adhere the NeurIPS Code of Ethics and the guidelines for their institution.
20

---

For initial submissions, do not include any information that would break anonymity (if applicable), such as the institution conducting the review.
16. Declaration of LLM usage
Question: Does the paper describe the usage of LLMs if it is important, original, or non-standard component of the core methods this research? Note that the LLM is used only for writing, editing, formatting purposes and does not impact the core methodology, scientific rigorousness, or originality of the research, declaration is not required.
Answer: [NA]
Justification: This research does not involve LLMs any important, original, non- standard components.
Guidelines:
The answer NA means that the core method development in this research does not involve LLMs as any important, original, non non-standard components.
Please refer to LLM policy for what should or should not be described.
21

---

A
More Experiment Details
Table 2: Benchmark details for RouterBench, SPROUT, and Open LLM Leaderboard v2 in our experiments.
(a) RouterBench
(b) SPROUT
(c) Open LLM Leaderboard v2
Dataset
Size
Dataset
Size
Dataset
Size
MMLU 21
14042
MATH Lvl 1-5 22
9884
MMLU-PRO
12032
Hellaswag 63
10042
MMLU-PRO
11786
MUSR 51
756
GSM8K g
7450
GPQA
45
541
MATH Lvl 1-5
1324
ARC Challenge
1470
MUSR
748
GPQA
45
1192
Winogrande 46
1267
RAGBench
18
1827
BBH
53
5761
MBPP 3
427
Openhermes 2.5 54
19455
Total
21065
MT- 65
80
Total
44241
Chinese
785
Consensus Summary
362
Bias Detection
285
Test Match
3
Accounting Audit
30
Abstract2tille
254
Total
36497
Benchmarks. We evaluate our method on three benchmarks: RouterBench (zero-shot version) 23 SPROUT (50), and Open LLM Leaderboard v2 (16). All three benchmarks constructed from multiple dataset sources. Table summarizes the query types in each benchmark, while Table details the LLMs used and their corresponding token costs.
For RouterBench, we identify 13 different data sources in a total 36497 samples - more than those reported in the original paper spanning diverse range of query domains. This benchmark includes 11 different L.LMs. Since does not provide predefined train/test split, we randomly sample 10000 queries as the test query set and treat the remaining queries as historical data. Note that we do not report per-token costs for models in RouterBench, as [23] does not provide this information. Instead, the benchmark includes precomputed costs for each query across all 11 LLMs, which directly use in our experiments.
For SPROUT, it consists of queries from 6 different datasets, covering different query domains, such as math and RAG. contains a total of 44241 samples across 13 LLMs. We use the provided training set as the historical dataset, and combine the validation and test sets to construct the test query set.
For Open LLM Leaderboard v2, we follow the same setup and data processing as [50,, resulting in 21065 samples. The processed benchmark includes different datasets, with each evaluating different aspects of LLM capabilities. This benchmark uses 18 different LLMs, and we randomly sample 10000 queries as the test set and use the remainder as the historical data. Since most evaluations in Open LLM Leaderboard are likelihood- based, the cost essentially determined by the length of the input. Following (50), we report the cost per input token in Table and compute the total cost of each query based on input token counts.
In the main setting, the queries are embedded using sideration, we additionally evaluate with two different embedding models: SFR- Embedding-e2--.. 40) and gte-Quen2-t 1. 1B-instruct. B5
en-v1.5 [59]. For the diversity con-
Baselines. We compare 8 different routing algorithms, categorized into two categories: model-based methods and training- free methods.
For Model-based methods, we follow the training approach in 50 and train two separate Roberta- based models (36] predict the performance and cost of each query. The performance prediction model is classification-bait based, aiming to select the optimal LLM with the highest expected perfor-
22

---

Table 3: Model lists and token costs (S/1M tokens) for RouterBench(left), SPROUT (middle), and
Open LLM Leaderboard v2 (right).
(a) RouterBench
(b) SPROUT
(c) Open LLM Leaderboard v2
Models
Models
Input Cost
Output Cost
Models
Cost
WizardLM M1zaddLM-13B-V12
claude-3- 3-5-sonnet-v1
3.00
15.00
-ikttal-8x7B-DPO
clande-instant-vl
mhan-text-premiest
0.50
1.50
Vi-34B-Chal
0.8
clando-vi
openai-gpt-44
2.50
10.00
QwQ-32R-PPess Preview
1.2
claude-v2
spenal-gat-fo-minn
0.15
0.60
Qwen2-72B-Inssnee
gpt-3.5-turb--1 106
1oanite---2b-inttmnn
0.10
0.10
Qwen2.5-776 Insttt
0.3
granite---Sb-instruct
0.20
0.20
Qwen2.5-72B-Bl 5122--nssttt
code- wallllla-nnnnaaat 34h
laam- 3-mmm-3-1-300 1-10-----700
0.90
0.90
WizardT M-2-8x22B
1.2
Ilaaa 2-70b-hht
Ilama-3- 1omma-3-1-Bh-imee 1-8hiinstrect
0.20
0.20
0.9
mistral-7b-chat
Mama--32--b-innstrue
0.06
gemma-2-277b-tt
mixtral-8 Hinxtal-8x7h-chhe 8x7h-chat
Ilama-332 3---3---22hhit
0.06
0.06
gemmm-2-9h-ir
0.1
Yi-34B-Chat
Jamma-333-70binsttuu
0.90
0.90
gemma-2b-it
0.1
mixttal--k.7--instruut
0.60
0.60
Llama-2-13b
Ilama hama-3-405h instruct
3.50
3.50
Meta-1 Meta-Ilamm-3. 1amm-3.1-700
0.9
Biitral-7--Inttuut---
0.2
Mistral-7B ---nttrrctt-t-...
0.2
Mixtral-&77B- I0-..tttrtt
0.6
TJama-3 I-Nematron 70R
mance, while the cost prediction model is regression- based and estimates the expected cost of an incoming query. This results in 2 different baselines:
Roberta--erf-routingg routes each query to the model with the highest predicted perfor-
mance;
Roberta-cost-routing routes each query to the model with the greatest available budget.
Training-free methods include 6 baselines:
Random routing, randomly selects a model for each query;
Greeedy-per--outting. uses ANNS to select the model with the highest predicted perfor-
mance;
Greedyy-cost-routingg uses ANNS to select the model with the most available budget;
KNN-perf-routing
23 uses KNN select the model with the highest performance;
KNN-cost-routing 23 uses KNN to select the model with the most available budget;
BatchSplit routing, groups incoming queries into small batches and solves the linear programming (LP) per batch to determine routing.
Note that in the online setting, the true remaining budget of each model is not directly observable during the routing process, as it depends the actual cost incurred after the query response is generated. Therefore, all cost-based methods and BatchSplit rely on predicted costs, which are obtained from predictive models, ANNS, KNN, to estimate the remaining available budget and make routing decisions.
We adopt HNSW (38) the main ANNS algorithm and set the number of candidate neighbors ([Ry)) to 5 for both ANNS and KNN. To assess the robustness of our algorithm under varying candidate set sizes, we further vary this number to 3, 7, and 10. However, many alternative methods, such as DiskANN 25), are interchangeable here, as listed in lattps://ant hann-benchmarks com For BatchSplit, we use mini-batch size of 256 to balance LP computation cost with the low-latency requirements of the practical online routing.
Metrics. In our experiments, we consider three key evaluation metries: (1) Performance, the overall performance score achieved by processing all test queries under the given budget constraints; (2) Performance per Cost, the ratio of total performance to the corresponding cost, reflecting overall
23

---

Table 4: Average cost and performance of models in RouterBench on historical data.
Model
Cost
Perf
Perf/Cost
(Perf/Cost)
7.27e-05
0,432
5944
77.10
claude-instant-vl
2.32e-04
0.598
2581
50.80
claude-v1
2.14e-03
0.631
295
17.18
claude-v2
2.41c-03
0.636
264
16.24
gpt-3.5-turbo-1166
2.42e-04
0.617
2546
50.45
gp1-4-1106-preview
3.28e-03
0.781
15.43
lode-llama-instruet--e
1.71e-04
0.203
1182
34.38
lama-2-70b-chat
2.02c-04
0.328
1627
40.34
mistral-7b-chat
4.56e-05
0.308
6768
82.27
mixtral-&x7b-chat
1.34e-04
0.550
4098
64.01
Yi-34B-Chir
1.85e-04
0.648
3503
59.19
Table 5: Average cost and performance of models in SPROUT on historical data.
Model
Cost
Perf
Perf/Cost
(Perf/Cost)"
claude-3-5ssonne-vv
7.65c-03
0.827
108
10.39
titan-text-rremirr-ll
5.64c-04
0.579
1027
32.04
openai-gpt-4o
4.92e-03
0.846
172
13.11
openai-gpt-4o-minl
3.40c-04
0.808
2378
48.76
granite-3-2b6
-ranite--2b-instruuet
8.54c-05
0.553
6473
80.46
gramite3-Sh-innttuet
1.50c-04
0.659
4403
66.36
llama-3-1-70-instrree
7.17e-04
0.810
1130
33.62
2.43e-04
0.690
2838
53.27
1---instret
6.67c-05
0.460
6904
83.09
6.47e-05
0.629
9722
98.60
-ama--3--70b-insttuuct
5.52e-04
0.804
1457
38.17
1ama-3-40Sb-insteee
2.01e-03
0.776
19.63
mixtral-8x7b-insttu
3.74c-04
0.616
1648
40.59
cost efficiency; (3) Throughpus, the total number queries successfully processed, indicating the processing capacity. We evaluate Throughput a key metric because goal is to design effective online routing algorithm for high-volume settings with limited token budgets. available budget may not suffice to serve all incoming queries within a given time unit. Therefore, Throughput reflects how efficiently an algorithm utilizes the available budget to maximize the number of queries successfully served during that current time unit.
these scenarios, the
Budget. Our algorithm aims to improve routing performance under limited budgets in high-volume settings. To simulate this high-volume, budget-constrained setting, we define the total budget based on the minimal cost required for a single model to process all test queries in the benchmark. In the main setting, the budget set to this minimal value. To evaluate the robustness of our algorithms, scale the budget by a factor ranging from 0.25 to 2.
We consider multiple strategies for splitting the total budget across models. In the main setting, we adopt cost-efficiency-berre based split strategy. As shown in Table 4 and 6 we report the average performance score, cost, and cost efficiency (Perf/Cost) of each model on the historical data across 3 benchmarks. observe a substantial disparity cost efficiency across models. For instance, for SPROUT, the most efficient model achieves cost efficiency of 9722, while the least efficient only reaches 108, nearly 100x difference. Directly allocating the budget based on cost efficiency is thus highly imbalanced, as it can result in nearly all resources being allocated to single model.

---

Table Average cost and performance of models in Open LLM Leaderboard v2 on historical data.
Model
Cost
Perf
Perf/Cost
(Perf/Cost))
Yi-34B-Chat
6.57e-04
0.428
652
25.53
Mixtral-&x7B-DPO
4.78e-04
0.401
839
28.97
QwQ-32B 12B-Preview
8.90e-04
0.552
621
24.91
Owen2-72B-Instmua
6.67c-04
0.562
842
29.02
Owen2.5-72B-Instnun
8.90c-04
0.561
630
25.10
Qwen2.5-7B-Inttrue
2.22e-04
0.420
1887
43.44
WizardL
9,85e-04
0.491
499
22.34
deepscck-llm-67bbee
7.05c-04
0.413
586
24.21
gemma-2-27b-it
6.13e-04
0.462
753
27.43
gemma-2-9b-it
2.30e-04
0.419
1826
42.72
gemma-2be
7,66e-05
0.191
2489
49.89
Llama-2-13b
2.
0.227
919
30,31
Meta-Llama-3.1-001
6.44e-04
0.548
852
29.18
Distral-BB-nsstruck
1.43e-04
0.258
1806
42.50
Mistral-7BB 1B-In--tuttt-tt0..
1.64e-04
0.311
1894
43.52
1istral-7B-
1.64c-04
0.336
2044
45.21
Mixtral-xx7B-hnssmuu--00..
4.92e-04
0.379
770
27.74
7.39e-04
0.506
686
26.19
Therefore, we adopt smoothed version that allocates the budget proportionally to the square root of each model's cost efficiency on the historical data, i.c., according PERE (PPRE-O.5. j0.5
In our robustness evaluations, we explore several alternative budget splitting strategies, including uniform split, random split, extreme split, cost-based split, and performance- based split. In the cost-base fost-based split, the budget allocated inversely proportional to the average cost. However, due to the extreme cost imbalance across models (as also observed in the cost-efficiency-basee split), also adopt a smoothed variant that splits the budget proportional to (CosT) )..5 In the performance-base split, the budget is directly assigned in proportion the average performance scores of the models. In the random split, the total budget is randomly allocated across LLMs, and the experiment is repeated 100 times account for variability. In the extreme split, 80% of the budget is assigned to the h least cost-efficient models, and the remaining 20% is uniformly distributed among the others, where ranges from 5.
Optimization Implementation. We implement all optimization codes using the CVXPY 12
package. For the one-timg teeetime optimization step in algorithm, use the L-BFGS-B solver [66]. For BatchSplit, which involves solving a linear program for each batch, we adopt the HIGHS solver [24]
Devices. All experiments are conducted machine equipped with 16 CPUs and 32GB of memory. For training the Roberta models used in the model-based baselines, we use two NVIDIA H200 GPUs.
B Theoretical Proofs
Definition 1 (e-Net [II.. Given parameter >> 0 and routing rule xx7),, a set & C [0, 1I is an e-net if, for any 7 E [0, 1JM there exists 7 E & such that V i,J, (1)(()) x.i S E.
B.1 Discussion on Our Theoretical Assumptions
We introduce several mild assumptions in our theoretical analysis and provide justifications for each below.
Random arrival order. We assume that the queries arrive in random order, i.e., they can be picked adversarially, but their order is randomly permuted. Note that this is weaker requirement
25

---

than assuming the queries are sampled i..d. from an unknown distribution. This is because if the queries are sampled i..d., then they also satisfy the random order requirement, and thus our assumption is weaker. Furthermore, the random order model is also a popular assumption in many other online algorithms [39[1] since typically allows one to go beyond worst-case hardness and obtain meaningful theoretical guarantees. In practice, we perform robustness studies by changing the query order and observe that our algorithm still outperforms baselines; see Section 4.1
"Copt is enough large" is practial. In Theorem we assume that Copt 2 A0 logí ( which c=11+)
Sman
is naturally aligned with high-volume practical settings. This is because Copt depends on the total number of queries IQ), whereas our lower bound assumption scales as a function of M, the number of LLMs. Typically, M can be thought of as a constant while [Q), the total number of queries, should grow over time. Indeed, in all of our benchmarks, we observed that for every query j. the optimal solution zi (that is, the performance score achieved by the optimal solution on query j) satisfies Eielar di 20.462 consistently on Open LLM Leaderboard v2, 0.639 on RouterBench, and 0.887 on SPROUT, meaning that in practice, Copt scales (QQ) (linear in Q). On the other hand, for constant and a (e.g. we use a = 0.0001, e = 0,025 in our main setting), our required lower bound is a polynomial of M (more specifically, it is close in M but it is inside a logarithm). However, we think of M as a constant. For example, M < 18 in all of our experiments. Even if M is large, it is reasonable to assume that it is orders of magnitude smaller than |Q] (in our experiments, Q is on the order of thousands to tens of thousands, and in real-world systems, can be much larger).
quadratic since + may depend exponentially
Our assumption is further corroborated by the relaxation used in Section 2.1 where if Copt is Smae sufficiently large, the original MILP can be closely approximated by its fractional LP relaxation with only a negligible optimality gap. We validate this in our main experiments over three benchmarks with the observed optimality gaps being: (i) 0.016% on SPROUT, (ii) 0.086% on NouterBench, and (iii) 0.3% on Open LLM Leaderboard v2.
Lastly, we remark that similar reasonable lower-bound assumptions have been made in prior work on the online matching problem [19 [1 39], where it is commonly assumed that bids for the items small compared to the total budget.
"Estimating query features via similarity"' is natural. The core intuition behind most previous
literature on predictive LLM routing (23 43 (66] 50 [2], which trains a model-based predictor on
auxiliary datasets to estimate performance and cost of future queries, aligns with Assumption [
Specifically, these approaches assume that similar queries share similar routing-relevan features. If no such relationship cxists, then historical data would be uninformative, and it would be impossible to leverage historical data for effective future routing. In this case, no meaningful inference can be made without directly querying the LLMs, and routing decisions degenerate to random selection.
One may argue that useful routing information can still be obtained by querying only a subset of LLMs. This idea is echoed in works that adopt cascading strategies. where LLMs are queried sequentially based on their observed capabilities on historical data 2 5.. However, these approaches also fundamentally rely on related assumption: LLMs that perform well on historical data or benchmarks are likely to perform well on future queries. Furthermore, these methods introduce significant latency and computational overhead, they may consume substantial token budgets before reaching the optimal LLM. This makes them impractical for high-volume online routing scenarios with tight token budgets and low-latency requirements.
If no useful routing information can be inferred from historical data, no matter whether it is related to model capability or query features, then the system would need to query all LLMs to make informed routing decisions. This is because in the worst case, under an adversary query targeting the LLM query order in the system, all LLMs may present extremely low performance, except the last LLM. In this situation, no strategy can be adopted to improve overall routing performance without assessing all LLMss Therefore, it is important and natural to establish our assumption or use related notion, e.g., Assumption | that links historical information with future queries to obtain meaningful routing information and improve routing performance.
26

---

B.2 Proof of Lemma 2
Lemma 2. Suppose that Vj E Q. and Vj E Rg, we have [[EMB(j) EMB( - 7, and
that Assumption holds. Then, the offtine approximate optimum Copt satisfies
Cope- Copt - 0(8).
Copt
Proof. Let denote the optimal solution to Cont. and 22 the optimal solution to Cope.
Case 1: Copt 2 Copt. We have
Capt - Capt
Σj Di des Ej diy
Copt
Dj E; dis
Σ j Ej dijItss
(dis dig 2015
Σ, E.( |R,1 EyER, dik- dis)z1
Σ, Σ daj
Ej E; disaress
01))
Σ3 E3 dis
S 0())
where the second inequality follows from the fact that Ej E, dijinng S EE, E, is the optimal solution to Copt. and the fourth inequality follows Assumption 1
disrai when 12ij
Case 2: Copt < Copt. We have
Capt - Capt Copt
Ej E, de 22 - -E, E, diszies
Ej Ee disatio
Ej (des - dig 2225
E, Σ, dejsIis
Σj E. म&. Enen, dik- diy)a22s
Σ, Σ, dis
Σ3 E3 dis dis
(6)
Σ, >, des
0())
where the second inequality uses the fact that E3 >, disze < E, E, dijai when æiay is the optimal solution to Copt, and the fourth inequality follows Assumption I and the final inequality follows E3 Ex disr2ij E3 Ex dejsrig.
B.3
Proof of Lemma 3
Lemma 3. Let Tb be an c-net and assume that
Copt
aM log M (M/1)/
2 2
Smar
(1
ff (C,(P) - -cC,l S 2i, then
x E= (0
27

---

Proof. Inspired by the techniques used in [I] 39 19.. we first prove that, under the given setting, the partial performance score can be accurately estimated with high probability. Specifically, for each i [M] and y E Φb we evaluate the following probability
Pr([Ct(P) - -Oi 2))
Observe that, for any j E P. the variance satisfies VAR[ad (p - (o) 11::1.. which implies
EjEr VARlad o (+ < e|| By applying Bernstein's 's inequality, we obtain
22/2 <|IC:11B + 3 088ma
Pr([C:(P) eC,l z.) S 2 exp
We aim to find such 2j that this probability is below a given tolerance r. Set RHS as T and solve for 24, we obtain
dy log 2 Fasmas
v ( log 2 aas + Se 8elog 1|C
3 log asaa + 2e 2o 2 11C.113
2
2/-
2
Without affecting the analysis, we define 2, = log 2 mas +
2e 2elog = 11|č for simplicity.
Set r = </(M ), and use Copt 2 Q (1[+d)
lo)))) ) we have
Σ 2
2 log 018maz + Σ v 2c log - 111:111
2
3
O(Mlog (88ma)) + Σ V 12 2Cismax
2
$ opp (1+ + 2Mc 2 Cssmax
C(e (1 +0) + + 8)) Ca
/oon
so (0 (1
This completes the proof.
B.4 Proof of Lemma 4
Lemma 4. Vi, it holds that Ejer "15tig(7") - E Ejggen S Ozz), then there exists
control parameter >> O, such that Vi, (1) (I)(C((P) - -cC; S and (2) (C;(P) eEil S Ozz)).
Proof. Define Mj Egeddgay(7)) - d) dx and H; Ejedd (1"")(")))))))))))))))))))) ΣS ()"):s(""). Then, we aim to ensure the following two conditions hold: (1) alMi 2i. and (2) a H,| S (zz).
If M, = 0, condition (1) holds trivially for any a > 0; similarly, if H, = O, condition (2) also holds for any 0.
Now consider the case where M, * then it requires that a S | and when H, * we need to (1z)) Let the set of indice for which H; + 0 or M, + O. For each E 1, we have
have a < H.
if M, + 0
O(zz)
if H, #
V11
M.
V1.2
[H.
x
if M, =0
x
Hf 0
Let V == Vi V and set
a = :==nn in
EE1
Since V; > for all E T, it follows that a > 0. Therefore, we find control parameter a > 0 such that both conditions (1) and (2) are satisfied.
D
28

---

B.5 Proof of Lemma 5
Lemma 5. Let & be an e-net. If Copt
22( aM Mo then Cest 2 (1 O(c)) aaa
Smeus
(11+6)
Proof. We first prove that V i, holds that max Ci F((())) Cest, S O(as) where
F((r') 7, B, + I(ade) - )
From Equation 5 it follows immediately that E, - F(7)). Case 1: 7 > 0. In this case,
=
max (nx
+4 Cest.i Ca - - min(E,, C.}
which follows Cest,i = min( CiJ. We consider two sub-cases separately; Sub-case 1.1: Σ, 915 < Bz.
Then,
[ [((7)) -eet, 7 (B, - (( S B, Enns
Due complementary slackness conditions over observed queries P, we have Σjer ((jio())))?"") cB,. Thus, it follows that
Σo - < c|B. )))))((")) ((=)
= maxf(C, F((")) Cesti S 0(2))
Sub-case 1.2: Σ, (1*)) B₁.
We obtain,
max Ci R(())) Cest, = -G- Es From Lemma 4 it can be expanded and bounded as:
Ō E, = Σ (od))a((("")EEE) -cEi) S O(zi)
(,, Cest. < 0(zi)
Case 2: 7 = 0. Then,
max Maxx(C,, ((,")) - Cests = =Ū; - min ( (C, E.}
When E, (r(") < B, this difference Ō - min(C; E.}- 0. Thus, we only consider the B,, leading to
situation E, Degetiy (x*)
max C. [(T")) Cest, = = min( E.} < G. E. O(z)
which follows Lemma 4
Lower Bound CY)) From Lemma and Lemma 4 we have,
(Y)
- min(C;:Ó,(PP) E, - Σ a (7*)}
JEP
2 min((1-
- c) - 2; (1 E) - 0(z))
2 (1 -c)Cestt 0(z;)
29

---

where second inequality follows that - (1 (11-)))
- 2; and IC, E, - Olsd.
Summing over all get Cest (V) 2 (1 61=s Σ: (2z)). Due the fact that Σ, 21 S
o 2 @eV(L+ (1
finally obtain
Cest () 2 (1 - -c)sss- - (1+)
Cest (V) 2 (1 O(s))Costt
This completes the proof.
B.6 Proof of Theorem
Theorem 1. For any given query set Q with random arrival order, Algorithm satisfies Copt
Cate
Oe + 6) assuming Capt 2 S2( 2 logí ( where Smaz is the maximun performance score obtained for any query, and & is 6-net defined over all possible routing strategies x(7).
(1+6)
Proof. Case 7" 4. According to Lemma and have union bound over T. This union bound
V V(1+ 5)C O) holds. Therefore, implics that with probability greater than 1 1- e, E 2s S SOee we have that
Σ 24 = max max Cest So 10 (1/11 8)0opt (11)))CCa
max F())) Cest
When (1 + 8)C 2 C/a, we have maxt max(C;F(x")) - Cest S O(E(1 + 8))oo)))Coot).
By weak dualtiy, we have Cest I aCoopt S F(7"). Also, we have Copi (6)] (from Lemmale 2 Therefore, we obtain that a(1 O(8))Copt Cest S O(e(1= o)p) = Cest/O 2 ( Cpp
Cope E [1 - 0 1+
When (1 + 5)popt < C/a by the same weak dualtiy, we have & - a(1 + O(p) S 1+0(8) OcC//a), which further implies that ò < OT-O(e)aa Copt- Therefore, have a(1
8)pppt Cest S O(eE)) Cast/a (1 60))Copp
We can define Catg == E, min E,dddusysss dy)xa((")) where T. = Σ E(jjs((()")) with t = argmax Σj ") s.t. Σj Ejgoo $ By.
Furthermore, we have Cast/a = Ex mint Es/a, E, dy) where Ei/ax = Σ3 desars((**) with = argmax Σ (.. s.t. Σÿ (1)"),(())) < B.
Let 1o be the largest / such that Σÿ (7*) S B,. According Assumption for each i E [M].
we have
:
- 0()) Σ ( < Σ =0mm()))=((0000) Σ ()
Therefore, we have
(B0 B
Let ko be the largest à such that Σx 91 (1*) S B Without loss of generalizability. assume
t 2 kj. Then, there exists set of tail queries, A,, which makes Equation (7) exceed B, by at most
30

---

B, Then, we define excess performance contributed by these tail queries as ΣJEA, diszis(?)). Because the query order is random, we consider the expected excess performance
B, E B.
E
Σ
JEAL
and the variance satisfies VAR VAR ())),((())) - (( Using Bernstein's 's inequality, we have
e Pr( Σ - a.) 2 (T0 jEA
3 Smaz
Follow Lemma 3 set RHS as c/(M]l)) use
Cape 2 22 o (og(MM and union bound for all ?*
Smax
(11+6)
and i, then with probability greater than 1 -,
Eeson [ (V0L
where we denote E = =; Ex. Based on this, we have
c ΣΣ de)))s())) - Σ :
ΣT. T: Σ Es/a <
Σ dxs))s(7"))
(1 + 066) Σ d ->>->>>> d
$
s 0 Σ F.ya (1++0(0)) Σ Σ d jEA,
$ 0 Σ + (1+000000++) + Ecs)
$ (0(0) +0 (000++((11) (
Σ Es/a
s (0(6) +0 (Vo(L+0)010/1
6)a)) Σ Es/a
$ (0(8) + 22/2 (20)) 8/ (5/aa
Σ Es/a
where the penultimate inequality follows Eja 2 Cest/a 2 (1 O1e + 6))
Finally, it leads to |Catg - Cest/al < (0(6) + 0 63/2 vota) Cast/ox Because Ceat/a >
(1-O(E + o0)C we obtain that Catz 2 1 1 6).
Copt
Case >x" & t. As is a e-net, there exists an 7 such that V i.j, (m1s("")-24p)) - S c. Therefore, we obtain
|C(("", ()-<C((7"")
-C P)]+ +)(+)()((+)))+)))))))()))))+)))) <(((7")
$ (((t
$ +x(00(((17))
31

---

Similarly, for each i, we have
Σ
Σ -(()))))((00)))))))))))
jEa.
jEA,
+1
Σ de)a;(())) - Σ dxja,(("")
SEA.
JEAL
+ 10(8) -(0)))))))))))))))
$ < + Σ
JEA.
c O(c)B((t*)/o)
where, with slight abuse of notation, we use Ex(r") to denote the value computed under y and Eyyr) under y/
By summing over all and following Lemma as well the proof in case 7" v. we obtain Cest/a 2 (1 11-0( O(e + 6)) and [Calg Cest/al - (0(0) o 3/2 v8/a Cest/a.
Cupt Therefore, Algorithm satisfies that Cata 1 0(c+).
C
Additional Experimental Results
hatormace
1000
2000
20000
Pefformacc
4000
5000
Paforans
LOO0
2000
100
1000
Sarvio
Broad har
KMN heet
Coye
Acbeet Cars
KAN Coul
Rabott her Noverta
coe Sandio
Greer Cral
MbN Cai
fasserte Chal
Coeady, KMN
Figure 7: Results under the worst-case query order, where queries are sorted in descending order of cost. (Left to right): the first three subfigures correspond to RouterBench, the next three to SPROUT, and the last three Open LLM Leaderboard v2.
C.1 Query Arrival Order
We evaluate the robustness our algorithm under varying query arrival orders. Specifically, we consider two settings: (1) randomized setting, where test queries are independently shuffled 100 times to reflect realistic, unpredictable online environments; and (2) a worst-case setting, where queries are sorted in descending order of their maximum cost across all models. This adversarial order simulates scenarios in which expensive queries arrive early and are more likely to exhaust the budget. Figure shows that our algorithm consistently outperforms all baselines across metries and benchmarks under random permutations. Even under the worst-case order (Figure ()) our method maintains the advantage, achieving the best performance across all metrics on SPROUT and Open LLM Leaderboard v2, and outperforming all baselines in terms of performance and cost-efficiency on RouterBench. These results demonstrate the robustness of our algorithm towards varying query orders.
32

---

Gweddy
Gredy
5000
Performanee
4000
5000
Thiuughpu
3000
4000
6000
2000
3000
4000
1000
2000
2000
8000
10000
Perfomance
6000
6000
88000
4000
4000
0000
2000
4000
2000
5000
10000
2000
Perfommece
4000
Performance per
2000
1500
0000
2000
1000
4000
1000
2000
500
10
10
14
10
LLMb
Deployed
Figure 8: Results when varying the configurations of deployed L.Mss. Rows correspond different datasets: RouterBench (top), SPROUT (middle), and Open LLM Leaderboard v2 (bottom).
Groody
BozchSpit
-+-
1200
1000
Neformonce per Cost
2000
Perfomaance
800
2000
Througheut
1500
600
1.000
1000
Perfommince par Cost
2500
Weffrranee
1250
1500
Thrmughput
1.000
750
1000
1000
500
500
20000
1000
per CAnt
2600
Performence
hroughhut
1500
1200
1000
1000
200
600
Least Cost Effective LLMs with 80% Budget
Least Cfst-Cffective LLMS with 80% Budget
hlasatt Dfftcivfective LLMs with 80% Dudget
Figure Results under the extreme budget split. Rows correspond different datasets: RouterBench (top), SPROUT (middle), and Open L.M Leaderboard v2 (bottom).
C.2 Scalability to LLM Deployments.
One of the key advantages of our algorithm is its scalability to varying configurations of LLM deployments. To evaluate the robustness of our algorithm, we vary the configurations of deployed LLMs on each benchmark. For RouterBench, which includes 11 distinct LLMs in total, vary the
33

---

Gready
Greedy
Cost
Ieformante
5000
Thrnughpur
2000
4000
4000
3000
1000
2000
8000
12500
Weffomance
Throughou
10000
Perfommance
4000
5000
2000
2500
2500
2000
5000
Performace
1500
2000
Throughhei ughhen
4000
1000
500
1000
1000
0.25 0.75 1.25 1.75 2.00 Budget Excest the cheapest modell
0.25
1.25 1,50 1.75 2,00 Budget (#cost of cheapest model
0.25 0.50 1.00 1.50 2.00
Budget (xcest ches modell
Figure Results when varying total budget B from 0.25 to 2x the cost the cheapest model. Rows correspond to different datasets: RouterBench (top), SPROUT (middle), and Open LLM Leaderboard v2 (bottom).
deployed LLMs from to 8. For SPROUT, which has 13 different LLMs, we vary the deployed LLMs from 10. For Open LLM Leaderboard v2, which includes 18 distinct models, vary the number of deployed LLMs from 2 to 16. In all settings where the number deployed LLMs is fewer than the maximum, times to ensure diversity and coverage possible configurations. Note that in this experiment, we compare only against training-free methods, retraining models used in model-based methods for each of the numerous settings would incur significant computational and deployment overhead. As shown in Figure & our algorithm consistently achieves strong performance across all deployment configurations, where the cost-efficiency gap over other baselines steadily increases. These results demonstrate the robustness and adaptability of our method diverse and dynamic LLM serving environments.
randomly sample the deployed LLMss and repeat the experiment 10
C.3
Budget Split
One key factor affecting the performance of routing algorithms is the choice of budget split strategy. We extend the default cost-efficiency-buseee split five alternative strategies. As shown in Figure 4 our algorithm consistently outperforms all baselines across all benchmarks and metrics under four different split strategies: cost-based, performance-bastt extreme split setting (Figure 9. where large portion of the budget is concentrated on few low- efficiency models, our method maintains leading performance. Notably, when 80% of the budget allocated to single model (h 1), our algorithm achieves nearly 2x the performance of the strongest baseline (BatchSplit) on RouterBench. On Open LLM Leaderboard v2, it also demonstrates approximately 2 higher cost efficiency than all baselines. These results underscore the strong robustness and adaptability of our algorithm against a wide range complex and imbalanced budget allocation schemes.
uniform, and random. Even under the
C.4 Total Budget
To evaluate the performance of our algorithms in different budget settings, we scale the total budget B from 0.25 the cost of the cheapest model. Results shown in Figure [o demoonsree that our algorithm achieves competitive superior performance compared to all basclines across benchmarks
34

---

Greedy
6000
2500
neformance
2000
Perforaance per
5000
Thooughou
4000
2000
1500
2000
1000
5000
10000
15000
20000
25000
5000
10000
15000
20000
25000
5000
10000
15000
20000
25000
4000
5000
Peformance
per
Thruuhhus
0000
4000
4000
2000
1000
2000
10000
25000
20000
10000
25000
1400
2000
Irffommnce
1200
1800
Turouphout
1000
2000
1600
2500
800
1400
2000
1200
1500
Auxiliary Points
Auxiliary
Figure 11: Results when varying the number of historical data points. Rows correspond to different datasets: RouterBench (top), SPROUT (middle), and Open LLM Leaderboard v2 (bottom).
and metrics. Notably, under the extremely constrained budget, it maintains clear advantage. For instance, at B 0.25, it achieves nearly 2x the performance and cost efficiency of the strongest baseline (BatchSplit) on the Open LLM Leaderboard v2. These results underscore the robustness of our method and its adaptability to different resource availability scenarios.
Table 7:
Per-query routing latency (ms) of different algorithms on RouterBench under varying numbers of queries.
Algorithm
4000 queries
6000 queries
8000 queries
10000 queries
Greedy-Perf
0.203
0.203
0.201
0.203
Greedy-Cost
0.233
0.230
0.226
0.233
KNN-Perf
0.478
0.475
0.469
0.475
KNN-Cost
0.300
0,282
0,281
0,278
BatchSplit
0,300
0.282
0.281
0.278
Ours
0.060
0.060
0.060
0.064
C.5
Routing Overhead & Quality of Historical Data
Routing Overhead. We evaluate the routing latency of Algorithm [nder varying query volumes. We compare Algorithm [ with training-fire free routing baselines, focusing on the core online routing stage that follows the embedding step. This focus is motivated by two key reasons: (1) The embedding step can operate asynchronously and is fully decoupled from the core routing logic, where its outputs are shareable across retrieval, logging. and other downstream tasks. (2) The embedding model is interchangeable (e.g., MiniLM, GTE-small, bge-small), while our core contribution lies in the core routing algorithm itself. As shown Table our method incurs negligible decision overhead compared to existing training-free baselines. Even under high query volume (10,000 queries), it introduces only 0.064ms routing latency per query and consistently achieves the lowest decision overhead (except the random routing strategy, which exhibits significantly worse performance).
35

---

Greedy
Gready
2500
Nefformance par Cost
5000
Performancc
2000
Thruughput
4000
1500
5,00
1.000
2000
500
1000
6.000
Derformnnce par Cost
4000
Pefforance
Throughput
5000
4000
4000
2000
3000
2000
1000
2000
2250
1500
Cost
2000
Performatce
1250
1750
3000
1000
Throughpps
2500
2000
1250
500
1000
750
10
ANNNNNN Candidates
ANNUKNN Candidates
ANNKNNN Candidates
Figure 12: Results when varying the number of search candidates. Rows correspond to different
datasets: RouterBench (top), SPROUT (middle), and Open LLM Leaderboard v2 (bottom).
2000
4000
Puflmann
4000
5000
5000
2500-
2000
2030
2500
1000
2000
1.00
Tiraa TER
2000
Perto mireeeee
10D0
1030
5000
Fertomeres
5000
Fimughtt
Peffomuact
2000
Inoughost
2200
Bundm
KM Ben
KNN Cap
apsert por mnternal
Rundom
Gieedy Coa
JON Eos
fiderma Coe
Rundom
Creery par
KB Pur
83tti30 Rnterms Coe "urs
Cheedy Be-1
K0N Non
For
Wocerte Poll
Duun
Runsam
Onedy Sap
FWN Cop
battliek
mncerte Ruberna Cort
0ro0y
appertty
Grady
Greettye
Figure 13: Results using different embedding models. Each group of 9 subfigures corresponds to one embedding: (a) D0wen-11.BB-ing
(subfigures 1-9), (b) 2 R (subfigures 10-18). Within each group, the first three subligures correspond to RouterBench, the next three to SPROUT, and the last three to Open LLM Leaderboard v2.
Quality of Historical Data. To assess robustness to data quality, we consider noisy setting with label perturbations and an out-of-distribution (OOD) setting with distribution shift. In the noisy setting, we introduce two types of strong noise simultaneously to the data label. For each performance label d'j, we randomly flip its value with probability of 20%. For each cost label gij. we apply multiplicative, mean-preserving noise consisting of: (i) log-normal jitter (logA\(0, o²) f with 0.25, and (ii) spike factor of 3.0 applied with 2% probability. In the OOD setting, we construct a distribution shift using RouterBench, which contains 13 diverse datasets. Specifically, we use MMLU as the historical dataset and evaluate on the remaining 12 datasets, which differ significantly in data distribution. Results in Table g show that our algorithm consistently outperforms all baselines under both noisy label and OOD settings. It achieves the highest overall performance, ratio, and the greatest throughput in both settings, demonstrating strong robustness to label noise and distribution shift.
the best performance-per-eeeee
36

---

Performncc per Cort
Perfomance
2000
Throughput
4000
5000
1000
2000
1000
10
10
10
10
10
10
10
10
10
10
10
10
10
10
5000
Perormance par Cast
0000
8000
Perforaace
4000
Throughout
6000
2000
4000
2000
2000
1000
2000
10-4
10-2
Perfomence per Cost
2500
Neffrrmnne
2000
Phroughuu
1000
1500
2000
1000
500
1000
10
10
10
0
10a
Alpha @Epsiton)
Alpha (Epsion)
Alpha (Epsilon)
Figure 14: Results when varying a and e. Rows correspond different datasets: RouterBench (top),
SPROUT (middle), and Open LLM Leaderboard v2 (bottom).
Routing performance on RouterBench under two challenging historical conditions: noisy data label and Performance per Cost, and Tput represents Throughput.
Table 8:
(OOD) data. Perf represents the Performance, PPC represents
Noisy Data Label
Di-off-Dittibbttinn (OOD)
Algorithm
Perf
Cost
PPC
Tput
Perf
Cost
PPC
Tput
Random
1403.250
0.419
3350.430
3227
1495.35
0.518
2888. 14
3308.00
Greedy-Pert
1323.600
0.370
3573.750
2471
807.15
0.252
3204.76
1643.00
Greedy-Cost
1660.200
0,461
3604,720
4047
1677.45
0,561
2989.30
4044.00
KNN-Perf
1323.950
0.369
3585,390
2472
816.10
0.254
3212,31
1658.00
KNN-Cost 1660.200
0.461
3604.720
4047
1679.70
0.561
2993.23
4047.00
BatchSplit
1757.250
0.456
3856.680
3974
1828.55
0.526
3474.42
4283.00
Roberta-Perf 83.000
0.045
1836.330
84
9,50
0.017
559.15
10.00
Roherta-Cost
358.000
0.075
4787.593
1616
1692.65
0.562
3013.92
4037.00
Ours
2319.650
0.440
5221.280
4775
2050.8
0.532
3851.53
4644.00
C.6
Historical Data Size & ANNS/KNN Candidates
Historical Data Size. To evaluate the robustness of our algorithm with respect to the size of historical
data, we vary the number of historical data points used in ANNS and KNN from 5000 25000. For RouterBench, whose maximum available historical data is 26497, we randomly sample the subset of data points from 5000 25000. For RouterBench, which contains up to 26497 historical records, we randomly sample subsets within this range. For SPROUT, with maximum of 30968 records, we similarly sample subsets from 5000 25000. For Open LLM Leaderboard v2, which has 11065 historical records, we sample subsets ranging from 5000 to 10000. As shown in Figure II the results clearly show that varying the amount of historical data used ANNS and KNN has minimal impact on performance, with our algorithm consistently and significantly outperforming all baselines across all settings. This demonstrates the robustness and efficiency of our algorithm: even with as few as 5000 historical records, remains effective for routing.
37

---

MMLU
Hellaswag
345.00
303.00
357.00
443.00
40.00
570.00
GSMBK
331.50
133.75
415.50
133.50
404. 75
438.00
14.25
366 90
258.50
1200
ARC Challenge
77.00
39.00
81.00
39.00
71.00
75.00
8.00
8.75
218.00
1000
Winogrande 63.00
48.00
88.00
47.00
95.00
72.00
23.25
17.75
110.00
MBPP.
12.00
MT-Bench- 4.10
3.10
4.70
3,60
5.30
4.30
0.00
0.00
9.20
Chinese: 7.00
8.00
7.00
8.00
8.00
14.00
7.75
0.00
43,00
600
Consensus Summary 20.00
13.75
28.25
13.00
26.00
30.00
0.00
0.00
28.75
Blas Detection 4.00
5.00
5.00
5,00
5.00
8.00
6.00
6.25
3,00
Accounting Audit
2.00
0.00
Abstract2title- 20.00
70.00
24.00
70.00
24.00
30.00
0.00
0.00
13.00
200
Test Match-
0.00
1.00
1.00
1.00
1.00
1.00
0.00
0.00
1,00
Random-
Greedy PPrr
Greedy Greedy__ Cost
KNN Perf-
KNN Cost:
BatchSplit
Roberta Perf.
Roberta, Cost
Ours
Figure 15: Results across different query types in RouterBench.
Number of ANNS/KNN Candidates. investigate the impact of the number of search candidates of ANNS and KNN routing performance, we vary the candidate pool size from the default 5 to 3, 7, and 10. shown in Figure the results show that performance is marginally affected, with a slight improvement the candidate pool size increases. Notably, a leading position across all settings. Even with as few as search candidates, it outperforms all baselines across benchmarks, demonstrating its stability and robustness to the choice of candidate pool size.
algorithm consistently maintains
C.7 Detailed Ablation Study
Impact of embedding models. The choice of embedding model is also important for estimating the performance score and cost of incoming queries. To evaluate the adaptivity of our algorithm to different embedding models used in ANNS, we conduct experiments with two larger embedding mod- els: SFR- See--EEmedding--- 2_R R (40) and gte-Qwen2-1 1. 55-innstruct (35). shown in Figure [3 our algorithm consistently outperforms all baselines across all benchmarks, demonstrating its robustness to the choice of embedding model.
Impact of and e. We evaluate the sensitivity of our method to the parameters and as shown in Figure 14 For a, we observe consistent decline performance as it increases, with the best result achieved at = 0.0001. This trend aligns with Lemma 4 which shows that a larger a amplifies the gap between the performance of our algorithm on the observed subset P. Ć(P), and its expected value eĆ. This increased discrepancy results in greater deviation in performance future queries, ultimately leading to a reduction in overall performance on the full query set Q. For the parameter observe that increasing its value initially improves performance. reaching peak at around = 0.025, after which further increases lead to decline. This aligns with the intuition that controls the number of samples used in the learning stage: too few samples lead to underfitting, while too many may lead to overfitting to the observed data.
C.8 Routing Analysis by Query Types
To gain deeper insights into how our algorithm routes different types of queries, we analyze its routing behavior across the three benchmarks. We categorize query types based on their data sources, as each
source is designed to evaluate different LLM capabilities. As shown in Figure 15 [6 and 17 our
38

---

MATH 618.70
108.80
821.20
832.60
872.20
902.00
1012.50
2000
MMLU-PRO 523.90
148.20
700.50
152.20
675.60
648.90
203.90
638.50
860.90
1500
GPQA 20.90
8.70
20.80
8.70
30.60
26.70
0.00
0.00
24.80
MUSR- 24.60
22.70
57.70
20.70
51.50
47.60
0.00
0.00
41.80
1000
RAGBench-
170.70
61.90
222.40
61.60
218.00
214.40
12.20
472.90
227.40
Openhemes
1459.90
417.50
2122.95
416.60
2096.80
2156.10
189.10
1800.30
2369.35
Random
Greedy Perf
Greedy Coott
KNN Perf
KNN Cost
BatchSplit
Roberta Perf
Roberta Cost
Ours
0
Figure 16: Results across different query types in SPROUT.
MMLU-PRO
800
MUSR
21.00
600
MATH
19.00
5.00
GPQA
379.00
195.00
392.00
198.00
398.00
415.00
58.00
364.00
980.00
Random
Greedy Pert-
Greedy Cost.
KNN Perf
KNN Cost
BatchSplit
Roberta Pert.
Roberta Cost
Ours-
Figure 17: Results across different query types in Open LLM Leaderboard v2.
algorithm consistently achieves superior or competitive routing performance in most query types across benchmarks. These results demonstrate the generalizability and effectiveness of our algorithm in handling diverse query types, which indicates that its performance is not dependent on a narrow subset of tasks.
D Query-Traffic Considerations in LLM Routing
In the practical LLM-serving systems, an additional important routing factor is query traffic patterns. However, the primary goal this work to develop a cost-efficient online routing algorithm, problem that has gained increasing attention in recent literature 43 23 50
especially given the
high computational cost L.M.s. To isolate this core algorithmic problem, we adopt standard
assumption widely used in the online algorithms literature ||] 39 19 incoming queries arrive in
39

---

randomly permuted order. This assumption, discussed in detail in Appendix B.I allows us to abstract away complex traffic dynamics and focus on the fundamental cost-efficiency routing problem.
Under this assumption, our algorithm is designed to operate on query-intrinsic features that are independent of time and query order, such as response performance score and cost per query across the models, In contrast, operational-state features, such as current queue lengths or system load, are beyond the scope of our current formulation and are more aligned with related but orthogonal problem: load balancing under traffic constraints.
Still, we believe our algorithm offers a natural foundation for incorporating such traffic-aware considerations. One potential approach is to discretize time into short windows and track the per- model backlog of unserved workload. Within each time window, corresponding "time-bucket" MILP can be solved with additional traffic constraints, and any unserved workload can be carried over to the next window. For instance, let lij denote the service time of query j on LLM i, by be the backlog of unserved workload for LLM i at the start of time window f, and Aa denote the available service capacity for LLM i during window t. Then, for each window and LLM i, we can add the following constraint to the MILP:
Enjay & max(0, Au - bach Vi,t
(8)
This "time-buckets formulation helps smooth bursts and reduce queuing delays. We leave the integration of such traffic-aware routing mechanisms to future work.
E Extended Related Work
LLM Routing, Existing LLM routing research primarily falls into two paradigms. The first focuses on improving response quality while managing cost, typically through ensembling outputs from different LLMs 266
55] or using cascading strategies that query LLMs sequentially based on their For instance, LLMM-Blender (26) proposes an ensembling framework that combines outputs from multiple open-source LLMs and selects the optimal response. (55] Jusing outputs Wang et al. [55] propose fuse outputs of expert models that capture complementary aspects of the data distribution, to generate the final answer. Frugal-GPT (5) adopts a sequential querying strategy, invoking LLMs in order of increasing capability until a satisfactory response is obtained. AutoMix (2) first uses smaller model to self-verify the quality of the response, based on which dynamically selects a suitably sized model for handling the query. Although these approaches can improve performance, they incur high latency and computational cost due to multiple model invocations per query.
capabilities 5 2
62
3
The second paradigm leverages historical or auxiliary datasets to estimate the performance and cost of each query and select the optimal LLM accordingly 43 50 23
B3 37 27
48 52 [5] 20 (56..
In this line of work, several approaches train model- based predictors using these labeled historical datasets. For example, RouterLLM [43 trains a BERT-base or causal LLM on the historical data annotated with human preferences to enhance routing accuracy, CARROT (50) trains Roberta
models to estimate both performance and cost for each query, enabling selection of the optimal LLM under any user-defined trade-off between quality and cost. HybridLLM [3) adopts the synthetic preference labels from the MixInstruct dataset (26] based on BARTScore 61 and trains a single BERT-based router for query routing. Zooter 37 distills reward signals from training queries and applies tag-based label enhancement to train a routing function that facilitates expert selection. TensorOpera [52) introduces soft label-based strategy based on the BERT similarity scores to train the baRT- predictor for query routing. GraphRouter [15] constructs a heterogeneous graph to capture the contextual relationship between the query requirements and the LLM capabilities for informed routing decisions. While these training-based approaches are effective for certain LLM deployment settings, they introduce nontrivial training overhead. Furthermore, adapting them to varying LLM deployment configurations typically requires retraining, which makes them unsuitable for constraiie online routing with diverse LLM deployment configurations.
Some methods avoid training by using approaches such as KNN 23 or similarity-weighted (SW) ranking 43 to estimate the performance and cost based on the historical data. While these approaches avoid model training overhead, they still incur substantial computational overhead and latency, as they rely on brute-force comparisons against the entire historical dataset to retrieve similar examples
40

---

or compute similarity scores without any optimization. Specifically, they operate with a high search complexity of O(N). where N is the size of the dataset. As a result, these methods are difficult to scale and impractical for high-volume, budget-constrained online routing scenarios.
4 have explored formulating L.M routing MILP. For instance, Sakota et al. 47 introduce two MILP-based strategies, targeting performance-orientee and cost-oriented, respectively. However, these methods face significant challenges in high-volume online routing settings, where queries arrive sequentially, rather than simultaneously. making the offline optimal infeasible to compute.
Recent efforts 47
We complement these works by introducing the first training-free free and efficient online routing method with provable performance guarantees, tailored for high-volume budget-constraing and dynamic LLM--ervvng environments.
Online Matching. This problem has been extensively studied for decades, with much of the
literature focusing on important special cases of the general online submodular welfare maximization problem [29]]] 32 These include the classical unweighted online bipartite matching problem [28 30
31, its extension to weeghted matching 4 [], the display ads allocation problem [14 and
the AdWords problem
39
F Broader Impacts
Our algorithm proposes an efficient, training-free solution for online routing in high-volume, budget- constrained LLM serving. significantly reduces serving costs and improves performance, which enables more sustainable, scalable, and cost-effective multi-LLM deployment. As technical contribution, it does not pose direct societal risks. We believe it promotes broader accessibility LLM services, and future work can further address potential concerns by incorporating responsible use guidelines.
41


Reviews:
[{"review_id": "w8VEV97xKY", "reviewer": "Reviewer_QUtW", "summary": "The paper introduces a training-free algorithm for optimizing the routing of user queries to multiple LLMs in online settings with constrained token budgets. The algorithm leverages a small subset of queries to builds an offline ANNS indice for estimating performance and cost for\neach deployed LLM, and performs a one-time optimization over a small subset of queries to learn weights for routing. These weights are utilized for guiding routing decisions of online queries, ensuring high performance and cost efficiency.", "questions": "1. What parameters have you set for HNSW? I only saw the number of neighbors in the appendix. However, the number of layers of HNSW is not specified. The parameters of HNSW might impact the evaluation results. Could you add evaluations for that? \n\n2. See weakness. \n\n3. Should be HNSW not HWSN throughout the whole paper.", "limitations": "The method only considers cost and efficiency as features for model selection but does not consider traffics of the queries. The authors mentioned to add additional constraints in the original MILP for incorporating other routing factors. However, it is not accurate as incorporating sequences of similar types of queries is not straightforward using MILP.", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 3, "originality": 3, "strengths_and_weaknesses": "Advantages:\n\n1. The performance of the method is good. It achieves an average improvement of 3.55× in overall performance, 1.85× in cost efficiency, and nearly 4.25× in throughput.\n\n2. The method does not require training or frequent finetuning existing models.\n\n3. The method looks not very sensitive to the distributions of user queries. Even if the query distribution might shift in online setting, it only requires an update on the HNSW index by inserting the new query data. And this process can be performed in an offline manner.\n\n4. The writing is clear.\n\n5. The evaluations are comprehensive.\n\nWhat I like most about this paper is that their method is simple but effective. It does not make strong or unrealistic assumptions and is suitable for real-world deployment. My major concern is, the method only considers cost and efficiency as features for model selection. However, in a real-world setting, the traffic of queries is also important. If a high volume of queries arrives at a same time and they are routed to a same LLM, there might be a traffic congestion. \nFor example, if a large number of users ask similar questions in a short amount of time, and the HNSW index suggests to route all the queries to the same LLM, the inference efficiency would be very low. However, at the same time, the other LLMs are idle. \nAlso, the arrival time of different queries and the sequences of different queries matter. \nI understand that solving this problem isn't straightforward, and the linear programming might not be suited. However, the problem is practical and important in a real-world setting.", "was_revised": true, "final_justification": "The authors have addressed my concern.", "rebuttal": "**Q1: The method only considers cost and efficiency as features for model selection but does not consider traffics of the queries. In a real-world setting, the traffic of queries is also important.**\n\nA: Thank you for your comments. We acknowledge that query traffic patterns play an important role in real-world systems. However, the primary goal of our work is to develop a cost-efficient online routing algorithm, a problem that has gained increasing attention in recent literature [1, 2, 3], especially given the high computational cost of LLMs. To isolate this core algorithmic problem, we adopt a standard assumption widely used in the online algorithms literature [4, 5, 6]: that incoming queries arrive in a randomly permuted order. This assumption, also discussed in detail in Appendix B.1, allows us to abstract away complex traffic dynamics and focus on the fundamental cost-efficiency routing problem.\n\nWe would like to clarify that, under this assumption, our framework is designed to operate on **query-intrinsic features** that are independent of time and query order, such as response performance score and cost per query across the models. In contrast, **operational-state features**, such as current queue lengths or system load, are beyond the scope of our current formulation and are more aligned with a related but orthogonal problem: load balancing under traffic constraints.\n\nStill, we believe our algorithm offers a natural foundation for incorporating such traffic-aware considerations. One potential approach is to discretize time into short windows and track the per-model backlog of unserved workload. Within each time window, a corresponding \"time-bucket\" MILP can be solved with additional traffic constraints, and any unserved workload can be carried over to the next window. For instance, let $\\ell_{ij}$ denote the service time of query $j$ on LLM $i$, $b_{it}$ be the backlog of unserved workload for LLM $i$ at the start of time window $t$, and $A_{it}$ denote the available service capacity for LLM $i$ during window $t$. Then, for each window $t$ and LLM $i$, we can add the following constraint to the MILP: \n$$\\sum_j \\ell_{ij} x_{ij} \\leq \\max \\\\{ 0, A_{it} - b_{it} \\\\}, \\quad \\forall i,t$$\nThis \"time-bucket\" formulation helps smooth bursts and reduce queuing delays.\n\nIn the revision, we will further explicitly clarify the scope of our current MILP formulation and also discuss such possible extensions of our algorithm.\n\n\n \n\n\n**Q2: What parameters have you set for HNSW? The number of layers of HNSW is not specified. The parameters of HNSW might impact the evaluation results. Could you add evaluations for that?**\n\nA: Thank you for pointing this out. We use the standard and recommended HNSW implementation from `hnswlib` with the following parameter settings in our paper: *construction effort factor* `ef_construction=200`, *max number of neighbors per node* `M = 32`, and *query search breadth* `ef = 50`. Regarding the number of layers in `hnswlib`, it is not a direct user-configurable hyperparameter. Instead, it is an emergent property of the graph determined during construction, which is primarily controlled by the `M` parameter. A smaller `M` tends to produce a taller, multi-layered graph, while a larger `M` results in a flatter, more interconnected one. \n\nTo evaluate the robustness of our algorithm to these three key parameters, we conduct ablation studies on RouterBench under the main evaluation setting. Specifically, we vary `ef_construction` from 100 to 900, `M` from 8 to 96, and `ef` from 32 to 384. The ablation results, shown in the following tables, demonstrate that our routing algorithm remains highly robust across a wide range of values for all three parameters:\n\n**Table 1. Performance of our algorithm on RouterBench with varying `ef_construction`**\n| `ef_construction`     | Peformance| Cost | Performance per Cost | Throughput | \n|----------------|--------|-------|---------|------|\n| 100    | 2785.40 | 0.46   | 6107.40 | 5305.00 |\n| 200    | 2744.85 | 0.45   | 6147.22 | 5196.00 |\n| 300    | 2738.35 | 0.45   | 6085.40 | 5215.00 |\n| 400    | 2747.90 | 0.45   | 6133.20 | 5217.00 |\n| 600    | 2715.80 | 0.44   | 6105.08 | 5168.00 |\n| 800    | 2726.80 | 0.45   | 6104.13 | 5169.00 |\n| 1200   | 2734.85 | 0.45   | 6125.43 | 5192.00 | \n\n**Table 2. Performance of our algorithm on RouterBench with varying `M`**\n| `M`     | Peformance| Cost | Performance per Cost | Throughput |\n|----------------|--------|-------|---------|------\n| 8      | 2596.60 | 0.44   | 5923.04 | 5084.00 |\n| 16     | 2764.15 | 0.45   | 6107.89 | 5272.00 |\n| 24     | 2745.45 | 0.45   | 6110.49 | 5211.00 |\n| 32     | 2744.85 | 0.45   | 6147.22 | 5196.00 |\n| 48     | 2729.20 | 0.45   | 6116.41 | 5194.00 |\n| 64     | 2726.40 | 0.45   | 6075.57 | 5201.00 |\n| 96     | 2763.35 | 0.45   | 6104.96 | 5214.00 |\n\n**Table 3. Performance of our algorithm on RouterBench with varying `ef`**\n| `ef`     | Peformance| Cost | Performance per Cost | Throughput |\n|----------------|--------|-------|---------|------|\n| 32     | 2730.35 | 0.45   | 6032.83 | 5195.00 |\n| 50     | 2744.85 | 0.45   | 6147.22 | 5196.00 |\n| 80     | 2594.10 | 0.43   | 5973.32 | 5021.00 |\n| 128    | 2706.90 | 0.44   | 6084.47 | 5170.00 |\n| 192    | 2601.85 | 0.44   | 5914.84 | 5022.00 |\n| 256    | 2710.80 | 0.44   | 6112.35 | 5171.00 |\n| 384    | 2744.20 | 0.45   | 6093.61 | 5223.00 |\n\n\n[1] Ong, Isaac, et al. \"Routellm: Learning to route llms with preference data.\" arXiv preprint arXiv:2406.18665 (2024).\n\n[2] Somerstep, Seamus, et al. \"Carrot: A cost aware rate optimal router.\" arXiv preprint arXiv:2502.03261 (2025).\n\n[3] Hu, Qitian Jason, et al. \"Routerbench: A benchmark for multi-llm routing system.\" arXiv preprint arXiv:2403.12031 (2024).\n\n[4] Devanur, Nikhil R., and Thomas P. Hayes. \"The adwords problem: online keyword matching with budgeted bidders under random permutations.\" Proceedings of the 10th ACM conference on Electronic commerce. 2009. \n\n[5] Mehta, Aranyak, et al. \"Adwords and generalized online matching.\" Journal of the ACM (JACM) 54.5 (2007): 22-es.\n\n[6] Gagan Goel and Aranyak Mehta. Online budgeted matching in random input models with applications to adwords. In SODA, volume 8, pages 982–991, 200"}, {"review_id": "QHuw6FcQDL", "reviewer": "Reviewer_f1oy", "summary": "Existing works for LLM router primarily focus on offline scenarios and struggle to adapt to online settings with high query volume and constrained token budgets.\n\nThis paper introduces the first training-free algorithm for online routing scenarios. The algorithm leverages approximate nearest neighbor search to efficiently estimate query features and performs a one-time optimization over a small set of initial queries to learn a routing strategy that guides future routing.\n\nThe algorithm estimates the performance scores and costs efficiently using a historical dataset, and learns a routing strategy from a small subset of observed queries (of size ϵ|Q|) to guide future query routing.\n\nExperiments on simulated traces show the performance.", "questions": "1. Move Table 1 to the next page.", "limitations": "yes", "rating": 3, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 2, "clarity": 3, "significance": 2, "originality": 2, "strengths_and_weaknesses": "Strengths\n\n1. Improving the efficiency of LLM routing is an important topic.\n\n2. The proposed method with approximate nearest neighbor search and online learning is helpful.\n\n3. Theoretical analysis and experiments are provided.\n\nWeaknesses\n\n1. Such approximate nearest neighbor methods highly rely on the training data. E.g. Routerbench has 36,497 examples. The paper uses 26,497 queries as historical data to construct the search examples and 10,000 queries for testing.\n\n2. Stronger model-based methods like BERT can be added. The router running time of these methods can also be compared.\n\n3. Experiments are only on simulated traces.", "was_revised": true, "final_justification": "After discussion with authors, the paper needs to improve the experiment setup to provide a fair comparison with baselines and consolidate the extra supporting experiments.", "rebuttal": "**Q1: Such approximate nearest neighbor methods highly rely on the training data. E.g. Routerbench has 36,497 examples. The paper uses 26,497 queries as historical data to construct the search examples and 10,000 queries for testing.**\n\nA: Thanks for the comments. We would like to clarify that our algorithm does not rely heavily on historical data. As we already showed in Appendix C.5 (Figure 11), varying the amount of historical data used for ANNS has minimal impact on performance. Our method consistently and significantly outperforms all baselines across all data sizes, demonstrating strong robustness. Notably, even with as few as **5000** historical records, our algorithm remains highly effective for routing.\n\n\n**Q2: Stronger model-based methods like BERT can be added.** \n\nA: We appreciate the suggestion. Following the main setting in the paper, we train two separate BERT-based models to predict the generation performance score and cost for each query, resulting in two additional BERT-based routing baselines:\n(i) BERT-perf-routing, which routes each query to the model with the highest predicted performance;\n(ii) BERT-cost-routing, which routes each query to the model with the greatest available budget.\nWe compare our algorithm with these two baselines on RouterBench under the main experimental setting. The detailed results are as follows:\n\n**Table 1.  Comparison of Our Routing Algorithm with BERT‑Based Methods on RouterBench**\n| Algorithm     | Peformance| Cost | Performance per Cost | Throughput |\n|----------------|--------|-------|---------|------|\n| Bert-Perf                                      | 384.25 | 0.154 | 2480.87 | 452  |\n| Bert-Cost                                      | 630.35 | 0.145 | 4340.51 | 156 |\n|**Ours**     | **2718.6** | 0.447  | **6075.58** | **5195**    |\n\nAs shown in the above results, our method achieves >4$\\times$ higher Performance and >3$\\times$ higher Throughput than the strongest BERT‑based baseline, while maintaining favorable cost efficiency.\n\n**Q3: The router running time of these methods can also be compared.**\n\nA: Thank you for raising this point. We provide a detailed comparison of routing latency on RouterBench under varying numbers of test queries. All implementations are in Python, and each method is executed using a single CPU thread. For model-based methods that require GPU computation, we follow the same setup as in [1] and use a single NVIDIA L4 GPU (24GB). Across all methods, we fix the processing batch size to 256 for consistency. The detailed latency results are summarized below, demonstrating the routing efficiency of our algorithm: our method achieves the **fastest routing among all baselines** (except the random routing strategy, which exhibits significantly poorer performance):\n\n**Table 2. Total routing latency (s) comparison of routing algorithms on RouterBench under varying numbers of queries**\n| Algorithm     | 4000 queries | 6000 queries | 8000 queries | 10000 queries |\n|----------------|--------|-------|---------|------|\n| Greedy-Perf            | 0.81         | 1.22         | 1.61         | 2.03           |\n| Greedy-Cost            | 0.93         | 1.38         | 1.81         | 2.33           |\n| KNN-Perf               | 1.91         | 2.85         | 3.75         | 4.75           |\n| KNN-Cost               | 1.92      | 3.12  | 4.07 | 5.06           |\n| BatchSplit             | 1.20         | 1.69         | 2.25         | 2.78           |\n| Roberta-Perf     | 107.91       | 157.93       | 212.71       | 265.78         |\n| Roberta-Cost      | 108.00       | 158.24       | 212.53       | 265.91         |\n| Bert-Perf              | 111.77       | 164.98       | 221.64       | 277.28         |\n| Bert-Cost              | 112.76       | 165.84       | 223.32       | 277.32         |\n| **Ours**               | **0.24**     | **0.36**     | **0.48**     | **0.64**       |\n\n\nThese results clearly show that our algorithm consistently achieves the lowest routing latency across all settings, outperforming all baseline methods. This demonstrates the strong routing efficiency of our approach. Furthermore, we note that our current implementation of our algorithm, which is written in Python and runs on a single CPU thread, can be further optimized. Since the algorithm does not require any GPU resources or operations, it can be easily reimplemented in a faster programming language such as C++ for better performance. In addition, because routing decisions for individual queries are made independently based on learned routing weights, the algorithm is naturally parallelizable and well-suited for multi-threaded execution. Applying these optimizations can further provide substantial speed-ups in practice.\n\n\n\n**Q4: Experiments are only on simulated traces.** \n\nA: Thank you for your comment. To the best of our knowledge, we have evaluated our method on almost all publicly available multi-LLM routing benchmarks [2, 3, 4] that are widely used in the literature and research community. We are not aware of any additional public datasets in this space. If the reviewer has any pointers to specific labeled traffic traces, we would be happy to incorporate them into further experiments.\n\n\n\n**Q5: Move Table 1 to the next page**\n\nA: Thank you for the suggestion. We will move Table 1 to an appropriate position on the next page in the revised version.\n\n[1] Ong, Isaac, et al. \"Routellm: Learning to route llms with preference data.\" arXiv preprint arXiv:2406.18665 (2024).\n\n[2] Hu, Qitian Jason, et al. \"Routerbench: A benchmark for multi-llm routing system.\" arXiv preprint arXiv:2403.12031 (2024).\n \n[3] Open llm leaderboard v2. https://huggingface.co/spaces/open-llm-leaderboard/open_llm_leaderboard, 2024.\n\n[4] Somerstep, Seamus, et al. \"Carrot: A cost aware rate optimal router.\" arXiv preprint arXiv:2502.03261 (2025)."}, {"review_id": "e4QNSImhqG", "reviewer": "Reviewer_RvpU", "summary": "This paper introduces a training-free routing strategy by leveraging the log of historical prompts and associated generations as well as their quality scores and costs. Specifically, it conducts semantic embedding based nearest neighbor search to retrieve similar past queries and estimate the performance by averaging recorded measures. Then, it combines estimated quality and cost of each model using learned and fixed weights to decide the final pick of the model.", "questions": "What is the query-level latency? How does it compare to other routing strategies including trained lightweight routers?", "limitations": "yes", "rating": 3, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 2, "clarity": 3, "significance": 2, "originality": 2, "strengths_and_weaknesses": "Strength:\n- Comprehensive evaluation on three benchmarks.\n- Extensive tests over query volume, arrival order, size of historical data, size of search candidates, etc.\n- Code and data are released for reproducibility.\n\nWeakness:\n- The effectiveness of the proposed method depends on reliable quality labels. The experiments mainly use the pre-existing ground truth and lack of robustness evaluation against noisy quality labels.\n- The baseline methods are somewhat weak. Some of the comparable works are discussed in the related work sections but are not empirically compared in the evaluation section. \n- The theoretical proof relies on strong assumptions including the existence of at least one close neighbor in the log and that generation quality and cost are smoothly tied to prompt embeddings. Similarly, evaluation is mainly conducted with an in-distribution setting, and it is unclear if the proposed method is robust enough to handle the out-of-distribution challenge and drifting query patterns in dynamic online settings.", "was_revised": true, "final_justification": "While I appreciate the additional results and explanations provided by the authors during the discussion period, I believe the paper needs another round of revision to consolidate the extra supporting experiments and strengthen the associated discussions. Therefore, I’m leaning toward a borderline rating.", "rebuttal": "**Q1: The experiments mainly use the pre-existing ground truth and lack of robustness evaluation against noisy quality labels.**\n\nA: Thank you for your comments. To demonstrate the robustness of our algorithm under noisy historical labels, we conduct experiments in a noisy setting where two types of strong noise are introduced simultaneously. Specifically, for each performance label $d_{ij}$, we randomly flip its value with a probability of 20%. For each cost label $g_{ij}$, we apply multiplicative, mean-preserving noise consisting of two components: (i) log‑normal jitter $\\left(\\log \\mathcal{N}(0, \\sigma^2) - \\frac{1}{2} \\sigma^2\\right)$ with $\\sigma = 0.25$, and (ii) a spike factor of 3.0 applied with probability 2%. \n\nWe compare our algorithm against all baseline methods on RouterBench under the main experimental setting. As shown in the results below, our method consistently outperforms all baselines under noisy historical labels. It achieves the highest overall performance, the highest throughput, and the best cost efficiency, demonstrating the strong robustness of our algorithm under noisy conditions.\n\n**Table 1. Routing performance under noisy historical data. Comparison between our algorithm and baselines on RouterBench.**\n|Algorithm|Peformance|Cost|Performance per Cost|Throughput|\n|----------------|--------|-------|---------|------|\n|Random|1403.25|0.419|3350.43|3227|\n|Greedy-Perf|1323.6|0.370|3573.75|2471|\n|Greedy-Cost|1660.2|0.461|3604.72|4047|\n|KNN-Perf|1323.95|0.369|3585.39|2472|\n|KNN-Cost|1660.2|0.461|3604.72|4047|\n|BatchSplit|1757.25|0.456|3856.68|3974|\n|Roberta-Perf|83|0.045|1836.33|84|\n|Roberta-Cost|358|0.075|4787.593|1616|\n|**Ours**|**2319.65**|0.444|**5221.28**|**4775**|\n\n\n\n**Q2: The baseline methods are somewhat weak.**\n\nA: Thank you for your suggestions. To the best of our knowledge, our work is the first to focus specifically on training-free online multi-LLM routing, and there are currently no existing methods that directly target the same setting. To provide further meaningful comparisons, we additionally include and adapt three local routing baselines adapted from two related works: RouteLLM (MF) and RouteLLM (BERT) from [1], and CARROT (RoBERTa) from [2]. Literature [1] is a well-known two-model routing approach, while [2] represents **the current state-of-the-art** in offline multi-LLM routing, with the goal of balancing cost and performance. \nSince [1] only handles two-model routing, we extend it to the multi-model case by training multi-label predictors for win rates and applying a **cheapest feasible model** strategy: routing to the cheapest model whose predicted win rate logit exceeds a threshold $\\alpha$. Furthermore, as all three baselines are originally intended for local or offline routing, we adapt them to our online setting. We use $20\\%$ historical data to search the threshold $\\alpha$ (for RouteLLM) and the cost-efficiency coefficient $\\mu$ (for CARROT) over the range [0, 1] with step size of 0.1 to maximize performance under a fixed budget.\n\nWe present comparisons on the most representative benchmark, RouterBench, under the main experimental setting. Our algorithm outperforms all three additional baselines across all key metrics while maintaining the lowest routing latency. Notably, it achieves over **1.5$\\times$** higher throughput than all baselines and a routing latency of just 0.64 seconds, which is over **200× faster** than the state-of-the-art CARROT method:\n\n**Table 2.  Comparison results with 3 additional baselines on RouterBench**\n|Algorithm|Peformance|Cost|Performance per Cost|Throughput|Total routing Latency(s)|\n|----------------|--------|-------|---------|------|------|\n|Multi-RouteLLM(MF)($\\alpha=0.6$)|2041|0.35|5883.61|3525|3.66|\n|Multi-RouteLLM(BERT)($\\alpha=0.4$)|1764.35|0.31|5753.82|3246|135.94|\n|CARROT(RoBERTa)($\\mu=0.2$)|1353.2|0.23|5987.61|2737|255.35|\n|**Ours**|**2718.6**|0.447|**6075.58**|**5195**|**0.64**|\n \n\n\n\n**Q3: The theoretical proof relies on strong assumptions including the existence of at least one close neighbor in the log and that generation quality and cost are smoothly tied to prompt embeddings. The evaluation is mainly conducted with an in-distribution setting, and it is unclear if the proposed method is robust enough to handle the out-of-distribution challenge and drifting query patterns in dynamic online settings.**\n\nA: Thank you for your comments. We believe there may be a misunderstanding, and we would like to clarify that the assumptions we make, which are discussed in detail in Appendix B.1, are all natural and mild. In particular, Assumption 1 is grounded in the core idea of informative query routing: we assume that there exist historical data points that are informative for routing future queries. This aligns with the core intuition behind nearly all prior predictive LLM routing methods [1, 2, 3, 4], which assume that some queries in the training or historical data share similar routing-relevant features with future queries.\nIf no such informative historical data exists, then leveraging training/historical data for predictive routing becomes impossible, and all previous methods, whether training language models or low-rank models on the historical data, would reduce to random routing, as discussed in Appendix B.1. In such a case, no meaningful inference can be made without directly querying the LLMs. One must query all LLMs to make informed routing decisions. This is because, in the worst case, under an adversary query targeting the LLM query order in the system, all LLMs may present extremely low performance, except the last LLM. This underscores the importance of Assumption 1, which connects historical data to future queries, enabling meaningful routing and improved performance.\n\nTo evaluate the robustness of our algorithm, we construct a challenging out-of-distribution setting using RouterBench, which consists of 13 distinct datasets with substantially different distributions (see Table 2 in the Appendix). We use a single dataset (MMLU) in RouterBench as historical data and treat the remaining 12 datasets (including Chinese, GSM8K, and so on) as the test set. We compare our algorithm against all baselines under the main setting in both the OOD and noisy settings. The detailed results are as follows:\n\n\n**Table 3.  Routing performance in the out-of-distribution setting: Comparison between our algorithm and baselines on RouterBench**\n|Algorithm|Peformance|Cost|Performance per Cost|Throughput|\n|----------------|--------|-------|---------|------|\n|Random|1495.35|0.518|2888.14|3308|\n|Greedy-Perf|807.15|0.252|3204.76|1643|\n|Greedy-Cost|1677.45|0.561|2989.30|4044|\n|KNN-Perf|816.10|0.254|3212.31|1658|\n|KNN-Cost|1679.70|0.561|2993.23|4047|\n|BatchSplit|1828.55|0.526|3474.42|4283|\n|Roberta-Perf|9.50|0.017|559.15|10|\n|Roberta-Cost|1692.65|0.562|3013.92|4037|\n|Multi-RouteLLM(MF)|924|0.247|3734.01|2227|\n|Multi-RouteLLM(BERT)|908.60|0.248|3657.92|2239|\n|CARROT(Roberta)|459.40|0.121|3783.47|738|\n|**Ours**|**2050.8**|0.532|**3851.53**|**4644**|\n\nAs shown in the Table, even under this challenging OOD setting, our algorithm consistently outperforms all baselines. It achieves the highest overall performance, the best performance-per-cost ratio, and the greatest throughput. These results highlight the strong robustness of our method to distribution shift and changing query patterns.\n\n\n**Q4: What is the query-level latency? How does it compare to other routing strategies including trained lightweight routers?**\n\nA: Thank you for raising this point. We provide a detailed comparison of query-level routing latency on RouterBench under varying numbers of test queries. All implementations are in Python, and each method is executed using a single CPU thread. For model-based methods that require GPU computation, we follow the same setup as in [1] and use a single NVIDIA L4 GPU (24GB). Across all methods, we fix the processing batch size to 256 for consistency. The detailed latency results are summarized below, where our method achieves the **fastest routing among all baselines** (except the random routing strategy, which exhibits significantly poorer performance).\n\n**Table 4. Per-query routing latency (ms) of different algorithms on RouterBench under varying numbers of queries**\n|Algorithm|4000queries|6000queries|8000queries|10000queries|\n|---------------------|------------|------------|------------|-------------|\n|Greedy-Perf|0.203|0.203|0.201|0.203|\n|Greedy-Cost|0.233|0.230|0.226|0.233|\n|KNN-Perf|0.478|0.475|0.469|0.475|\n|KNN-Cost|0.479|0.520|0.508|0.506|\n|BatchSplit|0.300|0.282|0.281|0.278|\n|Roberta-Perf|26.978|26.322|26.589|26.578|\n|Roberta-Cost|27.000|26.373|26.566|26.591|\n|Multi-RouteLLM(MF)|0.393|0.377|0.364|0.366|\n|Multi-RouteLLM(BERT)|13.620|13.568|13.661|13.594|\n|CARROT(Roberta)|26.015|25.413|25.644|25.535|\n|**Ours**|**0.060**|**0.060**|**0.060**|**0.064**|\n\nThese results clearly demonstrate that our algorithm consistently achieves the lowest per-query routing latency across all settings, significantly outperforming all baselines. Notably, compared to model-based routers, our method achieves over **200$\\times$** speed-up. Note that our current implementation, which is written in Python and runs on a single CPU thread, can be further optimized. Since it requires no GPU operations and handles queries independently, it can be easily reimplemented in a lower-level language such as C++ and parallelized to achieve even greater speed-ups in practice.\n\n[1] Ong, Isaac, et al. \"Routellm: Learning to route llms with preference data.\" arXiv preprint arXiv:2406.18665 (2024).\n\n[2] Somerstep, Seamus, et al. \"Carrot: A cost aware rate optimal router.\" arXiv preprint arXiv:2502.03261 (2025).\n\n[3] Hu, Qitian Jason, et al. \"Routerbench: A benchmark for multi-llm routing system.\" arXiv preprint arXiv:2403.12031 (2024).\n\n[4] Wang, Xinyuan, et al. \"Mixllm: Dynamic routing in mixed large language models.\" arXiv preprint arXiv:2502.18482 (2025)."}, {"review_id": "OZpvyTNsvJ", "reviewer": "Reviewer_toJm", "summary": "This paper proposes a training-free, online routing algorithm to efficiently handle high-volume, budget-constrained LLM inference requests. Unlike prior methods that rely on heavy offline training or dynamic retraining, the proposed method:\n1. Uses Approximate Nearest Neighbor Search (ANNS) to estimate query-level performance and cost features from historical data.\n2. Learns a single global routing strategy (γ)* based on a small subset of initial queries.\n3. Applies this learned strategy for online query routing using a principled dual formulation of a relaxed MILP.\n\nIt demonstrates strong theoretical guarantees (competitive ratio of 1-o(1) and empirical results showing up to: 3.55× performance, 1.85× better cost-efficiency, 4.25× higher throughput over 8 competitive baselines on 3 benchmarks.", "questions": "1. How sensitive is the routing performance to the quality and size of the historical dataset?\n2. How often should γ∗ be re-learned in a real system?\n3. Could reinforcement learning improve the second-stage routing?\n4. Can the proposed method be applied for VLM (vision language model)?", "limitations": "yes", "rating": 4, "confidence": 2, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 3, "originality": 3, "strengths_and_weaknesses": "Strengths:\n1. This is the first routing method for online multi-LLM serving that is training-free, addressing the scalability bottlenecks of prior methods in realistic deployments.\n2. Solid formulation of routing as a MILP and its LP relaxation.\n3. Compared against 8 baselines across multiple metrics and settings.\n\nWeaknesses:\n1. While the paper claims low-latency routing, it doesn’t provide absolute latency measurements (e.g., milliseconds per query) or breakdowns.", "was_revised": true, "final_justification": "My concerns are addressed.", "rebuttal": "**Q1: While the paper claims low-latency routing, it doesn’t provide absolute latency measurements (e.g., milliseconds per query) or breakdowns.**\n\nA: Thank you for raising this point. We provide a detailed comparison of per-query routing latency on RouterBench under varying numbers of test queries. All methods are implemented in Python and executed using a single CPU thread. For model-based approaches requiring GPU computation, we follow the same setup as in [1], using a single NVIDIA L4 GPU (24GB). To ensure consistency, we fix the processing batch size to 256 across all methods. The latency results are summarized below, showing that our method achieves the **fastest routing among all baselines** (except the random routing strategy, which exhibits significantly poorer performance).\n\n**Table 1. Per-query routing latency (ms) of different algorithms on RouterBench under varying numbers of queries**\n| Algorithm     | 4000 queries | 6000 queries | 8000 queries | 10000 queries |\n|----------------|--------|-------|---------|------|\n| Greedy-Perf            | 0.203          | 0.203          | 0.201          | 0.203           |\n| Greedy-Cost            | 0.233          | 0.230          | 0.226          | 0.233           |\n| KNN-Perf               | 0.478          | 0.475          | 0.469          | 0.475           |\n| KNN-Cost               | 0.479 |0.520 |0.508 |0.506          |\n| BatchSplit             | 0.300          | 0.282          | 0.281          | 0.278           |\n| Roberta-Perf    | 26.978         | 26.322         | 26.589         | 26.578          |\n| Roberta-Cost     | 27.000         | 26.373         | 26.566         | 26.591          |\n| **Ours**               | **0.060**      | **0.060**      | **0.060**      | **0.064**       |\n\nThese results clearly demonstrate that our algorithm consistently achieves the lowest per-query routing latency across all settings, significantly outperforming all baselines. Notably, compared to model-based routers, our method achieves over **200$\\times$** speed-up, highlighting its strong routing efficiency. Furthermore, our current implementation, which is written in Python and executed on a single CPU thread, can be further optimized. Since the algorithm requires no GPU operations, it can be easily reimplemented in a lower-level language such as C++ for further improvement. Additionally, because routing decisions for individual queries are made independently, the algorithm is inherently parallelizable and well-suited for multi-threaded execution. These optimizations can lead to substantial additional speed-ups in real-world deployments.\n\n\n**Q2: How sensitive is the routing performance to the quality and size of the historical dataset?**\n\nA: Thanks for your comments. We have already included detailed experiments on the impact of historical data size on routing performance in Appendix C.5 (see Figure 11). The results show that varying the amount of historical data has a negligible effect on our algorithm’s performance. Across all data sizes and settings, our method consistently and significantly outperforms all baselines, demonstrating strong robustness. Notably, even with as few as 5,000 historical records, our algorithm remains highly effective for routing.\nTo assess sensitivity to data quality, we consider two challenging settings: **noisy labels** and **out-of-distribution (OOD)** historical data. \n\nIn the **noisy setting**, we introduce two types of strong noise simultaneously. For each performance label $d_{ij}$, we randomly flip its value with a probability of 20%. For each cost label $g_{ij}$, we apply multiplicative, mean-preserving noise consisting of: (i) log-normal jitter $\\left(\\log \\mathcal{N}(0, \\sigma^2) - \\frac{1}{2}\\sigma^2\\right)$ with $\\sigma = 0.25$, and (ii) a spike factor of 3.0 applied with 2% probability.\n\nIn the **OOD setting**, we construct a distribution shift using RouterBench, which contains 13 diverse datasets (see Table 2 in the Appendix). We use MMLU as the historical dataset and evaluate on the remaining 12 datasets, which differ significantly in data distribution.\nIn both settings, our algorithm consistently outperforms all baselines under the main evaluation protocol. The detailed results are as follows:\n\n**Table 2.  Routing performance under noisy historical data: our algorithm v.s. baselines on RouterBench**\n| Algorithm     | Peformance| Cost | Performance per Cost | Throughput | \n|----------------|--------|-------|---------|------|\n| Random                  | 1403.250        | 0.419   | 3350.430        | 3227        |\n| Greedy-Perf             | 1323.600        | 0.370   | 3573.750        | 2471        |\n| Greedy-Cost             | 1660.200        | 0.461   | 3604.720        | 4047      |\n| KNN-Perf                | 1323.950        | 0.369   | 3585.390        | 2472        |\n| KNN-Cost                | 1660.200        | 0.461   | 3604.720        | 4047        |\n| BatchSplit              | 1757.250        | 0.456   | 3856.680        | 3974        |\n| Roberta-Perf            | 83.000          | 0.045   | 1836.330        | 84          |\n| Roberta-Cost            | 358.000         | 0.075   | 4787.593        | 1616        |\n| **Ours**                | **2319.650**    | 0.444 | **5221.280**     | **4775**     |\n\n\n**Table 3.  Routing performance in the out-of-distribution setting: Comparison between our algorithm and baselines on RouterBench**\n| Algorithm     | Peformance| Cost | Performance per Cost | Throughput | \n|----------------|--------|-------|---------|------|\n| Random                  | 1495.35        | 0.518   | 2888.14        | 3308.00        |\n| Greedy-Perf             | 807.15         | 0.252   | 3204.76        | 1643.00        |\n| Greedy-Cost             | 1677.45        | 0.561   | 2989.30        | 4044.00        |\n| KNN-Perf                | 816.10         | 0.254   | 3212.31        | 1658.00        |\n| KNN-Cost                | 1679.70        | 0.561   | 2993.23        | 4047.00        |\n| BatchSplit              | 1828.55        | 0.526   | 3474.42        | 4283.00        |\n| Roberta-Perf            | 9.50           | 0.017   | 559.15         | 10.00          |\n| Roberta-Cost            | 1692.65        | 0.562   | 3013.92        | 4037.00        |\n| **Ours**      |**2050.8** | 0.532 | **3851.53** | **4644.00** |\n\nAs shown in the above tables, our algorithm consistently outperforms all baselines under both noisy historical labels and out-of-distribution settings. In both cases, it achieves the highest overall performance, best performance-per-cost ratio, and greatest throughput, demonstrating strong robustness to label noise and varying distribution shift.\n\n**Q3: How often should γ∗ be re-learned in a real system?** \n\nA: Thank you for the question. In our approach, the routing weights $\\gamma^\\star$ are learned based on the number of upcoming queries to be routed and the chosen fraction ratio $\\epsilon$. For example, with $\\epsilon = 0.025$ and a total query batch of 10000, only 250 initial queries are needed to learn the routing weights $\\gamma^\\star$. In practice, incoming queries can be divided into sequential chunks (e.g., of size 10000), and $\\gamma^\\star$ is relearned for each chunk. Specifically, after finishing routing one chunk, we relearn $\\gamma^\\star$ for the next chunk. The overhead of this learning process is negligible, where it takes approximately 0.03s on 250 samples and 0.05s on 500 samples, and can be further improved. This means that, even in high-throughput scenarios (e.g., 10000 queries per second), this routing weight optimization only adds negligible overhead (0.03s), making the relearning process both efficient and practical for real systems.\n\n\n\n\n**Q4: Could reinforcement learning improve the second-stage routing?**\n\nA: Thanks for your suggestion. Using reinforcement learning (RL) for improving the second-stage routing is indeed an interesting direction. In our current design, we learn the routing weights efficiently via a one-shot optimization of the dual LP, which is highly efficient and requires no costly online training process.  While RL could offer benefits such as continual adaptation to changing query patterns and integration of richer feedback signals, it also introduces extra complexity and exploration overhead. We consider RL-based routing a promising avenue for future work.\n\n\n**Q5: Can the proposed method be applied for VLM (vision language model)?**\n\nA: Thanks for the question. Our routing framework is largely modality‑agnostic and only requires that the processed queries can be mapped into a vector space (embedding). In a VLM scenario, one can first encode each image (and its accompanying text, if any) into a joint embedding (e.g., via CLIP or another vision–language encoder). With this joint embedding, our algorithm can be naturally extended to the VLM setting by applying the same procedure: using ANNS to retrieve informative historical data points and performing online cost-efficient routing accordingly. We view this extension as an exciting future direction. \n\n\n[1] Ong, Isaac, et al. \"Routellm: Learning to route llms with preference data.\" arXiv preprint arXiv:2406.18665 (2024)."}]

Author rebuttal:

Meta-review: This paper proposes the first training-free algorithm for online routing in multi-LLM serving under constrained token budgets. The method leverages approximate nearest neighbor search on historical queries and performs a one-time optimization over a small subset of queries to derive routing weights, which are then used for efficient online routing. The authors provide both theoretical guarantees and extensive empirical results across three benchmarks and eight baselines, showing consistent improvements in performance, cost efficiency, and throughput.

The strengths of the paper lie in its novelty, simplicity, and practicality. The method avoids retraining, is robust to data size and distribution shifts, achieves significant empirical gains, and is supported by strong theoretical analysis. The evaluations are comprehensive, with ablations, robustness tests to noise, and latency measurements, making the work relevant for real-world deployments.

The weaknesses are that some reviewers questioned the reliance on high-quality historical data, limited real-world traces, and whether stronger model-based routers could offer more competitive baselines. There were also concerns about assumptions in the theoretical proof and the lack of traffic-aware constraints in the current formulation.

The main reason for acceptance is that the paper addresses an important and timely challenge in scalable LLM deployment with a simple yet powerful solution that demonstrates both theoretical rigor and empirical robustness. While some reviewers leaned borderline due to experimental setup or scope, the rebuttal convincingly clarified key points, added strong additional baselines (e.g., BERT, CARROT), robustness evaluations (noise, OOD), and latency breakdowns. This addressed the main criticisms from reviewers QUtW, f1oy, RvpU, and toJm, with most acknowledging that their concerns were resolved.
Decision: Accept (poster)