Decision trees are among the few models that people in credit, criminal justice, and social science routinely audit by hand. Their data is also often missing in telling ways: high earners skip the income question, and defendants with certain histories have blank records. Statisticians call this "missing not at random" (MNAR), meaning the chance that a value is missing depends on the value itself. Over the past few years, solvers that find the provably best small tree have become fast. Shortcut methods have become faster still, because they search exhaustively near the root and split greedily, one locally best split at a time, near the leaves. All of this was developed and validated on complete data. This proposal asks whether informative missingness creates a trap these fast learners fall into. The specific worry is a missing-value indicator that looks useless as a first split but becomes highly predictive once combined with another feature.
The approach is to manufacture the trap and measure it exactly. We inject missingness patterns with a known, adjustable degree of "deceptiveness" into standard tabular benchmarks. We then add missingness indicators to the feature set so an exact solver can certify the globally best tree. That certified optimum lets us report, for greedy trees, fast near-optimal trees, and gradient-trained soft trees, exactly how far each lands from the optimum and why. If the trap is real, we also test a small fix: spend exhaustive search wherever a missingness indicator is a candidate split.
Core Claim
The central hypothesis concerns where the predictive signal sits. Under MNAR missingness, the signal can live in the interaction between a missingness indicator and an observed feature rather than in either one alone. When it does, the problem looks like a parity function to a greedy learner: neither feature shows any gain as a first split, so greedy search never chooses them.
Two different regimes follow. Under simple self-masking, the indicator is equivalent to a threshold split. For example, if income is missing whenever it exceeds some value $t$, then "income missing" is the same as "income $> t$". Greedy routing of missing values should then lose nothing. Under conditional self-masking, the indicator matters only inside a subgroup, such as high earners hiding income only in some occupations. Greedy trees and the "greedy at the leaves" shortcut should then be stuck far from the optimum. The size of this entrapment should grow with a deceptiveness parameter we control.
This prediction speaks directly to a disagreement in the literature. Lookahead and Pathology in Decision Tree Induction found that one-level lookahead usually hurt on clean data: it lowered accuracy in 6 of 8 cases and evaluated over 419,000 splits versus about 1,700 for greedy search. Near-Optimal Decision Trees in a SPLIT Second found that exhaustive search near the root is essential, while greedy splitting suffices near the leaves. Our claim is that missingness determines which finding applies. Under deceptive MNAR, lookahead stops being harmful, and greedy splitting at the leaves stops being safe.
Positioning Against Prior Work
Two lines of work motivate the question. On the solver side, exact methods have become practical. These are dynamic programming and branch-and-bound searches over binarized features, which repeatedly split the search space into subproblems and discard any branch whose bound shows it cannot beat the best tree found so far. Examples include Branches, which reaches the optimum on monk1 in 0.05s versus about 3s for GOSDT, and Quant-BnB, which handles continuous features. Near-optimal shortcuts such as SPLIT and reference-ensemble guessing, which reports 10–100x speedups on COMPAS and FICO, trade certification for speed. Optimal or Greedy Decision Trees? showed across 180 datasets that optimal trees beat greedy trees by 1.0% to 1.3% at depth 3–4 when optimizing non-concave objectives such as accuracy. None of these works studies missing data. That is the validation gap we target: their accuracy and speed claims are untested in the regime where practitioners most need single auditable trees.
On the missingness side, Fairness without Imputation is the closest work. It proves that imputing first and training afterward can produce discriminatory models. It handles missing values inside a mixed-integer program by letting the optimizer route them to either branch, a scheme called Missing Incorporated as Attribute (MIA). However, it gives up on single exact trees in favor of time-limited ensembles. It also never asks whether a learner's search itself is trapped by the structure of missingness. Boosting Prediction with Data Missing Not at Random corrects MNAR bias in the label with propensity weighting, but inside greedy boosting. The unidentifiability results surveyed in Jarrett et al. constrain our design. Because MNAR mechanisms cannot be identified from observed data alone, we can only measure entrapment against ground truth when we generate the missingness ourselves. Semi-synthetic injection is therefore a requirement of the design, not a convenience.
The optimization literature supplies our lens and one baseline. The Gaussian continuation analysis shows that progressively smoothing a non-convex objective can steer search out of shallow traps. A soft tree, whose splits are smooth sigmoid routings, trained with an annealed sigmoid temperature is the natural tree analogue. Recursive decomposition (RDIS) shows that gradient descent with random restarts degrades badly as dimension grows. The decision tree setting is unusual in one respect: we can compute the exact global optimum. Entrapment can therefore be measured as a certified gap rather than estimated from the best of many restarts.
Research Program
The first component is a mask-augmented exact reference. MIA routing on a feature $x_j$ at threshold $t$ sends missing values either left or right. Both choices can be written as ordinary binary features: "$x_j \le t$ or missing" and "$x_j \le t$ and observed". We add both, plus the raw indicator "$x_j$ missing", to the binarized feature set. An unmodified exact solver (Branches and STreeD) then returns the certified optimal MIA tree under a misclassification-plus-leaf-penalty objective. This step is deliberately simple. It roughly doubles the binary features for incomplete columns, a cost we measure. It requires no new bounds, because each sample still has a fixed binary value for every encoded feature, so the solvers' caching and pruning stay valid.
The second component is a deceptiveness dial for missingness. We start from fully observed versions of COMPAS, Adult, HELOC, and Covertype and choose a feature $x_j$ to mask with probability
$$P(M_j = 1 \mid x) = \sigma\big(a\,(x_j - t)\,[\rho\, g(x_k) + (1-\rho)]\big).$$
Here $M_j$ is the missingness indicator, $\sigma$ is the logistic function, $a$ controls how sharp the masking is, $t$ is a threshold, and $g(x_k) \in \{-1, +1\}$ is a subgroup indicator on a second observed feature $x_k$. The parameter $\rho \in [0,1]$ sets deceptiveness. At $\rho = 0$ we have plain self-masking: the indicator stands in for "$x_j > t$" everywhere. At $\rho = 1$ the direction of masking flips across subgroups. This makes the indicator's marginal association with $x_j$, and hence with the label, close to zero, while its association within each subgroup stays strong.
We also report, as a diagnostic, the impurity gain the indicator would produce as a first split compared with its gain inside the $x_k$ subgroups. If the hypothesis is right, the ratio of these two gains should predict entrapment before any tree is trained.
The third component is the entrapment measurement. For each learner $A$ we compute the certified gap
$$\Delta_A = \frac{R(T_A) - R(T^\star)}{R(T^\star)},$$
where $R$ is the regularized training objective, $T_A$ is the tree returned by learner $A$, and $T^\star$ is the certified optimum on the same mask-augmented features. We pair $\Delta_A$ with out-of-sample accuracy on held-out rows scored against their true labels. Because we know which root split the optimum chose, we can also record whether each learner's error began at the root, the case Murthy and Salzberg studied, or at the leaves, the case SPLIT assumes is safe.
The fourth component is a fix, to be pursued only if entrapment appears. Mask-aware SPLIT keeps SPLIT's exhaustive search near the root and greedy splitting below it. However, when a subtree's candidate splits include a missingness indicator whose within-subgroup gain greatly exceeds its marginal gain, that subtree is reverted to exact search. This is a targeted reallocation of search effort, not a new solver.
A secondary arm uses KLIPS, the Korean Labor and Income Panel Survey, where about 30.6% of 2008 income responses are genuinely missing. There the missing values are in the label, so we weight the 0-1 loss by inverse propensity weights estimated from 2007 income, which serves as a shadow variable: it relates to 2008 income but is assumed not to affect whether the 2008 value is missing, following Zhao et al.. A weighted misclassification count still adds up leaf by leaf, so exact solvers accept it unchanged. This arm checks that the pipeline runs on real MNAR data. It makes no claim about ground truth, which unidentifiability rules out.
Baselines
The do-nothing reference is CART with complete-case deletion. It represents what many audited pipelines still do and anchors how much any missingness handling recovers.
The strongest fast competitor, and the one the hypothesis targets, is SPLIT and LicketySPLIT run on the same mask-augmented binary features. Its authors report test loss within 1% of optimal on HELOC and 100x–600x speedups over GOSDT on complete data, and these are the numbers it must keep under missingness. We will use the depth-split setting the authors derived as their recommended default and grant the same per-dataset time and tuning budget as every other method.
Greedy CART with MIA routing, plus XGBoost's built-in missing-value handling as an accuracy ceiling for non-auditable models, represents standard practice. On complete data, Optimal or Greedy Decision Trees? reports that greedy trees trail optimal trees by 1.0%–1.3% at depth 3–4. We treat that figure as the complete-data gap against which the MNAR gap is compared.
Impute-then-optimize means MICE, k-nearest-neighbor, or GNR imputation (Chen et al.) followed by Branches. It tests whether a good imputer removes the need for indicators.
The soft tree baseline is a gradient-trained soft tree given 20 random restarts and an annealed sigmoid temperature in the spirit of Gaussian continuation. Its wall-clock budget is matched to the exact solver's.
We will also compare against Fair MIP Forest's MIA formulation where code permits. The file reports no numerical accuracy for it in MNAR-tree settings. More generally, no reported result was found on Lacuna for any tree learner on injected MNAR feature missingness, so every number in that regime will be new.
The ablation isolating the key ingredient is mask-aware SPLIT versus vanilla SPLIT at equal runtime. Mask-aware SPLIT counts as beating vanilla SPLIT if it cuts the median certified gap $\Delta$ by at least half at $\rho \ge 0.5$ while staying within 2x of SPLIT's runtime. The exact mask-augmented solver counts as beating greedy MIA if its out-of-sample advantage at high $\rho$ is clearly larger than the 1.0%–1.3% complete-data gap.
Why not just…?
Why not just impute and then run an exact solver? Imputation methods that assume values are missing at random fill in plausible values and discard the fact that a value was missing. Under self-masking, that fact is often the signal. Fairness without Imputation found that impute-then-train pipelines swing unpredictably with the choice of imputer and are dominated on COMPAS, Adult, and HSLS. We include three imputers anyway. If GNR-imputed Branches matches the mask-augmented optimum at high $\rho$, the indicator story is wrong, and we will report that.
Why not just add indicator columns and run an existing exact solver? This is the most serious threat. It is literally our reference method, and for depth-3 trees on mid-sized data it may be all a practitioner needs. Our contribution does not depend on beating it. We use it to certify gaps, and the open question is whether the fast methods that make large data feasible survive missingness. Covertype is where this matters: there, exact solvers time out on complete data according to the SPLIT paper, and indicators make the feature set larger still. If exact solving with indicators scales fine on Covertype with missingness injected, the fix component becomes unnecessary and the work reduces to a validation study. That would still be useful, but smaller.
Why not just use greedy CART or XGBoost with built-in missing-value routing? At $\rho = 0$ we expect this to work, and the experiment is designed to show that. Greedy routing picks the side with the best immediate impurity gain, which is exactly the criterion that cannot see interaction-only signal. If greedy-MIA's gap stays flat as $\rho$ rises, the core claim is falsified.
Why not just train soft trees with restarts? RDIS's results suggest that random restarts scale poorly with dimension. Here we can measure this directly, since we know the certified optimum. A soft tree that finds the interaction would also need rounding to a hard tree for auditing, and we score the rounded tree.
Proposed Experiments and Decisive Checks
We run all four datasets at depths 3–5, sweeping $\rho \in \{0, 0.25, 0.5, 0.75, 1\}$ and missingness rates of 10%, 30%, and 50%, with five seeds and an 80/20 split. Hyperparameters are tuned by the same cross-validation budget for every method. Metrics are the certified gap $\Delta$, true-label test accuracy, leaf count, wall-clock time, and the rate at which each learner's root split matches the optimum's.
Three outcomes decide the question. First, does SPLIT's gap stay near zero at $\rho = 0$ and grow with $\rho$, with errors concentrated below the exhaustive-search depth? This tests whether greedy splitting at the leaves breaks under deceptive missingness. Second, at high $\rho$, does one-level lookahead improve on greedy splitting, reversing the 1995 finding? Third, does the root-versus-subgroup gain ratio predict $\Delta$ across datasets? If it does, practitioners get a cheap check, run before training, of whether a fast tree learner can be trusted on their missing data. A flat gap across $\rho$ would be an equally clear result: fast tree learners can then be used on informative missingness without change, as long as indicators are encoded.
References
- Lookahead and Pathology in Decision Tree Induction
- Near-Optimal Decision Trees in a SPLIT Second
- Branches: A Fast Dynamic Programming and Branch & Bound Algorithm for Optimal Decision Trees
- Quant-BnB: A Scalable Branch-and-Bound Method for Optimal Decision Trees with Continuous Features
- Fast Sparse Decision Tree Optimization via Reference Ensembles
- Optimal or Greedy Decision Trees? Revisiting their Objectives, Tuning, and Performance
- Fairness without Imputation: A Decision Tree Approach for Fair Prediction with Missing Values
- Boosting Prediction with Data Missing Not at Random
- HyperImpute: Generalized Iterative Imputation with Automatic Model Selection
- A Theoretical Analysis of Optimization by Gaussian Continuation
- Recursive Decomposition for Nonconvex Optimization - IJCAI-15 Distinguished Paper
- A Nuisance-Free Inference Procedure Accounting for the Unknown Missingness with Application to Electronic Health Records
- Deep Generative Imputation Model for Missing Not At Random Data