Approximate Nearest Neighbor Search

Exact search scores every stored vector against your query; approximate search scores only a shortlist picked by an index built ahead of time, trading a small, measurable chance of missing the true nearest match for a much faster query.

ANN scores a shortlist from one probed partition instead of the whole store, returning two of the true top three for a recall of 2 out of 3

Why Does This Exist?

Say your app stores a few million chunk embeddings and a question arrives. The honest way to answer "what is closest?" is to score the query against every stored vector and keep the best. That is exact nearest neighbor search, and its cost grows with the collection: double the vectors, double the work per query. You'll never feel that at a few thousand vectors. You feel it at millions of vectors with milliseconds to answer, which is exactly where retrieval sits in a modern request path.

Approximate nearest neighbor (ANN) search breaks that link between collection size and query cost. An index built ahead of time lets each query skip most of the collection and still land on the right answer, or close enough, almost every time. The price is a small chance of missing the true nearest match. This page is about that bargain: what gets built ahead of time, what gets skipped at query time, and how you measure what you lost.

Two neighbors go deeper on either side. The most common graph index gets its own treatment in HNSW, and the production system around the index, inserts, filters, and persistence, lives in vector databases.

The one idea you need first: every document is a list of numbers, and closeness is a similarity score between two lists, usually cosine similarity. If that picture is fuzzy, read embeddings and similarity metrics first, then come back. Everything below assumes you can picture points in space with a measurable distance between them.

Think of It Like This

A library shelved by topic instead of searched book by book

You need the book most similar to the one in your hand, and the library holds two million volumes. Checking every book is exact search: perfect, and you'll be there all week.

So you trust the organization someone built ahead of time. You walk to the one aisle where similar books are shelved and compare only the few dozen spines there. Most days you walk out with the best match, or one so close the difference doesn't matter, after touching a tiny fraction of the building. The aisle is the partition, walking past the other aisles is the skip, and peeking into a second aisle when you're unsure is the probe count knob.

Where it stops: library aisles are picked by people, and books stay where they are put. A vector index draws computed boundaries through space, and a boundary can fall between your query and its true nearest neighbor. When that happens, no careful browsing inside the wrong aisle recovers the book. That failure has a name and a number, and both are below.

How It Actually Works

The exact baseline

Call the query vector $q$ : the $d$ numbers your encoder produced for the query, where $d$ is the embedding dimension. Call the stored vectors $x_1, x_2, \ldots, x_n$ , where $n$ is the size of the collection. Pick a similarity score $s(q, x)$ , where a bigger value means closer, with cosine similarity the usual choice. Exact search computes $s(q, x_i)$ for every one of the $n$ vectors and keeps the top $k$ , where $k$ is how many neighbors you asked for. The cost per query grows with $n$ times $d$ : every vector, every dimension, every time.

The approximation

Every ANN index splits the work into two phases. At build time it organizes the vectors: partition methods sort them into clusters, and graph methods link each vector to a handful of nearby vectors. At query time it uses that structure to score a shortlist instead of the store: it probes the clusters nearest the query, or walks the graph from an entry point toward whatever looks closest, and ranks only what it visited.

Two knobs run every index, whatever its family. The probe count says how many clusters, or how long a graph walk, each query may spend: more probing buys recall and spends latency. The index size buys speed with memory: more links or finer clusters skip more work per query but cost storage. Push either knob and you slide along a three-way trade between recall, latency, and memory. When the collection is small enough to scan in budget, or a missed neighbor is unacceptable, skip the index and scan exactly.

Worked example

Five documents, two dimensions so you can follow along, query $q = [3, 1]$ . Cosine similarity is the dot product over both lengths:

s(q, x) = \frac{q \cdot x}{\lVert q \rVert \, \lVert x \rVert}

Here $q \cdot x$ is the dot product, the sum of pairwise products, and $\lVert q \rVert$ is the length, the square root of the sum of squares. The query length is $\lVert q \rVert = \sqrt{9 + 1} = \sqrt{10} \approx 3.16$ .

