Composite indexes: coarse filter, exact rescore

Real index configurations have names like a formula — a coarse quantizer, a compression scheme, a rescoring step, sometimes a graph over the top. They look like a menu of unrelated options. They are all instances of one pattern, applied once or several times over, and once you see the pattern the configurations stop needing to be memorised.

The naive approach

Pick the best single index and use it. A graph if you have memory, a cluster index if you don’t, with quantization if the vectors won’t fit.

How it fails: each family’s weakness is exactly where another’s strength is, and the weaknesses are not the same shape.

A graph index gives excellent recall per unit of latency and demands that everything be memory-resident for random access. A cluster index tolerates disk and pays for it with a coarse partition and boundary misses. Quantization solves memory and costs distance accuracy. Choosing one means accepting its weakness at full strength.

But notice the shapes. Quantization’s error is in the distances, and it is small — enough to disturb the ordering of near-ties, rarely enough to move a genuinely close vector far down the ranking. A cluster index’s error is in which candidates get examined, and it is coarse. Those are different failures, and a technique whose errors are small and pervasive can be made harmless by a technique that fixes ordering, while a technique whose errors are coarse can be compensated by examining more.

The pattern

Use a cheap, approximate mechanism to produce a candidate set. Then compute exact distances over the candidates only, and rank by those.

search(query, k, oversample):
    candidates ← cheap_stage(query, n = k × oversample)     # approximate, fast, wide
    scored     ← [ (c, exact_distance(query, c)) for c in candidates ]
    return top k of scored

The division of labour is total, and each stage has one job:

The cheap stage needs recall, not precision. Its only obligation is to include the right answers somewhere in its output. Their order within the candidate list is irrelevant, and false positives cost only a rescoring computation each. It is allowed to be badly wrong about ordering; it must not be wrong about membership.

The exact stage needs precision, not recall. It cannot add anything the cheap stage missed — a rescorer can only reorder what it was handed. But over what it was handed, its answer is exact.

That asymmetry is why the pattern works. Compression that would be unacceptable as a final ranking is perfectly acceptable as a filter, because the filter’s errors are the kind the second stage repairs, and the second stage is cheap because the candidate list is small.

The knob joining them is the oversampling factor. Retrieve k × 10 and rescore, and you tolerate a cheap stage that puts the right answer anywhere in its top ten times k. It is a runtime parameter, it moves you along the recall-latency curve without a rebuild, and it is the cheapest knob in a compressed index.

The standard combinations, read as instances

Every configuration below is the same two lines with different stages.

IVF-Flat. Cheap stage: the centroid comparison, which selects nprobe cells. Exact stage: a full scan of those cells with true distances. The approximation is entirely in cell selection.

IVF-PQ. Cheap stage: centroid comparison and compressed distance computation over the cells’ residual codes. Exact stage: rescore the finalists from full-precision vectors. Two layers of approximation, one rescore. This is the workhorse at very large scale, and the reason it beats an uncompressed index there is not that compression is good — it is that the alternative was serving uncompressed vectors from storage, which is far worse than serving compressed ones from memory.

Binary-then-exact. Cheap stage: Hamming distance over one-bit-per-dimension codes, which is a couple of instructions per 64 dimensions. Exact stage: full-precision rescore of a generous candidate list. The first stage is so cheap that a large oversampling factor is affordable, which is what makes an extremely lossy code viable.

HNSW as the coarse quantizer. Here is the one that surprises people, and it is the clearest illustration that the stages are interchangeable parts. A cluster index’s first stage compares the query against every centroid — linear in nlist, and nlist can be large. That first stage is itself a nearest-neighbour problem over the centroid list. So: index the centroids with a graph. Now selecting cells is a graph search rather than a scan, and nlist can grow far beyond what a linear scan tolerates, giving smaller cells and a finer partition. An index is being used as a component of another index’s coarse stage, and the pattern has nested.

Graph over quantized vectors, with rescoring. Build the graph, but store compressed vectors and traverse using approximate distances, then rescore the final candidates exactly. The graph’s memory problem is attacked directly. The cost is subtle and worth naming: the traversal decisions are now made on approximate distances, so the walk itself can take wrong turns — unlike a cluster index, where compression only affects scoring within a scan. Errors in navigation are not repaired by rescoring, because rescoring only reorders what the walk found.

Two-level partitioning for disk residency. A small in-memory structure routes to a modest number of large, contiguous partitions; each probed partition is read sequentially and scanned. Cheap stage in memory, exact stage from storage, with the partition layout arranged so a probe is one sequential read rather than many random ones. This is the pattern deliberately arranged around the cost structure of the storage device rather than around the cost of arithmetic.

What every instance must respect

Three constraints follow from the pattern itself, and getting any of them wrong breaks the design in a way that looks like a tuning problem.

The exact stage needs the exact data. Rescoring requires full-precision vectors for the candidates. If you compressed and discarded the originals, there is nothing to rescore from and the compressed distances are your final answer. So quantization reduces your memory footprint, not your total storage — the originals live somewhere, fetched for a few hundred candidates per query, which is a bounded number of reads rather than a traversal. A configuration that compresses and discards is a different, weaker design than one that compresses and rescores, and the difference does not show up until you measure recall.

A rescorer cannot recover a miss. This is the constraint that decides where to spend effort. If the cheap stage never surfaced the right vector, no downstream stage brings it back. Which means: tune the cheap stage for recall of the candidate set, and never for the precision of its ordering. Effort spent making the first stage rank better is wasted; effort spent making it include more is not.

Nested stages multiply their misses. Each approximate stage has its own recall, and the recall of the composition is the product. Two stages at 0.9 give roughly 0.81 before the exact stage sees anything, and the exact stage cannot lift that. This is why deep stacks of approximation are inadvisable and why diagnosing a composite index means measuring the stages separately: total recall tells you something is wrong, per-stage recall tells you which stage.

That last point is the practical technique worth extracting. To measure a stage in isolation, compare its candidate set against the exact answer for the same query. Does the true nearest neighbour appear anywhere in the cheap stage’s output? If yes, the cheap stage did its job and any remaining error is in the rescore budget or the final k. If no, oversampling and rescoring are irrelevant and the cheap stage is the thing to change.

Why the pattern is everywhere

Because it decouples two requirements that pull in opposite directions. Accuracy wants full-precision data and exhaustive comparison. Speed wants compact data and minimal comparisons. You cannot have both over the whole collection — but you can have compact-and-minimal over the collection and full-and-exhaustive over a few hundred candidates, and the composition inherits the cost of the first and much of the accuracy of the second.

It also explains what “approximate” is actually approximating in a modern index. Not the arithmetic — the finalists are compared exactly. The approximation is entirely in which candidates were nominated, at every stage, and every mechanism on this site is a different way of nominating them.