# Exploring the Whole Rashomon Set of Sparse Decision Trees

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

## Key facts

- Cited by 81 papers in the map (data through 14 Oct 2026).
- Builds on 14 of its 56 references that are in the map.
- First posted on arXiv 16 Sep 2022.

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

- [Understanding Black-box Predictions via Influence Functions](https://mlsanity.com/paper/1703.04730/) (2017)
- [Underspecification Presents Challenges for Credibility in Modern Machine Learning](https://mlsanity.com/paper/2011.03395/) (2020)
- [All Models are Wrong, but Many are Useful: Learning a Variable's Importance by Studying an Entire Class of Prediction Models Simultaneously](https://mlsanity.com/paper/1801.01489/) (2018)
- [Interpretable Machine Learning: Fundamental Principles and 10 Grand Challenges](https://mlsanity.com/paper/2103.11251/) (2021)
- [Understanding How Dimension Reduction Tools Work: An Empirical Approach to Deciphering t-SNE, UMAP, TriMAP, and PaCMAP for Data Visualization](https://mlsanity.com/paper/2012.04456/) (2020)
- [Predictive Multiplicity in Classification](https://mlsanity.com/paper/1909.06677/) (2019)
- [Optimal Sparse Decision Trees](https://mlsanity.com/paper/1904.12847/) (2019)
- [Generalized and Scalable Optimal Sparse Decision Trees](https://mlsanity.com/paper/2006.08690/) (2020)
- [On the Existence of Simpler Machine Learning Models](https://mlsanity.com/paper/1908.01755/) (2019)
- [Fast Sparse Decision Tree Optimization via Reference Ensembles](https://mlsanity.com/paper/2112.00798/) (2021)
- [Robust Optimization using Machine Learning for Uncertainty Sets](https://mlsanity.com/paper/1407.1097/) (2014)
- [A Theory of Statistical Inference for Ensuring the Robustness of Scientific Results](https://mlsanity.com/paper/1804.08646/) (2018)
- [Forward Stability and Model Path Selection](https://mlsanity.com/paper/2103.03462/) (2021)
- [Optimal Decision Trees for the Algorithm Selection Problem: Integer Programming Based Approaches](https://mlsanity.com/paper/1907.02211/) (2019)

## Built on by (most cited first, 30 of 81)

- [Amazing Things Come From Having Many Good Models](https://mlsanity.com/paper/2407.04846/) (2024)
- [Gradient Routing: Masking Gradients to Localize Computation in Neural Networks](https://mlsanity.com/paper/2410.04332/) (2024)
- [A Path to Simpler Models Starts With Noise](https://mlsanity.com/paper/2310.19726/) (2023)
- [Exploring and Interacting with the Set of Good Sparse Generalized Additive Models](https://mlsanity.com/paper/2303.16047/) (2023)
- [The Rashomon Importance Distribution: Getting RID of Unstable, Single Model-based Variable Importance](https://mlsanity.com/paper/2309.13775/) (2023)
- [An Empirical Evaluation of the Rashomon Effect in Explainable Machine Learning](https://mlsanity.com/paper/2306.15786/) (2023)
- [FasterRisk: Fast and Accurate Interpretable Risk Scores](https://mlsanity.com/paper/2210.05846/) (2022)
- [Position: Explain to Question not to Justify](https://mlsanity.com/paper/2402.13914/) (2024)
- [Dropout-Based Rashomon Set Exploration for Efficient Predictive Multiplicity Estimation](https://mlsanity.com/paper/2402.00728/) (2024)
- [The Dataset Multiplicity Problem: How Unreliable Data Impacts Predictions](https://mlsanity.com/paper/2304.10655/) (2023)
- [Systemizing Multiplicity: The Curious Case of Arbitrariness in Machine Learning](https://mlsanity.com/paper/2501.14959/) (2025)
- [Recourse under Model Multiplicity via Argumentative Ensembling (Technical Report)](https://mlsanity.com/paper/2312.15097/) (2023)
- [TimberTrek: Exploring and Curating Sparse Decision Trees with Interactive Visualization](https://mlsanity.com/paper/2209.09227/) (2022)
- [Algorithmic Arbitrariness in Content Moderation](https://mlsanity.com/paper/2402.16979/) (2024)
- [Rashomon Sets for Prototypical-Part Networks: Editing Interpretable Models in Real-Time](https://mlsanity.com/paper/2503.01087/) (2025)
- [Exploration of the Rashomon Set Assists Trustworthy Explanations for Medical Data](https://mlsanity.com/paper/2308.11446/) (2023)
- [Efficient Exploration of the Rashomon Set of Rule Set Models](https://mlsanity.com/paper/2406.03059/) (2024)
- [Be Intentional About Fairness!: Fairness, Size, and Multiplicity in the Rashomon Set](https://mlsanity.com/paper/2501.15634/) (2025)
- [Optimal or Greedy Decision Trees? Revisiting their Objectives, Tuning, and Performance](https://mlsanity.com/paper/2409.12788/) (2024)
- [The Utility of "Even if..." Semifactual Explanation to Optimise Positive Outcomes](https://mlsanity.com/paper/2310.18937/) (2023)
- [Near Optimal Decision Trees in a SPLIT Second](https://mlsanity.com/paper/2502.15988/) (2025)
- [Embracing Contradiction: Theoretical Inconsistency Will Not Impede the Road of Building Responsible AI Systems](https://mlsanity.com/paper/2505.18139/) (2025)
- [Who Are We Missing? A Principled Approach to Characterizing the Underrepresented Population](https://mlsanity.com/paper/2401.14512/) (2024)
- [Quantifying Prediction Consistency Under Fine-Tuning Multiplicity in Tabular LLMs](https://mlsanity.com/paper/2407.04173/) (2024)
- [SORTeD Rashomon Sets of Sparse Decision Trees: Anytime Enumeration](https://mlsanity.com/paper/2511.03344/) (2025)
- ["What is Different Between These Datasets?" A Framework for Explaining Data Distribution Shifts](https://mlsanity.com/paper/2403.05652/) (2024)
- [ExplainerPFN: Towards tabular foundation models for model-free zero-shot feature importance estimations](https://mlsanity.com/paper/2601.23068/) (2026)
- [Kernel KMeans clustering splits for end-to-end unsupervised decision trees](https://mlsanity.com/paper/2402.12232/) (2024)
- [Scalable Rule Lists Learning with Sampling](https://mlsanity.com/paper/2406.12803/) (2024)
- [Learning-Augmented Robust Algorithmic Recourse](https://mlsanity.com/paper/2410.01580/) (2024)

## Abstract (arXiv)

In any given machine learning problem, there may be many models that could explain the data almost equally well. However, most learning algorithms return only one of these models, leaving practitioners with no practical way to explore alternative models that might have desirable properties beyond what could be expressed within a loss function. The Rashomon set is the set of these all almost-optimal models. Rashomon sets can be extremely complicated, particularly for highly nonlinear function classes that allow complex interaction terms, such as decision trees. We provide the first technique for completely enumerating the Rashomon set for sparse decision trees; in fact, our work provides the first complete enumeration of any Rashomon set for a non-trivial problem with a highly nonlinear discrete function class. This allows the user an unprecedented level of control over model choice among all models that are approximately equally good. We represent the Rashomon set in a specialized data structure that supports efficient querying and sampling. We show three applications of the Rashomon set: 1) it can be used to study variable importance for the set of almost-optimal trees (as opposed to a single tree), 2) the Rashomon set for accuracy enables enumeration of the Rashomon sets for balanced accuracy and F1-score, and 3) the Rashomon set for a full dataset can be used to produce Rashomon sets constructed with only subsets of the data set. Thus, we are able to examine Rashomon sets across problems with a new lens, enabling users to choose models rather than be at the mercy of an algorithm that produces only a single model.