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 because summations and integrations can scale exponentially. The thesis studies probabilistic circuits as structurally constrained models that support recursive, tractable conditioning and related reasoning operations, while connecting them to hierarchical mixtures and deep-learning implementations.

Problem
Probabilistic inference is conceptually simple but generally requires summations or integrations that scale exponentially with problem dimensionality.
Method
The thesis uses decomposable, smooth probabilistic circuits whose normalized nodes form hierarchical mixtures and whose conditionals are computed recursively.
Results
Probabilistic circuits provide recursive conditional distributions by delegating conditioning through sum and product nodes to tractable input distributions.
Takeaways & Limitations
Probabilistic circuits offer a tractable framework for reasoning under uncertainty while retaining probabilistic structure and interfaces to deep-learning systems.
Takeaways & Limitations
For continuous densities, most probable explanation may not correspond to the decision that is desirable for real-valued state spaces.

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

This thesis centers rational AI on knowledge representation, reasoning, and learning, proposing probability as a conceptually simple language that connects uncertainty with logic, human reasoning, decision theory, and information theory. Probabilistic circuits address probability’s computational difficulty by imposing structural constraints that enable tractable, flexible inference over full joint distributions.

Introduction · 1.1 What is AI (roughly)?: The thesis focuses on rational AI’s minimalist core: knowledge representation, reasoning, and learning, while distinguishing these from more human-oriented capabilities.Reasoning derives new insights from stored information, and learning adaptively modifies or extends the system’s knowledge representation.
Simplicity: Probabilistic inference is conceptually simple but computationally difficult because summations and integrations can scale exponentially with problem dimensionality.The sum rule marginalizes unknown facts, the product rule conditions on observations, and inference cascades these rules to propagate information from observations to predictions.
Decision Making · Qualitative Similarities to Common Sense Reasoning: Probability supports optimal decision making by defining decisions as expected-loss minimizers and naturally represents non-monotonic belief updates and explaining away.These properties connect probabilistic reasoning to decision theory and qualitative features of common-sense reasoning discussed by Pearl.
1.2 The Role of Probability · Bayesianism and Consistency with Logic · Information Theory: Probability is proposed as an excellent core language for AI because it offers conceptual simplicity, expresses uncertainty, and connects to logic, human reasoning, decision theory, and information theory.Its foundations include the sum and product rules, while extreme probabilities recover propositional logic and Bayesian learning treats posterior inference as probabilistic reasoning about parameters given data.
1.3 Why Probabilistic Circuits?: Classical probabilistic models can represent domains accurately yet remain hard to run: inference in probabilistic graphical models may scale exponentially with tree-width, while task-specific neural networks lack flexible joint inference.Predicting arbitrary feature conditionals requires a model over the full joint distribution, and inference remains generally hard in deep generative models.
1.3 Why Probabilistic Circuits?: Probabilistic circuits combine full-joint probabilistic modeling with flexible, tractable inference by enforcing structural constraints, making them a hybrid of probabilistic graphical models and neural networks.Their structure guarantees tractable reasoning operations, drawing on recurring patterns in variable elimination, junction trees [28], arithmetic circuits, sum-product networks, cutset networks, and probabilistic sentential decision diagrams.
1.3 Why Probabilistic Circuits?: PCs consolidate existing tractable probabilistic-modeling and exact-inference approaches under a common syntax rather than introducing an entirely novel model class.Their structural constraints determine which reasoning operations remain tractable and delineate differences among related approaches.
1.3 Why Probabilistic Circuits?: Probabilistic circuits trade expressive efficiency and architectural freedom for tractable inference, so they do not make intrinsically hard probabilistic problems easy without approximation.The constraints limit the choice of neural-network structures and therefore impose limits on expressive efficiency.

Basic Probability Theory

The section presents the probability space as the foundational formalism for probabilistic reasoning, combining a sample space, a sigma-algebra of logically structured events, and a probability measure. It emphasizes that this framework precisely characterizes probability while remaining abstract enough to motivate more intuitive representations such as random variables.

Probability spaces: A probability space is the foundational contract of probabilistic AI: every probabilistic argument should reduce to (Ω,Σ,P), or it is not probability.This provides a soundness criterion for abstract and complex probabilistic models.
Measurable spaces: A measurable space consists of a non-empty sample space Ω and a sigma-algebra Σ that collects events while encoding logical negation, or, and and.The sigma-algebra is closed under complements, countable unions, and consequently countable intersections.
Events and abstraction: The sigma-algebra can provide a more macroscopic event representation than atomic outcomes, as shown by a die model that includes selected events without all singleton outcomes.For the die, Σ contains {1} and {2} but not {3} and {4}.
Probability spaces: A probability space adds a measure P:Σ→[0,1] that assigns probabilities to events, gives Ω probability 1, and is countably additive over disjoint events.The definition also implies P(∅)=0 and P(Ā)=1−P(A).
Intuition and representation: Although the probability-space definition is precise and minimalist, it offers limited intuition, motivating random variables that transform uncertainty over Ω into a more interpretable space X.The resulting space remains described by a probability measure.

Probabilistic Inference

Probabilistic inference uses distribution functions to represent knowledge and answer queries through a conceptually simple calculus, while many useful computations remain NP-hard. Core operations include marginalization, conditioning, optimization, and expected-loss decision making.

