In neural data compression, the standard approach involves quantizing continuous latent variables into discrete buckets. This process is often considered a "hacky" workaround because it introduces non-differentiable operations and quantization noise that researchers must compensate for during training.
Relative Entropy Coding (REC) offers a theoretically elegant alternative: a way to communicate a sample from a target distribution using only a shared prior, without ever explicitly quantizing the data. While long considered the "holy grail" of learned compression, REC was historically impractical due to runtimes that scaled exponentially with the information being transmitted.
A series of recent breakthroughs, led by Gergely Flamich, Stratis Markou, and José Miguel Hernández-Lobato, has transformed REC from a theoretical curiosity into a practical tool by reframing the sampling process as an efficient search problem.
The Communication Game
To understand REC, imagine Alice wants to send a specific sample $x$ to Bob. They both have access to a shared source of randomness (a prior distribution $P$). Alice’s goal is to pick a sample from this shared randomness that looks like it came from her target distribution $Q$, and then tell Bob which sample she picked.
The simplest way to do this is Rejection Sampling. Alice iterates through samples $x_1, x_2, ...$ from the prior until she finds one that satisfies a rejection criterion based on the density ratio $d(x) = q(x)/p(x)$. Once she finds a valid sample at index $i$, she sends the index $i$ to Bob. Bob, using the same random seed, generates the same sequence and picks the $i$-th sample.
The problem is the "waiting time." If the target distribution $Q$ is very different from the prior $P$, the probability of accepting a sample is tiny. Alice might have to check an astronomical number of samples, leading to the exponential runtime bottleneck that plagued early REC methods.
From Sampling to Search
The key insight in Fast Relative Entropy Coding with A* coding is that Alice does not need to check every sample linearly. Instead, the authors treat the space of possible samples as a tree that can be searched.
By using A* search and branch-and-bound techniques, Alice can prune large regions of the sample space. If she knows that a certain branch of the tree (representing a sub-region of the distribution) has a maximum density ratio that is too low to yield a valid sample, she can skip that entire branch. This optimization shifts the computational complexity from scaling exponentially to scaling linearly with the divergence between the distributions.
Pruning with Unimodality
The efficiency of these search-based methods relies on how well Alice can bound the density ratios. In Greedy Poisson Rejection Sampling (GPRS), Gergely Flamich demonstrates that for unimodal one-dimensional distributions, the search space can be pruned even more aggressively.
By reimagining rejection sampling as a greedy search over a Poisson process, GPRS achieves optimal runtime. The algorithm focuses its computational budget on regions where the density ratio is highest, effectively "skipping" the vacuum between meaningful samples.
Scaling to High Dimensions
While A* coding solved the exponential runtime for low-dimensional problems, high-dimensional latent spaces in neural networks still posed a challenge. The density ratio (the "infinity divergence") can be massive even if the average information gain (the KL divergence) is small.
In Faster Relative Entropy Coding with Greedy Rejection Coding, the researchers introduced space partitioning techniques that allow the expected search complexity to scale with the Kullback-Leibler (KL) divergence rather than the much larger infinity divergence.
This is a critical distinction:
- Infinity Divergence ($D_\infty$): Represents the worst-case ratio between distributions.
- KL Divergence ($D_{KL}$): Represents the average information content.
By ensuring runtime scales with $D_{KL}$, these algorithms remain fast even when the target and prior distributions have heavy tails or significant mismatches in specific regions, provided the total information transmitted remains reasonable.
Why It Works: The Heap Indexing Trick
A final piece of the puzzle is how to turn the search result into bits. The researchers utilize heap indexing: the position of the selected sample in the search tree or the sequence of the Poisson process serves as the compressed bitstring. Because the search process is deterministic given the shared seed, the index itself is a uniquely decodable code.
This transforms the act of finding a sample into the act of encoding a message, providing a seamless, quantization-free bridge between continuous neural representations and discrete digital communication.