# SORTeD Rashomon Sets of Sparse Decision Trees: Anytime Enumeration

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

## Key facts

- Cited by 6 papers in the map (data through 14 Oct 2026).
- Builds on 26 of its 64 references that are in the map.
- First posted on arXiv 5 Nov 2025.

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

- [Distribution-Free Predictive Inference For Regression](https://mlsanity.com/paper/1604.04173/) (2016)
- [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)
- [Predictive Multiplicity in Classification](https://mlsanity.com/paper/1909.06677/) (2019)
- [A survey on datasets for fairness-aware machine learning](https://mlsanity.com/paper/2110.00530/) (2021)
- [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)
- [Exploring the Whole Rashomon Set of Sparse Decision Trees](https://mlsanity.com/paper/2209.08040/) (2022)
- [MurTree: Optimal Classification Trees via Dynamic Programming and Search](https://mlsanity.com/paper/2007.12652/) (2020)
- [Amazing Things Come From Having Many Good Models](https://mlsanity.com/paper/2407.04846/) (2024)
- [Fast Sparse Decision Tree Optimization via Reference Ensembles](https://mlsanity.com/paper/2112.00798/) (2021)
- [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)
- [Strong Optimal Classification Trees](https://mlsanity.com/paper/2103.15965/) (2021)
- [FasterRisk: Fast and Accurate Interpretable Risk Scores](https://mlsanity.com/paper/2210.05846/) (2022)
- [Quant-BnB: A Scalable Branch-and-Bound Method for Optimal Decision Trees with Continuous Features](https://mlsanity.com/paper/2206.11844/) (2022)
- [Learning Optimal Fair Classification Trees: Trade-offs Between Interpretability, Fairness, and Accuracy](https://mlsanity.com/paper/2201.09932/) (2022)
- [Optimal Decision Trees for Nonlinear Metrics](https://mlsanity.com/paper/2009.06921/) (2020)
- [Optimal Sparse Regression Trees](https://mlsanity.com/paper/2211.14980/) (2022)
- [Partial Order in Chaos: Consensus on Feature Attributions in the Rashomon Set](https://mlsanity.com/paper/2110.13369/) (2021)
- [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)
- [Optimal or Greedy Decision Trees? Revisiting their Objectives, Tuning, and Performance](https://mlsanity.com/paper/2409.12788/) (2024)
- [Optimal Classification Trees for Continuous Feature Data Using Dynamic Programming with Branch-and-Bound](https://mlsanity.com/paper/2501.07903/) (2025)
- [Fast and Interpretable Mortality Risk Scores for Critical Care Patients](https://mlsanity.com/paper/2311.13015/) (2023)

## Built on by (most cited first, 6 of 6)

- [REALITrees: Rashomon Ensemble Active Learning for Interpretable Trees](https://mlsanity.com/paper/2603.22750/) (2026)
- [Horizon-Constrained Rashomon Sets for Chaotic Forecasting](https://mlsanity.com/paper/2605.05218/) (2026)
- [When Interpretability Is Unequally Distributed: Fairness in Hybrid Interpretable Models](https://mlsanity.com/paper/2605.28626/) (2026)
- [ArborEnum: Decision Tree Rashomon Sets over Continuous Features](https://mlsanity.com/paper/2608.04310/) (2026)
- [Falling Trees: A Model Class for Interpretable Risk Prioritization](https://mlsanity.com/paper/2609.23780/) (2026)
- [Largest Rashomon sets of decision trees for robust contextual optimization](https://mlsanity.com/paper/2610.04385/) (2026)

## Abstract (arXiv)

Sparse decision tree learning provides accurate and interpretable predictive models that are ideal for high-stakes applications by finding the single most accurate tree within a (soft) size limit. Rather than relying on a single "best" tree, Rashomon sets-trees with similar performance but varying structures-can be used to enhance variable importance analysis, enrich explanations, and enable users to choose simpler trees or those that satisfy stakeholder preferences (e.g., fairness) without hard-coding such criteria into the objective function. However, because finding the optimal tree is NP-hard, enumerating the Rashomon set is inherently challenging. Therefore, we introduce SORTD, a novel framework that improves scalability and enumerates trees in the Rashomon set in order of the objective value, thus offering anytime behavior. Our experiments show that SORTD reduces runtime by up to two orders of magnitude compared with the state of the art. Moreover, SORTD can compute Rashomon sets for any separable and totally ordered objective and supports post-evaluating the set using other separable (and partially ordered) objectives. Together, these advances make exploring Rashomon sets more practical in real-world applications.