How XGBoost Decides Splits: Gain, Cover, and Weight Explained

How XGBoost’s Tree-Splitting Algorithm Works

XGBoost builds trees by finding splits that maximally reduce a regularized objective function. Unlike standard gradient boosting that uses only first-order gradients, XGBoost employs a second-order Taylor expansion of the loss, making split evaluation both more accurate and computationally efficient. The algorithm selects the feature and threshold that maximize a quantity called gain — the reduction in the objective achieved by partitioning a node into two children.

The Core Objective and the Gain Formula

At a high level, XGBoost minimizes a regularized objective at step $t$:

$$\mathcal{L}^{(t)} \approx \sum_{i=1}^n \left[ g_i f_t(x_i) + \frac{1}{2} h_i f_t^2(x_i) \right] + \Omega(f_t)$$

where $g_i = \partial_{\hat{y}^{(t-1)}} l(y_i, \hat{y}^{(t-1)})$ is the first-order gradient, $h_i = \partial^2_{\hat{y}^{(t-1)}} l(y_i, \hat{y}^{(t-1)})$ is the second-order gradient (the Hessian), and $\Omega(f_t) = \gamma T + \frac{1}{2}\lambda \sum_{j=1}^T w_j^2$ penalizes the number of leaves $T$ and the L2 norm of leaf weights $w_j$.

For a given leaf node with instance set $I$, the optimal leaf weight $w^*$ is found by setting the derivative of the quadratic approximation to zero:

$$w^* = -\frac{\sum_{i \in I} g_i}{\sum_{i \in I} h_i + \lambda}$$

This is the leaf output value — the score added to the prediction for any instance falling into that leaf. The parameter $\lambda$ (L2 regularization on leaf weights) shrinks this output, preventing any single leaf from dominating the prediction.

The gain formula evaluates how much the objective improves when we split a node into left ($L$) and right ($R$) children:

$$\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$$

Here, $G_L = \sum_{i \in I_L} g_i$ and $H_L = \sum_{i \in I_L} h_i$ (the sums of gradients and Hessians in the left node), and similarly $G_R$ and $H_R$ for the right node. The term $\frac{(G_L+G_R)^2}{H_L+H_R+\lambda}$ represents the score of the parent node before splitting; the first two bracketed terms represent the scores of the two children. The difference — scaled by $\frac{1}{2}$ — is the reduction in loss. If this value exceeds $\gamma$, the split is accepted. Otherwise it is pruned.

The parameter $\gamma$ (gamma) acts as a minimum loss reduction threshold. It directly controls tree complexity: larger values produce shallower trees by requiring each split to justify itself with substantial gain. This is a form of pre-pruning built into the splitting criterion itself.

What G and H Actually Represent

The meaning of $g_i$ and $h_i$ depends on the loss function. For squared error loss $l(y, \hat{y}) = \frac{1}{2}(y - \hat{y})^2$:

$$g_i = \hat{y}_i - y_i \quad \text{(the residual)}$$ $$h_i = 1 \quad \text{(constant)}$$

In this case, $G$ is simply the sum of residuals, and $H$ is the count of instances. The gain formula reduces to a variance-reduction criterion scaled by instance counts — conceptually similar to how a standard regression tree splits, but with regularization baked in.

For logistic loss (binary classification), $g_i$ and $h_i$ take more complex forms involving predicted probabilities, and $h_i$ varies per instance — larger when predictions are uncertain (near 0.5) and smaller when confident. The quantity $H$ then represents not just count but the aggregate confidence or certainty of the gradient information: instances with uncertain predictions contribute more to $H$, effectively giving them greater weight in split decisions.

This is why $H$ is often called the cover of a node: it measures the “heaviness” or statistical weight of the data in that node. A node with large cover contains many instances or particularly uncertain ones. When computing the leaf weight $w^* = -G/(H+\lambda)$, the denominator $H + \lambda$ normalizes the gradient sum — more cover means more evidence, so the leaf output is naturally shrunk for sparsely populated or low-confidence nodes.

The Exact Greedy Algorithm

For a single feature, the algorithm proceeds as follows:

  1. Sort all instances by the feature value.
  2. Initialize $G_L = 0$, $H_L = 0$, and set $G_R = G_{\text{parent}}$, $H_R = H_{\text{parent}}$.
  3. Scan left to right: for each candidate split point between consecutive sorted values, add the current instance’s $g_i$ and $h_i$ to $G_L$ and $H_L$, subtract them from $G_R$ and $H_R$.
  4. Compute gain using the formula above. Track the maximum.
  5. After scanning all features, select the split with the highest gain (if it exceeds $\gamma$).

