Regret Bounds for Sequential Model Cascades: An Optimal-Stopping Formulation

Executive summary for technical leaders

A model cascade is the cheapest reliability lever in production AI: run a small model first, and pay for a large one only when the small one is unsure. The published record shows the lever is powerful. FrugalGPT reports matching GPT-4 quality with up to a 98 percent cost reduction on some tasks while sending only about one query in six to the expensive model.^[1] RouteLLM reports cutting cost by more than half while retaining roughly 95 percent of GPT-4 quality.^[2] Hybrid LLM reports up to 40 percent fewer calls to the large model with no drop in response quality.^[3] The mechanism is old: the attentional cascade that made real-time face detection possible in 2001 used a two-feature first stage to reject roughly half of all windows before any expensive computation ran.^[6]

Almost every one of these systems makes the escalate-or-answer decision the same way: it thresholds a confidence score. If the cheap model's confidence clears a fixed bar, accept its answer; otherwise escalate. This paper asks whether that rule is right, and what happens when the thresholds must be learned from live traffic. The answer has three parts. First, the cascade decision is an optimal stopping problem, and its optimal policy is not a confidence threshold but a reservation value: stop when the current estimated error drops below the expected cost of running the rest of the cascade. Second, a fixed confidence threshold matches that optimum only in a degenerate case, and otherwise leaves a quantifiable amount of money on the table, an approximation gap that grows with the escalation cost and with how correlated the models' errors are. Third, learning the thresholds online is cheap, its regret shrinks at a predictable rate, but that learning closes only the gap to the best threshold, never the gap between the best threshold and the true optimum.

flowchart LR
  Q["Query x"] --> M1["Run M1 (cost c1)"]
  M1 --> S1{"rho_1 within reservation?"}
  S1 -- "yes: stop" --> A1["Return a1"]
  S1 -- "no: escalate" --> M2["Run M2 (cost c2)"]
  M2 --> S2{"rho_2 within reservation?"}
  S2 -- "yes: stop" --> A2["Return a2"]
  S2 -- "no: escalate" --> M3["Run M3 (cost c3)"]
  M3 --> A3["Return a3"]

The practical upshot is a short checklist. Set the escalation rule from the continuation value, not from a raw confidence score. Calibrate the score before thresholding it, because a threshold on a miscalibrated signal is a threshold on the wrong axis.^[25] Measure the cross-model error correlation, because it sets the floor on how much a cascade can save. When that correlation is high, stop tuning the threshold and invest in a query-dependent router instead, because no threshold will reach the optimum. And when learning statistics from live traffic, budget an explicit exploration phase rather than adapting greedily. The rest of the paper makes each of these precise.

None of this argues against cascades; the point is to run them at their optimum rather than near it. The reservation-value rule is not more expensive to deploy than a threshold, it is the same one-comparison-per-stage decision with the comparison set correctly, and its first improvement over a global threshold, using the correct per-stage reservation risks derived from the downstream costs, is essentially free. The more expensive improvement, a query-dependent router that estimates the continuation value per query, is worth building only when the workload has high, query-dependent error correlation, and the analysis here tells you how to detect that case (measure the correlation) and how much it is worth (the approximation gap). The contribution is thus both a piece of theory, the identification of the cascade decision with optimal stopping and the derivation of its optimal rule and regret, and a decision procedure for practitioners, a short ordered checklist that says what to measure, in what order, and when to stop tuning and start building.

1. Introduction

The dominant cost structure of applied language modeling is heterogeneous: the price of a token differs by up to two orders of magnitude across the available APIs, and the quality difference between the cheapest and the most capable model is large on hard queries and negligible on easy ones.^[1] That combination is what makes cascades pay. If a cheap model answers the easy majority of queries correctly, and an expensive model is reserved for the hard minority, the blended cost can approach the cheap model's while the blended quality approaches the expensive model's. The entire art is the decision rule that separates easy from hard on a per-query basis, without knowing the ground truth, at the moment of the query.

1.1 The escalate-or-answer problem is everywhere

The same decision appears under many names. In classical computer vision it was the attentional cascade, a sequence of boosted classifiers that reject easy negatives early and pass only ambiguous windows to expensive stages.^[6] In budgeted learning it was sequential classification under a cost constraint, choosing sensors or features one at a time and deciding when the accumulated evidence justifies a decision.^[24] In modern LLM serving it is the model cascade and its close cousin the router. FrugalGPT learns which cheap models suffice for which queries and escalates the rest, matching GPT-4 with up to 98 percent lower cost or beating it by 4 percent at equal cost.^[1] RouteLLM learns a router from human preference data and reports more than a two-fold cost reduction at 95 percent of GPT-4 quality.^[2] Hybrid LLM routes on predicted difficulty and cuts large-model calls by up to 40 percent with no quality loss.^[3] A cascade that uses the cheap model's own answer consistency as its difficulty signal matches GPT-4 at roughly 40 percent of its cost across six reasoning benchmarks.^[4]

Even single-model test-time compute is a cascade in disguise. Extending a chain of thought,^[27] sampling more candidates, or running a verifier all spend more compute for a chance at a better answer, and the compute-optimal policy is to spend that budget adaptively per prompt: Snell and colleagues report that allocating test-time compute optimally is more than four times more efficient than a best-of-N baseline and can let a small model outperform one fourteen times larger on some problems.^[5] Adaptive per-prompt allocation is a stopping rule over compute, which is the object this paper studies.

The economics that make the decision matter are worth stating in numbers. The price gap between the cheapest and the most capable model on a task is large, up to two orders of magnitude per token across the available APIs, and it is not matched by a two-order quality gap on most queries.^[1] On easy queries the cheap and expensive models produce the same answer, so every unit spent on the expensive model is wasted; on hard queries the expensive model is worth its price. The entire value of a cascade is in spending the expensive model's budget only on the hard minority, and the entire risk is in misjudging which queries are hard from a signal available before the ground truth is. Because the hard fraction is often small, the blended cost can approach the cheap model's while the blended quality approaches the expensive model's, which is why reported savings are so large: FrugalGPT sends only 16.6 percent of HEADLINES queries to GPT-4 and still matches or beats it, because on that workload the cheap model already produces GPT-4-identical answers on 80 percent of queries.^[1]

That observation is the seed of a theme this paper develops formally: the achievable saving is a property of the workload, not only of the models. Two workloads with the same two models can yield very different savings depending on how often the models fail on the same queries. When failures are idiosyncratic to the cheap model, escalation rescues many queries cheaply; when failures are shared, escalation buys little because the expensive model also fails on the hard set. Section 6 turns this into a benefit-rate identity and an oracle bound on the escalation fraction. Before that, Sections 3 and 4 build the stopping model and derive its optimal policy, and Section 5 shows why the fixed-threshold rule most systems use is not that policy.

1.2 Cascade decisions are stopping decisions

The prevailing framing treats deferral as a classification problem: learn a rejector that decides, per query, whether to abstain and pass the query on. This is the lens of learning with a reject option,^[21][22] selective classification,^[23] and learning to defer to an expert.^[29] That lens is productive, but it hides two features that dominate the cascade problem. The first is sequential cost: you pay for every model you run, the payment is irreversible, and the decision at each stage is conditioned on everything seen so far. The second is option value: escalating is worth taking not only for the answer the next model gives but for the further option it preserves to escalate again. A one-shot rejector prices neither. An optimal stopping formulation prices both, because stopping theory is precisely the mathematics of deciding, under uncertainty and sequential cost, when the option to continue is no longer worth its price.^[11][12]

1.3 The gap in prior work

Three bodies of work touch the cascade problem without closing it. The deferral-as-classification literature characterizes the optimal one-shot rejector but abstracts away sequential cost and option value.^[22][23] The learned-router literature builds strong systems (FrugalGPT, RouteLLM, Hybrid LLM) and reports impressive cost curves, but treats the routing rule as a black-box classifier to be fit, not as the solution of a stopping problem with a known optimal form.^[1][2][3] Closest to our concern, Jitkrittum and colleagues characterize the Bayes-optimal deferral rule for a cascade and show empirically that confidence-based deferral fails when the downstream model's errors are correlated with the current model's, but they do not connect the rule to the reservation-value theory of optimal stopping, nor analyze the regret of learning it online.^[7] On the theory side, optimal stopping and the Pandora's box problem give the exact optimal policy for sequential search under inspection cost,^[8][9] and the bandit literature gives regret bounds for learning unknown distributions,^[15][16] but these have not been brought to bear on the model-cascade decision as such. This paper is the bridge. It imports the reservation-value structure from the search-theory side to say what the optimal cascade rule is, imports the regret machinery from the bandit side to say how fast that rule can be learned, and connects both to the measured behavior of deployed cascades to say which regime a given system is in. The synthesis is the contribution: each ingredient is known, but their combination answers a question none answers alone, namely whether the fixed thresholds in production are optimal (no), how far from optimal they are (the gap of Section 5), and whether learning fixes it (only the estimation part, Section 7).

1.4 Contributions

This paper makes four contributions, each a derivation carried out in full.

1. A stopping formulation and its optimal policy. We cast the cost-aware cascade as a finite-horizon optimal stopping problem (Section 3), derive its Bellman recursion, and show the optimal policy is a reservation-value rule: stop when current estimated error falls below the continuation value (Section 4). For the keep-best variant we identify the problem as Weitzman's Pandora's box and inherit its closed-form reservation value.^[8]
2. A proof that fixed confidence thresholds are suboptimal. We show a fixed confidence threshold equals the optimal policy if and only if the continuation value is constant across queries, and otherwise incurs a strictly positive approximation gap that we compute in closed form for a two-model cascade (Section 5). This turns the empirical finding of Jitkrittum and colleagues into a quantitative statement.^[7]
3. An error-correlation penalty. We derive the benefit rate of a cascade, the probability the cheap model errs and the expensive one does not, as a function of the two models' accuracies and their error correlation, and a matching oracle lower bound on the escalation fraction needed to hit a target error (Section 6). This explains why cascades save far more on some tasks than others at equal model quality.
4. Online regret bounds. We bound the regret of learning the thresholds from a stream of queries: order T to the two-thirds power in general and order square-root of T under a margin condition, matching the order of known online-Pandora guarantees,^[19][20] and we prove this estimation regret is orthogonal to the approximation gap, so more data never closes it (Section 7).

The remainder proceeds as follows. Section 2 reviews optimal stopping, Pandora's box, sequential testing, bandit regret, and the cascade and deferral literature. Section 3 gives the model. Section 4 derives the optimal policy and its reservation-value structure. Section 5 proves the suboptimality of fixed thresholds. Section 6 develops the correlation penalty. Section 7 gives the online regret analysis. Sections 8 through 11 discuss interpretation, threats to validity, practical implications, and open problems.

