Interpretable Multiway-Split Trees

Decision tree optimization is fundamental to interpretable machine learning, yet most tree learning algorithms are restricted to binary splits. This restriction can produce unnecessarily deep trees when the underlying decision logic is naturally multi-valued. Multiway-split trees address this, but finding sparse yet accurate ones is more challenging, as the number of possible partitions at each node grows combinatorially with the number of feature bins. We introduce SPLINTER (SParse Lookahead for Interpretable N-way Trees by Eliminative Ranking), a dynamic programming and branch-and-bound-based framework that combines efficient candidate generation with pruning bounds to find sparse, accurate multiway-split trees. Our empirical results show that our methods produce trees that achieve higher accuracy at a greater decision sparsity (shorter path lengths) than greedy multiway and near-optimal binary-split tree baselines, while remaining practical to train. We further extend the framework to approximate the Rashomon set of near-optimal multiway-split trees, allowing users to inspect multiple sparse and accurate alternatives.