A Unified Approach to Routing and Cascading for LLMs
Authors: Jasper Dekoninck
Maximilian Baader
Martin Vechev
Venue: ICML 2025 poster (2025)
Keywords: large language models
routing
cascading
Primary area: deep_learning->large_language_models
TL;DR: We combine cascading and routing into a more powerful model selection method called cascade routing.

Abstract: The availability of a wide range of large language models (LLMs) embedded in various agentic systems has significantly increased the potential of model selection strategies to improve the cost-performance tradeoff. Existing strategies involve either routing, where a single model is chosen per query, or cascading, which sequentially runs increasingly larger models until a satisfactory answer is found. However, current approaches face three key limitations: they (1) lack formal proofs of optimality, (2) fail to identify the conditions under which these strategies are most effective to improve the cost-performance tradeoff, and (3) are unable to combine both paradigms for further improvements. To address these issues, we first derive a novel optimal strategy for cascading and prove the optimality of an existing routing strategy. Further, we propose *cascade routing*, a unified framework that integrates routing and cascading into a theoretically optimal strategy. Through our analysis, we identify good quality estimators as the critical factor for the success of model selection paradigms.  Finally, in our experiments, we show that cascade routing consistently outperforms the individual approaches by a large margin and we analyze quality estimators to determine when routing and/or cascading are useful paradigms for model selection.

A Unified Approach to Routing and Cascading for LLMs
Jasper Dekoninck' Maximilian Baader' Martin Vechev
Abstract
To maximize performance, it is crucial select the most suitable model for each query, accounting for both the ex- pected quality of the model's output and the model's s cost. Such model selection strategies can significantly improve performance over any individual model and can reduce in- ference costs by selecting a smaller model when the query does not require the full capacity of larger model.
The availability a wide range of large language models (LLMs) embedded in various agentic systems has significantly increased the potential of model selection strategies to improve the cost- performance tradeoff. Existing strategies involve either routing, where a single model is chosen per query, or cascading, which sequentially runs in- creasingly larger models until a satisfactory an- swer is found. However, current approaches face three key limitations: they (1) lack formal proofs of optimality, (2) fail identify the conditions under which these strategies are most effective to improve the cost-performance tradeoff, and (3) are unable to combine both paradigms for fur- ther improvements. To address these issues, we first derive a novel optimal strategy for cascading and prove the optimality of an existing routing strategy. Further, unified framework that integrates routing and cascading into a theoretically optimal strategy. Through our analysis, we identify good quality estimators as the critical factor for the success of model selection paradigms. Finally, in our ex- periments, we show that cascade routing consis- tently outperforms the individual approaches by large margin and we analyze quality estimators to determine when routing and/or cascading are useful paradigms for model selection [
Routing and Cascading Two primary strategies have been proposed to solve model selection. The first, routing, directs each input query to specific model from set of available models (Chen et al. 2022 Liu et al.. 2024), as il- lustrated in Fig. T(a) This approach is particularly effective when different expert LLMs are needed for diverse tasks, enabling the selection of the most suitable expert for each query. The second strategy, cascading, processes an input query through sequence of increasingly larger models, stopping when a model produces answer deemed suf- ficiently good (Chen et al. 2023 Varshney & Baraa (202)), as illustrated in Fig. [(b) Cascading is particularly valu- able for handling queries of varying difficulty, as allows simpler queries to be addressed by smaller models while reserving more complex queries for larger models.
propose cascade routing,
Restrictive Conditions Despite their utility, both routing and cascading impose significant restrictions on the model selection process. In routing, the initial selection of a model is final, preventing any reconsideration after the initial de- cision. In cascading, each query must sequentially pass through models in the chain, with no option to skip a model. Therefore, less restrictive strategy that combines the strengths of both routing and cascading could offer sig- nificant performance improvements.
1. Introduction
Large language models (LLMs) have found applications in a wide range of tasks, some of which are easily handled by small models, while others require the full capacity of state- of of-the-art LLMs. This has led to the development of many fine-tuned models of various sizes that target specific tasks.
Lack of Deeper Understanding Further, the conditions under which current routing and cascading strategies are optimal, are not well understood. For routing, an exten- sive proof required just to show that current strategies are close to optimal (Chen et al., 2022). while the theo- retical analysis of cascading does not provide optimality guarantees (Chen et al.] 2023 Varshney & Baral (002)). This lack of theoretical understanding hinders the develop- ment of more effective model selection strategies. More- over, prior work fails to provide insights into the limitations of model selection strategies and cannot identify the con- ditions under which they are useful in practical scenarios.
'Department of Computer Science, ETH Zurich, Switzerland. Correspondence to: Jasper Dekoninck <jasper dekoninck inf. ethz.ch>>.
Proceedings of the 42nd International Conference on Machine Learning, Vancouver, Canada, PMLR 267, 2025. Copyright 2025 by the author(s).
Coode available
https://gittubb.com/e sri/
cascade- routing

---

A Unified Approach to Routing and Cascading for LLMs
Query
Query
Query
1
Cascade Router
Stop
Router
Cascader
Stop
Tri2
7/l
Y72/2
m2
Cascade Router
Stop
Stop
Cascader
Stop
m22
7733
Routing
(h) Cascading
(c) Cascade Routing (Ours)
Figure 1: Overview of three model selection strategies. Routing selects a single model for a query, cascading processes queries through sequence of models, and cascade routing generalizes both.
For instance, it is widely believed that one needs models of various sizes benefit from cascading (Chen et al. 2023 Gupta al. 2024: Khalili et al. 2022). but show that this notion is incorrect.
Key Contributions Our main contributions are:
derive optimal strategies for routing and cascading and obtain a new cascading strategy that is provably better than prior approaches
This Work: Cascade Routing To address these lim- itations, we first derive optimal routing and cascading strategies by framing them as linear optimization problems aimed at maximizing output quality while remaining within given cost budget. For routing, this optimal strategy is close the obtained by prior work, while for cascad- ing derive new strategy that is provably better than existing approaches. Building on this analysis, we propose new paradigm called cascade routing, which generalizes both routing and cascading. As illustrated in Fig. [[c], cas- cade routing initially routes query to any available model but keeps rerouting to different models until a model pro- duces answer of sufficient quality. We prove the opti- mality of cascade routing and show that it offers signifi- cantly more flexibility in processing query.
We introduce cascade routing, new paradigm that combines the strengths of routing and cascading, and prove its optimality ($4).
We conduct a thorough evaluation, demonstrating that cascade routing consistently outperforms the base- lines, highlighting the critical role of quality estima- tion for the effectiveness of model selection ($5).
2. Routing as Linear Optimization
We derive an optimal routing strategy to select the best model for given query, providing detailed proof's for all statements in this section in App.
Importance of Quality Estimation Our theoretical anal- ysis enables more thorough investigation into the factors that influence the effectiveness of model selection strate- gies. Specifically, we find that accurate estimates of model performance and response quality are most important. For routing, reliable ex-ante quality estimation the ability to given
Brief Overview In this section, we begin by defining a routing strategy function that maps queries models. Next, we introduce the notation for quality and cost func- tions, demonstrating how the optimal routing strategy can be formulated to maximize linear tradeoff between these two factors. Lastly, we give an illustrative example and dis- cuss the significance of quality estimation in routing and its impact on the effectiveness of the strategy.
predict whether model will perform well query-is essential. For cascading, robust post-hoc quality theimation-the ability to evaluate the quality of model's response after generation-2e is critical. Without it, the ef- fectiveness of cascading strategies is severely limited even when models of various sizes are available.
Routing In routing, our goal is develop strategy that selects the best language model for given input query. Formally, let X' represent the distribution over all pos- sible queries, and suppose we have & language models Mi.... my available for routing. Further, let Aş denote the set of all probability distributions over variables. A routing strategy can then be defined as follows:
We evaluate cascade routing on a range of tasks, demonstrating that it significantly outperforms both routing and cascading. Notably, cascade routing consistently out- performs other methods, improving performance by up 8% on the RouterBench benchmark (Hu et al. (2024) and by 14% on the SWE-Bench benchmark (Jimenez et al. (202)).
Results
Definition 1 (Routing). A routing strategy is a function s: X + AS that maps a query x. E X' to a probability distribution over models. si(z) denotes the probability that m; selected for query x.
Further, we show that our new cascading strategy outper- forms existing cascades in several scenarios by over 10%.
2

---

A Unified Approach to Routing and Cascading for LLMs
A routing strategy selects model by sampling from the distribution s(x) for each query x: In prior work, routing strategies were restricted to be deterministic, i.e. (2()) e {0.1) 1 (Chen et al. 2022 Hu et al.) 2024)). In contrast, we propose using a more general probabilistic strategy that en- ables a better solution and an easier theoretical analysis.
Theorem I continued. Furthermore, all routing strategies that have an expected cost that is exactly equal to B and can be written as convex combination of s and s for some X E RR achieve the same optimal quality.
In App. A we show how to obtain the optimal À and y for a cost budget B using a validation dataset D. In Algorithm we provide pseudocode for the optimal routing algorithm.
Quality and Cost In routing, we seek to maximize the output quality of the selected model while adhering to a given cost budget B. We define the quality function (xx as the output quality of model m, on query x, and the cost function c, (z) as the cost of rumning model m, on Qual- ity could measure model accuracy, user preference, or any other performance indicator. Cost could measure either monetary costs or latency, depending on the use case.
Algorithm 1
Optimal Routing Algorithm
Input: input query x, quality estimator q.. cost estimator e, tradeoff parameters À and
Output: Model index to be used for query x
I: Te T2, A) == 2 (1:) xx((z)
2: Tmax (z. A) == maxic (1.....)) (2)
However, since these functions are unknown in practice, we need estimators (x) and (x(x) that approximate the output quality and cost of querying model m, on input x. Estimators for (2r) can be created using small classifiers trained to predict model accuracy, as done in prior work (Hu et al. 2024 Shnitzer et al.] 2023). (x) can be esti- mated by tokenizing the input query and determining the average output length of the model on a query. Then, we can use API-specific costs per token to estimate the cost of running a model on query. Alternatively, we can also use average execution time as a proxy for cost.
3: best == {i
I (x, A) = Tmax (2,, ))}
4: min_cost_index index == arg minigrest C3 (x)
max_cost_ index == arg maes (x(x)
6: if random(O, 1) < 7 then
7: return
index
8: else
9: return max_cost_index
10: end if
Since 7 is often not equal to 0 or 1, SoFr is not nec- essarily deterministic, i.e., there are queries x such that $opr,i(x) & {0, 1} for some index i. Therefore, prior work that only considered deterministic routing strategies (Chen et al.] [002]] Hu et al., 2024) cannot express the optimal routing strategy and fall back to the near-optimal sun-
Optimal Routing Using these estimators, we can for- mally define the optimal routing strategy:
Definition 2 (Optimal Routing). The optimal routing strat- egy SOPT for a given cost budget B is the solution to the optimization problem that maximizes the expected output quality of the selected model while adhering to the budget:
Example To illustrate routing, consider a scenario with two models mn and my. The estimated cost a(x)) = (0.9,1) 1) is constant across queries and slightly lower for than for m2. The quality is estimated based on the category of the query, which is either math, code, or generic. For instance, let q = (0.8, 0.5), {(Ecode = (0.5, 0.8). and ((Xigemene) = (0.8. 0.9). For = 1 and 7 = 0.7, the cost-quality tradeoff is highest for m,, resp. m2, on math, resp. code, queries, and is equal for both models on generic queries. Thus, the router will select m1, resp. m2, for math, resp. code, queries, and select my with probability of 0.7 and m2 with a probability of 0.3 for generic queries.
Σ i=1 ( (((x))((x))
max
EZEX
(1)
Σ (()))(())))
S.L.
ExEx
< B.
We now explain how to solve this optimization problem. For given query x, it can be shown (see App. that the optimal routing strategy selects the model maximizing the cost-quality tradeoff T; (x, A) = q (x) - ((x( Here, À E R+ is a hyperparameter that controls the balance between quality and cost based on the budget B.
Ex-Ante Quality Estimation We explicitly distinguish between the model's true quality (x(x) and the ex-ante quality estimate (z). An optimal routing strategy will select a good model only if (x) q((x), otherwise the objective in Eq. (I) is not appropriate. Thus, even when routing is suited for the application, the strategy will fail if the quality estimates are inaccurate. This makes quality es- timation a critical component of routing strategies. While cost estimation also faces similar challenges, we found that it less critical and can be approximated more easily.
However, it can occur that several models achieve the same optimal cost-quality tradeoff for a given query. To ad- dress this, we define two deterministic strategies s (I) and A which, respectively, select the cheapest and most expensive model that achieves the optimal tradeoff. The optimal routing strategy Sopr is then determined by:
Theorem (Optimal Routing Strategy). For a cost budger B, there exists a X E Rt and a 7 E [0, 1] such that the optimal routing strategy Somr equals y + (1 - 7) stax
3

---

A Unified Approach to Routing and Cascading for LLMs
3. Cascading as Sequential Routing
the quality-cost tradeoff of Ma will be worse than the tradeoff of Mı:j-1, but Ma-++1 could still provide better outcome. Therefore, it is crucial to consider all supermod- els Mı.j.... . M1 at step j rather than making decisions solely hased on immediate performance.
We extend our analysis of the optimal routing strategy to a cascade. providing proofs for all statements in App. B
Brief Overview In this section, we reinterpret cascading as a sequence of routing problems. Furthermore, we show how our approach improves upon the cascading strategies used in prior work. Finally, examine the impact of post-hoc quality estimates on the effectiveness of cascad- ing strategies.
Quality and Cost To apply Theorem I to find the op- timal cascading strategy, we first need to derive the qual- ity and cost estimates of the supermodels. Both of these can depend on the answers of previously computed mod- els. Therefore, let (z)) and ق0ع (0)(2) represent the updated estimates in step after computing the first j 1 models.
Cascading In cascading, input query is processed se- quentially through a chain of models, typically arranged in order of increasing size or cost. The cascade stops once a model's output meets a certain condition, and that output is returned. We will reinterpret cascading as a sequence of routing problems. To do so, we first define the models over which we need to route, which we refer as supermodels.
We derive the quality and cost estimates associated with supermodel Mi:1, denoted as af (z) and (x). based on the quality and cost estimates of the individual mod- els. Trivially, the cost of the supermodel is equal to the sum of the individual model costs. The quality of su- permodel, however, is governed by the best model within it. Thus, it equals Eg. [max (z)..... (x())),, where the expected value reflects the uncertainty in each quality esti- mate. Specifically, each quality estimate (x) is modeled as a random variable estimating the true quality g:(x). This is crucial since ignoring uncertainty would falsely assume that the quality of a supermodel is always equal to the best model within it, even though the best model may return a poor answer, while another returns a good one. To estimate the uncertainties associated with the estimates, we compute the variance of q. (x) 4
Definition (Supermodel). A supermodel M is a se- quence of models .mi.))..,,m;.))) such that running a query through M is equivalent running it through each of the models in the sequence. M denotes the set of all supermod- els and by Mej we denote the supermodel (m....., m,))
In cascading, we only need to consider the supermodels MI.....,, MI.- The full expressivity of Definition 3 will
only be necessary for cascade routing in $
(k) (x)) over validation dataset.
Cascading as Sequential Routing Running a cascade on a sample x occurs in a sequence of steps, where at each step, the cascade determines whether to run the next model in the sequence or terminate. By step j. we have obtained outputs from the first j models. To decide whether to continue and run mj. we need to determine, in expectation, how well the supermodels Mı:j-1..... Mi.k will perform on the sample x. Once again, this performance is measured as having the highest expected output quality within a cer- tain cost budget. If M1y-1 offers the best performance, we terminate the cascade and return its output, i.e., the output of my-1. Otherwise, if any of My....... Mys has better performance, we continue the cascade and run mj. There- fore, step j. the cascade is equivalent to routing strategy that selects the best supermodel from Migj-1,... Mike Thus, a cascade can be formally defined as follows:
Optimal Cascading We now leverage the optimal rout- ing strategy from Theorem determine the optimal cas- cading strategy. As before, optimality is defined in terms of maximizing the expected output quality while adhering to a given cost budget. However, the budget is now only enforced over the entire cascade, and not over individual steps. This leads a slightly different formulation:
Theorem (Optimal Cascading Strategy). For a given cost budget B, there exist Ai,..., d R and a y e 1] such that the optimal cascading strategy SOPT
(sor),... ..oo)) .o.r,...,,or1. is given by (f) = -YSMIN ( (1-2))880 UL.);
(2).A,
(2),,, where SaIN and SMAX are defined as in Theorem
(3),3;
In App. B we explain how to obtain the hyperparameters A...... AR and y for a given cost budget B using a vali- dation dataset D. In Algorithm 2 we provide pseudocode for the optimal cascading algorithm, illustrating the steps involved in selecting the best model for a given query.
Definition 4 (Cascading Strategy). A cascading strategy is a sequence of routing strategies (s(!)..... s(k) such that slf) routes between the supermodels Mı.-1...., Ma
Notably, while the action associated with supermodels M M1s is the same, namely continuing the cas- cade, it is important to consider all these supermodels. In- deed, a model my might perform poorly while my+1 per- forms exceptionally well on a given query. In such cases,
Example To illustrate the optimal cascading strategy, consider once again a scenario with two models mı, m2 with costs (z) = (0.5, 1) and (x) = (0.5. (ig- noring uncertainty). In a cascade, we will always run mi for query x. Thus, we obtain the first model's output.
4

---

A Unified Approach to Routing and Cascading for LLMs
Algorithm 2 Optimal Cascading Algorithm
role. Cascading approaches are only advantageous when the post-hoc quality estimate provides significantly better information than the ex-ante estimate. If this improve- ment is minimal, it would be more effective to directly route queries to the most suitable model, bypassing the cas- cading process. While the post-hoc estimate is essential for refining decisions, the ex-ante quality estimate remains valuable in determining whether future models can poten- tially deliver better performance. Only in the threshold cascade strategy, where the ex-ante estimate is fixed, does it become irrelevant. By contrast, our approach improves upon the threshold cascade by incorporating both ex-ante and post-hoc quality estimates, thereby enabling more in- formed decision-making.
Input:
input query x, current step j. quality estimator d.
cost estimator ol) tradeoff parameters A and 7 Output: Whether to stop the cascade continue with the next model m;
1: for = j - to k do
( (x) = Egts [
( (x),....d" (x))
2:
1.1 (x) = -ii= a (z)
2
3:
4: end for
5: index == Router 2, (9 (1 (z)...., (......,.kk (x))
6:
(1)-(()) (x)..... 1 (1)(
7: if index == then
8: return stop
9: else
4. Cascade Routing as Cascade Generalization
10: return run my
11:
end if
Both routing and cascading are powerful techniques that enable the efficient use of multiple models. However, their use is often orthogonal: while routing is useful when ex- ante quality estimates are accurate, cascading is more ben- eficial when post-hoc estimates are accurate. We therefore present cascade routing, which is a generalization of both techniques. Proofs for all theorems and lemmas in this sec- tion are included in App.
Based on this output, we can adjust the quality and cost estimates. Suppose, for instance, that the model output is very long and its confidence in its own answer is only 30%. Then we update, for instance, (z) = (0.3, 0.6) and (x) = (1, 2). For A2 = 1, we would now stop the cascade and return the output of m2 since the cost-quality tradeoff is highest for the supermodel {m1]. If, instead, A2- 0.1, we would run m2 since the cost-quality tradeoff is highest for the supermodel (m1, m2). In this case, the cascade would return the output of m2.
Brief Overview In this section, we first define cascade routing and explain how it generalizes both routing and cas- cading. We then derive the optimal cascade routing strat- egy and solve several of the additional challenges that arise when applying cascade routing in practice. Finally, we pro- vide an illustrative example.
Prior Work Prior work on cascading has often relied on strong assumptions to simplify the strategy, using a treshold-strategy as an approximation of the optimal cas- cade. Specifically, in step j. the cascade continues if ali) (x) < Tj for some threshold T E R. To the best of our knowledge, all existing works can be seen as a spe- cific instantiation of this thresholding scheme with cost and quality estimators that depend on the specific application
Cascade Routing Cascade routing closely resembles cascading, but with one crucial difference: the routing strat- egy at step routes between all possible supermodels, not just the supermodels Mı.s-1,.... Mı.k. Therefore, both Definition and Theorem 2 can be extended to this setting.
used (Chen et al., [2023] Damani et al.) 20244] Gupta et al.)
Definition 5 (Cascade Routing). A cascade routing strat- egy is sequence of routing strategies such that, for a given sample x E X, s05) routes between all supermodels in M that start with the j - 1 models that have already been computed for this query.
2024 Jitkrittum et al. 2023b Nie al. 2024). Below, we outline the conditions under which this simplified approach
s(k)
is optimal.
Corollary 1 (Optimal Threshold Strategy). Under minor technical assumptions, the thresholding strategy is equiv- alent to our cascading strategy if and only if the follow- ing conditions hold: (l)(()) is independent of x for all (z) is independent of x for all i > j.
Theorem 3 (Optimal Cascade Routing). For given cost budget B, there exist X1,...,>> > E R- and a ? E IR+ such that the optimal cascade routing strategy SoPT- -YSMIN
i .k).....). g.))(2))
(SoPt...., ....8 is given by (1) ())A,, +(1 (1-211) ().A
(k)
MAX
and gld (x) is equal to a, (x).
(3),b3 and MMAX are defined as in Theorem
(2),),
where SMIN
Host-Hoc Quality Estimation Once again, this theoreti- cal framework highlights the importance of quality estima- tion, with a shift in focus from ex-ante quality estimation to host-hoe quality estimation, which now plays a critical
In Algorithm 3 we provide pseudocode for the cascade routing algorithm. While cascade routing is a seemingly simple extension of cascading, it also introduces additional challenges which we address now
5

