Research map / Learning theory and algorithms / Prediction and decision losses
SORTeD Rashomon Sets of Sparse Decision Trees: Anytime Enumeration
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Proposes SORTD, a best-first dynamic-programming method that enumerates sparse decision tree Rashomon sets in non-decreasing objective order (anytime), with a depth-two subroutine, and runs up to two orders of magnitude faster than TreeFARMS.
Problem
Enumerating the Rashomon set of sparse decision trees is computationally expensive, and existing methods (TreeFARMS) require a predefined tolerance and do not return trees in objective order, so early termination yields no guarantee of best models.
Approach
Enumerate trees in best-first order by maintaining sorted solution lists at each search node and combining child solutions lazily via a candidates queue (Cartesian-sum style), which gives anytime behavior and supports any separable, totally ordered objective, with post-hoc evaluation of other separable partially ordered objectives.
Key results
- SORTD is up to two orders of magnitude faster than TreeFARMS for enumerating full Rashomon sets across depths 3-5 and set sizes 10^1 to 10^6.
- SORTD uses roughly one order of magnitude less memory than TreeFARMS; most instances stay below 1 GB.
- With 30 features at depth four and 10^6 trees, SORTD completes all runs well below the 300 s limit, whereas TreeFARMS times out on some high-dimensional instances.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Enumerate the Rashomon set in objective order with SORTD instead of TreeFARMS enumeration | Sparse decision tree Rashomon-set computation · 30 binary classification datasets | runtime: up to two orders of magnitude | Helped |
| Use SORTD instead of TreeFARMS | Sparse decision tree Rashomon-set computation · 30 binary classification datasets | memory usage: one order of magnitude less memory | Helped |
| Estimate variable importance from the top 100 trees rather than the top 1 tree | LOFO variable importance analysis · 29 binary classification datasets | top-5 feature Jaccard stability: 19 of 29 datasets had a Jaccard index $\geq 0.8$; this increased to 26 datasets | Helped |
| Estimate variable importance from the top 100 trees rather than the top 1 tree | LOFO variable importance analysis · 29 binary classification datasets | Kendall’s τ ranking stability: 5 datasets using top-1 trees, and for 17 using top-100 trees | Helped |
| Use SORTD rather than CART or STreeD to enumerate regression-tree Rashomon sets | Regression trees · Regression benchmark datasets | number of trees found in the Rashomon set: orders of magnitude more trees | Helped |
Surprising findings
- Variable importance from the top-100 trees is relatively stable compared with top-10,000 (Jaccard >= 0.8 for 26 of 29 datasets).
Limitations
- Limited to binary features.
- Finding even one optimal tree is NP-hard, so enumeration becomes intractable for large depth, dataset, or set size.
- Objectives must be separable and totally ordered for direct computation; post-evaluation of partially ordered objectives requires batch retrieval and is not order-preserving.
Experimental setup
Datasets: 30 binary classification benchmark datasets (from TreeFARMS/MurTree collections) compas fico regression benchmark datasets fairness benchmark datasets
Benchmarks: 30 binary classification datasets compas fico regression datasets fairness datasets
Metrics: runtime (s) memory usage (GB) Rashomon set size LOFO variable importance Jaccard index Kendall's tau
Baselines: TreeFARMS CART STreeD
Builds on: STreeD TreeFARMS DL8
Closest papers by meaning
- Exploring the Whole Rashomon Set of Sparse Decision Trees (NeurIPS 2022 · similarity 0.94)
- Near-Optimal Decision Trees in a SPLIT Second (ICML 2025 · similarity 0.90)
- Optimal Decision Tree Pruning Revisited: Algorithms and Complexity (ICML 2025 · similarity 0.89)
- Witty: An Efficient Solver for Computing Minimum-Size Decision Trees (AAAI 2025 · similarity 0.87)
- Branches: Efficiently Seeking Optimal Sparse Decision Trees via AO* (ICML 2025 · similarity 0.87)
- Multistage Defer Trees for Hybrid Interpretability: If at First You Can't Succeed, Tree Again (NeurIPS 2026 · similarity 0.87)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.