Papers › A Case for Library-Level k-Means Binning in Histogram Gradient-Boosted Trees
A Case for Library-Level k-Means Binning in Histogram Gradient-Boosted Trees
Asher Labovich
Modern gradient-boosted decision trees (GBDTs) accelerate split finding with histogram-based binning, which reduces complexity from O(N) to O(B) given a fixed bin budget B. However, the predominant quantile binning strategy-designed to distribute data points evenly among bins-may overlook critical boundary values that could enhance predictive performance. In this work, we propose replacing quantile binning with a k-means discretizer initialized with quantile bins. We test this swap on 33 OpenML tasks plus synthetics that control for modality, skew, and bin budget. Across 18 regression datasets, k-means shows no statistically significant losses at the 5% level and wins in four cases-most strikingly a 55% MSE drop on one particularly skewed dataset-even though k-means' mean reciprocal rank (MRR) is slightly lower (0.65 vs 0.72). On the 15 classification datasets the two methods are statistically tied (MRR 0.70 vs 0.68) with gaps ≤0.2 pp. Synthetic experiments confirm consistently large MSE gains-typically >20% and rising to 90% as outlier magnitude increases or bin budget drops. We find that k-means keeps error on par with exact splitting when extra cuts add little value, yet still recovers key split points that quantile overlooks. As such, we advocate for a built-in bin_method=k-means flag, especially in regression tasks and in tight-budget settings such as the 32-64-bin GPU regime-because it is a "safe default" with large upside, yet adds only a one-off, cacheable overhead (≈ 2s to bin 10M rows on one core).
Code
Repository list and official/mentioned flags are the archive's, frozen 2025-07-28. Reachability, where shown, is from one Syntology probe window (2026-09-16 to 2026-09-18); repositories not probed show nothing. GitHub stars are not tracked.
Code Syntology ran Syntology
Not run by Syntology. Nothing on this page verifies that the listed code works.
Results from the paper archive 2025-07-28
No leaderboard rows for this paper in the archive.
Report a problem or propose a change · a person checks every report against the paper or source before anything changes; decisions are listed on /corrections