$d_1 = [3, 1]$ : dot $9 + 1 = 10$ , length $\sqrt{10}$ , so $s = 10 / 10 = 1.00$ . Same direction as the query.
$d_4 = [3, 0]$ : dot $9 + 0 = 9$ , length $3$ , so $s = 9 / (3 \times 3.16) \approx 0.95$ .
$d_2 = [2, 2]$ : dot $6 + 2 = 8$ , length $\sqrt{8} \approx 2.83$ , so $s = 8 / (2.83 \times 3.16) \approx 0.89$ .
$d_3 = [1, 3]$ : dot $3 + 3 = 6$ , length $\sqrt{10}$ , so $s = 6 / 10 = 0.60$ .
$d_5 = [0, 2]$ : dot $0 + 2 = 2$ , length $2$ , so $s = 2 / (2 \times 3.16) \approx 0.32$ .

The exact top $3$ are $d_1$ , $d_4$ , $d_2$ . Now suppose the index probes a subset that leaves $d_2$ on the skipped side of a partition boundary, and returns $d_1$ , $d_4$ , $d_3$ . Two of the three answers match. That fraction is the grade.

Grading the approximation: recall at k

Recall@k is the fraction of the true top $k$ that the shortlist actually contains:

\mathrm{recall@k} = \frac{\lvert \mathrm{approx} \cap \mathrm{exact} \rvert}{k}

Here $\mathrm{approx}$ is the $k$ ids ANN returned, $\mathrm{exact}$ is the $k$ ids an exhaustive scan returns, and the bars count shared ids. In the example above the overlap is $d_1$ and $d_4$ , so $\mathrm{recall@3} = 2 / 3 \approx 0.67$ . Measure it on your own representative queries, against an exact scan, before you believe any latency tuning. The number rests on one assumption: closeness in vector space tracks relevance. When the embedding itself misses the relevance signal, no index setting fixes it, and that is when teams add keyword search (hybrid search) or a second scoring pass (reranking).

Code

The point of this snippet is the grading step: rank exactly, then score an approximate shortlist against it.

1import math2
3
4def cosine(a: list[float], b: list[float]) -> float:5    dot = sum(x * y for x, y in zip(a, b))6    na = math.sqrt(sum(x * x for x in a))7    nb = math.sqrt(sum(y * y for y in b))8    return dot / (na * nb)9
10
11def recall_at_k(approx: list[str], exact: list[str]) -> float:12    hit = sum(1 for doc in approx if doc in exact)13    return hit / len(exact)14
15
16q = [3.0, 1.0]17docs = {18    "d1": [3.0, 1.0],19    "d4": [3.0, 0.0],20    "d2": [2.0, 2.0],21    "d3": [1.0, 3.0],22    "d5": [0.0, 2.0],23}24
25ranked = sorted(docs, key=lambda name: cosine(q, docs[name]), reverse=True)26print(ranked[:3])  # -> ['d1', 'd4', 'd2']27print(round(cosine(q, docs["d4"]), 4))  # -> 0.948728
29approx_top3 = ["d1", "d4", "d3"]  # d2 fell on the skipped side of the boundary30print(round(recall_at_k(approx_top3, ranked[:3]), 4))  # -> 0.6667

The exact ranking comes back $d_1$ , $d_4$ , $d_2$ , matching the hand computation, and the shortlist scores $0.67$ : two of three true neighbors recovered.

Watch Out For

Shipping an index you never graded

Every query returns a confident, plausibly ordered list, so nothing looks broken while recall sits far below what your offline eval assumed. The symptom is silence: fast answers, no errors, and relevance slightly worse than your measurements promised, with no dashboard pointing at the index.

Fix it before tuning anything: hold out a set of representative queries, run them through an exact scan once, and compute recall@k for your index settings. Write down the floor your product needs and refuse any configuration that lands under it.

Buying speed with the probe knob and paying in recall

Every index exposes an effort knob, probe count or walk length, that trades recall for latency. Turn it down and the latency dashboard glows green while the result lists quietly get worse. The symptom arrives late, as relevance complaints weeks after a deploy that only changed performance.

Never tune the index without remeasuring recall. Change one knob, rerun the same query set against the same exact baseline, and keep recall@k next to latency on one screen. If a faster setting drops recall under your floor, it is not faster. It is broken, politely.

The Quick Version

Exact search scores every stored vector against the query, so its cost grows with the collection; ANN scores a shortlist picked by an index built ahead of time.
Partition indexes probe the clusters nearest the query, while graph indexes walk neighbor links from an entry point toward it.
Recall at k is the grade: the fraction of the true top k that the shortlist contains, measured against an exact scan on your own queries.
Every index trades recall against latency and memory, and the probe count knob slides you along that curve.
When the collection is small or a missed neighbor is unacceptable, skip the index and scan exactly.