Module 5 — ANN Indexes: How Search Gets Fast

This is the engineering crown jewel of vector databases. ANN = Approximate Nearest Neighbor. The idea: don’t check every vector — be smart about which ones you check, accept a tiny chance of missing a true neighbor, and go 100–1000× faster. We’ll build intuition for each major family, then compare them.

The mindset shift

Brute force (Module 4) is like reading every book in the library to find one. ANN indexes are like the library’s organization system — sections, shelves, signs — that let you walk almost straight to the right book without examining the others. You might occasionally miss a book that was mis-shelved (that’s the “approximate” part), but you find the right shelf in seconds instead of days.

There are four big families. Modern databases mostly use HNSW (a graph) or IVF + PQ (clustering + compression), so spend the most energy there.

Family 1: Graph-based — HNSW (the modern default)

HNSW = Hierarchical Navigable Small World. It’s the most popular ANN index today (used by Qdrant, Weaviate, Milvus, Elasticsearch, pgvector, FAISS, and more). Intimidating name, friendly idea.

The intuition: “six degrees of separation” for vectors

Picture a social network. To get a message to a stranger across the world, you don’t know them directly — but you know someone who knows someone who knows them. A few hops through well-connected friends gets you there fast. HNSW builds exactly this kind of “small world” network among your vectors: each vector is connected to a handful of nearby vectors, and you reach any target in a few greedy hops.

The “hierarchical” part: an express-train map

HNSW stacks multiple layers, like a subway system with express and local lines:

Layer 2 (few nodes, long links):     A -------- F -------- K      ← express, big jumps
Layer 1 (more nodes):                A -- C -- F -- H -- K
Layer 0 (ALL nodes, short links):    A-B-C-D-E-F-G-H-I-J-K        ← local, fine detail

Search starts at the top (sparse, long-range links) and takes big jumps to get into the right neighborhood quickly.
Then drops down a layer, refining with shorter hops.
Finishes at layer 0 (which contains every vector) doing fine-grained local search to pin down the true nearest neighbors.

It’s like finding a house: first the country (express), then the city, then the street, then the door. Each layer zooms in.

How a search runs

Enter at the top layer’s entry point.
Greedily hop to whichever neighbor is closer to your query, until you can’t get closer on this layer.
Drop to the next layer down and repeat.
At layer 0, explore the local neighborhood and collect the best k.

The knobs you’ll actually tune

M — how many neighbors each node keeps. Higher M → better recall, more memory, slower build. Typical 16–64.
efConstruction — how hard it works while building the graph. Higher → better-quality graph, slower indexing. Typical 100–400.
efSearch (a.k.a. ef) — how many candidates it explores per query. This is your live speed↔recall dial. Higher ef → higher recall, slower query. You can change it per query without rebuilding. Typical 50–400.

Mental model: efSearch is the volume knob for accuracy. Turn it up until recall is good enough, then stop (higher costs latency for nothing).

HNSW pros and cons

✅ Excellent recall-vs-speed, great for low-latency search. Works well without GPUs. Supports incremental inserts.
❌ High memory — the graph links cost extra on top of the vectors themselves. Deletes are awkward (often “mark deleted,” rebuild later). Building large graphs is slow.

HNSW is the safe default for most apps under ~100M vectors. Above that, or when RAM is tight, people combine it with compression or switch toward IVF/PQ.

Family 2: Clustering-based — IVF (Inverted File Index)

IVF = Inverted File. The intuition: divide the space into neighborhoods, and only search the neighborhoods near your query.

How it works

Train: run k-means clustering to find, say, 1,000 cluster centers (“centroids”). Each centroid owns a region of space (a “cell” or “Voronoi cell”).
Index: assign every vector to its nearest centroid. Now each cell holds a list of the vectors inside it (that’s the “inverted list”).
Search: find the few centroids closest to your query, then brute-force search only the vectors in those few cells — ignoring the rest entirely.