1.5 Scope, method, and non-goals

This is a theory and synthesis paper. We prove statements about a stated model and we synthesize published measurements against them; we run no experiments and report none of our own. Every empirical number is attributed with an inline citation in the sentence that uses it, and the load-bearing numbers (the FrugalGPT cost reduction and escalation fraction, the RouteLLM and Hybrid LLM and mixture-of-thoughts cost figures, the Snell test-time-compute results) are cross-checked against a second independent source. Every figure is either an analytical model derived from our equations, labeled as such in its caption with its illustrative parameters stated, or a table of cited results with the source named. Our non-goals are equally explicit: we do not claim a new production system, we do not benchmark models, and we do not settle whether any particular confidence signal is well calibrated, though we note that calibration is a precondition for thresholding to make sense at all.^[25][26]

2. Background and related work

2.1 Optimal stopping and dynamic programming

Optimal stopping asks when to halt a sequential process to optimize an expected payoff that trades a reward for the cost of continuing. The classical theory, developed by Chow, Robbins, and Siegmund and later given its analytic form by Peskir and Shiryaev, solves finite-horizon problems by backward induction: the value of being in a state is the better of stopping now and continuing one more step, and the optimal rule stops wherever the immediate payoff dominates the expected continuation value.^[11][12] The machinery is dynamic programming,^[10] and its output is a partition of the state space into a stopping region and a continuation region separated by a free boundary. A cascade has exactly this structure with a finite horizon of K models, which is why the theory applies without modification.

It is worth stating the optimality principle the theory rests on, because we invoke it repeatedly. The value function defined by backward induction is optimal by a verification argument: any policy achieves at least the value of stopping when the immediate payoff beats the continuation value and continuing otherwise, and the backward-induction value is exactly the fixed point of that comparison, so no policy can do better. In continuous or infinite-horizon settings the same object is the Snell envelope, the smallest supermartingale dominating the payoff process, and the optimal stopping time is the first moment the envelope meets the payoff. For a finite cascade the envelope collapses to the K-step recursion, and the free boundary is the reservation value at each stage. The subtlety that matters for us is that the continuation value is an expectation over the not-yet-observed signal of the next model, so it is a forward-looking quantity that a rule reading only the current signal cannot contain. This is the formal seed of every suboptimality result in Section 5: a fixed threshold is a rule that refuses to look forward, and the theory says looking forward is exactly what the optimum requires.

2.2 Pandora's box and reservation values

Weitzman's 1979 solution to sequential search with inspection costs is the result we lean on most.^[8] An agent faces boxes, each with a known inspection cost and an unknown reward drawn from a known distribution. Opening a box pays its cost and reveals its reward; the agent may stop at any time and keep the best reward seen. Weitzman proved the optimal policy assigns each box a reservation value, the reward level that makes inspecting it a break-even proposition, defined by the indifference equation stating that the expected gain from opening the box above its reservation value equals its inspection cost. The optimal policy opens boxes in decreasing order of reservation value and stops as soon as the best reward in hand exceeds the reservation value of the next box. The rule is remarkable because it is an index policy: each box's reservation value depends only on that box, not on the others, yet the greedy index rule is globally optimal. Doval later studied the variant in which the agent may accept a box without inspecting it, showing the optimal order and stopping rule change; this is the right model when a downstream model is assumed better without being run.^[9]

The reservation value earns its name through a one-step indifference argument that we reuse in Section 4, so it helps to see it now. Consider a single box with reward $V$ and cost $c$, and suppose you hold an outside option worth $z$. Opening the box costs $c$ and then lets you take the better of $V$ and $z$, for a net value $-c+\mathbb{E}[\max (V,z)]$, while not opening keeps $z$. Opening is worthwhile exactly when $\mathbb{E}[\max (V,z)]-z\ge c$, and since $\max (V,z)-z=(V-z{)}^{+}$, the break-even outside option is the $z$ solving $\mathbb{E}[(V-z{)}^{+}]=c$, which is Weitzman's reservation value. The left side decreases in $z$ from $\mathbb{E}[V]$ toward zero, so the equation has a unique root, and the root depends only on the box's own distribution and cost, which is what makes the rule an index. The deep fact Weitzman proved is that this per-box index, computed in isolation, is globally optimal: opening in decreasing index order and stopping when the best reward in hand exceeds the next index is optimal even though each index ignored the other boxes. That decoupling is what we inherit for the cascade.

2.3 Sequential testing and the SPRT

When the signal at each stage is evidence accumulating toward a decision, the relevant optimum is Wald's sequential probability ratio test, proven by Wald and Wolfowitz to minimize the expected number of samples for fixed error probabilities.^[13] The SPRT accumulates a log-likelihood ratio and stops when it crosses an upper or lower boundary. The connection to cascades is direct: if each model contributes evidence about whether the current answer is correct, the cost-optimal stopping rule is a boundary on accumulated evidence, and the reservation-value rule specializes to a likelihood-ratio threshold. We use this to interpret confidence signals that are themselves aggregates, for example the answer-consistency signal of a self-sampling cascade.^[4]

The SPRT connection also carries a caution that the cascade inherits. Wald's boundaries are optimal only when the per-observation evidence is genuinely informative and the model of the two hypotheses is correct; if the likelihood ratio is miscalibrated, the boundary is placed at the wrong level and the test either stops too early (accepting wrong answers) or too late (wasting samples). Translated to the cascade, a consistency signal that is not calibrated to the actual probability of correctness produces a reservation boundary at the wrong error level, which is the same calibration precondition we flag throughout. The SPRT view is useful precisely because it makes the calibration requirement concrete: the number of agreeing samples is only a valid stopping statistic if agreement rate maps monotonically to correctness probability, which is an empirical property of the model and the task, not a given.

2.4 Bandits, indices, and regret

When the distributions governing rewards and costs are unknown, learning them while acting is the multi-armed bandit problem. Gittins showed that for a broad class of such problems the optimal policy is again an index policy, the dynamic allocation index now called the Gittins index.^[14] For the regret formulation, Lai and Robbins established that no policy can do better than logarithmic regret in the number of plays, and Auer, Cesa-Bianchi, and Fischer gave the upper confidence bound algorithm that achieves this logarithmic regret uniformly over time with a simple rule.^[17][16] The modern reference for the full range of regret analyses, which we use for the online part of this paper, is Lattimore and Szepesvari.^[15] Two recent works learn the Pandora's box problem itself online: Gergatsouli and Tzamos give low-regret algorithms when the value realizations arrive online,^[19] and Gatmiry, Kesselheim, Singla, and Wang study Pandora's box and the prophet inequality in the bandit model where the distributions must be learned.^[20] Their rates set the benchmark our threshold-learning bounds match in order.

Two ideas from this literature carry directly into Section 7. The first is the definition of regret as cumulative excess cost against the best fixed action in hindsight, which turns a learning problem into an optimization problem with a measurable target. The second is the exploration-exploitation tradeoff and its resolution by either committing after a fixed exploration budget (explore-then-commit) or maintaining optimistic estimates and acting greedily on them (upper confidence bounds). Explore-then-commit is simpler to analyze and yields a rate of order T to the two-thirds power in the general Lipschitz case; upper confidence bounds are more data-efficient and reach the order square-root of T minimax rate, or the logarithmic rate in the parametric case that Lai and Robbins proved optimal.^[17][16] We lead with explore-then-commit in the cascade because the natural exploration action, running the full cascade to observe every model's loss, has a clean cost and directly reveals the quantities the reservation rule needs, so the structured estimator beats a generic bandit that treats each threshold vector as an opaque arm. The lower bounds tell us where the ceiling is: no learner can beat square-root of T without extra structure, so an algorithm achieving it under a margin condition is order-optimal.

2.5 Cascades, deferral, and routing

The cascade idea is old and recurrent. Viola and Jones made it famous for detection.^[6] Trapeznikov and Saligrama formalized sequential classification under a budget.^[24] Chen, Zaharia, and Zou first brought API cascades to machine-learning services in FrugalML and then to language models in FrugalGPT.^[28][1] The deferral rule itself has been studied as learning with rejection,^[21][22] selective classification with its risk-coverage tradeoff,^[23][30] and learning to defer to an expert.^[29] For LLMs specifically, RouteLLM and Hybrid LLM learn routers,^[2][3] and the mixture-of-thoughts cascade uses answer consistency as the difficulty signal.^[4] The work nearest our central claim is Jitkrittum and colleagues, who characterize when confidence deferral suffices and show it fails under downstream error correlation.^[7] We recover their qualitative finding as a corollary of a reservation-value analysis and extend it with a closed-form gap and an online regret theory.

It is worth separating two decisions the literature sometimes conflates, because the stopping view keeps them distinct. Routing decides, before running any model, which model to send a query to, often a one-shot choice by a classifier that never runs the cheap model at all. Cascading runs the cheap model first and decides after seeing its output whether to escalate. The two differ in what signal is available: a router decides from the query alone, while a cascade decides from the query plus the cheap model's answer and confidence, which is strictly more information.^[3][2] The stopping formulation covers both, a router is the degenerate cascade that commits at stage zero using only the query, and a cascade uses the richer post-hoc signal, and it explains a common empirical observation: cascades that read the cheap model's answer often outperform routers that do not, because the answer and its confidence are informative about difficulty in ways the raw query is not.^[4] The cost of the cascade's extra information is that it always pays for the cheap model, even on queries it will escalate, which the reservation rule accounts for through the cumulative-cost term. Whether to route or cascade is itself a decision the framework prices: cascade when the cheap model's signal is worth its cost, route when the query alone predicts difficulty well enough to skip the cheap run.

2.6 Confidence signals and their reliability

Every cascade rule reads a confidence signal, and the rule can be no better than the signal it reads. Modern neural networks are systematically miscalibrated, typically overconfident, and require post-hoc correction to make their scores behave like probabilities.^[25] Language models can, when prompted well, estimate the probability that their own answer is correct, and this self-evaluation is reasonably calibrated by default but is damaged by preference tuning and partially restored by temperature adjustment.^[26] We treat the signal as a given primitive whose conditional error function is what the reservation rule thresholds; the calibration literature is what determines whether that function is monotone in the raw score, a condition our threshold results assume and practitioners must ensure.

2.7 What the stopping view adds over adjacent formulations

