# Vectorized Dynamic Histograms for Sparse Oblique Forests

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

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 15 of its 47 references that are in the map.
- First posted on arXiv 27 Feb 2026.

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

- [XGBoost: A Scalable Tree Boosting System](https://mlsanity.com/paper/1603.02754/) (2016)
- [YouTube-8M: A Large-Scale Video Classification Benchmark](https://mlsanity.com/paper/1609.08675/) (2016)
- [TabArena: A Living Benchmark for Machine Learning on Tabular Data](https://mlsanity.com/paper/2506.16791/) (2025)
- [ranger: A Fast Implementation of Random Forests for High Dimensional Data in C++ and R](https://mlsanity.com/paper/1508.04409/) (2015)
- [TabICLv2: A better, faster, scalable, and open tabular foundation model](https://mlsanity.com/paper/2602.11139/) (2026)
- [Tunability: Importance of Hyperparameters of Machine Learning Algorithms](https://mlsanity.com/paper/1802.09596/) (2018)
- [MLlib: Machine Learning in Apache Spark](https://mlsanity.com/paper/1505.06807/) (2015)
- [A Closer Look at TabPFN v2: Understanding Its Strengths and Extending Its Capabilities](https://mlsanity.com/paper/2502.17361/) (2025)
- [TabReD: Analyzing Pitfalls and Filling the Gaps in Tabular Deep Learning Benchmarks](https://mlsanity.com/paper/2406.19380/) (2024)
- [A Tensor Compiler for Unified Machine Learning Prediction Serving](https://mlsanity.com/paper/2010.04804/) (2020)
- [Sparse Projection Oblique Randomer Forests](https://mlsanity.com/paper/1506.03410/) (2015)
- [Yggdrasil Decision Forests: A Fast and Extensible Decision Forests Library](https://mlsanity.com/paper/2212.02934/) (2022)
- [Canonical Correlation Forests](https://mlsanity.com/paper/1507.05444/) (2015)
- [Forest Packing: Fast, Parallel Decision Forests](https://mlsanity.com/paper/1806.07300/) (2018)
- [Vectorized and performance-portable Quicksort](https://mlsanity.com/paper/2205.05982/) (2022)

## Abstract (arXiv)

Sparse oblique (SPO), part of the top-ranked configuration of Google's Yggdrasil Decision Forests (YDF), improve the accuracy while maintaining interpretability of Random Forests (RF) and Gradient Boosted Trees (GBT) by scanning a sparse linear combination of features instead of a single feature. Because projections are sampled at runtime, training is significantly slower, as pre-run optimizations such as presorting cannot be used. We overhaul SPO training in YDF, first by fixing inefficiencies in the released version, achieving 2-5x speedup, then by devising two novel methods, one aimed at GBTs and the other at RFs: (1) Hierarchical AVX2 and AVX-512-vectorized histogram filling speeds up typical GBT-depth trees by up to 1.6x in SPO-GBT and 2x for SPO-RF, and (2) runtime-dynamic histograms between vectorized histograms and exact splits, speeds up deeper, RF depth-typical trees (depths 16 to purity) by up to 1.6x with no detectable effect on accuracy. Our optimizations bring SPO-RF training time on par with YDF's axis-aligned RF. We extensively evaluate on 8 natural and 11 synthetic datasets of up to 10.5 million rows and 1.6 million features, from depth 6 to purity, and open-source the implementation.