---

A Unified Approach to Routing and Cascading for LLMs
Algorithm 3 Optimal Cascade Routing Algorithm
Lemma (Negative Marginal Gain). Let M E M and m be any model in M. Let the marginal gain of in w.r.t M be defined (M, X) TM (2, A). Then, if the marginal gain of m w.E.. M is strictly negative for a given query, the optimal cascade routing strategy will never run a supermodel M' E .M that contains all models in M.
Input: input query I, model indices run so far i quality estimator a(ا) cost estimator a(3)
tradeoff parameters A and Output: Index of the next model to run
1: S [M C
/ [1,....j-11 :4 M]
2: for M E S do
3: 9M (z) == Egon m (c) (x))
(5)
Example To illustrate the optimal cascade routing strat- egy, consider scenario with two models my and m2 with costs (z) = (0.5, 1) and (x) = (0.5, 0.8). In con- trast to cascading, we do not necessarily need to run my first. In this scenario, if λ = 0.1, we would immedi- ately run my. While we would most likely stop after ma- it is possible that its output is so bad that we update the quality estimator to (x) = (0.5, 0.1). In this case, for X2 0.1, we would run my next and return its output. If \ = 1, we come into the more classical cascading sce- nario explained before where my is run first.
4: Cas (a) = ΣlEM (x)
(i)
5: end for
6: index == Router (z. (450 (x) for M E S):
(c (x) for M E 2),))s,))
7:
8: possibilitiis == Snnex \ (61, ز
9: if possibilities @ then
10: refurn stop
11: else
12:
post_index== == arg minigpossiblliiss (z)
13: return min cost index
5. Experimental Evaluation
14:
end if
We now evaluate the performance of cascade routing and demonstrate that it significantly outperforms all other strategies. Additionally, we show that our new cascad- ing approach outperforms the threshold-based cascading method. For this purpose, we first conduct experiments on RouterBench (Hu et al. 2024). a benchmark specifically designed to evaluate routing and cascading ($5.I). Next, we test cascade routing on several additional benchmarks to evaluate its performance in more realistic scenarios ($5.2).
Model Order In cascading, the model order is predeter- mined, and the routing strategy only decides whether to proceed with the next model in the sequence. In contrast, cascade routing must dynamically determine the order in which models are computed. Despite this, both the esti- mated quality dx (a)) and cost abd (z) of a supermodel M are order-independent. Therefore, supermodels that con- tain the same models in a different order will have the same cost and quality. To mitigate this, we sort the models within the selected supermodel by cost and compute the cheap- est one first (illustrated in Lines 12-13 of Algorithm B) This approach aligns with cascading, where more expen- sive models are only used if cheaper models do not suffice.
In the appendix, we perform ablation study to examine the impact of various design choices in cascade routing on performance and runtime (App. F). Finally, in App. H we show detailed results as well as cost-quality tradeoff curves for several benchmarks.
5.1. RouterBench
Number of Supermodels In cascading, the quality and cost must be computed for a maximum of & supermodels at each step. However, in cascade routing, the number of supermodels grows exponentially, leading to the need to evaluate up 2* supermodels. This increase can become prohibitively costly, particularly since the model selection process must remain computationally negligible with re- spect to model computation. To mitigate this, we lever- age so-called negative marginal gains. It can be shown (see App. C) that if model m in a supermodel M neg- atively impacts the quality-cost tradeoff, all supermodels containing all models in M can be pruned from the search space. For example, if m2 negatively affects the quality- cost tradeoff of the supermodel {m, m2), we can prune all supermodels that contain both mi and m2. Since this negative contribution is quite common, this allows us to prune the search space significantly. More formally, this pruning operation relies on the following lemma:
RouterBench (Hu et al. 2024) is a benchmark developed to evaluate the efficacy of different model selection strate- gies. It includes questions from seven diverse benchmarks, such as MMLU (Hendrycks al.) 2021). GSM8K (Cobbe)
et al. 202I), and MBPP (Austin et al. 202I). alongside answers from eleven different models ranging from GPT-4 OpenAl 2023) to Mistral-7B (Jiang et al. 2023
Quality and Cost Estimates Similar to (Hu et al. 2024), we estimate quality and cost by adding zero-centered Gaus- sian noise to their true values. Both cost and quality esti- mates are modeled linear functions fitted on these noisy signals. Thus, the quality estimate can be expressed as (w:((x) = W +c) where e ~ (O, o²). ). A similar expression holds for the cost estimate. We define the vari- ance of the noisy signal as o before model computation (ex-ante estimates) and o2
post after (post-hoc estimates).
6

---

A Unified Approach to Routing and Cascading for LLMs
Table 1: AUC scores in % for different strategies on RouterBench across model and noise levels. All baselines are always
worse than the 95% confidence intervals of cascade routing. For a discussion on confidence intervals, we refer to App.
Three Models
Five Models
Eleven Models
Low
Med
High
Low
Med
High
Low
Med
High
Linear Interp.
69.62
69.62
69.62
69.22
69.22
69.22
70.51
70.51
70.51
Routing
79.73
74.97
71.81
81.24
74.43
71.33
83.25
74.63
72.67
Cascade (Baseline)
80.86
74.64
72.48
82.33
73.03
69.53
84.48
73.64
69.79
Cascade (Ours)
81.09
76.16
72.67
83.06
75.17
70.18
84.47
75.10
70.26
Cascade Routing (Ours)
82.36
76.55
73.22
84.33
76.31
72.75
87.24
77.57
74.40
3.0
3.0
12
2.4
2.4
9
1.8
1.8
'ost
post
1.2
1.2
3
0.6
0.6
2
0.0
0
0.0
0.0
0.6
1.2
1.8
2.4
3.0
0.0
0.6
1.2
1.8
2.4
3.0
O ante
O antt
(a) Comparison of cascade routing with routing.
(b) Comparison cascade routing with cascading.
Figure 2: Difference in AUC performance between cascade routing and baseline strategies on RouterBench for various noise values. Red indicates cascade routing is much better, while blue indicates is only a bit better.
To explore different uncertainty levels, we vary the vari- ances to simulate low-, medium-, and high-noise scenarios, with exact values for the variances given in App. D.I
Results Table I presents the results for the zero-shot set- ting, with the five-shot results detailed in App. H Cas- cade routing consistently outperforms all baseline strate- gies with performance gains between 1% to 4%, which measured relatively the naive linear interpolation base- line means that cascade routing improves by 13% to 80% over the baselines. This performance gap widens as more models are available and narrows under higher noise lev- els, indicating that cascade routing is most effective with large model sets and accurate cost and quality estimates. Furthermore, our new cascading strategy outperforms the threshold based cascade by up to 2%. reinforcing the prac- tical relevance of our theoretical results.
Models We evaluate cascade routing on RouterBench us- ing three, five, and eleven models available for model selec- tion, ensuring comprehensive evaluation across a range of scenarios. The exact models are provided in App. D.I
Strategies We compare cascade routing against several baseline strategies, including the routing strategy described in $ the threshold-based cascading approach from prior work (Corollary []. and the optimal cascading strategy (Theorem 2) Additionally, as in (Hu et al.] 2024), we in- clude a baseline that linearly interpolates cost and quality on the Pareto frontier of the models.
Quality Estimation To better understand the impact of quality estimation on model selection strategies, we ad- ditionally conduct experiments with five models under broader range of varying noise levels. Fig. iillustrates the difference in AUC performance between cascade routing and baseline strategies for all possible noise levels. The re- sults demonstrate that cascade routing consistently outper- forms the baselines, achieving up to an 8% improvement for cascading and up to a 12% improvement for routing. Notably, the performance gap highlights key differences
Evaluation Metric For each method, we evaluate perfor- mance using cost budgets ranging from the cheapest to the most expensive model. This produces a quality-cost curve for each strategy. Following (Hu et al. (2024). we use the Area Under the Curve (AUC) as the performance metric.
7

---

A Unified Approach to Routing and Cascading for LLMs
between the cascading and routing strategies. For rout- ing, the value of ane is critical-high amee significantly reduces performance compared to cascade routing. Con- versely, for cascading, poss plays more influential role, with higher values causing substantial performance degra- dation. These findings underscore the importance of accu- rate quality estimation for both strategies. Cascade rout- ing proves to be more robust solution by unifying the strengths of both approaches and effectively leveraging low ant and low post to enhance performance.
quality estimation scenarios. Interestingly, despite poor post-hoe quality estimation, our cascading strategy nearly matches the performance of routing. This suggests that the cascade effectively leverages ex-ante quality estimation to make informed decisions, unlike the baseline cascade.
We highlight that the cost estimator for SWE-Bench is latency-basedd computing cost as the time it takes to com- plete the task. In contrast, the estimator for Minerva Math and LiveCode uses the cost of the generation. Thus, cascade routing can adapt to different cost estimators.
5.2. Real-World Benchmarks
We now show that cascade routing outperforms baselines on more realistic benchmarks with quality estimates that can be used in real-world scenarios. We differentiate in our analysis between benchmarks where accurate quality estimation is available and those where it is not.
Poor Quality Estimation We perform experiments on classification and open-form reasoning tasks where there is no known accurate quality estimator. The classification benchmarks include ARC-Challenge (Clark et al.) 2018). MMLU-Pro (Wang et al. 2024), and MixEval (Ni et al. 2024). For open-form reasoning tasks, we use MMLU-Pro and GSM8k (Cobbe et al. 2021). In classification, models select a single option representing their answer, with no in- termediate reasoning process. In contrast, open-form rea- soning allows models to generate their answers after rea- soning. In this section, we evaluate two model families consisting of three models, LLAMA and GEMMA, and show similar numbers for the MISTRAL model family in App. [H] We create a quality estimator based on state-of-the-art work Gupta et al. (2024), which uses log probabilities as features. For full details on the benchmarks, models, and cost and quality estimators, refer to App. D
Accurate Quality Estimation We first evaluate cascade routing on two benchmarks that allow for accurate qual- ity estimation. First, in the domain of software engineer- ing, it is often easier to generate tests to reproduce spe- cific issues than to fix them. We therefore use SWE-Bench (Jimenez et al. 2024) as a benchmark where accurate post- hoc quality estimation is available. Specifically, we as- sume that the quality of a model's response can be accu- rately estimated by testing it on the ground-trutt test cases. Second, to simulate use-case where ex-ante quality es- timation is accurate, we use the Math and Coder models from the QWEN-2.5 model family (Yang et al.) [024] Hui 2024) and evaluate them on a combination of Min-
jet al. erva Math (Lewkowyzz et al., 2022) and LiveCodeBench (Jain et al. 2024). To obtain accurate quality estimates, we incorporate a sample's origin benchmark as a feature in the quality estimation model. For all details about the bench- marks, models, and estimators, we refer to App. D.I
Results Table 2 (right) presents the results for the LLAMA and GEMMA model families across both bench- marks. Cascade routing consistently performs on par with or outperforms all baselines, though with much narrower margins reaching up to 1.2%. This reduced gain can be at- tributed to the fact that the quality and cost estimates are very noisy, leading to performance gains over the naive baseline similar to those observed in very high-noise see- narios on RouterBench.
Results Table 2 (left) shows the results for both bench- marks. In Bench, our methods outperform baseline strategies by up to 14%. As expected, the routing strat- egy does not outperform the trivial baseline this bench- mark, as ex-ante quality estimates are insufficient. Interest- ingly, despite perfect post-hoc quality estimation for SWE- Bench, the baseline cascade strategy also performs poorly. This is due to the binary feedback of the quality estimator, which leads the threshold r of the baseline cascade to either admit all models (r 0) or only correct ones (r > 0).
6. Related Work
Routing Routing is a widely studied problem in machine learning, particularly in the task of directing input queries to specialized models. One of the most common appli- cations of routing is model selection for natural language
input queries with a known answer (Chuang et al.
2024
Ding et al. 2024 Hari & Thomson 2023 Liu al.
2024
For Minerva Math and LiveCodeBench, the opposite trend holds true. With accurate ex-ante quality estimation, the routing strategy achieves strong performance, surpassing the baseline cascade strategy by 10%. However, the cascade routing strategy still outperforms all methods, highlighting its robustness across diverse benchmarks and
Jang et al. 2023
Nguyen et al. 2024 Sakota et al. 2024
Shnitzer et al.) 2023). All these works train a model to pre- dict whether a given model will correctly answer a query. Though the setups in these works are largely similar, they vary in certain specifics, such as the type of input queries or the features used for quality estimation.
8

