Optimal hypersurface decision trees

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 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\ge K$ and fixed-dimensional feasibility tests are treated as constant-cost operations, where $G=\left(\genfrac{}{}{0ex}{}{D+M}{M}\right)-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)$. Experiments show that, for small trees, our efficient vectorized solver can explore over one million candidate trees in a matter of seconds. On both synthetic and real-world datasets, more expressive tree models consistently achieve higher predictive accuracy than approximate and optimal axis-parallel decision-tree models, often with substantially smaller tree sizes. In the most pronounced case, our model improves test accuracy by nearly 30% points relative to the optimal ADT algorithm.