# On the Expressive Efficiency of Sum Product Networks

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

## Key facts

- Cited by 16 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 27 Nov 2014.

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

- [Subtractive Mixture Models via Squaring: Representation and Learning](https://mlsanity.com/paper/2310.00724/) (2023)
- [Probabilistic Generating Circuits](https://mlsanity.com/paper/2102.09768/) (2021)
- [What is the Relationship between Tensor Factorizations and Circuits (and How Can We Exploit it)?](https://mlsanity.com/paper/2409.07953/) (2024)
- [Sum of Squares Circuits](https://mlsanity.com/paper/2408.11778/) (2024)
- [On the Relationship Between Monotone and Squared Probabilistic Circuits](https://mlsanity.com/paper/2408.00876/) (2024)
- [Polynomial Semantics of Tractable Probabilistic Circuits](https://mlsanity.com/paper/2402.09085/) (2024)
- [Probabilistic Neural Circuits](https://mlsanity.com/paper/2403.06235/) (2024)
- [How to Square Tensor Networks and Circuits Without Squaring Them](https://mlsanity.com/paper/2512.17090/) (2025)
- [Probabilistic Generating Circuits -- Demystified](https://mlsanity.com/paper/2404.02912/) (2024)
- [Rethinking Probabilistic Circuit Parameter Learning](https://mlsanity.com/paper/2505.19982/) (2025)
- [On the Expressive Power of Tree-Structured Probabilistic Circuits](https://mlsanity.com/paper/2410.05465/) (2024)
- [On the Hardness of Approximating Distributions with Tractable Probabilistic Models](https://mlsanity.com/paper/2506.01281/) (2025)
- [Probabilistic Graph Circuits: Deep Generative Models for Tractable Probabilistic Inference over Graphs](https://mlsanity.com/paper/2503.12162/) (2025)
- [A Quantum Information Theoretic Approach to Tractable Probabilistic Models](https://mlsanity.com/paper/2506.01824/) (2025)
- [A Sobering Look at Tabular Data Generation via Probabilistic Circuits](https://mlsanity.com/paper/2603.23016/) (2026)
- [The Expressivity Boundary of Probabilistic Circuits: A Comparison with Large Language Models](https://mlsanity.com/paper/2605.12940/) (2026)

## Abstract (arXiv)

Sum Product Networks (SPNs) are a recently developed class of deep generative models which compute their associated unnormalized density functions using a special type of arithmetic circuit. When certain sufficient conditions, called the decomposability and completeness conditions (or "D&C" conditions), are imposed on the structure of these circuits, marginal densities and other useful quantities, which are typically intractable for other deep generative models, can be computed by what amounts to a single evaluation of the network (which is a property known as "validity"). However, the effect that the D&C conditions have on the capabilities of D&C SPNs is not well understood. In this work we analyze the D&C conditions, expose the various connections that D&C SPNs have with multilinear arithmetic circuits, and consider the question of how well they can capture various distributions as a function of their size and depth. Among our various contributions is a result which establishes the existence of a relatively simple distribution with fully tractable marginal densities which cannot be efficiently captured by D&C SPNs of any depth, but which can be efficiently captured by various other deep generative models. We also show that with each additional layer of depth permitted, the set of distributions which can be efficiently captured by D&C SPNs grows in size. This kind of "depth hierarchy" property has been widely conjectured to hold for various deep models, but has never been proven for any of them. Some of our other contributions include a new characterization of the D&C conditions as sufficient and necessary ones for a slightly strengthened notion of validity, and various state-machine characterizations of the types of computations that can be performed efficiently by D&C SPNs.