Histogram Gradient Boosting: The Engineering Inside XGBoost, LightGBM and CatBoost

Ten million rows with 100 numeric features, stored as 32-bit floats, occupy about 4 GB. Store each value instead as the index of one of at most 256 bins and the same matrix fits in 1 GB of uint8. Bins also turn split finding from sorting values into summing into a few hundred buckets. That substitution, more than any change to the boosting algorithm, underlies all three libraries practitioners actually use.

The algorithm itself, boosting as gradient descent in function space, is covered in gradient boosting as functional gradient descent. This concept is about the machinery underneath it.

The objective every split is scored against

At boosting round \(t\), each training example \(i\) has a current prediction \(\hat y_i\), a gradient \(g_i = \partial_{\hat y} \ell(y_i, \hat y_i)\) and a Hessian \(h_i = \partial^2_{\hat y} \ell(y_i, \hat y_i)\). A new tree \(f\) with \(T\) leaves and leaf weights \(w_j\) is chosen to minimise a second-order Taylor approximation plus a complexity penalty:

where \(G_j\) and \(H_j\) sum \(g_i\) and \(h_i\) over the examples in leaf \(j\), \(\lambda\) is an L2 penalty on leaf weights, \(\alpha\) an L1 penalty and \(\gamma\) a cost per leaf. With \(\alpha = 0\) the optimal weight is \(w_j^* = -G_j/(H_j + \lambda)\), and splitting a node into left and right children improves the objective by

(Chen & Guestrin, 2016, XGBoost: A Scalable Tree Boosting System, KDD, arXiv:1603.02754). With \(\alpha > 0\), \(G_j\) is soft-thresholded by \(\alpha\) before squaring, so leaves with weak aggregate gradient get weight exactly zero.

Every candidate split needs only four numbers, \(G_L, H_L, G_R, H_R\). That is the property the engineering exploits.

The Hessian also gives the regularisation parameters a concrete meaning. For log loss, \(h_i = p_i(1 - p_i)\). A leaf of 100 examples the model already predicts at \(p = 0.99\) has \(H \approx 100 \times 0.0099 = 0.99\), so the XGBoost default min_child_weight of 1 forbids that split. It is a minimum Hessian mass, not a row count, and it stops the model chasing leaves it is already confident about.

From sorting to histograms

Exact split finding sorts each feature once and sweeps every distinct threshold, accumulating \(G\) and \(H\). XGBoost's original contribution included an approximate variant that proposes candidate thresholds from a Hessian-weighted quantile sketch, and a sparsity-aware search that learns a default direction for missing values at each split.

The histogram method commits to bins before training. Each feature is discretised into at most max_bin buckets (255 by default in LightGBM). To score a node, one pass over its rows adds each row's \(g_i\) and \(h_i\) into its bin for every feature, which is \(O(\text{rows} \times \text{features})\) of cheap additions. The split search then scans bins, \(O(\text{bins})\) per feature, instead of distinct values. Two further tricks compound. Histogram subtraction: a child's histogram equals its parent's minus its sibling's, so only the smaller child needs a data pass. Cache locality: uint8 bin indices fit many more rows per cache line than floats. XGBoost 2.0 made hist its default tree method.

LightGBM added two data-reduction techniques (Ke et al., 2017, LightGBM: A Highly Efficient Gradient Boosting Decision Tree, NeurIPS). Gradient-based one-side sampling keeps the fraction \(a\) of rows with the largest \(|g_i|\), samples a fraction \(b\) from the rest, and up-weights the sampled small-gradient rows by \((1-a)/b\) so gain estimates stay approximately unbiased. Exclusive feature bundling merges sparse features that are rarely nonzero together into one histogram, which matters for one-hot encoded data. The paper reports training up to more than 20 times faster than conventional GBDT at almost the same accuracy.

Growth policy and tree shape

Level-wise growth, XGBoost's default, splits every node at a depth before moving deeper, producing balanced trees bounded by max_depth. Leaf-wise (best-first) growth, LightGBM's default, always splits the leaf with the largest gain anywhere in the tree. For a fixed number of leaves it reaches lower training loss, and it builds deep, lopsided trees that overfit small datasets unless num_leaves (default 31) and min_data_in_leaf (default 20) are bounded.

CatBoost goes the other way and uses oblivious trees: every node at a given depth applies the same feature and threshold (Prokhorenkova et al., 2018, CatBoost: Unbiased Boosting with Categorical Features, NeurIPS, arXiv:1706.09516). A depth-6 oblivious tree is six comparisons that form a 6-bit index into 64 leaf values, with no branching, which makes inference fast and acts as a strong structural regulariser. Its other signature, ordered boosting, computes each example's residuals and categorical target statistics using only examples earlier in a random permutation, removing the target leakage that makes in-sample statistics optimistic.

When it breaks

Bins are frozen at training time. Thresholds can only fall on training-set bin boundaries. A feature whose serving distribution drifts past the top bin gets the edge leaf's value forever, and a coarse max_bin can hide a sharp threshold between two bin edges.

Non-convex or custom losses break the Newton step. If \(h_i \le 0\) or is near zero, \(-G/(H+\lambda)\) explodes or flips sign. Custom objectives need a positive, bounded Hessian surrogate, and libraries silently clip in different ways.

Library comparisons are unstable. Published rankings of the three libraries conflict, largely because defaults (growth policy, bins, categorical handling) and tuning budgets differ. Vendor benchmarks favour their own defaults; only an equal-budget comparison on your data transfers.

Reproducibility is not free. Multithreaded or GPU histogram sums and GOSS sampling can differ between runs, and near-tied gains then pick different splits.