Exploring XGBoost: A Deep Dive

17 min read. | 4237 total words.

XGBoost (Extreme Gradient Boosting) is an open-source library that implements gradient-boosted decision trees, an ensemble method that builds an additive sequence of trees where each new tree is fit to the gradient of the loss left by the ones before it. It supports regression, classification, ranking, and survival objectives behind a single training loop, and is implemented as a high-performance C++ core with CPU and CUDA/HIP backends, exposed through Python, R, and JVM bindings. On large tabular datasets it is a standard production choice for both accuracy and training throughput. This blog opens the box on how it works, end to end.

Part 1 rebuilds the math from scratch — what gradient boosting is, why second-order Newton boosting drops out naturally, how a single algorithm absorbs regression, classification, ranking, and survival analysis through a swap of objective function, and how the regularization term keeps trees honest.

Part 2 then walks the actual XGBoost source tree: the module map, where training and prediction live, the parameters that shape every tree, the CPU vs. GPU split, the kernels that drive tree_method="hist" on AMD Instinct GPUs, the data layouts (DMatrix, QuantileDMatrix, EllpackPage) that make all of it fast, a hand-worked example tree, and a closing tour of published benchmarks. By the end you should be able to read a stack trace from Learner::UpdateOneIter down to a StHistKernel dispatch and know exactly what each layer is doing — and why.

A decision tree is a piecewise-constant predictor that learns a partition of the input space by greedily splitting examples. At each internal node it picks a feature \(f\) and a threshold \(t\) and routes instances either left or right; at each leaf it stores a prediction. Training works top-down: try every candidate split, score it, keep the best, recurse. For numerical features and sorted data this enumeration is \(O(n·m)\) per node where n is the number of instances and m is the number of features — XGBoost actually uses one-hot encoding for categorical variables and stores zeros as missing values, so the same numerical machinery covers everything.

A single tree, however, has high variance: pushed deep enough it memorizes the training set and generalizes poorly. The classic remedy is to combine many trees into an ensemble and average (or boost) their predictions.

Why Boosting? A 1-Page Derivation#

Suppose you'd like to learn a function \(F(x)\) that minimizes a differentiable loss \(L(y, \hat y)\) averaged over training instances. Boosting builds the model additively, one estimator at a time:

\[ F_{m+1}(x) = F_m(x) + f(x). \]

Knowing the truth, the perfect correction would be \(f(x) = y - F_m(x)\) — the residual. Plug \(L(y, \hat y) = \tfrac12 (y - \hat y)^2\) in and look at the per-instance gradient of the cumulative loss \(J = \sum_i L(y_i, F(x_i))\):

\[ \frac{\partial J}{\partial F(x_i)} = \frac{\partial L(y_i, F(x_i))}{\partial F(x_i)} = F(x_i) - y_i. \]

\[ f(x) = y - F_m(x) = -\frac{\partial L(y, F(x))}{\partial F(x)}. \]

Adding a model that approximates this negative gradient is gradient descent — but in function space. That single observation generalizes to any differentiable loss: at each round, fit a weak learner to the negative gradient of L. This is gradient boosting.

XGBoost (Chen & Guestrin, 2016) generalizes the above in two ways: it allows any twice-differentiable convex loss, and it adds an explicit regularization term that penalizes tree complexity. The objective becomes

where \(T\) is the number of leaves and \(w\) is the vector of leaf weights. \(\gamma\) charges a constant penalty per leaf (so XGBoost will refuse to split unless the gain pays for it), and \(\lambda\) is the L2 penalty on weights (so leaves cannot blow up to extreme values).

\[ \mathrm{Obj}_m = \sum_i L\!\bigl(y_i,\;\hat y_i^{(m-1)} + f_k(x_i)\bigr) + \sum_k \Omega(f_k). \]

\[ g_i = \frac{\partial L(y_i, \hat y_i^{(m-1)})}{\partial \hat y_i^{(m-1)}}, \qquad h_i = \frac{\partial^{2} L(y_i, \hat y_i^{(m-1)})}{\partial (\hat y_i^{(m-1)})^{2}}. \]

