A Unified Approach to Routing and Cascading for LLMs

Authors: Jasper Dekoninck, Maximilian Baader, Martin Vechev
Primary area: foundation or frontier models, including LLMs
Keywords: large language models, routing, model evaluation

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.

Decision: reject
Reviewer scores: 6, 3, 6, 8, 3

Reviews and discussion:
<thread>
creation date:
1729858253417

thread_type:
official_review

<thread_object>
creator: reviewer_txch

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

strengths:
1. Good writing.
2. The research topic is valuable.
3. A formal proof is given.

weaknesses:
1. The strategies proposed in the paper produced little improvement.
2. More solid experimentation is needed.

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?
</content>
</thread_object>

</thread>
<thread>
creation date:
1730535863514

thread_type:
official_review

<thread_object>
creator: reviewer_pgv6

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

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.

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.

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?
</content>
</thread_object>

</thread>
<thread>
creation date:
1730551337789

thread_type:
official_review

<thread_object>
creator: reviewer_vrky

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

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.

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.

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.
</content>
</thread_object>

</thread>
<thread>
creation date:
1730574213767

thread_type:
official_review

<thread_object>
creator: reviewer_fzmq

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

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.

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.

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?
</content>
</thread_object>

</thread>
<thread>
creation date:
1730644941382

thread_type:
official_review

<thread_object>
creator: reviewer_npnb

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

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.

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.

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.
</content>
</thread_object>

</thread>
<thread>
creation date:
1732229685281

thread_type:
official_comment

<thread_object>
creator: authors

<content>
comment:
$\newcommand{R}{\textcolor{green}{tXch}}$
$\newcommand{S}{\textcolor{blue}{pgV6}}$
$\newcommand{T}{\textcolor{purple}{VrKy}}$
$\newcommand{U}{\textcolor{yellow}{fzmQ}}$
$\newcommand{V}{\textcolor{orange}{nPNB}}$

We thank the reviewers for their high-quality reviews and questions. We are particularly happy to read they find our paper well-written ($\V, \T, \R$), appreciate our solid theoretical basis ($\R,\S,\T,\U,\V$), and acknowledge our consistent performance gains ($\S,\V$). We identified two common questions between the reviewers and will also include a comprehensive overview of the changes made to the paper in response to the reviews.

**Q1. Does the paper provide any contribution beyond the introduction of cascade routing? ($\T,\V,\R$)**     
Yes, while cascade routing unifies routing and cascading strategies, the paper’s contributions extend far beyond this specific algorithm. Here, we elaborate on the most significant contributions:
- **A Theoretical Framework with Rigorous Guarantees**: One of the key contributions of our paper is the derivation of optimal strategies for both routing and cascading. This approach offers provable guarantees for the performance of these strategies, addressing a fundamental gap in prior work, which relied on heuristics or empirical methods without rigorous foundations.
- **Cascade Routing**: Cascade routing is not just a straightforward combination of routing and cascading strategies; it is a theoretically informed algorithm explicitly designed to balance cost-efficiency and adaptability. Without this theoretical understanding of the problem, it would have been impossible to propose an algorithm that effectively combines both routing and cascading.
- **No Further Gains from Algorithmic Improvements:** A particularly impactful conclusion from our work is provided by our theoretical analysis: by proving the optimality of the proposed algorithms, we can be certain that no (significant) further gains can be made by proposing new algorithms. Therefore, the research community for routing and cascading can now focus on improving quality and cost estimation methods, rather than developing new routing and/or cascading algorithms.

**Q2. Is the 1-4% accuracy improvement modest given the additional complexity and latency? ($\U, \T, \R$)**  
We argue that the reported 1-4% improvement is not modest when viewed in the broader context of the field. Several points support this:
- **Alignment with field benchmarks**: Improvements in routing and cascading algorithms have historically fallen within a similar range (Gupta et al. 2024, Ramirez et al. 2024, Jang et al. 2023, Nguyen et al. 2024). The consistency of our results across benchmarks shows that we improve upon prior work by as much as they improve over their own baselines, reaffirming the robustness of our contributions.
- **Practical implications of theoretical optimality**: Our results are not just empirical but grounded in theoretical guarantees. This ensures that any observed improvements are provably the best achievable under the current framework, making the method inherently more reliable and transferable to other applications.
- **Significance in specific domains**: In domains where the marginal value of improvement is high (e.g., regulatory compliance, critical automation systems), these consistent accuracy gains justify the additional complexity. Importantly, the consistency of our improvements ensures reliability.

