# GPU-acceleration for Large-scale Tree Boosting

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

## Key facts

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

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

- [Quantized Training of Gradient Boosting Decision Trees](https://mlsanity.com/paper/2207.09682/) (2022)
- [Predicting Different Types of Subtle Toxicity in Unhealthy Online Conversations](https://mlsanity.com/paper/2106.03952/) (2021)
- [Temporal Knowledge Distillation for Time-Sensitive Financial Services Applications](https://mlsanity.com/paper/2312.16799/) (2023)
- [Investigating the Generalizability of Physiological Characteristics of Anxiety](https://mlsanity.com/paper/2402.15513/) (2024)
- [Distributionally Robust Multi-Output Regression Ranking](https://mlsanity.com/paper/2109.12803/) (2021)
- [Prediction of fish location by combining fisheries data and sea bottom temperature forecasting](https://mlsanity.com/paper/2205.02107/) (2022)
- [A Case for Library-Level k-Means Binning in Histogram Gradient-Boosted Trees](https://mlsanity.com/paper/2505.12460/) (2025)
- [Parameter Space Analysis through Guided Visual Interpolations](https://mlsanity.com/paper/2509.19202/) (2025)

## Abstract (arXiv)

In this paper, we present a novel massively parallel algorithm for accelerating the decision tree building procedure on GPUs (Graphics Processing Units), which is a crucial step in Gradient Boosted Decision Tree (GBDT) and random forests training. Previous GPU based tree building algorithms are based on parallel multi-scan or radix sort to find the exact tree split, and thus suffer from scalability and performance issues. We show that using a histogram based algorithm to approximately find the best split is more efficient and scalable on GPU. By identifying the difference between classical GPU-based image histogram construction and the feature histogram construction in decision tree training, we develop a fast feature histogram building kernel on GPU with carefully designed computational and memory access sequence to reduce atomic update conflict and maximize GPU utilization. Our algorithm can be used as a drop-in replacement for histogram construction in popular tree boosting systems to improve their scalability. As an example, to train GBDT on epsilon dataset, our method using a main-stream GPU is 7-8 times faster than histogram based algorithm on CPU in LightGBM and 25 times faster than the exact-split finding algorithm in XGBoost on a dual-socket 28-core Xeon server, while achieving similar prediction accuracy.