Instead of searching 1,000,000 vectors, you search maybe the 10,000 that live in the handful of cells near your query. Massive speedup.

The key knobs

nlist — number of clusters (cells). More cells = smaller cells = faster search but you might need to probe more of them. Rule of thumb: ~√N.
nprobe — how many nearby cells to actually search per query. This is your speed↔recall dial. nprobe=1 is fastest but risky (the true neighbor might sit just across a cell boundary); higher nprobe checks more cells, raising recall and latency.

The boundary problem (why nprobe matters)

A query can land near the edge of its cell, with its true nearest neighbor sitting just inside the neighboring cell. If you only search one cell, you miss it. Probing several nearby cells fixes most of this. This boundary issue is the fundamental weakness of clustering methods.

IVF pros and cons

✅ Memory-efficient, fast, scales well, especially combined with PQ compression (below). Great on GPU.
❌ Needs a training step on representative data before you can add vectors. Quality depends on cluster quality; if your data distribution shifts, clusters go stale and you should retrain. The boundary problem caps recall unless you raise nprobe.

Family 3: Compression — Product Quantization (PQ)

PQ isn’t a search structure on its own — it’s a compression technique usually bolted onto IVF (giving IVF-PQ, the workhorse for billion-scale search). Its job: make each vector tiny so billions fit in RAM and comparisons get cheap. Full details and cousins (SQ, OPQ, binary) are in Module 6, but here’s the core idea since it pairs with IVF.

The intuition: Instead of storing 768 precise numbers per vector, chop the vector into chunks, and replace each chunk with the ID of the closest “representative” chunk from a small codebook. Like describing a paint color not by exact RGB but by the nearest name from a 256-color swatch book — “that’s roughly sky blue #137.” You store the number 137 (one byte) instead of three precise values.

A 768-dim float vector (3,072 bytes) can shrink to ~96 bytes or less — a ~32× reduction — at the cost of some precision. Distances computed on the compressed codes are approximate but very fast (precomputed lookup tables). IVF narrows where to look; PQ makes each look cheap and memory-light. That combination is how systems search billions of vectors on a single machine.

Family 4: Hashing — LSH (Locality-Sensitive Hashing)

LSH = Locality-Sensitive Hashing. The oldest popular ANN idea, more textbook than production-default today, but worth understanding.

The intuition: A normal hash function scatters similar inputs to totally different buckets (that’s what you want for hash maps). LSH does the opposite on purpose — it’s designed so that similar vectors are likely to land in the same bucket. To search, hash your query, look only in its bucket(s), compare against the few vectors there.

It’s like a coat check that deliberately puts similar coats on the same hook, so finding “a coat like this one” means checking just one hook.

✅ Simple, theoretically well-understood, easy to make streaming/online, good for some specialized similarity types.
❌ Generally worse recall-per-memory than HNSW or IVF-PQ for dense embeddings, so it’s faded from mainstream text/RAG use. Still appears in dedup, near-duplicate detection, and certain large-scale niche systems.

Other approaches you’ll hear about

Annoy (Spotify) — builds many random binary trees; simple, memory-mapped, great for static read-only datasets, but no easy updates. Used in recommendations.
ScaNN (Google) — anisotropic quantization + clever pruning; top-tier accuracy/speed, especially with the right hardware.
DiskANN / Vamana (Microsoft) — graph index designed to live on SSD, not just RAM, so you can serve a billion vectors from one machine cheaply. Increasingly important for cost.
SPANN, NGT, FALCONN — other research-grade indexes you’ll meet in papers.

The big comparison table

Index	Type	Speed	Recall	Memory	Updates	Best for
Flat	Exact	Slow	100%	High	Easy	Small data; ground truth; re-ranking
HNSW	Graph	Very fast	Very high	High	Inserts easy, deletes awkward	The default for <~100M, low latency
IVF	Cluster	Fast	High (tune nprobe)	Medium	Needs training	Large scale, GPU
IVF-PQ	Cluster+compress	Fast	Good (lossy)	Very low	Needs training	Billion-scale on limited RAM
LSH	Hashing	Fast	Lower	Medium	Streaming-friendly	Dedup, niche/streaming
Annoy	Trees	Fast	Good	Low (mmap)	Static only	Read-only recsys
DiskANN	Graph on SSD	Fast	High	Low RAM (uses SSD)	Moderate	Billion-scale, cost-sensitive

