ArborEnum: Decision Tree Rashomon Sets over Continuous Features

# ArborEnum: Decision Tree Rashomon Sets over Continuous Features
Source: [https://arxiv.org/html/2608.04310](https://arxiv.org/html/2608.04310)
###### Abstract

The Rashomon effect describes the phenomenon that many models can achieve nearly equivalent performance on the same learning task, with significant ramifications for robustness, feature importance, and customizability\. These use cases motivate the computation of Rashomon sets: the set of all models whose regularized loss is near\-optimal\. Decision trees are one of the few model classes for which Rashomon sets can be fully enumerated, but this computation has always been conditional on a binarization of the original data, either restricting which splits each tree is allowed to make or substantially increasing the complexity of an already difficult combinatorial problem\. We introduce the first algorithm that exactly enumerates decision\-tree Rashomon sets while exploiting the ordered structure of continuous features\. We further develop a relaxation for approximate enumeration and an anytime algorithm that progressively refines the set of candidate thresholds, producing increasingly detailed approximations that converge to the continuous\-feature Rashomon set\. Experiments show that coarse binarization can miss many trees, important features, and predictive multiplicity; our algorithms achieve orders\-of\-magnitude speedups over existing enumeration methods, with approximations providing further speedups while maintaining near\-perfect recall\.

The code for our method, ArborEnum, is available at—https://github\.com/zakk\-h/ArborEnum

## 1Introduction

For many prediction problems, there is not a single uniquely best model\. Instead, many distinct models often achieve nearly equivalent predictive performance\. This phenomenon, known as the Rashomon effect\(Breiman[1984](https://arxiv.org/html/2608.04310#bib.bib106)\), motivates the study of Rashomon sets\(Fisheret al\.[2019](https://arxiv.org/html/2608.04310#bib.bib155)\): collections of models whose objective values are within a prescribed tolerance of optimal\. Rather than returning only one model, Rashomon set methods expose the full set of high\-performing alternatives\.

Rashomon sets have been investigated for several model classes, including decision trees\(Xinet al\.[2022](https://arxiv.org/html/2608.04310#bib.bib126)\), rule lists\(Ciaperoniet al\.[2024](https://arxiv.org/html/2608.04310#bib.bib110)\), generalized additive models\(Zhonget al\.[2023](https://arxiv.org/html/2608.04310#bib.bib112)\), and prototypical\-part convolutional neural networks\(Donnellyet al\.[2025](https://arxiv.org/html/2608.04310#bib.bib157)\)\. We focus this work on finding Rashomon sets of decision trees\. Existing decision\-tree Rashomon set algorithms\(Heileet al\.[2026](https://arxiv.org/html/2608.04310#bib.bib156); Arslanet al\.[2025](https://arxiv.org/html/2608.04310#bib.bib131); Babbaret al\.[2025](https://arxiv.org/html/2608.04310#bib.bib105); Xinet al\.[2022](https://arxiv.org/html/2608.04310#bib.bib126)\)address this problem when given a set of binary features\. As a result, continuous features must usually be coarsely binarized before the Rashomon set is computed\. Even then, the search space is enormous\.Huet al\.\([2019](https://arxiv.org/html/2608.04310#bib.bib29)\)shows that the size of the search space of decision trees of depth44with only2020binary features is approximately8\.4×10188\.4\\times 10^\{18\}trees\. For some continuous features, there are thousands of cut points to consider\. Consequently, existing methods fail to scale to handle this important problem\.

We introduceArborEnum\(Algorithms forRelayingBounds forOrderedRashomonENUMeration\),the first framework designed for enumerating decision\-tree Rashomon sets over continuous features\. ArborEnum adapts threshold bounds developed for finding a single optimal tree\(brița2025optimal\)to enumerate trees whose objectives fall within a prescribed bound\. We use these bounds to propagate information from evaluated thresholds to nearby thresholds, allowing large ranges of candidate splits to be pruned efficiently\. ArborEnum can compute the information required by these bounds either optimally or approximately\. In the former case, ArborEnumexactly enumerates the continuous\-feature Rashomon set; in the latter, it yieldsapproximate variantsfor settings where exact enumeration remains too expensive,achieving a median speedup of 270×\\times\(Table[6](https://arxiv.org/html/2608.04310#A5.T6)\)\. For datasets where even high\-quality approximation remains computationally demanding, we propose ananytime algorithm that progressively refines the binarization and converges to the exact Rashomon set when run to completion\. These methods are supported by an improved representation of the Rashomon set that reduces runtime and memory usage while potentially improving approximation quality\. Across our experiments, exact enumeration is feasible on many datasets, while our approximations recover nearly all trees at a fraction of the cost on harder instances\. We further show that accounting for continuous thresholds is important for downstream analyses: coarse binarization can miss predictive multiplicity, important variables, and high\-quality trees in the Rashomon set, motivating the use of our anytime algorithm to refine the binarization as much as is computationally feasible\.

## 2Related Work

#### Greedy and optimal trees\.

Decision trees are among the most widely used interpretable model classes, with classical algorithms such as CART\(Breiman[1984](https://arxiv.org/html/2608.04310#bib.bib106)\)and C4\.5\(Quinlan[2014](https://arxiv.org/html/2608.04310#bib.bib18)\)providing scalable top\-down procedures for fitting trees\. These methods choose splits greedily, which makes them computationally efficient but without any optimality guarantees\.

A large body of recent work has studied optimal decision trees, including our setting of optimizing misclassification error plus a per\-leaf penalty\. Although this problem is NP\-hard, specialized methods based on mixed\-integer programming, dynamic programming, caching, and branch\-and\-bound have made it practical to find optimal trees of bounded size for many datasets\(Huet al\.[2019](https://arxiv.org/html/2608.04310#bib.bib29); Linet al\.[2020](https://arxiv.org/html/2608.04310#bib.bib37); Aglinet al\.[2020](https://arxiv.org/html/2608.04310#bib.bib123); Demirovićet al\.[2022](https://arxiv.org/html/2608.04310#bib.bib19); van der Lindenet al\.[2023](https://arxiv.org/html/2608.04310#bib.bib122)\)\. These methods admit an interpretation of searching over an AND/OR graph, where OR nodes correspond to split choices and AND nodes correspond to combining left and right solutions\(Sullivanet al\.[2024](https://arxiv.org/html/2608.04310#bib.bib115); Chaoukiet al\.[2025](https://arxiv.org/html/2608.04310#bib.bib116)\)\. This structure is what has allowed prior work to store Rashomon sets compactly\(Heileet al\.[2026](https://arxiv.org/html/2608.04310#bib.bib156); Arslanet al\.[2025](https://arxiv.org/html/2608.04310#bib.bib131); Xinet al\.[2022](https://arxiv.org/html/2608.04310#bib.bib126)\)\.

#### Binarization methods\.

A common way to apply binary\-feature tree optimization methods to continuous data is to binarize each continuous feature using a small number of thresholds, often chosen by empirical quantiles; for example,Babbaret al\.\([2025](https://arxiv.org/html/2608.04310#bib.bib105)\)uses three quantile thresholds per feature\. Threshold guessing\(McTavishet al\.[2022](https://arxiv.org/html/2608.04310#bib.bib114)\)instead trains a reference ensemble such as XGBoost, extracts candidate thresholds, and uses backward elimination to keep a small set of high\-quality splits\. While effective for finding a single optimal tree, this is less suitable for Rashomon sets, where the goal is to characterize many good models\.

#### Handling continuous features\.

Recent work extends these ideas to continuous features\(brița2025optimal; Kiossouet al\.[2026](https://arxiv.org/html/2608.04310#bib.bib33)\)\.Mazumderet al\.\([2022](https://arxiv.org/html/2608.04310#bib.bib30)\)handle continuous features by performing branch\-and\-bound over intervals of each feature and using quantile\-based upper and lower bounds to prune ranges of candidate thresholds that cannot contain an optimal tree\. However, they focus only on depth\-2 or depth\-3 trees, as the algorithm does not scale beyond that\.brița2025optimalalso optimize classification trees directly over continuous features, using bounds that are looser but cheaper to compute\.

#### Approximation algorithms\.

For the approximation algorithms in our work, we build onHeileet al\.\([2026](https://arxiv.org/html/2608.04310#bib.bib156)\), which uses a fast proxy algorithm to certify feasible completions within the Rashomon budget and prunes branches whose proxy\-completed objective exceeds that bound\. Since the budget is set relative to the proxy objective, this pruning rule is not overly aggressive; in fact, it is never incorrect when the proxy optimality gap is maximized at the root\. Our approximation algorithms extend this strategy to continuous features through new relaxations and proxy algorithms\. One important proxy is LicketySPLIT\(Babbaret al\.[2025](https://arxiv.org/html/2608.04310#bib.bib105)\)\. At each subproblem, it greedily completes the children of each candidate split, selects the split with the best completed regularized objective, and recurses on the resulting subproblems\. We relax LicketySPLIT to operate efficiently over continuous features and use the resulting algorithm, which we call “LicketySNIP,” as a proxy in our approximation methods\.

## 3Methods

LetDDdenote the current subproblem, represented by a bitvector over the training samples, and letγ\\gammabe a per\-leaf penalty\. Let𝒯d\\mathcal\{T\}\_\{d\}denote the set of axis\-aligned decision trees of depth at mostddon the training features\. Let𝒴\\mathcal\{Y\}denote the set of≥2\\geq 2class labels\. We score a tree by

Obj​\(T,D,γ\)=misclassifications​\(T;D\)\+γ⋅\|Leaves​\(T\)\|\.\\mathrm\{Obj\}\(T,D,\\gamma\)=\\mathrm\{misclassifications\}\(T;D\)\+\\gamma\\cdot\|\\mathrm\{Leaves\}\(T\)\|\.We use a*proxy algorithm*to obtain an objective value attained by some tree in𝒯d\\mathcal\{T\}\_\{d\}for the subproblem and remaining depthdd; this tree may be, but need not be, optimal\. Our pruning rules assume a proxy robustness condition: for instance, moving a few samples across a threshold changes the proxy\-completed objective by at most the number of samples moved\. Optimal proxies satisfy this condition, in which case our algorithm returns the exact Rashomon set\. For non\-optimal proxies, the same rule acts as a useful relaxation, enabling large speedups with little or no empirical loss in solution quality\.

Given a budgetεabs\\varepsilon\_\{\\mathrm\{abs\}\}, we find subtrees whose objective on the subproblem is at mostεabs\\varepsilon\_\{\\mathrm\{abs\}\}; if we are using an approximate proxy algorithm, we recover a subset of trees that satisfy this; otherwise, it is exact\. The multiplicative Rashomon set is defined usingεabs=\(1\+εmult\)​Optimal​\(D,d,γ\)\\varepsilon\_\{\\mathrm\{abs\}\}=\(1\+\\varepsilon\_\{\\mathrm\{mult\}\}\)\\textsc\{Optimal\}\(D,d,\\gamma\)so that it contains all trees whose objective is within a multiplicative factor of the optimal objective\. We approximate it by initially settingεabs=\(1\+εmult\)​Proxy​\(D,d,γ\)\.\\varepsilon\_\{\\mathrm\{abs\}\}=\(1\+\\varepsilon\_\{\\mathrm\{mult\}\}\)\\textsc\{Proxy\}\(D,d,\\gamma\)\.

For each subproblem–depth pair\(D,d\)\(D,d\), we persist at most \(1\) a cached proxy solution and its intermediate computations, \(2\) a pointer to a node whose rooted subgraph encodes a Rashomon set for that subproblem under some budgetεabs\\varepsilon\_\{\\textrm\{abs\}\}, and \(3\) one threshold\-to\-proxy\-completion map per continuous feature\. We additionally maintain a threshold registry𝒮\\mathcal\{S\}containing the active thresholds and per\-feature bounds that we lazily infer from thresholds found to be constant onDD\. We elaborate more on these in the following subsections\.

#### Storing the Rashomon Set\.

We encode the information needed to recover the Rashomon set via an \(acyclic\) AND/OR graph\. Each OR node represents a subproblem \(represented by a set of data points\), remaining depth, and budget, meaning the largest subtree objective we are willing to enumerate\. In the algorithms,GGdenotes a pointer to the OR node for the current subproblem\. We refer toGGas a subgraph, because the solutions for the subproblem are rooted atGG\. During the execution of our algorithms, each OR node stores its current budget, the minimum objective of any tree rooted at that node, and the split/leaf choices that we know can be completed within the budget\. Each of those split choices has edges to its left and right child subgraphs, so the Rashomon set can be recovered by traversing these choices in the AND/OR graph\. After the search terminates, we perform a post\-processing step that builds objective histograms at each OR node, which allows trees to be indexed efficiently in sorted order of objective value\. Before this post\-processing step, we refer to the structure as aminimum\-objective AND/OR graph\.

#### Existing Caching\.

Separate from the AND/OR graph, we adopt the proxy optimizer framework ofHeileet al\.\([2026](https://arxiv.org/html/2608.04310#bib.bib156)\), which caches proxy objective values and the intermediate computations used to obtain them\. When LicketySPLIT is used as the proxy, this cache includes the objective values returned by each greedy completion and its recursive calls, as well as those returned by each LicketySPLIT call and its recursive calls\. These memoized values are retained and reused throughout the Rashomon set computation\.

#### Subgraph Caching\.

In addition to the cache described above, we maintain an index into the AND/OR graph that maps each subproblem\-depth pair to its canonical OR node\. The index is budget\-independent: there is at most one OR node for each subproblem and remaining depth \(see lines 1 and 3 of Algorithm[1](https://arxiv.org/html/2608.04310#alg1)\)\. When a subproblem that was previously solved under a smaller budget is later reached with a larger budget, we start from the existing subgraph and extend it in place \(line 8 and after\), rather than rebuilding it\. Accordingly, each OR node records the largest budget for which it has been solved \(because of line 8\)\. Conversely, if the existing subgraph contains solutions for a budget larger than the requested budget, we return a pointer to it and defer the budget restriction to solution extraction\. \(lines 4\-6, details of extraction in Appendix[A\.10](https://arxiv.org/html/2608.04310#A1.SS10)\)\. During iterative budget refinement \(Appendix[A\.5](https://arxiv.org/html/2608.04310#A1.SS5)\), our mechanism reuses and expands existing child subgraphs \(called in lines 15 and 18\)\. In contrast, the mechanism ofHeileet al\.\([2026](https://arxiv.org/html/2608.04310#bib.bib156)\)repeatedly recurses from scratch as larger child budgets become available\. Appendix[B](https://arxiv.org/html/2608.04310#A2)establishes that this yields a more compact representation than existing methods\. Moreover, with an approximate proxy, solving under a larger budget can recover new trees that satisfy a smaller budget, improving approximation quality\.

#### Leaves\.

At each OR node, we add any prediction leaf whose objective is withinεabs\\varepsilon\_\{\\mathrm\{abs\}\}\(line 9\)\. We only add leaves that are not already stored inGG\.

#### Binary Features\.

For a binary feature,EnumerateBinaryFeature\(see Appendix[A\.2](https://arxiv.org/html/2608.04310#A1.SS2)\) partitionsDDintoDLD\_\{L\}andDRD\_\{R\}, computes proxy objectivesPLP\_\{L\}andPRP\_\{R\}for child subproblems, and discards the split ifPL\+PR\>εabsP\_\{L\}\+P\_\{R\}\>\\varepsilon\_\{\\mathrm\{abs\}\}\. Otherwise, it callsAddOrExtendSplit\(Appendix[A\.7](https://arxiv.org/html/2608.04310#A1.SS7)\) to construct or extend the child subgraphs and add the split toGG\.

Algorithm 1ArborEnum\(G,D,d,γ,εabs,𝒮\)\(G,D,d,\\gamma,\\varepsilon\_\{\\textrm\{abs\}\},\\mathcal\{S\}\)0:Empty or existing Rashomon subgraph

GGfor subproblem

DDand depth

dd, per\-leaf penalty

γ\\gamma, new budget

εabs\\varepsilon\_\{\\textrm\{abs\}\}, and threshold registry

𝒮\\mathcal\{S\}
1:

k←SubproblemKey​\(D,d\)k\\leftarrow\\textsc\{SubproblemKey\}\(D,d\)\{Identify the subproblem by its samples and remaining depth\}

2:if

k∈ℐGk\\in\\mathcal\{I\}\_\{G\}then\{Access global subgraph index

ℐG\\mathcal\{I\}\_\{G\}\}

3:

G←ℐG​\[k\]G\\leftarrow\\mathcal\{I\}\_\{G\}\[k\]\{Retrieve the canonical subgraph for this subproblem\-depth pair\}

4:if

Budget​\(G\)≥εabs\\textsc\{Budget\}\(G\)\\geq\\varepsilon\_\{\\textrm\{abs\}\}then

5:return

GG\{The desired solution is already encoded in the cached subgraph\}

6:endif

7:endif

8:

SetBudget​\(G,εabs\)\\textsc\{SetBudget\}\(G,\\varepsilon\_\{\\textrm\{abs\}\}\)\{Record the largest budget for which this node must be solved\}

9:

AddFeasibleLeaves​\(G,D,γ,εabs\)\\textsc\{AddFeasibleLeaves\}\(G,D,\\gamma,\\varepsilon\_\{\\textrm\{abs\}\}\)\{Add feasible leaves that are not already stored in

GG\}

10:if

d=0d=0or

εabs<2​γ\\varepsilon\_\{\\textrm\{abs\}\}<2\\gammathen

11:

ℐG​\[k\]←G\\mathcal\{I\}\_\{G\}\[k\]\\leftarrow G
12:return

GG\{No split fits in the remaining budget\}

13:endif

14:foreach continuous feature

ccdo

15:

EnumContFeature​\(G,D,c,d,γ,εabs,𝒮\)\\begin\{aligned\} &\\textsc\{EnumContFeature\}\(G,D,c,d,\\gamma,\\varepsilon\_\{\\textrm\{abs\}\},\\mathcal\{S\}\)\\end\{aligned\}\{Enumerate the currently available nonconstant thresholds of feature

cc;

𝒮\\mathcal\{S\}and

GGare updated by reference\}

16:endfor

17:foreach binary feature

jjdo

18:

EnumerateBinary​\(G,D,j,d,γ,εabs,𝒮\)\\textsc\{EnumerateBinary\}\(G,D,j,d,\\gamma,\\varepsilon\_\{\\textrm\{abs\}\},\\mathcal\{S\}\)\{Construct or extend the child subgraphs if the budget permits\}

19:endfor

20:

ℐG​\[k\]←G\\mathcal\{I\}\_\{G\}\[k\]\\leftarrow G\{Store a pointer to the canonical root of this subgraph\}

21:return

GG\{The Rashomon set is encoded in

GG\}

#### Handling Continuous Features\.

For continuous features, we assume that each continuous feature has been expanded into a contiguous, ordered block of threshold columns\. A threshold column corresponds to the rulexj≤νx\_\{j\}\\leq\\nu\(for some valueν\\nu\)\. These columns are nested:xj≤ν⟹xj≤ν′x\_\{j\}\\leq\\nu\\implies x\_\{j\}\\leq\\nu^\{\\prime\}forν′\>ν\\nu^\{\\prime\}\>\\nu\. We exploit this ordering to prune thresholds\. For example, suppose we know that a certain threshold column is always zero for each row in the current subproblem\. Then, we can exclude any lower\-indexed threshold because it will create an empty leaf\. We use𝒮\\mathcal\{S\}to track lower and upper bounds on the non\-constant thresholds and eliminate thresholds outside this range inInitAndPrune\. We update𝒮\\mathcal\{S\}lazily inEnumContFeatureas thresholds are explored\.

#### Continuous Feature Pruning\.

Within a continuous feature,EnumContFeaturesearches over threshold intervals in the spirit of ConTree\(brița2025optimal\)\. We modify the pruning rules to account for the Rashomon budget and per\-leaf penalty and maintain a map of thresholds to proxy completions to exploit repeated visits to the same subproblem, possibly with different budgets\. We allow the search to be over a subset of thresholds, included in𝒮\\mathcal\{S\}, which we call active thresholds\. In general, all thresholds are active, but we support activating only a subset of them for use by the anytime algorithm \(Algorithm[4](https://arxiv.org/html/2608.04310#alg4)\)

![Refer to caption](https://arxiv.org/html/2608.04310v1/newsubproblemcontinuous.png)Figure 1:InitAndPruneexample\. Using proxy completions inEEfor exhaustive thresholds 2 and 18, we prune active thresholds 0, 1, 10, 11, and 12 using active sample distances \(for instance,85−8\>7585\-8\>75, so we prune active threshold 0, whereas85−12≤7585\-12\\leq 75, so this test cannot prune active threshold 2\. For simplicity, we showEEstoring the sum of proxy completions \(notPLP\_\{L\}andPRP\_\{R\}\); we omit pruning based onγ\\gamma\. From𝒮\\mathcal\{S\}\(not shown\), thresholds 22 and above are constant\. We recursively construct subgraphs for active thresholds 3–6\.InitAndPrunereturns\[2,2\]\[2,2\]and\[7,9\]\[7,9\]\(the remaining active threshold indices\) forEnumContFeature\.
#### Specifics of Pruning\.

For each continuous feature,EnumContFeature\(Algorithm[3](https://arxiv.org/html/2608.04310#alg3)\) retrieves a queueQQof intervals over active threshold indices that remain to be explored\. This queue is created byInitAndPrune\(Algorithm[2](https://arxiv.org/html/2608.04310#alg2)\)\. On the first visit to a subproblem, no proxy completions have been stored, and Algorithm[2](https://arxiv.org/html/2608.04310#alg2)returns a range spanning all active threshold indices \(outside of what𝒮\\mathcal\{S\}knew was constant\)\. On later visits, it retrieves a mapEE, associated with the current subproblem, remaining depth, and continuous feature\. Each entry inEEmaps a threshold indexttto the previously computed proxy objectivesPL,PRP\_\{L\},P\_\{R\}for its left and right subproblems\. This structure is separate from the proxy algorithm’s caching:EEprovides information about the children subproblems that we have evaluated, not a solution to the subproblem\. Algorithm[2](https://arxiv.org/html/2608.04310#alg2)uses these stored values to prune portions of the search space \(Algorithm[2](https://arxiv.org/html/2608.04310#alg2), lines 7\-24\); Figure[1](https://arxiv.org/html/2608.04310#S3.F1)illustrates how different active threshold indices are ruled out to formQQ\. Storing the proxy\-completed objectives, rather than only whether each threshold was previously pruned, allows for work to be reused under different budgets\. Additionally,EEis keyed by indices in the exhaustive threshold set, not by active\-threshold positions, so it can be reused as additional thresholds become active\. All subsequent logic refers to a threshold by its index in the active threshold set\.

We track pruned or explored active thresholds as an ordered collection of disjoint index ranges, whose complement is the set of intervals that still need to be explored \(line 25\)\.ExcludedRangeTrackermaintains this collection using a red\-black tree of pairs\(a,b\)\(a,b\)ordered byaaand repeatedly merging a new range with any ranges that overlap or touch it\.

When looping over the stored proxy completions \(line 7\), if we come across a threshold whose proxy\-completed objective is now within budget, we go ahead and solve it for the first time or extend the subgraph; then it is no longer under consideration \(lines 13\-15\)\. If the proxy\-completed objective is outside the budget, we try to prune nearby thresholds \(lines 16\-22\)\. We also update global bounds when a child attains the minimum possible costγ\\gamma: if the left child has costγ\\gamma, moving the threshold farther left cannot improve the optimal completions; similarly for the right child \(lines 17\-18\)\.

We also prune thresholds neighboring any split whose proxy\-completed objective exceeds the budget\. For two threshold indicesssandttin the same continuous\-feature group, letXsX\_\{s\}andXtX\_\{t\}be the corresponding binary columns\. Define their active\-sample distance onDDas

distD​\(s,t\)=\|\{i∈D:Xs​\(i\)≠Xt​\(i\)\}\|\\mathrm\{dist\}\_\{D\}\(s,t\)=\\left\|\\\{i\\in D:X\_\{s\}\(i\)\\neq X\_\{t\}\(i\)\\\}\\right\|This is the number of active samples \(in the current subproblem\) whose branch assignment changes when moving the threshold fromsstott\.

Algorithm 2InitAndPrune\(G,D,c,d,γ,εabs,𝒮\)\(G,D,c,d,\\gamma,\\varepsilon\_\{\\textrm\{abs\}\},\\mathcal\{S\}\)0:Current OR node

GG, subproblem

DD, continuous feature identifier

cc, depth

dd, budget

εabs\\varepsilon\_\{\\textrm\{abs\}\}, and threshold registry

𝒮\\mathcal\{S\}\{Called inEnumContFeature\}

1:

k←SubproblemKey​\(D,d\)k\\leftarrow\\textsc\{SubproblemKey\}\(D,d\)
2:

E←𝒞map​\(k,c\)E\\leftarrow\\mathcal\{C\}\_\{\\textrm\{map\}\}\(k,c\)\{Fetch the map of exhaustive indices to cached left and right proxy completions\}

3:

\(L,U\)←RestrictRange​\(𝒮,D,c\)\(L,U\)\\leftarrow\\textsc\{RestrictRange\}\(\\mathcal\{S\},D,c\)\{Explore only active indices not known to be constant on

DD\}

4:

ℛexcluded←ExcludedRangeTracker​\(\)\\mathcal\{R\}\_\{\\textrm\{excluded\}\}\\leftarrow\\textsc\{ExcludedRangeTracker\}\(\)\{Track ranges of active thresholds that are already handled or pruned\}

5:\{Process cached proxy completions in the desired range\}

6:foreach

t∈Keys​\(E\)t\\in\\textsc\{Keys\}\(E\)do

7:

q←ActivePosition​\(𝒮,D,c,t\)q\\leftarrow\\textsc\{ActivePosition\}\(\\mathcal\{S\},D,c,t\)\{

ttis an exhaustive threshold\-column index \. Get its active index

qq\.\}

8:if

q<Lq<Lor

q\>Uq\>Uthen

9:continue\{The threshold is outside search bounds\}

10:endif

11:

\(PL,PR\)←E​\(t\)\(P\_\{L\},P\_\{R\}\)\\leftarrow E\(t\);

P←PL\+PRP\\leftarrow P\_\{L\}\+P\_\{R\}
12:if

P≤εabsP\\leq\\varepsilon\_\{\\textrm\{abs\}\}then

13:

AddOrExtendSplit​\(G,D,t,d,γ,εabs,𝒮,PL,PR\)\\begin\{aligned\} &\\textsc\{AddOrExtendSplit\}\(G,D,t,d,\\gamma,\\varepsilon\_\{\\textrm\{abs\}\},\\mathcal\{S\},P\_\{L\},P\_\{R\}\)\\end\{aligned\}\{Create or extend the child subgraphs for the current active thresholds\}

14:

ℛexcluded\.MarkExplored​\(q\)\\mathcal\{R\}\_\{\\textrm\{excluded\}\}\.\\textsc\{MarkExplored\}\(q\)\{The threshold has already been evaluated; we mark it as explored\}

15:else

16:\{Moving the threshold farther left/right cannot improve if that side is already a pure leaf\}

17:if

PL=γP\_\{L\}=\\gammathen

L←max⁡\{L,q\+1\}L\\leftarrow\\max\\\{L,q\+1\\\}
18:if

PR=γP\_\{R\}=\\gammathen

U←min⁡\{U,q−1\}U\\leftarrow\\min\\\{U,q\-1\\\}
19:

Δ←P−εabs\\Delta\\leftarrow P\-\\varepsilon\_\{\\textrm\{abs\}\}\{Compute by how much the proxy completion exceeds the budget\}

20:\{Closest active indices that are

≥Δ\\geq\\Deltasamples away\}

21:

ℓ←LeftBoundary​\(D,𝒮,c,t,q−1,L,Δ\)\\ell\\leftarrow\\textsc\{LeftBoundary\}\(D,\\mathcal\{S\},c,t,q\-1,L,\\Delta\)
22:

r←RightBoundary​\(D,𝒮,c,t,q\+1,U,Δ\)r\\leftarrow\\textsc\{RightBoundary\}\(D,\\mathcal\{S\},c,t,q\+1,U,\\Delta\)
23:

ℛexcluded\.PruneInterval​\(ℓ\+1,r−1\)\\mathcal\{R\}\_\{\\textrm\{excluded\}\}\.\\textsc\{PruneInterval\}\(\\ell\+1,r\-1\)\{Prune the neighborhood that can’t improve within budget\}

24:endif

25:endfor

26:

Q←ℛexcluded\.Complement​\(L,U\)Q\\leftarrow\\mathcal\{R\}\_\{\\textrm\{excluded\}\}\.\\textsc\{Complement\}\(L,U\)\{Return intervals of active thresholds that still require exploration\.\}

27:return

\(E,L,U,Q\)\(E,L,U,Q\)

Algorithm 3EnumContFeature\(GG,DD,cc,dd,γ\\gamma,εabs\\varepsilon\_\{\\textrm\{abs\}\},𝒮\)\\mathcal\{S\}\)0:Current OR node

GG, subproblem

DD, continuous feature identifier

cc, depth

dd, budget

εabs\\varepsilon\_\{\\textrm\{abs\}\}, and threshold registry

𝒮\\mathcal\{S\}
1:

\(E,L,U,Q\)←InitAndPrune​\(G,D,c,d,γ,εabs,𝒮\)\\begin\{aligned\} \(E,L,U,Q\)\\leftarrow\{\}&\\textsc\{InitAndPrune\}\(G,D,c,d,\\gamma,\\varepsilon\_\{\\textrm\{abs\}\},\\mathcal\{S\}\)\\end\{aligned\}
2:\{Explore the remaining intervals\}

3:while

Q≠∅Q\\neq\\emptysetdo

4:

\[i,j\]←Q\.Pop​\(\)\[i,j\]\\leftarrow Q\.\\textsc\{Pop\}\(\)\{The endpoints are active threshold positions\}

5:

i←max⁡\{i,L\}i\\leftarrow\\max\\\{i,L\\\};

j←min⁡\{j,U\}j\\leftarrow\\min\\\{j,U\\\}
6:if

i\>ji\>jthen

7:continue

8:endif

9:

m←⌊\(i\+j\)/2⌋m\\leftarrow\\lfloor\(i\+j\)/2\\rfloor\{See Appendix[A\.4](https://arxiv.org/html/2608.04310#A1.SS4)\. We evaluate the midpoint, update

EEand

𝒮\\mathcal\{S\}by reference, tighten

LLand

UU, and prune and/or enqueue parts of the interval \(into

QQ\)\}

10:

\(L,U\)←ProcessInterval\(G,D,c,d,γ,εabs,𝒮,E,Q,L,U,i,j,m\)\\begin\{aligned\} \(L,U\)\\leftarrow\{\}&\\textsc\{ProcessInterval\}\(G,D,c,d,\\gamma,\\\\ &\\qquad\\varepsilon\_\{\\textrm\{abs\}\},\\mathcal\{S\},E,Q,L,U,i,j,m\)\\end\{aligned\}
11:endwhile

Given a failed threshold,RightBoundarysearches through the active thresholds to its right and returns the first whose distance from the failed threshold is at leastΔ\\Delta\. If no such threshold exists within the search interval, it returns the position immediately beyond the interval\.LeftBoundarysearches to the left symmetrically\.

These routines implement the pruning implied by this assumption: if changing the branch assignment ofkksamples can change the proxy\-completed objective by at mostkk, then any threshold within distance less thanΔ\\Deltaof a failed threshold must also exceed the budget\. Accordingly, the routines move the interval endpoints just past all such thresholds\. This pruning is exact for any proxy satisfying the assumption, including an optimal proxy over all thresholds or any subset of thresholds, as well as a proxy that simply predicts the majority\-class leaf\. These routines can be implemented by binary search, becausedistD\\mathrm\{dist\}\_\{D\}is monotone when one threshold is fixed, and each distance computation can stop as soon asΔ\\Deltadiffering active samples have been found\.

After line 23, we have now exhausted all of the information we have cached about the subproblem\. We return a queue of the remaining intervals to explore, formed by taking the complement of the intervals that have already been pruned or re\-evaluated \(within the bounds for thresholds\)\. Algorithm[3](https://arxiv.org/html/2608.04310#alg3)processes this queue of intervals, evaluating the midpoint threshold of each interval as it is popped\.ProcessIntervalevaluates the midpoint threshold and its proxy completions\. If the proxy\-completed objective is within budget, it adds the split and requeues the neighboring left and right subintervals; otherwise, it applies the interval\-pruning rules described above\.

#### Proxy Algorithms with Continuous Features

In Appendix[C\.1](https://arxiv.org/html/2608.04310#A3.SS1), we describe our modifications to LicketySPLIT\(Babbaret al\.[2025](https://arxiv.org/html/2608.04310#bib.bib105)\)for continuous features, creating LicketySNIP\. We use interval\-pruning techniques similar to those in Algorithms[2](https://arxiv.org/html/2608.04310#alg2)and[3](https://arxiv.org/html/2608.04310#alg3)that are valid for optimal completions, but we apply them to greedy completions\. We also discuss modifications to the greedy subroutine so that consecutive thresholds can be evaluated efficiently\(Quinlan[2014](https://arxiv.org/html/2608.04310#bib.bib18)\)\.

#### Improvements without Caching\.

In Appendix[C\.2](https://arxiv.org/html/2608.04310#A3.SS2), we describe algorithmic improvements when not caching proxy solutions\. For example, once the Rashomon sets for the two children of a split have been computed, their minimum objectives can seed the iterative budget refinement for neighboring splits, allowing us to bypass the proxy\-pruning test with provably no loss in quality \(and a possible gain in quality\)\.

#### Further Approximation with Proxy Algorithms\.

Although the proxy could also operate over continuous thresholds, restricting it to a fixed binarization still provides theoretical guarantees relative to existing Rashomon set algorithms that require binarization\. In particular, if the proxy is optimal over the fixed binarization, then Algorithm[1](https://arxiv.org/html/2608.04310#alg1)recovers a superset of the trees returned by any method that enumerates the Rashomon set over that binarization \(Appendix[B](https://arxiv.org/html/2608.04310#A2)\)\.

#### Anytime Algorithm\.

Algorithm 4AnytimeArborEnum\(d,γ,εmult,ℬproxy\)\(d,\\gamma,\\varepsilon\_\{\\textrm\{mult\}\},\\mathcal\{B\}\_\{\\textrm\{proxy\}\}\)0:Depth budget

dd, per\-leaf penalty

γ\\gamma, Rashomon multiplier

εmult\\varepsilon\_\{\\textrm\{mult\}\}, and sorted list of proxy thresholds

ℬproxy\\mathcal\{B\}\_\{\\textrm\{proxy\}\}
1:

ℬbin←\\mathcal\{B\}\_\{\\textrm\{bin\}\}\\leftarrowsorted list of indices of ordinary binary features

2:

ℬinitial←SortUnique​\(ℬbin∪ℬproxy\)\\mathcal\{B\}\_\{\\textrm\{initial\}\}\\leftarrow\\textsc\{SortUnique\}\(\\mathcal\{B\}\_\{\\textrm\{bin\}\}\\cup\\mathcal\{B\}\_\{\\textrm\{proxy\}\}\)
3:

𝒮root←InitializeThresholdRegistry​\(ℬinitial\)\\mathcal\{S\}\_\{\\textrm\{root\}\}\\leftarrow\\textsc\{InitializeThresholdRegistry\}\(\\mathcal\{B\}\_\{\\textrm\{initial\}\}\)\{Initialize the active thresholds and continuous\-feature bounds \(no restrictions yet\)\}

4:

Droot←D\_\{\\textrm\{root\}\}\\leftarrowthe bitvector containing all training samples

5:Restrict proxy algorithms to

ℬproxy\\mathcal\{B\}\_\{\\textrm\{proxy\}\}
6:

εabs←\(1\+εmult\)​Proxy​\(Droot,d,γ,𝒮root\)\\varepsilon\_\{\\textrm\{abs\}\}\\leftarrow\(1\+\\varepsilon\_\{\\textrm\{mult\}\}\)\\textsc\{Proxy\}\(D\_\{\\textrm\{root\}\},d,\\gamma,\\mathcal\{S\}\_\{\\textrm\{root\}\}\)\{Initialize the root budget\}

7:\{Initially solve using a small set of active thresholds\}

8:

G←ArborEnum​\(G,Droot,d,γ,εabs,𝒮root\)\\begin\{aligned\} G\\leftarrow\{\}&\\textsc\{ArborEnum\}\(G,D\_\{\\textrm\{root\}\},d,\\gamma,\\varepsilon\_\{\\textrm\{abs\}\},\\mathcal\{S\}\_\{\\textrm\{root\}\}\)\\end\{aligned\}
9:whilenot

AllThresholdsActive​\(𝒮root\)\\textsc\{AllThresholdsActive\}\(\\mathcal\{S\}\_\{\\textrm\{root\}\}\)do

10:

ℬnew←SelectNewThresholds​\(𝒮root\)\\mathcal\{B\}\_\{\\textrm\{new\}\}\\leftarrow\\textsc\{SelectNewThresholds\}\(\\mathcal\{S\}\_\{\\textrm\{root\}\}\)\{By default, select one threshold from each gap between adjacent active thresholds\}

11:

ActivateThresholds​\(𝒮root,ℬnew\)\\textsc\{ActivateThresholds\}\(\\mathcal\{S\}\_\{\\textrm\{root\}\},\\mathcal\{B\}\_\{\\textrm\{new\}\}\)\{Update the threshold registry by reference\}

12:Clear

ℐG\\mathcal\{I\}\_\{G\}\{Cached subgraphs may be incomplete for the expanded active threshold set\}

13:

𝒱←∅\\mathcal\{V\}\\leftarrow\\emptyset\{Track graph nodes visited during this refinement pass\}

14:

RefineGraph​\(G,Droot,d,𝒮root,𝒱\)\\textsc\{RefineGraph\}\(G,D\_\{\\textrm\{root\}\},d,\\mathcal\{S\}\_\{\\textrm\{root\}\},\\mathcal\{V\}\)\{Extend the graph to include newly active thresholds when feasible\}

15:endwhile

16:whilenot

IsProxyOptimal​\(Proxy\)\\textsc\{IsProxyOptimal\}\(\\textsc\{Proxy\}\)do

17:Increase proxy strength by

11and update caches \{See Appendix[C\.1](https://arxiv.org/html/2608.04310#A3.SS1)\}

18:

𝒱←∅\\mathcal\{V\}\\leftarrow\\emptyset
19:

RefineGraph​\(G,Droot,d,𝒮root,𝒱\)\\textsc\{RefineGraph\}\(G,D\_\{\\textrm\{root\}\},d,\\mathcal\{S\}\_\{\\textrm\{root\}\},\\mathcal\{V\}\)\{Revisit the graph using the stronger proxy to recover falsely pruned splits\}

20:endwhile

21:return

GG

Table 1:Runtime on datasets using fully\-continuous features \(i\.e\., for existing methods, binarizing between every pair of unique values for each feature\)\.d=5;λ=0\.02;ε=0\.03d=5;\\lambda=0\.02;\\varepsilon=0\.03\. Time is reported by rounding to the nearest second\. The approximate algorithms are shown inbold, along with the best runtime among them for each dataset; likewise, the optimal algorithms and the best runtime among them areunderlined\. Mean and standard deviation are shown across 3 bootstraps\. The number after each dataset name is∑j\(uj−1\)\\sum\_\{j\}\(u\_\{j\}\-1\), whereuju\_\{j\}is the number of unique values of featurejj\. Results for all datasets are shown in Appendix[E\.2](https://arxiv.org/html/2608.04310#A5.SS2)\. – runs exceed 100\-hours or 128GB memory on at least one bootstrap\. \)\.LSR = LicketySPLIT\-Restricted; SNIP = LicketySNIP; SNIP\+GR = LicketySNIP with greedy restricted to a small binarization; OPT = optimal proxy\.

AnytimeArborEnum\(Algorithm[4](https://arxiv.org/html/2608.04310#alg4)\) starts from a coarse threshold set and progressively activates additional thresholds, thereby reducing the covering radius of the active thresholds relative to all thresholds and, consequently, the discretization\-induced optimality gap\. We present the simpler case in which the proxy remains restricted to the initial binarization \(ℬproxy\\mathcal\{B\}\_\{\\textrm\{proxy\}\}\), preserving the aforementioned guarantee relative to existing methods on the binarization\. More generally, the proxy may access all thresholds\. In this setting, whenever the proxy selects a split at a subproblem, we add that split to the subproblem’s active threshold set, ensuring that every proxy\-certified tree remains recoverable \(additional details in Appendix[A\.8](https://arxiv.org/html/2608.04310#A1.SS8)\)\. This variant is truly anytime: it can begin with no active continuous thresholds and, as the proxy is strengthened to optimality, converges to the complete continuous\-feature Rashomon set\. We discuss proxy strength further in Appendix[C\.1](https://arxiv.org/html/2608.04310#A3.SS1)\. In practice, this final step is optional, since our proxy algorithms attain near\-perfect recall \(Table[2](https://arxiv.org/html/2608.04310#S4.T2)\)\.

The initial pass runs Algorithm[1](https://arxiv.org/html/2608.04310#alg1)over an initial set of splits\. This call returns a minimum\-objective AND/OR graph; objective histograms are not populated until the algorithm terminates, since they will become stale\. Subsequent rounds activate new thresholds and callRefineGraph\(Appendix[A\.6](https://arxiv.org/html/2608.04310#A1.SS6)\) to update the graph\. For each existing split,RefineGraphrecursively refines its children, then performs iterative budget refinement, as new splits may improve a child’s minimum objective\.

## 4Evaluation

We organize our evaluation around three research questions:1\) Exact:when can we compute exact Rashomon sets on continuous features,2\) Approximate:can our approximations accurately recover the Rashomon set while substantially expanding the range of problems for which Rashomon sets can be computed efficiently, and3\) Anytime:can our anytime algorithm produce useful intermediate Rashomon sets while incurring minimal overhead when run to completion\. We use 20 datasets that have at least one continuous feature; additional experimental details are available in Appendix[E\.1](https://arxiv.org/html/2608.04310#A5.SS1)\. All methods are given a 100\-hour timeout and 128GB of memory to compute a Rashomon set for one bootstrap of a dataset, except for our anytime algorithms, which we gave a 24\-hour timeout and 32GB of memory\. We parameterize the leaf penalty asγ=round​\(λ​\|D\|\)\\gamma=\\mathrm\{round\}\(\\lambda\|D\|\), and chooseλ\\lambda\.

#### Runtime\.

Table[1](https://arxiv.org/html/2608.04310#S3.T1)compares our methods \(with different proxy algorithms\) to existing methods in terms of runtime across datasets\. Memory usage is shown in Appendix[E\.2](https://arxiv.org/html/2608.04310#A5.SS2); we are more memory\-efficient than existing methods on almost all datasets\. We report additional values ofλ\\lambdain Appendix[E\.2](https://arxiv.org/html/2608.04310#A5.SS2)\. We consider four proxies: an optimal decision tree algorithm obtained by extending LicketySNIP to higher lookaheads, LicketySNIP \(SNIP\), LicketySNIP with the greedy subroutine restricted to a small binarization \(SNIP\+GR\), and LicketySPLIT run directly on the small binarization \(LSR\)\. The binarization for LSR and SNIP\+GR is obtained from thresholds selected by a gradient\-boosted tree ensemble\. The four existing methods are given fully exhaustive binarizations, with thresholds placed between every pair of unique values for each continuous feature, so that they can enumerate the continuous\-feature Rashomon set exactly\. On Bike \(which had the fewest binary features by far\), our optimal method finishes63×63\\timesfaster than SORTeD, the only optimal method to finish; TreeFARMS did not finish\.

![Refer to caption](https://arxiv.org/html/2608.04310v1/7anytimedatasets.png)Figure 2:Anytime algorithm on 8 real\-world datasets\. We display three quantities about the Rashomon set at each stopping point: number of trees, the number of features present in the Rashomon set \(any of the splits from a continuous feature counts as one feature\), and the number of samples that receive conflicting predictions from Rashomon set members\. The curve for a given dataset is normalized by its maximum value\.d=5;λ=0\.005;ε=0\.015d=5;\\lambda=0\.005;\\varepsilon=0\.015\.
#### Approximation Quality\.

Table 2:Recall summary across 20 datasets with fully continuous features, relative to the best method that finished\. Entries are mean±\\pmstandard deviation across 3 bootstraps\. Individual results appear in Appendix[E\.2](https://arxiv.org/html/2608.04310#A5.SS2)\.d=5d=5andε=0\.03\\varepsilon=0\.03\.Bold:\>0\.99\>0\.99;underline:\>0\.98\>0\.98\.Table[2](https://arxiv.org/html/2608.04310#S4.T2)shows that using LicketySNIP as the proxy \(with or without restricting the greedy subroutine to a smaller binarization, middle and right columns\) achieves nearly\-perfect recall across all datasets, while remaining substantially faster than the optimal proxy\. The worst\-case across all 20 datasets and threeλ\\lambdavalues is still≥94\.5%\\geq 94\.5\\%\. Restricting further to LicketySPLIT over a binarization \(left column\) is sometimes faster \(and sometimes slower\) but can incur moderate recall loss on several datasets\. Overall, LicketySNIP\+GR offers the best tradeoff for users willing to sacrifice some recall; when perfect recall and a certificate of optimality are required, the optimal proxy should be used\.

#### Extending the Root Budget\.

Table 3:For every dataset on which ArborEnum\+SNIP\+GR does not achieve perfect recall \(averaged across bootstraps\), extending the root budget recovers the remaining trees with little additional runtime while remaining substantially faster than our optimal method\. The timings are obtained by first solving withεmult=0\.03\\varepsilon\_\{\\textrm\{mult\}\}=0\.03and then extending the subgraph\.λ=0\.005\\lambda=0\.005;λ=0\.01\\lambda=0\.01is shown in Appendix[E\.4](https://arxiv.org/html/2608.04310#A5.SS4)\.Because our subgraphs can be extended to a larger budget without repeating the subgraph computation, we can improve an approximate Rashomon set by repeatedly increasing the root budget without restarting the computation\. SORTeD is an anytime algorithm in the root budgetεabs\\varepsilon\_\{\\textrm\{abs\}\}, and such anytime algorithms have not been created previously for approximation algorithms\. Table[3](https://arxiv.org/html/2608.04310#S4.T3)shows that loosening the root budget can recover the remaining trees with limited additional runtime\.

This capability is useful in workflows where many candidate Rashomon sets are computed during development: after comparing them, a user can select one and invest additional computation to improve its approximation quality\. Likewise, this capability can facilitate the selection ofεmult\\varepsilon\_\{\\textrm\{mult\}\}: the graph can be extended incrementally across increasingly large values until a desired stopping criterion is reached\.

#### Adding Thresholds Anytime\.

Figure[2](https://arxiv.org/html/2608.04310#S4.F2)shows one variant of the anytime algorithm \(stopping when all thresholds are added; not increasing proxy strength\)\. We use LicketySNIP as a fully continuous proxy \(for simplicity, we don’t restrict greedy to a binarization\)\. Enumeration begins without considering any continuous\-feature thresholds and adds them over time\. Each point enumerates the Rashomon set over a binarization of increasing complexity \(possibly with some proxy thresholds included\)\. The results show that a coarse binarization provides an incomplete view of the Rashomon set over all thresholds\. As the binarization is refined, downstream properties converge more quickly than does the number of trees: important features are typically identified early, although some datasets continue to gain features late in the run, while predictive multiplicity converges more slowly\. Ideally, enumeration would always run to completion, but this is often infeasible\. This flexibility of early\-stopping comes at little additional cost: relative to running the corresponding non\-anytime algorithm on the final set of thresholds, the anytime procedure incurs a median runtime overhead of only 2\.7%\. Thus, the anytime variant can replace our non\-anytime algorithms, running to completion when feasible and stopping early when necessary\.

## 5Conclusion

We introduced ArborEnum, a framework for enumerating decision\-tree Rashomon sets using continuous features\. ArborEnum provides exact, approximate, and anytime algorithms, allowing practitioners to choose an approach suited to their computational constraints\. By combining continuous\-threshold pruning with budget\-independent subgraphs, our methods improve scalability without coarse binarization, while the anytime algorithm progressively considers more splits as time permits\. Future work could extend our algorithms to Rashomon sets of piecewise\-constant or piecewise\-linear regression trees or modify the pruning to ensure recovery of rule lists\. Another promising direction is to adapt the pruning conditions to obtain theoretical guarantees with respect to Rashomon sets of rule lists\.

## References

- G\. Aglin, S\. Nijssen, and P\. Schaus \(2020\)Learning optimal decision trees using caching branch\-and\-bound search\.InProceedings of the AAAI Conference on Artificial Intelligence,Vol\.34,pp\. 3146–3153\.Cited by:[§2](https://arxiv.org/html/2608.04310#S2.SS0.SSS0.Px1.p2.1)\.
- E\. Arslan, J\. G\. van der Linden, S\. Hoogendoorn, M\. Rinaldi, and E\. Demirović \(2025\)SORTeD Rashomon sets of sparse decision trees: anytime enumeration\.arXiv preprint arXiv:2511\.03344\.Cited by:[Appendix B](https://arxiv.org/html/2608.04310#A2.7.p7.6),[Appendix B](https://arxiv.org/html/2608.04310#A2.p1.1),[§1](https://arxiv.org/html/2608.04310#S1.p2.3),[§2](https://arxiv.org/html/2608.04310#S2.SS0.SSS0.Px1.p2.1)\.
- V\. Babbar, H\. McTavish, C\. Rudin, and M\. Seltzer \(2025\)Near\-optimal decision trees in a SPLIT second\.InInternational Conference on Machine Learning,Cited by:[§1](https://arxiv.org/html/2608.04310#S1.p2.3),[§2](https://arxiv.org/html/2608.04310#S2.SS0.SSS0.Px2.p1.1),[§2](https://arxiv.org/html/2608.04310#S2.SS0.SSS0.Px4.p1.1),[§3](https://arxiv.org/html/2608.04310#S3.SS0.SSS0.Px9.p1.1)\.
- M\. Bao, A\. Zhou, A\. S\. Zottola, B\. Brubach, S\. Desmarais, S\. A\. Horowitz, K\. Lum, and S\. Venkatasubramanian \(2021\)It’s compaslicated: the messy relationship between rai datasets and algorithmic fairness benchmarks\.InProceedings of the Thirty\-Fifth Conference on Neural Information Processing Systems \(NeurIPS\),Note:Datasets and Benchmarks Track \(Round 1\)Cited by:[Appendix D](https://arxiv.org/html/2608.04310#A4.SS0.SSS0.Px7.1.1)\.
- B\. Becker and R\. Kohavi \(1996\)Adult\.Note:UCI Machine Learning RepositoryDOI: https://doi\.org/10\.24432/C5XW20Cited by:[Appendix D](https://arxiv.org/html/2608.04310#A4.SS0.SSS0.Px2.1.1)\.
- L\. Breiman \(1984\)Classification and regression trees\.Routledge\.Cited by:[§1](https://arxiv.org/html/2608.04310#S1.p1.1),[§2](https://arxiv.org/html/2608.04310#S2.SS0.SSS0.Px1.p1.1)\.
- N\. R\. Burrows, I\. Hora, L\. S\. Geiss, E\. W\. Gregg, and A\. Albright \(2017\)Incidence of end\-stage renal disease attributed to diabetes among persons with diagnosed diabetes — united states and puerto rico, 2000–2014\.MMWR\. Morbidity and Mortality Weekly Report66\(43\),pp\. 1165–1170\.External Links:[Document](https://dx.doi.org/10.15585/mmwr.mm6643a2),[Link](https://doi.org/10.15585/mmwr.mm6643a2)Cited by:[Appendix D](https://arxiv.org/html/2608.04310#A4.SS0.SSS0.Px10.1.1)\.
- A\. Chaouki, J\. Read, and A\. Bifet \(2025\)Branches: efficiently seeking optimal sparse decision trees via ao\.InForty\-second International Conference on Machine Learning,Cited by:[§2](https://arxiv.org/html/2608.04310#S2.SS0.SSS0.Px1.p2.1)\.
- M\. Ciaperoni, H\. Xiao, and A\. Gionis \(2024\)Efficient exploration of the Rashomon set of rule\-set models\.InProceedings of the 30th ACM SIGKDD Conference on Knowledge Discovery and Data Mining \(KDD 2024\),Barcelona, Spain,pp\. 478–489\.External Links:[Document](https://dx.doi.org/10.1145/3637528.3671818)Cited by:[§1](https://arxiv.org/html/2608.04310#S1.p2.3)\.
- P\. Cortez and A\. M\. G\. Silva \(2008\)Using data mining to predict secondary school student performance\.External Links:[Link](https://api.semanticscholar.org/CorpusID:16621299)Cited by:[Appendix D](https://arxiv.org/html/2608.04310#A4.SS0.SSS0.Px19.1.1)\.
- P\. Cortez \(2008\)Student Performance\.Note:UCI Machine Learning RepositoryDOI: https://doi\.org/10\.24432/C5TG7TCited by:[Appendix D](https://arxiv.org/html/2608.04310#A4.SS0.SSS0.Px19.1.1)\.
- E\. Demirović, A\. Lukina, E\. Hebrard, J\. Chan, J\. Bailey, C\. Leckie, K\. Ramamohanarao, and P\. J\. Stuckey \(2022\)Murtree: optimal decision trees via dynamic programming and search\.Journal of Machine Learning Research23\(26\),pp\. 1–47\.Cited by:[§2](https://arxiv.org/html/2608.04310#S2.SS0.SSS0.Px1.p2.1)\.
- J\. Donnelly, Z\. Guo, A\. J\. Barnett, H\. McTavish, C\. Chen, and C\. Rudin \(2025\)Rashomon sets for prototypical\-part networks: editing interpretable models in real\-time\.In2025 IEEE/CVF Conference on Computer Vision and Pattern Recognition \(CVPR\),Vol\.,pp\. 4528–4538\.External Links:[Document](https://dx.doi.org/10.1109/CVPR52734.2025.00427)Cited by:[§1](https://arxiv.org/html/2608.04310#S1.p2.3)\.
- N\. Erickson, L\. Purucker, A\. Tschalzev, D\. Holzmüller, P\. M\. Desai, D\. Salinas, and F\. Hutter \(2025\)TabArena: a living benchmark for machine learning on tabular data\.External Links:2506\.16791,[Link](https://arxiv.org/abs/2506.16791)Cited by:[Appendix D](https://arxiv.org/html/2608.04310#A4.SS0.SSS0.Px6.1.1)\.
- H\. Fanaee\-T and J\. Gama \(2013\)Event labeling combining ensemble detectors and background knowledge\.Progress in Artificial Intelligence2,pp\. 113 – 127\.External Links:[Link](https://api.semanticscholar.org/CorpusID:256282956)Cited by:[Appendix D](https://arxiv.org/html/2608.04310#A4.SS0.SSS0.Px5.1.1)\.
- H\. Fanaee\-T \(2013\)Bike Sharing\.Note:UCI Machine Learning RepositoryDOI: https://doi\.org/10\.24432/C5W894Cited by:[Appendix D](https://arxiv.org/html/2608.04310#A4.SS0.SSS0.Px5.1.1)\.
- FICO \(2018\)Home equity line of credit \(heloc\) dataset\.FICO\.Note:FICO Explainable Machine Learning ChallengeExternal Links:[Link](https://community.fico.com/s/explainable-machine-learning-challenge)Cited by:[Appendix D](https://arxiv.org/html/2608.04310#A4.SS0.SSS0.Px13.1.1)\.
- A\. Fisher, C\. Rudin, and F\. Dominici \(2019\)All models are wrong, but many are useful: learning a variable’s importance by studying an entire class of prediction models simultaneously\.Journal of Machine Learning Research20\(177\),pp\. 1–81\.External Links:[Link](http://jmlr.org/papers/v20/18-760.html)Cited by:[§1](https://arxiv.org/html/2608.04310#S1.p1.1)\.
- I\. Guyon, L\. Sun\-Hosoya, M\. Boullé, H\. J\. Escalante, S\. Escalera, Z\. Liu, D\. Jajetic, B\. Ray, M\. Saeed, M\. Sebag, A\. Statnikov, W\. Tu, and E\. Viegas \(2019\)Analysis of the automl challenge series 2015\-2018\.InAutoML,Springer series on Challenges in Machine Learning\.External Links:[Link](https://www.automl.org/wp-content/uploads/2018/09/chapter10-challenge.pdf)Cited by:[Appendix D](https://arxiv.org/html/2608.04310#A4.SS0.SSS0.Px12.1.1),[Appendix D](https://arxiv.org/html/2608.04310#A4.SS0.SSS0.Px14.1.1)\.
- Z\. Heile, H\. McTavish, V\. Babbar, M\. Seltzer, and C\. Rudin \(2026\)Efficient rashomon set approximation for decision trees\.InForty\-third International Conference on Machine Learning,External Links:[Link](https://openreview.net/forum?id=Sgwd0l1u2V)Cited by:[§A\.1](https://arxiv.org/html/2608.04310#A1.SS1.SSS0.Px1.p1.1),[§A\.10](https://arxiv.org/html/2608.04310#A1.SS10.p8.4),[§A\.5](https://arxiv.org/html/2608.04310#A1.SS5.p1.2),[§A\.5](https://arxiv.org/html/2608.04310#A1.SS5.p2.1),[§A\.7](https://arxiv.org/html/2608.04310#A1.SS7.p3.2),[§A\.9](https://arxiv.org/html/2608.04310#A1.SS9.p4.1),[Appendix B](https://arxiv.org/html/2608.04310#A2.14.p3.5),[Appendix B](https://arxiv.org/html/2608.04310#A2.7.p7.6),[Appendix B](https://arxiv.org/html/2608.04310#A2.p3.1),[Appendix B](https://arxiv.org/html/2608.04310#A2.p7.2),[§C\.1](https://arxiv.org/html/2608.04310#A3.SS1.p3.5),[§C\.1](https://arxiv.org/html/2608.04310#A3.SS1.p9.1),[§C\.2](https://arxiv.org/html/2608.04310#A3.SS2.p2.1),[Appendix D](https://arxiv.org/html/2608.04310#A4.p3.1),[Table 22](https://arxiv.org/html/2608.04310#A5.T22),[Table 24](https://arxiv.org/html/2608.04310#A5.T24.5.1.1.5),[Table 25](https://arxiv.org/html/2608.04310#A5.T25.5.1.1.5),[Table 26](https://arxiv.org/html/2608.04310#A5.T26.5.1.1.5),[Table 27](https://arxiv.org/html/2608.04310#A5.T27.5.1.1.5),[Table 28](https://arxiv.org/html/2608.04310#A5.T28.5.1.1.5),[§1](https://arxiv.org/html/2608.04310#S1.p2.3),[§2](https://arxiv.org/html/2608.04310#S2.SS0.SSS0.Px1.p2.1),[§2](https://arxiv.org/html/2608.04310#S2.SS0.SSS0.Px4.p1.1),[§3](https://arxiv.org/html/2608.04310#S3.SS0.SSS0.Px2.p1.1),[§3](https://arxiv.org/html/2608.04310#S3.SS0.SSS0.Px3.p1.1),[Theorem 3](https://arxiv.org/html/2608.04310#Thmtheorem3.p1.4.4)\.
- M\. Hopkins, E\. Reeber, G\. Forman, and J\. Suermondt \(1999\)Spambase\.Note:UCI Machine Learning RepositoryDOI: https://doi\.org/10\.24432/C53G6XCited by:[Appendix D](https://arxiv.org/html/2608.04310#A4.SS0.SSS0.Px18.1.1)\.
- X\. Hu, C\. Rudin, and M\. Seltzer \(2019\)Optimal sparse decision trees\.InAdvances in Neural Information Processing Systems,Vol\.32,pp\. 7265–7273\.Cited by:[§1](https://arxiv.org/html/2608.04310#S1.p2.3),[§2](https://arxiv.org/html/2608.04310#S2.SS0.SSS0.Px1.p2.1)\.
- \[23\]\(2017\)In\-Vehicle Coupon Recommendation\.Note:UCI Machine Learning RepositoryDOI: https://doi\.org/10\.24432/C5GS4PCited by:[Appendix D](https://arxiv.org/html/2608.04310#A4.SS0.SSS0.Px8.1.1)\.
- H\. Kiossou, P\. Schaus, and S\. Nijssen \(2026\)Anytime optimal decision tree learning with continuous features\.arXiv preprint arXiv:2601\.14765\.Cited by:[§2](https://arxiv.org/html/2608.04310#S2.SS0.SSS0.Px3.p1.1)\.
- J\. Lin, C\. Zhong, D\. Hu, C\. Rudin, and M\. Seltzer \(2020\)Generalized and scalable optimal sparse decision trees\.InInternational Conference on Machine Learning,pp\. 6150–6160\.Cited by:[§2](https://arxiv.org/html/2608.04310#S2.SS0.SSS0.Px1.p2.1)\.
- P\. N\. Malani, J\. Kullgren, and E\. Solway \(2019\)National poll on healthy aging \(npha\), united states, april 2017\.Inter\-university Consortium for Political and Social Research\.Note:DistributorExternal Links:[Document](https://dx.doi.org/10.3886/ICPSR37305.v1),[Link](https://doi.org/10.3886/ICPSR37305.v1)Cited by:[Appendix D](https://arxiv.org/html/2608.04310#A4.SS0.SSS0.Px3.1.1)\.
- G\. A\. Marcoulides \(2005\)Discovering knowledge in data: an introduction to data mining\.Wiley\.Note:Churn datasetCited by:[Appendix D](https://arxiv.org/html/2608.04310#A4.SS0.SSS0.Px6.1.1)\.
- R\. Mazumder, X\. Meng, and H\. Wang \(2022\)Quant\-BnB: a scalable branch\-and\-bound method for optimal decision trees with continuous features\.InInternational Conference on Machine Learning,Vol\.162,pp\. 15255–15277\.Cited by:[§2](https://arxiv.org/html/2608.04310#S2.SS0.SSS0.Px3.p1.1)\.
- H\. McTavish, C\. Zhong, R\. Achermann, I\. Karimalis, J\. Chen, C\. Rudin, and M\. Seltzer \(2022\)Fast sparse decision tree optimization via reference ensembles\.InProceedings of the AAAI Conference on Artificial Intelligence,Vol\.36,pp\. 9604–9613\.Cited by:[§E\.1](https://arxiv.org/html/2608.04310#A5.SS1.p2.1),[§2](https://arxiv.org/html/2608.04310#S2.SS0.SSS0.Px2.p1.1)\.
- S\. Moro, P\. Rita, and P\. Cortez \(2014a\)Bank Marketing\.Note:UCI Machine Learning RepositoryDOI: https://doi\.org/10\.24432/C5K306Cited by:[Appendix D](https://arxiv.org/html/2608.04310#A4.SS0.SSS0.Px4.1.1)\.
- S\. Moro, P\. Cortez, and P\. Rita \(2014b\)A data\-driven approach to predict the success of bank telemarketing\.Decis\. Support Syst\.62,pp\. 22–31\.External Links:[Link](https://api.semanticscholar.org/CorpusID:14181100)Cited by:[Appendix D](https://arxiv.org/html/2608.04310#A4.SS0.SSS0.Px4.1.1)\.
- \[32\]\(2017\)National Poll on Healthy Aging \(NPHA\)\.Note:UCI Machine Learning RepositoryDOI: https://doi\.org/10\.3886/ICPSR37305\.v1Cited by:[Appendix D](https://arxiv.org/html/2608.04310#A4.SS0.SSS0.Px3.1.1)\.
- OpenML \(2018a\)Helena dataset\.OpenML\.Note:OpenML Dataset ID 41169; dataset from the ChaLearn Automatic Machine Learning \(AutoML\) ChallengeExternal Links:[Link](https://www.openml.org/d/41169)Cited by:[Appendix D](https://arxiv.org/html/2608.04310#A4.SS0.SSS0.Px12.1.1)\.
- OpenML \(2018b\)Jasmine dataset\.OpenML\.Note:OpenML Dataset ID 41143; dataset from the ChaLearn Automatic Machine Learning \(AutoML\) ChallengeExternal Links:[Link](https://www.openml.org/d/41143)Cited by:[Appendix D](https://arxiv.org/html/2608.04310#A4.SS0.SSS0.Px14.1.1)\.
- OpenML \(2019\)Diamonds dataset\.OpenML\.Note:OpenML Dataset ID 42225; dataset containing prices and attributes of nearly 54,000 diamondsExternal Links:[Link](https://www.openml.org/d/42225)Cited by:[Appendix D](https://arxiv.org/html/2608.04310#A4.SS0.SSS0.Px11.1.1)\.
- OpenML \(2022a\)Abalone dataset\.OpenML\.Note:OpenML Dataset ID 44956; dataset for predicting abalone age from physical measurementsExternal Links:[Link](https://www.openml.org/d/44956)Cited by:[Appendix D](https://arxiv.org/html/2608.04310#A4.SS0.SSS0.Px1.1.1)\.
- OpenML \(2022b\)Pol dataset\.OpenML\.Note:OpenML Dataset ID 44082; dataset used in the tabular data benchmark and derived from a binarized version of the original regression datasetExternal Links:[Link](https://www.openml.org/d/44082)Cited by:[Appendix D](https://arxiv.org/html/2608.04310#A4.SS0.SSS0.Px15.1.1)\.
- OpenML \(2022c\)RL dataset\.OpenML\.Note:OpenML Dataset ID 43949; dataset used in the tabular data benchmark and derived from the ChaLearn AutoML ChallengeExternal Links:[Link](https://www.openml.org/d/43949)Cited by:[Appendix D](https://arxiv.org/html/2608.04310#A4.SS0.SSS0.Px16.1.1)\.
- OpenML \(2025\)Wine dataset\.OpenML\.Note:OpenML Dataset ID 47041External Links:[Link](https://www.openml.org/d/47041)Cited by:[Appendix D](https://arxiv.org/html/2608.04310#A4.SS0.SSS0.Px20.1.1)\.
- J\. R\. Quinlan \(2014\)C4\.5: programs for machine learning\.Elsevier\.Cited by:[§C\.1](https://arxiv.org/html/2608.04310#A3.SS1.p12.8),[§2](https://arxiv.org/html/2608.04310#S2.SS0.SSS0.Px1.p1.1),[§3](https://arxiv.org/html/2608.04310#S3.SS0.SSS0.Px9.p1.1)\.
- C\. Sakar and Y\. Kastro \(2018\)Online Shoppers Purchasing Intention Dataset\.Note:UCI Machine Learning RepositoryDOI: https://doi\.org/10\.24432/C5F88QCited by:[Appendix D](https://arxiv.org/html/2608.04310#A4.SS0.SSS0.Px17.1.1)\.
- C\. O\. Sakar, S\. O\. Polat, M\. Katircioglu, and Y\. Kastro \(2018\)Real\-time prediction of online shoppers’ purchasing intention using multilayer perceptron and lstm recurrent neural networks\.Neural Computing and Applications31,pp\. 6893 – 6908\.External Links:[Link](https://api.semanticscholar.org/CorpusID:13682776)Cited by:[Appendix D](https://arxiv.org/html/2608.04310#A4.SS0.SSS0.Px17.1.1)\.
- C\. Sullivan, M\. Tiwari, and S\. Thrun \(2024\)Maptree: beating “optimal” decision trees with bayesian decision trees\.InProceedings of the AAAI Conference on Artificial Intelligence,Vol\.38,pp\. 9019–9026\.Cited by:[§2](https://arxiv.org/html/2608.04310#S2.SS0.SSS0.Px1.p2.1)\.
- J\. van der Linden, M\. de Weerdt, and E\. Demirović \(2023\)Necessary and sufficient conditions for optimal decision trees using dynamic programming\.InAdvances in Neural Information Processing Systems,Vol\.36,pp\. 9173–9212\.Cited by:[§2](https://arxiv.org/html/2608.04310#S2.SS0.SSS0.Px1.p2.1)\.
- R\. Xin, C\. Zhong, Z\. Chen, T\. Takagi, M\. Seltzer, and C\. Rudin \(2022\)Exploring the whole Rashomon set of sparse decision trees\.InAdvances in Neural Information Processing Systems,Vol\.35,pp\. 14071–14084\.Cited by:[Appendix B](https://arxiv.org/html/2608.04310#A2.7.p7.6),[Appendix B](https://arxiv.org/html/2608.04310#A2.p2.2),[§1](https://arxiv.org/html/2608.04310#S1.p2.3),[§2](https://arxiv.org/html/2608.04310#S2.SS0.SSS0.Px1.p2.1)\.
- I\. Yeh and C\. Lien \(2009\)The comparisons of data mining techniques for the predictive accuracy of probability of default of credit card clients\.Expert Syst\. Appl\.36,pp\. 2473–2480\.External Links:[Link](https://api.semanticscholar.org/CorpusID:15696161)Cited by:[Appendix D](https://arxiv.org/html/2608.04310#A4.SS0.SSS0.Px9.1.1)\.
- I\. Yeh \(2009\)Default of Credit Card Clients\.Note:UCI Machine Learning RepositoryDOI: https://doi\.org/10\.24432/C55S3HCited by:[Appendix D](https://arxiv.org/html/2608.04310#A4.SS0.SSS0.Px9.1.1)\.
- C\. Zhong, Z\. Chen, J\. Liu, M\. Seltzer, and C\. Rudin \(2023\)Exploring and interacting with the set of good sparse generalized additive models\.InAdvances in Neural Information Processing Systems,Cited by:[§1](https://arxiv.org/html/2608.04310#S1.p2.3)\.

## Appendix Contents

Appendix[A](https://arxiv.org/html/2608.04310#A1): Full Algorithms\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.[A](https://arxiv.org/html/2608.04310#A1)

Appendix[A\.1](https://arxiv.org/html/2608.04310#A1.SS1): Implementation\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.[A\.1](https://arxiv.org/html/2608.04310#A1.SS1)

Appendix[A\.2](https://arxiv.org/html/2608.04310#A1.SS2): ArborEnum\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.[A\.2](https://arxiv.org/html/2608.04310#A1.SS2)

Appendix[A\.3](https://arxiv.org/html/2608.04310#A1.SS3): InitAndPrune\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.[A\.3](https://arxiv.org/html/2608.04310#A1.SS3)

Appendix[A\.4](https://arxiv.org/html/2608.04310#A1.SS4): EnumContFeature\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.[A\.4](https://arxiv.org/html/2608.04310#A1.SS4)

Appendix[A\.5](https://arxiv.org/html/2608.04310#A1.SS5): Iterative Budget Refinement\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.[A\.5](https://arxiv.org/html/2608.04310#A1.SS5)

Appendix[A\.6](https://arxiv.org/html/2608.04310#A1.SS6): RefineGraph\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.[A\.6](https://arxiv.org/html/2608.04310#A1.SS6)

Appendix[A\.7](https://arxiv.org/html/2608.04310#A1.SS7): AddOrExtendSplit\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.[A\.7](https://arxiv.org/html/2608.04310#A1.SS7)

Appendix[A\.8](https://arxiv.org/html/2608.04310#A1.SS8): Anytime Algorithm\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.[A\.8](https://arxiv.org/html/2608.04310#A1.SS8)

Appendix[A\.9](https://arxiv.org/html/2608.04310#A1.SS9): Additional Methods\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.[A\.9](https://arxiv.org/html/2608.04310#A1.SS9)

Appendix[A\.10](https://arxiv.org/html/2608.04310#A1.SS10): AND/OR Graph Caching\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.[A\.10](https://arxiv.org/html/2608.04310#A1.SS10)

Appendix[B](https://arxiv.org/html/2608.04310#A2): Theoretical Results\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.[B](https://arxiv.org/html/2608.04310#A2)

Theorem[1](https://arxiv.org/html/2608.04310#Thmtheorem1): Distinct Budgets for One Subproblem\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.[1](https://arxiv.org/html/2608.04310#Thmtheorem1)

Theorem[2](https://arxiv.org/html/2608.04310#Thmtheorem2): Distinct Objectives for One Subproblem\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.[2](https://arxiv.org/html/2608.04310#Thmtheorem2)

Theorem[3](https://arxiv.org/html/2608.04310#Thmtheorem3): Factorial Path Duplication\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.[3](https://arxiv.org/html/2608.04310#Thmtheorem3)

Theorem[4](https://arxiv.org/html/2608.04310#Thmtheorem4): Binarization Optimality Gap\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.[4](https://arxiv.org/html/2608.04310#Thmtheorem4)

Theorem[5](https://arxiv.org/html/2608.04310#Thmtheorem5): Selecting Thresholds with Covering Radius Guarantee\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.[5](https://arxiv.org/html/2608.04310#Thmtheorem5)

Theorem[6](https://arxiv.org/html/2608.04310#Thmtheorem6): Optimality Gap induced by Threshold\-Selection\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.[6](https://arxiv.org/html/2608.04310#Thmtheorem6)

Theorem[7](https://arxiv.org/html/2608.04310#Thmtheorem7): Number of Thresholds for some Covering Radius\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.[7](https://arxiv.org/html/2608.04310#Thmtheorem7)

Theorem[8](https://arxiv.org/html/2608.04310#Thmtheorem8): Quantile Snapping Bound\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.[8](https://arxiv.org/html/2608.04310#Thmtheorem8)

Theorem[9](https://arxiv.org/html/2608.04310#Thmtheorem9): Midpoint Refinement Halves Covering Radius\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.[9](https://arxiv.org/html/2608.04310#Thmtheorem9)

Theorem[10](https://arxiv.org/html/2608.04310#Thmtheorem10): Fixed\-Binarization Superset Guarantee\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.[10](https://arxiv.org/html/2608.04310#Thmtheorem10)

Appendix[C](https://arxiv.org/html/2608.04310#A3): Proxy Algorithms\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.[C](https://arxiv.org/html/2608.04310#A3)

Appendix[C\.1](https://arxiv.org/html/2608.04310#A3.SS1): LicketySNIP and Proxy Strength\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.[C\.1](https://arxiv.org/html/2608.04310#A3.SS1)

Appendix[C\.2](https://arxiv.org/html/2608.04310#A3.SS2): Improvements without Proxy Caching\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.[C\.2](https://arxiv.org/html/2608.04310#A3.SS2)

Theorem[11](https://arxiv.org/html/2608.04310#Thmtheorem11): Neighboring\-Threshold Pruning\-Test\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.[11](https://arxiv.org/html/2608.04310#Thmtheorem11)

Appendix[D](https://arxiv.org/html/2608.04310#A4): Datasets\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.[D](https://arxiv.org/html/2608.04310#A4)

Appendix[E](https://arxiv.org/html/2608.04310#A5): Experiments\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.[E](https://arxiv.org/html/2608.04310#A5)

Appendix[E\.1](https://arxiv.org/html/2608.04310#A5.SS1): Computational Resources\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.[E\.1](https://arxiv.org/html/2608.04310#A5.SS1)

Appendix[E\.2](https://arxiv.org/html/2608.04310#A5.SS2): Timing, Memory, and Recall\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.[E\.2](https://arxiv.org/html/2608.04310#A5.SS2)

Appendix[E\.3](https://arxiv.org/html/2608.04310#A5.SS3): Anytime Overhead\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.[E\.3](https://arxiv.org/html/2608.04310#A5.SS3)

Appendix[E\.4](https://arxiv.org/html/2608.04310#A5.SS4): Improving Recall with a Bigger Budget\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.[E\.4](https://arxiv.org/html/2608.04310#A5.SS4)

Appendix[E\.5](https://arxiv.org/html/2608.04310#A5.SS5): Budget\-Independent Subgraphs\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.[E\.5](https://arxiv.org/html/2608.04310#A5.SS5)

## Appendix AFull Algorithms

This appendix gives the full pseudocode for the algorithms described in the main text\.

### A\.1Implementation

#### Subproblem representation\.

We represent each subproblemDDas a bitvector over the training samples, with one bit indicating whether each sample is active in the subproblem\. Bitvectors are stored as arrays of 64\-bit words, so intersections, differences, and sample counts can be computed efficiently using bitwise operations and popcount\. Feature columns and class\-label indicators are represented in the same way\. To reduce memory usage, we identify each cached subproblem by a 64\-bit fingerprint of its bitvector together with its remaining depth; this mapping is not strictly injective, but the probability of a collision over the bitvectors encountered \(with the same remaining depth\) in a run is astronomically small\(Heileet al\.[2026](https://arxiv.org/html/2608.04310#bib.bib156)\)\.

### A\.2ArborEnum

Algorithm[1](https://arxiv.org/html/2608.04310#alg1)gives the completeArborEnumprocedure\. Here, we expand the two helper routines that handle feasible prediction leaves and ordinary binary features\. Continuous features are handled byEnumContFeature\(Algorithm[3](https://arxiv.org/html/2608.04310#alg3)\), and feasible splits are materialized or extended byAddOrExtendSplit\(Algorithm[16](https://arxiv.org/html/2608.04310#alg16)\)\.

#### Feasible leaves\.

For each class label,AddFeasibleLeavescomputes the objective of the corresponding prediction leaf and adds it when it is within the current budget\. Because a cached subgraph may already contain leaves found under a smaller budget, the routine adds only leaves that are not already stored inGG\.

Algorithm 5AddFeasibleLeaves\(G,D,γ,εabs\)\(G,D,\\gamma,\\varepsilon\_\{\\textrm\{abs\}\}\)0:Current OR node

GG, subproblem

DD, per\-leaf penalty

γ\\gamma, and budget

εabs\\varepsilon\_\{\\textrm\{abs\}\}
1:foreachclass label

b∈𝒴b\\in\\mathcal\{Y\}do

2:

ℓb←γ\+\|\{\(xi,yi\)∈D:yi≠b\}\|\\ell\_\{b\}\\leftarrow\\gamma\+\\left\|\\\{\(x\_\{i\},y\_\{i\}\)\\in D:y\_\{i\}\\neq b\\\}\\right\|
3:if

ℓb≤εabs\\ell\_\{b\}\\leq\\varepsilon\_\{\\textrm\{abs\}\}and

GGdoes not contain a leaf predicting

bbthen

4:

AddLeaf​\(G,b,ℓb\)\\textsc\{AddLeaf\}\(G,b,\\ell\_\{b\}\)\{Add the newly feasible prediction leaf\}

5:endif

6:endfor

#### Faster leaf implementation\.

Algorithm[5](https://arxiv.org/html/2608.04310#alg5)is written for the general multiclass setting, but its leaf objectives can often be computed more efficiently\. For example, in binary classification, letn=\|D\|n=\|D\|and letn1n\_\{1\}be the number of positive examples inDD\. Thenn0=n−n1n\_\{0\}=n\-n\_\{1\}, so the two possible leaf objectives are obtained from a single class\-count computation: a leaf predicting0has objectiveγ\+n1\\gamma\+n\_\{1\}, whereas a leaf predicting11has objectiveγ\+n0\\gamma\+n\_\{0\}\. WhenDDand the positive\-label set are stored as bitvectors,n1n\_\{1\}can be computed with one bitwise intersection and population count\. Algorithm[6](https://arxiv.org/html/2608.04310#alg6)gives this specialized implementation\.

Algorithm 6AddFeasibleBinaryLeaves\(G,D,γ,εabs\)\(G,D,\\gamma,\\varepsilon\_\{\\textrm\{abs\}\}\)0:Current OR node

GG, subproblem

DD, per\-leaf penalty

γ\\gamma, and budget

εabs\\varepsilon\_\{\\textrm\{abs\}\}
1:

n←\|D\|n\\leftarrow\|D\|
2:

n1←\|D∩Y1\|n\_\{1\}\\leftarrow\|D\\cap Y\_\{1\}\|\{One bitwise intersection and popcount\}

3:

n0←n−n1n\_\{0\}\\leftarrow n\-n\_\{1\}
4:

ℓ0←γ\+n1\\ell\_\{0\}\\leftarrow\\gamma\+n\_\{1\}\{Misclassified positives when predicting

0\}

5:

ℓ1←γ\+n0\\ell\_\{1\}\\leftarrow\\gamma\+n\_\{0\}\{Misclassified negatives when predicting

11\}

6:if

ℓ0≤εabs\\ell\_\{0\}\\leq\\varepsilon\_\{\\textrm\{abs\}\}and

GGdoes not contain a leaf predicting

0then

7:

AddLeaf​\(G,0,ℓ0\)\\textsc\{AddLeaf\}\(G,0,\\ell\_\{0\}\)
8:endif

9:if

ℓ1≤εabs\\ell\_\{1\}\\leq\\varepsilon\_\{\\textrm\{abs\}\}and

GGdoes not contain a leaf predicting

11then

10:

AddLeaf​\(G,1,ℓ1\)\\textsc\{AddLeaf\}\(G,1,\\ell\_\{1\}\)
11:endif

#### Binary features\.

For an ordinary binary featurejj,EnumerateBinarypartitions the current subproblem and ignores the feature if either child is empty\. Otherwise, it computes proxy objectives for the two children\. If their sum is within the parent budget,AddOrExtendSplitconstructs or extends the corresponding child subgraphs using the budget\-refinement procedure described in Appendix[A\.7](https://arxiv.org/html/2608.04310#A1.SS7)\.

Algorithm 7EnumerateBinary\(G,D,j,d,γ,εabs,𝒮\)\(G,D,j,d,\\gamma,\\varepsilon\_\{\\textrm\{abs\}\},\\mathcal\{S\}\)0:Current OR node

GG, subproblem

DD, binary feature

jj, remaining depth

dd, per\-leaf penalty

γ\\gamma, budget

εabs\\varepsilon\_\{\\textrm\{abs\}\}, and threshold registry

𝒮\\mathcal\{S\}
1:

\(DL,DR\)←Partition​\(D,j\)\(D\_\{L\},D\_\{R\}\)\\leftarrow\\textsc\{Partition\}\(D,j\)
2:if

DL=∅D\_\{L\}=\\emptysetor

DR=∅D\_\{R\}=\\emptysetthen

3:return\{The feature is constant on

DD\}

4:endif

5:

PL←Proxy​\(DL,d−1,γ,𝒮\)P\_\{L\}\\leftarrow\\textsc\{Proxy\}\(D\_\{L\},d\-1,\\gamma,\\mathcal\{S\}\)
6:

PR←Proxy​\(DR,d−1,γ,𝒮\)P\_\{R\}\\leftarrow\\textsc\{Proxy\}\(D\_\{R\},d\-1,\\gamma,\\mathcal\{S\}\)
7:if

PL\+PR\>εabsP\_\{L\}\+P\_\{R\}\>\\varepsilon\_\{\\textrm\{abs\}\}then

8:return\{The proxy completion exceeds the parent budget\}

9:endif

10:

AddOrExtendSplit\(G,D,j,d,γ,εabs,𝒮,PL,PR\)\\begin\{aligned\} &\\textsc\{AddOrExtendSplit\}\(G,D,j,d,\\gamma,\\varepsilon\_\{\\textrm\{abs\}\},\\\\ &\\qquad\\mathcal\{S\},P\_\{L\},P\_\{R\}\)\\end\{aligned\}\{Construct or extend the child subgraphs\}

### A\.3InitAndPrune

Algorithm[2](https://arxiv.org/html/2608.04310#alg2)gives the completeInitAndPruneprocedure\. Here, we describe the implementation ofExcludedRangeTracker, which records active threshold positions that have already been explored or pruned\. These positions are indices into the ordered active thresholds of the current continuous feature:0,1,…0,1,\\ldots\. Thus, the tracker operates directly on contiguous active\-position indices and does not require access to the threshold registry𝒮\\mathcal\{S\}\.

The tracker stores disjoint, nonadjacent closed intervals\[a,b\]\[a,b\]in an ordered map implemented as a red\-black tree\. Each tree entry is a pair\(a,b\)\(a,b\), keyed and ordered by its left endpointaa\. This makes it so that predecessor and successor intervals can be found in logarithmic time\. When a new excluded interval is inserted, the tracker merges it with every stored interval that overlaps or touches it\.

MarkExploredexcludes one active threshold position and is implemented as a call toPruneInterval\.PruneIntervalinserts an arbitrary closed interval and restores the invariant that all stored intervals are disjoint and nonadjacent\. Here,Left\(z\) andRight\(z\) denote the left and right endpoints, respectively, of the interval stored at red\-black\-tree entryzz\.

There are two cases to be aware of\.

- •There can be at most one interval to handle whose interval overlaps or touches the new interval on the left \(by the invariant\)\. That is, we merge the contiguous interval that overlaps or touchesℓ\\ell, if it exists\. There cannot be a chain of contiguous intervals by the invariant\.
- •There can be multiple intervals to the right ofℓ\\ellthat become mergeable asrrexpands\. In particular, there may be single indices that all get absorbed by\[ℓ,r\]\[\\ell,r\]\(i\.e\., they are inside the new interval but not contiguous: such as\[2,8\]\[2,8\]having\[4,4\]\[4,4\]and\[6,6\]\[6,6\]inside\)

PruneIntervalfirst checks the interval immediately precedingℓ\\ell, since that is the only earlier interval that could overlap or touch the new interval \(by the invariant\)\. It then scans forward through successor intervals, repeatedly merging any interval whose left endpoint is at mostr\+1r\+1; each merge may increaserr, which can cause the enlarged interval to reach additional successors\. After all overlapping or adjacent intervals have been removed, the routine inserts the single merged interval\[ℓ,r\]\[\\ell,r\]into the red\-black tree\.

Complementscans the intervals from left to right and returns the maximal unexplored intervals within the current search bounds\[L,U\]\[L,U\]\. It scans the stored intervals from left to right while maintainingqq, the first position that has not yet been covered or returned\. That is, we have the invariant that \(at every point in the scan\)qqis the smallest position in\[L,U\]\[L,U\]that has not yet been covered by an excluded interval or added toQQ\. After adding a gap\[q,a−1\]\[q,a\-1\], the updateq←max⁡\{q,b\+1\}q\\leftarrow\\max\\\{q,b\+1\\\}restores the invariant for the next iteration\.

The implementations ofLeftBoundaryandRightBoundary, which determine the intervals passed toPruneInterval, are given in Appendix[A\.9](https://arxiv.org/html/2608.04310#A1.SS9)\.

Algorithm 8ℛexcluded\\mathcal\{R\}\_\{\\textrm\{excluded\}\}\.MarkExplored\(q\)\(q\)0:Excluded\-range tracker

ℛexcluded\\mathcal\{R\}\_\{\\textrm\{excluded\}\}and active threshold position

qq
1:

ℛexcluded\.PruneInterval​\(q,q\)\\mathcal\{R\}\_\{\\textrm\{excluded\}\}\.\\textsc\{PruneInterval\}\(q,q\)\{Exclude the single explored position\}

Algorithm 9ℛexcluded\\mathcal\{R\}\_\{\\textrm\{excluded\}\}\.PruneInterval\(ℓ,r\)\(\\ell,r\)0:Excluded\-range tracker

ℛexcluded\\mathcal\{R\}\_\{\\textrm\{excluded\}\}and closed interval

\[ℓ,r\]\[\\ell,r\]of active threshold positions

1:if

ℓ\>r\\ell\>rthen

2:return

3:endif

4:

z←ℛexcluded\.UpperBound​\(ℓ\)z\\leftarrow\\mathcal\{R\}\_\{\\textrm\{excluded\}\}\.\\textsc\{UpperBound\}\(\\ell\)\{First stored interval whose left endpoint exceeds

ℓ\\ell\}

5:if

zzhas a predecessor

ppand

Right​\(p\)\+1≥ℓ\\textsc\{Right\}\(p\)\+1\\geq\\ellthen

6:

ℓ←Left​\(p\)\\ell\\leftarrow\\textsc\{Left\}\(p\)
7:

r←max⁡\{r,Right​\(p\)\}r\\leftarrow\\max\\\{r,\\textsc\{Right\}\(p\)\\\}
8:Delete

ppfrom

ℛexcluded\\mathcal\{R\}\_\{\\textrm\{excluded\}\}
9:endif

10:while

z≠∅z\\neq\\emptysetand

Left​\(z\)≤r\+1\\textsc\{Left\}\(z\)\\leq r\+1do

11:

r←max⁡\{r,Right​\(z\)\}r\\leftarrow\\max\\\{r,\\textsc\{Right\}\(z\)\\\}
12:

z←z\\leftarrowthe successor of

zzafter deleting

zz
13:endwhile

14:Insert

\(ℓ,r\)\(\\ell,r\)into

ℛexcluded\\mathcal\{R\}\_\{\\textrm\{excluded\}\}\{Intervals remain disjoint and nonadjacent\}

Algorithm 10Complement\(ℛexcluded,L,U\)\(\\mathcal\{R\}\_\{\\textrm\{excluded\}\},L,U\)0:Excluded\-range tracker

ℛexcluded\\mathcal\{R\}\_\{\\textrm\{excluded\}\}and current search bounds

\[L,U\]\[L,U\]over active threshold positions

1:

Q←∅Q\\leftarrow\\emptyset;

q←Lq\\leftarrow L
2:foreachstored interval

\(a,b\)\(a,b\)in increasing order of

aado

3:if

b<Lb<Lthen

4:continue

5:endif

6:if

a\>Ua\>Uthen

7:break

8:endif

9:if

q<aq<athen

10:

Q\.Push​\(\[q,min⁡\{a−1,U\}\]\)Q\.\\textsc\{Push\}\(\[q,\\min\\\{a\-1,U\\\}\]\)\{Add the unexplored gap preceding

\[a,b\]\[a,b\]\}

11:endif

12:

q←max⁡\{q,b\+1\}q\\leftarrow\\max\\\{q,b\+1\\\}
13:if

q\>Uq\>Uthen

14:break

15:endif

16:endfor

17:if

q≤Uq\\leq Uthen

18:

Q\.Push​\(\[q,U\]\)Q\.\\textsc\{Push\}\(\[q,U\]\)
19:endif

20:return

QQ

### A\.4EnumContFeature

Algorithm[3](https://arxiv.org/html/2608.04310#alg3)gives the completeEnumContFeatureprocedure\. It searches the intervals of active threshold positions returned byInitAndPrune\(Algorithm[2](https://arxiv.org/html/2608.04310#alg2)\)\. The queueQQcontains intervals that have not already been evaluated or pruned using cached entries in the mapEE\. For each interval, the algorithm evaluates its midpoint so that a failed proxy completion may prune thresholds on both sides\. The helper routineProcessInterval, given in Algorithm[11](https://arxiv.org/html/2608.04310#alg11), performs this evaluation and updatesEE,QQ, and the threshold registry𝒮\\mathcal\{S\}\.

#### Threshold\-support bounds\.

For each continuous featurecc, the threshold registry𝒮\\mathcal\{S\}stores the active thresholds and lower and upper bounds on the exhaustive threshold indices that may still induce a nonconstant split\. These bounds summarize information that would otherwise be carried separately along every path\. For a threshold rulexc≤νtx\_\{c\}\\leq\\nu\_\{t\}, an empty left child implies that every smaller threshold is also constant on the current subproblem; an empty right child implies the analogous fact for every larger threshold\. Moreover, a threshold that is constant onDDremains constant on every descendant subproblemD′⊆DD^\{\\prime\}\\subseteq D\. Therefore, wheneverProcessIntervaldiscovers an empty child, it lazily records the corresponding bound in𝒮\\mathcal\{S\}, rather than eagerly updating every descendant or testing all thresholds in that direction\.

The bounds stored in𝒮\\mathcal\{S\}are expressed using exhaustive threshold indices, so they remain valid if additional thresholds become active during the anytime algorithm\.RestrictRange, used by Algorithm[2](https://arxiv.org/html/2608.04310#alg2), converts these bounds to the corresponding active\-position interval\[L,U\]\[L,U\]for the current call\. WithinEnumContFeature,LLandUUare tightened immediately when new constant regions are discovered \(we note that they can also be tightened for other reasons\)\. Intervals already present inQQneed not be removed eagerly: when they are later popped, Algorithm[3](https://arxiv.org/html/2608.04310#alg3)intersects them with the current\[L,U\]\[L,U\]and discards them if the intersection is empty\.

#### Cached proxy completions\.

The structureEEis a map from exhaustive threshold indices to pairs of cached child proxy objectives\(PL,PR\)\(P\_\{L\},P\_\{R\}\)\. We use exhaustive indices as keys, rather than active positions, because active positions may change when the anytime algorithm activates new thresholds\.ProcessIntervalreceives the midpointmmas an active position and first maps it to its exhaustive threshold indextt\. If both children are nonempty, it computes and storesE​\(t\)=\(PL,PR\)E\(t\)=\(P\_\{L\},P\_\{R\}\)\. Thus, later calls under a different budget or a refined active threshold set can reuse the same proxy completions\.

Algorithm 11ProcessInterval\(G,D,c,d,γ,εabs,𝒮,E,Q,L,U,i,j,m\)\(G,D,c,d,\\gamma,\\varepsilon\_\{\\textrm\{abs\}\},\\mathcal\{S\},E,Q,L,U,i,j,m\)0:Current OR node

GG, subproblem

DD, continuous feature

cc, remaining depth

dd, per\-leaf penalty

γ\\gamma, budget

εabs\\varepsilon\_\{\\textrm\{abs\}\}, threshold registry

𝒮\\mathcal\{S\}, proxy completion map

EE, interval queue

QQ, current bounds

\[L,U\]\[L,U\], popped interval

\[i,j\]\[i,j\], and midpoint active position

mm
1:

t←ExhaustiveIndex​\(𝒮,c,m\)t\\leftarrow\\textsc\{ExhaustiveIndex\}\(\\mathcal\{S\},c,m\)\{Map the active position to its threshold\-column index\}

2:

\(DL,DR\)←Partition​\(D,t\)\(D\_\{L\},D\_\{R\}\)\\leftarrow\\textsc\{Partition\}\(D,t\)
3:if

DL=∅D\_\{L\}=\\emptysetthen

4:

RaiseLowerBound​\(𝒮,c,t\+1\)\\textsc\{RaiseLowerBound\}\(\\mathcal\{S\},c,t\+1\)\{Thresholds at or below

ttare constant on

DD\}

5:

L←max⁡\{L,m\+1\}L\\leftarrow\\max\\\{L,m\+1\\\}
6:if

m\+1≤jm\+1\\leq jthen

7:

Q\.Push​\(\[m\+1,j\]\)Q\.\\textsc\{Push\}\(\[m\+1,j\]\)
8:endif

9:return

\(L,U\)\(L,U\)
10:endif

11:if

DR=∅D\_\{R\}=\\emptysetthen

12:

LowerUpperBound​\(𝒮,c,t−1\)\\textsc\{LowerUpperBound\}\(\\mathcal\{S\},c,t\-1\)\{Thresholds at or above

ttare constant on

DD\}

13:

U←min⁡\{U,m−1\}U\\leftarrow\\min\\\{U,m\-1\\\}
14:if

i≤m−1i\\leq m\-1then

15:

Q\.Push​\(\[i,m−1\]\)Q\.\\textsc\{Push\}\(\[i,m\-1\]\)
16:endif

17:return

\(L,U\)\(L,U\)
18:endif

19:

𝒮L←𝒮\\mathcal\{S\}\_\{L\}\\leftarrow\\mathcal\{S\};

𝒮R←𝒮\\mathcal\{S\}\_\{R\}\\leftarrow\\mathcal\{S\}
20:

LowerUpperBound​\(𝒮L,c,t−1\)\\textsc\{LowerUpperBound\}\(\\mathcal\{S\}\_\{L\},c,t\-1\)
21:

RaiseLowerBound​\(𝒮R,c,t\+1\)\\textsc\{RaiseLowerBound\}\(\\mathcal\{S\}\_\{R\},c,t\+1\)
22:

PL←Proxy​\(DL,d−1,γ,𝒮L\)P\_\{L\}\\leftarrow\\textsc\{Proxy\}\(D\_\{L\},d\-1,\\gamma,\\mathcal\{S\}\_\{L\}\)\{Using

𝒮L\\mathcal\{S\}\_\{L\}only exploits known constant thresholds\}

23:

PR←Proxy​\(DR,d−1,γ,𝒮R\)P\_\{R\}\\leftarrow\\textsc\{Proxy\}\(D\_\{R\},d\-1,\\gamma,\\mathcal\{S\}\_\{R\}\)
24:

E​\(t\)←\(PL,PR\)E\(t\)\\leftarrow\(P\_\{L\},P\_\{R\}\)\{Update the map by reference\}

25:

P←PL\+PRP\\leftarrow P\_\{L\}\+P\_\{R\}

Algorithm 12ProcessInterval\(continued\)26:if

P≤εabsP\\leq\\varepsilon\_\{\\textrm\{abs\}\}then

27:

AddOrExtendSplit\(G,D,t,d,γ,εabs,𝒮,PL,PR\)\\begin\{aligned\} &\\textsc\{AddOrExtendSplit\}\(G,D,t,d,\\gamma,\\varepsilon\_\{\\textrm\{abs\}\},\\\\ &\\qquad\\mathcal\{S\},P\_\{L\},P\_\{R\}\)\\end\{aligned\}
28:if

i≤m−1i\\leq m\-1then

29:

Q\.Push​\(\[i,m−1\]\)Q\.\\textsc\{Push\}\(\[i,m\-1\]\)
30:endif

31:if

m\+1≤jm\+1\\leq jthen

32:

Q\.Push​\(\[m\+1,j\]\)Q\.\\textsc\{Push\}\(\[m\+1,j\]\)
33:endif

34:return

\(L,U\)\(L,U\)
35:endif

36:\{The proxy completion is outside the budget; tighten bounds when one child is already a pure leaf\}

37:if

PL=γP\_\{L\}=\\gammathen

38:

L←max⁡\{L,m\+1\}L\\leftarrow\\max\\\{L,m\+1\\\}
39:endif

40:if

PR=γP\_\{R\}=\\gammathen

41:

U←min⁡\{U,m−1\}U\\leftarrow\\min\\\{U,m\-1\\\}
42:endif

43:

Δ←P−εabs\\Delta\\leftarrow P\-\\varepsilon\_\{\\textrm\{abs\}\}
44:

ℓ←LeftBoundary​\(D,𝒮,c,t,m−1,max⁡\{i,L\},Δ\)\\ell\\leftarrow\\textsc\{LeftBoundary\}\(D,\\mathcal\{S\},c,t,m\-1,\\max\\\{i,L\\\},\\Delta\)
45:

r←RightBoundary​\(D,𝒮,c,t,m\+1,min⁡\{j,U\},Δ\)r\\leftarrow\\textsc\{RightBoundary\}\(D,\\mathcal\{S\},c,t,m\+1,\\min\\\{j,U\\\},\\Delta\)\{Positions in

\[ℓ\+1,r−1\]\[\\ell\+1,r\-1\]are pruned\}

46:if

i≤min⁡\{ℓ,U\}i\\leq\\min\\\{\\ell,U\\\}then

47:

Q\.Push​\(\[i,min⁡\{ℓ,U\}\]\)Q\.\\textsc\{Push\}\(\[i,\\min\\\{\\ell,U\\\}\]\)
48:endif

49:if

max⁡\{r,L\}≤j\\max\\\{r,L\\\}\\leq jthen

50:

Q\.Push​\(\[max⁡\{r,L\},j\]\)Q\.\\textsc\{Push\}\(\[\\max\\\{r,L\\\},j\]\)
51:endif

52:return

\(L,U\)\(L,U\)

If the midpoint split is feasible \(within budget\), both neighboring subintervals remain potentially feasible and are placed back intoQQ\. If it is infeasible,LeftBoundaryandRightBoundaryidentify the nearest positions on each side whose active\-sample distance fromttis at leastΔ=P−εabs\\Delta=P\-\\varepsilon\_\{\\textrm\{abs\}\}; the positions strictly between those boundaries cannot improve enough to enter the budget\. Their implementations are given in Appendix[A\.9](https://arxiv.org/html/2608.04310#A1.SS9)\.

### A\.5Iterative Budget Refinement

Algorithms[13](https://arxiv.org/html/2608.04310#alg13)and[14](https://arxiv.org/html/2608.04310#alg14)describe how we solve the two child subgraphs of a feasible split under a shared parent budget\. The key issue is that the budget available to one child depends on the best objective attainable by the other child\. That is, we want all solutions to the left subproblem that can be paired with the best solution in the right subproblem and remain within the parent budget \(and vice versa\)\. If we only know that the right child can be completed with objectiveP2P\_\{2\}, then we can only prove that the left child needs to be solved up to budgetεabs−P2\\varepsilon\_\{\\mathrm\{abs\}\}\-P\_\{2\}\. Once the left child is solved, its true minimum objective may be smaller than its initial proxy cost, which increases the budget available to the right child\. This can in turn increase the budget available to the left child, so the process alternates until neither child receives a larger budget \(this occurs when a side does not improve on its best solution\)\.GraphSolveOrderedis very similar to iterative budget refinement inHeileet al\.\([2026](https://arxiv.org/html/2608.04310#bib.bib156)\)\.

Algorithm 13GraphSolveOrdered\(G1,G2,D1,D2,d,γ,εabs,P1,P2,𝒮1,𝒮2\)\\begin\{aligned\} \\textsc\{GraphSolveOrdered\}\(&G\_\{1\},G\_\{2\},D\_\{1\},D\_\{2\},d,\\gamma,\\varepsilon\_\{\\textrm\{abs\}\},\\\\ &P\_\{1\},P\_\{2\},\\mathcal\{S\}\_\{1\},\\mathcal\{S\}\_\{2\}\)\\end\{aligned\}0:Left/right subgraphs after relabeling, left/right datasets after relabeling, remaining depth

dd, regularization

γ\\gamma, parent budget

εabs\\varepsilon\_\{\\textrm\{abs\}\}, initial proxy/minimum costs

P1,P2P\_\{1\},P\_\{2\}, and threshold registries

𝒮1,𝒮2\\mathcal\{S\}\_\{1\},\\mathcal\{S\}\_\{2\},

Budget​\(∅\)=0\\mathrm\{Budget\}\(\\emptyset\)=0
1:

ε1\(new\)←εabs−P2\\varepsilon\_\{1\}^\{\(\\textrm\{new\}\)\}\\leftarrow\\varepsilon\_\{\\textrm\{abs\}\}\-P\_\{2\}
2:while

ε1\(new\)\>Budget​\(G1\)\\varepsilon\_\{1\}^\{\(\\textrm\{new\}\)\}\>\\textsc\{Budget\}\(G\_\{1\}\)do

3:

ArborEnum​\(G1,D1,d,γ,ε1\(new\),𝒮1\)\\textsc\{ArborEnum\}\(G\_\{1\},D\_\{1\},d,\\gamma,\\varepsilon\_\{1\}^\{\(\\textrm\{new\}\)\},\\mathcal\{S\}\_\{1\}\)\{Solve or extend the first subgraph\}

4:

ε2\(new\)←εabs−G1\.min\_objective\\varepsilon\_\{2\}^\{\(\\textrm\{new\}\)\}\\leftarrow\\varepsilon\_\{\\textrm\{abs\}\}\-G\_\{1\}\.\\textit\{min\\\_objective\}
5:if

ε2\(new\)\>Budget​\(G2\)\\varepsilon\_\{2\}^\{\(\\textrm\{new\}\)\}\>\\textsc\{Budget\}\(G\_\{2\}\)then

6:

ArborEnum​\(G2,D2,d,γ,ε2\(new\),𝒮2\)\\textsc\{ArborEnum\}\(G\_\{2\},D\_\{2\},d,\\gamma,\\varepsilon\_\{2\}^\{\(\\textrm\{new\}\)\},\\mathcal\{S\}\_\{2\}\)\{Solve or extend the second subgraph\}

7:

ε1\(new\)←εabs−G2\.min\_objective\\varepsilon\_\{1\}^\{\(\\textrm\{new\}\)\}\\leftarrow\\varepsilon\_\{\\textrm\{abs\}\}\-G\_\{2\}\.\\textit\{min\\\_objective\}
8:endif

9:endwhile

The continuous\-feature pruning rules and the anytime algorithm require a wrapper around the procedure inHeileet al\.\([2026](https://arxiv.org/html/2608.04310#bib.bib156)\)\. In particular, because the anytime algorithm revisits subproblems after activating additional thresholds, one child subgraph may improve while the other remains unchanged\. Therefore, the order in which the two children are extended can matter\.

GraphSolveSiblings\(Algorithm[14](https://arxiv.org/html/2608.04310#alg14)\) wraps the left and right children of an actual split\. If both child subgraphs are empty, it simply callsGraphSolveOrdered, and both sides will be solve at least once\. If the split has already been encountered, the routine uses the existing child budgets, stored minimum objectives, and new proxy costs to determine whether either child can be extended under the parent budget\. When extension is needed, it starts with the child whose newly available budget has increased\.

This ordering is important during anytime refinement\. After new thresholds are activated,RefineGraphmay improve the minimum objective of one child but not the other\. If one child’s minimum objective improves, then the budget available to its sibling increases\. We therefore first solve the sibling whose budget increased\. This gives that sibling an opportunity to improve its own minimum objective, which may in turn increase the budget available to the first child\. The ordered solve then alternates until neither child can be extended further\.

Algorithm 14GraphSolveSiblings\(GL,GR,DL,DR,d,γ,εabs,PL,PR,𝒮L,𝒮R\)\\begin\{aligned\} \\textsc\{GraphSolveSiblings\}\(&G\_\{L\},G\_\{R\},D\_\{L\},D\_\{R\},d,\\gamma,\\varepsilon\_\{\\textrm\{abs\}\},\\\\ &P\_\{L\},P\_\{R\},\\mathcal\{S\}\_\{L\},\\mathcal\{S\}\_\{R\}\)\\end\{aligned\}0:Existing left/right subgraphs

GL,GRG\_\{L\},G\_\{R\}which are either both empty or both non\-empty, left/right datasets

DL,DRD\_\{L\},D\_\{R\}, remaining depth

dd, regularization

γ\\gamma, parent budget

εabs\\varepsilon\_\{\\textrm\{abs\}\}, proxy costs

PL,PRP\_\{L\},P\_\{R\}, and threshold registries

𝒮L,𝒮R\\mathcal\{S\}\_\{L\},\\mathcal\{S\}\_\{R\}
1:if

GL=∅G\_\{L\}=\\emptysetand

GR=∅G\_\{R\}=\\emptysetthen

2:

GraphSolveOrdered\(GL,GR,DL,DR,d,γ,εabs,PL,PR,𝒮L,𝒮R\)\\begin\{aligned\} \\textsc\{GraphSolveOrdered\}\(&G\_\{L\},G\_\{R\},D\_\{L\},D\_\{R\},d,\\gamma,\\varepsilon\_\{\\textrm\{abs\}\},\\\\ &P\_\{L\},P\_\{R\},\\mathcal\{S\}\_\{L\},\\mathcal\{S\}\_\{R\}\)\\end\{aligned\}
3:else

4:

εL←Budget​\(GL\)\\varepsilon\_\{L\}\\leftarrow\\textsc\{Budget\}\(G\_\{L\}\)\{

GLG\_\{L\}has already been solved up to this budget\}

5:

εR←Budget​\(GR\)\\varepsilon\_\{R\}\\leftarrow\\textsc\{Budget\}\(G\_\{R\}\)\{

GRG\_\{R\}has already been solved up to this budget\}

6:

P^L←min\{PL,GL\.min\_objective\}\\widehat\{P\}\_\{L\}\\leftarrow\\min\\\{P\_\{L\},G\_\{L\}\.\\textit\{min\\\_objective\}\\\}
7:

P^R←min\{PR,GR\.min\_objective\}\\widehat\{P\}\_\{R\}\\leftarrow\\min\\\{P\_\{R\},G\_\{R\}\.\\textit\{min\\\_objective\}\\\}
8:

εL\(new\)←εabs−P^R\\varepsilon\_\{L\}^\{\(\\textrm\{new\}\)\}\\leftarrow\\varepsilon\_\{\\textrm\{abs\}\}\-\\widehat\{P\}\_\{R\}
9:

εR\(new\)←εabs−P^L\\varepsilon\_\{R\}^\{\(\\textrm\{new\}\)\}\\leftarrow\\varepsilon\_\{\\textrm\{abs\}\}\-\\widehat\{P\}\_\{L\}
10:if

εL\(new\)≤εL\\varepsilon\_\{L\}^\{\(\\textrm\{new\}\)\}\\leq\\varepsilon\_\{L\}and

εR\(new\)≤εR\\varepsilon\_\{R\}^\{\(\\textrm\{new\}\)\}\\leq\\varepsilon\_\{R\}then

11:return

12:endif

13:if

εL\(new\)\>εL\\varepsilon\_\{L\}^\{\(\\textrm\{new\}\)\}\>\\varepsilon\_\{L\}then

14:

GraphSolveOrdered\(GL,GR,DL,DR,d,γ,εabs,P^L,P^R,𝒮L,𝒮R\)\\begin\{aligned\} \\textsc\{GraphSolveOrdered\}\(&G\_\{L\},G\_\{R\},D\_\{L\},D\_\{R\},d,\\gamma,\\\\ &\\varepsilon\_\{\\textrm\{abs\}\},\\widehat\{P\}\_\{L\},\\widehat\{P\}\_\{R\},\\mathcal\{S\}\_\{L\},\\mathcal\{S\}\_\{R\}\)\\end\{aligned\}
15:else

16:

GraphSolveOrdered\(GR,GL,DR,DL,d,γ,εabs,P^R,P^L,𝒮R,𝒮L\)\\begin\{aligned\} \\textsc\{GraphSolveOrdered\}\(&G\_\{R\},G\_\{L\},D\_\{R\},D\_\{L\},d,\\gamma,\\\\ &\\varepsilon\_\{\\textrm\{abs\}\},\\widehat\{P\}\_\{R\},\\widehat\{P\}\_\{L\},\\mathcal\{S\}\_\{R\},\\mathcal\{S\}\_\{L\}\)\\end\{aligned\}
17:endif

18:endif

### A\.6RefineGraph

RefineGraph\(Algorithm[15](https://arxiv.org/html/2608.04310#alg15)\) updates an existing minimum\-objective AND/OR graph after the active threshold set has been enlarged by the anytime algorithm\. The input graph already encodes feasible trees for an earlier, smaller set of active thresholds\. The goal ofRefineGraphis not to rebuild this graph from scratch, but to recursively extend it so that it is valid for the new active threshold set\.

The routine proceeds in post\-order\. For each split already stored atGG, it copies the current threshold registry into child\-specific registries𝒮L\\mathcal\{S\}\_\{L\}and𝒮R\\mathcal\{S\}\_\{R\}\. If the split is a thresholdttof continuous featurecc, the left child satisfiesxc≤νtx\_\{c\}\\leq\\nu\_\{t\}, soLowerUpperBoundrestricts the upper bound of𝒮L\\mathcal\{S\}\_\{L\}tot−1t\-1\. Similarly, the right child satisfiesxc\>νtx\_\{c\}\>\\nu\_\{t\}, soRaiseLowerBoundrestricts the lower bound of𝒮R\\mathcal\{S\}\_\{R\}tot\+1t\+1\. The routine then recursively refines both children using their respective registries\.

After the children have been refined, an existing binary split is passed toAddOrExtendSplit, since improved child minimum objectives may permit additional iterative budget refinement\. Existing continuous splits need not be handled separately here: the subsequent call toEnumContFeatureprocesses all active thresholds, including thresholds already stored inGG, using their cached proxy completions\. The threshold bounds are already stored in𝒮\\mathcal\{S\}and will be used later\.

Algorithm 15RefineGraph\(G,D,d,𝒮,𝒱\)\(G,D,d,\\mathcal\{S\},\\mathcal\{V\}\)0:Existing OR node

GG, subproblem bitvector

DD, remaining depth

dd, threshold registry

𝒮\\mathcal\{S\}, and set

𝒱\\mathcal\{V\}of OR nodes already refined during this pass

1:if

G=∅G=\\emptysetthen

2:return

3:endif

4:

εabs←Budget​\(G\)\\varepsilon\_\{\\textrm\{abs\}\}\\leftarrow\\textsc\{Budget\}\(G\)
5:if

G∈𝒱G\\in\\mathcal\{V\}then

6:return\{

GGwas already refined during this pass\}

7:endif

8:

𝒱←𝒱∪\{G\}\\mathcal\{V\}\\leftarrow\\mathcal\{V\}\\cup\\\{G\\\}
9:if

d≤0d\\leq 0or

εabs<2​γ\\varepsilon\_\{\\textrm\{abs\}\}<2\\gammathen

10:return\{No split can fit within the remaining budget\}

11:endif

12:

𝒜←Splits​\(G\)\\mathcal\{A\}\\leftarrow\\textsc\{Splits\}\(G\)\{Snapshot the splits present when this call begins\}

13:foreach split node

s∈𝒜s\\in\\mathcal\{A\}do

14:

t←Feature​\(s\)t\\leftarrow\\textsc\{Feature\}\(s\)
15:

\(DL,DR\)←Partition​\(D,t\)\(D\_\{L\},D\_\{R\}\)\\leftarrow\\textsc\{Partition\}\(D,t\)
16:

𝒮L←𝒮\\mathcal\{S\}\_\{L\}\\leftarrow\\mathcal\{S\};

𝒮R←𝒮\\mathcal\{S\}\_\{R\}\\leftarrow\\mathcal\{S\}
17:if

ttis a threshold of continuous feature

ccthen

18:

LowerUpperBound​\(𝒮L,c,t−1\)\\textsc\{LowerUpperBound\}\(\\mathcal\{S\}\_\{L\},c,t\-1\)\{Thresholds at or above

ttare constant on

DLD\_\{L\}\}

19:

RaiseLowerBound​\(𝒮R,c,t\+1\)\\textsc\{RaiseLowerBound\}\(\\mathcal\{S\}\_\{R\},c,t\+1\)\{Thresholds at or below

ttare constant on

DRD\_\{R\}\}

20:endif

21:

RefineGraph\(s\.left,DL,d−1,𝒮L,𝒱\)\\textsc\{RefineGraph\}\(s\.\\textit\{left\},D\_\{L\},d\-1,\\mathcal\{S\}\_\{L\},\\mathcal\{V\}\)
22:

RefineGraph\(s\.right,DR,d−1,𝒮R,𝒱\)\\textsc\{RefineGraph\}\(s\.\\textit\{right\},D\_\{R\},d\-1,\\mathcal\{S\}\_\{R\},\\mathcal\{V\}\)
23:if

ttis an ordinary binary featurethen

24:

PL←Proxy​\(DL,d−1,γ,𝒮L\)P\_\{L\}\\leftarrow\\textsc\{Proxy\}\(D\_\{L\},d\-1,\\gamma,\\mathcal\{S\}\_\{L\}\)
25:

PR←Proxy​\(DR,d−1,γ,𝒮R\)P\_\{R\}\\leftarrow\\textsc\{Proxy\}\(D\_\{R\},d\-1,\\gamma,\\mathcal\{S\}\_\{R\}\)
26:

AddOrExtendSplit\(G,D,t,d,γ,εabs,𝒮,PL,PR\)\\begin\{aligned\} &\\textsc\{AddOrExtendSplit\}\(G,D,t,d,\\gamma,\\varepsilon\_\{\\textrm\{abs\}\},\\\\ &\\qquad\\mathcal\{S\},P\_\{L\},P\_\{R\}\)\\end\{aligned\}
27:endif

28:endfor

29:foreach continuous feature

ccdo

30:

EnumContFeature​\(G,D,c,d,γ,εabs,𝒮\)\\begin\{aligned\} &\\textsc\{EnumContFeature\}\(G,D,c,d,\\gamma,\\varepsilon\_\{\\textrm\{abs\}\},\\mathcal\{S\}\)\\end\{aligned\}\{Add newly active feasible thresholds and extend existing ones\}

31:endfor

### A\.7AddOrExtendSplit

AddOrExtendSplit\(Algorithm[16](https://arxiv.org/html/2608.04310#alg16)\) is the routine that materializes a creates or extends a given split at an OR node\. It partitions the current subproblem, constructs the threshold registries for the two children, and retrieves the existing child subgraphs when the split is already stored inGG\.

For a continuous thresholdttof featurecc, the left child satisfiesxc≤νtx\_\{c\}\\leq\\nu\_\{t\}, so every threshold of featureccwith exhaustive index at leastttis constant onDLD\_\{L\}\. We therefore tighten the upper bound in𝒮L\\mathcal\{S\}\_\{L\}tot−1t\-1\. Symmetrically, the right child satisfiesxc\>νtx\_\{c\}\>\\nu\_\{t\}, so every threshold with index at mostttis constant onDRD\_\{R\}, and we tighten the lower bound in𝒮R\\mathcal\{S\}\_\{R\}tot\+1t\+1\. These are the child\-specific bounds later used byRestrictRange\. For an ordinary binary feature, both child registries are unchanged copies of𝒮\\mathcal\{S\}\.

The two children are then passed toGraphSolveSiblings, which solves or extends them under the shared parent budget\. If both child subgraphs are nonempty after this refinement, the split is valid in the Rashomon graph\. If the split is new, it is added toGGwith its left and right child subgraphs\. If the split already exists, the routine updates the minimum objective stored atGGusing the improved child objectives\.AddSPLIT\(Heileet al\.[2026](https://arxiv.org/html/2608.04310#bib.bib156)\)already handles this minimum objective propagation, so we only explicitly handle it in the case that we are extending a split\.

Algorithm 16AddOrExtendSplit\(G,D,t,d,γ,εabs,𝒮,PL,PR\)\(G,D,t,d,\\gamma,\\varepsilon\_\{\\textrm\{abs\}\},\\mathcal\{S\},P\_\{L\},P\_\{R\}\)0:Current OR node

GG, subproblem

DD, split feature or threshold

tt, remaining depth

dd, per\-leaf penalty

γ\\gamma, parent budget

εabs\\varepsilon\_\{\\textrm\{abs\}\}, threshold registry

𝒮\\mathcal\{S\}, and child proxy objectives

PL,PRP\_\{L\},P\_\{R\}
1:

\(DL,DR\)←Partition​\(D,t\)\(D\_\{L\},D\_\{R\}\)\\leftarrow\\textsc\{Partition\}\(D,t\)
2:

𝒮L←𝒮\\mathcal\{S\}\_\{L\}\\leftarrow\\mathcal\{S\};

𝒮R←𝒮\\mathcal\{S\}\_\{R\}\\leftarrow\\mathcal\{S\}
3:if

ttis a threshold of continuous feature

ccthen

4:

LowerUpperBound​\(𝒮L,c,t−1\)\\textsc\{LowerUpperBound\}\(\\mathcal\{S\}\_\{L\},c,t\-1\)\{Thresholds at or above

ttare constant on

DLD\_\{L\}\}

5:

RaiseLowerBound​\(𝒮R,c,t\+1\)\\textsc\{RaiseLowerBound\}\(\\mathcal\{S\}\_\{R\},c,t\+1\)\{Thresholds at or below

ttare constant on

DRD\_\{R\}\}

6:endif

7:if

GGalready contains split

ttthen

8:Let

\(GL,GR\)\(G\_\{L\},G\_\{R\}\)be the existing children of split

tt
9:

is\_new←false\\textit\{is\\\_new\}\\leftarrow\\textbf\{false\}
10:else

11:

GL←∅G\_\{L\}\\leftarrow\\emptyset;

GR←∅G\_\{R\}\\leftarrow\\emptyset
12:

is\_new←true\\textit\{is\\\_new\}\\leftarrow\\textbf\{true\}
13:endif

14:

GraphSolveSiblings\(GL,GR,DL,DR,d−1,γ,εabs,PL,PR,𝒮L,𝒮R\)\\begin\{aligned\} \\textsc\{GraphSolveSiblings\}\(&G\_\{L\},G\_\{R\},D\_\{L\},D\_\{R\},d\-1,\\gamma,\\varepsilon\_\{\\textrm\{abs\}\},\\\\ &P\_\{L\},P\_\{R\},\\mathcal\{S\}\_\{L\},\\mathcal\{S\}\_\{R\}\)\\end\{aligned\}
15:if

GL=∅G\_\{L\}=\\emptysetor

GR=∅G\_\{R\}=\\emptysetthen

16:return\{The split has no feasible pair of child subtrees\}

17:endif

18:ifis\_newthen

19:

AddSplit​\(G,t,GL,GR\)\\textsc\{AddSplit\}\(G,t,G\_\{L\},G\_\{R\}\)
20:else

21:

G\.min\_objective←min\{G\.min\_objective,GL\.min\_objective\+GR\.min\_objective\}G\.\\textit\{min\\\_objective\}\\leftarrow\\min\\\{G\.\\textit\{min\\\_objective\},G\_\{L\}\.\\textit\{min\\\_objective\}\+G\_\{R\}\.\\textit\{min\\\_objective\}\\\}
22:endif

### A\.8Anytime Algorithm

AnytimeArborEnum\(Algorithm[4](https://arxiv.org/html/2608.04310#alg4)\) progressively constructs a Rashomon graph over increasingly large sets of active thresholds\. The goal of this section is to provide an overview of the method and additional details including refining the proxy\. The algorithm begins with the ordinary binary features and an initial proxy threshold setℬproxy\\mathcal\{B\}\_\{\\textrm\{proxy\}\}\. These thresholds are used to initialize the root threshold registry𝒮root\\mathcal\{S\}\_\{\\textrm\{root\}\}, which stores both the currently active thresholds and the continuous\-feature bounds\. The proxy is restricted toℬproxy\\mathcal\{B\}\_\{\\textrm\{proxy\}\}, and the first call toArborEnumconstructs a minimum\-objective AND/OR graph over the initial active threshold set\.

The algorithm then repeatedly activates additional continuous thresholds\. After each refinement,ActivateThresholds​\(𝒮root,ℬnew\)\\textsc\{ActivateThresholds\}\(\\mathcal\{S\}\_\{\\textrm\{root\}\},\\mathcal\{B\}\_\{\\textrm\{new\}\}\)updates the threshold registry by reference \(to add the new thresholds\), andRefineGraphrevisits the existing graph\. This recursively refines child subgraphs, reruns iterative budget refinement where necessary, and searches for continuous splits that were unavailable in earlier rounds but are now active \. We clear the canonical subgraph indexℐG\\mathcal\{I\}\_\{G\}between threshold\-refinement rounds because a cached subgraph that was complete for the previous active threshold set is not necessarily complete for the enlarged set\. The graph itself is preserved and extended in place\. The threshold\-to\-proxy completion maps and the proxy algorithm’s own cache are also retained, so previously computed proxy completions remain available\. As subgraphs are revisited,ℐG\\mathcal\{I\}\_\{G\}is repopulated and again provides reuse within the new active threshold set\.

Once all thresholds are active, the algorithm may optionally strengthen the proxy until it becomes optimal\. This phase is optional because increasing proxy strength may be substantially more expensive than threshold refinement\. After each increase in proxy strength, proxy caches are updated as described in Appendix[C\.1](https://arxiv.org/html/2608.04310#A3.SS1), the threshold\-to\-proxy completion maps whose values depend on the previous proxy are cleared or recomputed, andℐG\\mathcal\{I\}\_\{G\}is cleared because cached completeness guarantees were established using the previous proxy\. The existing Rashomon graph is not discarded\. Instead,RefineGraphrevisits and extends it using the stronger proxy\. Thus, early stopping returns the best graph constructed so far, whereas running both phases to completion recovers the full continuous\-feature Rashomon set when the proxy becomes optimal\.

Algorithm[4](https://arxiv.org/html/2608.04310#alg4)presents the simpler variant in which the proxy is restricted toℬproxy\\mathcal\{B\}\_\{\\textrm\{proxy\}\}, while the active enumeration thresholds stored in𝒮root\\mathcal\{S\}\_\{\\textrm\{root\}\}form a superset ofℬproxy\\mathcal\{B\}\_\{\\textrm\{proxy\}\}\. We can relax this restriction by allowing the proxy to use a larger threshold set and return both the objective of its certified tree and that tree’s root split for the current subproblem and depth\. We then activate this root split locally at the corresponding OR node and evaluate it immediately\. This adds at most one proxy\-selected threshold per subproblem and ensures that the proxy\-certified tree remains recoverable even when its root split is not yet globally active\. Consequently, the anytime algorithm may begin with no active continuous thresholds, add proxy\-selected thresholds locally as needed, and still progressively activate the remaining thresholds globally until all thresholds are available\.

There is one important thing to note that may not be immediately clear\. During refinement, a binary feature may not have been used previously\. But, now with an expanded active set, it may need to be used\. This can only happen in our framework if a minimum objective improves in the sibling subproblem\. Because the proxy is fixed at some granularity, whether fully continuous features or some binarization, it is not able to give a different value\. If one child subgraph improves its minimum objective, the budget available to the sibling increases\.RefineGraphtherefore callsAddOrExtendSpliton each existing binary split after recursively refining its children\. This invokes iterative budget refinement, which may extend either child under the newly available budget\. Because extending a child callsArborEnum, all of that child’s candidate splits are considered again, including binary splits that were previously outside the child’s budget but are now feasible\.ArborEnumwill extend the subgraph to the bigger budget while reconsidering all binary features that are not yet in the graph, reconsidering all old active continuous thresholds that are not yet in the graph, and considering all continuous thresholds that just became active\.

Algorithm 17AnytimeArborEnum\(d,γ,εmult,ℬproxy\)\(d,\\gamma,\\varepsilon\_\{\\textrm\{mult\}\},\\mathcal\{B\}\_\{\\textrm\{proxy\}\}\)0:Depth budget

dd, per\-leaf penalty

γ\\gamma, Rashomon multiplier

εmult\\varepsilon\_\{\\textrm\{mult\}\}, and sorted list of proxy thresholds

ℬproxy\\mathcal\{B\}\_\{\\textrm\{proxy\}\}
1:

ℬbin←\\mathcal\{B\}\_\{\\textrm\{bin\}\}\\leftarrowsorted list of indices of ordinary binary features

2:

ℬinitial←SortUnique​\(ℬbin∪ℬproxy\)\\mathcal\{B\}\_\{\\textrm\{initial\}\}\\leftarrow\\textsc\{SortUnique\}\(\\mathcal\{B\}\_\{\\textrm\{bin\}\}\\cup\\mathcal\{B\}\_\{\\textrm\{proxy\}\}\)
3:

𝒮root←InitializeThresholdRegistry​\(ℬinitial\)\\mathcal\{S\}\_\{\\textrm\{root\}\}\\leftarrow\\textsc\{InitializeThresholdRegistry\}\(\\mathcal\{B\}\_\{\\textrm\{initial\}\}\)\{Initialize active thresholds and unrestricted feature bounds\}

4:

Droot←D\_\{\\textrm\{root\}\}\\leftarrowthe bitvector containing all training samples

5:Restrict proxy algorithms to

ℬproxy\\mathcal\{B\}\_\{\\textrm\{proxy\}\}
6:

εabs←\(1\+εmult\)​Proxy​\(Droot,d,γ,𝒮root\)\\varepsilon\_\{\\textrm\{abs\}\}\\leftarrow\(1\+\\varepsilon\_\{\\textrm\{mult\}\}\)\\textsc\{Proxy\}\(D\_\{\\textrm\{root\}\},d,\\gamma,\\mathcal\{S\}\_\{\\textrm\{root\}\}\)\{Initialize the root budget\}

7:

G←ArborEnum\(G,Droot,d,γ,εabs,𝒮root\)\\begin\{aligned\} G\\leftarrow\{\}&\\textsc\{ArborEnum\}\(G,D\_\{\\textrm\{root\}\},d,\\gamma,\\varepsilon\_\{\\textrm\{abs\}\},\\\\ &\\qquad\\mathcal\{S\}\_\{\\textrm\{root\}\}\)\\end\{aligned\}
8:whilenot

AllThresholdsActive​\(𝒮root\)\\textsc\{AllThresholdsActive\}\(\\mathcal\{S\}\_\{\\textrm\{root\}\}\)do

9:

ℬnew←SelectNewThresholds​\(𝒮root\)\\mathcal\{B\}\_\{\\textrm\{new\}\}\\leftarrow\\textsc\{SelectNewThresholds\}\(\\mathcal\{S\}\_\{\\textrm\{root\}\}\)\{By default, select one threshold in the gap between two active indices \(for each pair of consecutive active indices\)\}

10:

ActivateThresholds​\(𝒮root,ℬnew\)\\textsc\{ActivateThresholds\}\(\\mathcal\{S\}\_\{\\textrm\{root\}\},\\mathcal\{B\}\_\{\\textrm\{new\}\}\)\{Update the root registry by reference\}

11:Clear

ℐG\\mathcal\{I\}\_\{G\}\{Cached subgraphs may be incomplete for the enlarged active set\}

12:

𝒱←∅\\mathcal\{V\}\\leftarrow\\emptyset
13:

RefineGraph​\(G,Droot,d,𝒮root,𝒱\)\\textsc\{RefineGraph\}\(G,D\_\{\\textrm\{root\}\},d,\\mathcal\{S\}\_\{\\textrm\{root\}\},\\mathcal\{V\}\)\{Extend the existing graph using the newly active thresholds\}

14:endwhile

15:whilenot

IsProxyOptimal​\(Proxy\)\\textsc\{IsProxyOptimal\}\(\\textsc\{Proxy\}\)do

16:Increase proxy strength by

11
17:Clear each threshold\-to\-proxy completion map

𝒞map\\mathcal\{C\}\_\{\\textrm\{map\}\}\{Their stored objectives were computed using the previous proxy\}

18:Clear

ℐG\\mathcal\{I\}\_\{G\}\{Cached completeness guarantees used the previous proxy\}

19:

𝒱←∅\\mathcal\{V\}\\leftarrow\\emptyset
20:

RefineGraph​\(G,Droot,d,𝒮root,𝒱\)\\textsc\{RefineGraph\}\(G,D\_\{\\textrm\{root\}\},d,\\mathcal\{S\}\_\{\\textrm\{root\}\},\\mathcal\{V\}\)\{Revisit the existing graph using the stronger proxy\}

21:endwhile

22:return

GG

### A\.9Additional Methods

The boundary routines are implemented by binary search \(with a small amount of initial probing\) and use the active thresholds stored in𝒮\\mathcal\{S\}\. After a failed threshold, they find the closest active position that can possibly recover from the gapΔ\\Delta, usingO​\(log⁡\|𝒜c\|\)O\(\\log\|\\mathcal\{A\}\_\{c\}\|\)calls toFarEnough, where𝒜c\\mathcal\{A\}\_\{c\}is the ordered list of active exhaustive threshold indices for featurecc\. Depending on the active\-threshold spacing, however, the nearest active threshold may already be far enough away\. Therefore, each routine first tests the nearest two active positions in its search direction and returns immediately if either has active\-sample distance at leastΔ\\Delta; otherwise, it applies binary search to the remaining interval\. Each call toFarEnoughstops as soon asΔ\\Deltadiffering active samples have been found\.

We store each subproblemDDand exhaustive threshold columnXtX\_\{t\}as packed bitvectors\. Theiith bit indicates whether sampleiiis active inDDor satisfies thresholdtt, respectively\. These bitvectors are stored as arrays of 64\-bit machine words, allowing each bitwise operation to process 64 samples at once;Popcountreturns the number of set bits in each word\.

Algorithm 18RightBoundary\(D,𝒮,c,t,i,b,Δ\)\(D,\\mathcal\{S\},c,t,i,b,\\Delta\)0:Subproblem bitvector

DD, threshold registry

𝒮\\mathcal\{S\}, continuous feature

cc, failed exhaustive threshold index

tt, search interval

\[i,b\]\[i,b\]over active positions, and gap

Δ\\Delta
1:if

i\>bi\>bthen

2:return

b\+1b\+1
3:endif

4:foreach

p∈\{i,min⁡\{i\+1,b\}\}p\\in\\\{i,\\min\\\{i\+1,b\\\}\\\}do

5:

s←ExhaustiveIndex​\(𝒮,c,p\)s\\leftarrow\\textsc\{ExhaustiveIndex\}\(\\mathcal\{S\},c,p\)
6:if

FarEnough​\(D,t,s,Δ\)\\textsc\{FarEnough\}\(D,t,s,\\Delta\)then

7:return

pp
8:endif

9:endfor

10:

ℓ←min⁡\{i\+2,b\+1\}\\ell\\leftarrow\\min\\\{i\+2,b\+1\\\};

r←br\\leftarrow b;

q←b\+1q\\leftarrow b\+1
11:while

ℓ≤r\\ell\\leq rdo

12:

m←⌊\(ℓ\+r\)/2⌋m\\leftarrow\\lfloor\(\\ell\+r\)/2\\rfloor
13:

s←ExhaustiveIndex​\(𝒮,c,m\)s\\leftarrow\\textsc\{ExhaustiveIndex\}\(\\mathcal\{S\},c,m\)
14:if

FarEnough​\(D,t,s,Δ\)\\textsc\{FarEnough\}\(D,t,s,\\Delta\)then

15:

q←mq\\leftarrow m;

r←m−1r\\leftarrow m\-1
16:else

17:

ℓ←m\+1\\ell\\leftarrow m\+1
18:endif

19:endwhile

20:return

qq

Algorithm 19LeftBoundary\(D,𝒮,c,t,j,a,Δ\)\(D,\\mathcal\{S\},c,t,j,a,\\Delta\)0:Subproblem bitvector

DD, threshold registry

𝒮\\mathcal\{S\}, continuous feature

cc, failed exhaustive threshold index

tt, search interval

\[a,j\]\[a,j\]over active positions, and gap

Δ\\Delta
1:if

a\>ja\>jthen

2:return

a−1a\-1
3:endif

4:foreach

p∈\{j,max⁡\{j−1,a\}\}p\\in\\\{j,\\max\\\{j\-1,a\\\}\\\}do

5:

s←ExhaustiveIndex​\(𝒮,c,p\)s\\leftarrow\\textsc\{ExhaustiveIndex\}\(\\mathcal\{S\},c,p\)
6:if

FarEnough​\(D,s,t,Δ\)\\textsc\{FarEnough\}\(D,s,t,\\Delta\)then

7:return

pp
8:endif

9:endfor

10:

ℓ←a\\ell\\leftarrow a;

r←max⁡\{j−2,a−1\}r\\leftarrow\\max\\\{j\-2,a\-1\\\};

q←a−1q\\leftarrow a\-1
11:while

ℓ≤r\\ell\\leq rdo

12:

m←⌊\(ℓ\+r\)/2⌋m\\leftarrow\\lfloor\(\\ell\+r\)/2\\rfloor
13:

s←ExhaustiveIndex​\(𝒮,c,m\)s\\leftarrow\\textsc\{ExhaustiveIndex\}\(\\mathcal\{S\},c,m\)
14:if

FarEnough​\(D,s,t,Δ\)\\textsc\{FarEnough\}\(D,s,t,\\Delta\)then

15:

q←mq\\leftarrow m;

ℓ←m\+1\\ell\\leftarrow m\+1
16:else

17:

r←m−1r\\leftarrow m\-1
18:endif

19:endwhile

20:return

qq

Algorithm 20FarEnough\(D,s,t,Δ\)\(D,s,t,\\Delta\)0:Subproblem bitvector

DD, exhaustive threshold indices

s,ts,t, and gap

Δ\\Delta
1:if

Δ≤0\\Delta\\leq 0then

2:returntrue

3:endif

4:

z←0z\\leftarrow 0
5:foreach machine word

wwdo

6:

z←z\+Popcount​\(Dw∧\(Xs,w⊕Xt,w\)\)z\\leftarrow z\+\\textsc\{Popcount\}\\\!\\left\(D\_\{w\}\\wedge\(X\_\{s,w\}\\oplus X\_\{t,w\}\)\\right\)
7:if

z≥Δz\\geq\\Deltathen

8:returntrue

9:endif

10:endfor

11:returnfalse

We also provide pseudocode for calculating the number of samples that exhibit predictive multiplicity and the number of features used in the Rashomon graph\. See Algorithms[21](https://arxiv.org/html/2608.04310#alg21),[22](https://arxiv.org/html/2608.04310#alg22),[23](https://arxiv.org/html/2608.04310#alg23), and[24](https://arxiv.org/html/2608.04310#alg24)\.

Algorithm 21CountSamplesWithMultiplePredictions\(G,X\)\(G,X\)0:Root OR node

GGof the Rashomon graph and training samples

XX
1:

m←0m\\leftarrow 0
2:foreach sample

xi∈Xx\_\{i\}\\in Xdo

3:

𝒴i←ReachablePredictions​\(G,xi\)\\mathcal\{Y\}\_\{i\}\\leftarrow\\textsc\{ReachablePredictions\}\(G,x\_\{i\}\)
4:if

\|𝒴i\|≥2\|\\mathcal\{Y\}\_\{i\}\|\\geq 2then

5:

m←m\+1m\\leftarrow m\+1
6:endif

7:endfor

8:return

mm

Algorithm 22ReachablePredictions\(G,x\)\(G,x\)0:OR node

GGand sample

xx
1:

𝒴reachable←∅\\mathcal\{Y\}\_\{\\mathrm\{reachable\}\}\\leftarrow\\emptyset
2:foreach leaf choice

ℓ\\ellstored in

GGdo

3:

𝒴reachable←𝒴reachable∪\{Prediction​\(ℓ\)\}\\mathcal\{Y\}\_\{\\mathrm\{reachable\}\}\\leftarrow\\mathcal\{Y\}\_\{\\mathrm\{reachable\}\}\\cup\\\{\\textsc\{Prediction\}\(\\ell\)\\\}
4:endfor

5:foreach split choice

ssstored in

GGdo

6:if

xxsatisfies the split condition of

ssthen

7:

G′←LeftChild​\(s\)G^\{\\prime\}\\leftarrow\\textsc\{LeftChild\}\(s\)
8:else

9:

G′←RightChild​\(s\)G^\{\\prime\}\\leftarrow\\textsc\{RightChild\}\(s\)
10:endif

11:

𝒴reachable←𝒴reachable∪ReachablePredictions​\(G′,x\)\\mathcal\{Y\}\_\{\\mathrm\{reachable\}\}\\leftarrow\\mathcal\{Y\}\_\{\\mathrm\{reachable\}\}\\cup\\textsc\{ReachablePredictions\}\(G^\{\\prime\},x\)
12:if

\|𝒴reachable\|≥2\|\\mathcal\{Y\}\_\{\\mathrm\{reachable\}\}\|\\geq 2then

13:return

𝒴reachable\\mathcal\{Y\}\_\{\\mathrm\{reachable\}\}\{The sample already has conflicting predictions\}

14:endif

15:endfor

16:return

𝒴reachable\\mathcal\{Y\}\_\{\\mathrm\{reachable\}\}

Algorithm 23CountGraphFeatures\(G\)\(G\)0:Root OR node

GGof the Rashomon graph

1:

ℱ←∅\\mathcal\{F\}\\leftarrow\\emptyset
2:

𝒱←∅\\mathcal\{V\}\\leftarrow\\emptyset
3:

CollectGraphFeatures​\(G,ℱ,𝒱\)\\textsc\{CollectGraphFeatures\}\(G,\\mathcal\{F\},\\mathcal\{V\}\)
4:return

\|ℱ\|\|\\mathcal\{F\}\|

Algorithm 24CollectGraphFeatures\(G,ℱ,𝒱\)\(G,\\mathcal\{F\},\\mathcal\{V\}\)0:OR node

GG, set of encountered features

ℱ\\mathcal\{F\}, and set of visited OR nodes

𝒱\\mathcal\{V\}
1:if

G=∅G=\\emptysetor

G∈𝒱G\\in\\mathcal\{V\}then

2:return

3:endif

4:

𝒱←𝒱∪\{G\}\\mathcal\{V\}\\leftarrow\\mathcal\{V\}\\cup\\\{G\\\}
5:foreach split choice

ssstored in

GGdo

6:

j←OriginalFeature​\(SplitFeature​\(s\)\)j\\leftarrow\\textsc\{OriginalFeature\}\(\\textsc\{SplitFeature\}\(s\)\)\{Map all thresholds of one continuous feature to the same feature\}

7:

ℱ←ℱ∪\{j\}\\mathcal\{F\}\\leftarrow\\mathcal\{F\}\\cup\\\{j\\\}
8:

CollectGraphFeatures​\(LeftChild​\(s\),ℱ,𝒱\)\\textsc\{CollectGraphFeatures\}\(\\textsc\{LeftChild\}\(s\),\\mathcal\{F\},\\mathcal\{V\}\)
9:

CollectGraphFeatures​\(RightChild​\(s\),ℱ,𝒱\)\\textsc\{CollectGraphFeatures\}\(\\textsc\{RightChild\}\(s\),\\mathcal\{F\},\\mathcal\{V\}\)
10:endfor

We also provide a more efficient implementation ofGetKthTreeWithObjectivethan was present inHeileet al\.\([2026](https://arxiv.org/html/2608.04310#bib.bib156)\)\. For full context, see Algorithm 12\-14 inHeileet al\.\([2026](https://arxiv.org/html/2608.04310#bib.bib156)\)\.

Algorithm 25GetKthTreeWithObjective\(G,z,k\)\(G,z,k\)0:OR node

GG, target objective

zz, and zero\-indexed position

kkamong trees rooted at

GGwith objective

zz
1:

BuildHistogramsPost​\(G\)\\textsc\{BuildHistogramsPost\}\(G\)\{Ensure all objective histograms are available\}

2:\{Enumerate feasible leaves before splits\}

3:foreachleaf

\(b,ℓ\)∈Leaves​\(G\)\(b,\\ell\)\\in\\textsc\{Leaves\}\(G\)do

4:if

ℓ=z\\ell=zthen

5:if

k=0k=0then

6:return

MakeLeaf​\(b\)\\textsc\{MakeLeaf\}\(b\)
7:endif

8:

k←k−1k\\leftarrow k\-1
9:endif

10:endfor

11:\{Enumerate split trees in stored order\}

12:foreachsplit

s∈Splits​\(G\)s\\in\\textsc\{Splits\}\(G\)do

13:

GL←Left​\(s\)G\_\{L\}\\leftarrow\\textsc\{Left\}\(s\);

GR←Right​\(s\)G\_\{R\}\\leftarrow\\textsc\{Right\}\(s\)
14:

c←0c\\leftarrow 0\{Number of objective\-

zztrees encountered under this split\}

15:foreach

\(zL,nL\)∈Histogram​\(GL\)\(z\_\{L\},n\_\{L\}\)\\in\\textsc\{Histogram\}\(G\_\{L\}\)do

16:

zR←z−zLz\_\{R\}\\leftarrow z\-z\_\{L\}
17:

nR←HistogramCount​\(GR,zR\)n\_\{R\}\\leftarrow\\textsc\{HistogramCount\}\(G\_\{R\},z\_\{R\}\)\{Use binary search in the sorted histogram to find the number of trees with objective

zRz\_\{R\}\}

18:if

nR\>0n\_\{R\}\>0then

19:

n←nL​nRn\\leftarrow n\_\{L\}n\_\{R\}\{Number of trees in this Cartesian\-product block\}

20:if

k<c\+nk<c\+nthen

21:

q←k−cq\\leftarrow k\-c
22:

kL←⌊q/nR⌋k\_\{L\}\\leftarrow\\left\\lfloor q/n\_\{R\}\\right\\rfloor
23:

kR←qmodnRk\_\{R\}\\leftarrow q\\bmod n\_\{R\}
24:

TL←GetKthTreeWithObjective​\(GL,zL,kL\)T\_\{L\}\\leftarrow\\textsc\{GetKthTreeWithObjective\}\(G\_\{L\},z\_\{L\},k\_\{L\}\)
25:

TR←GetKthTreeWithObjective​\(GR,zR,kR\)T\_\{R\}\\leftarrow\\textsc\{GetKthTreeWithObjective\}\(G\_\{R\},z\_\{R\},k\_\{R\}\)
26:return

MakeSplit​\(Feature​\(s\),TL,TR\)\\textsc\{MakeSplit\}\(\\textsc\{Feature\}\(s\),T\_\{L\},T\_\{R\}\)
27:endif

28:

c←c\+nc\\leftarrow c\+n
29:endif

30:endfor

31:

k←k−ck\\leftarrow k\-c\{Skip all objective\-

zztrees under this split\}

32:endfor

### A\.10AND/OR Graph Caching

![Refer to caption](https://arxiv.org/html/2608.04310v1/tiedgraph.png)Figure 3:An example graph structure for encoding a Rashomon set\. The OR nodes at the bottom of this figure have more split/leaf choices connected to them\. We now state what must be true about these features \(F1, F2, F3, F4, F5, and F6\) for this graph to be built the way it is\. It does not matter whether these are truly binary features or a threshold of a continuous feature\.Assumption 1:F2 and F3 are the same if F1 is True\. Thus, the nodes on the far left connect to the same children \(and they need the same budget\)Assumption 2:\!F3 & F5 gives the same bitvector as \!F4 & \!F6\. They may need the same budget; they also may not need the same budget\. The OR node encodes solutions for the larger of the two budgets, so that it works for both\.Remaining Remark:The remaining shared children are due to conjunctions of literals being invariant to permutation\.Without caching Rashomon subgraphs, the enumeration builds a trie over sequences of split decisions\. That is, each root\-to\-node path corresponds to an ordered sequence of splits encountered by the recursion\. This representation is order\-dependent: two different split sequences may reach the same subproblem, but they are still represented by different nodes because they arise from different paths in the recursion\.

A first improvement is to cache Rashomon subgraphs by subproblem, remaining depth, and budget\. This changes the data structure from an acyclic AND/OR graph that is a trie into an acyclic AND/OR graph that isn’t a trie\. The graph is still acyclic because every split decreases the remaining depth and restricts the active sample set, but an OR node may now have multiple parents\. Conceptually, this is simply duplicate elimination: whenever two recursive paths reach the same subproblem with the same remaining depth and budget, we store one canonical OR node and point both parents to it\. We note that this caching covers more than just permutations of split choices because we use cache based on what samples are in the subproblem\. That set of samples can be reached in many different ways\.

We push this idea further by making the cache independent of the budget\. Instead of storing separate subgraphs for the same subproblem and remaining depth under different budgets, we store a single canonical OR node for each pair\(D,d\)\(D,d\)\. This node represents the largest budget under which that subproblem has so far been expanded\. If the same subproblem is later reached with a budget that is no larger than the stored budget, we return the existing node\. If it is reached with a larger budget, we extend the existing node in place\. Thus, at no point do we maintain more than one subgraph for the same subproblem\-depth pair \(i\.e\., this is not a deduplication step at the end of the algorithm, but the algorithm never maintains more than one at a time\)\.

This does not lose information because any smaller\-budget Rashomon set can be carved out of the larger\-budget subgraph during extraction\. In fact, in the approximation regime, this can lead to more trees recovered, because approximation algorithms return a subset of trees with budgetεabs\\varepsilon\_\{\\textrm\{abs\}\}at each subproblem\. The larger graph may contain split or leaf choices whose objectives exceed a smaller requested budget, we claim that these choices are can be ignored when extracting trees under that smaller budget\.

It remains to explain why this is compatible with the objective histograms used for indexing trees\. For each OR node, we store a histogram

HG=\{\(o,c\)\},H\_\{G\}=\\\{\(o,c\)\\\},whereoois an achievable objective value for a subtree rooted atGG, andccis the number of such subtrees with objectiveoo\. Leaf choices contribute one unit of mass to the bucket corresponding to their leaf objective\. A split contributes by combining the histograms of its two children\. If the left and right child histograms contain entries\(oL,cL\)\(o\_\{L\},c\_\{L\}\)and\(oR,cR\)\(o\_\{R\},c\_\{R\}\), respectively, then the split contributes

\(oL\+oR,cL​cR\)\(o\_\{L\}\+o\_\{R\},\\;c\_\{L\}c\_\{R\}\)to the parent histogram, provided that

oL\+oR≤εG,o\_\{L\}\+o\_\{R\}\\leq\\varepsilon\_\{G\},whereεG\\varepsilon\_\{G\}is the budget of the parent OR node\. That is, the propagation step is a budget\-filtered cross product, of the two child histograms\.

Because histograms are built after the graph has been expanded, there are no issues with them becoming stale\. We also remark that while we are storing one OR node where other representations store multiple, this is not true at the root node\. The root node has a single budget and its histogram is filtered exactly to the Rashomon budget of interest\.

In summary, internal OR nodes may store more information than their parent needs\. However, when that parent combines the child histograms, it applies its own budget filter to the child objective pairs\. Therefore, even if a child histogram contains entries enabled by a larger budget, only child subtrees that fit within the parent’s remaining budget contribute to the parent’s histogram\. This means that tasks like "finding the 50th tree in the Rashomon set", which map to finding the 7th tree with objective 112 are unchanged, if we get to a node that has more information than we need, that doesn’t effect the indexing operations\.

Thus, indexing operations are unchanged\. For example, finding the 50th tree in the Rashomon set may reduce to finding the 7th tree with objective 112 in a child subgraph; this is the type of recursive indexing used byHeileet al\.\([2026](https://arxiv.org/html/2608.04310#bib.bib156)\)to enumerate trees in sorted order\. The procedure identifies the split containing the desired tree, then recurses on the left and right child subgraphs, asking for theL1L\_\{1\}th left subtree with objectiveL2L\_\{2\}and theR1R\_\{1\}th right subtree with objectiveR2R\_\{2\}\.

The presence of additional trees in the cached child subgraph does not affect this query, because those extra trees have objectives above the budget relevant to the parent query\. Indexing only scans histogram entries with the target objective or smaller, and these entries are guaranteed to be fully represented in the cached graph: the cached graph has been expanded to at least the budget needed for the current query\. Therefore, the larger cached subgraph behaves exactly like the smaller\-budget subgraph for sorted\-order indexing\.

## Appendix BTheoretical Results

![Refer to caption](https://arxiv.org/html/2608.04310v1/budgetgraph.png)Figure 4:An example showing a dataset where the subproblem\{s\}\\\{\\text\{s\}\\\}is reached withMMdifferent budgets\. This is accomplished by usingMMdifferent splits at the root \(they can be viewed as being part of the same continuous feature\)\. There are2​M\+12M\+1samples\.PiP\_\{i\}are points with positive labels,NiN\_\{i\}are points with negative labels,ssis a special point\.εabs\\varepsilon\_\{\\text\{abs\}\}is the budget at the root\. We assume an optimal proxy\.###### Theorem 1\(Distinct Budgets for One Subproblem\)\.

Fix depth budgetd=2d=2\. For everyMM, there exists a binary classification dataset withn=2​M\+1n=2M\+1samples andMMbinary features such that the same subproblem is reached withM=Ω​\(n\)M=\\Omega\(n\)distinct remaining budgets\. Thus, a budget\-dependent AND/OR graph that keys nodes by\(D,d,B\)\(D,d,B\)may storeΩ​\(n\)\\Omega\(n\)OR nodes for a single canonical subproblem\(D,d\)\(D,d\), while a budget\-independent representation stores only one\.

###### Proof\.

Letγ\\gammadenote the leaf penalty, and chooseγ\>M\\gamma\>M\. We consider an optimal Rashomon set algorithm\. It may or may not use bounds for continuous features\. Construct a dataset consisting of one special pointss, positive pointsP1,…,PMP\_\{1\},\\ldots,P\_\{M\}, and negative pointsN1,…,NMN\_\{1\},\\ldots,N\_\{M\}\. Thusn=2​M\+1n=2M\+1\. Assign labels

y​\(s\)=0,y​\(Pi\)=1,y​\(Ni\)=0\.y\(s\)=0,\\qquad y\(P\_\{i\}\)=1,\\qquad y\(N\_\{i\}\)=0\.Use a continuous featurexxwhose ordering is

s,P1,P2,…,PM,N1,…,NM\.s,P\_\{1\},P\_\{2\},\\ldots,P\_\{M\},N\_\{1\},\\ldots,N\_\{M\}\.For eachi=1,…,Mi=1,\\ldots,M, let the thresholdx≤τix\\leq\\tau\_\{i\}split the data into

Li=\{s,P1,…,Pi\},Ri=\{Pi\+1,…,PM,N1,…,NM\}\.L\_\{i\}=\\\{s,P\_\{1\},\\ldots,P\_\{i\}\\\},\\qquad R\_\{i\}=\\\{P\_\{i\+1\},\\ldots,P\_\{M\},N\_\{1\},\\ldots,N\_\{M\}\\\}\.Also include a binary featurezzsatisfying

z​\(s\)=1,z​\(Pi\)=z​\(Ni\)=0\.z\(s\)=1,\\qquad z\(P\_\{i\}\)=z\(N\_\{i\}\)=0\.
Therefore, after taking thresholdx≤τix\\leq\\tau\_\{i\}, a split onzzinsideLiL\_\{i\}produces the two children

\{s\}and\{P1,…,Pi\}\.\\\{s\\\}\\qquad\\text\{and\}\\qquad\\\{P\_\{1\},\\ldots,P\_\{i\}\\\}\.Hence, for everyii, the same subproblemS=\{s\}S=\\\{s\\\}is reached after two splits\. It remains to show that the remaining budget at this same subproblem depends onii\. Let the root budgetεabs\\varepsilon\_\{\\mathrm\{abs\}\}be large enough that all these trees are feasible; for concreteness, take

εabs=4​γ\.\\varepsilon\_\{\\mathrm\{abs\}\}=4\\gamma\.Sinceγ\>M\\gamma\>M, no depth\-one split insideRiR\_\{i\}is cheaper than predicting a single leaf\. Thus

Opt⁡\(Ri,1\)=γ\+\(M−i\),\\operatorname\{Opt\}\(R\_\{i\},1\)=\\gamma\+\(M\-i\),becauseRiR\_\{i\}containsM−iM\-ipositive points andMMnegative points, so the minority class has sizeM−iM\-i\. The other sibling,\{P1,…,Pi\}\\\{P\_\{1\},\\ldots,P\_\{i\}\\\}, is pure, so

Opt⁡\(\{P1,…,Pi\},0\)=γ\.\\operatorname\{Opt\}\(\\\{P\_\{1\},\\ldots,P\_\{i\}\\\},0\)=\\gamma\.
Therefore, the budget remaining for the shared subproblemS=\{s\}S=\\\{s\\\}along the path corresponding to thresholdiiis

Bi=εabs−Opt⁡\(Ri,1\)−Opt⁡\(\{P1,…,Pi\},0\)\.B\_\{i\}=\\varepsilon\_\{\\mathrm\{abs\}\}\-\\operatorname\{Opt\}\(R\_\{i\},1\)\-\\operatorname\{Opt\}\(\\\{P\_\{1\},\\ldots,P\_\{i\}\\\},0\)\.
Substituting the two expressions above gives

Bi=4​γ−\(γ\+M−i\)−γ=2​γ−M\+i\.B\_\{i\}=4\\gamma\-\(\\gamma\+M\-i\)\-\\gamma=2\\gamma\-M\+i\.
It remains to verify that the leafS=\{s\}S=\\\{s\\\}fits within each remaining budget\. SinceSSis pure and has remaining depth zero,

Opt⁡\(S,0\)=γ\.\\operatorname\{Opt\}\(S,0\)=\\gamma\.Using thatγ\>M\\gamma\>M, then for everyi=1,…,Mi=1,\\ldots,M,

Bi=2​γ−M\+i≥γ\.B\_\{i\}=2\\gamma\-M\+i\\geq\\gamma\.
ThusB1,B2,…,BMB\_\{1\},B\_\{2\},\\ldots,B\_\{M\}are all distinct and achievable within the fixed root budget\. A budget\-dependent graph may therefore create theMMdistinct OR nodes

\(S,0,B1\),\(S,0,B2\),…,\(S,0,BM\),\(S,0,B\_\{1\}\),\(S,0,B\_\{2\}\),\\ldots,\(S,0,B\_\{M\}\),
even though the active sample set and remaining depth are identical in all cases\. A budget\-independent graph instead creates one canonical OR node\(S,0\)\(S,0\)and extends it as larger budgets are encountered\. Sincen=2​M\+1n=2M\+1, this is aΩ​\(n\)\\Omega\(n\)\-factor reduction in OR\-node count for this subproblem\. Onnnsamples, the mistakes term takes at mostn\+1n\+1values, and the number of leaves is at mostnn\(we do not consider leaves with zero\-support in our algorithms, consistent withArslanet al\.\([2025](https://arxiv.org/html/2608.04310#bib.bib131)\); Heileet al\.\([2026](https://arxiv.org/html/2608.04310#bib.bib156)\); Xinet al\.\([2022](https://arxiv.org/html/2608.04310#bib.bib126)\)\)\. ∎

The previous theorem is related \(but not exactly equivalent\) to howArslanet al\.\([2025](https://arxiv.org/html/2608.04310#bib.bib131)\)stores Rashomon sets\. Their implementation uses a BranchTracker together with a UB parameter, which is analogous to our objective budget\. From inspecting SORTeD, we find that the representation is not fully budget\-independent\. It avoids duplicate cached entries when an existing cached UB dominates the requested UB; however, if the same subproblem is later requested with a larger UB, SORTeD constructs a new tracker state rather than extending or merging the old one in place\. This theorem does not directly apply to SORTeD, but, something else does\. Thus, SORTeD supports restricting a previously computed solution set, but not expanding it\. Consequently, repeatedly loosening the root budget forces previously solved subproblems to be recomputed under larger descendant budgets \(without a natural "extend" operation\), without the opportunity for incremental subgraph reuse\.

We now connect to TreeFARMS ofXinet al\.\([2022](https://arxiv.org/html/2608.04310#bib.bib126)\), showing the analogous bound except for their model sets\. TreeFARMS allowsγ\\gammato be non\-integer, so beyond this lower bound \(which holds ever for integerγ\\gamma\), there may be even more duplication\.

###### Theorem 2\(Distinct Objectives for One Subproblem\)\.

Fix depth budgetd=1d=1\. For everyMM, there exists a binary classification dataset withn=2​Mn=2Msamples andMMbinary features such that a single subproblem\-depth pairSShasM=Ω​\(n\)M=\\Omega\(n\)distinct achievable objective values among depth\-one trees\. Therefore, a model\-set representation that identifies instances by\(S,objective\)\(S,\\mathrm\{objective\}\), as in TreeFARMS, will storeΩ​\(n\)\\Omega\(n\)distinct model\-set instances for the same subproblem\-depth pairSS\. A budget\-independent representation that keys the subproblem only bySSand stores all objective realizations beneath that node stores only one canonical subproblem node\.

###### Proof\.

Letγ\\gammadenote the leaf penalty\. Construct a binary classification dataset with positive points

P1,…,PMP\_\{1\},\\ldots,P\_\{M\}and negative points

N1,…,NM\.N\_\{1\},\\ldots,N\_\{M\}\.Thusn=2​Mn=2M\. Let the subproblem that we refer to in the theorem statement be the full support

S=\{P1,…,PM,N1,…,NM\}\.S=\\\{P\_\{1\},\\ldots,P\_\{M\},N\_\{1\},\\ldots,N\_\{M\}\\\}\.
We do not continue to remind the reader thatSSis paired with a depth budget of 1; we instead take it to be implied\.

For eachi=1,…,Mi=1,\\ldots,M, define a binary featureziz\_\{i\}by

zi​\(Pj\)=1if and only if​j≤i,zi​\(Nj\)=0for all​j\.z\_\{i\}\(P\_\{j\}\)=1\\quad\\text\{if and only if \}j\\leq i,\\qquad z\_\{i\}\(N\_\{j\}\)=0\\quad\\text\{for all \}j\.SplittingSSonziz\_\{i\}gives the two children

Li=\{P1,…,Pi\},Ri=\{Pi\+1,…,PM,N1,…,NM\}\.L\_\{i\}=\\\{P\_\{1\},\\ldots,P\_\{i\}\\\},\\qquad R\_\{i\}=\\\{P\_\{i\+1\},\\ldots,P\_\{M\},N\_\{1\},\\ldots,N\_\{M\}\\\}\.The left childLiL\_\{i\}is pure positive, so its leaf misclassification cost is zero\. The right childRiR\_\{i\}containsM−iM\-ipositives andMMnegatives, so its optimal leaf prediction is negative and its misclassification cost isM−iM\-i\. Therefore, the objective of the depth\-one tree that splits onziz\_\{i\}is

Obji=\(M−i\)\+2​γ,\\mathrm\{Obj\}\_\{i\}=\(M\-i\)\+2\\gamma,because the tree has two leaves\. Asiiranges from11toMM, the values

2​γ\+M−1,2​γ\+M−2,…,2​γ2\\gamma\+M\-1,\\quad 2\\gamma\+M\-2,\\quad\\ldots,\\quad 2\\gammaare all distinct\. Hence the same canonical subproblemSShasMMdistinct achievable objective values within depth budgetd=1d=1\.

Now choose the Rashomon threshold large enough to include all these trees, for example

≥2​γ\+M−1\.\\geq 2\\gamma\+M\-1\.Then allMMdepth\-one trees belong to the Rashomon set\. We can also include single\-leaf trees with either a positive or negative predicting leaf \(depending on the budget\)\. ∎

We now connect to PRAXIS ofHeileet al\.\([2026](https://arxiv.org/html/2608.04310#bib.bib156)\), showing a much stronger bound because there is no subgraph caching, only caching of proxy solutions\.

###### Theorem 3\(Factorial Path Duplication\)\.

For every depthdd, there exists a binary classification dataset withddbinary features such that, if the Rashomon budget contains all depth\-ddtrees, then every depth zero subproblem is represented at leastd\!d\!times in the representation fromHeileet al\.\([2026](https://arxiv.org/html/2608.04310#bib.bib156)\), but only once in a canonical AND/OR graph keyed by active sample set and remaining depth\.

###### Proof\.

Let the dataset contain one sample for each binary vector in\{0,1\}d\\\{0,1\\\}^\{d\}, with featuresx1,…,xdx\_\{1\},\\ldots,x\_\{d\}\. Take the Rashomon budget large enough that every depth\-ddtree is feasible\.

Fix any samplev=\(v1,…,vd\)∈\{0,1\}dv=\(v\_\{1\},\\ldots,v\_\{d\}\)\\in\\\{0,1\\\}^\{d\}, and let

Sv=\{x∈\{0,1\}d:xj=vj​for all​j=1,…,d\}\.S\_\{v\}=\\\{x\\in\\\{0,1\\\}^\{d\}:x\_\{j\}=v\_\{j\}\\text\{ for all \}j=1,\\ldots,d\\\}\.This identifies a subregion containing onlyvv\. For any permutationπ\\piof\{1,…,d\}\\\{1,\\ldots,d\\\}, consider the path that splits first onxπ​\(1\)x\_\{\\pi\(1\)\}, then onxπ​\(2\)x\_\{\\pi\(2\)\}, and so on, always following the branch

xπ​\(k\)=vπ​\(k\)\.x\_\{\\pi\(k\)\}=v\_\{\\pi\(k\)\}\.After allddsplits, the active sample set is

\{x:xπ​\(1\)=vπ​\(1\),…,xπ​\(d\)=vπ​\(d\)\}=Sv\.\\\{x:x\_\{\\pi\(1\)\}=v\_\{\\pi\(1\)\},\\ldots,x\_\{\\pi\(d\)\}=v\_\{\\pi\(d\)\}\\\}=S\_\{v\}\.Thus the same depth\-zero subproblem\(Sv,0\)\(S\_\{v\},0\)is reached by alld\!d\!feature orderings\.

The representation inHeileet al\.\([2026](https://arxiv.org/html/2608.04310#bib.bib156)\)caches proxy solutions based on caching a bitvector representing what samples are in the subproblem, but does not cache AND/OR subgraphs\. Thus, the only way that AND/OR subgraphs are attached is by directly following the recursion path, which is ordered\. That means that the representation inHeileet al\.\([2026](https://arxiv.org/html/2608.04310#bib.bib156)\)is stored in memory as a path\-based trie and identifies subproblems by the ordered sequence of splits used to reach them, even if the bitvector\-based caching of subproblems allows for quick construction of a subgraph for the same problem\. Thus, under the representation fromHeileet al\.\([2026](https://arxiv.org/html/2608.04310#bib.bib156)\), thesed\!d\!orderings created\!d\!distinct nodes for the same subproblem\(Sv,0\)\(S\_\{v\},0\)\. In contrast, a canonical AND/OR graph identifies subproblems by their active sample set and remaining depth\. Therefore, all of these paths point to a single OR node for\(Sv,0\)\(S\_\{v\},0\)\. Sincevvwas arbitrary, the claim holds for every depth\-zero subproblem\. ∎

The following results characterize what happens as a continuous feature is binarized using increasingly many thresholds: as the selected thresholds better approximate the full set of continuous splits, the worst\-case optimality gap decreases according to Theorem[4](https://arxiv.org/html/2608.04310#Thmtheorem4)\. Theorems[5](https://arxiv.org/html/2608.04310#Thmtheorem5)–[8](https://arxiv.org/html/2608.04310#Thmtheorem8)give concrete ways to select thresholds within each feature while controlling this approximation error and, in some cases, the number of thresholds required\. We also study how to refine an existing threshold set by adding new thresholds, directly connecting these guarantees to our anytime algorithm\. In particular, Theorem[9](https://arxiv.org/html/2608.04310#Thmtheorem9)shows that one midpoint\-refinement round reduces the covering radius fromδ\\deltato at most⌈δ/2⌉\\lceil\\delta/2\\rceil\.

###### Theorem 4\(Binarization Optimality Gap\)\.

LetD=\{\(xi,yi\)\}i=1nD=\\\{\(x\_\{i\},y\_\{i\}\)\\\}\_\{i=1\}^\{n\}be a binary classification dataset with continuous features\. Consider decision trees of depth at mostddwith objective

Obj​\(T,D,γ\)=misclassifications​\(T;D\)\+γ​\|Leaves​\(T\)\|\.\\mathrm\{Obj\}\(T,D,\\gamma\)=\\mathrm\{misclassifications\}\(T;D\)\+\\gamma\|\\mathrm\{Leaves\}\(T\)\|\.Letℋcont\\mathcal\{H\}\_\{\\mathrm\{cont\}\}denote the set of all continuous threshold splits and letℋbin\\mathcal\{H\}\_\{\\mathrm\{bin\}\}denote a restricted set of binary threshold columns\.

Assume thatℋbin\\mathcal\{H\}\_\{\\mathrm\{bin\}\}satisfies the following Hamming snapping condition: for every continuous threshold splith∈ℋconth\\in\\mathcal\{H\}\_\{\\mathrm\{cont\}\}, there exists a binary threshold splith^∈ℋbin\\hat\{h\}\\in\\mathcal\{H\}\_\{\\mathrm\{bin\}\}such that

dH​\(h,h^\):=\|\{i:h​\(xi\)≠h^​\(xi\)\}\|≤δ\.d\_\{H\}\(h,\\hat\{h\}\):=\\left\|\\\{i:h\(x\_\{i\}\)\\neq\\hat\{h\}\(x\_\{i\}\)\\\}\\right\|\\leq\\delta\.Then

OPTbin​\(D,d\)−OPTcont​\(D,d\)≤\(2d−1\)​δ,\\mathrm\{OPT\}\_\{\\mathrm\{bin\}\}\(D,d\)\-\\mathrm\{OPT\}\_\{\\mathrm\{cont\}\}\(D,d\)\\leq\(2^\{d\}\-1\)\\delta,whereOPTcont​\(D,d\)\\mathrm\{OPT\}\_\{\\mathrm\{cont\}\}\(D,d\)is the optimal objective over depth\-ddtrees using arbitrary continuous thresholds, andOPTbin​\(D,d\)\\mathrm\{OPT\}\_\{\\mathrm\{bin\}\}\(D,d\)is the optimal objective over depth\-ddtrees using only splits fromℋbin\\mathcal\{H\}\_\{\\mathrm\{bin\}\}\.

###### Proof\.

LetT⋆T^\{\\star\}be an optimal depth\-ddcontinuous\-threshold tree\. We construct a treeT^\\widehat\{T\}with the same topology and the same leaf predictions asT⋆T^\{\\star\}, but with each internal split replaced by its snapped binary split\.

A depth\-ddbinary tree has at most2d−12^\{d\}\-1internal nodes\. By the Hamming snapping assumption, each internal split ofT⋆T^\{\\star\}can be replaced by a binary split that disagrees with it on at mostδ\\deltatraining samples\. When one split is replaced, only samples whose branch assignment changes at that split can possibly change their final leaf assignment\. Therefore, replacing one split can change the prediction of at mostδ\\deltatraining samples, and hence can increase the number of misclassifications by at mostδ\\delta\.

Applying this argument to every internal node and taking a union bound, replacing all internal splits increases the number of misclassifications by at most

\(2d−1\)​δ\.\(2^\{d\}\-1\)\\delta\.The snapped treeT^\\widehat\{T\}has the same topology asT⋆T^\{\\star\}, so it has the same number of leaves\. Hence the leaf penalty is unchanged:

γ​\|Leaves​\(T^\)\|=γ​\|Leaves​\(T⋆\)\|\.\\gamma\|\\mathrm\{Leaves\}\(\\widehat\{T\}\)\|=\\gamma\|\\mathrm\{Leaves\}\(T^\{\\star\}\)\|\.Thus

Obj​\(T^;D\)≤Obj​\(T⋆;D\)\+\(2d−1\)​δ\.\\mathrm\{Obj\}\(\\widehat\{T\};D\)\\leq\\mathrm\{Obj\}\(T^\{\\star\};D\)\+\(2^\{d\}\-1\)\\delta\.SinceT^\\widehat\{T\}is feasible for the binarized problem,

OPTbin​\(D,d\)≤Obj​\(T^;D\)\.\\mathrm\{OPT\}\_\{\\mathrm\{bin\}\}\(D,d\)\\leq\\mathrm\{Obj\}\(\\widehat\{T\};D\)\.Combining this withObj​\(T⋆;D\)=OPTcont​\(D,d\)\\mathrm\{Obj\}\(T^\{\\star\};D\)=\\mathrm\{OPT\}\_\{\\mathrm\{cont\}\}\(D,d\)gives

OPTbin​\(D,d\)−OPTcont​\(D,d\)≤\(2d−1\)​δ\.\\mathrm\{OPT\}\_\{\\mathrm\{bin\}\}\(D,d\)\-\\mathrm\{OPT\}\_\{\\mathrm\{cont\}\}\(D,d\)\\leq\(2^\{d\}\-1\)\\delta\.∎

Algorithm 26Greedy threshold selection algorithm0:Attainable split ranks

Rj=\{r1<⋯<rm\}R\_\{j\}=\\\{r\_\{1\}<\\cdots<r\_\{m\}\\\}, radius

δ\\delta
1:

Bj←∅B\_\{j\}\\leftarrow\\emptyset,

i←1i\\leftarrow 1
2:while

i≤mi\\leq mdo

3:

a←ria\\leftarrow r\_\{i\}
4:Let

qqbe the largest index such that

rq≤a\+δr\_\{q\}\\leq a\+\\delta
5:

Bj←Bj∪\{rq\}B\_\{j\}\\leftarrow B\_\{j\}\\cup\\\{r\_\{q\}\\\}
6:Set

iito the smallest index such that

ri\>rq\+δr\_\{i\}\>r\_\{q\}\+\\delta
7:endwhile

8:return

BjB\_\{j\}

Algorithm[26](https://arxiv.org/html/2608.04310#alg26)provides one way to choose different thresholds for a continuous feature such that every split on a midpoint of two unique values is withinδ\\deltaof a chosen threshold\. This is a standard greedy algorithm that appears in scheduling or covering problems\. As we show in Theorem[5](https://arxiv.org/html/2608.04310#Thmtheorem5), it is optimal because we are working in 1D \(handling one continuous feature at a time\)\.

###### Theorem 5\(Selecting Thresholds with Covering Radius Guarantee\)\.

Fix a continuous featurejjand let

Rj=\{r1<⋯<rm\}R\_\{j\}=\\\{r\_\{1\}<\\cdots<r\_\{m\}\\\}be its attainable split ranks, i\.e\., the cumulative sample counts after each distinct feature value\. For any integerδ≥0\\delta\\geq 0, Algorithm[26](https://arxiv.org/html/2608.04310#alg26)returns a setBj⊆RjB\_\{j\}\\subseteq R\_\{j\}such that

maxr∈Rj⁡minb∈Bj⁡\|r−b\|≤δ\.\\max\_\{r\\in R\_\{j\}\}\\min\_\{b\\in B\_\{j\}\}\|r\-b\|\\leq\\delta\.Moreover, among subsets ofRjR\_\{j\}with the above covering radius guarantee \(at mostδ\\delta\), the algorithm uses the minimum possible number of selected thresholds\.

###### Proof\.

Letaabe the leftmost uncovered attainable rank\. Any selected rank that coversaamust lie inRj∩\(−∞,a\+δ\]R\_\{j\}\\cap\(\-\\infty,a\+\\delta\]\. The algorithm chooses the largest such rank, saybb\. This choice covers all attainable ranks up tob\+δb\+\\delta\. No feasible solution can coveraausing a selected rank to the right ofbb, becausebbis the largest attainable rank within distanceδ\\deltaofaa\. Therefore, replacing the first selected rank of any optimal solution bybbcannot decrease the set of ranks covered to the right\. After removing the ranks covered bybb, the same argument applies recursively to the remaining suffix\. Thus the greedy algorithm is optimal\. The covering property follows directly from the construction\. ∎

###### Theorem 6\(Optimality Gap induced by Threshold\-Selection\)\.

For each continuous featurejj, constructBjB\_\{j\}using Algorithm[26](https://arxiv.org/html/2608.04310#alg26)with radiusδ\\delta, and letℋbin\\mathcal\{H\}\_\{\\mathrm\{bin\}\}be the corresponding selected threshold columns\. Then

OPTbin​\(D,d\)−OPTcont​\(D,d\)≤\(2d−1\)​δ\.\\mathrm\{OPT\}\_\{\\mathrm\{bin\}\}\(D,d\)\-\\mathrm\{OPT\}\_\{\\mathrm\{cont\}\}\(D,d\)\\leq\(2^\{d\}\-1\)\\,\\delta\.Consequently, choosing

δ≤ϵ2d−1\\delta\\leq\\frac\{\\epsilon\\,\}\{2^\{d\}\-1\}gives a objective gap of at mostϵ\\epsilon\.

###### Proof\.

Every continuous threshold on featurejjis equivalent on the training data to one attainable rankr∈Rjr\\in R\_\{j\}, since tied feature values cannot be separated\. By Theorem[5](https://arxiv.org/html/2608.04310#Thmtheorem5), there exists a selected rankb∈Bjb\\in B\_\{j\}with\|r−b\|≤δ\|r\-b\|\\leq\\delta\. The corresponding threshold columns differ on exactly the samples whose ranks lie betweenrrandbb, so their Hamming distance is at mostδ\\delta\. Thusℋbin\\mathcal\{H\}\_\{\\mathrm\{bin\}\}satisfies the Hamming snapping condition of Theorem[4](https://arxiv.org/html/2608.04310#Thmtheorem4), and the bound\(2d−1\)​δ\(2^\{d\}\-1\)\\,\\deltafollows immediately\. ∎

###### Theorem 7\(Number of Thresholds for some Covering Radius\)\.

LetRj=\{r1<⋯<rm\}R\_\{j\}=\\\{r\_\{1\}<\\cdots<r\_\{m\}\\\}be the attainable split ranks for featurejj\. Algorithm[26](https://arxiv.org/html/2608.04310#alg26)selects at most

\|Bj\|≤⌈rm−r1\+12​δ\+1⌉≤⌈n2​δ\+1⌉\|B\_\{j\}\|\\leq\\left\\lceil\\frac\{r\_\{m\}\-r\_\{1\}\+1\}\{2\\delta\+1\}\\right\\rceil\\leq\\left\\lceil\\frac\{n\}\{2\\delta\+1\}\\right\\rceilthresholds\.

###### Proof\.

Each selected rank covers all attainable ranks within distanceδ\\delta, i\.e\., an interval of at most2​δ\+12\\delta\+1integer ranks\. Algorithm[26](https://arxiv.org/html/2608.04310#alg26)is optimal by Theorem[5](https://arxiv.org/html/2608.04310#Thmtheorem5), so it uses no more thresholds than are needed to cover the full integer interval\[r1,rm\]\[r\_\{1\},r\_\{m\}\]by intervals of length2​δ\+12\\delta\+1\. This requires at most

⌈rm−r1\+12​δ\+1⌉\\left\\lceil\\frac\{r\_\{m\}\-r\_\{1\}\+1\}\{2\\delta\+1\}\\right\\rceilintervals\. Sincerm−r1\+1≤nr\_\{m\}\-r\_\{1\}\+1\\leq n, the second bound follows\. ∎

###### Theorem 8\(Quantile Snapping Bound\)\.

Fix a continuous featurejjand a deterministic ordering of training samples by this feature, breaking ties arbitrarily\. Letℋrank\\mathcal\{H\}\_\{\\mathrm\{rank\}\}be the set of all prefix threshold columns in this ordering \(cuts between distinct values and within tied values\)\. For an integerK≥1K\\geq 1, select theKKquantile ranks

bq=⌊q​nK\+1⌉,q=1,…,K,b\_\{q\}=\\left\\lfloor\\frac\{q\\,n\}\{K\+1\}\\right\\rceil,\\qquad q=1,\\ldots,K,and letℋbin\\mathcal\{H\}\_\{\\mathrm\{bin\}\}be the corresponding threshold columns\. Then everyh∈ℋrankh\\in\\mathcal\{H\}\_\{\\mathrm\{rank\}\}has a selectedh^∈ℋbin\\hat\{h\}\\in\\mathcal\{H\}\_\{\\mathrm\{bin\}\}with

dH​\(h,h^\)≤⌈nK\+1⌉\.d\_\{H\}\(h,\\hat\{h\}\)\\leq\\left\\lceil\\frac\{n\}\{K\+1\}\\right\\rceil\.Consequently, Theorem[4](https://arxiv.org/html/2608.04310#Thmtheorem4)gives

OPTbin​\(D,d\)−OPTrank​\(D,d\)≤\(2d−1\)​⌈nK\+1⌉\.\\mathrm\{OPT\}\_\{\\mathrm\{bin\}\}\(D,d\)\-\\mathrm\{OPT\}\_\{\\mathrm\{rank\}\}\(D,d\)\\leq\(2^\{d\}\-1\)\\left\\lceil\\frac\{n\}\{K\+1\}\\right\\rceil\.

###### Proof\.

A prefix\-threshold column is determined by a prefix sizer∈\{1,…,n−1\}r\\in\\\{1,\\ldots,n\-1\\\}\. The Hamming distance between prefix columns of ranksrrandssis exactly\|r−s\|\|r\-s\|, since they differ precisely on the samples between the two prefix endpoints\. TheKKquantile ranks divide\{1,…,n−1\}\\\{1,\\ldots,n\-1\\\}intoK\+1K\+1intervals of length at most⌈n/\(K\+1\)⌉\\lceil n/\(K\+1\)\\rceil, so everyrrhas a quantile rankbqb\_\{q\}with\|r−bq\|≤⌈n/\(K\+1\)⌉\|r\-b\_\{q\}\|\\leq\\lceil n/\(K\+1\)\\rceil\. Applying Theorem[4](https://arxiv.org/html/2608.04310#Thmtheorem4)withδ=⌈n/\(K\+1\)⌉\\delta=\\lceil n/\(K\+1\)\\rceilgives the claimed bound\. ∎

Theorem[8](https://arxiv.org/html/2608.04310#Thmtheorem8)assumes a fixed tie\-breaking order\. In practice we use value thresholdsxj≤tx\_\{j\}\\leq tat empirical quantile values, deduplicate, and discard constant columns\. In the absence of ties this coincides with the rank construction above\. For Theorem[9](https://arxiv.org/html/2608.04310#Thmtheorem9), we make the same assumption\.

###### Theorem 9\(Midpoint Refinement Halves Covering Radius\)\.

Fix a continuous featurejjand fix a deterministic ordering of the training samples by this feature, breaking ties arbitrarily\. Let

Rjrank=\{1,…,n−1\}R\_\{j\}^\{\\mathrm\{rank\}\}=\\\{1,\\ldots,n\-1\\\}denote the set of nonconstant prefix ranks in this ordering \(i\.e\., eachr∈Rjrankr\\in R\_\{j\}^\{\\mathrm\{rank\}\}determines the prefix\-threshold column that assigns the firstrrsamples to one branch and the remaining samples to the other; ranks that split tied values are allowed\)\. ForB⊆RjrankB\\subseteq R\_\{j\}^\{\\mathrm\{rank\}\}, define its covering radius by

rad​\(B\)=maxr∈Rjrank⁡minb∈B⁡\|r−b\|\.\\mathrm\{rad\}\(B\)=\\max\_\{r\\in R\_\{j\}^\{\\mathrm\{rank\}\}\}\\min\_\{b\\in B\}\|r\-b\|\.Supposerad​\(B\)≤δ\\mathrm\{rad\}\(B\)\\leq\\delta\. FormB\+B^\{\+\}by adding toBB: for every adjacent pairb<b′b<b^\{\\prime\}inBB, the nearest integer rank to\(b\+b′\)/2\(b\+b^\{\\prime\}\)/2; for the left boundary interval\[1,bmin\]\[1,b\_\{\\min\}\], the nearest integer rank to\(1\+bmin\)/2\(1\+b\_\{\\min\}\)/2; and for the right boundary interval\[bmax,n−1\]\[b\_\{\\max\},n\-1\], the nearest integer rank to\(bmax\+n−1\)/2\(b\_\{\\max\}\+n\-1\)/2\. Then

rad​\(B\+\)≤⌈δ2⌉\.\\mathrm\{rad\}\(B^\{\+\}\)\\leq\\left\\lceil\\frac\{\\delta\}\{2\}\\right\\rceil\.

###### Proof\.

We prove that every rankr∈Rjrankr\\in R\_\{j\}^\{\\mathrm\{rank\}\}is within distance at most⌈δ/2⌉\\lceil\\delta/2\\rceilof some rank inB\+B^\{\+\}\.

Interior intervals\.Letb<b′b<b^\{\\prime\}be adjacent ranks inBB, and consider the integer interval\[b,b′\]\[b,b^\{\\prime\}\]\. SinceBBhas covering radius at mostδ\\delta, every integer rank in\[b,b′\]\[b,b^\{\\prime\}\]is within distanceδ\\deltaof eitherbborb′b^\{\\prime\}\. Therefore

⌊b′−b2⌋≤δ\.\\left\\lfloor\\frac\{b^\{\\prime\}\-b\}\{2\}\\right\\rfloor\\leq\\delta\.Let

μ=round⁡\(b\+b′2\),\\mu=\\operatorname\{round\}\\\!\\left\(\\frac\{b\+b^\{\\prime\}\}\{2\}\\right\),whereround\\operatorname\{round\}returns the nearest integer \(breaking ties arbitrarily\)\. The largest gap between consecutive ranks in\{b,μ,b′\}\\\{b,\\mu,b^\{\\prime\}\\\}is at most

⌈b′−b2⌉\.\\left\\lceil\\frac\{b^\{\\prime\}\-b\}\{2\}\\right\\rceil\.Hence every integer rank in\[b,b′\]\[b,b^\{\\prime\}\]is within distance at most

⌊12​⌈b′−b2⌉⌋\\left\\lfloor\\frac\{1\}\{2\}\\left\\lceil\\frac\{b^\{\\prime\}\-b\}\{2\}\\right\\rceil\\right\\rfloorof one ofb,μ,b′b,\\mu,b^\{\\prime\}\. Since

⌊b′−b2⌋≤δ,\\left\\lfloor\\frac\{b^\{\\prime\}\-b\}\{2\}\\right\\rfloor\\leq\\delta,the overall term is at most⌈δ/2⌉\\lceil\\delta/2\\rceil\. Thus, every rank in the interior interval\[b,b′\]\[b,b^\{\\prime\}\]is covered byB\+B^\{\+\}with radius at most⌈δ/2⌉\\lceil\\delta/2\\rceil\.

Boundary intervals\.For the left boundary, the assumed covering guarantee implies

bmin−1≤δ,b\_\{\\min\}\-1\\leq\\delta,sincebminb\_\{\\min\}is the closest selected rank inBBto the leftmost rank11\. Let

μL=round⁡\(1\+bmin2\)\\mu\_\{L\}=\\operatorname\{round\}\\\!\\left\(\\frac\{1\+b\_\{\\min\}\}\{2\}\\right\)be the integer rank added in the left boundary interval\. Then every rank in\[1,bmin\]\[1,b\_\{\\min\}\]is within distance at most

⌈bmin−12⌉≤⌈δ2⌉\\left\\lceil\\frac\{b\_\{\\min\}\-1\}\{2\}\\right\\rceil\\leq\\left\\lceil\\frac\{\\delta\}\{2\}\\right\\rceilof eitherμL\\mu\_\{L\}orbminb\_\{\\min\}\.

The right boundary is identical\. Finally, every rank inRjrankR\_\{j\}^\{\\mathrm\{rank\}\}lies either on a boundary or between two adjacent ranks\. Each such interval is covered byB\+B^\{\+\}with radius at most⌈δ/2⌉\\lceil\\delta/2\\rceil\. Therefore

rad​\(B\+\)≤⌈δ2⌉\.\\mathrm\{rad\}\(B^\{\+\}\)\\leq\\left\\lceil\\frac\{\\delta\}\{2\}\\right\\rceil\.∎

###### Theorem 10\(Fixed\-Binarization Superset Guarantee\)\.

Using a proxy restricted to a fixed binarization, if the proxy is optimal over that binarization, then our continuous\-threshold algorithm recovers a superset of the trees returned by exact Rashomon set enumeration over that binarization\.

###### Proof\.

Because the proxy is optimal over some binarization, it satisfies the robustness conditions we assume in our pruning\. Seebrița2025optimalfor details of this fact\. Therefore, we will never prune a split that could actually be completed by the proxy to be within budget\. This means that we consider optimal completions over the binarization on every split in the binarization\. That is, we fully enumerate the Rashomon set over binary features\. We also evaluate binarized optimal completions on other thresholds\. These thresholds imply we could return more trees than we would by finding a Rashomon set over the binarization\. ∎

There are many interesting theoretical guarantees inHeileet al\.\([2026](https://arxiv.org/html/2608.04310#bib.bib156)\), including Theorem 3\.5, Corollary 3\.6, Theorem A\.3, and Corollary A\.6\. These all extend to continuous features whenever the proxy does not violate the continuous\-feature pruning conditions\. This holds, for example, for a majority\-leaf proxy or an optimal proxy restricted to any subset of split options\. In particular, we would like to highlight that if the proxy’s optimality gap is maximized at the root, we recovers the full Rashomon set without additional slack\. In the worst case, the proxy may be optimal at the root and attain its full gap only on a descendant subproblem; multiplying the root budget byccstill guarantees full recovery \(whereccis the worst\-case optimality gap\)\. Although we are not aware of formal approximation algorithms for decision tree optimization when considering the same split choices, our preceding continuous\-feature results bound the gap between optimal trees with and without discretization\. Thus, an optimal proxy over a carefully chosen subset of thresholds yields both computational savings and an explicit recovery guarantee\. In practice, we do find using a near\-optimal proxy over an extended feature set is even better than this option\.

## Appendix CProxy Algorithms

### C\.1LicketySNIP and Proxy Strength

In this section, we provide pseudocode for the LicketySNIP proxy algorithm \(Algorithm[27](https://arxiv.org/html/2608.04310#alg27)\)\. The parameterℓ\\ellcontrols the proxy strength\. Whenℓ=0\\ell=0, LicketySNIP reduces to a fast greedy completion\. Whenℓ=1\\ell=1, it roughly chooses the best split using greedy completions, fixes that split, and then recurses on the two child subproblems\. In other words, it recursively chooses splits whose quality is estimated by greedy completions\. Thisℓ=1\\ell=1setting is the default algorithm we refer to as LicketySNIP\. Whenℓ=2\\ell=2, the algorithm instead chooses the best split using LicketySNIP\(ℓ=1\\ell=1\) completions, and so on\.

The reason we say “roughly” is that we apply the same neighborhood\-pruning idea when evaluating these cheap split completions\. Thus, if one threshold has a poor proxy completion, we choose to prune nearby thresholds, assuming the greedy completions are robust\.

This process creates a hierarchy of proxy algorithms; more details and provable cache reuse are given inHeileet al\.\([2026](https://arxiv.org/html/2608.04310#bib.bib156)\)\. For example, if we first use greedy completions as our proxy and then upgrade to LicketySNIP\(ℓ=1\\ell=1\), the greedy\-completion caches can be reused when solving theℓ=1\\ell=1subproblems\. The same reuse continues as we increaseℓ\\ell, until the proxy eventually becomes exact\. This lookahead parameterℓ\\ellis exactly what we mean by proxy strength in the anytime algorithm\. As a result, LicketySNIP is naturally amenable to staged refinement: we can begin with cheap proxy evaluations, cache their results, and then increaseℓ\\ellto obtain stronger certificates while reusing the work already performed\.

Unlike the threshold\-to\-proxy completion maps used by the Rashomon set algorithm, the mapEEinBestContinuousSplitSNIPis local to a single continuous\-feature search and is not cached across calls\. PersistingEEis valuable for Rashomon set enumeration because the same subproblem–depth pair may be revisited many times as the anytime algorithm activates additional thresholds or as iterative budget refinement increases the budget given to it\. In the proxy optimization, by contrast, once a subproblem and depth have been solved, they need not be revisited\. This is why we do not persistEE\. However, maintaining a temporaryEEduring the current queue search remains useful because the proxy incumbentB⋆B^\{\\star\}can improve as better thresholds are found\. A threshold evaluated earlier may therefore become a stronger pruning certificate later: asB⋆B^\{\\star\}decreases, the gapPL​\(t\)\+PR​\(t\)−B⋆P\_\{L\}\(t\)\+P\_\{R\}\(t\)\-B^\{\\star\}increases, allowing a larger neighborhood aroundttto be pruned without recomputing its proxy completions\. Accordingly, whenever an interval is popped fromQQ,ShrinkFromEvaluatedreapplies the evaluations accumulated in the local mapEEusing the current incumbent, after whichEEis discarded when the feature search terminates\.

Algorithm 27LicketySNIP\(D,d,ℓ,γ,𝒮\)\(D,d,\\ell,\\gamma,\\mathcal\{S\}\)0:Subproblem

DD, remaining depth

dd, lookahead

ℓ\\ell, per\-leaf penalty

γ\\gamma, and threshold registry

𝒮\\mathcal\{S\}
1:if

d=0d=0then

2:return

LeafObj​\(D,γ\)\\textsc\{LeafObj\}\(D,\\gamma\)
3:endif

4:if

ℓ=0\\ell=0then

5:return

GreedyContinuous​\(D,d,γ,𝒮\)\\textsc\{GreedyContinuous\}\(D,d,\\gamma,\\mathcal\{S\}\)
6:endif

7:if

d=1d=1then

8:return

ExactStumpContinuous​\(D,γ,𝒮\)\\textsc\{ExactStumpContinuous\}\(D,\\gamma,\\mathcal\{S\}\)
9:endif

10:

ℓ←min⁡\{ℓ,d−1\}\\ell\\leftarrow\\min\\\{\\ell,d\-1\\\}
11:if

\(D,d,ℓ\)\(D,d,\\ell\)is in the LicketySNIP cachethen

12:returncached value

13:endif

14:

Lleaf←LeafObj​\(D,γ\)L\_\{\\mathrm\{leaf\}\}\\leftarrow\\textsc\{LeafObj\}\(D,\\gamma\)
15:if

Lleaf≤2​γL\_\{\\mathrm\{leaf\}\}\\leq 2\\gammathen

16:Cache andreturn

LleafL\_\{\\mathrm\{leaf\}\}
17:endif

18:

B←LleafB\\leftarrow L\_\{\\mathrm\{leaf\}\}\{Current best proxy objective\}

19:

s⋆←⊥s^\{\\star\}\\leftarrow\\bot\{Best split found so far\}

20:foreach ordinary binary feature

jjdo

21:

\(DL,DR\)←Partition​\(D,j\)\(D\_\{L\},D\_\{R\}\)\\leftarrow\\textsc\{Partition\}\(D,j\)
22:if

DL=∅D\_\{L\}=\\emptysetor

DR=∅D\_\{R\}=\\emptysetthen

23:continue

24:endif

25:

PL←LicketySNIP​\(DL,d−1,ℓ−1,γ,𝒮\)P\_\{L\}\\leftarrow\\textsc\{LicketySNIP\}\(D\_\{L\},d\-1,\\ell\-1,\\gamma,\\mathcal\{S\}\)
26:

PR←LicketySNIP​\(DR,d−1,ℓ−1,γ,𝒮\)P\_\{R\}\\leftarrow\\textsc\{LicketySNIP\}\(D\_\{R\},d\-1,\\ell\-1,\\gamma,\\mathcal\{S\}\)
27:if

PL\+PR<BP\_\{L\}\+P\_\{R\}<Bthen

28:

B←PL\+PRB\\leftarrow P\_\{L\}\+P\_\{R\}
29:

s⋆←js^\{\\star\}\\leftarrow j
30:endif

31:endfor

32:foreach continuous feature group

J=\[a,b\)J=\[a,b\)do

33:

\[a′,b′\)←RestrictRange​\(𝒮,D,J\)\[a^\{\\prime\},b^\{\\prime\}\)\\leftarrow\\textsc\{RestrictRange\}\(\\mathcal\{S\},D,J\)
34:if

a′≥b′a^\{\\prime\}\\geq b^\{\\prime\}then

35:continue

36:endif

37:

\(BJ,sJ\)←BestContinuousSplitSNIP​\(D,d,ℓ−1,γ,𝒮,\[a′,b′\),B\)\(B\_\{J\},s\_\{J\}\)\\leftarrow\\textsc\{BestContinuousSplitSNIP\}\(D,d,\\ell\-1,\\gamma,\\mathcal\{S\},\[a^\{\\prime\},b^\{\\prime\}\),B\)
38:if

BJ<BB\_\{J\}<Bthen

39:

B←BJB\\leftarrow B\_\{J\}
40:

s⋆←sJs^\{\\star\}\\leftarrow s\_\{J\}
41:endif

42:endfor

43:

A←LleafA\\leftarrow L\_\{\\mathrm\{leaf\}\}
44:if

s⋆≠⊥s^\{\\star\}\\neq\\botthen

45:

\(DL,DR\)←Partition​\(D,s⋆\)\(D\_\{L\},D\_\{R\}\)\\leftarrow\\textsc\{Partition\}\(D,s^\{\\star\}\)
46:

𝒮L←𝒮\\mathcal\{S\}\_\{L\}\\leftarrow\\mathcal\{S\};

𝒮R←𝒮\\mathcal\{S\}\_\{R\}\\leftarrow\\mathcal\{S\}
47:if

s⋆s^\{\\star\}is a threshold of continuous feature

ccthen

48:

LowerUpperBound​\(𝒮L,c,s⋆−1\)\\textsc\{LowerUpperBound\}\(\\mathcal\{S\}\_\{L\},c,s^\{\\star\}\-1\)
49:

RaiseLowerBound​\(𝒮R,c,s⋆\+1\)\\textsc\{RaiseLowerBound\}\(\\mathcal\{S\}\_\{R\},c,s^\{\\star\}\+1\)
50:endif

51:

QL←LicketySNIP​\(DL,d−1,ℓ,γ,𝒮L\)Q\_\{L\}\\leftarrow\\textsc\{LicketySNIP\}\(D\_\{L\},d\-1,\\ell,\\gamma,\\mathcal\{S\}\_\{L\}\)
52:

QR←LicketySNIP​\(DR,d−1,ℓ,γ,𝒮R\)Q\_\{R\}\\leftarrow\\textsc\{LicketySNIP\}\(D\_\{R\},d\-1,\\ell,\\gamma,\\mathcal\{S\}\_\{R\}\)
53:

A←min⁡\{A,QL\+QR,B\}A\\leftarrow\\min\\\{A,Q\_\{L\}\+Q\_\{R\},B\\\}
54:endif

55:Cache

AAfor

\(D,d,ℓ\)\(D,d,\\ell\)
56:return

AA

Algorithm 28BestContinuousSplitSNIP\(D,d,ℓ,γ,𝒮,\[a,b\),B\)\(D,d,\\ell,\\gamma,\\mathcal\{S\},\[a,b\),B\)0:Subproblem

DD, remaining depth

dd, child lookahead

ℓ\\ell, penalty

γ\\gamma, threshold registry

𝒮\\mathcal\{S\}, threshold interval

\[a,b\)\[a,b\), and incumbent objective

BB
1:

B⋆←BB^\{\\star\}\\leftarrow B;

t⋆←⊥t^\{\\star\}\\leftarrow\\bot
2:

E←∅E\\leftarrow\\emptyset\{

E​\[t\]=\(PL​\(t\),PR​\(t\)\)E\[t\]=\(P\_\{L\}\(t\),P\_\{R\}\(t\)\)stores evaluated proxy completions\}

3:

Q←\{\[a,b−1\]\}Q\\leftarrow\\\{\[a,b\-1\]\\\}
4:

L←aL\\leftarrow a;

U←b−1U\\leftarrow b\-1
5:while

Q≠∅Q\\neq\\emptysetdo

6:Remove an interval

\[i,j\]\[i,j\]from

QQ
7:

\(i,j\)←ShrinkFromEvaluated​\(E,D,i,j,L,U,B⋆\)\(i,j\)\\leftarrow\\textsc\{ShrinkFromEvaluated\}\(E,D,i,j,L,U,B^\{\\star\}\)
8:

i←max⁡\{i,L\}i\\leftarrow\\max\\\{i,L\\\};

j←min⁡\{j,U\}j\\leftarrow\\min\\\{j,U\\\}
9:if

i\>ji\>jthen

10:continue

11:endif

12:

m←⌊\(i\+j\)/2⌋m\\leftarrow\\lfloor\(i\+j\)/2\\rfloor
13:

\(DL,DR\)←Partition​\(D,m\)\(D\_\{L\},D\_\{R\}\)\\leftarrow\\textsc\{Partition\}\(D,m\)
14:if

DL=∅D\_\{L\}=\\emptysetthen

15:

L←max⁡\{L,m\+1\}L\\leftarrow\\max\\\{L,m\+1\\\}
16:Add

\[m\+1,j\]\[m\+1,j\]to

QQ
17:continue

18:endif

19:if

DR=∅D\_\{R\}=\\emptysetthen

20:

U←min⁡\{U,m−1\}U\\leftarrow\\min\\\{U,m\-1\\\}
21:Add

\[i,m−1\]\[i,m\-1\]to

QQ
22:continue

23:endif

24:

𝒮L←𝒮\\mathcal\{S\}\_\{L\}\\leftarrow\\mathcal\{S\};

𝒮R←𝒮\\mathcal\{S\}\_\{R\}\\leftarrow\\mathcal\{S\}
25:

LowerUpperBound​\(𝒮L,c,m−1\)\\textsc\{LowerUpperBound\}\(\\mathcal\{S\}\_\{L\},c,m\-1\)
26:

RaiseLowerBound​\(𝒮R,c,m\+1\)\\textsc\{RaiseLowerBound\}\(\\mathcal\{S\}\_\{R\},c,m\+1\)
27:

PL←LicketySNIP​\(DL,d−1,ℓ,γ,𝒮L\)P\_\{L\}\\leftarrow\\textsc\{LicketySNIP\}\(D\_\{L\},d\-1,\\ell,\\gamma,\\mathcal\{S\}\_\{L\}\)
28:

PR←LicketySNIP​\(DR,d−1,ℓ,γ,𝒮R\)P\_\{R\}\\leftarrow\\textsc\{LicketySNIP\}\(D\_\{R\},d\-1,\\ell,\\gamma,\\mathcal\{S\}\_\{R\}\)
29:

E​\[m\]←\(PL,PR\)E\[m\]\\leftarrow\(P\_\{L\},P\_\{R\}\)
30:

P←PL\+PRP\\leftarrow P\_\{L\}\+P\_\{R\}
31:if

P<B⋆P<B^\{\\star\}then

32:

B⋆←PB^\{\\star\}\\leftarrow P
33:

t⋆←mt^\{\\star\}\\leftarrow m
34:endif

35:if

PL=γP\_\{L\}=\\gammathen

36:

L←max⁡\{L,m\+1\}L\\leftarrow\\max\\\{L,m\+1\\\}\{Farther\-left thresholds cannot improve the left child\}

37:endif

38:if

PR=γP\_\{R\}=\\gammathen

39:

U←min⁡\{U,m−1\}U\\leftarrow\\min\\\{U,m\-1\\\}\{Farther\-right thresholds cannot improve the right child\}

40:endif

41:if

P≥B⋆P\\geq B^\{\\star\}then

42:

Δ←max⁡\{1,P−B⋆\}\\Delta\\leftarrow\\max\\\{1,P\-B^\{\\star\}\\\}
43:

u←TightenUpper​\(D,m,i,m−1,Δ\)u\\leftarrow\\textsc\{TightenUpper\}\(D,m,i,m\-1,\\Delta\)
44:

v←TightenLower​\(D,m,m\+1,j,Δ\)v\\leftarrow\\textsc\{TightenLower\}\(D,m,m\+1,j,\\Delta\)
45:if

i≤ui\\leq uthen

46:Add

\[i,u\]\[i,u\]to

QQ
47:endif

48:if

v≤jv\\leq jthen

49:Add

\[v,j\]\[v,j\]to

QQ
50:endif

51:else

52:Add

\[i,m−1\]\[i,m\-1\]and

\[m\+1,j\]\[m\+1,j\]to

QQ
53:endif

54:endwhile

55:return

\(B⋆,t⋆\)\(B^\{\\star\},t^\{\\star\}\)

Lines 4\-8 of Algorithm[29](https://arxiv.org/html/2608.04310#alg29)uses a pruning technique that has not been previously used in this work\. Given a subtree that handles splits on the left, a subtree that handles splits on the right, and haven’t handled the middle, and this is already over the incumbent solution, you can prune the entirity of the middle\. While we do have both left and right proxy completions if we have one of them, this is particularly effective because we can avoid needing to compute active sample distances\. Thus, even if this does not help most of the time, it is a cheap check that can be very rewarding\. We do not apply this pruning in our Rashomon set enumeration because that algorithm already processes every entry in its completion mapEEunder a fixed objective bound\. Best\-split selection requires a different design: its incumbent can improve throughout the search, so previously evaluated completions must be reconsidered adaptively as intervals are popped from the queue\. Thus, the fixed\-bound structure of Rashomon enumeration supports largely upfront pruning, whereas proxy split selection require something adaptive\. Needing to be adaptive motivates the inclusion of this lightweight check\.

Algorithm 29ShrinkFromEvaluated\(E,D,i,j,L,U,B⋆\)\(E,D,i,j,L,U,B^\{\\star\}\)0:Local map

EEfrom evaluated threshold indices to proxy completions, subproblem

DD, popped interval

\[i,j\]\[i,j\], current global bounds

\[L,U\]\[L,U\], and incumbent proxy objective

B⋆B^\{\\star\}
1:

u←PredecessorKey​\(E,i\)u\\leftarrow\\textsc\{PredecessorKey\}\(E,i\)\{Largest evaluated threshold strictly below

ii, or

⊥\\bot\}

2:

v←SuccessorKey​\(E,j\)v\\leftarrow\\textsc\{SuccessorKey\}\(E,j\)\{Smallest evaluated threshold strictly above

jj, or

⊥\\bot\}

3:\{This is a pruning technique frombrița2025optimal\.\}

4:if

u≠⊥u\\neq\\botand

v≠⊥v\\neq\\botthen

5:

\(PL​\(u\),PR​\(u\)\)←E​\(u\)\(P\_\{L\}\(u\),P\_\{R\}\(u\)\)\\leftarrow E\(u\)
6:

\(PL​\(v\),PR​\(v\)\)←E​\(v\)\(P\_\{L\}\(v\),P\_\{R\}\(v\)\)\\leftarrow E\(v\)
7:if

PL​\(u\)\+PR​\(v\)≥B⋆P\_\{L\}\(u\)\+P\_\{R\}\(v\)\\geq B^\{\\star\}then

8:return

\(1,0\)\(1,0\)\{No threshold in

\[i,j\]\[i,j\]can strictly improve the incumbent\}

9:endif

10:endif

11:if

u≠⊥u\\neq\\botthen

12:

\(PL​\(u\),PR​\(u\)\)←E​\(u\)\(P\_\{L\}\(u\),P\_\{R\}\(u\)\)\\leftarrow E\(u\)
13:

P​\(u\)←PL​\(u\)\+PR​\(u\)P\(u\)\\leftarrow P\_\{L\}\(u\)\+P\_\{R\}\(u\)
14:if

P​\(u\)≥B⋆P\(u\)\\geq B^\{\\star\}then

15:

Δ←max⁡\{1,P​\(u\)−B⋆\}\\Delta\\leftarrow\\max\\\{1,P\(u\)\-B^\{\\star\}\\\}
16:

i←max⁡\{i,RightBoundary​\(D,u,i,U,Δ\)\}i\\leftarrow\\max\\\!\\left\\\{i,\\textsc\{RightBoundary\}\(D,u,i,U,\\Delta\)\\right\\\}\{Move right until strict improvement is possible\}

17:endif

18:endif

19:if

v≠⊥v\\neq\\botthen

20:

\(PL​\(v\),PR​\(v\)\)←E​\(v\)\(P\_\{L\}\(v\),P\_\{R\}\(v\)\)\\leftarrow E\(v\)
21:

P​\(v\)←PL​\(v\)\+PR​\(v\)P\(v\)\\leftarrow P\_\{L\}\(v\)\+P\_\{R\}\(v\)
22:if

P​\(v\)≥B⋆P\(v\)\\geq B^\{\\star\}then

23:

Δ←max⁡\{1,P​\(v\)−B⋆\}\\Delta\\leftarrow\\max\\\{1,P\(v\)\-B^\{\\star\}\\\}
24:

j←min⁡\{j,LeftBoundary​\(D,v,j,L,Δ\)\}j\\leftarrow\\min\\\!\\left\\\{j,\\textsc\{LeftBoundary\}\(D,v,j,L,\\Delta\)\\right\\\}\{Move left until strict improvement is possible\}

25:endif

26:endif

27:

i←max⁡\{i,L\}i\\leftarrow\\max\\\{i,L\\\};

j←min⁡\{j,U\}j\\leftarrow\\min\\\{j,U\\\}
28:return

\(i,j\)\(i,j\)

For the greedy subroutine, there are two natural ways to handle continuous features\. One option is to avoid bitvectors and instead create sorted lists of sample indices for each feature, maintaining these lists across recursive calls\. With this representation, we can scan each feature in sorted order, updating the class counts on the left and right sides incrementally to efficiently identify the best split\.

The empirical question is whether the cost of constructing and maintaining these sorted index lists is justified relative to running the greedy solver directly over binarized threshold features\. Because our main algorithm does not maintain sorted index lists throughout the search, this representation must be constructed specifically for each greedy proxy call\. This setup cost can outweigh the savings, particularly when the proxy is invoked on small subproblems deep in the search space\. Empirically, the sorted\-index representation is not beneficial on small\- to medium\-sized problems and can incur a \(2–3×2\\text\{\-\-\}3\\times\) overhead\. On larger problems, however, it can provide substantial speedups\.

This comparison should not be interpreted as evidence that binarized threshold representations are generally slower in our implementation\. In the greedy split\-selection loop, we do not use bounds to skip groups of similar thresholds, whereas the main algorithm applies additional pruning that can eliminate large collections of thresholds at once\. The greedy solver is also particularly well suited to sorted index lists: evaluating a candidate split requires only the feature values and the corresponding class counts; the latter can be updated efficiently when traversing left to right\. More general decision\-tree optimization routines must preserve joint information about samples across features and subproblems\.

Appendix[E\.2](https://arxiv.org/html/2608.04310#A5.SS2)compares the sorted\-index implementation with a greedy subroutine operating over binarized threshold features\. The latter is unchanged fromHeileet al\.\([2026](https://arxiv.org/html/2608.04310#bib.bib156)\), except that it skips consecutive thresholds that induce the same partition of the current subproblem\.

In the main\-paper experiments, we use fast bitvector operations for the greedy subroutine, either over all thresholds or over a restricted binarization\. While it is true that a better default for large\-scale problems is to create sorted\-lists of indices, we find that an even better default is to consider a smaller binarization with fast bitvector operations\.

When a greedy proxy subroutine is called, and if we do not want to scan the pre\-binarized threshold columns with bitvectors, we instead obtain a sorted list of active sample indices for each continuous feature\. This can be done in two ways\. First, we may sort the samples once at the root for each continuous feature and, at a later subproblem, filter this global ordering to the samples active in the current subproblem\. Second, we may collect the active samples in the current subproblem and sort them locally by the feature value\. Our implementation uses the former approach\. Given a subproblemDDand a continuous featurejj, let

i1,…,imi\_\{1\},\\ldots,i\_\{m\}be the active samples inDD, sorted so that

xi1​j≤xi2​j≤⋯≤xim​j\.x\_\{i\_\{1\}j\}\\leq x\_\{i\_\{2\}j\}\\leq\\cdots\\leq x\_\{i\_\{m\}j\}\.
We evaluate all candidate thresholds for featurejjin one left\-to\-right sweep\(Quinlan[2014](https://arxiv.org/html/2608.04310#bib.bib18)\)\. Initially, all samples lie on the right\. Letn=\|D\|n=\|D\|andppbe the number of positive samples inDD\. We maintain left\-side countsnLn\_\{L\}andpLp\_\{L\}, initialized to zero\. At each distinct valuevv, we move the entire tie blockBv=\{i∈D:xi​j=v\}B\_\{v\}=\\\{i\\in D:x\_\{ij\}=v\\\}from right to left and update

nL←nL\+\|Bv\|,pL←pL\+∑i∈Bv𝟏​\{yi=1\}\.n\_\{L\}\\leftarrow n\_\{L\}\+\|B\_\{v\}\|,\\qquad p\_\{L\}\\leftarrow p\_\{L\}\+\\sum\_\{i\\in B\_\{v\}\}\\mathbf\{1\}\\\{y\_\{i\}=1\\\}\.The right\-side counts follow by subtraction:

nR=n−nL,pR=p−pL\.n\_\{R\}=n\-n\_\{L\},\\qquad p\_\{R\}=p\-p\_\{L\}\.We then score the threshold aftervvfrom these counts\. For information gain,

Score​\(v\)=H​\(p/n\)−nLn​H​\(pL/nL\)−nRn​H​\(pR/nR\),\\mathrm\{Score\}\(v\)=H\(p/n\)\-\\frac\{n\_\{L\}\}\{n\}H\(p\_\{L\}/n\_\{L\}\)\-\\frac\{n\_\{R\}\}\{n\}H\(p\_\{R\}/n\_\{R\}\),whereH​\(q\)=−q​log⁡q−\(1−q\)​log⁡\(1−q\)H\(q\)=\-q\\log q\-\(1\-q\)\\log\(1\-q\)\. At depth11, we instead use the negative sum of the two child leaf objectives\. After selecting the best threshold, we partition the sorted sample indices into the two child subproblems and recurse\.

### C\.2Improvements without Proxy Caching

Algorithm 30WalkFromSolvedThreshold\(G,D,d,γ,εabs,𝒮,c,q,PL,PR\)\(G,D,d,\\gamma,\\varepsilon\_\{\\mathrm\{abs\}\},\\mathcal\{S\},c,q,P\_\{L\},P\_\{R\}\)0:Current OR node

GG, subproblem

DD, depth

dd, budget

εabs\\varepsilon\_\{\\mathrm\{abs\}\}, threshold registry

𝒮\\mathcal\{S\}, continuous feature

cc, active position

qq, and proxy completions

\(PL,PR\)\(P\_\{L\},P\_\{R\}\)for the threshold

1:

𝒜←ActiveThresholds​\(𝒮,D,c\)\\mathcal\{A\}\\leftarrow\\textsc\{ActiveThresholds\}\(\\mathcal\{S\},D,c\)
2:

t←𝒜​\[q\]t\\leftarrow\\mathcal\{A\}\[q\]
3:

\(GL,GR\)←AddOrExtendSplit\(G,D,t,d,γ,εabs,𝒮,PL,PR\)\(G\_\{L\},G\_\{R\}\)\\leftarrow\\begin\{aligned\} \\textsc\{AddOrExtendSplit\}\(&G,D,t,d,\\gamma,\\varepsilon\_\{\\mathrm\{abs\}\},\\\\ &\\mathcal\{S\},P\_\{L\},P\_\{R\}\)\\end\{aligned\}
4:if

GL=∅G\_\{L\}=\\emptysetor

GR=∅G\_\{R\}=\\emptysetthen

5:return

6:endif

7:

L←MinObjective​\(GL\)L\\leftarrow\\textsc\{MinObjective\}\(G\_\{L\}\)
8:

U←MinObjective​\(GR\)U\\leftarrow\\textsc\{MinObjective\}\(G\_\{R\}\)
9:

Δ←εabs−\(L\+U\)\\Delta\\leftarrow\\varepsilon\_\{\\mathrm\{abs\}\}\-\(L\+U\)
10:if

Δ<0\\Delta<0then

11:return

12:endif

13:

WalkDirection\(G,D,d,γ,εabs,𝒮,c,q,t,L,U,Left\)\\begin\{aligned\} \\textsc\{WalkDirection\}\(&G,D,d,\\gamma,\\varepsilon\_\{\\mathrm\{abs\}\},\\mathcal\{S\},c,\\\\ &q,t,L,U,\\textsc\{Left\}\)\\end\{aligned\}
14:

WalkDirection\(G,D,d,γ,εabs,𝒮,c,q,t,L,U,Right\)\\begin\{aligned\} \\textsc\{WalkDirection\}\(&G,D,d,\\gamma,\\varepsilon\_\{\\mathrm\{abs\}\},\\mathcal\{S\},c,\\\\ &q,t,L,U,\\textsc\{Right\}\)\\end\{aligned\}

Algorithm[30](https://arxiv.org/html/2608.04310#alg30)gives an optional subroutine forEnumContFeaturethat uses solved thresholds to seed nearby ones\. When a threshold is within budget, the minimum objectives of its left and right child subgraphs give upper bounds on the optimal child solutions for neighboring thresholds\. If these induced bounds are within budget, we skip the proxy\-pruning test for the neighboring threshold and callAddOrExtendSplitdirectly\. This procedure can be chained across consecutive thresholds, using each newly solved threshold to seed the next, while provably returning a superset of the trees that would otherwise be returned \(Theorem[30](https://arxiv.org/html/2608.04310#alg30)\)\. In practice, this is unnecessary when we can cache every intermediate solution computed during each proxy query, but it can be very beneficial in memory\-constrained settings\.

Algorithm 31WalkDirection\(G,D,d,γ,εabs,𝒮,c,q,t,L,U,dir\)\(G,D,d,\\gamma,\\varepsilon\_\{\\mathrm\{abs\}\},\\mathcal\{S\},c,q,t,L,U,\\mathrm\{dir\}\)0:Current OR node

GG, subproblem

DD, depth

dd, budget

εabs\\varepsilon\_\{\\mathrm\{abs\}\}, threshold registry

𝒮\\mathcal\{S\}, continuous feature

cc, solved position

qq, solved threshold

tt, child minima

L,UL,U, and direction

dir\\mathrm\{dir\}
1:

𝒜←ActiveThresholds​\(𝒮,D,c\)\\mathcal\{A\}\\leftarrow\\textsc\{ActiveThresholds\}\(\\mathcal\{S\},D,c\)
2:

tanchor←tt\_\{\\mathrm\{anchor\}\}\\leftarrow t
3:

Lanchor←LL^\{\\mathrm\{anchor\}\}\\leftarrow L
4:

Uanchor←UU^\{\\mathrm\{anchor\}\}\\leftarrow U
5:

Δ←εabs−\(Lanchor\+Uanchor\)\\Delta\\leftarrow\\varepsilon\_\{\\mathrm\{abs\}\}\-\(L^\{\\mathrm\{anchor\}\}\+U^\{\\mathrm\{anchor\}\}\)
6:if

dir=Left\\mathrm\{dir\}=\\textsc\{Left\}then

7:

ℛ←\(q−1,q−2,…,0\)\\mathcal\{R\}\\leftarrow\(q\-1,q\-2,\\ldots,0\)
8:else

9:

ℛ←\(q\+1,q\+2,…,\|𝒜\|−1\)\\mathcal\{R\}\\leftarrow\(q\+1,q\+2,\\ldots,\|\\mathcal\{A\}\|\-1\)
10:endif

11:foreach

r∈ℛr\\in\\mathcal\{R\}do

12:

s←𝒜​\[r\]s\\leftarrow\\mathcal\{A\}\[r\]
13:if

dir=Left\\mathrm\{dir\}=\\textsc\{Left\}then

14:

x←distD​\(s,tanchor\)x\\leftarrow\\mathrm\{dist\}\_\{D\}\(s,t\_\{\\mathrm\{anchor\}\}\)
15:else

16:

x←distD​\(tanchor,s\)x\\leftarrow\\mathrm\{dist\}\_\{D\}\(t\_\{\\mathrm\{anchor\}\},s\)
17:endif\{Number of active samples whose side changes\}

18:if

x\>Δx\>\\Deltathen

19:break

20:endif

21:

\(DL,DR\)←Partition​\(D,s\)\(D\_\{L\},D\_\{R\}\)\\leftarrow\\textsc\{Partition\}\(D,s\)
22:if

DL=∅D\_\{L\}=\\emptysetthen

23:

RaiseLowerBound​\(𝒮,c,s\+1\)\\textsc\{RaiseLowerBound\}\(\\mathcal\{S\},c,s\+1\)
24:break

25:endif

26:if

DR=∅D\_\{R\}=\\emptysetthen

27:

LowerUpperBound​\(𝒮,c,s−1\)\\textsc\{LowerUpperBound\}\(\\mathcal\{S\},c,s\-1\)
28:break

29:endif

30:if

dir=Left\\mathrm\{dir\}=\\textsc\{Left\}then

31:

P^L←Lanchor\\widehat\{P\}\_\{L\}\\leftarrow L^\{\\mathrm\{anchor\}\}
32:

P^R←Uanchor\+x\\widehat\{P\}\_\{R\}\\leftarrow U^\{\\mathrm\{anchor\}\}\+x\{Right child gained at most

xxsamples\}

33:else

34:

P^L←Lanchor\+x\\widehat\{P\}\_\{L\}\\leftarrow L^\{\\mathrm\{anchor\}\}\+x
35:

P^R←Uanchor\\widehat\{P\}\_\{R\}\\leftarrow U^\{\\mathrm\{anchor\}\}\{Left child gained at most

xxsamples\}

36:endif

37:

\(GL,GR\)←AddOrExtendSplit\(G,D,s,d,γ,εabs,𝒮,P^L,P^R\)\(G\_\{L\},G\_\{R\}\)\\leftarrow\\begin\{aligned\} \\textsc\{AddOrExtendSplit\}\(&G,D,s,d,\\gamma,\\varepsilon\_\{\\mathrm\{abs\}\},\\\\ &\\mathcal\{S\},\\widehat\{P\}\_\{L\},\\widehat\{P\}\_\{R\}\)\\end\{aligned\}
38:if

GL=∅G\_\{L\}=\\emptysetor

GR=∅G\_\{R\}=\\emptysetthen

39:break

40:endif

41:

tanchor←st\_\{\\mathrm\{anchor\}\}\\leftarrow s
42:

Lanchor←MinObjective​\(GL\)L^\{\\mathrm\{anchor\}\}\\leftarrow\\textsc\{MinObjective\}\(G\_\{L\}\)
43:

Uanchor←MinObjective​\(GR\)U^\{\\mathrm\{anchor\}\}\\leftarrow\\textsc\{MinObjective\}\(G\_\{R\}\)
44:

Δ←εabs−\(Lanchor\+Uanchor\)\\Delta\\leftarrow\\varepsilon\_\{\\mathrm\{abs\}\}\-\(L^\{\\mathrm\{anchor\}\}\+U^\{\\mathrm\{anchor\}\}\)
45:endfor

To be precise, we assume that whenever a subproblem is solved with budget at least its proxy objective, the resulting subgraph has minimum objective no worse than the proxy objective\. This is proven inHeileet al\.\([2026](https://arxiv.org/html/2608.04310#bib.bib156)\), though there are some subtleties introduced with our neighborhood pruning\. The condition holds immediately when the proxy is optimal, either over all continuous thresholds or over a fixed binarization\. It also holds for any proxy satisfying the robustness conditions that the pruning assumes, so that the proxy split is not falsely pruned by neighboring\-threshold bounds\. In the anytime algorithm, we also track the proxy’s selected split separately as a special threshold that is evaluated before similarity\-based pruning; this also ensures that the proxy tree is recovered at a subproblem\. When when not doing this, empirically, our near\-perfect recall results suggest that this condition is satisfied\.

The intuition is as follows: whenever the initial solves construct feasible solutions within the available budget, iterative budget refinement can propagate their minimum objectives and recover the same solutions that would have been obtained from the proxy\. Conversely, if a proxy solution cannot be recovered, then its objective already exceeds the available budget, so it could not have contributed any trees under the original procedure\.

###### Theorem 11\(Neighboring\-Threshold Pruning\-Test\)\.

Assume that whenever a subproblem is solved with budget at least its proxy objective, the resulting subgraph has minimum objective no worse than the proxy objective\. Then the neighboring\-threshold walk in Algorithm[30](https://arxiv.org/html/2608.04310#alg30)never sacrifices approximation quality relative to explicitly applying the proxy\-pruning test at each threshold\.

###### Proof\.

Consider a solved thresholdttwith child subgraphs of minimum objectivesL​\(t\)L\(t\)andU​\(t\)U\(t\), and suppose

L​\(t\)\+U​\(t\)≤εabs\.L\(t\)\+U\(t\)\\leq\\varepsilon\_\{\\mathrm\{abs\}\}\.Let

Δ=εabs−L​\(t\)−U​\(t\)\\Delta=\\varepsilon\_\{\\mathrm\{abs\}\}\-L\(t\)\-U\(t\)be the remaining slack\. Now move to a neighboring thresholdssin the same continuous feature group, and let

x=distD​\(t,s\)x=\\mathrm\{dist\}\_\{D\}\(t,s\)be the number of active samples whose branch assignment changes betweenttandss\.

Suppose first thatsslies to the right oftt\. Then the left child gains at mostxxsamples, while the right child loses samples\. Reusing the solved left subtree fromttcan increase its loss by at mostxx, and reusing the solved right subtree cannot increase its loss because it is evaluated on fewer samples\. Thus the split atsshas a certified completion with child objectives bounded by

L​\(t\)\+xandU​\(t\)\.L\(t\)\+x\\qquad\\text\{and\}\\qquad U\(t\)\.Ifx≤Δx\\leq\\Delta, then

L​\(t\)\+x\+U​\(t\)≤εabs,L\(t\)\+x\+U\(t\)\\leq\\varepsilon\_\{\\mathrm\{abs\}\},so these bounds are sufficient child budgets for callingAddOrExtendSplitatsswithout first recomputing the proxy\-pruning test\. The leftward case is symmetric\.

By assumption, whenever a child is given budget at least its proxy objective, the constructed subgraph has minimum objective no worse than that proxy objective\.

Now we ask whether the child budgets assigned byAddOrExtendSplitare at least the corresponding proxy objectives\. If they are, then the claim follows\. This may not be immediate: finding a child subgraph whose minimum objective is no worse than the proxy objective does not, by itself, say that we have recovered every tree that the proxy\-pruning test would have recovered\. The reason it is enough is thatAddOrExtendSplitperforms iterative budget refinement\. Once one child is solved to objective no worse than its proxy objective, the next refinement step subtracts this no\-larger objective instead of the original walk boundL​\(t\)\+xL\(t\)\+xorU​\(t\)U\(t\)\. Therefore the opposite child receives a budget at least as large as it would have received under the explicit proxy\-pruning test\. Thus the refinement process reaches the same budgets as the explicit proxy procedure, possibly one iteration later\. Since iterative budget refinement is run to convergence, this delay does not change the recovered set\.

Let

PL​\(s\)andPR​\(s\)P\_\{L\}\(s\)\\qquad\\text\{and\}\\qquad P\_\{R\}\(s\)denote the proxy objectives of the left and right child subproblems induced by thresholdss\. We only need to consider the case where the proxy completion atssis within budget, namely

PL​\(s\)\+PR​\(s\)≤εabs\.P\_\{L\}\(s\)\+P\_\{R\}\(s\)\\leq\\varepsilon\_\{\\mathrm\{abs\}\}\.If this inequality fails, then explicitly applying the proxy\-pruning test atsswould pruness, so the neighboring\-threshold walk cannot miss any threshold that the proxy\-pruning test would have retained\.

Thus suppose

PL​\(s\)\+PR​\(s\)≤εabs\.P\_\{L\}\(s\)\+P\_\{R\}\(s\)\\leq\\varepsilon\_\{\\mathrm\{abs\}\}\.
Furthermore, we are only interested in the case wherePL​\(S\)≤L​\(t\)\+xP\_\{L\}\(S\)\\leq L\(t\)\+xandPR​\(s\)≤U​\(t\)P\_\{R\}\(s\)\\leq U\(t\)\. If either one of these is not true, then our budgets are set for the chilren by subtracting a smaller number: thus the budgets are at least as large, and because we knowPL​\(s\)\+PR​\(s\)≤εabsP\_\{L\}\(s\)\+P\_\{R\}\(s\)\\leq\\varepsilon\_\{\\mathrm\{abs\}\}, we also knowPL​\(s\)≤εabs−PR​\(s\)P\_\{L\}\(s\)\\leq\\varepsilon\_\{\\mathrm\{abs\}\}\-P\_\{R\}\(s\)andPR​\(s\)≤εabs−PL​\(s\)P\_\{R\}\(s\)\\leq\\varepsilon\_\{\\mathrm\{abs\}\}\-P\_\{L\}\(s\)\. That is, we know that if the true proxy check passes that the children subproblems are set with budget at least the proxy, so setting budgets any bigger will also be at least the proxy\.

Therefore, we are left with handling the cases wherePL​\(S\)≤L​\(t\)\+xP\_\{L\}\(S\)\\leq L\(t\)\+xandPR​\(s\)≤U​\(t\)P\_\{R\}\(s\)\\leq U\(t\)\.

We knowL​\(t\)\+x≤εabs−U​\(t\)L\(t\)\+x\\leq\\varepsilon\_\{\\mathrm\{abs\}\}\-U\(t\)because these upper bounds pass the pruning test\. We assumed thatPL​\(S\)≤L​\(t\)\+xP\_\{L\}\(S\)\\leq L\(t\)\+x, so we have ensured it on this side\.

It remains to check the other side\. We knowU​\(t\)≤εabs−\(L​\(t\)\+x\)U\(t\)\\leq\\varepsilon\_\{\\mathrm\{abs\}\}\-\(L\(t\)\+x\)\. By analogous reasoning \(knowingPR​\(s\)≤U​\(t\)P\_\{R\}\(s\)\\leq U\(t\)\), we have the guarantee here\.

Thus, we were fine if the true proxy test failed, fine if either one of the proxy objectives were bigger than our guesses, and if either one of our proxy objectives are smaller than our guesses\. Therefore, no approximation quality is lost \(and maybe some is gained\)\. To state clearly, we can solve either side first, and whether we subtract a smaller or bigger number than the proxy, it is okay\.

∎

## Appendix DDatasets

We summarize each dataset considered in our experiments, including the corresponding binary prediction problem\.

Across all datasets, we discard observations with missing entries and represent categorical features using one\-hot encoding\.

We use 20 datasets in this work, most of which are drawn from the benchmark suite ofHeileet al\.\([2026](https://arxiv.org/html/2608.04310#bib.bib156)\)\. We exclude several datasets from that suite because they contain only binary features, such as Droid and Monk2, and add several additional datasets to reach our goal of 20 datasets\.

#### Abalone\(OpenML[2022a](https://arxiv.org/html/2608.04310#bib.bib104)\)\(4,177 samples\)

Predict whether an abalone is male based on its physical measurements\. Exhaustive binarization of this dataset creates 6039 columns \(not counting the label\)\.

#### Adult\(Becker and Kohavi[1996](https://arxiv.org/html/2608.04310#bib.bib139)\)\(48,842 samples\)

Predict whether an individual earns more than $50,000 per year based on demographic and occupational attributes\. Exhaustive binarization of this dataset creates 27237 columns\.

#### Aging\([32](https://arxiv.org/html/2608.04310#bib.bib51);[P\. N\. Malani, J\. Kullgren, and E\. Solway \(2019\)](https://arxiv.org/html/2608.04310#bib.bib52)\)\(714 samples\)

Predict whether an individual has visited at least two doctors\. Exhaustive binarization of this dataset creates 35 columns\.

#### Bank\(Moroet al\.[2014b](https://arxiv.org/html/2608.04310#bib.bib54),[a](https://arxiv.org/html/2608.04310#bib.bib53)\)\(45,211 samples\)

Predict whether a client subscribes to a term deposit following a marketing campaign\. Exhaustive binarization of this dataset creates 9530 columns\.

#### Bike\(Fanaee\-T and Gama[2013](https://arxiv.org/html/2608.04310#bib.bib55); Fanaee\-T[2013](https://arxiv.org/html/2608.04310#bib.bib56)\)\(17,379 samples\)

Predict whether bike rental demand exceeds the median\. Exhaustive binarization of this dataset creates 279 columns\.

#### Churn\(Ericksonet al\.[2025](https://arxiv.org/html/2608.04310#bib.bib60); Marcoulides[2005](https://arxiv.org/html/2608.04310#bib.bib61)\)\(5,000 samples\)

Predict whether a customer will churn\. Exhaustive binarization of this dataset creates 16400 columns\.

#### Compas\(Baoet al\.[2021](https://arxiv.org/html/2608.04310#bib.bib62)\)\(4,966 samples\)

Predict whether a defendant will recidivate within two years\. Exhaustive binarization of this dataset creates 120 columns\.

#### Coupon\([23](https://arxiv.org/html/2608.04310#bib.bib102)\)\(108 samples\)

Predict whether an individual accepts a recommended coupon\. Exhaustive binarization of this dataset creates 64 columns\.

#### Credit\(Yeh[2009](https://arxiv.org/html/2608.04310#bib.bib64); Yeh and Lien[2009](https://arxiv.org/html/2608.04310#bib.bib65)\)\(30,000 samples\)

Predict whether a client will default on their credit card payment in the following month\. Exhaustive binarization of this dataset creates 174581 columns\.

#### Diabetes\(Burrowset al\.[2017](https://arxiv.org/html/2608.04310#bib.bib66)\)\(253,680 samples\)

Predict whether an individual is diabetic\. Exhaustive binarization of this dataset creates 185 columns\.

#### Diamonds\(OpenML[2019](https://arxiv.org/html/2608.04310#bib.bib101)\)\(53,940 samples\)

Predict whether a diamond belongs to cut category 2 based on its physical attributes\. Exhaustive binarization of this dataset creates 2074 columns\.

#### Helena\(OpenML[2018a](https://arxiv.org/html/2608.04310#bib.bib72); Guyonet al\.[2019](https://arxiv.org/html/2608.04310#bib.bib58)\)\(65,196 samples\)

Predict whether an instance belongs to the most frequent class\. Exhaustive binarization of this dataset creates 1540012 \(over 1 million\) columns\.

#### Heloc\(FICO[2018](https://arxiv.org/html/2608.04310#bib.bib73)\)\(2,502 samples\)

Predict whether an individual is high\- or low\-risk for a home equity line of credit\. Exhaustive binarization of this dataset creates 1505 columns\.

#### Jasmine\(OpenML[2018b](https://arxiv.org/html/2608.04310#bib.bib79); Guyonet al\.[2019](https://arxiv.org/html/2608.04310#bib.bib58)\)\(2,984 samples\)

Binary classification using the provided target column\. Exhaustive binarization of this dataset creates 2457 columns\.

#### Pol\(OpenML[2022b](https://arxiv.org/html/2608.04310#bib.bib100)\)\(10,082 samples\)

Binary classification using the provided target column\. Exhaustive binarization of this dataset creates 2126 columns\.

#### Rl\(OpenML[2022c](https://arxiv.org/html/2608.04310#bib.bib99)\)\(4,970 samples\)

Binary classification using the provided target column\. Exhaustive binarization of this dataset creates 1313 columns\.

#### Shopping\(Sakar and Kastro[2018](https://arxiv.org/html/2608.04310#bib.bib91); Sakaret al\.[2018](https://arxiv.org/html/2608.04310#bib.bib92)\)\(12,330 samples\)

Predict whether an online shopping session ends in a purchase\. Exhaustive binarization of this dataset creates 23909 columns\.

#### Spambase\(Hopkinset al\.[1999](https://arxiv.org/html/2608.04310#bib.bib93)\)\(4,601 samples\)

Predict whether an email is spam\. Exhaustive binarization of this dataset creates 15037 columns\.

#### Student\(Cortez[2008](https://arxiv.org/html/2608.04310#bib.bib94); Cortez and Silva[2008](https://arxiv.org/html/2608.04310#bib.bib95)\)\(649 samples\)

Predict whether a student passes a course \(final grade≥10\\geq 10\)\. Exhaustive binarization of this dataset creates 114 columns\.

#### Wine\(OpenML[2025](https://arxiv.org/html/2608.04310#bib.bib98)\)\(6,497 samples\)

Predict whether wine quality is at least 7\. Exhaustive binarization of this dataset creates 2640 columns\.

## Appendix EExperiments

### E\.1Computational Resources

All experiments were conducted on an institutional computing cluster\. Each run was executed on a single compute node equipped with an AMD EPYC 9554 processor \(2\.75 GHz, 64 physical cores\) and was restricted to a single CPU core\. With one exception, each algorithm was given 128 GB of memory and a 100\-hour timeout to compute a Rashomon set for one bootstrap of one dataset for one set of parameters\. We instead limited our anytime algorithms to 32 GB of memory and a 24\-hour timeout, both to reduce resource usage and to evaluate their performance in a more resource\-constrained setting\.

When restricting a proxy algorithm, or one of its subroutines, to a fixed binarization, we select candidate thresholds using the ThresholdGuessing procedure ofMcTavishet al\.\([2022](https://arxiv.org/html/2608.04310#bib.bib114)\)\. We train a gradient\-boosted tree ensemble with 150 depth\-2 estimators and random seed 0, extract the thresholds used by the ensemble, and apply backward elimination to remove thresholds without reducing the ensemble’s training accuracy\.

### E\.2Timing, Memory, and Recall

Table 4:λ=0\.02,ε=0\.03,d=5\\lambda=0\.02,\\varepsilon=0\.03,d=5\. Runtime and peak memory for the exhaustive threshold \(fully continuous\) setting\. Our methods are the four variants shown in the table, each combining our continuous\-feature Rashomon set algorithm \(ArborEnum\) with a different proxy algorithm\. Time is reported in seconds and peak RSS is reported in MB\. Mean±\\pmstd across 3 bootstraps\. Entries marked “–” correspond to partial or unfinished runs with a 100hr timeout and 128GB memory limit\.Table 5:λ=0\.02,ε=0\.03,d=5\\lambda=0\.02,\\varepsilon=0\.03,d=5\. Recall for the exhaustive threshold \(fully continuous\) setting\. mean±\\pmstd is reported\. Recall is reported relative to the best method that finished\. Formally, we calculate the guessed Rashomon bound by taking the minimum objective any method found, counting the number of trees each method found within that bound, and scoring a method by the number of trees as a proportion of the best\. Entries marked “–” correspond to partial or unfinished runs\. Our methods are the four variants shown in the table, each combining our continuous\-feature Rashomon set algorithm with a different proxy algorithm\.We use one\-sided Wilcoxon signed\-rank tests on the results in Table[6](https://arxiv.org/html/2608.04310#A5.T6), treating the mean runtime across the three bootstraps as one paired observation per dataset\. Each comparison includes only datasets for which both methods completed\. Because we perform two runtime comparisons, we control the family\-wise error rate atα=0\.05\\alpha=0\.05using Holm’s correction\. On the six datasets where both our optimal method and SORTD completed, our optimal method was significantly faster \(W=0W=0, Holm\-adjustedp=0\.0156p=0\.0156\)\. On the 14 datasets where both SNIP\+GR and our optimal method completed, SNIP\+GR was also significantly faster \(W=0W=0, Holm\-adjustedp=1\.22×10−4p=1\.22\\times 10^\{\-4\}\)\. These complete\-case comparisons are conservative with respect to the faster methods: for instance, SORTD is not penalized for running out of memory or time\.

Table 6:λ=0\.02,ε=0\.03,d=5\\lambda=0\.02,\\varepsilon=0\.03,d=5\. Runtime for the exhaustive\-threshold \(fully continuous\) setting\. Time is reported in seconds as mean±\\pmstandard deviation across 3 bootstraps\. Entries marked “–” correspond to partial or unfinished runs under a 100\-hour timeout and 128GB memory limit\. The best completed runtime in each row is bolded and the second\-best is underlined\. Our methods are the first four shown in the table, each combining our continuous\-feature Rashomon set algorithm with a different proxy algorithm\.LSR = LicketySPLIT over a binarization; SNIP = LicketySNIP \(fully continuous\); SNIP\+GR = LicketySNIP with its greedy subroutine restricted to a binarization\.

Table 7:λ=0\.02,ε=0\.03,d=5\\lambda=0\.02,\\varepsilon=0\.03,d=5\. Peak memory for the exhaustive\-threshold \(fully continuous\) setting\. Peak RSS is reported in MB as mean±\\pmstandard deviation across 3 bootstraps\. Entries marked “–” correspond to partial or unfinished runs under a 100\-hour timeout and 128GB memory limit\. The lowest completed memory usage in each row is bolded and the second\-lowest is underlined\. Our methods are the first four shown in the table, each combining our continuous\-feature Rashomon set algorithm with a different proxy algorithm\.DatasetLSRSNIPSNIP\+GROptimalPRAXISSORTDTreeFARMSRESPLITAbalone1823\.5±2412\.81823\.5\\pm 2412\.81259\.3±1544\.11259\.3\\pm 1544\.11251\.0±1528\.6\\boldsymbol\{1251\.0\\pm 1528\.6\}53538\.0±44185\.353538\.0\\pm 44185\.3––––Adult837\.4±17\.4\\boldsymbol\{837\.4\\pm 17\.4\}891\.1±12\.5891\.1\\pm 12\.5851\.0±10\.9851\.0\\pm 10\.928629\.1±960\.428629\.1\\pm 960\.4––––Aging249\.1±0\.4249\.1\\pm 0\.4248\.0±0\.8248\.0\\pm 0\.8250\.6±0\.6250\.6\\pm 0\.6253\.9±2\.4253\.9\\pm 2\.4223\.1±1\.5223\.1\\pm 1\.5196\.4±1\.3\\boldsymbol\{196\.4\\pm 1\.3\}5350\.2±1187\.75350\.2\\pm 1187\.7233\.9±1\.8233\.9\\pm 1\.8Bank376\.0±1\.6376\.0\\pm 1\.6358\.3±0\.7\\boldsymbol\{358\.3\\pm 0\.7\}366\.1±0\.5366\.1\\pm 0\.510577\.0±826\.510577\.0\\pm 826\.5––––Bike298\.8±8\.7\\boldsymbol\{298\.8\\pm 8\.7\}299\.6±5\.8299\.6\\pm 5\.8299\.5±7\.2299\.5\\pm 7\.23044\.2±89\.83044\.2\\pm 89\.8356\.5±22\.4356\.5\\pm 22\.412139\.7±213\.212139\.7\\pm 213\.2–2824\.3±36\.72824\.3\\pm 36\.7Churn335\.2±49\.2\\boldsymbol\{335\.2\\pm 49\.2\}337\.4±58\.8337\.4\\pm 58\.8338\.4±57\.6338\.4\\pm 57\.6129432\.5±1527\.8129432\.5\\pm 1527\.8––––Compas255\.1±3\.1255\.1\\pm 3\.1251\.0±1\.1251\.0\\pm 1\.1254\.3±1\.1254\.3\\pm 1\.1276\.9±2\.1276\.9\\pm 2\.1233\.4±3\.6\\boldsymbol\{233\.4\\pm 3\.6\}434\.0±11\.8434\.0\\pm 11\.8–365\.6±0\.8365\.6\\pm 0\.8Coupon272\.1±34\.6272\.1\\pm 34\.6249\.7±2\.7249\.7\\pm 2\.7252\.0±3\.1252\.0\\pm 3\.1250\.5±1\.1250\.5\\pm 1\.1284\.2±96\.3284\.2\\pm 96\.3197\.4±0\.9\\boldsymbol\{197\.4\\pm 0\.9\}3084\.8±318\.23084\.8\\pm 318\.2–Credit1231\.4±30\.21231\.4\\pm 30\.21217\.0±3\.1\\boldsymbol\{1217\.0\\pm 3\.1\}1218\.8±2\.41218\.8\\pm 2\.4–––––Diabetes379\.5±0\.7379\.5\\pm 0\.7353\.4±1\.3\\boldsymbol\{353\.4\\pm 1\.3\}378\.5±1\.3378\.5\\pm 1\.3808\.1±54\.1808\.1\\pm 54\.1372\.5±8\.7372\.5\\pm 8\.724278\.8±434\.424278\.8\\pm 434\.4–2748\.5±9\.72748\.5\\pm 9\.7Diamonds355\.0±2\.2355\.0\\pm 2\.2341\.6±3\.9\\boldsymbol\{341\.6\\pm 3\.9\}346\.0±4\.2346\.0\\pm 4\.26282\.0±131\.16282\.0\\pm 131\.14424\.3±595\.34424\.3\\pm 595\.3–––Helena15908\.0±21\.515908\.0\\pm 21\.515861\.3±16\.8\\boldsymbol\{15861\.3\\pm 16\.8\}15879\.9±17\.115879\.9\\pm 17\.1–––––Heloc537\.2±227\.4\\boldsymbol\{537\.2\\pm 227\.4\}548\.9±162\.1548\.9\\pm 162\.1565\.2±184\.1565\.2\\pm 184\.1–3213\.1±1695\.33213\.1\\pm 1695\.3––20853\.2±2931\.520853\.2\\pm 2931\.5Jasmine646\.8±424\.1\\boldsymbol\{646\.8\\pm 424\.1\}704\.8±483\.7704\.8\\pm 483\.7751\.2±550\.0751\.2\\pm 550\.0–4275\.8±3840\.14275\.8\\pm 3840\.1––32739\.5±1899\.432739\.5\\pm 1899\.4Pol1945\.8±882\.3\\boldsymbol\{1945\.8\\pm 882\.3\}2094\.3±727\.82094\.3\\pm 727\.82014\.6±768\.62014\.6\\pm 768\.635074\.4±2411\.635074\.4\\pm 2411\.6––––Rl1363\.4±453\.81363\.4\\pm 453\.81198\.2±166\.1\\boldsymbol\{1198\.2\\pm 166\.1\}1248\.4±214\.31248\.4\\pm 214\.345360\.1±6446\.045360\.1\\pm 6446\.021879\.3±4285\.121879\.3\\pm 4285\.1–––Shopping3037\.6±210\.33037\.6\\pm 210\.31563\.7±140\.9\\boldsymbol\{1563\.7\\pm 140\.9\}1596\.9±97\.51596\.9\\pm 97\.5–––––Spambase64879\.6±12411\.8\\boldsymbol\{64879\.6\\pm 12411\.8\}–93511\.3±31495\.693511\.3\\pm 31495\.6–––––Student253\.3±0\.6253\.3\\pm 0\.6251\.5±1\.5251\.5\\pm 1\.5253\.1±2\.0253\.1\\pm 2\.0871\.6±23\.4871\.6\\pm 23\.4226\.1±1\.6\\boldsymbol\{226\.1\\pm 1\.6\}526\.4±12\.3526\.4\\pm 12\.3–287\.1±5\.8287\.1\\pm 5\.8Wine348\.9±44\.0348\.9\\pm 44\.0304\.2±34\.0\\boldsymbol\{304\.2\\pm 34\.0\}306\.0±31\.9306\.0\\pm 31\.978053\.3±10711\.478053\.3\\pm 10711\.42361\.7±1519\.22361\.7\\pm 1519\.2–––

LSR = LicketySPLIT over a binarization; SNIP = LicketySNIP \(fully continuous\); SNIP\+GR = LicketySNIP with its greedy subroutine restricted to a binarization\.

Table 8:λ=0\.02,ε=0\.03,d=5\\lambda=0\.02,\\varepsilon=0\.03,d=5\. Runtime with at most 100 thresholds per continuous feature\. Time is reported in seconds as mean±\\pmstandard deviation across 3 bootstraps\. Entries marked “–” correspond to partial or unfinished runs under a 100\-hour timeout and 128GB memory limit\. The best completed runtime in each row is bolded and the second\-best is underlined\. Our methods are the first four shown in the table, each combining our continuous\-feature Rashomon set algorithm with a different proxy algorithm\.LSR = LicketySPLIT over a binarization; SNIP = LicketySNIP \(fully continuous\); SNIP\+GR = LicketySNIP with its greedy subroutine restricted to a binarization\.

Table 9:λ=0\.02,ε=0\.03,d=5\\lambda=0\.02,\\varepsilon=0\.03,d=5\. Peak memory with at most 100 thresholds per continuous feature\. Peak RSS is reported in MB as mean±\\pmstandard deviation across 3 bootstraps\. Entries marked “–” correspond to partial or unfinished runs under a 100\-hour timeout and 128GB memory limit\. The lowest completed memory usage in each row is bolded and the second\-lowest is underlined\. Our methods are the first four shown in the table, each combining our continuous\-feature Rashomon set algorithm with a different proxy algorithm\.LSR = LicketySPLIT over a binarization; SNIP = LicketySNIP \(fully continuous\); SNIP\+GR = LicketySNIP with its greedy subroutine restricted to a binarization\.

Table 10:λ=0\.02,ε=0\.03,d=5\\lambda=0\.02,\\varepsilon=0\.03,d=5\. Recall with at most 100 thresholds per continuous feature for our four methods\. Mean±\\pmstandard deviation is reported across 3 bootstraps\. Recall is measured relative to the best method that finished: we use the minimum objective found by any method as the guessed Rashomon bound, count the trees each method found within that bound, and divide by the largest such count\. Entries marked “–” correspond to partial or unfinished runs\. The best recall in each row is bolded and the second\-best distinct recall is underlined\. Our methods are the four shown in the table, each combining our continuous\-feature Rashomon set algorithm with a different proxy algorithm\.Table 11:λ=0\.01,ε=0\.03,d=5\\lambda=0\.01,\\varepsilon=0\.03,d=5\. Runtime for the exhaustive\-threshold \(fully continuous\) setting\. Time is reported in seconds as mean±\\pmstd across 3 bootstraps\. Best values are bolded and second\-best values are underlined\. Entries marked “–” correspond to partial or unfinished runs with a 100hr timeout and 128GB memory limit\. Our methods are the four shown in the table, each combining our continuous\-feature Rashomon set algorithm with a different proxy algorithm\.Table 12:λ=0\.01,ε=0\.03,d=5\\lambda=0\.01,\\varepsilon=0\.03,d=5\. Peak memory for the exhaustive\-threshold \(fully continuous\) setting\. Peak RSS is reported in MB as mean±\\pmstd across 3 bootstraps\. Best values are bolded and second\-best values are underlined\. Entries marked “–” correspond to partial or unfinished runs with a 100hr timeout and 128GB memory limit\. Our methods are the four shown in the table, each combining our continuous\-feature Rashomon set algorithm with a different proxy algorithm\.Table 13:λ=0\.01,ε=0\.03,d=5\\lambda=0\.01,\\varepsilon=0\.03,d=5\. Recall for the exhaustive\-threshold \(fully continuous\) setting, reported as mean±\\pmstd across 3 bootstraps\. Recall is measured relative to the best method that finished: we take the minimum objective found by any completed method, count each method’s trees within the resulting Rashomon bound, and divide by the largest such count\. Best values are bolded and second\-best values are underlined\. Entries marked “–” correspond to partial or unfinished runs with a 100hr timeout and 128GB memory limit\. Our methods are the four shown in the table, each combining our continuous\-feature Rashomon set algorithm with a different proxy algorithm\.Table 14:λ=0\.005,ε=0\.03,d=5\\lambda=0\.005,\\varepsilon=0\.03,d=5\. Runtime for the exhaustive threshold \(fully continuous\) setting\. Time is reported in seconds as mean±\\pmstd across 3 bootstraps\. Entries marked “–” correspond to partial or unfinished runs with a 100hr timeout and 128GB memory limit\. The fastest completed method is bolded and the second\-fastest distinct method is underlined\. Our methods are the four shown in the table, each combining our continuous\-feature Rashomon set algorithm with a different proxy algorithm\.Table 15:λ=0\.005,ε=0\.03,d=5\\lambda=0\.005,\\varepsilon=0\.03,d=5\. Peak memory for the exhaustive threshold \(fully continuous\) setting\. Peak RSS is reported in MB as mean±\\pmstd across 3 bootstraps\. Entries marked “–” correspond to partial or unfinished runs with a 100hr timeout and 128GB memory limit\. The lowest completed memory usage is bolded and the second\-lowest distinct value is underlined\. Our methods are the four shown in the table, each combining our continuous\-feature Rashomon set algorithm with a different proxy algorithm\.Table 16:λ=0\.005,ε=0\.03,d=5\\lambda=0\.005,\\varepsilon=0\.03,d=5\. Recall for the exhaustive threshold \(fully continuous\) setting\. Mean±\\pmstd is reported across 3 bootstraps\. Recall is measured relative to the best method that finished\. Entries marked “–” correspond to partial or unfinished runs\. The highest completed recall is bolded and the second\-highest distinct value is underlined\. Our methods are the four shown in the table, each combining our continuous\-feature Rashomon set algorithm with a different proxy algorithm\.Table 17:Runtime comparison of LicketySNIP using sorted lists of active sample indices versus binary threshold columns for its fully continuous greedy subroutine\. The italicized ArborEnum\+SNIP\+GR column is shown only as a reference and is not part of the comparison; accordingly, it does not affect the bolding\.λ=0\.02\\lambda=0\.02,ε=0\.03\\varepsilon=0\.03,d=5d=5, and exhaustive thresholds\. Time is reported in seconds as mean±\\pmstandard deviation across 3 bootstraps\.Table 18:Runtime comparison of LicketySNIP using sorted lists of active sample indices versus binary threshold columns for its fully continuous greedy subroutine\. The italicized ArborEnum\+SNIP\+GR column is shown only as a reference and is not part of the comparison; accordingly, it does not affect the bolding\.λ=0\.01\\lambda=0\.01,ε=0\.03\\varepsilon=0\.03,d=5d=5, and exhaustive thresholds\. Time is reported in seconds as mean±\\pmstandard deviation across 3 bootstraps\.Table 19:λ=0\.005\\lambda=0\.005,ε=0\.03\\varepsilon=0\.03, andd=5d=5\. Runtime of ArborEnum\+LicketySNIP depending on when the greedy subroutine in LicketySNIP uses binary threshold columns or sorted lists\. The italicized ArborEnum\+SNIP\+GR column is shown only as a reference and is not part of the comparison; accordingly, it does not affect the bolding or underlining\. Time is reported in seconds as mean±\\pmstandard deviation across 3 bootstraps\. The best value among the first two columns in each row is bolded, and the second\-best is underlined\.
### E\.3Anytime Overhead

Table[20](https://arxiv.org/html/2608.04310#A5.T20)reports the runtime overhead of the anytime algorithm when proxy strength is held fixed\. In some cases, the anytime variant is actually faster because it explores subproblems in a different order\. Across datasets, the median overhead is only \(2\.7%\)\.

In all experiments, we evaluate the anytime algorithm without progressively strengthening the proxy because our approximate proxies already recover essentially all trees while running orders of magnitude faster than an optimal proxy\. For example, when the approximation is \(100×\\times\) faster, approximately \(99%\) of the full optimal runtime would be spent obtaining a certificate of optimality and recovering the small number of remaining trees\. We therefore focus on the more practically consequential regime of aiming to converge to our approximations\. Runtime overhead is also less informative in the optimal\-proxy setting, since one could simply discard the approximate computation and rerun the optimal method from scratch, incurring only about a \(1%\) overhead when the approximation is \(100×\\times\) faster\.

Table 20:Runtime overhead of the anytime algorithm \(ArborEnum\+LicketySNIP\) relative to non\-anytime execution using the LicketySNIP proxy \(ArborEnum\+LicketySNIP\) over continuous features\. Each value is the mean±\\pmstandard deviation across three bootstraps of the anytime runtime divided by the non\-anytime runtime\.λ=0\.02\\lambda=0\.02andεmult=0\.03\\varepsilon\_\{\\mathrm\{mult\}\}=0\.03\.
### E\.4Improving Recall with a Bigger Budget

Table[21](https://arxiv.org/html/2608.04310#A5.T21)presents the same result as the main paper but forλ=0\.01\\lambda=0\.01\. We do not show results forλ=0\.02\\lambda=0\.02because this proxy choice always yielded perfect approximation quality \(there is nothing to show\)\.

Table 21:For every dataset on which ArborEnum\+SNIP\+GR does not achieve perfect recall \(averaged across bootstraps\), extending the root budget recovers the remaining trees with little additional runtime while remaining substantially faster than our optimal method when it completes\. The timings are obtained by first solving withεmult=0\.03\\varepsilon\_\{\\textrm\{mult\}\}=0\.03and then extending the subgraph\.λ=0\.01\\lambda=0\.01\.
### E\.5Budget\-Independent Subgraphs

Table 22:Effect of budget\-independent subgraph caching forλ=0\.005\\lambda=0\.005andεmult=0\.015\\varepsilon\_\{\\mathrm\{mult\}\}=0\.015\. Speedup is the runtime without storing pointers to previously constructed subgraphs, as in PRAXIS\(Heileet al\.[2026](https://arxiv.org/html/2608.04310#bib.bib156)\), divided by the runtime with budget\-independent subgraph caching\. The increase in trees is the number of trees recovered with budget\-independent subgraph caching divided by the number recovered without storing subgraph pointers\.DatasetSpeedup by Caching×\\timesIncrease in Trees by CachingOR Nodes with Budget\-Independent CachingOR Nodes without Stored Subgraph Pointers, as in PRAXISAdult1\.0431\.0004042,661Aging0\.9891\.00011Bank0\.9971\.0001,1611,659Bike1\.0321\.00080,817424,071COMPAS1\.0541\.0005,51235,981Coupon53\.5861\.00092,711116,247,505Credit0\.9911\.00033Diabetes1\.0031\.00011Diamonds0\.9981\.000173349HELOC1\.0211\.0011,103,1348,545,465Pol1\.0121\.0003,00113,743Shopping1\.0001\.0001,0371,037Spambase1\.3221\.0071,047,39924,536,957Student0\.9801\.0001,2404,981Wine1\.0061\.0005621,177

Table 23:Effect of budget\-independent subgraph caching forλ=0\.005\\lambda=0\.005andεmult=0\.03\\varepsilon\_\{\\mathrm\{mult\}\}=0\.03\. Speedup is the runtime without storing pointers to previously constructed subgraphs, as in PRAXIS, divided by the runtime with budget\-independent subgraph caching\. The increase in trees is the number of trees recovered with budget\-independent subgraph caching divided by the number recovered without storing subgraph pointers\.Table 24:Effect of budget\-independent subgraph caching forλ=0\.005\\lambda=0\.005andεmult=0\.05\\varepsilon\_\{\\mathrm\{mult\}\}=0\.05\. Speedup is the runtime without storing pointers to previously constructed subgraphs, as in PRAXIS, divided by the runtime with budget\-independent subgraph caching\. The increase in trees is the number of trees recovered with budget\-independent subgraph caching divided by the number recovered without storing subgraph pointers\.Table 25:Effect of budget\-independent subgraph caching forλ=0\.005\\lambda=0\.005andεmult=0\.5\\varepsilon\_\{\\mathrm\{mult\}\}=0\.5\. Speedup is the runtime without storing pointers to previously constructed subgraphs, as in PRAXIS, divided by the runtime with budget\-independent subgraph caching\. The increase in trees is the number of trees recovered with budget\-independent subgraph caching divided by the number recovered without storing subgraph pointers\.Table 26:Effect of budget\-independent subgraph caching forλ=0\.01\\lambda=0\.01andεmult=0\.03\\varepsilon\_\{\\mathrm\{mult\}\}=0\.03\. Speedup is the runtime without storing pointers to previously constructed subgraphs, as in PRAXIS, divided by the runtime with budget\-independent subgraph caching\. The increase in trees is the number of trees recovered with budget\-independent subgraph caching divided by the number recovered without storing subgraph pointers\.Table 27:Effect of budget\-independent subgraph caching forλ=0\.01\\lambda=0\.01andεmult=0\.05\\varepsilon\_\{\\mathrm\{mult\}\}=0\.05\. Speedup is the runtime without storing pointers to previously constructed subgraphs, as in PRAXIS, divided by the runtime with budget\-independent subgraph caching\. The increase in trees is the number of trees recovered with budget\-independent subgraph caching divided by the number recovered without storing subgraph pointers\.Table 28:Effect of budget\-independent subgraph caching forλ=0\.02\\lambda=0\.02andεmult=0\.2\\varepsilon\_\{\\mathrm\{mult\}\}=0\.2\. Speedup is the runtime without storing pointers to previously constructed subgraphs, as in PRAXIS, divided by the runtime with budget\-independent subgraph caching\. The increase in trees is the number of trees recovered with budget\-independent subgraph caching divided by the number recovered without storing subgraph pointers\.