Comparing HNSW and IVF as the retrieval index
HNSW is a memory-hungry proximity graph with high recall and low latency; IVF clusters vectors and scans only nprobe lists, trading recall for cheaper memory and faster builds.
Imagine finding the closest house to yours in a huge city. HNSW is like a friend who already walked every street and built a network of shortcuts — ask and they hop neighbor to neighbor straight to the closest house, fast, but holding all those shortcuts in their head takes a lot of room. IVF is like splitting the city into postal zones first. You only walk the few zones nearest your address. That is much less effort to set up, but if you check too few zones you might miss the truly closest house sitting just over a zone boundary. The number of zones you agree to check is a dial — check more for accuracy, fewer for speed. Both methods give you a very-close answer, not a guaranteed-perfect one.
Concept explanation~2 min read
Everything you need to truly understand this topic: intuition, mechanics, step by step explanation, code, formulas, and worked example. Click to expand.
Concept explanation~2 min read
Everything you need to truly understand this topic: intuition, mechanics, step by step explanation, code, formulas, and worked example. Click to expand.
Almost every RAG system rests on an approximate nearest-neighbor index, and the two names you will be asked to compare are HNSW and IVF. The question is rarely "define them" — it is "which would you pick and why," which is really a question about resource constraints. Get the mechanism right and the trade-offs fall out naturally.
The trap is treating one as universally better. HNSW is the popular default, so candidates reach for it reflexively and forget that at billion-vector scale the memory and build cost can make it the wrong call. The strong answer names the binding constraint first, then maps it to the index whose costs you can afford to pay.
How the HNSW graph walk actually finds neighbors
HNSW stands for Hierarchical Navigable Small World. Picture a stack of graphs. The bottom layer contains every vector, each linked to its nearby neighbors. Each higher layer is a sparser sample, so the top layer has only a few long-range nodes acting like an express highway.
A query enters at the top. It greedily hops to whichever neighbor is closer to the query, then drops a layer and repeats, refining locally until it can't improve. The candidate frontier width is set by efSearch: a larger value explores more nodes per step, lifting recall at the cost of latency. The graph density per node is set by M at build time.
The payoff is that the number of hops grows only logarithmically with dataset size, so latency stays low even as the corpus grows. The bill comes due in memory and build time. Every node stores M edges per layer, which inflates the footprint to roughly 1.5x to 2x the raw vectors. And construction is sequential-ish — each insert searches the existing graph to find its neighbors — so building on hundreds of millions of vectors can take hours.
Situations where this technique stops working.
2–4 min · Everything important, quickly.
| Dimension | HNSW (graph) | IVF / IVFPQ (clustering) |
|---|---|---|
| Mechanism | Greedy walk over a multi-layer proximity graph | Scan the nprobe nearest k-means clusters |
| Recall | High out of the box | Depends on nprobe; tunable up at latency cost |
| Query latency | Low, near constant with dataset size | Higher; grows with nprobe and list size |
| Memory | High (graph edges, ~1.5-2x vectors) | Low, especially with product quantization |
| Build time | Slow, hard to parallelize | Fast, embarrassingly parallel k-means |
| Key knobs | M, efConstruction, efSearch | nlist, nprobe, PQ code size |
Real products, models, and research that use this idea.
- Pinecone and Qdrant default to HNSW for low-latency, high-recall serving on RAM-resident indexes.
- FAISS ships IVF and IVFPQ as the go-to for billion-scale indexes where memory and build time dominate.
What an interviewer would ask next. Try answering before peeking at the approach.
QHow do efSearch in HNSW and nprobe in IVF play analogous roles?
Both widen the search frontier to trade latency for recall. Contrast efSearch growing the candidate list during the graph walk versus nprobe adding more clusters to scan.
Red flags & common mistakes
The phrases that signal junior thinking. Click to expand.
Red flags & common mistakes
The phrases that signal junior thinking. Click to expand.
Calling HNSW an exact method. It is approximate — the greedy graph walk can settle in a local minimum and miss the true nearest neighbor, same as IVF can miss a cluster.
60 second bullets to scan on the way to the call.
Why both HNSW and IVF are approximate, not exact
How the HNSW greedy descent uses sparse top layers
Primary sources. Browse if you want the original framing.
Same topic, related formats. Practice these next.