Approximate Nearest Neighbor

Comparing a query against every stored vector is exact and, past a few million documents, too slow. Approximate search arranges the vectors so most can be ruled out without ever being examined, accepting that it will occasionally miss the true nearest neighbour in exchange for looking at a small fraction of them.

HNSW builds a layered graph and walks it greedily from a sparse top layer downward; IVF clusters the space and probes only the nearest few cells. Both expose a knob that trades recall for latency, so a single recall number means nothing without the latency it was measured at. Index build time and memory are real costs that benchmarks routinely leave out.

Exact search is Θ(Nd) per query. HNSW's greedy descent is Θ(d·log N) under its idealised analysis, with the constant hidden in how many neighbours each node keeps — the same parameter that sets the index's memory. Recall is not a property of the index alone but of the index and the search effort together, which is why it has to be reported as a curve rather than a number.