1Note that there exists compression algorithms optimized particularly for speed by using simple entropy
models (Townsend et al., 2019), though that also leads to worse bitrates. See Sec. 3.3 for detailed discussion.

2

Published as a conference paper at ICLR 2022

partitions the current interval [a, b) using the left and right side cumulative probability of xi:

li(xi) := p(Xi < xi | x1, . . . , xi−1),

hi(xi) := p(Xi≤ xi | x1, . . . , xi−1).
LOSSLESS COMPRESSION WITH PROBABILISTIC CIRCUITS