Why Exact Search Fails, and the ANN Trade
In one line: comparing a query against every vector is correct and too slow, and every index that fixes it is buying speed with accuracy you choose to give up.
The brute-force arithmetic
Exact nearest-neighbour search compares the query to every stored vector. The cost is straightforward:
Comparisons = vectors x dimensions 10,000,000 vectors x 768 dims = 7.7e9 multiply-adds per query
On a single core that is seconds. Heavily optimised and parallelised it can reach tens of milliseconds — and it scales linearly, so ten times the corpus is ten times the latency, forever.
There is a scale below which this is genuinely the right answer, and saying so is a good signal:
| Corpus | Exact search |
|---|---|
| Under ~10,000 | Trivially fast. Use it. An index is pure overhead |
| ~100,000 | Feasible, tens of milliseconds with good libraries |
| ~1,000,000 | Borderline; depends hard on your latency budget |
| 10,000,000+ | Not viable in an interactive path |
What approximate means
Approximate nearest-neighbour search examines a small fraction of the corpus by exploiting structure built at index time, and accepts that it will sometimes miss a true neighbour.
The quality measure is recall: of the true top-k, how many did the index actually return.
Recall@10 = (returned items that are in the true top 10) / 10
Typical production settings run 90–99%. The crucial framing: recall is a dial you choose, not a property you discover. Every index exposes parameters that trade it against speed, and the design question is what recall your product needs.
The three-way trade
Every ANN index negotiates the same three quantities, and you can have any two.
Reading the pairings makes it concrete:
High recall and low latency — search more of the graph, faster, which means more memory: bigger graphs, more connections, everything resident.
High recall and low memory — compress the vectors and search harder to compensate, which costs latency.
Low latency and low memory — examine less and store less, which costs recall.
The senior version of this is to notice that the product decides where you sit. A legal search where missing a document is a liability wants recall above almost everything. A recommendation carousel where item eleven is as good as item nine can run at 90% recall and spend the savings elsewhere.
Recall is not free to measure
An awkward practical point that catches teams out: computing recall requires knowing the true nearest neighbours, which means running the exact search you were trying to avoid.
The standard approach is to do it once, offline, on a sample:
Two things to say about it. The ground truth needs recomputing when the corpus changes materially, because the true neighbours move. And this measures recall against the embedding's notion of nearest, not against relevance — a 99% recall index on a poor embedding model is faithfully retrieving the wrong things.
The families
Two structures dominate production, plus one worth knowing for scale.
| Graph-based (HNSW) | Partition-based (IVF) | Disk-based | |
|---|---|---|---|
| Idea | Navigate a neighbour graph greedily | Cluster the space, search a few clusters | Keep the graph on SSD, cache the hot part |
| Recall at speed | Best in class | Good | Good |
| Memory | High — the graph is large | Moderate, and tunable | Low RAM, high storage |
| Build time | Slow | Faster, needs a training pass | Slow |
| Updates | Incremental inserts are fine | Drifts as data changes; retrain periodically | Awkward |
| Use when | RAM is available and recall matters | Large corpus, memory constrained | Past ~100M vectors |
The default for most systems is graph-based, because RAM is usually available at the scales most products operate at and it gives the best recall-per-millisecond. The next two lessons take each in turn.
Key takeaway
Brute force costs vectors times dimensions per query and scales linearly, which makes it correct and right below roughly a hundred thousand vectors and unusable past ten million. Approximate search trades recall for speed, and recall is a dial you set rather than a property you find — measured against an offline brute-force ground truth on sampled queries. Every index negotiates recall, latency and memory and you can have two; which two is a product decision. And index recall is not retrieval relevance: a perfect index on a poor embedding retrieves the wrong things faithfully.
Next: the graph index, and what its parameters actually do.