It helps to state precisely what the optimal stopping formulation contributes over the three adjacent framings, because each captures part of the problem. The classification-with-rejection framing models the decision to abstain but treats it as one-shot: it prices the current model's error and the cost of abstaining, but not the sequential cost of running several models nor the option value of preserving the ability to escalate again.^[21][22] The selective-prediction framing gives the risk-coverage tradeoff, how much accuracy improves as you abstain on more queries, but it is a single-model notion and does not model where the abstained queries go or what they cost.^[23] The learned-router framing is operationally closest, but it fits the routing decision as a supervised classification problem against a heuristic label (did the expensive model win) rather than deriving the decision from a cost objective, so it cannot say when its label is the right target or how far its rule is from optimal.^[2][3] The stopping view supplies exactly the missing pieces: it prices the sequential cost through the cumulative-cost term, it prices the option value through the continuation value, and it derives the optimal decision as the reservation comparison, which lets us both characterize the optimum and measure any rule's distance from it. Nothing in the stopping view contradicts the other framings; it subsumes them as special cases (a one-model cascade is selective prediction, a cascade with a supervised router is a learned approximation to the reservation rule) and adds the sequential-cost structure they omit.

The one framing the stopping view does not subsume is the fully general reinforcement-learning treatment of an agent that interleaves model calls with external actions. A cascade is a restricted control problem, two actions per stage and a finite horizon, and that restriction is what buys the closed-form reservation rule. A general agent whose escalation changes the environment (for example, an agent that calls a tool whose result changes the query) needs the full apparatus of sequential decision-making, and the reservation rule is then only a local approximation valid when the escalation does not change the state. We keep to the restricted problem deliberately, because it is the one that admits sharp results and it covers the large and growing class of cascade and router deployments.

3. The cascade stopping model

3.1 Formal setup

Fix an ordered cascade of K models $M_1,\dots ,M_K$ with per-query costs $c_1\le c_2\le \cdots \le c_K$ measured in whatever unit the operator pays in (tokens, dollars, or latency). A query $x$ is drawn from a distribution $\mathcal{D}$. Running model i produces an answer $a_i$, incurs a loss ${\ell }_i\in [0,1]$ (for instance the zero-one error of $a_i$ against the unknown ground truth), and emits a confidence signal $s_i\in \mathcal{S}$. The signal is an observable proxy for the unobservable loss; its usefulness is entirely captured by the conditional error function

the expected loss of the answer in hand given everything observed through stage i. The signal can be many things in practice, and the model is agnostic to which: it can be the maximum softmax probability of the answer token, a self-evaluation in which the model estimates the probability its own answer is correct,^[26] the agreement rate across several samples (self-consistency), a learned verifier's score, or a feature of the query itself. All that the theory requires is that the signal carry information about the loss, which is measured by how much ${\rho }_i(s_i)$ varies with $s_i$: a useless signal makes ${\rho }_i$ constant and reduces the cascade to a fixed schedule, while a perfect signal makes ${\rho }_i$ a zero-one indicator of correctness and lets the cascade escalate exactly the wrong answers. Real signals sit between, and their quality is the single most important input to a cascade's performance, more important than the choice of threshold rule, because no rule can separate hard from easy queries better than the signal allows.

A policy $\pi$ observes $s_1,\dots ,s_i$ after running $M_i$ and chooses to stop (return $a_i$) or continue (run $M_{i+1}$). Its stopping time $\tau \in \{1,\dots ,K\}$ is the index of the model whose answer is returned, and the cost actually paid is the sum of the costs of every model run,

because a cascade must run each model to reach the next. We distinguish two variants by which answer is returned. In the keep-best (recall) variant the returned loss is ${\min }_{j\le \tau }{\ell }_j$, the best answer among those produced; this is faithful when answers are cheap to store and a verifier can pick among them. In the take-last (no-recall) variant the returned loss is ${\ell }_{\tau }$, the most recent model's answer; this is faithful when later models are assumed strictly better and only the last answer is kept. The two variants correspond to Weitzman's and Doval's settings respectively.^[8][9]

The operator's objective scalarizes quality and cost through a price $\lambda >0$ that expresses how many units of loss one unit of cost is worth:

3.2 The Bellman recursion

Solve by backward induction on the stage index. Let $V_i(h_i)$ be the minimal expected value of the remaining objective given the history $h_i=(s_1,\dots ,s_i)$ observed after running $M_i$, measured from stage i onward and excluding costs already sunk. At the last stage the policy must stop, so $V_K(h_K)={\rho }_K(h_K)$ in the take-last variant. At any earlier stage the value is the smaller of the stop value and the continue value:

The stop value is the expected loss of the answer in hand. The continue value pays the next model's cost now and inherits the optimal value from the next stage in expectation over the signal it will reveal. Define the continuation value

which is the expected cost, in the same units as loss, of running the rest of the cascade optimally starting from $M_{i+1}$. The optimal policy is then immediate from Equation (4): stop at stage i if and only if the current estimated error is no larger than the continuation value,

This is the whole optimal rule, and it is worth pausing on what it says. The threshold that the current estimated error is compared against is not a constant. It is $Q_i(h_i)$, the continuation value, which depends on the costs and qualities of every downstream model and, through the conditional expectation, on the history $h_i$ itself. Figure 3 shows the two costs as functions of the current estimated error and the reservation value at their crossing.

Two remarks make the recursion precise. First, the recursion is a genuine dynamic program because the state after stage i is a sufficient statistic for the future: given the history $h_i$, the distribution of every downstream signal and loss is determined, so the value-to-go depends on the past only through $h_i$. When the raw history is unwieldy, the belief state, the posterior over the correctness of the current answer and over which downstream models will succeed, is the compressed sufficient statistic, and the cascade becomes a partially observed Markov decision process with a two-action (stop, continue) control at each stage. Second, the min in Equation (4) is attained, and the optimal policy is deterministic: because the stop and continue values are well-defined numbers for each history, ties form a measure-zero set under mild continuity of the signal distribution, and off that set the better action is unique. There is therefore no benefit to randomizing the escalation decision, which is worth noting because some production systems escalate a random fraction of borderline queries; the theory says the cost-optimal rule is a hard boundary, and randomization can only match it, never beat it, under a fixed price $\lambda$.

3.3 The constrained form and the price lambda

Operators usually think not in a price $\lambda$ but in a constraint: minimize cost subject to a quality floor, or maximize quality subject to a budget. The two views are equivalent by Lagrangian duality. The constrained problem of minimizing expected cost subject to an expected-loss constraint $\mathbb{E}[{\ell }_{\tau }]\le \epsilon$ has the Lagrangian

whose stationary policy for the optimal multiplier ${\lambda }^{\ast }$ coincides with the minimizer of $J(\pi )$ in Equation (3) up to the constant $\epsilon /\lambda$. The multiplier ${\lambda }^{\ast }$ is the shadow price of the quality constraint: it is the marginal cost of tightening the loss floor by one unit, and it is exactly the $\lambda$ to plug into the reservation rule. This is why a single knob, the price, traces the entire cost-quality frontier: sweeping $\lambda$ from zero to infinity moves the operating point from always-escalate (best quality, highest cost) to never-escalate (cheapest, worst quality), and each intermediate $\lambda$ is the frontier point for the corresponding budget.

A worked instance makes the duality tangible. Suppose an operator has a monthly compute budget and wants the lowest error achievable within it. Sweeping $\lambda$ from large (never escalate) to small (always escalate) generates a curve of (expected cost, expected error) points, one per $\lambda$, and the operator picks the $\lambda$ whose expected cost equals the budget; the corresponding error is the best achievable, and the corresponding reservation risks are the thresholds to deploy. The multiplier at that point is the marginal price of compute in error units: it says how much error one more unit of budget would remove, which is exactly the number a finance owner needs to decide whether to raise the budget. This is why the stopping formulation is not only a correctness statement but a budgeting tool: it turns a vague quality-cost preference into a single number that both sets the thresholds and prices the next dollar of spend. The same machinery handles a quality floor instead of a budget: fix the error target, read off the $\lambda$ whose expected error meets it, and its expected cost is the cheapest way to hit the target.

3.4 Assumptions

The results that follow rest on four assumptions, stated here and revisited in Section 9.

• A1 (informative signal). The conditional error ${\rho }_i(s_i)$ is measurable and, in the threshold results of Section 4, monotone in a scalar summary of the signal, so that thresholding the signal and thresholding the estimated error coincide. Calibration is what makes this hold in practice.^[25]
• A2 (additive, known-order cost). Costs add across stages as in Equation (2), and the cascade order is fixed by cost. When models may be reordered, the relevant optimum is the index policy of Weitzman or Gittins.^[8][14]
• A3 (stationary stream, Sections 3 to 6). Queries are drawn i.i.d. from a fixed $\mathcal{D}$. Section 7 relaxes knowledge of $\mathcal{D}$ but keeps stationarity; Section 9 discusses drift.
• A4 (bounded loss). Losses lie in $[0,1]$ and costs in $[0,C_{\max }]$, so the objective is bounded, which the regret analysis needs.

flowchart TB
  subgraph KB["Keep-best (Weitzman)"]
    K1["Run M1"] --> K2["Run M2"] --> K3["Run M3"]
    K1 -.-> KP["Return best of a1, a2, a3"]
    K2 -.-> KP
    K3 -.-> KP
  end
  subgraph TL["Take-last (Doval)"]
    T1["Run M1"] --> T2["Run M2"] --> T3["Run M3"]
    T3 --> TP["Return a3 only"]
  end

3.5 The always-escalate and never-escalate baselines

Two degenerate policies bound the frontier and give the price $\lambda$ its meaning. The never-escalate policy stops at the first model always, paying cost $c_1$ and incurring expected loss $\mathbb{E}[{\ell }_1]=e_1$, for objective $e_1+\lambda c_1$. The always-escalate policy runs the whole cascade, paying $C_K={\sum }_j{c}_j$ and incurring the last model's loss $e_K$ (take-last) or the best loss (keep-best), for objective $e_K+\lambda C_K$ in the take-last case. The optimal policy is never worse than either, and equals never-escalate for $\lambda$ large enough that even the first escalation fails the reservation test, and equals always-escalate for $\lambda$ small enough that every escalation passes it. Between those extremes the optimum is a genuine mixture that escalates a query-dependent subset, and its objective traces the interior of the cost-quality frontier. The width of the interesting region, the range of $\lambda$ for which the optimum is neither extreme, is exactly the range in which the escalation decision is nontrivial and in which the suboptimality of a fixed threshold, studied next, can bite. Outside that range a threshold is trivially optimal because so is a constant policy, which is why Figure 6 shows the gap vanishing at both ends of the cost axis.

The baselines also clarify what the price $\lambda$ encodes operationally. Setting $\lambda$ equal to the ratio of the value of a correct answer to the cost of a token makes the objective a pure expected-utility expression, and the reservation rule then stops when the marginal expected accuracy gain of escalating is smaller than its marginal cost. Operators who cannot name a dollar value for accuracy can instead pick the constrained form of Section 3.3 and let the dual multiplier reveal the implied $\lambda$, which is often more intuitive: it is the shadow price of the quality SLO, the extra spend a one-point accuracy improvement would justify. Either way, a single scalar traces the frontier, and the entire design problem reduces to choosing where on that frontier to sit and then implementing the reservation rule that reaches it.

