Probabilistic Circuits as Reasoning Machines in Artificial Intelligence (Part I)

Robert Peharz

Source-linked AI summary

Probabilistic Circuits as Reasoning Machines in Artificial Intelligence (Part I)

Robert Peharz

arXiv:2608.16565v1Aug 17, 2026cs.AIcs.LGmath.PR

TL;DR

Probabilistic inference is conceptually simple but generally computationally intractable. This thesis studies probabilistic circuits as structurally constrained models that recursively support tractable conditional reasoning, while reporting an implementation about five times slower than MLPs.

Problem
Probabilistic inference requires summations or integrations that generally scale exponentially with problem dimensionality, motivating computationally tractable alternatives.
Source: Simplicity · p. 14
Method
The thesis develops probabilistic circuits as hierarchical mixtures whose conditional distributions are recursively delegated through sum and product nodes.
Source: §5.1.2 · p. 62, §5.3 · p. 68
Results
A standard einsum implementation of probabilistic circuits was about 5 times slower than MLPs, with further optimization potentially narrowing the difference.
Source: §5.7.3 · p. 76
Takeaways & Limitations
Recursive conditioning makes probabilistic circuits a structured framework for expressing conditional distributions from tractable input distributions.
Source: §5.3 · p. 68
For continuous densities, most probable explanation may not match the outcome desired for real-valued state spaces, making decision theory relevant.
Source: §3.7 · p. 47

Abstract

from arXiv · show

This cumulative habilitation thesis studies probabilistic circuits (PCs) as a powerful and tractable framework for reasoning and learning under uncertainty in artificial intelligence (AI). It first advocates for probability as a core language for AI, emphasizing its connections to logic and information theory; the conceptual simplicity of probabilistic reasoning---based primarily on the sum and product rules; the parallels between probabilistic inference and human cognition; and the role of probability in optimal decision making. However, probability also faces significant computational challenges, as probabilistic inference is NP-hard in almost all probabilistic models. PCs address these challenges through structural constraints that ensure exact computation of a wide range of inference queries in polynomial time, such as marginals, conditionals, most probable explanations, expectations, and more advanced inference tasks. This thesis synthesizes a decade of research across foundations, algorithmic developments, and empirical validation of PCs. Key contributions highlighted in this work are foundational theory of PCs, Bayesian approaches for learning PCs, scalable implementations and integration with deep learning, hybrid models that combine PCs with intractable models, and connections with symbolic machine learning paradigms. This is the first part of my Habilitation Thesis. The second part is omitted, as it comprises the cumulative part of the thesis and has been published at various venues (see Chapter 5).

Probabilistic Reasoning and AI · Introduction

The thesis frames rational AI around knowledge representation, reasoning, and learning, and argues that probability is an excellent core language because it combines conceptual simplicity with uncertainty handling and links to logic, cognition, decision theory, and information theory. Probabilistic circuits address probability’s computational difficulty by structurally enabling exact, efficient, and flexible inference while trading off expressive efficiency.

1.1 What is AI (roughly)?

The thesis centers rational AI on knowledge representation, reasoning, and learning as its minimalist core notion.Reasoning transforms represented information into new insights, while learning incorporates information unavailable at design time.Source: §1.1 · pp. 12–13

Simplicity

Probabilistic reasoning reduces inference to cascades of the sum and product rules, which marginalize unknown facts and condition on observations to propagate uncertainty from evidence to predictions.This is conceptual simplicity, not computational simplicity: general inference can require exponentially scaling summations or integrations.Source: Simplicity · pp. 13–14

Decision Making; Qualitative Similarities to Common Sense Reasoning

Probability supports optimal decision making by defining actions through minimum expected loss under the relevant joint distribution.It also naturally models non-monotonic belief updates and explaining away, patterns associated with common-sense reasoning.Source: Decision Making · p. 14, Qualitative Similarities to Common… · p. 15

Bayesianism and Consistency with Logic

Probability extends classical logic with uncertainty, while Bayesian modelling unifies learning and reasoning through posterior inference over parameters given data.Under Cox’s theorem assumptions, probability is presented as the sound extension of logic to continuous plausibility values.Source: Bayesianism and Consistency with Logic · pp. 15–16

Information Theory

Information theory reinforces the probabilistic view by treating negative log probability as information content and uncertainty as lack of information.Because information states are agent-dependent, this perspective also supports a Bayesian interpretation of probabilistic reasoning.Source: Information Theory · p. 16