---

A Unified Approach to Routing and Cascading for LLMs
Table 2: AUC scores on practical benchmarks. On the left, resp. right, side we show the benchmarks with good, resp. poor, quality estimates. The highest numbers are bolded, and underlined numbers are within the 95% confidence intervals of the we present benchmark-specifee AUC
highest number. For a discussion on confidence intervals, refer to App. E In App. G values for results averaged over several benchmarks.
SWE-Bench
Moth+Code
Classification
Open-Form
10 MODELS 5 MODELS
QWEN
LlAmM
GEMMA
LLAMA
GEMMA
Linear Interp.
40.51
38.64
39.63
74.28
61.68
79.11
54.10
Routing
40.47
39.40
47.46
74.92
64.44
79.32
58.40
Cascade (Buseline)
38.52
45.89
37.68
74.81
54.32
79.23
56.18
Cascade (Ours)
53.20
50.94
46.76
75.46
62.79
79.22
56.18
Cascade Routing (Ours)
54.12
51.09
48.55
75.52
64.84
79.88
59.66
Routing is also applied in other areas. For instance, Lu et al. (2024); Ong et al. (2024) use preference data to train a quality estimator, which facilitates routing in scenarios involving real-world user queries where clear ground-truth answers may not exist. Additionally, Chen et al. (0022) employ routing for API selection in multi-label classifica- tion tasks, focusing on directing queries the appropriate API based on task requirements. Similarly, Zhang al.) (2024b) apply routing in software agent environments, di- recting user issues to the agent most suited to handle them. Finally, Pichlmeier et al. (2024) dynamically routes token generation instead of entire queries, allowing for more fine- grained routing decisions.
ciency. Furthermore, Xue al. (2023) apply cascading to majority voting for single model to obtain a method called dynamic voting: the cascade stops depending on the aggre- gated answers of all previous model computations. Lastly, (Zhang et al.) 2024a) propose the use of multi-objective quality metrics to guide cascading decisions and do not solely focus on accuracy.
All works mentioned here can be seen as an instantiation of the thresholding mechanism outlined in Corollary with application-specific quality and cost estimates.
7. Conclusion
In this work, we introduced novel framework for routing and cascading that enabled us to propose theoretically op- timal strategies for both paradigms. Further, we used this analysis to propose new paradigm for model selection, cascade routing, which combines the benefits of routing and cascading. We showed that cascade routing can signif- icantly outperform its baselines, especially with good qual- ity and cost estimates. We also find that our new cascad- ing strategy significantly outperforms existing approaches to cascading, showing our theoretical analysis also leads to practical gains.
Cascading Cascading techniques are primarily used to reduce inference costs by employing smaller models ini- tially and only cascading to larger models if the smaller ones fail to provide sufficiently accurate answer. Most of- ten, cascading decisions are based on the smaller model's confidence in its own predictions (Chen et al. 2023 2024
Ramírez al. 2024 Varshney & Baral 2022). However, alternative techniques also exist. For example, Madaan et al. 2223) propose running models multiple times and measuring the variance in their responses to decide whether to cascade to a larger model.
Impact Statement
For classification tasks, early stopping is another cascad- ing strategy (Li et al. 2021: Schuster et al. 2022). In this approach, the cascade halts when a model's intermediate layers generate representations that are sufficiently infor- mative to predict the correct class. This reduces compu- tational costs by avoiding the need to process every query through the entire model.
Our work can significantly impact the field of model selec- tion strategies. By providing a theoretical foundation for routing and cascading, we have shown that these strategies can be improved by using more accurate quality and cost estimates. Cascade routing combines the strengths of both routing and cascading and offers a more flexible and effec- tive model selection strategy. Furthermore, by underscor- ing the importance of quality estimation, we highlighted a critical area for future research in model selection strategies that could lead to further improvements in this area.
There has also been specific research on quality estimation within cascading frameworks. Gupta et al. (2024) exam- ine various measures of uncertainty in language model an- swers, evaluating their impact on cascading performance. Meanwhile, Jitkrittum et al. (2023)) explore failure cases in cascading mechanisms that rely on uncertainty, introduc- ing alternative quality measures that enhance cascade effi-
9

---

