Approximate nearest neighbour
An embedding is only useful if you can find its neighbours fast. Exact search is the honest baseline, not a strawman: brute force over a million vectors is correct and far too slow, so every production store replaces it with a structure that is probably right. This part builds HNSW's layered graph by hand, watches a query descend it, then places the whole index zoo on the same four axes — recall, latency, memory and build cost — before confronting the case that breaks them all: a filter.
Exact search is the baseline
Correct, simple, and the thing you measure against
Exact nearest-neighbour search — "flat" — computes a distance from the query to every vector and takes the top k. It has no recall parameter because its recall is 1.0 by construction, it has no build step, and its cost is linear in the corpus. That makes it the reference every approximation must be measured against, and the answer for small corpora: below a few tens of thousands of vectors, a flat index is fast enough and you should stop optimising.
Above that, the arithmetic turns. A million vectors at 1,536 dimensions is six gigabytes in float32 and a million distance computations per query — fine on a GPU, hopeless on a request path. Approximate algorithms accept a recall below 1.0 in exchange for not visiting everything. The only meaningful question is how much recall, at what latency, at what memory cost, and how long the build takes — four axes, and they trade against each other.
The index families
Partition, compress, or link
Every ANN structure is one or more of three ideas: partition the space so a query can ignore most of it, compress the vectors so more fit in memory and each comparison is cheaper, or link the vectors into a graph that can be navigated greedily. The families combine them.
| Family | The idea | Where it wins |
|---|---|---|
| Flat (exact) | Scan everything. | Small corpora; the ground truth you measure against. |
| IVF | k-means into nlist cells; probe the nearest nprobe. | Large corpora where a few cells hold the answer. |
| IVF + PQ | Compress each residual into product-quantisation codes. | Memory-constrained: keep the whole index resident. |
| HNSW | A multi-layer navigable graph; greedy descent then a bounded layer-0 search. | Low latency and high recall when memory is available. |
| ScaNN | Anisotropic quantisation tuned for inner-product search. | Recall-optimised compressed indexes. |
| DiskANN / Vamana | A graph designed to live on SSD with a single pass. | Billions of vectors on one node; memory too small for the graph. |
The rest of this part turns each of those rows into something you can see: HNSW's graph and its search trace, IVF-PQ's cells and its compression error, the four-way tradeoff as a chart you can steer, and finally the filter that turns a good index into a bad one.
HNSW: a graph you can watch
Greedy descent above, bounded search below
HNSW builds a hierarchy of graphs over the same points. The top layers are sparse, with long edges that cross the space; the bottom layer is dense, with short edges between near neighbours. A query enters at the top, greedily walks to the closest node it can see, drops a layer, walks again, and finally runs a bounded best-first search at layer 0 keeping efSearch candidates. The graph is built with a degree cap M and a build-time candidate list efConstruction.
The two knobs do different jobs. M and efConstruction are fixed when you build: they decide how good the graph is. efSearch is chosen per query and does not require a rebuild: raise it and recall rises, latency rises with it, and memory does not move. Below, the query point descends the layers, visits nodes greedily, and the trace is drawn in order. Watch the visited count — the honest proxy for latency — move with efSearch, and whether the true nearest neighbour was found.
Layer-0 edges faint, layer-1 in pink, layer-2+ in dark blue. The numbered rings are the visited trace; the dashed path is the greedy descent.
IVF and product quantisation
Partition the space, then compress what is left
IVF runs k-means to place nlist centroids, assigns every vector to its nearest cell, and at query time probes only the nprobe nearest cells. Recall is bounded by a simple fact: if the true neighbour's cell is not probed, it cannot be found. Product quantisation attacks the memory side instead, splitting each vector into sub-vectors and replacing each with a codebook index, which is why the reconstructed point sits near — but rarely on — the original.
Below, the corpus is quantised into cells coloured by list. The query point probes the nearest nprobe cells (highlighted), and the thin lines from each point to its reconstruction show the quantisation error. Raise nprobe and recall climbs while more candidates are scanned; lower nbits and memory falls while the reconstructions drift further from the originals.
Cells coloured by list; the probed cells are highlighted. Grey dots are originals, coloured dots are reconstructions, lines are the quantisation error.
The four-way tradeoff
Recall, latency, memory, build
No index dominates. Flat has perfect recall and the worst latency and memory. IVF-PQ is tiny and fast and pays in recall. HNSW is fast and accurate and pays in memory and build time. DiskANN puts the graph on SSD, so it scales to billions but each hop is a disk read. Choosing is a matter of which constraint binds: latency budget, memory budget, corpus size, or how often you can afford to rebuild.
The scatter plots each family at its typical operating point. Set your budgets and the picker recommends a family — then move a budget and watch the recommendation flip.
x is relative latency, y is recall, bubble size is relative memory. The shaded band is your latency budget; the picker ranks by recall subject to both budgets.
Why filtered ANN is hard
A filter can delete the path the graph needs
Real queries are rarely "nearest neighbour of anything"; they are "nearest policy document", "nearest result this tenant may see", "nearest product in stock". A metadata filter turns the search into a constrained one, and the graph does not know about the constraint. This is where the naive approaches break.
- Post-filtering searches the unfiltered graph and discards results that fail the filter. Simple, and it collapses as selectivity falls: if 1% of the corpus passes and you fetched ten candidates, you may have fetched none of them. The fix is over-fetching — request roughly k/selectivity candidates — which is exactly what destroys latency.
- Pre-filtering restricts traversal to passing vectors. Now the filter is respected, but the graph's long edges have been deleted: the nodes that connected a region to its neighbours may all fail the filter, so the walk becomes stranded and recall falls even though every returned result is valid.
The plot compares the two as the filter narrows. Post-filtering tracks selectivity until over-fetching cannot keep up; pre-filtering holds on longer but degrades as connectivity disappears. Both trough hard when the filter is truly narrow, and both are seeded simulations rather than measurements.
Recall against filter selectivity (log scale). Post-filter over-fetches roughly k/selectivity; pre-filter keeps the filter but loses the graph's edges.
Cheat sheet
| Question | The answer |
|---|---|
| Why keep a flat index? | It is the ground truth: recall 1.0 by construction, and fast enough below a few tens of thousands of vectors. |
| What do M and efConstruction do? | Build-time: they set the graph's degree and the quality of the neighbour lists. Changing them means rebuilding. |
| What does efSearch do? | Query-time: the size of the layer-0 candidate list. Raise it for recall, pay in latency, no rebuild. |
| What does nprobe do? | Query-time for IVF: how many cells to scan. Recall is capped by whether the true cell was probed. |
| What does PQ cost? | Memory, in exchange for compression error — reconstructions sit near the original, never on it. |
| Memory or latency bound? | Memory-bound: IVF-PQ or ScaNN. Latency- and recall-bound with RAM to spare: HNSW. Billions on one node: DiskANN. |
| Why is filtered ANN hard? | A filter can exclude the whole neighbourhood the graph would traverse; post-filtering collapses with selectivity and pre-filtering breaks connectivity. |
| What if filters are common? | Partition the index by the filter so it becomes routing. Otherwise over-fetch and measure recall under the filter. |
Further reading
- Malkov & Yashunin, "Efficient and robust approximate nearest neighbor search using Hierarchical Navigable Small World graphs", 2016/2018 — HNSW, the graph the first demo animates.
- Jégou, Douze & Schmid, "Product Quantization for Nearest Neighbor Search", IEEE TPAMI 2011 — the compression half of IVF-PQ.
- Guo et al., "Accelerating Large-Scale Inference with Anisotropic Vector Quantization" (ScaNN), ICML 2020 — recall-optimised quantisation for inner-product search.
- Subramanya et al., "DiskANN: Fast Accurate Billion-point Nearest Neighbor Search on a Single Node", NeurIPS 2019 — the graph that lives on SSD.
- Johnson, Douze & Jégou, "Billion-scale similarity search with GPUs" (Faiss), 2017 — the reference implementation of IVF, PQ and the flat baseline.
- Cormack, Clarke & Buettcher, "Reciprocal Rank Fusion outperforms Condorcet and individual rank learning methods", SIGIR 2009 — the fusion method Part 16 builds on.