Research map / Learning theory and algorithms / Prediction and decision losses
Free Lunch in the Forest: Functionally-Identical Pruning of Boosted Tree Ensembles
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Proposes FIPE, an iterative exact-certified pruning method that removes and reweights trees in boosted/bagged tree ensembles so the prediction function is identical over the entire feature space.
Problem
Tree ensembles (boosting, random forests) are accurate but large, slow at inference, and hard to interpret; existing pruning methods trade accuracy for size with no guarantee on test behavior.
Approach
Prune ensembles to a reweighted subset that is provably functionally identical to the original on the whole input space, by alternating a linear/combinatorial pruner over a finite point set with a MILP separation oracle that searches for counterexample points via leaf-path variables; the ell-1 variant is an LP approximation.
Key results
- FIPE with l1 pruning keeps 100% test faithfulness across all datasets and ensemble sizes 50-1000 while reducing AdaBoost ensembles to roughly 10-20% of their size (e.g., 37% at M=50 and 19% at M=200 for average relative size across ensembles).
- Across 1000-learner AdaBoost ensembles, FIPE retains about 85.7% average accuracy, while DREP, IC and IMD baselines at matched size lose accuracy (80.7%, 79.0%, 38.3% respectively).
- Certification of functional identity required fewer than 200 oracle calls even for large ensembles, and l1 relaxation matched l0 pruning sizes for all but one dataset with much faster runtime.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use FIPE-L1 instead of the non-faithful pruning baselines | AdaBoost ensembles · all datasets (mean), M=100 | accuracy: 81.68% -> 85.55% | Helped |
| Use FIPE-L1 instead of the non-faithful pruning baselines | AdaBoost ensembles · all datasets (mean), M=200 | accuracy: 81.25% -> 85.70% | Helped |
| Use FIPE-L1 instead of the non-faithful pruning baselines | AdaBoost ensembles · all datasets (mean), M=500 | accuracy: 80.72% -> 85.83% | Helped |
| Use FIPE-L1 instead of the non-faithful pruning baselines | AdaBoost ensembles · all datasets (mean), M=1000 | accuracy: 80.70% -> 85.66% | Helped |
| Replace the exact ∥·∥0 pruning objective with the approximate ∥·∥1 objective (ablation) | FIPE · FICO | pruning time: 456 -> 30 | Helped |
| Replace the exact ∥·∥0 pruning objective with the approximate ∥·∥1 objective (ablation) | FIPE · Seeds | number of active learners: 9 -> 10 | Hurt |
| Increase the original ensemble size from 50 to 1000 learners (ablation) | FIPE-L1-pruned AdaBoost · 11 datasets (mean) | number of active learners | Mixed |
Surprising findings
- Close to 90% of AdaBoost base learners are superfluous and can be removed when remaining learners are reweighted, with some late learners receiving very large weights.
- Non-faithful baselines (DREP, IC, IMD) at matched size lose accuracy and faithfulness, showing pruning without a guarantee degrades performance.
Limitations
- Exact l0 formulation struggles to scale to large datasets and big ensembles; l1 relaxation is approximate and not guaranteed minimal.
- Faithfulness is enforced on the whole feature space, which limits compression compared to faithfulness on plausible inputs; the problem is NP-hard.
Experimental setup
Datasets: Seeds Ionosphere Breast-Cancer-Wisconsin Pima-Diabetes Spambase COMPAS-ProPublica PoL FICO House-16H HTRU2 ELEC2
Benchmarks: Seeds Ionosphere Breast-Cancer-Wisconsin Pima-Diabetes Spambase COMPAS-ProPublica PoL FICO House-16H HTRU2 ELEC2
Metrics: number of active learners (l0 norm) faithfulness (FI) on test set test accuracy oracle calls runtime
Baselines: DREP IC IMD
Builds on: Vidal, Pacheco, and Schiffer (2020) faithful pruning Parmentier and Vidal (2021) counterfactual MILP Kantchelian et al. (2016) classifier evasion
Closest papers by meaning
- MEPSI: An MDL-Based Ensemble Pruning Approach with Structural Information (AAAI 2024 · similarity 0.88)
- Compressing tree ensembles through Level-wise Optimization and Pruning (ICML 2025 · similarity 0.88)
- Minimax Rates and Spectral Distillation for Tree Ensembles (NeurIPS 2026 · similarity 0.87)
- Ensemble Pruning for Out-of-distribution Generalization (ICML 2024 · similarity 0.86)
- GDeR: Safeguarding Efficiency, Balancing, and Robustness via Prototypical Graph Pruning (NeurIPS 2024 · similarity 0.85)
- GRANDE: Gradient-Based Decision Tree Ensembles for Tabular Data (ICLR 2024 · similarity 0.85)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.