1.2 The Role of Probability

Probability is proposed as an excellent AI language because it offers conceptual simplicity, represents uncertainty, and connects reasoning with logic, human cognition, decision theory, and information theory.The thesis presents this as a working hypothesis rather than a claim that probability is computationally simple.Source: §1.2 · p. 13, Decision Making · p. 14, Bayesianism and Consistency with Logic · p. 15

1.3 Why Probabilistic Circuits?

Probabilistic models often represent domains accurately but make exact inference computationally hard, whereas neural networks typically make limited task-specific inference easy without supporting general joint-distribution queries.Predicting arbitrary feature subsets requires a model of the full joint distribution, for which inference is generally hard in deep generative models.Source: §1.3 · p. 17
Probabilistic circuits combine joint-distribution representation with exact, efficient inference by imposing structural constraints, consolidating prior tractable models as a common framework.These constraints preserve tractability but can reduce expressive efficiency, so PCs seek the best approximation under tractable-inference constraints.Source: §1.3 · pp. 17–18

Basic Probability Theory

This section develops probability as a rigorous calculus for reasoning under uncertainty, covering probability spaces, measures, core rules, conditioning, independence, and random-variable-based representations of distributions.

Basic Probability Theory

A probability space is the compact formal foundation of probabilistic AI, serving as an insurance that abstract methods remain mathematically sound.Any probabilistic argument should reduce to a probability space or establish its existence.Source: Basic Probability Theory · p. 19

2.1 Measurable Space

A measurable space consists of a non-empty sample space Ω and a sigma-algebra Σ that organizes events while remaining closed under logical set operations.Atomic events are individual ω ∈ Ω, whereas Σ provides a more macroscopic event structure and is closed under complements, countable unions, and intersections.Source: §2.1 · p. 20, §2.1.1 · pp. 21–22

2.1.1 Events are Sets

Events are subsets in the sigma-algebra, which may deliberately provide a macroscopic view that excludes some singleton atomic events.For a die, the sigma-algebra generated by prime and odd outcomes contains {1} and {2}, but not {3} or {4}.Source: §2.1.1 · p. 21

2.2 Probability Space

A probability space adds a probability measure P to (Ω,Σ), assigning values in [0,1] with total mass one and countable additivity over disjoint events.The resulting triplet (Ω,Σ,P) fully characterizes probability in mainstream mathematics.Source: §2.2 · p. 22

2.2.1 Why Sigma-Algebras?

Sigma-algebras are necessary because, on uncountable spaces, some subsets are non-measurable; they restrict probability to sets for which consistent measures can be defined.For real-valued domains, Borel sigma-algebras provide a standard choice generated by intervals.Source: §2.2.1 · pp. 23–24

2.3 Interpretations of Probability

Probability admits complementary interpretations as relative frequency, relaxed logic truth values or plausibility, and information content, without one being the uniquely correct interpretation.The negative logarithm maps probability to information content, measured in bits or nats, making probability and information content bijectively related.Source: §2.3 · pp. 25–26

2.4 Fundamental Laws of Probability

Probabilistic modelling represents domains and uncertainties with probability spaces, while reasoning relies on a few conceptually simple primitives, especially the sum and product rules.These rules are discussed at the distribution-function level but correspond to more fundamental laws of probability measures.Source: §2.4 · pp. 26–27

2.4.1 Law of Total Probability (The Sum Rule)

The sum rule computes P(B) by summing probabilities of B jointly occurring with the mutually exclusive and exhaustive events in a partition, thereby forgetting or accounting for unknown alternatives.It follows from countable additivity because the joint events B ∩ A_i partition B.Source: §2.4.1 · p. 27

2.4.2 Conditional Probability (The Product Rule)

Conditional probability updates a global probability model by rebasing it on the observed event B, with P(A|B) determined through the intersection A∩B and P(B).The conditional construction treats B as a new sample space, while events outside B receive probability zero when the original space is retained.Source: §2.4.2 · pp. 27–29

2.4.3 Bayes’ Rule (The Rule of Inverse Probability)

Bayes’ rule reverses conditional reasoning, making an accessible direction P(A|B) usable for the desired direction P(B|A) in inverse problems, although computation may remain difficult.The text identifies imaging, detection, and robotics as examples of inverse problems and notes that most Bayesian problems are numerically challenging.Source: §2.4.3 · pp. 29–30

