PaperlayerView exact revision on arXiv

Source-linked AI summary

A Unified Approach to Routing and Cascading for LLMs

Jasper Dekoninck, Maximilian Baader, Martin Vechev

arXiv:2410.10347v3cs.CL

TL;DR

Model selection seeks to balance output quality and cost, but routing and cascading impose restrictions and prior approaches leave room for better-supported strategies. The paper derives optimal strategies and proposes cascade routing; it reports stronger benchmark performance, while finding that estimator quality is important to effectiveness.

  • Problem

    Routing commits to one model per query and cascading requires sequential processing through a chain, while model selection aims to balance output quality and cost.

    Source: §1 · p. 1

  • Method

    The paper derives optimal routing and cascading strategies and introduces cascade routing, which routes queries and can reroute until an answer meets a quality threshold.

    Source: §1 · p. 2

  • Results

    Cascade routing consistently outperforms routing and cascading, improving performance by up to 8% on the RouterBench benchmark and by 14% on the SWE-Bench benchmark.

    Source: §1 · p. 2, §7 · p. 9

  • Takeaways & Limitations

    Reliable ex-ante quality estimates are essential for routing, while robust post-hoc response-quality estimates are critical for cascading.

    Source: §1 · p. 2

Abstract

from arXiv · show

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

1. Introduction

Model selection can match model capacity to query needs while balancing output quality and cost, but routing and cascading impose restrictions and lack sufficient theoretical guidance. The paper derives optimal strategies, introduces cascade routing, and reports stronger benchmark performance alongside the importance of quality estimation.

Routing and Cascading

  • Routing fixes one model per query, while cascading processes queries sequentially and stops when an answer meets a quality condition.Routing suits diverse expert tasks, whereas cascading can reserve larger models for more difficult queries.Source: §1 · p. 1

Restrictive Conditions

  • Routing cannot reconsider its initial choice, and cascading cannot skip models in its chain, motivating a less restrictive combined strategy.The paper also identifies limited understanding of optimality and of the conditions under which these strategies are useful.Source: §1 · p. 1

This Work: Cascade Routing

  • The paper frames routing and cascading as cost-budgeted quality maximization, derives optimal strategies, and introduces cascade routing as a theoretically optimal generalization of both.Cascade routing routes a query initially, then reroutes until a model produces an answer of sufficient quality.Source: §1 · p. 2

Importance of Quality Estimation

  • Accurate quality estimates matter: routing needs reliable ex-ante predictions, while cascading needs robust post-hoc evaluation of generated responses.Without robust post-hoc estimation, cascading remains limited even when models of various sizes are available.Source: §1 · p. 2

Results

  • Cascade routing improves performance by up to 8% on the RouterBench benchmark and by 14% on the SWE-Bench benchmark; the new cascading strategy outperforms existing cascades by over 10% in several scenarios.The authors report that cascade routing consistently outperforms both routing and cascading.Source: §1 · p. 2

2. Routing as Linear Optimization

The section formulates routing as a budget-constrained optimization over query-specific model choices. Its optimal strategy selects models by estimated quality-cost tradeoffs and may randomize among tied choices.

Routing

  • Routing strategies map queries to distributions over available models, and each model's quality and cost are estimated for the budgeted optimization.A strategy samples a model from the query-specific distribution.Source: §2 · pp. 2–3

Optimal Routing

  • The optimal router maximizes expected output quality subject to a cost budget, using estimated quality and cost because the underlying functions are unknown in practice.Quality may represent accuracy or user preference, and cost may represent money or latency.Source: §2 · p. 3
  • For each query, the strategy selects a model maximizing estimated quality minus λ times estimated cost, with λ controlling the quality-cost balance for budget B.The optimal strategy can combine the deterministic cheapest- and most-expensive tied choices using γ.Source: §2 · p. 3
  • Unlike prior deterministic routers, the proposed probabilistic strategy can express the optimal routing policy when γ is neither 0 nor 1.Prior work therefore falls back to a near-optimal deterministic strategy in such cases.Source: §2 · p. 3

Example

  • In the two-model example, the router chooses the higher-tradeoff model for math and code queries, but randomizes between models for generic queries.For generic queries, it selects m1 with probability 0.7 and m2 with probability 0.3.Source: §2 · p. 3

3. Cascading as Sequential Routing

The section reframes cascading as sequential routing among supermodels and derives a strategy that maximizes expected output quality under a total cost budget. It also identifies when threshold-based cascading is optimal and when cascading is useful relative to routing.

