7.1 Overview and core innovations
LightGBM (Light Gradient Boosting Machine) is a highly efficient gradient boosted decision tree system from Guolin Ke and colleagues at Microsoft Research Asia, working with Peking University, published at NIPS 2017 (now NeurIPS; paper LightGBM: A Highly Efficient Gradient Boosting Decision Tree). The next milestone after XGBoost, LightGBM not only speeds up training by orders of magnitude but also shows clear advantages in memory efficiency, high-dimensional sparse data and large-scale settings.
Four core techniques are the foundation of its efficiency:
- Histogram-based decision trees: continuous features are discretized into a limited number of bins, and statistics and split finding happen on the histogram, which takes per-feature split search from $O(\#\text{data})$ down to $O(\#\text{bin})$ (building the histogram itself is still $O(\#\text{data})$). Histogram algorithms predate LightGBM — they’re the foundation here, and the next three items are what the paper contributes.
- Leaf-wise growth: each step splits the leaf with the largest gain rather than splitting every node at a level uniformly. For the same number of splits it reaches lower training loss and converges faster.
- GOSS (Gradient-based One-Side Sampling): sample by gradient magnitude — keep all large-gradient samples, randomly sample the small-gradient ones, and scale the sampled small-gradient samples by a constant weight to compensate for the changed distribution. That cuts the sample count sharply while largely preserving accuracy (the paper gives an approximation-error bound).
- EFB (Exclusive Feature Bundling): identify mutually exclusive features in high-dimensional sparse data and bundle them into a single feature, which reduces dimensionality and speeds up both histogram construction and split finding.
The key point: LightGBM isn’t just XGBoost with engineering polish. It redesigns the basic tree-learning loop at the algorithm level — histograms instead of pre-sorting, leaf-wise instead of level-wise, and GOSS and EFB attacking the dominant cost of histogram construction from the sample side and the feature side respectively. That’s what keeps it efficient on large data (tens of millions of samples, tens of thousands of features).
7.2 Histogram-based decision trees
7.2.1 The idea: discretize features into k bins
Classic GBDT and XGBoost’s exact greedy algorithm sort and scan every possible split point on every feature. At millions of samples that pre-sorting becomes the bottleneck. The histogram approach changes the paradigm: discretize continuous features into at most $k$ bins (the max_bin parameter, default 255), build histograms over the binned values for the statistics, and reduce split search from $O(\#\text{data})$ to $O(\#\text{bin})$.
Concretely, there are two stages:
Stage one: binning
- For each continuous feature, divide its range into $k$ intervals (bins).
- Use a subsample (the
bin_construct_sample_cntparameter, default 200,000 samples) to determine bin boundaries (roughly equal-frequency / quantile based). - Map the original floating-point values to integer bin indices. LightGBM picks the storage type from
max_binautomatically —uint8_twhenmax_bin=255, for instance.
Stage two: histogram traversal (split finding)
- For each leaf, build a histogram for each feature.
- Each bin accumulates the gradient sum $\sum g_i$, the Hessian sum $\sum h_i$ and the sample count (Algorithm 1 in the paper lists only the gradient sum and sample count; the implementation also accumulates the Hessian).
- Traverse all bins, compute the split gain, and find the best split point.
7.2.2 The procedure
The full LightGBM histogram procedure:
- Discretize: for each continuous feature, split its values into $k$ bins based on quantiles of the training data.
- Map samples: replace each sample’s raw feature value with its bin index.
- Build histograms: for each feature at the current node, initialize a histogram array of length $k$.
- Aggregate: walk the samples in the node and add $g_i$ and $h_i$ into the bin each sample maps to.
- Find the split: treat each bin boundary as a candidate, compute the gain, and take the best.
- Recurse: repeat steps 3-5 on the children until a stopping condition is met.
7.2.3 Complexity (versus pre-sorting)
| Stage | Pre-sorted (XGBoost exact) | Histogram (LightGBM) | Why it’s better |
|---|---|---|---|
| Preprocessing | $O(\#\text{data} \times \#\text{feature} \times \log \#\text{data})$ | Binning: determine boundaries on a sample, then map linearly | No need to sort the full dataset |
| Histogram construction (per node) | No such step | $O(\#\text{data} \times \#\text{feature})$ | Simple accumulation, but still the dominant cost |
| Split search (per node) | $O(\#\text{data} \times \#\text{feature})$ | $O(\#\text{bin} \times \#\text{feature})$ | $\#\text{bin} \ll \#\text{data}$ (255 by default vs. millions) |
| Memory | Raw float values plus pre-sort indices | Only bin indices (e.g. uint8_t), no pre-sort information | Much lower memory |
| Cache friendliness | Poor (random access to gradient statistics) | Good (sequential access over histogram arrays) | Higher cache hit rate |
| GPU acceleration | Complicated | A natural fit | Histogram aggregation parallelizes well |
Since $\#\text{bin}$ (255 by default) is far smaller than $\#\text{data}$ (millions, typically), the split search step is nearly free: on a 10-million-sample dataset, pre-sorting examines about 10 million candidates, while the histogram only scans 255 bin boundaries. But overall training doesn’t get ten-thousand times faster, because building the histogram still visits every sample in the node at $O(\#\text{data} \times \#\text{feature})$. The paper notes this step dominates total cost, which is why LightGBM adds GOSS to reduce $\#\text{data}$ and EFB to reduce $\#\text{feature}$.
7.2.4 Histogram subtraction
Exploiting the binary tree structure, LightGBM uses histogram subtraction. In a binary tree, a parent’s histogram equals the sum of its children’s:
$$ \mathrm{Hist}_{\text{parent}} = \mathrm{Hist}_{\text{left}} + \mathrm{Hist}_{\text{right}} $$($\mathrm{Hist}$ here avoids confusion with the Hessian sum $H$; the identity holds bin by bin for gradient sums, Hessian sums and sample counts.) So for each split you only build the histogram of the smaller child and get the other by subtracting:
$$ \mathrm{Hist}_{\text{sibling}} = \mathrm{Hist}_{\text{parent}} - \mathrm{Hist}_{\text{node}} $$Why it helps:
- The conventional approach walks the samples twice per split, once per child, at a cost proportional to the parent’s sample count.
- With subtraction you only walk the smaller child — at most half the parent’s samples — and get the other side by subtraction, so histogram construction visits at most half as many samples.
- The subtraction costs only $O(\#\text{bin} \times \#\text{feature})$, independent of sample count, far less than rebuilding.
The same optimization applies under leaf-wise growth: after splitting a leaf, only the smaller of the two new leaves needs a histogram built.
7.2.5 The regularizing effect of discretization
Binning doesn’t just speed things up; it also regularizes in a way that may be unexpected:
- Less overfitting: squeezing continuous values into a limited set of bins quantizes the feature, which makes the model less sensitive to tiny fluctuations in the training data.
- Quantization noise (an intuition): discretization makes split points less precise; but each tree is only one weak learner in an ensemble, so slightly coarse split points usually have limited effect on final accuracy and can sometimes reduce fitting to small fluctuations in the training data.
- What the docs say: a smaller
max_binmay lower training accuracy while improving generalization (easing overfitting). Whether it actually helps depends on the data — confirm it on a validation set.
7.3 Leaf-wise growth
7.3.1 Compared with level-wise growth
Traditional tree boosting (including XGBoost’s default grow_policy='depthwise') grows level-wise: the tree grows by levels, and all nodes at a level split together. LightGBM grows leaf-wise (also called best-first): each step splits whichever current leaf has the largest gain (largest loss reduction). The strategy comes from best-first decision trees (Shi, 2007), and XGBoost’s hist / approx methods can use it too via grow_policy='lossguide'.
graph TD
subgraph LevelWise["Level-wise: grow by level, all nodes at a level split together"]
A1["Root"] --> B1["Level 1"]
A1 --> B2["Level 1"]
B1 --> C1["Level 2"]
B1 --> C2["Level 2"]
B2 --> C3["Level 2"]
B2 --> C4["Level 2"]
end
subgraph LeafWise["Leaf-wise: split only the highest-gain leaf each time"]
A2["Root"] --> B3["Gain=0.8"]
A2 --> B4["Gain=0.3"]
B3 --> C5["Gain=0.6"]
B3 --> C6["Gain=0.5"]
B4 --> C7["..."]
B4 --> C8["..."]
end
style A1 fill:#f9f,stroke:#333
style A2 fill:#f9f,stroke:#333
| Dimension | Level-wise | Leaf-wise |
|---|---|---|
| Growth | Split by level; all nodes at a level split together | Split only the highest-gain leaf each time |
| Tree shape | Balanced, even across levels | Unbalanced; some branches may go deep |
| Convergence | Slower; wasted splits (low-gain nodes are split anyway) | Faster; focuses on high-gain splits, each yielding the largest loss reduction |
| Overfitting risk | Lower (depth is controllable) | Higher (needs max_depth or num_leaves limits) |
| Training loss at equal leaf count | Higher | Usually lower (per the docs, leaf-wise tends to reach lower loss at fixed #leaf) |
| Representative implementations | XGBoost (default depthwise), sklearn GradientBoosting* | LightGBM, XGBoost (lossguide), sklearn HistGradientBoosting* |
| When | Small data, balanced trees wanted | Large data, training efficiency wanted |
7.3.2 The gain formula
The gain under leaf-wise growth is essentially the same as XGBoost’s (Section 6.3.6 of XGBoost), both coming from the second-order approximation. LightGBM’s source writes a leaf’s score as $\frac{G^2}{H+\lambda}$, with no $\frac{1}{2}$ factor, so the gain is
$$ \mathrm{Gain} = \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} $$A split happens only when $\mathrm{Gain}$ exceeds min_gain_to_split (default 0). Here $G_L, G_R$ are the gradient sums of the left and right children, $H_L, H_R$ the Hessian sums, and $\lambda$ corresponds to lambda_l2 (default 0, whereas XGBoost’s lambda defaults to 1). With lambda_l1 set, $G$ becomes the soft-thresholded $\operatorname{sign}(G)\max(\lvert G \rvert - \lambda_1, 0)$, as in XGBoost.
Because of the missing $\frac{1}{2}$, the same split scores twice the gain in LightGBM as the bracketed expression in XGBoost, so
min_gain_to_splitand XGBoost’sgammaaren’t numerically interchangeable.
The heart of leaf-wise growth: among all candidate leaves, split the one with the largest gain above. That contrasts sharply with level-wise’s even-handedness, which splits every node at a level whether or not the gain is worth it.
7.3.3 Why it’s faster, and why depth still needs controlling
Why it’s faster:
- Concentrated effort: level-wise splits low-gain (even near-zero-gain) nodes anyway, which wastes computation. Leaf-wise puts effort where the potential is, and every split delivers the largest loss reduction.
- Lower loss for the same number of splits: at the same split count (the same compute), leaf-wise usually reaches lower training loss, because it works on the region that most needs splitting.
- Good fit with histogram subtraction: leaf-wise splits one leaf at a time, so histograms only need building for that leaf and its children.
Overfitting risk and control:
- Leaf-wise can produce badly unbalanced trees — some branches very deep (overfitting small regions), others shallow.
- Unchecked, it can produce deep leaves holding only a few samples, which overfits.
LightGBM controls this with the following parameters:
| Parameter | Default | Effect |
|---|---|---|
max_depth | -1 (unlimited) | Maximum tree depth, capping growth |
num_leaves | 31 | Maximum leaves, the main complexity control under leaf-wise |
min_data_in_leaf | 20 | Minimum samples per leaf, keeping leaves from being too sparse |
min_sum_hessian_in_leaf | 0.001 | Minimum Hessian sum per leaf, controlling leaf confidence |
Rule of thumb: a binary tree of depth $d$ has at most $2^d$ leaves, so if you set both, num_leaves <= 2^max_depth should hold. With max_depth = 7, a num_leaves above 128 is meaningless. The official tuning guide recommends going well below $2^{\text{max\_depth}}$. Note that even with max_depth set, trees still grow leaf-wise; max_depth is only an extra cap.
7.4 GOSS (Gradient-based One-Side Sampling)
7.4.1 The idea: large-gradient samples contribute more
GOSS starts from an observation about gradient distributions: in each gradient boosting round, a sample’s gradient magnitude reflects how well the model has fitted it. Large-gradient samples are under-trained; small-gradient ones are already fitted reasonably well. So large-gradient samples contribute more to the information gain.
GOSS sampling:
- Keep all large-gradient samples (the top $a \times 100\%$ by gradient magnitude).
- Randomly sample small-gradient samples ($b \times 100\%$ of the rest).
- Rescale the sampled small-gradient samples by a constant multiplier so that the gain estimate stays unbiased.
As a result GOSS builds each tree from roughly $(a + b) \times 100\%$ of the samples. In LightGBM, $a$ and $b$ are the parameters top_rate (default 0.2) and other_rate (default 0.1), so 30% of samples per round by default; the paper’s experiments used $a=b=0.05$ or $a=b=0.1$ and found accuracy nearly identical to training on everything.
7.4.2 The procedure (pseudocode)
flowchart TD
A["Input: training set I, parameters a, b"] --> B["Compute gradients g_i for all samples"]
B --> C["Sort descending by |gradient|"]
C --> D["topSet = first a * len(I) samples"]
C --> E["randomly pick b * len(I) from the rest"]
D --> F["usedSet = topSet + randSet"]
E --> F
F --> G["scale randSet samples by (1-a)/b"]
G --> H["build a tree on usedSet"]
H --> I{"stopping condition met?"}
I -->|No| B
I -->|Yes| J["output the final model"]
Pseudocode:
- Input: training data $I$, large-gradient sampling rate $a$, small-gradient sampling rate $b$
- Compute the correction factor: $fact \leftarrow (1-a)/b$
- Number of large-gradient samples: $topN \leftarrow a \times |I|$
- Number of random samples: $\mathit{randN} \leftarrow b \times \lvert I \rvert$
- For each iteration:
- Compute the gradients $g_i$ for all samples
- Sort descending by gradient magnitude to get the index array $\mathit{sorted}$
- $\mathit{topSet} \leftarrow \mathit{sorted}[1:\mathit{topN}]$ // keep the large-gradient samples
- $\mathit{randSet} \leftarrow \operatorname{RandomPick}(\mathit{sorted}[\mathit{topN}+1:\mathit{end}],\ \mathit{randN})$ // sample the small-gradient ones
- $\mathit{usedSet} \leftarrow \mathit{topSet} \cup \mathit{randSet}$
- Initialize weights $w_i \leftarrow 1$ (for all samples)
- For each sample in $\mathit{randSet}$: $w_i \leftarrow w_i \times \mathit{fact}$ // rescale the small-gradient samples
- Build a tree on the weighted samples $(\mathit{usedSet}, -g_{\mathit{usedSet}}, w_{\mathit{usedSet}})$
- Output the final model
Implementation details (LightGBM source,
src/boosting/goss.hpp)
- The sort key is $\lvert g_i h_i \rvert$, not $\lvert g_i \rvert$ alone; for squared loss ($h_i$ constant) the two are equivalent.
- The factor $\frac{1-a}{b}$ multiplies both the gradients and the Hessians of the sampled small-gradient samples.
- The first $\lfloor 1/\text{learning\_rate} \rfloor$ rounds skip GOSS sampling (10 rounds at a learning rate of 0.1, for instance), because early gradients are generally large and sampling gains little.
- From version 4.0, GOSS is enabled with
data_sample_strategy='goss'; the oldboosting='goss'still works but warns and is interpreted asboosting='gbdt'plusdata_sample_strategy='goss'.
7.4.3 The corrected information-gain formula
GOSS estimates the gain on the sampled set and introduces the constant $\frac{1-a}{b}$ to scale the gradient sum over $B$ back up to the size of the full small-gradient set $A^c$, which makes the estimate approximately unbiased.
The paper measures split quality with the variance gain. At a node with sample set $O$, splitting on feature $j$ at threshold $d$:
$$ V_{j\mid O}(d) = \frac{1}{n_O}\left[\frac{\left(\sum_{\{x_i \in O:\, x_{ij} \le d\}} g_i\right)^2}{n_{l\mid O}^j(d)} + \frac{\left(\sum_{\{x_i \in O:\, x_{ij} > d\}} g_i\right)^2}{n_{r\mid O}^j(d)}\right] $$where $n_O$ is the node’s sample count and $n_{l\mid O}^j(d)$, $n_{r\mid O}^j(d)$ are the left and right counts. It’s the $\frac{G^2}{H+\lambda}$ of XGBoost with $h_i = 1$ and $\lambda = 0$.
Let $A$ be the large-gradient set (all kept, fraction $a$), $A^c$ the rest, and $B$ a random subset of $A^c$ (size $b \times n$). Let $A_l = \{x_i \in A \mid x_{ij} \leq d\}$ and $A_r = \{x_i \in A \mid x_{ij} > d\}$ be the split of $A$ at $d$, with $B_l, B_r$ defined likewise.
GOSS’s gain estimate is
$$ \tilde{V}_j(d) = \frac{1}{n}\left[ \frac{\left(\sum_{x_i \in A_l} g_i + \frac{1-a}{b} \sum_{x_i \in B_l} g_i\right)^2}{n_l^j(d)} + \frac{\left(\sum_{x_i \in A_r} g_i + \frac{1-a}{b} \sum_{x_i \in B_r} g_i\right)^2}{n_r^j(d)} \right] $$Notation:
| Symbol | Meaning |
|---|---|
| $A$ | Large-gradient sample set (all kept, fraction $a$) |
| $B$ | Random subset sampled from the small-gradient samples (fraction $b$) |
| $A_l, A_r$ | Large-gradient samples left and right of the split |
| $B_l, B_r$ | Sampled small-gradient samples left and right of the split |
| $\frac{1-a}{b}$ | Compensation factor: $B$ holds $bn$ samples but stands for $(1-a)n$ samples of $A^c$; scaling restores the expected gradient sum to the true sum over $A^c$ |
| $n_l^j(d), n_r^j(d)$ | Sample counts left and right of split $d$ |
Theoretical guarantee: Theorem 3.2 of the paper shows that with probability at least $1-\delta$ the approximation error satisfies
$$ \mathcal{E}(d) \leq C_{a,b}^2 \ln\frac{1}{\delta} \cdot \max\left\{\frac{1}{n_l^j(d)}, \frac{1}{n_r^j(d)}\right\} + 2DC_{a,b}\sqrt{\frac{\ln(1/\delta)}{n}} $$where the approximation error is $\mathcal{E}(d) = \left\lvert \tilde{V}_j(d) - V_j(d) \right\rvert$, $C_{a,b} = \frac{1-a}{\sqrt{b}} \max_{x_i \in A^c} \lvert g_i \rvert$, $D = \max\left(\bar{g}_l^j(d), \bar{g}_r^j(d)\right)$, and $\bar{g}_l^j(d)$, $\bar{g}_r^j(d)$ are the mean absolute gradients on each side.
The key conclusion: the error is asymptotically $O\left(\frac{1}{n_l^j(d)} + \frac{1}{n_r^j(d)} + \frac{1}{\sqrt{n}}\right)$. As long as splits aren’t too unbalanced ($n_l^j(d), n_r^j(d) \ge O(\sqrt{n})$), the second term dominates and vanishes at $O(1/\sqrt{n})$ as $n$ grows — meaning that with plenty of data GOSS’s approximation is quite accurate. The paper also notes that random sampling is the special case $a=0$, and that GOSS’s error is often smaller.
7.4.4 Compared with AdaBoost’s sampling
| Feature | AdaBoost sampling | GOSS |
|---|---|---|
| Basis for weighting | Sample weights (set by earlier classifiers’ error rates) | Gradient magnitude (set by the current model’s fit) |
| Sampling | Weighted training directly (reweighting) or weighted resampling with replacement | Keep large-gradient samples, sample small-gradient ones at random |
| Applies to | AdaBoost / weighted boosting | GBDT / LightGBM (gradient magnitude as a proxy for informativeness) |
| Correction | None explicit (weights normalize naturally) | Explicit constant multiplier $(1-a)/b$ correcting the gain |
| Theory | Bound showing training error falls exponentially with rounds | Bound on the approximation error of the variance-gain estimate (Theorem 3.2) |
| Core idea | Focus on hard, misclassified samples | Focus on samples the model hasn’t fitted (large gradients) |
AdaBoost’s sample weights directly reflect accumulated misclassification; GBDT can accept external sample weights, but which samples need attention in each round is usually expressed by the current loss’s gradient. GOSS uses gradient magnitude as a proxy for how much information a sample carries, which keeps the “focus on hard samples” intuition while fitting GBDT’s gradient-based framework.
7.5 EFB (Exclusive Feature Bundling)
7.5.1 The idea: bundle mutually exclusive features
EFB tackles feature redundancy in high-dimensional sparse data. Real data — especially after one-hot encoding or bag-of-words representation — is very high-dimensional and very sparse. Many features are mutually exclusive: rarely non-zero in the same row. For example:
- One-hot encoded categoricals: exactly one of the columns is 1 in each row.
- Bag-of-words in text: each document contains only a few terms.
EFB bundles mutually exclusive features into a single feature, reducing dimensionality without losing information, which speeds up histogram construction and split finding.
7.5.2 Conflict graph plus a greedy bundling algorithm
The paper proves (Theorem 4.1) that partitioning features into the minimum number of exclusive bundles is NP-hard. The proof reduces graph coloring to it: given any graph $G=(V,E)$, build a feature per vertex, so that two features joined by an edge are simultaneously non-zero on some sample (i.e. they conflict); then the vertices of one color correspond exactly to an exclusive bundle.
Since the exact problem is intractable, LightGBM uses a greedy approximation:
flowchart TD
A["Input: feature set F"] --> B["Build the conflict graph G=(V,E)"]
B --> C["Sort features by degree descending"]
C --> D["Initialize bundles as an empty list"]
D --> E{"Any unassigned features?"}
E -->|Yes| F["Take the next feature f"]
F --> G["Find the bundle with the fewest conflicts"]
G --> H{"Conflicts within threshold?"}
H -->|Yes| I["Add f to that bundle"]
H -->|No| J["Create a new bundle containing f"]
I --> E
J --> E
E -->|No| K["Output the bundles"]
Pseudocode:
- Input: feature set $F$, maximum conflict count $K$ (the paper’s main text describes the allowed conflict level with a per-bundle maximum conflict rate $\gamma$, and notes that randomly polluting a few feature values affects training accuracy by at most $O\left([(1-\gamma)n]^{-2/3}\right)$, so a small $\gamma$ balances accuracy and efficiency well)
- Build the conflict graph $G = (V, E)$:
- one vertex per feature
- add edge $(i,j)$ when features $i$ and $j$ are both non-zero on some row, weighted by the number of conflicts
- Sort features by vertex degree descending
- Initialize: $\mathit{bundles} \leftarrow []$, plus each bundle’s accumulated conflict count
- For each feature $f$ in that order:
- Check the existing bundles in turn: if the conflicts between $f$ and a bundle plus that bundle’s existing conflicts are $\le K$, put $f$ in it and stop checking
- If no bundle can take $f$: create a new bundle containing only $f$
- Output: $\mathit{bundles}$
In the paper this step is “put it in the first bundle that fits” (first-fit), not “find the bundle with the fewest conflicts.”
Complexity:
- Greedy bundling (Algorithm 3 in the paper) costs $O(\#\text{feature}^2)$ and runs once before training.
- At millions of features that’s still slow, so the paper gives a faster variant: skip the graph and sort features by number of non-zero values descending (more non-zeros means more likely to conflict, similar in effect to sorting by degree).
- The paper’s main experiments use $\gamma = 0$, i.e. no conflicts allowed. In LightGBM 4.x, EFB is toggled by
enable_bundle(defaulttrue), and no conflict-rate parameter is exposed (settingmax_conflict_ratein 4.7.0 reports Unknown parameter).
7.5.3 Why one-hot categoricals are naturally exclusive
One-hot encoding turns a $K$-category feature into $K$ binary features:
- For any sample exactly one of the $K$ is 1 and the rest are 0.
- So all $K$ are pairwise fully exclusive (conflict rate 0).
- EFB can bundle the $K$ features into one, taking the feature count from $K$ down to 1.
The paper’s experiments show EFB brings substantial speedups on datasets with many one-hot or otherwise sparse features (KDD Cup 2010/2012, for instance). Beyond one-hot features, EFB also bundles sparse features that are “implicitly exclusive.”
7.5.4 The offset technique
Once several features are bundled into one, values need to be traceable back to their original feature. LightGBM uses offsets.
Say we bundle two features:
- Feature A: range $[0, 10)$
- Feature B: range $[0, 20)$
Add an offset of 10 to feature B, taking its range to $[10, 30)$. The bundle’s range becomes $[0, 30)$ (the paper writes $[0, 30]$), and the histogram can tell which original feature each value came from.
In general:
$$ \text{newBin}[i] = \begin{cases} F[j].\text{bin}[i] + \text{binRanges}[j] & \text{if } F[j].\text{bin}[i] \neq 0 \\ 0 & \text{if } F[j].\text{bin}[i] = 0 \text{ for all } j \end{cases} $$where the cumulative offsets $\text{binRanges}$ accumulate each feature’s bin count:
$$ \text{binRanges} = \left[0,\ \#\text{bin}(F_1),\ \#\text{bin}(F_1)+\#\text{bin}(F_2),\ \dots\right] $$Because features within a bundle are exclusive, at most one is non-zero per sample, so $\text{newBin}[i]$ is uniquely determined (Algorithm 4 in the paper; with a few conflicts, later features overwrite earlier values). All the features’ zero values share bin 0 of the bundle.
Example (bin 0 represents zero, and each feature’s non-zero bins follow):
| Original feature | Bins for non-zero values | Offset | Resulting bin in the bundle |
|---|---|---|---|
| F1 | $1 \sim 2$ | 0 | $1 \sim 2$ |
| F2 | $1 \sim 3$ | 2 | $3 \sim 5$ |
| F3 | $1 \sim 4$ | 5 | $6 \sim 9$ |
The bundle has $1 + 2 + 3 + 4 = 10$ bins (the shared bin 0 plus each feature’s non-zero bins), and the three features’ ranges don’t overlap.
7.5.5 Measured effect
The paper’s experiments (Table 2, average time per iteration) show:
- With EFB alone (EFB_only versus lgb_baseline), sparse large datasets speed up markedly: about $8.5\times$ on Allstate (6.07 s down to 0.71 s per iteration), $6.3\times$ on KDD10, $8.3\times$ on KDD12 and $5.1\times$ on Flight Delay; the dense LETOR dataset barely moves (0.49 s to 0.46 s). These datasets range from 136 features (LETOR) to 54 million (KDD12).
- Adding GOSS as well (full LightGBM) with 10%-20% of the data gives GOSS another near-$2\times$ speedup on its own.
- EFB removes the need to maintain a separate non-zero data table per sparse feature while building trees, which saves memory.
- Bundling previously scattered features improves spatial locality and markedly raises cache hit rates.
7.6 Handling categorical features
LightGBM supports categorical features natively, with no manual one-hot encoding. That matters most for high-cardinality categoricals (user IDs, product IDs), where one-hot encoding produces high-dimensional sparse features that are both inefficient and prone to overfitting.
The mechanism
Category values must be encoded as non-negative integers: declare categorical features with
categorical_feature. The core library requires integer category values (cast toint32; negative values are treated as missing, and consecutive integers starting at 0 are best) and will not map strings to integers automatically. In the Python package, if the input is a pandas DataFrame withcategorycolumns, the integer codes are extracted automatically, and you can usecategorical_feature='auto'(the default; the latest docs say only unordered category columns are detected automatically, ordered ones being treated as numeric). Categories unseen in training are treated as missing at prediction time.Statistics-based splitting: for a categorical feature, LightGBM doesn’t look for a single numeric threshold; it partitions the set of categories into two subsets. With $k$ categories there are $2^{k-1}-1$ bipartitions, which is infeasible to enumerate — but for regression trees an efficient solution exists (Fisher, 1958) that finds the optimal partition in about $O(k \log k)$. Specifically:
- At the current node, compute each category’s gradient sum $G_c$ and Hessian sum $H_c$.
- Sort categories by $\frac{G_c}{H_c + \text{cat\_smooth}}$ (the docs describe sorting by
sum_gradient / sum_hessian; the implementation adds the smoothing termcat_smoothto the denominator). - Scan the sorted sequence from both ends like a continuous feature to find the best two-subset partition.
- When the category count doesn’t exceed
max_cat_to_onehot(default 4), use one-vs-rest splitting instead (one category against the rest).
Regularization parameters for categorical splits:
cat_smooth(default 10, reducing noise from small categories),cat_l2(default 10, extra L2 regularization on categorical splits),max_cat_threshold(default 32, capping the number of split points considered),min_data_per_group(default 100, minimum samples per category group). The docs recommendmin_data_per_groupandcat_smoothto curb overfitting with few samples or many categories; for features with very many categories, treating the integer codes as numeric often works better.Avoiding one-hot’s curse of dimensionality: for high-cardinality categoricals (millions of user IDs), one-hot encoding yields a million-dimensional sparse matrix. LightGBM treats it as one feature whose histogram has as many bins as categories (or the capped maximum), which is far more memory- and compute-efficient than one-hot.
Usage:
| |
7.7 Parallel learning and memory optimization
What follows is based on the “Optimization in Distributed Learning” section of LightGBM’s official Features documentation. The parallel mode is selected by tree_learner: serial (default, single machine), feature, data or voting.
7.7.1 Feature parallelism (tree_learner='feature')
Classic feature parallelism: data is split by column across workers. Each worker finds a local best split on its feature subset, they communicate to agree on the global best, the worker holding that feature performs the split, and then broadcasts the left/right assignment for every sample. Two drawbacks: the split itself is $O(\#\text{data})$ and can’t be parallelized, and broadcasting the assignment costs about $O(\#\text{data}/8)$ (1 bit per sample).
LightGBM’s feature parallelism: every worker holds the full dataset, and they just search different feature subsets:
- Each worker finds the best split {feature, threshold} among the features it owns.
- They communicate and agree on the global best.
- Every worker performs that split locally (since all have the full data, no assignment needs broadcasting).
Because the split is still $O(\#\text{data})$, feature parallelism gives limited speedup with many samples; use data parallelism there.
7.7.2 Data parallelism (tree_learner='data')
Classic data parallelism: data is split by row; each worker builds local histograms, which are merged into a global histogram for split finding. The drawback is communication volume: about $O(\#\text{machine} \times \#\text{feature} \times \#\text{bin})$ with point-to-point communication, or about $O(2 \times \#\text{feature} \times \#\text{bin})$ with collective operations such as All Reduce.
LightGBM’s data-parallel optimizations:
- Reduce Scatter instead of full merging: different workers merge histograms for different (non-overlapping) features, each finds a local best split on its merged histograms, then they synchronize to get the global best.
- Combined with histogram subtraction: each split only communicates the smaller child’s histogram, the other coming from subtraction.
- Together, the communication cost is about $O(0.5 \times \#\text{feature} \times \#\text{bin})$.
7.7.3 Voting parallelism (tree_learner='voting')
Voting parallelism reduces data parallelism’s communication to a constant independent of feature count. It comes from PV-Tree (Meng et al., NIPS 2016) and uses two rounds of voting:
- Local voting: each worker selects its top-$k$ features by local gain (the
top_kparameter, default 20). - Global voting: votes are aggregated and the top-$2k$ features globally are selected by vote count.
- Only those $2k$ features’ full histograms are collected, merged, and used to determine the best split.
A larger top_k is more accurate but slower. The official Distributed Learning Guide advises: feature parallelism for few samples; data parallelism for many samples and few features; voting parallelism when both are large.
7.7.4 Memory optimizations
| Technique | Mechanism | Effect |
|---|---|---|
| Histogram storage | Store bin indices as uint8 | 75% less memory than storing raw values as float32 |
| Histogram subtraction | Parent histogram minus child histogram | At least halves the sample traversal for histogram construction |
| EFB | Bundle exclusive features | Fewer features, fewer histogram builds |
| GOSS | Sample the small-gradient samples | Each tree uses about $(a+b)$ of the samples (0.2 + 0.1 by default, a 70% reduction) |
| Native categorical support | Avoids high-dimensional one-hot | Much lower memory with high-cardinality categoricals |
7.8 LightGBM in Kaggle and in production
Since its 2017 release, LightGBM has quickly become a standard tool in Kaggle competitions and in industry.
Kaggle:
- On a large number of structured-data competitions, LightGBM is a first-choice baseline alongside XGBoost.
- Its faster training is a clear advantage in competitions that need rapid iteration and many model experiments.
- In memory-constrained environments (Kaggle Notebooks, for instance), its memory efficiency lets it handle larger data.
In production:
- Ad click-through rate prediction (CTR): large-scale, high-dimensional sparse ad features are exactly what GOSS and EFB were designed for, and LightGBM is widely used for CTR estimation.
- Recommender systems: as a feature-interaction model over high-dimensional sparse user-item features.
- Credit risk: for credit scoring and fraud detection, LightGBM trains efficiently and supports model explanation through feature importance and SHAP values (
predict(..., pred_contrib=True)), which makes it a common choice. - Time series forecasting: with appropriate feature engineering, LightGBM does well in a variety of forecasting competitions.
Choosing between it and XGBoost (a rough empirical guide; the sample-size thresholds aren’t hard lines — see Comparing Algorithms and Choosing One for detail):
- With little data (under 10,000 samples) the two are close; XGBoost’s exact greedy may be slightly better.
- At medium scale (10,000-100,000), LightGBM’s speed advantage starts to show.
- At larger scale (over 100,000, or high-dimensional sparse), LightGBM usually trains faster with less memory and is the default pick.
- When accuracy is paramount, tune both and stack them.
7.9 The Python API and key parameters
LightGBM offers two Python interfaces: the native lgb.train one and a scikit-learn compatible one.
Native API (lgb.train)
| |
Scikit-learn compatible API
| |
In LightGBM 4.7.0, the sklearn interface’s
fit()warns thateval_setis deprecated in favor of the keyword argumentseval_X=..., eval_y=...; earlier versions support onlyeval_set, so the code here still uses it — both forms currently run. The sklearn interface also usesbest_iteration_automatically inpredict/predict_probaafter early stopping.
Key parameters
| Parameter | Meaning | Default | Tuning advice |
|---|---|---|---|
num_leaves | Maximum leaves | 31 | The key leaf-wise complexity control. With max_depth = $d$ it shouldn’t exceed $2^d$, and in practice is usually well below $2^d$. |
max_depth | Maximum tree depth | -1 | Limits overfitting; $\le 0$ means unlimited. Typically 5-10. |
learning_rate | Learning rate | 0.1 | Typical values 0.01-0.3. Smaller values go with more n_estimators. |
min_data_in_leaf | Minimum samples per leaf | 20 | Guards against overfitting; raise it for big data, lower it for small. Named min_child_samples in sklearn. |
feature_fraction | Column sampling fraction | 1.0 | Fraction of features sampled per tree; prevents overfitting, typically 0.8. colsample_bytree in sklearn; per-node sampling is feature_fraction_bynode. |
bagging_fraction | Row sampling fraction | 1.0 | Fraction of samples drawn without replacement; takes effect only with bagging_freq > 0. subsample in sklearn. |
bagging_freq | Row sampling frequency | 0 | How often to resample, in rounds; 0 disables bagging. subsample_freq in sklearn. |
lambda_l1 / reg_alpha | L1 regularization | 0.0 | Produces sparse weights, Lasso-like. |
lambda_l2 / reg_lambda | L2 regularization | 0.0 | Penalizes large weights, against overfitting. Typical 0.1-10. |
cat_smooth | Categorical smoothing | 10 | Smoothing for categorical features, keeping rare categories from overfitting. |
max_bin | Maximum histogram bins | 255 | Larger improves accuracy at higher cost; smaller regularizes. |
min_gain_to_split | Minimum split gain | 0.0 | No split below this gain (similar in meaning to XGBoost’s gamma, but on a different numeric scale; see 7.3.2). |
data_sample_strategy | Sample-sampling strategy | bagging | bagging (random row sampling) or goss; added in 4.0. top_rate (default 0.2) and other_rate (default 0.1) are GOSS’s $a$ and $b$. |
boosting_type | Boosting type | gbdt | gbdt (standard gradient boosting), dart (Dropouts meet Multiple Additive Regression Trees), rf (random forest). The old goss option became data_sample_strategy='goss'. |
7.10 Pseudocode and implementation details
The overall LightGBM training flow
Pseudocode:
- Input: training set $D = \{(x_i, y_i)\}_{i=1}^n$, number of iterations $T$, parameter set $\Theta$
- Feature preprocessing:
- For each continuous feature: split into $k$ bins based on quantiles
- Map sample feature values to bin indices (storage chosen from
max_bin, e.g.uint8_t) - If EFB is enabled: greedily bundle exclusive features and compute offsets
- Initialize: $\hat{y}_i \leftarrow b_0$ for all $i$ (with
boost_from_average=true, $b_0$ for regression, binary classification and similar tasks is the constant matching the label mean; otherwise 0) - For $t = 1, 2, \dots, T$:
- Compute gradients and Hessians: $g_i \leftarrow \frac{\partial L(y_i, \hat{y}_i)}{\partial \hat{y}_i}$, $h_i \leftarrow \frac{\partial^2 L(y_i, \hat{y}_i)}{\partial \hat{y}_i^2}$ for all $i$
- If GOSS is enabled:
- Sort samples descending by $\lvert g_i \rvert$ (in the implementation $\lvert g_i h_i \rvert$)
- $\mathit{topSet} \leftarrow$ the first $a \times n$ large-gradient samples
- $\mathit{randSet} \leftarrow$ $b \times n$ samples drawn at random from the rest
- $\mathit{usedSet} \leftarrow \mathit{topSet} \cup \mathit{randSet}$
- Multiply $g_i$ and $h_i$ of the $\mathit{randSet}$ samples by $\frac{1-a}{b}$
- Build the tree on $\mathit{usedSet}$
- Otherwise (standard GBDT): build the tree on all samples (or the bagging sample)
- Build the $t$-th tree (leaf-wise):
- Build histograms at the root, find its best split and gain
- Repeat at most $L_{\max} - 1$ times, where $L_{\max}$ is
num_leaves:- Pick the leaf with the largest best-split gain among all current leaves
- If that gain $\le$
min_gain_to_split(or no leaf satisfiesmin_data_in_leaf,max_depthand other constraints), stop growing - Perform the split to get two new leaves
- Use histogram subtraction: walk the samples of the smaller child to build its histograms (accumulating $G$ and $H$ per feature, with features sampled by
feature_fraction), and subtract from the parent for the other child - Scan bin boundaries on the two new leaves’ histograms for their own best splits and gains
- For each leaf $j$: compute the output $w_j^* \leftarrow -\frac{G_j}{H_j + \lambda}$ ($\lambda$ is
lambda_l2; withlambda_l1, use the soft-thresholded $G_j$) - Update predictions: $\hat{y}_i \leftarrow \hat{y}_i + \eta \cdot f_t(x_i)$
- Check early stopping: stop if the validation metric hasn’t improved in $\mathit{patience}$ rounds
- Output: the final model $F(x) = b_0 + \eta \sum_{t=1}^T f_t(x)$ (LightGBM stores leaf values already scaled by the learning rate)
Where the pieces live in the source
The LightGBM source tree maps onto the techniques above (the repo was microsoft/LightGBM, now moved to lightgbm-org/LightGBM with the old address redirecting; paths below follow the main branch):
- C++ core: the main training logic is under
src/. - Histograms and split finding:
src/treelearner/feature_histogram.hpp(and.cpp) implements histogram statistics, split-gain computation and categorical splits. - Leaf-wise tree learner:
src/treelearner/serial_tree_learner.cppimplements single-machine leaf-wise growth. - Parallel tree learners:
feature_parallel_tree_learner.cpp,data_parallel_tree_learner.cppandvoting_parallel_tree_learner.cppundersrc/treelearner/. - GOSS:
src/boosting/goss.hppimplements gradient-based one-side sampling (plain bagging is inbagging.hppalongside). - EFB:
FastFeatureBundling/FindGroupsinsrc/io/dataset.cppperforms feature bundling when a Dataset is constructed. - Networking:
src/network/implements socket / MPI and collective communication.
7.11 A commented Python example (classification, regression, feature importance, early stopping)
| |
