# On the Hardness of Approximating Distributions with Tractable Probabilistic Models

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

## Key facts

- Cited by 2 papers in the map (data through 14 Oct 2026).
- Builds on 17 of its 50 references that are in the map.
- First posted on arXiv 2 Jun 2025.

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

- [Attention Is All You Need](https://mlsanity.com/paper/1706.03762/) (2017)
- [Denoising Diffusion Probabilistic Models](https://mlsanity.com/paper/2006.11239/) (2020)
- [Generative Adversarial Networks](https://mlsanity.com/paper/2203.00667/) (2022)
- [Normalizing Flows for Probabilistic Modeling and Inference](https://mlsanity.com/paper/1912.02762/) (2019)
- [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)
- [Group Fairness by Probabilistic Modeling with Latent Fair Decisions](https://mlsanity.com/paper/2009.09031/) (2020)
- [Sum of Squares Circuits](https://mlsanity.com/paper/2408.11778/) (2024)
- [On the Expressive Efficiency of Sum Product Networks](https://mlsanity.com/paper/1411.7717/) (2014)
- [On Relaxing Determinism in Arithmetic Circuits](https://mlsanity.com/paper/1708.06846/) (2017)
- [Scalable Neural-Probabilistic Answer Set Programming](https://mlsanity.com/paper/2306.08397/) (2023)
- [On the Relationship Between Monotone and Squared Probabilistic Circuits](https://mlsanity.com/paper/2408.00876/) (2024)
- [Solving Marginal MAP Exactly by Probabilistic Circuit Transformations](https://mlsanity.com/paper/2111.04833/) (2021)
- [On the Relationship Between Probabilistic Circuits and Determinantal Point Processes](https://mlsanity.com/paper/2006.15233/) (2020)
- [Approximate Probabilistic Inference via Word-Level Counting](https://mlsanity.com/paper/1511.07663/) (2015)
- [On the Expressive Power of Tree-Structured Probabilistic Circuits](https://mlsanity.com/paper/2410.05465/) (2024)
- [Lower Bounds for Approximate Knowledge Compilation](https://mlsanity.com/paper/2011.13721/) (2020)

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

- [On the Approximation Complexity of Matrix Product Operator (MPO) Born Machines](https://mlsanity.com/paper/2605.11471/) (2026)
- [The Expressivity Boundary of Probabilistic Circuits: A Comparison with Large Language Models](https://mlsanity.com/paper/2605.12940/) (2026)

## Abstract (arXiv)

A fundamental challenge in probabilistic modeling is to balance expressivity and inference efficiency. Tractable probabilistic models (TPMs) aim to directly address this tradeoff by imposing constraints that guarantee efficient inference of certain queries while maintaining expressivity. In particular, probabilistic circuits (PCs) provide a unifying framework for many TPMs, by characterizing families of models as circuits satisfying different structural properties. Because the complexity of inference on PCs is a function of the circuit size, understanding the size requirements of different families of PCs is fundamental in mapping the trade-off between tractability and expressive efficiency. However, the study of expressive efficiency of circuits are often concerned with exact representations, which may not align with model learning, where we look to approximate the underlying data distribution closely by some distance measure. Moreover, due to hardness of inference tasks, exactly representing distributions while supporting tractable inference often incurs exponential size blow-ups. In this paper, we consider a natural, yet so far underexplored, question: can we avoid such size blow-up by allowing for some small approximation error? We study approximating distributions with probabilistic circuits with guarantees based on f-divergences, and analyze which inference queries remain well-approximated under this framework. We show that approximating an arbitrary distribution with bounded f-divergence is mathsfNP-hard for any model that can tractably compute marginals. In addition, we prove an exponential size gap for approximation between the class of decomposable PCs and that of decomposable and deterministic PCs.