# Lossless Compression with Probabilistic Circuits arXiv: https://arxiv.org/abs/2111.11632 · HTML: https://mlsanity.com/paper/2111.11632/ ## Key facts - Cited by 20 papers in the map (data through 14 Oct 2026). - Builds on 23 of its 58 references that are in the map. - First posted on arXiv 23 Nov 2021. ## Builds on (most cited first, 23 of 23) - [PyTorch: An Imperative Style, High-Performance Deep Learning Library](https://mlsanity.com/paper/1912.01703/) (2019) - [Fashion-MNIST: a Novel Image Dataset for Benchmarking Machine Learning Algorithms](https://mlsanity.com/paper/1708.07747/) (2017) - [Auto-Encoding Variational Bayes](https://mlsanity.com/paper/1312.6114/) (2013) - [Density estimation using Real NVP](https://mlsanity.com/paper/1605.08803/) (2016) - [NICE: Non-linear Independent Components Estimation](https://mlsanity.com/paper/1410.8516/) (2014) - [Improving Variational Inference with Inverse Autoregressive Flow](https://mlsanity.com/paper/1606.04934/) (2016) - [NVAE: A Deep Hierarchical Variational Autoencoder](https://mlsanity.com/paper/2007.03898/) (2020) - [Einsum Networks: Fast and Scalable Learning of Tractable Probabilistic Circuits](https://mlsanity.com/paper/2004.06231/) (2020) - [Practical Full Resolution Learned Lossless Image Compression](https://mlsanity.com/paper/1811.12817/) (2018) - [Practical Lossless Compression with Latent Variables using Bits Back Coding](https://mlsanity.com/paper/1901.04866/) (2019) - [Integer Discrete Flows and Lossless Compression](https://mlsanity.com/paper/1905.07376/) (2019) - [Bit-Swap: Recursive Bits-Back Coding for Lossless Compression with Hierarchical Latent Variables](https://mlsanity.com/paper/1905.06845/) (2019) - [Tractable Regularization of Probabilistic Circuits](https://mlsanity.com/paper/2106.02264/) (2021) - [HiLLoC: Lossless Image Compression with Hierarchical Latent Variable Models](https://mlsanity.com/paper/1912.09953/) (2019) - [IDF++: Analyzing and Improving Integer Discrete Flows for Lossless Compression](https://mlsanity.com/paper/2006.12459/) (2020) - [Compression with Flows via Local Bits-Back Coding](https://mlsanity.com/paper/1905.08500/) (2019) - [On the Out-of-distribution Generalization of Probabilistic Image Modelling](https://mlsanity.com/paper/2109.02639/) (2021) - [iVPF: Numerical Invertible Volume Preserving Flow for Efficient Lossless Compression](https://mlsanity.com/paper/2103.16211/) (2021) - [Strudel: Learning Structured-Decomposable Probabilistic Circuits](https://mlsanity.com/paper/2007.09331/) (2020) - [Group Fairness by Probabilistic Modeling with Latent Fair Decisions](https://mlsanity.com/paper/2009.09031/) (2020) - [Disentangling Latent Space for VAE by Label Relevant/Irrelevant Dimensions](https://mlsanity.com/paper/1812.09502/) (2018) - [Improving Lossless Compression Rates via Monte Carlo Bits-Back Coding](https://mlsanity.com/paper/2102.11086/) (2021) - [Smoothing Structured Decomposable Circuits](https://mlsanity.com/paper/1906.00311/) (2019) ## Built on by (most cited first, 20 of 20) - [Semantic Probabilistic Layers for Neuro-Symbolic Learning](https://mlsanity.com/paper/2206.00426/) (2022) - [An Introduction to Neural Data Compression](https://mlsanity.com/paper/2202.06533/) (2022) - [Scaling Up Probabilistic Circuits by Latent Variable Distillation](https://mlsanity.com/paper/2210.04398/) (2022) - [Computationally-Efficient Neural Image Compression with Shallow Decoders](https://mlsanity.com/paper/2304.06244/) (2023) - [Scaling Tractable Probabilistic Circuits: A Systems Perspective](https://mlsanity.com/paper/2406.00766/) (2024) - [Image Inpainting via Tractable Steering of Diffusion Models](https://mlsanity.com/paper/2401.03349/) (2023) - [What is the Relationship between Tensor Factorizations and Circuits (and How Can We Exploit it)?](https://mlsanity.com/paper/2409.07953/) (2024) - [Understanding the Distillation Process from Deep Generative Models to Tractable Probabilistic Circuits](https://mlsanity.com/paper/2302.08086/) (2023) - [Sparse Probabilistic Circuits via Pruning and Growing](https://mlsanity.com/paper/2211.12551/) (2022) - [SC2 Benchmark: Supervised Compression for Split Computing](https://mlsanity.com/paper/2203.08875/) (2022) - [Building Expressive and Tractable Probabilistic Generative Models: A Review](https://mlsanity.com/paper/2402.00759/) (2024) - [Polynomial Semantics of Tractable Probabilistic Circuits](https://mlsanity.com/paper/2402.09085/) (2024) - [Scaling Continuous Latent Variable Models as Probabilistic Integral Circuits](https://mlsanity.com/paper/2406.06494/) (2024) - [Probabilistic Integral Circuits](https://mlsanity.com/paper/2310.16986/) (2023) - [How to Square Tensor Networks and Circuits Without Squaring Them](https://mlsanity.com/paper/2512.17090/) (2025) - [Tractable Representation Learning with Probabilistic Circuits](https://mlsanity.com/paper/2507.04385/) (2025) - [Certifying Fairness of Probabilistic Circuits](https://mlsanity.com/paper/2212.02474/) (2022) - [Hallucination as an Anomaly: Dynamic Intervention via Probabilistic Circuits](https://mlsanity.com/paper/2605.05953/) (2026) - [AstroCompress: A benchmark dataset for multi-purpose compression of astronomical data](https://mlsanity.com/paper/2506.08306/) (2025) - [The Expressivity Boundary of Probabilistic Circuits: A Comparison with Large Language Models](https://mlsanity.com/paper/2605.12940/) (2026) ## Abstract (arXiv) Despite extensive progress on image generation, common deep generative model architectures are not easily applied to lossless compression. For example, VAEs suffer from a compression cost overhead due to their latent variables. This overhead can only be partially eliminated with elaborate schemes such as bits-back coding, often resulting in poor single-sample compression rates. To overcome such problems, we establish a new class of tractable lossless compression models that permit efficient encoding and decoding: Probabilistic Circuits (PCs). These are a class of neural networks involving |p| computational units that support efficient marginalization over arbitrary subsets of the D feature dimensions, enabling efficient arithmetic coding. We derive efficient encoding and decoding schemes that both have time complexity O (log(D) · |p|), where a naive scheme would have linear costs in D and |p|, making the approach highly scalable. Empirically, our PC-based (de)compression algorithm runs 5-40 times faster than neural compression algorithms that achieve similar bitrates. By scaling up the traditional PC structure learning pipeline, we achieve state-of-the-art results on image datasets such as MNIST. Furthermore, PCs can be naturally integrated with existing neural compression algorithms to improve the performance of these base models on natural image datasets. Our results highlight the potential impact that non-standard learning architectures may have on neural data compression.