# Polynomial Semantics of Tractable Probabilistic Circuits

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

## Key facts

- Cited by 12 papers in the map (data through 14 Oct 2026).
- Builds on 14 of its 39 references that are in the map.
- First posted on arXiv 14 Feb 2024.

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

- [Einsum Networks: Fast and Scalable Learning of Tractable Probabilistic Circuits](https://mlsanity.com/paper/2004.06231/) (2020)
- [A Differential Approach to Inference in Bayesian Networks](https://mlsanity.com/paper/1301.3847/) (2013)
- [Probabilistic Generating Circuits](https://mlsanity.com/paper/2102.09768/) (2021)
- [Lossless Compression with Probabilistic Circuits](https://mlsanity.com/paper/2111.11632/) (2021)
- [On Tractable Computation of Expected Predictions](https://mlsanity.com/paper/1910.02182/) (2019)
- [On the Expressive Efficiency of Sum Product Networks](https://mlsanity.com/paper/1411.7717/) (2014)
- [Smoothing Structured Decomposable Circuits](https://mlsanity.com/paper/1906.00311/) (2019)
- [On the Relationship Between Probabilistic Circuits and Determinantal Point Processes](https://mlsanity.com/paper/2006.15233/) (2020)
- [Scaling Integer Arithmetic in Probabilistic Programs](https://mlsanity.com/paper/2307.13837/) (2023)
- [Exact Bayesian Inference on Discrete Models via Probability Generating Functions: A Probabilistic Programming Approach](https://mlsanity.com/paper/2305.17058/) (2023)
- [Mixtures of All Trees](https://mlsanity.com/paper/2302.14202/) (2023)
- [Variable Elimination in the Fourier Domain](https://mlsanity.com/paper/1508.04032/) (2015)
- [Probabilistic Deep Learning using Random Sum-Product Networks](https://mlsanity.com/paper/1806.01910/) (2018)
- [Exact Probabilistic Inference Using Generating Functions](https://mlsanity.com/paper/2302.00513/) (2023)

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

- [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)
- [A Compositional Atlas for Algebraic Circuits](https://mlsanity.com/paper/2412.05481/) (2024)
- [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)
- [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)
- [The Limits of Tractable Marginalization](https://mlsanity.com/paper/2506.12020/) (2025)
- [Probabilistic Circuits for Cumulative Distribution Functions](https://mlsanity.com/paper/2408.04229/) (2024)
- [Approximate Bayesian Inference via Bitstring Representations](https://mlsanity.com/paper/2508.13598/) (2025)
- [Learning Tractable Distributions Of Language Model Continuations](https://mlsanity.com/paper/2511.16054/) (2025)

## Abstract (arXiv)

Probabilistic circuits compute multilinear polynomials that represent multivariate probability distributions. They are tractable models that support efficient marginal inference. However, various polynomial semantics have been considered in the literature (e.g., network polynomials, likelihood polynomials, generating functions, and Fourier transforms). The relationships between circuit representations of these polynomial encodings of distributions is largely unknown. In this paper, we prove that for distributions over binary variables, each of these probabilistic circuit models is equivalent in the sense that any circuit for one of them can be transformed into a circuit for any of the others with only a polynomial increase in size. They are therefore all tractable for marginal inference on the same class of distributions. Finally, we explore the natural extension of one such polynomial semantics, called probabilistic generating circuits, to categorical random variables, and establish that inference becomes #P-hard.