  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
$\mathcal{O} (\log(D) \cdot |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.
