Over-Fetch and Exact Reranking in Two-Stage Vector Retrieval

Every approximate index returns candidates selected by a proxy. The proxy might be a quantized distance, a graph traversal’s visited set, a hash bucket’s contents, or a coarse cluster’s posting list. The final answer must be produced by something more accurate than the proxy, and the gap between the two is bridged by fetching more candidates than the caller asked for and rescoring them exactly. The size of that over-fetch is the single parameter that decides whether the system meets its recall target or misses it while looking healthy.

The distinction between candidate recall and result recall

A two-stage system has two different recall numbers, and conflating them hides the failure.

Candidate recall is the fraction of true nearest neighbors that appear anywhere in the candidate list. If the exact top ten contains a document that the index never retrieved, no reranking can recover it, and the final result is wrong regardless of the reranker’s quality.

Result recall is the fraction of true nearest neighbors present in the final top ten. It is bounded above by candidate recall, and it equals candidate recall when the reranker’s ordering of the candidates matches the exact ordering of those same candidates. Since the reranker usually computes the exact distance, the second equality holds by construction: the reranker cannot reorder two candidates incorrectly if it scores them exactly. So for a pure distance-based system, result recall equals candidate recall, and the over-fetch exists solely to raise candidate recall.

That changes when the reranker is not a distance computation. A cross-encoder that scores query-document pairs jointly can produce a final ordering that differs from the distance ordering, and its own errors become part of the budget. For the distance-based case, which is the common one, the analysis is clean and the over-fetch can be sized from the index’s measured behavior.

The shape of the candidate-recall curve

Plot candidate recall at $k$ as a function of the candidate count $k’$ for a fixed query set. The curve starts at whatever the index achieves with a minimal fetch, rises steeply, and then flattens as it approaches one. The flattening point is where the index has found essentially everything it is going to find; further candidates add no recall and add work.

The curve’s initial value is set by the index’s quality, and its slope is set by the density of near-ties in the collection. A collection with many near-duplicate records has a flat top: the tenth and hundredth nearest neighbors may be nearly equidistant, so the ranking within that band is arbitrary and any candidate set that reaches into the band contains the same quality of results. A collection with distinct clusters has a steeper curve, because the true neighbors are separated from the rest and the index either finds them or does not.

The practical consequence is that $k’$ must be chosen from a measurement, not from a formula. The formula $k’ = \alpha k$ with a constant $\alpha$ is a starting point, and the value of $\alpha$ that reaches a target depends on the index, the collection, and the query distribution.

A reasonable procedure is to sample a few hundred queries, compute exact top-$k$ by brute force, and measure candidate recall at several $k’$ values. The smallest $k’$ that clears the target with margin is the operating point. It should be re-measured after any change to the index parameters, the embedding model, or the collection’s composition, because all three move the curve.

Why the over-fetch is not free

The cost of over-fetching has two components that scale differently.

The first is the index’s own cost, which grows roughly linearly in $k’$ for a scan-based index and sublinearly for a graph index, since a wider beam shares work across candidates. In an inverted file with product quantization, the scan is over a fixed number of probed cells and the candidate list is truncated at the end, so over-fetching within the scanned set is nearly free, since the codes are already in hand and the table lookups are already done, as described in Product Quantization and the Asymmetric Distance Computation. Widening $k’$ beyond the scanned set requires probing more cells, which is where the cost jumps; the cell count is the parameter examined in Coarse Quantization with Inverted Files and the nprobe Setting.

The second is the rerank cost, which is linear in $k’$ and expensive per candidate. Fetching the full vector for each candidate and computing an exact distance costs 3072 bytes and 768 multiply-accumulates for a 768-dimensional float32 vector. At $k’ = 1000$, that is three megabytes of vector data and 768,000 operations per query, a small fraction of a full scan but a large multiple of the index’s own cost if the index is a graph that visited a few hundred nodes.

The rerank cost also has a memory-access pattern problem. Candidates from a graph traversal are scattered across the collection, so fetching their full vectors is a random read per candidate if the vectors are not in memory. In a codes-in-RAM, vectors-on-disk arrangement, $k’ = 1000$ means a thousand random reads, which at device latency dominates everything else. This is why the over-fetch must be sized against the recall target rather than maximized: the last few percent of recall are bought at the highest cost per point.

import numpy as np

def two_stage(query, codes, codebooks, full_vectors, k=10, k_prime=200):
    """Cheap proxy scan over all codes, then exact rescoring of the shortlist."""
    m, kk, sub = codebooks.shape
    table = np.empty((m, kk), dtype=np.float32)
    for j in range(m):
        diff = codebooks[j] - query[j * sub:(j + 1) * sub]
        table[j] = (diff ** 2).sum(1)

    approx = table[np.arange(m)[None, :], codes].sum(1)      # one pass, no gathers of vectors
    shortlist = np.argpartition(approx, k_prime - 1)[:k_prime]

    exact = ((full_vectors[shortlist] - query) ** 2).sum(1)  # random access, expensive
    order = np.argsort(exact)[:k]
    return shortlist[order], approx[shortlist[order]], exact[order]

