XGBoost Approximate Split-Finding and the Weighted Quantile Sketch

Q: Does `hist` use the weighted quantile sketch?

No. `hist` uses fixed-width or quantile-based binning at the start of training, then reuses those bins. It does not adapt bins per node or weight instances by hessian for bin placement. This simplicity is what makes `hist` fast, but it can be slightly less precise than `approx` for highly non-uniform feature distributions.

Q: Can I use `approx` on a single machine?

Yes. `approx` is fully supported in single-machine mode. It may be useful when you want adaptive, hessian-weighted candidate proposals without the fixed binning of `hist`.

Q: How do I know if my $\epsilon$ is too large?

If validation performance degrades noticeably compared to `exact` or `hist`, your $\epsilon$ may be too large. Try reducing it in steps (e.g., 0.1 → 0.05 → 0.03 → 0.01) and observe the accuracy-time trade-off curve. Past a certain point, further reductions yield diminishing returns.

The exact greedy algorithm for finding tree splits requires sorting all feature values at every node, an $O(n \log n)$ operation per feature per split. For datasets with millions of instances and hundreds of features, this becomes computationally prohibitive. XGBoost’s approximate algorithm sidesteps this bottleneck by proposing candidate split points from a compressed summary of the feature distribution. The core data structure enabling this is the weighted quantile sketch, which summarizes feature values weighted by their second-order gradient (hessian) statistics, ensuring that instances with higher “confidence” in their loss contribution receive more representation in the sketch. The result is a scalable, mergeable, and distributed-friendly split-finding procedure that closely approximates the exact greedy solution while reducing the number of candidate split evaluations from $O(n)$ to a small constant governed by a tunable parameter $\epsilon$.

The Scalability Problem with Exact Greedy

In gradient tree boosting, constructing a single decision tree involves recursively partitioning the feature space. At each node, the exact greedy algorithm examines every possible split point for every feature. This requires:

Sorting all training instances by each feature value.
Scanning the sorted list to compute the gain for each candidate split.

The sorting step dominates. For a dataset with $n$ instances and $m$ features, sorting all features at a single node costs $O(m \cdot n \log n)$. Since this repeats at every node in the tree, the total cost grows rapidly with data size. Moreover, the sorted data cannot always fit in cache, leading to irregular memory access patterns that further degrade performance on modern hardware.

As Chen & Guestrin (2016) note, the exact greedy algorithm is “prohibitively expensive” when data does not fit entirely in memory. The approximate algorithm was designed specifically to address this limitation.

The Approximate Algorithm: Candidate-Based Splitting

The approximate algorithm replaces exhaustive enumeration with a two-phase approach:

Proposal phase: For each feature, propose a set of candidate split points $S_k = {s_{k1}, s_{k2}, \ldots, s_{kl}}$ that partition the feature distribution into roughly equal-percentile buckets.
Evaluation phase: Map each training instance to the bucket it belongs to, then evaluate the split gain only at the boundaries between adjacent buckets.

The number of candidate points $l$ is controlled by the parameter $\epsilon$, where approximately $l \approx 1/\epsilon$. With $\epsilon = 0.1$, the algorithm evaluates roughly 10 candidate splits per feature instead of $n-1$ possible splits. This decouples split-finding cost from the number of training instances.

The Weighted Quantile Sketch

A naive percentile-based proposal would treat all instances equally. XGBoost’s key innovation is weighting each instance by its hessian value $h_i$ (the second derivative of the loss function with respect to the prediction). This is not arbitrary—the hessian directly appears in the gain equation for split evaluation.

Recall the objective function at a given node:

$$ \text{Gain} = \frac{1}{2} \left[ \frac{G_L^2}{H_L + \lambda} + \frac{G_R^2}{H_R + \lambda} - \frac{(G_L + G_R)^2}{H_L + H_R + \lambda} \right] - \gamma $$

where $G = \sum g_i$ and $H = \sum h_i$ are sums of gradients and hessians over instances in a node. The hessian acts as a weight: instances with larger $h_i$ contribute more to the denominator $H + \lambda$ and thus exert greater influence on the gain.

