16 · Approximate nearest neighbors
Brute-force search is O(N) per query — fine for thousands, hopeless for millions. ANN indexes (IVF, HNSW) trade a sliver of recall for a huge speedup by searching only a fraction of the vectors.
Approximate nearest-neighbour (ANN) search beats brute force by NOT comparing the query to every vector. IVF clusters the data and searches only the nearest few clusters; HNSW walks a navigable graph greedily. You give up a little recall (you may miss a true neighbour) for an order-of-magnitude speedup.
Without this:
Without ANN, every query scans all N vectors. That's fine in a demo but quadratic-feeling at scale: at 10M vectors a brute-force query is far too slow and costs too much CPU, so latency and bills explode.
Last lesson our query ran a cosine loop over every record. That is brute force / exact search: O(N) comparisons per query. With 5 documents it's instant; with 10 million it's a non-starter — you can't dot-product 10M vectors for every user keystroke.
The fix is Approximate Nearest Neighbour (ANN) search. The word "approximate" is the deal: you accept a small chance of missing a true neighbour in exchange for searching only a fraction of the data. Two families dominate:
IVF — Inverted File Index (cluster then probe). Pre-cluster all vectors into, say, 100 buckets (with k-means). Each bucket has a centroid (its average vector). At query time you (1) compare the query to the ~100 centroids, (2) pick the nprobe nearest buckets, and (3) run the exact cosine search only inside those buckets. If each bucket holds N/100 vectors and you probe 3 buckets, you compare against ~3N/100 vectors instead of N — a ~30× cut. The risk: a true neighbour sitting in a bucket you didn't probe is missed.
HNSW — Hierarchical Navigable Small World (greedy graph walk). Build a multi-layer graph where each vector links to a few near neighbours. Searching starts at an entry point in the top (sparse) layer and greedily hops to whichever neighbour is closer to the query, descending layers until it converges — like zooming in on a map. It visits only a logarithmic number of nodes, never all N. It's the default in most modern vector DBs because recall stays high at very low latency.
Both knobs trade the same currency: recall@k vs speed. Recall@k = (true top-k neighbours the ANN actually returned) / k. Probe more buckets (IVF) or widen the search beam (HNSW) → higher recall, slower. Probe fewer → faster, lower recall. Let's build IVF and measure that tradeoff.
Below we implement IVF end to end with a tiny inline k-means (seeded RNG, so it's reproducible). We cluster ~200 random vectors into buckets, then for one query compare two strategies:
- Brute force — cosine against all 200 (the exact ground truth).
- IVF — find the
nprobenearest centroids and search only those buckets.
We report how many comparisons each did and the recall@k of IVF against the exact answer. Then we sweep nprobe to watch recall climb toward 1.0 as we probe more buckets — the speed/recall dial in action.
Python (in browser)
IVF searches only the nearest clusters: at nprobe=2 it does a fraction of the comparisons and still recovers most of the true top-k. Probing more trades speed for recall.
Python runs entirely in your browser via Pyodide (~6 MB on first Run, cached after).
The numbers tell the whole story. At nprobe=1 IVF compares against a small slice and runs fastest, but recall is below 1.0 — it sometimes misses a true neighbour that lived in an unprobed bucket. As nprobe rises, more comparisons recover more of the true top-k, until probing all buckets is just brute force again (recall 1.0, no savings). The sweet spot is the smallest nprobe that gives acceptable recall for your task.
In production you never hand-build this — but the read-along shows you the knobs are the same words you just implemented. Faiss exposes nlist (number of IVF buckets) and nprobe; HNSW exposes M (graph degree) and efSearch (search beam width). Every one of them is the recall/speed dial you just turned.
Faiss IVF (nlist/nprobe) and HNSW (M/efSearch) are the production versions of the dial you tuned by hand — same recall-vs-speed tradeoff, native-speed implementation.
An IVF index splits 1,000,000 vectors into 1,000 buckets. You set nprobe=5. Roughly how many vectors does each query compare against, and what's the catch?
- Brute-force (exact) search is O(N) per query — fine for thousands of vectors, far too slow for millions.
- IVF clusters vectors with k-means and probes only the nearest few buckets; HNSW walks a navigable graph greedily — both visit a fraction of the data.
- ANN trades recall for speed: nprobe (IVF) and efSearch (HNSW) dial how many vectors you check, so always measure recall@k on your data when tuning.
Every large-scale vector DB (Pinecone, Qdrant, Milvus, pgvector with HNSW) uses ANN indexes; Faiss powers many of them under the hood with the nlist/nprobe and M/efSearch knobs you just used.
If you remove it: Without ANN, retrieval latency grows linearly with the corpus; past a few million vectors every query becomes too slow and too expensive to serve in real time.