**We made the following changes to our paper:**
- **Confidence Intervals**: We have added a discussion of confidence intervals in Appendix E. In Tables 1 and 2, we have underlined the numbers that are not statistically significantly lower than the highest value for clarity.
- **Further Runtime Analysis**: Additional experiments analyzing the runtimes of different cascade routing variants on random data are included in Appendix F. These experiments confirm that the "Slow" variant does not scale well, while the "Greedy" variant remains highly efficient for up to 80 models.
- **Latency**: The latencies associated with each method in Section 5.2 are analyzed in Appendix G. Our findings show that cascade routing is, on average, no more than 0.6 seconds slower than direct routing.
- **Benchmark-Specific Results**: Appendix H provides benchmark-specific AUC scores for the experiment discussed in Section 5.2.
</content>
</thread_object>

</thread>
<thread>
creation date:
1733308091487

thread_type:
official_comment

<thread_object>
creator: authors

<content>
comment:
We sincerely thank all five reviewers for their constructive comments and questions, which have significantly helped us improve our work. We are particularly encouraged by the reviewers' recognition of our paper's strengths, as summarized below:
$\newcommand{R}{\textcolor{green}{tXch}}$
$\newcommand{S}{\textcolor{blue}{pgV6}}$
$\newcommand{T}{\textcolor{purple}{VrKy}}$
$\newcommand{U}{\textcolor{black}{fzmQ}}$
$\newcommand{V}{\textcolor{orange}{nPNB}}$

**Solid Theoretical Basis**
- The presented framework provides a strong theoretical foundation to routing and cascading which was lacking prior work ($\V,\U,\T,\S,\R$).
- Cascade routing effectively combines routing and cascading for improved query handling ($\S,\U,\T$). 

**Good Presentation**
- The paper is well written, clearly presented, and easy to understand ($\V,\T,\R$).

**Consistent Performance Gains**
- Our experimental evaluation shows that cascade routing demonstrates consistent performance improvements over routing and cascading ($\V,\S$). 

We acknowledge that our initial submission had areas for improvement. We believe to have addressed the following main concerns by the reviewers:
- **Small Performance Gains**: We clarified that the gains were statistically significant, and that our theoretical optimality guarantees show that algorithmic improvements cannot significantly improve upon the presented method. This latter point was appreciated by Reviewer $\T$ who increased their score.
- **Novelty Cascade Routing**: We clarified that our novel reinterpretation of routing and cascading was essential in enabling the straightforward proposal and presentation of the cascade routing algorithm. Furthermore, the new theoretical foundation underlying routing and cascading was also required for the development of cascade routing.

In response to the reviewers’ thorough reviews, we have provided the following additional information and experiments which we incorporated in the revision of the paper:

- **Confidence Intervals**: We now include confidence intervals, indicating that our results are statistically significant.
- **Runtime Analysis**: We extended our ablation study, confirming our initial results regarding runtime improvements in the presented algorithm.
- **Latency**: We show that total latency is only increased slightly by cascade routing, and is generally lower than cascading.

We additionally clarified the following significant points to individual reviewers:
- **Applications**: While cascading approaches are inapplicable to user-oriented applications where time-to-first token is important, there are many applications that go beyond this use-case for LLMs, especially regarding high-stakes decision making and large-scale operations.
- **Hyperparameter Optimization is Cheap**: Hyperparameter optimization generally only takes a couple of hours on a couple of CPUs.

Once again, we deeply appreciate the valuable feedback and guidance provided by the reviewers.

Best regards,  
The authors
</content>
</thread_object>

</thread>


Metareview:
metareview:
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.