SORTeD Rashomon Sets of Sparse Decision Trees: Anytime Enumeration

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.

2 Related work Methods Rashomon set computation has recently been explored for risk score models [29,31], additive models [20,24,32], rule sets [33,34], random forest [24], and kernel ridge regression [24]. For sparse decision trees-the focus of this work-the only dedicated approach is TreeFARMS [30], which enumerates every tree within a given user-chosen tolerance (the "Rashomon multiplier") but does not preserve a global ordering of trees with respect to the objective. However, this user tolerance is rarely known a priori: an overly large value may result in generating billions of trees, which is memory and time intensive; while a small value may return too few trees. Additionally, TreeFARMS is tailored to classification, and extension to other optimization tasks is non-trivial.

On the contrary, our method produces solutions iteratively in non-decreasing order, allowing the algorithm to stop as soon as a target number of high-quality trees is reached without relying on an accurately tuned tolerance. This gives SORTD an anytime behavior: stopping the search at any time yields a Rashomon set. Furthermore, a specialised depth-two solver reduces runtime and improves scalability with both the number of features and the depth budget. Finally, SORTD handles any separable and totally ordered loss function and supports post-hoc evaluation of separable and partially ordered objectives (e.g., multi-objective optimization), hence increasing flexibility in learning and evaluation.

Decision trees Early decision tree induction methods, such as AID [35] for recursive regression analysis, and CHAID [36] for classification, use top-down induction to infer the next best split. The two most popular approaches, CART [2] and C4.5 [3], share this paradigm. While these methods typically yield good results, their greedy nature may yield models that are arbitrarily larger than optimal [37]. Indeed, provably optimal trees that are obtained through exhaustive search on average obtain a better size-accuracy, and hence interpretability-accuracy, trade-off than greedy approaches [6,7]. Although finding such optimal trees is NP-hard [38], the problem remains tractable for a limited number of features and small tree-size limits [39], and recent dynamic programming (DP) approaches can typically find optimal trees of limited size for real-world datasets in seconds [e.g., 16, 40].

Unlike these approaches, our work aims not to find a single best tree, but the set of all good trees. A key advantage is that this set can be explored to find optimal solutions for other objectives or constraints that are harder to optimize directly. For example, while Demirović et al. [41] develop a specialized DP algorithm for non-linear metrics such as F1-score, Xin et al. [30] obtain the optimal F1-score tree from the Rashomon set based on optimizing accuracy. Similarly, rather than building a custom method for each objective or constraint, such as for example, a demographic parity fairness constraint [42], we explore the Rashomon set instead to find trees that are both accurate and fair.