💡 LightGBM
LightGBM keeps XGBoost's mathematics unchanged. The leaf weight is still $w^{*} = -G/(H+\lambda)$ and the split gain is still built from $G^2/(H+\lambda)$ terms.
What LightGBM changes is how the search is done, and it changes three things:
| XGBoost (exact) | LightGBM | |
|---|---|---|
| Finding thresholds | sort every feature, try every midpoint | bucket into a fixed number of bins |
| Growing the tree | level-wise — fill each depth before going deeper | leaf-wise — always split the most promising leaf |
| Using the rows | all of them | GOSS — keep large gradients, subsample small ones |
Each of these is an approximation traded for speed, and each is worked through below
with the actual numbers. At the end the tree is matched against the real lightgbm.
Display helpers ready: banner, step, check, expand, show_matrix, show_matmul, show_elementwise.
Tree diagram helper ready: draw_tree(root, title).
1. The Task and the Starting Point
Same 12 EEG recordings and the same regression target as the XGBoost walkthrough.
One difference in setup: LightGBM starts from the mean of $y$ rather than a fixed
constant (boost_from_average). That has a neat consequence worth noticing immediately.
12 recordings x 3 features
id region line_length spike_rate age y_class y_reg
-------------------------------------------------------------------------------
rec00 frontal 12.0 0.5 24.0 0 0.2
rec01 temporal 15.0 1.2 31.0 0 0.5
rec02 temporal 42.0 6.8 58.0 1 6.4
rec03 occipital 38.0 5.1 47.0 1 4.8
rec04 frontal 11.0 0.3 19.0 0 0.1
rec05 temporal 55.0 8.2 63.0 1 9.1
rec06 occipital 40.0 1.9 35.0 1 3.5
rec07 temporal 47.0 7.4 52.0 1 7.2
rec08 frontal 14.0 0.8 28.0 0 0.3
rec09 occipital 51.0 6.1 60.0 1 6.9
rec10 frontal 45.0 2.4 41.0 0 1.6
rec11 temporal 35.0 4.7 30.0 1 4.1
-------------------------------------------------------------------------------
class balance: 5 negative, 7 positive
y_reg mean = 3.7250, std = 3.0518
init_score = mean(y) = 3.725000
id y pred0 g = p - y h
--------------------------------------------
rec00 0.20 3.7250 3.5250 1
rec01 0.50 3.7250 3.2250 1
rec02 6.40 3.7250 -2.6750 1
rec03 4.80 3.7250 -1.0750 1
rec04 0.10 3.7250 3.6250 1
rec05 9.10 3.7250 -5.3750 1
rec06 3.50 3.7250 0.2250 1
rec07 7.20 3.7250 -3.4750 1
rec08 0.30 3.7250 3.4250 1
rec09 6.90 3.7250 -3.1750 1
rec10 1.60 3.7250 2.1250 1
rec11 4.10 3.7250 -0.3750 1
--------------------------------------------
SUM 44.70 44.7000 -0.000000 12
G = -0.0000000000 <- exactly zero, and not by accident:
starting at the mean makes the total gradient vanish, because
sum(mean(y) - y_i) = n*mean(y) - sum(y) = 0 by definition of the mean.
So the root similarity G^2/(H+lambda) = 0.000000,
and every bit of gain a split earns is pure separation of positive from
negative gradients.
2. Histogram Binning
Exact split finding sorts a feature and tests every midpoint: $O(n \log n)$ per feature per node, and $n-1$ candidate thresholds.
LightGBM instead pushes every value into one of max_bin buckets once, before
training, and then only ever considers bin boundaries as thresholds. With 255 bins
the number of candidates stops growing with $n$ entirely.
To make the bucketing visible, max_bin is set to 4 below — so 12 distinct values
collapse into 4 groups and only 3 thresholds survive.
feature 'spike_rate' with max_bin = 4
bin edges: [1.1 3.55 6.275]
id value bin g h
--------------------------------------
rec04 0.30 0 3.6250 1
rec00 0.50 0 3.5250 1
rec08 0.80 0 3.4250 1
rec01 1.20 1 3.2250 1
rec06 1.90 1 0.2250 1
rec10 2.40 1 2.1250 1
rec11 4.70 2 -0.3750 1
rec03 5.10 2 -1.0750 1
rec09 6.10 2 -3.1750 1
rec02 6.80 3 -2.6750 1
rec07 7.40 3 -3.4750 1
rec05 8.20 3 -5.3750 1
--------------------------------------
exact search would test 11 thresholds;
histogram search tests 3.
Building the histogram
For each bin LightGBM accumulates just two numbers — the sum of gradients and the sum of Hessians:
$$\text{Hist}[b] = \Big(\textstyle\sum_{i:\,\text{bin}(i)=b} g_i,\;\; \sum_{i:\,\text{bin}(i)=b} h_i\Big)$$
This is a single $O(n)$ pass. Everything after it costs $O(\text{bins})$ and never touches the rows again.
histogram for 'spike_rate' bin count sum g sum h -------------------------------- 0 3 10.5750 3.0 1 3 5.5750 3.0 2 3 -4.6250 3.0 3 3 -11.5250 3.0 -------------------------------- ALL 12 -0.0000 12.0 totals match the full dataset: G True, H True
Scanning the histogram
Finding the best threshold is now a single left-to-right sweep accumulating prefix sums. The right side never has to be computed — it is the total minus the left:
$$G_R = G_{\text{total}} - G_L, \qquad H_R = H_{\text{total}} - H_L$$
prefix-sum scan over the 4 bins of 'spike_rate'
split after bin G_L H_L G_R H_R S_L S_R gain
----------------------------------------------------------------------------------------
0 10.5750 3.0 -10.5750 9.0 27.9577 11.1831 19.5704
1 16.1500 6.0 -16.1500 6.0 37.2604 37.2604 37.2604
2 11.5250 9.0 -11.5250 3.0 13.2826 33.2064 23.2445
----------------------------------------------------------------------------------------
best: split after bin 1, gain 37.260357 (lightgbm would print 74.520714)
which corresponds to the threshold 3.5500
exact search over all 11 thresholds: gain 37.260357 at 3.550
histogram search with only 4 bins : gain 37.260357 at 3.550
same gain? True
With 4 bins the approximation happens to land on the same split. Coarser
bins lose accuracy; finer bins cost more. max_bin is exactly that dial.
Why this is fast
Exact split finding costs $O(n \log n)$ per feature per node. Histogram building costs $O(n)$ once, and every node after that costs $O(\#\text{bins})$ regardless of how many rows it holds.
On 12 rows this is irrelevant. The table below scales the row count up to make the difference visible.
rows exact (ms) histogram (ms) speedup
--------------------------------------------------
1000 0.11 0.08 1.4x
10000 0.42 0.10 4.3x
100000 4.52 0.69 6.5x
500000 32.82 6.11 5.4x
--------------------------------------------------
And the real saving is bigger than this: the binning pass happens ONCE for
the whole training run, while the sort in exact mode happens at every node.
The histogram subtraction trick
A second saving, and it is nearly free. After splitting a node, LightGBM builds the histogram for the smaller child only, then obtains the other by subtraction:
$$\text{Hist}_{\text{sibling}} = \text{Hist}_{\text{parent}} - \text{Hist}_{\text{child}}$$
So the cost of a node pair is set by the smaller child, not the parent.
parent has 12 rows; children have 6 and 6 bin parent G small G parent-small direct G equal ------------------------------------------------------------ 0 10.5750 10.5750 0.0000 0.0000 True 1 5.5750 5.5750 0.0000 0.0000 True 2 -4.6250 0.0000 -4.6250 -4.6250 True 3 -11.5250 0.0000 -11.5250 -11.5250 True ------------------------------------------------------------ subtraction reproduces the sibling histogram exactly: G True, H True, count True rows actually scanned: 6 instead of 6 (0 saved at this node alone)
3. Leaf-wise Growth
This is the change with the biggest effect on the shape of the tree.
- Level-wise (XGBoost's default): split every node at depth $d$ before touching
depth $d+1$. The tree stays balanced. Capacity is controlled by
max_depth. - Leaf-wise (LightGBM): keep every splittable leaf in a queue, and always split the
one with the highest gain, wherever it is. The tree becomes deep and lopsided.
Capacity is controlled by
num_leaves.
For a fixed number of leaves, leaf-wise reaches a lower loss — it spends its budget
where the gain is, instead of spreading it evenly. The cost is that it can drive a
single branch very deep and overfit, which is why num_leaves (and
min_data_in_leaf) matter far more than max_depth in LightGBM.
LEAF-WISE growth (LightGBM), num_leaves = 4:
step 1: split leaf holding 12 rows on spike_rate <= 3.55 gain 37.2604
step 2: split leaf holding 6 rows on line_length <= 40.00 gain 3.3292 (next best leaf offered 1.3342)
step 3: split leaf holding 6 rows on line_length <= 27.50 gain 1.3342
resulting leaves: [2, 4, 4, 2] depths [2, 2, 2, 2]
objective: -41.923833
LEVEL-WISE growth (XGBoost style), max_depth = 2 -> also 4 leaves:
resulting leaves: [4, 2, 2, 4] depths [2, 2, 2, 2]
objective: -41.923833
strategy leaves max depth objective
----------------------------------------------
leaf-wise 4 2 -41.9238
level-wise 4 2 -41.9238
----------------------------------------------
On THIS dataset the two strategies produce the identical tree - same
objective, same depth. 12 rows with clean structure simply do not offer
the highest-gain leaf anywhere for level-wise order to matter.
That is worth stating plainly rather than asserting a difference that
is not there. A dataset where it DOES matter is built below.
leaves leaf-wise level-wise
---------------------------------
2 -37.2604 -37.2604
3 -40.5896 -41.9238
4 -41.9238 -41.9238
5 -42.1450 -42.1450
6 -42.1450 -42.1450
8 -42.1450 -42.1450
---------------------------------
(lower is better; on this data the two curves lie exactly on top of
each other - the leaf budget, not the growth order, is what binds here.)
The two growth strategies, drawn
The diagrams below are built with the same leaf budget of 4 and the same gain formula. Only the choice of which leaf to split next differs.
Level-wise fills each depth completely before descending. Leaf-wise repeatedly picks the highest-gain leaf anywhere in the tree.
On this 12-row table they happen to produce the same tree - the dataset is too small and too cleanly separated for the orders to diverge. The section after this builds a dataset where they genuinely differ.
Both trees spent exactly 3 splits, and here they spent them the same way. On 12 well-separated rows the highest-gain leaf happens to be the next one in level order anyway, so the two strategies coincide.
A dataset where the growth order really does matter
The two strategies diverge when the signal is concentrated: one region of the feature needs many splits to describe, the rest needs almost none.
Below, y oscillates sharply for $x < 0.3$ and is flat afterwards. Level-wise spends
half its budget describing the flat region, because it is obliged to fill each depth.
Leaf-wise pours the budget into the oscillating part, where the gain is.
400 rows; y oscillates for x < 0.3 and is flat above it
budget leaf-wise obj level-wise obj lw depth lv depth leaf-wise better?
----------------------------------------------------------------------------------
4 -199.47 -153.72 3 2 True
6 -212.42 -212.42 3 3 True
8 -218.35 -215.45 4 3 True
12 -220.62 -220.00 5 4 True
16 -220.62 -220.62 5 5 True
----------------------------------------------------------------------------------
leaf-wise is never worse: True
and at budget 4 it is far better (-199.5 vs -153.7)
Red segments are the leaves. Level-wise wastes cuts on the flat right side;
leaf-wise concentrates them on the left where the function actually moves.
This is why num_leaves - not max_depth - is the capacity knob in LightGBM:
a depth limit barely constrains a tree that grows in one direction, and a
large num_leaves on a small dataset overfits quickly.
4. GOSS — Gradient-based One-Side Sampling
A row with a gradient near zero is already well predicted and contributes almost nothing to any split's gain. GOSS exploits that:
- Sort rows by $|g_i|$ and keep the top $a$ fraction — the under-fitted rows.
- Randomly sample a $b$ fraction of the remaining rows.
- Amplify the sampled ones by $\dfrac{1-a}{b}$ when accumulating $G$ and $H$.
The amplification is the important part. Without it, throwing away most small-gradient rows would bias the gain estimate; with it, the histogram remains an approximately unbiased estimate of the full-data one.
a = 0.3 -> keep the 3 largest |g|
b = 0.3 -> sample 3 of the remaining 9
amplification factor (1-a)/b = (0.7)/0.3 = 2.3333
id g |g| group weight g used
----------------------------------------------------------
rec05 -5.3750 5.3750 LARGE 1.0000 -5.3750
rec04 3.6250 3.6250 LARGE 1.0000 3.6250
rec00 3.5250 3.5250 LARGE 1.0000 3.5250
rec07 -3.4750 3.4750 sampled 2.3333 -8.1083
rec08 3.4250 3.4250 sampled 2.3333 7.9917
rec01 3.2250 3.2250 dropped 0.0000 0.0000
rec09 -3.1750 3.1750 dropped 0.0000 -0.0000
rec02 -2.6750 2.6750 dropped 0.0000 -0.0000
rec10 2.1250 2.1250 sampled 2.3333 4.9583
rec03 -1.0750 1.0750 dropped 0.0000 -0.0000
rec11 -0.3750 0.3750 dropped 0.0000 -0.0000
rec06 0.2250 0.2250 dropped 0.0000 0.0000
----------------------------------------------------------
rows used: 6 of 12 (50%) - the rest are skipped entirely
best split on FULL data : spike_rate <= 3.55 gain 37.2604
best split under GOSS : line_length <= 46.00 gain 45.3354
same split chosen? False
>>> On 12 rows GOSS throws away half the data and lands on a DIFFERENT
>>> split, with a gain even larger than the full-data optimum. That is not
>>> a bug in the method - it is a sample far too small for it to mean
>>> anything. GOSS is a large-n technique, so it is tested properly below.
Does the amplification actually work?
The claim is that $\frac{1-a}{b}$ makes the subsampled gain an approximately unbiased estimate of the full-data gain. On 12 rows that cannot be seen. The experiment below uses 5000 rows and repeats the sampling 200 times, comparing:
- GOSS with amplification — as LightGBM does it,
- the same subset without amplification — i.e. naively dropping rows,
against the true full-data gain.
N = 5000 rows, a = 0.3, b = 0.3, 200 repetitions
estimator mean gain std bias vs truth
--------------------------------------------------------------------
full data (truth) 582.191 0.000 0.000
GOSS with (1-a)/b 547.837 6.114 -34.354
same rows, no amplification 506.542 3.505 -75.649
--------------------------------------------------------------------
relative bias, amplified : 5.90%
relative bias, unamplified : 12.99%
amplification reduces the bias by 55% (closer to truth: True)
Note that the amplified estimate is NOT exactly unbiased, and it should not
be expected to be. The (1-a)/b factor makes the sampled SUMS G and H
unbiased, but the gain is a nonlinear function of them - a ratio of squares -
so a residual bias survives the correction. What matters in practice is that
the same split still wins, and the ranking of candidate splits is preserved.
The amplified histogram straddles the true gain; the unamplified one sits
far to the left, because dropping rows removes their gradient mass entirely.
That is the whole reason GOSS is not simply 'drop the easy rows'.
5. Checking Against the Real LightGBM
Training lightgbm with num_leaves = 3 and matching regularisation should reproduce
the same split and the same leaf outputs.
Two conventions to know when reading its dump:
leaf_valueis the absolute prediction, i.e. $\text{init} + \eta\,w^{*}$, not the increment.split_gainomits the $\tfrac12$, exactly like XGBoost's dump.
lightgbm's tree 0:
{
"split_index": 0,
"split_feature": 1,
"split_gain": 74.52069854736328,
"threshold": 3.5500000000000003,
"decision_type": "<=",
"default_left": true,
"missing_type": "None",
"internal_value": 3.725,
"internal_weight": 12,
"internal_count": 12,
"left_child": {
"leaf_index": 0,
"leaf_value": 3.0328571761115675,
"leaf_weight": 6,
"leaf_count": 6
},
"right_child": {
"split_index": 1,
"split_feature": 0,
"split_gain": 6.658480167388916,
"threshold": 39.00000000000001,
"decision_type": "<=",
"default_left": true,
"missing_type": "None",
"internal_value": 4.41714,
"internal_weight": 6,
"internal_count": 6,
"left_child": {
"leaf_index": 1,
"leaf_value": 3.8700000448773304,
"leaf_weight": 1.9999999999999998,
"leaf_count": 2
},
"right_child": {
"leaf_index": 2,
"leaf_value": 4.607000045950214,
"leaf_weight": 4,
"leaf_count": 4
our leaf-wise tree with num_leaves = 3:
leaf rows G H w* init + eta*w*
----------------------------------------------------------
0 6 16.1500 6 -2.30714 3.032857
1 4 -14.7000 4 2.94000 4.607000
2 2 -1.4500 2 0.48333 3.870000
----------------------------------------------------------
root split : lightgbm = spike_rate <= 3.5500, gain 74.5207
ours = spike_rate <= 3.5500, gain 74.5207 (x2 convention)
MATCH: True / gain True
leaf values ours : [np.float64(3.032857), np.float64(3.87), np.float64(4.607)]
leaf values lightgbm : [3.032857, 3.87, 4.607]
MATCH: True
predictions MATCH lightgbm: True
ours : [3.0329 3.0329 4.607 3.87 3.0329 4.607 3.0329 4.607 3.0329 4.607 3.0329 3.87 ]
lightgbm : [3.0329 3.0329 4.607 3.87 3.0329 4.607 3.0329 4.607 3.0329 4.607 3.0329 3.87 ]
6. Summary
| Idea | What it changes | Cost of the approximation |
|---|---|---|
| Histogram binning | thresholds $n-1 \to \#\text{bins}$ | splits limited to bin edges |
| Histogram subtraction | sibling is free | none — exact |
| Leaf-wise growth | split the best leaf, not the next level | deeper, easier to overfit |
| GOSS | uses a fraction of rows | small variance, corrected by $\frac{1-a}{b}$ |
| EFB | bundles mutually-exclusive sparse columns | negligible on dense data |
The one idea: the mathematics of gradient boosting was already settled by XGBoost. LightGBM's contribution is that the search — not the objective — is where the time goes, so it approximates the search and leaves the objective alone.
The practical consequence: because growth is leaf-wise, num_leaves is the real
capacity knob. Setting max_depth alone does not constrain a LightGBM model the way it
constrains an XGBoost one, and a large num_leaves on a small dataset overfits quickly.
What is deliberately left out: Exclusive Feature Bundling in detail, native categorical handling, DART, and the distributed histogram-merging protocol.