Skip to content
Tutorials Center
My learning

Topics

Lesson 10 of 40 ยท Gradient Boosting Basics

Histogram Splits and Tree Growth Strategies

Understand why modern boosters bin features into histograms, how level-wise (XGBoost) and leaf-wise (LightGBM) growth differ, and what max_bin, max_depth and num_leaves control.

Finding the best split exactly means sorting every feature at every node, which is slow on large tables. Today's fast boosters avoid this with two ideas: put feature values into a small number of bins (a histogram) and search the bin edges only, and choose a growth strategy that decides which node gets split next. Those ideas explain most of the speed of XGBoost's hist method and of LightGBM, and they explain why max_depth and num_leaves behave differently.

Histogram-based splitting

Before training, each numeric feature is divided into at most max_bin bins (255 by default in LightGBM and 256 in XGBoost's hist). The bin boundaries come from quantiles of the training data, so each bin holds roughly the same number of rows. Every row then stores a small integer (its bin) instead of a float.

To score splits at a node, the algorithm sums gradients and Hessians per bin, producing a histogram of at most max_bin entries, and then scans the bin edges. The cost depends on the number of bins, not on the number of distinct values, and it fits in cache. A useful trick follows: when a parent histogram is known and one child's histogram is computed, the sibling's histogram is just parent minus child, which halves the work.

Python Quantile bins and the cost of fewer bins

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Quantile bins split a skewed feature into groups of similar row counts, so crowded regions get fine resolution and sparse tails get coarse ones. With 256 bins a 10,000-value column is searched at 255 candidate cuts instead of 9,999.

How max_bin changes a model

Fewer bins mean coarser thresholds, which is faster and a form of regularization; too few can miss important cuts. The default is nearly always fine, and lowering it (for example to 63) is a speed trick on huge data. Because binning uses only training data, new values beyond the extremes fall into the first or last bin.

Python max_bin in practice

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Expect the RMSE to improve as bins grow and flatten out, while timing drifts up. Treat the seconds as noisy in a browser; the trend in error is what carries over.

Level-wise versus leaf-wise growth

Both libraries grow one tree by repeatedly splitting a node, but the order differs.

  • Level-wise (depth-wise): split every node on the current level, then go one level deeper. The shape is balanced and max_depth bounds it. This is XGBoost's default (grow_policy="depthwise").
  • Leaf-wise (best-first): always split the single leaf, anywhere in the tree, that yields the largest gain. The shape is lopsided, deep where the data are hard. This is LightGBM's strategy, bounded by num_leaves.
flowchart TB
  subgraph LW["Level-wise: finish a level first"]
    A1[root] --> B1[L] & C1[R]
    B1 --> D1[LL] & E1[LR]
    C1 --> F1[RL] & G1[RR]
  end
  subgraph BF["Leaf-wise: split the best leaf"]
    A2[root] --> B2[L] & C2[leaf]
    B2 --> D2[leaf] & E2[LR]
    E2 --> F2[leaf] & G2[leaf]
  end

With the same number of leaves, the leaf-wise tree can reach a lower loss, but it can also grow a very deep narrow branch that overfits.

For the same leaf count, best-first growth picks the highest-gain splits, so it usually reaches lower training loss faster. That is the reason LightGBM is quick and strong, and the reason it can overfit small data when num_leaves is high. XGBoost can imitate it: grow_policy="lossguide" with max_leaves set.

Python Same leaf budget, two growth policies

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Compare the rows: with equal leaves the best-first tree usually fits training data at least as well, and giving it many more leaves widens the train/test gap on a small dataset. This is the practical lesson: when you use leaf-wise growth, control num_leaves first and treat max_depth as a safety cap.

Matching parameters across libraries

A depth-d balanced tree has up to 2^d leaves, so max_depth=6 corresponds to roughly num_leaves=64. Because leaf-wise trees are not balanced, a safe LightGBM setting is below that, for example num_leaves of 31 with max_depth=-1 (unlimited), or max_depth=8 as a cap. You will tune both in Tree Complexity Parameters.

Check your understanding

Quick check ยท 4 questions

of 4 answered You scored / 4 ยท perfect!

  1. 1. What does a histogram-based booster store for each numeric value?

    Features are binned once, so splits are searched over bin edges instead of every distinct value.
  2. 2. Which growth policy splits the leaf with the largest gain anywhere in the tree?

    Leaf-wise growth is best-first, which is LightGBM's approach and XGBoost's lossguide policy.
  3. 3. Why does the sibling-subtraction trick save time?

    Because parent = left + right, only the smaller child must be computed from data.
  4. 4. You switch to leaf-wise growth on a 1,000-row dataset and test error rises. What is a likely cause?

    Best-first growth can create deep, narrow branches; reduce num_leaves or add minimum leaf sizes.

Summary

  • Histogram boosting bins each feature (default about 255 bins) and scans bin edges, which is fast and cache friendly.
  • max_bin trades resolution for speed; the default is usually right.
  • XGBoost grows level-wise by default; LightGBM grows leaf-wise and controls size with num_leaves.
  • Leaf-wise trees fit faster but overfit small data more easily.
  • XGBoost can grow leaf-wise with grow_policy="lossguide".

Next: XGBoost Scikit-learn API