# Smoothing Structured Decomposable Circuits

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

## Key facts

- Cited by 14 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 1 Jun 2019.

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

- [On the Complexity of SHAP-Score-Based Explanations: Tractability via Knowledge Compilation and Non-Approximability Results](https://mlsanity.com/paper/2104.08015/) (2021)
- [Probabilistic Generating Circuits](https://mlsanity.com/paper/2102.09768/) (2021)
- [Lossless Compression with Probabilistic Circuits](https://mlsanity.com/paper/2111.11632/) (2021)
- [Polynomial Semantics of Tractable Probabilistic Circuits](https://mlsanity.com/paper/2402.09085/) (2024)
- [Compositional Probabilistic and Causal Inference using Tractable Circuit Models](https://mlsanity.com/paper/2304.08278/) (2023)
- [Tractable Boolean and Arithmetic Circuits](https://mlsanity.com/paper/2202.02942/) (2022)
- [A Compositional Atlas of Tractable Circuit Operations: From Simple Transformations to Complex Information-Theoretic Queries](https://mlsanity.com/paper/2102.06137/) (2021)
- [Probabilistic Generating Circuits -- Demystified](https://mlsanity.com/paper/2404.02912/) (2024)
- [Efficient Computation of Shap Explanation Scores for Neural Network Classifiers via Knowledge Compilation](https://mlsanity.com/paper/2303.06516/) (2023)
- [GraphSPNs: Sum-Product Networks Benefit From Canonical Orderings](https://mlsanity.com/paper/2408.09451/) (2024)
- [Pseudo Polynomial-Time Top-k Algorithms for d-DNNF Circuits](https://mlsanity.com/paper/2202.05938/) (2022)
- [The Gradient of Algebraic Model Counting](https://mlsanity.com/paper/2502.18406/) (2025)
- [Pruning Boolean d-DNNF Circuits Through Tseitin-Awareness](https://mlsanity.com/paper/2407.17951/) (2024)
- [Numerical Considerations in Weighted Model Counting](https://mlsanity.com/paper/2508.06264/) (2025)

## Abstract (arXiv)

We study the task of smoothing a circuit, i.e., ensuring that all children of a plus-gate mention the same variables. Circuits serve as the building blocks of state-of-the-art inference algorithms on discrete probabilistic graphical models and probabilistic programs. They are also important for discrete density estimation algorithms. Many of these tasks require the input circuit to be smooth. However, smoothing has not been studied in its own right yet, and only a trivial quadratic algorithm is known. This paper studies efficient smoothing for structured decomposable circuits. We propose a near-linear time algorithm for this task and explore lower bounds for smoothing decomposable circuits, using existing results on range-sum queries. Further, for the important case of All-Marginals, we show a more efficient linear-time algorithm. We validate experimentally the performance of our methods.