Restructuring Tractable Probabilistic Circuits

Honghua Zhang, Benjie Wang, Marcelo Arenas, Guy Van den Broeck
Proceedings of The 28th International Conference on Artificial Intelligence and Statistics, PMLR 258:2566-2574, 2025.

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.

Cite this Paper

BibTeX
@InProceedings{pmlr-v258-zhang25f, title = {Restructuring Tractable Probabilistic Circuits}, author = {Zhang, Honghua and Wang, Benjie and Arenas, Marcelo and den Broeck, Guy Van}, booktitle = {Proceedings of The 28th International Conference on Artificial Intelligence and Statistics}, pages = {2566--2574}, year = {2025}, editor = {Li, Yingzhen and Mandt, Stephan and Agrawal, Shipra and Khan, Emtiyaz}, volume = {258}, series = {Proceedings of Machine Learning Research}, month = {03--05 May}, publisher = {PMLR}, pdf = {https://raw.githubusercontent.com/mlresearch/v258/main/assets/zhang25f/zhang25f.pdf}, url = {https://proceedings.mlr.press/v258/zhang25f.html}, 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.} }
Endnote
%0 Conference Paper %T Restructuring Tractable Probabilistic Circuits %A Honghua Zhang %A Benjie Wang %A Marcelo Arenas %A Guy Van den Broeck %B Proceedings of The 28th International Conference on Artificial Intelligence and Statistics %C Proceedings of Machine Learning Research %D 2025 %E Yingzhen Li %E Stephan Mandt %E Shipra Agrawal %E Emtiyaz Khan %F pmlr-v258-zhang25f %I PMLR %P 2566--2574 %U https://proceedings.mlr.press/v258/zhang25f.html %V 258 %X 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.
APA
Zhang, H., Wang, B., Arenas, M. & den Broeck, G.V.. (2025). Restructuring Tractable Probabilistic Circuits. Proceedings of The 28th International Conference on Artificial Intelligence and Statistics, in Proceedings of Machine Learning Research 258:2566-2574 Available from https://proceedings.mlr.press/v258/zhang25f.html.

Related Material