A deep ensemble runs every member model on every input and averages their predictions. This is reliable, but it multiplies inference cost by the number of members, even for inputs where the first one or two members already settle the answer. We propose running ensemble members one at a time, cheapest first, and stopping as soon as a calibrated rule says the remaining members almost certainly would not change the ensemble's final prediction. The guarantee is stated relative to the full ensemble: across test inputs, the stopped prediction differs from what the full ensemble would have output at most an $\alpha$ fraction of the time. Because that target is the full ensemble's own output rather than a human label, the rule can be calibrated, and recalibrated after distribution shift, on unlabeled data simply by running the full ensemble on a sample of inputs.
This matters because the existing ways of cutting ensemble cost each give something up. Static pruning keeps a fixed subset for every input. Sparse ensembles save FLOPs that ordinary GPUs cannot turn into wall-clock time. Learned cascades save compute but give no statement about how often they deviate from the system they replace. A stopping rule that uses the partial ensemble's own agreement, and whose error rate relative to the full ensemble is controlled without labels, would let a practitioner deploy "the ensemble" at roughly the cost of a small fraction of it and know how faithful the substitute is.
Core Claim
Order the $M$ members by cost. After $k$ members have run, let $\bar p_k(x)$ be their averaged class probabilities and $\hat y_k(x)$ its top class. For $k<M$, compute a stopping score $s_k(x)$ from the partial ensemble: the margin of $\bar p_k$, the members' pairwise disagreement so far, and how much weight $(M-k)/M$ the unrun members still carry. Stop at the first $k$ with $s_k(x)\ge\lambda$, and otherwise run all $M$. The loss for one input is
$$ \ell(x;\lambda)=\mathbb{1}\left[\hat y_{\tau_\lambda(x)}(x)\neq \hat y_M(x)\right], $$
where $\tau_\lambda(x)$ is the stopping step. We choose $\lambda$ with Conformal Risk Control. That method calibrates a threshold so that the expected value of a bounded loss that shrinks monotonically as the threshold grows stays below a target $\alpha$, with finite-sample validity. It reports achieved risks of 0.0987 at target 0.1 on polyp segmentation and 0.0499 at target 0.05 on ImageNet.
Our loss is not automatically monotone, because a prediction can flip and flip back as members are added. We therefore control its running maximum over larger thresholds, which is monotone and bounds the true loss from above. This makes the guarantee conservative but valid. It holds under exchangeability between calibration and test inputs, and it controls disagreement with the full ensemble, not accuracy directly. A second variant uses labels and controls excess error instead: the loss fires only when the stopped prediction is wrong and the full ensemble is right.
There is also a label-free, zero-risk reference point. If the margin of $\bar p_k$ exceeds $2(M-k)/M$, no outputs the remaining members could produce can change the argmax, so the prediction is certified. We expect the calibrated rule to stop much earlier than this certified rule. The size of that gap measures how much the statistical guarantee buys over worst-case reasoning.
Relation to Prior Work
Four lines of prior work motivate the proposal, because each found the cost problem and left the adaptive, guaranteed version open:
- Pareto Ensemble Pruning searches for a fixed sub-ensemble that trades error against size.
- Liquid Democracy for Low-Cost Ensemble Pruning drops weak members during training and passes their votes to stronger ones.
Both produce one subset for all inputs. We keep every member available and decide per input.
- Early Exiting with Ensemble Internal Classifiers treats the intermediate-layer classifiers of one BERT or ALBERT model as a voting committee and exits when votes cross a hand-set threshold.
We move this idea from the layers of one network to separate, independently trained models, and we replace the heuristic threshold with a calibrated one.
- Learning to Cascade is the closest competitor. It retrains the cheap model with a loss that knows the specific backup's errors, cutting multiply-accumulate operations by 55% in a MobileNetV2→ResNet18→ResNet152 cascade on CIFAR-100 while improving accuracy.
Our method differs in three ways. It needs no retraining. It treats the partial ensemble's agreement, not a single model's confidence, as the stopping signal. It states a controlled deviation rate.
- Efficient Dynamic Ensembling for Multiple LLM Experts learns a reinforcement-learning controller to chain language-model experts.
It is expensive to train and has no error guarantee. We deliberately avoid a learned controller.
Two papers constrain the design:
- When are ensembles really effective? shows that ensemble gains track the ratio of member disagreement to member error, and that this ratio collapses for large models trained to zero training error.
For our method, this cuts both ways. Low disagreement means early stopping will be cheap and faithful, but also that the full ensemble adds little. We will report savings together with the full ensemble's gain over its best single member, so that low-disagreement pools are not mistaken for wins.
- Deep Ensembling with No Overhead for either Training or Testing (FreeTickets) cuts FLOPs through unstructured sparsity, but notes that standard GPUs do not realize these savings.
Our savings come from skipping dense models entirely, so we measure wall-clock time, not only FLOPs.
Conformal Prediction for Ensembles supplies a later extension rather than the core method. It aggregates all members' scores into tighter prediction sets (set size 34.0 versus 69.1 for naive ensembling on ImageNet), but requires every member to run. A natural follow-up is to control the probability that the stopped prediction falls outside the full ensemble's aggregated set.
Research Program
The first component is the stopping rule itself. We will compare three stopping scores:
- running margin alone;
- margin plus disagreement among the members run so far;
- margin scaled by the remaining weight $(M-k)/M$.
We will also compare member orderings: by cost, and by a greedy order chosen on a held-out split to maximize early agreement with the full ensemble. The ordering, the score, and $\lambda$ are each fit on separate data splits so the guarantee stays valid.
The second component is calibration under shift. Because the disagreement loss needs no labels, we can recalibrate $\lambda$ on a few thousand unlabeled deployment inputs by running the full ensemble on them. We will test whether this restores the target rate after shift, where a threshold calibrated on clean data may fail.
The third component is honest cost accounting:
- expected member evaluations per input;
- multiply-accumulate operations;
- wall-clock latency at batch size 1 and at realistic batch sizes, where early-stopped inputs leave the batch.
Baselines
The naive reference is the full ensemble, which runs all members on every input. It fixes the accuracy ceiling and the cost we try to cut. Beside it we report the best single member at matched cost, and the cheapest member alone, which is the floor.
The strongest existing method is Learning to Cascade. Its strongest reported number is a 55% cost reduction with improved accuracy in the three-model cascade on CIFAR-100, plus 31% and 36% reductions without accuracy loss for ResNet18 and ResNet152. We will reimplement it on the same member pool and data splits, with the same number of tuning trials for its loss weight and cost parameter as we spend choosing our stopping score and ordering. Beating it means one of two outcomes. Our method could match its accuracy at equal or lower measured cost with no retraining. Or, at equal cost, it could meet the stated deviation rate across test resamplings and under shift in cases where Learning to Cascade's validation-tuned threshold does not.
For static pruning we run Pareto Ensemble Pruning on the same validation predictions. We pick the frontier point whose cost equals our expected cost and compare accuracy and agreement with the full ensemble. Its reported result is best test error or smallest size in 60% of 30 UCI datasets. That result is on tabular pools, so we do not reuse it as a target number.
For vertical early exiting we compare with the voting exit of Early Exiting with Ensemble Internal Classifiers on SST-2. It reports 93.5% accuracy at a 1.5x speedup with ALBERT. The fair comparison fixes total parameters and latency budget, so that a pool of small, different encoders competes against one large backbone with exits.
Three ablations isolate the key ingredients:
- The certified margin rule has zero statistical risk. The gap between it and our rule is what calibration buys.
- The same stopping score with $\lambda$ tuned for average accuracy on validation, without conformal calibration, tests whether the guarantee costs any efficiency.
- A single-model-confidence score, versus our partial-ensemble score, tests whether agreement among members is the useful signal.
Why not just…?
Why not just threshold the cheap model's softmax, tuned on validation? This is the real threat. On in-distribution test data, a well-tuned threshold may reach nearly the same cost-accuracy curve. The proposal does not claim to beat it on that curve alone. It claims to beat it on reliability. Learning to Cascade's own analysis shows plain confidence thresholds misjudge when escalation helps, but a tuned threshold carries no statement about its deviation rate. We will report, over many random calibration and test splits and on shifted data, how often each method exceeds the target deviation rate. If the tuned threshold stays within the target as often as ours and costs the same, the contribution reduces to label-free recalibration, and we will say so.
Why not just prune the ensemble to a fixed smaller subset? Static subsets pay the same price on easy and hard inputs. The disagreement-error analysis in When are ensembles really effective? implies ensemble gains concentrate on the inputs where members disagree, which a fixed subset cannot target. The Pareto Ensemble Pruning comparison at matched expected cost settles this directly. If a fixed subset matches our accuracy at equal cost, adaptivity is not worth it for that pool.
Why not just train one larger model? At a fixed parameter budget on Fashion-MNIST, To Ensemble or Not Ensemble found that a single large MLP beat an independently trained small ensemble. So this can win. Our setting differs: the members already exist, as is common when pooling pretrained models, and the question is how to use them cheaply. We still include a single model matched to our expected cost. Wherever it matches the stopped ensemble, we report that ensembling was not warranted for that pool.
Proposed Experiments
On CIFAR-100 we use the MobileNetV2, ResNet18 and ResNet152 pool from Learning to Cascade, plus a five-seed ResNet deep ensemble. On ImageNet we use a heterogeneous pool of five pretrained classifiers spanning a roughly tenfold cost range. On CIFAR-10 we calibrate on clean data and test on CIFAR-10-C and CIFAR-10.1, with and without unlabeled recalibration. On SST-2, TREC and AG's News we use a pool of differently pretrained encoders.
For each setting we report:
- the achieved deviation rate against targets $\alpha\in\{0.01, 0.02, 0.05\}$ over 1,000 random splits;
- accuracy;
- expected member evaluations, operations and measured latency;
- the full ensemble's accuracy gain over its best member, together with the pool's disagreement-to-error ratio.
The results would settle the question in one of the following ways:
- Success. The rule meets the target deviation rate in distribution and, after unlabeled recalibration, under corruption. It halves or better the cost of the full ensemble on pools where the ensemble actually helps. It stops well before the certified rule.
- Failure. Any one of the following would count against the method: a validation-tuned threshold matches both cost and reliability, a fixed Pareto-pruned subset matches accuracy at equal cost, or savings appear only on pools whose ensemble gain is negligible.
References
- Conformal Risk Control
- Pareto Ensemble Pruning
- Liquid Democracy for Low-Cost Ensemble Pruning
- Early Exiting with Ensemble Internal Classifiers
- Learning to Cascade: Confidence Calibration for Improving the Accuracy and Computational Cost of Cascade Inference Systems
- Efficient Dynamic Ensembling for Multiple LLM Experts
- When are ensembles really effective?
- Deep Ensembling with No Overhead for either Training or Testing: The All-Round Blessings of Dynamic Sparsity
- Conformal Prediction for Ensembles: Improving Efficiency via Score-Based Aggregation
- To Ensemble or Not Ensemble: When Does End-to-End Training Fail?