A boosted ensemble adds up many small models, called base learners, one after another. Every test example pays for every one of them, even when the first few already settle the answer. Two lines of work each handle half of this problem. Capacity-conscious boosting can safely mix cheap stumps with expensive deep trees and still come with generalization guarantees, but it evaluates the whole ensemble on every input. Cost-aware and early-exit methods cut per-example compute, but either lack guarantees or apply only to neural networks. We propose training a boosted ensemble together with a learned rule for when to stop adding base learners. The key change is that each new tree is fit only on the examples that will actually reach it. As a result, the training objective itself decides where to put expensive capacity: deep trees become affordable once they sit late in the sequence and only hard examples ever evaluate them.
In plain terms, the ensemble learns an ordering from cheap to expensive and a per-example "you're done" signal, and each tree specializes to the examples still unresolved at its position. The claim to be tested has two parts. First, this survivor-aware training beats training an ensemble normally and adding early stopping afterwards. Second, the gap is largest on data where hard examples form a distinct region rather than a thin band near the decision boundary. That is exactly the regime where Boosting with Abstention showed that thresholding a model's confidence after training is the wrong tool.
Core Claim
Deep Boosting (DeepBoost) and its multi-class extension, Multi-Class Deep Boosting, supply the method we reuse. At each boosting round, DeepBoost chooses both the tree depth and the tree. It penalizes each chosen tree by the Rademacher complexity (a measure of how well a function family can fit random noise) of its depth class, weighted by the tree's ensemble weight. Deep trees are selected only when they earn their extra complexity. These papers also motivate the gap: the authors optimize capacity at training time, yet inference is all-or-nothing.
Cost efficient gradient boosting (CEGB) makes individual trees cheap on average. It grows them best-first under a penalty on split nodes traversed and features acquired, so easy inputs take short paths. CEGB still evaluates every tree, and its penalty is an empirical heuristic with no capacity bound. The early-exit neural literature, BEEM and latency-aware early exit, stops a sequence of computations per input. BEEM stops using agreement between successive exits. The latency-aware method tunes thresholds under a latency budget. Both treat the underlying model as fixed or layer-structured, not as a sequence of learners whose capacity is chosen during training.
The proposal combines three ingredients that no single prior method has together:
- DeepBoost's per-round choice of depth class.
- A learned stopping function at each round, in the spirit of the explicit abstention functions of Boosting with Abstention.
- A cost term weighted by the probability that an example is still running.
Research Program
Let $f_t(x)=\sum_{s\le t}\alpha_s h_s(x)$ be the ensemble after $t$ rounds. Here $h_s$ is drawn from a depth class $\mathcal{H}_{p(s)}$ and $\alpha_s$ is its weight.
At each round a simple stopping function $r_t(x)\in[0,1]$ gives the probability of stopping after round $t$. It is a small tree over the current margin $|f_t(x)|$ and a few raw features. The survival probability of reaching round $t$ is $S_t(x)=\prod_{s<t}(1-r_s(x))$. The ensemble's prediction is the partial sum at the stopping round, taken in expectation over stopping. We minimize
$$\frac{1}{m}\sum_{i=1}^m \sum_{t=1}^T S_t(x_i)\,r_t(x_i)\,\Phi\big(y_i f_t(x_i)\big) \;+\; \sum_{t=1}^T\big(\lambda\,\mathcal{R}_m(\mathcal{H}_{p(t)})+\beta\big)|\alpha_t| \;+\; \mu\,\frac{1}{m}\sum_{i=1}^m\sum_{t=1}^T S_t(x_i)\,c_t(x_i),$$
where the terms are as follows. $\Phi$ is DeepBoost's exponential or logistic surrogate loss. $\lambda$ and $\beta$ are DeepBoost's capacity and sparsity weights. $c_t(x)$ is the number of split nodes example $x$ traverses in tree $t$, which is CEGB's evaluation-cost measure. $\mu$ prices compute. By convention $r_T\equiv 1$, so every example stops by the last round.
The third term is what makes a depth-10 tree cheap when few examples survive to its round. The first term means tree $t$ is fit to residuals weighted by $S_t$, so it specializes to the examples still unresolved at its position. Training alternates two steps. The first is a DeepBoost-style coordinate step choosing $(p,h,\alpha)$ with survivor-weighted gradients. The second refits the stopping functions with the trees held fixed.
The theoretical work has a specific target. We aim for a margin bound for the stopped predictor in which the DeepBoost term $\sum_t\alpha_t\mathcal{R}_m(\mathcal{H}_{p(t)})$ appears alongside a term for the stopping family's complexity. We conjecture that the extra term grows only logarithmically in $T$, since the stopped predictor selects one of $T$ partial sums. We will report honestly whether survival weighting can tighten the capacity term, or whether all trees must be paid for uniformly because some examples reach them all.
Baselines
The naive reference point is DeepBoost trained normally and evaluated on every tree. It fixes the accuracy ceiling and the cost ceiling. We use the authors' tuning protocol for $\lambda$ and $\beta$.
The strongest existing competitor on accuracy per unit cost is CEGB. It is the only method in the file that directly optimizes tree-evaluation and feature cost, and its paper reports better accuracy–cost curves than the budgeted pruning methods GREEDYMISER and BUDGETPRUNE on Yahoo! LTR, MiniBooNE, Forest Covertype and HEPMASS. The file contains no numeric values for these curves, so no reported result was found on Lacuna for CEGB's error or cost numbers on any of these datasets. We will reproduce CEGB with the same number of rounds, the same data splits, and the same hyperparameter search budget for its cost weight as we give to $\mu$.
A second strong competitor combines CEGB with post-hoc stopping. We train CEGB, then add a margin-threshold exit whose threshold is tuned for a latency target in the manner of the latency-aware early-exit paper. This composite is the most dangerous comparison, because it stacks cheap trees and early stopping without our joint training.
Two ablations isolate our key ingredient. The first uses our full model structure, including learned stopping functions and the cost term, but trains the trees with uniform rather than survivor weights and fits the stopping functions afterwards. The second replaces the learned stopping functions with margin thresholds, keeping survivor-weighted training.
Beating a baseline means one of two things on at least four of the six tabular datasets, at matched mean split-nodes-per-example, with significance across ten seeds:
- strictly lower test error at the same cost, or
- at least 30% lower cost at equal error.
Why not just…?
Why not just cap all trees at depth 2 or 3? Uniformly shallow trees give predictable latency. Deep Boosting reports that its mixed-depth ensembles beat fixed-depth AdaBoost on the ocr17-mnist and ocr49-mnist datasets (significant at the 2% level) while using fewer total nodes than $\ell_1$-regularized AdaBoost. Shallow ensembles can therefore cost more overall, not less. We will still include fixed depths 2, 4 and 6 in every accuracy–cost plot, since a shallow ensemble with few rounds could dominate at the low-cost end.
Why not just train a normal ensemble, sort its trees by cost, and stop when the margin is large? This is the real threat. It may capture most of the savings. Boosting with Abstention gives a reason to expect it falls short: margin thresholds can only reject a narrow band around the decision boundary, and its learned rejection functions achieved lower rejection loss than confidence thresholding on credit, climate, skin and medical. That evidence covers binary classification with stumps, not stopping deep-tree sequences. Our first ablation settles the question directly. If the post-hoc version matches the full method, we will report that survivor-weighted training is unnecessary and reframe the contribution around the bound.
Why not just use CEGB, which already makes deep trees cheap? CEGB shortens paths within each tree but has a floor proportional to the number of trees, since every tree is evaluated. It has no mechanism for making later trees specialists. The CEGB-plus-exit composite tests whether bolting stopping onto CEGB closes the gap. We expect it to stay competitive on Yahoo! LTR, where feature costs dominate, because our cost term covers only split nodes unless we add CEGB's feature term. We plan to add that term there.
Proposed Experiments
The primary benchmarks are CEGB's datasets, MiniBooNE, Forest Covertype, HEPMASS-1000 and Yahoo! LTR, plus the multi-class UCI sets from Multi-Class Deep Boosting, Pendigits, Letters and Satimage, using its $F_{\text{maxsum}}$ surrogate. We report full accuracy–cost curves, sweeping $\mu$ and each baseline's cost knob, with mean and 95th-percentile split nodes per example.
We then run three decisive checks.
The first is a fraction-reaching diagnostic. We plot the depth of tree $t$ against the fraction of test examples that reach round $t$. The mechanism predicts that deep trees concentrate late and are reached by a minority. If depth is flat across rounds, the mechanism is not doing what we claim.
The second is an overthinking test, following BEEM's observation that stopping early can beat full evaluation. We check whether the stopped predictor's error is below that of the same ensemble run to completion on the stopped examples.
The third is a shift test addressing the threshold brittleness noted for the latency-aware early-exit method. We train on one Covertype region and test on others, measuring how far realized cost departs from the target for learned stopping functions versus tuned margin thresholds.