Histogram Split Finding and the Weighted Quantile Sketch

The exact greedy split search sorts each feature at every node it touches. That sort is the dominant cost of tree building on large data, and it repeats work: the rows arriving at a child are a subset of the rows at the parent, and their order under a given feature is already known. Histogram split finding removes the sort entirely by replacing the feature’s values with small integer bin indices computed once, up front. The split search then becomes a counting pass.

The trade is explicit: threshold precision for throughput. A feature reduced to 255 bins can only produce 254 distinct thresholds, no matter how many distinct values it had, so the fitted function is coarser than an exact search would produce. In practice the loss in accuracy is small and the gain in speed is large, which is why every major boosted-tree implementation offers this mode and most default to it.

Binning once, counting per node

A binning pass maps each feature to $B$ bins, typically 255 so that a bin index fits in one byte. Some implementations reserve one index for missing values, leaving 254 bins for observed values and therefore 253 candidate thresholds per feature. The mapping is monotone for ordered features: values below the first cut point get bin 0, values between the first and second get bin 1, and so on. What is stored in the training matrix afterwards is not the value but the index, so a dataset of a million rows and a hundred features occupies a hundred million bytes rather than eight hundred million for 64-bit floats.

At a node, the algorithm allocates a histogram of $B$ slots per feature, each slot holding a pair (gradient sum, hessian sum), and makes one pass over the node’s rows:

def build_histogram(rows, bins, grad, hess, n_features, B):
    # hist[j][b] holds the (gradient, hessian) sums of feature j, bin b
    hist = [[[0.0, 0.0] for _ in range(B)] for _ in range(n_features)]
    for i in rows:
        g, h = grad[i], hess[i]
        for j in range(n_features):
            slot = hist[j][bins[i][j]]
            slot[0] += g
            slot[1] += h
    return hist

The cost is one addition per feature per row, with the bin index already in memory, so the pass is linear in the node’s data volume and has no comparison or branch per candidate. After the pass, the candidates are the $B-1$ boundaries, and the prefix sums over the histogram give the left-child statistics directly, so the scan itself is $B$ steps per feature rather than $n$.

Total work per level is therefore $O(n \cdot p)$ for the histogram passes plus $O(p \cdot B)$ for the scans, against $O(p \cdot n \log n)$ for the exact search. The comparison flatters the histogram more than the constants do, but the asymptotic difference is real: at depth $d$, the exact method re-sorts at every node, while the histogram method never sorts after the initial binning pass.

Building the second histogram by subtraction

A node’s two children partition its rows, so their histograms sum to the parent’s, bin by bin. That means only one child’s histogram needs to be built; the other is obtained by subtracting it from the parent’s. Constructing the histogram for the smaller child and subtracting yields the larger one, because the subtraction costs $B$ operations per feature regardless of how many rows the child holds.

The saving is a factor close to two per level, and it compounds: at every split the more expensive histogram is never built. The technique requires the parent’s histogram to be retained until both children have been processed, which increases peak memory by one histogram per level on the active path, a small price relative to the time saved. It also requires exact arithmetic consistency; with floating-point sums, the subtracted histogram differs from a directly built one in the last bits, which is harmless for split selection but means the two orders are not bit-identical.

Placing the cut points

Uniform bins are the wrong default. A feature with a long right tail would spend most of its bins on a region containing almost no rows, and all the candidate thresholds that matter would collapse into the first few bins. Quantile bins fix this by placing cut points so that each bin holds roughly the same number of rows.

Weighting the quantiles is the refinement that boosting needs. In a gradient-boosted tree, a row’s importance at a node is not uniform: it contributes a hessian $h_i$ to the split criterion, and rows that the model already predicts confidently have small $h$. Cutting at equal row quantiles puts resolution where there are many rows, not where there is curvature. The weighted quantile sketch instead chooses cut points so that each bin holds roughly equal total weight $\sum h_i$, which puts resolution where the objective can still change.

Exact weighted quantiles are not available in one streaming pass without storing the data, so the sketch is approximate. The standard formulation offers a guarantee of the form: any cut point returned is within a factor $1 \pm \epsilon$ of the true weighted quantile, for a sketch whose size grows like $O(\tfrac{1}{\epsilon}\log(\epsilon n))$. Setting $\epsilon$ trades bin count against fidelity, and because the sketch is built once per feature over a sample of the rows, the binning pass is far cheaper than the tree growth that follows.

What 255 buckets cost

The precision loss has three distinct shapes.

Thresholds snap to bin edges. Two values in the same bin are indistinguishable to the split search, so a split that should separate them cannot be expressed. With 255 bins and heavy duplication in the data this rarely matters; with a continuous feature and few rows per bin, the split location can be off by the width of a bin. For a well-behaved feature the bin width at the median is roughly the interquartile range divided by the local bin density, which for skewed features can be large.

The loss is not uniform across the tree. Bins are global, computed once on the whole training set. A node deep in the tree may contain only rows from one part of the range, where a single global bin covers most of its samples. Then the node’s histogram has very few non-empty bins, and its split resolution is much coarser than 255. Rebinning per node would recover the resolution at the cost of the sorting the method was designed to avoid.

Binning is a modelling assumption that can be violated at inference time. The bin edges are stored with the model. A value outside the range seen in training maps to the first or last bin, which is consistent with how trees extrapolate: not at all. If a serving pipeline applies a different binning, or if the feature is transformed differently, the model silently reads the wrong bin, and the error is invisible because every bin is valid.

Two hyperparameters interact with all of this. The number of bins sets the resolution; the minimum number of samples or minimum hessian per child prevents a split from carving out a bin with three rows in it. With 255 bins, the smallest representable child is one bin wide, so a minimum-child constraint is the only thing standing between the search and arbitrary small partitions.

Sparse data and exclusive features

Wide, sparse data, as produced by one-hot encoding, spends most of its histogram work on zeros. Two techniques address it.

A dedicated missing-value bin lets the split search choose a default direction: rows with a missing value are assigned to whichever child gives the larger gain, and the choice is stored per node. This is strictly better than filling with a constant, because the direction is learned rather than assumed, and it costs one extra bin slot per feature.

Exclusive feature bundling goes further. If two sparse features are almost never non-zero on the same row, they cannot interact, and their columns can be merged into one by offsetting the bin indices of one so that they do not overlap. A bundle of $k$ mutually exclusive features occupies one column with $k$ disjoint ranges of bins. The histogram cost for the bundle is one pass instead of $k$, and the split search sees each constituent feature’s bins separately, so the model is unchanged. The condition is almost-never rather than never, so bundling introduces a small amount of spurious co-occurrence that must be bounded by a conflict threshold.

These techniques are specific to boosting’s access pattern. A bagged forest builds each tree from a bootstrap sample of rows, and the histogram of a resample can be derived from the full histogram only approximately, because resampling changes counts by multinomial noise rather than by subsetting. The result is that histogram methods are most valuable where gradient boosting dominates, and forests keep their exact or presorted split search longer.

The histogram also changes what “exact” means for the objective. In the second-order formulation described in the regularized split gain, a split’s gain is computed from the sums $G$ and $H$ in each child; the histogram stores exactly those sums, so the gain of a bin-boundary split is computed with no additional error. All the approximation is in which thresholds are candidates, not in how they are scored, and that separation is what makes the method predictable: adding bins strictly refines the candidate set, so the best achievable gain is monotone in $B$.