Bit-Swap: Recursive Bits-Back Coding for Lossless Compression with Hierarchical Latent Variables

The "bits back" argument (Wallace, 1990; Hinton & Van Camp, 1993) suggests lossless compression schemes with latent variable models. However, how to translate the "bits back" argument into efficient and practical lossless compression schemes is still largely an open problem. Bits-Back with Asymmetric Numeral Systems (Townsend et al., 2018) makes "bits back" coding practically feasible, yet when executed on hierarchical latent variable models, their algorithm becomes substantially inefficient. In this paper we propose Bit-Swap, a compression scheme that generalizes existing lossless compression techniques and results in strictly better compression rates for hierarchical latent variable models. Through experiments we verify that the proposed technique results in lossless compression rates that are empirically superior to existing techniques.