Lesson 4.3
Re-ranking the candidates
The compressed search gets you a rough shortlist fast. A quick exact re-score of just that shortlist buys most of the lost recall back.
Rough first, exact second
Compressed distances are estimates, so the top few they return are sometimes slightly wrong. The standard cure is a two-pass search. First pass: use the fast compressed estimates to pull a shortlist of, say, the top 50 candidates (the rough best guesses, roughly right but not yet trustworthy). Second pass: re-score just those 50 with exact distances, using the full vectors, and keep the real top few. The exact pass is expensive per comparison, but you only run it on a tiny shortlist, so it is cheap overall.
Below, with re-ranking off, the rough shortlist misses a true neighbour or two (shown in coral). Turn re-ranking on and grow the shortlist N: the exact re-score pulls the true top-4 back in, and recall climbs toward a perfect 1.0.
Grow the shortlist, then re-rank it exactly
recall@4 --
true neighbour, found true, missed returned, wrong
Re-ranking takes a shortlist from the fast compressed search, re-scores it with exact distances, and keeps the true top-k (the k best results you actually want to return). Most lost recall comes back for very little extra work.
The catch, and the balance
Re-ranking needs the full vectors on hand for the second pass, so you keep them somewhere cheaper, on disk or in slower memory, away from the compressed codes that drive the fast first pass. The shortlist size N is the dial: too small and a true neighbour never makes the shortlist to be rescued; too large and the exact pass starts to cost real time. A little re-ranking is one of the best deals in the whole pipeline.
Key takeaways
Re-ranking re-scores a small compressed shortlist with exact distances to recover the true top-k.
It recovers most of the recall lost to compression for very little extra compute.
The shortlist size N is the dial: too small misses neighbours, too large costs time.