Stochastic Likelihood Encoding for Data Compression

19 concepts7 papers1 proposal

In classical information theory and data compression, encoding is typically viewed as a deterministic search. To compress a message, an encoder searches a codebook for the single "best" match—whether that means finding a codeword within a discrete joint-typicality set or finding the exact maximum a posteriori (argmax) representation.

However, a powerful paradigm shift replaces this deterministic search with stochastic encoding. Instead of picking the single best codeword, a stochastic encoder treats the codebook as a probability distribution, sampling a codeword with a probability proportional to its likelihood or posterior weight. This approach smooths out discrete error boundaries into continuous probabilistic relationships, making complex communication networks mathematically tractable and enabling deep generative models to compress data at rates approaching the true theoretical optimum.


The Theoretical Foundation: The Likelihood Encoder

The mathematical foundation of this paradigm was formalized by Eva C. Song et al. in The likelihood encoder for lossy source compression. Traditionally, proving fundamental limits in lossy compression relied on "joint-typicality" arguments, which require manually counting discrete error events across a codebook. The authors introduced the likelihood encoder, a mechanism that stochastically selects a codeword index with a probability proportional to the likelihood of the source sequence given that codeword under a chosen test channel.

By framing encoding as a soft, random process rather than a hard search, the authors showed that error bounds could be derived directly from the properties of the probability distributions themselves, bypassing combinatorial proofs. In their follow-up work, The Likelihood Encoder for Lossy Compression, the authors demonstrated that this framework provides elegant, unified achievability proofs for classic network information theory problems (such as Wyner-Ziv and Berger-Tung coding), even when dealing with continuous alphabets.

Deterministic Encoding:  Source Data ───> [ Hard Search / Argmax ] ───> Best Codeword
Stochastic Encoding:     Source Data ───> [ Likelihood Sampling ]  ───> Probabilistic Codeword

This shift from hard selection to soft sampling also simplifies finite-blocklength analysis. Mohammad Reza Aref et al. leveraged this concept in A Technique for Deriving One-Shot Achievability Results in Network Information Theory. By replacing deterministic decoders with a probability distribution over the codebook, the authors derived unified "one-shot" achievability bounds for multi-user networks. Because the analysis relies on distribution behavior rather than rigid packing lemmas, the bounds seamlessly transition from finite-blocklength regimes to classical asymptotic limits.


Soft Decoding and Channel Simulation

The utility of soft, probabilistic selection extends from pure information-theoretic proofs to practical code design and channel simulation. When a system utilizes the full posterior probability distribution of bits rather than making hard block-level decisions, the mathematical analysis of error rates simplifies significantly.

For instance, in Comparing the Bit-MAP and Block-MAP Decoding Thresholds of Reed-Muller Codes on BMS Channels, Shrinivas Kudekar et al. analyzed decoding strategies that treat the decoder's output as a random variable based on posterior bit probabilities. This probabilistic approach allowed the authors to refine bounds on the weight distribution of Reed-Muller codes, proving their capacity-achieving robustness across binary symmetric memoryless channels.

A closely related problem is channel simulation—the task of making a clean channel behave exactly like a noisy one using a shared sequence of random bits. Sharang M. Sriramu et al. applied soft decoding to this problem in Fast Channel Simulation via Error-Correcting Codes. Their framework, PolarSim, uses a soft decoding mechanism at the encoder to evaluate inputs against shared randomness. This ensures that the simulated output adheres precisely to the target probability distribution while minimizing the required bitrate, achieving near-optimal simulation rates with high computational efficiency.


Bridging to Deep Learning: Importance Weighted Compression

While information theorists used stochastic encoding to simplify proofs, the machine learning community independently arrived at a similar concept when trying to compress data using deep generative models.

In Variational Autoencoders (VAEs), lossless compression is traditionally achieved via bits-back coding. The expected bitrate of standard bits-back coding is bounded by the Evidence Lower Bound (ELBO). However, the ELBO introduces a strict bitrate penalty equal to the Kullback-Leibler (KL) divergence between the approximate posterior and the true posterior. To get tighter bounds, researchers use Importance Weighted Autoencoders (IWAEs), which sample multiple latent variables to better approximate the true distribution.

Lucas Theis and Jonathan Ho bridged this gap in Importance weighted compression by demonstrating that the IWAE loss function is explicitly the mathematical cost of a stochastic compression scheme.

The authors introduced two key mechanisms to realize this:

  1. Softmin Coding (Lossy): Instead of picking a single latent state, the encoder generates multiple stochastic encodings and selects one using a softmin operation weighted by rate-distortion costs. The expected cost of this method directly aligns with the IWAE loss.
  2. Stochastic Bits-Back (Lossless): By treating the selection of importance samples as a stochastic transmission problem, the authors showed that bits-back coding can be adapted to IWAEs, allowing lossless compression costs to approach the theoretical optimum as more samples are added.

To push this to its asymptotic limit, Yangjun Ruan et al. developed McBits (Monte Carlo Bits-Back) in Improving Lossless Compression Rates via Monte Carlo Bits-Back Coding. By integrating Monte Carlo importance sampling directly into the bits-back framework, the authors demonstrated that as the number of importance samples increases, the compression rate asymptotically approaches the true marginal likelihood of the data, effectively eliminating the KL divergence penalty caused by imperfect variational posteriors.


Why It Works: The Intuition of Soft Selection

Why does stochastic likelihood encoding work so well across both mathematical proofs and practical compression algorithms?

  • Error Smoothing: In deterministic encoding, a small change in the input data can cause a discrete, chaotic jump to a completely different codeword, making error analysis highly discontinuous. Stochastic encoding maps inputs to codewords smoothly via probabilities. This allows researchers to bound errors using the smooth properties of distributions (like total variation distance or KL divergence) rather than combinatorial counting.
  • Averaging Out the Variational Gap: In deep learning compression, picking a single latent representation forces the model to pay a penalty for the mismatch between the proposal distribution and the true data distribution. By stochastically weighting or sampling multiple proposals (as in IWAE, softmin coding, or McBits), the encoder can dynamically adjust its choice. This effectively "averages out" the local sub-optimality of individual codewords, driving the empirical bitrate down to the true physical limit of the data source.

Key Foundational Work

The likelihood encoder for lossy source compression (2014) — contributed 2 concept elements to this direction.
A Technique for Deriving One-Shot Achievability Results in Network Information Theory (2013) — contributed 2 concept elements to this direction.
History & citationVersion 1 · 2026-10-04

Current · Permanent link

View frozen version 1

Cite this direction

Latest version (a living page):

@misc{lacuna_iwae_loss_as_compression_cost_bf3137c5,
  title = {IWAE loss as compression cost},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/iwae-loss-as-compression-cost/rdr_bf3137c5295a49e8bb2f1b6bc696705f},
  note = {Latest version of a living research direction; cite a version for a fixed text. Accessed 2026-11-20},
}

This exact version (version 1, frozen text):

@misc{lacuna_iwae_loss_as_compression_cost_bf3137c5_v1,
  title = {IWAE loss as compression cost},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/iwae-loss-as-compression-cost/rdr_bf3137c5295a49e8bb2f1b6bc696705f/v/1},
  note = {Version 1, frozen 2026-10-04. Accessed 2026-11-20},
}
About

These directions overlap with this one through shared papers.

See something wrong? Report a mistake