BEST-Route: Adaptive LLM Routing with Test-Time Optimal Compute
Authors: Dujian Ding
Ankur Mallick
Shaokun Zhang
Chi Wang
Daniel Madrigal
Mirian Del Carmen Hipolito Garcia
Menglin Xia
Laks V. S. Lakshmanan
Qingyun Wu
Victor Rühle
Venue: ICML 2025 poster (2025)
Keywords: Large language models
Efficient ML
Query Routing
Test-time Optimal Compute
Primary area: deep_learning->large_language_models

Abstract: Large language models (LLMs) are powerful tools but are often expensive to deploy at scale.  LLM query routing mitigates this by dynamically assigning queries to models of varying cost and quality to obtain a desired tradeoff. Prior query routing approaches generate only one response from the selected model and a single response from a small (inexpensive) model was often not good enough to beat a response from a large (expensive) model due to which they end up overusing the large model and missing out on potential cost savings. However, it is well known that for small models, generating multiple responses and selecting the best can enhance quality while remaining cheaper than a single large-model response. We leverage this idea to propose BEST-Route, a novel routing framework that chooses a model and the number of responses to sample from it based on query difficulty and the quality thresholds. Experiments on real-world datasets demonstrate that our method reduces costs by up to 60% with less than 1% performance drop.

BEST-Route: Adaptive LLM Routing with Time Optimal Compute
Dujian Ding' Ankur Mallick?
Shaokun Zhang 3 Chi Wang Daniel Madrigal
Mirian Del Carmen Hipolito Garcia Menglin Xia Laks V. S. Lakshmanan
Qingyun Wu 36 Victor Rühle"
Abstract
substantial computational costs, driven by their large sizes and autoregressive text generation, making their deploy- ment a challenge for both developers and users (Yu et al., 2022). The growing demand for I.L.-backed services has spurred the development of innovative solutions to achieve efficiency without sacrificing quality.
Large language models (LLMs) are powerful tools but are often expensive to deploy scale. LLM query routing mitigates this by dynamically assigning queries to models of varying cost and quality to obtain desired tradeoff. Prior query routing approaches generate only one response from the selected model and a single response from a small (inexpensive) model was often not good enough to beat a response from a large (ex- pensive) model due to which they end up overus- ing the large model and missing out on poten- tial cost savings. However, it is well known that for small models, generating multiple responses and selecting the best can enhance quality while remaining cheaper than a single large-model re- sponse. We leverage this idea to propose BEST- Route, novel routing framework that chooses model and the number of responses to sample from it based on query difficulty and the quality thresholds. Experiments on real-world datasets demonstrate that our method reduces costs by up to 60% with less than 1% performance drop.
The rising costs of LLM inference have spurred efforts to develop smaller, more cost-effective models such as self- consistency (Wang et al., 2023) and re-ranking (Chuang et al., 2023). However despite several innovations in this space (Dubey et al., 2024; Abdin et al., 2024), small models continue to come up short in terms of response quality when compared to the largest, most powerful models (see Figure where y-axis measures response quality). Therefore an alternate line of work has focused on combining multiple models, small and large, to balance response quality and cost (Ding et al., 2024; Ong et al., 2024; Kim et al., 2023; Chen et al., 2023). Broadly speaking these works seek to leverage the small models to respond to easier queries while saving the large models for the more challenging queries thereby reducing costs without loss of response quality, In particular there are three sub-areas where this principle has been applied: 1) Query routing (e.g. Ong et al. (2024)) where a classifier/scorer rates the difficulty of an input and selects models accordingly, 2) Speculative decoding (e.g. Kim et al. (2023)) where a small (drafter) model returns candidate response tokens that are accepted/rejected by the large (verifier) model, and 3) Model cascades (e.g. Chen et al. (2023)) where the query passes through the models sequentially, from the cheapest to the most costly, until either a satisfactory response is obtained or a pre-defined max number of models of the cascade is reached.
1. Introduction
Large language models (LLMs) have revolutionized natural language processing (NLP) by delivering state-of-the-art performance across a wide range of tasks, from language understanding to creative writing, code generation, and be- yond (Zhao al., 2023). Their widespread deployment in applications like ChatGPT (OpenAI, a) and other conversa- tional agents (Zheng et al., 2023; Zhang et al., 2024a;b) has made them a cornerstone of modern NLP systems. However, the superior performance of these models often comes with
This work focuses on query routing and seeks to combine model selection with adaptive allocation of computing re- sources test-time (Snell et al., 2024) obtain notable re- sponse quality improvements compared to prior work while achieving substantial cost reduction. We observe that ma- jor drawback of many prior query routing approaches is that they are unable to leverage extra compute and scale up the performance of the smaller (lower cost) models in their portfolio. Therefore they often end up routing all but the easiest queries to large models and thus provide little cost savings (this is shown in prior work (Ding et al., 2024) and
'University of British Columbia (work performed during in- ternship at Microsoft) *Microsoft 'Pennsylvania State Univer- sity "Google (work performed while at Microsoft) UUniversity of British Columbia " 'AG2AI, Inc.. Correspondence to: Dujian Ding <dujian. @egmmllllmm......
Proceedings of the 4nnd International Conference Machine Learning. Vancouver, Canada. PMLR 267, 2025. Copyright 20255 by the author(s).

---

BEST-Route: Adaptive LLM Routing with Test-Time Optimal Compute
BEST-Route
1. Match Probability Prediction
2. Best-of-N Sampling
Multi-Head Router
Selected LLM
Query q
LLMs
cH
Select the optimal
Query
S$S
LLM and Best-of-N combination
Response 1
Reeponse
N=1
N Responses
N=2
Best Response
Query q
Proxy RM
N=N
Score each response using proxy reward model and return the best.
Best Response
Figure 1. System overview of BEST-Route: Best-of-n Enhanced Sampling and Test-time Route Optimization.
in couple of the baseline routing approaches in Figure 3).
adding minimal overhead. 2) Test-time optimal compute strategy: We introduce a best-of-n sampling mechanism, al- lowing the router to select the most effective response which improves performance while still saving costs. 3) Scalable real-world evaluations: We demonstrate the effectiveness of our approach on large-scale datasets, achieving signifi- cant cost savings with minimal response quality drop.
We propose Best-of-n Enhanced Sampling and Test-time Route Optimization Route), novel LLM routing framework that effectively balances cost and quality through two key innovations. First, a cost-efficient multi- heati- router dynamically assesses query difficulty to select the appropriate model and allocate computational resources. Second, a test-time optimal compute strategy leverages best- of-n sampling (Stiennon et al., 2020; Nakano et al., 2021) to enhance small-model performance. This ensures that easy queries are routed to smaller, cheaper models with minimal sampling, while harder queries benefit from the ad advanced capabilities of larger models. Our framework employs a flexible model orchestration pipeline to adapt to varying cost-quality requirements. Specifically, our router predicts the likelihood that small model, with best-of-n sampling, can generate responses comparable powerful reference model (e.g., GPT-4o). This enables the selection of the op- timal moall-model and sampling strategy combination, en- suring high-quality responses at minimal cost. Unlike prior work with static sampling policies, our router adaptively determines the number of samples (and hence the compute allocation) needed for a small model to match the quality of the reference large model at the lowest cost. The overall routing framework is illustrated in Figure 1. Experiments on large-scale, real-world datasets (Section 5) demonstrate that our method achieves up to 60% cost reduction with less than % performance degradation, significantly improving upon prior routing techniques and contributing toward more efficient LLM service deployment.
Our work provides a robust solution for both L.M service providers and end-users mnd-users, offering a flexible framework that balances cost and performance. By leveraging adaptive routing and test-time optimization, we advance the field of cost-efficient LLM inference, enabling broader accessibility and adoption of LLM-backed applications.
2. Related Work
Efficient Machine Learning (ML) Inference. Large lan- guage models (LLMs) have revolutionized natural language processing and related fields, offering remarkable effec- tiveness and generalizability. However, their increasing size comes at the cost of significant computational de- mands and prohibitive expenses for both training and de- ployment (Treviso et al., 2023; Bender et al., 2021). To address inference costs, prior research has focused static efficiency optimizations such model pruning (Hassibi et al., 1993; LeCun et al., 1989), quantization (Jacob et al., 2018; Vanhoucke et al., 2011), knowledge distillation (Hin- ton et al., 2015; Urban et al., 2016), and neural architecture search (Elsken et al., 2019; Zoph & Le, 2016). While these techniques produce smaller, lower-cost models, they offer fixed trade-off's between accuracy and efficiency, limiting their adaptability. Given that LLMs are expected to serve wide range of tasks with varying accuracy and cost con- straints, dynamic optimization approaches are essential to
The main contributions of this work are: 1) Cost-efficient router design: We propose query difficulty-aware routing framework that allocates computational resources dynam- ically to achieve effective cost-accuracy trade-offs while
2

---