4. Structure of the optimal policy

4.1 The reservation-risk rule

Equation (6) already gives the optimal rule as a comparison of current estimated error against the continuation value. Under Assumption A1 this comparison is a threshold on the signal. Write $t_i^{\ast }(h_i)=Q_i(h_i)$ for the reservation risk at stage i. Because ${\rho }_i$ is monotone in the signal, there is a signal level at which ${\rho }_i(s_i)=t_i^{\ast }$, and the optimal policy stops for all signals cleaner than that level:

The reservation risk has a clean monotonicity across stages that Figure 5 illustrates. Early in the cascade there are many cheap downstream options, so the option value of continuing is high and the reservation risk is generous: you accept a fairly high estimated error because escalation is cheap insurance. Late in the cascade the remaining options are few and expensive, the option value is low, and the reservation risk tightens toward zero at the last stage, where it is exactly zero because there is nothing left to escalate to. This is the opposite of what a naive reading suggests: the cheap early models should be trusted less, not more, because distrusting them is cheap.

The monotonicity is not merely illustrative; it follows from the recursion. Write ${\bar{t}}_i=\mathbb{E}[t_i^{\ast }]$ for the average reservation risk at stage i. The continuation value at stage i is $\lambda c_{i+1}+\mathbb{E}[V_{i+1}]$, and $V_{i+1}=\mathbb{E}[\min ({\rho }_{i+1},Q_{i+1})]\le \mathbb{E}[{\rho }_{i+1}]$, so the value-to-go can only improve on stopping immediately at the next stage. As the stage index rises toward K, two things happen: the number of remaining escalation options falls, so the min in the value function is taken over fewer alternatives and $V_{i+1}$ rises toward the raw next-stage error; and the cheapest remaining cost $c_{i+1}$ rises because the cascade is cost-ordered. Both push the reservation risk down: fewer options and pricier ones make continuing less attractive, so the bar for stopping loosens earlier and tightens later. At the final stage the continuation set is empty, the continue value is infinite (there is nothing to run), and the reservation risk is zero: you accept whatever the last model gives because you must. This is a theorem-level statement of the intuition that the option value of escalation is front-loaded, and it is the opposite of the common heuristic of setting a single global confidence bar for all stages.

4.2 The Weitzman identity for keep-best cascades

In the keep-best variant the problem is exactly Pandora's box with rewards $v_i=1-{\ell }_i$ (answer quality) and inspection costs $\lambda c_i$. Weitzman's reservation value $z_i$ is defined by the indifference equation

which states that the expected quality gained by opening box i above the level $z_i$ equals its inspection cost.^[8] The optimal policy opens boxes in decreasing order of $z_i$ and stops when the best quality in hand exceeds the next box's reservation value. For a cost-ordered cascade whose more expensive models are also higher quality, the cost order and the reservation-value order coincide, and the rule reduces to the reservation-risk rule of Equation (8) with $t_i^{\ast }=1-z_{i+1}$. The important structural fact, which we use in Section 5, is that $z_i$ depends only on box i's own reward distribution and cost, so the optimal reservation value is a property of the downstream model, not of the current model's confidence. A rule that thresholds only the current model's confidence is therefore reading the wrong quantity.

4.3 The take-last variant and Doval's shift

In the take-last variant the agent discards earlier answers, so stopping at stage i means committing to ${\ell }_i$ even if an earlier answer was better. Doval's analysis of the no-recall Pandora problem shows the optimal policy is no longer a pure decreasing-index rule: because the agent cannot fall back on a discarded box, it is willing to escalate on the strength of an uninspected box's promise, and the reservation risk shifts to account for the lost fallback.^[9] In cascade terms, the take-last reservation risk is lower (more eager to escalate) than the keep-best one whenever a later model is expected to be better, because there is no cost-free way to recover the earlier answer. Real LLM cascades sit between the two variants: answers are cheap to store, so keep-best is usually available and preferable, but many systems take the last answer for simplicity and thereby adopt the less favorable reservation structure without realizing it.

4.4 Specialization to accumulated evidence

When the signal at each stage is itself an accumulation of evidence, for example the number of agreeing samples in a self-consistency check,^[4] the conditional error ${\rho }_i$ is a function of a running log-likelihood ratio, and the reservation rule specializes to Wald's boundary: stop and accept when the ratio crosses an upper threshold, escalate when it crosses a lower one.^[13] The two Wald boundaries are the reservation risks for the accept and escalate actions, and Wald and Wolfowitz's optimality of the SPRT is the statement that this boundary minimizes expected cost among all stopping rules with the same error profile. This gives a principled reading of consistency-based cascade signals: the right number of samples to draw before escalating is the one that brings the ratio to the reservation boundary, not a fixed sample budget.

4.5 The two-model reservation value in closed form

For two models the reservation rule has a closed form that repays study, because it shows exactly which quantities the optimal threshold depends on. The optimum stops at model 1 when ${\rho }_1(s_1)\le Q_1(s_1)$, and with only one downstream model the continuation value is $Q_1(s_1)=\lambda c_2+\mathbb{E}[{\ell }_2\mid s_1]$, since running model 2 is terminal. Write $d(s_1)=\mathbb{E}[{\ell }_2\mid s_1]$ for the expected downstream loss given the stage-1 signal. The optimal reservation risk is therefore

$t_1^{\ast }(s_1)=\lambda c_2+d(s_1),$

and the optimal rule stops iff ${\rho }_1(s_1)\le \lambda c_2+d(s_1)$. Three features are visible. First, the threshold rises with the escalation cost $\lambda c_2$: a more expensive downstream model makes you tolerate more error before escalating. Second, it rises with the downstream loss $d(s_1)$: if model 2 is also likely to be wrong on this query, escalating is pointless and you should stop even at high error. Third, and most important, $d(s_1)$ depends on the stage-1 signal, so the optimal threshold is a function of the signal, not a constant. A fixed confidence threshold $\theta$ replaces $\lambda c_2+d(s_1)$ with a constant, which is correct only if $d(s_1)$ does not vary with $s_1$, that is, only if the downstream loss is uninformed by the stage-1 signal. The moment the signal that says model 1 is unsure also predicts model 2 will struggle, $d(s_1)$ climbs on exactly the queries where ${\rho }_1$ is high, the optimal threshold climbs with it, and the constant threshold escalates queries it should not. This is the two-model instance of Proposition 1, and it is the closed form behind the worked example in Section 5.4.

4.6 Index optimality and the question of order

A subtlety we have glossed is whether the cost order is the right order to run models in. We assumed the cascade runs cheapest first, which is the natural choice and is optimal under a mild condition, but it is worth seeing why. In Weitzman's keep-best setting the optimal order is by decreasing reservation value, not by cost, and the two coincide only when a cheaper model also has a higher reservation value.^[8] The reservation value of a model is high when it is cheap and its reward distribution has substantial upside, so among models of similar quality the cheaper one has the higher reservation value and should be run first, which recovers the cost order. The order can flip when a slightly more expensive model is much more likely to resolve the query, in which case running it first, even though it costs more, is optimal because it ends the cascade sooner in expectation. This is the same logic that makes a good specialist worth trying before a general model on a query in its specialty, and it is why production routers sometimes skip the cheapest model entirely for certain query types.

When the operator can choose the next model freely at each step rather than following a fixed list, the problem becomes a Markovian bandit and Gittins's theorem applies: compute a dynamic allocation index for each available model and run the one with the highest index, which is the reservation value generalized to the choice.^[14] The index is still an isolated per-model computation, so the remarkable decoupling survives: even with a free choice of next model, the optimal policy never needs to jointly reason about all models, only to rank them by an index each computes alone. This is the theoretical backing for the practical pattern of maintaining a per-model score and always escalating to the highest-scoring untried model, and it tells us that pattern is not a heuristic but an optimal policy under the stated conditions. The cost order we assume for the main results is the special case where the index order matches the cost order, which holds whenever quality rises with cost, the usual situation; the general case is a direct application of the index theorem and does not require new analysis.

5. Fixed confidence thresholds are suboptimal

5.1 The confidence-threshold policy class

The policy almost every deployed cascade uses is the confidence-threshold policy: fix a per-stage threshold ${\theta }_i$ and stop at stage i whenever the current model's estimated error clears it, ${\rho }_i(s_i)\le {\theta }_i$, with the thresholds tuned globally on a validation set. Call this class ${\Pi }_{\mathrm{conf}}$. It is attractive because it is simple, it needs only the current model's confidence, and it requires no model of downstream behavior. The question is what that simplicity costs.

The class is a strict subset of the stopping policies. A general stopping policy at stage i is any measurable function of the history $h_i$ to the two actions; the confidence class restricts that function to a threshold on ${\rho }_i$ alone, discarding any part of the history that predicts downstream behavior without changing the current error estimate. That discarded information is precisely what distinguishes an easy query the cheap model happens to be unsure about (worth escalating) from a hard query no model can answer (not worth escalating), and both can present the same current confidence. A confidence threshold, seeing only the confidence, must treat them identically, and whichever action it picks is wrong for one of them. This is the informal version of the impossibility that Proposition 1 makes exact: the class is too coarse to separate cases the optimum separates, and the coarseness is not a tuning problem but a representational one.

5.2 When a fixed threshold is optimal

Compare ${\Pi }_{\mathrm{conf}}$ against the optimal rule of Equation (8). The optimal rule stops when ${\rho }_i(s_i)\le t_i^{\ast }(h_i)$; the confidence rule stops when ${\rho }_i(s_i)\le {\theta }_i$. These coincide for all histories if and only if the reservation risk $t_i^{\ast }(h_i)$ equals a constant ${\theta }_i$ almost surely. From Equation (5) the reservation risk varies with $h_i$ only through the continuation value, so we have the following.

The proof is immediate from Equation (8): the two stopping regions are identical iff their thresholds are identical as functions of $h_i$, and the optimal threshold is constant iff its only history-dependent term, the continuation value, is constant. The condition has a clear meaning. The continuation value is constant when knowing that the cheap model is unsure tells you nothing about whether the expensive model will succeed, that is, when the models' errors are independent conditional on the signal. The moment hard queries are hard for both models, observing a weak signal at stage i raises the expected downstream loss, the continuation value climbs, the optimal reservation risk climbs with it, and a fixed threshold can no longer track it. This is exactly the regime in which Jitkrittum and colleagues observe confidence deferral to fail, now derived rather than measured.^[7]

