# A canonical generalization of OBDD

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

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 14 of its 44 references that are in the map.
- First posted on arXiv 7 Apr 2026.

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

- [Probabilistic Circuits for Variational Inference in Discrete Graphical Models](https://mlsanity.com/paper/2010.11446/) (2020)
- [SDDs are Exponentially More Succinct than OBDDs](https://mlsanity.com/paper/1601.00501/) (2016)
- [Compositional Probabilistic and Causal Inference using Tractable Circuit Models](https://mlsanity.com/paper/2304.08278/) (2023)
- [Connecting Knowledge Compilation Classes and Width Parameters](https://mlsanity.com/paper/1811.02944/) (2018)
- [Restructuring Tractable Probabilistic Circuits](https://mlsanity.com/paper/2411.12256/) (2024)
- [Lower Bounds for Exact Model Counting and Applications in Probabilistic Databases](https://mlsanity.com/paper/1309.6815/) (2013)
- [A Circuit-Based Approach to Efficient Enumeration](https://mlsanity.com/paper/1702.05589/) (2017)
- [Circuit Treewidth, Sentential Decision, and Query Compilation](https://mlsanity.com/paper/1701.04626/) (2017)
- [On the relation between structured d-DNNFs and SDDs](https://mlsanity.com/paper/1912.01430/) (2019)
- [Compilation and Fast Model Counting beyond CNF](https://mlsanity.com/paper/2502.00434/) (2025)
- [Solving MaxSAT and #SAT on structured CNF formulas](https://mlsanity.com/paper/1402.6485/) (2014)
- [No small nondeterministic read-once branching programs for CNFs of bounded treewidth](https://mlsanity.com/paper/1407.0491/) (2014)
- [An extended Knowledge Compilation Map for Conditional Preference Statements-based and Generalized Additive Utilities-based Languages](https://mlsanity.com/paper/2102.04107/) (2021)
- [Structured d-DNNF Is Not Closed Under Negation](https://mlsanity.com/paper/2402.04832/) (2024)

## Abstract (arXiv)

We introduce Tree Decision Diagrams (TDD) as a model for Boolean functions that generalizes OBDD. They can be seen as a restriction of structured d-DNNF; that is, d-DNNF that respect a vtree T. We show that TDDs enjoy the same tractability properties as OBDD, such as model counting, enumeration, conditioning, and apply, and are more succinct. In particular, we show that CNF formulas of treewidth k can be represented by TDDs of FPT size, which is known to be impossible for OBDD. We study the complexity of compiling CNF formulas into deterministic TDDs via bottom-up compilation and relate the complexity of this approach with the notion of factor width introduced by Bova and Szeider.