BEST-Route: Adaptive LLM Routing with Test-Time Optimal Compute
enable more flexible and cost-effective inference (Ding et al., 2022; 2025).
text generation. Model Cascades (Chen et al., 2023; Gupta et al., 2024; Yue al., 2023) performs inference by sequen- tially calling LLMs with effective post-hoe deferral rules based on either the confidence scores or answer consistency of weaker I.LMs. More recently, a line of work studies how to combine the capacity from different LLMs to fur- ther improve response quality. Mixture-of-Agent (Wang et al., 2024b) leverages the collective strengths of multiple LLMs by introducing layered architecture where agents iteratively refine responses. PackLLM (Mavromatis et al., 2024) introduces test-time fusion approach that minimizes perplexity to determine the contribution of each model in a weighted ensemble. However, these approaches typically call more than one LLM for a single query and can incur significant computational overheads.
LLM Routing. LLM routing has become an effective ap- proach to provide dynamic optimization among multiple LLMs by striking good balances between overall response quality and incurred costs. In Ding et al. (2024); Ong et al. (2024), authors propose effective routing strategies to dynamically allocate queries between one strong-ands expensive LLM and one weak-yet-cheap LLM to reduce inference costs while maintaining high performance. Recent work extends the binary routing framework to accommo- date a large set of LLMs. Srivatsa et al. (2024) investi- gates the feasibility of routing queries to the most suitable L.MM from a selected set of models based on input features. FORC (Sakota et al., 2024) predicts the cost and perfor- mance of multiple LLMs using a meta- meta-model and assigns queries to suitable models for optimized cost-performance trade-offs. ZOOTER (Lu et al., 2023) uses reward models to route queries to the most suitable LLMs, achieving high accuracy and reduced computational overhead. While ef- fective, these routing approaches cannot utilize additional compute enhance the performance of smaller, lower-cost models, particularly when the performance gap between models is substantial.
3. Problem Formulation
3.1. Motivation
Varying Query Difficulty. Queries naturally vary in dif- ficulty according to their complexity, ambiguity, and task requirements. For example, a query like "Rewrite the sen- tence so that it's in the present tense -Shee had worked at the company for the past 3 years'." is straightforward and can be accurately resolved by a smaller or less capable model. In contrast, more complex query like "Can you summarize the implications of quantum entanglement on secure commu- nication?" ?" requires nuanced understanding and reasoning, demanding the capabilities of a larger, more powerful model or additional test-time compute resources such as sampling multiple responses. In Ding et al. (2024); Ong et al. (2024), authors demonstrate that complex or ambiguous tasks bene- fit from the broader knowledge and reasoning capabilities of larger models, and therefore difficult queries can be routed to larger and more capable LLMs to maintain response qual- ity, while easy queries can be served by smaller L.MSs to achieve significant cost savings.
Test Time Optimal Compute. Test-time optimal compute techniques (Snell et al., 2024) such as best-of-n sampling is effeetive for improving outcomes on challenging queries. These methods allow the model to explore multiple poten- tial responses, increasing the likelihood of generating high- quality answers. In Brown et al. (2024), the authors observe that increasing the number of sampled responses boosts the probability of finding correct solutions for hard queries, es- pecially in tasks like coding and mathematics. Similarly, Chen et al. (2024a) finds out that increasing the number of LLM calls improves performance on "easy" queries and highlights the importance of adapting compute strategies to query difficulty. More recently, Gui et al. (2024); Jinnai et al. (2024) demonstrates the effectiveness of best-of-n sampling for aligning I.IM outputs to human preferences by selecting the best response among multiple samples. However, this line of work primarily focuses on scaling the test-time com- pute of a single LLM,, missing the opportunity of harnessing the respective strengths of multiple models.
Sub-optimal Model Utilization. While several works have explored leveraging query difficulty variation by rout- ing queries to appropriate models, they face limitations that prevent them from fully utilizing available LLM infrastruc- ture for maximum gains. Many approaches focus solely on routing between two models -oneels--neaae small and one large (Kag et al., 2022; Ding et al., 2024; Ong et al., 2024). This is a reasonable starting point, as the binary case is easier to analyze, and early LLM inference platforms offered only a limited selection of models. However, with platforms like Hugging Face (HuggingFace) now providing diverse range of LLMs across the cost-quality spectrum, routing across all available models is crucial for achieving the best trade-off.
Other Multi-LLM Inference Techniques. Speculative decoding (Leviathan et al., 2023; Kim et al., 2023; Chen et al., 2024b; Narasimhan et al., 2024) speeds up decoding of expensive LLMs by invoking small decoders on the "easy" decoding steps. Unlike LLM routing, which optimizes query traffic distribution among multiple I.LMs to balance cost and performance, speculative decoding solely focuses on accelerating the decoding process within single expensive model by mitigating the inefficiencies of auto-regressive
While some works (Šakota et al., 2024; Shnitzer et al., 2023; Srivatsa et al., 2024) attempt route among more than
3

---

BEST-Route: Adaptive LLM Routing with Test-Time Optimal Compute
Two models, they often fail to fully utilize smaller models, frequently defaulting querying the largest model. Our experiments in Section 5 confirm this trend. A common technique for enhancing moall-mddel response quality is best-of-n sampling, where multiple responses are gener- ated, and the best one is selected (Stiennon et al., 2020; Nakano et al., 2021). However, prior approaches are often too costly and time-consuming for real-time inference due to the extensive usage of large (LLM-based) reward models (Lambert et al., 2024). To address this, we first develop a low-cost best-of-n sampling method to enhance small- model response quality at inference time. We then train a router to select the optimal model and number of responses, achieving the best quality at the lowest cost.
etary expenses. While FLOPs offer a serdware-indeeendee measure, they do not always correlate well with practical concerns like wall-clock latency, energy usage, or finan- cial costs, which are more relevant to end users (Dao et al., 2022). For LLM service users, inference costs primarily consist of input and output token expenses, calculated by multiplying the respective token counts by their unit prices (see Table 6). In this work, we quantify inference costs in USD and also report the latency of our routing framework as part of our evaluation.
4. Routing Framework
We first develop a memory efficient approach for best-of-n sampling from LLLMs and then design a router that selects the appropriate LLM and number of samples for each query,
3.2. Problem Setting
We propose a routing framework for efficiently serving user queries using multiple large language models (LLMs) with varying cost and quality, such as those offered by popular LLM serving platforms (HuggingFace; OpenAI, b). Our system consists of a powerful reference model, Mer (e.g., GPT-40), and a set of smaller, more cost-efficient models, M. Given a query g. we can directly return one response from Met or return the best-of-n n responses from a model in M. A router must efficiently select the model and sample count to minimize inference costs while preserving response quality near that of Mief, with minimal added latency/cost overheads. It is worth noting that we always route each query to single LLM during inference rather than employ- ing an ensemble (Jiang et al., 2023) or cascade (Chen et al., 2023), both of which involve multiple LLM calls per query and can lead to substantial computational overheads.
4.1. Memory Efficient Best-of-n Sampling
Best-of-n sampling (Stiennon et al., 2020; Nakano et al., 2021; Gui et al., 2024; Brown et al., 2024) enhances LLM response quality by generating n candidates and selecting the best, leveraging output variability to better align with quality expectations. A straightforward option for best-of-n sampling is to score each response using human evaluators or Ludee systems (Zheng et al., 2023), but inte- grating human scorers is impractical for real-time inference, and LLM-based scoring adds substantial compute and mem- smaller proxy reward model
ory costs. Instead, to approximate these costly scoring methods and efficiently select the best response.
Given an input query 4. and n responses s1 s1 Ror sg)) denote the ground truth quality score of a response 8, obtained via an expensive scoring approach such as human or LLM-as-a-judge scoring and let Reraay (q. sq)) denote the score from the proxy reward model. We will use the notation R Rerasy (s(g) for brevity.
obtained from the same LLM, let
3.3. Evaluation Metric
Response Quality. Automatically evaluating text genera- tion remains a challenging and extensively researched prob- lem. Traditional metrics like BLEU and ROUGE, origi- nally developed for machine translation and summarization, often exhibit weak alignment with human judgment and have limited applicability across diverse NLP tasks (Blagec et al., 2022). Recent studies (Jiang et al., 2023; Wang et al., 2024a) suggest that LLMs, when properly prompted or fine- tuned, can provide more -llinned evaluations. In this work, we adopt armoRM (Wang et al., 2024a), a fine-tuned Llama3-8B model, to assess response quality. armoRM ranks highly on advanced evaluation model benchmarks (Lambert et al., 2024) and, due to its relatively small size (8B), enables feasible large-scale evaluation. We also inde- pendently demonstrate the effectiveness of armoRM scores in Appendix C.
We aim to select the best out of n responses as per the ground truth reward RcT()(g)). Thus, if the ordering of responses is preserved under the proxy model i.e. Reroxy (s)( > Reonyy (s)(g) whenever Rer(s:(g)) Rar(>;(g)) then it can be used for best-of-n sampling.
Since we only want the proxy model to preserve the rank- ing of responses, we train Ryroxy by minimizing a pairwise ranking loss on a set P of training pairs constructed as P = ((s,,')|RRr)) (Rr((s) > Rs)(s')) The loss function is
Luak
Σ (E
log (Ronaxy (5) Rypoay(s))) (1)
[P]
where (xx = - is the sigmoid function. The loss formulation is obtained from previous reward modeling work (Ouyang et al., 2022).
1
Inference Cost. The cost of running a model can be mea- sured using various metrics, such as FLOPs, latency, or mon-
4

---

BEST-Route: Adaptive LLM Routing with Test-Time Optimal Compute
Algorithm BEST-Route
Avp. arm ORM score (1)
0.124
Input: Query 9, Maximal sample number n, Match proba- bility threshold 6, Proxy reward model Rproxy' Models (M,,.., Mk), J. Reference model Meti Average output lengths wng.output.eengthh..l Input and output token prices input_token_ www.ttooiieeeeae.... price|
0.122
for best-at--
0.120
turbo
mhisak-b
purput.okeen.priceMMM.
mistral Bx7o
phi-l-mediun
Output: Final response.
ghi 3 mini
/ 1. Compute Match Probabilities:
10
foreach M E (M,,...,, do
for = 1 to do
Figure 2. armoRM score of response selected through best-of-n sampling using our proxy reward model consistently increases.
match_ Brach_prob[[M,22 MultHeeadRouter.peeee wrateet.tteticttcchhccccc M, Mer)
To construct the training set P, we generate n 20 sample responses S = {s1 (1). s2()). ...., (2) for each training query @ E Q and compute (G)( using the armoRM score (Wang et al., 2024a). While armoRM ranks highly on benchmarks like RewardBench (Lambert et al., 2024), our framework supports any LLM or human judge as ground truth. Next, we select three responses per query: worst (Sworst), median (5median), and best (8hes),, and form two pairs: (Sworst: Smedian) and (Smedian Sbeat). We obtain such paris for all queries and aggregate them to form P which is used to train Reeox by minimising Equation (1).
/ 2. Filter and Compute Costs: valid_comb < 0
foreach (M, E match_probb pro.hkpprbbbooo do if pratcchprrbb(MM i)] 2 then
costs[[M, i)] + i x avg output length[M]
x
sutput_token. piieee__r + g.inttt toputttoken.priceAAA
x
valid comb <- valid comb ((M,
/+ 3. Select Optimal Combination: if valid_comb + 0 then (M*, ,x) + arg min (M, costs [ost
Note that n responses from each query can generate (?) pairs but many pairs may have similar quality scores, mak- ing fine-graine grained ranking difficult and hindering training performance. We use only the worst, median, and best responses prioritize pairs with the largest ground truth score differences. Since best-of-n sampling focuses selecting the highest-quality response, minor misclassifica- tions among similar-quality pairs has minimal impact. Our approach ensures that the proxy reward model effectively guides high-quality sampling while reducing training com- plexity.
else
L (M*, 8)) + (Met, 1)
/ 4. Execute sampling Strategy: */
Draw i samples (p., from M for query q and compute small arg max.g Rsrov(()) return small
from the set M and return the best-of-n responses from it using the sampling approach described above. The key intu- ition here is that for many small models, sampling multiple responses and selecting the best often still cheaper than sampling single response from the reference model (see Section 5 for cost breakups). We will describe the router design by first introducing a pair-wise router for routing be- tween two models, then extending it to matrix- of-routers that can route between more than two models, and finally describing our multi-headed router which is a single router that approximates the matrix-of-router while signficantly reducing cost/latency overheads.
During inference, for given query g, we (1) generate n sample responses S = {s) (q), s2(q)...., pute the proxy scores for each sample: (x)) for i == 1,,,..., n, and (3) select the response with the highest proxy score 8* arg max.es Rpooxy()) (s). Figure plots the average armoRM score (ReT) for the best-of-n responses selected by our proxy reward model for the test set (see Section 5) with varying n. The consistent increase in ar- moRM score n increases shows that Rymsky works as expected. In particulari it is not seen to suffer from reward hacking (Skalse et al., 2022) (i.e. poor correlation with RGT) often seen when optimizing imperfect proxy rewards.
(2) com-
Pair-Wise Router. Given a query q and two candidate inference options-a large reference model Miar (e.g.. GPT- 4o) and a smaller model M (c.g., Llama-3. 1.b)... and a specific value of sampling by generating n samples and then selecting the best using our proxy reward model as,
augment Msnall with best-of-n
4.2. Test-time Optimal LLM Routing
Recall from Section 3.2 that the goal of routing is to select either a powerful reference model Met (c.g., GPT-4o) and return a single response from it, or select a smaller model
$ Amall
arg max Reeaay (s), S= (=1()), s2(g), .......,))))))) (2))
RCS
(2)
5

