Two-Stage Search with Compressed Candidates and Exact Rescoring

A 96-byte code cannot reliably tell rank 10 from rank 30. That sounds fatal and is not, because the compressed stage does not have to rank correctly. It only has to put the true answers somewhere inside a shortlist that something more accurate will then reorder. Recall at depth 100 is a far weaker requirement than recall at depth 10, and the gap between those two quantities is where almost all practical compression gain lives.

Why one stage cannot work

Routing errors and quantisation errors are recoverable in different ways, and only one of them is recoverable by spending time. If the router never visits the true nearest neighbour, raising efSearch or nprobe visits more of the corpus and eventually visits it. If the router does visit it but the compressed code scores it below a decoy, further probing cannot help: the comparison itself is wrong, and wrong identically every time. More candidates then make matters worse, because each additional candidate is another chance for a decoy to beat the real answer.

So compression imposes a ceiling, and the only ways through it are a larger code or a second, more accurate scoring pass. RaBitQ's authors say this directly about aggressive quantisation, that it "can hardly produce reasonable recall" without re-ranking (Gao & Long, SIGMOD 2024). FAISS encodes the same conclusion structurally, wrapping compressed indexes in a Refine(...) component and recommending OPQ-plus-4-bit-PQ with refinement at its memory-constrained branches (FAISS wiki, Guidelines to choose an index). pgvector's binary-quantisation recipe states plainly that re-ranking with the original vectors improves recall (pgvector README).

k_factor, the parameter nobody sizes

The rescore stage takes the compressed stage's top \(k \times \text{k\_factor}\) candidates and recomputes exact distances on them. At k_factor = 1 the pass is decorative: it reorders the \(k\) results the compressed stage already chose, and cannot introduce the candidate it ranked \(k+1\). At 100 it is a second search.

The right value follows from one measurement nobody takes: the compressed stage's recall at depth \(k \times \text{k\_factor}\). Measure that curve once and the parameter picks itself. A worked shape, for 50M 768-dimensional vectors with OPQ96,IVF,PQ96: at k_factor = 10 the rescorer handles 100 candidates, costing about 77 kFLOP plus 100 random reads of 3,072 bytes each. Served from NVMe at queue depth 32, that is well under a millisecond, and it is typically worth more recall than several doublings of the probe budget.

DiskANN: the rescore is the architecture

DiskANN's design makes the two stages a memory-tiering decision. Compressed codes stay in RAM and are used only for navigation; full-precision vectors live on SSD and are read for the candidates that need exact scoring, with the reads prefetched so I/O overlaps traversal. The reported result is a billion points served from one 64 GB workstation at over 5,000 QPS, mean latency under 3 ms, and 95%+ 1-recall@1 on SIFT1B, where FAISS and IVFOADC+G+P at comparable memory footprint levelled off near 50% 1-recall@1 (Subramanya et al., NeurIPS 2019).

That 50-versus-95 comparison is the clearest published evidence for the whole idea. The systems had comparable routers and comparable memory budgets; what differed was whether anything exact ever saw the candidates.

When it breaks

The full vectors have to exist somewhere. A deployment that compressed its only copy has no rescore available at any price, and discovers this after recall has already plateaued.

Latency moves from compute-bound to I/O-bound, which changes what tuning means. One hundred serialised 100 µs page reads is 10 ms; the same reads at queue depth 32 are closer to half a millisecond. If the rescore path does not issue reads concurrently, the stage will look far more expensive than it is.

Finally, two stages mean two places recall can be lost, and the usual instinct is to blame the wrong one. Instrument them separately: measure the compressed stage's recall at shortlist depth, and the rescorer's agreement with exact search on that shortlist. Without that split, every recall incident becomes a guess.