  Latent variable models have been successfully applied in lossless compression
with the bits-back coding algorithm. However, bits-back suffers from an
increase in the bitrate equal to the KL divergence between the approximate
posterior and the true posterior. In this paper, we show how to remove this gap
asymptotically by deriving bits-back coding algorithms from tighter variational
bounds. The key idea is to exploit extended space representations of Monte
Carlo estimators of the marginal likelihood. Naively applied, our schemes would
require more initial bits than the standard bits-back coder, but we show how to
drastically reduce this additional cost with couplings in the latent space.
When parallel architectures can be exploited, our coders can achieve better
rates than bits-back with little additional cost. We demonstrate improved
lossless compression rates in a variety of settings, especially in
out-of-distribution or sequential data compression.
