LightGBM: A Highly Efficient Gradient Boosting Decision Tree

Gradient Boosting builds an ensemble of decision trees sequentially. Each new tree is trained on the residual errors (gradients) of all previous trees. To find the best split at each node, the algorithm must evaluate every possible split point for every feature — and that means scanning the entire dataset per candidate split.

XGBoost uses a pre-sorted algorithm: it sorts each feature's values and walks through them to calculate information gain. This is exact, but for $n$ data points and $d$ features, the cost is $O(n \cdot d)$ per tree node — and a typical model has thousands of nodes across hundreds of trees.

When $n$ reaches millions and $d$ reaches thousands, the training time becomes a serious practical barrier.

Instead of examining every unique feature value, LightGBM buckets continuous features into a fixed number of discrete bins (typically 255). Building a histogram — a count and gradient sum per bin — costs $O(n)$, but finding the best split then costs only $O(\text{bins})$ instead of $O(n)$.

Think of it like grading exams: instead of ranking every student's exact score, you bin them into letter grades (A, B, C, D, F). You lose a tiny bit of precision, but you can spot the best split point between grades almost instantly. And with 255 bins, the precision loss is negligible.

An additional trick: the histogram subtraction optimization. If a parent node's histogram is known, the histogram of one child can be obtained by subtracting the other child's histogram from it. This halves the histogram construction cost.

Most boosting frameworks (including XGBoost's default) grow trees level-wise: they split all nodes at the current depth before moving deeper, producing balanced trees. This is safe but inefficient — it wastes splits on nodes that contribute little to the loss reduction.

LightGBM grows trees leaf-wise: at each step, it finds the leaf with the largest potential loss reduction across the entire tree and splits that one. This produces asymmetric, deeper trees that converge faster — achieving the same loss with fewer total splits.

The risk is overfitting: a leaf-wise tree can grow very deep on one side, memorizing noise in small partitions. LightGBM controls this with max_depth and num_leaves parameters — think of num_leaves as a budget: the tree can spend its splits wherever the gain is highest, but it cannot exceed the budget.

Not all data instances contribute equally to learning. Instances with large gradients are the ones the model currently gets most wrong — they carry the most information for improving the next tree. Instances with small gradients are already well-predicted and contribute less.

GOSS exploits this insight: it keeps all instances with large gradients (the top $a$ fraction) and randomly samples from the remaining small-gradient instances (keeping a fraction $b$). To avoid biasing the learned model, it multiplies the sampled small-gradient instances by a constant factor $\frac{1-a}{b}$ to compensate for the under-sampling.

The result: the histogram is built from a much smaller subset of the data, but the distribution of information gain is approximately preserved. Typical settings ($a = 0.2$, $b = 0.1$) mean the tree is built on only 30% of the data, yielding roughly a 2× speedup on top of histograms alone.

Real-world datasets — especially after one-hot encoding — are often highly sparse: most feature values are zero. Many of these features are mutually exclusive — they rarely take non-zero values simultaneously. For example, in one-hot encoded text data, the column for "apple" and the column for "orange" never both equal 1 in the same row.

EFB identifies such mutually exclusive features and merges them into a single bundle feature. If feature A ranges from 0–10 and feature B ranges from 0–20, the bundle stores A's values as-is and offsets B's values by adding 10. The tree can then split on the bundle instead of two separate features, cutting the effective feature count dramatically.

Finding the optimal bundling is NP-hard (it reduces to graph coloring), so EFB uses a greedy algorithm: build a conflict graph where edges connect features that are not mutually exclusive, then greedily assign features to bundles while allowing a small conflict rate.

Each boosting round proceeds as follows:

1. Compute gradients for all instances using the current model's predictions.
2. GOSS sampling — keep all large-gradient instances, randomly sample from the rest.
3. EFB — bundle mutually exclusive features (done once at initialization).
4. Build histograms for each feature (or bundle) on the sampled data.
5. Find best splits by scanning histogram bins (not raw values).
6. Grow the tree leaf-wise — always split the leaf with the highest gain.
7. Add the new tree to the ensemble with a learning rate shrinkage.

Steps 4 and 5 are where the histogram trick saves time. Step 2 reduces the data going into step 4. Step 3 reduces the features. Together, they compound into the 20× speedup.

The paper evaluated LightGBM on five public datasets ranging from 0.5M to 10M instances. Compared to XGBoost's pre-sorted algorithm, LightGBM achieved speedups of 6× to 21× while maintaining nearly identical accuracy (measured by AUC for classification and NDCG@10 for ranking).

Breaking down the contributions: GOSS alone provides roughly a 2× speedup by training on 10–20% of the data. EFB provides additional speedup proportional to the feature sparsity — on one-hot encoded features, it can reduce the effective feature count by an order of magnitude. The histogram-based approach provides the foundation that both build on.