SORTeD Rashomon Sets of Sparse Decision Trees: Anytime Enumeration
Authors: Elif Arslan
Jacobus G. M. van der Linden
Serge Hoogendoorn
Marco Rinaldi
Emir Demirović
Venue: NeurIPS 2025 spotlight ()
Keywords: Rashomon sets
decision trees
interpretable machine learning
Primary area: general_machine_learning

Abstract: 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.

SORTeD Rashomon Sets of Sparse Decision Trees: Anytime Enumeration
Elif Arslan
Jacobus M. van der Linden Delft University of Technology, Netherlands G. M. vanderLinnen@tuudff..
Delft University of Technology, Netherlands Sarslan-1@tudel:1
Serge Hoogendoorn
Marco Rinaldi
Delfi University of Technology, Netherlands S.P. Hoogeendoorn@tuueeff...
Delfi University of Technology, Netherlands M. KiKinaldi@tueelfft..
Emir Demirovié
Delft University of Technology, Netherlands
E. Demmirovic@@udell..
Abstract
Sparse decision tree learning provides accurate and interpretable predictive models that are ideal for high-stakes applications by finding the single accurate within a (soft) size limit. Rather than relying on single "best" tree, Rashomon sets sets-trees with similar performance but varying structures can be used to en- hance variable importance analysis, enrich explanations, and enable users to choose simpler trees or those that satisfy stakeholder preferences (c.g., fairness) without hard-coding such criteria into the objective function. However, because finding the optimal tree NP-hard, enumerating the Rashomon set inherently challenging. Therefore, we introduce SORTD, a novel framework that improves scalability and enumerates trees the Rashomon set in order of the objective value, thus offering anytime behavior. Our experiments show that SORTD reduces runtime by up two orders of magnitude compared with the state of art. Moreover, SORTD compute Rashomon sets for any separable and totally ordered objective and supports post-evaluating the set using other separable (and partially ordered) objec- tives. Together, these advances make exploring Rashomon sets more practical in real-world applications.
Introduction
Decision trees widely regarded of the most interpretable models, their decision paths are easy to follow and understand. While is commonly believed that interpretability comes at the cost of accuracy, recent findings suggest that some applications this trade-off may be negligible (I). This makes decision trees even more appealing in practice, specifically for high-stakes domains.
Decision trees have been extensively studied, with early popular approaches such CART ( and C4.5 (3] focusing on greedy top-down induction. Because the size of a tree correlates with its comprchensibility (4, recent research has also examined optimal or sparse decision trees that maximise performance for a given size limit, thereby obtaining a better accuracy-interee interrcccynttrrrrtablittt trade-off [5] () Consequently, the literature presents variety of approaches
compute such
optimal trees, including mixed-integer programming (7.)), Boolean satisfiability (10 12), constraint programming [13). branch-and-boumt (14), and dynamic programming [15 18
39th Conference on Neural Information Processing Systems (NcurIPS 2025).

---

These methods share the property of returning single decision tree that is constructed to perform well with respect to a loss function. However, there are typically many approximately equally good-but but possibly very fefereentddcision--ree models for given learning problem. This phenomenon is known as the Rashomon effect (19), and the set of all models within a tolerance of the globally optimal loss value is called the Rashomon set.
Rashomon sets offer several advantages over relying on single best model. In explainable AI, they enable the discovery of simpler models 20 2T]. support diverse counterfactual explanations (22).
address underspecification [23), also in explanations (24). and improve variable- crtableeimportance anal- ysis (25]. In addition, they allow evaluation of criteria that are difficult to encode directly into the objective function-sucd as faimess or robustness- by analysing properties across the set. In recidivism prediction. Fisher et al. (26) examined the influence of aaassassocitted variables, and Marx et al. [27] explored how similar models might yield conflicting predictions. Rashomon sets also provide more flexible interface for stakeholders, enabling them to select models that best align with their domain-spectie sppcific constraints. In healthcare, diverse set of models obtained from the Rashomon
set was used to support informed decision-making 28 29
Benefiting from the Rashomon set requires efficient evaluation, as the set size can be prohibitively large (with only ten features and a depth budget of four, it may exceed 10 trees). Practical use cases often require finding the most accurate trees, while also satisfying structural constraints (e.g., limits on tree size or mandatory/forriideen features) or attaining favourable scores on complementary objectives (e.g., fairness). This search task would be greatly simplified if candidate trees were generated in non-decreasing order of their objective value, preventing users from spending substantial time to examine the entire set to locate the desired models.
The current state-of-the-art for obtaining the Rashomon set of sparse decision trees 330 returns every tree whose performance falls within a user-chosen tolerance of the best model (e.g.. 5% above the optimum) but the output is not ordered by the objective. If the search is terminated early, e.g., because of time-out, there is no guarantee that the returned set contains the actually best models according to the objective. Furthermore, when the appropriate margin is uncertain, it is often more practical to select larger value, which can result in the construction of an extremely large set; conversely, if a fixed number of top-ranked models is of interest, there is no systematic mechanism to terminate enumeration once that quantity has been reached.
To address these concerns, we propose a novel framework, SORTD (Sorted Rashomon Sets of Trees using Dynamic Programming). In doing so, achieve three contributions. First, we compute the Rashomon set in order: trees with the best objective values are generated first. Ordered generation enables early termination when a specified number of high-quality models has been obtained, hence providing an anytime Rashomon set property. Our experiments show that having access to the best models early can speed up downstream evaluation tasks such as variable- ciabbleeipprttacce analysis.
Our second contribution is improved scalability in the Rashomon set calculation. To reduce runtime, SORTD incorporates specialised algorithm for trees of depth two or less. This design allows SORTD to scale well with both the number of features and the depth budget. In our evaluation on variety of benchmark classification datasets, we show that SORTD significantly outperforms the state-of-the--ar,, achieving speed-ups of up to two orders of magnitude.
Finally, our third contribution is providing general framework that computes Rashomon sets for separable and totally ordered objectives and evaluates them with any separable and partially ordered one. We demonstrate this by enumerating the Rashomon set also for regression trees in addition to classification, and evaluating the Rashomon set of decision trees using an additional fairness objective. Together, these contributions make SORTD a practical and scalable tool for decision tree training, evaluation, and selection.
The rest of the paper is organized as follows: Sec. rreviewss related work; Sec. Doc.B.oover covers preliminaries; Sec. details the Rashomon set calculation; and Sec. 5 presents the experiments.
2 Related work
Methods
Rashomon set computation has recently been explored for risk score models [29
31
additive models 22) 24 32,, rule sets (3 34). random forest (24), and kernel ridge regression
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 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 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 upproaches, 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 trade-off than greedy approaches (6]
obtain better size-accuracy, and hence www.rrrttaabliyaacurreee
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 single best tree, but the set of all good trees. 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 specialized DP algorithm for non-linear metrics such as Fl-score, Xin et al. (30) obtain the optimal Fl-score tree from the Rashomon set based on optimizing accuracy. Similarly, rather than building custom method for each objective or constraint, such as for example, a demographic parity fairness we explore the Rashomon set instead to find trees that are both accurate and fair.
constraint 42
3 Preliminaries
Notation Given set of binary features F and set of labels K, a sample (I; k;) is a pair of feature vector vi E {0, 1)IFl and label k; E K. A dataset D {<xs, ki)) is the set of samples that can be used to train prediction model. Since we assume that the features are binary, we use D(J) to indicate the set of samples where ʃ is satisfied and D(F) is the set of samples where f' is not satisfied.
Sparse tree objective A binary tree is a function T : (0, 131P1 + K that recursively maps feature vector x to a predicted label k. Starting with the root node, each internal node in T sends an instance left or right when its specified binary feature test is satisfied in æ or not. The final leaf node then provides its assigned label as the return value. The optimization task in this work considers finding trees that optimize a given objective function. In Appendix A.9 we consider arbitrary separable and totally ordered objectives [40), but in the main text, we limit our discussion for brevity to finding optimal sparse classification trees, for which we need to find the tree that minimizes:
C(T, = D
Σ 1T(x) + +N((T.
(a.K)ED
This equation penalizes each misclassification and additionally, the number of leaf nodes NTT) by a complexity cost À [43). Given Eq. 1 T = argminreT(a) C(T, D) finds the optimal tree from the set of all trees ((d) of maximum depth d.
Rashomon set Given a Rashomon multiplier e, the Rashomon set is the set of trees with an objective value within the Rashomon bound ((T', D, =) (1 + ETC(T", D). We obtain the Rashomon set:
R(T D,e) (T E T(d) D) < ((T,D,e))
(2)
3

---

Depth-two subroutine A specialized subroutine for finding optimal trees of depth two was proposed by Demirović et al. [16]. It has significant computation advantage by exploiting precomputed frequency counts instead of repeatedly recursively splitting the dataset. Taking binary classification as example, with D+ the set of positive samples, then (+i))) = H[ k) (a, k) E D+ (f+)] and = [(x,Ai k) (r, k) E D+(f) n D+ are the number of occurrences of feature f.- and of fi and f, combined respectively in the positive samples, which can be counted efficiently by looping over sparse representations of the feature vectors. The frequency counts for other possible feature inclusions or exclusions of features Si and fj in a depth-two tree are calculated implicitly using only these two definitions. E.g., (t: = (fi) - Q (t. J2) represents the number of instances that satisfy feature fú but not fz. The frequency counts Q for negative labels can be calculated analogously. Combining both positive and negative frequency counts allows us to directly compute misclassification scores for all possible depth-two trees.
4 In-order Rashomon set calculation
4.1 High-level idea
Given a depth budget, we construct the Rashomon set by exploring decision trees in ascending (i.e., best-first) order of their objective values. We first identify the optimal tree and set the Rashomon bound (tolerance of the best model). We then iteratively build the Rashomon set by maintaining sorted lists of solutions for each node in the search tree. Note that our contribution lies in this second phase: efficiently identifying and ordering these additional solutions.
To compute the Rashomon set, we list, starting with the optimal one(s), followed by the suboptimal solutions in order of their objective value. A search node contains helper node for each possible split on all features f E F, and one for creating leaf node. Each helper node- branching or leaf- of the search node also maintains its own sorted solution list and pointer to its next unprocessed solution with minimum objective value. Leaf nodes contribute a single solution while branching nodes generate multiple.
search tree. Each search node maintains sorted solution
In essence, during Rashomon set computation, search node either repeatedly returns its best next solution from its sorted list or explores new candidates through its helper nodes when no furthrr solution is available. In this exploration phase, the node selects the best next solution among its helpers, and the chosen helper prepares its next candidate if one exists. The search node then returns this selected solution. This process continues until the Rashomon bound or the Rashomon set size is reached. This lazy enumeration strategy computes new solutions only when needed, thereby reducing computation time.
Search Node
Branching Nodes
Leaf Node
ft
fz
sorted solution list
0
fi,
0.20]
sorted solution list
sorted solution list [ fz. abj 0.30]
sorted solution list 0 k = 0, obj 0.35)
{f
fs, obj 0.25]
0 K obj 0.20
2
{
obj 0.30
ff obj 0.36]
3
[
ob) 0.35)
next U -ー
next
J2.
4
[ = oz,obj 0.36]
Figure 1: Search tree structure. The left-most node is the current search node with its sorted solution list. The middle nodes are branching nodes with features fi and fz. The right-most is a leaf node.
Example 1. Fig. ssoos a search node with three helper nodes: two of its branching nodes and one leaf node. Its solution list aggregates the solutions from the helpers. The leaf node's 's only solution is already included. The branching node with feature fi has the next minimum solution value 0.42.
Fig. 2 shows how a branching node computes its next solution by combining the best solutions from its left and right child nodes. It computes the Cartesian sum {a + b b a E A,b B} (see, e.g.. 44

---

45D, but iteratively and in sorted order, while the sets A and B (the solution lists of the child nodes) the same time are also iteratively generated (and also in-order). The best solution of this branch node is formed by pairing the child search nodes' best solutions (their solutions with index 0). To find the next-best solution, we increment either the left or right index. The lower-valued combination is selected as the next solution, and the other is stored in the candidates queue. In each step, the next solution is either the minimum valued candidate or new combination obtained by incrementing one of the indices of the current next solution.
sorted solution list V Jr obj 0.20
f1
lindxx O, rindex
lindex left solutions
rindex right solutions
Inext RF=
0.22
(f fa, obj t.10
{ = obj 0.10]
Klindex 0, rindex
Cf obj 0.40)
(f D, obj 0.32)
candidates queue
{f fi. obj 0.50)
rindex-
Figure 2: Next solution calculation in a branching node.
Example 2. In Fig. 2 after adding the best solution of value 0.10 + 0.10 = 0.20 (lindex O, rindex = 0), two new options with values 0.10 + 0.32 0.42 (lindex O, rindex = 1) and 0.40 + 0.10 = 0.50 (lindex= = 1, rindex = 0) are considered. The former becomes the next solution, and the latter is stored the candidates queue.
4.2 Algorithm
Phase of our algorithm calculates the optimal tree given dataset, and a depth budget and meanwhile also caches optimal solutions to subproblems. In Phase 2-the focus of our contribution- we create a search tree over subproblems, with each search node holding a sorted list of computed solutions (so far), and the value of the next best solution (initially set to the cached optimal partial solutions). Phase 2 then iteratively requests the next best solution from the root search node, which recursively constructs it by requesting the next best solutions from its child search nodes (sce Appendix (A.I).
Alg. M shows how a search node computes its next best solution. First, the helper node with the smallest next solution value node.nert is found (Line 1). A solution group sol is then created to collect all solutions with the same objective value (Line 2). If the helper node a branching node, additional solutions with the same value are retrieved from its candidates queue CQ (Lines 4-5). This queue is a heap of tuples value, lindex,, rindez), sorted by sol.value, while ländex and rindex are solution indices in the left and right child search nodes' solution lists. Using these indices, ExploreCandidatte recursively explores each retrieved solution to determine whether incrementing the left or right index produces new solutions with the same objective value (Line 6). Solutions matching the solution group's 's value are added to the solution group (see Appendix (A.2). while the others are added to the candidates queue (Lines 7-8). Then, the next solution value of the branching node becomes the minimum solution value in the candidates queue (Line 9).
If the helper node is a leaf node, its next solution and candidates queue become empty (Line 11). The helper node is removed from the list of helper nodes if its candidates queue is empty or if the value of its next solution is higher than the search node's 's upper bound (Lines 12-13). This is because it can no longer contribute new valid solutions in future iterations. Finally, the solution group is added to the helper node's sorted solution list SST (Line 14), and it is returned as the next solution (Line 15).
Alg. 2 details the ExploreCandidates procedure. The list of solutions to explore is initialized with the same-valued solutions list (Line 2). For each solution in this list, new index pairs are generated by incrementing either the left or right index by one (Lines 6-7). If the resulting index pair has not been evaluated previously (Line 8), the left (right) child search node is queried to return its solution with the left (right) index (Lines 9-10). If the child search node does not have that solution yet, is obtained by calling GextextSolution (Alg. [. These left and right solutions are combined into a new solution (Line 11, see Appendix A.3 for the details of the solution combination). the combined solution has the same value as the branching node's current next solution, it is added to the same-vale valued solution list and is explored recursively in later iterations (Lines 13-15). Otherwise, it added to the distinct-valuu solutions list (Lines 16-18).
5

---

Algorithm 1 GetNextSolution()
1: node -- arg mode helper modes node. next
2: sol CreateSSluuionnrrout feature node. node.neat)
3: if noode.ssrranchingNooee]]] then
4: same tome_valued sols t- node. Wet..Seaattoosiiiiaaaneeenoooo same_valued
5: node.CQ +- node. CQ \ same_ valued _ols
6: same valued same_valued _ssssslss others
node. Bat.lpalreCaniiiatttsssmmeeeee valued sols, node.nert)
7:
sol.Add( same ssllsssmea_lllllll valued sols)
8:
node. mode.CQ= + node. CQ U others
mode.nert <- node. CQ.CCQQ.......... (o..TTo()odce value 10: else
9:
11: node. CQ + 0. node.ner next + DO node.nert UB then helper_nodes + Snodes \ {node} node.SSI. node.SSL sol
if node. mode.CQ=a
13:
15:
return sol
Algorithm 2 ExpploreCandidattessssan aasaaaandiiiitssssssmseuuuaaaadd palued _slls next)
1: distinct distinct_valued. sols 0
2: sols p_eeplore t- same ses___aled___e_eeee
3: while jos_to_erplore & do
4: sol sols__t__expooeePPP
5:
for reft__nncremett right increment E {(1,0), (0, 1)) do
6:
left_inder + sol.lineex + deft_nncreeen right_ coll__iderr-e + sol.rinder. + jebbbi_nccemmnn not Visited(lesl_ánnde inder, (ight_inddez) then
7:
8:
9:
GeteeteeeNNhlliinn Sectiionneff_nddeee solR + nodeR- GetNttSSouutinn rright_ inder) sol' t- fnode.feature, Combine solR)} Visited index, right_indez) + true if sol'. value next then
solz -
10:
11:
12:
13:
14:
came_valuee sols +- same same_valued _sols U sol' sols to jo_erplore sols to to__rploree U {sol') else if sol'.valus value < U then defl_inders, sol' .rider + vight_ini inder
15:
16:
sol' lindex Distincl_valued__ distincl valued poouedd_sols sols &- distincl valued_sols sol' return same_valute name_valued_oee sols, distinct-valnne -oaleeds_o
18:
Depth-two subroutine To improve scalability, Alg. 3 adapts the depth-two subroutine proposed by Demirović et al. (16) (see Sec.B) to efficiently calculate all depth-two solutions of three branching nodes. It iterates over all pairs of features ft, fj (Lines 1-2), with fi the branching feature in the root, and f, in either the left or right branching nodes. It then computes the optimal solutions sol, and s for the left and right subtree (Line 4-5). While doing so, only the solutions with values within the upper bound are kept (Lines 6-9). For each left solution, the combinations obtained with the right solutions iteratively evaluated and inserted into the node', sorted solution list until the combination exceeds the upper bound (Lines 11 11-14). See Appendix A.6 for computing trees with one branching nodes.
limit is set on the Rashomon set size, computing all depth-two trees may be unnecessary. We address this by rerunning the depth-two subroutine with an incrementally increased upper bound until the actual upper bound is reached. See Appendix A.7 for details.
4.3 Comparison to the state-of-the-art
TreeFARMS (30
calculates the Rashomon set of trees using a depth-first search and supports only classification tasks. requires predefined Rashomon multiplier. Its solutions can be sorted efficiently but only after full enumeration, making correct estimation of the multiplier necessary.

---

will show in the Algorithm 3 CalculateeThreeeooeeessiiiiiii F, Q, Q-)
1: for b; E F do
2:
left_sols t- 0, right_sols <- 0 for fg E v.i do
3:
4:
sols Sol(fj, Combine(mini (+(,f Q min))))) Q (. (.D
5:
solg t Sol(ff, Combinne(minf Q* (f.ft), Q (f.f)) min Q (f.
6:
if volu. S node. UB then left_sols sols + left foftsssos_ U {solz}
7:
8:
soln-value I node. UB then
9:
right moltt_sols=>
right_ solssssossss U {sola]
10:
for left E left_sols in ascending order do
for right E right_sso in ascending order do val +- Combine (eft, right)
12:
13:
if val node. UB then break Mooee.SLLAdddSSllll val))
14:
In contrast, SORTD computes the Rashomon set in order of objective value using best-first search, enabling anytime behavior: produces a valid Rashomon set at any point. This is particularly beneficial for high-dimensional datasets, ensuring search termination and stable performance. It additionally eliminates the need to guess the Rashomon multiplier, as the search can also stop based on specified set size. When SORTD is run in the same way TreeFARMS (i.e., with a fixed Rashomon bound), SORTD returns the whole Rashomon set up to two orders of magnitude faster than TreeFARMS, while using up to order of magnitude less memory, next section. Furthermore, SORTD is not limited to classification tasks, supporting any separable and totally ordered objective for computation and any separable and partially ordered objective for post-cvaluation.
Limitations
Our approach is limited to binary features, which is a common limitation [e]g..30..
And since finding even a single optimal tree is NP-hard, enumerating the Rashomon set for larger depth budgets, dataset sizes, or target set sizes becomes intractable. However, our scalability improvements extend the range of problem instances that can practically be solved.
5 Experimental evaluation
We conduct series of experiments with the following aims: (I) to assess SORTD's 's runtime efficiency in computing Rashomon sets; (2) to showcase that small number of high-quality trees-easily found by SORTD- be informative for model evaluation via variable importance analysis; and (3) to demonstrate SORTD's flexibility in enumerating and analysing Rashomon sets under varying objective functions.
Experiment set-up For aims (1) and (2), we use the 30 benchmark binary classification datasets
previously used to assess state-of-the-art methods [TO] 15 16 30, 46). For aim (3) we adopt common
regression [47] and fairness benchmark datasets [88]. We implemented SORTD in C++ and provide
it python package We use STreeD [40] to compute optimal trees in SORTD's ''s first phase. All
experiments are run single-threaded on an Intel Xeon E5-6448Y @ 2.1 GHz with 100 GB RAM 49
with 300 seconds time limit. Further details are provided in Appendix
5.1 Runtime performance
We evaluated SORTD's runtime performance against the state-of-the-ar method TreeFARMS (30] across varying Rashomon set sizes n²'.. Since TreeFARMS requires the Rashomon multiplier (or bound) to be specified in advance, multipliers (see Appendix B.2) using the following procedure. We varied the depth budget d E (3, 4, 5) and the complexity cost À E {0.001, 0.01, 0.13. Using each (dataset, A) combination, we
ensured a fair comparison by precomputing the Rashomon

---

ran SORTD to find the smallest multiplier& e that yields at least n = 10" trees for {l..... ,6. 6). We limited n to six, we consider sets larger than 10 trees to be impractical for real-world analysis. Both methods then used these multipliers for Rashomon set enumeration, and runtime was measured to obtain the whole Rashomon set up to the specified bound.
Fig. plots the empirical cumulative distribution of runtimes for finding the whole Rashomon set of the specified size, aggregated over all datasets and À values (see Appendix B.2 for detailed results). Across every depth budget and Rashomon set size, SORTD consistently outperforms TreeFARMS, reaching speed-ups of up two orders of magnitude. increases only slightly most
the depth budget grows, SORTD's runtime -ost sets are produced under 10 seconds even at the largest depth- Whereas TreeFARMS slows by more than an order of magnitude and hits the time limit after depth budget three. Moreover, at higher depth limits, SORTD scales better for increasingly large Rashomon sets.
TreeFARMS
SORTD
n² 10a
n²
10
n² 10c
=
d 4
Total computed (%)
100
75
50
25
11
1100
10
2
10
10
10a
10
10
10
10
10
10
10
10
10
10a
Runtime (s)
Runtime (s)
Runtime (s)
Figure 3: Cumulative runtime (s) distribution across tree depths d and Rashomon set sizes n The x-axis is logarithmic and shows the runtime for enumerating the full Rashomon set. SORTD is up to two orders of magnitude faster than TreeFARMS.
We additionally investigated how feature dimensionality affects runtime. Fig. shows the empirical cumulative distribution of runtimes at depth budget four and n = 10 while varying the feature dimension of the input dataset. Runtime increases for both methods as dimensionality grows, but SORTD is impacted less. Once the feature count exceeds 30, TreeFARMS fails to finish computing some Rashomon sets within the time limit. In contrast, SORTD remains fast: even with 30 features, it completes all runs well below the time limit.
TreeFARMS
SORTD
|F| < 15
16 < F < 30
F >> 30
Total computed (%)
100
75
50
25
0
10
10
10
10a
10a
10
10
109
10a
10a
10
10
10
10a
10a
Runtime (s)
Runtime (8)
Runtime (s)
Figure 4: Cumulative runtime (s) distribution across varying feature dimensionality, with depth budget four and n²" - The x-axis is logarithmic and shows the runtime for enumerating the full Rashomon set. SORTD scales better with more features than TreeFARMS.
Furthermore, we evaluated the memory usage of SORTD. Fig. 5 shows the empirical cumulative distribution of memory usage in gigabytes. For most of the instances, SORTD's memory usage remains below GB, leading to on order of magnitude less memory usage. In contrast, TreeFARMS shows substantially higher memory requirements, particularly at greater depths.
5.2 Variable importance analysis
To test whether SORTD's in-order solution generation facilitates downstream evaluation, we measured variable importance with the Srave-One-Feauuree (LOFO) score (50) by computing the increase
8

---

TreeFARMS
SORTD
n
10
10
n²
10
Total computed (%)
d=3
100
75
50
25
10
10"
10'
10
10
10
10'
10a
10
10
10'
10a
Memory usage (GB)
Memory usage (GB)
Memory usage (GB)
Figure 5: Cumulative memory usage (GB) distribution across tree depths d and Rashomon set sizes
n² Note the logarithmic x-axis. SORTD uses one order of magnitude less memory than TreeFARMS.
the area under the Rashomon objective curve when that feature omitted. Fig. 6 iillustrates LOFO
on the compas [51] and fico [52] datasets using the top-100 trees. As reported by Fisher et al. (26).
"priors is an important variable in compas. our analysis, omitting this feature noticeably shifts the loss curve, and similar effect is observed when excluding external risk estimate features in fico, highlighting their strong predictive influence.
We now start our test whether variable importance obtained through different Rashomon set sizes provides similar insights. We treated variable importance values derived from the top-10,000 trees as reference, and compared them with the ones obtained from the top-1 and top-100 trees. Since importance estimates within Rashomon sets can vary under resampling (25), each dataset was bootstrapped 20 times. For each resample, we computed the Rashomon multiplier required to obtain least 10,000 trees and constructed the corresponding set using the multipliers. We then evaluated the increase in area under the Rashomon objective curve using À 0.01 and depth budget of four. Due to its high runtime requirement, the biodeg dataset was not used in this experiment.
Compas (A 0.01, n 100)
Fico (A 0.01, n² 100)
Relative loss (%)
Relative loss (%)
2
All features
All fentures
priors:33
Exteenaal Extiatttee .949
age:<(2)
ExternalliskFatimnaaaa
juvenile- crimes:
Inquiry 75
100
20
40
60
80
100
Solution index
Solution index
Figure 6: Top-3 influential features identified via LOFO. Shifts in the relative loss curves after removing each feature indicate their influence on the Rashomon set for the compas and fico datasets.
We evaluated top-5 feature stability using the Jaccard index (AA n BI/IAU B)) and full ranking stability using Kendall's (53. Comparing top-1 to 10p-10,000 trees, 19 of 29 datasets had Jaccard index 2 0.8; this increased to 26 datasets for top-100. Similarly, 7 2 0.7 held for datasets using top-1 trees, and for 17 using top- 100 trees (see Appendix B.7 These results suggest that variable importance is relatively stable when using 100 trees, highlighting the potential of estimating the importance values from smaller Rashomon sets. This is particularly useful for large datasets, where computing large Rashomon sets is impractical. Developing theoretical guidelines for the minimum number of trees required to obtain stable importance estimates could further facilitate this analysis.
5.3 Evaluating other objectives
SORTD also supports objectives beyond accuracy (see Appendix A.9). optimizing separable totally ordered objectives directly and evaluating separable and partially ordered ones indirectly.

---

Regression For example, SORTD can directly find the Rashomon set of sparse regression trees with the totally ordered objective of minimal mean mean-squared error. We demonstrate this capability by comparing SORTD with the heuristic CART (2) and the optimal method STreel (40) since other method is known for generating this set. Both methods repeatedly compute trees for random samples of the data until given time limit. Fig. 7 shows that SORTD finds trees in order until the 10% relative bound is reached, whereas, as observed (30] for classification tasks, CART and STreeD find orders of magnitude fewer trees in the Rashomon set. See Appendix B.8 for further details.
Syuchronous Machine
Airfoil Self-Noise
Scoul Bike Sharing Demand
Relative loss (%)
20
SORTD
CART
STreaD
10
109
10a
10
10
10
10
10a
10
10
10a
10a
10a
10
10c
10
Solution index
Solution index
Solution index
Figure 7: Relative loss compared to the optimal solution of all regression trees found within the one minute time-out for max-depth four, À = 0.001, and ε = 0.1. Dashed lines indicate the Rashomon bound. SORTD finds orders of magnitude more trees in the Rashomon set than the other methods.
Equality of opportunity SORTD can also evaluate partially ordered objectives such multi- objective criteria indirectly. E.g., to find fair accurate trees. SORTD can first obtain the Rashomon set based on accuracy, and then evaluate it using another objective such as -quality-ff-opportunii the difference in the true positive rate of two discrimination-son senssiive groups. For example, Fig. shows the top 107 trees in the Rashomon set for accuracy evaluated with the equality-of titiity-oo-oppruuuiii metric. In Appendix B.9 we provide further details and a runtime comparison with STreeD.
i.c..
Adult
Bank Marketing
Compas
Discrimination (%
Discrimination (%
0.0
Diserinination
-2.5
Tree size
No 11-0---0
-19
-2
-6
-7.5
-8
83.50
84.00
80.25
89.75
66.50 66.75 67.00
Accuracy (%)
Accuracy (%)
Accuracy (%)
Figure 8: The top 10" trees in the accuracy Rashomon set evaluated using with max-depth four and X 0.001. The red lines show the Pareto-front of accuracy and fairness. The colours indicate tree size. The sign of the discrimination shows which group is disadvantaged.
Conclusion
The Rashomon set of sparse decision trees offers many advantages over relying single model, provided can be explored efficiently. SORTD makes such exploration practical: enumerates trees in ascending objective order, allowing the highest-quality candidates to be retrieved and evaluated quickly. At the same time, its algorithmic design scales significantly better than the and uses less memory either the feature dimensionality or the depth budget grows. Finally, it supports separable totally ordered objectives for Rashomon set computation, as well as separable and partially ordered objectives for fast post-hoc evaluation. Together, these advances turn large-scale Rashomon-set analysis and model selection into a viable option for real-world applications.
Acknowledgments
This research was supported by the TU Delft AI Labs program.
10

---

References
[1] Cynthia Rudin. "Stop Explaining Black Box Machine Learning Models for High Stakes Decisions and Use Interpretable Models Instead". In: Nature machine intelligence 1.5 (2019),
pp. 206-215.
[2] Leo Breiman, Jerome H. Friedman, Richard A. Olshen, and Charles J. Stone. Classification and Regression Trees. Monterey. CA: Wadsworth and Brooks, 1984.
[3] J. Ross Quinlan. C4.5: Programs for Machine Learning. San Francisco, CA: Morgan Kaufmann Publishers Inc, 1993.
[4] Rok Piltaver, Mitja Luštrek, Matjaž Gams, and Sandra Martinčić-Ipššé.. "What makes clas- sification trees comprehensible?" In: Expert Systems with Applications 62 (2016), pp. 333- 346.
[5] Jimmy Lin, Chudi Zhong, Diane Hu, Cynthia Rudin, and Margo Seltzer. "Generalized and Scalable Optimal Sparse Decision Trees". In: Proceedings of ICMI--00. 2020, pp. 6150-6160.
[6] Jacobus G. M. van der Linden, Daniël Vos, Mathijs M. de Weerdt, Sicco Verwer, and Emir Demirović. "Optimal or Greedy Decision Trees? Revisiting their Objectives, Tuning, and Performance". In: arXiv preprint arXiv:2409. 12788 (2024).
[7] Dimitris Bertsimas and Jack Dunn. "Optimal classification trees". In: Machine Learning 106.7
(2017), pp. 1039-1082.
[8] Sicco Verwer and Yingqian Zhang. "Learning decision trees with flexible constraints and objectives using integer optimization". In: Proceedings of CPAIOR-17. 2017, pp. 94-103.
[9] Sina Aghaei, Andrés Gómez, and Phebe Vayanos. "Strong Optimal Classification Trees". In: Operations Research (2024).
[10] Nina Narodytska. Alexey Ignatiev, Filipe Pereira, and Joao Marques-Sine Silva. "Learning Optimal Decision Trees with SAT In: Proceedings of IJCAI-18. 2018, pp. 1362-1368.
[11] Hao Hu, Mohamed Siala, Emmanuel Hebrard, and Marie-José Huguet. "Learning Optimal Decision Trees with MaxSAT and its Integration AdaBoost". In: IJCAI-PRICAI 2020. 2020,
pp. 1170-1176.
[12] Pouya Shati, Eldan Cohen, and Sheila A. Mcllraith. "SAT-based optimal classification trees for non-binary data". In: Constraints 28.2 (2023), pp. 166-202.
[13] Hélene Verhaeghe, Siegfried Nijssen, Gilles Pesant, Claude-Guy Quimper, and Pierre Schaus. "Learning Optimal Decision Trees using Constraint Programming". In: Construints 25.3 (2020),
pp. 226-250.
[14] Rahul Mazumder, Xiang Meng, and Haoyue Wang. "Quant-BnB: A Scalable Branch-and- Bound Method for Optimal Decision Trees with Continuous Features". In: Proceedings of ICML-22. 2022, pp. 15255-15277.
[15] Gaël Aglin, Siegfried Nijssen, and Pierre Schaus. "Learning Optimal Decision Trees Using Caching Branch-and-Boun Search". In: Proceedings of AAAI-20. 2020, pp. 3146-3153.
[16] Emir Demirovié, Anna Lukina, Emmanuel Hebrard, Jeffrey Chan, James Bailey, Christopher Leckie, Kotagiri Ramamohanarao, and Peter J. Stuckey. "Murtree: Optimal Decision Trees via Dynamic Programming and Search". In: Journal of Machine Learning Research 23.26 (2022), pp. 1-47.
[17] Hayden McTavish, Chudi Zhong, Reto Achermann, Ilias Karimalis, Jacques Chen, Cynthia Rudin, and Margo Seltzer. "Fast Sparse Decision Tree Optimization via Reference Ensembles". In: Proceedings of AAAI-22. 2022, pp. 9604-9613,
[18] Cätälin E. Brita, Jacobus G. M. van der Linden, and Emir Demirović. "Optimal Classification Trees for Continuous Feature Data Using Dynamic Programming with Branch-and- " In: Proceedings of AAAI-25. 2025, pp. 11131-11139,
[19] Leo Breiman. "Statistical modeling: The two cultures (with comments and rejoinder by the author)". In: Statistical science 16.3 (2001), pp. 199-231.
[20] Lesia Semenova, Cynthia Rudin, and Ronald Parr. "On the Existence of Simpler Machine Learning Models". In: Proceedings of the 2022 ACM Conference on Fairness, Accountability. and Transpurency. 2022, pp. 1827-1858.
[21] Cynthia Rudin, Chudi Zhong, Lesia Semenova, Margo Seltzer, Ronald Parr, Jiachang Liu, Srikar Katta, Jon Donnelly, Harry Chen, and Zachery Boner. "Position: Amazing Things Come From Having Many Good Models". : In: Proceedings ICML-24. 2024, pp. 42783-42795.
11

---

[22] Hayden Andersen, Andrew Lensen, Will Browne, and Yi Mei. "Producing Diverse Rashomon Sets of Counterfactual Explanations with Niching Particle Swarm Optimization Algorithms". In: Proceedings of the Genetic and Evolutionary Computation Conference. 2023, pp. 393-401. [23] Alexander D' Amour, Katherine Heller, Dan Moldovan, Ben Adlam, Babak Alipanahi, Alex Beutel, Christina Chen, Jonathan Deaton, Jacob Eisenstein, Matthew D Hoffman, et al. "Under- specification Presents Challenges for Credibility in Modern Machine Learning.. In: Journal of Muchine Learning Research 23.226 (2022), pp. 1-61.
[24] Gabriel Laberge, Yann Pequignot, Alexandre Mathicu, Foutse Khomh, and Mario Marchand. "Partial Order in Chaos: Consensus on Feature Attributions in the Rashomon Set", In: Journal of Machine Learning Research 24.364 (2023), PP. 1-50.
[25] Jon Donnelly, Srikar Katta, Cynthia Rudin, and Edward Browne. "The Rashomon Impor- tance Distribution: Getting RID of Unstable, Single Model-Basee Variable Importance". In: Advances in NeurlPS-255 23. 2023, pp. 6267-6279.
[26] Aaron Fisher, Cynthia Rudin, and Francesca Dominici. "All Models are Wrong, but Many are Useful: Learning a Variable's Importance by Studying an Entire Class of Prediction Models Simultancously" In: Journal of Machine Learning Research 20.177 (2019), pp. 1-81.
[27] Charles T. Marx, Flavio du Pin Calmon, and Berk Ustun. "Predictive Multiplicity in Classifica- tion". In: Proceedings of ICML-20. 2020, pp. 6765-6774.
[28] Katarzyna Kobylińíska, Mateusz Krzyziński,, Rafal Machowicz, Mariusz. Adamek, and Prze- mystaw Biecek. "Exploration of the Rashomon Set Assists Trustworthy Explanations for Med- ical Data". In: IEEE Journal of Biomedical and Health Informatics 28.11 (2024), pp. 6454- 6465.
[29] Chloe Qinyu Zhu, Muhang Tian, Lesia Semenova, Jiachang Liu, Jack Xu, Joseph Scarpa, and Cynthia Rudin. "Fast and Interpretable Mortality Risk Scores for Critical Care Patients". In: Journal of the American Medical Informatics Association 32.4 (2025), pp. 736-747.
[30] Rui Xin, Chudi Zhong, Zhi Chen, Takuya Takagi, Margo Seltzer, and Cynthia Rudin. "Explor- ing the Whole Rashomon Set of Sparse Decision Trees". In: Advances in NeurIPS-22. 2022, pp. 14071-14084.
[31] Jiachang Liu, Chudi Zhong, Boxuan Li, Margo Seltzer, and Cynthia Rudin. "FasterRisk: Fast and Accurate Interpretable Risk Scores". In: Advances in NeurlPS-22. 2022, pp. 17760-17773
[32] Chudi Zhong. Zhi Chen, Jiachang Liu, Margo Seltzer, and Cynthia Rudin. "Exploring and Interacting with the Set of Good Sparse Generalized Additive Models". In: Advances in MeurIPS-233. 2023, pp. 36673-56699
[33] Martino Ciaperoni, Han Xiao, and Aristides Gionis. "Efficient Exploration of the Rashomon Set of Rule-Set Models", In: Proceedings Of The 30th ACM SIGKDD Conference On Knowledge Discovery And Data Mining. 2024, pp. 478-489.
[34] Satoshi Hara and Masakazu Ishihata. " "Approximate and Exact Enumeration of Rule Models". In: Proceedings of AAAI-18. 2018, pp. 3157-3164.
[35] James N. Morgan and John A. Sonquist. "Problems in the Analysis of Survey Data, and Proposal" In: Journal of the American Statistical Association 58.302 (1963), pp. 415-434, [36] Gordon V. Kass. "An Exploratory Technique for Investigating Large Quantities of Categorical
Data". In: Journal of the Royal Staristical Society. Series C (Applied Statistics) 29.2 (1980),
Pp. 119-127.
[37] Michael R. Garey and Ronald L. Graham. "Performance Bounds on the Splitting Algorithm for Binary Testing". In: Acta Informatica 3.4 (1974), pp. 347-355.
[38] Laurent Hyafil and Ronald L. Rivest. "Constructing optimal binary decision trees is NP-
complete". In: Information processing letters 5.1 (1976), pp- 15-17.
[39] Sebastian Ordyniak and Stefan Szeider. "Parameterized Complexity of Small Decision Tree Leaming".. In: Proceedings of AAAI-21. 2021, pp. 6454-6462.
[40] Jacobus G. M. van der Linden, Mathijs de Weerdt, and Emir Demirovié. "Necessary and Sufficient Conditions for Optimal Decision Trees using Dynamic Programming". In: Advances in NeurlPS-23. 2023, pp. 9173
[41] Emir Demirović and Peter Stuckey. "Optimal Decision Trees for Nonlinear Metrics". In: Proceedings of AAAI-21. 2021, pp. 3733-3741.
12

---

[42] Jacobus G. M. van der Linden, Mathijs M. de Weerdt, and Emir Demirović. "Fair and Optimal Decision Trees: A Dynamic Programming Approach". In: Advances in NeurlPS-22. 2022.
pp. 38899-38911.
[43] Xiyang Hu, Cynthia Rudin, and Margo Seltzer. "Optimal Sparse Decision Trees". In: Advances in NeurlPS-19, 2019, pp. 7267-7275.
[44] Donald B. Johnson and Tetsuo Mizoguchi. "Selecting the Ktth Element in X + Y and X1
X2 +.... Xm= In: SIAM Journal on Computing 7.2 (1978), pp. 147-153.
[45] Greg N. Frederickson and Donald B. Johnson. "The Complexity of Selection and Ranking in
X + Y and Matrices with Sorted Columns". In: Journal of Computer and System Sciences
24.2 (1982), pp. 197-208.
[46] Sicco Verwer and Yingqian Zhang. "Learning Optimal Classification Trees Using a Binary Linear Program Formulation" In: Proceedings of AAAI-19. 2019, pp. 1625-1632.
[47] Rui Zhang, Rui Xin, Margo Seltzer, and Cynthia Rudin. "Optimal Sparse Regression Trees".
In: Proceedings of AAAI-23. 2023, pp- 11270-11279.
[48] Tai Le Quy, Arjun Roy, Vasileios Iosifidis, Wenbin Zhang, and Eirini Ntoutsi. "A survey on datasets for fairness- fairness-awart aware machine learning". In: Wiley Interdisciplinary Reviews: Data Mining and Knowledge Discovery (2022), e1452.
[49] Delft High Performance Computing Centre (DHPC). DelftBlue Supercomputer (Phase 2).
attps://wwwz wwwp://wwdllf...m wwtdeeeft..n//pc//aaa//////
htt//dhcc/art// http:/44463//efffBlueehssse 2024.
[50] Jing Lei, Max G'Sell, Alessandro Rinaldo, Ryan J Tibshirani, and Larry Wasserman. "Distribution free predictive inference for regression", In: Journal of the American Statis- tical Association 13.523 (2018), pp. 1094-1111.
[51] Julia Angwin, Jeff Larson, Surya Mattu, and Lauren Kirchner. Machine Bias, May 2016. URL: https: http://wwppppblccaaaaa www.:pppppb..cc..oorraatttteeeee wttp//aaticee//mmciiee...m bias risk - assessments in criminal-sentenciing
[52] FICO, Google, Imperial College London, MIT, University of Oxford, UC Irvine, and UC Berkeley. Explainable Machine Learning Challenge. 2018. URL: https: / community
fico. wwtpo/////pppaaalaaliloo wacooll-mmaiieee-ee Seeiiiieeeerrning-aae chaiaang-caaleegee
[53] Maurice G. Kendall. "A New Measure of Rank Correlation". In: Biometrika 30.1-2 (1938),
pp. 81-93.
[54] Siegfried Nijssen and Elisa Fromont. "Optimal constraint- based decision tree induction from itemset lattices". In: Data Mining and Knowledge Discovery 21.1 (2010), pp. 9-51.
[55] Dheeru Dua and Casey Graff. UCI Machine Learning Repository. 2017. archive ics. uci. edu/ml
URL: http: //
[56] Tong Wang, Cynthia Rudin, Finale Doshi-Velez, Yimin Liu, Erica Klampfl, and Perry Mac- Neille. "A bayesian framework for learning rule sets for interpretable classification". In: Journal of Machine Learning Research 18.70 (2017), pp. 1-37.
[57] Christian Bessiere, Emmanuel Hebrard, and Barry O'Sullivan. "Minimising decision tree size as combinatorial optimisation". In: International Conference on Principles and Practice of Constraint Programminng. 2009, pp. 173-187.
[58] Mim den Bos, Jacobus G. M. van der Linden, and Emir Demirović. "Piecewise Constant and Linear Regression Trees: An Optimal Dynamic Programming Approach". In: Proceedings of ICML-24. 2024.
[59]
Dutch Central Bureau for Statistics. Dutch Census 2001 public use files (anonymized 1 1% samples from the microdata files). DANS. 2001. DOT: http:: //doi. arg//10.1 /te///..1102////1
xms xxc4a
[60] Paulo Cortez and Alice Maria Gonçalves Silva. "Using data mining to predict secondary school student performance". In: Proceedings of 5th FUture BUsiness TEChnology Conference. 2008,
pp. 5-12.
[61] Beata Strack, Jonathan P. DeShazo, Chris Gennings, Juan L. Olmo, Sebastian Ventura, Krzysztof J. Cios, and John N. Clore. "Impact of HbAle measurement on hospital read- mission rates: analysis of 70,000 clinical database patient records". In: BioMed research international (2014).
[62] Sérgio Moro, Paulo Cortez, and Paulo Rita. "A data-driven approach to predict the success of bank telemarketing".. , In: Decision Support Systems 62 (2014), pp. 22-31.
13

---

[63] Jakub Kuzilek, Martin Hlosta, and Zdenek Zdrahal. "Open university learning analytics dataset". In: Scientific data 4 (2017). p. 170171.
[64] Nathanael Jo, Sina Aghaei, Jack Benson, Andrés Gómez, and Phebe Vayanos. "Learning Optimal Fair Decision Trees: Trade-offs Between Interpretability. Fairness, and Accuracy". In: Proceedings of the 2023 AAAI/ACM Conference on AI, Ethics, and Society. 2023, pp. 181-192.
14

---

NeurIPS Paper Checklist
If you answer [Yes] question, in the justification please point to the section(s) where related material for the question can be found.
Claims
Question: Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Answer: [Yes]
Justification: Yes, we state the contributions including the key results in the abstract and introduction section.
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made in the paper.
The abstract and/or introduction should clearly state the claims made, including the contributions made the paper and important assumptions and limitations. A No or NA answer to this question will not be perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results can be expected to generalize to other settings.
is fine to include aspirational goals as motivation as long as is clear that these goals attained by the paper.
2. Limitations
Question:
Does the paper discuss the limitations of the work performed by the authors?
Answer: [Yes]
Justification: Enumerating the Rashomon set for larger depth budgets, dataset sizes, or target set sizes becomes intractable since even finding a single optimal tree is NP-hard. Our method also requires input datasets be binary.
Guidelines:
The answer NA means that the paper has no limitation while the answer No means that the paper has limitations, but those are not discussed in the paper.
The authors are encouraged to create a separate "Limitations" section their paper.
The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (e.g.. independence assumptions, noiseless settings, model well well-specification asymptotic approximations only holding locally). The authors should reflect how these assumptions might be violated in practice and what the implications would be.
The authors should reflect on the scope of the claims made, e.g., if the approach was only tested on few datasets or with few runs. In general, empirical results often depend on implicit assumptions, which should be articulated.
The authors should reflect on the factors that influence the performance of the approach. For example, facial recognition algorithm may perform poorly when image resolution is low or images are taken in low lighting. Or speech-to-text system might not be used reliably to provide closed captions for online lectures because it fails handle technical jargon.
The authors should discuss the computational efficiency of the proposed algorithms and how they scale with dataset size.
If applicable, the authors should discuss possible limitations of their approach to address problems of privacy and faimess.
While the authors might fear that complete honesty about limitations might be used by reviewers as grounds for rejection, worse outcome might be that reviewers discover limitations that aren't acknowledged the paper. The authors should use their best judgment and recognize that individual actions in favor of transparency play an impor- tant role in developing norms that preserve the integrity of the community. Reviewers will be specifically instructed to not penalize honesty concerning limitations.
15

---

3. Theory assumptions and proofs
Question: For each theoretical result, does the paper provide the full set of assumptions and complete (and correct) proof?
Answer: [NA]
Justification: This paper does not have theoretical results.
Guidelines:
The answer NA means that the paper does not include theoretical results.
All the theorems, formulas, and proofs in the paper should be numbered and cross- referenced.
All assumptions should be clearly stated or referenced in the statement of any theorems.
The proofs can either appear in the main paper or the supplemental material, but if they appear in the supplemental material, the authors are encouraged to provide a short proof sketch to provide intuition.
Inversely, any informal proof provided in the core of the paper should be complemented by formal proofs provided in appendix or supplemental material.
Theorems and Lemmas that the proof relies upon should be properly referenced.
4. Experimental result reproducibility
Question: Does the paper fully disclose all the information needed to reproduce the main ex- perimental results of the paper to the extent that affects the main claims and/or conclusions of the paper (regardless of whether the code and data are provided or not)?
Answer: [Yes]
Justification: Yes, we provide the steps to reproduce main results the paper by explaining the algorithm in high-level (Sec. (Sec./4.1) and in detail (Sec. 4.2 A.pendix A.9) Additionally,
we will provide open access to the code when the paper is published.
Guidelines:
The answer NA means that the paper does not include experiments.
If the paper includes experiments, a No answer to this question will not perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not.
If the contribution is dataset and/or model, the authors should describe the steps taken make their results reproducible or verifiable.
Depending on the contribution, reproducibility can be accomplished in various ways. For example, if the contribution is novel architecture, describing the architecture fully might suffice, or if the contribution a specific model and empirical evaluation, may be necessary either make it possible for others to replicate the model with the same dataset, or provide access to the model. In general. releasing code and data is often one good way accomplish this, but reproducibility instructions for how to replicate the results, access to a hosted model (e.g.. in the case of large language model), releasing of a model checkpoint, or other means that are appropriate to the research performed.
also be provided via detailed
While NeurlPS does not require releasing code, the conference does require all submis- sions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) If the contribution is primarily a new algorithm, the paper should make clear how to reproduce that algorithm.
(b) the contribution is primarily a new model architecture, the paper should describe the architecture clearly and fully.
(c) If the contribution is new model (e.g., a large language model), then there should either be way to access this model for reproducing the results or way to reproduce the model (e.g., with an open-source dataset instructions for how to construct the dataset).
(d) We recognize that reproducibility may tricky in some cases, in which case authors welcome describe the particular way they provide for reproducibility.
16

---

In the case of closed-source models, it may be that access to the model is limited in some way (e.g., registered users), but it should be possible for other researchers to have some path to reproducing or verifying the results.
5. Open access to data and code
Question: Does the paper provide open access to the data and code, with sufficient instruc- tions to faithfully reproduce the main experimental results, as described in supplemental material?
Answer: [Yes]
Justification: We will provide open access to the code if the paper is published. We use open datasets for evaluations and their sources are cited the paper.
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurIPS code and data submission guidelines (https://nips.co cc/
for more details.
While we encourage the release of code and data, we understand that this might not be possible, "No" is an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (e.g., for a new open-source benchmark).
The instructions should contain the exact command and environment needed to run to reproduce the results. See the NeurlPS code and data submission guidelines (https
wttpps.ccpublli//uiiieee guwde// CodeeSumiia issiiiissiio onyolicy) for more details.
The authors should provide instructions on data access and preparation, including how access the raw data, preprocessed data, intermediate data, and generated data,
The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. If only subset of experiments reproducible, they should state which ones are omitted from the script and why.
At submission time, to preserve anonymity, the authors should release anonymized versions (if applicable).
Providing as much information as possible in supplemental material (appended to the paper) recommended, but including URLs to data and code permitted.
6. Experimental setting/details
Question:
Does the paper specify all the training and test details (e.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?
Answer: [Yes]
Justification: We explain the instance generation steps and how the algorithms are run in Sec. 5 and and Appendix B
Guidelines:
The answer NA means that the paper does not include experiments.
The experimental setting should be presented in the core of the paper to level of detail that is necessary to appreciate the results and make sense of them.
The full details can be provided either with the code, in appendix, or as supplemental material.
7. Experiment statistical significance
Question: Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Answer: [Yes]
Justification:
We report the standard error of the runtime experiments in Appendix B
Guidelines:
The answer NA means that the paper does not include experiments.
17

---

The authors should answer "Yes" if the results are accompanied by error bars, confi- dence intervals, or statistical significance tests, least for the experiments that support the main claims of the paper.
The factors of variability that the enror bars are capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, or overall
with given experimental conditions).
The method for calculating the error bars should be explained (closed form formula, call to a library function, bootstrap, etc.)
The assumptions made should be given (e.g., Normally distributed errors).
It should be clear whether the error bar is the standard deviation or the standard error of the mean.
is OK to report 1-sigma error bars, but one should state it. The authors should preferably report a 2-sigma error bar than state that they have 96% CI, if the hypothesis of Normality of errors is not verified.
For asymmetric distributions, the authors should be careful not to show in tables or figures symmetric error bars that would yield results that out of range (e.g. negative error rates).
If error bars are reported in tables or plots, The authors should explain in the text how they were calculated and reference the corresponding figures or tables in the text.
8. Experiments compute resources
For each experiment, does the paper provide sufficient information on the com- puter resources (type of compute workers, memory, time of execution) needed reproduce the experiments?
Question:
Answer: [Yes]
Justification: The compute resource is detailed in Sec. We additionally provided the runtime results of the experiments in Appendix B
Guidelines:
The answer NA means that the paper does include experiments.
The paper should indicate the type of compute workers CPU or GPU, internal cluster, or cloud provider, including relevant memory and storage.
The paper should provide the amount of compute required for each of the individual experimental runs as well as estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported in the paper (e.g., preliminary failed experiments that didn't make it into the paper).
9. Code ethics
Question: Does the research conducted in the paper conform, in every respect, with the NeurIPS Code of Ethics
Answer:
[Yes]
Justification:
We checked our paper with the Ethics Guidelines.
Guidelines:
The answer NA means that the authors have not reviewed the NeurlPS Code of Ethics.
If the authors answer No, they should explain the special circumstances that require deviation from the Code of Ethics.
The authors should make sure to preserve anonymity (e.g.. there special consid- eration due to laws or regulations in their jurisdictio))
10. Broader impacts
Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer: [NA]
Justification: Our method is a general machine learning model. It is not tailored any specific application.
18

---

Guidelines:
The answer NA means that there no societal impact of the work performed.
If the authors answer NA or No. they should explain why their work has no societal impact why the paper does not address societal impact.
Examples of negative societal impacts include potential malicious or unintended uses (e.g., disinformation, generating fake profiles, surveillance), fairness considerations (e.g., deployment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considcrations.
The conference expects that many papers will be foundational research and tied to particular applications, let alone deployments. However, if there is a direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that an improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point out that a generic algorithm for optimizing neural networks could enable people to train models that generate Deepfakes faster.
The authors should consider possible harms that could arise when the technology is being used as intended and functioning conrectly, harms that could arise when the technology is being used as intended but gives incorrect results, and harms following from (intentional unintentional) misuse of the technology.
If there are negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition to attacks, mechanisms for monitoring misuse, mechanisms to monitor how system learns from feedback over time, improving the efficiency and accessibility of ML).
11. Safeguards
Does the paper deseribe safeguards that have been put in place for responsible release of data models that have high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?
Question:
Answer: [NA]
Justification:
We not aware of any risk of misuse.
Guidelines:
The answer NA means that the paper poses no such risks.
Released models that have high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model. for example by requiring that users adhere to usage guidelines or restrictions to access the model or implementing safety filters.
Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images.
We recognize that providing effective safeguards is challenging, and many papers do not require this, but we encourage authors to take this into account and make best faith effort.
12. Licenses for existing assets
Are the creators or original owners of assets (e.g., code, data, models), used in the paper, properly credited and are the license and terms of use explicitly mentioned and properly respected?
Question:
Answer: [Yes]
Yes, we have cited the original authors and publishers of all codes and datasets used in the paper. Furthermore, our code includes acknowledgments for any components developed by third parties.
Justification:
Guidelines:
The answer NA means that the paper does not existing assets.
The authors should cite the original paper that produced the code package dataset.
The authors should state which version of the asset used and, possible, include URL.
19

---

The name of the license (e.g., CC-BY 4.0) should be included for each asset. For scraped data from a particular source (c.g., website), the copyright and terms of service of that source should be provided.
assets are released, the license, copyright information, and terms use in the package should be provided. For popular datasets, paperssippsiiiie thcode. com datasets has curated licenses for some datasets. Their licensing guide can help determine the license of dataset.
For existing datasets that are re-pa se-packaged, both the original license and the license of the derived asset (if it has changed) should be provided. If this information is not available online, the authors are encouraged to reach out to the asset's ' creators.
13. New assets
Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?
Answer: [Yes]
Justification: We provide explanations in the code repository. We will provide open access to the code once the paper published.
Guidelines:
The answer NA means that the paper does not release assets.
Researchers should communicate the details of the dataset/code/model part of their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent was obtained from people whose asset is used.
At submission time, remember to anonymize your assets (if applicable). You can either create an anonymized URL or include an anonymized zip file.
14. Crowdsoureing and research with human subjects
Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given to participants and screenshots, if applicable, as well details about compensation (if any)?
Answer: [NA]
Justification:
We did not involve crowdsourcing and did not use human subjects for this
research.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Including this information the supplemental material is fine, but if the main contribu- tion of the paper involves human subjects, then as much detail as possible should be included the main paper.
According to the NeurIPS Code Ethics, workers involved in data collection, curation, or other labor should be paid at least the minimum wage in the country of the data collector.
15. Institutional review board (IRB) approvals or equivalent for research with human subjects
Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or an equivalent approval/review based on the requirements of your country or institution) were obtained?
Question:
Answer: [NA]
We did not involve crowdsourcing and did not use human subjects for this research.
Justification:
Guidelines:
20

---

The answer NA means that the paper does not involve crowdsoureing nor research with
human subjects.
Depending on the country in which research is conducted, IRB approval (or equivalent)
may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper.
We recognize that the procedures for this may vary significantly between institutions and locations, and expect authors adhere the NeurIPS Code of Ethics and the guidelines for their institution.
For initial submissions, do not include any information that would break anonymity (if applicable), such as the institution conducting the review.
16. Declaration of LLM usage
Does the paper describe the usage of LLMs if it is important, original, or non-standard component of the core methods in this research? Note that if the LLM is used only for writing, editing, formatting purposes and does not impact the core methodology, scientific rigorousness, or originality of the research, declaration is not required.
Question:
Answer: [NA]
Justification:
We did use LLMs for core method development.
Guidelines:
The answer NA means that the core method development in this research does not involve LLMs as any important, original, or non-standard components.
Please refer to our LLM policy httt:s///earrrps.cc///ffeeeeeeee for what should or should not be described.
21

---

A Detailed method description
A.1 Main algorithm of Rashomon set calculation
We generate the Rashomon set by iteratively computing trees in ascending order of their objective values. Alg. summarizes how the Rashomon set is computed once the optimal solution has been found. The algorithm takes as input: the maximum depth d, the training dataset D, the optimal solution value sol", the Rashomon multiplier the maximum number of trees n and a cache of optimal solutions of the subtrees. The Rashomon multiplier and the maximum number of trees are complementary: specifying either one is sufficient. If the Rashomon multiplier is omitted, large default value is used to derive the bound.
Next, the root search node is initialized by setting its upper bound to the Rashomon bound and retrieving its optimal solution from the cache (Line 2). This optimal value then compared with the bound to determine whether any solutions lie within the Rashomon set. If the condition is satisfied, additional solutions are iteratively added to the node's sorted solution list until stopping criterion is met (Lines 6).
Algorithm 4 Main (d, sol", ,E, cache)
1: 0 < .eauue x (1 + E)
2: root_ prot_search___ -nddeeddoe + InitializeSearchNooe((1, D, cache)
3: sol 6 root_ vrot_search_node..co
4: while sol. S and
seerrhh_ooeee.. < n do
5: sol +
node. GeNNeetSSttl)))innn
6: root_search Cerrc__ndde.50 node.SSL t root_osorree SSL {sol}
7: return root_ poot_search___ _ode.ooddsSS
A.2 Solutions structure
A Rashomon set may contain well over billion trees, and enumerating such a large set has a high computational and memory load. Therefore, we adopt the grouped solution structure used in [30]: Fig. [ shows how (partial) solutions (i.e., subtrees) are stored in memory. Solutions grouped by their objective value and the splitting feature of the (subtree) root node, followed by a list of pairs of solutions for the left and right subtrees. The details of how same-valued solutions grouped are given in Sec. 4.2
recursively
Example 3. In Fig. D the left of the figure represents different solution values of branching node. Because the first two solution values are the same, solution group (right upper side of the image) with two solution pairs created. As for the remaining solution value, a solution group (right lower side of the image) with one solution pair is created.
solution-1
{f == f2. = 0.5)
obj 0.5
oby 0.5
obj = 0.6
solution paits
fz
f2
fa
left : {f
fs. obj = 0.3)
right: {f 0, obj 0.2)
left: {s St, 0.3)
fs
fa
right: {s 0, 0.23
solution
{f fz. 0.6)
solution pairs
obj
0.3
obj
0.2
obj = 0.3
obj =
0.2
obj
0.4 obj
0.2
left: (1 = 0, 0.4) right (f = 0b 0.2]
Figure 9: SORTD grouped solution structure.
22

---

A.3 Incorporating the regularization cost
The regularization term in the objective function penalizes model complexity by adding À for every leaf node (Eq. (T). Consequently, creating a new split that raises the leaf node count by one increases the objective value even if predictive accuracy is unchanged. To capture this effect, we assign fixed cost of X to each branching decision. If the tree consists of single root leaf, the same cost À is added once for that leaf node.
We use the branching cost while combining left and right solutions and while determining the upper bounds of the child search nodes (see Appendix (A.4).
To construct a solution for a branching (search) node, the algorithm first calculates solutions for its left and right child nodes. It then combines these partial solutions obtain the parent solution (Alg. [ Line 1 ). Since the learning objective imposes a regularization penalty of À per additional leaf, we add the same branching cost of À when combining the left and right subtree solutions follows:
solp.value + X. Combine (solt, solR) soly, value + solr- value
A.4 Upper bounding
To avoid exploring low-quality regions that cannot contribute to the Rashomon set, every search node is equipped with upper bound on the solution value of any tree it may still yield. The root node's upper bound is initialized with the Rashomon bound, and each helper node simply inherits its parent's 's upper bound. Child search nodes, however, receive tighter bounds that account for the best solution already attainable in the complementary subtree. Given a branching node and its upper bound UB, the upper bounds of the child search nodes calculated follows:
U CBL(UB, (UB, solly) UB solit X UBR (UB, soli) = UB soli A.
(4)
(5)
Here, À is to account for the branching cost (see Appendix A.3) while solī and solă are the optimal solution values of the left and right child search nodes, respectively. These optimal solutions are either retrieved from cache optimal solutions or computed using STreeD (40) if absent.
We also use the upper bounds of branching and search nodes for two additional purposes: (1) to filter helper nodes whose next solution value exceeds its search node's 's upper bound (see Alg. : and (2) to determine whether a newly generated solution obtained by combining left and a right solution should be accepted, by comparing it against the branching node's upper bound (see Alg. 2
A.5 Caching
A subtree can be encountered multiple times during the search. To avoid recomputing its solutions in different parts of the search space, we cache both solutions themselves -ste-dsoredd in the search node's sorted solution list and the objects required to compute them, namely the branching search nodes.
We adopt the caching mechanism of Demirović et al. (16), which supports strategies: dataset caching, in which a subtree is identified by the set of samples it contains, and branch caching, in which identified by the features used in every branching decision from the root that subtree. In our experiments, we used dataset caching.
When new search node is created, the algorithm first queries the cache. If the subtree is present, the node reuses the cached solution list and branching nodes. The solution list is then extended not already exhausted- by all search nodes that share it.
A.6 Depth-two subroutine
We use a specialized algorithm to calculate the Rashomon set when the remaining depth budget is at most two. Sec. 4.2 details how, for a given search node, we enumerate all trees that contain three branching nodes. Below, we describe the cases with one and two branching nodes.
Alg. 5 outlines the procedure for generating all trees with single branching node. The algorithm takes as input a search node node, feature set F, class frequency counts Q+ and Q and an upper bound UB. For each feature in F. the algorithm computes the label assignments for the left and right
23

---

children that minimize their respective subtree costs. These two partial solutions are then combined (a.nddix..33ooo for details). the resulting solution value is within the upper bound, the solution is added to the search node's s sorted solution list (Lines 3-4).
(Line 2; see Appendix A.3
Algorithm 5 CalculatteOnNNNdeoollooee,, Q+ Q UB)
for f. E F do 2: val <- Combine(mminQQ(((), Q (A)))
min|
3: if val < UB then
4: L
molee:SS..Sorteelnnsnt((///// va!))
For trees with exactly two branching nodes, the feasible topology is restricted to one of two mirror images: either the left subtree is leaf and the right subtree contains a single branching node, or vice versa. Alg. 6 handles the case in which the right child a leaf; the symmetric case treated analogously.
The procedure begins by selecting feature for the root split and computing the solution of the right subtree being leaf (Line 3). Next, it creates second split in the left subtree using any remaining feature from F and evaluates every possible label assignment, selecting the minimal left-subtree solution value (Line 5). If this value does not exceed the upper bound, the left-subtree solution stored (Lines 6-7). Each stored left solution then combined with the right-leaf solution. The resulting trees inserted into the search node's 's sorted solution list whenever its overall solution value remains within the upper bound (Lines 8-12).
Algorithm 6 CalculateT
F, F.Q+, (B,B)
1:
for S: E F do left_sols +- 0
2:
3:
salR + ( (ft)) (fA))
4:
for fo E F, iF do
5:
val, = Combine (Q+ (f. , Q- min() Q (f,5)) if vall S UB then left_sols + left_sols U Sol(f;, volz)
6:
7:
8:
for Teft E left_sols do
9:
val + Coomiieeleeeeett value, valg)
if val < UB then
11:
sol t UpdaatSooutionnff. val)
Snde.SSL.SortedInserr
The case where the left tree is leaf node and the right tree has a branching node is calculated analogously." **
A.7 Gradual solution creation
When the Rashomon set is subject to a size limit (see Alg. enumerating only subset of the depth-two trees can suffice. We achieve this by tightening the upper bound, hence pruning more candidates, reducing memory usage and runtime. the bound too low, however, the algorithm may spend significant effort (e.g., computing frequency counts) only to yield a single solution; if it is too high, many unused trees are still generated. Empirically, bound that guarantees the inclusion leaf solution and all trees with most one branching node strikes good balance. Therefore, initialize the depth-two upper bound as
ÙB = min D) UB}
(6)
where D and UB denote the dataset and the search node's bound, T is the single-leaf tree that node, and X is the branching cost (Appendix A.3).
With UB set, Alg. 3 5
and generate the depth-two solutions. If the calculated solutions are exhausted before the Rashomon-set size limit is reached, we relax the bound as follows:
UB
(UB ÚB) < 0.2 UB
UB
ÚB + 0.5 (UB ÚB)
otherwise
24

---

This increases the upper bound at diminishing rate, as the number of solutions grows exponentially with respect to the changes in the upper bound.
A.8 Ignoring trivial extensions
By default, SORTD allows extending a tree node with two child nodes that share the same label. Following Xin al. [30]. we refer to these trivial extensions. SORTD can optionally disregard such trees when calculating the Rashomon set. A trivial extension occurs when a branching node produces two leaf nodes whose labels are identical, so the branching does not change the objective value except for the added complexity cost. A trivial extension is detected during the depth-two subroutine (e.g.. Alg. Line 12) or branch-tracker iterations (Alg. Line 11) the following condition holds:
IsLeaf (left) and (rihtt) and left.label = right.labe!
(8)
In some cases, at least one leaf label may be arbitrary: assigning one label or another does not affect the objective value. In this case, SORTD assigns one label arbitrarily, stores one of the alternatives, and when combining with another leaf node, selects the label that avoids creating a trivial extension.
Removing trivial extensions reduces the number of trees in a Rashomon set for fixed Rashomon multiplier, or equivalently, increases the Rashomon multiplier attainable for fixed set size, As shown in Appendix B.6 SORTD maintains performance improvements of up to two orders of magnitude also when trivial extensions are excluded.
A.9 Optimizing other objectives
SORTD supports computing Rashomon sets for separable and totally ordered objectives directly and post-evaluating other separable and partially-ordered objectives over already computed Rashomon set indirectly.
Optimizing totally ordered objectives SORTD's Rashomon construction is based the STreeD framework [40). and therefore easily generalizes to other objectives than the regularized misclas- sification score. However, since SORTD requires sorting partial solutions in its search nodes, cannot support all optimization tasks that STreel) supports i.e., all separable and partially ordered tasks. Specifically, SORTD requires separable and lotally ordered solutions. Additionally, in implementation, we assume all objectives are additive, i.c., solutions from left and right subtrees can be combined using addition. SORTD therefore, has the same generalizability as DL8 (54).
To support other objectives, the only major change is to redefine the objective function C(T, For example, to optimize regression trees by minimizing the sum of squared errors, we define:
C) =
Σ (#:))ED
(T(x) - y)² + ANTT).
To illustrate this, we show in Appendix B.8 SORTD's performance in finding the Rashomon set for regression trees.
Post-evaluating other objectives After generating a Rashomon set, the trees in this set can be evaluated using any objective by going over each tree one at time. However, computing an objective for each tree individually can be expensive. Therefore, we provide special procedure to post-evaluate objectives that are separable (as defined by Linden al. (40)), i.e., we can compute the objective values separately for the left and right subtrees and combine them afterwards. This requires defining some cost function g( D, k) for leaf nodes with D the input dataset and the assigned label. This cost function does not necessarily need to return real-valued number, but can also, for example, return a tuple of values. Similarly, we need to define a combining operator ① that takes a left and right solution and returns the cost of combining both (again, not necessarily real-valued number).
SORTD uses these functions to construct new Rashomon set, with equal- valued solutions grouped together (see Appendix(A.2 However, in this post-evaluation, we no longer require the objective to be totally ordered, so we can no longer acquire the solutions in order of the second objective. In practice, we obtain the Rashomon set in order according to the optimization objective (e.g.. regularized accuracy), by retrieving them in batches. We run Alg. [ a certain Rashomon set size: evaluate the obtained solutions using the second objective; and possibly rerun Alg. 4 with larger
25

---

return (acc, disc) Rashomon set size, continuing where we left. This can be repeated until a certain time-out or some other user-defined stopping criterion.
To facilitate ease of evaluation, SORTD allows users to define the leaf cost function and the combining operator in Python and pass them SORTD. Consider, for example, optimizing trees with multi-objective criterion of regularized accuracy and the fairness metric The equality of opportunity loss is defined as the difference the true positive rate between two discrimination sensitive groups. More formally, let be the true label, ý the predicted label, then equality of opportunity requires:
P = y 1, group one) = P(ù = y group two).
(10)
We can compute this by defining a leaf cost function that counts for both groups how many samples with the true positive label are also predicted with positive label. Additionally, we count the total number of misclassifications so that we can also compute the accuracy. Hence, the solution tu- ple returned will be (misclassifications, positive cateee_oon____e wownl_group____ combining operator is then simply element-wise addition of two tuples. Finally, we need to provide function that computes from these tuples in the root node the actual objective value. In this example, the final objective value is a tuple of the accuracy the difference the true positive rate for two groups. These tuples can then be filtered to only keep the Pareto front. In Python,
cwwnt_group __). The
write:
def leaf (dataview, label):
mis mattaviewnnum_neee num instannstnncsss ctatttance__fo_____e_ for forelabel (1 label)
if label == 1:
Assume feature
the discrimination sensitive feature
groupi_size dataview num num_ fosstances_for_labbeee andaelladd_____aeeea_ _nd__aatuuree_f 0)
6
groupo_size dataview num_ datavies.num www.instaaccesfforr (1) groupi_size
return (mis, 0) return (mis, groupo_size, groupi_size)
10 def (sol1: tuple, sol2: tuple): return (sol1(0) + sol2(0), soll [1] + so12[1), soll [2] sol2 (2))
def obj (sol: tuple):
acc 1.0 sol [0] n
15
disc (sol [1] N_pos_ (sol [2] / N_pos-group1)
18 model SORTDClassifier ("cost- conp-o-opexx-ccuuceee cost_ coaa__compeexity00.
max_depth=3,
max nax_num_trees trees 10000)
model. y)
results = model.. evaluate othher otther_obeectiveeC y, leaf, add) solution_values [obj (s. objective) for in results]
Listing 1: Example Python Code for optimizing accuracy and equality of opportunity.
B Experiment details
B.1 Classification datasets
We selected all 46 binary classification datasets with less than 100 binary features from 16 and
We excluded nine duplicate datasets and three trivially solvable (solved in under one second). We also removed four datasets that exceeded memory limits when calculating the Rashomon multipliers for specific Rashomon set sizes. This computation
30
memory intensive because the Rashomon multipliers were unknown, which required setting the upper bound to a high value.
After these exclusions, 30 datasets remained. From these, climinated duplicate and complementary features. Table [ lists the datasets together with their sample size and resulting feature size, [D] and [F|, respectively. These datasets were used in runtime (Sec. 5.1 and variable importance analysis
(Sec. 5.2 The original datasets can be obtained from the UCT Machine Learning repository [55] and
from 51 52 56 57].
https://bituukket wwwt://rr/nnnnnnnnnnneeeeeeeeeee
attps://githie www.//ooo/sssooepeeeeeeeeoo htte-sssssopppttteeaareee
26

---

Table Classification datasets
Dataset
DD
[F]
Dataset
D
F]
anneal
812
44
HTRU2
17898
57
bank
4521
23
hypothyroid
3247
39
banknote
1372
16
kr-vs-kp
3196
38
bar-7
1913
lymph
148
47
biodeg
1055
81
messidor
1151
24
breast
699
monk1
124
15
car
1728
15
monk2
169
11
cheap
2653
monk3
122
15
coffee
3816
15
mouse
70
45
compas
6907
soybean
630
42
diabetes
768
11
spect
267
22
expensive
1417
tic-tac-toe
958
18
fico
10459
17
tumor
336
17
haberman
306
92
vote
435
48
hepatitis
137
34
yeast
1484
46
B.2 Runtime performance
We generated benchmark instances by varying the complexity penalty {0.001, 0.01, 0.1) and the depth budget E {3, 4, 5}. For each (dataset, X, d) combination, we use SORTD to compute the minimum Rashomon multiplier (and corresponding Rashomon bound) that yields at least 10" trees for every n E [l,...,6)) 6}. Because both methods employ a grouped solution structure, requesting 10" solutions may sometimes yield more than 10*+1 solutions, with the additional solutions sharing the same objective value. In such cases, we did not generate separate instance for the 10"+1 target, as it was already satisfied. Finally, we ran each instance five times.
We compare SORTD with the state-of-the-arr algorithm TreeFARMS [30]. under a 300- second time limit per instance. Each experiment is repeated five times. We set rashomon_ cattooooonnnnrreee wtt.iialeeeteessieeeeeeeeeeeeeee results with trivial extensions ignored). Runtime results presented in Tables 2 4 The results of the instances with depth budget three are not presented as both methods solved most of them within second. Entries marked -_' indicate omitted runs due excessive memory usage. We denote runtimes below one second with << 1', and timeouts with "> 300'.
www.exeeessii ions False for both methods (see Sec. B.6 for runtime
As expected, increasing À simplifies the search problem for both methods. A larger penalty on leaf usage encourages shallower trees, which effectively prunes deeper parts of the search space. In contrast, small À values lead to significantly larger search spaces.
Across most instances, SORTD completes enumeration within one second for depth four and within ten seconds for depth five. In contrast, TreeFARMS exhibits high variability- for depth four, runtimes range from below a second to full timeouts. Its performance degrades further with increasing depth, frequently timing out for À 0.001 and À 0.01 especially when the feature size of the dataset is high.
To evaluate the overall performance of SORTD compared to TreeFARMS, Tables also report the geometric mean of the average runtime ratios tIeeFARMS Roooos/ttsRrru /tSORDD where timeout values are considered as 300 seconds. Results show that SORTD achieves up to two orders of magnitude improvement in runtime over TreeFARMS for Rashomon set enumeration. These findings further emphasize SORTD's scalability, particularly as problem complexity increases with respect to tree depth, dataset size, and regularization parameter X.
27

---

Table 2: Runtime (s) performance of methods to caleulate Rashomon datasets and depth budgets with À = 0.001 and n² = 10", n E {1.... 6). Results are reported as mean standard error. A indicates results that omitted due to their high memory requirement.
d d=
Dataset
[D]
FF
TreeFARMS
SORTD
TreeFARMS
SORTD
breast
699
10
<1
monk2
169
11
<1
<
210.1
<1
diabetes
768
11
<1
<
<1
compas
6907
12
<I
<
1+0,0
<1
bar-7
1913
14
<1
<
1+0.0
1728
15
<1
<
5.0.2
expensive
1417
15
<1
<
6+0.1
cheap
2653
15
1+0.0
<
6ł0.1
monk1
124
15
<1
440.7
monk3
122
15
140.0
<1
22+0.7
coffee
3816
15
140.0
<
740.2
banknote
1372
16
<1
<1
tumor
336
17
240.1
<
20
fico
10459
17
540.2
<
321111
240.0
tic-tac-toe
958
18
240.0
<
21+0.0
<1
spect
267
22
22+0.7
>300
bank
4521
23
820.1
<
88:0.4
2+0.0
messidor
1151
24
540.3
<
3340.7
hepatitis
137
34
10342.6
<
>300
14.
kr-vs-kp
3196
46+0.66
<
>300
12+0011
hypothyroid
3247
39
4940.8
>300
9+0.5
soybean
630
42
5742.0
<
>300
710.2
anneal
812
44
24:0.3
<
>300
5.0.1
mouse
910.11
<
>300
5=0.11
yeast
1484
46
184+11.3
<
>300
14
lymph
148
47
13916.1
<1
>300
9#0.0
vote
435
48
>300
<1
>300
1340.1
HTRU2
17898
57
>300
540.2
>300
140+2.55
biodeg
1055
81
>300
4+0.0
>300
203
haberman
306
92
>300
2+0..0
>300
155++3.8
Geometric mean improvement
86.95
24.30
Table 3: Runtime (s) performance of methods to calculate Rashomon sets across datasets with A = 0.01 and nf 10", n (., 6). Results are reported as mean + standard error. indicates results that are omitted due to their high memory requirement.
d =
d d= 5
Dataset
D
TreeFARMS
SORTD
TreeFARMS SORTD
breast
699
10
<1
<1
monk2
169
11
<1
<1
2+0.1
<1
diabetes
768
<1
compas
6907
12
<1
<1
<1
<1
bar-7
1913
14
<1
<|
1::.00
1728
15
<I
<1
510.22
<]
expensive
1417
15
<1
<
610.11
cheap
2653
15
1+0.1
<
510.4
monkl
124
15
<
<1
5+1.1
monk3
122
15
2+0.1
<]
32115
coffee
3816
15
1
<1
740.
28

---

d=
d=
Dataset
[P]
TreeFARMS SORTD
TreeFARMS
SORTD
banknote
1372
16
<1
<
1+0.00
tumor
336
17
2+0.11
<
1940.5
<1
fico
10459
17
5:0.2
<
3741.6
340.1
tic-tac-toe
958
18
240.00
<
2110.1
spect
267
22
33412
<1
>300
<1
bank
4521
23
7#0.4
<
4945.8
310.2
messidor
1151
24
5:0.4
<
3342.8
<1
hepatitis
137
34
125+2.4
<
>300
7249.2
kr-vs-kp
3196
38
46:00,9
<
>300
11:0.2
hypothyroid
3247
21+3.5
<
79+20.3
6+t.44
soybean
630
42
102
<
>300
5+0.2
anneal
812
44
25+00.7
>300
5+0.2
mouse
70
45
11:00.3
<1
>300
5.H011
yeast
1484
189
<
>300
13:0..7
lymph
148
47
241 13.9
<
>300
6+t011
vote
435
48
>300
<1
>300
8:0.55
HTRU2
17898
57
198724.7
810.4
224424.9
117=660
biodeg
1055
>300
440.1
haberman 306
92
>300
340.3
>300
133+2.7
Geometric mean improvement
68.57
24.60
Table 4: Runtime (s) performance of methods calculate Rashomon sets across datasets with 0.1 and n 10", n E {1, 6}. Results are reported as mean + standard error.
d =
d d=
Dataset
[D]
FF
TreeFARMS
SORTD
TreeFARMS
SORTD
breast
699
10
<1
<1
<1
monk2
169
11
<1
<
1+0.3
<1
diabetes
768
11
<1
<]
<|
compas
6907
12
<I
<1
<1
<1
bar-7
1913
14
<
car
1728
15
<1
<
2+0.5
expensive
1417
15
<
240.5
cheap
2653
15
<1
<
140.3
monk1
124
15
140.2
<
11+27
monk3
122
15
<1
4+13
coffee
3816
15
1+0.2
<
24.55
banknote
1372
16
<1
<
<1
tumor
336
17
140.2
<
2+0.7
fico
10459
17
240.6
<
411.2
24.3
tic-tac-toe
958
18
2+0.3
<
6+1.4
spect
267
22
742.8
<
11+4.3
bank
4521
23
340.8
<
1...4
2+0.3
messidor
1151
24
240.5
24..77
hepatitis
137
34
14+5.1
<
15+55.9
12+24
kr-vs-kp
3196
38
32+4.7
<1
125+25.2
440.6
hypothyroid
3247
39
4+1.0
<1
5+1.4
5+0.8
soybean
630
42
1546.00
2249.00
410.77
anneal
812
44
3+0.7
<1
3+1.0
340.5
70
45
942.5
<1
56421.8
140.2
yeast
1484
46
66+13.3
1402
131+24.5
10+1.5
lymph
148
50=14.5
<I
73420.5
340.5
vote
435
48
10::2.9
1013.00 <1
440.8
29

---

d=
d d=
Dataset
[|]
TreeFARMS
SORTD
TreeFARMS
SORTD
HTRU2
17898
57
30:19.77
6
35+11.6
11+11.5
biodeg
1055
81
170=27.3
6:0.88
haberman
306
92
255+21.1
2:0033
265
2173.7
Geometric mean improvement
16.06
6.10
Longer runtime evaluation for timeout instances Runtime results in Tables show that several TreeFARMS (30) instances reached the 300-second time limit. To further examine these cases, we extended the runtime limit to 3600 seconds. Tables 5 6 present the results for depth budgets four and five, respectively.
With the extended limit, most depth-four instances complete within the allotted time. For depth five, TreeFARMS requires substantially more memory for some larger instances and longer runtimes for others, highlighting SORTD's 's improvements in runtime and memory efficiency.
Table 5: Runtime (8) of methods for calculating the Rashomon set of the timeout instances in Sec. B.2 with a depth budget four, aggregated for each dataset and X.
Dataset
À
TreeFARMS
SORTD
biodeg
0.001
>3600
biodeg
0.01
>3600
4
biodeg
0.1
1499
9
haberman
0.001
653
2
haberman
0.01
2025
haberman
0.1
387
3
HTRU2
0.001
754
5
HTRU2
0.01
641
10
lymph
0.01
<1
lymph
0.1
vote
0.001
454
<1
vote
0.01
406
vote
0.1
2
Geometric mean improvement
325.64
Table 6: Runtime (s) of methods for calculating the Rashomon set of the timeout instances in Sec. B.2
with a depth budget of five, aggregated for each dataset and X. indicates results omitted due to high memory requirements.
Dataset
TreeFARMS
SORTD
anneal
0.001
570
anneal
0.01
513
6
biodeg
0.001
195
biodeg
0.01
104
haberman
0.001
>3600
154
haberman
0.01
145
haberman
0.1
27
hepatitis
0.001
2318
57
hepatitis
0.01
>3600
80
HTRU2
0.001
134
HTRU2
0.01
125
HTRU2
0.1
170
hypothyroid
0.001
1654
9
hypothyroid
0.01
9
30

---

Dataset
TreeFARMS
SORTD
kr-vs-kp
0.001
1250
12
kr-vs-kp
0.01
1323
11
kr-vs-kp
0.1
369
lymph
0.001
1888
9
lymph
0.01
>3600
lymph
0.1
6
mouse
0.001
1195
mouse
0.01
1031
mouse
0.1
3
soybean
0.001
>3600
soybean
0.01
2604
6
spect
0.001
1365
<1
spect
0.01
2269
<1
spect
0.1
vote
0.001
>3600
13
0.01
2114
vote
0.1
9
yeast
0.001
yeast
0.01
13
yeast
0.1
21
Geometric mean improvement
197.27
B.3 Memory Performance
Using the same experimental setup described in Sec. B.2 we additionally evaluated the memory usage of both methods. Tables show the detailed results (in gigabytes). Datasets for which both methods required less than GB memory are omitted from the tables, although their values are included in the geometric means of the average memory usage ratios TheeAARM MSooRT reported at the end of each table.
Table 7: Memory usage (GB) of methods calculate Rashomon across datasets with À 0.001 and 7 = 10", n E {1,... 6}. Results are reported as mean + standard error. A indicates results that omitted due their high memory requirement.
d=4
d d=
Dataset
D
FF
TreeFARMS
SORTD
TreeFARMS SORTD
coffee
3816
15
<1
<1
1#0.0
<|
fico
10459
17
1+0.0
<1
840.0
<1
tic-tac-toe
958
<1
<1
240.0
<|
spect
267
22
<1
<1
340.0
<1
bank
4521
23
1+0.0
840.0
<
messidor
1151
24
<1
<1
140.0
<
hepatitis
137
34
140.0
340.0
kr-vs-kp
3196
38
440.0
2440.0
hypothyroid
3247
39
440.0
<1 24+0.0
soybean
630
42
240.0
<1
13+02
anneal
812
44
1+0,0
<]
940.0
yeast
1484
46
1010.1
2410.0
lymph
148
47
140.0
<1
410.1
<|
vote
435
48
440.0
1740.2
HTRU2
17898
57
2440.0
<1
3915,6
<
biodeg
1055
81
2440.0
7147.8
<I
haberman
306
92
1+0.0
<1
4+0.0
<1
Geometric mean improvement
24.95
44.99
31

---

The geometric mean results indicate that, for each depth and À configuration, SORTD reduces memory usage by more than an order of magnitude compared to TreeFARMS. Combined with the runtime results, these findings demonstrate that SORTD achieves superior overall efficiency in both runtime and memory performance.
Across all datasets, maximum depths, and À values, SORTD's memory usage consistentl remains below GB. In contrast, TreeFARMS shows substantially higher memory requirements, particularly at greater depths for À 0.001 and À = 0.01, and in datasets with larger feature spaces.
Table 8: Memory usage (GB) of methods to calculate Rashomon sets actoss datasets with À 0.01 and n = 10", n E {l..., ., 6}. Results are reported as mean standard error. A '_' indicates results that are omitted due to their high memory requirement.
d 4
d d=
Dataset
[D]
[P]
TreeFARMS
SORTD
TreeFARMS
SORTD
coffee
3816
15
<1
1+0.0
<|
fico
10459
17
1+0.0
<1
840.0
<1
tic-tac-toe
958
<1
240.0
<|
spect
267
22
<1
<1
340.0
<l
bank
4521
23
1+0.1
<1
420.5
<|
messidor
1151
24
<1
<1
140.0
<|
hepatitis
137
34
1+0.0
<1
820.1
kr-vs-kp
3196
38
440.1
<1
24+0.0
hypothyroid
3247
39
2+0.4
<1
4+12
soybean
630
42
240.00
13+0.3
anneal
812
44
1+0.0
8+0.1
yeast
1484
46
1040.1
2410.0
lymph
148
47
240.0
<1
1240.2
<
vote
435
48
340.2
<1
740.9
HTRU2
17898
57
1741.9
<]
22:3.00
140.4
biodeg
1055
81
3614.2
10010000
<1
haberman 306
92
240.2
<1
540.1
<1
Geometric mean improvement
21.28
30.36
Table 9: Memory usage (GB) of methods to calculate Rashomon sets across datasets with 0.1 and nf 10", (1, (,..,,,, 6). Results reported mean + standard error. A s_' indicates results that are omitted due to their high memory requirement.
d 14
d=
Dataset
DD]
[F]
TreeFARMS SORTD
TreeFARMS SORTD
kr-vs-kp
3196
38
34004
<1
7116
<1
yeast
1484
46
3::0.7
611.6
<|
HTRU2
17898
57
21:0.7
<1
2+:0.7
5.1.7
biodeg 1055
81
9+1.8
<1
haberman 306
92
1=0.11
<1
240..4
1+0.22
Geometric mean improvement
12.91
4.21
B.4
Rashomon multipliers
Table 10 reports the minimum Rashomon multiplier values computed by SORTD to yield least 10" trees for each n E [1,...,6) 6) for subset of datasets. These results correspond to instances with 0.01 and depth budget of four. For readability, values are rounded two decimal places.
The table reveals substantial variation in the Rashomon multipliers required to achieve given set size across datasets. For example, while 0.16 is necessary to obtain 10 trees for the hypothyroid
32

---

dataset, the same value yields over one million trees for the specr dataset. This illustrates the difficulty of selecting an appropriate Rashomon multiplier target desired size. SORTD addresses this challenge through its ordered solution enumeration and anytime behavior: enumeration can be stopped once the desired number of models is reached, while still preserving the Rashomon set. property without requiring prior knowledge of the Rashomon multiplier (or bound).
Table 10: Rashomon multipliers required obtain least 10 trees for instances with À 0.01 and depth budget four. The required multipliers vary strongly across datasets.
n
Dataset
10a
10a
103
101
105
106
bank
0.08
0.13
0.16
0.23
0,25
0.32
car
0.03
0,06
0.11
0.14
0.17
0.23
hypothyroid
0.16
0.19
0.34
0.39
0.54
0,58
monkl
0.0
0.14
0.29
0,43
0.43
0.57
monk2
0.01
0.03
0.04
0.07
0.09
0.12
monk3
0.06
0.14
0.21
0.25
0.35
0,42
mouse
0.0
0.0
0.08
0.19
0.27
0.33
spect
0.0
0.02
0.05
0.07
0.1
0.13
tic-tac-toe
0.01
0.01
0.04
0.05
0.08
0.1
vote
0.16
0.17
0.32
0.32
0.44
0.47
B.5 Comparison the tree ordering
A key difference between the state-of-the-an approach (TreeFARMS (30) and SORTD lies in how trees are ordered within the Rashomon set. Fig. illustraas this distinction. The figure reports the minimum number of trees that must be examined sequentially from the start of the Rashomon set to include all trees within the top 2% of the lowest distinct objective values.
Bar-7 7 0.01, 0.05)
Monk2 (2 0.01, & 0.1)
400
1000
Largest index
Largesi index
200
500
TreeFARMS
TreeFARMS
SORTD
SORTD
25
50
75
100
25
50
75
100
Top x% of lowest objective values
Top x% of lowest objective values
Figure 10: Largest index of the trees that belong the top-2% of the lowest distinct objective values.
As the examples show, identifying trees within the top 20% of lowest objective values using the state-of-the-art method may require exploring nearly the entire set. In contrast, SORTD provides early access to high-quality solutions, greatly reducing the overall evaluation effort.
B.6 Runtime performance without trivial extensions
In Sec. B.2 evaluated the runtime performance of SORTD while allowing trees with trivial extensions during Rashomon set computation. A trivial extension refers to a split that produces two leaf nodes with the same label (see Sec. A.8) We now assess how excluding such trees affects SORTD's runtime performance.
Following the same experimental setup as in Sec. B. we generated benchmark instances by vary- ing the complexity penalty E (0.001, 0.01, 0. T and the depth budget d E (4,5). For each (dataset, X, d) combination, SORTD used to compute the minimum Rashomon multiplier (and
33

---

corresponding Rashomon bound) required to obtain at least 10" trees for every E fl,..., 6). Using these multipliers, constructed the respective Rashomon to evaluate the performance of SORTD against TreeFARMS.
For fixed Rashomon size, ignoring trivial extensions can increase the required multiplier values, making some instances slightly more difficult. This is reflected in a modest rise in runtime. Nevertheless, SORTD's runtime performance remains stable, consistently achieving to two orders of magnitude speed improvement over TreeFARMS.
Runtime results presented in Tables
Table 11:
Runtime (s) of both methods for Rashomon set computation with trivial extensions ignored, across datasets and depth budgets, for À 0.001 and n" 10", n (l..... .6. Results are reported as mean + standard error.
d= 4
d=
Dataset
[D]
F1
TreeFARMS SORTD
TreeFARMS
SORTD
breast
699
10
<1
<1
<1
monk2
169
11
<1
<1
3+0.1
diabetes
768
11
<1
compas
6907
12
<1
<1
140.0
<1
bar-7
1913
14
<1
1+0.1
car
1728
15
140.0
<
710.1
expensive
1417
15
140.0
<
610.1
cheap
2653
15
120.0
<
520.1
monk1
124
15
6+0.8
monk3
122
15
3+0.
31+3.7
coffee
3816
15
1+0.0
6+0.2
banknote
1372
16
<1
<I
<1
tumor
336
17
240.0
<
1840.11
fico
10459
17
6.0.11
<
3840.88
240.1
tic-tac-toe
958
18
240.0
<
22.00.3
spect
267
22
29:1.
<1
>300
bank
4521
23
11:0.2
<1
121+1.7
140.0
messidor
1151
24
540.2
<1
4611.6
<1
hepatitis
137
34
112+3.6
>300
2+0.1
kr-vs-kp
3196
38
62+2.7
<
>300
10+0.3
hypothyroid
3247
39
58+1.8
<
>300
8+0.44
soybean
630
42
65.1.77
>300
6.1.22
anneal
812
44
42-1.6
<
>300
5.0.2
70
45
12+:0.6
<
>300
440.2
yeast
1484
46
240
<
>300
16400.4
lymph
148
16348.1
<
>300
8=:0.5
vote
435
48
>300
<
>300
910.1
HTRU2
17898
57
>300
440.1
>300
111
biodeg
1055
81
>300
4+0.1
>300
194+6.9
haberman 306
>300
2+0.11
>300
147+4.3
Geometric mean improvement
95.29
32.90
Table 12:
Runtime (s) of both methods for Rashomon set computation with trivial extensions ignored, across datasets and depth budgets, for 0.01 and n² 10" {1,...,6). Results reported as mean + standard error.
d=4
d=
Dataset [D]
FF
TreeFARMS SORTD
TreeFARMS
SORTD
breast monk2
699
10
<1
<1
<1 3+0.1
169
11
<1
<1
diabetes
768
11
<1
<1
<1
34

---

d= 4
d=
Dataset
[D]
TreeFARMS SORTD
TreeFARMS
SORTD
compas
6907
12
<1
<
1+0.2
<1
bar-7
1913
14
<1
<
1+0.1
<1
car
1728
15
120.1
<1
710.2
<1
expensive
1417
15
1:0.0
<1
710.1
cheap
2653
15
140.1
<1
440.4
<1
monk1
124
15
2+0.2
<
1412.6
monk3
122
15
320.3
<
5415.1
<
coffee
3816
15
140.0
<
610.2
banknote
1372
16
<1
<
<1
<]
tumor
336
2+0.11
18+0.3
fico
10459
17
640.3
<
43+1.
2+02
tic-tac-toe
958
18
2+0.0
22+0..4
spect
267
22
38.1.55
<I
>300
<1
bank
4521
23
10:0.6
<
75:17.6
240.2
messidor
1151
24
641.33
<
384:2.1
<1
hepatitis
137
34
134+3.0
<1
>300
140.1
kr-vs-kp
3196
38
7043.1
<1
>300
1040.4
hypothyroid
3247
39
3745.3
<1
1381
6:1.66
soybean
630
42
8042.2
<
>300
510.2
anneal
812
44
47+2.6
<
>300
5+0.2
mouse
70
45
15+0.8
<
>300
5+0.2
yeast
1484
46
23445.6
140.1
>300
13:0..5
lymph
148
47
>300
<1
>300
6.L0.2
Vote
435
48
>300
<1
>300
7+0.5
HTRU2
17898
57
25.6
644.44
227+25.2
126:16.7
biodeg
1055
81
>300
440.2
>300
984
haberman 306
92
>300
310.2
>300
12242.1
Geometric mean improvement
70.30
29.77
Runtime (s) of both methods for Rashomon set computation with trivial extensions ignored, across datasets and depth budgets, for 0.1 and n² 10", {1, f1....,6) ,6. Results reported as mean - standard error. indicates runs omitted due to excessive memory usage.
Table 13:
d=4
d=
Dataset
DD
[F]
TreeFARMS SORTD
TreeFARMS SORTD
breast
699
10
<1
<1
<1
<1
monk2
169
11
2+0.4
<1
diabetes
768
11
<1
<1
<1
<1
compas
6907
<1
1+0.2
<|
bar-7
1913
14
<1
<1
140.3
<1
car
1728
15
1=0.22
<1
440.9
<
expensive
1417
15
<1
<1
240.7
<
cheap
2653
15
<1
2+05
<
monk1
124
15
24.033
17439
<|
monk3
122
15
240.5
<1
24+6.7
<
coffee
3816
15
140.2
3+07
<l
banknote
1372
16
<1
<1
<1
<l
tumor
336
17
140.2
411.4
<
fico
10459
17
410.8
<
9126
2403
tic-tac-toe
958
18
240.3
6t1.66
<|
spect
267
22
1743.1
90125.55
<1
bank
4521
23
411.0
8+2.4
2+0.3
messidor
1151
24
2+0.7
4+1.2
140.2
35

---

d=4
d d=
Dataset
[]]
[F]
TreeFARMS
SORTD
TreeFARMS
SORTD
hepatitis
137
34
34=10.0
<1
41:13.0
2+0.3
kr-vs-kp
3196
38
53:7.9
<1
178#28.2
540.8
hypothyroid
3247
39
21
<1
38213.77
610.9
soybean
630
42
3148.9
42:12211
540.8
anneal
812
44
1143.44
<1
16415.3
340.5
mouse
70
45
21:6.3
110
1
yeast
1484
46
114=16.0
140.2
185=24.7
10
lymph
148
47
112=25.0
12242668
410.7
vote
435
48
64=24.1
<1
67424.7
511.
HTRU2
17898
57
49-13.5
5+0.7
70+222.0
50+9..
biodeg
1055
81
177=26.9
6+0.88
haberman
306
92
259-21.4
2+0.3
276
22+33.7
Geometric mean improvement
28.30
11.71
B.7 Variable importance analysis
evaluated using the leave one feature procedure (50) with À = 0.01, depth = 4. For each dataset, we generated 20 stratified bootstrap samples, computed the Rashomon multiplier required to obtain at least 10,000 trees, and constructed the corresponding set using these multipliers. For each bootstrap sample, we also calculated the top-1 and top-100 Rashomon sets and ranked features according the increase in area under the tree-index versus objective-value curve when each feature was removed. Kendall's r and Jaccard index were used to evaluate the stability of the full and top-5 variable ranking, respectively. Table presents the results.
Variable importance Rashomon
Table 14: Variable importance similarity compared to LOFO based on n² = 104.
Kendall's
Jaccard Index
Dataset
n² =1
n²
100
n²
100
diabetes
0.71
0.89
1.0
1.0
anneal
0.02
0.59
0.8
1.0
bank
-0.22
0.64
0.4
1.0
banknote
0.68
0.93
1.0
1.0
bar-7
0.56
0.78
1.0
1.0
breast
0.69
0.91
0.6
1.0
car
0.70
0.83
0.8
0.8
cheap
0.47
0.83
0.8
1.0
coffee
0.73
0.81
1.0
1.0
compas
0.42
0.88
0.6
0.8
expensive
0.79
0.79
0.8
0.6
fico
0.13
0.79
0.4
0.8
haberman
0.25
0.46
0.4
0.8
hepatitis
0.43
0.62
0.2
0.4
HTRU2
0.12
0.21
0.6
1.0
hypothyroid
0.11
0.42
0.4
0.8
kr-vs-kp
0.39
0.49
0.8
0.8
lymph
0.50
0.72
0.8
0.8
messidor
0.60
0.80
0.8
1.0
monk1
0.66
0.66
0.6
0.8
monk2
0.75
0.75
1.0
0.8
monk3
0.68
0.64
1.0
1.0
mouse
0.34
0.51
1.0
0.8
tumor
0.57
0.85
0.8
1.0
soybean
0.26
0.79
0.8
1.0
36

---

Kendall's
Jaccard Index
Dataset
n² =
n"
100
n
T
n²
100
spect
0.58
0.74
0.8
0.6
tic-tac-toe
0.61
0.67
1.0
1.0
vote
0.06
0.69
0.2
0.8
yeast
0.38
0.74
0.8
0.8
The stability of the top-1 tree versus the top-10,000 trees is low for most datasets with only five of them satisfying 0.7, and 19 of them have Jaccard index of value at least 0.8. In contrast, for the top-100 versus 10,100000 trees, 17 datasets satisfy 2 0.7 and 26 exceed a Jaccard index exceeding 0.8, indicating that smaller Rashomon sets can yield similar variable importance values larger Rashomon sets.
B.8 Regression results
This section provides the details the regression experiment shown in Fig. 7 and additionally analyses the runtime performance of SORTD for regression.
Data For the regression experiments, their binarization of non-binary features Learning repository [55]. For all datasets, we normalize the regression label by subtracting the mean and dividing by the standard deviation.
the datasets from Zhang et al. [47 and also follow The datasets can also be obtained from the UCI Machine
Fl
Comparison with CART and STreeD Since there are, the best of our knowledge, no previous methods to enumerate the whole Rashomon set of regression trees, we follow the set-up by Xin al. [30], who did similar experiment for classification trees: compare SORTD with both the heuristic CART [2) and the optimal method STTreeD [40] when those are called repeatedly on random samples of the data. STreel is state-of-the-ar optimal method for computing optimal regression
trees 58
In this experiment, we impose 60 seconds timeout for each method. CART and STreeD are repeatedly within that time budget on random samples of 50% of the total dataset. All resulting unique trees are kept. SORTD, the other hand, is set in order until time-out or until the Rashomon set exhausted. We use the Rashomon multiplier 0.1, complexity cost À 0.001, and maximum depth 4.
and collects trees in the Rashomon
Fig. 7 in the main text shows how SORTD can find orders of magnitude more trees in the Rashomon set than either CART or STreeD within the time limit. For the Synchronous Machine Dataset, SORTD finds the whole Rashomon set within two seconds, whereas both STreeD and CART find only a fraction in the allotted 60 seconds. For both Airfoil Self-Noise and Seoul Bike Sharing Demand, SORTD finds orders of magnitude more trees than either CART or STreeD the given time limit, These results confirm what Xin et al. (30] also concluded for classification: enumerating the whole Rashomon set can be done best with a dedicated method.
Runtime Additionally, analyse the runtime performance of SORTD to calculate the Rashomon set regression trees. Here, we set the complexity cost À 0.01, the Rashomon multiplier to 1.0, the maximum number of trees nT = 10 and we test both with maximum depth of four and five. We run all experiments five times on all datasets with a time-out of 300 seconds.
Table 15 shows that SORTD successfully enumerates the top one million trees for all benchmark datasets within the time limit for d = 4, except for one, and for all but three for d = 5.
In comparison to the experiments on classification trees shown above in Appendix B.2) the regression tree Rashomon set more time intensive compute. We think this is because the regression loss allows for many more unique loss values. Since SORTD combines solutions with the same value (see Appendix A.2), more unique loss values result in a higher runtime. Runtime performance can
httpp///gtthhooccmm//mmmuaaagggg tree- benchmark
37

---

Table 15: SORTD runtime (s) performance methods to calculate Rashomon sets for regression trees across datasets with À = 0.01 and n = 10 Results are reported as mean + standard error.
Dataset
DD
IF
d=
d 5
Airfoil Self-Noise
1503
17
2 = 0.1
Air Quality
111
16
2
9
Energy Efficiency (Cooling)
768
27
80
> >00
Energy Efficiency (Heating)
768
27
94 9.434
>00
Household
2049280
53
134
+34
Medical Cost Personal
1338
16
=
12
Optical Interconnection Network
640
29
<1
13
Real Estate Valuation
414
18
130
18
Seoul Bike Sharing Demand
8760
32
>00
>00
Servo
167
15
2
4.2
Synchronous Machine
557
<1
<1
Yacht Hydrodynamics
308
35
1.5
157 4.9
likely be improved by setting a higher tolerance for which solution values are considered the 'same". Currently, SORTD uses tolerance of 10-4
B.9
oqppotttyof results
This section provides the details on the equality-of-oppont opportuuitty experiment shown in Fig. B and additionally analyses the runtime performance of SORTD for evaluating such second objective.
Data For the -fpport-off experiments,
the datasets from Le Quy et al. [48] and follow their suggested binarization of non-binary features. In Table [6] we report which feature is selected as the discrimination sensitive feature. References the original datasets can be found here
[1 55 63
Pareto front Fig. shows how SORTD can be used to generate a Rashomon set for sparse classification trees, which are then evaluated using secondary objective: equality of opportunity. Since SORTD generates the solutions increasing order of its objective, examines the most accurate trees first. Therefore, when halting the search any time, (partial) Pareto front over the primary and secondary objectives can be computed. The results in Fig. 8 show that among the top 107 sparse depth-four classification i.e., the true positive rate of one group is at least 2% higher than another. For the Bank Marketing dataset, tree with zero discrimination found among the top 107 trees. For the Compas dataset the most fair dataset in the top 10" trees still has 2.5% discrimination. It also shows that by reducing accuracy by only 0.5%, the discrimination score can be lowered from 7% to 2.5%.
for the Adult dataset, all trees have least 2% discrimination,
Runtime comparison We evaluate SORTD's efficiency in evaluating second objective such as equality of opportunity by comparing it with the optimal dynamic programming approach STreeD (40), which supports optimizing accuracy and equality of opportunity. We do compare with the mixed- integer programming approach by Jo et al. (64) since Linden et al. [40] report runtimes several orders of magnitude lower than theirs, while computing the same optimal solutions.
We run SORTD by iteratively generating the next best n²" trees according to the regularized accuracy objective. We then evaluate the newly generated trees as described in Appendix A.9 using the metric. a tree is found within the pre-set discrimination limit 8, we stop. Otherwise, SORTD generates the next batch of n² trees and repeats. Since SORTD yields trees in order of the regularized accuracy objective, the first tree finds within the discrimination limit must be optimal with respect the regularized accuracy objective.
In the comparison with STreeD, there are couple of small differences that may influence runtime: (1) We run SORTD using the regularized accuracy objective, each leaf node is penalized with
38

---

the sparsity penalty A. In this experiment, we set À = 0.01. STreeD's optimization task by default does not consider such regularization. (2) STreeD also considers non- majority labels in leaf nodes, whereas SORTD by default does not. Because of these two differences, STreeD and SORTD are not guaranteed to find the same optimal solution, although we verified that the solutions are close. Since our main aim in this experiment is to validate that SORTD can successfully be used to post-evaluate secondary objective, we consider these differences acceptable.
Table 16: Runtime (s) performance to compute an optimal fair tree with at most 1% discrimination, and maximum depth d averaged over five runs. For SORTD, we X 0.01 and iteratively evaluate 10 trees. Results are reported as mcan + standard error. Best results are bold.
Dataset
Sensitive feature
|D|
[F]
STreeD
SORTD
Adult
Gender
45222
18
0.0
1 0.0
Bank marketing Communities & crime
Married
45211
47
=
0.1
7 7 0.0
Race
1994
98
6
0.0
21 0.1
Compas recid. Compas viol. recid.
Race
6172
10
<1
<1
Race
4020
10
<1
0.0
Diabetes
Race
45715
129
36 -
0.0
58 1.2.
Dutch census
Gender
60420
9
0.0
79 0.5
German credit
Gender
1000
70
32 = 0.2
3
KDD census income
Race
284556
118
0.1
134 0.6
Lawschool
Race
20798
20
<1
4 0.0
OULAD
Gender
21562
17 0.2
+ 0.0
Ricci
Race
118
5
<1
<1
Student Portuguese
Gender
649
1 0.0
0.0
Student mathematics
Gender
395
56
<1
6 0.0
Table 16 shows the mean runtime performance of STreeD and SORTD find fair and optimal trees with max-depth d = 3, discrimination limit 6 1%, and sparsity penalty À = 0.01 (for SORTD). With SORTD,, iteratively produce and evaluate n 10 trees until tree within the discrimination limit is found, or until the time-out of 300 seconds. The results show that SORTD remains close in performance to STreeD, and for some datasets, such German credit and OULAD, even performs significantly better. These results are obtained by evaluating the secondary objective using callbacks to Python. Hence, if runtime performance was the main concern, these results could be further improved by computing this also in C++.
Concluding, these results show that using Rashomon sets optimize (totally ordered) objective, and later evaluating the Rashomon set (possibly iteratively) using second objective (such that this multi-objective optimization task is only partially ordered) is promising.
39


Reviews:
[{"review_id": "tjseN0picM", "reviewer": "Reviewer_TncC", "summary": "Rashomon sets of sparse decision trees are useful for downstream data analysis, such as variable importance analysis. However, getting the entire Rashomon set might be too time-consuming. To circumvent this difficulty, the authors propose to only get the top-$n$ sparse trees, using a best-first search approach so that the algorithm can exit early. To further improve the computational efficiency, the authors apply the depth-two subroutine, which has already been explored in previous works. Experimental results show that the proposed method, SORTeD, can run significantly faster than the SOTA TreeFARMS method.", "questions": "1. Can you confirm whether my understanding (alternating between popping and exploring) is correct?\n2. Can you perform an ablation study by only using best-first search but NOT using depth-two routine? How does this compare with SORTeD in terms of running time?\n3. The time limit (300) is too small in my opinion. The idea of collecting the Rashomon set is to spend some time collecting the entire set. We only do this once and save all the trees. Afterwards, we can explore the entire space instantaneously by making queries in this Rashomon set space. In this sense, it is fine if practitioners can spend some time waiting for collection process to finish. Could you increase the running time (300-> 3600) and do the time comparison again? I am interested in seeing whether TreeFAMRS can at least do a descent job (by finish collecting all the trees in the Rashomon set or the top-$n$ trees) if practitioners are willing to wait.\n4. For variable importance analysis, it's unclear to me whether using the top-$n$ trees and all trees in the Rashomon set provide the same results. Can you elaborate on this? Can top-$n$ trees provide the same quantitative and qualitative variable importance analysis? Under what circumstances? Can we get any theories in this direction? If these two approaches give different variable importance analysis results, then it's unclear what benefit we get by obtaining only the top-$n$ trees. This is actually an important question. If getting the top-$n$ trees is not enough, then it undermines the motivation of this work.\n5. Unlike Figure 3, Figure 4 only contain solid lines. What happens when $n=10^4$ and $n=10^6$ for Figure 4?", "limitations": "There isn't a specific paragraph discussing the limitations in the main paper. However, such a discussion is included in one of the checklist answers.", "rating": 4, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 3, "originality": 2, "strengths_and_weaknesses": "**Strength**\n\n1. The writing for the introduction paragraph is pretty strong. The language is both concise and comprehensive.\n2. Clear run-time improvement over the baseline TreeFARMS.\n3. The main contribution is an engineering effort in C++ programming to make the whole program work for best-first search on the task of collecting the Rashomon set. Conceptually, the contribution is fair (See my #5 below for the weaknesses)\n\n**Weakness**\n\n3. The writing for the methodology section (Section 4) is a little bit too complicated in my opinion. I spent several hours without understanding in details of what is going on. The central idea is simple. The first phase is popping. We keep popping out the best solution in the queue. If we cannot certify the solutions in the queue are the best, we should switch to the second phase --- exploring (to certify optimality in the remaining search space). We alternate between the popping phase and exploration phase until we reach the Rashomon set limit. I suggest the authors give this big picture at the beginning of Section 4.\n\n4. To continue on this thread, I suggest the authors highlight/boldface this sentence \"If the child search node does not have that solution yet, it is obtained by calling GetNextSolution (Alg. 1).\" I believe this is the key step for understanding the big picture. We need to alternate between popping and further exploration.\n\n5. Conceptually, there aren't any big surprising innovations. Best-first search is one of the standard searching methods. Depth-two subroutine has already been proposed in previous works.\n\n6. This is a minor comment. In some sense, the substantial time-improvement isn't that too surprising. Firstly, the goals of SORTeD and TreeFARMS are different. SORTeD only care about the top-$n$ trees in the Rashomon set, while TreeFARMS want to collect ALL the trees in the Rashomon set. Secondly, SORTeD use the depth-two subroutine, which I believe play a big part in the time improvement. It is worthwhile to conduct some ablation study to see how much an impact this depth-two subroutine play by turning it off and just having the best-first search framework.", "was_revised": true, "final_justification": "In summary, I think the key contribution of this paper is proposing to incorporate the depth-two solver into the branch and bound framework to make the overall BnB run fast. We can regard this as a new heuristic technique in finding good solutions when the tree depth is small. TreeFARMS didn't spend much time in designing good heuristics and its past series of papers focus more on deriving the lower bounds for pruning purposes. It's intuitively understandable now why the author claims their work is a step further than TreeFARMS.", "rebuttal": "We would like to thank the reviewer for the positive comments. We reply to the questions below:\n\n**Q1:** *\"Can you confirm whether my understanding (alternating between popping and exploring) is correct?\"*\n\nIt is correct that popping and exploring procedures are alternatingly called.  However, the solutions that are inserted into the sorted solution lists are guaranteed to be the best. Popping continues until all solutions in the sorted solution list are used and the next one is requested.  In that case, exploration (GetNextSolution function call) begins. \n\n**W3 \\& W4:**  *\"The writing for the methodology section (Section 4) is a little bit too complicated...I suggest the authors give this big picture at the beginning of Section 4.\"*\n\nThank you for your suggestions. We will provide the big picture both for the search node and for the helper nodes so that it is easier to understand their roles and how these roles are linked to each other. \n\nWe will additionally highlight the sentence *\"If the child search node does not have that solution yet, it is obtained by calling GetNextSolution (Alg. 1)\"*.\n\n**W5:** *\"Conceptually, there aren't any big surprising innovations. Best-first search is one of the standard searching methods...\"* \n\nDue to the following reasons, we consider our methodology to be innovative: \n\n+ Although best-first search is a well-known method, to the best of our knowledge, our application of BFS in an and/or-search graph that yields lists of solutions by computing a Cartesian sum of (yet incomplete) subproblem solution lists is novel (see lines 155-157). \n+ We contribute a new gradual solution creation technique for the depth-two solver (Appendix A.7) to improve its anytime performance.  \n+ Unlike previous work, SORTD can compute and evaluate Rashomon sets across a range of tasks, including classification and regression objectives. \n \n**Q2 & W6b:** *\"Can you perform an ablation study by only using best-first search but NOT using depth-two routine?...\", \"...SORTeD use the depth-two subroutine, which I believe play a big part in the time improvement...\"*\n\nThe scalability advantage is mostly obtained through the depth-two solver. Our specific contribution in this component is the use of a gradual solution creation technique (Appendix A.7), which improves its anytime performance. The novel search technique does not contribute to SORTD’s runtime but provides an anytime behavior, which we believe is essential to parse larger datasets, specifically, if good Rashomon bounds cannot be guessed beforehand.\n\n**W6a:** *\"...In some sense, the substantial time-improvement isn't that too surprising. Firstly, the goals of SORTeD and TreeFARMS are different...\"*\n\n+ Our approach solves the same problem as TreeFARMS, i.e., given some bound, return the whole Rashomon set. Our approach supports setting this bound in the same way TreeFARMS does: by some relative performance to the optimal solution (implied by the Rashomon multiplier epsilon). In addition, we also support setting the bound by fixing the size of the Rashomon set. \n+ We ensure a fair comparison by running TreeFARMS with precise epsilon input such that it outputs the same number of trees as SORTD. Under this fair comparison, SORTD has a substantial runtime improvement over TreeFARMS. \n\n\n**Q3:** *\"The time limit (300) is too small...\"* \n\nOur approach is two orders of magnitude faster and offers anytime behavior, as shown in Fig. 3 and Tables 2–4.  In practice, this allows SORTD to be used for exploring larger datasets within a similar time limit. While we could extend the time limit, the benefit of doing so is unclear to us.\n\n**Q4** *\"For variable importance analysis, it's unclear to me whether using the top- trees and all trees in the Rashomon set provide the same results... If getting the top- trees is not enough, then it undermines the motivation of this work.\"*\n\nWe want to correct the misunderstanding that the difference is between evaluating the top-n trees and all trees in the Rashomon set. Instead, the difference is how the Rashomon set is defined: by its size (top-n) or by some Rashomon multiplier epsilon.The purpose of our experiment in Section 5.2 and B.4 is to show the variable importance measured is relatively stable for 100 or 10,000 trees. Developing theories on the necessary number of trees, rather than the bound, to get stable measurements of variable importance is an interesting future work. \n \nBeyond facilitating variable importance analysis, the sorted Rashomon set also aids the model selection process by generating trees in order while requiring less runtime. \n\n**Q5:** *\"Unlike Figure 3, Figure 4 only contain solid lines. What happens when  and  for Figure 4?\"*\n\nIn Figure 4, we show the cumulative runtime distribution across datasets with $n^T = 10^6$ and maximum depth 4. We will make this clear in the figure caption and explanation.  The figure shows that as the number of features increases, the proportion of problem instances for which the Rashomon set calculation finishes within the time limit decreases. This effect is notably more pronounced for TreeFARMS compared to SORTD.\n\n**Limitations:** *\"There isn't a specific paragraph discussing the limitations in the main paper. However, such a discussion is included in one of the checklist answers.\"*\n\nThat is a good point, we will provide the limitations in the main paper."}, {"review_id": "SdqGXNbm0z", "reviewer": "Reviewer_miaQ", "summary": "The authors propose a scalable algorithm “SORTD” for enumerating the Rashomon set of sparse decision trees. (The Rashomon set is the set of models that are near-optimal, e.g., whose accuracy is within epsilon of the optimal model accuracy.) The authors build on TreeFarms, prior work that uses dynamic programming and specialized data structures to enumerate the Rashomon set of sparse trees. The distinguishing features of SORTD are that it is more scalable and it finds trees in best-to-worst order. Since trees are enumerated best-to-worst, there is “anytime” functionality (i.e., computations that only require part of the Rashomon set can be completed more quickly) and it is not necessary to know the Rashomon parameter epsilon a-priori.", "questions": "- The number of features correlates with runtime (Fig. 4) but looking at Table 2 in the appendix, it doesn’t totally explain the variance between datasets (nor does dataset size). Are there other dataset properties, e.g., separability or maximal accuracy, that can help explain runtime variations?\n- Section 5.2 (Variable Importance Analysis) for top-5 feature stability using Jaccard and Kendall’s T, how much worse are these metrics if we use a random selection of 100 or 10000 Rashomon set members (e.g., terminating TreeFarms once the specified number of models have been sampled)? I.e., how beneficial is having the most-performant Rashomon set members for variable importance analysis on a subset of the Rashomon set?\n- Any workarounds for memory constraints? (Ok if this is for future work, but what general directions are promising?)", "limitations": "Mostly — see comments about scaling and memory concerns", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 3, "originality": 2, "strengths_and_weaknesses": "###Strengths\n* Potential for high impact, because the code is available as a python package and this paper improves on the scalability bottleneck of existing methods for Rashomon set enumeration. \n* The experiments are comprehensive \n* As described in section 5.3 (regression trees and fairness metrics), the  approach can be used for real-world important tasks \n\n\n###Weaknesses\n* Inherent limitations to the approach include that it is limited to sparse decisions trees and it has high memory requirements. I think the high memory requirements is of particular concern because it would limit how widely this approach can be used. \n* Minor: is there a typo in Fig 2? (Swap lindex and rindex in “next” and “candidates queue”)", "was_revised": true, "final_justification": "It's a well written paper that provides a solid technical contribution with potential for high impact for practitioners and researchers. The rebuttal addressed all my concerns.", "rebuttal": "We would like to thank the reviewer for the positive comments. We reply to the questions below:\n\n**W1 & Q3:**  *\"...I think the high memory requirements is of particular concern because it would limit how widely this approach can be used...\"*,  *\"Any workarounds for memory constraints?...\"*\n\nThe high memory requirements only occurred during the experiment preparation phase for precomputing the Rashomon multiplier epsilon values that were required for a fair comparison with TreeFARMS (but SORTD itself does not require them). We will clarify this in the text.The actual comparison between TreeFARMS and SORTD records no exceeded memory limits. In fact, we observe approximately 5-7 times less memory usage by our approach than TreeFARMS, and on average over all instances, SORTD uses less than 1GB of memory. We will add these results to the appendix. \n\nThe memory requirements could potentially be further decreased by\n\n+ Wiping the cache (partly) at least for the suboptimal solutions that are never used in the Rashomon set [1], which could additionally contribute to the runtime performance,  \n+ Gradually increasing the Rashomon multiplier until a certain set size is obtained, \n+ Keeping track of fewer statistics, or only those we are interested in because our experiments were run while SORTeD was using various data structures to calculate statistics such as “number of trees with feature f”. \n\n**Q1:** *\"...Are there other dataset properties, e.g., separability or maximal accuracy, that can help explain runtime variations?\"*\n\nOther dataset properties that help explain runtime variations are (i) separability, (ii) maximal accuracy, (iii) equivalent feature vectors, (iv) feature vector sparsity, (v) feature similarity, among others. For example, if a 100% accurate tree exists for a given depth limit, the phase 1 (identifying the optimal tree and setting the Rashomon bound) search can terminate early. If not, much more time is spent proving that the current best tree is indeed optimal. \n\n**Q2:** *\"(Variable Importance Analysis)...how much worse are these metrics if we use a random selection of 100 or 10000 Rashomon set members (e.g., terminating TreeFarms once the specified number of models have been sampled)?...\"*\n\nA randomly selected set of trees might provide more stable variable importance estimates than a single tree; however, the runtime efficiency of SORTD remains essential for solving such difficult instances. In our experiments, we observed that TreeFARMS failed to find optimal solutions for some problem instances when the dataset had high dimensionality and the cost-complexity parameter $\\lambda$ was low (e.g., the Haberman dataset with $\\lambda=0.001$).  \n\n\n**W2:** *\"Minor: is there a typo in Fig 2? (Swap lindex and rindex in “next” and “candidates queue”)\"*\n\nYes, we will correct it, thank you. \n\n\n[1] Aglin, G., Nijssen, S., & Schaus, P. (2023). Learning optimal decision trees under memory constraints. In I. Ntoutsi, C. Tintarev, G. Vretos, A. S. Verebes, & D. Frossard (Eds.), Machine Learning and Knowledge Discovery in Databases. ECML PKDD 2023. Lecture Notes in Computer Science (Vol. 14139, pp. 393–409). Cham: Springer."}, {"review_id": "T9f3rxJpR4", "reviewer": "Reviewer_2J8x", "summary": "The authors extend the STreeD decision tree optimization framework to support objective-value-ordered Rashomon set enumeration. The approach yields more than an order of magnitude improvement in runtime relative to state-of-the-art TreeFARMS, and allows extension of Rashomon sets to additive objectives with total orderings (significantly, giving us the first full Rashomon set enumeration algorithm for regression trees). The appendix details an additional benefit: the approach can compute other separable, partially ordered objectives while enumerating the Rashomon set, saving some computation time relative to computing those objectives afterwards.", "questions": "- Could you please expand a bit on the benefit of the depth 2 solver? My understanding from MurTree is that asymptotically this solver is quite similar to a standard brute force search unless the binarization system is particularly sparse. (i.e. if each feature has ½ of its values true and the other half false, the runtime improvement is just a factor of 4). Since this work uses a sparsity term, lambda, there’s some limit on how sparse each reasonable feature is (since there’s no reason to consider features that have fewer than 2/lambda values true for binary classification). Clearly there’s a benefit to this approach relative to TreeFARMs, but it seems like it’s not an asymptotic improvement (and indeed, it’s sort of hard for me to tell from figure 3 that the scaling with depth is better than a constant factor improved, albeit an impressive constant factor).\n\n\n- How are you measuring partial progress in treefarms (i.e. how quickly each individual tree is generated), particularly when it times out? I’ve always run treefarms to completion before analyzing the set, and I’m not sure how to think about partial output from the algorithm (i.e. all the results for depth 5). It’s not clear to me from glancing at the experiment code for the treefarms comparison how intermediate results were collected, so a response here would be appreciated as it would save me some digging.", "limitations": "I'd be interested in seeing the results in 5.2 relative to a true Rashomon set, rather than the set of top 10,000 models. This is at most a minor limitation, though.", "rating": 6, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 4, "clarity": 4, "significance": 3, "originality": 2, "strengths_and_weaknesses": "Strengths: \n\n-\tA flexible framework for Rashomon sets across many additive objectives, including regression\n-\tSubstantial runtime improvements\n-\tGiving the Rashomon set in sorted order, right away, makes finding the Rashomon set across a range of choices of epsilon more convenient. \n-\tI think the way of enumerating the set in objective order is quite clever, and of interest in general. \n\nWeaknesses: \n\n-\tThe prior state of the art allows random sampling from the Rashomon set, which I believe this approach does not\n-\tWhile this work is correct that TreeFARMS does not preserve objective ordering, my understanding is that this work is incorrect in stating there is no ordering at all to TreeFARMS trees. TreeFARMS trees are structured in relation to the splits used, allowing users to traverse the Rashomon set by split structures as in TimberTrek [1], rather than by objective ordering (when all trees in the Rashomon set are already near-equivalent in objective value). \n\nMinor Weaknesses: \n\n-\tWhile some applications clearly benefit from sorting the Rashomon set, not all do: the point of the Rashomon set for reasonable epsilon is that all models within it differ only trivially, so their relative ordering is not deeply significant. Giving a total ordering can imply meaningful differences among models that are, in practice, interchangeable.\n-\tWith the prior state-of-the-art, it was not particularly complicated to get a top-k set of trees, or the sorted ordering, from TreeFARMS when the full set is of the size this  paper defines as reasonable (10^6 or less). The sorting can be done as post-processing in reasonable time.\n-\tThe top 100 model approach for variable importance (section 5.2) shows some similarity to the conclusions with the top 10,000, but with limitations: a high jaccard similarity for 20 out of 29 datasets is better than the result for a single model, but still only just above 2/3 of datasets. (As a minor note - the top 100 threshold approach used here seems like it forces breaking ties arbitrarily, relative to just using a Rashomon set with a small epsilon) \n\n[1] Wang, Zijie J., et al. \"Timbertrek: Exploring and curating sparse decision trees with interactive visualization.\" 2022 IEEE Visualization and Visual Analytics (VIS). IEEE, 2022.", "was_revised": true, "final_justification": "The authors have convincingly addressed my concerns in discussion. I'll highlight again the strengths I mentioned this work demonstrates: \n\n-\tA flexible framework for Rashomon sets across many additive objectives, including regression\n-\tSubstantial runtime improvements\n-\tGiving the Rashomon set in sorted order, right away, makes finding the Rashomon set across a range of choices of epsilon more convenient. \n-\tI think the way of enumerating the set in objective order is quite clever, and of interest in general. \n\nIn my opinion, improving the accessibility and flexibility of a Rashomon framework for trees is a substantial contribution to the field, enough to warrant a 6. While the authors and I have a difference of opinion about how important enumerating the set in sorted order is, we certainly agree that it's a useful improvement.", "rebuttal": "We would like to thank the reviewer for the positive comments. We reply to the questions below:\n\n**Q1:** *\"Could you please expand a bit on the benefit of the depth 2 solver?... \"*\n\nThe depth-two solver improves the scalability by order of magnitude in practice. The reviewer is right to observe that there is indeed no asymptotic improvement in the worst case (50% sparsity) even though the constant improvement is significant (the improvements are a function of the sparsity). Other important elements of the depth-two solver are that it re-uses the previous counts if two consecutive datasets are similar, and that it provides a strong reduction in cache entries (which contributes to a smaller memory footprint). \n\n**Q2:** *\"How are you measuring partial progress in treefarms... \"*\n\nWe clarify that we did not evaluate the partial progress of TreeFARMS. Instead, we either waited for TreeFARMS to compute the entire Rashomon set or for it to reach the time limit and then reported the runtime. If this question refers to Figure 3, the distribution shown in the figure represents the percentage of problem instances (dataset x lambda) for which the full Rashomon set was found within the time limit, not the percentage of trees generated (we will improve the figure caption). \n\n**W1:** *\"The prior state of the art allows random sampling from the Rashomon set, which I believe this approach does not\"*\n\nSORTD also supports sampling. The Python interface of SORTD includes the function get_tree_n(index), which allows retrieval of a tree by its index and thus enables flexible sampling. Given SORTD’s runtime efficiency, sampling after generating the full Rashomon set can still result in a faster sampled subset compared to TreeFARMS. \n\n**W2:** *\"While this work is correct that TreeFARMS does not preserve objective ordering, my understanding is that this work is incorrect in stating there is no ordering at all to TreeFARMS trees...\"*\n\nIn the paper we were referring to the objective ordering, we will make it clear in the paper.  \n\n**MW1:** *\"...Rashomon set for reasonable epsilon is that all models within it differ only trivially, so their relative ordering is not deeply significant...\"*\n\n We agree that a Rashomon set with a reasonable epsilon is valuable, but the drawback is that it requires guessing the correct epsilon. Our goal is to remove this requirement. For example, in our experiments, sometimes epsilon=10% contains only the optimal solution, and sometimes it contains millions of trees (see Table 5 and the Rashomon multipliers discussion on page 29). By asking for the top-n trees, we get more stable performance, and the anytime behavior is valuable, e.g., within a few minutes we can already get results without needing to wait for the entire Rashomon set given an epsilon. We will make this clearer in the paper. \n\n\n**MW2:** *\"With the prior state-of-the-art, it was not particularly complicated to get a top-k set of trees, or the sorted ordering...The sorting can be done as post-processing in reasonable time\"*\n\nThat is correct, it is not complicated, but it requires guessing the correct Rashomon multiplier value and then waiting for TreeFARMS to terminate. In addition, our approach SORTD does not require epsilon, and we also compute the Rashomon set orders of magnitude faster whilst providing anytime behavior (allowing different objectives), see Figure 3 and Tables 2-4. We will include this discussion in the paper in a dedicated subsection (or Appendix). \n\n\n**MW2:** *\"The top 100 model approach for variable importance (section 5.2) shows some similarity to the conclusions with the top 10,000, but with limitations...\"*\n\nThe purpose of our experiment in Section 5.2 and B.4 is to show that it is useful to use a small number of trees to gain insight, not necessarily to prove the true variable importance (more trees is always better in that regard). For a very large dataset such as Haberman or Biodeg, this is particularly valuable. \n\n**Limitations:** *\"I'd be interested in seeing the results in 5.2 relative to a true Rashomon set...\"*\n\nIf we understand the ‘true’ Rashomon set as a set defined by a Rashomon multiplier epsilon, we may observe that by selecting top 10k trees, we also implicitly select an epsilon (the epsilon is defined by the last tree found). In this sense, the experiment in Section 5.2 is what reviewer is asking for. We will clarify this in the paper."}, {"review_id": "YDvppQjoeY", "reviewer": "Reviewer_v9wz", "summary": "This paper introduces SORTD, a method to generate Rashomon Sets of sparse decision tree models.\n\nThe proposed algorithm uses dynamic programming with bounds, caching, and specialized subroutines to efficiently represent and explore the space of sparse decision trees in order of ascending (best first) objective function. Because it generates all sparse decision trees in the Rashomon set in ascending order of their objective function, SORTD provides anytime guarantees and does not require pre-fixing the Rashomon parameter $\\epsilon$ -- which are two important advances compared to the state-of-the-art. \n\nAn efficient procedure is also provided to compute partially ordered objectives in a post-hoc manner all over the Rashomon set, without having to explicitly compute it from scratch for each tree.\n\nThorough experiments confirm the efficiency of the proposed algorithm to generate Rashomon sets for any totally ordered objective and to evaluate them efficiently with respect to additional (partially ordered) desiderata (here, the equal opportunity statistical fairness metric).", "questions": "Q1/ \"Our analysis indicates that this scalability stems from a compensating effect in SORTD’s search: although more features increase the number of branching nodes per search node, they also shorten the sorted solution lists each search node maintains.\" (line 243) -> This sentence is a bit unclear to me. Could you please clarify how increasing the number of features (so basically the number of split possibilities) can actually shorten the solution lists ?\n\nQ2/ SORTD uses specialized subroutine for trees containing 1, 2 or 3 branching nodes, that are said to \"reduce runtime and improve\nscalability with both the number of features and the depth budget\". Did you perform ablation experiments to precisely quantify the speedup provided by using (or not) these subroutines ?\n\nQ3/ The fact that SORTD generates sparse decision trees within the Rashomon set in ascending order of their objective function is an important advantage as it provides nice anytime behaviour. Nevertheless, technically speaking, even though they are not generated, suboptimal solutions still need to be explored (e.g., in Figure 2, how to be sure that other splits are not better without verifying them ?). I guess this is done implicitly when calling STreeD to generate the optimal solution values of the left and right child search nodes of a given branching node ? Could you conceptually elaborate on that ?\n\nQ4/ What would be the main challenges towards extending the proposed approach to generate Rashomon sets of other types of interpretable models ? (e.g., rule lists, whose Rashomon set was already explored and for which efficient branch-and-bound algorithms were proposed such as CORELS)", "limitations": "yes", "rating": 5, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 3, "originality": 2, "strengths_and_weaknesses": "Quality: The problem is well-motivated, the related work is properly introduced and discussed. The proposed approach is technically solid, and the empirical evaluation is thorough. \n\nClarity: I found the paper pleasant to read. The different bounds, algorithms and subroutines are sufficiently detailed. Nice visualizations are provided for all experiments, allowing assessment of the results and their statistical significance.\n\n Significance: SORTD improves the state-of-the-art by (i) allowing an anytime behaviour (ii) avoiding pre-fixing a Rashomon parameter which could be too large or too small depending on the data and hypothesis class at hand and (iii) empirically improving scalability and efficiency of generating Rashomon sets for sparse decision trees (compared to state-of-the-art approaches). The ability to handle arbitrary objectives (as long as they are totally ordered and additive) is also a significant advantage of the method. I believe the provided implementation can be a useful tool for the interpretable machine learning community.\n\nOriginality: The proposed algorithm incorporates many building blocks from the literature on (optimal) sparse decision trees optimization, and on constructing their Rashomon sets. It results in a very technical contribution, with the conceptual/theoretical novelty being limited.\nNevertheless, the core idea of exploring the Rashomon set of sparse decision trees in ascending objective function order (i.e., best first) makes sense and empirically provides significant advantages (as aforementioned). \n\nScalability remains limited, as Rashomon sets are empirically explored only for decision trees with depth <= 5, and even in this setup, 100GB of RAM are necessary (with some experiments actually reaching the limit). But still, this is an improvement over the state-of-the-art. Maybe reporting some memory use values (in practice, are we far from using the allocated 100GB ?) could be worth it ?\n\n\nMinor:\n- (typo) Line 13 of Algorithm 2: what does \"if sol ′.value ← next then\" mean ? This looks like an assignment (with operator ←) rather than a comparison (as described in the main text on line 197). Also, \"next\" is undefined in this context.\n- (typo) Line 923: \"and a the fairness metric [...]\"\n- In Appendix B1, it is mentioned that 4 datasets were excluded because they \"exceeded memory limits while solving\". Could you clarify this ?(i.e., was the memory limit reached with the proposed SORTD, TreeFarms, or both ?)\n- (typo) Line 1073: \"[...], which are then evaluate [...]\"\n- (typo) Line 1109: \"[...] objective),\" (additional closing parenthesis)", "was_revised": true, "final_justification": "I maintain my original rating for this paper. As mentioned in my review, I believe this is an interesting and technically solid work. The resulting tool can be useful for the interpretable ML community. The authors' rebuttal brought some additional information regarding memory requirements and scalability that are worth including in a revised version of their paper and confirm my positive evaluation of this work.", "rebuttal": "We would like to thank the reviewer for the positive comments. We reply to the questions below:\n\n**Q1:** *\"...Could you please clarify how increasing the number of features ... can actually shorten the solution lists?\"*\n\nWe would like to highlight that the size of the Rashomon set is fixed in this analysis. Adding features would potentially increase the Rashomon set size given a fixed Rashomon bound. However, given a fixed Rashomon set size, the solutions would be distributed to the solutions list of more branching nodes. \n\n**Q2:** *\"...Did you perform ablation experiments to precisely quantify the speedup provided by using (or not) these subroutines ?\"*\n\nMost processes in SORTD are used to calculate the solutions in order, which are not expected to improve the runtime performance. Therefore, the scalability performance (demonstrated in Figure 3 and Figure 4) is mostly obtained through the depth-two solver. \n\n**Q3:** *\"...even though they are not generated, suboptimal solutions still need to be explored (e.g., in Figure 2, how to be sure that other splits are not better without verifying them ?)...\"*\n\nWe manage this situation by asking for the next solutions one by one. Each branching node needs to prepare its best solution, and the search node accepts the one with the lowest value. It is possible that the best solution of a branching node is left unused; however, this would require calculating only one extra solution.  \n\n**Q4:** *\"What would be the main challenges towards extending the proposed approach to generate Rashomon sets of other types of interpretable models?...\"*\n\nThe application of the techniques of our approach to other interpretable models depends on the properties of that model. For example, can the model be solved using best-first search; can the problem be split into smaller repeated subproblems for using DP; can subproblem relations be modeled in a graph? \n\n**Weakness:** *\"...Maybe reporting some memory use values (in practice, are we far from using the allocated 100GB ?) could be worth it ?\"*\n\nThe high memory requirements only occurred during the experiment preparation phase for precomputing the Rashomon multiplier epsilon values that were required for a fair comparison with TreeFARMS (but SORTD itself does not require them). We will clarify this in the text. The actual comparison between TreeFARMS and SORTD records no exceeded memory limits. In fact, we observe approximately 5-7 times less memory usage by our approach than TreeFARMS, and on average over all instances, SORTD uses less than 1GB of memory. We will add these results to the appendix. \n\n**Minor Weakness 2:** *\"In Appendix B1, it is mentioned that 4 datasets were excluded because they \"exceeded memory limits while solving. ... was the memory limit reached with the proposed SORTD, TreeFarms, or both?\"*\n\nWe used SORTD to precompute the precise Rashomon multiplier epsilon values for TreeFarms. This means the memory limits were observed with SORTD.  \n\n**Minor Weakness 1:** *\"what does \"if sol ′.value ← next then\" mean?\"*\n\nThe reviewer is correct, it is a typo. We will change the assignment operator to the equality comparison operator."}, {"review_id": "S0uXuTLDVT", "reviewer": "Reviewer_hQ9P", "summary": "This work gives a method to enumerate the Rashomon set of sparse decision trees, over any totally ordered objective, in order of the trees' dataset objective value. The algorithm stores partial solutions at descending levels of the tree in two types of 'helper' nodes -- branching nodes, which enable further splits, and leaf nodes, which terminate the tree. Broadly speaking, the algorithm computes optimal solutions to subproblems in every branching node, and prunes subproblems by keeping running upper and lower bounds on the possible objective in a subproblem. The enumeration algorithm outputs the optimal tree at the top level (the global optimal tree), then in some sense \"percolates\" optimal solutions from the left and right subtrees up to the top of the tree. The algorithm stops when it has either enumerated all trees in the Rashomon set, has reached a time limit, or when it has enumerated a fixed number of trees. Thus, this algorithm gives two novel capabilities; first, it can enumerate the Rashomon set of sparse decision trees in order; second, it can compute the Rashomon set with respect to any totally ordered (and, for practical purposes, separable) objective function. The authors also include timing experiments to demonstrate an improvement over the current state-of-the-art in TreeFARMS, as well as case studies in variable importance, Rashomon sets of sparse regression trees, and fairness.", "questions": "1. Do you think that SORTD's speed advantage would persist if compared against TreeFARMS, but with the depth-2 solver? To rephrase -- is it the optimization framework itself that gives the advantage over TreeFARMS, or the incorporation of a very helpful extra algorithmic component?\n\n2. Is this algorithm able to easily exclude trivial extensions from the Rashomon set (as defined in the TreeFARMS algorithm; extra splits that don't change predictions, but also don't exceed the Rashomon bound)? Ignoring trivial extensions is a useful feature for TreeFARMS which also aids computation, so comparing to TreeFARMS without ignoring trivial extensions appears to be hamstringing TreeFARMS unduly, if SORTD is in fact unable to easily ignore them. \n\n3. How does the Rashomon set of sparse regression trees compare to the Rashomon set of sparse decision trees (say, on a threshold of the continuous regression label to turn it into a classification problem)? Are the Rashomon sets similar? Do the trees share many common prefixes?", "limitations": "yes", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 4, "significance": 3, "originality": 3, "strengths_and_weaknesses": "## Strengths\n\n1. The insight that the STreeD framework for decision tree optimization can be adapted to find all models in the Rashomon set of totally ordered (and perhaps additive) objective functions in order, and quickly at that, strikes me as both novel and significant. \n\n2. The speedups over TreeFARMS, in combination with the anytime enumeration capability and objective function flexibility, are fairly represented by this paper to be steps toward the practical application of Rashomon set methods. \n\n3. The paper was succinct, well-written, and easy to follow. The paper was well-situated among other literature in the related work section. The descriptions of the algorithms, both in the high-level idea and in the details in the paper and the appendix, were clear and I feel as if I understand both their motivation and implementation.\n\n\n## Weaknesses\n\n### Significant Weaknesses\n\nIn summary, I felt as if the case studies provided to demonstrate the practical utility of SORTD were somewhat superficial.\n\n1. The Model Class Reliance metric due to Fisher et al., 2019, already captures the essence of the LOFO case study. The resulting insights in the first example that \"priors > 3\" and \"ExternalRiskEstimate\" are important are not new, and are easily obtainable via existing approaches. \n\n2. The work of Donnelly et al., 2023: The Rashomon Importance Distribution: Getting RID of Unstable, Single Model-based Variable Importance gives a principled way to obtain a distribution of variable importances in the Rashomon set via bootstrapping.\nIn the second example, I feel as if the novel insight from this paper is not that Rashomon sets improve the stability of variable importance (which is thoroughly discussed by Donnelly et al., 2023), but that you don't need many models from the Rashomon set to significantly improve reliability. This point felt under-explored -- indeed, only 20/29 of the datasets analyzed met the 0.8 threshold for Jaccard index for top-100, which to me is not enough to indicate reliability. \n\n3. Similarly, the example given for generating sparse regression trees, while interesting for the fact that SORTD can indeed compute the Rashomon set of sparse regression trees, did not add much to the paper. TreeFARMS was already shown by Xin et al., 2022 to dominate methods which generate single optimal trees on bootstraps, and there is no reason to expect that another Rashomon set algorithm should be different. I think that the main point of this section was that SORTD can indeed effectively compute the Rashomon set of objective functions beyond misclassification error, and perhaps this could have been emphasized moreso than comparison to CART and STreeD.\n\n### Minor Weaknesses\n\n1. The abstract seems to imply that SORTD somehow bypasses the NP-hard optimal tree problem by enumerating Rashomon sets in order. This is an issue of wording, not content.\n\n2. I think that this work would benefit from a figure or analysis supporting the claim on line 243, that the scalability of SORTD derives from the shortening of solution lists, despite more branching nodes. This analysis seems plausible when adding bad or do-nothing features to the dataset, but when adding good features I would expect the number of models in the Rashomon set to explode, and concurrently for solution lists to get longer even though there are more branching nodes.", "was_revised": true, "final_justification": "After my discussion with the authors, I am raising my score to a 5 (accept). The actual method of the paper, anytime enumeration of the Rashomon set with respect to any separable objective function, is a significant step forward in the field of Rashomon set computation. My primary concerns with the paper were that the case studies presented as evaluation were superfluous and did not demonstrate new capabilities beyond what previously existed. After consideration of the responses and other reviews, I've concluded that the case studies sufficiently demonstrate that the proposed method can indeed handle flexible objective functions, is faster than TreeFARMS, and allows for computation with a fixed number of trees in addition to with a fixed Rashomon bound. In essence -- SORTD hasn't lost anything that TreeFARMS has, and it's faster and more flexible. With that in mind, the case studies are good enough for me to confidently recommend acceptance of the paper, given its strong methodological progress.", "rebuttal": "We would like to thank the reviewer for the positive comments. We reply to the questions below:\n\n**Q1:** *\"Do you think that SORTD's speed advantage would persist if compared against TreeFARMS, but with the depth-2 solver?...\"*\n\nThe scalability advantage is indeed mostly obtained through the depth-two solver. The novel search technique provides an anytime behavior, which we believe is essential to parse larger datasets, specifically, if beforehand good Rashomon bounds cannot be guessed. Compared to TreeFARMS, SORTD is also more flexible in terms of the variety of objective functions it supports.  \n\n**Q2:** *\"...comparing to TreeFARMS without ignoring trivial extensions appears to be hamstringing TreeFARMS unduly...\"*\n\n The impact of ignoring trivial extensions is a much smaller Rashomon set (under the assumption of a fixed Rashomon multiplier epsilon values), thus improving both methods' runtime. In our experiments, on the other hand, we search for fixed-size Rashomon sets (e.g., 10^6, see Table 2). After modifying SORTD to support the exclusion of trivial extensions, our evaluation shows that both methods had higher runtime compared to the case where trivial extensions are not ignoried (as fixing Rashomon set size resulted in higher Rashomon multiplier epsilon values). However, SORTD still maintained up to a two orders of magnitude runtime advantage over TreeFARMS. We will include the results in the appendix.\n\n**Q3:** *\"How does the Rashomon set of sparse regression trees compare to the Rashomon set of sparse decision trees\"*\n\nThe main difference we observed was that the number of unique solution values for regression was much larger than for classification. This is expected since the regression loss is continuous. Investigating the comparison of these two sets could be interesting for future research.  \n\n**SW1:** *\"The Model Class Reliance metric due to Fisher et al., 2019, already captures the essence of the LOFO case study...\"*\n\nOur objective in Figure 5 is to give a visualization of how we calculated LOFO values using Rashomon sets rather than providing an analysis of certain datasets. We will make it clear in the paper.\n\n**SW2:** *\"I feel as if the novel insight from this paper is not that Rashomon sets improve the stability of variable importance ... but that you don't need many models from the Rashomon set to significantly improve reliability...\"*\n\nOur variable importance analysis indeed does not aim to demonstrate that Rashomon sets improve the stability of variable importance. It aims to show that variable importance measured is relatively stable for 100 or 10,000 trees. Yet, developing theories on the necessary number of trees, rather than the bound (as in Donnelly et al., 2023), to get stable measurements of variable importance is an interesting future work. \n\n**SW3:** *\"...I think that the main point of this section was that SORTD can indeed effectively compute the Rashomon set of objective functions beyond misclassification error...\"*\n\nIndeed, in Section 5.3, we aim to demonstrate the capability of SORTD to calculate and evaluate Rashomon sets of varying objectives. As there is no benchmark method of generating Rashomon sets of regression trees, we demonstrate SORTD’s ability by comparing it with CART. Highlighting this in the text is useful; we will make the necessary adjustments. \n\n**MW1:** *\"The abstract seems to imply that SORTD somehow bypasses the NP-hard optimal tree problem...\"*\n\nThank you, we will change the sentence.\n\n**MW2:** *\"...when adding good features I would expect the number of models in the Rashomon set to explode, and concurrently for solution lists to get longer...\"*\n\nWe would like to highlight that the size of the Rashomon set is fixed in this analysis. Adding good features would potentially increase the Rashomon set size given a fixed Rashomon bound. However, given a fixed Rashomon set size, the solutions would be distributed to the solutions list of more branching nodes."}]

Author rebuttal:

Meta-review: This study introduces a novel anytime algorithm for enumerating Rashomon sets of sparse decision trees across various objective functions. The paper has received five reviews, with scores ranging from weak to strong acceptance. Reviewers unanimously agree on the paper's quality, its positioning in relation to related work, the benefits of this anytime enumeration method, and the significance of the experimental results. In summary, this represents an important contribution to the field of interpretable machine learning and the enumeration of Rashomon sets. For these reasons, I strongly recommend its acceptance.

Additionally, the authors effectively addressed several clarity issues during the rebuttal phase. For the revised version of the paper, I suggest incorporating this discussion to further enhance its quality.
Decision: Accept (spotlight)