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 models that allow for "tractable inference"—calculating complex quantities like marginal probabilities exactly and efficiently. However, they suffer from a significant "compatibility" problem. Operations like multiplying two distributions—essential for adding logical constraints or performing causal adjustments—typically require both circuits to share the exact same vtree (a hierarchical partitioning of variables).
When structures do not match, the multiplication problem is generally #P-hard. This limitation forces practitioners to commit to a single structure during training, restricting the model's flexibility. This paper introduces a framework to transform a circuit from one structure to another on-the-fly without a catastrophic explosion in circuit size.
Methodology: The Restructuring Framework
The proposed restructuring approach follows a three-step process:
- Bayesian Network Interpretation: The authors prove that any structured-decomposable PC can be viewed as a tree-shaped Bayesian Network where internal nodes represent latent (hidden) variables.
- Vtree Labeling: A greedy algorithm identifies "covers"—small sets of latent variables that act as separators. These separators capture the conditional independencies required by the new target structure.
- Recursive Reconstruction: Using these separators, a bottom-up recursive algorithm builds a new PC that conforms to the target vtree.
The Role of Contiguity
A key theoretical contribution is the definition of contiguity. A circuit is contiguous if its internal nodes represent a continuous range of variables (e.g., $X_2$ to $X_5$). For contiguous circuits, such as Hidden Markov Models (HMMs) and Probabilistic Context-Free Grammars (PCFGs), restructuring is particularly efficient, enabling polynomial-time multiplication even across different vtrees.
Algorithm for PC Construction
The core of the restructuring process is the recursive construction of the new circuit. By leveraging the latent variable separators identified in the labeling phase, the algorithm builds the new PC structure while preserving the original probability distribution.
Key Insights and Results
Tighter Depth Reduction
Previously, transforming a circuit into a "shallow" (log-depth) version was known to be possible but computationally expensive, with an expected size increase of $O(n^3h^6)$. This work proves a significantly tighter bound of $O(nh^3)$, where $n$ is the number of variables and $h$ is the hidden state size. This makes parallelized PC inference on modern GPUs far more practical.
Polynomial-Time Multiplication
The paper demonstrates that two contiguous structured PCs can be multiplied in polynomial time if they have different vtrees, provided one has a linear structure or limited depth. This allows for the combination of models trained with different structural biases.
Preservation of Determinism
The restructuring algorithm is shown to preserve determinism, a property crucial for tasks like finding the most likely state (MAP inference), ensuring that the transformed circuits remain useful for a wide range of downstream tasks.
Conclusion and Future Work
This work provides a general algorithm for restructuring PCs, overcoming a major hurdle in the application of tractable models. While the current labeling algorithm is greedy and focuses on binary vtrees, the results for contiguous circuits and depth reduction represent a significant step forward. Future research may explore optimal labeling strategies and extending these techniques to multi-way variable partitions.
Summary updated