A new framework lets researchers audit every viable decision tree a model could produce, not just the one it picked.
A team of researchers has published a method called Algebraic Decision Tree Counting (ADTC) that reframes decision tree analysis as a sum-of-products computation over an algebraic structure called a semiring. The approach unifies optimization, counting, and sampling into a single framework, and a dynamic programming algorithm keeps the computation tractable despite the hypothesis space growing doubly exponential with tree depth. Their software, emtrees, runs the method against real-world datasets to surface trade-offs across accuracy, size, and fairness simultaneously.
Explainable AI has a credibility problem: most auditing tools inspect the model you got, not the full landscape of models you could have gotten. ADTC is a rare attempt to close that gap formally, offering evidence-based model selection rather than post-hoc rationalization. In sensitive domains like lending or healthcare, knowing that a chosen tree is optimal across multiple criteria - not just accurate - is exactly the kind of proof regulators are starting to demand.
The complexity bound of O*(n^O(Delta)) in the number of features is honest about its limits: deep trees with many features will still strain compute. But for the shallow, interpretable trees that Explainable AI actually prizes, this looks like a practical tool, not just a theoretical exercise.