Vector Databases & ANN IndexesOpen in Colab

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 kk-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 NN vectors of dimension dd:

cost=O(N⋅d)per query\text{cost} = O(N \cdot d) \quad\text{per query}

At N=107N = 10^7 and d=768d = 768 that is ~8×1098\times10^9 multiply-adds per query — tens to hundreds of milliseconds, and it grows linearly with the corpus. ANN indexes break the linear-in-NN 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-kk 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.

MetricFormulaWhen
Cosine1−a⋅b∥a∥∥b∥1 - \frac{\mathbf{a}\cdot\mathbf{b}}{\lVert\mathbf{a}\rVert\lVert\mathbf{b}\rVert}most text embeddings (direction = topic)
Dot product− a⋅b-\,\mathbf{a}\cdot\mathbf{b}when magnitude is meaningful (some trained retrievers)
Euclidean (L2L_2)∥a−b∥\lVert\mathbf{a}-\mathbf{b}\rVertimage/spatial embeddings

Trick: if you L2L_2-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 O(N)O(N). The right choice below ~10⁴–10⁵ vectors, and the ground truth you measure other indexes against.

IVF (Inverted File). Cluster all vectors into nlistn_{\text{list}} 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:

candidates≈N⋅nprobenlist  ≪  N\text{candidates} \approx N \cdot \frac{n_{\text{probe}}}{n_{\text{list}}} \;\ll\; N

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 mm 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 ~mm 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.

IndexRecallLatencyMemoryBuild/insert
Flatexacthighlowtrivial
IVFtunablelowlowk-means once
HNSWvery highvery lowhighslow
IVF-PQlowervery lowvery lowk-means ×(m+1)

Beyond the index

  • Metadata filtering: "nearest neighbours where tenant = 42 AND year ≥ 2023". Naive post-filtering can empty your top-kk; 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)

N=1,000,000N = 1{,}000{,}000 vectors, nlist=1000n_{\text{list}} = 1000 cells (so ~1000 vectors each). With nprobe = 10:

candidates≈1,000,000⋅101000=10,000\text{candidates} \approx 1{,}000{,}000 \cdot \tfrac{10}{1000} = 10{,}000

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

1/7

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.

python
1def ivf_search(q, k, nprobe):
2
3 # 1. coarse quantizer: rank the cells
4 d = [dist(q, c) for c in centroids]
5 cells = argsort(d)[:nprobe]
6
7 # 2. scan only the probed cells
8 cand = []
9 for c in cells:
10 cand += inverted_list[c]
11
12 # 3. exact distances on candidates
13 scored = [(dist(q,x), x) for x in cand]
14 return sorted(scored)[:k]
state
600 vectors, 16 k-means cells (rings = centroids)
-4.24.23.6-3.6c0c1c2c3c4c5c6c7c8c9c10c11c12c13c14c15dim 0dim 1
index
N → 600nlist → 16smallest cell → 16largest cell → 62

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 N⋅nprobe/nlistN \cdot n_{\text{probe}}/n_{\text{list}} 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 nprobe exists. Recall at nprobe = 1 is 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. Raising nprobe to 3 converges them. What you buy with nprobe is not average recall, it is recall for the unlucky queries.

Common mistakes

  1. Treating ANN as exact. Always measure recall@k against a flat-index ground truth on a sample before trusting it.
  2. Index/metric mismatch. Building for L2L_2 then querying with cosine (or comparing vectors from two different embedding models) returns nonsense.
  3. Forgetting to normalize when your similarity assumes unit vectors.
  4. Post-filtering instead of filtered search. Retrieving top-kk and then applying a strict metadata filter can return far fewer than kk results; push the filter into the search.
  5. Re-tuning nothing. nprobe/efSearch ship at conservative defaults; the right value depends on your recall target and corpus.

Related concepts

Concept neighbourhood

How this concept connects — click any node to jump there, or explore the whole concept map.

RelatedReferenced by
Vector Databases & ANN IndexesBM25: Lexical RankingHNSW: Hierarchical Naviga…Embeddings & Semantic Sea…Retrieval-Augmented Gener…RAG Architectures: Which …Deep & Two-Tower Recommen…K-Means Clustering