Research map / Probabilistic and scientific modeling / Variational and generative sampling
Sum of Squares Circuits
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Shows squared probabilistic circuits can be less expressive than monotonic ones and introduces sum-of-compatible-squares (SOCS) circuits that are exponentially more expressive than both, unifying several tractable models via a theoretical expressiveness hierarchy plus small-scale distribution estimation experiments.
Problem
Characterizing expressive efficiency among tractable probabilistic circuit classes: monotonic PCs, squared PCs with real or complex parameters, and related models like Born machines and PSD models.
Approach
Propose sum of compatible squares (SOCS) circuits, sums of squared structured-decomposable circuits that are pairwise compatible, and prove they are exponentially more expressive than both monotonic and squared PCs; show squared complex PCs reduce to SOCS with real parameters and that PSD models, Born machines and squared neural families fall in this class.
Key results
- On UCI datasets (except Gas), a monotonic PC achieves higher test log-likelihood than a single real squared PC, while complex squared PCs consistently outperform both.
- Complex squared PCs and their product with a monotonic PC (monotonic x complex squared) achieve lower test BPD than monotonic PCs and real squared PCs on MNIST, FashionMNIST and CelebA, with the product model using fewer parameters than a single complex squared PC.
- Theory: SOCS PCs of size O(d^3) can represent functions requiring exponential size for both monotonic and single squared structured-decomposable PCs; any structured-decomposable circuit is a difference of two SOCS PCs.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use a structured monotonic PC instead of a single real squared PC | Distribution estimation · Power, Hepmass, MiniBooNE, and Gas | test log-likelihood | Mixed |
| Use a single complex squared PC instead of a monotonic or real squared PC | Distribution estimation · Power, Gas, Hepmass, and MiniBooNE | test log-likelihood | Helped |
| Use SOCS PCs instead of monotonic PCs | Distribution estimation · Power, Gas, Hepmass, and MiniBooNE | test log-likelihood | Helped |
| Increase the number of squared components beyond 4 in a SOCS PC | SOCS PCs · Power, Gas, Hepmass, and MiniBooNE | test log-likelihood | No clear effect |
| Use complex rather than real parameters in a SOCS PC | SOCS PCs · Power, Gas, Hepmass, and MiniBooNE | test log-likelihood | No clear effect |
| Use a single complex squared PC instead of a monotonic or real squared PC | Image distribution estimation · MNIST, FashionMNIST, and CelebA | bits-per-dimension (BPD) | Helped |
| Multiply a monotonic PC by a complex squared PC | Product of monotonic and complex squared PCs (monotonic PC · complex squared PC) · Image distribution estimation | bits-per-dimension (BPD) | Helped |
| Use a real squared PC instead of a monotonic PC | Image distribution estimation · MNIST, FashionMNIST, and CelebA | bits-per-dimension (BPD) | No clear effect |
Limitations
- Open whether polysize monotonic or structured-decomposable PCs can be captured by polysize SOCS PCs.
- Relation between expressive products (monotonic x SOCS) and Inception PCs is left open.
- Experiments are limited to small-scale distribution estimation on UCI and image datasets.
Experimental setup
Datasets: UCI Power UCI Gas UCI Hepmass UCI MiniBooNE MNIST FashionMNIST CelebA
Benchmarks: UCI Power UCI Gas UCI Hepmass UCI MiniBooNE MNIST FashionMNIST CelebA
Metrics: average test log-likelihood bits-per-dimension
Baselines: monotonic structured-decomposable PCs single real squared PC single complex squared PC mixtures of monotonic PCs
Builds on: probabilistic circuits squared probabilistic circuits compatibility of circuits Born machines PSD models
Closest papers by meaning
- Subtractive Mixture Models via Squaring: Representation and Learning (ICLR 2024 · similarity 0.89)
- On the Hardness of Approximating Distributions with Tractable Probabilistic Models (NeurIPS 2025 · similarity 0.88)
- The Expressivity Boundary of Probabilistic Circuits: A Comparison with Large Language Models (NeurIPS 2026 · similarity 0.88)
- On the Relationship Between Monotone and Squared Probabilistic Circuits (AAAI 2025 · similarity 0.88)
- Scaling Probabilistic Circuits via Monarch Matrices (ICML 2025 · similarity 0.87)
- Scaling Continuous Latent Variable Models as Probabilistic Integral Circuits (NeurIPS 2024 · similarity 0.86)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.