To make the proof fully explicit, fix a stage i and consider the two stopping regions as subsets of signal space. The optimal region is ${\mathcal{S}}^{\ast }=\{s:{\rho }_i(s)\le Q_i(s)\}$ and the threshold region is ${\mathcal{S}}_{\theta }=\{s:{\rho }_i(s)\le \theta \}$. They coincide on a positive-measure basis only if the boundary ${\rho }_i(s)=Q_i(s)$ is a level set ${\rho }_i(s)=\theta$, which requires $Q_i(s)$ constant on the boundary. If $Q_i$ takes two distinct values $q_1<q_2$ on positive-measure sets, then any single $\theta$ either lies below $q_1$ (and wrongly escalates queries with ${\rho }_i\in (\theta ,q_1]$ the optimum would stop on), above $q_2$ (and wrongly stops queries the optimum would escalate), or between them (and does both), so on a positive-measure set the two policies disagree. On that set the optimum takes the cheaper action by construction, so the threshold pays strictly more and the gap of Equation (10) is strictly positive. The converse is immediate: if $Q_i$ is constant almost surely, setting $\theta =Q_i$ makes the regions equal and the gap zero. Constant continuation value is therefore necessary and sufficient for a fixed threshold to be optimal.

5.3 The approximation gap

When the continuation value varies, the confidence policy is strictly worse, and we can say by how much. Let ${\pi }_{\theta }$ be the best policy in ${\Pi }_{\mathrm{conf}}$ and ${\pi }^{\ast }$ the optimum. The excess cost is the expectation, over histories where the two policies disagree, of the cost difference between the action the threshold takes and the action the optimum takes:

The gap is nonnegative because on every history where the policies agree the contribution is zero, and where they disagree the optimum takes the cheaper action by definition, so the threshold pays the absolute difference between the stop and continue costs. The gap is strictly positive whenever the reservation risk has positive variance and the fixed threshold falls strictly inside its range, because then a positive-measure set of histories has ${\rho }_i$ between the fixed threshold and the true reservation risk, and on that set the two policies disagree. This proves the qualitative claim: any fixed confidence threshold is suboptimal unless the reservation risk is degenerate.

It is worth being precise about what the gap is and is not. It is not the difference between the cascade and the best single model, which can be large or small depending on the workload; it is the difference between the best fixed-threshold cascade and the best possible cascade with the same models and signals. A team can have an excellent cascade that saves 90 percent over the expensive model and still be leaving the gap on the table, because the gap is measured against the cascade optimum, not against the expensive-model baseline. This matters for how the gap is detected: it does not show up as poor absolute performance, only as performance that plateaus below what a query-dependent rule would reach, which is invisible unless you either fit the reservation rule or build a router and compare. The estimation-versus-approximation decomposition of Section 7 is what makes the gap observable, by separating the part of the shortfall that more data removes (estimation) from the part that only a richer rule removes (the gap), so a team that has clearly converged its threshold and still trails a small pilot router is looking at the gap.

For a two-model cascade the gap has a closed form worth seeing. Let the cheap model have estimated-error distribution with density $f(\rho )$ over $[0,1]$, and let the continuation value given signal be $Q_1(\rho )=\lambda c_2+g(\rho )$, where $g(\rho )$ is the expected downstream loss as a function of the cheap model's estimated error (increasing in $\rho$ under error correlation). The optimal rule stops iff $\rho \le \lambda c_2+g(\rho )$; the best fixed threshold $\theta$ stops iff $\rho \le \theta$. The gap integrates the disagreement:

where ${\rho }^{\ast }(\rho )$ denotes the optimal boundary at estimated error $\rho$. Minimizing over $\theta$ gives the best threshold, and the residual is the irreducible approximation gap of the class. Figure 6 plots how this residual varies with the escalation cost.

5.4 A worked two-model example

Make it concrete. Suppose the cheap model is right on 60 percent of queries and its confidence perfectly separates a clean subpopulation (estimated error 0.05) from a murky one (estimated error 0.6), with 60 percent of queries clean. The expensive model costs $\lambda c_2=0.15$ in loss units and is right on 90 percent of clean queries but, under high error correlation, only 55 percent of murky ones, so its loss is 0.10 on clean and 0.45 on murky. On a clean query the optimal rule compares stop cost 0.05 against continue cost $0.15+0.10=0.25$, and stops. On a murky query it compares stop cost 0.6 against continue cost $0.15+0.45=0.60$, and is indifferent, tipping to stop as soon as correlation pushes the downstream murky loss above 0.45. A fixed confidence threshold that escalates all murky queries, the intuitive choice because their confidence is low, pays 0.15 in cost to move loss from 0.6 to 0.45 on those queries, a net change of zero to slightly negative once the cost is counted. The threshold escalates exactly the queries where escalation does not pay, which is the signature of the gap. The optimal policy escalates murky queries only when the expensive model's murky loss is enough below 0.45 to cover its cost, a condition the raw confidence signal cannot express.

5.5 Reconciling with the deferral literature

Proposition 1 recovers and sharpens the central finding of the confidence-deferral literature. Jitkrittum and colleagues characterize the Bayes-optimal deferral rule and show confidence deferral underperforms when the downstream model's errors are input-dependent and correlated with the current model's.^[7] In our terms, input-dependent downstream error is exactly a non-constant continuation value, which by Proposition 1 is exactly the condition under which a fixed threshold is suboptimal, and Equation (10) gives the size of the shortfall. The learned-router systems can be read as attempts to enlarge the policy class enough to represent the query-dependent reservation value: RouteLLM's win-prediction model and Hybrid LLM's difficulty predictor are estimates of the downstream-relevant quantity that a raw confidence score omits.^[2][3] The stopping view explains why those systems beat thresholds: they are approximating $Q_i(h_i)$ rather than ignoring it.

5.6 A three-model worked example

Extend the two-model example to three models to see how the reservation risks chain. Let the costs in loss units be $\lambda c_1=0.01$, $\lambda c_2=0.08$, $\lambda c_3=0.30$, and suppose the signal at each stage splits queries into clean (estimated error 0.05) and murky (estimated error 0.5). Suppose the models' murky-query losses are 0.5, 0.3, and 0.15 respectively, and their clean-query losses are all near 0.03. Solve backward. At stage 3 there is nothing to escalate to, so the policy stops with reservation risk zero and accepts model 3's loss. At stage 2 the continuation value on a murky query is $\lambda c_3+0.15=0.45$, which exceeds the murky stop cost 0.3, so the policy stops at model 2 on murky queries: escalating to model 3 costs 0.30 to move loss from 0.30 to 0.15, a net loss of 0.15, not worth it. At stage 1 the continuation value on a murky query is the cost of running model 2 optimally, which is $\lambda c_2+0.30=0.38$, below the murky stop cost 0.5, so the policy escalates murky queries from model 1 to model 2. The optimal path for a murky query is therefore run model 1, escalate to model 2, stop; model 3 is never reached even though it is the most accurate, because its cost exceeds the accuracy it would add. A fixed confidence threshold that escalates all murky queries to the most accurate model would pay 0.30 to reach model 3 and lose money, and a threshold tuned to stop at model 2 on murky queries happens to match the optimum here only because the example's continuation value is constant across murky queries; introduce query-level variation in model 3's accuracy and no single threshold tracks the optimum, by Proposition 1.

The example also illustrates the front-loaded option value of Section 4.1. The stage-1 reservation risk is high (the policy escalates murky queries readily) because a cheap downstream model is available, while the stage-2 reservation risk is low (the policy stops on murky queries) because the only remaining option is expensive. This is the opposite of the instinct to trust the biggest model most; the cascade trusts the biggest model least in the sense that it reaches it least, precisely because reaching it is expensive.

5.7 Routers as continuation-value estimators

The stopping view gives a clean account of why learned routers outperform confidence thresholds, and of what they are really computing. A router that reads query features and predicts whether the expensive model will win is, in the language of Section 4.5, an estimator of the downstream loss $d(s_1)$ or equivalently of the continuation value $Q_1$. RouteLLM's win-prediction model estimates the probability that the strong model beats the weak one, which is one minus a normalized $d(s_1)$, and its cost threshold converts that estimate into the escalation decision, which is exactly the reservation comparison with a learned continuation value.^[2] Hybrid LLM's difficulty predictor plays the same role, estimating a query-level difficulty that stands in for the downstream loss.^[3] The mixture-of-thoughts cascade estimates ${\rho }_1$ itself through answer consistency, which improves the stop side of the comparison without addressing the continuation side.^[4] Seen this way, the router literature is a sequence of increasingly good approximations to the same continuation value the theory identifies, and the reason each beats a raw confidence threshold is that a raw threshold approximates $Q_1$ by a constant while a router approximates it by a function of the query. The remaining approximation error of a router is the distance between its predicted continuation value and the true one, which is a regression problem with its own sample complexity, an open question we return to in Section 11.

6. The error-correlation penalty

6.1 The benefit rate of a cascade

A cascade rescues a query only when the cheap model is wrong and the expensive model is right, because those are the queries escalation converts from failure to success. Let $Y_1,Y_2\in \{0,1\}$ be the error indicators of the two models on a random query, with marginal error rates $e_1=\mathrm{Pr}(Y_1=1)$ and $e_2=\mathrm{Pr}(Y_2=1)$, and let $\varphi$ be the phi coefficient (the correlation of the two binary error indicators). The benefit rate is the probability the cheap model errs and the expensive one does not:

The first two equalities are exact; the third uses the standard identity relating the joint probability of two Bernoulli variables to their marginals and phi coefficient. The benefit rate is decreasing in $\varphi$: at fixed marginal accuracies, the more the two models fail together, the smaller the set of queries a cascade can rescue. When errors are independent ( $\varphi =0$) the benefit rate is $e_1(1-e_2)$, its largest value for a given pair of accuracies at nonnegative correlation; when errors are maximally correlated the benefit rate falls toward $\max (0,e_1-e_2)$, which is zero whenever the expensive model is no more accurate than the cheap one on the shared hard set. Figure 8 plots the decline.

The identity is worth deriving from the two-by-two contingency table of the two error indicators, because it makes the assumptions visible. The joint distribution of $(Y_1,Y_2)$ is fixed by three numbers: the two marginals $e_1,e_2$ and any one joint cell. Write $p_{11}=\mathrm{Pr}(Y_1=1,Y_2=1)$. The phi coefficient is the Pearson correlation of the two Bernoulli variables, and by definition $\varphi =(p_{11}-e_1{e}_2)/\sqrt{e_1{e}_2(1-e_1)(1-e_2)}$, so $p_{11}=e_1{e}_2+\varphi \sqrt{e_1{e}_2(1-e_1)(1-e_2)}$. The benefit cell is $p_{10}=\mathrm{Pr}(Y_1=1,Y_2=0)=e_1-p_{11}$ because the row for $Y_1=1$ sums to $e_1$, which gives Equation (12) directly. The derivation exposes the two limits. Independence sets $\varphi =0$ and $p_{11}=e_1{e}_2$, so $p_{10}=e_1(1-e_2)$. Maximal positive correlation drives $p_{11}$ to its Frechet upper bound $\min (e_1,e_2)$, so when $e_2\le e_1$ the benefit collapses to $e_1-e_2$, the pure marginal-accuracy difference, and every query the cheap model can be rescued on is one the expensive model was already going to answer anyway. The lesson for measurement is that the benefit rate is not recoverable from the two models' accuracies alone; it needs the joint cell, which means a paired evaluation on the same queries, not two separate accuracy numbers.

