mlsanityData to 14 Oct 2026

Restructuring Tractable Probabilistic Circuits

arXiv 2411.12256 ↗First posted 19 Nov 2024cs.AI cs.LGcited by 7

Not on the map. Why?

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.

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

35 of 66 references.

References · 35

  1. 2020Einsum Networks: Fast and Scalable Learning of Tractable Probabilistic Circuitscited by 103
  2. 2022Semantic Probabilistic Layers for Neuro-Symbolic Learningcited by 103
  3. 2013A Differential Approach to Inference in Bayesian Networkscited by 93
  4. 2023Tractable Control for Autoregressive Language Generationcited by 65
  5. 2016On the Latent Variable Interpretation in Sum-Product Networkscited by 40
  6. 2021Tractable Regularization of Probabilistic Circuitscited by 39
  7. 2023Subtractive Mixture Models via Squaring: Representation and Learningcited by 39
  8. 2024Adaptable Logical Control for Large Language Modelscited by 30
  9. 2021Probabilistic Generating Circuitscited by 25
  10. 2016A Unified Approach for Learning the Parameters of Sum-Product Networkscited by 24
  11. 2020Strudel: Learning Structured-Decomposable Probabilistic Circuitscited by 24
  12. 2024Scaling Tractable Probabilistic Circuits: A Systems Perspectivecited by 23
23 more
  1. 2020Group Fairness by Probabilistic Modeling with Latent Fair Decisionscited by 22
  2. 2021Interventional Sum-Product Networks: Causal Inference with Tractable Probabilistic Modelscited by 22
  3. 2023Image Inpainting via Tractable Steering of Diffusion Modelscited by 22
  4. 2024What is the Relationship between Tensor Factorizations and Circuits (and How Can We Exploit it)?cited by 22
  5. 2024Where is the signal in tokenization space?cited by 21
  6. 2024Sum of Squares Circuitscited by 21
  7. 2020Probabilistic Circuits for Variational Inference in Discrete Graphical Modelscited by 20
  8. 2016SDDs are Exponentially More Succinct than OBDDscited by 19
  9. 2019On Tractable Computation of Expected Predictionscited by 19
  10. 2022Sparse Probabilistic Circuits via Pruning and Growingcited by 17
  11. 2024On the Relationship Between Monotone and Squared Probabilistic Circuitscited by 14
  12. 2015On the Relationship between Sum-Product Networks and Bayesian Networkscited by 13
  13. 2024Building Expressive and Tractable Probabilistic Generative Models: A Reviewcited by 12
  14. 2024Polynomial Semantics of Tractable Probabilistic Circuitscited by 12
  15. 2023Compositional Probabilistic and Causal Inference using Tractable Circuit Modelscited by 10
  16. 2017Approximation Complexity of Maximum A Posteriori Inference in Sum-Product Networkscited by 7
  17. 2023Bayesian Structure Scores for Probabilistic Circuitscited by 7
  18. 2019Sum-Product Network Decompilationcited by 5
  19. 2024Probabilistic Generating Circuits -- Demystifiedcited by 4
  20. 2017A Circuit-Based Approach to Efficient Enumerationcited by 3
  21. 2024A Circus of Circuits: Connections Between Decision Diagrams, Circuits, and Automatacited by 3
  22. 2024On the Expressive Power of Tree-Structured Probabilistic Circuitscited by 3
  23. 2022Marginal Inference queries in Hidden Markov Models under context-free grammar constraintscited by 2

Built on by

Cited by year (2026 to 14 Oct)

Citing papers per year: 2024: 1; 2025: 3; 2026: 3.

7 papers.

  1. 2024A Compositional Atlas for Algebraic Circuitscited by 10
  2. 2025Scaling Probabilistic Circuits via Monarch Matricescited by 9
  3. 2025How to Square Tensor Networks and Circuits Without Squaring Themcited by 5
  4. 2026Constrained Decoding for Diffusion Language Models via Efficient Inference over Finite Automatacited by 4
  5. 2025Learning Tractable Distributions Of Language Model Continuationscited by 0
  6. 2026A canonical generalization of OBDDcited by 0
  7. 2026Grab a Coffee: Future-Aware Guidance for Discrete Diffusion with Compiled Objectivescited by 0