A Unified Approach to Routing and Cascading for LLMs

## Abstract

Abstract The widespread applicability of large language models (LLMs) has increased the availability of many fine-tuned models of various sizes targeting specific tasks. Given a set of such specialized models, to maximize overall performance, it is important to figure out the optimal strategy for selecting the right model for a given user query. An effective strategy could drastically increase overall performance and even offer improvements over a single large monolithic model. Existing approaches typically fall into two categories: routing, where a single model is selected for each query, and cascading, which runs a sequence of increasingly larger models until a satisfactory answer is obtained. However, both have notable limitations: routing commits to an initial model without flexibility, while cascading requires executing every model in sequence, which can be inefficient. Additionally, the conditions under which these strategies are provably optimal remain unclear. In this work, we derive optimal strategies for both routing and cascading. Building on this analysis, we propose a novel approach called cascade routing , which combines the adaptability of routing with the cost-efficiency of cascading. Our experiments demonstrate that cascade routing consistently outperforms both routing and cascading across a variety of settings, improving both output quality and lowering computational cost, thus offering a unified and efficient solution to the model selection problem. 1 1 1 Code available at https://github.com/eth-sri/cascade-routing .

## 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-the-art LLMs. This has led to the development of many fine-tuned models of various sizes that target specific tasks. To maximize performance, it is crucial to select the most suitable model for each query, accounting for both the expected quality of the model’s output and the model’s cost. Such model selection strategies can significantly improve performance over any individual model and can reduce inference costs by selecting a smaller model when the query does not require the full capacity of a larger model.

#### Routing and Cascading

Two primary strategies have been proposed to solve model selection. The first, routing, directs each input query to a specific model from a set of available models (Chen et al., ; Liu et al., ), as illustrated in Fig. 1(a). This approach is particularly effective when different expert LLMs are needed for different tasks, enabling the selection of the most suitable expert for each query. The second strategy, cascading, processes an input query through a sequence of increasingly larger models, stopping when a model produces an answer deemed sufficiently good (Chen et al., ; Varshney and Baral, ), as illustrated in Fig. 1(b). Cascading is particularly valuable for handling queries of varying difficulty, as it allows simpler queries to be addressed by smaller, less expensive models while reserving more complex queries for larger models.

#### 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 decision. In cascading, each query must sequentially pass through all models in the chain until a suitable answer is found, with no option to reroute to a potentially better model. Therefore, a less restrictive strategy that combines the strengths of both routing and cascading could offer significant performance improvements.

#### Lack of Theoretical Understanding

Furthermore, the conditions under which current routing and cascading strategies are optimal, are not well understood. For routing, an extensive proof is required just to show that current strategies are *close to* optimal (Chen et al., ), while the theoretical analysis of current cascading algorithms is based on restrictive assumptions and does not provide optimality guarantees (Chen et al., ; Varshney and Baral, ). This lack of theoretical understanding hinders the development of more effective model selection strategies.

Figure: ((a)) Routing

#### This Work: Cascade Routing

To address these limitations, we first derive optimal routing and cascading strategies by framing them as linear optimization problems aimed at maximizing output quality while remaining within a given cost budget. For routing, this optimal strategy is close to the one obtained by prior work, while for cascading we derive a new strategy that is provably better than existing approaches. Building on this theoretical analysis, we propose a new paradigm called cascade routing, which generalizes both routing and cascading. As illustrated in Fig. 1(c), cascade routing initially routes a query to any available model but keeps rerouting to different models until a model produces an answer of sufficient quality. We prove the optimality of our cascade routing strategy and show that it offers significantly more flexibility in processing a query.

#### Results

We evaluate cascade routing on a wide range of tasks, demonstrating that it significantly outperforms both routing and cascading. Notably, cascade routing consistently improves performance by $1\%$ to $4\%$ across all settings on the popular RouterBench benchmark (Hu et al., ), which represents a relative improvement over a naive baseline by an additional $13\%$ to $80\%$. Furthermore, we show that our new cascading strategy outperforms existing cascading strategies by up to $2\%$, validating that our theoretical analysis leads to practical improvements over prior work.

#### Contributions

Our main contributions are as follows:

- •
We derive optimal strategies for routing and cascading and obtain a new cascading strategy that is provably better than prior approaches (Section 2, Section 3).
- •
We introduce cascade routing, a new paradigm that combines the strengths of routing and cascading, and prove its optimality (Section 4).
- •
We conduct a thorough evaluation, demonstrating that cascade routing consistently outperforms the baselines (Section 5).

## 2 Routing as Linear Optimization

We derive an optimal routing strategy to select the best model for a given query, providing detailed proofs for all statements in this section in App. A. We will use the analysis presented here to develop the optimal cascading and cascade routing strategies in Section 3 and Section 4, respectively.

#### Routing Strategy

In routing, our goal is to develop a strategy that selects the best language model for a given input query. Formally, let $\mathcal{X}$ represent the distribution over all possible queries, and
suppose we have $k$ language models $m_{1},\dots,m_{k}$ available for routing.
Further, let $\Delta_{k}$ denote the set of all probability distributions over $k$ variables. A routing strategy can then be defined as follows:

###### Definition 1 (Routing) .

A routing strategy $s$ is a function $s\colon\mathcal{X}\rightarrow\Delta_{k}$ that maps a query $x\in\mathcal{X}$ to a probability distribution over models. $s_{i}(x)$ denotes the probability that $m_{i}$ is selected for query $x$.

A routing strategy selects a model by sampling from the distribution $s(x)$ for each query $x$. In prior work, routing strategies were restricted to be deterministic, i.e., $s_{i}(x)\in\{0,1\}$ (Chen et al., ; Hu et al., ). In contrast, we propose using a more general probabilistic routing strategy that enables a better solution and an easier theoretical analysis.

###### Definition 1 (Routing) .

#### Quality and Cost

In routing, we seek to maximize the expected output quality of the selected model while adhering to a given cost budget $B$. Quality could measure model accuracy, user preference, or any other performance indicator. We define the quality function $q_{i}(x)$ as the output quality of model $m_{i}$ on query $x$, and the cost function $c_{i}(x)$ as the cost of running model $m_{i}$ on $x$.

However, since these functions are unknown in practice, we need estimators $\hat{q}_{i}(x)$ and $\hat{c}_{i}(x)$ that approximate the output quality and cost of querying model $m_{i}$ on input $x$. Estimators for $q_{i}(x)$ can be created using small classifiers trained to predict model accuracy, as done in prior work (Hu et al., ; Shnitzer et al., ). $\hat{c}_{i}(x)$ can be estimated 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 a query.

#### Optimal Routing

Using these estimators, we can formally define the optimal routing strategy:

###### Definition 2 (Optimal Routing) .

The optimal routing strategy $s_{\textsc{opt}}$ for a given cost budget $B$ is the solution to the optimization problem

$$ $\displaystyle\max_{s}$ $\displaystyle\mathbb{E}_{x\in\mathcal{X},i\in\{1,\dots,k\}}(s_{i}(x)\hat{q}_{i }(x))$ (1) s.t. $\displaystyle\mathbb{E}_{x\in\mathcal{X},i\in\{1,\dots,k\}}(s_{i}(x)\hat{c}_{i }(x))\leqslant B.$ $$

We now explain how to solve this linear optimization problem. Intuitively, the optimal routing strategy optimizes the cost-quality tradeoff $\tau_{i}(x,\lambda)=\hat{q}_{i}(x)-\lambda\hat{c}_{i}(x)$, where $\lambda\in\mathbb{R}^{+}$ controls the balance between quality and cost based on the budget $B$. For each query $x$, the model that achieves the highest value of $\tau_{i}(x,\lambda)$ is selected.

More formally, for a given $\lambda\in\mathbb{R}^{+}$, we define two deterministic routing strategies: $s_{\textsc{min}}^{\lambda}(x)$, which selects the cheapest model achieving the optimal cost-quality tradeoff, and $s_{\textsc{max}}^{\lambda}(x)$, which selects the most expensive model achieving this tradeoff. The optimal routing strategy $s_{\textsc{opt}}$ is then determined by the following theorem:

###### Theorem 1 (Optimal Routing Strategy) .

For a given cost budget $B$, there exists a $\lambda\in\mathbb{R}^{+}$ and a $\gamma\in[0,1]$ such that the optimal routing strategy $s_{\textsc{opt}}$ equals $\gamma s_{\textsc{min}}^{\lambda}+(1-\gamma)s_{\textsc{max}}^{\lambda}$. Furthermore, all routing strategies that have an expected cost that is exactly equal to $B$ and can be written as a convex combination of $s_{\textsc{min}}^{\lambda^{\prime}}$ and $s_{\textsc{max}}^{\lambda^{\prime}}$ for some $\lambda^{\prime}\in\mathbb{R}^{+}$ achieve the same optimal quality.

Since $\gamma$ is often not equal to 0 0 or $1$, the optimal routing strategy is not deterministic and instead selects a model probabilistically. Therefore, prior work that only considered deterministic routing strategies (Chen et al., ; Hu et al., ) cannot express the routing strategy from Theorem 1 and fall back to the near-optimal $s_{\textsc{min}}^{\lambda}$ instead.

Due to the second part of Theorem 1, we only need to find *a* set of hyperparameters $\lambda$ and $\gamma$ that achieve the desired cost budget. To determine these parameters, we estimate the cost of each strategy using a validation dataset $D$ that is representative of the query distribution $\mathcal{X}$. Since the cost of $s_{\textsc{min}}^{\lambda}$ increases as $\lambda$ decreases (see App. A), we use a binary search to find the appropriate value of $\lambda$. $\gamma$ is determined by interpolating between the costs of $s_{\textsc{min}}^{\lambda}$ and $s_{\textsc{max}}^{\lambda}$ to match the budget $B$.

