Gen AI

Approximate Nearest Neighbor Search

Exact search checks every stored vector against a query; approximate search checks only a promising subset, trading a small chance of missing the true nearest match for a much faster query.

Exact search checks every stored vector against the query, while approximate search only checks a promising subset, trading a small chance of missing the true nearest neighbour for a large speedup

Why Does This Exist?

Finding the exact nearest neighbor to a query vector, done honestly, means comparing the query against every single vector in the collection and keeping track of the closest ones — a linear scan whose cost grows directly with how many vectors are stored. That's manageable for a collection of a few thousand items. It becomes genuinely impractical at the scale real embeddings-based systems actually operate at: millions or billions of stored vectors, with search latency budgets measured in milliseconds, not seconds.

Approximate nearest neighbor (ANN) search exists to break that linear relationship between collection size and query cost. Instead of guaranteeing the mathematically exact nearest neighbor every time, ANN algorithms build a structure ahead of time that lets a query skip the vast majority of the collection and still find, with very high but not perfect probability, the same result exact search would have found — at a small fraction of the cost.

Think of It Like This

Finding a book by browsing shelves, not scanning every book in the building

To find the exact best-matching book in a library by brute force, you'd have to pick up and inspect every single book on every shelf, compare it to what you're looking for, and keep the best match seen so far — thorough, and completely impractical for a library with millions of volumes.

A sensible person instead walks to the section where relevant books are shelved, based on the building's organization, and only closely inspects the handful of books actually near that section. This almost always finds the best match, or something extremely close to it, while inspecting a tiny fraction of the building's total collection. It's not a guarantee — occasionally the perfect match got shelved somewhere slightly unexpected — but the speedup is enormous, and the accuracy cost is usually small enough to be worth it entirely.

How It Actually Works

The core tradeoff: recall, latency, and memory

Every ANN algorithm sits somewhere on a three-way tradeoff. Recall measures how often the approximate search actually returns what exact search would have returned — a recall of 0.95 at $k{=}10$ means the approximate top-10 matches the true top-10 about 95% of the time. Latency is how fast a single query resolves. Memory is how much space the index structure itself consumes, on top of the raw vectors. Improving one of these generally costs one of the other two: a structure that searches faster typically needs more memory to hold its navigation shortcuts, or trades away some recall to skip more of the collection.

Two dominant families of approach

Graph-based methods build a navigable graph over the stored vectors ahead of time, where each vector connects to a handful of others that are close to it. A query starts at some entry point and walks the graph, always moving toward whatever neighbor looks closest to the query, converging on a strong candidate set quickly without ever touching most of the graph. Partition-based methods instead divide the vector space into clusters ahead of time, and a query only searches within whichever cluster (or handful of clusters) it falls closest to, ignoring the rest of the space entirely. Both approaches achieve the same underlying goal — skip the vast majority of vectors — through different structural mechanisms, and different specific algorithms within each family make different tradeoffs among recall, latency, and memory.

Measuring whether the approximation is good enough

Because ANN search is, by design, not guaranteed to be exact, any real deployment needs to actually measure how close its approximation comes to exact search on representative queries — this is recall@k, computed by running the same queries through both an approximate index and an exact linear scan, then checking what fraction of the true top-k results the approximate search actually returned. A recall@k below roughly 0.9 to 0.95 usually means users are getting meaningfully worse results than an offline quality evaluation, run against exact search, would suggest — a gap that's invisible unless someone explicitly measures it.

Show Me the Code

A simple recall@k measurement, comparing an approximate result set against the true exact-search result set for the same query.

1import numpy as np2
3
4def exact_top_k(query: np.ndarray, vectors: np.ndarray, k: int) -> set[int]:5    sims = vectors @ query / (np.linalg.norm(vectors, axis=1) * np.linalg.norm(query))6    return set(np.argsort(-sims)[:k])7
8
9def recall_at_k(approx_ids: set[int], exact_ids: set[int]) -> float:10    return len(approx_ids & exact_ids) / len(exact_ids)11
12
13rng = np.random.default_rng(0)14vectors = rng.normal(size=(1000, 32))15query = rng.normal(size=32)16
17true_top5 = exact_top_k(query, vectors, k=5)18approx_top5 = set(list(true_top5)[:4]) | {999}     # simulate an approximate search missing one true match19
20print(true_top5)                          # -> the exact top-5 ids21print(round(recall_at_k(approx_top5, true_top5), 2))  # -> 0.8 -- 4 of 5 true neighbors recovered

A recall of 0.8 here means the approximate search found four of the five true nearest neighbors and substituted one wrong candidate — the kind of gap that's easy to miss without explicitly comparing against exact search on a held-out set of queries.

Watch Out For

Never measuring recall against exact search

It's tempting to configure an ANN index once, confirm queries return results quickly, and move on without ever checking those results against what exact search would have returned. A misconfigured index can silently run at a much lower recall than intended — fast, and consistently missing relevant results — with nothing in the system flagging that gap, because every query still returns a plausible-looking, confidently-ranked list.

Tuning purely for latency without checking the recall cost

Every ANN algorithm exposes tuning parameters that trade recall for speed, and it's easy to tune purely toward a latency target without checking what recall that configuration actually delivers. A configuration that looks great on a latency dashboard can be quietly returning far worse search results than a slightly slower configuration would, and that quality gap generally isn't visible anywhere a latency-focused dashboard would show it.

The Quick Version

Exact nearest-neighbor search scans every stored vector, which becomes impractical at large collection sizes.
Approximate nearest-neighbor search builds a structure ahead of time that lets a query skip most of the collection, at a small, tunable accuracy cost.
Every ANN algorithm trades among recall, latency, and memory — improving one generally costs one of the other two.
Graph-based and partition-based methods are the two dominant approaches, achieving the same skip-most-of-the-collection goal differently.
Recall@k, measured against exact search on real queries, is the only way to know how much accuracy an approximate configuration is actually costing.