# On Relaxing Determinism in Arithmetic Circuits

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

## Key facts

- Cited by 14 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 22 Aug 2017.

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

- [R2-Guard: Robust Reasoning Enabled LLM Guardrail via Knowledge-Enhanced Logical Reasoning](https://mlsanity.com/paper/2407.05557/) (2024)
- [Tractable Regularization of Probabilistic Circuits](https://mlsanity.com/paper/2106.02264/) (2021)
- [Tractable Uncertainty for Structure Learning](https://mlsanity.com/paper/2204.14170/) (2022)
- [Causal Inference Using Tractable Circuits](https://mlsanity.com/paper/2202.02891/) (2022)
- [Compositional Probabilistic and Causal Inference using Tractable Circuit Models](https://mlsanity.com/paper/2304.08278/) (2023)
- [Tractable Boolean and Arithmetic Circuits](https://mlsanity.com/paper/2202.02942/) (2022)
- [COLEP: Certifiably Robust Learning-Reasoning Conformal Prediction via Probabilistic Circuits](https://mlsanity.com/paper/2403.11348/) (2024)
- [Provable Guarantees on the Robustness of Decision Rules to Causal Interventions](https://mlsanity.com/paper/2105.09108/) (2021)
- [Certifying Fairness of Probabilistic Circuits](https://mlsanity.com/paper/2212.02474/) (2022)
- [Causal Unit Selection using Tractable Arithmetic Circuits](https://mlsanity.com/paper/2404.06681/) (2024)
- [On the Hardness of Approximating Distributions with Tractable Probabilistic Models](https://mlsanity.com/paper/2506.01281/) (2025)
- [Explaining Deep Tractable Probabilistic Models: The sum-product network case](https://mlsanity.com/paper/2110.09778/) (2021)
- [Optimal Transport for Probabilistic Circuits](https://mlsanity.com/paper/2410.13061/) (2024)
- [Hardware-efficient tractable probabilistic inference for TinyML Neurosymbolic AI applications](https://mlsanity.com/paper/2507.05141/) (2025)

## Abstract (arXiv)

The past decade has seen a significant interest in learning tractable probabilistic representations. Arithmetic circuits (ACs) were among the first proposed tractable representations, with some subsequent representations being instances of ACs with weaker or stronger properties. In this paper, we provide a formal basis under which variants on ACs can be compared, and where the precise roles and semantics of their various properties can be made more transparent. This allows us to place some recent developments on ACs in a clearer perspective and to also derive new results for ACs. This includes an exponential separation between ACs with and without determinism; completeness and incompleteness results; and tractability results (or lack thereof) when computing most probable explanations (MPEs).