How Native Tree-Based Models Handle Missing at Random (MAR) Data

An in-depth look at how XGBoost, LightGBM, and CatBoost naturally handle Missing at Random (MAR) data through advanced routing mechanisms like sparsity-aware splitting and surrogate splits. It outlines the mechanics behind native tree handling and flags key limitations when applying these techniques to statistical inference.

Author: Somesh Chatterjee
Tags: missing-data-imputation, data-science, tree-based-models

How Native Tree-Based Models Handle Missing at Random (MAR) Data

Tree-based machine learning models handle Missing at Random (MAR) data natively by learning optimal routing paths or assigning surrogate splits directly during training. Instead of requiring manual pre-imputation, these algorithms treat missingness as an informative feature capability, utilizing the relationships between observed fields and missing gaps to make decisions.

1. Sparsity-Aware Split Finding (XGBoost & LightGBM)

Modern gradient-boosted trees use an automated routing strategy called Sparsity-Aware Splitting to process missing values dynamically.

  • The Mechanism: When the algorithm evaluates a feature split (e.g., Age > 30), it maps two scenarios for rows where Age is missing: sending all missing values to the left child node, and sending them all to the right child node.
  • Why it works for MAR: The algorithm calculates the training gain for both directions and permanently assigns a default direction for missing values at that specific split based on whichever path yields the highest accuracy. Because MAR data is systematic and correlated with other observed variables, the tree naturally learns the most logical pathway for the missing data based on the surrounding context of the sample.

2. Missing Incorporated in Attributes / MIA (CatBoost)

CatBoost evaluates missingness explicitly as a separate structural category during its split calculation process.

  • The Mechanism: When building a split on a numerical feature, CatBoost evaluates three distinct routing options: values smaller than the threshold, values greater than the threshold, and missing values. It then clusters the missing values with whichever side optimizes the loss function.
  • Why it works for MAR: By explicitly processing the missing status alongside the values, it naturally maps out conditional patterns where the absence of a value depends heavily on the trajectory of prior features in the tree.

3. Surrogate Splits (Classical Random Forests / CART)

Traditional decision trees (like the original CART algorithm) use a fallback strategy called Surrogate Splits when a primary feature value is missing during prediction.

  • The Mechanism: If a node splits on Income but a sample’s Income value is missing, the tree looks for a "surrogate" feature that is highly correlated with Income within that specific subset of data (e.g., Education Level or Job Title). It then uses that surrogate feature to route the sample.
  • Why it works for MAR: This directly leverages the core definition of MAR. Since MAR assumes that the missingness is fully explained by other observed variables, surrogate splits naturally substitute the missing value with its most highly correlated, observed counterparts.

⚠️ A Critical Technical Caveat

While native tree routing is highly effective for predictive machine learning tasks, it does not "fix" the dataset or impute underlying values.

If your goal is statistical inference (e.g., calculating unbiased population coefficients or p-values), relying solely on native tree routing can still yield biased structural understandings. The algorithm optimizes purely for the final prediction rather than preserving the true joint probability distribution of the features. For inference tasks, Multiple Imputation (MICE) remains necessary.