3. Cascading as Sequential Routing

  • At each step, cascading can be treated as routing among supermodels that include the models already run and possible continuations.The cascade stops if the current supermodel offers the best quality-cost tradeoff; otherwise, it runs the next model.Source: §3 · p. 4
  • The decision must consider every possible continuation, since a later model may perform well even when the immediate next model performs poorly.Choosing only by immediate performance can miss a better quality-cost tradeoff from a later supermodel.Source: §3 · p. 4
  • Supermodel cost is the sum of its models’ costs, while its quality estimate is the expected maximum estimated quality, accounting for uncertainty.The quality estimates are modeled as random variables, and their variance is estimated on validation data.Source: §3 · p. 4
  • Under a total cost budget, Theorem 2 gives an optimal cascading strategy that maximizes expected output quality.The budget applies across the entire cascade, not separately at each step.Source: §3 · p. 4
  • Threshold-based cascading is optimal only under conditions including query-independent costs and qualities, and equality between supermodel and individual-model quality estimates.The corollary states these conditions are necessary and sufficient under minor technical assumptions.Source: §3 · p. 5
  • Cascading is advantageous when post-hoc estimates improve substantially on ex-ante estimates; the proposed strategy uses both kinds of estimates.If the post-hoc improvement is minimal, direct routing is more effective; ex-ante estimates still help assess whether future models may improve performance.Source: §3 · p. 5

4.Cascade Routing as Cascade Generalization

Cascade routing generalizes routing and cascading by allowing each step to choose among all supermodels consistent with the models already run. The section gives an optimal strategy and practical choices for model order and search pruning.

4.Cascade Routing as Cascade Generalization

  • Routing is most useful with accurate ex-ante estimates, while cascading benefits more from accurate post-hoc estimates; cascade routing generalizes both.The framework combines these paradigms rather than restricting model selection to one of them.Source: 4.Cascade Routing as Cascade… · p. 5
  • Under a cost budget, Theorem 3 gives an optimal cascade-routing strategy that selects among all eligible supermodels at each step.Unlike ordinary cascading, cascade routing is not restricted to the predetermined chain of models.Source: 4.Cascade Routing as Cascade… · p. 5
  • The algorithm returns the next model to run or stops when no eligible models remain.Its inputs include models already run, quality and cost estimates, and tradeoff parameters.Source: 4.Cascade Routing as Cascade… · p. 6
  • Cascade routing must dynamically choose model order, then runs the cheapest model in the selected supermodel first because supermodel quality and cost are order-independent.This preserves the option to use more expensive models only when cheaper ones do not suffice.Source: 4.Cascade Routing as Cascade… · p. 6
  • Although the number of possible supermodels can grow exponentially, negative marginal gains let the search prune supersets of a harmful model combination.If adding a model strictly worsens a supermodel’s quality-cost tradeoff for a query, the optimal strategy will not run any supermodel containing that combination.Source: 4.Cascade Routing as Cascade… · p. 6

5. Experimental Evaluation

Across RouterBench and real-world benchmarks, cascade routing generally matches or outperforms the baselines, with larger gains when estimates are accurate and more models are available. The results also show that the relative value of routing and cascading depends on the quality-estimation setting.

5.1. RouterBench

  • RouterBench evaluates strategies with noisy linear quality and cost estimates, varying noise and using three, five, or eleven models; performance is measured by AUC across cost budgets.The benchmark draws questions from seven benchmarks and includes answers from eleven models.Source: §5.1 · pp. 6–7
  • 1%–4% performance gains over baseline strategies, or 13%–80% relative to naive linear interpolation, were reported on RouterBench; gains widened with more models and narrowed under higher noise.The new cascading strategy also outperformed threshold-based cascading by up to 2%.Source: §5.1 · p. 7, Table 1 · p. 7
  • Up to 8% improvement for cascading and up to 12% for routing were reported across varying noise levels, while cascade routing consistently outperformed the baselines.The figure compares AUC differences across noise values; its colors distinguish larger from smaller advantages for cascade routing.Source: §5.1 · p. 7, Figure 2 · p. 7

5. Experimental Evaluation

  • The real-world evaluation distinguishes settings with accurate quality estimates from those without a known accurate estimator.For SWE-Bench, ground-truth tests estimate post-hoc quality; for the math and coding tasks, benchmark origin is a feature for ex-ante estimation.Source: §5.2 · p. 8

