A Unified Approach to Routing and Cascading for LLMs

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.

Can you clarify how $\gamma$ is determined and whether step-specific $\gamma_j$ factors might improve performance?
First, 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.

The 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.

Since 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.

Is the cost of quality estimation factored in when evaluating the AUC score?
In 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.

Did you include baselines based on adaptive thresholds?
Yes, 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.

We 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.

Can you add some illustrative examples of cascade routing?
Yes, 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.

Does cascade routing only look at the supermodels $M_{1:j-1}, \dots, M_{1:k}$?
No, 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.

Can you clarify what you mean in the model ordering paragraph?
This 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.

Could you add a discussion regarding robustness of the method to estimation errors?
Yes, 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.

Does restricting the maximum depth of cascade routing significantly affect performance?
The 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.

We thank the reviewer for their detailed review. Below, we address their remaining questions.

Why is the expectation of the maximum but not just $q_i$?
There 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.

The 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.

Did you include the latest state-of-the-art models?
Yes, 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.

How does the latency of cascade routing compare with the baselines?
Generally, 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.

Can you clarify how you estimated quality on the RouterBench benchmark?
As 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.

Is one of your main claims that the routing strategy is better than prior work?
No, 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.

Can you provide performance-cost tradeoff curves?
Yes, 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.

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.

Could you formulate cascade routing as a bi-level optimization problem?
Yes, 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.

Why have you not included the baseline Learning How Hard to Think: Input-Adaptive Allocation of LM Computation?
The 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. Our 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.

Does the optimality proof require good quality estimation?
No, 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. We 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.

What about the increased inference and latency costs?
Cascade routing does not inherently increase inference costs. On the contrary, our results indicate that, under identical budget constraints, cascade routing achieves higher accuracy. More 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.

What are the requirements for the training data?
The 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.

Could you provide supplementary materials?
Contrary 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.

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.

What is the role of the superscript (j) in Theorem 2?
The 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.

What is the role of the variance for quality estimation?
Quality 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.

More 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.

How are hyperparameters selected?
Almost 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.

Can you define the extremes of quality strategies instead of cost strategies?
Both 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.

How exactly are you pruning the search space?
We 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.

Can you add an algorithm block explaining cascade routing?
Yes, we will incorporate the recommended algorithm block. Additionally, we will provide an illustrative example.

What is the exit criterion?
The 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$.

How does your approach select the next supermodel?
Cascade 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$.