---

BEST-Route: Adaptive LLM Routing with Test-Time Optimal Compute
We want our router to estimate the likelihood of small being at least as good as Stef, the response from Mret, under the ground-truth reward, RGT. Therefore for each training query q. we generate label
best-of-n sampling strategy against the reference model. Secondly, we identify combinations where the predicted match probability meets exceeds the threshold and com- pute the incurred cost for each valid combination Next, from the valid combinations, we select the one with the smallest estimated cost. If no combination satisfies the threshold, we use the reference model with one single call. Lastly, for the selected model and sampling strategy, we draw the desired number of samples, evaluate them using the proxy reward model, and return the response with the highest proxy score.
(g) = Pr[ (ftr 2 [see)
(3)
Our pair-wise router is trained to minimize the cross entropy loss,
Suirr
Σ (vn(9) (n) + (1- yo log(( Px()))), GE
Q
(4)
where (g) is the probability predicted by the router that the best-of-n response, from Msmall is good single response from Mre for that value of n, termed as match probability.
5. Evaluation
5.1. Evaluation Setup
Matrix-of-Routery Let there be K small models in the set M. We can train K' N distinct pair-wise routers, in our mftrix--ofrooters, Each router predicts the match probabil- ity between smaller model with best-of-n sampling and Met for specific value of (1 S S N).
Dataset. We introduce a large-scale dataset covering diverse tasks, including question answering, coding, and safety evaluation, with examples collected from multiple sources (see Appendix A.1). The dataset consists of 10K instruction examples, split into 8K/IK/IK for training, val- idation, and testing. We evaluate BEST-Route across 8 popular LLMs GPT-40, GPT-3.5-turbo, Llama-3.1-8B, Mistral-7B, Mistral-8x7B, Phi-3-mini, Phi-3-medium, and Codestral-22B by generating 20 responses per example. We further perform out-off distriibbttoon (OOD) evaluation of BEST-Route using MT-Bench (Zheng et al., 2023).
Cost-Efficient Multi-Head Router. Training and deploying K x N separate pair-wise routers is computationally expen- sive. To address this, we propose a cost-efficient multi-head router design.
Specifically, we leverage a shared BERT-style backbone Routerahared encodes the query g into a shared representation h, and train K x N lightweight classification heads Heads,n separately predict:
Router and Proxy Reward Model. We use DeBERTa- v3-small (He et al., 2020) (44M) as the backbone to train our Multi-Head Router, while the proxy reward model is fine-tuned from OpenAssistant RM 2, DeBeRTa-v3-large model (300M). We train both Multi-Head Router and the proxy reward model with the corresponding loss from Sec- tion 4 for 5 epochs and use the validation set to choose the best checkpoints for final evaluation. All inference experi- ments are conducted using paid API access from OpenAl 3, AzureML 4, and Mistral AI 5, while router training and in- ference are performed on an NVIDIA A A100 GPU (80GB RAM). Codes will be released upon acceptance of this work.
(2) = - (W,n hy + bs..) IskSK, 1sn (5)
where (xx) = - is the sigmoid function, W is the weight vector, by,n is the bias term, and (g) denotes the probability that the best-of-n response, from the 4 model in M is as good as single response from Mer for that n.
At inference time, users can set thresholds on Pk.n (4) to balance cost and accuracy. Higher thresholds favor the reference model, improving quality at increased costs. Mul- tiple model and best-of-n combinations can meet given threshold. BEST-Route effectively selects among them using cost estimation to ensure high-quality responses at minimal cost.
Evaluation Metrics. We assess response quality using armoRM scores (Wang et al., 2024a) and measure efficiency based on incurred inference costs, which include input and output token pricing (see Table 6). We also report trained router performance using BLEU and ROUGE in Section 5.5.
Specifically, total cost comprises prompt and response costs, computed as the product of token count and unit token price for inputs and outputs, respectively. Since output length is unknown inference, we estimate it using average training data lengths. We demonstrate that this estimation has low error and can effectively support the development of efficient routing frameworks (see Appendix 1.
Inppt tokens are only charged once because most modern L.Mss support returning multiple responses at once for given query. For example, you can set the "num return sequences" hyper- parameter for HuggingFace LLMs to tune the number of indepen- dently computed returned sequences for each query.
hhttss//lugginggfce.com wtwp://wwwa....oe../////e/emmeee Asstppnnnssstttn/eewarraaa
deberta-v3- --lagee--2
The overall test-time optimal LLM routing framework is as depicted in Algorithm 1. We first use the Multi-Head Router to predict the match probability for each model and
'https///peeai..oo http:///pppaaiicoooa//pa/ppeeeee cow./appppriciig//////////cp
*hups://aaure microsoft. cww/en-
us/pricinng/ddeaall//hhii
6

---

BEST-Route: Adaptive LLM Routing with Test-Time Optimal Compute
0.126
Response Quality Drop (armoRM score)
0.124
9pt-4o
Cost Reduction
w.r.t. always using GPT-4o (%)
armoRM scores (T)
0.122
(%)
N-label
BEST-Route
10
0.63
0.19
20
1.17
0.21
40
3.26
0.47
gpt-35 turbo
0.116
60
5.08
0.80
phi- 3-medium mistral-Bx77b
Nobbel Neclows Claileing BEST-Routa to
0.114
N-class Clustering 0% cost reduction with 0% quality drop.
0.07% cost reduction with 0% quality drop.
phi-3-mini
0.112
mistral-7B 7o
Cost ($ 1K queries)
Table I. Cost reduction v.s. performance drops. Performance drops are computed w.r.t. always using the reference model (GPT-4o).
Figure 3. Routing performance results.
Baselines. We compare BEST-Route against 3 routing baselines from prior work (Srivatsa et al., 2024), includ- ing (1) N-class Routing- a BERT-based router aiming to predict the best LLM for a given input query, (2) N- label Routing- - BERT-based router predicting all capa- ble LLMs and selecting the cheapest one, (3) Clustering- based Routing- fitting K-Means clustering model to query- specific features and routing queries to the optimal LLM corresponding to their assigned cluster. We further consider Model Cascade baselines (Yue et al., 2023) and report re- sults in Appendix B.2. All baseline details are provided in Appendix A.2.
0.126
Random
phi-3 mhiil In-1)
0.124
3 mini In-3)
armoRM scores (t)
0.122
0.120
0.118
0.116
0.114
2 Cost (S 1K queries)
Experiments. We investigate our test-time optimal L.LM routing framework. We evaluate the routing performance in Section 5.2 (Figure 3 and Table 1), validate that the router is indeed adaptively distributing queries between dif- ferent L.LMs to achieve good cost-v.s.-accuracy trade-offs in Section 5.3, demonstrate that our routing framework is of negligible compute overhead in Section 5.4, examine the router generalizability in Section 5.5, show that our cost estimation is of low estimation error in Appendix B.1, and present more performance results compared to model cas- cade baselines in Appendix B.2. Our code is available at https//gghhbbb.oommmmcccco/tt//t
Figure 4. Routing performance between GPT-4o and Phi-3-mini with best-of-n sampling where n = 1,3.
minimal cost savings. Similarly, N-label Routing struggles to reduce costs while preserving response quality, leading to over 5% performance drop at 60% cost reduction.
In contrast, BEST-Route consistently outperforms all base- lines, achieving higher cost reductions with lower perfor- mance degradation. Notably, BEST-Route achieves 60% cost reduction with only a 0.8% quality drop, up to 4.28% better than all baselines (Table 1).
5.2. Router Performance Results
We also examine the impact of best-of-n sampling (Fig- ure 4) by comparing GPT-4o and Phi-3-mini at = 1, 3. The results show that best-of-n sampling significantly en- hances routing performance, achieving better cost-accuracy trade-offs. We further compare BEST-Route with best-of-n sampling for each LLM (Figure 5). Best-of-n offers fixed trade-offs for each model and n pair and often yields lower- quality responses (e.g., 4.9% quality drop for Phi-3-mini, 1. % for LLaMA-3, 1-8B at n = 5). In contrast, BEST- Route offers flexible trade-offs, achieving 20% cost reduc- tion with only 0.21% % quality drop, and 40% cost reduction with 0.47% drop, with the max sampling number n = 5.
We evaluate the effectiveness of routing queries across LLMs with significant performance gaps (Figure 3), with numerical results summarized in Table 1. Routing is in- herently challenging as the reference model (e.g., GPT-4o) dominates for most queries, making cost reduction difficult without sacrificing quality.
Unlike BEST-Route, which enables adaptive cost-accuracy trade-off's through a tunable threshold, N-class Routing and Clustering- based Routing make fixed routing decisions, of- fering no flexibility. As a result, they largely default to using the reference model for nearly all queries, achieving
7

---

REST-Route: Adaptive LLM Routing with Test-Time Optimal Compute
0.126
1ama-31.00 8b
mistral-7 7b
ph-3 min!
proyAAM
mutii heod router
0.124
BEST-Route Overhead
armRRM scores (t)
20.0
0.122
17.5
Average Latency (5) fof best-of-n
besk-off
15.0
0.118
35 turbo
31
12.5
0.116
mixttr ah
mistr
10.0
pri-S-medlium PN--3-mini
0.114
got sia BEST Route
0
2.5
Cost ($ 1K queries)
Figure 5. BEST-Route best-of-n for each single LLM.
Figure Overhead analysis.
opt-4b
Response Quality Drop (armoRM score)
Before Adding Codestra-228
After Addlig Codestra-228
Cost Reduction
w.r.t always using GPT-4o (%)
Usarge (%6)
80-
(%)
N-label
BEST-Route
10
0.88
0.25
26-
20
2.29
0.43
025
575 300 Cost (5/ query)
550
025 359 5.35 3:60
3,25
40
4.41
1.56
Cost ($/ querr)))
5.89
1.59
Figure 6. Model usage before and after adding Codestral-22b coding queries.
N-class Clustering
0% cost reduction with 0% quality drop.
0% cost reduction with 0% quality drop.
Table 3. OOD evaluation on MT-Bench. Performance drops are computed w.r.t. always using the reference model (i.e., GPT-4o).
5.3. Router Validation Results
validate that BEST-Route effectively balances cost and accuracy by adaptively routing queries between small and large models and leveraging specialized models for further gains. We conduct experiments coding queries with GPT-4o, GPT-3.5-turbo, Mistral-8x7b, and the specialized coding model Codestral-222 222b, analyzing cost oos--performanc trade-offs and traffic distribution before and after adding Codestral-
Route primarily selects Mistral-8x7b under strict cost con- straints due to its low cost and reasonable accuracy (see Table the Appendix). As the budget increases, queries shift towards GPT-3.5-turbo and GPT-4o for improved ac- curacy. However, after Codestral-226 is added, significant portion of coding queries is redirected from GPT-3.5-turbe to the specialized model, leading to better cost-performance trade-off's (Table 2). Notably, BEST-Route achieves to 20% cost reduction while exceeding GPT-4o performance (negative response quality drop in Table corresponds to response quality gain over always using GPT-4o). This suggests that query routing can only save cost but also improve performance, consistent with prior findings for the two-model case (Ding et al., 2024).
As shown in Figure 6, when Codestral-22b absent, BEST-
Response Quality Drop (armoRM score)
Cost Reduction
w.t.t always using GPT-4o (%)
(%)
Before
After Adding Codestral-222
Adding Codestral-22b
0.50
-0.10
5.4. Router Latency
20
0.77
-0.50
40
2.67
2.49
We measure the latency of BEST- and compare it with the inference latency of different LLMs. We locally deploy Llama-3.1-8b. Mistral-7b, and Phi-3-mini that we use in our experiments to generate responses to user queries for evaluation purpose. We do not measure the latency of LLM APIs (e.g., GPT-3.5-turbo) because they introduce
5.64
5.11
Table 2. Cost reduction v.s. performance drops on coding queries. Performance drops are computed w.r.t. always using the reference model (GPT-4o).
8

