XGBoost internals from scratch: the second-order gain, the closed-form leaf weight, and what λ and γ actually do

Plain gradient boosting fits each new tree to the previous model's residuals. XGBoost keeps that skeleton but rebuilds the engine — and the rebuild is what makes it the algorithm that keeps winning tabular competitions. I built a tiny 1-D demo that computes every piece of it for real, and once you see the four moving parts, the "magic" turns out to be a couple of closed-form formulas. Here they are.

Every point carries a gradient and a curvature

Instead of chasing raw residuals, XGBoost writes down a single regularized objective and approximates it with a second-order Taylor expansion around the ensemble's current prediction F. That means every sample carries two numbers: a gradient gᵢ = ∂l/∂F and a Hessian hᵢ = ∂²l/∂F². For squared error hᵢ = 1 always; for log-loss hᵢ = pᵢ(1−pᵢ) — the curvature quietly down-weights points the model is already confident about.

def grad_hess(y, F, loss="logloss"):
    if loss == "mse":                 # l = 1/2 (y - F)^2
        g = F - y
        h = np.ones_like(F)           # h == 1  (constant!)
    else:                             # logistic
        p = 1.0 / (1.0 + np.exp(-F))
        g = p - y
        h = p * (1.0 - p)             # h == p(1-p)  (varies per point)
    return g, h

A leaf is two sums; a split is one formula

Plug the Taylor approximation into the objective with an L2 penalty ½λΣw², and the optimum for a leaf holding index set I is exactly w* = −G/(H+λ), with G=Σgᵢ and H=Σhᵢ. A whole leaf collapses to just those two sums — nothing else about the points matters. Its contribution to the objective (the "similarity score") is −½·G²/(H+λ), and a split's gain is how much that score improves, minus a per-leaf cost γ.

def leaf_weight(G, H, lam):
    return -G / (H + lam)                 # closed-form optimum, L2-shrunk

def split_gain(GL, HL, GR, HR, lam, gamma):
    G, H = GL + GR, HL + HR
    sim  = lambda g, h: g*g / (h + lam)   # similarity score of a node
    return 0.5 * (sim(GL, HL) + sim(GR, HR) - sim(G, H)) - gamma

That gain — ½[ G_L²/(H_L+λ) + G_R²/(H_R+λ) − G²/(H+λ) ] − γ — is the single formula the whole demo sweeps. Slide a split threshold along the feature and the gain curve rises and falls; the dashed γ line is the bar a split must clear.

Finding the best split is one sorted pass

Sort the points by the feature, walk left to right accumulating G_L, H_L, and the right side is just the totals minus the left. Score each threshold, keep the best. This is the "exact greedy" algorithm — O(#points) per feature after the sort.

def best_split(g, h, x, lam, gamma):
    order = np.argsort(x); g, h, x = g[order], h[order], x[order]
    G, H = g.sum(), h.sum()
    GL = HL = 0.0; best = (0.0, None)
    for i in range(len(x) - 1):
        GL += g[i]; HL += h[i]            # move point i to the left child
        if x[i] == x[i+1]: continue       # can't split between equal values
        gain = split_gain(GL, HL, G-GL, H-HL, lam, gamma)
        if gain > best[0]: best = (gain, 0.5*(x[i] + x[i+1]))
    return best

What λ and γ actually do

These are the two knobs XGBoost adds, and the demo lets you drag both. λ (L2 regularization) makes you divide by a larger H+λ, so every leaf weight shrinks toward zero — and gains shrink with it. γ is the minimum gain a split must produce to be worth making: raise it past the peak of the gain curve and the split is pruned, collapsing the branch to a single leaf. That one test — is gain still positive after subtracting γ? — is the entire pruning mechanism.

Where plain GB hides inside

The clarifying fact: plain gradient boosting is the same loop with h ≡ 1, λ = γ = 0. Then the leaf is just the mean residual −G/n and it never prunes. So for squared error (hᵢ=1, meaning H == n) XGBoost with no regularization is plain variance-reduction boosting. The Hessian only earns its keep on losses like log-loss, where hᵢ = pᵢ(1−pᵢ) genuinely varies per point and the second-order gain diverges from the first-order one.

# XGBoost leaf : w* = -G / (H + lam)   # curvature-weighted + L2 shrunk
# plain-GB leaf: w  = -G / n           # 1st order, no lambda, no gamma

Everything after that is systems engineering: real XGBoost bins each feature into ~256 buckets once so a split search becomes a bin-wise cumulative sum instead of a re-sort, and it is sparsity-aware, learning a default direction for missing values by trying both and keeping whichever gives more gain. But the statistics are all above — a gradient, a Hessian, a closed-form leaf, and a gain with two regularizers.

Drag λ and γ and watch the tree and the gain curve respond:
https://dev48v.infy.uk/ml/day40-xgboost-internals.html