# Tractable Boolean and Arithmetic Circuits

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

## Key facts

- Cited by 9 papers in the map (data through 14 Oct 2026).
- Builds on 36 of its 112 references that are in the map.
- First posted on arXiv 7 Feb 2022.

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

- [Neural Probabilistic Logic Programming in DeepProbLog](https://mlsanity.com/paper/1907.08194/) (2019)
- [A Semantic Loss Function for Deep Learning with Symbolic Knowledge](https://mlsanity.com/paper/1711.11157/) (2017)
- [Neurosymbolic AI: The 3rd Wave](https://mlsanity.com/paper/2012.05876/) (2020)
- [Neural-Symbolic Learning and Reasoning: A Survey and Interpretation](https://mlsanity.com/paper/1711.03902/) (2017)
- [A Symbolic Approach to Explaining Bayesian Network Classifiers](https://mlsanity.com/paper/1805.03364/) (2018)
- [Einsum Networks: Fast and Scalable Learning of Tractable Probabilistic Circuits](https://mlsanity.com/paper/2004.06231/) (2020)
- [On The Reasons Behind Decisions](https://mlsanity.com/paper/2002.09284/) (2020)
- [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)
- [From Statistical Relational to Neuro-Symbolic Artificial Intelligence](https://mlsanity.com/paper/2003.08316/) (2020)
- [Embedding Symbolic Knowledge into Deep Networks](https://mlsanity.com/paper/1909.01161/) (2019)
- [On the Latent Variable Interpretation in Sum-Product Networks](https://mlsanity.com/paper/1601.06180/) (2016)
- [On Tractable Representations of Binary Neural Networks](https://mlsanity.com/paper/2004.02082/) (2020)
- [Efficient Generation of Structured Objects with Constrained Adversarial Networks](https://mlsanity.com/paper/2007.13197/) (2020)
- [SPFlow: An Easy and Extensible Library for Deep Probabilistic Learning using Sum-Product Networks](https://mlsanity.com/paper/1901.03704/) (2019)
- [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)
- [SDDs are Exponentially More Succinct than OBDDs](https://mlsanity.com/paper/1601.00501/) (2016)
- [SPPL: Probabilistic Programming with Fast Exact Symbolic Inference](https://mlsanity.com/paper/2010.03485/) (2020)
- [On Quantifying Literals in Boolean Logic and Its Applications to Explainable AI](https://mlsanity.com/paper/2108.09876/) (2021)
- [Three Modern Roles for Logic in AI](https://mlsanity.com/paper/2004.08599/) (2020)
- [On Relaxing Determinism in Arithmetic Circuits](https://mlsanity.com/paper/1708.06846/) (2017)
- [Smoothing Structured Decomposable Circuits](https://mlsanity.com/paper/1906.00311/) (2019)
- [An Advance on Variable Elimination with Applications to Tensor-Based Computation](https://mlsanity.com/paper/2002.09320/) (2020)
- [Efficient Explanations for Knowledge Compilation Languages](https://mlsanity.com/paper/2107.01654/) (2021)
- [The Sum-Product Theorem: A Foundation for Learning Tractable Models](https://mlsanity.com/paper/1611.03553/) (2016)
- [Partition Function Estimation: A Quantitative Study](https://mlsanity.com/paper/2105.11132/) (2021)
- [Approximation Complexity of Maximum A Posteriori Inference in Sum-Product Networks](https://mlsanity.com/paper/1703.06045/) (2017)
- [On the Relative Expressiveness of Bayesian and Neural Networks](https://mlsanity.com/paper/1812.08957/) (2018)
- [A Compositional Atlas of Tractable Circuit Operations: From Simple Transformations to Complex Information-Theoretic Queries](https://mlsanity.com/paper/2102.06137/) (2021)

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

- [R2-Guard: Robust Reasoning Enabled LLM Guardrail via Knowledge-Enhanced Logical Reasoning](https://mlsanity.com/paper/2407.05557/) (2024)
- [KLay: Accelerating Arithmetic Circuits for Neurosymbolic AI](https://mlsanity.com/paper/2410.11415/) (2024)
- [COLEP: Certifiably Robust Learning-Reasoning Conformal Prediction via Probabilistic Circuits](https://mlsanity.com/paper/2403.11348/) (2024)
- [On the Complexity of Counterfactual Reasoning](https://mlsanity.com/paper/2211.13447/) (2022)
- [Causal Unit Selection using Tractable Arithmetic Circuits](https://mlsanity.com/paper/2404.06681/) (2024)
- [Tractable Bounding of Counterfactual Queries by Knowledge Compilation](https://mlsanity.com/paper/2310.03352/) (2023)
- [Constrained Identifiability of Causal Effects](https://mlsanity.com/paper/2412.02869/) (2024)
- [Logical Guidance for the Exact Composition of Diffusion Models](https://mlsanity.com/paper/2602.05549/) (2026)
- [Causal Neural Probabilistic Circuits](https://mlsanity.com/paper/2603.01372/) (2026)

## Abstract (arXiv)

Tractable Boolean and arithmetic circuits have been studied extensively in AI for over two decades now. These circuits were initially proposed as "compiled objects," meant to facilitate logical and probabilistic reasoning, as they permit various types of inference to be performed in linear-time and a feed-forward fashion like neural networks. In more recent years, the role of tractable circuits has significantly expanded as they became a computational and semantical backbone for some approaches that aim to integrate knowledge, reasoning and learning. In this article, we review the foundations of tractable circuits and some associated milestones, while focusing on their core properties and techniques that make them particularly useful for the broad aims of neuro-symbolic AI.