Asymmetric distance

Do not blur both sides

Search asks one question over and over: how far is the query from each stored vector? But the stored vectors are now codes, not real values. The naive fix is to quantize the query too and compare code to code. That throws away accuracy on both sides at once: the query gets rounded to its nearest level, the stored vector was already rounded, so you are comparing two blurred values. The better move is asymmetric (the two sides are treated differently on purpose): keep the query exactly as it is, and measure only to the stored vector's representative.

Drag the query below. The coral dashed line is the asymmetric estimate, measured to the stored point's centre; it stays close to the true grey line. The readout also shows the error if you had snapped the query too, which is consistently worse.

And it is fast

Asymmetric distance is not only more accurate, it is cheap to compute at scale. For a query, you precompute its distance to all 256 entries in each chunk's codebook once, building a small lookup table (a ready-made table of those precomputed distances). After that, any stored vector's estimated distance is just a handful of table lookups added together, one per chunk. Millions of comparisons become millions of cheap sums, no decompression required.

That is the whole reason compressed search is viable: the codes never have to be expanded back into vectors to be compared.

Key takeaways