🤖 AI

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

This first part of a cumulative habilitation thesis advocates for probabilistic circuits as a tractable framework for AI reasoning and learning under uncertainty, synthesizing a decade of research on their foundational theory, learning algorithms, scalable implementations, and integration with deep and symbolic machine learning paradigms.

Original authors: Robert Peharz

Published 2026-08-18

📖 6 min read🧠 Deep dive

CC BY 4.0

Original authors: Robert Peharz

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

In the quest to build machines that think, scientists have long debated the best language for intelligence. One camp argues for rigid logic, where facts are absolute and conclusions follow strict rules. Another favors neural networks, systems that learn by spotting patterns in vast amounts of data, much like a human brain. But there is a third, older path that treats uncertainty not as a flaw to be fixed, but as a fundamental feature of the world. This approach relies on probability, a mathematical framework that allows a system to say, "I am not sure, but here is how likely different outcomes are." It is the language of risk, of guessing the weather, or of a doctor weighing symptoms against a diagnosis. The power of probability lies in its ability to combine what is known with what is unknown, updating beliefs as new evidence arrives. However, for decades, this elegant language has been difficult to use in practice. While the rules for reasoning with probability are simple, actually performing the calculations for complex real-world problems often requires a computer to perform an impossible number of steps, taking longer than the age of the universe to finish.

Robert Peharz, a researcher at the Graz University of Technology, has spent the last decade working to solve this computational bottleneck. His work focuses on a specific type of model called a probabilistic circuit. Imagine a vast, branching tree where every leaf represents a simple piece of information, and every branch combines these pieces to form a complete picture of the world. In standard models, calculating the likelihood of a specific scenario requires tracing every possible path through this tree, a task that becomes exponentially harder as the tree grows. Peharz's research demonstrates that by imposing a few strict architectural rules on how these branches connect, we can make the entire calculation fast and exact. These rules ensure that the model never gets stuck trying to count every possibility. Instead, it can instantly answer complex questions, such as predicting the most likely cause of a set of symptoms or determining the probability of a specific event given a mountain of data.

The core of Peharz's contribution is the realization that these circuits are not just a new invention, but a unifying language for many existing methods. He shows that various models, from arithmetic circuits to sum-product networks, are actually different names for the same underlying structure. By treating them as one cohesive family, he has been able to develop a set of standard tools that work across the board. One of his key findings is that these circuits can be built to be "smooth" and "decomposable." In plain terms, this means the model is organized so that it never tries to multiply two pieces of information that depend on the same unknown factor, and it never adds together two different possibilities that cover different sets of facts. These structural constraints act like a traffic system for the computer's calculations, preventing traffic jams and ensuring that information flows smoothly from the bottom of the tree to the top.

Because of this organization, the computer can perform tasks that were previously considered too difficult. For instance, it can calculate the average outcome of a situation or find the single most probable explanation for a set of observations in a fraction of a second. Peharz has also shown how to teach these circuits to learn from data. He developed methods that allow the model to adjust its internal weights automatically, finding the best fit for the data without needing to guess. Furthermore, he has proven that these circuits can be combined with other powerful, but computationally heavy, machine learning tools. By using the probabilistic circuit as a fast, reliable engine to handle the easy parts of a problem, and letting slower, more complex models handle the difficult parts, the system as a whole becomes both powerful and efficient. This hybrid approach allows researchers to build models that are not only accurate but also capable of explaining their reasoning.

The work also bridges the gap between statistical learning and symbolic logic. Peharz demonstrated that these circuits can be transformed into decision trees, a classic method for making choices based on rules. This connection allows the system to handle missing data gracefully; if a piece of information is missing, the circuit can simply ignore that branch and still provide a valid answer, rather than failing. He also applied these ideas to the field of cybersecurity, using the circuits to analyze physical side-channels, such as power consumption, to uncover secret encryption keys. In these tests, the circuit-based approach was significantly more successful and robust against noise than previous methods.

