Optimal hypersurface decision trees

Xi He

cs.LGSep 15, 2025

Optimal hypersurface decision trees

Authors: Xi He

Organizations: Department of Computer Science, Peking University, Beijing, China, 1000871

Abstract

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\left(K!K N^{KG+1}\right)$ when $N\geq K$ and fixed-dimensional feasibility tests are treated as constant-cost operations, where $G=\binom{D+M}{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(K^2)$ to $O(K)$ .

Figures & tables

Panel of Figure 1 — 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$ ).

Panel of Figure 2 — 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 ).

Panel of Figure 4 — Figure 4: Parallel run times for $\mathit{sodt}_{\text{rec}}$ and $\mathit{sodt}_{\text{vec}}$ across $K$ (left), and log-log run time for $\mathit{sodt}_{\text{vec}}$ up to $1\times 10^{6}$ 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

Panel of Figure 6 — 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

h_{i}=\{(x,y,z):z=0\}

with

X_{i}=\{(4,3,0),(0,2,0),(0,-2,0)\}

h_{j}=\{(x,y,z):y=0\}

with

X_{j}=\{(13,0,1),(7,0,-4),(8,0,3)\}

, and

h_{k}=\{(x,y,z):x=5\}

with

X_{k}=\{(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

X_{i}

are

3,2,-2

and the

z

-coordinates in

X_{j}

are

1,-4,3

, both

p_{\mathrm{str}}(X_{i},h_{j})

and

p_{\mathrm{str}}(X_{j},h_{i})

hold; hence

p_{\mathrm{crs}}(h_{i},h_{j})

is true. Nevertheless,

X_{i}\subset\{x<5\}=h_{k}^{-}

and

X_{j}\subset\{x>5\}\subset h_{k}^{+}

. In other words, the blue hyperplane (

h_{i}

) and yellow hyperplanes (

h_{j}

) are crossed (mutually straddling), but there exists a third hyperplane (

h_{k}

) 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.

Panel of Figure 9 — Figure 9: Running time comparison between $\mathit{sodt}_{\text{rec}}$ and $\mathit{sodt}_{\text{vec}}$ with varying $K$ on sequential setting.

Panel of Figure 10 — Figure 10: Running time comparison between $\mathit{sodt}_{\text{rec}}$ and $\mathit{sodt}_{\text{vec}}$ with varying $K$ on parallel setting.

Panel of Figure 11 — 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.

Panel of Figure 12 — 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	89.12 (0.04) 93.82 (3.01) 91.72 (3.83) 100 (0.00) 100 (0.00)	82.61 (0.04) 86.12 (3.73) 84.57 (4.03) 93.50 (3.21) 100 (0.00)	2.92 (0.27) 4.00 (0.00) 3.00 (0.00) 2.00 (0.00) 2.00 (0.00)	2.00 (0.00) 3.18 (0.38) 2.00 (0.00) 2.00 (0.00) 2.00 (0.00)	1.97 (0.09) 2.49 (0.16) 2.00 (0.00) 1.67 (1.20) 1.67 (1.20)	1.96 (0.15) 2.15 (0.20) 2.00 (0.00) 1.65 (0.16) 1.66 (0.16)
3	CART-depth-3 CART-size-6 ConTree-3 HDT Ground Truth	90.72 (4.71) 93.88 (3.89) 95.98 (2.93) 100 (0.00) 100 (0.00)	81.30 (5.71) 83.92 (5.55) 85.25 (4.96) 94.91 (2.36) 100 (0.00)	5.90 (0.00) 6.00 (0.00) 6.94 (0.24) 3.00 (0.00) 3.00 (0.00)	3.00 (0.00) 4.02 (0.65) 3.00 (0.00) 3.00 (0.00) 2.72 (0.45)	2.83 (0.14) 3.10 (0.24) 2.99 (0.03) 2.25 (0.00) 2.18 (0.11)	2.77 (0.19) 2.71 (0.20) 2.99 (0.04) 2.18 (0.25) 2.07 (0.24)
4	CART-depth-3 CART-size-8 ConTree-3 HDT Ground Truth	87.98 (5.26) 93.90 (3.93) 93.12 (4.02) 97.46 (1.70) 100 (0.00)	77.66 (5.38) 81.93 (4.93) 81.51 (4.78) 89.89 (3.71) 100 (0.00)	6.12 (0.86) 8.00 (0.00) 7.00 (0.00) 4.00 (0.00) 4.00 (0.00)	3.00 (0.00) 4.54 (0.57) 3.00 (0.00) 3.52 (0.50) 3.52 (0.50)	2.87 (0.14) 3.49 (0.21) 3.00 (0.00) 2.63 (0.19) 2.63 (0.19)	2.86 (0.15) 3.13 (0.21) 3.00 (0.00) 2.60 (0.31) 2.63 (0.33)

Appendix

Table 3: The effect of tree size of ground truth tree. No noise in data, training size = 100.

Training set size	Method	Train Acc (%)	Test Acc (%)	Tree size	Depth
					Maximum	Average	Expected


100	CART-depth-2 CART-size-4 ConTree-2 HDT Ground Truth	89.76 (5.11) 97.62 (2.51) 93.52 (3.53) 100 (0.00) 100 (0.00)	75.46 (15.70) 80.26 (16.80) 78.62 (16.14) 84.38 (19.27) 100 (0.00)	2.88 (0.32) 4.00 (0.00) 3.00 (0.00) 2.00 (0.00) 0.00 (0.00)	2.00 (0.00) 3.92 (0.69) 2.00 (0.00) 2.00 (0.00) 2.00 (0.00)	1.96 (0.11) 3.01 (0.30) 2.00 (0.00) 1.67 (0.00) 1.67 (0.00)	1.96 (0.12) 2.52 (0.33) 2.00 (0.00) 1.66 (0.25) 1.70 (0.25)
200	CART-depth-2 CART-size-4 ConTree-2 HDT Ground Truth	89.00 (4.49) 94.49 (3.02) 92.87 (3.38) 99.94 (0.16) 100 (0.00)	84.62 (5.23) 89.57 (4.04) 88.51 (3.99) 97.97 (1.01) 100 (0.00)	2.92 (0.27) 4.00 (0.00) 3.00 (0.00) 2.00 (0.00) 2.00 (0.00)	2.00 (0.00) 3.26 (0.44) 2.00 (0.00) 2.00 (0.00) 2.00 (0.00)	1.97 (0.09) 2.50 (0.17) 2.00 (0.00) 1.67 (0.00) 1.67 (0.00)	1.98 (0.07) 2.17 (0.21) 2.00 (0.00) 1.71 (0.25) 1.70 (0.25)
400	CART-depth-2 CART-size-4 ConTree-2 HDT Ground Truth	87.45 (4.69) 92.58 (3.48) 91.44 (3.37) 99.85 (0.21) 100 (0.00)	84.62 (4.90) 89.35 (4.08) 88.78 (4.00) 98.98 (0.58) 100 (0.00)	2.98 (0.14) 4.00 (0.00) 3.00 (0.00) 2.00 (0.00) 2.00 (0.00)	2.00 (0.00) 3.24 (0.43) 2.00 (0.00) 2.00 (0.00) 2.00 (0.00)	1.99 (0.05) 2.53 (0.17) 2.00 (0.00) 1.67 (0.00) 1.67 (0.00)	1.99 (0.05) 2.15 (0.24) 2.00 (0.00) 1.71 (0.25) 1.70 (0.25)

Appendix

Table 4: The effect of training data size. Ground truth-tree size

K=2

Data dimension	Method	Train Acc (%)	Test Acc (%)	Tree size	Depth
					Maximum	Average	Expected


2	CART-depth-2 CART-size-4 ConTree-2 HDT Ground Truth	89.00 (4.49) 94.49 (3.02) 92.87 (3.38) 99.94 (0.16) 100 (0.00)	84.62 (5.23) 89.57 (4.04) 88.51 (3.99) 97.97 (1.01) 100 (0.00)	2.92 (0.27) 4.00 (0.00) 3.00 (0.00) 2.00 (0.00) 2.00 (0.00)	2.00 (0.00) 3.26 (0.44) 2.00 (0.00) 2.00 (0.00) 2.00 (0.00)	1.97 (0.09) 2.53 (0.17) 2.00 (0.00) 1.67 (0.00) 1.67 (0.00)	1.98 (0.07) 2.17 (0.21) 2.0 (0.00) 1.71 (0.25) 1.70 (0.25)
4	CART-depth-2 CART-size-4 ConTree-2 HDT Ground Truth	79.94 (4.53) 84.17 (4.41) 82.80 (4.16) 95.13 (1.38) 100 (0.00)	73.97 (4.74) 76.72 (4.48) 76.16 (4.82) 90.97 (2.55) 100 (0.00)	3.00 (0.00) 4.00 (0.00) 3.00 (0.00) 2.00 (0.00) 2.00 (0.00)	2.00 (0.00) 3.10 (0.3) 2.00 (0.00) 2.00 (0.00) 2.00 (0.00)	2.00 (0.00) 2.48 (0.13) 2.00 (0.00) 1.67 (0.00) 1.67 (0.00)	2.00 (0.00) 2.24 (0.18) 2.00 (0.00) 1.67 (0.13) 1.67 (0.12)
8	CART-depth-2 CART-size-4 ConTree-2 HDT Ground Truth	75.05 (5.72) 79.25 (5.66) 77.78 (5.36) 89.08 (4.26) 100 (0.00)	67.54 (7.08) 69.66 (6.75) 69.40 (6.37) 82.95 (5.70) 100 (0.00)	3.00 (0.00) 4.00 (0.00) 3.00 (0.00) 2.00 (0.00) 2.00 (0.00)	2.00 (0.00) 3.12 (0.325) 2.00 (0.00) 2.00 (0.00) 2.00 (0.00)	2.00 (0.00) 2.48 (0.14) 2.00 (0.00) 1.67 (0.00) 1.67 (0.00)	2.00 (0.00) 2.21 (0.22) 2.00 (0.00) 1.48 (0.12) 1.49 (0.13)

Appendix

Table 5: Effects of dimensionality. Training size = 100. No noise. Ground truth tress are size 2.

Noise level	Method	Train Acc (%)	Test Acc (%)	Tree size	Depth
					Maximum	Average	Expected


0	CART-depth-2 CART-size-4 ConTree-2 HDT Ground Truth	90.42 (4.61) 95.19 (3.11) 93.49 (3.60) 99.62 (0.68) 100 (0.00)	87.25 (5.20) 91.21 (3.94) 89.99 (3.71) 98.06 (1.21) 100 (0.00)	2.92 (0.27) 4.0 (0.00) 2.98 (0.04) 2.00 (0.00) 2.00 (0.00)	2.00 (0.00) 3.18 (0.38) 2.00 (0.00) 2.00 (0.00) 2.00 (0.00)	1.97 (0.09) 2.49 (0.16) 1.99 (0.05) 1.67 (0.00) 1.67 (0.00)	1.99 (0.03) 2.11 (0.23) 1.98 (0.11) 1.67 (0.28) 1.68 (0.28)
5	CART-depth-2 CART-size-4 ConTree-2 HDT Ground Truth	86.29 (4.48) 90.64 (3.07) 89.07 (3.45) 95.00 (0.20) 95.00 (0.00)	87.15 (4.89) 91.01 (3.67) 89.87 (3.47) 97.20 (1.40) 100 (0.00)	2.94 (0.24) 4.0 (0.00) 3.00 (0.00) 2.00 (0.00) 2.00 (0.00)	2.00 (0.00) 3.20 (0.40) 2.00 (0.00) 2.00 (0.00) 2.00 (0.00)	1.98 (0.08) 2.50 (0.16) 2.00 (0.00) 1.68 (0.00) 1.67 (0.00)	1.99 (0.02) 2.10 (0.24) 2.00 (0.00) 1.62 (0.29) 1.68 (0.28)
10	CART-depth-2 CART-size-4 ConTree-2 HDT Ground Truth	82.25 (3.78) 86.25 (2.67) 84.69 (3.09) 90.45 (0.49) 90.00 (0.00)	86.74 (5.36) 90.45 (4.07) 89.48 (3.96) 97.59 (1.21) 100 (0.00)	2.98 (0.14) 4.00 (0.00) 3.00 (0.00) 2.00 (0.00) 2.00 (0.00)	2.00 (0.00) 3.12 (0.32) 2.00 (0.00) 2.00 (0.00) 2.00 (0.00)	1.99 (0.05) 3.12 (0.32) 2.00 (0.00) 1.67 (0.00) 1.67 (0.00)	2.00 (0.01) 2.16 (0.26) 2.00 (0.00) 1.64 (0.30) 1.68 (0.28)

Appendix

Table 6: The effect of noise on labels. Training data size = 100. Ground truth trees are size 2.

Noise level	Method	Train Acc (%)	Test Acc (%)	Tree size	Depth
					Maximum	Average	Expected


0	CART-depth-2 CART-size-4 ConTree-2 HDT Ground Truth	90.29 (4.74) 94.20 (3.70) 92.73 (3.90) 99.88 (0.26) 100 (0.00)	87.23 (5.14) 90.32 (4.24) 89.55 (4.10) 98.08 (1.00) 100 (0.00)	2.96 (0.20) 4.00 (0.00) 3.00 (0.00) 2.00 (0.00) 2.00 (0.00)	2.00 (0.00) 3.2 (0.399) 2.00 (0.00) 2.00 (0.00) 2.00 (0.00)	1.99 (0.065) 2.51 (0.16) 2.00 (0.00) 1.67 (0.00) 1.67 (0.00)	1.99 (0.09) 2.09 (0.33) 2.00 (0.00) 1.63 (0.29) 1.63 (0.28)
5	CART-depth-2 CART-size-4 ConTree-2 HDT Ground Truth	90.16 (4.63) 93.98 (3.78) 92.62 (3.79) 99.62 (0.40) 99.59 (0.44)	87.16 (5.06) 90.32 (4.20) 89.50 (3.94) 98.10 (1.01) 100 (0.00)	2.98 (0.14) 4.00 (0.00) 3.00 (0.00) 2.00 (0.00) 2.00 (0.00)	2.00 (0.00) 3.24 (0.43) 2.00 (0.00) 2.00 (0.00) 2.00 (0.00)	1.99 (0.05) 2.53 (0.17) 2.00 (0.00) 1.67 (0.00) 1.67 (0.00)	2.00 (0.01) 2.05 (0.32) 2.00 (0.00) 1.64 (0.28) 1.65 (0.28)
10	CART-depth-2 CART-size-4 ConTree-2 HDT Ground Truth	90.30 (4.55) 93.98 (3.57) 92.50 (3.65) 99.07 (0.62) 98.81 (0.71)	87.36 (5.09) 90.30 (4.55) 89.38 (4.09) 97.50 (0.90) 100 (0.00)	2.96 (0.20) 4.00 (0.00) 3.00 (0.00) 2.00 (0.00) 2.00 (0.00)	2.00 (0.00) 3.28 (0.45) 2.00 (0.00) 2.00 (0.00) 2.00 (0.00)	1.99 (0.065) 2.54 (0.17) 2.00 (0.00) 1.67 (0.00) 1.67 (0.00)	1.99 (0.09) 2.03 (0.34) 2.00 (0.00) 1.58 (0.29) 1.65 (0.28)

Appendix

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

\mathit{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

\mathit{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

\mathit{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 Tree Learning

Decision tree learning builds hierarchical, rule-based models for prediction, balancing accuracy, computational cost, and interpretability.

See all 69 papers

Literati: Towards Anytime Optimal Shape Generalized Trees via AO*
Sep 8, 2026Nakul Upadhya, Eldan CohenTree Search Decision Tree Learning
Department of Mechanical and Industrial Engineering University of Toronto, Toronto, Canada
Search Strategies for Optimal Classification and Regression Trees
Jul 30, 2026Jacobus G. M. van der Linden, Mim van den Bos, Emir DemirovićDecision Tree Learning Classification
Delft University of Technology
ArborEnum: Decision Tree Rashomon Sets over Continuous Features
Aug 5, 2026Zakk Heile, Hayden McTavish, Margo Seltzer +1Decision Tree Learning
Department of Computer Science, Duke University, Durham, USA · Department of Computer Science, University of British Columbia, Vancouver, Canada

Sep 8, 2026J/K move · Enter open · S save

Literati: Towards Anytime Optimal Shape Generalized Trees via AO*

Nakul Upadhya, Eldan Cohen

Department of Mechanical and Industrial Engineering University of Toronto, Toronto, Canada

Tree Search Decision Tree Learning

Open paper AskPDF arXiv

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.

Abstract

Decision Tree Learning

Explore similar work

Literati: Towards Anytime Optimal Shape Generalized Trees via AO*

Search Strategies for Optimal Classification and Regression Trees

ArborEnum: Decision Tree Rashomon Sets over Continuous Features