mlsanityData to 7 Oct 2026

Tractable Boolean and Arithmetic Circuits

arXiv 2202.02942 ↗First posted 7 Feb 2022cs.AI cs.CC cs.LGcited by 9

Not on the map. Why?

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.

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

Builds on

36 of 112 references.

References · 36

  1. 2019Neural Probabilistic Logic Programming in DeepProbLogcited by 389
  2. 2017A Semantic Loss Function for Deep Learning with Symbolic Knowledgecited by 267
  3. 2020Neurosymbolic AI: The 3rd Wavecited by 253
  4. 2017Neural-Symbolic Learning and Reasoning: A Survey and Interpretationcited by 195
  5. 2018A Symbolic Approach to Explaining Bayesian Network Classifierscited by 130
  6. 2020Einsum Networks: Fast and Scalable Learning of Tractable Probabilistic Circuitscited by 102
  7. 2020On The Reasons Behind Decisionscited by 99
  8. 2013A Differential Approach to Inference in Bayesian Networkscited by 93
  9. 2020On the Tractability of SHAP Explanationscited by 92
  10. 2020From Statistical Relational to Neuro-Symbolic Artificial Intelligencecited by 63
  11. 2019Embedding Symbolic Knowledge into Deep Networkscited by 49
  12. 2016On the Latent Variable Interpretation in Sum-Product Networkscited by 40
24 more
  1. 2020On Tractable Representations of Binary Neural Networkscited by 34
  2. 2020Efficient Generation of Structured Objects with Constrained Adversarial Networkscited by 27
  3. 2019SPFlow: An Easy and Extensible Library for Deep Probabilistic Learning using Sum-Product Networkscited by 26
  4. 2016A Unified Approach for Learning the Parameters of Sum-Product Networkscited by 24
  5. 2020Strudel: Learning Structured-Decomposable Probabilistic Circuitscited by 24
  6. 2016SDDs are Exponentially More Succinct than OBDDscited by 19
  7. 2020SPPL: Probabilistic Programming with Fast Exact Symbolic Inferencecited by 18
  8. 2021On Quantifying Literals in Boolean Logic and Its Applications to Explainable AIcited by 16
  9. 2020Three Modern Roles for Logic in AIcited by 15
  10. 2017On Relaxing Determinism in Arithmetic Circuitscited by 14
  11. 2019Smoothing Structured Decomposable Circuitscited by 14
  12. 2020An Advance on Variable Elimination with Applications to Tensor-Based Computationcited by 10
  13. 2021Efficient Explanations for Knowledge Compilation Languagescited by 9
  14. 2016The Sum-Product Theorem: A Foundation for Learning Tractable Modelscited by 8
  15. 2021Partition Function Estimation: A Quantitative Studycited by 8
  16. 2017Approximation Complexity of Maximum A Posteriori Inference in Sum-Product Networkscited by 7
  17. 2018On the Relative Expressiveness of Bayesian and Neural Networkscited by 7
  18. 2021A Compositional Atlas of Tractable Circuit Operations: From Simple Transformations to Complex Information-Theoretic Queriescited by 7
  19. 2018On the Relative Succinctness of Sentential Decision Diagramscited by 6
  20. 2019Knowledge Compilation for Boolean Functional Synthesiscited by 6
  21. 2013Lower Bounds for Exact Model Counting and Applications in Probabilistic Databasescited by 5
  22. 2015New Limits for Knowledge Compilation and Applications to Exact Model Countingcited by 5
  23. 2013Model Counting of Query Expressions: Limitations of Propositional Methodscited by 3
  24. 2021A Normal Form Characterization for Efficient Boolean Skolem Function Synthesiscited by 2

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2022: 1; 2023: 1; 2024: 5; 2025: 0; 2026: 2.

9 papers.

  1. 2024R2-Guard: Robust Reasoning Enabled LLM Guardrail via Knowledge-Enhanced Logical Reasoningcited by 41
  2. 2024KLay: Accelerating Arithmetic Circuits for Neurosymbolic AIcited by 16
  3. 2024COLEP: Certifiably Robust Learning-Reasoning Conformal Prediction via Probabilistic Circuitscited by 9
  4. 2022On the Complexity of Counterfactual Reasoningcited by 7
  5. 2024Causal Unit Selection using Tractable Arithmetic Circuitscited by 3
  6. 2023Tractable Bounding of Counterfactual Queries by Knowledge Compilationcited by 2
  7. 2024Constrained Identifiability of Causal Effectscited by 1
  8. 2026Logical Guidance for the Exact Composition of Diffusion Modelscited by 1
  9. 2026Causal Neural Probabilistic Circuitscited by 0