# Optimal hypersurface decision trees

arXiv: https://arxiv.org/abs/2509.12057 · HTML: https://mlsanity.com/paper/2509.12057/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 9 of its 27 references that are in the map.
- First posted on arXiv 15 Sep 2025.

## Builds on (most cited first, 9 of 9)

- [Optimal Sparse Decision Trees](https://mlsanity.com/paper/1904.12847/) (2019)
- [Generalized and Scalable Optimal Sparse Decision Trees](https://mlsanity.com/paper/2006.08690/) (2020)
- [MurTree: Optimal Classification Trees via Dynamic Programming and Search](https://mlsanity.com/paper/2007.12652/) (2020)
- [Quant-BnB: A Scalable Branch-and-Bound Method for Optimal Decision Trees with Continuous Features](https://mlsanity.com/paper/2206.11844/) (2022)
- [Optimal Sparse Regression Trees](https://mlsanity.com/paper/2211.14980/) (2022)
- [Optimal Classification Trees for Continuous Feature Data Using Dynamic Programming with Branch-and-Bound](https://mlsanity.com/paper/2501.07903/) (2025)
- [Proper decision trees: An axiomatic framework for solving optimal decision tree problems with arbitrary splitting rules](https://mlsanity.com/paper/2503.01455/) (2025)
- [Functional design of efficient and parallelizable combinatorial generators using convolution](https://mlsanity.com/paper/2507.03980/) (2025)
- [Foundational theory for optimal decision tree problems. I. Algorithmic and geometric foundations](https://mlsanity.com/paper/2509.11226/) (2025)

## Abstract (arXiv)

The study of optimal decision trees has gained increasing attention in recent years; however, despite substantial progress, it still suffers from two major challenges: First, trees constructed by existing optimal decision tree (ODT) algorithms have limited expressivity, as they are typically restricted to axis-parallel splits or binary features. Second, these algorithms generally do not scale well to large datasets. These two challenges are intertwined: decision trees with more expressive splitting rules incur significantly higher combinatorial complexity, making the ODT problem even more difficult to solve when using complex splits. Building on He and Little's proper decision tree framework, we propose the first algorithm for solving the optimal hypersurface decision tree problem with time complexity Oleft(K!× NDG+Gright), where G is a variable depends on both K (tree size), M (polynomial degree of hypersurface) and D (data dimension). To the best of our knowledge, no known algorithm is capable of producing decision trees with hypersurface splits. Moreover, the proposed algorithm is inherently amenable to vectorization, enabling efficient parallelization. Its generic design pattern also allows it to be used to accelerate other ODT variants, such as axis-parallel decision trees. Furthermore, we identify an effective pruning strategy for the optimal hypersurface decision tree problem, which enables our algorithm to run significantly faster than the worst-case upper bound, together with an incremental procedure that reduces the cost of checking the feasibility of a single configuration from quadratic to linear time.