Instance-Adaptive Lazy Inference for Tree Ensembles via Stability Surrogates and Residual-Capacity Certificates

Treeensembles usually evaluate every tree or boosting stage for every input, even when the partial prediction has already stabilized. We study inference-time lazy evaluation for pre-trained random forests and gradient-boosted decision trees. LazyRF stops random-forest evaluation using a Bayesian vote-stability score for the current leading class. LazyGBM uses a deterministic residual-capacity certificate: if the current class separation exceeds twice the maximum possible contribution of later stages, the final predicted class is guaranteed unchanged. At the default LazyRF threshold, LazyRF reduces evaluated trees by 60–90% across four benchmarks and 30 seeds while passing a paired-seed equivalence check with a 0.002 accuracy margin against full random-forest evaluation. For LazyGBM, the certified rule is conservative: certificate-only savings are 1–12% in the reported ablations, while more aggressive heuristic exits are reported separately and treated as empirically audited prototypes. We, therefore, use evaluated trees or stages as the main cost measure. Runtime measurements provide Python-prototype context rather than hardware-independent latency claims.