Throughout his research, Peharz has addressed a common misconception in the field: the idea that you must choose between a model that is easy to calculate with and one that is expressive enough to describe complex reality. His results show that this is a false choice. While there are limits to how compactly a probabilistic circuit can represent certain types of data, he has shown that for many practical applications, these models are just as good as, or even better than, the more complex, intractable alternatives. He has also clarified that adding certain features, like unnormalized weights, does not actually increase the model's power, a finding that helps simplify the design of these systems.

The ultimate goal of this work is to create artificial intelligence that is not only smart but also reliable and understandable. By grounding AI in the rigorous rules of probability and ensuring that the calculations can be done exactly and quickly, Peharz's research provides a foundation for machines that can reason under uncertainty with the same confidence a human expert might. This approach moves beyond the "black box" nature of many modern AI systems, offering a way to see exactly how a conclusion was reached. As these methods are integrated into deep learning frameworks and combined with other technologies, they promise to make artificial intelligence more trustworthy, capable of handling the messy, uncertain reality of the world without sacrificing speed or accuracy.

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

Problem Statement

Artificial Intelligence (AI) requires systems capable of knowledge representation, reasoning, and learning under uncertainty. While probability theory provides a rigorous, consistent, and conceptually simple language for these tasks—reducible to the sum and product rules—it faces a fundamental computational barrier: probabilistic inference is generally NP-hard in most probabilistic models.

Existing frameworks exhibit a dichotomy:

Expressive but Intractable Models: Deep generative models (e.g., VAEs, GANs, Normalizing Flows, Score-based models) and complex Probabilistic Graphical Models (PGMs) can represent complex joint distributions but typically require approximate inference (e.g., variational inference, MCMC) because exact marginalization or conditioning is computationally prohibitive.
Tractable but Limited Models: Models with bounded tree-width or specific structural constraints allow exact inference but often suffer from limited expressive efficiency, requiring exponentially large representations for certain distributions.

The core problem addressed is the lack of a unified framework that combines the expressivity of deep learning with the tractability of exact probabilistic inference, allowing for the computation of marginals, conditionals, expectations, and most probable explanations (MPE) in polynomial time without approximation.

Methodology: Probabilistic Circuits (PCs)

The paper proposes Probabilistic Circuits (PCs) as a "lingua franca" for tractable probabilistic modeling. PCs are defined as directed acyclic computational graphs (neural networks) with three types of nodes:

Distribution Nodes (Leaves): Parametric probability distributions (e.g., Gaussians, categorical) over subsets of variables.
Sum Nodes: Weighted sums of inputs, representing mixtures.
Product Nodes: Products of inputs, representing factorizations.

To ensure tractable inference, PCs must satisfy specific structural constraints:

Decomposability: The inputs to any product node must have disjoint scopes (sets of variables). This ensures that the product represents a factorized distribution where variables are independent.
Smoothness: The inputs to any sum node must have identical scopes. This ensures that the sum represents a valid mixture distribution.
Determinism: (Optional but powerful) At most one input to a sum node is non-zero for any given complete assignment. This enables efficient computation of the Most Probable Explanation (MPE).

Under these constraints, PCs function as hierarchical mixture models. The paper demonstrates that if the leaf distributions support tractable marginalization and conditioning, these operations can be "delegated" recursively through the network:

Marginalization: The marginal of a sum is the sum of marginals; the marginal of a product is the product of marginals (due to disjoint scopes).
Conditioning: The conditional of a sum is a re-weighted sum of conditionals; the conditional of a product is the product of conditionals.
Expectations and Covariances: These can be computed via recursive network passes using the law of total expectation and covariance.
MPE: Under determinism, MPE can be computed via a single forward pass by selecting the maximizing branch at each sum node.

Key Contributions

The thesis synthesizes a decade of research, highlighting the following contributions:

1. Foundations and Theory

