Abstract: Probabilistic circuits (PCs) are a unifying representation for probabilistic models that support tractable inference. Numerous applications of PCs like controllable text generation depend on the ability to efficiently multiply two circuits. Existing multiplication algorithms require that the circuits respect the same structure, i.e. variable scopes decomposes according to the same vtree. In this work, we propose and study the task of restructuring structured(-decomposable) PCs, that is, transforming a structured PC such that it conforms to a target vtree. We propose a generic approach for this problem and show that it leads to novel polynomial-time algorithms for multiplying circuits respecting different vtrees, as well as a practical depth-reduction algorithm that preserves structured decomposibility. Our work opens up new avenues for tractable PC inference, suggesting the possibility of training with less restrictive PC structures while enabling efficient inference by changing their structures at inference time.
Introduction
Probabilistic Circuits (PCs) are a powerful class of generative models prized for their "tractable inference" capabilities. They allow for the exact and efficient calculation of complex probabilities, such as marginals, which are often #P-hard in other graphical models. However, this tractability is typically conditional: the circuit must adhere to a specific hierarchical structure known as a vtree.
A significant bottleneck in PC research has been the difficulty of combining models. If two PCs—for instance, a language model and a logical constraint—do not share the exact same vtree, multiplying them to find their intersection is generally computationally intractable. Furthermore, many PCs are "deep," leading to slow evaluation on modern parallel hardware like GPUs. Previous attempts to reduce circuit depth often resulted in an exponential explosion in model size.
Methodology: The Restructuring Framework
This paper introduces a formal framework for "restructuring" PCs, allowing them to be transformed from one vtree structure to another while preserving the underlying probability distribution. The authors bridge the gap between PCs and Graphical Models through a three-step process:
- Bayesian Network Interpretation: The authors prove that any structured-decomposable PC can be viewed as a tree-shaped Bayesian Network (BN) with categorical latent variables. This "BN Bridge" allows the use of established tools like d-separation to solve circuit-compilation problems.
- The "Covering" Algorithm: To transition to a new target structure, the algorithm identifies sets of latent variables (called "covers" or "labels") in the BN that satisfy the conditional independence requirements of the new structure.
- Recursive Reconstruction: Using these covers, the algorithm recursively builds a new PC from the bottom up.
A key technical contribution is the concept of Contiguity. A PC is contiguous if its variables follow a linear ordering. For contiguous circuits, finding these covers is highly efficient, enabling polynomial-time restructuring.
Key Insights and Results
Polynomial-Time Multiplication
The authors identify a new class of PCs that can be multiplied in polynomial time, even with different structures, provided they satisfy the contiguity property. This bypasses traditional complexity barriers for models like Hidden Markov Models and Probabilistic Context-Free Grammars.
Tighter Depth Reduction and GPU-Friendliness
The paper demonstrates that any structured PC can be restructured into a "shallow" (logarithmic depth) version with a size bound of $O(nh^3)$, where $n$ is the number of variables and $h$ is the hidden state size. This is a massive improvement over previous theoretical bounds ($O(n^3h^6)$), suggesting that GPU-friendly PCs are much more compact than previously thought.
Determinism Preservation
The restructuring algorithm preserves "determinism," a property essential for tasks like finding the most likely state (MAP inference), ensuring the transformed models remain useful for a wide range of downstream tasks.
Limitations and Future Work
While the theoretical bounds are promising, the paper focuses on algorithmic complexity rather than empirical validation on large-scale benchmarks. The current approach for finding latent variable covers is "greedy"; determining whether an "optimal" labelling exists that minimizes the resulting circuit size remains an open problem. Additionally, the complexity depends on the cardinality of the labelling ($M$), which could grow large if the target structure is highly incompatible with the source, though many practical cases remain efficient.
Summary updated