6.2 The oracle minimum escalation fraction

The benefit rate sets a hard floor on how cheap a cascade can be at a target quality. Suppose the cheap model alone has error $e_1$ and the operator wants overall error at most $\epsilon <e_1$. Every unit of error reduction must come from escalating a query in the rescue set, so even an oracle that escalates exactly the right queries must send at least a $\beta$-limited fraction to the expensive model. The minimum escalation fraction to reach error $\epsilon$ is

where $e_2^{\mathrm{rescue}}$ is the expensive model's error on the rescued queries and the second inequality uses $e_2^{\mathrm{rescue}}\ge 0$. The bound is intuitive: to remove a fraction $e_1-\epsilon$ of errors you must escalate at least that many of the cheap model's mistakes, and more if the expensive model does not fix all of them. This is the theory behind FrugalGPT's headline number. On HEADLINES the cheap model (GPT-J) produces identical generations to GPT-4 on 80 percent of queries and beats it on 6 percent, so the rescue set is small and the correlation structure favorable, and FrugalGPT can hold quality while sending only 16.6 percent of queries to GPT-4, a 98 percent cost reduction.^[1] On tasks where the models fail together the same bound forces a much larger escalation fraction and a much smaller saving. Figure 9 plots the floor.

A numeric walkthrough fixes the intuition. Take a cheap model with error $e_1=0.40$ and a target overall error $\epsilon =0.10$. To remove 30 points of error (from 0.40 to 0.10) the oracle must escalate at least the queries carrying those errors that the expensive model can fix. If the expensive model is perfect on the rescued queries, the minimum escalation fraction is $(0.40-0.10)/0.40=0.75$: three quarters of queries must go to the expensive model, and the cascade saves little. If instead the cheap model's error is only $e_1=0.10$ and the target is $\epsilon =0.05$, the minimum escalation fraction is $(0.10-0.05)/0.10=0.50$ in the worst case but far smaller when the cheap model's residual errors are the easy-for-the-big-model kind, which is the favorable-correlation case. The gap between these two scenarios, both with plausible numbers, is the difference between a cascade that saves 25 percent and one that saves 90 percent, and it is driven by the cheap model's competence and the error correlation, not by any property of the threshold rule. This is the quantitative core of the advice to measure before tuning: the achievable saving is bounded by numbers you can estimate in an afternoon, and no amount of threshold engineering moves the bound.

6.3 Why cascades save more on some tasks