---

BEST-Route: Adaptive LLM Routing with Test-Time Optimal Compute
Cost Reduction
Response Quality Drop w.r.t. always using GPT-4o (%)
BLEU
ROUGE
(%) N-label
BEST-Route
N-label
BEST-Route
10
6.57
3.61
6.10
3.88
20
13.13
6.07
11.65
7.27
40
25,80
12.76
22.26
15.78
60
31.70
18.07
27.62
21.97
N-class Clustering
0.2% cost reduction with 0.7% quality drop.
0.2% cost reduction with 0.9% quality drop.
0% cost reduction with 0% quality drop.
0% cost reduction with 0% quality drop.
Table 4. Routing performance under BLEU and ROUGE. Performance drops are computed w.r.t always using the reference model (i.e., GPT-4o).
additional delays due to network latency and queuing, and inference latency is expected to be significantly higher than that of the router.
6. Limitations
While BEST-Route effectively reduces inference costs while maintaining high response quality, our approach has some limitations that warrant further investigation:
The latency of BEST-Route primarily stems from three com- ponents: (1) match probability prediction by the Multi-Head Router, (2) LLM generation latency for producing n re- sponses, and (3) best-of-n sampling overhead from using the proxy reward model. As shown Figure 7, the routing overhead is negligible compared to LLM inference time. For instance, at n 20, match probability prediction takes 0.04s and best-of-n sampling adds 0.58s, making the total overhead 18.7x faster than the fastest LLM (Llama-3.1 1-8b). Moreover, increasing n has only a marginal impact on over- all latency. As n grows from 1 to 20, LLM generation latency increases by just 30% for Phi-3-mini, 53.7% for Mistral-7b, and 59.3% for Llama-3. 1-8b, demonstrating the efficiency of our best-of-n sampling strategy.
Dependency on Proxy Reward Model Accuracy. Our best- of-n sampling strategy relies on the proxy reward model to rank generated responses effectively. Although our ex- periments demonstrate strong aligmment between the proxy model and ground-trui evaluations, potential misalignment in certain cases may result in suboptimal response selection.
Scalability to Extremely Large Model Pools. While BEST- Route extends routing beyond binary selection to diverse set of models, its effectiveness in handling extremely large model pools (e.g.. hundreds of LLMs) remains unexplored. Efficiently scaling our router design to such a vast space may require additional optimizations.
5.5. Router Generalizability
7. Conclusion
To investigate the generalizability of BEST- eval- uate the trained routers on the -uttof-diitribution (OOD) dataset - MT-Bench (Zheng et al., 2023), and more metrics (e.g., BLEU and ROUGE) in addition to armoRM scores.
In this work, we introduced BEST-Route, novel frame- work for adaptive LLM routing that optimizes inference costs while maintaining high response quality. Our approach combines a cost-efficient routing strategy with test-time opti- mal compute through best-of-n sampling, enabling dynamic model selection tailored to query difficulty. Through ex- tensive evaluations real-world datasets, we demonstrate that BEST-Route achieves up to 60% cost reduction with less than 1% performance drop, significantly outperforming prior routing frameworks. Our multi-head router design allows for -ne-grained trade-offs between accuracy and ef- ficiency, while our cost-aware best-of-n sampling strategy further enhances response quality without unnecessary com- putational overhead. Our findings suggest that BEST-Route provides flexible and effective solution for cost-efficient LLM inference, paving the way for more accessible and adaptive LLM services.
As shown in Table 3, BEST-Route consistently outperforms all baselines on MT-Bench. For example, it achieves 60% cost reduction with only a 1.59% performance drop - up to 4.3% better than the strongest baseline. In contrast, N-class and clustering-based routing often default to using GPT-4o, yielding minimal cost savings, while N-label routing suffers notable quality drops especially at high cost reduction rates. Similarly, as shown in Table 4, we observe that BEST-Route consistently achieves better trade-off's than all baselines under both BLEU and ROUGE (e.g.. N-label routing has up to 31.7% BLEU drop 60% cost reduction, vs. only 18.07% drop for BEST-Route). These results demonstrate the robustness of BEST-Route under distribution shifts and generalizability to alternative quality metrics.
9

---

BEST-Route: Adaptive LLM Routing with Test-Time Optimal Compute
Acknowledgements
Chuang, Y.-S., Fang, W., Li, S.-W., Yih, W.-t,, and Glass, J. Expand, rerank, and retrieve: Query reranking for open-domain question answering. In Findings of the Association for Computational Linguistics: ACL 2023,
The authors would like to thank Yizhu Jiao, Xuefeng Du, Hao Kang, Yinfang Chen, Ruomeng Ding, and Wenyue Hua for helpful discussions.
pp. 12131-12147, 2023.
Impact Statement
Dao, T., Fu, D., Ermon, S., Rudra, A., and Ré, C. Flashat- tention: Fast and memory-effiieen exact attention with io-awareness. Advances Neural Information Process- ing Systems, 35:16344-16359 2022.
This paper presents work whose goal is to advance the field of Machine Learning. There are many potential societal consequences of our work, none which we feel must be specifically highlighted here.
Ding, D., Amer- Yahia, S., and Lakshmanan, L. On effi- cient approximate queries over machine learning models. Proceedings of the VLDB Endowment, 16(4):918-9)) 2022.
References
Abdin, M., Aneja, J., Awadalla, H., Awadallah, A., Awan,
A. A., Bach, N., Bahree, A., Bakhtiari, A., Bao, J., Behl, H., et al. Phi-3 technical report: A highly capable lan- guage model locally on your phone. arXiv preprint arXiv:2404. 14219, 2024.
Ding, D., Mallick, A., Wang, C., Sim, R., Mukherjee, S., Rühle, V., Lakshmanan, L. V., and Awadallah, A. H. Hy- brid 11m: Cost-efficient and quality-aware query routing. In The Twelfth International Conference on Learning Representations, 2024.
Bafna, P., Pramod, D., and Vaidya, A. Document cluster- ing: Tf-idf approach. 2016 International Conference on Electrical, Electronics, and Optimization Techniques (ICEEOT), pp. 61-66. IEEE, 2016.
Ding, D., Xu, B., and Lakshmanan, V. Occam: Towards cost-efficient and accuracy- aware classification inference. In The Thirteenth International Conference on Learning Representations, 2025.
Bender, E. M., Gebru, T., McMillan-Majoo A., and Shmitchell, S. On the dangers of stochastic parrots can language models be too big? In Proceedings of the 2021 ACM Conference Fairness, Accountabilityy and Transparency, pp. 110-623, Virtual Event Canada, March 2021. ACM. ISBN 978-1-4503-8309-7. doi: 041145734421888344455222 URL https::t///t/. //ll.//.//////// acm. org/doi/100 111111111155334211111 .1..2218888444999 3445922.
Dubey, A., Jauhri, A., Pandey, A., Kadian, A., Al-Dahle, A., Letman, A., Mathur, A., Schelten, A., Yang, A., Fan, A., et al. The llama 3 herd of models. arXiv preprint arXiv:2407.21785 2024.
Elsken, T., Metzen, J. H., and Hutter, F. Neural architecture search: A survey. The Journal of Machine Learning Research, 20(1):1997-2017, 2019.
Blagec, K., Dorffner, G., Moradi, M., Ott, S., and Samwald, M. A global analysis of metrics used for measuring per- formance in natural language processing, arXiv preprint arXiv:2204. 12220..1155 11574, 2022.
Gui, L., Gârbacea, C., and Veitch, V. Bonbon alignment for large language models and the sweetness of best-of-n sampling. arXiv preprint arXiv:2406.00832. 2024.
Brown, B., Juravsky, J., Ehrlich, R., Clark, R., Le, Q. V., Ré, C., and Mirhoseini, A. Large language monkeys:
Gupta, N., Narasimhan, H., Jitkrittum, W., Rawat, A. S.,
Menon, A. K., and Kumar, S. Language model cascades: Token-level uncertainty and beyond. arXiv preprint arXiv:2404.10133 2024.
Scaling inference compute with repeated sampling. arXiv preprint 2rXiv:2407.21787 2024.
Chen, L., Zaharia, M., and Zou, J. Frugalgpt: How to use large language models while reducing cost and improving performance. arXiv preprint S.Ki::2305.0176 2023.
Hassibi, B., Stork, D. G., and Wolff, G. J. Optimal brain surgeon and general network pruning. In IEEE interna- tional conference on neural networks, pp. 293-299, IEEE, 1993.
Chen, L.. Davis, J. Q.. Hanin, B., Bailis, P., Stoica, I., Za- haria, M., and Zou, J. Are more IIm calls all you need? towards scaling laws of compound inference systems. arXiv preprint arXivv2403.024111 2024a.
He, P., Liu, X., Gao. J., and Chen, W. Deberta: Decoding- enhanced bert with disentangled attention. arXiv preprint arXiv:2006.0366 2020.
Chen, Z., May, A., Svirschevski. R., Huang, Y., Ryabinin, M., Jia, Z., and Chen, B. Sequoia: Scalable, robust, and Hurdware-aware speculative decoding. arXiv preprint arXiv:2402.12331 12374, 2024b.
Hinton, G., Vinyals, O., Dean, J., et al. Distilling the knowledge in a neural network. arXiv preprint arXiv: A503:/5003.2255 503303331..,..0 2(7), 2015.
10

---

