Measured on real embeddings

1The setup

Each method compresses 384 floats into 64 bits: a 192× reduction. Codebooks are trained on 63,120 windows and scored on the 23,490 windows of four other books. Recall is 10-recall@10 over 500 queries from yet other books, with no re-ranking.

Fig 4.8.1Every method at 64 bits

Read it left to right Each step down in error costs a step right in encode time. Hover for details. The pink points use the order of the windows, explained below.

2Five lessons

1. Freeing the codebooks helps most. From PQ to greedy RQ the error falls 25% for a few times the encode cost. A learned rotation (OPQ) recovers most of that gap by itself, which says PQ’s weakness is correlated blocks.

2. Better encoders give diminishing returns. A beam of 4 costs 3.7× greedy for 2.3% less error. A beam of 16 costs 15× and gains nothing on held-out books. LSQ gets 10% at 8×.

3. Squared error is not recall. Keeping the top 8 principal directions has only somewhat more error than PQ but half the recall (0.05 against 0.11). It throws away the many small directions that separate near neighbours.

4. Eight bytes for 384 dimensions is brutal. The best recall here is 0.24. That is a shortlist, not an answer. Real systems re-rank, and Priya will budget more than 8 bytes.

5. These embeddings are harder than older ones. The earlier write-up this book grew from ran the same benchmark on averaged word vectors and saw roughly a third less error at every step. A contrastively trained transformer spreads information over more directions (an effective dimension of 68), and that is exactly what makes it a better embedder and a worse compression target.

3A cheap trick that beats the expensive ones

Marginalia’s windows arrive in reading order, and consecutive windows have cosine 0.70. So instead of quantizing $x_t$ , quantize what the previous window did not already tell you:

\text{predict } \tilde x_t = \alpha\,\kdec{\hat x_{t-1}}, \qquad \text{code } \kres{e_t} = \kvec{x_t} - \tilde x_t \text{ with RQ}, \qquad \kdec{\hat x_t} = \tilde x_t + \hat e_t

Video encoders do not predict every block. They try both ways and keep the better one, paying a flag bit. Same here: code each window independently and predictively, keep whichever is closer.

0.538 greedy RQ, each window alone
0.525 always predict from the previous window
0.501 predict only when it helps (64% of windows)
0.525 beam 4, for comparison (3.7× the encode time)

With the per-window choice, locality buys 7% less error than greedy RQ at about twice its cost, more than any beam width achieved. And the two combine: the beam can encode the prediction errors too.

4What Priya takes away

PPriyaWEEK 6 · AFTER THE BENCHMARK

“So 8 bytes won’t cut it on its own, and going from greedy RQ to anything fancier is a rounding error next to going from 8 bytes to 16. We’ll take 16-byte RQ with a small beam in RAM, and re-rank the top couple of hundred against int8 vectors on SSD.”

At 16 bytes (128 bits) RQ’s error is 0.41 and its recall before re-ranking 0.31; at 32 bytes, 0.27 and 0.47.