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

Luca Pascal Staus, Christian Komusiewicz, Frank Sommer, Manuel Sorge

Overview

Researchers have introduced Witty, a high-performance solver designed to find the smallest possible decision tree that perfectly classifies a given dataset. By optimizing the "witness-tree" algorithmic paradigm, Witty achieves a massive 32-fold speedup over current state-of-the-art solvers like MurTree. It is particularly effective for datasets with many feature values, a scenario where previous methods often struggled.

The Challenge of Minimum-Size Decision Trees

Decision trees are highly valued for their interpretability. However, to remain interpretable and generalize well to unseen data, these trees must be compact. Finding the absolute smallest tree that correctly classifies every point in a training set—known as the Minimum-Size Decision Tree (MSDT) problem—is NP-hard.

Existing optimal solvers typically rely on SAT-based encodings or Dynamic Programming. These methods often require "binarizing" data (converting all features into binary yes/no questions), which can lead to a combinatorial explosion in complexity. Witty addresses these scalability issues by avoiding mandatory binarization and utilizing a more flexible search strategy.

The Witness-Tree Paradigm

Witty is built on the witness-tree paradigm. Unlike traditional top-down heuristics (such as CART), this approach starts with a single leaf and iteratively refines it. When the current tree misclassifies an example (a "dirty" example), that example becomes a "witness." The algorithm then branches to find a new cut that separates this witness, ensuring all future refinements maintain correct classification for that witness.

The witness-tree refinement process, showing iterative steps (a-d) to resolve misclassified examples.

To make this search efficient, Witty incorporates several key optimizations:

  • Data Reduction Rules: Simplifying the dataset by removing redundant features or examples before the search begins.
  • Dirty Example Priority: A heuristic that selects which misclassified example to fix first to minimize the search space.
  • Advanced Lower Bounds: Using Set Cover logic to prune hopeless branches early.
  • Subset Constraints and Caching: Novel techniques to skip redundant thresholds and reuse lower bounds for specific data subsets.

Performance and Key Results

The researchers evaluated Witty using 700 instances derived from the Penn Machine Learning Benchmarks (PMLB). Witty significantly outperformed previous state-of-the-art tools:

  • Vs. MurTree: Witty achieved a 32-fold mean speedup and was particularly dominant on datasets with high-cardinality features.
  • Vs. SAT-based Solvers: Witty was approximately 61 times faster than leading SAT implementations.
  • Solving Capacity: Witty solved 388 out of 700 test instances, surpassing MurTree (371) and SAT-based methods.
Percentage of solved instances over time, demonstrating Witty's superior performance and scalability compared to MurTree and basic implementations.

The combination of these optimizations resulted in a 324-fold speedup compared to a naive implementation of the witness-tree algorithm.

Limitations and Future Outlook

Witty currently focuses on perfect classification for binary problems, meaning it finds trees with 100% accuracy on training data. While this is ideal for certain logic-based tasks, real-world data is often noisy. Future work aims to adapt Witty to handle misclassification tolerances, multi-class data, and different optimization objectives, such as minimizing tree depth rather than total node count. Despite these current limits, Witty represents a significant leap in making optimal decision tree induction practical for real-world datasets.

Summary updated

Abstract

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 $\mathbb{R}^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.
BibTeX
@inproceedings{staus2025witty,
  author = {Luca Pascal Staus and Christian Komusiewicz and Frank Sommer and Manuel Sorge},
  title = {{Witty: An Efficient Solver for Computing Minimum-Size Decision Trees}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {2025},
  doi = {10.1609/aaai.v39i19.34268},
}
Figure