Normalization and Expressivity: The author proves that using unnormalized sum weights does not increase the modeling power of smooth, decomposable PCs; they can be transformed into normalized equivalents without changing the represented distribution. Similarly, the concept of "consistency" (a relaxation of decomposability) is shown not to significantly extend expressivity beyond standard decomposability.
Latent Variable Interpretation: PCs are formally interpreted as hierarchical latent variable models. This allows for the derivation of exact ancestral sampling, the Expectation-Maximization (EM) algorithm, and a "decompilation" of PCs into Bayesian Networks with latent variables.

2. Bayesian Approaches

Bayesian Inference: The work introduces Gibbs sampling algorithms for PC parameters, extending leaves to mixtures of exponential families to handle anonymous data types.
Structure Learning: A principled Bayesian structure score for deterministic PCs is derived using factorized Dirichlet priors. This allows for learning optimal structures in the infinite data limit, a principled approach previously missing for PCs.

3. Deep Learning Integration

Scalable Implementations: The thesis details the evolution of PC implementations from initial TensorFlow graphs to RAT-SPNs and Einsum Networks (EiNets). EiNets utilize tensor contraction (einsum) to vectorize operations, achieving performance comparable to Multi-Layer Perceptrons (MLPs) and enabling training on large datasets like MNIST.
Conditional PCs: The framework supports conditional PCs where parameters are functions of context (learned via neural networks), enabling tractable inference in conditional distributions $p(y|x)$ .
Robustness: The connection to decomposable neural networks (relaxing probabilistic constraints) allows for exact robustness guarantees against adversarial attacks.

4. Hybrid Models

The thesis proposes a "middle ground" approach, combining tractable PCs with intractable models:

PCs as Sub-modules: Replacing intractable components (e.g., object models in the Attend-Infer-Repeat system) with PCs to perform exact marginalization of large latent spaces, leaving only a few variables for variational inference.
Intractable Models as Leaves: Using VAEs or Gaussian Processes (GPs) as leaf nodes within a PC. This creates a "collection of small intractable models glued together by a tractable model," improving convergence and log-likelihoods compared to standalone VAEs.
Integral Nodes: Augmenting PCs with integral nodes over continuous latent variables, leveraging numerical quadrature for exact inference in cases where standard VAEs require approximation.

5. Connections to Symbolic Models

Decision Trees: A method to transform decision trees into PCs, converting conditional classifiers into full joint distributions while preserving the original classification logic.
Knowledge Graph Embeddings (KGEs): Mapping KGEs to PCs, enabling standard maximum likelihood training, sampling from SPO triplets, and encoding hard logical constraints.
Side-Channel Attacks: Applying PC inference to soft analytic side-channel attacks (SASCA) on cryptographic algorithms (e.g., AES), achieving exact inference and higher success rates than loopy belief propagation.

Results and Claims

The paper claims that PCs offer a unique position in the AI landscape:

Exactness: Unlike most deep generative models, PCs guarantee exact computation of marginals, conditionals, and expectations in polynomial time relative to the circuit size.
Competitive Performance: Empirical evidence (referenced in Part II of the thesis) suggests that tractable models often compete with, and sometimes outperform, intractable models in terms of log-likelihood and predictive accuracy, challenging the assumption that tractability necessitates poor expressivity.
Interpretability: The hierarchical mixture structure and the ability to perform exact inference make PCs highly interpretable, supporting tasks like outlier detection and missing data imputation.
Unified Framework: PCs serve as a unifying syntax for various existing tractable models (e.g., Arithmetic Circuits, Sum-Product Networks, Cutset Networks), clarifying their structural differences and shared properties.

Significance

The significance of this work lies in its advocacy for probability as a core language for AI and the demonstration that tractability is achievable without sacrificing the ability to represent complex joint distributions.

By establishing structural constraints (decomposability, smoothness, determinism) as the mechanism for tractability, the thesis provides a rigorous foundation for "Reasoning Machines" that can perform optimal decision-making under uncertainty. It bridges the gap between the conceptual elegance of probabilistic reasoning (sum/product rules) and the practical demands of modern AI, offering a framework where inference is not an approximation but a guaranteed, efficient computation. The work positions PCs not merely as a model class, but as a foundational approach for integrating learning, reasoning, and decision theory in a consistent manner.