Vector Databases & ANN Indexes
The embeddings lesson turns text into vectors and ranks them by cosine similarity. That works fine for a few thousand documents. At a few million, scoring the query against every vector (exact -nearest-neighbour) is too slow for an interactive request. A vector database is a system built around an Approximate Nearest Neighbour (ANN) index that returns most of the true neighbours in a fraction of the time, plus the operational machinery (persistence, metadata filtering, updates, sharding) a production retriever needs.
The cost of exact search
Exact kNN scans all vectors of dimension :
At and that is ~ multiply-adds per query — tens to hundreds of milliseconds, and it grows linearly with the corpus. ANN indexes break the linear-in- scan by only looking at a small, cleverly chosen subset of candidates.
The fundamental trade-off
ANN returns most of the true neighbours, most of the time. Every index exposes a knob (cells probed, graph search width) that trades recall (fraction of true top- you actually find) against latency. There is no free lunch — you choose the operating point.
Distance metrics
The index is built for a specific metric; mixing them silently returns garbage.
| Metric | Formula | When |
|---|---|---|
| Cosine | most text embeddings (direction = topic) | |
| Dot product | when magnitude is meaningful (some trained retrievers) | |
| Euclidean () | image/spatial embeddings |
Trick: if you -normalize every vector once at insert time, cosine ranking and dot-product ranking become identical, so the index can use the faster dot product.
The main ANN index families
Flat (brute force). No index — scan everything. Exact (100% recall), simple, but . The right choice below ~10⁴–10⁵ vectors, and the ground truth you measure other indexes against.
IVF (Inverted File). Cluster all vectors into cells with k-means (the cell centroids are a coarse quantizer). At query time, find the nprobe nearest centroids and search only the vectors in those cells:
nprobe is the recall/latency knob: nprobe = nlist recovers exact search; nprobe = 1 is fastest but misses neighbours that fall just across a cell boundary.
HNSW (Hierarchical Navigable Small World). A multi-layer proximity graph. Search starts at a sparse top layer, greedily hops toward the query, then descends into denser layers — like a skip-list for geometry. Gives excellent recall at low latency and is the default in most modern vector DBs; the cost is high memory and slower inserts. Knobs: M (edges per node) and efSearch (candidate-list width during search).
Product Quantization (PQ). A compression layer, usually combined with IVF (IVF-PQ). Split each vector into sub-vectors, k-means each subspace into 256 centroids, store each sub-vector as a 1-byte centroid id. A 768-dim float32 vector (3072 bytes) shrinks to ~ bytes (~100× smaller), so billion-scale indexes fit in RAM. Distances are approximated from small lookup tables; recall drops, so PQ is typically used to shortlist candidates that are then re-ranked with exact vectors.
| Index | Recall | Latency | Memory | Build/insert |
|---|---|---|---|---|
| Flat | exact | high | low | trivial |
| IVF | tunable | low | low | k-means once |
| HNSW | very high | very low | high | slow |
| IVF-PQ | lower | very low | very low | k-means ×(m+1) |
Beyond the index
- Metadata filtering: "nearest neighbours where
tenant = 42 AND year ≥ 2023". Naive post-filtering can empty your top-; production engines do filtered ANN that respects the predicate during the search. - Hybrid search: fuse ANN scores with a keyword (BM25) score so exact IDs and rare tokens still match (the embeddings lesson's hybrid search).
- CRUD + persistence + sharding: add/delete/update vectors, snapshot to disk, and scale across machines. HNSW in particular makes deletes awkward, which is a real operational concern.
IVF candidate count (worked intuition)
vectors, cells (so ~1000 vectors each). With nprobe = 10:
You score 10k vectors instead of 1M (a 100× speedup) at the cost of missing any true neighbour whose vector landed in one of the 990 un-probed cells. Raising nprobe to 50 scores 50k vectors and recovers most of that lost recall.
Watch a probe run
600 vectors, 16 cells, and one query that nprobe = 1 gets wrong.
IVF search — probing cells, and the neighbours that fall across the boundary
The index, built once: k-means partitions all 600 vectors into 16 cells, and each cell keeps an inverted list of the vector ids that fell in it. Cells hold 16–62 vectors (mean 38) — k-means balances by geometry, not by count, so a dense region gets small tight cells and a sparse one gets a large loose cell. Nothing here depends on the query; this cost is paid at build time.
600 vectors in 16 k-means cells. The walkthrough query is not hand-picked: it is the first query in a 400-query evaluation set that nprobe = 1 gets wrong, and it loses its true nearest neighbour not because that vector ranked badly but because its cell was never opened. Two measured payoffs follow: the recall-vs-candidates curve against the page's N·nprobe/nlist estimate, and the finding that recall at nprobe = 1 depends almost entirely on how close the query sits to a cell boundary — which is precisely what raising nprobe buys back.
What to notice:
- Frame 3: what "approximate" actually means. Everything dim on the plot is not ranked lower; its distance is never computed. IVF's error mode is not mis-ranking, it is non-consideration.
- Frame 4: the miss, in full. Recall@5 collapses to 20%, and the true nearest neighbour — 0.16 away — is among the losses. It lives one cell over, and that cell's list was never opened. The query was not unlucky in any deep sense: its two nearest centroids are 0.90 and 0.96 away.
- Frame 6: the estimate holds. Measured candidate counts track to within a few percent across the whole sweep, so the back-of-envelope above is a real planning tool. Note also where recall saturates: 3 of 16 cells (19%) recovers 99.7% of exact search's answers, and the remaining 13 cells are pure cost.
- Frame 7: the payoff, and the reason
nprobeexists. Recall atnprobe = 1is barely a property of the index. Split the queries by how close they sit to a cell boundary and the top quartile gets 100% while the bottom gets 55.6% — from the same index at the same setting. Raisingnprobeto 3 converges them. What you buy withnprobeis not average recall, it is recall for the unlucky queries.
Common mistakes
- Treating ANN as exact. Always measure recall@k against a flat-index ground truth on a sample before trusting it.
- Index/metric mismatch. Building for then querying with cosine (or comparing vectors from two different embedding models) returns nonsense.
- Forgetting to normalize when your similarity assumes unit vectors.
- Post-filtering instead of filtered search. Retrieving top- and then applying a strict metadata filter can return far fewer than results; push the filter into the search.
- Re-tuning nothing.
nprobe/efSearchship at conservative defaults; the right value depends on your recall target and corpus.
Related concepts
- HNSW: Hierarchical Navigable Small World Graphs: the graph index this page names as the modern default, opened up from the inside
- Embeddings & Semantic Search: where the vectors and cosine similarity come from
- Retrieval-Augmented Generation: the vector DB is the retriever that feeds an LLM
- Clustering: k-means is the coarse quantizer inside IVF and PQ