BEST-Route: Adaptive LLM Routing with Test-Time Optimal Compute
HaggingFace. Hugging face inference api. https:// buggingface. wttp:/naaa.c..eoeeeeeeeeeeeeeeee wwweeeecooiooeeeeeeeeeeeee
Mavromatis, C., Karypis, P., and Karypis, G. Pack of Ilms: Jacob, B., Kligys, S., Chen, B., Zhu, M., Tang, M., Howard, A. Adam, H., and Kalenichenko, D. Quantization and training of neural networks for efficient integer- arithmetic-only inference. In Proceedings of the IEEE conference on computer vision and pattern recognition, pp. 2704-2713, 2018.
Model fusion test-time via perplexity optimization. arXiv preprint arXiv:2404. 11531, 2024.
Nakano, R., Hilton, J., Balaji, S., Wu, J., Ouyang, I.., Kim, C., Hesse, C., Jain, S., Kosaraju, V., Saunders, W., et al. Webgpt: Browser-assisted question-answering with hu- man feedback. arXiv preprint arXiv:2112.09332 2021.
Narasimhan, H., Jitkrittum, W., Rawat, A. S., Kim, S., Gupta, N., Menon, A. K., and Kumar, S. Faster cascades via speculative decoding. arXiv preprint 17Xiv:2405.19261 2024.
Jiang, D., Ren, X., and Lin, B. Y. Lim-blender: Ensembling large language models with pairwise ranking and genera- tive fusion. arXiv preprint arXiv:2306.0255
2023.
Ong, I,, Almahairi, A., Wu, V., Chiang, W.-L., Wu, T., Gon- zalez, J. E., Kadous, M. W., and Stoica, I. Routellm: Learning to route Ilms with preference data. arXiv preprint arXiv:2406. 2024.
Jinnai, Y., Morimura, T., Ariu, K., and Abe, K. Reg- ularized best-of-n sampling to mitigate reward hack- ing for language model alignment. arXiv preprint arXiv:2404.01054, 2024.
OpenAI. Chatgpt. https: / /ctttcaaaaccccc opw.ai.enna............. com/,
Kag, A., Fedorov, I., Gangrade, A., Whatmough, P., and Saligrama, V. Efficient edge inference by selective query. In The Eleventh International Conference on Learning Representations, 2022.
OpenAl. Openai platform. htttps://platee
b.
Ouyang, L., Wu, J., Jiang, X., Almeida, D., Wainwright, C., Mishkin, P., Zhang, C., Agarwal, S., Slama, K., Ray, A., et al. Training language models to follow instructions with human feedback. Advances in neural information processing systems, 35:27730-2777 27744, 2022.
Kim, S., Mangalam, K., Moon, S., Malik, J., Mahoney, M. W., Gholami, A., and Keutzer, K. Speculative decod- ing with big little decoder. In seieth- Conference on Neural Information Processing Systems, 2023.
Lambert, N., Pyatkin, V., Morrison, J., Miranda, L., Lin, B. Y., Chandu, K., Dziri, N., Kumar, S., Zick, T., Choi, Y., et al. Rewardbench: Evaluating reward models for language modeling. arXiv preprint 13377 2024.
Papineni, K., Roukos, S., Ward, T., and Zhu, W.-. Bleu: a method for automatic evaluation of machine transla- tion. In Proceedings of the 40th annual meeting of the Association for Computational Linguisties, pp. 311-318, 2002.
Šakota, M., Peyrard, M., and West, R. Fly-swat or cannon? cost-effective language model choice via meta-modeling. In Proceedings of the I 17th ACM International Conference on Web Search and Data Mining, pp. 606-615, 2024.
Langley, P. Crafting papers machine learning. In Langley, P. (ed.), Proceedings of the 17th International Conference on Machine Learning (ICML 2000), pp. 1207-1216, Stan- ford, CA, 2000. Morgan Kaufmann.
Shnitzer, T., Ou, A., Silva, M., Soule, K., Sun, Y., Solomon, J., Thompson, N., and Yurochkin, M. Large language model routing with benchmark datasets. arXiv preprint arXiv:2309. 2102239999779. 2023.
LeCun, Y., Denker, J., and Solla, Optimal brain damage. Advances in neural information processing systems, 2, 1989.
Leviathan, Y., Kalman, M., and Matias, Y. Fast inference from transformers via speculative decoding. In Inter- national Conference on Machine Learning, pp. 19274- 19286. PMLR, 2023.
Skalse, J., Howe, N., Krasheninnikov, D., and Krueger, D. Defining and characterizing reward gaming. Advances in Neural Information Processing Systems, 35:9460-9471, 2022.
Lin, C.-Y. Rouge: A package for automatic evaluation of summaries. In Text summarization branches out, pp. 74-81, 2004.
Snell, C., Lee, J., Xu, K., and Kumar, A. Scaling Ilm test- time compute optimally can be more effective than scal- ing model parameters. arXiv preprint arXiv:2408.03314, 2024.
Lu, K., Yuan, H., Lin, R., Lin, J., Yuan, Z., Zhou, C., and Zhou, Routing to the expert: Efficient reward- guided ensemble of large language models. arXiv preprint OrXiv:23/1.0000 1.8692, 2023.
Srivatsa, K., Maurya, K. K., and Kochmar, E. Harnessing the power of multiple minds: Lessons learned from 1lm routing. arXiv preprint arXiv:2405.004 00460 2024.

---

BEST-Route: Adaptive LLM Routing with Test-Time Optimal Compute
Stiennon, N., Ouyang, L.,, Wu, J., Ziegler, D., Lowe, R., Voss, C.,, Radford, A., Amodei, D., and Christiano, P. F. Learning to summarize with human feedback. Ad- vances in Neural Information Processing Systems, 33: 3008-3021, 2020.
Zhao, W. X., Zhou, K., Li, J., Tang, T., Wang, X., Hou, Y.,
Min, Y., Zhang, B., Zhang, Dong, Z.., et al. A survey of large language models. arXiv preprint arXiv:2303.18223, 2023.
Zheng, L., Chiang, W.-L., Sheng, Y., Zhuang, S., Wu, Z., Zhuang, Y., Lin, Z.,, Li, Z., Li, D., Xing, E., al. Judging ilm-as-a-judge with mt-bench and chatbot arena. arXiv preprint arXiv:2306.00 056805 2023.
Treviso, M., Lee, J.-U., Ji, T., Aken, B. v., Cao, Q. Ciosici, M. R., Hassid, M., Heafield, K., Hooker, S., Raffel, C., et al. Efficient methods for natural language processing: survey. Transactions of the Association for Computa- tional Linguistics, 11:22--60,, 2023.
Zoph, B. and Le, Q. V. Neural architecture search with reinforcement learning. arXiv preprint 1rx1v:161..0157.
2016.
Urban, G., Geras, K. J., Kahou, S. E., Aslan, O., Wang. S., Caruana, R., Mohamed, A., Philipose, M., and Richard- son, M. Do deep convolutional nets really need be deep and convolutional? arXiv preprint arXiv:1603.00 2016.
Vanhoucke, V., Senior, A., and Mao, M. Z. Improving the speed of neural networks on cpus. 2011.
Wang. H., Xiong, W., Xie, T., Zhao, H., and Zhang, T. Inter- pretable preferences via multi-ohjective reward modeling and mixture- offexeerss. arXiv preprint arXiv:2406. 12845, 2024a.
Wang, J., Wang, J., Athiwaratkun, B., Zhang, C., and Zou, Mixture-of-agent enhances large language model capabilities. arXiv preprint arXiv:2406. 04692, 2024b.
Wang, X.. Wei, J., Schuurmans, D., Le, Q. V., Chi, E. H., Narang, S., Chowdhery, A., and Zhou, D. Self- consistency improves chain of thought reasoning in lan- guage models. In The Eleventh International Conference on Learning Representations, 2023.
Yu, G.-L,, Jeong, J. S., Kim, G.-W., Kim, S., and Chun, B.- G. Orca: A distributed serving system for (Transformer- Based} generative models. In 16th USENIX Symposium on Operating Systems Design and Implementation (OSDI 22). pp. 521 11185588222 2022.
Yue, M., Zhao, J., Zhang, M., Du, L.,, and Yao, Large language model cascades with mixture of thoughts rep- resentations for cost-efficient reasoning. arXiv preprint arXiv:2310.033094, 2023.
Zhang, S., Zhang, J., Ding, D., Garcia, M. H., Mallick, A., Madrigal, D., Xia, M., Rühle, V., Wu, Q., and Wang, C. Ecoact: Economic agent determines when to register what action. arXiv preprint arXiv:241 2..0:6431,,,,3, 2024a.
Zhang, S., Zhang, J., Liu, J., Song. L., Wang. C., Krishna, R., and Wu, Q Offline training of language model agents with functions as learnable weights. In Forty-first Inter- national Conference on Machine Learning, 2024b.
12

---

BEST-Route Adaptive LLM Routing with Test-Time Optimal Compute
Scenario
Source
# Examples
Question Answering
MixInstruct
6,000
Coding
RewardBench
984
2K total
CodeUltraaFeedback
1,016
Safety
RewardBench
740
2K total
BeaverTails
1,260
Total
Mix
10,000
Table 5. Dataset statistics. It contains 10K examples and we randomly split the dataset into train/dev/test in 8K/IK/IK sizes.
Inputs
Outputs
Model
($/1M Tokens)
(S/IM Tokens)
GPT-4o
5
15
GPT-3.5-turbo
3
Llama-3.1-4
0.3
0.61
Mistral-7b
0.25
0.25
Mistral-8x7b
0.7
0.7
Phi-3-mini
0.3
0.9
Phi-3-medium
0.5
1.5
Codestra-22b
Table LLM input and output token prices.
A. Experiment Details
A.1. Dataset
We introduce new dataset to evaluate the effectiveness of different routing strategies across wide range of tasks (e.g.. question answering, coding, safety evaluation). We collect a large-scale set instruction examples primarily from four sources, as shown in Table 5. The broad range of tasks in the dataset enables us to train generic routing framework that will be effective across different scenarios. We sample 8K examples for training, 1K for validation, and 1K for testing, We then run K popular LLMs GPT-4o, GPT-3.5-turbo, Llama-3.1-8h Mistral-7b, Mistral-8x7b, Phi-3-mini, Phi-3-medium, and specilized coding model Codestral-22b to generate 20 responses these 10k examples.
A.2. Baselines
We consider three baselines from previous L.M routing work in the main evaluation section.
1. N-class Routing. BERT-based router aiming to predict the best L.M for given input query.
2. N-label Routing (Srivatsa et al., 2024). Similarly, a BERT BERT-based router aiming to predict all LLMs capable for a given input query and selecting the cheapest LLM there are multiple candidates.
3. Clustering- blusee Routing (Srivatsa et al., 2024). We apply K- K-Means clustering model to query-speciff features extracted from the training data using TF-IDF vectorizer (Bafna et al., 2016) to identify discrete clusters. For each cluster in the training set, the most effective LLM is selected. During inference, test set queries are routed to the optimal I.IM corresponding to their assigned cluster. We choose K = 50 by default as suggested in (Srivatsa et al., 2024).
We further compare BEST-Route with Model Cascades (Yue et al., 2023) to further demonstrate the effectiveness of our approach. Results are summarized in Appendix B.2. Specifically, Model Cascades ranks all LLMs based on their average inference costs on the training data, which are calculated as the sum of the prompt cost and the average response cost. For each LLM in the cascade, we sequentially sample K responses and stop once the most consistent response i* achieves a consistency score above predefined threshold, The consistency score for a response E [K] defined as the average of
13

