i=1.
i=1 and G(x) := {p(x1, . . . , xi−1, Xi < xi)}D

4The only difference between the computation of the ith term of F (x) and the ith term of G(x) is in the

value assigned to the inputs for variable Xi (i.e., probabilities pn(Xi = x) vs. pn(Xi < x)).

5

X1X2X3X4PixelhasbeensentPixelbeingsentStreamingcode(e.g.,rANS)Bitstreamp(x3|x1,x2)X1X1X2X2X3X3X4Imagepatch,e.g.,2×2Group#1Group#2Group#3Allnodesingroups#1,#2,and#3donotneedtobeexplicitlyevaluated.EncoderDecoderSamePCp(x3|x1,x2)X1X2X3X4Reconstructed patchStreamingcode(e.g.,rANS)Published as a conference paper at ICLR 2022

Algorithm 1 Compute F (x) (see Alg. 3 for details)
1: Input: A smooth and structured-decomposable PC p, variable instantiation x
2: Output: Fπ(x) = {p(x1, . . . , xi)}D
3: Initialize: The probability p(n) of every unit n is initially set to 1
4:
5: for i = 1 to D do
6:

Evaluate PC units in evali in a bottom-up manner and compute p(x1, . . . , xi)
LOSSLESS COMPRESSION WITH PROBABILISTIC CIRCUITS