# Sum of Squares Circuits

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

## Key facts

- Cited by 21 papers in the map (data through 14 Oct 2026).
- Builds on 30 of its 79 references that are in the map.
- First posted on arXiv 21 Aug 2024.

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

- [Adam: A Method for Stochastic Optimization](https://mlsanity.com/paper/1412.6980/) (2014)
- [Fashion-MNIST: a Novel Image Dataset for Benchmarking Machine Learning Algorithms](https://mlsanity.com/paper/1708.07747/) (2017)
- [Deep Learning Face Attributes in the Wild](https://mlsanity.com/paper/1411.7766/) (2014)
- [Complex Embeddings for Simple Link Prediction](https://mlsanity.com/paper/1606.06357/) (2016)
- [RotatE: Knowledge Graph Embedding by Relational Rotation in Complex Space](https://mlsanity.com/paper/1902.10197/) (2019)
- [Masked Autoregressive Flow for Density Estimation](https://mlsanity.com/paper/1705.07057/) (2017)
- [Unitary Evolution Recurrent Neural Networks](https://mlsanity.com/paper/1511.06464/) (2015)
- [Semantic Probabilistic Layers for Neuro-Symbolic Learning](https://mlsanity.com/paper/2206.00426/) (2022)
- [A Differential Approach to Inference in Bayesian Networks](https://mlsanity.com/paper/1301.3847/) (2013)
- [Unsupervised Generative Modeling Using Matrix Product States](https://mlsanity.com/paper/1709.01662/) (2017)
- [Tree Tensor Networks for Generative Modeling](https://mlsanity.com/paper/1901.02217/) (2019)
- [Not All Neuro-Symbolic Concepts Are Created Equal: Analysis and Mitigation of Reasoning Shortcuts](https://mlsanity.com/paper/2305.19951/) (2023)
- [Expressive power of tensor-network factorizations for probabilistic modeling, with applications from hidden Markov models to quantum machine learning](https://mlsanity.com/paper/1907.03741/) (2019)
- [Non-parametric Models for Non-negative Functions](https://mlsanity.com/paper/2007.03926/) (2020)
- [On the Latent Variable Interpretation in Sum-Product Networks](https://mlsanity.com/paper/1601.06180/) (2016)
- [Subtractive Mixture Models via Squaring: Representation and Learning](https://mlsanity.com/paper/2310.00724/) (2023)
- [BEARS Make Neuro-Symbolic Models Aware of their Reasoning Shortcuts](https://mlsanity.com/paper/2402.12240/) (2024)
- [Parameterized Machine Learning for High-Energy Physics](https://mlsanity.com/paper/1601.07913/) (2016)
- [Conditional Sum-Product Networks: Imposing Structure on Deep Probabilistic Architectures](https://mlsanity.com/paper/1905.08550/) (2019)
- [PSD Representations for Effective Probability Models](https://mlsanity.com/paper/2106.16116/) (2021)
- [How to Turn Your Knowledge Graph Embeddings into Generative Models](https://mlsanity.com/paper/2305.15944/) (2023)
- [On the Expressive Efficiency of Sum Product Networks](https://mlsanity.com/paper/1411.7717/) (2014)
- [On the Relationship Between Monotone and Squared Probabilistic Circuits](https://mlsanity.com/paper/2408.00876/) (2024)
- [A mathematical motivation for complex-valued convolutional networks](https://mlsanity.com/paper/1503.03438/) (2015)
- [Squared Neural Families: A New Class of Tractable Density Models](https://mlsanity.com/paper/2305.13552/) (2023)
- [Polynomial Semantics of Tractable Probabilistic Circuits](https://mlsanity.com/paper/2402.09085/) (2024)
- [Positive semidefinite rank](https://mlsanity.com/paper/1407.4095/) (2014)
- [Scaling Continuous Latent Variable Models as Probabilistic Integral Circuits](https://mlsanity.com/paper/2406.06494/) (2024)
- [Exact, Fast and Expressive Poisson Point Processes via Squared Neural Families](https://mlsanity.com/paper/2402.09608/) (2024)
- [The square root rank of the correlation polytope is exponential](https://mlsanity.com/paper/1411.6712/) (2014)

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

- [What is the Relationship between Tensor Factorizations and Circuits (and How Can We Exploit it)?](https://mlsanity.com/paper/2409.07953/) (2024)
- [A Probabilistic Neuro-symbolic Layer for Algebraic Constraint Satisfaction](https://mlsanity.com/paper/2503.19466/) (2025)
- [Scaling Probabilistic Circuits via Monarch Matrices](https://mlsanity.com/paper/2506.12383/) (2025)
- [Fast and Expressive Multi-Byte Prediction with Probabilistic Circuits](https://mlsanity.com/paper/2511.11346/) (2025)
- [Restructuring Tractable Probabilistic Circuits](https://mlsanity.com/paper/2411.12256/) (2024)
- [How to Square Tensor Networks and Circuits Without Squaring Them](https://mlsanity.com/paper/2512.17090/) (2025)
- [Rethinking Probabilistic Circuit Parameter Learning](https://mlsanity.com/paper/2505.19982/) (2025)
- [Tractable Representation Learning with Probabilistic Circuits](https://mlsanity.com/paper/2507.04385/) (2025)
- [Hellinger Multimodal Variational Autoencoders](https://mlsanity.com/paper/2601.06572/) (2026)
- [An Embarrassingly Simple Way to Optimize Orthogonal Matrices at Scale](https://mlsanity.com/paper/2602.14656/) (2026)
- [On the Hardness of Approximating Distributions with Tractable Probabilistic Models](https://mlsanity.com/paper/2506.01281/) (2025)
- [The Limits of Tractable Marginalization](https://mlsanity.com/paper/2506.12020/) (2025)
- [Squared families: Searching beyond regular probability models](https://mlsanity.com/paper/2503.21128/) (2025)
- [A Quantum Information Theoretic Approach to Tractable Probabilistic Models](https://mlsanity.com/paper/2506.01824/) (2025)
- [The Theory and Practice of MAP Inference over Non-Convex Constraints](https://mlsanity.com/paper/2602.08681/) (2026)
- [Geometry-Aware Probabilistic Circuits via Voronoi Tessellations](https://mlsanity.com/paper/2603.11946/) (2026)
- [A Sobering Look at Tabular Data Generation via Probabilistic Circuits](https://mlsanity.com/paper/2603.23016/) (2026)
- [How to Approximate Inference with Subtractive Mixture Models](https://mlsanity.com/paper/2604.16714/) (2026)
- [Scalable Expectation Estimation with Subtractive Mixture Models](https://mlsanity.com/paper/2503.21346/) (2025)
- [Learning Markov Processes as Sum-of-Square Forms for Analytical Belief Propagation](https://mlsanity.com/paper/2604.07525/) (2026)
- [On the Approximation Complexity of Matrix Product Operator (MPO) Born Machines](https://mlsanity.com/paper/2605.11471/) (2026)

## Abstract (arXiv)

Designing expressive generative models that support exact and efficient inference is a core question in probabilistic ML. Probabilistic circuits (PCs) offer a framework where this tractability-vs-expressiveness trade-off can be analyzed theoretically. Recently, squared PCs encoding subtractive mixtures via negative parameters have emerged as tractable models that can be exponentially more expressive than monotonic PCs, i.e., PCs with positive parameters only. In this paper, we provide a more precise theoretical characterization of the expressiveness relationships among these models. First, we prove that squared PCs can be less expressive than monotonic ones. Second, we formalize a novel class of PCs -- sum of squares PCs -- that can be exponentially more expressive than both squared and monotonic PCs. Around sum of squares PCs, we build an expressiveness hierarchy that allows us to precisely unify and separate different tractable model classes such as Born Machines and PSD models, and other recently introduced tractable probabilistic models by using complex parameters. Finally, we empirically show the effectiveness of sum of squares circuits in performing distribution estimation.