###### Definition 2 (Optimal Routing) .

###### Theorem 1 (Optimal Routing Strategy) .

## 3 Cascading as Sequential Routing

In this section, we extend our analysis of the optimal routing strategy to the cascade setting, providing detailed proofs for all the statements in this section in App. B. The solution derived here will be used to develop the optimal strategy for cascade routing in Section 4.

#### Cascading

In cascading, an input query is passed through a chain of increasingly larger and more expensive models. 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 to as supermodels.

###### Definition 3 (Supermodel) .

A supermodel $M$ is a sequence of models $(m_{i_{1}},\dots,m_{i_{j}})$ such that running a query through $M$ is equivalent to running it through each of the models in the sequence. The set of all supermodels is denoted as $\mathcal{M}$. By $M_{i:j}$ we denote the supermodel $(m_{i},\dots,m_{j})$.

In cascading, we only need to consider the supermodels $M_{1:1},\dots,M_{1:k}$. The full expressivity of Definition 3 will only be necessary for cascade routing in Section 4.

A cascade occurs as a sequence of decision steps, where at each step, it decides whether to compute the next model in the sequence or terminate. By step $j$, the first $j-1$ models have been computed. At this point, the cascade will run one of the supermodels $M_{1:j-1},\dots,M_{1:k}$. If any of the supermodels $M_{1:j},\dots,M_{1:k}$ is optimal, the cascade proceeds to run the next model. In contrast, if the supermodel $M_{1:j-1}$ is optimal, the cascade halts and returns the output of the last computed model.

Thus, a cascade can be characterized as a sequence of routing strategies that route between the supermodels $M_{1:j-1},\dots,M_{1:k}$. Even though the action associated with supermodels $M_{1:j},\dots,M_{1:k}$ – continuing the cascade – is the same, it is essential to use all of them in the routing strategy. For instance, if $m_{j}$ performs poorly but $m_{j+1}$ performs exceptionally well on a given query, the cascade should continue. Limiting consideration to the supermodels $M_{1:j-1}$ and $M_{1:j}$ alone would therefore result in suboptimal decisions. Formally, we define a cascading strategy as follows:

###### Definition 4 (Cascading Strategy) .

A cascading strategy $s$ is a sequence of routing strategy $(s^{(1)},\dots,s^{(k)})$ such that $s^{(j)}$ routes between the supermodels $M_{1:j-1},\dots,M_{1:k}$.

###### Definition 3 (Supermodel) .

###### Definition 4 (Cascading Strategy) .

#### Quality and Cost

To apply Theorem 1 to find the optimal cascading strategy, we first need to derive the quality and cost estimates of the supermodels. Both of these can depend on the answers of previously computed models. Therefore, let $\hat{q}^{(j)}(x)$ and $\hat{c}^{(j)}(x)$ represent the updated estimates in step $j$ after computing the first $j-1$ models.

We derive the quality and cost estimates associated with supermodel $M_{1:i}$, denoted as $\hat{q}^{(j)}_{1:i}(x)$ and $\hat{c}^{(j)}_{1:i}(x)$, based on the quality and cost estimates of the individual models. Trivially, the cost estimate of the supermodel is equal to the sum of the individual model costs. The quality of a supermodel, however, is governed by the best model within it. Thus, it equals $\mathbb{E}[\max(\hat{q}_{1}(x),\dots,\hat{q}_{i}(x))]$, where the expected value reflects the uncertainty in each quality estimate. This expected value 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 quality estimates, we compute the variance of $\hat{q}^{(j)}_{i}(x)-\hat{q}^{(k)}_{i}(x)$ over a validation dataset $D$.

While the form of these estimates works well in practice and is intuitively clear, we note that alternative approaches are possible. However, the optimality proof of our cascading strategy does not depend on the specific form of the estimates, and can therefore be adapted to other formulations.

#### Optimal Cascading

We now leverage the optimal routing strategy from Theorem 1 to determine the optimal cascading 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 the individual steps. This leads to a slightly different formulation of the optimal cascading strategy:

###### Theorem 2 (Optimal Cascading Strategy) .

For a given cost budget $B$, there exist $\lambda_{1},\dots,\lambda_{k}\in\mathbb{R}^{+}$ and a $\gamma\in[0,1]$ such that the optimal cascading strategy $s_{\textsc{opt}}=(s^{(1)}_{\textsc{opt}},\dots,s^{(k)}_{\textsc{opt}})$ is given by the equalities $s^{(j)}_{\textsc{opt}}=\gamma s^{(j),\lambda_{j}}_{\textsc{min}}+(1-\gamma)s^{
(j),\lambda_{j}}_{\textsc{max}}$ where $s^{(j),\lambda_{j}}_{\textsc{min}}$ and $s^{(j),\lambda_{j}}_{\textsc{max}}$ are defined as in Theorem 1.

The main difference between Theorem 2 and Theorem 1 is that not all combinations of hyperparameters $\lambda_{1},\dots,\lambda_{k}\in\mathbb{R}^{+}$ and $\gamma\in[0,1]$ that achieve cost budget $B$ are optimal. Instead, finding the optimal hyperparameters requires solving another optimization problem. Specifically, let us denote by $Q_{D}\colon(\mathbb{R}^{+})^{k+1}\rightarrow\mathbb{R}$, resp. $C_{D}\colon(\mathbb{R}^{+})^{k+1}\rightarrow\mathbb{R}$, the average quality, resp. cost, of a cascading strategy on a training dataset $D$ for a given set of hyperparameters $\lambda_{1},\dots,\lambda_{k}\in\mathbb{R}^{+}$ and $\gamma\in[0,1]$. Then, the optimal hyperparameters are the solution to the optimization problem

$$ $\displaystyle\max_{\lambda_{1},\dots,\lambda_{k},\gamma}$ $\displaystyle Q_{D}(\lambda_{1},\dots,\lambda_{k},\gamma)$ (2) s.t. $\displaystyle C_{D}(\lambda_{1},\dots,\lambda_{k},\gamma)\leqslant B.$ $$

