Scaling Probabilistic Circuits via Monarch Matrices

Honghua Zhang, Meihua Dang, Benjie Wang, Stefano Ermon, Nanyun Peng, and Guy Van den Broeck, in Proceedings of the 42nd International Conference on Machine Learning (ICML), 2025.

Abstract

Probabilistic Circuits (PCs) are tractable representations of probability distributions allowing for exact and efficient computation of likelihoods and marginals. Recent advancements have improved the scalability of PCs by leveraging their sparse properties or tensorized operations. However, no existing method fully exploits both aspects simultaneously. In this paper, we propose a novel sparse and structured parameterization for the sum blocks in PCs. By replacing dense matrices with sparse Monarch matrices, we significantly reduce the memory and computation costs, scaling PCs to next level. From a theory perspective, our construction arises naturally from circuit multiplication; from a practical perspective, compared to previous efforts on scaling up tractable probabilistic models, our approach not only achieves state-of-the-art generative modeling performance on challenging benchmarks like Text8, LM1B and ImageNet, but also demonstrates superior scaling behavior, achieving the same performance with substantially less compute as measured by the number of floating-point operations (FLOPs) during training.

Bib Entry

@inproceedings{zhang2025monarch,
  title = {Scaling Probabilistic Circuits via Monarch Matrices},
  author = {Zhang, Honghua and Dang, Meihua and Wang, Benjie and Ermon, Stefano and Peng, Nanyun and den Broeck, Guy Van},
  year = {2025},
  booktitle = {Proceedings of the 42nd International Conference on Machine Learning (ICML)}
}