If we were to reweight the feature distribution so that each instance’s contribution to the quantile summary is proportional to $h_i$, we would ensure that the sketch preserves more detail in regions where the loss surface is steeper—precisely where accurate splits matter most. This is exactly what the weighted quantile sketch does.

Formal Definition

A weighted dataset $\mathcal{D} = {(x_{1k}, w_1), \ldots, (x_{nk}, w_n)}$ is defined for each feature $k$, where the weight $w_i = h_i$. The weighted quantile sketch summarizes this distribution such that for any query rank $q \in [0, 1]$, it can return a value $x$ satisfying:

$$ \left| \sum_{x_{ik} < x} w_i - q \sum_{i=1}^n w_i \right| \leq \epsilon \sum_{i=1}^n w_i $$

In other words, the sketch maintains an $\epsilon$-approximate weighted quantile summary. Candidate splits are then proposed at evenly spaced ranks: $q = \frac{1}{l}, \frac{2}{l}, \ldots, \frac{l-1}{l}$, where $l = \lceil 1/\epsilon \rceil$.

Data Structure Properties

The weighted quantile sketch is implemented as a mergeable summary. The original paper proposes an algorithm inspired by the GK summary and adapted for weighted data. Its key properties:

Deterministic: Produces consistent summaries given the same data.
Mergeable: Two sketches built on disjoint data partitions can be combined without accessing the original data. This is critical for distributed training.
Fixed memory: The sketch size is bounded by $O(1/\epsilon)$, not by $n$.
Streaming: New instances can be inserted incrementally.

The merge operation works by concatenating the sorted lists of quantile points from two sketches and then pruning redundant points to maintain the $\epsilon$ guarantee. In distributed settings, each worker builds a local sketch, sends the compact summary to the coordinator, and merged summaries produce globally consistent candidate splits.

The $\epsilon$ Parameter

The parameter sketch_eps (often just called $\epsilon$) directly controls the accuracy-speed trade-off:

Smaller $\epsilon$ → more candidate points (roughly $1/\epsilon$) → split locations closer to exact greedy → higher computational cost.
Larger $\epsilon$ → fewer candidates → faster training → potentially coarser splits.

Typical values range from 0.01 to 0.1. At $\epsilon = 0.03$, approximately 33 candidate splits are evaluated per feature. The exact relationship between $\epsilon$ and the number of candidates depends on the data distribution and weight distribution; the sketch provides a worst-case guarantee, not an exact count.

Global vs. Local Proposal

The approximate algorithm supports two strategies for when candidate splits are proposed:

Global Proposal (`sketch_eps` applied once)

Candidate splits are proposed once at the beginning of tree construction, using the full dataset. The same candidates are reused at every node. This is extremely fast since the sketch is built only once, but accuracy degrades for deeper trees because the feature distribution within a node can shift substantially from the global distribution. Global proposal is effective for shallow trees or when $\epsilon$ is set small enough to compensate.

Local Proposal (`updater='grow_local_histmaker'`)

Candidate splits are re-proposed at each node using only the instances reaching that node. This adapts to the local distribution and typically yields better accuracy at the cost of rebuilding sketches at every split. Local proposal dominates in practice for most applications because the sketch construction cost is small relative to the accuracy gains.

The XGBoost parameter documentation notes that local proposal is the default behavior when using the approx tree method.

Distributed Computation via Mergeable Summaries

The mergeable property of the weighted quantile sketch is essential for distributed training. In a cluster with $K$ workers:

Each worker builds a local weighted quantile sketch on its data partition.
Workers send their compact sketches (size $O(1/\epsilon)$) to the master.
The master merges all sketches to produce global candidate splits.
Candidate splits are broadcast back to workers.
Workers compute gradient histograms at the candidate points and send aggregated statistics to the master for split evaluation.

The communication cost is proportional to $K \cdot m / \epsilon$, independent of $n$. For $n = 10^8$, $m = 100$, and $\epsilon = 0.05$, each worker transmits roughly 2,000 float values per feature, which is negligible compared to transmitting the raw data.

