# Solving Marginal MAP Exactly by Probabilistic Circuit Transformations

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

## Key facts

- Cited by 11 papers in the map (data through 14 Oct 2026).
- Builds on 8 of its 30 references that are in the map.
- First posted on arXiv 8 Nov 2021.

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

- [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)
- [Tractable Regularization of Probabilistic Circuits](https://mlsanity.com/paper/2106.02264/) (2021)
- [Strudel: Learning Structured-Decomposable Probabilistic Circuits](https://mlsanity.com/paper/2007.09331/) (2020)
- [Leveraging Probabilistic Circuits for Nonparametric Multi-Output Regression](https://mlsanity.com/paper/2106.08687/) (2021)
- [Approximation Complexity of Maximum A Posteriori Inference in Sum-Product Networks](https://mlsanity.com/paper/1703.06045/) (2017)
- [Maximum A Posteriori Inference in Sum-Product Networks](https://mlsanity.com/paper/1708.04846/) (2017)
- [Tractable Computation of Expected Kernels](https://mlsanity.com/paper/2102.10562/) (2021)

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

- [Semantic Probabilistic Layers for Neuro-Symbolic Learning](https://mlsanity.com/paper/2206.00426/) (2022)
- [Building Expressive and Tractable Probabilistic Generative Models: A Review](https://mlsanity.com/paper/2402.00759/) (2024)
- [Compositional Probabilistic and Causal Inference using Tractable Circuit Models](https://mlsanity.com/paper/2304.08278/) (2023)
- [A Compositional Atlas for Algebraic Circuits](https://mlsanity.com/paper/2412.05481/) (2024)
- [Causal Unit Selection using Tractable Arithmetic Circuits](https://mlsanity.com/paper/2404.06681/) (2024)
- [Efficient and Reliable Probabilistic Interactive Learning with Structured Outputs](https://mlsanity.com/paper/2202.08566/) (2022)
- [Neural Network Approximators for Marginal MAP in Probabilistic Circuits](https://mlsanity.com/paper/2402.03621/) (2024)
- [On the Hardness of Approximating Distributions with Tractable Probabilistic Models](https://mlsanity.com/paper/2506.01281/) (2025)
- [Solving Satisfiability Modulo Counting for Symbolic and Statistical AI Integration With Provable Guarantees](https://mlsanity.com/paper/2309.08883/) (2023)
- [Solving Satisfiability Modulo Counting Exactly with Probabilistic Circuits](https://mlsanity.com/paper/2503.01009/) (2025)
- [Probably Approximately Correct Maximum A Posteriori Inference](https://mlsanity.com/paper/2601.16083/) (2026)

## Abstract (arXiv)

Probabilistic circuits (PCs) are a class of tractable probabilistic models that allow efficient, often linear-time, inference of queries such as marginals and most probable explanations (MPE). However, marginal MAP, which is central to many decision-making problems, remains a hard query for PCs unless they satisfy highly restrictive structural constraints. In this paper, we develop a pruning algorithm that removes parts of the PC that are irrelevant to a marginal MAP query, shrinking the PC while maintaining the correct solution. This pruning technique is so effective that we are able to build a marginal MAP solver based solely on iteratively transforming the circuit -- no search is required. We empirically demonstrate the efficacy of our approach on real-world datasets.