Vector databases & ANN search (HNSW & IVF-PQ)

Hook

Finding the nearest vector to a query, exactly, means comparing it to every single vector in the index. That's fine for eight vectors. It stops being fine somewhere around a million. The fix is to stop looking everywhere — and accept that "nearly the right answer" is what that trade buys you.

Intuition

Query assigned to cluster A — search checks 6 of 8 points.

Approximate search: a4 (distance 1)

Brute force: a4 (distance 1)

Match — same answer

Eight vectors, two clusters. Switch queries and watch the search check a handful of points instead of all eight — and watch whether that handful still contains the actual answer.

Formalize

An exact nearest-neighbor search compares a query against every indexed vector:

\text{nearest}(q) = \arg\min_{p \in \text{index}} \; \lVert q - p \rVert^2

$\text{nearest}(q)$ — the true nearest neighbor to query $q$ , found by exact search.
$q$ — the query vector.
$p$ — a candidate vector being compared against the query.
$\text{index}$ — the full set of stored vectors.

An approximate index (here, a tiny IVF (Inverted File index)-style partition) precomputes a few centroids, assigns every indexed vector to its nearest one, and at query time only searches the query's own assigned cluster:

\text{ann}(q) = \arg\min_{p \in \text{cluster}(\text{nearest-centroid}(q))} \; \lVert q - p \rVert^2

$\text{ann}(q)$ — the approximate nearest neighbor the index actually returns for query $q$ .
$\text{nearest-centroid}(q)$ — the single precomputed centroid closest to the query.
$\text{cluster}(\cdot)$ — the set of indexed vectors assigned to a given centroid; only this set gets searched.

Cheap because it skips most of the data
Searching one cluster is a handful of comparisons instead of the whole index — the speedup and the risk come from the exact same decision: never looking at most of the data.
Wrong when the true neighbor lives in another cluster
When the true nearest neighbor happens to live in a different cluster than the one the query got assigned to, the approximate search never sees it at all — it has no way to know what it skipped.

Play

deep in cluster: ANN checks 6/8 points, reports a4 (d=1). Brute force reports a4 (d=1) — match

near boundary: ANN checks 6/8 points, reports a4 (d=8). Brute force reports b4 (d=5) — miss

A query deep inside a cluster's territory: the approximate search checks a fraction of the index and finds exactly what brute force would have found. A query near the boundary between clusters: same fraction of work, but the assigned cluster doesn't contain the true nearest neighbor — it's sitting just across the line, in the cluster that never got searched.

Worked example

A boundary query at (5, 4)
- Distance to centroid A, $(0,0)$ : $(5-0)^2+(4-0)^2=25+16=41$
- Distance to centroid B, $(10,10)$ : $(5-10)^2+(4-10)^2=25+36=61$
Closer to A, so the index only searches cluster A's four points.
The best answer within cluster A
Distance to each of cluster A's four points:
- $a_1(1,1)$ : $(5-1)^2+(4-1)^2=16+9=25$
- $a_2(2,0)$ : $(5-2)^2+(4-0)^2=9+16=25$
- $a_3(0,3)$ : $(5-0)^2+(4-3)^2=25+1=26$
- $a_4(3,2)$ : $(5-3)^2+(4-2)^2=4+4=8$
$a_4$ is nearest, at distance $8$ . The approximate search returns it confidently — it has no way to know what it didn't look at.
The true nearest neighbor was in cluster B all along
A boundary point in cluster B, $b_4(6,6)$ : $(5-6)^2+(4-6)^2=1+4=5$ — closer than anything in cluster A ( $8$ ), but invisible to a search that only ever considered one cluster.

Checkpoint

This query sits near the cluster boundary. The index reports a4 as the nearest neighbor — but that's only the best match within the cluster it searched. Find the actual nearest neighbor, considering every point in the index.

Pick a point to try it

Summary

\text{ann}(q) = \arg\min_{p \in \text{cluster}(\text{nearest-centroid}(q))} \; \lVert q - p \rVert^2 \;\neq\; \arg\min_{p \in \text{index}} \; \lVert q - p \rVert^2

Every real vector database — FAISS (short for Facebook AI Similarity Search)'s IVF, HNSW (short for Hierarchical Navigable Small World)'s graph layers, ScaNN (short for Scalable Nearest Neighbors)'s quantized clusters — makes this exact trade in some form: search a shortlist instead of the whole index, and accept a small, bounded chance of missing the true best match in exchange for search times that don't grow linearly with the index size. Probing more than one cluster near a boundary shrinks that miss rate at the cost of some of the speedup; it's a dial, not a fixed answer. This closes Part XIX's tour of production systems — the last chapter draws ingestion, serving, and drift detection from every chapter in this part into one monitored pipeline.