mlsanityData to 7 Oct 2026

SORTeD Rashomon Sets of Sparse Decision Trees: Anytime Enumeration

arXiv 2511.03344 ↗First posted 5 Nov 2025cs.LGcited by 5

Not on the map. Why?

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.

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

Builds on

26 of 64 references.

References · 26

  1. 2016Distribution-Free Predictive Inference For Regressioncited by 657
  2. 2020Underspecification Presents Challenges for Credibility in Modern Machine Learningcited by 488
  3. 2018All Models are Wrong, but Many are Useful: Learning a Variable's Importance by Studying an Entire Class of Prediction Models Simultaneouslycited by 364
  4. 2019Predictive Multiplicity in Classificationcited by 162
  5. 2021A survey on datasets for fairness-aware machine learningcited by 157
  6. 2019Optimal Sparse Decision Treescited by 104
  7. 2020Generalized and Scalable Optimal Sparse Decision Treescited by 98
  8. 2019On the Existence of Simpler Machine Learning Modelscited by 87
  9. 2022Exploring the Whole Rashomon Set of Sparse Decision Treescited by 80
  10. 2020MurTree: Optimal Classification Trees via Dynamic Programming and Searchcited by 61
  11. 2024Amazing Things Come From Having Many Good Modelscited by 52
  12. 2021Fast Sparse Decision Tree Optimization via Reference Ensemblescited by 37
14 more
  1. 2023Exploring and Interacting with the Set of Good Sparse Generalized Additive Modelscited by 30
  2. 2023The Rashomon Importance Distribution: Getting RID of Unstable, Single Model-based Variable Importancecited by 29
  3. 2021Strong Optimal Classification Treescited by 27
  4. 2022FasterRisk: Fast and Accurate Interpretable Risk Scorescited by 21
  5. 2022Quant-BnB: A Scalable Branch-and-Bound Method for Optimal Decision Trees with Continuous Featurescited by 19
  6. 2022Learning Optimal Fair Classification Trees: Trade-offs Between Interpretability, Fairness, and Accuracycited by 15
  7. 2020Optimal Decision Trees for Nonlinear Metricscited by 13
  8. 2022Optimal Sparse Regression Treescited by 13
  9. 2021Partial Order in Chaos: Consensus on Feature Attributions in the Rashomon Setcited by 12
  10. 2023Exploration of the Rashomon Set Assists Trustworthy Explanations for Medical Datacited by 11
  11. 2024Efficient Exploration of the Rashomon Set of Rule Set Modelscited by 10
  12. 2024Optimal or Greedy Decision Trees? Revisiting their Objectives, Tuning, and Performancecited by 7
  13. 2025Optimal Classification Trees for Continuous Feature Data Using Dynamic Programming with Branch-and-Boundcited by 6
  14. 2023Fast and Interpretable Mortality Risk Scores for Critical Care Patientscited by 4

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2026: 5.

5 papers.

  1. 2026REALITrees: Rashomon Ensemble Active Learning for Interpretable Treescited by 1
  2. 2026Horizon-Constrained Rashomon Sets for Chaotic Forecastingcited by 0
  3. 2026When Interpretability Is Unequally Distributed: Fairness in Hybrid Interpretable Modelscited by 0
  4. 2026ArborEnum: Decision Tree Rashomon Sets over Continuous Featurescited by 0
  5. 2026Falling Trees: A Model Class for Interpretable Risk Prioritizationcited by 0