Sections 6.1 and 6.2 together answer a question practitioners meet constantly: why does the same cascade architecture save 98 percent on one workload and 20 percent on another, with the same two models? The answer is not the models' individual accuracies, which are fixed, but the correlation of their errors on the workload. A workload where the cheap model's failures are idiosyncratic (independent of the expensive model's) has a large rescue set and cheap escalation; a workload where failures are shared (a genuinely hard domain both models struggle with) has a small rescue set and expensive escalation. This reframes cascade design as a measurement problem: before tuning any threshold, estimate the cross-model error correlation on a held-out sample, because it, not the model choice, bounds the achievable saving.

6.4 Correlation in deeper cascades

In a cascade of more than two models the benefit rate generalizes to a chain of conditional rescue probabilities, and the correlation penalty compounds. The queries reaching stage $i+1$ are those the first i models all failed on, a set already selected for difficulty, so the conditional error of model $i+1$ on that set is higher than its marginal error, and the benefit of the next escalation is smaller than the marginal accuracies suggest. Formally, the benefit of escalating from stage i to $i+1$ is $\mathrm{Pr}(Y_{i+1}=0\mid Y_1=\cdots =Y_i=1)$, a conditional survival probability that decreases in the pairwise error correlations. In the extreme of a common hard core of queries that every model fails on, the rescue probability at every stage collapses on that core, and the deep cascade wastes its most expensive stages running models that cannot help. This is the theoretical reason a three-model cascade is not automatically better than a two-model one: each added stage pays its cost on the residual hard set, which is exactly the set where correlation makes the added model least likely to help.

The measurement implication sharpens accordingly. Sizing a deep cascade requires not just the pairwise correlations but the conditional error of each model on the set its predecessors failed, which is a quantity only a full-cascade evaluation reveals. This is one more reason the exploration action of Section 7, running every model on a sample of queries, is the right primitive: it yields the joint error structure that both the reservation rule and the correlation penalty need, and no cheaper measurement substitutes for it. Teams that estimate each model's accuracy in isolation and assume independence will systematically overestimate a deep cascade's savings, because independence is the most optimistic correlation and real workloads sit well away from it.

7. Online regret of learning the policy

7.1 What the learner observes

In deployment the operator does not know the distributions $({\rho }_i,Q_i,{\ell }_i)$ and must learn them from traffic. The learning problem's difficulty depends on the feedback. In the full-cascade feedback model, during exploration the learner runs every model on a query and observes every loss ${\ell }_1,\dots ,{\ell }_K$, which is expensive but informative and matches how offline threshold tuning is done. In the bandit feedback model the learner observes only the losses of the models it actually ran, which is cheaper but partial, and is the setting of the online-Pandora and bandit-Pandora results.^[19][20] We analyze the full-cascade model in detail because it yields clean bounds and mirrors practice, and we cite the bandit results for the order-matching guarantees in the partial-feedback case.

7.2 Explore-then-commit regret

The simplest analyzable learner is explore-then-commit (ETC). For the first $m$ queries the learner runs the full cascade, paying full cost, and records $(s_1,\dots ,s_K,{\ell }_1,\dots ,{\ell }_K)$. It then estimates the reservation risks by solving the empirical Bellman recursion on these samples, obtaining thresholds $\hat{t}$, and commits to them for the remaining $T-m$ queries. Regret against the best policy in the class decomposes into an exploration term and an exploitation term:

where ${\Delta }_{\exp }\le \lambda (C_{\max }-c_1)$ is the per-query overpayment during exploration (running the whole cascade instead of stopping early) and $t^{\star }$ is the best in-class threshold. The estimation term is governed by how fast the empirical thresholds converge. Because each threshold is a one-dimensional quantity estimated from $m$ i.i.d. samples, standard concentration gives $|\hat{t}-t^{\star }|=O(1/\sqrt{m})$, and because the objective $J$ is Lipschitz in the thresholds with some constant $L$ (a small change in a threshold changes the objective only through the measure of queries whose decision flips, bounded by the density times the shift), the per-query estimation regret is $O(L/\sqrt{m})$. Substituting and optimizing the exploration length,

The general rate is therefore $T^{2/3}$. Under a margin condition, that the objective is locally quadratic around a well-separated optimum so that a threshold error $\delta$ costs only $O({\delta }^2)$ rather than $O(\delta )$, the estimation regret per query improves to $O(1/m)$, the optimal exploration length shrinks to $m^{\star }\sim \sqrt{T}$, and $R_T=O(\sqrt{T})$. These rates match the order of the online and bandit Pandora's box guarantees.^[19][20] Figures 10 and 11 show the tradeoff and the rates.

The two ingredients of Equation (15) deserve their own derivation, because they are where the rate comes from. The first is the Lipschitz constant. Perturb a single threshold from $t$ to $t+\delta$. The only queries whose decision changes are those with estimated error in $(t,t+\delta ]$, a set of probability at most $f_{\max }\delta$ where $f_{\max }$ bounds the density of $\rho$. Each such query changes the objective by at most the cost swing $\lambda C_{\max }+1$, so the objective moves by at most $L\delta$ with $L=f_{\max }(\lambda C_{\max }+1)$. That constant is finite whenever the estimated-error density is bounded, a mild condition that fails only if a positive mass of queries sits exactly at a threshold. The second ingredient is the estimation rate. Each reservation risk is a functional of the empirical distribution of the $m$ exploration samples, and by standard concentration (Hoeffding for the cell probabilities, propagated through the smooth Bellman map) the estimate concentrates at $|\hat{t}-t^{\star }|=O_p\left(\sqrt{\log (1/\eta )/m}\right)$ with probability $1-\eta$. Multiplying the threshold error by the Lipschitz constant gives per-query estimation regret $O(L/\sqrt{m})$, and integrating the two terms of Equation (14) over the horizon and optimizing $m$ gives the $T^{2/3}$ rate. The margin improvement replaces the linear $L\delta$ dependence with a quadratic one: near a well-separated optimum the objective is flat to first order, so a threshold error $\delta$ costs $O({\delta }^2)$, the per-query estimation regret becomes $O(1/m)$, and the optimal exploration shrinks to $\sqrt{T}$.

7.3 Adaptive learners and lower bounds

A more data-efficient learner treats each candidate threshold vector as an arm and runs an upper-confidence-bound policy over a discretization of the threshold space. Discretizing each of the $K-1$ thresholds to a grid of spacing $ϵ$ yields $A=(1/ϵ{)}^{K-1}$ arms, and the UCB regret bound of Auer, Cesa-Bianchi, and Fischer gives $O(\sqrt{AT\log T})+ϵLT$, whose optimization over $ϵ$ also yields a sublinear rate that degrades gracefully in the number of stages.^[16][15] The exponential dependence on $K$ in the arm count is why the structured ETC analysis, which estimates each threshold directly rather than searching a product grid, is preferable for deep cascades. On the lower-bound side, Lai and Robbins's $\Omega (\log T)$ bound for parametric bandits and the standard $\Omega (\sqrt{T})$ minimax bound for the nonparametric case tell us the ETC rates are of the right order and cannot be improved beyond $\sqrt{T}$ without further structure.^[17]

7.4 Estimation regret does not close the approximation gap

The most important consequence of the regret analysis is a negative one. All of the bounds above measure regret against the best policy in the chosen class ${\Pi }_{\mathrm{conf}}$. They say estimation regret shrinks to zero. They say nothing about the approximation gap $\Delta$ of Section 5, which is the distance from the best threshold to the true optimum and is a property of the class, not of the data. The total excess cost of an online threshold learner is the sum of the two:

$\text{total excess}=\underset{\text{estimation}\to 0}{\underbrace{R_T/T}}+\underset{\text{approximation, fixed}}{\underbrace{\Delta }}.$

As the horizon grows the first term vanishes and the second remains. A team that keeps tuning its confidence threshold will see improvement plateau at $\Delta$ above the optimum, and no amount of additional traffic will push it lower. The only way through the floor is to change the class: replace the fixed threshold with a rule that reads features predictive of the continuation value, which is exactly what a learned router does. Figure 12 shows the decomposition. This is the precise sense in which the stopping view is actionable: it tells a team whether its problem is too little data (keep collecting) or too weak a rule (build a router), which are addressed by opposite investments.

7.5 Contextual reservation learning and the router regret

The natural response to the approximation floor is to enrich the class from constant thresholds to functions of the query, which turns the learning problem from scalar-threshold estimation into contextual stopping. The learner now fits a function ${\hat{Q}}_i(x)$ that predicts the continuation value from query features and stops when ${\rho }_i(s_i)\le {\hat{Q}}_i(x)$. The regret against the best function in the chosen hypothesis class decomposes exactly as before into an estimation part, which shrinks with data at a rate set by the complexity of the hypothesis class, and an approximation part, which is now the distance from the best function in the class to the true continuation value. Enriching the class trades a large, fixed approximation floor (the constant-threshold gap) for a smaller approximation floor plus a larger estimation term (fitting a function needs more data than fitting a scalar). The right level of enrichment is the one that minimizes the sum, which is a bias-variance tradeoff on the policy class itself. This is why a moderately expressive router often beats both a raw threshold (too much approximation error) and a very high-capacity router (too much estimation error at realistic data volumes), and it frames router design as choosing the capacity that matches the available preference or label budget.

The contextual regret rate depends on the hypothesis class in the usual way: for a finite-dimensional linear class the estimation regret is of order square-root of the dimension times T, and for richer nonparametric classes it degrades with the class's metric entropy. The precise rates for contextual stopping with a cost-additive objective are less settled than the scalar case, which is why we flag contextual reservation learning as an open problem in Section 11 rather than claiming a bound. The qualitative message is robust regardless of the exact rate: moving from thresholds to routers converts a fixed approximation floor into a vanishing estimation term, so with enough data the router reaches the true optimum that no threshold can, and the practical question is only whether the data budget justifies the router's capacity.

A final practical note on the exploration schedule. Explore-then-commit is easy to implement, but its fixed exploration budget is brittle under drift, because a schedule sized for horizon $T$ commits too early if the distribution shifts mid-stream. A doubling schedule, in which the learner re-enters exploration whenever the horizon doubles or a drift detector fires, recovers robustness at the cost of a logarithmic factor in the regret, and is what we would recommend in production over a single-shot explore-then-commit. Upper confidence bound methods adapt more gracefully but pay the exponential-in-K arm count of Section 7.3 unless they exploit the threshold structure; a structured optimistic estimator that maintains confidence intervals on each reservation risk directly, rather than on each threshold vector, is the right middle ground and, to our knowledge, has not been analyzed for this problem.

8. Discussion

The stopping formulation disagrees with common practice in three concrete places. First, it says the escalation decision should compare current estimated error against a continuation value, not against a fixed confidence bar, and that the continuation value is a property of the downstream models and the query, not of the current model's confidence. A team that tunes one global threshold per stage is implicitly assuming the continuation value is constant, an assumption Proposition 1 shows is almost never exactly true and Section 6 shows is badly false whenever errors are correlated. Second, it says the reservation risk should be more generous early in the cascade and stricter late, the opposite of the common instinct to trust the big model's confidence more than the small one's; the small model should be distrusted more precisely because escalating past it is cheap. Third, it says the ceiling on a cascade's saving is set by cross-model error correlation, a measurable property of the workload, so cascade design should begin with a correlation measurement, not a model selection.

The view also unifies several lines of work. Learned routers are, in this light, function approximators for the continuation value, which is why they beat thresholds exactly when the continuation value varies.^[2][3] The reorderable-cascade case, where the operator may choose which model to run next rather than following a fixed order, is a Gittins-index problem, and the index is the reservation value.^[14] Adaptive test-time compute is a degenerate cascade in which the stages are successive increments of reasoning on a single model, and the compute-optimal allocation Snell and colleagues find empirically is the reservation rule applied to that cascade.^[5][27] Calibration is the precondition that makes the whole apparatus run, because a reservation rule thresholds an estimated error, and an estimated error is only meaningful if the signal is calibrated.^[25][26] The surprising element, relative to the intuition that a good confidence score is all a cascade needs, is that the confidence score is structurally the wrong input: it measures the current model's uncertainty, while the optimal decision needs the downstream model's expected success, and those coincide only when errors are independent.

The formulation also clarifies the relationship between cascades and two adjacent inference techniques that are often discussed separately. Speculative decoding, in which a cheap draft model proposes tokens that an expensive model verifies and accepts or corrects, is a token-level cascade with an exact-recall guarantee: the verifier ensures the output distribution matches the expensive model's, so the stop decision (accept the draft) has zero quality cost and the only tradeoff is compute. That degenerate case, zero downstream loss on acceptance, is exactly the regime where the reservation value is trivial and a fixed acceptance rule is optimal, which is why speculative decoding does not face the suboptimality of Section 5. Model cascades face it precisely because their stop decision does carry a quality cost: the cheap model's answer might be wrong, and no cheap verifier certifies it. The difference between the two is the difference between a lossless and a lossy stop, and it maps onto whether the continuation value is trivial or query-dependent.

A second connection is to the reorderable cascade. We have assumed the models are run in cost order, but some systems can choose which model to run next, for instance selecting a specialist model based on the query. When the choice of next model is free, the problem becomes a bandit over models with an index policy, and Gittins's theorem says the optimal policy runs the model with the highest dynamic allocation index, which is the reservation value adapted to the choice.^[14] The practical reading is that specialist routing (choosing which expensive model to escalate to) and difficulty routing (choosing whether to escalate) are the same problem at different granularity, and both are solved by an index. This unifies the router literature's two moves, selecting a model and deciding to escalate, under one optimality principle.

A third connection is to calibration, which the formulation reveals as load-bearing rather than cosmetic. The reservation rule thresholds an estimated error ${\rho }_i(s_i)$, and that estimate is only usable if the signal is calibrated so that a stated error of 0.2 corresponds to a 20 percent chance of being wrong. Modern models are systematically overconfident and require post-hoc correction,^[25] and preference tuning damages the calibration that pretraining produced, though temperature adjustment partially restores it.^[26] A cascade built on an uncalibrated signal thresholds the wrong axis: it stops on queries the model is confidently wrong about and escalates queries it is underconfidently right about, and no amount of threshold tuning fixes a monotonicity failure in the underlying signal. Calibration is therefore a precondition for the entire apparatus, and the first diagnostic when a well-designed cascade underperforms should be a reliability diagram of its confidence signal, not a re-tuning of its threshold.

flowchart TB
  subgraph C["Confidence threshold"]
    C1["signal s_i"] --> C2{"s_i above theta?"} --> C3["stop or escalate"]
  end
  subgraph R["Learned router"]
    R1["query features"] --> R2["predict downstream win"] --> R3["route"]
  end
  subgraph O["Reservation rule (optimal)"]
    O1["rho_i current error"] --> O3{"rho_i within Q_i?"}
    O2["Q_i continuation value"] --> O3
    O3 --> O4["stop or escalate"]
  end

Figure 14 closes the discussion by returning to the cost-quality frontier through the lens of correlation. The frontier a cascade can reach is not a single curve but a family indexed by the workload's error correlation, and the gap between the independent-error frontier and the correlated-error frontier is the same quantity, expressed on the cost-quality plane, that Sections 5 and 6 expressed as a gap and a benefit rate.

A last discussion point is when not to cascade at all, which the framework answers cleanly. The oracle escalation bound of Equation (13) gives the minimum fraction of queries that must go to the expensive model to hit a quality target; multiply it by the expensive model's cost and compare to running the expensive model on everything. When the required escalation fraction is high, because the cheap model's error is large or the cross-model correlation is high, the cascade's saving over always using the expensive model is small, and the added complexity of the cascade (two models to serve, a signal to calibrate, a threshold or router to maintain) may not justify it. The cascade is most valuable in the opposite regime: a competent cheap model, a favorable correlation structure, and a small hard fraction, which is exactly the FrugalGPT HEADLINES regime where 98 percent savings are reported.^[1] The framework thus does not merely tell you how to run a cascade; it tells you whether to, by turning the decision into a comparison of the oracle escalation cost against the flat cost of the expensive model, both of which are estimable from a small labeled sample.

Stepping back, the broader lesson is about where the leverage in a cascade actually sits. The intuitive place to spend engineering effort is the decision rule, the threshold or router that picks which queries to escalate, and a large literature optimizes exactly that. The stopping analysis says the decision rule matters, but bounded by two quantities upstream of it: the quality of the confidence signal, which caps how well any rule can separate easy from hard, and the cross-model error correlation, which caps how much that separation is worth. A team that pours effort into the rule while ignoring the signal and the correlation is optimizing the last term in a product whose other terms it has not measured. The reframing this paper offers is to treat the cascade as a measurement problem first and an optimization problem second: measure the signal's calibration and the workload's correlation, which together bound the achievable outcome, and only then optimize the rule within those bounds, using the reservation form that is provably correct rather than a threshold that is provably not. This inverts the usual order of work, and it is the order the theory recommends because it front-loads the cheap measurements that determine whether the expensive optimization is worth doing at all.

9. Threats to validity and limitations

The results are statements about a model, and the model makes assumptions that reality violates in known ways. We list the load-bearing ones.

Signal informativeness and calibration (A1). The threshold results assume the conditional error is monotone in a scalar summary of the signal, which requires the signal to be calibrated. Real confidence scores are often miscalibrated, and preference tuning makes this worse.^[25][26] When the signal is not monotone in error, thresholding it is doubly wrong, and even the best-in-class threshold of Section 5 is not the relevant comparison. Our gap results should then be read as lower bounds on the true suboptimality.

Cost additivity and fixed order (A2). We assume costs add and the order is fixed by cost. Real systems have shared prefixes, caching, and batching that make cost non-additive, and some systems can choose which model to run next, which moves the problem to the Gittins-index setting we only sketch.^[14] The reservation-value structure survives these changes, but the closed forms do not.

Stationarity (A3). The regret analysis assumes an i.i.d. stream. Production traffic drifts, and under drift the best thresholds move, so a committed ETC learner incurs additional regret proportional to the drift rate. Non-stationary regret for this problem is open (Section 11), and our $T^{2/3}$ and $\sqrt{T}$ rates are stationary-case results.

The correlation model. The benefit-rate identity of Equation (12) uses the phi coefficient, which captures only the linear part of the dependence between the two error indicators. Higher-order dependence can make the true rescue set larger or smaller than the phi-based estimate, so Figure 8 is a first-order model, not an exact law. The oracle escalation bound of Equation (13) is exact as a lower bound but its upper counterpart depends on the escalation rule's ability to identify the rescue set, which is itself limited by signal quality.

Two-model closed forms. The explicit gap of Equation (11) and the worked example are for two models. The multi-stage gap is still given by Equation (10), but its evaluation requires the full continuation-value profile and does not reduce to a single integral. The qualitative conclusions (positive gap under continuation-value variance, correlation-driven benefit) hold at any depth.

The price and the objective. We scalarize quality and cost with a single price $\lambda$, which assumes the operator can express the tradeoff as a linear combination. Real objectives are sometimes non-linear (a hard latency SLO is a constraint, not a price, and a reputational cost of a wrong answer may be convex in error rate), and for those the reservation rule still holds stagewise but the mapping from constraint to price is more involved than the linear dual of Section 3.3. The results are stated for the linear-price case and extend to convex objectives with the appropriate subgradient in place of $\lambda$, but we do not carry out that extension here.

Signal and loss observability. The reservation rule needs the conditional error ${\rho }_i(s_i)$, which is an expectation over the unobserved ground truth. Offline it is estimated from labeled data; online it is estimated from delayed or partial feedback, and if labels never arrive (a common case in production, where correctness is not observed) the rule must lean on a proxy such as a learned verifier, whose own error propagates into the reservation estimate. Our regret analysis assumes exploration reveals the losses, which is the labeled-feedback case; the no-label case is strictly harder and is not covered by our bounds.

We ran no experiments. Every empirical figure quoted (FrugalGPT, RouteLLM, Hybrid LLM, the mixture-of-thoughts cascade, Snell, Viola-Jones) is from the cited source on that source's benchmark, and the cross-system table of Figure 7 is not comparable row to row because the benchmarks differ. Our own figures are analytical models with stated parameters, drawn to show the shape the theory predicts, not to report measurements. Where the theory meets data, it is through the cited numbers, and we have cross-confirmed the load-bearing ones against a second source. The theory could be right in structure and still mispredict a particular system if that system violates an assumption, which is why the practical implications below are framed as measurements to take, not numbers to trust.

10. Practical implications

For a team operating a cascade or router, the analysis reduces to five actions. First, replace the raw confidence threshold with an estimate of the continuation value: run the full cascade on a validation sample, solve the empirical Bellman recursion, and stop when the current estimated error falls below the fitted reservation risk. This is a small offline computation and it removes the part of the gap due to using a constant threshold where the reservation value is roughly constant. Second, calibrate the confidence signal before thresholding, because a reservation rule on a miscalibrated error estimate is a rule on the wrong axis.^[25][26] Third, measure the cross-model error correlation on a held-out sample, because Equation (13) turns it into a floor on your achievable escalation fraction and therefore your achievable saving; if the correlation is high, no threshold tuning will reach the savings you might expect from the models' individual accuracies. Fourth, if the continuation value varies substantially with the query (equivalently, if error correlation is high and query-dependent), invest in a learned, feature-based router rather than tuning thresholds, because Section 7.4 shows the threshold class has an approximation floor that data cannot remove.^[2][3] Fifth, when learning statistics from live traffic, use an explicit explore-then-commit schedule sized near the $T^{2/3}$ optimum rather than adapting the threshold greedily, which can lock in an early bad estimate; re-explore when you detect drift.

There is a natural order to these actions, because they have different costs and payoffs. The cheapest and highest-leverage is the correlation measurement: it is a single paired evaluation on a held-out sample, and it tells you whether a cascade can save what you hope before you build anything. If the correlation is high enough that even the oracle escalation fraction of Equation (13) is large, a cascade is the wrong tool and the money is better spent on a better cheap model or a different architecture. If the correlation is favorable, the next action is calibration, because every downstream decision reads the confidence signal and a miscalibrated signal poisons all of them. Only after those two is threshold-or-router tuning worthwhile, and the estimation-versus-approximation decomposition tells you which: if a well-tuned threshold plateaus above your target, the plateau is the approximation floor and the fix is a router, not more tuning. Following this order avoids the common failure of spending weeks tuning a threshold on a workload whose correlation structure caps the achievable saving below the target no matter what the threshold is.

The reservation rule itself is cheap to deploy. Given a labeled validation sample, run the full cascade on it, estimate each model's conditional error and cost, solve the K-step Bellman recursion once to get the reservation risks, and ship them as the stop thresholds, refreshing on a schedule or on a drift trigger. This is a small offline computation, and it captures the part of the optimum a constant threshold misses whenever the reservation risk varies across stages (which it always does, by Section 4.1) even before any query-dependent router is built. In other words, the first improvement over a global confidence threshold, using the correct per-stage reservation risks, is nearly free and strictly dominates the global threshold; the router is the second, more expensive improvement that closes the remaining query-dependent gap.

Monitoring deserves its own note, because a cascade's health is not visible from its aggregate cost and quality alone. The two quantities that drive the reservation rule, the conditional error at each stage and the continuation value, can drift independently of the headline numbers: a shift in the query mix can raise the hard fraction without changing average accuracy for a while, and a model update on either end of the cascade can change the error correlation and thus the achievable saving. The right instruments are a reliability diagram of the confidence signal (to catch calibration drift), a running estimate of the cross-model error correlation on a small labeled trickle (to catch changes in the achievable saving), and the realized escalation fraction against its oracle floor (to catch a rule that has drifted away from the reservation risks). A cascade that is quietly degrading will usually show it first in one of these three before it shows in the aggregate cost, which is why we recommend tracking them explicitly rather than waiting for the blended metric to move. The practice of instrumenting these signals is where the theory of this paper meets the day-to-day of operating a system, and it is the same instrumentation an observability stack already collects for other purposes.

The robustness of the recommendations to the paper's assumptions is worth stating plainly, since a practitioner will not have i.i.d. traffic or a perfectly calibrated signal. The reservation rule is the optimal policy under the stated assumptions, but even when they fail it strictly dominates a global confidence threshold, because using the correct per-stage reservation risks can only help relative to a single shared threshold. The correlation measurement is robust because it is a direct estimate of a workload property, not a model of it, so it degrades gracefully as the sample grows noisy. The regret schedule is the least robust piece, since it assumes stationarity, which is why we recommend the drift-triggered doubling variant over a single-shot explore-then-commit in any real deployment. In short, the ordering of actions, measure correlation, calibrate, fit reservation risks, then consider a router, holds up under assumption failure even where the exact bounds do not, because each action is individually beneficial and the order reflects cost and leverage rather than a fragile chain of theorems.

These actions connect to the broader practice covered in our other work on agentic systems, where cascades sit inside larger loops, and on LLMOps and observability, which is where the correlation and calibration measurements this analysis calls for actually get taken. The cost side of the argument is developed further in our research on model routing and cascades and hybrid inference economics, and the test-time-compute connection in the cost of reasoning. Teams setting an overall AI cost strategy will find the governance framing in AI strategy and value complementary to the per-query analysis here.

11. Open problems and future work

Five directions follow directly from the gaps above. First, contextual reservation learning: the router that breaks the approximation floor is a function approximator for $Q_i(h_i)$, and the right way to learn it is as a contextual stopping problem, for which the regret theory is less developed than the scalar-threshold case and whose sample complexity in the query features is open. Second, non-stationary regret: production streams drift, and a regret theory for the cascade under drift, with an explicit dependence on the drift rate and a principled re-exploration trigger, would tell operators when to relearn. Third, combinatorial cascades: real agent systems are not linear chains but graphs of tools and models, and the stopping problem becomes a sequential decision over a directed acyclic graph, connecting to the combinatorial-cost Pandora variants. Fourth, joint training and routing: if the models can be trained knowing they will sit in a cascade, the optimal joint design of models and reservation rule is a bilevel problem whose solution likely differs from training each model in isolation and then cascading. Fifth, sample complexity of the correlation estimate: since cross-model error correlation sets the achievable saving, how many labeled queries are needed to estimate it to a given precision, and how does estimation error in the correlation propagate into the escalation-fraction bound, is a concrete and answerable question.

Three further directions are worth naming. Sixth, label-free reservation estimation: in many deployments correctness is never observed, so the conditional error must be estimated from proxies such as self-consistency or a learned verifier, and the propagation of proxy error into the reservation rule, and the resulting regret, is unstudied. The connection to selective prediction under weak supervision is natural but the cost-additive structure changes the analysis. Seventh, the value of recall: we treated the keep-best and take-last variants separately, but real systems can choose how many earlier answers to retain at a storage cost, which is a middle ground between Weitzman and Doval whose optimal retention policy is open.^[8][9] Eighth, adversarial and strategic queries: if the query distribution is chosen adversarially (a user probing for the cheap model's blind spots, or a cost attacker trying to force escalation), the stationary regret bounds do not apply, and the right framework is adversarial online learning with the cascade cost as the loss, connecting the problem to online learning against an adaptive adversary.

Across all of these, the unifying object is the continuation value $Q_i(h_i)$. Every open question is, in one way or another, about estimating it better (contextual learning, label-free estimation), about the cost of estimating it under adverse conditions (non-stationarity, adversarial queries), or about designing systems whose continuation value is easier to estimate or more favorable (joint training, recall policies). This is the sense in which the stopping formulation is generative rather than merely descriptive: it names the single quantity that all the hard problems are about, which is the first step to solving them.

Frequently asked questions

Glossary

Cascade

An ordered sequence of models of increasing cost and (typically) quality, run one at a time, with a decision after each about whether to accept its answer or escalate.

Optimal stopping

The problem of deciding when to halt a sequential process to optimize an expected payoff that trades reward against the cost of continuing; solved by backward induction.^[11]

Continuation value Q_i

The expected cost, in loss units, of running the rest of the cascade optimally from stage i onward, including the next model's cost and its optimal continuation.

Reservation value / reservation risk

The level of current estimated error at which stopping and escalating are equally good; it equals the continuation value. The optimal rule stops below it.^[8]

Confidence-threshold policy

The deployed rule that stops when the current model's confidence clears a fixed bar; a proper subclass of stopping policies that omits the continuation value.

Approximation gap

The excess cost of the best in-class policy over the true optimum; a fixed property of the policy class that data cannot remove.

Benefit rate

The probability that the cheap model errs and the expensive one is right; the fraction of queries a cascade can rescue, decreasing in cross-model error correlation.

Phi coefficient

The correlation of two binary error indicators; here it measures how much two models tend to fail on the same queries.

Explore-then-commit (ETC)

A learner that gathers data for a fixed exploration length, estimates the optimal thresholds, then commits; regret of order T to the two-thirds power in general.

Regret

Cumulative excess cost of a learning policy over the best fixed policy in hindsight; the standard online-learning performance measure.^[15]

Pandora's box

Weitzman's sequential-search problem with inspection costs, whose reservation-value index policy is the optimal cascade rule for the keep-best variant.^[8]