# Decomposing Observational Multiplicity in Decision Trees: Leaf and Structural Regret

arXiv: https://arxiv.org/abs/2603.11701 · HTML: https://mlsanity.com/paper/2603.11701/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 10 of its 19 references that are in the map.
- First posted on arXiv 12 Mar 2026.

## Builds on (most cited first, 10 of 10)

- [Selective Classification for Deep Neural Networks](https://mlsanity.com/paper/1705.08500/) (2017)
- [Underspecification Presents Challenges for Credibility in Modern Machine Learning](https://mlsanity.com/paper/2011.03395/) (2020)
- [Robust Loss Functions under Label Noise for Deep Neural Networks](https://mlsanity.com/paper/1712.09482/) (2017)
- [Predictive Multiplicity in Classification](https://mlsanity.com/paper/1909.06677/) (2019)
- [Predictive Multiplicity in Probabilistic Classification](https://mlsanity.com/paper/2206.01131/) (2022)
- [The Dataset Multiplicity Problem: How Unreliable Data Impacts Predictions](https://mlsanity.com/paper/2304.10655/) (2023)
- [Investigating the Impact of Balancing, Filtering, and Complexity on Predictive Multiplicity: A Data-Centric Perspective](https://mlsanity.com/paper/2412.09712/) (2024)
- [Stability of decision trees and logistic regression](https://mlsanity.com/paper/1903.00816/) (2019)
- [Observational Multiplicity](https://mlsanity.com/paper/2507.23136/) (2025)
- [Exploring Loss Design Techniques For Decision Tree Robustness To Label Noise](https://mlsanity.com/paper/2405.17672/) (2024)

## Abstract (arXiv)

Many machine learning tasks admit multiple models that perform almost equally well, a phenomenon known as predictive multiplicity. A fundamental source of this multiplicity is observational multiplicity, which arises from the stochastic nature of label collection: observed training labels represent only a single realization of the underlying ground-truth probabilities. While theoretical frameworks for observational multiplicity have been established for logistic regression, their implications for non-smooth, partition-based models like decision trees remain underexplored. In this paper, we introduce two complementary notions of observational multiplicity for decision tree classifiers: leaf regret and structural regret. Leaf regret quantifies the intrinsic variability of predictions within a fixed leaf due to finite-sample noise, while structural regret captures variability induced by the instability of the learned tree structure itself. We provide a formal decomposition of observational multiplicity into these two components and establish statistical guarantees. Our experimental evaluation across diverse credit risk scoring datasets confirms the near-perfect alignment between our theoretical decomposition and the empirically observed variance. Notably, we find that structural regret is the primary driver of observational multiplicity, accounting for over 15 times the variability of leaf regret in some datasets. Furthermore, we demonstrate that utilizing these regret measures as an abstention mechanism in selective prediction can effectively identify arbitrary regions and improve model safety, elevating recall from 92% to 100% on the most stable sub-populations. These results establish a rigorous framework for quantifying observational multiplicity, aligning with recent advances in algorithmic safety and interpretability.