---

BEST-Route: Adaptive LLM Routing with Test-Time Optimal Compute
Estimation Error
Model
($ ($/ query)
GPT-4o
0.0027
GPT-3.5-turbo
0.0006
Llama-3.1-8b
0.0001
Mistral-7b
0.0001
Mistral-8x7b
0.0001
Phi-3-mini
0.0002
Phi-3-medium
0.0003
Codestra-22b
0.0004
Table 7. LLM response cost estimation error.
gpt-4o
armoRM scores (1)
0.120
0.118
aut-33--urbe
0.116
Ilma 31.
phi-a-medlum
Cascading (exart matchi
0.114
Cascading (bleu]
phi-3 mini mistral-7b
Casccading (souge)
0.112
* BEST-Rous
6 Cost (S/ queries)
10
12
Figure 8. Routing performance results compared to model cascades baselines.
the agreement function values between i and [K]. expressed
consistency(f: = K
Σ jE[K]
funce,func(i,]] j).
Following (Yue al., 2023), K and measure consistency using three agreement functions: exact_match, BLEU (Papineni et al., 2002), and ROUGE (Lin, 2004) scores. The most consistent response, i", is determined
arg max; consistency(i) for i E K.
B. Additional Experiments
B.1. Response Cost Estimation
In BEST-Route, estimate the incurred response for given LLM and best-of-n sampling strategy. The response costs can be computed by multiplying the number of output tokens the unit output token prices (see Table 6). We use the average number of output tokens from the training split as the output length estimator for each L.LM to estimate the cost. We validate that our response cost estimation is of low error and hence can be used to effectively distinguish LLMs at different cost levels for given queries (see Table 7). Specifically, the average estimation error for each query is less than $0.003 for all LLMs and as low as $0.0001 for Llama-3. 1-188,, Mistral-7b, and Mistral-8xy -b77,, which demonstrates the robustness of our cost estimation.
B.2. Performance Results Compared to Model Cascades
We compare BEST-Route with Model Cascades (Yue et al., 2023) to further demonstrate the effectiveness our approach. Results are summarized in Figure and Table All cascading approaches ineur significantly higher costs to deliver equally
14

---

BEST-Route: Adaptive LLM Routing with Test-Time Optimal Compute
Cost Reduction
Response Quality Drop (armoRM score) w.r.t always using GPT-4o (%)
Cascading (exact (exact_match)
Cascading (BLEU)
Cascading (ROUGE)
(%)
BEST-Route
10
7.26
5.60
6.10
0.19
20
7.26
5.69
6.22
0.21
40
7.26
6.23
6.90
0.47
60
7.26
6.61
7.02
0.80
Table Cost reduction v.s. performance drops with model cascades baselines. Performance drops are computed w.r.t. always using the reference model (GPT-4o).
good responses compared to the reference model, due its cascading design which triggers more than one LLMs resolve given query. Similarly, BEST-Route outperforms all model cascades baselines by delivering higher quality responses while achieving higher cost savings. Specifically, BEST-Route achieves 60% cost reduction with 0.8% quality drop, which is up to 6.46% better than all cascading-based routers.
C. arrmoRM Score A Case Study
armoRM score (Wang et al., 2024a) a comprehensive response quality metric that aggregates 19 evaluation perspectives, including Helpfulness, Correctness, Coherence, and Verbosity. constructed by collecting ground truth ratings for each perspective, followed by normalization, de-biasing, and weighted summation into a unified score ranging from -1 to 1.
A small armoRM score increase can reflect meaningful improvements across multiple quality dimensions, as illustrated in the following example.
Query: Is it normal to have fever when I'm sick?
Response (armoRM 0. 112): Yes, having fever when you' sick often cates that your body is fighting off infection illness. Fever is natural defense mechanism whereby your body's s temperature increases to create an environment less conducive for pathogens to multiply.
Response 2 (armoRM 0.127): Yes, it is common to have a fever when you' re sick. A fever is your body's natural response to fighting off an infection. It indicates that your immure system is actively working to fight the pathogens causing the illness. However, if your fever is above 101 (38.3%C) and persists for more than couple of days, it's good idea to seek medical advice to ensure there isn't a more serious underlying condition.
Both Response I and 2 cover the perspective that "fever is natural defense mechanism". However, Response 2 further enriches the argument by discussing the potential danger of persisting high fever and suggests to users to seek medical advice in such cases, which could be life-critical in healthcare consultations and is missing from Response
15


Reviews:
[{"review_id": "XxEdj053jd", "reviewer": "Reviewer_ewCv", "summary": "The paper introduces BEST-Route, an adaptive routing framework designed to optimize inference efficiency and response quality in large language models (LLMs). The framework dynamically selects an appropriate LLM and determines the optimal number of responses to sample (best-of-n sampling) based on the estimated difficulty of individual queries. It builds on the observation that combining multiple responses from smaller, more cost-effective models, along with a lightweight proxy reward model to select the best response, significantly enhances quality while often being more economical than consistently using larger, costly models.\n\nMain contributions of the paper are:\n* Introduces a dynamic multi-head router that adaptively assesses query difficulty to efficiently allocate computational resources, optimizing the trade-off between inference cost and response accuracy.\n\n* Employs best-of-n sampling to produce multiple candidate responses from smaller models, selecting the highest-quality response through an efficiently trained proxy reward model.\n\n* Empirical evaluations demonstrate that BEST-Route significantly improves inference efficiency, achieving up to 60% cost reduction with less than a 1% decrease in response quality compared to consistently utilizing a state-of-the-art reference model (GPT-4o).", "questions": "", "limitations": "", "rating": 4, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for the thoughtful and constructive comments. Several comments pertain to the generalizability of BEST-Route, and we address them jointly below for clarity.\n\n**Q1: The authors present clear results across diverse tasks, yet the evaluation is primarily conducted on datasets curated specifically for this paper. Additional evidence showing performance consistency on independently curated datasets or real-world deployments could further strengthen the generalizability of their approach.**\n\nA1: Thanks for this comment. We would like to clarify that our dataset is a random sample of multiple public benchmarks such as CodeUltraFeedback [1] and BeaverTails [2], which are independently curated by other parties. That said, to further evaluate generalizability, we test BEST-Route on the out-of-distribution (OOD) benchmark MT-Bench [3], a widely used dataset covering writing, reasoning, fact extraction, and roleplay. Please see A2 below for details.\n\n**Q2: The submission briefly acknowledges potential sensitivity to data drift but does not provide empirical evidence or in-depth analysis regarding the robustness of BEST-Route under changing data distributions. Addressing this gap through empirical evaluation or detailed discussion would be beneficial for supporting practical deployment scenarios.  \nQ3: However, although the dataset provides a valuable evaluation framework across multiple tasks, it doesn't show the generalizability of the approach especially with data drift in real-world cases.**\n\nA2: Thanks for highlighting this. We evaluate BEST-Route on the OOD dataset MT-Bench [3]. As shown in the table below, BEST-Route consistently outperforms all baselines. For example, it achieves 60% cost reduction with only a 1.59% performance drop – up to 4.3% better than the strongest baseline. In contrast, N-class and clustering-based routing often default to using GPT-4o, yielding minimal cost savings, while N-label routing suffers notable quality drops especially at high cost reduction rates. These results demonstrate BEST-Route's robustness under distribution shifts.\n\n|  | Response Quality Drop (armoRM score) | w.r.t. always using GPT-4o (%) |\n|:---:|:---:|:---:|\n| Cost Reduction (%) |     N-label   | BEST-Route |\n| 10 | 0.88 | **0.25** |\n| 20 | 2.29 | **0.43** |\n| 40 | 4.41 | **1.56** |\n| 60 | 5.89 | **1.59** |\n| N-class | N-class achieves 0% cost reduction  | with 0% quality drop. |\n| Clustering | Clustering achieves 0% cost reduction | with 0% quality drop. |\n\nA detailed visualization of quality-v.s.-cost trade-offs achieved by different methods on MT-Bench is provided in Figure 5, accessible via the anonymous [link](https://github.com/BEST-Route2025/BEST-Route/blob/main/README.md#figure-5-routing-performance-results-on-the-ood-dataset-mt-bench).\n\n**Thank you for your time and consideration. We sincerely hope that you find our responses convincing and would consider increasing your rating.**\n\nReferences:   \n[1] Weyssow, Martin, et al. \"Codeultrafeedback: An llm-as-a-judge dataset for aligning large language models to coding preferences.\" arXiv preprint arXiv:2403.09032 (2024).   \n[2] Ji, Jiaming, et al. \"Beavertails: Towards improved safety alignment of llm via a human-preference dataset.\" Advances in Neural Information Processing Systems 36 (2023): 24678-24704.   \n[3] Zheng, Lianmin, et al. \"Judging llm-as-a-judge with mt-bench and chatbot arena.\" Advances in Neural Information Processing Systems 36 (2023): 46595-46623.", "claims_and_evidence": "Supported claims:\n* The paper demonstrates the effectiveness of its multi-head router architecture, supported by comprehensive experiments across a diverse set of real-world tasks.\n* The paper demonstrates the performance gains from utilizing best-of-n sampling on smaller models through detailed quantitative results.\n* Detailed analyses against baseline methods (N-label, N-class, clustering, and cascade methods) support the claim that BEST-Route achieves significant inference cost reductions with minimal impact on response quality\n\nProblematic claims:\n* The authors present clear results across diverse tasks, yet the evaluation is primarily conducted on datasets curated specifically for this paper. Additional evidence showing performance consistency on independently curated datasets or real-world deployments could further strengthen the generalizability of their approach.\n* The submission briefly acknowledges potential sensitivity to data drift but does not provide empirical evidence or in-depth analysis regarding the robustness of BEST-Route under changing data distributions. Addressing this gap through empirical evaluation or detailed discussion would be beneficial for supporting practical deployment scenarios.", "methods_and_evaluation_criteria": "* The proposed BEST-Route framework introduces a novel multi-head routing architecture, integrating best-of-n sampling for smaller models\n* The proposed benchmark dataset covers a range of important application scenarios (e.g., question answering, coding, and safety evaluation)\n* However, although the dataset provides a valuable evaluation framework across multiple tasks, it doesn't show the generalizability of the approach especially with data drift in real-world cases.", "theoretical_claims": "NA", "experimental_designs_or_analyses": "Please see methods section above", "relation_to_broader_scientific_literature": "The paper contributes to the active area of cost-efficient LLM inference by combining adaptive routing techniques with test-time optimal compute strategies.", "essential_references_not_discussed": "NA", "other_strengths_and_weaknesses": "The paper is very well written and easy to follow", "other_comments_or_suggestions": "Update: The provided rebuttal strengthens the paper so I increased my score to 4.", "questions_for_authors": "NA", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "jFV8uUE5DF", "reviewer": "Reviewer_Yhv8", "summary": "This paper proposes BEST-Route, combining two different research areas: model selection (through routing) with adaptive allocation of test-time compute (e.g., best-of-n sampling). Their framework dynamically selects a model and the optimal number of responses to sample based on query difficulty and quality thresholds. Experimental results show up to 60% cost savings with less than 1% performance degradation compared to always using a large model.", "questions": "", "limitations": "", "rating": 4, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "**Q1: The claim “surpassing prior routing approaches and setting a new standard for efficient LLM service deployment” seems too strong. While the method shows clear improvements over prior routing approaches, it would benefit from direct comparisons with other efficiency techniques, such as speculative decoding.**\n\nA1: Thanks for the comment. We will revise the claim to emphasize that our method significantly improves upon prior routing techniques, contributing toward more efficient LLM service deployment. It is worth noting that our approach is orthogonal and complementary to efficiency techniques like speculative decoding [1], which accelerates decoding for expensive models. In contrast, BEST-Route reduces cost by intelligently assigning “easy” queries to small models while maintaining high performance. A hybrid system could combine the advantages of both techniques and could first route queries (via BEST-Route) between cheap and expensive LLMs, and then apply speculative decoding if the expensive model is selected to yield further efficiency gains.\n\n**Q2: Additional discussion is needed on how well BEST-Route generalizes to unseen datasets. Ideally, testing on another dataset would strengthen the results. This is the main weakness of the paper, in my opinion.**\n\nA2: Thanks for this insightful comment. We evaluate the trained routers on the OOD dataset, MT-Bench [2], and observe that BEST-Route achieves strong performance under data distribution shifts (e.g., 60% cost reduction with only 1.59% quality drop). Due to the space limit, please refer to A2 for Reviewer ewCv for details.\n\n**Q3: “The rising costs of LLM inference have”. I get your point but it would be good to provide some examples (e.g., self-consistency, reranking, etc.)**\n\nA3: Thanks for the comment. We will revise the introduction by including examples on “the rising costs of LLM inference”, such as self-consistency [3], which samples multiple reasoning paths and selects the most consistent answer at increased cost, and reranking [4], which generates multiple candidates and uses a re-ranker to select the ones that could lead to better final results at increased inference costs.​\n\n**Q4: “3) Model cascades ( e.g. Chen et al. (2023)) where the query passes through the models sequentially, from the cheapest to the most costly, until a satisfactory response is obtained.”- Not always “until a satisfactory response is obtained”… most cases consider a fixed number of models in the cascade**\n\nA4: Thank you for the comment. We will revise to clarify that, most cascade approaches consider sequentially executing models, until either a satisfactory response is obtained or a pre-defined max number of models of the cascade is reached [5].\n\n**Q5: “... a single response from a small (inexpensive) model was often not good enough to beat a response from a large (expensive) model …” and “small models continue to come up short in terms of response quality when compared to the largest, most powerful models”. While I agree with this, there are cases when this is not the case. For instance, check Table 1 of Farinhas et al. (2025). Even though this is for model cascading and specific for machine translation, I think it’s worth mentioning in Section 2.**\n\nA5: Thank you for pointing this out. We agree and we have independently verified this behaviour in our evaluation. While small models underperform large ones on average, specific cases exist where they perform comparably or even better. Farinhas et al. (2025) observed that though Tower-v2 7B is inferior to its large counterpart Tower-v2 70B on average, it can outperform the large model on 32% cases. This observation motivates routing queries between LLMs to not only save costs but also improve performance. Table 2 in our paper empirically supports this intuition by showing cases where routing achieves significant cost reduction (e.g., 20%) as well as performance improvements (e.g., 0.5%). We will clarify more on this observation in our revision.\n\n**Q6: Typo in L048-049: “development innovative solutions”**\n\nA6: Thank you. We will fix this in the revision.\n\n**Thank you for your time and consideration. We sincerely hope that you find our responses convincing and would consider increasing your rating.**\n\nReferences:  \n[1] Leviathan, Yaniv, et al. \"Fast inference from transformers via speculative decoding.\" ICML 2023.  \n[2] Zheng, Lianmin, et al. \"Judging llm-as-a-judge with mt-bench and chatbot arena.\" NeurIPS 2023.  \n[3] Wang, Xuezhi, et al. \"Self-consistency improves chain of thought reasoning in language models.\" arXiv 2022.  \n[4] Chuang, Yung-Sung, et al. \"Expand, Rerank, and Retrieve: Query Reranking for Open-Domain Question Answering.\" ACL Findings 2023.  \n[5] Chen, Lingjiao, et al. \"Frugalgpt: How to use large language models while reducing cost and improving performance.\" arXiv 2023.  \n[6] Farinhas, António, et al. \"Translate Smart, not Hard: Cascaded Translation Systems with Quality-Aware Deferral.\" arXiv 2025.", "claims_and_evidence": "- The main claim, “Experiments on real-world datasets demonstrate that our method reduces costs by up to 60% with less than 1% performance drop”, is validated empirically on a dataset compiled from existing sources (Table 3).\n\n- The claim “surpassing prior routing approaches and setting a new standard for efficient LLM service deployment” seems too strong. While the method shows clear improvements over prior routing approaches, it would benefit from direct comparisons with other efficiency techniques, such as speculative decoding, as mentioned in the related work.", "methods_and_evaluation_criteria": "The methods and evaluation criteria seem reasonable. However,  if I understood correctly, the router is trained on data that is very similar to the validation and test data (since all splits are sampled from the dataset that they collected). While this is acknowledged as a limitation, additional discussion is needed on how well BEST-Route generalizes to unseen datasets. Ideally, testing on another dataset would strengthen the results. This is the main weakness of the paper, in my opinion.", "theoretical_claims": "NA", "experimental_designs_or_analyses": "See the comments above.", "relation_to_broader_scientific_literature": "The paper combines research on query routing with test-time compute and cites related work properly.", "essential_references_not_discussed": "See below.", "other_strengths_and_weaknesses": "Strengths:  The motivation is well explained, and the topic is important, especially now with the trend of building larger and larger models. I particularly appreciate Section 3.1. Also, combining test time computing with routing makes a lot of sense and has not been explored before (to my knowledge).", "other_comments_or_suggestions": "- “The rising costs of LLM inference have”. I get your point but it would be good to provide some examples (e.g., self-consistency, reranking, etc.)\n\n- “3) Model cascades ( e.g. Chen et al. (2023)) where the query passes through the models sequentially, from the cheapest to the most costly, until a satisfactory response is obtained.”- Not always “until a satisfactory response is obtained”… most cases consider a fixed number of models in the cascade\n\n- “Prior query routing approaches generate only one response from the selected model and a single response from a small (inexpensive) model was often not good enough to beat a response from a large (expensive) model due to which they end up overusing the large model and missing out on potential cost savings.” and “, small models continue to come up short in terms of response quality when compared to the largest, most powerful models”. While I agree with this, there are cases when this is not the case. For instance, check Table 1 of Farinhas et al. (2025). Even though this is for model cascading and specific for machine translation, I think it’s worth mentioning in Section 2.\n\n- Typo in L048-049: “development innovative solutions”\n\n\nReferences: \n\nFarinhas et al., 2025. Translate Smart, not Hard: Cascaded Translation Systems with Quality-Aware Deferral\n\n\n**Update after the rebuttal**: I increased my score to 4.", "questions_for_authors": "NA", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "nZRtCzeGZf", "reviewer": "Reviewer_HDLo", "summary": "This paper proposes a cost-effective LLM inference framework that leverages multiple small LLMs alongside a large LLM (GPT-4o). A router model is trained to (1) select which LLM to use from the candidate pool, (2) determine how many responses that LLM should generate, and (3) select the best response among them. The goal is to strike a balance between inference cost and response quality. Experimental results suggest that the proposed BEST-route method effectively achieves this balance.", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for thoughtful comments. Due to space limits, we have paraphrased some questions to save space while preserving the original intent.\n\n**Q1: The claim of “optimal balance” between cost and quality is too strong without theoretical justification. A more appropriate phrasing would be “preferred” or “effective” trade-off, unless supported by a formal composite metric.**\n\nA1: Thanks for the comment. This work aims to effectively uplift the performance-cost trade-offs achieved by routing techniques. We will revise the claim as “BEST-Route achieves an effective trade-off between cost and quality”, as suggested.\n\n**Q2: The exclusive use of armoRM (also used for training) may introduce bias. Additional metrics like BLEU, ROUGE, or human evaluation are recommended for a more comprehensive assessment.**\n\nA2: Thanks for the comment. We now report BLEU and ROUGE scores, as shown in the tables below. Since human evaluation is expensive and unscalable, we leave it in future work. We observe that BEST-Route consistently achieves better trade-offs than all baselines (e.g., N-label routing has up to 31.7% BLEU drop at 60% cost reduction, vs. only 18.07% drop for BEST-Route).\n\n|  | Response Quality Drop (BLEU score) | w.r.t. always using GPT-4o (%) |\n|:---:|:---:|:---:|\n| Cost Reduction (%) |     N-label   | BEST-Route |\n| 10 | 6.57 | **3.61** |\n| 20 | 13.13 | **6.07** |\n| 40 | 25.80 | **12.76** |\n| 60 | 31.70 | **18.07** |\n| N-class | N-class achieves 0.2% cost reduction | with 0.7% quality drop. |\n| Clustering | Clustering achieves 0% cost reduction | with 0% quality drop. |\n\n|  | Response Quality Drop (ROUGE score) | w.r.t. always using GPT-4o (%) |\n|:---:|:---:|:---:|\n| Cost Reduction (%) |     N-label   | BEST-Route |\n| 10 | 6.10 | **3.88** |\n| 20 | 11.65 | **7.27** |\n| 40 | 22.26 | **15.78** |\n| 60 | 27.62 | **21.97** |\n| N-class | N-class achieves 0.2% cost reduction | with 0.9% quality drop. |\n| Clustering | Clustering achieves 0% cost reduction | with 0% quality drop. |\n\nA detailed visualization is provided in Figure 2 and 3, via [link](https://github.com/BEST-Route2025/BEST-Route/blob/main/README.md).\n\n**Q3: It is unclear why the experiments do not include the previous “best-of-n sampling” baselines, where multiple responses are generated and the best is selected using a reward model. These baselines are highly relevant for comparison, and should be included or clearly justified.**\n\nA3: Thanks for the comment. We have implemented the best-of-n sampling baseline and report the performance in Figure 1, via [link](https://github.com/BEST-Route2025/BEST-Route/blob/main/README.md). Best-of-n offers fixed trade-offs for each model and n pair and often yields lower-quality responses (e.g., 4.9% quality drop for Phi-3-mini, 1.1% for LLaMA-3.1-8B at n=5). In contrast, BEST-Route offers flexible trade-offs, achieving 20% cost reduction with only 0.21% quality drop, and 40% cost reduction with 0.47% drop, with the max sampling number n=5.\n\n**Q4: The architecture of the proxy reward model R_proxy(s) is unclear. While the cost-efficient multi-head router is stated to use a BERT-style backbone, no analogous detail is given for the proxy reward model.**\n\nA4: In Lines 283-286, we mentioned “the proxy reward model is fine-tuned from OpenAssistant RM, a DeBERTa-v3-large model (300M)”. Specifically, the proxy reward model is a DeBERTa model [1] which improves BERT with enhanced mask decoder and disentangled attention. In our evaluation, we observe that the proxy reward model is cost-efficient and incurs negligible overhead (see Figure 6 in our paper).\n\n**Q5: In section 4.2, the \"They key intuition\" should be \"The key intuition\".**\n\nA5: Thank you. We will fix this in the revision.\n\n**Q6: The output range of R_proxy(s) is unclear. Clarifying whether scores are normalized (e.g., within [0,1]) is important for interpreting outputs and their role in selection (e.g., the L_rank in equation (1)).**\n\nA6: Thanks for the comment. In our paper, we train a proxy reward model to “preserve the ranking of responses” and take the output logits as the proxy reward scores R_proxy(s), which ranges from (-∞, +∞). A higher proxy score indicates a better response quality. In our evaluation, proxy reward scores range from -12.25 to 12.1875, as detailed in Figure 4, accessible via [link](https://github.com/BEST-Route2025/BEST-Route/blob/main/README.md).\n\nIn equation (1), we construct training pairs in the form of (good response s, bad response s’) and train the proxy reward model to preserve the ranking of responses by minimizing the negative log likelihood loss L_rank, which takes on lower values as the proxy reward score difference, R_proxy(s) - R_proxy(s’), gets larger .\n\n**Thank you for your time and consideration. We sincerely hope that you find our responses convincing and would consider increasing your rating.**\n\nReferences:  \n[1] He, Pengcheng, et al. \"DEBERTA: DECODING-ENHANCED BERT WITH DISENTANGLED ATTENTION.\" ICLR 2021.", "claims_and_evidence": "The paper should avoid claiming that it achieves an optimal balance between cost and quality, as no theoretical evidence is provided to justify the optimality. A more appropriate claim would be that the method achieves a preferred or effective trade-off.\n\nIf the authors wish to make such a claim, they should justify its superiority using a well-defined metric that quantifies the trade-off between cost and quality, such as a composite metric that integrates both factors.", "methods_and_evaluation_criteria": "The paper evaluates response quality solely using armoRM, which is also the training objective for the method. This introduces potential bias and may not fully capture response quality. The reviewer recommends incorporating additional evaluation metrics, such as BLEU, ROUGE, or human evaluation, to provide a more comprehensive assessment.", "theoretical_claims": "No theoretical analysis is included.", "experimental_designs_or_analyses": "It is unclear why the experiments do not include the previous “best-of-n sampling” baselines, where multiple responses are generated and the best is selected using a reward model. These baselines are highly relevant for comparison, as they also aim to balance cost and quality. The authors should either include such baselines or provide a clear justification for their omission.", "relation_to_broader_scientific_literature": "The paper reveals that there is potential to actively select between LLMs with different costs. The trade-off between cost and performance can be vital.", "essential_references_not_discussed": "None.", "other_strengths_and_weaknesses": "The paper does not sufficiently describe the architecture of the proxy reward model \n$R_{proxy}(s)$. While the cost-efficient multi-head router is stated to use a BERT-style backbone, no analogous detail is given for the reward model. This information is crucial for reproducibility and understanding the model’s capacity.", "other_comments_or_suggestions": "In section 4.2, the \"They key intuition\" should be \"The key intuition\".", "questions_for_authors": "The paper does not clarify the output range of the proxy reward model \n$R_{proxy}(s)$. Is the score normalized to lie within [0,1]? Knowing the score range is important for interpreting the reward model’s outputs and understanding how it influences selection (e.g., the $L_{rank}$ in equation (1)).", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "nFA1s1qhFQ", "reviewer": "Reviewer_2U5y", "summary": "This work proposes BEST-Route, a method that combines LLM routing with test-time compute scaling.\nGiven a pool of LLMs and an input query, a router determines not only which LLM to route the query to, but also the number of responses to sample for it before applying Best-of-N (BoN) sampling.\nDetails about training the router and the proxy reward model for BoN sampling are explained.\nEmpirical results on various benchmarks show that the proposed method achieves a better cost-accuracy trade-off than baseline approaches.\n\n**Update after rebuttal:** I'd like to thank the authors for their answers to my clarification questions, and will keep my positive rating unchanged.", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "**Q1: For the calculation of cost[(M, i)] in Algorithm 1, the number of sampled responses i is multiplied only with the output length, not with the input length. Is this a typo or intentional? Are the costs in experiment results calculated in the same way? This calculation seems to rely on the assumption that the input tokens are only charged once when sampling i responses for the same prompt; otherwise, it would be an underestimate of the actual cost by the proposed method.**\n\nA1: Thanks for the question. This way of cost calculation is intended. Most modern LLMs support returning multiple responses at once for a given query. For example, you can set the “num_return_sequences” hyper-parameter for HuggingFace LLMs (https://huggingface.co/docs/transformers/en/main_classes/text_generation) to tune the number of independently computed returned sequences for each query. Given this, we only need to feed the prompt/input tokens once to get multiple response samples. Therefore, “input tokens are only charged once when sampling i responses for the same prompt”. We will clarify more on this in the revision.\n\n**Q2: What does \"Random\" in the legend of Figure 4 mean?**\n\nA2: “Random” stands for the baseline which randomly routes queries between the large and small models at different ratios. This baseline has been adopted in prior binary routing work [1, 2].\n\n**Q3: In Line 425 Left, the authors mention that increasing n has a marginal impact on overall latency. Is this due to implementation of batch inference and parallelism?**\n\nA3: Thank you for the question. This is for the same reason as explained in A1. The overall latency comprises the prefilling latency (processing the prompt tokens) and decoding latency (generating output tokens). Since we generate n responses in parallel with the same prompt (e.g., https://github.com/huggingface/transformers/blob/v4.50.0/src/transformers/generation/utils.py#L2317), increasing n only leads to modest decoding latency overhead and marginal overall latency increments (see Figure 6 in our paper). We use a batch size of 1 but larger batches may further reduce latency and are worth future exploration.\n\n**Q4: Could you provide some context about the armoRM score, e.g., how significant is an increase from 0.112 to 0.126?**\n\nA4: Thanks for the question. armoRM score [3] is a comprehensive response quality metric that aggregates 19 evaluation perspectives, including Helpfulness, Correctness, Coherence, and Verbosity. It is constructed by collecting ground-truth ratings for each perspective, followed by normalization, de-biasing, and weighted summation into a unified score ranging from -1 to 1. \n\nAn increase from 0.112 to 0.126 reflects meaningful improvements across multiple quality dimensions. In our evaluation, Mistral-7B scores 0.112 on average, while GPT-4o reaches 0.126 — consistent with benchmarks like MMLU [4], where GPT-4o surpasses 85% accuracy vs. ~60% accuracy for Mistral-7B, underscoring the significance of this gap.\n\nQualitatively, we observe that responses at 0.112 are generally helpful but limited, whereas higher-scoring responses (e.g., 0.126) offer deeper insight and more comprehensive guidance. We provide one example to illustrate this difference.\n\n“  \nQuery:  Is it normal to have a fever when I'm sick?\n\nResponse 1 (armoRM = 0.112):\nYes, having a fever when you're sick often indicates that your body is fighting off an infection or illness. Fever is a natural defense mechanism whereby your body's temperature increases to create an environment less conducive for pathogens to multiply.\n\nResponse 2 (armoRM = 0.127):\nYes, it is common to have a fever when you're sick. A fever is your body's natural response to fighting off an infection. It indicates that your immune system is actively working to fight the pathogens causing the illness. **However, if your fever is above 101°F (38.3°C) and persists for more than a couple of days, it's a good idea to seek medical advice to ensure there isn't a more serious underlying condition.**  \n”\n\nBoth Response 1 and 2 cover the perspective that “fever is a natural defense mechanism”. However, Response 2 further enriches the argument by discussing the potential danger of persisting high fever and suggests to users to seek medical advice in such cases, which could be life-critical in healthcare consultations and is missing from Response 1.\n\n**Thank you for your time and consideration. We sincerely hope that you find our responses convincing and would consider increasing your rating.**\n\nReferences:  \n[1] Ding, Dujian, et al. \"Hybrid LLM: Cost-Efficient and Quality-Aware Query Routing.\" ICLR. 2024.  \n[2] Ong, Isaac, et al. \"RouteLLM: Learning to Route LLMs from Preference Data.\" ICLR. 2025.  \n[3] Wang, Haoxiang, et al. \"Interpretable Preferences via Multi-Objective Reward Modeling and Mixture-of-Experts.\" EMNLP Findings. 2024.  \n[4] Hendrycks, Dan, et al. \"Measuring Massive Multitask Language Understanding.\" ICLR. 2021.", "claims_and_evidence": "The claims made in the submission are supported by clear and convincing evidence.", "methods_and_evaluation_criteria": "The proposed methods and evaluation criteria make sense to me.", "theoretical_claims": "There is no theoretical claim in this work.", "experimental_designs_or_analyses": "I have checked the experimental designs and analyses, which make sense to me. I only have a clarification question about cost calculation; see Question 1 below.", "relation_to_broader_scientific_literature": "Both LLM routing and test-time scaling (via BoN sampling) have been well studied in prior works.\nThe key novelty in this work is a combination of both, i.e., boosting the accuracy by BoN sampling when the query is routed to a smaller model, which can still be cheaper than calling the most expensive LLM once.", "essential_references_not_discussed": "Not that I'm aware of.", "other_strengths_and_weaknesses": "N/A", "other_comments_or_suggestions": "N/A", "questions_for_authors": "Some questions for clarification:\n\n1. For the calculation of cost[(M, i)] in Algorithm 1, the number of sampled responses $i$ is multiplied only with the output length, not with the input length. Is this a typo or intentional? Are the costs in experiment results calculated in the same way? This calculation seems to rely on the assumption that the input tokens are only charged once when sampling $i$ responses for the same prompt; otherwise, it would be an underestimate of the actual cost by the proposed method.\n\n2. What does \"Random\" in the legend of Figure 4 mean?\n\n3. In Line 425 Left, the authors mention that increasing $n$ has a marginal impact on overall latency. Is this due to implementation of batch inference and parallelism?\n\n4. Could you provide some context about the armoRM score, e.g., how significant is an increase from 0.112 to 0.126?", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Meta-review: This paper works on query routing for LLMs, and proposes a method called BEST-Route, which optimally balances cost and quality through: 1) multi-headed router that dynamically assesses the query difficulty for model selection and 2) a test-time optimal compute strategy that uses best-of-n sampling. The rebuttal addressed the reviewers' initial concerns, and all reviewers recommend acceptance after the rebuttal phase. The ideas are novel and interesting, and the motivation is clear. I thus recommend acceptance.
Decision: Accept (poster)