# Witty: An Efficient Solver for Computing Minimum-Size Decision Trees

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

## Key facts

- Cited by 5 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 16 Dec 2024.

## Built on by (most cited first, 5 of 5)

- [Constrained and Robust Policy Synthesis with Satisfiability-Modulo-Probabilistic-Model-Checking](https://mlsanity.com/paper/2511.08078/) (2025)
- [Optimal Decision Tree Pruning Revisited: Algorithms and Complexity](https://mlsanity.com/paper/2503.03576/) (2025)
- [Learning Small Decision Trees with Few Outliers: A Parameterized Perspective](https://mlsanity.com/paper/2505.15648/) (2025)
- [Improving Decision Trees through the Lens of Parameterized Local Search](https://mlsanity.com/paper/2510.12726/) (2025)
- [RS-ORT: A Reduced-Space Branch-and-Bound Algorithm for Optimal Regression Trees](https://mlsanity.com/paper/2510.23901/) (2025)

## Abstract (arXiv)

Decision trees are a classic model for summarizing and classifying data. To enhance interpretability and generalization properties, it has been proposed to favor small decision trees. Accordingly, in the minimum-size decision tree training problem (MSDT), the input is a set of training examples in ℝd with class labels and we aim to find a decision tree that classifies all training examples correctly and has a minimum number of nodes. MSDT is NP-hard and therefore presumably not solvable in polynomial time. Nevertheless, Komusiewicz et al. [ICML '23] developed a promising algorithmic paradigm called witness trees which solves MSDT efficiently if the solution tree is small. In this work, we test this paradigm empirically. We provide an implementation, augment it with extensive heuristic improvements, and scrutinize it on standard benchmark instances. The augmentations achieve a mean 324-fold (median 84-fold) speedup over the naive implementation. Compared to the state of the art they achieve a mean 32-fold (median 7-fold) speedup over the dynamic programming based MurTree solver [Demirovi'c et al., J. Mach. Learn. Res. '22] and a mean 61-fold (median 25-fold) speedup over SAT-based implementations [Janota and Morgado, SAT '20]. As a theoretical result we obtain an improved worst-case running-time bound for MSDT.