A Unified Approach to Routing and Cascading for LLMs
Acknowledgements
10.48550/ARXIV2241100 13284. URL http:://:///di.oor 10. 11.4550//axiv...o 2418. 13284
This work was funded in part by the Swiss National Sci- ence Foundation (SNSF) 1000021_2096666
Clark, P.. Cowhey, I., Etzioni, O., Khot, T., Sabharwal, A., Schoenick, C.,, and Tafjord, O. Think you have solved question answering? try arc, the A12 reasoning chal- lenge. ArXiv preprint, 1801. 2018.
This work has been done as part of the EU grant ELSA (European Lighthouse on Secure and Safe AI, grant agree- ment no. 101070617). Views and opinions expressed are however those of the authors only and do not necessarily reflect those of the European Union or European Commis- sion. Neither the European Union nor the European Com- mission can be held responsible for them.
Cobbe, K. Kosaraju, V., Bavarian, M., Chen, M., Jun, H., Kaiser, L., Plappert, M., Tworek, J., Hilton, J., Nakano, R., Hesse, C., and Schulman, J. Training ver- ifiers to solve math word problems. ArXiv preprint, 10.168,, 2021.
The work has received funding from the Swiss State Secre- tariat for Education, Research and Innovation (SERI).
Damani, M., Shenfeld, I., Peng, A., Bobu, A., and Andreas, J. Learning how hard to think: Input-adaptive allocation of LM computation. CORR, abs/2410.04700 2024. doi: 10. 1044550/ARXX.22410007000 URL httpttts//o::ooorr
References
Austin, J., Odena, A., Nye. M. I., Bosma, M.. Michalewski, H., Dohan, D., Jiang, E., Cai, C. J., Terry, M., Le, Q. V., and Sutton, C. Program synthesis with large language models. CoRR, abs/2108.07732, 2021. URL /ttps://
10. 00.48550/arXiv http://arxxiv..2.... 201.
Ding, D., Mallick, A., Wang, C., Sim, R., Mukherjee, S., Rühle, V., Lakshmanan, L. V. S., and Awadallah, A. H. Hybrid LLM: cost-efficient and quality-aware query routing. In The Twelfth International Confer- ence on Learning Representations, ICLR 2024, Vienna, Austria, May 7-11, 2024. OpenReview.net, 2024. URL https:// wwt.://weeeeooommmmm/0/00mmommm
arxiv www..orggaabs/210.0777
Chen, D., Zhuang, Y., Zhang, S., Liu, J., Dong, S., and Tang, S. Data shunt: Collaboration of small and large models for lower costs and better performance. In Wooldridge, M. J., Dy, J. G., and Natarajan, S. (eds.). Thirty-Eight AAAI Conference on Artificial In- telligence, AAAI 2024, Thirty-Sixth Conference on Inno- vative Applications of Artificial Intelligence, IAAI 2024, Fourteenth Symposium on Educational Advances in Ar- tificial Intelligence, EAAI 2014, February 20-27, 2024, Vancouver, Canada, pp. 11249-11257. AAAI Press,
Gao, L., Tow, J., Abbasi, B., Biderman, S., Black, S., DiPofi, A., Foster, C., Golding, L., Hsu, J., Le Noac'h, A., Li, H., McDonell, K., Muennighoff, N., Ociepa, C., Phang, J., Reynolds, L.., Schoelkopf, H., Skowron, A., Sutawika, L., Tang, E., Thite, A., Wang. B., Wang. K., and Zou, A. A framework for few-shot language model evaluation, 07 2024. URL/tttss///zenod org/ records/12608602
2024. doi: 10.1609/AAALLV3311002000
https:
7/doi 1rdoi.org/10.1669999 1609//100.aa..... v38110. 29003
Gupta, N., Narasimhan. H., Jitkrittum, W., Rawat, A. S., Menon, A. K., and Kumar, S. Language model cascades: Token-level uncertainty and beyond. In The Twelfth International Conference on Learning Representations, ICLR 2024. Vienna, Austria, May 7-11, 2024. OpenRe- view.net, 2024. id=KgaBScZ4VI
Chen, L., Zaharia, M., and Zou, J. Efficient online MLAPI selection for multi-label classification tasks. In Chaud- huri, K., Jegelka, S., Song, L.,, Szepesvári, C., Niu, G., and Sabato, S. (eds.), International Conference on Ma- chine Learning, ICML 2022, 17-23 July 2022, Balti- more, Maryland, USA, volume 162 of Proceedings of Machine Learning Research, pp. 9716-3746, PMLR, 2022. URL httpps://proceedinngs . mlr. press/v162/ chen22ad. l
Hari, S. N. and Thomson, M. Tryage: Real-time, intelli- gent routing of user prompts to large language models. CoRR, abs/2308. 1 1601,, 2023. doi: 10.48550/ARXIV. 2308. 118811666 11601. URL http::ttpp//ooo.../ http:///ooo.rr/////./ /tt:://doo..rr11118////0///////0
Chen, L., Zaharia, M., and Zou, J. Frugalgpt: How to use large language models while reducing cost and improv- ing performance. CoRR, abs/2305.05177 2023. doi: 10.48550/ARXI.2305500111 156660.0....6..... [RL/https:///oo.org/) 10. 10.48550/arXiv 2ttp:///aaXxv.225..025 2aw..2235..177777 05176
2308. 11601
Hendrycks, D.,, Burns, C., Basart, S., Zou, A., Mazeika, M., Song, D., and Steinhardt, J. Measuring massive mul- titask language understanding. In Pruc. of ICLR, 2021.
Chuang, Y., Zhou, H., Sarma, P. K., Gopalan, P., Boc- cio, J., Bolouki, S., and Hu, X. Learning to route with confidence tokens. CoRR, abs/2410. 13284, 2024. doi:
Hu, Q. J., Bieker, J., Li, X., Jiang, N., Keigwin, B., Ran- ganath, G., Keutzer, K., and Upadhyay, S. K. Router- bench: A benchmark for multi-llm routing system.
10

---

A Unified Approach to Routing and Cascading for LLMs
CoRR, abs/2403. 12031, 2024. doi: 10.48550/ARXIV. 2403.12031. URL htt.httts::/ddi.orr/100 4rr5.///........//r....v..
Jitkrittum, W., Gupta, N., Menon, A. K., Narasimhan, H., Rawat, A. S., and Kumar, S. When does confidence- based cascade deferral suffice? In Oh, A., Naumann, T., Globerson, A., Saenko, K., Hardt, M., and Levine, S. (eds.), Advances in Neural Information Processing Systems 36: Annual Conference on Neural Information Processing Systems 2023, NeurlPS 2023, New Orleans,
2403. 12031
Hui, B., Yang, J., Cui, Z., Yang, J., Liu, D., Zhang. L., Liu, T., Zhang, J., Yu, B., Dang, K., Yang, A., Men, R., Huang, F. Ren, X., Ren, X., Zhou, J., and Lin, J. Qwen2.5-coder technical report. CoRR, abs/2409. 12186, 2024, doi: 10.48550/ARXIV. 2409.12186. UtL/Ittps:///o..org/// 40550//a00000000..... 2409. 12186
LA, USA, December 10 - 16, 2023, 2023b. URL http:
7/papers wwt.ss.iisssccc.c....... httppppp./c/ppppeeeeeeeee/e////e
rence.
html
Jain, N., Han, K., Gu, A., Li, W., Yan, F., Zhang, T., Wang, S., Solar-Lezama, A., Sen, K., and Sto-
Khalili, L., You, Y., and Bohannon, J. Babybear:
Cheap inference triage for expensive language models. CoRR, abs/2205.11745 2022. doi: 10.48550/ARXIV. 2205. URL https://///o org/ 48550/ axiv. 2205.
ica, I. Livecodebench: Holistic and contamination free evaluation of large language models for code. CoRR, abs/2403.0799 2024. doi: 10,48550/ARXIV. 2403.07974. URL http::://oi..orrr /1t.:////..////////////// arxiv. 2793.87974
Lewkowycz, A., Andreassen, A., Dohan, D., Dyer, E., Michalewski, H., Ramasesh, V. V., Slone, A., Anil, C., Schlag, I., Gutman-Solo, T., Wu, Y., Neyshabur, B., Gur-Ari, G., and Misra, V. Solving quantita- tive reasoning problems with language models. In Koyejo, S., Mohamed, S., Agarwal, A., Belgrave, D., Cho, K., and Oh, A. (eds.), Advances in Neural Information Processing Systems 35: Annual Con- ference on Neural Information Processing Systems 2022, NeurlPS 2022, New Orleans, LA, USA, Novem- ber 28- December 9, 2022, 2022. URL. http:
Jang, J., Kim, S., Ye, S., Kim, D., Logeswaran, I.., Lee, M., Lee, K., and Sco, M. Exploring the benefits of training expert language models over instruction tuning. In Krause, A.. Brunskill, E., Cho, K., Engelhardt, B., Sabato, S., and Scarlett, J. (eds.), International Con- ference on Machine Learning, ICML 2023, 23-29 July 2023, Honolulu, Hawaii, USA, volume 202 of Proceed- ings of Machine Learning Research, pp. 14729. PMLR, 2023. URL httpss:://prroceedinng mlr. prrss// /202/jang23a.hom
/ Seapersmnnss.ccappeer.lll/////pp
Jang, A. Q. Sablayrolles, A., Mensch, A., Bamford, C., Chaplot, D. S., de Las Casas, D., Bressand, F., Lengyel, G., Lample, G., Saulnier, L.., Lavaud, I.. R., Lachaux, M., Stock, P., Scao, T. L., Lavril, T., Wang. T., Lacroix, T., and Sayed, W. E. Mistral 7b, CoRR, abs/2310.06825, 2023. doi: 1048550/ARKIV:3310065555
Sabbeerfffeeeoffffooocc444ale2e. html
Li, L., Lin, Y., Chen, D., Ren, S., Li, P., Zhou, J., and Sun, X. Cascadebert: Accelerating inference of pre-trained language models via calibrated complete models cascade. In Moens, M., Huang, X., Specia, I.,, and Yih, S. W. (eds.). Findings of the Associa- tion for Computational Linguistics: EMNLP 2021, Vir- tual Event / Punta Cana, Dominican Republic, 16-20 November, 2021, pp. 475-486. Association for Com- putational Linguistics, 2021. doi: 10.18653/V1/0021. FINDINGS-EEMNIPPS. URL httpps://6oi.org//10 18653/w1/2021. www..iinninnsseee.....33
Jimenez, C. E., Yang. J., Wettig, A., Yao, S., Pei, K., Press, O., and Narasimhan, K. R. Swe-bench: Can language models resolve real-world github issues? In The Twelfth International Conference on Learning Representations, ICLR 2024, Vienna, Austria, May 7-11, 2024. OpenRe- view.net, 2024. WRT. httpp:: wwt.:/ee///ooooooe umm Id=VTF8yN0M66
Jitkrittum, W., Gupta, N., Menon, A. K., Narasimhan, H., Rawat, A. S., and Kumar, S. When does confidence- based cascade deferral suffice? In Oh, A., Naumann, T., Globerson, A., Saenko, K., Hardt, M., and Levine, S. (eds.), Advances in Neural Information Processing Systems 36: Annual Conference on Neural Information Processing Systems 2023, NeurlPS 2023, New Orleans, LA, USA, December 10 - 16, 2023, 2023a. URL http:
Liu, Y., Zhang, H., Miao, Y., Le, V., and Li, Z. Optllm: Optimal assignment of queries to large language models. CoRR, abs/2405.1 15130, 2024. doi: 10.48550/ARXIV. 1505. URL htttp::////// org/10, 48550/arXiv. 15136]
Lu, K. Yuan, H., Lin, R., Lin, J., Yuan, Z., Zhou, C.,, and Zhou, J. Routing to the expert: Efficient reward- guided ensemble of large language models. In Duh, fi0eeeef0S54ccff3aaaaaaeeeeeaeee Abstraactttbbattttcccccca waapossrrrct-oofeeeeeetee Conference K., Gómez-Adorno H., and Bethard, S. (eds.). Pro- ceedings of the 2024 Conference of the North Amer-
html

---

A Unified Approach to Routing and Cascading for LLMs
ican Chapter of the Association for Computational Linguistics: Human Language Technologies (Volume 1: Long Papers), NAACL 2024, Mexico City, Mex- ico, June 16-21, 2024, pp. 1964-1974. Association for Computational Linguistics, 2024. doi: 10.18633/V1/ 2024NNAACL-LONG..00. URL https://doi.org//B) 18653/w1/2624.naace Long. long.oo.. 109
10.48500ARXI.220000002 UtL.httss://doi.org 10. 48.455//aarii....
Sakota, M., Peyrard, M., and West, R. Fly-swat can- non? cost-effective language model choice via meta- modeling. In Caudillo-Mata, L. A., Lattanzi, S., Med- ina, A. M., Akoglu, L.,, Gionis, A., and Vassilvitskii, S. (eds.), Proceedings of the 17th ACM International Conference on Web Search and Data Mining, WSDM 2024, Merida, Mexico, March 4-8, 2024, pp. 606-615 URL
Madaan, A., Aggarwal, P., Anand, A., Potharaju, S. P., Mishra, S., Zhou, P., Gupta, A., Rajagopal, D., Kap- paganthu, K., Yang, Y., Upadhyay, S., Mausam, and
ACM, 2024. doi: 10.1145/361685553666 https: https://6oi.orr/10. Stapar/g/...111//1111 1155/3616685.333388
Faruqui, M. Automix: Automatically mixing lan- guage models. CoRR, abs/2310. 12963, 2023. doi: 10.45500ARXI12231002296 URL /RL.https://dbi.orr/ 10.48550/arXiv.222 wwt..a.........2.....
Schuster, T., Fisch, A., Gupta, J., Dehghani, M., Bahri, D., Tran, V., Tay, Y., and Metzler, D. Confident adaptive language modeling, In Koyejo, S., Mohamed, S., Agarwal, A., Belgrave, D., Cho, K., and Oh, A. (eds.), Advances in Neural Information Processing Systems 35: Anmual Conference on Neural Information Processing Systems 2022, NeurIPS 2022, New Orleans, LA, USA, November 28- December 9, 2022, 2022. http:
Nguyen, Q. H., Hoang, D. C., Decugis, J., Manchanda, S., Chawla, N. V., and Doan, K. D. Metallm: A high- sech-pefformant and cost-efficient dynamic framework for wrapping llms. CoRR, 15/2407.10834 2024. doi: 000.550/RXXV.240..0055 URL httphttss///do..rrg 10. 48558/arXxi
//papers.nipss.ccpppprrrr http:///pppppprllleee/////////// 3aaco31llaaa55a22444cc11122222.3 Confrreccee html
Ni, J., Xue, F. Yue, X., Deng, Y., Shah, M., Jain, K., Neubig, G., and You, Y. Mixeval: Deriving wis- dom of the crowd from LLM benchmark mixtures. CoRR, hbs/2406.065655 2024. doi: A0.48550/ARXIV. 2406.06565. URL http:::////0110001104094055505/ 2406. 06565
Shnitzer, T., Ou, A., Silva, M.. Soule, K., Sun, Y., Solomon, J., Thompson, N., and Yurochkin, M. Large language model routing with benehmark datasets. CoRR, abs/2309. 15789, 2023. doi: 10.48550/ARXIV. 2309. URL http:tts//ooo.orrg/////o 48550////10110////////
Nie, L., Ding, Z., Hu, E., Jermaine, C. M., and Chaud- huri, S. Online cascade learning for efficient infer- ence over streams. In Forty-first International Confer- ence on Machine Learning, ICMI. 2024, Vienna, Aus- tria, July 21-27, 2024. OpenReview.net, 2024. URL bttps://openrewieet http://wwww.tttooommnn/////aaaaa
7309.15788
Varshney, N. and Baral, C. Model cascading: To- wards jointly improving efficiency and accuracy of NLP systems. In Goldberg, Y., Kozareva, Z., and Zhang, Y. (eds.), Proceedings of the 2022 Conference on Empirical Methods in Natural Language Processing. EMNLP 2022, Abu Dhabi, United Arab Emirates, De- cember 7-11, 2022, pp. 11007-11021, Association for Computational Linguistics, 2022. doi: 10.18653/VI/ 202. URL URL/ittp::///0..or///// 18653/v1/2022. wwtp:/22222.mmmp...m em main. 756.
Ong. I., Almahairi, A., Wu, V., Chiang, W., Wu, T., Gonzalez, J. E., Kadous, M. W., and Stoica, I. Routellm: Learning to route Iims with preference data. CoRR, abs/2406. 18665, 2024. doi: 10.48550/ARXIV. 2406.18665. URL http::////6011000111.88885550000
2406. 18665
Wang, Y., Ma, X., Zhang, G., Ni, Y., Chandra, A., Guo, S., Ren, W., Arulraj. A., He, X., Jiang, Z., Li, T., Ku, M., Wang, K., Zhuang, A., Fan, R., Yue, X., and Chen, W. Mmlu-pro: A more robust and chal- lenging multi-task language understanding benchmark. CoRR, abs/2406.0155 2024. doi: 10.48550/ARXIV. 2406.01574. URL httph:ttts::ooogg//ooo 40550////.....////.......
OpenAI. GPT-4 technical report. CoRR, abs/2303.08774, 2023. doi: 10.485500/2Xx..2230..87777
Pichlmeier, J., Ross, P., and Luckow, A. Domain-Awee Aware LLM Routing During Generation In 2024 IEEE Inter- national Conference on Big Data (BigData), pp. 8235- 8237, Los Alamitos, CA, USA, December 2024. IEEE Computer Society. doi: 10. DiL10///BiDDaa222222224 10825152. URL https:://oooi.... http:s///oo...eeecootteeeeeeeees iececoopuuerssociitty otgg/..1119/Biii...... 1119///ggaaaa22223..... 2624. 16825152
Xue, M., Liu, D., Lei, W., Ren, X., Yang, B., Xie, J., Zhang, Y., Peng, D., and Lv, J. Dynamic voting for ef- ficient reasoning in large language models. In Bouamor, H., Pino. J., and Bali, K. (eds.), Findings of the Asso- ciation for Computational Linguisties: EMNLP 2023,
Ramírez, G., Birch, A., and Titov, I. Optimising calls to large language models with uncertainty-basee two- tier selection. CoRR, abs/2405.00 02134,, 2024. doi:
12

---

A Unified Approach to Routing and Cascading for LLMs
Singapore, December 6-10, 2023, pp. 3085-3104. As- sociation for Computational Linguistics, 2023. doi: 10. 10055///1222.FNNNN-GEEEEMMLLLL
URL https: 7/doi //dol.org/10.18633332 11119/12..663331//22233.. fin.iiiggn..innnn........ emn Lp 203
Yang, A., Zhang, B., Hui, B., Gao, B., Yu, B., Li, C., Liu, D., Tu, J., Zhou, J., Lin, J., Lu, K., Xue, M., Lin, R., Liu, T., Ren, X., and Zhang, Z. Qwen2.5-math technical report: Toward mathemattcal expert model via self-improvement. CoRR, abs/2409. 12122, 2024. doi: 10.48550/ARXXV.2200.1112 12122. URL/httss://6bi.org 48.48550/arXiv. 2489.
Zhang, K., Peng, L.. Wang, C., Go, A., and Liu, X. LLM cascade with multi-objective optimal consider- ation. CoRR, abs/2410.08014, 2024a. doi: 10.
48550/ARXIV.241000001444 URL https://doi.org/ 10. 1B.48558/arx3..2410..G8
Zhang, K., Yao, W., Liu, Z., Feng, Y., Liu, Z., Murthy, R., Lan, T., Li, L., Lou, R., Xu, J., Pang. B., Zhou, Y., Heinecke, S., Savarese, S., Wang, H., and Xiong, C. Diversity empowers intelligence: Integrating ex- pertise of software engineering agents, 2024b. URL https///arxv..om/bb///44.0000
13

---

A Unified Approach to Routing and Cascading for LLMs
A. Routing
First, we explain how to obtain the hyperparameters and y for the routing strategy. We then provide a more exact formulation of the routing optimization problem and prove Theorem [
Hyperparameters Due to the second part of Theorem [ only need find set of hyperparameters À and y that achieve the cost budget. Indeed, all routing strategies that have expected cost that is exactly equal to B and can be written as convex combination of * and MAX for some X R+ achieve the same optimal quality.
To determine these parameters, we estimate the cost of a strategy using a validation dataset D that is representative of the query distribution X. We then perform a hyperparameter search to find optimal values of À and y. By leveraging several properties of routing strategies, one can show that this hyperparameter search can be reduced to a single binary search over X, enabling quick and efficient hyperparameter optimization process.
Proving the Theorem program over functions X R instead of functions X As. This makes the optimization problem more tractable. Specifically, Eq. ① can be rewritten follows:
To prove Theorem I we first rewrite the routing optimization problem in Eq. as linear
max BRNX
Σ (x)
s.t. Exex
Σ (x)) <B B
(2)
k Vi (1...., B} Vo E X: 8:(x) 2 0 Σ s5(x) =1
j=1
We then rewrite Theorem M to allow for a more exact formulation of the optimal routing strategy:
Theorem 4. (Optimal Routing Strategy) Suppose there exists admissible solution to the set of constraints in Eq.
For any À E IR,,, let Sx be the set of routing strategies s that satisfy the following constraints:
X {L,..., k] g.(x) AE(x)= < mmx (x) (eg(2) s())=
(3)
If there exists strategy in So that has cost less than or equal to B, then this strategy achieves the optimal quality. Otherwise, there exists X E RR such that Sx contains routing strategy that has exactly cost B and all routing strategies in UxeR+ Sx that have cost B achieve the same optimal quality.
There is one extra condition mentioned here that we omitted in the main text. The requirement of having at least an admissible solution to the constraints in Eq. 2 is necessary to ensure that the set of possible solutions to Eq. (2) is not empty. For instance, the cost budget B can be too low such that even running the cheapest model for each query is too expensive.
The formulation of SoPr_a0 as a convex combination of s and MAX a direct consequence of Theorem 4 Indeed, let X be defined in Theorem 4 Then s resp. SMxX must have the lowest, resp. highest, cost among all routing strategies in Sx.. Since there is routing strategy in Sx- that has cost B, there must exist convex combination of s and s that also has cost B and thus achieves the optimal quality.
We first prove several lemmas before proving the theorem.
Lemma 2. Sx is non-empty and convex for all X E R+
Proof. Non-emptiness follows from the fact that the routing strategy that assigns all probability mass for sample x to model i for which (x( - (a((x) is maximal, is in Sx. For convexity, let s(1), ((2) E Sx be arbitrary. Let 87 be the convex
combination of (1) and (22) with weight 7 [0, 1]. Let X' be arbitrary. Then, s7 (x) > if and only if s (1)
(x:
or 8 (x) > 0. Since ,()),{()) E Sx, we have (x) - xx(x) > max, & (x) Ad, (x) for all such that s (x) > 0r
(2) (x) > 0. This implies that (x) \x((x)) max, & (x) (x) for such that s7 (a) > 0. Thus, 8 E S2.
14

---

A Unified Approach to Routing and Cascading for LLMs
Lemma 3.
Let X1 < x2 and s03, resp. greater or equal the cost of s(2), iee,
8(2) be arbitrary routing strategies in Sya. resp. Sxy- Then, the cost of s(2)
k
k 2 (x)a
E ExEx
Σ
5 (o)a(())
> Bexx
Σ
Proof. We show that for any x E X, the cost of (22) is greater or equal to the cost of 8(2) Let E X be arbitrary. Suppose g(1) is strictly cheaper than s(2), Then, there must exist a model pair i such that (z) < 22((2), of > of (x) > 0.
and oj ( (xr) > (x) > O. However, of (x) > 0 implies
(x)
((())))((1))
> (1)(())))())))
Furthermore, since A1 - 22 O, we have
(()) -22) > (x)( - -22).
Adding these two incqualities gives
((()) - X2((x) > (x(2)) (222(T),
which is a contradiction with 8) (f) > O. Thus, the cost of (1) is greater or equal to the cost of s(2)
Lemma 4. Let A be the sei of points À E R such that there exist an x E X and i + j such that (((x) - (0(()) = (x) - -G2 Let d1 < A2 be such that (11, n = 9. Then, Sy = Sxy. Furthermore, if [1, A2] n = {X*}, then
Sx C Sx- for all X E (2).
Proof. We first show the first statement by showing that Ss \ Sx₂= = Sx₂ \ Sx, = follows analogously. Suppose there exists a routing strategy E Sx, \ Sxa. Since s & Sxz, there must exist an x E X and model such that sx(x)) 0 and (z)x) - (z) max, (x) (x). Let j be an index such that (z) )zd((z) < & (z) )2 Since E SX., we have (x)) - ( b (z)) (x). By continuity, there exists a À [Ar, such that (z) (x()) (x) - (x)( which is contradiction with [21, n = 0.
Now suppose (Ar, A2] n = (A*). Let X E A*) be arbitrary and let 8 E Sx be arbitrary. We show that 8 E Sx-- For E (X*, A2). the proof is completely analogous. By contradiction, suppose there exists an x E X and model such that sx(x) 0 and (z(x) (x) < max, (x) - (x). This means there exists a model j such that (x(x) - X ( <
(x) (z). Since s E Sx, we know that (. (x) > (x) (x)) This implies that there must exist
X E (*1, such that (x) Nā(x)= (x) X (x). However, this is contradiction with [}, A²) nA = 0. Thus,
E Sx-.
In what follows, we will assume that |A| < xc. This is very minor assumption. For instance, if & and é only take on a finite amount of values, this is trivially satisfied. Since estimators are implemented on computer, they will always have a finite precision, meaning that ② and é will only take on a finite amount of values.
Lemma 5. Let X < X2 and 8(), resp. s(2) be arbitrary routing strategies in Sx resp. Sxa, with costs resp. B, and B Then, for any B E [B1, B2] there exists a E [>1, such that Sx contains a routing strategy that has exactly cost B.
Proof. Let B E [Bi, B2] be arbitrary. If
Bi or B B2, the statement is trivially true. Therefore, suppose B E (B1, B2). Let be as defined in Lemma By Lemma
3 there exists X E A2] such that all strategies in Sx for À X*, resp. À >> X", have cost at least, resp. at most, B. If X & A, then the first part of Lemma 4 together with |A| < co, implies that Sx- Sx- Sx-+e for some least and at most B, meaning they should equal B. We can therefore assume that X E A. By Lemma 4 and |A] < 00,
0. All the strategies in Sx- must therefore have cost both at
there is en E > 0 such that Sx- - C Sx- and Sx-+e C Sx.. Lets E -x--c and s E Sx-+e te be arbitrary. Let 87 be the
convex combination of 8 and s with weight y E [0, 1]. Since s5 E Sx-, we have s E Sx- by Lemma 2 Denote by B resp. B the cost of s resp st. Furthermore, the cost of s7 is B + (1 - B+ Since E [B B there exists y E [0, 1] such that s has cost exactly B.
We can now prove the theorem.
15

---

A Unified Approach to Routing and Cascading for LLMs
Proof. If Sy contains solution that has cost less than or equal to B, then this solution trivially achieves the optimal quality. Thus, for the rest of the proof we can assume that the cost of every solution in So is greater than B. For À + co, Sx contains the solution that assigns all probability mass to the model with the lowest cost. Since there is an admissible solution, this solution necessarily has cost less than B. Therefore, by Lemma S contains a routing strategy that has exactly cost B.
there exists X IR such that Sx-
Let be an arbitrary routing strategy in UXER+ Sx that has cost B. Specifically, let 8 Sx. Let s' be any other routing strategy that is an admissible solution to the optimization problem. Then:
A Σ
Baex
(()))(()))
= -EEE
Σ {(())()))) AB
< E ExEX
(((x) (1:(2) - ^a(x)) AB
< Exex
Σ sc(x)) (4:(0)) - xa(x)) +B
Exx
Σ ((())((()))
Thus, s achieves the optimal quality.
B. Cascading
To prove Theorem 2 we heavily rely on the results derived in App-AA As explained in S cascading can be reinterpreted as a sequence of routing problems. However, to prove optimality, we need to be slightly more careful with the exact formulation of the problem.
At step j. the cascading strategy needs to decide whether stop the cascade or continue to the next model. It should con- tinue to the next model if any of the supermodels M Mis better run than M1 for some measure of 'better'. Therefore, the cascading strategy is indeed performing routing operation between the supermodels Mı:j-1,.... Mi
However, the optimization problem does slightly change compared to the routing problem. First of all, for each query E X, there is a possibility that the cascade is stopped before step j. Therefore, the cascade should not aim to optimize the quality at step j for such a query, since it would not have any effect on the overall quality of the cascade. Furthermore, the budget B is only enforced over the entire cascade, and not over the individual steps. Since the problem changes through steps, is not required that the cost of the router at step j is exactly equal to B.
Therefore, reformulate cascading using inner and outer optimization problem. The inner optimization problem aims to find the optimal routing strategy step j for given budget By. The outer optimization problem aims to find the optimal budget Bj for each step j such that the overall quality of the cascade is maximized under the constraint that the total cost of the cascade is at most B.
To formulate this more exactly, let P, ) be the probability that the cascade computed supermodel M by step j. Then, the inner optimization problem step j can formulated as:
16

---

A Unified Approach to Routing and Cascading for LLMs
max ru)
E Exox
Pj (M
Σ
na(3))
==1-1
s.t. Baox
Py(M11-1)
Σ
( (a)
< Bj
(4)
i=j-1
Vi 11- Vor X (2)
2 DA
Σ (2)(2)) =1
(=1-
Note that P3 (M can be incorporated in the quality and cost estimates. This leaves with the exact same optimization problem the routing problem, but with different budget By. Since the chosen model only depends the maximization of (M (z) P, (M (I), the probability P, ( can be divided out of the optimization problem.
The inner optimization problems prove the existence of optimal routing strategies at each step with parameters X₃- We note that there only needs be one parameter 7 that determines the convex combination since the budget B only enforced over the entire cascade.
Let us denote the quality and cost of the entire cascading strategy for given parameters X X and 7 as Q(A and C(A1...., )u, respectively. Then, the outer optimization problem can be formulated as:
max
Q(A 7u:
A
(5)
s.t. C( AE, &
To solve this outer optimization problem, we simply perform a hyperparameter search over the budgets BI...., Bx using a hyperparameter optimization search as discussed in $3
B.1. Prior Approximations
We now prove Corollary [ let C1 be defined as follows:
Before doing so, we first need to define what we exactly mean by equivalency. For this purpose,
C { is cascading strategy with parameters A du, = 0 using estimates g00) (,,
Similarly, C2 be defined as follows:
C2 = is thresholding strategy with parameters Ti,..., Tk using estimates g0),e(0))
e(ii}
We note that we set 7 0 since the thresholding strategy is deterministic. We therefore restrict the cascading strategy to be deterministic well.
We define the equivalence between the two sets as follows:
Definition 6 (Equivalence of Strategies), We say set of strategies C1 is equivalent to another set of strategies C2, denoted as C₁ Cz. for all so E C U C2 there exists a $1 E C₁, and C2 such that for all x E X, su. $1 and $2 take the same decisions on x.
We can now more accurately state the conditions under which the thresholding strategy is equivalent to the optimal strategy. Corollary (Optimal Thresholding Strategy). Let C₁ C2 be defined as above. Then, C₁ C2 if and only if there exists alternative quality and cost estimates gf"% (x) and e!"" (x) with associated set of cascading strategies C₁ such that C1 C₁ and the following conditions hold on these alternative quality and cost estimates: a(11 (x) is independent of x and bigger than 0, <i) (x) is independent of x for all i > j. and qit (x) is equal to اااا" (x).
The main difference between Corollary 2 and Corollary iss that we impose the possibility of alternative quality and cost estimates. However, this does not really influence equivalency in the intuitive sense. Indeed, one could alternatively phrase
17

---

A Unified Approach to Routing and Cascading for LLMs
the corollary follows: the thresholding strategy is equivalent any of our cascading strategies if and only if is possible construct alternative estimates such that the conditions hold.
Proof. We note that the cascade E C1 continues sample if the following condition holds:
-
max (E(....)))
d (x) Aycl (x)
(6)
If C1 Ci it is clear that Eq. (6) reduces to the thresholding strategy for all strategies in C₁. Indeed, for any & E C₁,
(()
A and the thresholding strategy is equivalent to 8. Alternatively, if C2, suppose
(t)
set Tj ()... 91s
ma..e k} d A5cl2 =g13 -y for some index i. Then, set X / / /ofa and the cascading strategy
is equivalent to s. Therefore, C1 Ci C2.
Suppose now that Ci = Cz. We construct alternative quality and cost estimates q, /."h" (x) and 2لااy (x) such that the conditions
hold and such that Ci C₁. For this purpose, define (3) (I) for all i. E (I,...,k) qi (2) 1 for all i >> j.
()) (x) a (x:) otherwise. Furthermore, we set 01s (x) (5) (x) for all i, (1...., kj. The equivalence of C
and d3 and C2 can now be proven analogously to the previous paragraph. Therefore, C₁ = Ci = C2.
C. Cascade Routing
We first note that the proof of the optimality of the cascade routing strategy is equivalent the proof of the optimality of the cascade strategy, except that the expectation in the optimization problem Eq. 4 is now not only over X, but also over all possible supermodels that were computed by step j - However, this does not change the optimization problem, To prove the
and the proof is completely analogous to the proof given in 3 Thus, all we need to prove is Lemma 1 lemma, we first prove the following lemma.
Lemma 6. Let Q1...., Qx be distributions. Let S be the superset of k}. Then f S - R defined as f(S) E(maxies Qi) is submodular. Here, we define max Q; -00
Proof. Let CC( (L....., k} and j {L....,k) k} be arbitrary. To show the submodularity of f. need to show that ((TU 2 -(s ((S).
We can write:
((SUU) f(S) = E max Q:) - E max Q,) SES
(ES
E(max (0, Qj max Q:))
E(max (0, Qj max Q.))
iET
EE max Q,) Tmmax Q:) (ETU())
1ET
fTT {í)) - f(T).
In the proof, we needed maxeu Qi = -0 in the case T = 0.
We note that the assertion that max;e Qi = -o corresponds to the fact that giving no answer to a query has -oo quality.
We can now prove Lemma
Proof. Let M and m be in the lemma. Suppose M' is supermodel that contains all models in M. Furthermore, let M M' \ m. We show that the supermodel M is always strictly preferred over M'. To this, we note that the difference between TMe (z, X) and TM (z, A) is equal to
E( max Qmr (x)) - E( max (x)) Ayūm(()) m' m'EM"
me W'
By Lemma 6 this difference is smaller than (x) - q (M),(m)(z)) (z) - (x) Thus, by assumption, this difference is negative, and therefore M" is always preferred over M', which concludes the proof.
18

---

A Unified Approach to Routing and Cascading for LLMs
Table 3: Standard deviations of the noise levels on the RouterBench dataset.
Quality
Cost
Tbefore
Fater
Tbefuee
Falter
Low
0.6
0.3
0,0002
0.00005
MEDIUM
1.6
0.8
0.0004
0,0001
HIGH
2.4
1.2
100
100
D. Experimental Details
We describe some additional details about the experimental setup and the datasets used our experiments.
D.1. Routerbench
Data Split We use 5% of the RouterBench data (around 2000 samples) to optimize the hyperparameters of cascading, routing, and cascade routing. The remaining 95% is used for evaluation. We use the same data split for all noise levels.
Noise Table we specify the standard deviations of the noise levels on the RouterBench dataset. To put these numbers into context, we note that quality varies between and and the average cost of the smallest models is 0.000073, while the average cost of the largest models is 0.003281. We fit logistic regression model this noisy signal to obtain the quality and cost estimates. This simulates the noise in the features that are used to estimate the quality and cost of the models.
Models In the evaluated scenarios for three models, use the models MIXTRAL- -EATAAL--XB--CAAY 1106, and GPT-4- 10T-4-1100-PPP PREVIE... When using five models, we add WIZARDLM-1338 13B-V1.2 and CLAUDE-V2 to the mix. For eleven models, we use all models available in the benchmark.
D.2. Accurate Quality Estimation
Data Split For the SWE-Bench benchmark, we use its verified data split and divide the dataset into training and cali- bration subsets, with each comprising 50% of the data. For the Minerva Math and LiveCodeBench benchmark, we only include the Algebra portion of Minerva Math to ensure that both benchmarks have a comparable number of samples for evaluation. Similarly, we also perform 50% split of this dataset into training and calibration sets.
Evaluation Setting For the SWE- evaluation, we analyze the performance of 10 models submitted the bench- mark's leaderboard. The logs for these models were obtained from the official SWE- repository Specifically, we evaluated the following models:
www.44022.weagentccclee claude3opus
28241997_nfactoria
20240728
20240728_sweagent wweagent_gpt40
9224622_.weageettcccade..
00241016.epam-aii- -o
20240824_gru
28241106_navie-2 2-ptaii----ttto-sooeeet
20240820_epam -0
28241028 agentless-1.5.gptteee
For each model, extract the time required to complete task to measure cost.
http:/gttthi.....s/.eeeeeeet com/swe- bewpbbeeeeeeeeeeeeeteesseeeee
19

---

A Unified Approach to Routing and Cascading for LLMs
For BivchodeBench and Minerva Math, evaluate the following models:
QWEEN22.-COODRR-7--IIRRR
QWEE-2.5-COODER-1.. 1.5-INRRRUC
QWEN-2..5MAAIII-7-BNNSRRR
QwEN-22.--MAYTI--5B--INNN
We conduct experiments using version 5 of the LiveCodeBench benchmark from its official repository. For Minerva Math, we utilize the LM Evaluation Harness (Gao et al. 2024) to ensure consistent and reliable evaluation.
Cost Estimation For SWE-Bench, the cost is defined as the time (in seconds) that model takes to complete task. A linear regression model is fitted to predict this cost based on the query length and, when available, the cost of running other models.
For LiveCodeBench and Minerva Math, the cost is calculated as the total number of tokens in both the query and the answer, multiplied by the size of the model (in billions of parameters). Similar SWE-Bench, linear model is used to predict the cost based query length and other models' costs.
Quality Estimation For ex-ante quality estimation in SWE-Bench, train logistic regression model that predicts quality based on the query length and one-hot encoded variable representing the query's 's source repository. Post-hoc quality estimation leverages the ground-truth quality scores computed during evaluation.
For ex-ante quality estimation in Minerva Math and LiveCodeBench, we include the query length, query source (Minerva Math or BineCodeeenchh, and the difficulty level of the problem as defined by the benchmark. Post-hoc quality estimation incorporates additional information, such as whether the parsed answers from different models agree with one another.
D.3. Poor Quality Estimation
Data Split We split each dataset in each benchmark into a training set and test set, each comprising 50% of the data. For all datasets except GSM8k, the training set is created by splitting the original test data. In the case of GSM8K, since a separate training set is already available, we this pre-existing training data, leaving the original test set unchanged. The training set is then further divided, with 50% used for training quality and cost estimators, and the remaining 50% reserved for hyperparameter optimization through validation.
Evaluation Setting We use completion-bass based evaluation in a one-shot setting for each benchmark. For the classification tasks, we obtain the probability associated with each class ("A", "B", "C",... from the model directly. For open-form reasoning tasks, we extract the answer by instruction the model to generate a completion that ends with an extractable answer. If the model does not output an answer in the correct format, we perform best-effort extraction by trying various regex patterns. Details on the prompts and regex patterns used for each benehmark are provided in the code repository.
Models For the LLAMA-3.1 model family, we use the models LLAMA-3. 1---A-33--BB-ISSTRCCT LLAMA-3. 3.-M---.1-7BB... INSTRUCT, and LLAMA-3.11405EB --0SS--INT For the GEMMA model family, INSTRUCT, GEMMA-2-9B-INSTRRCCT and -A-.---XXX--SSTTUTT-OOOOO and MIXTRAL-8X22B I-N.SSITT--TTTT-VO..... models MISTRAL- 7B 7-------BIUTTTOOO MIXTRAL-8X
the models GEMMA-2B. For the MISTRAL model family, we use the
Cost Estimation For cost estimation, we first calculate the number of tokens in both the query and the model's response. We then use API-based prices per token for each model to estimate the cost In classification, where responses consist of a single token, the cost can be determined before running the model. In open-form reasoning tasks, where response lengths vary, we estimate this length based on responses from previous models in the cascade if the model has not yet been computed. If model response is available, we estimate the response length using the average from the training data.
We used the Together API for all our experiments.
20

---

A Unified Approach to Routing and Cascading for LLMs
Table 4: AUC scores in % for different strategies on RouterBench in the 0-shot setting with 2o confidence intervals.
Three Models
Five Models
Eleven Models
Low
High
Low
High
Low
High
Cascade Routing (Ours)
82.37
0.92
76.57 0.96
73.23 -0.3
84.33 0.20
76.32*0.5F
0.97
72.75
1775""0.00 0.40
87.24
2 0.26
77.58 0.33
74.41
0.33
Routing
2.64-0.18
1.5910.3
15
1.40" 15
17
3.10
1.88 0.17
1.41 1.41
+0.17
4.00 17
a1
2.94 20
1.73
Cascade (Baseline)
1.50
0.10
1.91 0.19
0.7418.19 0.
2.00
3.29
0.27
3.22*
0.24
2.761
3.92 00.90
4.61 -0.38
Cascade (Ours)
1.28f0.11
0.39
0.5418.12
1.27
1.14 0.20
2.57
2.77
2.46*0.22
4.14
Table 5: AUC scores in % for different strategies on RouterBench in the 5-shot setting across model and noise levels with 2a confidence intervals. Bold numbers indicate that the confidence interval contains zero
Three Models
Five Models
Eleven Models
Low
Med
High
Low
Med
High
Low
Med
High
Cascade Ronting (Ours) 83.7922.35
78.85
77.1 tt-at
85.5
78.77 22
76.74 0.36
88.7818.2
80.8916.29
78.03
0.31
Routing
2.3 0.14
1.64-8-1
1.1
3.08 10.10
1.94
1.21 10.14
3. 3.43-012
3.13 0..1
1.6
Cascade (Baseline)
-0 00.64 0.11
0.28 -n
10.13
0.22 0.10
1.23
2. 2.19
2.83
1.24
1.64
2.29 10.2
3.09 0.27
Cascade (Ours)
1.02
0.09"0.11
0.31
0.1 0.14
1.25 0.00
1.59 0.17
2.45 0.21
+9.31
2.06 0..1
2:22 0.19
2.95 -0.24
Features Quality Estimates We specify the exact features used for the logistic regression model that serves as the quality estimator in |5.2 First, we include one-hot encoding of the various datasets in each benchmark. Furthermore, for classification, we include the probability associated with the highest class and the entropy of the class probabilities if the model has been computed. If several models have been computed, we include both whether they agree on their prediction, and the JS-divergence between their class probabilities. For open-form reasoning, we include the perplexity, number of tokens, and several quantiles of the logits if the model has been computed, in accordance with Gupta et al. (2024). several models have been computed, we also include whether they agree on their prediction.
We note that we train separate logistic regression model for each history of computed models, and for each model separately as well. Thus have one linear model for each combination of a target model my and computed models mi....., m.,. All the linear models are trained on the training set included in the benchmark.
E. Confidence Intervals
To check whether the results obtained by cascade routing are significantly higher than our baselines in Tables 1 and I0] we perform bootstrapping on the samples in the dataset. Specifically, we compute the confidence interval associated with the difference between the AUC scores of cascade routing and the baselines. If this difference is positive and its 20 confidence interval does not contain zero, we can conclude that cascade routing is significantly better than the baseline.
These confidence intervals are reported in Tables 4
F. Additional Experiments
F.I Ablation Study
We conduct an ablation study to examine the impact of various design choices in cascade routing on performance and runtime. Runtime is critical factor because the overhead introduced by the strategy must be negligible compared to the time required for model computation. If the strategy adds significant overhead, its performance gains may be offset by the increased runtime. We also include an additional ablation that specifically targets runtime on random data App. F.2
To investigate this, we repeat the experiment from $5.1 using all eleven models, testing different variations of cascade routing. We evaluate slower variation that omits Lemma] ! thereby requiring more supermodels to be evaluated (SLOW), a greedy variation that only considers supermodels of length j - at step j (GreEDy), and a version that does not compute the expected value when evaluating supermodel quality, using the quality of the best model instead (No-EXPECT).
Results Table 7 presents the results. As expected, the SLOW variation is almost an order of magnitude slower while achieving similar performance. In contrast, both GREEDY and No-EXPECT are faster but perform worse in the low- and medium-noise scenarios by 0.5% to 1.3%. Interestingly, there is a much smaller performance gap in the high-noise scenario. This is due to the very low variance in the quality estimates, since the linear model used for quality estimation predicts an almost constant value for each query this scenario, making the expected value computation less important.
21

---

A Unified Approach to Routing and Cascading for LLMs
Table 6: AUC scores on the realistic benchmarks with 2a confidence intervals. Bold numbers indicate that the confidence interval contains zero.
SWE: Bench
Math+Code
Classification
Open-Fome Menn-Form
10 MODELS
MODELS
QWEN
I.AAMA
GEMMA
MISTRAL.
L.AMM
GFMMA
MISTRAL
Cascade Routing (Ours)
54.21 7.40
51.20_7.20 7.44
1..95 48.51
2.80
75.56 1.16
L.23
1.30 64.89 1.42
65.02 1.40
79.95_1.33
11:28
1.33
59.70 1-62
58.77 11:42
Routing
2..66*t
11.71 1.38
1.11
0.60 0.60
0.39
0.08
0010
0.56 ss
1.26
1.26-0:57
0.02
Cascade (Baseline)
15.36 +-300
5.17 1.00
10.77
0.71 14.30
10.51 +0.02
3.79 0.73
0.65 0::25
3.47 4..77
10.45 +1115
3:22
Cascade (Ours)
0.83
0.11 1:04
1.05
1.8220:33
0.06"0.17 0.11
2.04
1.67 1.67-0.42
00.41
0.20
2.00-0.36
3.06 +.66
Table 7: AUC scores and average runtime for variations of cascade routing on RouterBench when using all eleven models.
Low-Noise
Medium-Noise
Hiise
AUC (%)
Time (ms)
AUC (%)
Time (ms)
AUC (%)
Time (ms)
Cascade Routing
87.29
15.26
77.61
9.53
74.41
13.68
SLOW
87.30
78.88
77.61
87.72
74.40
88.76
GREEDY
85.93
1.39
77.17
1.17
74.35
0.89
1O-EXPECT
85.98
4.78
77.11
2.49
74.35
2.08
Furthermore, the GREEDY and No-EXPECT variants perform very similarly, while GREEDY is about twice fast No- EXPECT. This suggests that one should almost always use the normal variant of cascade routing, and only consider the GREEDY variant if runtime is critical concern. Neither the SLOW nor the No-EXPECT variant is recommended, as they either perform worse or are significantly slower than the normal variant.
F22 Runtime Analysis
We further analyze the runtime of the four variants of cascade routing presented in App. F.1 Specifically, perform experiments with random data, scaling the number of models to 80 to evaluate the runtime of all variants. Furthermore, we include a fifth variant of cascade routing in the analysis MAX-DEPTIL which restricts cascade routing to a maximum depth of models. MAX-DEPTH does not reduce performance of cascade routing if the optimal depth is less than or equal to models. However, it does significantly reduce the runtime of cascade routing.
For each number of models, we generate 100 data points, each with random quality and cost estimates associated with each model. For each point, generate the hyperparameters A1;-..; As and y randomly. We then report the average runtime of the five variants of cascade routing in Fig. 3
The results show the varying computational complexity of the different variants of cascade routing. S1.w has the highest runtime, and becomes computationally too expensive even when using less than 20 models. In contrast, standard cascade routing has a significantly lower runtime, and able to handle up 40 models within second runtime. Its faster variant, MAX-DEPTH, is able to handle up 80 models within second runtime. Furthermore, we now also see clear difference between NO-EXPECT and GREEDY. While GREEDY remains computationally very cheap even for 80 models, NO-EXPECT has a significantly higher runtime, even obtaining higher runtimes than MAX-DEPTII for 80 models.
Runtime (s)
10a
10a
10"
10
NORMAL
10-2
GREEDY
No EXPECTATION
10-3
Thus, the conclusions from App. are further supported by the runtime analysis: GREEDY is the most efficient variant of cascade routing, while NORMAL is the most efficient variant that does not compromise perfor- mance. MAX-DEPTH is good choice if the optimal depth is known to be less than or equal to 3 models, as it significantly reduces runtime with- out compromising performance. Since cascades of more than 3 models are rare, MAX-DEPTH is a good choice in practice.
MAX DEPTH
4
0
20
40
60
80
Number of Models
Figure 3: Runtime of cascade routing vari- ants for different numbers of models.
22

---

A Unified Approach to Routing and Cascading for LLMs
Table 8: Classification AUC values for each benchmark separately for the experiment performed in 5.2
LLAMA
GEMMA
MISTRAL
MMLU
ARC
MixEval
MMLU
ARC
MixEval
MMLU
ARC
MixEval
Linear Interp.
53.82
93.15
82.86
39.40
82.28
70.97
39.76
85.39
73.03
Routing
55.32
98.12
82.86
40.01
83.13
73.12
40.61
85.64
74.28
Cascade (Baseline)
54.80
94.08
84.15
36.43
77.53
66.10
36.99
83.88
72.73
Cascade (Ours)
55.05 55.40
94.16
84.00
37.68
79.80
70.57
37.03
86.27
74.42
Cascade Routing (Ours)
93.90
83.91
39.93
83.74
73.16
40.56
86.52
74.64
Table Open-fore AUC values for each benchmark separately for the experiment performed in 5.22
LLAMA
GEMMA
MISTRAL.
MMLU
GSM8K
MMLU
GSM8K
MMLU
GSM8K
I Linear Interp.
65.64
94.43
36.52
73.86
41.40
67.84
Routing
65.75
94.15
38.08
75.01
43.03
68.00
Cascade (Baseline)
66.07
95.17
35.76
68.44
38.88
60.82
Cascade (Ours)
66.25
94.94
38.16
71.10
40.76
64.53
Cascade Routing (Ours)
66.60
94.69
40.43
75.25
42.93
68.30
G. Detailed Results
We present benchmark-specific AUC values for the experiment performed in $5.2 Table@foo for classification and Table for open-form reasoning. In Fig. show the quality-cost tradeoff curves for several benchmarks. The curves obtained by varying the cost threshold and plotting the resulting accuracy and cost values in curve.
H. Additional Results
In Table I0 we report the AUC scores for the RouterBench dataset for different noise levels for the five-shot evaluation. Our conclusions presented in $5.1 remaiin consistent with the results presented in Table TO However, there one notable inconsistency: two of the three low-noise scenarios, our cascading strategy performs worse than the threshold-based baseline cascade. In the scenario with three models, we find its cause can be found in the more difficult optimization surface for the hyperparameters of our cascading strategy. Specifically, our cascading strategy at some point starts to lose quality cost increases. By simply setting the hyperparameters of the cascading strategy once it starts to lose quality to the ones where it obtained its highest quality, we obtain quality of 83.35% over the 13.17% of the baseline cascade.
In contrast, for low-noise and eleven models, a similar approach does not yield a better result. Rather, the discrepancy is caused by small mismatch between the quality estimates of supermodels and the chosen model. While the quality estimate is based on the expected maximum of all models, we restrict the selected model to be the last model that was computed in the cascade. Since the expected maximum is higher than the quality of the last model, this discrepancy can lead to suboptimal decisions. By allowing both the baseline cascade and our cascading strategy select the model with the highest quality estimate, we find that our cascading strategy once again outperforms the baseline cascade. Note that this slight discrepancy is not relevant for cascade routing, since the extra restriction is not imposed in this setting.
23

---

A Unified Approach to Routing and Cascading for LLMs
Quality
Quality
Quality
0.8
0.55
0.75
0.7
0.50
0.70
Models
Models
Models
Linear Interpolation
Linear Interpolation
Linear Interpolation
Routing
Routing
0.65
Roating
0.5
(Baseine)
(Baseline)
(Baseline)
Caocade (Ours)
0.30
Cascade (Ouns)
Cascade (Ours]
Coucade Routing
Cascada Routing
Cascade Routing
0.60
0.25
0.002
0.003
0.0000
0.0305
0.0010
Cost
Cost
Cost
RouterBench, medium noise, 5 models
(b) SWE-Bench with 5 models
(c)
Classification task for the LLAMA models
Figure 4: Quality-cost tradeoff curves for several benchmarks.
Table 10: AUC scores in for different strategies on RouterBench across model and noise levels for five-shot evaluation. Highest numbers bolded, underlined numbers within the 95% confidence intervals of the highest number. For discussion on confidence intervals, we refer to App.
Three Models
Five Models
Eleven Models
Low
Med
High
Low
Med
High
Low
Med
High
Lincar Interp.
74.21
74.21
74.21
73.82
73.82
73.82
75.16
75.16
75.16
Routing
81.50
77.22
76.01
82.43
76.84
75.54
85.34
77.77
76.44
Cascade (Baselinc)
83.16
78.58
76.89
84.27
76.59
73.92
87.14
78.60
74.94
Cascade (Ours)
82.78
78.77
77.01
84.26
77.19
74.30
86.72
78.67
75.08
Cascade Routing (Ours)
83.80
78.86
77.11
85.50
78.78
76.75
88.78
80.90
78.04
Table 11: AUC scores on several benchmarks for the MISTRAL model family. Highest numbers are bolded, underlined numbers within the 95% confidence intervals of the highest number. For confidence intervals, App. E
Classification
Open-Form
Linear Interp.
63.39
53.86
Routing
64.89
58.71
Cascade (Baseline)
61.20
48.29
Cascade (Ours)
63.31
55.51
Cascade Routing (Ours)
64.97
58.73
24


Reviews:
[{"review_id": "F7z1NBFRWU", "reviewer": "Reviewer_bNjc", "summary": "The paper proposes to combine cascading and routing, two common approaches for inference with multiple LLMs. The authors formulate each as an optimization problem and then solve it to derive optimal routing and cascading approaches. Finally, they propose \"cascade routing\" which is a generalized optimization formulation that can be solved to derive a combination of cascading and routing with multiple models where at each level of the cascade, one of the models is selected for inference. Evaluation results show that the approach outperforms approaches that do only cascading or routing.\n\n## update after rebuttal\n\nWhile the authors have responded to all of my questions with adequate clarification, and I feel the paper makes an interesting contribution, I still feel that the writing is very dense, and the exact algorithm is hard to follow. I am not sure how much this can be rectified at the camera-ready stage and therefore I am keeping my score at 3.", "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 their review. We are happy to hear that they found our experiments valid, our approach novel, and that we provide a better understanding of cascading. Below, we address their remaining questions.\n\n**What is the role of the superscript (j) in Theorem 2?**  \nThe superscript $(j)$ indicates that the quality estimator can update each time a model is executed. For instance, $q^{(0)}$ refers to the quality estimator before executing any model. For example, $q^{(0)}$ could predict quality based on the average accuracy across a training dataset. After model execution, $q^{(1)}$ can use the newly obtained data to refine quality estimates. For example, if the executed model generates long reasoning, it might suggest a more challenging question, requiring the estimator to reduce the accuracy predictions.\n\n**What is the role of the variance for quality estimation?**  \nQuality estimators are often not exact, meaning there is an uncertainty in their prediction. Modeling this uncertainty enables us to find more optimal solutions. For instance, variance allows us to capture low-probability events where the output of a model is “surprisingly” bad given the quality estimate. The linearity of the routing problem ensures that the variance does not influence the optimal solution. In contrast, the $\\max$ operator used for quality estimation in supermodels for cascading is not linear, and therefore gives a different solution when incorporating variance.\n\nMore explicitly, the equation  $\\mathbb{E}(\\max(\\hat{q}_1(x), …, \\hat{q}_k(x)))$ would simplify to $\\max(\\hat{q}_1(x), …, \\hat{q}_k(x))$. Thus, the quality of the supermodel would be equal to the quality of its best-performing model. Yet, the supermodel has higher costs compared to using the best individual model alone. Thus, the cost-quality tradeoff of such a supermodel would be strictly worse, and cascading routing would therefore never select a supermodel consisting of more than one model. However, by incorporating variance, the quality of the supermodel improves. Specifically, unexpectedly poor predictions from the best individual model can be compensated by better predictions from other models. This aggregation effect results in a better cost-quality tradeoff.\n\n**How are hyperparameters selected?**  \nAlmost all parameters are determined automatically. As shown in Equation (2) on Line 192,  $\\lambda_1, \\dots, \\lambda_k, \\gamma$ are all determined using an automated tool and a small calibration set. The only hyperparameter that requires manual setting, is the cost budget $B$. This hyperparameter is very interpretable, and cannot be set automatically as it depends on the specific use-case and budget of the user.\n\n**Can you define the extremes of quality strategies instead of cost strategies?**  \nBoth approaches are equivalent and would lead to the same optimal solution! Selecting the cheapest model that achieves the same optimal tradeoff is equivalent to selecting the one with lowest quality. Indeed, if $q_1 - \\lambda c_1 = q_2 - \\lambda c_2$ and $c_1 < c_2$, then $q_1 < q_2$. Thus $s^\\lambda_\\min$ and $s^\\lambda_\\max$  are the extremes of both cost and quality. \n\n**How exactly are you pruning the search space?**  \nWe are pruning supermodels from the set of all supermodels, not models from the set of all models. If a supermodel $M_1$ satisfies the pruning conditions in Lemma 1, we prune all supermodels $M_2$ that are a superset of $M_1$, i.e., $M_1 \\subseteq M_2$. To illustrate, suppose we have four models, and the presence of $m_2$ negatively impacts the cost-quality tradeoff of the supermodel {$m_1, m_2$}. Therefore, all supermodels containing both $m_1$ and $m_2$ are pruned. Thus, instead of evaluating all 16 supermodels, we would exclude {$m_1, m_2, m_3, m_4$}, {$m_1, m_2, m_3$}, {$m_1, m_2, m_4$}, and {$m_1, m_2$}. We will clarify this.\n\n**Can you add an algorithm block explaining cascade routing?**  \nYes, we will incorporate the recommended algorithm block. Additionally, we will provide an illustrative example.\n\n**What is the exit criterion?**  \nThe algorithm stops if the current supermodel is deemed to be the most optimal one. For example, suppose two steps into our cascade routing process we have executed models $m_1$ and $m_4$. If the algorithm predicts the supermodel {$m_1, m_4$} as optimal, it stops. Conversely, if it selects {$m_1, m_4, m_5$} as optimal, the process continues by executing $m_5$.\n\n**How does your approach select the next supermodel?**  \nCascade routing computes the quality-cost tradeoff for all possible supermodels and selects the supermodel offering the best tradeoff. Continuing with the example above, “all possible supermodels” refers to every supermodel containing $m_1$ and $m_4$, as these have already been executed. Among these, the algorithm selects the supermodel with the best cost-quality tradeoff. If the best supermodel is {$m_1, m_4, m_5$}, cascade routing proceeds by executing $m_5$.", "claims_and_evidence": "Yes", "methods_and_evaluation_criteria": "Yes", "theoretical_claims": "I checked the proofs at a high level, and they appear correct to me.", "experimental_designs_or_analyses": "I have checked the experiments in the main paper, and I do not have any issues with their validity.", "relation_to_broader_scientific_literature": "Strengths:\n\n1. The novel cascading approach proposed by the paper can improve over existing cascading approaches and provide a better understanding of LLM cascades\n\n2. The combination of cascading and routing has the potential to combine the best of both worlds\n\nWeaknesses:\n\n1. The optimization problem requires careful selection of hyperpaparameters and it is not clear how bad an incorrect choice would be\n\n2. The explanation of Cascade Routing in Section 4 is quite dense. Specifically, it is not clear how the approach selects the next supermodel at each step or what the exit criteria is.", "essential_references_not_discussed": "N/A", "other_strengths_and_weaknesses": "Some of the details are not clear (see questions below)", "other_comments_or_suggestions": "I would strongly recommend adding an algorithm block in the main paper or appendix to explain the cascade routing approach clearly.", "questions_for_authors": "1. The role of the superscript (j) in Theorem 2 is not clear.\n\n2. The role of variance in estimating the expected max quality of the models in the cascade is not clear to me.\n\n3. Why do you only consider the extremes of cost in defining in $s_\\min$ and $s_\\max$? Can't we similarly define strategies for the extremes of quality?\n\n4. Why, in Lemma 1, can all supermodels containing all models in $M$ be pruned from the search space if one model $m \\in M$ negatively impacts the quality cost tradeoff? Shouldn't we just prune $m$ and not all models in $M$?", "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": {"ethical_review_concerns": "N/A"}}, {"review_id": "cbWRNAoCUm", "reviewer": "Reviewer_4YAD", "summary": "Existing routing and cascading serve as two distinct strategies for LLMs. This work provides a theoretical analysis of the optimality of existing routing strategies and further proposes cascade routing that integrates both routing and cascading as a theoretically optimal strategy. Cascade routing frames the problem as a linear optimization problem by maximizing output quality within a limited computation budget. In the experiments, cascade routing shows improvements over individual routing or cascading approaches.\n\n## update after rebuttal\nI thank the author for the rebuttal, which mostly addressed my concerns. Therefore, I have increased my score from 2 to 3. However, I still find the quality estimation metric studied in this work questionable and limited, which I consider as the core for improving routing and cascading.", "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 their review. We are pleased that they appreciated our optimality analysis of the strategies, our comprehensive discussion of quality estimation, and the demonstrated improvement of our cascade algorithms over baselines. Below, we address their remaining questions.\n\n**Could you formulate cascade routing as a bi-level optimization problem?**  \nYes, one could formulate cascade routing as a bi-level optimization problem. However, such a bi-level formulation would yield solutions identical to those derived through our current linear optimization approach. To argue why bi-level optimization would not lead to further improvements, suppose we have two strategies $s_1$ and $s_2$ that achieve the same quality, but $s_1$ is cheaper than $s_2$ (both below the allocated cost budget $B$). Since our algorithm optimizes the cost-quality tradeoff, it would always select $s_1$ as the final strategy, and not $s_2$. Therefore, bi-level optimization would be completely equivalent to our current approach.\n\n**Why have you not included the baseline Learning How Hard to Think: Input-Adaptive Allocation of LM Computation?**  \nThe strategy presented in this paper is equivalent to our baseline routing strategy instantiated with an application-specific quality estimator. Specifically, the quality estimator is the inverse of the difficulty predictor introduced in the cited paper. Thus, the innovations from the cited work can also enhance cascade routing performance when used for quality estimation.\nOur experimental section already includes multiple diverse quality estimators, and due to constraints on space and time, we could not explore all possible estimators. Importantly, our primary goal is to demonstrate that cascade routing consistently outperforms other strategies across different instantiations of quality and cost estimators. We will clarify this relationship explicitly in the revised paper, illustrating how the referenced work can be seen as an instantiation of our routing strategy.\n\n**Does the optimality proof require good quality estimation?**  \nNo, we want to stress that the optimality proof holds even in the presence of bad quality estimators. If all that is available are bad quality estimators, no algorithm could outperform cascade routing and obtain better performance. However, better quality estimators could increase the predictive power of algorithms like ours. Thus, our algorithm achieves optimality given current estimation techniques.\nWe further emphasize that even with suboptimal quality estimators, cascade routing consistently outperforms baseline strategies. Given that most research in this area focuses precisely on improving quality estimation, these innovations can be directly integrated into cascade routing to further enhance performance.\n\n**What about the increased inference and latency costs?**  \nCascade routing does not inherently increase inference costs. On the contrary, our results indicate that, under identical budget constraints, cascade routing achieves higher accuracy.\nMore importantly, latency costs can be explicitly incorporated into the cascade routing cost function, enabling direct optimization for latency. For instance, the cost in our SWE-Bench benchmark is measured as the total time in seconds it takes an agent to complete the task. As can be seen there, cascade routing is much better than routing for the same latency. This is because cascade routing can decide to run cheaper models first before executing the larger model that has higher latency. We will clarify this point in our revised paper.\n\n**What are the requirements for the training data?**  \nThe amount of training data required for fitting cascade routing parameters is generally modest, typically consisting of only a few hundred samples. The associated training overhead is minimal since the procedure involves fitting merely $k+1$ parameters, making it easily executable on standard hardware within a short duration. We further found during our experimentation that the impact of the training data on output quality remains minor, provided it reasonably resembles the benchmark data.\n\n**Could you provide supplementary materials?**  \nContrary to the reviewer's observation, we confirm that our code was included as supplementary material. Additionally, we have provided extensive supplemental details in the appendix.", "claims_and_evidence": "There are no particular claims made in the paper.", "methods_and_evaluation_criteria": "The proposed method, cascade routing, makes sense by reframing the optimization problem as a linear optimization problem with a budget constraint. The evaluation set is fair. However, quality estimation is questionable.", "theoretical_claims": "This work formulates the optimal routing strategy and optimal cascading strategy in Theorem 1 and 2, respectively. It argues that cascade routing can also serve as the optimal strategy. The formulation is correct. However, the assumption is built on top of a perfect estimation of the quality and cost of the query. Therefore, the final strategy may not be optimal.", "experimental_designs_or_analyses": "The experiments are conducted on RouterBench and Practical Benchmarks that are reasonable.", "relation_to_broader_scientific_literature": "The routing and cascading is important for efficient LLM serving and deployments.", "essential_references_not_discussed": "[1] Damani, M., Shenfeld, I., Peng, A., Bobu, A., & Andreas, J. (2024). Learning How Hard to Think: Input-Adaptive Allocation of LM Computation (No. arXiv:2410.04707). arXiv. https://doi.org/10.48550/arXiv.2410.04707 [ICLR 2025]", "other_strengths_and_weaknesses": "Strength:\n1. This work provides a good optimality analysis of the individual routing and cascading strategies. \n\n2. The discussion on the ex-ante quality estimation and post-hoc quality estimation is great.\n\n3. The proposed cascade routing shows improvement over individual routing and cascading strategies.\n\nWeakness\n1. This work is highly reliant on an accurate quality estimation. However, in many real scenarios, the quality is often difficult to estimate, and simply using uncertainty is not convincing enough to show the optimality of the proposed approach, since LLMs are exposed to miscalibrated predictions.\n\n2. The baselines are relatively weak. There are a few competitive routing baselines but have not been included and compared in this work. [1]\n\n3. The increased inference cost has not been discussed explicitly in the work. In addition, the requirement of a training set, and the actual stability with respect to the size of the training set are not discussed.", "other_comments_or_suggestions": "It would be beneficial if the author could include the training cost, the inference latency, and the inference cost compared to individual baselines in the main body of the work, together with the main table.", "questions_for_authors": "1. Instead of considering the optimal strategy as a linear optimization problem, does it make more sense to frame it as a bi-level optimization, minimizing the cost while maximizing the performance, such that leading to a better Pareto-front?", "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": "i8spFVCVZV", "reviewer": "Reviewer_wKyv", "summary": "This paper studies how to use multiple LLMs to improve overall performance under budget constraints. The key idea is to combine two popular approaches, model routing and model cascade. The authors start with analyzing model routing, and then generalizes this analysis to multiple rounds of model routing, which the authors term as cascade routing. Experiments with real-world datasets are performed and analyzed.", "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 their detailed review. Below, we address their remaining questions.\n\n**Why is the expectation of the maximum but not just $q_i$?**  \nThere are two primary reasons for using the expectation of the maximum. First, while the model $m_i$ is often stronger than the model $m_{i-1}$, this does not hold universally. For example, our experiments for the LiveCodeBench and Minerva benchmarks include four models: a small and large math model and a small and large code model. The math models perform better on mathematical queries, while the code models perform better on code queries. It is impossible to rank these four models such that each subsequent model $m_i$ is always better than $m_{i-1}$ for all queries.\n\nThe second reason is more technical: the suggested change would imply that the quality of the supermodel is equal to the quality of its best-performing model. Yet, the supermodel has higher costs compared to using the best individual model alone. Thus, the cost-quality tradeoff of such a supermodel would be strictly worse, and cascading routing would therefore never select a supermodel consisting of more than one model. This would reduce it to a routing strategy.\n\n**Did you include the latest state-of-the-art models?**  \nYes, our experiments on SWE-Bench employ state-of-the-art agents, primarily based on advanced models such as GPT-4o and Claude-3.5-sonnet. Additionally, our experiments on LiveCodeBench and Minerva use the state-of-the-art open-source Qwen-2.5 model family. Although Llama-3 is no longer considered the absolute state-of-the-art due to recent advances, it remains a robust and widely used model family. Thus, our experiments confirm that cascade routing is effective when applied to current state-of-the-art models.\n\n**How does the latency of cascade routing compare with the baselines?**    \nGenerally, the latency of cascade routing falls between pure routing and pure cascading strategies, as it can selectively execute multiple models (increases latency) or skip models (reduces latency). Moreover, for specific applications, latency costs can be explicitly incorporated into the cascade routing cost function, enabling direct optimization for latency. For instance, the cost in our SWE-Bench benchmark is measured as the total time in seconds it takes an agent to complete the task. As can be seen there, cascade routing is much better than routing for the same latency. This is because cascade routing can decide to run cheaper models first before executing the larger model that has higher latency. We will clarify this point in our revised paper.\n\n**Can you clarify how you estimated quality on the RouterBench benchmark?**  \nAs explained in lines 297-308, we use random noise estimators for RouterBench. Specifically, we add normal noise of varying strength to the ground-truth quality and cost. This enables us to simulate real-world scenarios with varying fidelities of quality and cost estimators. For instance, high noise would simulate scenarios with poor estimators. This enables us to systematically evaluate our algorithm across varied conditions. Specifically, Figure 2 illustrates the extent of improvement provided by cascade routing over baseline methods under different noise scenarios. This choice is very similar to the choice by the authors of RouterBench, who use a slightly different form of this random noise. \n\n**Is one of your main claims that the routing strategy is better than prior work?**  \nNo, we have been careful throughout the paper not to claim that our proposed routing algorithm is a major improvement over existing methods. For instance, in lines 77-79, we explicitly state that the algorithm introduced in Section 2 closely resembles previous work. Our primary contribution in Section 2 is providing a clean and rigorous proof of optimality for this approach. Our significant algorithmic advancements over prior methods appear in Sections 3 and 4. Specifically, the algorithms for cascading and cascade routing represent substantially novel contributions. Thus, the analysis presented in Section 2 primarily serves as a foundation for introducing and validating these new algorithms in Sections 3 and 4: without this analysis, demonstrating their optimality would not be possible.\n\n**Can you provide performance-cost tradeoff curves?**  \nYes, we will incorporate these curves in our revision. Generally, they closely resemble those presented in Hu (2024), confirming our averaged results and clearly demonstrating that cascade routing consistently outperforms other approaches.", "claims_and_evidence": "- The overall idea of combing cascade and routing seems reasonable, although a little incremental.\n\n- Optimal routing strategy: A main claim is that prior work cannot express the optimal solution derived by Theorem 1. This is based on the assumption that \"it can occur that several models achieve the same optimal cost-quality tradeoff for a given query\". But isn't this a pathological case? As long as the cost is different for all models, then the cost-quality tradeoff will be different for all models which can answer the user question correctly. Among all models that answer it correctly, the optimal solution is simply the one with the lowest cost. In other words, given the limited scope, I am unsure if the complex analysis is worth it.", "methods_and_evaluation_criteria": "The method sounds reasonable, but the evaluation metric is a bit limited. See my comments later.", "theoretical_claims": "No, I only scanned the analysis.", "experimental_designs_or_analyses": "The experiments only report AUC by varying the cost from the cheapest to the most expensive model's price. However, the cost of a cascade approach may be higher than the most expensive model since it may call multiple models for a given question. Following (Hu 2024), I would also be curious to see the performance-cost tradeoff curves.", "relation_to_broader_scientific_literature": "NA", "essential_references_not_discussed": "NA", "other_strengths_and_weaknesses": "NA", "other_comments_or_suggestions": "NA", "questions_for_authors": "1. In line 216, why is the expectation of the maximum but not just q_i?\n\n2. How does the proposed cascade routing perform with more recent models, such as GPT-4o, Claude 3.5 Sonnet, and Gemini 1.5 Pro?\n\n3. How does the latency of cascade routing compare with the baselines?\n\n4. What is the trade-off curve (acc/AUC/exact match vs cost) for the proposed cascade routing?\n\n5. How do the authors predict the model quality on ROUTERBENCH?", "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": "HNkmhITsEx", "reviewer": "Reviewer_abFg", "summary": "The paper proposes a unified framework termed \"cascade routing\" that integrates routing and cascading strategies to optimize the selection of large language models (LLMs) based on a cost-performance tradeoff. It gives a theoretically grounded method using linear optimization to derive optimal routing and cascading strategies, supported by proofs of optimality. The authors provide mathematical formulations and theorems, and present experimental results across multiple benchmarks such as RouterBench and SWE-Bench. These experiments demonstrate that cascade routing outperforms routing and cascading baselines.\n\n## update after rebuttal\nThank the authors for their response, which has clarified most of my concerns. Overall, I find the paper's contributions to the theoretical framework—particularly in unifying routing and cascading via the concept of \"supermodel\"—to be quite novel. I would personally vote for acceptance.", "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 their review. We are happy to hear that they found our claims well supported, our theoretical reformulation fresh and neat, and our experiments convincing. Below, we address their questions.\n\n**Can you clarify how $\\gamma$ is determined and whether step-specific $\\gamma_j$ factors might improve performance?**  \nFirst, we highlight that this parameter is generally of minor significance, becoming relevant only when $s_{\\min}$ and $s_{\\max}$ differ. This scenario is limited to cases where two or more models achieve exactly identical trade-offs, which occurs rarely in practice. \n\nThe value of $\\gamma$ is determined according to the procedure outlined in lines 701-702: we first estimate the costs associated with $s_{\\min}$ and $s_{\\max}$ using training data, and then select $\\gamma$ to precisely satisfy the budget constraint $B$ by solving $B = \\gamma B^- + (1 - \\gamma) B^+$. Since this equation is always invertible, as $B \\in [B^-, B^+]$, $\\gamma$ exists.  Due to linearity in cost, the resulting optimal routing algorithm, $\\gamma s_{\\min} + (1 - \\gamma) s_{\\max}$, matches the budget exactly. \n\nSince the only purpose of $\\gamma$ in the proof is to ensure that the cost of the final strategy exactly matches $B$, using step-specific $\\gamma_j$ will not significantly alter the strategy and would yield equivalent theoretical quality.\n\n**Is the cost of quality estimation factored in when evaluating the AUC score?**  \nIn all our experiments, the cost of quality estimation was sufficiently negligible to exclude it from the AUC score. Specifically, we used small linear models based on model confidence or categorical features. Running these linear models essentially does not cost anything. The reviewer correctly points out that cheap quality estimates are essential. However, we do want to point out that all current algorithms suffer from this limitation.\n\n**Did you include baselines based on adaptive thresholds?**  \nYes, as the presented baseline cascade does allow for adaptive thresholds. All works cited by the reviewer can be reformulated under the thresholding mechanism presented in Corollary 1. Specifically, by appropriately selecting the estimator $q_{j-1}^{(j)}(x)$, our formulation becomes equivalent. For example, for [1], one can set $q_{j-1}^{(j)}(x) = \\eta_{h^2}(x) - \\eta_{h^1}(x)$, thereby exactly recovering their scheme. We will clarify this in the revised paper.\n\nWe also agree with the reviewer’s observation regarding the restrictive nature of the optimality conditions presented in Corollary 1. We stress that these strict conditions apply exclusively to the optimality of the baseline thresholding mechanism, and not to our newly introduced cascading approach.\n\n**Can you add some illustrative examples of cascade routing?**  \nYes, reviewer bNjc similarly suggested that adding an algorithm block for cascade routing would enhance clarity. We will incorporate both an algorithmic description and an illustrative example into the paper.\n\n**Does cascade routing only look at the supermodels $M_{1:j-1}, \\dots, M_{1:k}$?**  \nNo, the given subset of supermodels is only required during cascading. As stated in lines 260-261, we specifically remove this requirement from cascade routing, thereby allowing consideration of all possible supermodels.\n\n**Can you clarify what you mean in the model ordering paragraph?**  \nThis paragraph serves only to identify the optimal initial model to execute within the chosen supermodel. To illustrate, suppose we label models from least to most expensive as $m_1, \\dots, m_k$. If the cascade routing algorithm initially selects the optimal supermodel as {$m_3, m_5$}, the model $m_3$ will be executed first. Subsequently, after updating quality and cost estimates, the algorithm may identify a new optimal supermodel, for instance, {$m_1, m_2, m_3$}. Since $m_3$ has already been executed, it remains part of the optimal set, and thus $m_1$ will be run next. We will clarify this in the paper.\n\n**Could you add a discussion regarding robustness of the method to estimation errors?**  \nYes, we provide an empirical discussion of the robustness of all methods by discussing ex-ante and post-hoc quality estimation and showing performance for different estimation errors in Figure 2. These discussions say where both cascading and routing are most helpful, and in which cases cascade routing outperforms them most. However, we were not able to prove any interesting results regarding the effect of estimation errors on performance as this is a very difficult problem.\n\n**Does restricting the maximum depth of cascade routing significantly affect performance?**  \nThe reviewer accurately notes that our theoretical proof imposes no explicit restriction on the number of models executed. However, we wish to emphasize that, in practical settings, cascade routing very rarely selects more than five models. Thus, enforcing a maximum cascade depth has negligible practical impact.", "claims_and_evidence": "The claims are overall well supported. See weakness and questions below for details.", "methods_and_evaluation_criteria": "The chosen benchmarks are commonly-used benchmarks and are relevant to the task of LLM model selection. The use of AUC as a metric is appropriate for evaluating cost-performance trade-offs. See weakness and questions below for details.", "theoretical_claims": "I looked at the proofs in Appendix but did not check the details. There are some fuzzy spots—like how they pick certain parameters and some limiting assumptions—that make the paper a bit unclear. See weakness and questions below for details.", "experimental_designs_or_analyses": "The evaluation is compromised by synthetic noise in RouterBench, which may not mirror real-world conditions. Also, incorporating stronger baselines, such as adaptive thresholding methods (See missing references below), would offer a more meaningful comparison.\nExperiments also show minimal gains under poor quality estimation, underscoring the framework’s sensitivity to this factor. The analysis lacks depth regarding robustness to estimation errors, limiting its interpretability.", "relation_to_broader_scientific_literature": "Overall the paper situates itself within the broader field of model selection for LLMs, building on established concepts while introducing a novel unification of LLM routing and cascading.", "essential_references_not_discussed": "The paper would benefit from citing previous works on dynamic thresholds for cascading [1,2]. These could provide a more competitive baseline than the simplistic cascades currently evaluated.\n\n[1] Jitkrittum, Wittawat, et al. \"When does confidence-based cascade deferral suffice?.\" Advances in Neural Information Processing Systems 36 (2023): 9891-9906.\n[2] Nie, Lunyiu, et al. \"Online cascade learning for efficient inference over streams.\" Proceedings of the 41st International Conference on Machine Learning. 2024.", "other_strengths_and_weaknesses": "Strengths:\nI really like the idea of framing cascading as routing among \"supermodels.\" It’s a clever way to unify routing and cascading into a single theoretical framework that feels both fresh and neat. The convex combination approach is novel and provides new insights in achieving better cost-performance trade-offs. The theoretical claims are supported by detailed mathematical derivations and proofs provided in the appendices, and the experimental results on multiple benchmarks provide convincing empirical evidence. \n\nWeaknesses:\n1. In the analysis, restricting cascading to be deterministic is oversimplifying this line of approaches. There are many works [1-3] that dynamically adapt the confidence thresholds in cascades by a separate post-hoc confidence calibration model. I would suggest comparing with stronger baselines in the experiments. \n2. While the proofs are mostly sound, certain ambiguities in the proof make it unclear to the readers. \n- The assumption $|\\Lambda| < \\infty$ (finite points where tradeoffs equalize) is justified by finite precision in practice but limits theoretical generality. In continuous spaces, $ \\Lambda $ could be infinite.\n- The proof assumes a convex combination exists for any $ B $, but if $ S_{\\lambda^*} $ contains multiple strategies with varying costs, selecting $ \\gamma $ to hit $ B $ precisely is not detailed. The proof states it \"must exist,\" but the mechanism is opaque.\n- In Appendix B, a single $ \\gamma $ across steps simplifies the problem but lacks justification beyond the global budget constraint. Step-specific $ \\gamma_j $ might better reflect varying tradeoffs.\n- For the proof regarding the equivalence of Thresholding and Cascading, I found the conditions restrictive—constant costs and query-independent quality estimates rarely hold in practice, and the supermodel quality assumption feels contrived.\n- Regarding the cascade routing approach, the exponential growth of supermodel combinations is acknowledged but unresolved theoretically. Computational complexity is highlighted in Appendix F and mitigated by restricting max. depth, but the proof assumes full evaluation, which is infeasible for large $ k$.\n3. In practice, quality estimation—whether ex-ante or post-hoc — is not free and must come with a time/cost that can significantly influence the evaluation of the proposed cascade routing framework. However, the paper assumes that quality estimates $\\hat{q}_i(x)$ and cost estimates $hat{c}_i(x)$ for each model and query are readily available. If the time/cost of quality estimation is high, it could offset the advantages of the framework, especially in applications where efficiency is important.\n\n[1] Jitkrittum, Wittawat, et al. \"When does confidence-based cascade deferral suffice?.\" Advances in Neural Information Processing Systems 36 (2023): 9891-9906.\n[2] Nie, Lunyiu, et al. \"Online cascade learning for efficient inference over streams.\" Proceedings of the 41st International Conference on Machine Learning. 2024.\n[3] Enomoro, Shohei, and Takeharu Eda. \"Learning to cascade: Confidence calibration for improving the accuracy and computational cost of cascade inference systems.\" Proceedings of the AAAI Conference on Artificial Intelligence. Vol. 35. No. 8. 2021.", "other_comments_or_suggestions": "Typo: line 961, \"we extract the answer by instruction the model\", instruction\" should be \"instructing\"\nSee below for other suggestions.", "questions_for_authors": "1. It's unclear to me in the experiments how 𝛾 is determined in practice. \n2. In cascading, would step-specific $ \\gamma_j $ improve performance by reflecting varying tradeoffs?\n3. Quality estimation isn’t free in practice. Is this factored into the framework when evaluating the AUC score?\n4. The experimental results look good, but the lack of stronger baselines (e.g., adaptive cascades) —please consider addressing these in revisions.\n5. Adding more illustrative examples in the paper to aid readers in understanding the convex combination approach and the dynamic routing decisions in cascade routing. \n6. Does the notation $ M_{1:j-1}, \\ldots, M_{1:k} $ in cascade routing imply a fixed sequence, or is it just a label? Please clarify, as it seems to conflict with the flexibility of cascade routing.\n6. The \"Model Order\" paragraph in Sec 4 is a bit confusing -- if models are sorted by cost within supermodels, is the model invocation order in cascade routing fully flexible? If so, can you provide an example of a non-sequential order to illustrate this?", "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: Cascading and routing are two common strategies to reduce LLM inference costs: both these strategies leverage a pool of LLMs, and select the most suitable LLM for a given query. The authors derive the optimal strategy for routing and cascading, and provide a new strategy for cascading that has better optimality guarantees than prior approaches. They also propose a hybrid strategy that combines cascading and routing, and experimentally demonstrate its efficacy over pure cascading and pure routing baselines.

The reviewers generally appreciate the unified theoretical analysis and find the proposed cascade routing strategy to be a useful contribution. However, there were concerns about the writing being unclear in some places, the method relying on the availability of good quality estimators, the need for heavy hyper-parameter optimization, and the baselines being relatively weak. Many of these concerns were addressed during the rebuttal stage. We trust the authors will incorporate all the changes promised, including providing clarifications about the baselines, and providing an algorithm block and an illustrative example.

Based on my own reading of the paper, I really liked the formulation of cascading and routing under a unified framework. I have the following comments that I strongly encourage the authors to address in their camera-ready paper:
- **Routing to supermodels**: In Section 3, the authors view cascading as a sequential routing problem, where at each step $j$, they route to one of the supermodels $M_{1:j-1}, \ldots,  M_{1:k}$. What would happen in this formulation when we decide to route to supermodel $M_{1:i}$, where $i > j$? Would you simply choose to call the next model $m_j$, or directly call model $m_i$? I guess it is the former, but this wasn't clear from the discussion after Definition 4. A similar question arises in Section 4. With a cascade router, what does it mean to route to supermodel $M$ at step $j-1$: would this result in invoking the smallest model in $M$ or *all* models in $M$?

- **Randomized routing:** In your optimality analysis, you allow for a randomized routing strategy, providing greater flexibility compared to prior work. However, it is important that you discuss the feasibility/difficulty of employing a randomized router in practice. Furthermore, even in a setting where we are allowed only deterministic routing decisions, it might be worth mentioning that the optimal router can be shown to be of the form $s^\lambda(x) = {\rm argmax}_i ~q_i(x) - \lambda\cdot c_i(x)$ (i.e., a single deterministic router) by making *continuity assumptions on the data distribution* (via a Neyman-Pearson like analysis). For e.g. Theorem 6 in [2] derives the optimal deterministic classifier for the case of two models; Proposition 1 in [3] derives this for the multi-model case.

- **Quality estimator details:** You mention that in your real-world experiments, you use a linear model on log-probability features. It might be worth clarifying if you use the log-probabilities from *all* models invoked at the current step. More generally, it might be worth elaborating on the construction of the quality estimator in the main text (perhaps move some details from the appendix), as this is a crucial component in your proposal.

- **Relationship to [2]:** The paper by Trapeznikov et al. (2013) [1] also present some optimality results for sequential routing, and the results have some similarity to your results for cascading (see e.g, the optimal solution in Theorem 1 in their paper). Might be worth having a discussion on the connections to this paper.


[1] Supervised Sequential Classification Under Budget Constraints. AISTATS 2013.

[2] Learning to Reject Meets Long-tail Learning. ICLR 2024.

[3] Universal Model Routing for Efficient LLM Inference, arXiv:2502.08773 , 2025.
Decision: Accept (poster)