Here is a minimal Python implementation for educational purposes:

import numpy as np

def find_best_split(X, y, loss='squared_error', lam=1.0, gamma=0.0):
    """
    Find the best split point using exact greedy search.
    X: (n_samples, n_features) feature matrix
    y: (n_samples,) target values
    Returns: (best_feature, best_threshold, best_gain)
    """
    n_samples, n_features = X.shape

    # Compute gradients and hessians for the parent node
    if loss == 'squared_error':
        # For squared error: g = pred - y, h = 1
        # With initial prediction = 0, g = -y, h = 1
        g = -y.astype(np.float64)
        h = np.ones(n_samples, dtype=np.float64)
    elif loss == 'logistic':
        # For logistic loss with initial pred = 0: p = 0.5
        p = np.full(n_samples, 0.5)
        g = p - y.astype(np.float64)
        h = p * (1 - p)
    else:
        raise ValueError(f"Unknown loss: {loss}")

    G_parent = g.sum()
    H_parent = h.sum()

    best_gain = -np.inf
    best_feature = None
    best_threshold = None
    parent_score = (G_parent ** 2) / (H_parent + lam)

    for feature_idx in range(n_features):
        # Sort instances by this feature
        sorted_indices = np.argsort(X[:, feature_idx])
        g_sorted = g[sorted_indices]
        h_sorted = h[sorted_indices]
        x_sorted = X[sorted_indices, feature_idx]

        G_L, H_L = 0.0, 0.0
        G_R, H_R = G_parent, H_parent

        for i in range(n_samples - 1):
            G_L += g_sorted[i]
            H_L += h_sorted[i]
            G_R -= g_sorted[i]
            H_R -= h_sorted[i]

            # Skip if this split point has the same value as the next
            if x_sorted[i] == x_sorted[i + 1]:
                continue

            # Compute gain
            left_score = (G_L ** 2) / (H_L + lam)
            right_score = (G_R ** 2) / (H_R + lam)
            gain = 0.5 * (left_score + right_score - parent_score) - gamma

            if gain > best_gain:
                best_gain = gain
                best_feature = feature_idx
                best_threshold = (x_sorted[i] + x_sorted[i + 1]) / 2.0

    return best_feature, best_threshold, best_gain

This implementation directly mirrors the algorithm described in the XGBoost paper by Chen and Guestrin (2016). In production XGBoost, the codebase uses highly optimized C++ routines with column block structures and cache-aware access patterns — see the official XGBoost source documentation for details on the ColMaker and HistMaker updaters.

Computational Complexity

The exact greedy algorithm requires sorting each feature, yielding complexity:

$$\mathcal{O}(n_{\text{features}} \times n_{\text{samples}} \times \log(n_{\text{samples}}))$$

For large datasets this becomes expensive. XGBoost mitigates this through several strategies:

  • Column block structure: Data is stored in compressed column (CSC) format in memory, with feature values pre-sorted. Sorting happens once before tree construction begins, and the sorted indices are reused across all splits at a given level.
  • Approximate algorithm: Instead of evaluating every candidate split, XGBoost proposes candidate quantile points weighted by Hessian values. This reduces the scan to a small number of buckets.
  • Histogram-based method: The HistMaker updater (used by default in recent XGBoost versions) bins continuous features into discrete bins and accumulates gradients per bin, achieving near-constant time per feature evaluation.

In practice, XGBoost dynamically chooses between exact and approximate strategies based on data size and user configuration (the tree_method parameter).

Handling Missing Values: The Sparsity-Aware Algorithm

Real-world datasets frequently contain missing values. XGBoost handles these natively through its sparsity-aware split finding. For each candidate split, the algorithm learns the default direction for missing values:

  1. All instances with missing values for the current feature are initially set aside.
  2. The gain is computed with these instances sent entirely to the left child.
  3. The gain is computed with these instances sent entirely to the right child.
  4. The direction yielding the higher gain becomes the learned default for that split.

This is performed efficiently by maintaining separate accumulators for non-missing instances and adding the missing batch at the end. The learned default direction is stored in the tree node, so at inference time missing values are automatically routed without imputation.