We could not find an analytical solution to this problem. Therefore, we assume $\lambda_{1}=\dots=\lambda_{k}=\lambda$ and apply the binary search technique from Section 2 to determine the optimal $\lambda$. This value is then used as initialization for a hyperparameter optimization tool, Hyperopt(^2^22[https://github.com/hyperopt/hyperopt](https://github.com/hyperopt/hyperopt)), to find the optimal values.

###### Theorem 2 (Optimal Cascading Strategy) .

#### Prior Work

Prior work on cascading has often relied on strong assumptions to simplify the strategy. The most common technique uses a threshold to decide whether to continue the cascade on an input $x$ (Chen et al., ; Gupta et al., ). Specifically, in step $j$, the cascade continues if $\hat{q}^{(j)}_{j-1}(x)<\tau_{j}$ for some threshold $\tau_{j}\in\mathbb{R}$. Below, we outline the conditions under which this simplified approach is optimal.

###### Corollary 1 (Optimal Threshold Strategy) .

Under minor technical assumptions, the thresholding strategy is equivalent to our cascading strategy if and only if the following conditions hold: the cost estimate $\hat{c}^{(j)}_{i}(x)$ is independent of $x$ for all $i,j\in\{1,\dots,k\}$, $\hat{q}^{(j)}_{i}(x)$ is independent of $x$ for all $i\geqslant j$, and the quality estimate $\hat{q}^{(j)}_{1:i}(x)$ is equal to $\hat{q}^{(j)}_{i}(x)$.

###### Corollary 1 (Optimal Threshold Strategy) .

## 4 Cascade Routing as Cascade Generalization

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 we have several specialized models that are experts at specific tasks, cascading is more beneficial when input queries vary in difficulty. In this section, we therefore present cascade routing, which is a generalization of both techniques. Proofs for all theorems and lemmas in this section are included in App. C.

#### Cascade Routing

Cascade routing closely resembles cascading, but with one crucial difference: the routing strategy at step $j$ routes between all possible supermodels, not just the supermodels $M_{1:j-1},\dots,M_{1:k}$. Therefore, both Definition 4 and Theorem 2 can be extended to this setting.

###### Definition 5 (Cascade Routing) .

A cascade routing strategy $s$ is a sequence of routing strategies $(s^{(1)},\dots,s^{(k)})$ such that, for a given sample $x\in\mathcal{X}$, $s^{(j)}$ routes between all supermodels in $\mathcal{M}$ that start with the $j-1$ models that have already been computed for this query.

###### Theorem 3 (Optimal Cascade Routing) .

For a given cost budget $B$, there exist $\lambda_{1},\dots,\lambda_{k}\in\mathbb{R}^{+}$ and a $\gamma\in\mathbb{R}^{+}$ such that the optimal cascade routing strategy $s_{\textsc{opt}}=(s^{(1)}_{\textsc{opt}},\dots,s^{(k)}_{\textsc{opt}})$ is given by $s^{(j)}_{\textsc{opt}}=\gamma s^{(j),\lambda_{j}}_{\textsc{min}}+(1-\gamma)s^{
(j),\lambda_{j}}_{\textsc{max}}$ where $s^{(j),\lambda_{j}}_{\textsc{min}}$ and $s^{(j),\lambda_{j}}_{\textsc{max}}$ are defined as in Theorem 1.

While cascade routing extends cascading and can therefore use the same hyperparameter optimization scheme, it also introduces additional challenges which we address in the following paragraphs.

###### Definition 5 (Cascade Routing) .

###### Theorem 3 (Optimal Cascade Routing) .

#### Model Order

In cascading, the model order is predetermined, 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 estimated quality $\hat{q}^{(j)}_{M}(x)$ and cost $\hat{c}^{(j)}_{M}(x)$ of a supermodel $M$ are order-independent. Therefore, supermodels that contain the same models in a different order will have the same associated cost and quality. To mitigate this, we sort the models within the selected supermodel by cost and compute the cheapest one first. This approach aligns with cascading, where more expensive models are only used if cheaper models do not suffice.

#### Number of Supermodels

In cascading, the quality and cost must be computed for a maximum of $k$ supermodels at each step. However, in cascade routing, the number of supermodels grows exponentially, leading to the need to evaluate up to $2^{k}$ supermodels. This increase can become prohibitively costly, particularly since the model selection process must remain computationally negligible with respect to model computation. To mitigate this, we leverage so-called negative marginal gains. Specifically, if a model $m$ in a supermodel $M$ negatively impacts the quality-cost tradeoff, all supermodels containing all models in $M$ can be pruned from the search space. 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:

###### Lemma 1 (Negative Marginal Gain) .

Let $M\in\mathcal{M}$ and $m$ be any model in $M$. Let the marginal gain of $m$ w.r.t. $M$ be defined as $\tau_{M}(x,\lambda)-\tau_{M\setminus\{m\}}(x,\lambda)$. Then, if the marginal gain of $m$ w.r.t. $M$ is strictly negative for a given query, the optimal cascade routing strategy will never run a supermodel $M^{\prime}\in\mathcal{M}$ that contains all models in $M$.

###### Lemma 1 (Negative Marginal Gain) .

## 5 Evaluation

We evaluate the performance of cascade routing and demonstrate that it significantly outperforms all other strategies. Additionally, we show that our new cascading approach surpasses the threshold-based cascading method (see Corollary 1). For this purpose, we first conduct experiments on RouterBench (Hu et al., ), a benchmark specifically designed to evaluate routing and cascading (Section 5.1). Next, we test cascade routing on two additional benchmarks to evaluate its performance in more realistic scenarios (Section 5.2). Lastly, we perform an ablation study to examine the impact of various design choices in cascade routing on performance and runtime (Section 5.3).

### 5.1 RouterBench

RouterBench (Hu et al., ) is a benchmark developed to evaluate the efficacy of different model selection strategies. It includes questions from seven diverse benchmarks, such as MMLU (Hendrycks et al., ), GSM8k (Cobbe et al., ), and MBPP (Austin et al., ), alongside answers from eleven different models ranging from GPT-4 (OpenAI, ) to Mistral-7B (Jiang et al., ). All models are evaluated under both zero-shot and five-shot settings.

#### Quality and Cost Estimates

Similar to (Hu et al., ), we estimate quality and cost by adding zero-centered Gaussian noise to their true values. Both cost and quality estimates are modeled as linear functions fitted on these noisy signals. We define the variance of the noisy signal as $\sigma_{\text{before}}^{2}$ before model computation and $\sigma_{\text{after}}^{2}$ after. By ensuring that $\sigma_{\text{after}}<\sigma_{\text{before}}$, this setup reflects the increased accuracy in cost and quality estimates after model computation, which is an essential requirement for cascading to perform well. To explore different uncertainty levels, we vary the variances to simulate low-, medium-, and high-noise scenarios, with exact values for the variances detailed in App. D.

#### Models

We evaluate cascade routing on RouterBench using three, five, and all eleven models available for model selection, ensuring a comprehensive evaluation across a range of scenarios. The exact models for each scenario are provided in App. D.

Figure: Figure 2: Quality-cost tradeoff on RouterBench for five models and medium-noise.
Refer to caption: x1.png

#### Strategies

We compare cascade routing against several baseline strategies, including the routing strategy described in Section 2, the threshold-based cascading approach from prior work (Corollary 1), and the optimal cascading strategy (Theorem 2). Additionally, as in (Hu et al., ), we include a baseline that linearly interpolates cost and quality on the Pareto frontier of the models. Fig. 2 illustrates the performance of these strategies with five models in a medium-noise setting.

#### Evaluation Metric

For each method, we evaluate performance using cost budgets ranging from the cheapest to the most expensive model, as shown in Fig. 2. This produces a quality-cost curve for each strategy. Following (Hu et al., ), we use the Area Under the Curve (AUC) as the performance metric.

**Table 1: AUC scores in $\%$ for different strategies on RouterBench across model and noise levels.**
|  | Three Models | Five Models | Eleven Models |  |  |  |  |  |  |
| --- | --- | --- | --- | --- | --- | --- | --- | --- | --- |
|  | Low | Med | High | Low | Med | High | Low | Med | High |
| Linear Interp. | $69.619\,211$ | $69.619\,211$ | $69.619\,211$ | $69.223\,137$ | $69.223\,137$ | $69.223\,137$ | $70.506\,406$ | $70.506\,406$ | $70.506\,406$ |
| Routing | $79.726\,787$ | $74.965\,568$ | $71.812\,637$ | $81.235\,991$ | $74.432\,665$ | $71.328\,369$ | $83.245\,409$ | $74.632\,066$ | $72.670\,410$ |
| Cascade (Baseline) | $80.863\,873$ | $74.641\,304$ | $72.475\,432$ | $82.332\,691$ | $73.029\,091$ | $69.526\,597$ | $84.480\,300$ | $73.643\,526$ | $69.788\,751$ |
| Cascade (Ours) | $81.129\,172$ | $76.100\,591$ | $72.666\,791$ | $83.049\,498$ | $75.148\,599$ | $70.175\,505$ | $84.449\,863$ | $75.103\,982$ | $70.255\,392$ |
| Cascade Routing | $82.339\,794$ | $76.556\,644$ | $73.232\,318$ | $84.342\,562$ | $76.315\,419$ | $72.744\,801$ | $87.275\,863$ | $77.615\,533$ | $74.397\,709$ |

#### Results

Table 1 presents the results for the zero-shot setting, with the five-shot results detailed in App. E. Cascade routing consistently outperforms all baseline strategies with performance gains between $1\%$ to $4\%$, which measured relatively to the naive linear interpolation baseline 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 levels, 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 practical relevance of our theoretical results.

### 5.2 Other Benchmarks

RouterBench does not provide log probabilities associated with model answers, which constrains the construction of more realistic quality estimates using features like perplexity. To address this, we develop two benchmarks that better simulate practical use cases for cascade routing.

#### Datasets

We perform experiments on classification and open-form reasoning tasks. The classification benchmarks include ARC-Challenge (Clark et al., ), MMLU-Pro (Wang et al., ), and MixEval (Ni et al., ). For open-form reasoning tasks, we use MMLU-Pro and GSM8k (Cobbe et al., ). In classification, models select a single option representing their answer, with no intermediate reasoning process. In contrast, open-form reasoning allows models to generate their answers after reasoning. We split each benchmark into a training set for training quality and cost estimates and a test set for evaluation. We evaluate nine models, three each from the Llama-3.1 (AI@Meta, ), Gemma (Gemma Team et al., ), and Mistral (Jiang et al., ) model families. The exact models are specified in App. D.

#### Quality and Cost Estimates

We estimate model quality by fitting a linear model based on features that reflect model uncertainty, such as perplexity (Gupta et al., ). Further features include the originating benchmark of each sample and whether earlier models in the cascade agree on their prediction. Full details on the features are provided in App. D. The linear model is trained using these features on the benchmark’s training split.

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.(^3^33We used the [Together API](https://www.together.ai/) for all our experiments.) 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 no model response is available, we estimate the response length using the average from the training data.

**Table 2: AUC scores on a classification and open-form reasoning benchmark.**
|  | Classification | Open-Form |  |  |  |  |
| --- | --- | --- | --- | --- | --- | --- |
|  | Llama | Gemma | Mistral | Llama | Gemma | Mistral |
| Linear Interp. | $74.282\,600$ | $61.683\,007$ | $63.389\,435$ | $79.113\,000$ | $54.097\,636$ | $53.859\,567$ |
| Routing | $74.922\,474$ | $64.439\,964$ | $64.890\,300$ | $79.318\,910$ | $58.395\,591$ | $58.705\,107$ |
| Cascade (Baseline) | $74.791\,917$ | $54.308\,093$ | $61.216\,450$ | $79.232\,862$ | $56.175\,065$ | $48.288\,646$ |
| Cascade (Ours) | $75.424\,172$ | $62.817\,299$ | $63.360\,217$ | $79.683\,355$ | $57.672\,177$ | $55.507\,380$ |
| Cascade Routing | $75.523\,230$ | $64.699\,685$ | $64.970\,634$ | $79.837\,041$ | $59.615\,956$ | $58.689\,949$ |

#### Results

Table 2 presents the results for the Llama, Gemma, and Mistral model families across both benchmarks. Cascade routing consistently performs on par with or outperforms all baselines, though with narrower margins reaching up to $1.2\%$. This reduced gain can be attributed to two main factors. First, the quality and cost estimates are very noisy, leading to performance gains over the naive baseline similar to those observed in high-noise scenarios on RouterBench. Second, the cascading strategy sometimes underperforms compared to the linear interpolation baseline, indicating that the post-computation features used for quality estimation, such as perplexity, do not provide sufficient advantage to warrant running models in a cascading fashion.

As expected, cascade routing is most effective when both routing and cascading outperform the linear interpolation baseline. When cascading offers no or very small performance improvement, cascade routing typically reduces to pure routing. Larger performance gains are observed only when cascading adds value beyond routing. Our results suggest that more sophisticated methods are needed to enhance quality estimates and improve the overall effectiveness of all model selection strategies in practical applications.

### 5.3 Ablation Study

We conduct an ablation study to examine the impact of various design choices in cascade routing on performance and runtime. Runtime is a 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.

To investigate this, we repeat the experiment from Section 5.1 when using all eleven models, testing different variations of cascade routing. We evaluate a slower variation that omits Lemma 1, thereby requiring more supermodels to be evaluated (Slow), a greedy variation that only considers supermodels of length $j+1$ 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).

**Table 3: AUC scores and average runtime for various variations of cascade routing on RouterBench when using all eleven models.**
|  | Low-Noise | Medium-Noise | High-Noise |  |  |  |
| --- | --- | --- | --- | --- | --- | --- |
|  | AUC (%) | Time (ms) | AUC (%) | Time (ms) | AUC (%) | Time (ms) |
| Cascade Routing | $87.262\,698$ | $12.047\,858$ | $77.604\,619$ | $12.754\,497$ | $74.407\,472$ | $9.412\,891$ |
| Slow | $87.293\,511$ | $80.037\,322$ | $77.624\,591$ | $87.231\,799$ | $74.407\,204$ | $67.450\,265$ |
| Greedy | $85.932\,291$ | $1.635\,961$ | $77.162\,711$ | $1.587\,761$ | $74.351\,528$ | $1.040\,749$ |
| No-Expect | $85.977\,675$ | $3.370\,333$ | $77.111\,513$ | $3.039\,908$ | $74.347\,163$ | $1.773\,999$ |

#### Results

Table 3 presents the results of the ablation study. 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 seems to be 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 in this scenario, making the expected value computation less important.

Furthermore, the Greedy and No-Expect variants perform very similarly, while Greedy is about twice as fast as 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 a 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.

## 6 Related Work

We discuss related work in routing and cascading.

#### Routing

Routing is a widely studied problem in machine learning, particularly in the task of directing input queries to specialized expert models. One of the most common applications of routing is model selection for natural language input queries with a known correct answer (Ding et al., ; Hari and Thomson, ; Liu et al., ; Jang et al., ; Nguyen et al., ; Sakota et al., ; Shnitzer et al., ). All these works train a machine learning model to predict 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.

Routing is also applied in other areas. For instance, Lu et al. (); Ong et al. () 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. () employ routing for API selection in multi-label classification tasks, focusing on directing queries to the appropriate API based on task requirements. Similarly, Zhang et al. () apply routing in software agent environments, directing user issues to the agent most suited to handle them.

#### Cascading

Cascading techniques are primarily used to reduce inference costs by employing smaller models initially and only cascading to larger models if the smaller ones fail to provide a sufficiently accurate answer. Most often, cascading decisions are based on the smaller model’s confidence in its own predictions (Chen et al., ; Ramírez et al., ; Varshney and Baral, ). However, alternative techniques also exist. For example, Madaan et al. () propose running models multiple times and measuring the variance in their responses to decide whether to cascade to a larger model.

For classification tasks, early stopping is another cascading strategy (Li et al., ; Schuster et al., ). In this approach, the cascade halts when a model’s intermediate layers generate representations that are sufficiently informative to predict the correct class. This reduces computational costs by avoiding the need to process every query through the entire model.

There has also been specific research on quality estimation within cascading frameworks. Gupta et al. () examine various measures of uncertainty in language model answers, evaluating their impact on cascading performance. Meanwhile, Jitkrittum et al. () explore failure cases in cascading mechanisms that rely on uncertainty, introducing alternative quality measures that enhance cascade efficiency. Lastly, Xue et al. () apply cascading to majority voting for a single model to obtain a method called dynamic voting: the cascade stops depending on the aggregated answers of all previous model computations. This allows the system to process simpler queries using fewer votes while allocating more computational resources for harder queries.

## 7 Limitations

While cascade routing provides a promising approach to improve model selection strategies, it requires accurate cost and quality estimates to be effective. However, in Section 5.2 we found that quality estimates based on current state-of-the-art methods contain significant noise. This limits the performance improvement of cascade routing over routing, as the quality estimates are not accurate enough to guide the selection of the best model. As shown in Section 5.1, lower noise in the quality and cost estimates lead to much better performance of all model selection strategies, indicating that further work that aims to reduce the noise in the quality and cost estimates is needed to fully leverage the potential of cascade routing.

Another limitation is the necessity of a training dataset to optimize the hyperparameters associated with cascade routing. While both routing and cascading suffer from the same disadvantage, the training data required for routing is much more minimal, since it only needs to estimate two hyperparameters. In contrast, cascade routing requires estimating multiple hyperparameters on a more complex optimization surface.

## 8 Conclusion

In this work, we introduced a novel framework for routing and cascading that enabled us to propose theoretically optimal strategies for both paradigms. Furthermore, we used this theoretical analysis to propose a new paradigm for model selection, cascade routing, which combines the benefits of both routing and cascading. We showed that cascade routing can significantly outperform its baselines, especially with good quality and cost estimates. Furthermore, we found that our new cascading strategy significantly outperforms existing approaches to cascading, showing our theoretical analysis also leads to practical gains. Our work provides a theoretical foundation for model selection strategies and opens up new avenues for future research in this area, especially in the direction of obtaining more accurate quality and cost estimates.

## Reproducibility Statement

All our proofs are included in the appendix and contain the exact conditions under which each statement in the main text holds. We furthermore make our code available with clear instructions on how to reproduce our results.

## Acknowledgements

This work was funded in part by the Swiss National Science Foundation (SNSF) [200021_207967].

This work has been done as part of the EU grant ELSA (European Lighthouse on Secure and Safe AI, grant agreement 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 Commission. Neither the European Union nor the European Commission can be held responsible for them.

The work has received funding from the Swiss State Secretariat for Education, Research and Innovation (SERI).

## Appendix A Routing

To prove Theorem 1, we first rewrite the routing optimization problem in Eq. 1 as a linear program over functions $s:\mathcal{X}\rightarrow\mathbb{R}^{k}$ instead of functions $s:\mathcal{X}\rightarrow\Delta_{k}$. This makes the optimization problem more tractable. Specifically, Eq. 1 can be rewritten as follows:

$$ $\displaystyle\max_{r}$ $\displaystyle\mathbb{E}_{x\sim\mathcal{X}}\left[\sum_{i=1}^{k}s_{i}(x)\hat{q}_ {i}(x)\right]$ (3) s.t. $\displaystyle\mathbb{E}_{x\sim\mathcal{X}}\left[\sum_{i=1}^{k}s_{i}(x)\hat{c}_ {i}(x)\right]\leqslant B$ $\displaystyle\forall i\in\{1,...,k\}:\forall x\in\mathcal{X}:s_{i}(x)\geq 0 \land\sum_{j=1}^{k}s_{j}(x)=1$ $$

We then rewrite Theorem 1 to allow for a more exact formulation of the optimal routing strategy:

###### Theorem 4 .

(Optimal Routing Strategy)
Suppose there exists an admissible solution to the set of constraints in Eq. 3. For any $\lambda\in\mathbb{R}^{+}$, let $S_{\lambda}$ be the set of routing strategies $s$ that satisfy the following constraints:

$$ $\forall x\in\mathcal{X},\forall i\in\{1,...,k\}:\hat{q_{i}}(x)-\lambda\hat{c_{ i}}(x)<\max_{j}\hat{q_{j}}(x)-\lambda\hat{c_{j}}(x)\Rightarrow s_{i}(x)=0$ (4) $$

If there exists a strategy in $S_{0}$ that has a cost less than or equal to $B$, then this strategy achieves the optimal quality. Otherwise, there exists a $\lambda^{*}\in\mathbb{R}^{+}$ such that $S_{\lambda}$ contains a routing strategy that has exactly cost $B$ and all routing strategies in $\bigcup_{\lambda\in\mathbb{R}^{+}}S_{\lambda}$ 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. 3 is necessary to ensure that the set of possible solutions to Eq. 3 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 $s_{\textsc{opt}}$ as a convex combination of $s_{\textsc{min}}^{\lambda}$ and $s_{\textsc{max}}^{\lambda}$ is a direct consequence of Theorem 4. Indeed, let $\lambda^{*}$ be as defined in Theorem 4. Then $s_{\textsc{min}}^{\lambda^{*}}$, resp. $s_{\textsc{max}}^{\lambda^{*}}$, must have the lowest, resp. highest, cost among all routing strategies in $S_{\lambda^{*}}$. Since there is a routing strategy in $S_{\lambda^{*}}$ that has cost $B$, there must exist a convex combination of $s_{\textsc{min}}^{\lambda^{*}}$ and $s_{\textsc{max}}^{\lambda^{*}}$ that also has cost $B$ and thus achieves the optimal quality.

We first prove several lemmas before proving the theorem.

###### Lemma 2 .

$S_{\lambda}$ is non-empty and convex for all $\lambda\in\mathbb{R}^{+}$.

###### Proof.

Non-emptiness follows from the fact that the routing strategy that assigns all probability mass for a sample $x$ to a model $i$ for which $\hat{q_{i}}(x)-\lambda\hat{c_{i}}(x)$ is maximal, is in $S_{\lambda}$. For convexity, let $s^{(1)},s^{(2)}\in S_{\lambda}$ be arbitrary. Let $s^{\gamma}$ be the convex combination of $s^{(1)}$ and $s^{(2)}$ with weight $\gamma\in[0,1]$. Let $x\in\mathcal{X}$ be arbitrary. Then, $s_{i}^{\gamma}(x)>0$ if and only if $s_{i}^{(1)}(x)>0$ or $s_{i}^{(2)}(x)>0$. Since $s^{(1)},s^{(2)}\in S_{\lambda}$, we have $\hat{q_{i}}(x)-\lambda\hat{c_{i}}(x)\geqslant\max_{j}\hat{q_{j}}(x)-\lambda
\hat{c_{j}}(x)$ for all $i$ such that $s_{i}^{(1)}(x)>0$ or $s_{i}^{(2)}(x)>0$. This implies that $\hat{q_{i}}(x)-\lambda\hat{c_{i}}(x)\geqslant\max_{j}\hat{q_{j}}(x)-\lambda
\hat{c_{j}}(x)$ for all $i$ such that $s_{i}^{\gamma}(x)>0$. Thus, $s^{\gamma}\in S_{\lambda}$.
∎

###### Lemma 3 .

Let $\lambda_{1}<\lambda_{2}$ and $s^{(1)}$, resp. $s^{(2)}$ be arbitrary routing strategies in $S_{\lambda_{1}}$, resp. $S_{\lambda_{2}}$. Then, the cost of $s^{(1)}$ is greater or equal to the cost of $s^{(2)}$, i.e.,

$$ $\mathbb{E}_{x\sim\mathcal{X}}\left[\sum_{i=1}^{k}s^{(1)}_{i}(x)\hat{c}_{i}(x) \right]\geqslant\mathbb{E}_{x\sim\mathcal{X}}\left[\sum_{i=1}^{k}s^{(2)}_{i}(x )\hat{c}_{i}(x)\right]$ $$

###### Proof.

We show that for any $x\in\mathcal{X}$, the cost of $s^{(1)}$ is greater or equal to the cost of $s^{(2)}$. Let $x\in\mathcal{X}$ be arbitrary. Suppose $s^{(1)}$ is strictly cheaper than $s^{(2)}$. Then, there must exist a model pair $i,j$ such that $\hat{c}_{i}(x)<\hat{c}_{j}(x)$, $s^{(1)}_{i}(x)>s^{(2)}_{i}(x)\geqslant 0$, and $s^{(2)}_{j}(x)>s^{(1)}_{j}(x)\geqslant 0$. However, $s^{(1)}_{i}(x)>0$ implies

$$ $\hat{q}_{i}(x)-\lambda_{1}\hat{c}_{i}(x)\geqslant\hat{q}_{j}(x)-\lambda_{1} \hat{c}_{j}(x).$ $$

Furthermore, since $\lambda_{1}-\lambda_{2}<0$, we have

$$ $\hat{c}_{i}(x)(\lambda_{1}-\lambda_{2})>\hat{c}_{j}(x)(\lambda_{1}-\lambda_{2}).$ $$

Adding these two inequalities gives

$$ $\hat{q}_{i}(x)-\lambda_{2}\hat{c}_{i}(x)>\hat{q}_{j}(x)-\lambda_{2}\hat{c}_{j} (x),$ $$

which is a contradiction with $s^{(2)}_{j}(x)>0$. Thus, the cost of $s^{(1)}$ is greater or equal to the cost of $s^{(2)}$.
∎

###### Lemma 4 .

Let $\Lambda$ be the set of points $\lambda\in\mathbb{R}$ such that there exist an $x\in\mathcal{X}$ and $i\neq j$ such that $\hat{q_{i}}(x)-\lambda\hat{c_{i}}(x)=\hat{q_{j}}(x)-\lambda\hat{c_{j}}(x)$. Let $\lambda_{1}<\lambda_{2}$ be such that $[\lambda_{1},\lambda_{2}]\cap\Lambda=\emptyset$. Then, $S_{\lambda_{1}}=S_{\lambda_{2}}$. Furthermore, if $[\lambda_{1},\lambda_{2}]\cap\Lambda=\{\lambda^{*}\}$, then $S_{\lambda}\subset S_{\lambda^{*}}$ for all $\lambda\in[\lambda_{1},\lambda_{2}]$.

###### Proof.

We first show the first statement by showing that $S_{\lambda_{1}}\setminus S_{\lambda_{2}}=\emptyset$. $S_{\lambda_{2}}\setminus S_{\lambda_{1}}=\emptyset$ follows analogously. Suppose there exists a routing strategy $s\in S_{\lambda_{1}}\setminus S_{\lambda_{2}}$. Since $s\notin S_{\lambda_{2}}$, there must exist an $x\in\mathcal{X}$ and model $i$ such that $s_{i}(x)>0$ and $\hat{q_{i}}(x)-\lambda_{2}\hat{c_{i}}(x)<\max_{j}\hat{q_{j}}(x)-\lambda_{2}
\hat{c_{j}}(x)$. Let $j$ be an index such that $\hat{q_{i}}(x)-\lambda_{2}\hat{c_{i}}(x)<\hat{q_{j}}(x)-\lambda_{2}\hat{c_{j}}
(x)$. Since $s\in S_{\lambda_{1}}$, we have $\hat{q_{i}}(x)-\lambda_{1}\hat{c_{i}}(x)\geqslant\hat{q_{j}}(x)-\lambda_{1}
\hat{c_{j}}(x)$. By continuity, there exists a $\lambda\in[\lambda_{1},\lambda_{2}]$ such that $\hat{q_{i}}(x)-\lambda\hat{c_{i}}(x)=\hat{q_{j}}(x)-\lambda\hat{c_{j}}(x)$, which is a contradiction with $[\lambda_{1},\lambda_{2}]\cap\Lambda=\emptyset$.

Now suppose $[\lambda_{1},\lambda_{2}]\cap\Lambda=\{\lambda^{*}\}$. Let $\lambda\in[\lambda_{1},\lambda^{*})$ be arbitrary and let $s\in S_{\lambda}$ be arbitrary. We show that $s\in S_{\lambda^{*}}$. For $\lambda\in(\lambda^{*},\lambda_{2}]$, the proof is completely analogous. By contradiction, suppose there exists an $x\in\mathcal{X}$ and model $i$ such that $s_{i}(x)>0$ and $\hat{q_{i}}(x)-\lambda^{*}\hat{c_{i}}(x)<\max_{j}\hat{q_{j}}(x)-\lambda^{*}
\hat{c_{j}}(x)$. This means there exists a model $j$ such that $\hat{q_{i}}(x)-\lambda^{*}\hat{c_{i}}(x)<\hat{q_{j}}(x)-\lambda^{*}\hat{c_{j}}
(x)$. Since $s\in S_{\lambda}$, we know that $\hat{q_{i}}(x)-\lambda\hat{c_{i}}(x)\geqslant\hat{q_{j}}(x)-\lambda\hat{c_{j}}
(x)$. This implies that there must exist a $\lambda^{\prime}\in[\lambda_{1},\lambda^{*})$ such that $\hat{q_{i}}(x)-\lambda^{\prime}\hat{c_{i}}(x)=\hat{q_{j}}(x)-\lambda^{\prime}
\hat{c_{j}}(x)$. However, this is a contradiction with $[\lambda_{1},\lambda^{*})\cap\Lambda=\emptyset$. Thus, $s\in S_{\lambda^{*}}$.
∎

In what follows, we will assume that $|\Lambda|<\infty$. This is a very minor assumption. For instance, if $\hat{q}$ and $\hat{c}$ only take on a finite amount of values, this is trivially satisfied. Since estimators are implemented on a computer, they will always have a finite precision, meaning that $\hat{q}$ and $\hat{c}$ will only take on a finite amount of values.

###### Lemma 5 .

Let $\lambda_{1}<\lambda_{2}$ and $s^{(1)}$, resp. $s^{(2)}$ be arbitrary routing strategies in $S_{\lambda_{1}}$, resp. $S_{\lambda_{2}}$, with costs resp. $B_{1}$ and $B_{2}$. Then, for any $B\in[B_{1},B_{2}]$ there exists a $\lambda\in[\lambda_{1},\lambda_{2}]$ such that $S_{\lambda}$ contains a routing strategy that has exactly cost $B$.

###### Proof.

Let $B\in[B_{1},B_{2}]$ be arbitrary. If $B=B_{1}$ or $B=B_{2}$, the statement is trivially true. Therefore, suppose $B\in(B_{1},B_{2})$. Let $\Lambda$ be as defined in Lemma 4. By Lemma 3, there exists a $\lambda^{*}\in[\lambda_{1},\lambda_{2}]$ such that all strategies in $S_{\lambda}$ for $\lambda<\lambda^{*}$, resp. $\lambda>\lambda^{*}$, have cost at least, resp. at most, $B$. If $\lambda^{*}\notin\Lambda$, then the first part of Lemma 4, together with $|\Lambda|<\infty$, implies that $S_{\lambda^{*}}=S_{\lambda^{*}-\epsilon}=S_{\lambda^{*}+\epsilon}$ for some $\epsilon>0$. All the strategies in $S_{\lambda^{*}}$ must therefore have cost both at least and at most $B$, meaning they should equal $B$. We can therefore assume that $\lambda^{*}\in\Lambda$. By Lemma 4 and $|\Lambda|<\infty$, there is en $\epsilon>0$ such that $S_{\lambda^{*}-\epsilon}\subset S_{\lambda^{*}}$ and $S_{\lambda^{*}+\epsilon}\subset S_{\lambda^{*}}$. Let $s^{-}\in S_{\lambda^{*}-\epsilon}$ and $s^{+}\in S_{\lambda^{*}+\epsilon}$ be arbitrary. Let $s^{\gamma}$ be the convex combination of $s^{-}$ and $s^{+}$ with weight $\gamma\in[0,1]$. Since $s^{-},s^{+}\in S_{\lambda^{*}}$, we have $s^{\gamma}\in S_{\lambda^{*}}$ by Lemma 2. Denote by $B^{-}$, resp. $B^{+}$, the cost of $s^{-}$, resp $s^{+}$. Furthermore, the cost of $s^{\gamma}$ is $\gamma B^{-}+(1-\gamma)B^{+}$. Since $B\in[B^{-},B^{+}]$, there exists a $\gamma\in[0,1]$ such that $s^{\gamma}$ has cost exactly $B$.
∎

We can now prove the theorem.

###### Proof.

If $S_{0}$ contains a 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 $S_{0}$ is greater than $B$. For $\lambda\rightarrow\infty$, $S_{\lambda}$ 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 5, there exists a $\lambda^{*}\in\mathbb{R}$ such that $S_{\lambda^{*}}$ contains a routing strategy that has exactly cost $B$.

Let $s$ be an arbitrary routing strategy in $\bigcup_{\lambda\in\mathbb{R}^{+}}S_{\lambda}$ that has cost $B$. Specifically, let $s\in S_{\lambda}$. Let $s^{\prime}$ be any other routing strategy that is an admissible solution to the optimization problem. Then:

$$ $\displaystyle\mathbb{E}_{x\in X}\left[\sum_{i=1}^{k}s_{i}^{\prime}(x)\hat{q}_{ i}(x)\right]$ $\displaystyle=\mathbb{E}_{x\in X}\left[\sum_{i=1}^{k}s_{i}^{\prime}(x)\hat{q}_ {i}(x)-\lambda B+\lambda B\right]$ $\displaystyle\leqslant\mathbb{E}_{x\in X}\left[\sum_{i=1}^{k}s_{i}^{\prime}(x) \left(\hat{q}_{i}(x)-\lambda\hat{c}_{i}(x)\right)+\lambda B\right]$ $\displaystyle\leqslant\mathbb{E}_{x\in X}\left[\sum_{i=1}^{k}s_{i}(x)\left( \hat{q}_{i}(x)-\lambda\hat{c}_{i}(x)\right)+\lambda B\right]$ $\displaystyle=\mathbb{E}_{x\in X}\left[\sum_{i=1}^{k}s_{i}(x)\hat{q}_{i}(x)\right]$ $$

Thus, $s$ achieves the optimal quality.

∎

###### Theorem 4 .

###### Lemma 2 .

###### Proof.

###### Lemma 3 .

###### Proof.

###### Lemma 4 .

###### Proof.

###### Lemma 5 .

###### Proof.

###### Proof.

## Appendix B Cascading

To prove Theorem 2, we heavily rely on the results derived in App. A. As explained in Section 3, 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 to stop the cascade or to continue to the next model. It should continue to the next model if any of the supermodels $M_{1:j},\dots,M_{1:k}$ is better to run than $M_{1:j-1}$ for some measure of ’better’. Therefore, the cascading strategy is indeed performing a routing operation between the supermodels $M_{1:j-1},\dots,M_{1:k}$.

However, the optimization problem does slightly change compared to the routing problem. First of all, for each query $x\in\mathcal{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, it is not required that the cost of the router at step $j$ is exactly equal to $B$.

Therefore, we reformulate cascading using an inner and outer optimization problem. The inner optimization problem aims to find the optimal routing strategy at step $j$ for a given budget $B_{j}$. The outer optimization problem aims to find the optimal budget $B_{j}$ 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_{j}(M)$ be the probability that the cascade computed supermodel $M$ by step $j$. Then, the inner optimization problem at step $j$ can be formulated as:

$$ $\displaystyle\max_{r^{(j)}}$ $\displaystyle\mathbb{E}_{x\sim\mathcal{X}}\left[P_{j}(M_{1:j-1})\sum_{i=j-1}^{ k}r_{1:i}(x)\hat{q}^{(j)}_{1:i}(x)\right]$ (5) s.t. $\displaystyle\mathbb{E}_{x\sim\mathcal{X}}\left[P_{j}(M_{1:j-1})\sum_{i=j-1}^{ k}r_{1:i}(x)\hat{c}^{(j)}_{1:i}(x)\right]\leqslant B_{j}$ $\displaystyle\forall i\in\{j-1,...,k\}:\forall x\in\mathcal{X}:r_{1:i}(x)\geq 0 \land\sum_{i=j-1}^{k}r_{1:i}(x)=1$ $$

Note that $P_{j}(M_{1:j-1})$ can be incorporated in the quality and cost estimates. This leaves us with the exact same optimization problem as the routing problem, but with a different budget $B_{j}$. Since the chosen model only depends on the maximization of $P_{j}(M_{1:j-1})\hat{q}^{(j)}_{i}(x)-\lambda_{j}P_{j}(M_{1:j-1})\hat{c}^{(j)}_
{i}(x)$, the probability $P_{j}(M_{1:j-1})$ can be divided out of the optimization problem.

The inner optimization problems prove the existence of optimal routing strategies at each step $j$ with parameters $\lambda_{j}$. We note that there only needs to be one parameter $\gamma$ that determines the convex combination since the budget $B$ is only enforced over the entire cascade.

Let us denote the quality and cost of the entire cascading strategy for given parameters $\lambda_{1},\dots,\lambda_{k}$ and $\gamma$ as $Q(\lambda_{1},\dots,\lambda_{k},\gamma)$ and $C(\lambda_{1},\dots,\lambda_{k},\gamma)$ respectively. Then, the outer optimization problem can be formulated as:

$$ $\displaystyle\max_{\lambda_{1},\dots,\lambda_{k},\gamma}$ $\displaystyle Q(\lambda_{1},\dots,\lambda_{k},\gamma)$ (6) s.t. $\displaystyle C(\lambda_{1},\dots,\lambda_{k},\gamma)\leqslant B$ $$

To solve this outer optimization problem, we simply perform a hyperparameter search over the budgets $B_{1},\dots,B_{k}$ using a hyperparameter optimization search as discussed in Section 3.

### B.1 Prior Approximations

We now prove Corollary 1. Before doing so, we first need to define what we exactly mean by equivalency. For this purpose, let $\mathcal{C}_{1}$ be defined as follows:

$$ $\mathcal{C}_{1}=\left\{s\mid s\text{ is a cascading strategy with parameters } \lambda_{1},\dots,\lambda_{k},\gamma=0\text{ using estimates }\hat{q}^{(j)}, \hat{c}^{(j)}\right\}$ $$

Similarly, let $\mathcal{C}_{2}$ be defined as follows:

$$ $\mathcal{C}_{2}=\left\{s\mid s\text{ is a thresholding strategy with parameters }\tau_{1},\dots,\tau_{k}\text{ using estimates }\hat{q}^{(j)},\hat{ c}^{(j)}\right\}$ $$

We note that we set $\gamma=0$ since the thresholding strategy is deterministic. We therefore restrict the cascading strategy to be deterministic as well.

We define the equivalence between the two sets as follows:

###### Definition 6 (Equivalence of Strategies) .

We say a set of strategies $\mathcal{C}_{1}$ is equivalent to another set of strategies $\mathcal{C}_{2}$, denoted as $\mathcal{C}_{1}\equiv\mathcal{C}_{2}$, if for all $s_{0}\in\mathcal{C}_{1}\cup\mathcal{C}_{2}$ there exists a $s_{1}\in\mathcal{C}_{1}$, and a $s_{2}\in\mathcal{C}_{2}$ such that for all $x\in\mathcal{X}$, $s_{0}$, $s_{1}$ and $s_{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 2 (Optimal Thresholding Strategy) .

Let $\mathcal{C}_{1}$, $\mathcal{C}_{2}$ be defined as above. Then, $\mathcal{C}_{1}\equiv\mathcal{C}_{2}$ if and only if there exists alternative quality and cost estimates $\hat{q}_{i}^{(j)^{\prime}}(x)$ and $\hat{c}_{i}^{(j)^{\prime}}(x)$ with associated set of cascading strategies $\mathcal{C}_{1}^{\prime}$ such that $\mathcal{C}_{1}\equiv\mathcal{C}_{1}^{\prime}$ and the following conditions hold on these alternative quality and cost estimates: $\hat{c}^{(j)^{\prime}}_{i}(x)$ is independent of $x$ and bigger than 0 0, $\hat{q}^{(j)^{\prime}}_{i}(x)$ is independent of $x$ for all $i\geqslant j$, and $\hat{q}^{(j)^{\prime}}_{1:i}(x)$ is equal to $\hat{q}^{(j)^{\prime}}_{i}(x)$.

The main difference between Corollary 2 and Corollary 1 is 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 the corollary as follows: the thresholding strategy is equivalent to any of our cascading strategies if and only if it is possible to construct alternative estimates such that the conditions hold.

###### Proof.

We note that the cascade $s\in\mathcal{C}_{1}$ continues on a sample if the following condition holds:

$$ $\hat{q}_{1:j-1}^{(j)}(x)-\lambda_{j}\hat{c}_{1:j-1}^{(j)}(x)<\max_{i\in\{j,... ,k\}}\hat{q}_{1:i}^{(j)}(x)-\lambda_{j}\hat{c}_{1:i}^{(j)}(x)$ (7) $$

If $\mathcal{C}_{1}\equiv\mathcal{C}_{1}^{\prime}$, it is clear that Eq. 7 reduces to the thresholding strategy for all strategies in $\mathcal{C}_{1}^{\prime}$. Indeed, for any $s\in\mathcal{C}_{1}^{\prime}$, set $\tau_{j}=\max_{i\in\{j,...,k\}}\hat{q}_{1:i}^{(j)}-\lambda_{j}\hat{c}_{j:i}^{(
j)}$ and the thresholding strategy is equivalent to $s$. Alternatively, if $s\in\mathcal{C}_{2}$, suppose $\max_{i\in\{j,...,k\}}\hat{q}_{1:i}^{(j)}-\lambda_{j}\hat{c}_{j:i}^{(j)}=\hat{
q}_{1:i}^{(j)}-\lambda_{j}\hat{c}_{j:i}^{(j)}$ for some index $i$. Then, set $\lambda_{j}=\tau_{j}/\hat{c}_{j:i}^{(j)}-\hat{q}_{1:i}^{(j)}/\hat{c}_{j:i}^{(j)}$ and the cascading strategy is equivalent to $s$. Therefore, $\mathcal{C}_{1}\equiv\mathcal{C}_{1}^{\prime}\equiv\mathcal{C}_{2}$.

Suppose now that $\mathcal{C}_{1}\equiv\mathcal{C}_{2}$. We construct alternative quality and cost estimates $\hat{q}_{i}^{(j)^{\prime}}(x)$ and $\hat{c}_{i}^{(j)^{\prime}}(x)$ such that the conditions hold and such that $\mathcal{C}_{1}\equiv\mathcal{C}_{1}^{\prime}$. For this purpose, we define $\hat{c}_{i}^{(j)^{\prime}}(x)=1$ for all $i,j\in\{1,\dots,k\}$, $\hat{q}_{i}^{(j)^{\prime}}(x)=1$ for all $i\geqslant j$, and $\hat{q}_{i}^{(j)^{\prime}}(x)=\hat{q}_{i}^{(j)}(x)$ otherwise. Furthermore, we set $\hat{q}_{1:i}^{(j)^{\prime}}(x)=\hat{q}_{i}^{(j)^{\prime}}(x)$ for all $i,j\in\{1,\dots,k\}$. The equivalence of $\mathcal{C}_{1}^{\prime}$ and $\mathcal{C}_{2}$ can now be proven analogously to the previous paragraph. Therefore, $\mathcal{C}_{1}\equiv\mathcal{C}_{1}^{\prime}\equiv\mathcal{C}_{2}$.
∎

###### Definition 6 (Equivalence of Strategies) .

###### Corollary 2 (Optimal Thresholding Strategy) .

###### Proof.

## Appendix C Cascade Routing

We first note that the proof of the optimality of the cascade routing strategy is equivalent to the proof of the optimality of the cascade strategy, except that the expectation in the optimization problem Eq. 5 is now not only over $x\in X$, but also over all possible supermodels that were computed by step $j-1$. However, this does not change the optimization problem, and the proof is completely analogous to the proof given in Section 3. Thus, all we need to prove is Lemma 1. To prove the lemma, we first prove the following lemma.

###### Lemma 6 .

Let $Q_{1},...,Q_{k}$ be distributions. Let $\mathcal{S}$ be the superset of $\{1,...,k\}$. Then $f:\mathcal{S}\rightarrow\mathbb{R}$ defined as $f(S)=\mathbb{E}(\max_{i\in S}Q_{i})$ is submodular. Here, we define $\max_{i\in\emptyset}Q_{i}=-\infty$

###### Proof.

Let $T\subset S\subset\{1,\dots,k\}$ and $j\in\{1,\dots,k\}$ be arbitrary. To show the submodularity of $f$, we need to show that

$$ $f(T\cup\{j\})-f(T)\geq f(S\cup\{j\})-f(S).$ $$

We can write:

$$ $\displaystyle f(S\cup\{j\})-f(S)$ $\displaystyle=\mathbb{E}(\max_{i\in S\cup\{j\}}Q_{i})-\mathbb{E}(\max_{i\in S} Q_{i})$ $\displaystyle=\mathbb{E}(\max(0,Q_{j}-\max_{i\in S}Q_{i}))$ $\displaystyle\leqslant\mathbb{E}(\max(0,Q_{j}-\max_{i\in T}Q_{i}))$ $\displaystyle=\mathbb{E}(\max_{i\in T\cup\{j\}}Q_{i})-\mathbb{E}(\max_{i\in T} Q_{i})$ $\displaystyle=f(T\cup\{j\})-f(T).$ $$

In the proof, we needed $\max_{i\in\emptyset}Q_{i}=-\infty$ in the case $T=\emptyset$.
∎

We note that the assertion that $\max_{i\in\emptyset}Q_{i}=-\infty$ corresponds to the fact that giving no answer to a query has $-\infty$ quality.

We can now prove Lemma 1.

###### Proof.

Let $M$ and $m$ be as in the lemma. Suppose $M^{\prime}$ is a supermodel that contains all models in $M$. Furthermore, let $M^{\prime\prime}=M^{\prime}\setminus m$. We show that the supermodel $M^{\prime\prime}$ is always strictly preferred over $M^{\prime}$. To see this, we note that the difference between $\tau_{M^{\prime}}(x,\lambda)$ and $\tau_{M^{\prime\prime}}(x,\lambda)$ is equal to

$$ $\mathbb{E}(\max_{m^{\prime}\in M^{\prime}}\hat{q}_{m^{\prime}}(x))-\mathbb{E}( \max_{m^{\prime}\in M^{\prime\prime}}\hat{q}_{m^{\prime}}(x))-\lambda_{j}\hat{ c}_{m}(x)$ $$

By Lemma 6, this difference is smaller than $\hat{q}_{M}(x)-\hat{q}_{M\setminus\{m\}}(x)-\lambda_{j}\hat{c}_{m}(x)$. Thus, by assumption, this difference is negative, and therefore $M^{\prime\prime}$ is always preferred over $M^{\prime}$, which concludes the proof.
∎

###### Lemma 6 .

###### Proof.

###### Proof.

## Appendix D Experimental Details

We describe some additional details about the experimental setup and the datasets used in our experiments.

### D.1 Routerbench

**Table 4: Standard deviations of the noise levels on the RouterBench dataset.**
|  | Quality | Cost |  |  |
| --- | --- | --- | --- | --- |
|  | $\sigma_{\text{before}}$ | $\sigma_{\text{after}}$ | $\sigma_{\text{before}}$ | $\sigma_{\text{after}}$ |
| 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 |

#### 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

In Table 4 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 0 0 and $1$, and the average cost of the smallest models is $0.000073$, while the average cost of the largest models is $0.003281$. We fit a logistic regression model on 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, we use the models Mixtral-8x7b-Chat, GPT-3.5-Turbo-1106, and GPT-4-1106-Preview. When using five models, we add WizardLM-13B-V1.2 and Claude-v2 to the mix. For eleven models, we use all models available in the benchmark.

### D.2 Other Benchmarks

#### Data Split

We split each dataset in each benchmark into a training set and a 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 use 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-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 a best-effort extraction by trying various regex patterns. Details on the prompts and regex patterns used for each benchmark are provided in the code repository.

#### Models

For the Llama-3.1 model family, we use the models Llama-3.1-8B-Instruct, Llama-3.1-70B-Instruct, and Llama-3.1-405B-Instruct. For the Gemma model family, we use the models Gemma-2B-Instruct, Gemma-2-9B-Instruct, and Gemma-2-27B-Instruct. For the Mistral model family, we use the models Mistral-7B-Instruct-v0.3, Mixtral-8x7B-Instruct-v0.1, and Mixtral-8x22B-Instruct-v0.1.

#### Features Quality Estimates

We specify the exact features used for the logistic regression model that serves as the quality estimator in Section 5.2. First, we include a 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. []. If several models have been computed, we also include whether they agree on their prediction.

We note that we train a separate logistic regression model for each history of computed models, and for each model separately as well. Thus we have one linear model for each combination of a target model $m_{i}$ and computed models $m_{i_{1}},\dots,m_{i_{j}}$. All the linear models are trained on the training set included in the benchmark.

## Appendix E Additional Results

In Table 5 we report the AUC scores for the RouterBench dataset across different models and noise levels for the five-shot evaluation. Our conclusions presented in Section 5.1 remain consistent with the results presented in Table 5. However, there is one notable inconsistency: in 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 as 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 a quality of $83.35\%$ over the $83.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 a 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 to 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.

**Table 5: AUC scores in $\%$ for different strategies on RouterBench across model and noise levels for five-shot evaluation.**
|  | Three Models | Five Models | Eleven Models |  |  |  |  |  |  |
| --- | --- | --- | --- | --- | --- | --- | --- | --- | --- |
|  | Low | Med | High | Low | Med | High | Low | Med | High |
| Linear Interp. | $74.210\,281$ | $74.210\,281$ | $74.210\,281$ | $73.823\,577$ | $73.823\,577$ | $73.823\,577$ | $75.160\,194$ | $75.160\,194$ | $75.160\,194$ |
| Routing | $81.495\,843$ | $77.223\,977$ | $76.006\,404$ | $82.425\,209$ | $76.843\,640$ | $75.542\,914$ | $85.341\,982$ | $77.767\,974$ | $76.435\,299$ |
| Cascade (Baseline) | $83.163\,363$ | $78.578\,931$ | $76.885\,932$ | $84.271\,977$ | $76.593\,376$ | $73.918\,097$ | $87.143\,259$ | $78.603\,027$ | $74.942\,672$ |
| Cascade (Ours) | $82.678\,614$ | $78.793\,712$ | $77.003\,991$ | $84.264\,853$ | $77.195\,958$ | $74.297\,096$ | $86.671\,101$ | $78.674\,625$ | $75.075\,952$ |
| Cascade Routing | $83.818\,197$ | $78.920\,287$ | $77.106\,730$ | $85.506\,838$ | $78.822\,596$ | $76.736\,936$ | $88.783\,678$ | $80.881\,557$ | $78.020\,648$ |

## Peer Reviews

confidence: 4
contribution: 2
initial_rating: 6
presentation: 3
questions: 1. How does the computational cost of cascade routing, including the pruning strategy, scale with the number of available models? Have you tested this with significantly larger model sets, such as dozens or hundreds of models? Are there further optimizations that could enhance scalability?

2. The paper acknowledges the limitations of current quality estimation methods. Could you elaborate on potential future directions for improving these estimations? Are there specific features or model architectures that you find promising? Additionally, how does the choice of quality metric, such as accuracy versus user preference, impact the performance of cascade routing?

3. I suggest that the authors provide a more detailed error analysis of the results across different benchmarks. This analysis could offer insights into the types of queries where cascade routing excels or underperforms, guiding future improvements.
soundness: 3
strengths: 1. The paper frames routing and cascading as linear optimization problems, deriving optimal strategies for both. This provides a strong theoretical foundation lacking in prior work, which often relied on heuristics or simplifying assumptions. The theoretical framing allows for provable optimality under certain conditions.

2. Experimental evaluations on RouterBench consistently demonstrate improved performance, yielding a 1-4% increase in AUC across various noise levels and model set sizes, for both routing and cascading tasks.

3. Overall, the paper is well-written, clearly presented, and easy to follow, making it readily accessible to readers.
summary: The paper explores the challenges of efficiently using large language models (LLMs) by evaluating existing model selection strategies: routing and cascading. Routing selects a single model per query, while cascading runs models sequentially until a satisfactory answer is found. However, routing lacks flexibility, and cascading is inefficient.

The paper contributes by deriving optimal strategies for both routing and cascading. Building on this analysis, the authors introduce "cascade routing," which combines the adaptability of routing with the cost-efficiency of cascading. Experiments demonstrate that cascade routing consistently outperforms existing methods across various scenarios, enhancing output quality and reducing computational costs. This approach offers a more unified and efficient solution to the model selection problem.
weaknesses: 1. The core idea is an incremental approach that combines two existing methods, which somewhat limits the paper's novelty.

2. The effectiveness of cascade routing depends on precise quality and cost estimations. The paper acknowledges this limitation, demonstrating that performance gains decrease with less accurate estimates. Although various estimation methods are explored, further research is necessary to enhance their robustness in real-world scenarios.

---

confidence: 4
contribution: 1
initial_rating: 3
presentation: 3
questions: * Given the significant latency overhead of running multiple models sequentially, could you provide a comprehensive analysis of end-to-end response times? How does this compare to simpler approaches like routing-only or ensemble methods?
* For quality estimation of model responses, have you considered more sophisticated evaluation methods beyond perplexity and uncertainty features? For example, using LLM-as-Judge to better evaluate the response's quality?
* The 1-4% accuracy improvement seems modest given the additional complexity and latency. Could you elaborate on specific use cases or scenarios where this trade-off would be clearly beneficial? Perhaps certain domains or applications where even small accuracy gains are highly valuable?
soundness: 1
strengths: * The paper provides rigorous proofs for optimality conditions in both routing and cascading, establishing a solid mathematical framework for model selection.
* The paper combines two previously separate approaches (routing and cascading) into a single coherent framework, showing how they can complement each other.
summary: This paper introduces cascade routing, a framework that unifies and generalizes two common LLM model selection strategies: routing (which selects one model per query) and cascading (which tries progressively larger models). The authors provide theoretical proofs for optimal strategies in both routing and cascading, then use these insights to develop cascade routing. Their approach allows dynamic model selection and sequencing based on both query difficulty and model specialization. Empirical results show 1-4% improvements over baselines across multiple benchmarks. The work's main contribution is providing a theoretical framework that unifies these previously separate approaches to model selection.
weaknesses: * The paper shows only 1-4% accuracy improvements, which may not justify the significant complexity, computation and latency overhead of running multiple models sequentially. The practical value proposition needs stronger motivation.
* There is no discussion of end-to-end inference latency when running multiple models in sequence. While API costs are analyzed, total response time - a critical metric for real-world applications that affect users' experienc - is completely ignored.
* Simply using perplexity and uncertainty features to measure the models' response quality is not fair.
* Additionally, Chain-of-thought methods should be another baseline to compare with the cascading methods.

---

confidence: 4
contribution: 2
initial_rating: 6
presentation: 3
questions: 1. As mentioned in the paper, the proposed method performs poorly when the quality and cost estimates are inaccurate, which raises concerns about its practical application.
 
2. I would like to know how much training data is required for the hyperparameter training of this method compared to existing routing and cascading approaches. I hope the authors can provide some comparative results.
soundness: 3
strengths: 1. This paper presents a theoretical analysis of existing LLM selection strategies and introduces a new cascading strategy that outperforms current methods under specific conditions.
2. The paper is generally well-articulated and easy to understand.
summary: Given the current landscape, where numerous fine-tuned models of varying sizes are tailored to specific tasks, this paper introduces a solution for selecting the most suitable model for a given user query, called Cascade Routing. This approach combines the adaptability of routing with the cost-efficiency of cascading, resulting in improved output quality while reducing computational costs, outperforming existing methods.
Furthermore, the paper offers a theoretical analysis of both existing routing and cascading methods, as well as the proposed Cascade Routing approach. Both theoretical analysis and experimental results consistently demonstrate the superiority of the proposed method over current alternatives.
weaknesses: 1. The paper lacks experimental results for other routing and cascade methods, such as [1] and the existing routing and cascading methods mentioned in the related work. These methods can also reduce the cost of LLMs without compromising response quality.
[1] Large Language Model Cascades with Mixture of Thought Representations for Cost-Efficient Reasoning
 
2. The strength of this paper's approach lies in achieving higher accuracy at the same computational cost, though it comes at the expense of longer runtime. Given that the accuracy improvement ranges are only between 1% to 4%, the authors need to demonstrate that the additional runtime is sufficiently minimal to justify the practicality of this approach.
Specifically, the authors should clearly state the runtime of different methods in the experiments presented in Figure 2 and Table 2 and include the runtime and AUC for the three methods: Linear Interpolation, Routing, and Cascade (Baseline) in Table 3.
 
3. The method proposed in this paper does not change the model order compared to the existing cascade approach, nor does it alter the methods for estimating cost and output quality. It simply expands the search space, resulting in limited contributions.

---

confidence: 3
contribution: 3
initial_rating: 8
presentation: 4
questions: 1. The cascade routing method heavily relies on precise estimates of quality and computational cost for each model. In practical scenarios, these estimates can be noisy, especially since they are typically derived from previous outputs or simple statistical models. When these estimates contain high levels of noise, cascade routing's decision-making becomes less effective. How can this issue be addressed especially for real-time or adaptive applications where quality and cost estimates are challenging to maintain with high accuracy?

2. Cascade routing involves tuning multiple hyperparameters to balance cost, quality, and routing decisions. This includes setting parameters for each model’s cost-quality tradeoff, which adds complexity to the optimization process. Would the optimization be time-consuming and computationally expensive?
soundness: 4
strengths: * Cascade routing effectively combines the strengths of routing and cascading for improved query handling in LLMs.

* The paper provides a solid theoretical basis, with optimal strategies derived for both routing and cascading.

* Experimental results confirm significant performance gains, especially under low-noise settings.
summary: This paper presents cascade routing, a novel model selection strategy for large language models (LLMs) that unifies the strengths of traditional routing and cascading methods. Routing directs queries to a specific model, optimizing for task-specific expertise but lacks flexibility to adjust once selected, while cascading processes queries sequentially through models, which can be inefficient. Cascade routing addresses these limitations by combining adaptability with cost-efficiency, dynamically routing queries across models until a high-quality response is reached. The authors theoretically derive optimal strategies for both routing and cascading, integrating them into the cascade routing framework, which is shown to significantly outperform existing methods in accuracy and cost-effectiveness across diverse benchmarks.
weaknesses: * Cascade routing's effectiveness is limited by the accuracy of quality and cost estimates, which can be noisy.

* Cascade routing requires multiple hyperparameters, making it challenging to tune effectively without extensive data.

---

confidence: 3
contribution: 2
initial_rating: 3
presentation: 2
questions: 1. The minor performance improvement (1%~4%) with the proposed scheme in the paper raises doubts about whether this enhancement is simply due to experimental uncertainty.  For greater conviction, I would advocate for more rigorous experimental designs that demonstrate substantial and statistically significant performance improvements.
2. What criteria should guide the decision on which models are assigned to the same cascade level? Additionally, what is the optimal number of models to be considered at each cascade level within the routing strategy？
3. Does combining cascading and routing hold the key to solving this problem, or would factors like quality estimation approaches be more promising topics for research?
soundness: 2
strengths: 1. Good writing.
2. The research topic is valuable.
3. A formal proof is given.
summary: The widespread applicability of large language models (LLMs) has increased the availability of many fine-tuned models of various sizes targeting specific tasks. An effective strategy can increase overall performance and even offer improvements over a single large monolithic model. Existing model selection strategies, such as routing and cascading, have their drawbacks. Routing commits to an initial model without flexibility, while cascading requires running every model in sequence, which can be inefficient. The paper proposes a novel approach called cascade routing, which combines the adaptability of routing with the cost-efficiency of cascading to improve output quality and reduce computational cost.
weaknesses: 1. The strategies proposed in the paper produced little improvement.
2. More solid experimentation is needed.

Meta-review: The paper studies optimal strategies for routing and cascading in LLMs. Experiments demonstrate that the proposed combined approach outperforms routing or cascading when deployed alone. 

Reviewers appreciated the importance of the questions asked, and applauded the theoretical contribution of formally posing this joint optimization problem. On the negative side, but routing and cascading are existing methods and, as such, blending the two was deemed somewhat incremental. The paper acknowledges that estimation of problem parameters may be difficult, which may further hinder the applicability of the method. Another recurring issue was the small comparative improvement over baselines: the optimization does not seem to yield significant dividends.

The authors addresses several concerns in the rebuttal phase, particularly adding experiments w.r.t. to scaling depth in routing and added more results on benchmarks; these are in the right direction, and more such results would strengthen the paper further. Latency results should be in TTFT, taking into account all possible overheads. The authors are encouraged to actually measure deployments. Performance of competitors should also be reported in a unified fashion.

Decision: Reject