5.2. Real-World Benchmarks

  • On SWE-Bench, methods improved over baselines by up to 14%; routing did not beat the trivial baseline, and threshold-based cascading performed poorly despite perfect post-hoc estimation.The binary estimator feedback makes the threshold either admit all models or only correct ones.Source: §5.2 · p. 8
  • On Minerva Math and LiveCodeBench, routing surpassed baseline cascading by 10%, but cascade routing still outperformed all methods.The cascade nearly matched routing despite poor post-hoc estimates, consistent with its use of ex-ante estimates.Source: §5.2 · p. 8
  • With noisy estimates on classification and open-form reasoning tasks, cascade routing matched or outperformed baselines, with gains reaching up to 1.2%.The authors attribute the narrower gains to very noisy quality and cost estimates.Source: §5.2 · p. 8

6. Related Work

Related work studies routing queries to suitable models and cascading from smaller to larger models, with varied quality signals and stopping rules. The paper frames these approaches as instances of thresholding with application-specific quality and cost estimates.

Routing

Cascading

  • Cascades usually defer to larger models when smaller ones lack sufficient confidence, while alternatives use response variance or early stopping within a model.The passage cites Chen et al. (2023; 2024), Ramírez et al. (2024), Varshney & Baral (2022), Madaan et al. (2023), Li et al. (2021), and Schuster et al. (2022).Source: §6 · p. 9
  • Cascade quality-estimation work studies uncertainty and alternative quality measures, while other methods use prior answers or multi-objective metrics to guide stopping.The passage cites Gupta et al. (2024), Jitkrittum et al. (2023a), Xue et al. (2023), and Zhang et al. (2024a).Source: §6 · p. 9
  • The paper views the related approaches as instances of thresholding using application-specific quality and cost estimates.This framing is stated for all works mentioned in the section.Source: §6 · p. 9

7. Conclusion

The conclusion presents theoretical strategies for routing and cascading, then introduces cascade routing as a combined model-selection paradigm. It reports practical gains, especially when quality and cost estimates are good.

7. Conclusion

  • The paper's framework yields theoretically optimal strategies for both routing and cascading.The conclusion also reports that the new cascading strategy significantly outperforms existing approaches.Source: §7 · p. 9
  • Cascade routing combines the benefits of routing and cascading and can significantly outperform its baselines, especially with good quality and cost estimates.The conclusion characterizes cascade routing as a new model-selection paradigm.Source: §7 · p. 9
  • The new cascading strategy significantly outperforms existing cascading approaches, indicating practical gains from the theoretical analysis.Source: §7 · p. 9

Impact Statement

The impact statement connects model-selection strategies with improved performance and lower inference costs, and identifies quality estimation as a future research area.

Impact Statement

  • More accurate quality and cost estimates can improve routing and cascading strategies.Source: Impact Statement · p. 9
  • Cascade routing combines routing and cascading and is described as a more flexible and effective model-selection strategy.Source: Impact Statement · p. 9
  • The statement identifies quality estimation as a critical area for future model-selection research that could lead to further improvements.Source: Impact Statement · p. 9

A. Routing

This section formalizes optimal routing and cascading, including conditions for thresholding and results used in cascade-routing analysis, and reports RouterBench evaluations with noisy quality and cost estimates across scenarios with three, five, or eleven models.

A. Routing

  • For an admissible budget, routing either uses an optimal-quality strategy in S0 within budget or a strategy in Sλ* with cost exactly B and optimal quality.A binary search over λ can efficiently tune the routing hyperparameters; admissibility requires that some strategy meets the budget.Source: A. Routing · pp. 14, 16

B. Cascading

  • Cascading optimizes each step’s routing under a step-specific budget, then chooses those budgets to maximize overall quality under the total cost constraint.The total budget applies to the whole cascade, not each step; queries stopped earlier do not need quality optimization at later steps.Source: B. Cascading · pp. 16–17

B.1. Prior Approximations

  • Thresholding is equivalent to deterministic cascading exactly when alternative quality and cost estimates can be constructed to satisfy the corollary’s conditions.The equivalence concerns strategies making the same decisions on every query.Source: §B.1 · pp. 17–18

C. Cascade Routing

  • The cascade-routing optimality proof reduces to a lemma showing that the expected maximum of model-quality distributions over a set is submodular.The empty set’s maximum is defined as −∞.Source: C. Cascade Routing · p. 18

D.1. Routerbench

  • 5% of RouterBench data (around 2000 samples) tunes hyperparameters, while the remaining 95% evaluates all methods using the same split at every noise level.Source: §D.1 · p. 19
  • Noise levels are specified by standard deviations in Table 3; logistic regression fits noisy quality and cost signals, with quality ranging from 0 to 1 and smallest- versus largest-model average costs of 0.000073 and 0.003281.Source: §D.1 · p. 19, Table 3 · p. 19
  • Three-model scenarios use MIXTRAL-8X7B-CHAT, GPT-3.5-TURBO-1106, and GPT-4-1106-PREVIEW; five-model scenarios add WIZARDLM-13B-V1.2 and CLAUDE-V2, while eleven-model scenarios use every benchmark model.Source: §D.1 · p. 19

