How we got here

Gradient-boosted trees are the sum of forty years of small, sharp ideas. This page traces that lineage and marks where bonsai stands on each idea: adopted, adapted, declined, still open, or first done here.

This page supersedes the archived library notes for XGBoost, LightGBM, and CatBoost.

The diagram sketches the timeline. The table below carries the detail, one row per idea. Each row links into the guide, the decisions log, or a design note for how bonsai handles that idea.

timeline
    title The gradient-boosted-tree lineage
    section 1980s
        1984 : CART
    section 1990s
        1997 : AdaBoost
    section 2000s
        2001 : Gradient boosting machines
        2002 : Stochastic gradient boosting
    section 2010s
        2010 : Boruta (shadow features)
        2015 : DART
        2016 : Regularized objective : Weighted quantile sketch : Sparsity-aware split finding
        2017 : Histogram binning : GOSS : EFB : Leaf-wise growth : GPU histogram training
        2018 : Oblivious trees : Ordered target statistics : Ordered boosting : TreeSHAP
        2019 : Monotone and interaction constraints : scikit-learn HistGradientBoosting
    section 2020s
        2026 : Cross-architecture reproducibility : Device-resident objective : The single-card ceiling

The milestones

Year	Idea	Carried by	bonsai
1984	CART: Recursive binary splits, one prediction per leaf: the regression tree every booster still grows. (Breiman, Friedman, Olshen, and Stone, 1984)	XGBoost, LightGBM, CatBoost, bonsai	adopted
1997	AdaBoost: Combine many weak learners by reweighting the examples each one gets wrong. (Freund and Schapire, JCSS 1997)	none	adapted
2001	Gradient boosting machines: Fit each new tree to the gradient of the loss, so boosting becomes gradient descent in function space. (Friedman, Annals of Statistics 2001)	XGBoost, LightGBM, CatBoost, bonsai	adopted
2002	Stochastic gradient boosting: Subsample the rows before each tree, trading a little bias for lower variance and faster fits. (Friedman, CSDA 2002)	XGBoost, LightGBM, CatBoost, bonsai	adopted
2010	Boruta (shadow features): Select features by competing each against a permuted copy of itself, so the model calibrates its own importance noise floor. (Kursa and Rudnicki, JSS 2010)	none	declined
2015	DART: Drop a random subset of existing trees before each round, borrowing dropout from neural networks. (Rashmi and Gilad-Bachrach, AISTATS 2015)	XGBoost, LightGBM, bonsai	adopted
2016	Regularized objective: Score splits with a regularized second-order (Newton) objective and read leaf values from the same gradient and hessian sums. (Chen and Guestrin, KDD 2016)	XGBoost, LightGBM, CatBoost, bonsai	adopted
2016	Weighted quantile sketch: Propose split points from hessian-weighted quantiles, keeping approximate split finding accurate at scale. (Chen and Guestrin, KDD 2016)	XGBoost, bonsai	adapted
2016	Sparsity-aware split finding: Learn one default branch direction per split in a single pass over the present values, for missing and implicitly-zero entries. (Chen and Guestrin, KDD 2016)	XGBoost	declined
2017	Histogram binning: Bucket each feature into a few hundred bins, so splits search over bins, not raw values. (Ke et al., NeurIPS 2017)	XGBoost, LightGBM, CatBoost, bonsai	adopted
2017	GOSS: Keep every large-gradient row and subsample the rest, focusing the fit on the hard examples. (Ke et al., NeurIPS 2017)	LightGBM, bonsai	adopted
2017	EFB: Bundle mutually exclusive sparse features into one, shrinking the feature count with little accuracy loss. (Ke et al., NeurIPS 2017)	LightGBM	declined
2017	Leaf-wise growth: Grow the single highest-gain leaf next instead of a whole level, cutting loss faster per node. (Ke et al. (LightGBM), NeurIPS 2017)	XGBoost, LightGBM, bonsai	adopted
2017	GPU histogram training: Build the split histograms on the GPU, moving the training bottleneck onto the device. (Mitchell and Frank, PeerJ CS 2017)	XGBoost, LightGBM, CatBoost, bonsai	adopted
2018	Oblivious trees: Use the same split across a whole tree level, giving symmetric trees and branch-free prediction. (Prokhorenkova et al., NeurIPS 2018)	CatBoost, bonsai	adopted
2018	Ordered target statistics: Encode a category by the target mean over only the rows seen before it, so the statistic cannot leak the label. (Prokhorenkova et al., NeurIPS 2018)	CatBoost, bonsai	adapted
2018	Ordered boosting: Score each row with a model trained without it, removing the target leakage of ordinary boosting. (Prokhorenkova et al., NeurIPS 2018)	CatBoost	tbd
2018	TreeSHAP: Compute exact Shapley feature attributions for a tree ensemble in polynomial time. (Lundberg, Erion, and Lee, 2018)	XGBoost, LightGBM, CatBoost, bonsai	adopted
2019	Monotone and interaction constraints: Constrain a feature's effect to one direction, or restrict which features may interact on a path. (XGBoost and LightGBM engineering, circa 2019)	XGBoost, LightGBM, bonsai	adopted
2019	scikit-learn HistGradientBoosting: Ship a histogram gradient-boosting estimator in the standard scikit-learn API. (scikit-learn 0.21, 2019)	bonsai	adopted
2026	Cross-architecture reproducibility: Produce byte-identical models across host architectures at a fixed thread count. (bonsai, 2026 (decision 59))	bonsai	origin
2026	Device-resident objective: Derive each tree's gradients on the GPU and fuse leaf values into resident scores, deleting the per-tree host round-trip. (bonsai, 2026 (decisions 77 to 79))	bonsai	origin
2026	The single-card ceiling: Measure how large a dataset one GPU trains end to end: a 500M by 100 float32 matrix on one 80GB card. (bonsai, 2026)	bonsai	origin

Status legend

Status	Meaning
adopted	bonsai implements the idea.
adapted	bonsai carries the idea in a changed form.
declined	Measured or judged not worth the complexity, for now.
tbd	A named future campaign, not yet built.
origin	First done in bonsai.

About this page

The diagram and the table are generated from docs/learn/timeline.json by scripts/render_timeline.py, and CI fails on drift. Edit the data, not this page.