# The Limits of Tractable Marginalization

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

## Key facts

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

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

- [An Introduction to Variational Autoencoders](https://mlsanity.com/paper/1906.02691/) (2019)
- [Semantic Probabilistic Layers for Neuro-Symbolic Learning](https://mlsanity.com/paper/2206.00426/) (2022)
- [Tractable Control for Autoregressive Language Generation](https://mlsanity.com/paper/2304.07438/) (2023)
- [Tractable Regularization of Probabilistic Circuits](https://mlsanity.com/paper/2106.02264/) (2021)
- [Subtractive Mixture Models via Squaring: Representation and Learning](https://mlsanity.com/paper/2310.00724/) (2023)
- [Adaptable Logical Control for Large Language Models](https://mlsanity.com/paper/2406.13892/) (2024)
- [Probabilistic Generating Circuits](https://mlsanity.com/paper/2102.09768/) (2021)
- [Scaling Tractable Probabilistic Circuits: A Systems Perspective](https://mlsanity.com/paper/2406.00766/) (2024)
- [Image Inpainting via Tractable Steering of Diffusion Models](https://mlsanity.com/paper/2401.03349/) (2023)
- [Sum of Squares Circuits](https://mlsanity.com/paper/2408.11778/) (2024)
- [SPPL: Probabilistic Programming with Fast Exact Symbolic Inference](https://mlsanity.com/paper/2010.03485/) (2020)
- [Sampling from a k-DPP without looking at all items](https://mlsanity.com/paper/2006.16947/) (2020)
- [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)
- [Smoothing the gap between NP and ER](https://mlsanity.com/paper/1912.02278/) (2019)
- [On the Relationship Between Probabilistic Circuits and Determinantal Point Processes](https://mlsanity.com/paper/2006.15233/) (2020)
- [Characteristic Circuits](https://mlsanity.com/paper/2312.07790/) (2023)
- [Scaling Integer Arithmetic in Probabilistic Programs](https://mlsanity.com/paper/2307.13837/) (2023)
- [Generative Marginalization Models](https://mlsanity.com/paper/2310.12920/) (2023)
- [Probabilistic Generating Circuits -- Demystified](https://mlsanity.com/paper/2404.02912/) (2024)
- [Bit Blasting Probabilistic Programs](https://mlsanity.com/paper/2312.05706/) (2023)
- [Query DAGs: A Practical Paradigm for Implementing Belief Network Inference](https://mlsanity.com/paper/1408.1480/) (2014)
- [Probabilistic Circuits for Cumulative Distribution Functions](https://mlsanity.com/paper/2408.04229/) (2024)
- [Exact Soft Analytical Side-Channel Attacks using Tractable Circuits](https://mlsanity.com/paper/2501.13748/) (2025)

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

- [To Neuro-Symbolic Classification and Beyond by Compiling Description Logic Ontologies to Probabilistic Circuits](https://mlsanity.com/paper/2601.14894/) (2026)
- [Learning Tractable Distributions Of Language Model Continuations](https://mlsanity.com/paper/2511.16054/) (2025)

## Abstract (arXiv)

Marginalization -- summing a function over all assignments to a subset of its inputs -- is a fundamental computational problem with applications from probabilistic inference to formal verification. Despite its computational hardness in general, there exist many classes of functions (e.g., probabilistic models) for which marginalization remains tractable, and they can be commonly expressed by polynomial size arithmetic circuits computing multilinear polynomials. This raises the question, can all functions with polynomial time marginalization algorithms be succinctly expressed by such circuits? We give a negative answer, exhibiting simple functions with tractable marginalization yet no efficient representation by known models, assuming textsfFPneq#textsfP (an assumption implied by textsfP neq textsfNP). To this end, we identify a hierarchy of complexity classes corresponding to stronger forms of marginalization, all of which are efficiently computable on the known circuit models. We conclude with a completeness result, showing that whenever there is an efficient real RAM performing virtual evidence marginalization for a function, then there are small circuits for that function's multilinear representation.