# Accelerating Relative Entropy Coding with Space Partitioning

arXiv: https://arxiv.org/abs/2405.12203 · HTML: https://mlsanity.com/paper/2405.12203/

## Key facts

- Cited by 4 papers in the map (data through 14 Oct 2026).
- Builds on 17 of its 35 references that are in the map.
- First posted on arXiv 20 May 2024.

## Builds on (most cited first, 17 of 17)

- [Variational image compression with a scale hyperprior](https://mlsanity.com/paper/1802.01436/) (2018)
- [End-to-end Optimized Image Compression](https://mlsanity.com/paper/1611.01704/) (2016)
- [Learned Image Compression with Discretized Gaussian Mixture Likelihoods and Attention Modules](https://mlsanity.com/paper/2001.01568/) (2020)
- [The Perception-Distortion Tradeoff](https://mlsanity.com/paper/1711.06077/) (2017)
- [A* Sampling](https://mlsanity.com/paper/1411.0030/) (2014)
- [Nonlinear Transform Coding](https://mlsanity.com/paper/2007.03034/) (2020)
- [Practical Full Resolution Learned Lossless Image Compression](https://mlsanity.com/paper/1811.12817/) (2018)
- [Lossy Compression with Gaussian Diffusion](https://mlsanity.com/paper/2206.08889/) (2022)
- [Practical Lossless Compression with Latent Variables using Bits Back Coding](https://mlsanity.com/paper/1901.04866/) (2019)
- [Minimal Random Code Learning: Getting Bits Back from Compressed Model Parameters](https://mlsanity.com/paper/1810.00440/) (2018)
- [Compressing Images by Encoding Their Latent Representations with Relative Entropy Coding](https://mlsanity.com/paper/2010.01185/) (2020)
- [Algorithms for the Communication of Samples](https://mlsanity.com/paper/2110.12805/) (2021)
- [On the advantages of stochastic encoders](https://mlsanity.com/paper/2102.09270/) (2021)
- [Compression with Bayesian Implicit Neural Representations](https://mlsanity.com/paper/2305.19185/) (2023)
- [Modality-Agnostic Variational Compression of Implicit Neural Representations](https://mlsanity.com/paper/2301.09479/) (2023)
- [RECOMBINER: Robust and Enhanced Compression with Bayesian Implicit Neural Representations](https://mlsanity.com/paper/2309.17182/) (2023)
- [Some Notes on the Sample Complexity of Approximate Channel Simulation](https://mlsanity.com/paper/2405.04363/) (2024)

## Built on by (most cited first, 4 of 4)

- [Compression as Adaptation: Implicit Visual Representation with Diffusion Foundation Models](https://mlsanity.com/paper/2603.07615/) (2026)
- [Accelerating Diffusion Sampling via Speculative Draft Trees](https://mlsanity.com/paper/2609.17691/) (2026)
- [Training-Free Vector Quantization via Gaussian VAEs](https://mlsanity.com/paper/2512.06609/) (2025)
- [Watermarkable Multi-Draft Speculative Sampling via Poisson Processes](https://mlsanity.com/paper/2609.21858/) (2026)

## Abstract (arXiv)

Relative entropy coding (REC) algorithms encode a random sample following a target distribution Q, using a coding distribution P shared between the sender and receiver. Sadly, general REC algorithms suffer from prohibitive encoding times, at least on the order of 2^DKL[Q||P], and faster algorithms are limited to very specific settings. This work addresses this issue by introducing a REC scheme utilizing space partitioning to reduce runtime in practical scenarios. We provide theoretical analyses of our method and demonstrate its effectiveness with both toy examples and practical applications. Notably, our method successfully handles REC tasks with DKL[Q||P] about three times greater than what previous methods can manage, and reduces the bitrate by approximately 5-15% in VAE-based lossless compression on MNIST and INR-based lossy compression on CIFAR-10, compared to previous methods, significantly improving the practicality of REC for neural compression.