Restructuring Tractable Probabilistic Circuits

Honghua Zhang, Benjie Wang, Marcelo Arenas, Guy Van den Broeck

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:

  1. 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.
  2. 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.
  3. Recursive Reconstruction: Using these covers, the algorithm recursively builds a new PC from the bottom up.
A labelling of a target vtree W using latent variables (Z) from the source PC's Bayesian Network representation.

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.

The recursive construction of a PC node using sum (⊕) and product (⊗) layers to satisfy the conditional probabilities defined by the target structure.

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

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.
BibTeX
@inproceedings{zhang2025restructuring,
  author = {Honghua Zhang and Benjie Wang and Marcelo Arenas and Guy Van den Broeck},
  title = {{Restructuring Tractable Probabilistic Circuits}},
  booktitle = {International Conference on Artificial Intelligence and Statistics},
  year = {2025},
  url = {https://openreview.net/forum?id=t1HteHSSfe},
}

Loading related content...

Figure