# Pruning Random Forests for Prediction on a Budget

arXiv: https://arxiv.org/abs/1606.05060 · HTML: https://mlsanity.com/paper/1606.05060/

## Key facts

- Cited by 14 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 16 Jun 2016.

## Built on by (most cited first, 14 of 14)

- [A Survey on Active Feature Acquisition Strategies](https://mlsanity.com/paper/2502.11067/) (2025)
- [Stochastic Encodings for Active Feature Acquisition](https://mlsanity.com/paper/2508.01957/) (2025)
- [Costly Features Classification using Monte Carlo Tree Search](https://mlsanity.com/paper/2102.07073/) (2021)
- [Spatial State-Action Features for General Games](https://mlsanity.com/paper/2201.06401/) (2022)
- [A Collection of Quality Diversity Optimization Problems Derived from Hyperparameter Optimization of Machine Learning Models](https://mlsanity.com/paper/2204.14061/) (2022)
- [Simplification of Forest Classifiers and Regressors](https://mlsanity.com/paper/2212.07103/) (2022)
- [Fast Classification with Sequential Feature Selection in Test Phase](https://mlsanity.com/paper/2306.14347/) (2023)
- [Boosted Trees on a Diet: Compact Models for Resource-Constrained Devices](https://mlsanity.com/paper/2510.26557/) (2025)
- [Evolutionary Optimization of High-Coverage Budgeted Classifiers](https://mlsanity.com/paper/2110.13067/) (2021)
- [A Framework for Verifiable and Auditable Federated Anomaly Detection](https://mlsanity.com/paper/2203.07802/) (2022)
- [Scalable Online Disease Diagnosis via Multi-Model-Fused Actor-Critic Reinforcement Learning](https://mlsanity.com/paper/2206.03659/) (2022)
- [Online Decentralized Frank-Wolfe: From theoretical bound to applications in smart-building](https://mlsanity.com/paper/2208.00522/) (2022)
- [Simplifying Random Forests' Probabilistic Forecasts](https://mlsanity.com/paper/2408.12332/) (2024)
- [Trainable Bitwise Soft Quantization for Input Feature Compression](https://mlsanity.com/paper/2603.05172/) (2026)

## Abstract (arXiv)

We propose to prune a random forest (RF) for resource-constrained prediction. We first construct a RF and then prune it to optimize expected feature cost & accuracy. We pose pruning RFs as a novel 0-1 integer program with linear constraints that encourages feature re-use. We establish total unimodularity of the constraint set to prove that the corresponding LP relaxation solves the original integer program. We then exploit connections to combinatorial optimization and develop an efficient primal-dual algorithm, scalable to large datasets. In contrast to our bottom-up approach, which benefits from good RF initialization, conventional methods are top-down acquiring features based on their utility value and is generally intractable, requiring heuristics. Empirically, our pruning algorithm outperforms existing state-of-the-art resource-constrained algorithms.