Optimal decision trees have attracted increasing attention in recent years, yet existing algorithms face two closely related challenges. First, the trees they construct have limited expressivity because their splitting rules are typically restricted to axis-parallel splits or binary features. Second, these algorithms generally scale poorly to large datasets. These challenges compound one another: more expressive splitting rules increase the combinatorial complexity of the search space, making the resulting optimal decision tree (ODT) problem even more difficult to solve. Building on the proper decision tree framework of \citet{he2025odt}, we propose, to the best of our knowledge, the first algorithm for constructing optimal decision trees with hypersurface splits. The algorithm has worst-case work complexity O(K!KNKG+1) when N≥K and fixed-dimensional feasibility tests are treated as constant-cost operations, where G=(MD+M)−1 depends on the hypersurface polynomial degree M and the data dimension D. Its structure is naturally amenable to vectorization and parallelization, enabling efficient execution on GPUs, and the generic algorithm design can be used to accelerate other ODT variants, such as axis-parallel decision (ADT) trees. We further develop a safe pruning strategy that substantially reduces the number of candidate configurations and an incremental generation procedure that reduces the associated feasibility-checking cost from O(K2) to O(K).
Figures & tables
Figure 1: Synthetic dataset (left) generated by degree-2 polynomials; axis-parallel decision trees learned by CART and the state-of-the-art optimal algorithm—ConTree (middle two); and hypersurface decision trees (HSDT) learned using our algorithm (right), with corresponding numbers of misclassifications (nmc), tree depths ( d ), and tree sizes ( K ).
Figure 2: Taxonomy of optimal decision tree problems. Much of the prior work that claims to solve ODT problems solves only the ODT-BF problem. When solving ODT problems, one can optimize either depth-constrained trees or size-constrained trees (also referred to as sparse decision trees ).
Figure 4: Parallel run times for sodtrec and sodtvec across K (left), and log-log run time for sodtvec up to 1×106 nested combinations (right).
Table 4
Dataset
N
D
C
CART-depth d=2
ConTree d=2
CART-size K=2
CART-size K=3
HDT K=2
HDT K=3
haberman
283
3
2
75.58/73.68 (1.62/3.14)
76.99/72.98 (0.93/3.06)
74.25/72.63 (1.26/4.52)
75.31/73.68 (1.82/2.94)
79.38/ 78.25 (1.23/3.60)
80.70 /78.24 (1.39/4.87)
BldTrns
502
4
2
75.71/72.08 (1.05/2.02)
77.16/71.09 (0.60/1.70)
75.71/72.08 (1.05/02.02)
76.91/74.06 (0.56/03.09)
79.38/ 78.50 (1.16/4.37)
80.71 /78.25 (1.12/3.86)
sepsis
975
3
2
94.13/93.64 (0.30/1.06)
94.26/93.74 (0.30/0.88)
94.13/93.64 (0.30/1.06)
94.18/93.64 (0.35/1.06)
94.97/ 93.85 (0.44/1.95)
95.39 / 93.85 (0.43/1.95)
algerian
243
14
2
99.28/98.37 (0.25/1.53)
99.69/95.92 (0.25/2.24)
99.28/98.37 (0.25/1.52)
99.59/98.37 (0.21/1.53)
99.59/97.96 (0.43/1.44)
100 / 98.78 (0.00/1.12)
Table 2: (Part I: K in 2, 3) Five-fold cross-validation results. We compare the performance of our HDT model, with K (number of splitting rules) ranging from 2 to 3 and the depth is fixed as 2, against approximate methods:size- and depth-constrained CART algorithms (CART-size and CART-depth), as well as the state-of-the-art optimal ADT algorithm, ConTree ( Brita et al., 2025 ) . Results are reported as mean accuracy on the training and test sets in the format Training Error / Test Error (Standard Deviation: Train / Test) . The best-performing algorithm in each row is shown in bold . Complete results appear in Table 8 .
Appendix figures & tables15 assets
Supplementary material from the paper’s appendix.
Appendix
Figure 6: Same ground truth synthetic dataset as 1 . The above three models are axis-parallel decision trees learned by CART and the below three are axis-parallel decision trees learned by ConTree algorithm.
Figure 7: Let hi={(x,y,z):z=0} with Xi={(4,3,0),(0,2,0),(0,−2,0)} , hj={(x,y,z):y=0} with Xj={(13,0,1),(7,0,−4),(8,0,3)} , and hk={(x,y,z):x=5} with Xk={(5,7,1),(5,−2,3),(5,−1,5)} . Each set contains three affinely independent points, and the nine points are in general position (no four are coplanar). Since the y -coordinates in Xi are 3,2,−2 and the z -coordinates in Xj are 1,−4,3 , both pstr(Xi,hj) and pstr(Xj,hi) hold; hence pcrs(hi,hj) is true. Nevertheless, Xi⊂{x<5}=hk− and Xj⊂{x>5}⊂hk+ . In other words, the blue hyperplane ( hi ) and yellow hyperplanes ( hj ) are crossed (mutually straddling), but there exists a third hyperplane ( hk ) that can separate them.
Figure 8: The three pairwise ancestry relations. The upper row shows the two rules and their defining point sets; the lower row shows the corresponding tree structures. (a) In mutual ancestry, both root orders are valid. (b) In asymmetrical ancestry, only one root order is valid. (c) In no ancestry, neither rule can be a direct ancestor of the other. The last case concerns direct ancestry only and does not, without an additional geometric condition, rule out the two rules appearing in separate branches of a larger tree.
Figure 9: Running time comparison between sodtrec and sodtvec with varying K on sequential setting.
Figure 10: Running time comparison between sodtrec and sodtvec with varying K on parallel setting.
Figure 11: Combinatorial complexity of feasible nested combinations with varying K . Each bar corresponds to a fixed K starts from K=2 (left-most bar) to the value of K labeled below each group of bars.
Figure 12: Combinatorial complexity of feasible nested combinations with varying K . Each bar corresponds to a fixed K starts from K=2 (left-most bar) to the value of K labeled below each group of bars.
Tree size ( K )
Method
Train Acc (%)
Test Acc (%)
Tree size
Depth
Maximum
Average
Expected
2
CART-depth-2 CART-size-4 ConTree-2 HDT Ground Truth
Table 7: The effect of noise on training data. Training data size = 100. Ground truth trees are size 2.
Dataset
N
D
C
CART-depth d=2
ConTree d=2
CART-size K=2
CART-size K=3
HDT K=2
HDT K=3
Parkinsons
195
22
2
87.95/84.62 (1.48/5.85)
93.20/82.56 (1.04/5.23)
87.82/85.13 (1.67/6.36)
90.77/86.67 (1.04/5.71)
93.72/ 89.74 (1.66/3.14)
94.49 / 89.74 (2.15/3.14)
Diabetic
1146
19
2
65.55/64.00 (0.92/3.74)
67.36/63.48 (0.79/3.95)
65.55/64.00 (0.92/3.74)
67.53/62.96 (1.05/2.66)
79.93/ 76.52 (1.17/1.71)
80.09 /76.35 (1.06/2.38)
BalScl
625
4
3
71.72/65.12 (0.94/2.00)
72.88/66.88 (0.35/1.40)
69.80/63.20 (0.44/1.75)
72.68/64.64 (1.12/2.74)
93.44/94.40 (0.33/1.26)
94.28 / 94.56 (0.30/1.54)
StatlogVS
845
18
4
53.34/52.66 (0.32/2.97)
62.42/61.89 (0.91/4.07)
49.94/48.40 (0.64/3.73)
53.34/52.66 (0.32/2.97)
65.12/63.31 (0.78/4.73)
68.75 / 64.38 (0.74/2.58)
Appendix
Table 8: (Part II: K in 2, 3) Five-fold cross-validation results on the UCI dataset. We compare the performance of our HDT algorithm, with K (number of splitting rules) ranging from 2 to 3, trained using sodtWSH —against approximate methods:size- and depth-constrained CART algorithms (CART-size and CART-depth), as well as the state-of-the-art optimal axis-parallel decision tree algorithm, ConTree. The depth of the CART-depth and ConTree algorithms are fixed at 2. Results are reported as mean accuracy on the training and test sets in the format Training Accuracy / Test Accuracy(Standard Deviation: Train / Test) . The best-performing algorithm in each row is shown in bold .
Dataset
N
D
C
CART-depth d=3
ConTree d=3
CART-size K=4
CART-size K=5
CART-size K=6
HDT K=4
HDT K=5
HDT K=6
haberman
283
3
2
77.35/74.39 (1.38/3.25)
80.97/72.98 (1.22/03.94)
76.20/73.33 (1.99/2.58)
77.17/72.28 (2.21/1.72)
77.97/72.28 (1.71/2.58)
81.68/78.94 (0.86/3.51)
82.48/79.29 (0.97/4.30)
82.83 / 79.65 (1.15/4.37)
BldTrns
502
4
2
77.41/74.06 (0.64/03.62)
80.45/74.06 (0.843/2.76)
78.40/77.23 (0.56/2.80)
79.05/75.45 (1.32/4.13)
79.20/73.86 (1.21/3.41)
81.68/78.94 (0.97/3.51)
82.48/79.30 (1.20/2.88)
82.83 / 79.65 (1.15/4.23)
sepsis
975
3
2
94.23/93.74 (0.35/1.19)
94.56/93.44 (0.34/1.10)
94.28/93.54 (0.33/1.11)
94.39/93.54 (0.34/0.95)
94.44/93.54 (0.29/0.95)
95.77/93.85 (0.43/1.95)
96.10/93.85 (0.43/1.95)
96.44 / 94.05 (0.46/1.72)
algerian
243
14
2
99.59/98.37 (0.21/1.53)
100 /95.51 (0.00/3.00)
99.79/98.37 (0.25/1.53)
99.90/98.37 (0.21/1.53)
100 /98.37 (0.00/1.53)
100 / 99.18 (0.00/1.12)
100 /97.96 (0.00/1.44)
100 /96.74 (0.00/1.83)
Appendix
Table 9: (Part I: K in 4, 5, 6) Five-fold cross-validation results on the UCI dataset. We compare the performance of our HDT algorithm, with K (number of splitting rules) ranging from 4 to 6, trained using sodtWSH —against approximate methods:size- and depth-constrained CART algorithms (CART-size and CART-depth), as well as the state-of-the-art optimal axis-parallel decision tree algorithm, ConTree. The depth of the CART-depth and ConTree algorithms are fixed at 3. Results are reported as mean accuracy on the training and test sets in the format Training Error / Test Error (Standard Deviation: Train / Test) . The best-performing algorithm in each row is shown in bold .
Dataset
N
D
C
CART-depth d=3
ConTree d=3
CART-size K=4
CART-size K=5
CART-size K=6
HDT K=4
HDT K=5
HDT K=6
iris
147
4
3
98.12/90.67 (1.26/2.49)
99.82/91.33 (0.34/4.00)
98.80/88.00 (1.03/4.52)
99.15/88.00 (0.76/4.52)
99.32/88.00 (0.64/4.52)
99.15/96.77 (2.94/12.61)
100 / 97.77 (0.00/12.61)
100 /96.77 (0.00/12.61)
MnkPrb
432
6
2
82.44/78.62 (3.61/3.89)
89.51 / 86.44 (1.43/5.65)
82.43/78.62 (3.61/3.89)
83.25/78.16 (2.41/2.72)
81.54/77.01 (2.60/3.17)
82.46/81.38 (1.30/5.6)
82.73/81.61 (1.61/5.75)
82.96/82.30 (1.50/6.38)
UKM
403
5
5
88.76/86.42 (1.38/3.75)
91.55 / 87.90 (0.60/3.26)
85.34/80.00 (0.46/3.86)
87.39/83.70 (0.64/3.44)
89.57/87.65 (0.32/1.35)
73.10/68.89 (10.74/17.00)
73.60/75.30 (10.17/9.88)
73.79/75.56 (10.3/9.54)
TchAsst
106
5
4
62.38/41.82 (2.21/4.45)
67.62/46.36 (2.65/10.52)
58.81/40.91 (1.43/4.98)
62.14/43.64 (2.31/3.64)
63.81/42.73 (2.88/4.64)
78.33/ 62.73 (1.13/10.85)
79.76/ 62.73 (1.19/10.85)
80.48 /59.09 (1.81/8.50)
Appendix
Table 10: (Part II: K in 4, 5, 6) Five-fold cross-validation results on the UCI dataset. We compare the performance of our HDT algorithm, with K (number of splitting rules) ranging from 4 to 6, trained using sodtWSH —against approximate methods:size- and depth-constrained CART algorithms (CART-size and CART-depth), as well as the state-of-the-art optimal axis-parallel decision tree algorithm, ConTree. The depth of the CART-depth and ConTree algorithms are fixed at 3. Results are reported as mean accuracy on the training and test sets in the format Training Error / Test Error (Standard Deviation: Train / Test) . The best-performing algorithm in each row is shown in bold .
Decision trees are prized for their interpretability and strong performance on tabular data, but popular greedy top-down induction algorithms can yield suboptimal and unnecessarily complex structures. Optimal decision tree methods address this through global optimization, yet remain restricted to axis-aligned threshold splits, which limit the expressivity of each node and often force deep, complex trees to capture non-linear feature effects. Shape Generalized Trees (SGTs) generalize threshold splits to learnable univariate shape functions, improving expressivity and enabling more compact trees. However, existing SGT induction algorithms are greedy and offer no optimality guarantees. In this work, we introduce Literati, the first algorithm for optimal SGT induction. We propose a novel AND/OR graph formulation of the problem that jointly optimizes tree structure and shape function complexity. To solve this AND/OR graph, we develop an AO*-based algorithm with two enhancements that improve anytime performance while preserving optimality: a secondary heuristic for OR-node selection and a round-robin policy for AND-node exploration. Across 24 real-world datasets, Literati achieves higher training and test accuracy than state-of-the-art tree approaches.
Nakul Upadhya, Eldan Cohen
Department of Mechanical and Industrial Engineering University of Toronto, Toronto, Canada
Optimal decision trees (ODTs) are compact, interpretable machine learning models that globally optimize a given objective, but their scalability remains challenging. While recent work has proposed a variety of search strategies to improve scalability, the precise contribution of each strategy remains unclear. To address this gap, we introduce a general algorithmic framework for ODTs that instantiates previously used search strategies and enables the definition of new ones. This provides a common lens through which to understand and compare different strategies, which we use to empirically investigate the effect of 18 search strategies. Compared to the state of the art, the best strategy in our evaluation achieves significantly better anytime performance for classification, and improves runtime by more than an order of magnitude for regression.
Jacobus G. M. van der Linden, Mim van den Bos, Emir Demirović
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.
Zakk Heile, Hayden McTavish, Margo Seltzer +1
Department of Computer Science, Duke University, Durham, USA · Department of Computer Science, University of British Columbia, Vancouver, Canada