These are the gradient and Hessian of the loss at every training row. XGBoost stores them packed together as GradientPair, and they are the only thing the tree updater needs from the loss function.

A tree predicts a constant within each leaf, so \(f_k(x) = w_{q(x)}\) where \(q(x)\) is the leaf index that \(x\) lands in. Summing per leaf and writing \(G_j = \sum_{i \in I_j} g_i\), \(H_j = \sum_{i \in I_j} h_i\),

\[ \mathrm{Obj}_m = \sum_{j=1}^{T} \Bigl[ G_j\, w_j + \tfrac{1}{2}(H_j + \lambda)\, w_j^{2} \Bigr] + \gamma\, T. \]

For a fixed tree structure, set the derivative w.r.t. \(w_j\) to zero:

\[ \boxed{\,\mathrm{Obj}_m^{*} = -\frac{1}{2}\sum_{j=1}^{T} \frac{G_j^{2}}{H_j + \lambda} + \gamma\, T.\,} \]

\[ \boxed{\;\mathrm{Gain} = \tfrac{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 .\;} \]

That single formula is the workhorse of every XGBoost tree updater (CPU exact, CPU approx, CPU hist, GPU hist, and GPU approx), and the γ term is what stops the tree from growing forever even when there is some signal in a split. To find the best split for a feature you scan its sorted values left to right, maintain a running (G_L, H_L), derive (G_R, H_R) by subtraction from the node total, and keep the maximum-gain candidate.

\[ \hat y(x) \;=\; \mathrm{link}^{-1}\!\Bigl(\, b + \sum_{k=1}^{K} f_k(x) \,\Bigr) , \qquad f_k(x) = w_{q_k(x)} . \]

The bracketed sum is what XGBoost calls the margin (raw score before link). For binary:logistic you apply sigmoid to get a probability; for multi:softprob you stack K margins per row and apply softmax; for reg:squarederror the link is the identity and the margin is the prediction. The Booster.predict(..., output_margin=True) switch lets you peek at the raw margin directly. This is handy for SHAP, calibration work, or cross-library checks. Figure 1 details and maps the prediction steps across the theory, Python API and Cpp modules.

Figure 1: Prediction pipeline.#

Figure 1: Prediction pipeline.#

The reason XGBoost feels like a Swiss army knife is structural: the entire boosting loop only needs (g_i, h_i) per row. Where those come from is the objective function's job, and objectives are pluggable. Everything else (the tree updaters, the histograms, and the GPU kernels) is identical regardless of whether you are predicting house prices, click-through rate, or document relevance.

The C++ contract is a one-method interface (ObjFunction::GetGradient); the Python contract is a function that returns (grad, hess) arrays of the same shape as y. Built-in objectives live under src/objective/ and are registered through XGBOOST_REGISTER_OBJECTIVE, so adding a new one means writing a .cc (or .cu) file and rebuilding. No changes to the boosting loop are required.

Switching workloads therefore requires changing only one parameter. No other code changes are required:

Under the hood, all three calls walk through the same Learner::UpdateOneIter → GBTree::DoBoost → TreeUpdater::Update path; only the objective module that fills GradientPair differs. This is also why metrics are not the loss: eval_metric (e.g. auc, ndcg@10, mae) is consumed by Metric::Evaluate for logging and early stopping but never feeds back into (g, h). A common confusion is to set eval_metric="logloss" and assume training "uses log loss" — what actually drives training is the objective. Mismatched objectives and metrics are perfectly legal and sometimes useful (train logistic, evaluate on AUC), but they do not swap each other out.

The optimal weight \(w_j^* = -G_j / (H_j + \lambda)\) shrinks toward zero as λ grows. Even a leaf with strong gradient signal is dampened. This is the L2 control on leaf magnitude.

The optimal weight \(w_j^* = -G_j / (H_j + \lambda)\) shrinks toward zero as λ grows. Even a leaf with strong gradient signal is