# MABSplit: Faster Forest Training Using Multi-Armed Bandits

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

## Key facts

- Cited by 4 papers in the map (data through 14 Oct 2026).
- Builds on 13 of its 77 references that are in the map.
- First posted on arXiv 14 Dec 2022.

## Builds on (most cited first, 13 of 13)

- [XGBoost: A Scalable Tree Boosting System](https://mlsanity.com/paper/1603.02754/) (2016)
- [Beyond the Imitation Game: Quantifying and extrapolating the capabilities of language models](https://mlsanity.com/paper/2206.04615/) (2022)
- [GFlowNet Foundations](https://mlsanity.com/paper/2111.09266/) (2021)
- [Hyperparameters and Tuning Strategies for Random Forest](https://mlsanity.com/paper/1804.03515/) (2018)
- [NL-Augmenter: A Framework for Task-Sensitive Natural Language Augmentation](https://mlsanity.com/paper/2112.02721/) (2021)
- [Extremely Fast Decision Tree](https://mlsanity.com/paper/1802.08780/) (2018)
- [CLTune: A Generic Auto-Tuner for OpenCL Kernels](https://mlsanity.com/paper/1703.06503/) (2017)
- [Medoids in almost linear time via multi-armed bandits](https://mlsanity.com/paper/1711.00817/) (2017)
- [Ultra Fast Medoid Identification via Correlated Sequential Halving](https://mlsanity.com/paper/1906.04356/) (2019)
- [Adaptive Monte Carlo Multiple Testing via Multi-Armed Bandits](https://mlsanity.com/paper/1902.00197/) (2019)
- [Approximate Function Evaluation via Multi-Armed Bandits](https://mlsanity.com/paper/2203.10124/) (2022)
- [FastForest: Increasing Random Forest Processing Speed While Maintaining Accuracy](https://mlsanity.com/paper/2004.02423/) (2020)
- [Image Compression and Classification Using Qubits and Quantum Deep Learning](https://mlsanity.com/paper/2110.05476/) (2021)

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

- [Medoid splits for efficient random forests in metric spaces](https://mlsanity.com/paper/2306.17031/) (2023)
- [BanditPAM++: Faster k-medoids Clustering](https://mlsanity.com/paper/2310.18844/) (2023)
- [Bayesian Decision Trees via Tractable Priors and Probabilistic Context-Free Grammars](https://mlsanity.com/paper/2302.07407/) (2023)
- [Multi-Armed Bandits-Based Optimization of Decision Trees](https://mlsanity.com/paper/2508.05957/) (2025)

## Abstract (arXiv)

Random forests are some of the most widely used machine learning models today, especially in domains that necessitate interpretability. We present an algorithm that accelerates the training of random forests and other popular tree-based learning methods. At the core of our algorithm is a novel node-splitting subroutine, dubbed MABSplit, used to efficiently find split points when constructing decision trees. Our algorithm borrows techniques from the multi-armed bandit literature to judiciously determine how to allocate samples and computational power across candidate split points. We provide theoretical guarantees that MABSplit improves the sample complexity of each node split from linear to logarithmic in the number of data points. In some settings, MABSplit leads to 100x faster training (an 99% reduction in training time) without any decrease in generalization performance. We demonstrate similar speedups when MABSplit is used across a variety of forest-based variants, such as Extremely Random Forests and Random Patches. We also show our algorithm can be used in both classification and regression tasks. Finally, we show that MABSplit outperforms existing methods in generalization performance and feature importance calculations under a fixed computational budget. All of our experimental results are reproducible via a one-line script at https://github.com/ThrunGroup/FastForest.