Train a decision tree on a dataset. Train another on a slightly different sample from the same population. The two trees may classify the same individual differently — not because the models disagree about the population, but because the tree structure itself is unstable. Small changes in training data produce different splits, different leaves, different predictions for the same person.
Fokkema & Haslbeck (arXiv:2603.11701) decompose this instability into two components. Leaf regret: the variability of predictions within a fixed leaf due to finite-sample noise in estimating the leaf's label. Structural regret: the variability caused by the tree structure changing entirely — the splits happen at different features or thresholds, routing the individual to a fundamentally different part of the tree.
The finding: structural regret dominates. It creates over 15 times more variability than leaf regret in credit risk datasets. The tree's architecture is the unstable part, not its terminal predictions. Even when two trees agree on the general shape of the decision boundary, the precise location of each split is sensitive to individual training points.
This matters for algorithmic fairness. If you're denied a loan, was it because the model learned that people like you are risky (a population-level judgment) or because this particular tree happened to place a split that routes you to a “deny” leaf while an equally valid tree would route you to “approve”? The decomposition answers this: mostly the latter.
The practical fix is selective prediction. Use the regret measures to identify the unstable regions — the individuals for whom structural regret is high — and abstain from prediction there. On the most stable subpopulations, recall rises from 92% to 100%. The cost of knowing where you're uncertain is a smaller but more reliable coverage.
The tree looks deterministic. The instability is hidden in the training process, not visible in the deployed model. You need to retrain to see it.