R4.5 · LESSON 5 OF 6

Reranking

Calculate vector-code storage and distinguish scalar, product and binary quantization from reranking.

THE IDEA

Reranking

A common pattern: search the compressed index cheaply for a generous shortlist (say 100 candidates), then rescore only those with the original vectors and keep the best k. Reranking 100 candidates costs 76,800 multiply-adds in 768 dimensions, against 768 million for an exact scan of a million vectors. But a rerank only reorders its shortlist: a relevant document that never entered it cannot come back.

shortlist size n (candidates reranked)2

id	approximate score	exact score	in shortlist?	true top-2?
0	9	1	yes
1	8	5	yes	yes
2	7	2	no
3	6	9	no	yes
4	5	3	no
5	4	4	no

shortlist by approximate score: [0, 1] rerank by exact score → top-2: [1, 0] true top-2: [3, 1] recall 0.5 id 3 never entered the shortlist, so no amount of exact reranking can recover it

At scale: reranking 100 candidates in 768 dimensions is 76,800 multiply-adds, against 768,000,000 for an exact scan of a million vectors (10,000× less).

Grow the shortlist until the true neighbours are inside it.

Predict first. Does exact reranking guarantee the exact global top-k when the candidates are incomplete?

Chapter context

Compressed vectors reduce storage and memory bandwidth, but approximate distance calculations can change rankings. Separate the compressed search representation from any original vectors retained for a later accurate rerank.

TRY IT YOURSELF

Part 1. Do it hands-on

Cost a rerank by hand, then build the shortlist and rerank pipeline and find the shortlist size that recovers the true neighbours.

shortlist size n (candidates reranked)2

id	approximate score	exact score	in shortlist?	true top-2?
0	9	1	yes
1	8	5	yes	yes
2	7	2	no
3	6	9	no	yes
4	5	3	no
5	4	4	no

shortlist by approximate score: [0, 1] rerank by exact score → top-2: [1, 0] true top-2: [3, 1] recall 0.5 id 3 never entered the shortlist, so no amount of exact reranking can recover it

At scale: reranking 100 candidates in 768 dimensions is 76,800 multiply-adds, against 768,000,000 for an exact scan of a million vectors (10,000× less).

rerank multiply-adds (100 × 768) full scan multiply-adds times less arithmetic recall with n = 2

To do: Compressed search returns 100 candidates; you rerank them with the original 768-d vectors. Multiply-adds for the rerank?
To do: An exact scan of 1,000,000 such vectors would need how many multiply-adds? (e.g. 7.68e8)
To do: So the rerank is about how many times less arithmetic than a full exact scan?
To do: Toy corpus: approximate scores [9,8,7,6,5,4], exact scores [1,5,2,9,3,4] for ids 0–5. Shortlist the top 2 by approximate score, rerank to the top 2 by exact score. recall of the true top-2 (ids 3 and 1)?

Part 2. Do it in code

shortlist(approx, n): ids of the n highest approximate scores (ties: lower id).
rerank(ids, exact, k): the k ids with the highest exact score among the shortlist (ties: lower id).
pipeline(approx, exact, n, k): shortlist then rerank.
pipeline_recall(approx, exact, n, k): the fraction of the true top-k (by exact score over ALL ids) that the pipeline returns.
min_shortlist(approx, exact, k): the smallest n whose pipeline recall is 1.0, or None.
rerank_ops(n, dim): multiply-adds for the rerank (n · dim); full_scan_ops(total, dim).

def shortlist(approx, n):
    pass

def rerank(ids, exact, k):
    pass

def pipeline(approx, exact, n, k):
    pass

def pipeline_recall(approx, exact, n, k):
    pass

def min_shortlist(approx, exact, k):
    pass

def rerank_ops(n, dim):
    pass

def full_scan_ops(total, dim):
    pass

Ctrl/⌘ + Enter runs it

Stuck, or something not working? You can come back to it any time.

CHECK YOUR UNDERSTANDING

Does exact reranking guarantee exact global top-k when candidates are incomplete?

AYesBNo

Chapter reference: math, worked example & code

This section belongs to the whole chapter, so it is the same on every lesson in it and may cover a different lesson's topic. The code for the experiment you just ran is inside the experiment itself.

Math and notation

For d float32 coordinates, raw vector bytes are 4d. For M PQ subspaces and b bits per subspace, code bytes are $Mb/8$ when packed. For equal-size subspaces, float32 codebooks total $2^b d\times4$ bytes, excluding additional index data.

Worked example

A 768D float32 vector uses 768×4=3072 bytes. With 96 subspaces and 8-bit codes it uses 96 bytes: 32 times smaller for the per-vector representation. The shared codebooks contain 256×768 float32 values, requiring 786,432 bytes. Original vectors retained for reranking are an additional cost.

Reference code

The following example uses the Python standard library and does not call a remote service.

dimension,parts,bits=768,96,8
raw=dimension*4
code=parts*bits//8
book=(2**bits)*dimension*4
assert raw == 3072 and code == 96
assert raw/code == 32
assert book == 786432
assert sum(a!=b for a,b in zip('1010','1111')) == 2

Python examples are provided for study and local execution; this page does not execute Python.

Common mistakes

Compression ratio for code bytes is not the total-system ratio. PQ codes are indices into learned representatives, not simply truncated float bits. Reranking cannot find missing candidates.