# Algebraic Model Counting for Global Analysis of Optimal Decision Trees

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

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 8 of its 33 references that are in the map.
- First posted on arXiv 2 Jul 2026.

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

- [Equality of Opportunity in Supervised Learning](https://mlsanity.com/paper/1610.02413/) (2016)
- [Predictive Multiplicity in Classification](https://mlsanity.com/paper/1909.06677/) (2019)
- [Generalized and Scalable Optimal Sparse Decision Trees](https://mlsanity.com/paper/2006.08690/) (2020)
- [Exploring the Whole Rashomon Set of Sparse Decision Trees](https://mlsanity.com/paper/2209.08040/) (2022)
- [Optimal Decision Trees for Nonlinear Metrics](https://mlsanity.com/paper/2009.06921/) (2020)
- [Computing the Collection of Good Models for Rule Lists](https://mlsanity.com/paper/2204.11285/) (2022)
- [Enumeration of Distinct Support Vectors for Interactive Decision Making](https://mlsanity.com/paper/1906.01876/) (2019)
- [Fagin's Theorem for Semiring Turing Machines](https://mlsanity.com/paper/2507.18375/) (2025)

## Abstract (arXiv)

Ensuring model reliability in Explainable AI requires a global assessment of the hypothesis space. We propose a formal framework for the exhaustive analysis of optimal and near-optimal decision trees, called Algebraic Decision Tree Counting (ADTC). Inspired by Algebraic Model Counting (AMC) in knowledge representation, ADTC reformulates diverse analytical tasks, such as optimization, counting, and sampling, into a unified sum-of-products computation over a semiring R. While the hypothesis space of decision trees is doubly exponential with respect to the maximum depth Delta, our dynamic programming algorithm achieves O^*(nO(Delta)) time complexity in the number of features n, where O^* suppresses polynomial factors. To handle complex constraints consisting of multiple tree metrics, we introduce model behavior tensors that aggregate semiring values via convolution products over a tensor semiring. This algebraic approach efficiently constructs a model profile that captures the global landscape and trade-offs between criteria such as accuracy, size, and fairness. We demonstrate the utility of our software, emtrees, on real-world datasets, illustrating how ADTC facilitates evidence-based model selection in sensitive domains.