2.4.4 (Conditional) Independence

Independence means that observing B does not change the probability of A, while conditional independence applies the same equivalent definitions within the probability space conditioned on C.For conditional independence, all probabilities in the independence definitions are conditioned on C, with P(C) > 0.Source: §2.4.4 · pp. 30–31

2.5 Random Variables

Random variables provide an interpretable interface to abstract probability spaces by measurably mapping uncertain sample-space outcomes into state spaces such as numbers, vectors, graphs, or functions.Measurability requires measurable domain and codomain spaces and measurable pre-images of codomain events.Source: §2.5 · pp. 31–32

2.5.1 Distribution of a Random Variable

A random variable induces a distribution PX on its state space by assigning each event the probability of its pre-image, thereby describing uncertainty about its values.The induced distribution is also called the law of X or the pushforward measure of P under X.Source: §2.5.1 · p. 32

2.5.2 Distribution Functions

Distribution functions describe random-variable uncertainty directly through PMFs for discrete states and PDFs for continuous variables, using sums or integrals respectively.PMFs cannot represent uncountable state spaces such as R or C, while densities are not unique because changes at countably many points do not affect integrals.Source: §2.5.2 · pp. 33–34

2.5.3 Multivariate Random Variables and Joint Distributions

Multivariate random variables represent multiple potentially correlated quantities through joint PMFs, PDFs, or hybrid distributions, all describing probability measures by summing or integrating over events.Hybrid distributions combine discrete and continuous variables, with the distinction among joint representations determined by their underlying counting, Lebesgue, or product measures.Source: §2.5.3 · pp. 34–36

Probabilistic Inference

This section presents probability as a foundation for representing knowledge and performing inference through marginalization, conditioning, and related operations. It develops expectations and most probable explanations as inference queries, and connects predictive distributions to task-dependent decisions through decision theory.

Probabilistic Inference

Probabilistic inference represents knowledge with distributions and centers on marginalization and conditioning, while expectations and optimization are important queries that are often computationally hard.Probabilistic circuits are introduced as a framework for computing these queries exactly and efficiently.Source: Probabilistic Inference · p. 37

3.1 Marginalization (The Sum Rule)

Marginalization integrates or sums over unknown variables to produce an exact reduced distribution over the retained variables, consistently regardless of elimination order.It is the sum rule and can be interpreted as reasoning while ignoring or accounting for unknown quantities.Source: §3.1 · pp. 38–39

3.2 Conditioning (The Product Rule)

Conditioning updates the distribution over remaining variables after observing evidence, using the joint distribution divided by the evidence marginal.For continuous variables, conditioning is well-defined when the marginal density is non-zero and continuous at the conditioning value.Source: §3.2 · pp. 39–40

3.3 The Chain Rule

Repeated application of the product rule yields the chain rule, factorizing a joint distribution into ordered marginals and conditionals for flexible multi-step reasoning.Any variable ordering is allowed, producing K! chain rules for a partition into K blocks; this underlies Bayesian networks and autoregressive distribution estimators.Source: §3.3 · pp. 42–43

3.4 Bayes Rule (Law of Inverse Probability)

Bayes rule reverses the direction of reasoning from observed data to latent quantities, combining a likelihood and prior to infer the posterior in inverse problems.It supports inference about latent parameters, hypotheses, or structures from observations.Source: §3.4 · p. 43

3.5 (Conditional) Independence

Independence means that learning one variable does not change another’s distribution, while conditional independence allows this relationship to depend on a third variable.The definitions are expressed through equivalent distributional conditions for all relevant values.Source: §3.5 · pp. 43–44

3.6 Expectations

Expectations provide a single-value decision from a distribution, but the average may be unrepresentative, especially for multimodal distributions.Exact conditional inference can incorporate observed measurements and missing-at-random variables, while retaining the full distribution preserves uncertainty.Source: §3.6 · p. 45
Expected transformations, moments, variances, and covariances summarize distributions as concrete values and support subsequent optimization and decision making.The law of the unconscious statistician computes E[g(X)] directly from the distribution of X, while covariance captures pairwise dependence in random vectors.Source: §3.6 · p. 46

3.7 Most Probable Explanation