D.2. Accurate Quality Estimation

This material specifies the evaluation settings and quality and cost estimators used for accurate- and poor-estimation experiments, then describes how confidence intervals are used to assess differences from baselines.

D.2. Accurate Quality Estimation

  • SWE-Bench uses verified data split into equal training and calibration subsets, while Minerva Math and LiveCodeBench use Algebra-only Minerva data with the same split.The accurate-estimation evaluation also uses SWE-Bench leaderboard models and version 5 of LiveCodeBench.Source: §D.2 · pp. 19–20
  • For accurate estimation, SWE-Bench cost is task-completion time and quality is estimated from query length and repository; other costs use tokens times model size, with benchmark-specific quality features.Linear models predict cost; post-hoc estimates use evaluation quality scores for SWE-Bench and model-answer agreement information for Minerva Math and LiveCodeBench.Source: §D.2 · p. 20

D.3. Poor Quality Estimation

  • Poor-estimation experiments split data for estimator training and validation, use one-shot completion evaluation, and estimate open-form response length from prior cascade responses or training averages.For classification, cost is known from a single-token response; quality features include class probabilities, entropy, agreement, and, for open-form tasks, perplexity and logits.Source: §D.3 · pp. 20–21
  • Separate logistic-regression quality models are trained for each target model and computed-model history using the benchmark training set.This setup creates a distinct estimator for each combination of target model and previously computed models.Source: §D.3 · p. 21

E. Confidence Intervals

  • Bootstrap confidence intervals for AUC differences are used to determine significance; cascade routing is considered significantly better when the difference is positive and its 2σ interval excludes zero.The intervals are reported in Tables 4–6.Source: E. Confidence Intervals · p. 21

F.1. Ablation Study

The ablation compares cascade-routing variants on performance and runtime, while the runtime analysis scales those variants to larger model sets. The standard method preserves performance well, and restricted depth can reduce runtime when its condition holds.

F.1. Ablation Study

  • GREEDY and NO-EXPECT are faster but lose 0.5%–1.3% in low- and medium-noise settings; GREEDY is about twice as fast as NO-EXPECT, while SLOW is nearly an order of magnitude slower for similar performance.The performance gap between GREEDY/NO-EXPECT and the standard variant is much smaller at high noise, where estimated quality varies little.Source: §F.1 · p. 21, Table 7 · p. 22
  • Use the standard variant when preserving performance matters; GREEDY is the runtime-focused option, while SLOW and NO-EXPECT are not recommended.The reported recommendation follows from GREEDY's runtime advantage and the other variants' performance or runtime drawbacks.Source: §F.1 · pp. 21–22

F.2. Runtime Analysis

  • With 80 models, GREEDY remains computationally cheap, while standard cascade routing handles up to 40 models within 1 second and MAX-DEPTH up to 80.SLOW becomes too expensive below 20 models; NO-EXPECT is slower than MAX-DEPTH at 80 models.Source: §F.2 · p. 22, Figure 3 · p. 22
  • MAX-DEPTH reduces runtime without reducing performance when the optimal cascade depth is at most 3 models.The analysis uses random quality and cost estimates, with 100 data points per model count.Source: §F.2 · p. 22

G. Detailed Results

The section describes quality-cost curves for several benchmarks, formed by varying the cost threshold and plotting the resulting accuracy and cost.

G. Detailed Results

  • Varying cost threshold λ produces curves of the resulting accuracy and cost for several benchmarks.The section also points to benchmark-specific AUC values for classification and open-form reasoning.Source: G. Detailed Results · p. 23

H. Additional Results

The additional results examine five-shot RouterBench outcomes and a discrepancy in the low-noise, eleven-model cascading setting. They identify hyperparameter tuning and model-selection restrictions as explanations for observed differences.

H. Additional Results

  • In the three-model low-noise scenario, resetting cascading-strategy hyperparameters to their highest-quality settings once quality starts falling as cost rises yields 83.35% quality, versus 83.17% for the threshold-based baseline cascade.Source: H. Additional Results · p. 23
  • In the low-noise, eleven-model case, the expected maximum quality estimate can exceed the last computed model's quality, producing suboptimal choices under the cascade's selection restriction.Allowing both cascade methods to select the model with the highest quality estimate restores the proposed cascade's advantage over the baseline; cascade routing does not impose this restriction.Source: H. Additional Results · p. 23

Related papers

Loading 2410.10347v3…