From spectrum to bit budget

1The rule

Rotate the data onto its principal directions. Direction $i$ now has variance $\lambda_i$ : its bar in the spectrum. For bell-shaped data, rate–distortion theory gives the best possible way to split a bit budget among the directions. It is called reverse water-filling.

Pick a water level $\kbook{\theta}$ .
Give direction $i$ about $\tfrac12 \log_2(\lambda_i/\theta)$ bits.
Directions whose bar is below the water get zero bits.

\kbits{R} \;=\; \sum_{i\,:\,\lambda_i > \theta} \tfrac12 \log_2\frac{\lambda_i}{\kbook{\theta}} \qquad\qquad \kres{D} \;=\; \sum_i \min(\lambda_i,\ \kbook{\theta})

Big bars get many bits, small bars a few, tiny bars none. After coding, every direction that got bits has the same leftover error $\theta$ , and every direction that did not is lost entirely.

Fig 3.4.1Reverse water-filling

Drag the budget This is the real spectrum of the embeddings. The lime part of each bar is what gets described; the faded red part is the error that remains. At 8 bytes, how many directions get anything at all?

2“Keep the top 8 dimensions” is a crude version of this

Truncating to the top 8 principal directions and storing each as int8 spends 8 bits on each of 8 directions and nothing on the rest. Water-filling says that is the wrong shape:

the 9th direction is almost as important as the 8th, and gets zero;
the 1st gets 8 bits when it deserves about 3.

3How good can transform + scalar get?

For Gaussian data, PCA + scalar quantization + the right allocation gets close to the theoretical best at moderate and high rates. The remaining gap is small and fixed:

A quarter of a bit is nothing if you are spending 8 bits per dimension. It is ruinous if your whole budget is 0.2.

4So why does anyone use vector quantization?

Two reasons, and both are visible in measurements.

Very low rates At 8 bytes for 384 dimensions you have about 0.17 bits per dimension. A scalar quantizer cannot spend a fraction of a bit on a coordinate. A vector quantizer spends bits on whole vectors, so it can.
Data that is not one bell Embeddings form clusters: topics, genres, languages. PCA only sees the ellipse around the whole cloud. A codebook can put its points right on the clusters.

Fig 3.4.2Error against bits, measured

Measured, from 4 bytes to 384 bytes Each dot is a full train-and-evaluate run on held-out books. The dashed line is the Gaussian bound from water-filling. Switch to recall to see what the error means for search.

Read the chart from left to right:

Left (under 128 bits): vector quantizers lead. At 64 bits RQ reaches 0.54 against 0.60 for PCA + scalar and 0.71 for plain PQ.
Middle (about 1 bit per dimension): everything converges. At 512 bits OPQ, PCA + scalar and RQ are at 0.11, 0.12 and 0.13.
Right (several bits per dimension): plain scalar quantization of the raw coordinates is as good as anything, needs no training and is trivial to run. That is why many vector databases simply ship int8.

5What to read for the theory

Goyal, “Theoretical Foundations of Transform Coding” (IEEE Signal Processing Magazine, 2001). Exactly this page’s question.
Cover and Thomas, Elements of Information Theory, the rate–distortion chapter. Reverse water-filling comes from here.
Gersho and Gray, Vector Quantization and Signal Compression. The deep dive on layer 2.