The `tree_method` Parameter

XGBoost exposes the split-finding strategy through the tree_method parameter. Understanding the differences is essential for practical use:

exact: Exact greedy algorithm. Sorts all feature values at every node. Accurate but slow for large data. Single-machine only.
approx: The approximate algorithm with weighted quantile sketch. Supports distributed training. Use with sketch_eps to control accuracy.
hist: A histogram-based method that bins continuous features into discrete integer bins (default 256 bins) at the start of training. Split finding then operates on bin indices rather than raw values, eliminating per-node sorting entirely. Inspired by LightGBM’s approach.
auto: Automatically selects based on dataset size and training context. Typically chooses hist for single-machine and approx for distributed.

The hist method has become the default in recent XGBoost versions (since 1.0.0) because it offers the best balance of speed and accuracy for most use cases. It differs from approx in a key way: while approx builds weighted quantile summaries adaptively per node (if local) or once globally, hist pre-defines fixed-width bins globally and never re-adjusts them. This fixed binning enables additional optimizations like integer-based indexing and cache-friendly memory layouts.

When to Use Which Method

Based on the original paper’s benchmarks and community experience:

Datasets under ~10,000 instances: exact is feasible and provides the most precise splits.
Medium to large datasets (10K–10M instances): hist is the recommended default. It matches or exceeds approx in accuracy while being significantly faster due to binning.
Very large distributed datasets (>10M instances, multiple machines): approx with global or local proposal remains viable, though distributed hist is now available in recent versions.
When interpretability demands exact feature value splits: exact preserves the actual observed values, whereas approx and hist evaluate splits at interpolated or binned positions.

In the original Chen & Guestrin (2016) experiments on the Higgs boson dataset ($n = 10.5$M, $m = 28$), the approximate algorithm with $\epsilon = 0.05$ achieved AUC within 0.1% of exact greedy while reducing training time by roughly a factor of 2–3 on a single machine. With distributed training across 4 machines, the approximate algorithm scaled near-linearly.

Practical Guidance

For most practitioners, the decision tree is straightforward:

Start with tree_method='hist'. It is the default and performs excellently across a wide range of problems. The fixed binning introduces negligible accuracy loss in practice while providing dramatic speed improvements.
If using approx, tune sketch_eps. Values between 0.03 and 0.05 are typical starting points. Monitor training time and validation metrics to find the right trade-off. For distributed training, approx with local proposal often works well.
Avoid exact unless necessary. It rarely provides meaningful accuracy gains over hist or approx for datasets large enough to make it slow.
Monitor feature distributions. If your data has extreme skew or heavy tails, the weighted quantile sketch in approx may allocate more candidate points to dense regions. Check that important sparse regions are not being under-represented. The hist method’s fixed binning can also struggle with heavy-tailed features; consider preprocessing with quantile transforms in such cases.

Frequently Asked Questions

Why weight by hessian rather than gradient?

The hessian quantifies the curvature of the loss function. In the gain equation, $H$ appears in the denominator and controls how much a split can reduce the loss. An instance with large hessian has a “sharper” loss contribution—moving its prediction changes the loss more dramatically. Weighting by hessian ensures the sketch prioritizes accurate split placement where it matters most for the objective.

Does hist use the weighted quantile sketch?

No. hist uses fixed-width or quantile-based binning at the start of training, then reuses those bins. It does not adapt bins per node or weight instances by hessian for bin placement. This simplicity is what makes hist fast, but it can be slightly less precise than approx for highly non-uniform feature distributions.

Can I use approx on a single machine?

Yes. approx is fully supported in single-machine mode. It may be useful when you want adaptive, hessian-weighted candidate proposals without the fixed binning of hist.

How do I know if my $\epsilon$ is too large?

If validation performance degrades noticeably compared to exact or hist, your $\epsilon$ may be too large. Try reducing it in steps (e.g., 0.1 → 0.05 → 0.03 → 0.01) and observe the accuracy-time trade-off curve. Past a certain point, further reductions yield diminishing returns.