8.1 Overview and core innovations
CatBoost (Categorical Boosting) is a gradient boosted decision tree implementation open-sourced by Yandex, the Russian search company, in 2017. Two papers are central: Prokhorenkova et al., CatBoost: unbiased boosting with categorical features (NeurIPS 2018, arXiv 2017), which introduces ordered boosting and ordered target statistics; and Dorogush, Ershov and Gulin, CatBoost: gradient boosting with categorical features support (arXiv 2018), which covers the library’s overall design, feature combinations and GPU implementation. The name states the positioning: unbiased, efficient gradient boosting for datasets with many categorical features. Compared with XGBoost and LightGBM, CatBoost’s distinctiveness lies in systematically solving, at the theoretical level, the prediction shift problem in gradient boosting, and in proposing ordered boosting and ordered target statistics, with oblivious trees as base learners.
CatBoost’s three core techniques:
- Ordered boosting: uses random permutations to avoid target leakage in gradient estimation, which addresses prediction shift at the root.
- Oblivious trees: every node at a level uses the same feature and split condition, producing symmetric, balanced trees that reduce overfitting and speed up prediction. Oblivious trees aren’t CatBoost’s invention (related work dates to the 1990s), but CatBoost makes them the default base learner and adds a purpose-built fast predictor.
- Ordered target statistics: an unbiased target-encoding scheme for categorical features that avoids the target leakage of conventional target encoding.
8.2 Three core problems: prediction shift, gradient bias, categorical features
The CatBoost papers argue that conventional gradient boosting (XGBoost and LightGBM included) suffers from a shift caused by target leakage, which shows up in two places: gradient estimation and target statistics for categorical features. Three points follow.
Problem one: prediction shift
Prediction shift means that for a training sample $x_k$, the conditional distribution of the current model’s output $F^{t-1}(x_k)$ given $x_k$ differs from the conditional distribution of $F^{t-1}(x)$ for a new test sample $x$. The reason: in standard gradient boosting, the $t$-th tree computes gradients from the $(t-1)$-round model’s predictions on all training samples, and that model was trained on those very samples, labels included. So each sample’s gradient implicitly carries information about its own label, which biases the gradient estimate and in turn shifts the final model. Theorem 1 of the paper proves this rigorously in a simplified setting: squared loss, two independent Bernoulli features $x^{(1)}, x^{(2)}$ with $p = \frac{1}{2}$, true function $y = f^*(x) = c_1 x^{(1)} + c_2 x^{(2)}$, two boosting steps, each with one decision stump (a tree of depth 1) and step size 1.
- If each step uses an independent sample of size $n$, then $\mathbb{E}\, F^2(x) = f^*(x) + O(2^{-n})$, essentially unbiased;
- if both steps use the same data, then $\mathbb{E}\, F^2(x) = f^*(x) - \frac{1}{n-1} c_2 \left(x^{(2)} - \frac{1}{2}\right) + O(2^{-n})$, a bias inversely proportional to $n$.
Intuition: during training the model “peeks” at the current sample’s label to compute its gradient update, much as tuning hyperparameters on a validation set overstates performance on that set.
Problem two: gradient estimation bias
The direct consequence of prediction shift is a biased gradient estimate. In standard gradient boosting, sample $i$’s gradient $g_i$ is computed from model $F_{t-1}$, and $F_{t-1}$ was trained using sample $i$’s information. That dependency means the gradient estimate is no longer unbiased for the true loss gradient.
CatBoost introduces random permutations via ordered boosting, ensuring each sample’s gradient comes only from a model that has never seen that sample, which removes the target leakage.
Problem three: target leakage in categorical features
Conventional target encoding for categoricals (replacing a category with the mean label of that category) leaks the target badly:
- For training sample $i$, computing the category statistic from its own label leaks that label into the feature.
- The model then looks excellent on the training set and overfits badly on test. The paper gives an extreme example: if every value of a categorical feature occurs exactly once and $P(y=1 \mid \text{category}) = 0.5$, then a target statistic computed over all the data depends only on each sample’s own label, and a single threshold separates the training set perfectly; on test data the encoding is the same for every sample (equal to the prior), so accuracy is just 0.5.
- The usual workarounds each have flaws: holdout TS (compute statistics on one part, train on the other) wastes data; leave-one-out TS looks like it excludes the sample but still leaks. For a categorical feature where all samples share the same value, for instance, the leave-one-out encoding’s magnitude depends only on the sample’s own label (positive samples encode slightly lower than negative ones), so one threshold separates the training set perfectly.
CatBoost’s ordered target statistics solve this by computing the statistic in an ordered fashion, using only the data preceding the sample.
8.3 Ordered boosting
8.3.1 The idea: random permutations to avoid target leakage
The idea comes from a key observation: in standard gradient boosting, when computing gradients for the $t$-th tree, the current model $F_{t-1}$ has already been updated $t-1$ times using all training samples, including the one at hand. Each sample’s gradient therefore implicitly carries its own information — target leakage.
CatBoost’s answer: impose a random permutation on the training data. For each sample, build a model using only the samples that precede it in the permutation, and compute that sample’s gradient from that model.
More precisely (the ideal version of Algorithm 1 in the paper): draw a random permutation $\sigma$ and maintain $n$ supporting models $M_1, \dots, M_n$, where $M_i$ is trained on only the first $i$ samples of the permutation. At each boosting step, the residual (negative gradient) of the sample in position $j$ is computed with $M_{j-1}$, so the residual doesn’t depend on that sample’s own label. This ideal version needs $n$ models, multiplying both compute and memory by $n$, which is impractical; Section 8.3.3 describes CatBoost’s approximation.
flowchart TD
A["Draw a random permutation sigma"] --> B["For each sample i in sigma order"]
B --> C["Build a model from only the data before it"]
C --> D["Predict the current sample with the prefix model"]
D --> E["Compute gradient g_i for sample i"]
E --> F{"Samples left?"}
F -->|Yes| B
F -->|No| G["Fit the t-th tree on all samples"]
G --> H{"Stopping condition met?"}
H -->|No| A
H -->|Yes| I["Output the final model"]
8.3.2 Compared with conventional gradient boosting
| Dimension | Conventional GBDT/XGBoost/LightGBM | Ordered boosting (CatBoost) |
|---|---|---|
| Gradient computation | Gradients from a model trained on all samples | Each sample’s gradient from a model trained only on the samples preceding it |
| Target leakage | Present (each gradient carries its own sample’s information) | Removed (a sample’s gradient doesn’t depend on its own label) |
| Prediction shift | Present | Removed |
| Training efficiency | One tree per round | Still one tree structure per round, but multiple sets of supporting-model leaf values must be maintained, so it’s slower (in the paper’s experiments, Ordered is about 1.7 times slower than Plain) |
| Approximation | None | Multiple random permutations, and supporting models kept only for prefixes of length $2^j$ |
| Theoretical analysis | The paper proves a prediction shift inversely proportional to sample size (Theorem 1) | Residuals come from models that haven’t seen the sample, which avoids the shift by construction |
8.3.3 The approximation: multiple permutations
Following the definition exactly would need a different model per sample per round, which is computationally hopeless. Using oblivious trees as base learners, CatBoost implements it as follows (Section 5 of the paper):
- Draw $s+1$ random permutations $\sigma_0, \sigma_1, \dots, \sigma_s$. $\sigma_1, \dots, \sigma_s$ are used to evaluate splits and fix the tree structure; $\sigma_0$ is used to compute the final model’s leaf values. Multiple permutations are needed because within one permutation the early samples have very short “histories,” so their target statistics and residuals have high variance; several permutations lower the variance of the final model.
- Pick one permutation per round at random: at round $t$, draw $\sigma_r$ from $\{\sigma_1, \dots, \sigma_s\}$, and compute both the categorical features’ ordered target statistics (Section 8.5) and the gradients under that permutation.
- Share the tree structure: maintain supporting models $M_{r,j}$, where $M_{r,j}(i)$ is the current prediction for sample $i$ from a model using only the first $j$ samples of $\sigma_r$. When building a tree, sample $i$ uses the gradient $\mathrm{grad}_{r,\sigma_r(i)-1}(i)$, based only on samples preceding it. When evaluating a candidate split, sample $i$’s leaf value is the average gradient of the samples preceding it within the same leaf, and a cosine similarity measures how well those leaf values match the gradients (the
score_functionparameter, defaultCosine). Once the structure is fixed, the same structure is added to every supporting model, each with its own leaf values. - Leaf values for the final model: after all trees are built, the final model $F$ gets its leaf values the standard way, with samples assigned to leaves according to target statistics computed under $\sigma_0$. For test samples, target statistics use the full training data.
- Reducing complexity: instead of storing all $O(s n^2)$ values $M_{r,j}(i)$, only $M'_{r,j}(i) := M_{r,2^j}(i)$ are stored and updated ($j = 1, \dots, \lceil \log_2 n \rceil$, and only for samples with $\sigma_r(i) \le 2^{j+1}$), bringing the maintained predictions down to $O(s n)$. Table 1 of the paper gives the per-round complexity: computing gradients and updating supporting models are both $O(s \cdot n)$, and tree building is $O(\lvert C \rvert \cdot n)$ ($C$ the set of candidate splits), so the asymptotic complexity matches standard GBDT with ordered target statistics.
8.3.4 Ordered versus Plain
CatBoost has two boosting modes, selected by boosting_type:
- Plain: the standard gradient boosting loop; with categorical features, ordered target statistics are still computed under $\sigma_1, \dots, \sigma_s$.
- Ordered: the ordered boosting described above.
The paper’s experiments show Ordered’s advantage is clearest on small datasets: the fewer the samples, the larger Plain’s relative error, consistent with Theorem 1’s “bias inversely proportional to $n$.”
The default isn’t always Ordered Per the current docs,
boosting_typedefaults toPlainon CPU; on GPU it defaults toOrderedwhen there are at most 50,000 samples and the task isn’t multiclass, and toPlainotherwise. Setboosting_type='Ordered'explicitly when you want ordered boosting. Either way, categorical features are handled with ordered target statistics.
8.4 Oblivious trees
8.4.1 Structure: same feature and split condition per level
Oblivious trees (also called symmetric trees) are CatBoost’s base tree structure. Unlike conventional decision trees (CART, the trees in XGBoost and LightGBM), oblivious trees are strictly symmetric:
- All nodes at a level use the same splitting feature.
- All nodes at a level use the same split condition (the same threshold).
- Each leaf corresponds to a binary path from root to leaf (a sequence of left/right choices), so the tree is always a perfectly balanced full binary tree. An oblivious tree of depth $d$ is equivalent to a decision table with $2^d$ cells: the combination of $d$ binary conditions determines the leaf.
graph TD
subgraph ObliviousTree["Oblivious tree: same feature and condition per level"]
A["Root
feature_A > 0.5"] --> B["Level 1
feature_B > 1.2"]
A --> C["Level 1
feature_B > 1.2"]
B --> D["Level 2
feature_C > 3.0"]
B --> E["Level 2
feature_C > 3.0"]
C --> F["Level 2
feature_C > 3.0"]
C --> G["Level 2
feature_C > 3.0"]
end
subgraph TraditionalTree["Conventional tree: different splits per node"]
H["Root
feature_A > 0.5"] --> I["feature_B > 0.3"]
H --> J["feature_D > 2.1"]
I --> K["feature_C > 1.0"]
I --> L["feature_E > 0.8"]
J --> M["feature_F > 5.0"]
J --> N["leaf"]
end
8.4.2 Benefits: less overfitting, faster prediction
Less overfitting:
- Conventional trees choose a splitting feature independently at each node, which readily overfits local noise in the training data.
- The forced symmetry of oblivious trees limits model flexibility, acting as strong regularization and reducing overfitting risk (the paper: “Such trees are balanced, less prone to overfitting”). The price is weaker expressiveness per tree, so more trees are usually needed.
- Symmetry means each feature’s effect applies uniformly at a given level, which avoids over-optimizing for particular data subsets.
Faster prediction:
- In a conventional tree, prediction starts at the root and evaluates each node’s split condition in turn, so the path length equals the tree depth.
- In an oblivious tree, each level’s condition doesn’t depend on the path taken, so $d$ conditions can be evaluated independently and simultaneously, with no level-by-level branching.
- More importantly, an oblivious tree has exactly $2^{d}$ leaves, each identified by a unique binary code. The predictor described by Dorogush et al. (2018) first binarizes the features and statistics it uses, then computes the $t$-th tree’s leaf index as
where $B(x, f) \in \{0, 1\}$ is sample $x$’s value on binary feature $f$, and $f(t, i)$ is the binary feature used at level $i$ of tree $t$. Leaf values are stored in an array of length $2^d$ and read by index directly, which speeds up prediction considerably.
- That paper measured, on the Epsilon dataset with comparable tree counts (capped at 8000 trees): single-threaded, CatBoost predicted in 2.4 s, XGBoost in 78 s (about 32.5 times) and LightGBM in 122 s (about 50.8 times); with 32 threads the factors were about 19.5 and 74, summarized as “about 25 times faster than XGBoost and 60 times faster than LightGBM.” The gap comes from both the oblivious structure and the purpose-built predictor, and the authors note it’s only a rough comparison.
Simpler split search:
- Because all nodes at a level share a split, each level only needs one split that is best in aggregate for all its nodes (candidate scores are summed over the level’s leaves) rather than one per node.
- That speeds up tree building further.
- Beyond the default
grow_policy='SymmetricTree', CatBoost also supportsDepthwise(grow level by level, but each node may choose its own split) andLossguide(grow the leaf with the largest loss reduction, withmax_leaves, default 31). Per the docs,depthdefaults to 6, and to 16 withLossguide.
8.5 Categorical features (ordered target statistics)
8.5.1 The formula
Handling categorical features is one of CatBoost’s core strengths. Conventional approaches (one-hot encoding, say) produce high-dimensional sparse features for high-cardinality categoricals; target encoding (replacing a category with the mean label of that category) keeps dimensionality low but leaks the target badly.
CatBoost’s ordered target statistics compute a target statistic for each category value using only the samples preceding the current one in the permutation.
For categorical feature $k$ and category value $x_{ik}$, let $\mathcal{D}_i = \{ j : \sigma(j) < \sigma(i) \}$ be the set of samples preceding sample $i$ in the random permutation $\sigma$. The ordered target statistic for sample $i$ is
$$ \hat{x}_{ik} = \frac{\sum_{j \in \mathcal{D}_i} \mathbb{1}_{[x_{jk} = x_{ik}]} \cdot y_j + a \cdot P}{\sum_{j \in \mathcal{D}_i} \mathbb{1}_{[x_{jk} = x_{ik}]} + a} $$If the samples are re-sorted by $\sigma$ beforehand, the summation runs over $j = 1, \dots, i-1$ (the form used in Dorogush et al.).
Notation:
| Symbol | Meaning |
|---|---|
| $x_{ik}$ | The original category value of sample $i$ on categorical feature $k$ |
| $\hat{x}_{ik}$ | The numeric feature for sample $i$ after ordered-target-statistic encoding |
| $y_j$ | Target label of sample $j$ |
| $\mathbb{1}_{[x_{jk} = x_{ik}]}$ | Indicator, 1 when sample $j$’s category value equals sample $i$’s, otherwise 0 |
| $a$ | Prior weight ($a > 0$), controlling prior strength |
| $P$ | Prior value: typically the global label mean for regression, or the prior probability of the positive class for binary classification |
| $\sigma$ | The random permutation of training samples, an artificial “time order” |
8.5.2 How it avoids target leakage
Why do ordered target statistics avoid target leakage?
The key is that both numerator and denominator sum over $\mathcal{D}_i$ — only samples preceding the current one — borrowing the online-learning idea that you can only see history. That means:
- Sample $i$’s label $y_i$ is not used in computing sample $i$’s own category encoding.
- The encoding therefore carries no information about sample $i$’s target, which removes the leakage.
- At prediction time, new samples use statistics over the full training data (since they aren’t in the training permutation).
- The paper summarizes a good target statistic with two properties: P1, training and test samples’ encodings have the same distribution given the label (no conditional shift); P2, all training data can be used both to compute statistics and to train the model. Greedy TS violates P1, holdout TS violates P2, and ordered TS satisfies both.
What prior smoothing does:
- When a category value appears for the first time in the permutation (denominator 0), the encoding falls back to the global prior $P$.
- The parameter $a$ controls prior strength: the larger $a$, the closer the encoding to the global prior, and the stronger the regularization.
- This matters most for rare categories (those appearing few times in training), preventing overfitting to them.
Multiple permutations:
- With a single permutation, early samples have very short “histories,” so their encodings have far higher variance than later samples’. CatBoost therefore uses different permutations across boosting rounds: each round draws one at random from $\sigma_1, \dots, \sigma_s$ and computes that round’s target statistics under it (see Section 8.3.3).
- Note this isn’t averaging encodings over permutations: Dorogush et al. point out that directly averaging statistics from several permutations causes overfitting, and CatBoost avoids it through the leaf-value computation of Section 8.3.3.
- Ordered TS and ordered boosting must use the same permutation ($\sigma_{\text{cat}} = \sigma_{\text{boost}}$), which ensures sample $i$’s label enters neither its own encoding nor the model that computes its gradient.
8.5.3 Feature combinations
Encoding categorical features one at a time loses interactions between them. In music recommendation, for instance, encoding “user ID” and “genre” separately can’t express “this user likes rock,” whereas their combination as a new categorical feature expresses it directly. The number of combinations grows exponentially in the number of categorical features, so they can’t all be enumerated; CatBoost uses a greedy strategy (Dorogush et al., 2018; Prokhorenkova et al., 2018):
- The first split of a tree doesn’t consider combinations.
- At each later split, every categorical feature already used in the tree (and every combination already formed) is joined with each categorical feature in the dataset, producing new candidate combinations.
- Numeric splits already used in the tree (of the form “numeric feature > threshold”) also count as two-valued categorical features and can take part in combinations.
- Combination features are converted to target statistics on the fly during training.
The maximum number of features in a combination is set by max_ctr_complexity (default 4; on GPU for multiclass tasks, categorical features default to 1).
8.5.4 Other details: CTR types, multiple priors, one-hot
- Count statistics: besides target statistics, CatBoost can use how often a category occurs in the dataset as a numeric feature (CTR type
Counter), which also applies to feature combinations. - Multiple priors: to find a suitable prior at each step, CatBoost tries several priors at once and builds one feature per prior.
- CTR types: on CPU,
Borders,Buckets,BinarizedTargetMeanValueandCounterare available, configured viasimple_ctrandcombinations_ctr(see the Categorical features parameter page in the docs). - One-hot for low-cardinality categories: features with at most
one_hot_max_sizecategories are one-hot encoded and no CTR is computed. Per the docs, the default is generally 2 (only two-valued categoricals are one-hot encoded), 10 in Ranking mode, and 255 in some GPU cases. - Temporally ordered data: with
has_time=True, CatBoost stops shuffling and uses the input order as “time” for ordered statistics and ordered boosting, which suits data with a natural temporal order.
8.6 The Python API and key parameters
CatBoost’s Python API is feature-rich and supports categorical features natively (strings or integers, but not floats; missing values in categorical columns must first be filled with a valid value such as a string).
Native API (CatBoostClassifier / CatBoostRegressor)
| |
Key parameters
| Parameter | Meaning | Default | Tuning advice |
|---|---|---|---|
iterations | Number of iterations (trees) | 1000 | Tune with learning_rate; usually 500-2000. |
depth | Tree depth (oblivious tree levels) | 6 (16 with Lossguide) | Controls model complexity. Deeper captures more complex patterns but overfits more easily. Typical 4-10. |
learning_rate | Learning rate | chosen automatically / 0.03 | For Logloss, MultiClass and RMSE, if leaf_estimation_iterations, leaf_estimation_method and l2_leaf_reg aren’t set, the rate is chosen from the data and iteration count (and printed); otherwise the default is 0.03. Typical 0.01-0.3. |
boosting_type | Boosting mode | CPU: Plain | Ordered or Plain. On GPU, defaults to Ordered when there are at most 50,000 samples and the task isn’t multiclass. Try Ordered on small datasets. |
l2_leaf_reg | L2 regularization on leaves | 3.0 | Penalizes large leaf weights, against overfitting. Typical 1-10. |
random_strength | Randomness in split scores | 1.0 | Adds mean-zero Gaussian noise to each candidate split’s score, with variance shrinking over training; this parameter multiplies that variance. Larger means more regularization. |
bootstrap_type | Sample sampling scheme | CPU (non-multiclass): MVS (subsample=0.8); otherwise mostly Bayesian | Choices: Bayesian, Bernoulli, MVS, Poisson (GPU only), No. |
bagging_temperature | Bayesian bootstrap temperature | 1 | Only with bootstrap_type='Bayesian'. Assigns random weights to samples: 0 means all weights are 1 (no sampling), 1 means weights follow an exponential distribution, and larger values sample more aggressively. |
border_count | Split points for numeric features | CPU: 254; GPU: 128 | Number of quantization borders for numeric features (alias max_bin). More improves accuracy at higher cost. |
one_hot_max_size | One-hot threshold | generally 2 | Categorical features with at most this many categories are one-hot encoded rather than getting target statistics. |
max_ctr_complexity | Maximum features per combination | 4 | Controls the order of categorical combinations (8.5.3). |
grow_policy | Growth policy | SymmetricTree | SymmetricTree (oblivious), Depthwise (level-wise), Lossguide (leaf-wise). |
cat_features | Categorical feature indices | None | Column indices of categorical features; CatBoost handles them. |
8.7 A commented Python example
| |
Part III summary: this part laid out the mathematics, core algorithms and engineering optimizations of three modern gradient boosting implementations. XGBoost established the theoretical basis of modern tree boosting with second-order Taylor expansion and explicit regularization; LightGBM made training efficient at scale through histograms, leaf-wise growth, GOSS and EFB; CatBoost systematically addressed prediction shift and categorical feature handling with ordered boosting and ordered target statistics, and balanced regularization against prediction speed with oblivious trees. Each has its emphasis, and the right choice in practice depends on data size, feature types and performance requirements.