Foundations: Distribution functions represent dependencies and uncertainty, while inference answers queries of interest about the represented knowledge.
Computational scope: Inference also supports expectations and optimization, but these queries are typically NP-hard in probabilistic models.Probabilistic circuits are introduced as a framework for computing such queries tractably.
Marginalization: Marginalization integrates out variables Z to obtain the exact distribution over a subset Y, thereby reasoning while ignoring or accounting for unknown quantities.The operation is consistent: different sequences of marginalizing variables yield the same resulting marginal.
Conditioning: Conditioning updates the distribution over Y after observing or injecting evidence that Z=z, and for continuous Z is well-defined when pZ(z) is non-zero and continuous.
Decision making: Expected-loss minimization converts a conditional distribution into a hard decision: squared loss selects the mean, whereas absolute loss selects the median and is robust to outliers.This decision step is ideally performed last because it discards the distribution’s uncertainty; optimality requires an adequate loss, the true data-generating distribution, and exact computation.

State of The Art

Probabilistic approaches gained prominence in AI as the need to represent uncertainty became clear, despite early concerns about probability’s computational difficulty. Graphical models provide an intuitive language for probabilistic structure, but exact inference is generally hard, motivating tractable restrictions and alternative deep models.

State of The Art: AI’s shift from logic-based methods toward probabilistic approaches reflected increasing recognition that real-world scenarios require uncertainty modeling.Probability initially faced criticism over computational challenges and perceived impracticality before gradually gaining ground.
State of The Art: Graphical models, especially Bayesian networks, remain a cornerstone and lingua franca of probabilistic modeling because their structure expresses conditional independence and supports tractable inference and learning.Their prominence has diminished somewhat in the deep learning era, but their visual representation remains useful for stating model structure and assumptions.
State of The Art: Exact marginalization in graphical models is generally NP-hard, while bounded-treewidth models permit tractable exact inference.Most probabilistic machine learning systems can be mapped to graphical models that concisely express their structure and assumptions.
State of The Art: Deep autoregressive models use the probability chain rule with shared neural networks and can represent any joint distribution in principle.They can be viewed as fully connected Bayesian networks, supporting sampling and density evaluation.
State of The Art: Marginals, conditionals, and complex inference remain challenging in deep autoregressive models despite their support for sampling and density evaluation.This limitation follows from their fully connected Bayesian-network interpretation.

46 State of The Art

Modern probabilistic models prioritize expressive generative representations, but many rely on approximate inference or lack tractable density, marginal, and conditional evaluation. This contrasts with probability’s ideal as a rigorous reasoning framework under uncertainty.

Neural generative models: VAEs use neural networks to transform simple latent distributions into flexible infinite-mixture models, while amortized encoders approximate posteriors through the ELBO objective.Exact inference is hard, so the ELBO provides a lower bound on log-likelihood for learning.
Neural generative models: GANs train a discriminator adversarially rather than maximizing a likelihood bound, enabling realistic sampling but generally not density evaluation or tractable marginal and conditional inference.Their objective minimizes a probabilistic divergence distinct from maximum likelihood.
Neural generative models: Normalizing Flows provide exact density computation and sampling through bijective transformations, but marginals and conditionals remain challenging.They begin with a simple distribution and use the change-of-variables formula for transformed densities.
Energy- and score-based models: Energy-based and score-based models are highly expressive, yet density evaluation, sampling, marginals, and conditionals are typically intractable or approximation-dependent.Score-Based Models currently represent the state of the art in image generation when combined with diffusion and Langevin dynamics [61], despite difficult-to-validate approximations.
Probabilistic modeling landscape: Probabilistic Programming [69] expresses flexible models as programs whose posterior queries are generally handled with variational inference or Monte Carlo, illustrating the field’s broader reliance on approximation.Gaussian Processes provide a prominent exception-oriented probabilistic modeling framework, with Gaussianity supporting marginal computations and applications in Bayesian modeling and optimization.

Probabilistic Circuits

Probabilistic circuits make probabilistic reasoning tractable by enforcing structural constraints that enable exact, polynomial-time inference, while sacrificing some expressive efficiency. This chapter develops their core operations and summarizes a decade of foundational, algorithmic, and learning contributions to PCs.

Motivation and scope: PCs compute inference tasks such as marginals and conditionals exactly in polynomial time, preserving probabilistic reasoning without approximation.Their tractability comes from structural constraints including smoothness, decomposability, determinism, and related properties.
Expressiveness and normalization: PC tractability is obtained at the cost of expressiveness, because some distributions compact in other probabilistic models require exponentially large PC representations.Normalized sum weights do not improve modeling power, since they can be restored efficiently without changing the represented distribution.
Marginalization: Decomposability and smoothness enable linear-time marginalization, provided the input distributions support tractable marginal computation.The resulting marginal PC represents the exact marginal of the original PC.
Conditioning: Conditioning can be delegated recursively through sum and product nodes, yielding a conditional PC that represents the exact conditional distribution.For product nodes, the conditional operation distributes over the product of the conditionals.
Higher-order inference: The same structural properties support exact expectation and covariance computations through vector- and matrix-valued message passing.The root vector equals the PC expectation, while covariance matrices are computed recursively from input covariances.
Applications and contributions: The chapter also develops PCs as hierarchical latent-variable models and extends them to sampling, expectation-maximization, representation learning, semi-supervised classification, and additional probabilistic queries.Determinism additionally enables fast global maximum-likelihood parameter computation and closed-form Bayesian structure scores.