The most probable explanation selects the state with maximal probability, but for continuous densities it may identify a narrow low-mass region rather than the most probable region overall.In the example, y*=9 has density approximately 0.8 but only about 0.1% of the probability mass, whereas the mode near −10 has density approximately 0.2 and accounts for 99.9%.Source: §3.7 · p. 47

3.8 Decision Theory

Decision theory chooses the value minimizing expected loss conditional on available evidence, making the assumptions about acceptable errors explicit.Under suitable loss specification, the rule is optimal for repeated decisions when the true conditional distribution is known and the expected loss can be computed exactly.Source: §3.8 · pp. 49–50
Squared-distance loss yields the distribution mean, while absolute-distance loss yields the median and is robust to extreme outliers.For the Gaussian-mixture example, the median is about −9.9975 and remains virtually unchanged even when the low-weight component mean moves to 9000 or farther.Source: §3.8 · p. 50
Prematurely replacing a predictive distribution with a single value discards uncertainty and can compromise downstream probabilistic reasoning, while loss design itself may be difficult and ethically sensitive.The ideal decision-theoretic guarantees require an adequate loss function, access to the true data-generating distribution, and exact computation; alternative rules can support risk-aware or set-valued predictions.Source: §3.8 · pp. 50–51

State of The Art

Probabilistic approaches became central in AI as uncertainty gained recognition, with graphical models providing an intuitive language for structure, assumptions, and tractable inference. However, general graphical-model inference is NP-hard, and autoregressive models retain difficult marginal and conditional computations despite flexible density modeling.

State of The Art

Probabilistic reasoning gained ground after uncertainty became recognized as essential for real-world AI, with Judea Pearl’s seminal book establishing it as a central approach.AI had previously been dominated by logic-based methods, while probability faced criticism over computational difficulty and perceived impracticality.Source: State of The Art · p. 53
Graphical models, especially Bayesian networks, remain a cornerstone and lingua franca of probabilistic modeling through visualized conditional-independence assumptions and connections to tractable inference and learning.Source: State of The Art · p. 53
Inference in graphical models is generally NP-hard, although bounded treewidth enables exact tractable inference.Most probabilistic machine learning systems can be mapped to graphical models that concisely express model structure and assumptions.Source: State of The Art · p. 53
Deep Autoregressive Models use the probability chain rule with shared neural networks and can represent any joint distribution in principle.They support sampling and density evaluation, but marginals, conditionals, and complex inference tasks remain challenging.Source: State of The Art · p. 53

46 State of The Art

Contemporary probabilistic models often prioritize expressive generation while relying on approximate or intractable inference. Probabilistic circuits instead explicitly prioritize tractable probabilistic reasoning.

Neural latent-variable models

VAEs use neural transformations of simple latent distributions to define infinite mixture models, while amortized encoders approximate posteriors through ELBO optimization.Exact inference is hard, so the encoder jointly improves the ELBO estimate and model parameters.Source: §46 · p. 54

Adversarial models

GANs train generators adversarially against discriminators, enabling realistic sampling but generally lacking density evaluation and tractable marginal or conditional inference.Their objective minimizes a divergence distinct from maximum likelihood.Source: §46 · p. 54

Invertible generative models

Normalizing Flows [49] provide exact density computation and sampling through bijective transformations, but marginals and conditionals remain challenging.They apply the change-of-variables formula to transformed simple distributions.Source: §46 · p. 54

Energy- and score-based models

Energy-based and score-based models offer flexible neural representations, yet density evaluation, sampling, marginals, and conditionals are typically intractable or require difficult-to-validate approximations.Score-Based Models combined with diffusion and Langevin dynamics represent the state of the art for image generation [61].Source: §46 · pp. 54–55

Other probabilistic frameworks

Gaussian Processes support tractable marginals and conditionals, but their cubic cost in data points motivates sparse inducing-point methods; probabilistic programming [69] generally uses approximate inference.Probabilistic programming expresses models as programs with random variables and commonly applies variational inference or Monte Carlo techniques.Source: §46 · p. 55

Motivation for probabilistic circuits

Across these approaches, expressivity often takes precedence over exact inference, whereas probabilistic circuits explicitly focus on tractability rather than assuming tractable models must underperform.The thesis attributes this contrast partly to deep-learning-oriented function approximation and notes low-tree-width graphical models and GPs as exceptions.Source: §46 · pp. 55–56