# A Compositional Atlas for Algebraic Circuits

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

## Key facts

- Cited by 10 papers in the map (data through 14 Oct 2026).
- Builds on 25 of its 59 references that are in the map.
- First posted on arXiv 7 Dec 2024.

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

- [Neural Probabilistic Logic Programming in DeepProbLog](https://mlsanity.com/paper/1907.08194/) (2019)
- [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)
- [On the Tractability of SHAP Explanations](https://mlsanity.com/paper/2009.08634/) (2020)
- [NeurASP: Embracing Neural Networks into Answer Set Programming](https://mlsanity.com/paper/2307.07700/) (2023)
- [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)
- [Scaling Up Probabilistic Circuits by Latent Variable Distillation](https://mlsanity.com/paper/2210.04398/) (2022)
- [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)
- [SPPL: Probabilistic Programming with Fast Exact Symbolic Inference](https://mlsanity.com/paper/2010.03485/) (2020)
- [Tractable Uncertainty for Structure Learning](https://mlsanity.com/paper/2204.14170/) (2022)
- [FAQ: Questions Asked Frequently](https://mlsanity.com/paper/1504.04044/) (2015)
- [Polynomial Semantics of Tractable Probabilistic Circuits](https://mlsanity.com/paper/2402.09085/) (2024)
- [Solving Marginal MAP Exactly by Probabilistic Circuit Transformations](https://mlsanity.com/paper/2111.04833/) (2021)
- [Compositional Probabilistic and Causal Inference using Tractable Circuit Models](https://mlsanity.com/paper/2304.08278/) (2023)
- [On the Semantics and Complexity of Probabilistic Logic Programs](https://mlsanity.com/paper/1701.09000/) (2017)
- [Restructuring Tractable Probabilistic Circuits](https://mlsanity.com/paper/2411.12256/) (2024)
- [AND/OR Multi-Valued Decision Diagrams (AOMDDs) for Graphical Models](https://mlsanity.com/paper/1401.3448/) (2014)
- [Solving #SAT and Bayesian Inference with Backtracking Search](https://mlsanity.com/paper/1401.3458/) (2014)
- [Efficient Knowledge Compilation Beyond Weighted Model Counting](https://mlsanity.com/paper/2205.07496/) (2022)
- [smProbLog: Stable Model Semantics in ProbLog for Probabilistic Argumentation](https://mlsanity.com/paper/2304.00879/) (2023)
- [Causal Unit Selection using Tractable Arithmetic Circuits](https://mlsanity.com/paper/2404.06681/) (2024)
- [A Circus of Circuits: Connections Between Decision Diagrams, Circuits, and Automata](https://mlsanity.com/paper/2404.09674/) (2024)
- [Tractable Circuits in Database Theory](https://mlsanity.com/paper/2407.01127/) (2024)

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

- [Scaling Probabilistic Circuits via Monarch Matrices](https://mlsanity.com/paper/2506.12383/) (2025)
- [The DeepLog Neurosymbolic Machine](https://mlsanity.com/paper/2508.13697/) (2025)
- [How to Square Tensor Networks and Circuits Without Squaring Them](https://mlsanity.com/paper/2512.17090/) (2025)
- [Every Feedforward Neural Network Definable in an o-Minimal Structure Has Finite Sample Complexity](https://mlsanity.com/paper/2605.07097/) (2026)
- [DeepLog: A Software Framework for Modular Neurosymbolic AI](https://mlsanity.com/paper/2605.10279/) (2026)
- [Probabilistic Graph Circuits: Deep Generative Models for Tractable Probabilistic Inference over Graphs](https://mlsanity.com/paper/2503.12162/) (2025)
- [Approximate Bayesian Inference via Bitstring Representations](https://mlsanity.com/paper/2508.13598/) (2025)
- [ExplainFuzz: Explainable and Constraint-Conditioned Test Generation with Probabilistic Circuits](https://mlsanity.com/paper/2604.06559/) (2026)
- [Learning Tractable Distributions Of Language Model Continuations](https://mlsanity.com/paper/2511.16054/) (2025)
- [Variance Computation for Weighted Model Counting with Knowledge Compilation Approach](https://mlsanity.com/paper/2601.03523/) (2026)

## Abstract (arXiv)

Circuits based on sum-product structure have become a ubiquitous representation to compactly encode knowledge, from Boolean functions to probability distributions. By imposing constraints on the structure of such circuits, certain inference queries become tractable, such as model counting and most probable configuration. Recent works have explored analyzing probabilistic and causal inference queries as compositions of basic operators to derive tractability conditions. In this paper, we take an algebraic perspective for compositional inference, and show that a large class of queries - including marginal MAP, probabilistic answer set programming inference, and causal backdoor adjustment - correspond to a combination of basic operators over semirings: aggregation, product, and elementwise mapping. Using this framework, we uncover simple and general sufficient conditions for tractable composition of these operators, in terms of circuit properties (e.g., marginal determinism, compatibility) and conditions on the elementwise mappings. Applying our analysis, we derive novel tractability conditions for many such compositional queries. Our results unify tractability conditions for existing problems on circuits, while providing a blueprint for analysing novel compositional inference queries.