A Worked Micro-Example

Consider a tiny regression dataset with two features and squared error loss ($\lambda = 0$, $\gamma = 0$): With initial prediction $\hat{y} = 0$ for all instances, the gradients are $g_i = -y_i$ and Hessians $h_i = 1$:

  • Instance A: $g_A = -2.0$, $h_A = 1.0$
  • Instance B: $g_B = -4.0$, $h_B = 1.0$
  • Instance C: $g_C = -6.0$, $h_C = 1.0$

Parent node: $G = -12.0$, $H = 3.0$, parent score = $(-12)^2 / 3 = 48.0$.

Splitting on $x_1$ (sorted values: 1.0, 2.0, 3.0):

  • Split at 1.5: Left = {A}, Right = {B, C}

    • $G_L = -2.0$, $H_L = 1.0$ → score = $4.0/1 = 4.0$
    • $G_R = -10.0$, $H_R = 2.0$ → score = $100.0/2 = 50.0$
    • Gain = $0.5 \times (4.0 + 50.0 - 48.0) = 3.0$

  • Split at 2.5: Left = {A, B}, Right = {C}

    • $G_L = -6.0$, $H_L = 2.0$ → score = $36.0/2 = 18.0$
    • $G_R = -6.0$, $H_R = 1.0$ → score = $36.0/1 = 36.0$
    • Gain = $0.5 \times (18.0 + 36.0 - 48.0) = 3.0$

Both splits yield gain 3.0. The algorithm would select one (typically the first encountered).

Splitting on $x_2$ (sorted values: 1.0, 2.0, 3.0):

  • Split at 1.5: Left = {B}, Right = {A, C}

    • $G_L = -4.0$, $H_L = 1.0$ → score = 16.0
    • $G_R = -8.0$, $H_R = 2.0$ → score = 32.0
    • Gain = $0.5 \times (16.0 + 32.0 - 48.0) = 0.0$

  • Split at 2.5: Left = {B, C}, Right = {A}

    • $G_L = -10.0$, $H_L = 2.0$ → score = 50.0
    • $G_R = -2.0$, $H_R = 1.0$ → score = 4.0
    • Gain = $0.5 \times (50.0 + 4.0 - 48.0) = 3.0$

The best split overall has gain 3.0. After splitting, the leaf weights are computed as $w^* = -G/(H+\lambda)$. For the left leaf of the $x_1 \leq 2.5$ split (instances A and B), $w^* = -(-6.0)/2.0 = 3.0$. The right leaf (instance C) gets $w^* = -(-6.0)/1.0 = 6.0$.

The Role of Regularization in Practice

The two regularization parameters serve distinct purposes:

  • $\lambda$ (lambda) shrinks leaf weights continuously. Larger $\lambda$ makes $w^*$ smaller, reducing the influence of any single tree. It appears in the denominator of every score term, so it directly reduces gain for splits that would create leaves with small $H$ — effectively penalizing splits that isolate few instances.
  • $\gamma$ (gamma) imposes a discrete cost per split. Even if gain is positive, the split is rejected unless it exceeds $\gamma$. This directly limits tree depth and prevents splits that barely improve the objective.

Together, they provide complementary control: $\lambda$ smooths the model globally, while $\gamma$ prunes aggressively. In practice, tuning $\gamma$ often has a stronger effect on tree depth than tuning $\lambda$, but both interact with the learning rate and number of estimators.

FAQ

Why does XGBoost use second-order information instead of just gradients?

The Hessian provides curvature information, allowing a more accurate quadratic approximation of the loss. This leads to better split choices than first-order methods (which implicitly assume a linear loss surface). It also enables the closed-form optimal leaf weight $w^* = -G/(H+\lambda)$, avoiding line search.

What happens when $H$ is zero or very small?

If $H + \lambda$ approaches zero, the leaf weight and gain terms become numerically unstable. In practice, $\lambda > 0$ prevents division by zero. For losses where $h_i$ can be zero (e.g., some robust losses), XGBoost adds a small constant to ensure stability.

How does XGBoost handle categorical features?

Since version 1.5, XGBoost supports native categorical splits via the enable_categorical parameter. For categorical features, the algorithm performs optimal partitioning by sorting categories by their gradient statistics and finding the best grouping — this is more efficient than one-hot encoding and avoids the bias introduced by arbitrary ordinal mappings.