Rate-Distortion Theory

Entropy answers how many bits a source needs when you must reconstruct it exactly. Almost nothing in machine learning needs exact reconstruction. Quantising a weight matrix to 4 bits, evicting 80 percent of a KV cache, dropping half the tokens in a prompt, distilling a 70B model into an 8B one: each throws information away deliberately and asks only that the output stay close enough. The theory of close enough is rate-distortion, and Shannon wrote it down in 1959, eleven years after the source coding theorem (Shannon, 1959, Coding Theorems for a Discrete Source with a Fidelity Criterion, IRE Int. Conv. Rec. 7:142-163).

The function

Fix a source \(X\) with distribution \(p(x)\), a reconstruction alphabet \(\hat{X}\), and a distortion measure \(d(x, \hat{x}) \ge 0\) that says how bad it is to reproduce \(x\) as \(\hat{x}\). The rate-distortion function is

Read it as a constrained optimisation over channels. You are free to design any stochastic map from source to reconstruction, subject to average distortion at most \(D\). Among all such maps, \(R(D)\) is the smallest mutual information any of them carries. Shannon's theorem says that number is exactly the asymptotically achievable rate in bits per symbol: no code beats it, and codes approaching it exist.

Three properties do most of the practical work. \(R(D)\) is non-increasing in \(D\), so more tolerance never costs more bits. It is convex, which is why the interesting operating points sit at the knee and why mixing two codecs cannot beat the curve. And \(R(0) = H(X)\) for a discrete source under a distortion measure that is zero only on exact matches, so lossless coding is the left endpoint of the same curve, not a different problem.

For a Gaussian source with squared-error distortion the function is closed-form and worth memorising:

Invert it and the consequence is stark: \(D = \sigma^2 2^{-2R}\), so every extra bit quarters the achievable squared error and halves the RMS error. That factor of four per bit is the origin of the "6 dB per bit" rule of thumb in signal processing, and it is why quantisation error falls geometrically rather than linearly as you add bits.

Computing it, and why nobody does

The minimisation has an alternating algorithm, discovered independently by Blahut and Arimoto in 1972, that converges to the true \(R(D)\) for a known discrete source. It is the exact analogue of the Blahut-Arimoto algorithm for channel capacity, run in the other direction.

In practice nobody computes \(R(D)\) for a neural network, because \(p(x)\) over weight matrices or activation tensors is unknown and enormous. What survives into practice is the shape of the argument: pick a distortion measure that matches what you care about, then measure your own achieved (rate, distortion) pairs and check whether a competing method dominates yours. A method that is strictly below another's curve everywhere is better; a method that crosses is better only in a region, and the crossing point is the engineering decision.

Choosing the distortion measure is the whole game

This is where rate-distortion analysis of neural systems usually goes wrong. Squared error on weights is convenient and nearly meaningless: two quantisers with identical weight MSE can differ by several points of downstream accuracy, because the error that matters is error in the function, not in the parameters.

Better distortion measures used in practice:

• Layer output error, \(\|W x - \hat{W} x\|^2\) over a calibration set, which is what GPTQ and similar second-order methods actually minimise. It weights weight-error by input covariance, so directions the data never excites are free to be wrong.
• KL divergence to the original model's output distribution, which is the natural measure when the deliverable is a distribution rather than an argmax, and the one distillation optimises.
• Task loss on a held-out set, which is the honest measure and the most expensive to evaluate.

The variational autoencoder makes the connection explicit: the ELBO decomposes into a rate term and a distortion term, and models with identical ELBO can sit at completely different points on the rate-distortion plane, with correspondingly different behaviour (Alemi et al., 2018, Fixing a Broken ELBO, arXiv:1711.00464). Optimising the sum tells you nothing about where on the curve you land.

When it breaks

The theory is asymptotic in block length. It promises that codes approaching \(R(D)\) exist for long enough sequences; it says nothing about a single 4096-by-4096 matrix quantised element-wise, where the achievable rate can be far above the bound. Vector quantisation closes part of that gap, which is exactly the argument behind lattice codebooks in modern LLM quantisers.

It also assumes a known, stationary source. Weight distributions shift across layers, and activation distributions shift with the input, which is why per-channel and per-group scales beat a single global scale by more than the extra scale parameters cost.

Finally, average distortion is a weak guarantee. \(\mathbb{E}[d] \le D\) permits rare catastrophic errors, and rare catastrophic errors are precisely what a user notices. Practical compression work almost always ends up constraining a tail quantile too, at which point you have left Shannon's formulation and are doing something empirical. See language modelling as compression for the lossless half of this story.