# Restructuring Tractable Probabilistic Circuits

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

## Key facts

- Cited by 7 papers in the map (data through 14 Oct 2026).
- Builds on 35 of its 66 references that are in the map.
- First posted on arXiv 19 Nov 2024.

## Builds on (most cited first, 30 of 35)

- [Einsum Networks: Fast and Scalable Learning of Tractable Probabilistic Circuits](https://mlsanity.com/paper/2004.06231/) (2020)
- [Semantic Probabilistic Layers for Neuro-Symbolic Learning](https://mlsanity.com/paper/2206.00426/) (2022)
- [A Differential Approach to Inference in Bayesian Networks](https://mlsanity.com/paper/1301.3847/) (2013)
- [Tractable Control for Autoregressive Language Generation](https://mlsanity.com/paper/2304.07438/) (2023)
- [On the Latent Variable Interpretation in Sum-Product Networks](https://mlsanity.com/paper/1601.06180/) (2016)
- [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)
- [A Unified Approach for Learning the Parameters of Sum-Product Networks](https://mlsanity.com/paper/1601.00318/) (2016)
- [Strudel: Learning Structured-Decomposable Probabilistic Circuits](https://mlsanity.com/paper/2007.09331/) (2020)
- [Scaling Tractable Probabilistic Circuits: A Systems Perspective](https://mlsanity.com/paper/2406.00766/) (2024)
- [Group Fairness by Probabilistic Modeling with Latent Fair Decisions](https://mlsanity.com/paper/2009.09031/) (2020)
- [Interventional Sum-Product Networks: Causal Inference with Tractable Probabilistic Models](https://mlsanity.com/paper/2102.10440/) (2021)
- [Image Inpainting via Tractable Steering of Diffusion Models](https://mlsanity.com/paper/2401.03349/) (2023)
- [What is the Relationship between Tensor Factorizations and Circuits (and How Can We Exploit it)?](https://mlsanity.com/paper/2409.07953/) (2024)
- [Where is the signal in tokenization space?](https://mlsanity.com/paper/2408.08541/) (2024)
- [Sum of Squares Circuits](https://mlsanity.com/paper/2408.11778/) (2024)
- [Probabilistic Circuits for Variational Inference in Discrete Graphical Models](https://mlsanity.com/paper/2010.11446/) (2020)
- [SDDs are Exponentially More Succinct than OBDDs](https://mlsanity.com/paper/1601.00501/) (2016)
- [On Tractable Computation of Expected Predictions](https://mlsanity.com/paper/1910.02182/) (2019)
- [Sparse Probabilistic Circuits via Pruning and Growing](https://mlsanity.com/paper/2211.12551/) (2022)
- [On the Relationship Between Monotone and Squared Probabilistic Circuits](https://mlsanity.com/paper/2408.00876/) (2024)
- [On the Relationship between Sum-Product Networks and Bayesian Networks](https://mlsanity.com/paper/1501.01239/) (2015)
- [Building Expressive and Tractable Probabilistic Generative Models: A Review](https://mlsanity.com/paper/2402.00759/) (2024)
- [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)
- [Approximation Complexity of Maximum A Posteriori Inference in Sum-Product Networks](https://mlsanity.com/paper/1703.06045/) (2017)
- [Bayesian Structure Scores for Probabilistic Circuits](https://mlsanity.com/paper/2302.12130/) (2023)
- [Sum-Product Network Decompilation](https://mlsanity.com/paper/1912.10092/) (2019)

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

- [A Compositional Atlas for Algebraic Circuits](https://mlsanity.com/paper/2412.05481/) (2024)
- [Scaling Probabilistic Circuits via Monarch Matrices](https://mlsanity.com/paper/2506.12383/) (2025)
- [How to Square Tensor Networks and Circuits Without Squaring Them](https://mlsanity.com/paper/2512.17090/) (2025)
- [Constrained Decoding for Diffusion Language Models via Efficient Inference over Finite Automata](https://mlsanity.com/paper/2607.07026/) (2026)
- [Learning Tractable Distributions Of Language Model Continuations](https://mlsanity.com/paper/2511.16054/) (2025)
- [A canonical generalization of OBDD](https://mlsanity.com/paper/2604.05537/) (2026)
- [Grab a Coffee: Future-Aware Guidance for Discrete Diffusion with Compiled Objectives](https://mlsanity.com/paper/2609.35924/) (2026)

## Abstract (arXiv)

Probabilistic circuits (PCs) are a unifying representation for probabilistic models that support tractable inference. Numerous applications of PCs like controllable text generation depend on the ability to efficiently multiply two circuits. Existing multiplication algorithms require that the circuits respect the same structure, i.e. variable scopes decomposes according to the same vtree. In this work, we propose and study the task of restructuring structured(-decomposable) PCs, that is, transforming a structured PC such that it conforms to a target vtree. We propose a generic approach for this problem and show that it leads to novel polynomial-time algorithms for multiplying circuits respecting different vtrees, as well as a practical depth-reduction algorithm that preserves structured decomposibility. Our work opens up new avenues for tractable PC inference, suggesting the possibility of training with less restrictive PC structures while enabling efficient inference by changing their structures at inference time.