Running several models and combining their predicted class probabilities is one of the most reliable ways to gain accuracy. It is also expensive. The best current fix is an early-exit cascade: run models one at a time, combine the probabilities seen so far, and stop as soon as the combined answer looks trustworthy. These cascades learn when to stop from a large labeled validation set collected in advance, and they never revisit that rule once deployed. This proposal learns the stopping rule online from a trickle of correctness feedback, while serving traffic. It treats each "stop or run one more model" decision as a logistic bandit, meaning a sequential decision problem in which the probability of success is a sigmoid of a linear score.
The reason this needs new machinery is specific. A cascade wants to stop in exactly the region where its combined confidence is very high, which is the flat tail of the sigmoid. Classical logistic bandit algorithms explore far too much in that region, because their guarantees scale with how flat the sigmoid can get. A recent line of bandit theory removes that penalty by noticing that outcomes in the flat tail are almost deterministic and therefore cheap to learn. We propose to carry that theory over to ensemble stopping, and to test whether it matters in practice. The test compares against simpler options: online retraining without deliberate exploration, and classical bandits that do pay the flatness penalty.
Core Claim
Stopping decisions face censored feedback. When the cascade stops after model $i$, it later learns whether its answer was right. It never learns whether running model $i+1$ would have fixed a wrong answer. A learner that greedily refits its stopping rule on observed outcomes can therefore lock in an overconfident habit. This is most likely after a distribution shift, when the deeper models start to matter more on inputs the cascade now exits on. Some deliberate exploration of "continue" is needed. The cheap way to get it is a confidence set whose width shrinks where the stop decision is easy.
Concretely, at stage $i$ we summarize the probabilities produced so far into a fixed-length feature vector $\phi \in \mathbb{R}^d$. The summary uses the sorted top-$k$ probabilities of the running combination, its entropy, and pairwise agreement among the executed models, so $d$ does not grow with the number of classes. For each later stage $j$, a logistic model estimates the chance that the stage-$j$ combined answer is correct, $\mu(\phi^\top \theta_j)$, where $\mu$ is the sigmoid and $\theta_j$ is learned online. The cascade continues from $i$ to $j$ only if an optimistic estimate of the gain exceeds the extra cost:
$$\mu(\phi^\top \hat\theta_j) - \mu(\phi^\top \hat\theta_i) + \beta_t\, \mu'(\phi^\top \hat\theta_j)\, \|\phi\|_{H_j^{-1}} > \lambda\, c_{ij}.$$
Here $\hat\theta$ are the current estimates and $\beta_t$ is a confidence radius. $H_j$ is the curvature-weighted information matrix, in which each past observation counts in proportion to its local slope $\mu'$. $c_{ij}$ is the compute or API cost of running stages $i+1..j$, and $\lambda$ sets the accuracy–cost trade-off. The factor $\mu'(\cdot)$ in the bonus is the key ingredient. Where the deeper stage is already predicted to be almost surely right or almost surely wrong, the bonus vanishes, and the method explores mainly where the outcome is uncertain.
The theoretical target is a regret bound against the best stopping policy in this logistic class. The leading term should scale like $d\sqrt{T/\kappa_*}$ per stage, where $T$ is the number of queries and $\kappa_*$ is the inverse slope at the optimal decision. That form is what the instance-wise logistic bandit analysis gives, and the worst-case flatness constant should appear only in lower-order terms.
Relation to Prior Work
The method draws on three logistic bandit papers. Improved Optimistic Algorithms for Logistic Bandits builds confidence sets from the curvature-weighted information matrix, which pushes the flatness constant $\kappa$ out of the leading regret term. Instance-Wise Minimax-Optimal Algorithms for Logistic Bandits shows that regret scales as $d\sqrt{T/\kappa_*}$, with matching lower bounds, so flatness near the optimum actually helps. It also shows that "detrimental" actions in the flat tails are discarded during a short transitory phase. Online (Multinomial) Logistic Bandit: Improved Regret and Constant Computation Cost gives online mirror descent updates with constant per-round cost, which we reuse so the stopping learner adds negligible latency. All three treat actions as abstract vectors. None of them considers a decision whose features are the outputs of earlier models, or feedback that is censored by the decision itself.
The motivating gap comes from ensemble efficiency work. Unifying Stacking and Cascading for Efficient Ensemble Inference (also LazyStack) trains small networks on the probabilities of the models executed so far and exits when their confidence passes a threshold. It discovers good model orderings from an offline labeled set and shows that cheapest-first ordering is often wrong. It cannot adapt after deployment, and it reports weaker gains on ImageNet-1K because probability mass spreads over many classes. FrugalGPT cascades language models with a trained scoring classifier but discards earlier models' outputs when deciding. RouteLLM and the JiSi system (Beyond Gemini-3-Pro: Revisiting LLM Routing and Aggregation at Scale) route queries using offline preference data or a labeled "embedding bank." All of these supply the setting. All are trained once offline, and none addresses exploration under censored feedback.
Probability Based Stacked Generalization supplies the representation: continuous probabilities carry more signal than hard votes. Our top-$k$ summary borrows from Determine-Then-Ensemble, which shows that the union of each model's top 10 tokens is enough for ensembling language models. That paper also constrains the design. It finds that combining models more than about 10% apart in accuracy hurts the stronger one. A stopping rule that pays to run a weak model and then mixes it in uniformly would repeat that mistake, so our combination step is a learned probability stacker, not an average. We also check whether the bandit's elimination of never-useful stages recovers the 10% rule without having to set it by hand.
Research Program
The work has three parts.
The first part is algorithmic. We will implement the stopping learner over a fixed model ordering. Following LazyStack's finding that a few orderings dominate, we will then extend it to a small set of candidate orderings chosen from a warm-start split of a few hundred labeled examples. The online combiner is a multinomial logistic stacker over the top-$k$ union, updated with the constant-time mirror descent step. The stopping models share its updates.
The second part is theoretical. We will prove the $\kappa$-free leading-term regret for the two-stage case (stop vs. run one more model) under censored feedback. We will then state the multi-stage bound as a conjecture unless the proof goes through.
The third part is diagnostic. We will record which stages the learner stops paying for, and how quickly it does so, and compare this pruning with static performance gates.
Baselines
The do-nothing references are the single best base model and the full probability-stacked ensemble run on every query. These bound accuracy from below and above, and the full ensemble also bounds cost from above.
The heuristic cascade runs models cheapest-first and exits when the latest model's top softmax probability passes a threshold. That threshold is tuned on the same warm-start split the other methods receive.
The strongest existing method is LazyStack, trained offline. Its reported results are 38× speedup at 97% of full-ensemble accuracy on NSL-KDD and 2.5× speedup at 97% accuracy on CIFAR-100 (LazyStack). There is no reported numeric result on Lacuna for LazyStack on ImageNet-1K, AG News or SST-5. We will run LazyStack twice. The first run gives it its full labeled validation set, which is its native, favorable condition. The second gives it only our warm-start split, so the comparison isolates how much offline data each method needs. For language models, the reference is FrugalGPT on HEADLINES, which reports up to 98.3% cost reduction while matching the best individual model (FrugalGPT).
Two ablations isolate the key ingredient. Greedy online uses the same features, combiner and update rule as our method, with the exploration bonus removed. It is plain online refitting of LazyStack-style stoppers. Flat-penalty optimism keeps the bonus but uses the worst-case slope instead of the local slope $\mu'$, which approximates classical GLM-UCB.
All methods get the same base models, the same label stream, the same per-query costs and the same hyperparameter search budget. Our method beats the field if two things hold. Under stationary streams, it matches offline LazyStack's accuracy–cost curve within seed noise while using only the warm-start labels. Under shift, it achieves lower cumulative error-plus-$\lambda$-cost than greedy online, and lower cost than flat-penalty optimism at equal accuracy.
Why not just…?
Why not just retrain LazyStack's substackers online as labels arrive? This is the real threat, and it is the greedy ablation. If prefixes from deeper stages keep being sampled anyway, for example because the threshold is conservative, the censoring bias may never bite and greedy refitting will match us. The shift experiments below test this directly. If greedy matches us across shifts, we will report that exploration is unnecessary and that the contribution reduces to an online stacker.
Why not just recalibrate the confidence threshold online, for example with temperature scaling on recent labels? Recalibration fixes miscalibration of the current combined answer. It still never observes what deeper models would have said on queries it exits. It is also a special case of our learner with $d=1$ and no bonus, so it appears as a further ablation. LazyStack's results already show that using all earlier outputs beats thresholding the latest one alone.
Why not just use standard GLM-UCB or Thompson sampling? The logistic bandit papers show that the classical bound scales with $\kappa$, which grows exponentially with how sharp the scores are (Improved Optimistic Algorithms for Logistic Bandits). Confident exits live in exactly that regime. We expect classical optimism to keep running expensive models on easy queries. The sharpness sweep below measures this rather than assuming it.
Proposed Experiments
The benchmarks follow LazyStack's suite: NSL-KDD, CIFAR-100, ImageNet-1K, AG News and SST-5, with HEADLINES for a language-model cascade. Each dataset is replayed as a stream after a small labeled warm-start. Correctness labels are revealed for a fixed fraction of queries.
We create shift in two ways. The first holds out some classes or categories from the warm-start portion and introduces them mid-stream. The second reorders the stream by a feature-based clustering. The metrics are cumulative regret against the best fixed policy in hindsight, accuracy, average cost per query, and the fraction of queries reaching each stage.
Three checks decide the question. First, in the shift streams, greedy online should show a lasting accuracy drop after the shift on inputs where deeper models become necessary, while our method should recover. If this does not appear, the core claim fails.
Second, a sharpness sweep scales base-model temperatures so that stopping decisions move further into the sigmoid tails. Flat-penalty optimism's cost should grow with sharpness, while ours stays flat. This is the empirical signature of the regret claim.
Third, on ImageNet-1K, the top-$k$ summary features should narrow LazyStack's reported many-class weakness. We regard this as the least certain outcome, and will report it whichever way it goes.
A secondary check compares the set of stages the learner stops paying for with the set excluded by the 10% performance-gap rule from Determine-Then-Ensemble.
References
- Improved Optimistic Algorithms for Logistic Bandits
- Instance-Wise Minimax-Optimal Algorithms for Logistic Bandits
- Online (Multinomial) Logistic Bandit: Improved Regret and Constant Computation Cost
- Unifying Stacking and Cascading for Efficient Ensemble Inference
- FrugalGPT: How to Use Large Language Models While Reducing Cost and Improving Performance
- RouteLLM: Learning to Route LLMs from Preference Data
- Beyond Gemini-3-Pro: Revisiting LLM Routing and Aggregation at Scale
- Stacked generalization: when does it work?
- Determine-Then-Ensemble: Necessity of Top-k Union for Large Language Model Ensembling