30x (resp. 10x) faster than both baselines.6 Furthermore, a bigger PC model (M = 32) with 7M
parameters achieved codeword bpd 1.24, and is still 5x faster than BitSwap and IDF. Note that at
the cost of increasing the bitrate, one can signiﬁcantly improve the en- and decoding efﬁciency. For
example, by using a small VAE model, Townsend et al. (2019) managed to compress and decompress
10,000 binarized MNIST samples in 3.26s and 2.82s, respectively.
Related work As hinted by Sec. 2, we seek to directly learn probability distributions p(X) that are
expressive and support tractable (de)compression. In contrast, existing Flow-based (van den Berg
et al., 2020; Zhang et al., 2021b) and VAE-based (Townsend et al., 2019; Kingma et al., 2019; Ho et al.,
2019) neural lossless compression algorithms are based on an orthogonal idea: they adopt simple
(oftentimes fully factorized) distributions over a latent space Z to ensure the tractability of encoding
LOSSLESS COMPRESSION WITH PROBABILISTIC CIRCUITS