Why do quantized vector indexes rescore a shortlist against full-precision vectors?

## The observation rescoring is built on Quantization error is not uniformly harmful. A compressed distance is good enough to answer "is this vector roughly in the right neighbourhood?" and bad at answering "which of these five is closest?" — the residual you threw away is on the same order as the gaps that separate top candidates. That asymmetry is exploitable: use the cheap representation for the coarse question, and the expensive representation only for the fine one, on a handful of candidates. ## The two-pass shape 1. **Shortlist.** Search the compressed index for the top `k * oversample` candidates. With binary codes this is a XOR and a popcount per candidate, running over a corpus that now fits in cache-friendly memory. With PQ codes it is a sum of lookups. 2. **Rescore.** Fetch the original vectors for exactly those candidates, compute the true distance for each, sort, and return the top k. The second pass touches maybe 200 vectors out of a billion, so its arithmetic cost is negligible. What it costs is *access*: 200 lookups into whatever store holds the full-precision vectors. ## A concrete configuration A common high-compression setup: binary quantization at one bit per dimension gives a 32x reduction, so 768-dimension vectors go from 3 KB to 96 bytes and a very large corpus becomes RAM-resident. Hamming scan produces the top 200. Full float32 vectors live on SSD or memory-mapped from disk — they are never needed for the scan, only for 200 reads. The float rescore reorders those 200, and the final top 10 is close to what exact search would have returned. Recall that would have been mediocre on binary codes alone typically climbs back into the high nineties. ## Tuning the oversampling factor This is the single knob, and it behaves like nprobe: sweep it and read the knee. - Below the knee, recall is capped by the shortlist itself. If the true nearest neighbour is ranked 340th by the compressed distance and you only retrieved 200, rescoring cannot help — the candidate was never in the room. This is the most common misconfiguration. - Above the knee, recall flattens and you are paying fetch latency for nothing. The right factor depends on how lossy the first pass is: binary codes need a much larger multiple (often 10x-30x of k) than an 8-bit scalar-quantized pass (often 2x-4x). Measure against exact ground truth on real queries; the value does not transfer between embedding models. ## Where the full vectors live, and what that costs Rescoring has a hard prerequisite that people forget when they design for minimum footprint: **the originals must still exist.** If you deleted the float vectors after encoding, the compressed ranking is the only ranking you will ever have. The placement choice is a real one: - **In RAM** — fastest, but then you are paying the memory you were trying to save. Sensible only if compression was for speed rather than capacity. - **On SSD / memory-mapped** — the usual answer. Random 3 KB reads at a few hundred per query are well within NVMe capability, and the OS page cache keeps hot vectors resident. Adds perhaps single-digit milliseconds. - **In a separate service or object store** — workable in batch, usually too slow for interactive traffic because of per-fetch round-trips. ## Cascades The pattern generalizes to more than two tiers: a binary Hamming pass to a few thousand, a PQ pass to a few hundred, then a float rescore to k. Each tier is cheaper per candidate and less accurate than the next, and each one's oversampling factor is tuned so the true neighbours survive to the following stage. The same logic reappears one layer up in retrieval systems that follow vector search with a heavier reranker — cheap recall first, expensive precision last. ## How to tell it is misconfigured The diagnostic signature is distinctive: recall is capped no matter how much you raise the first-pass effort, because the ceiling is the shortlist size, not the scan. Conversely, if raising the oversampling factor moves recall not at all, your first-pass representation is better than you assumed and you can shrink the shortlist to reclaim latency. Always evaluate recall@k of the *final* output against exact search, never the recall of the shortlist stage in isolation.