How to actually choose (a decision guide)

< ~1M vectors, simple needs? Flat / pgvector. Don’t overthink it.
Need lowest latency, have RAM, < ~100M vectors? HNSW. The default.
RAM-constrained or 100M–1B+ vectors? IVF-PQ (or HNSW-PQ).
Billions of vectors, want one cheap machine? DiskANN / disk-based indexes.
Static dataset, simple recsys? Annoy.
Always: measure recall vs. latency on your data and tune the dials (efSearch, nprobe). The “best” index is the one that hits your recall target within your latency budget at your cost.

Hands-on: HNSW vs flat with FAISS

# pip install faiss-cpu numpy
import faiss, numpy as np, time

d, N = 128, 200_000
data = np.random.randn(N, d).astype("float32")
faiss.normalize_L2(data)
q = data[:5].copy()   # use 5 real vectors as queries

# Exact (ground truth)
flat = faiss.IndexFlatIP(d)        # inner product = cosine on normalized vecs
flat.add(data)
_, true_ids = flat.search(q, 10)

# HNSW (approximate)
hnsw = faiss.IndexHNSWFlat(d, 32)  # M = 32
hnsw.hnsw.efConstruction = 200
hnsw.add(data)
hnsw.hnsw.efSearch = 64            # the speed/recall dial
_, approx_ids = hnsw.search(q, 10)

# Measure recall@10
recall = np.mean([len(set(t) & set(a)) / 10 for t, a in zip(true_ids, approx_ids)])
print("recall@10:", recall)        # try efSearch = 16, 64, 256 and watch it rise

Change efSearch to 16, then 256, and watch recall (and time) move. That single experiment teaches the whole module in your hands.

Gotchas

Tuning blind. Always measure recall against flat ground truth before shipping. “It returns results” ≠ “it returns the right results.”
HNSW memory surprise. The graph adds significant RAM on top of the raw vectors. Size your machine for it.
IVF without enough training data. k-means needs representative samples (rule of thumb: ≥ 30–256 × nlist points). Too few → bad clusters → bad recall.
Forgetting deletes. HNSW deletes are typically soft (tombstones); space and quality degrade until you rebuild. Plan periodic re-indexing.
Treating PQ recall as free. Compression is lossy. Often you PQ-search to get candidates, then re-rank them with full-precision vectors (Module 6) to recover accuracy.
One index for everything. Different collections/workloads may want different indexes and dials. Don’t assume a global setting fits all.

Check yourself

Explain HNSW’s “hierarchical” layers with an analogy.
What do efSearch (HNSW) and nprobe (IVF) have in common?
What is the “boundary problem” in IVF and how do you mitigate it?
In one sentence, what does Product Quantization buy you and what does it cost?
Your dataset is 800M vectors and RAM is limited. Which index family fits, and why not plain HNSW?

Answers: (1) Like a subway with express and local lines (or zooming country→city→street→door): top layers make big jumps to the right region, lower layers refine locally, layer 0 has every node for precision. (2) Both are the per-query speed↔recall dial — raise them for higher recall at the cost of latency, no rebuild needed. (3) A query near a cell edge can have its true neighbor in an adjacent cell; raise nprobe to search several nearby cells. (4) It shrinks vectors ~8–32× and speeds up distance computation, at the cost of some precision (lossy). (5) IVF-PQ or DiskANN — plain HNSW’s full-precision vectors plus graph links would need far too much RAM at 800M; compression or SSD-resident indexes keep it affordable.

➡️ Next: 06-quantization-and-compression.md — shrinking vectors in depth.