HNSW vs IVF: Graph Traversal, Cluster Probing, and the Recall-Latency Trade-off

Core Concept

Exact nearest-neighbour search scores a query against every vector — honest, but it does not scale. HNSW and IVF are two different ways to make the search approximate: HNSW is a proximity graph you walk, IVF is a cluster index you partition. Both do a cheap coarse step, then a fine local step — and both miss when the true neighbour falls just outside the region they chose to look in.

Key Components

Graph index

HNSW

Hierarchical Navigable Small World. Layer 0 is a dense graph of short local links; higher layers are sparser with long-range links. Knobs: M (neighbours per node), efConstruction (build effort), efSearch (query frontier).

Cluster index

IVF

Inverted File. Train nlist centroids, assign every vector to a list; a query probes only its nprobe nearest lists. Product Quantization shrinks memory further, at a recall cost.

Shared shape

Coarse-to-Fine

HNSW: greedy descent from the sparse top layer, then frontier expansion at layer 0. IVF: centroid selection, then list scanning. The coarse step is where each method can be wrong.

The real metric

Recall @ Fixed Latency

Raising efSearch or nprobe buys recall and costs latency. The honest axis is recall@10 at a fixed p95 latency — plus memory and build time.

How It Works

Baseline: brute force scores the query against all vectors. This is your ground truth — too slow to serve, but it defines what "recall" means.

HNSW path: enter at a sparse upper layer, greedily follow long-range links toward the query, descend layer by layer, then expand a candidate frontier (efSearch) in the dense base layer. The result is the nearest stored vector — the query itself is external, not a node.

IVF path: compare the query to nlist centroids, pick the nprobe nearest lists, score only the vectors inside them. Worked example: 1,000 lists, nprobe=3 — you scan 3 lists instead of 1,000.

Where each fails: HNSW misses on a weak entry route or a frontier too small to reach the true neighbour. IVF misses when the true neighbour sits just across an unprobed cluster boundary.

Falsify it

Build both indexes over the same vectors. Hold out brute-force neighbours as ground truth. Sweep efSearch for HNSW and nprobe for IVF. Plot recall@10 against p95 latency, memory, and build time. "HNSW is faster" with no fixed recall or hardware is not a claim — it is a slogan.

Real-World Applications

Online RAG / semantic search — low-latency, high-recall lookups over embedding stores; HNSW fits when RAM is available and inserts arrive online.
Very large batch collections — billions of vectors, built in one pass; IVF's list scanning is GPU-friendly and memory-friendly, especially with quantization.
Memory-constrained deployments — IVF + Product Quantization can fit indexes that would not fit as dense graphs.
Hybrid systems — coarse partitioning with graph or compressed search inside partitions; the decision is made at a target recall, not at default settings.

Checkpoint — answer before you move on

An IVF index has nlist=1,000 and nprobe=3. What exactly does the query score, and where is the classic miss?
In HNSW, what does efConstruction control versus efSearch — and which of the two is a query-time cost you pay on every request?
Why is "HNSW is faster than IVF" not falsifiable as stated, and what benchmark would make it a real comparison?