The function returns both the approximate and exact scores for the winners, which is useful for detecting a proxy that has drifted: if the two scores disagree systematically, the codebooks no longer represent the collection. It also assumes the query and the stored vectors share a normalization convention; mixing normalized and unnormalized data here produces a systematic offset of exactly the kind Cosine Similarity and the Geometry of Normalized Embedding Vectors warns about.

Calibrating the proxy against the exact score

The approximate score is not the exact score, and the difference between them has structure worth measuring. For product quantization, the approximate distance is the distance to the code’s reconstruction, and the reconstruction minimizes the distance to the record, not to the query. The error is therefore two-sided: a record whose code happens to sit nearer the query than the record does is scored too well, and one whose code sits farther is scored too poorly. Which records are favored depends on the query’s direction relative to the codebook’s Voronoi boundaries, so the bias is not a constant offset that a single correction removes.

A monotone mapping fitted from approximate to exact score on a sample of records removes the systematic component of the error and leaves the query-dependent part. Per-cell statistics help, since a cell’s codebook coverage is more homogeneous than the collection’s. Neither correction changes the candidate set, so neither recovers recall that the shortlist has already lost; they only improve the ordering within the shortlist.

The measurement that matters is the rank correlation between the approximate and exact orders within the candidate set. If the proxy’s top candidate is often not the exact top candidate, then a small $k’$ returns the wrong answer even though candidate recall is high: the right documents are present but the ordering is wrong, and the truncation to $k$ discards them. This is the case where the over-fetch must be large enough that the truncation does not cut into the region where the proxy’s ordering is unreliable.

A useful diagnostic: compute, for a sample of queries, the rank of the exact top-$k$ results in the proxy’s ordering. If the exact top result appears at proxy rank 40 with any regularity, then $k’ = 10$ truncates it away, and the over-fetch must be at least the 95th percentile of that rank distribution.

When the second stage is not a distance

Cross-encoder reranking replaces the exact distance with a learned scoring function applied to the query and each candidate jointly. It is far more expensive per candidate, a forward pass through a transformer rather than a dot product, so its candidate budget is much smaller, often in the tens rather than the hundreds. That makes candidate recall the binding constraint: the first stage must deliver the right documents into a short list, and the reranker’s quality is irrelevant if they are not there.

The first stage’s target therefore changes. When the second stage is exact distance, the target is “the true top ten are in the candidate set”. When the second stage is a learned reranker, the target is “the documents the reranker would rank highly are in the candidate set”, which is a different set and generally a larger one, because the reranker’s notion of relevance is broader than distance to the query embedding.

This is the point where the embedding model’s role becomes visible. If the first stage’s embedding was trained to make relevant documents close to the query, the two notions coincide and the short list works. If the embedding was trained for a different objective, or on a different notion of relevance, the short list is optimized for the wrong target and the reranker cannot compensate. The diagnostic is to measure recall of the reranker’s top results in the first stage’s candidate list; a shortfall indicates a mismatch between the stages rather than a parameter that needs widening.

The degenerate cases

An empty candidate list is possible when the filter, the probe count, or the traversal yields nothing. The rerank stage must handle it explicitly rather than indexing into an empty array; the filtered-query case where this arises most often is examined in Metadata Filtering Inside a Vector Index and the Selectivity Collapse.

Duplicate candidates are the second case. A graph traversal can reach the same node by multiple paths, and an inverted file with records assigned to multiple cells can return the same record twice. The rerank stage must deduplicate before truncating, or the final list contains repeated documents and fewer than $k$ distinct results.

A third is stale vectors. If the stored full vector has been updated but the code has not, the exact rescore and the proxy disagree, and the candidate selection was based on outdated data. Keeping codes and vectors in sync requires updating both on every write, and the failure is silent until recall degrades.

The final case is a query whose nearest neighbor is at the boundary of the collection’s distribution. The proxy’s error is largest there, because the codebook has few training examples in that region, and the exact top result may be far down the proxy’s ordering. Over-fetching enough to cover the tail is expensive; accepting lower recall for out-of-distribution queries is often the right trade, provided the response indicates it. A distance threshold on the final result, or a comparison of the top score against a calibrated expectation, gives the caller the information to distinguish a good match from a poor one.

The design conclusion is that the two stages must be measured together. Candidate recall, proxy rank correlation, and rerank cost form a triangle, and the over-fetch is the point chosen inside it. Choosing it from a default rather than from a measurement on the actual collection is how a system ends up with a recall number that looks acceptable in aggregate and fails on the queries that matter.