Article

Accuracy Recovery with Rescoring

· 4 min read

1. Introduction

When we use quantization methods like scalar, binary, or product quantization, we are compressing our vectors to save memory and improve performance.

However, this compression can slightly reduce the accuracy of our similarity searches, because the quantized vectors are only approximations of our original data. A faster search is not very useful if the results it returns are noticeably worse.

So, to mitigate this loss of accuracy, you can use a combination of three techniques: oversampling, rescoring, and reranking. Together, they help recover much of the accuracy that quantization gives up, without sacrificing all of its speed benefits.

2. Oversampling

Let's say you are performing a search in a collection that uses binary quantization. The database retrieves the top candidates using the quantized vectors, based on their similarity to the query vector as determined by the quantized data. This part of the search is fast, precisely because it relies on the compressed vectors.

brief description

But since some relevant matches could be missed in this initial search, we apply oversampling to compensate. Oversampling means retrieving more vectors, more candidates than you actually need, which increases the chances that the most relevant vectors make it into the final results.

For example, if your desired number of results is four, and you set an oversampling factor of two, the database will retrieve eight candidates instead of four:

4 × 2 = 8 candidates

brief description

More candidates mean a better chance of containing higher-quality results once the final ranking is decided.

3. Rescoring

After oversampling gathers a larger pool of potential matches, each candidate is re-evaluated based on additional criteria, to ensure higher relevance to the query. This re-evaluation step is what we call rescoring.

Rescoring works by mapping the quantized vectors back to their corresponding original, uncompressed vectors. This allows the system to consider additional precision and sometimes additional context or metadata that wasn't fully captured in the initial quantized search. Because the comparison now happens against the original vectors, this step leads to noticeably more accurate results.

brief description

Interestingly, during this rescoring process, one of the lower-ranked candidates pulled in by oversampling might actually turn out to be a better match than some of the original top-k candidates that would have been chosen without oversampling at all.

And even though rescoring uses the original, larger vectors, the overall process still remains very fast, because only a small portion of the vectors, the oversampled candidates are being compared, not the entire dataset.

4. Reranking

With the new similarity scores produced by rescoring, reranking is the step where the final top candidates are determined based on these updated scores, rather than the original quantized ones.

For example, suppose we're retrieving a top-k of four with an oversampling factor of two. A candidate that was ranked 8th in the initial quantized search might improve its score after rescoring, simply because the original vectors capture more context than the quantized ones.

brief description

As a result, this candidate could move into the final top-k after reranking, replacing a less relevant option that had originally made the cut.

5. Conclusion

If quantization is affecting performance in an application that still needs high accuracy, combining it with oversampling, rescoring, and reranking is a great strategy. It lets you keep most of the speed and memory benefits of quantization while recovering much of the accuracy you would otherwise lose.

That said, this approach does increase the latency of each query, since more candidates are retrieved and more comparisons are made against the original vectors. So if you need faster searches and can tolerate some loss in accuracy, you might choose oversampling without rescoring, or simply adjust the oversampling factor to find the right balance for your use case.