and generate codewords whose expected length approaches the theoretical limit (i.e., the negative
cross-entropy between D and p). Although there exist various close-to-optimal compression schemes
(e.g., Huffman Coding (Huffman, 1952) and Arithmetic Coding (Rissanen, 1976)), a natural question
to ask is what are the requirements on the model p such that compression algorithms can utilize it for
encoding/decoding in a computationally efﬁcient manner? In this paper, we highlight the advantages
of tractable probabilistic models for lossless compression by introducing a concrete class of models
that are expressive and support efﬁcient encoding and decoding.
To encode a sample x, a standard streaming code operates by sequentially encoding every symbol
xi into a bitstream b, such that xi occupies approximately − log p(xi|x1, . . . , xi−1) bits in b. As a
result, the length of b is approximately − log p(x). For example, Arithmetic Coding (AC) encodes the
symbols {xi}D
LOSSLESS COMPRESSION WITH PROBABILISTIC CIRCUITS