The "Highway" Approach
HNSW (Hierarchical Navigable Small World) is currently the most widely used ANN algorithm in production vector databases. It consistently delivers the best speed-recall trade-off for in-memory datasets and is the default index type in Pinecone, Weaviate, Qdrant, and others.
The intuition comes from navigating an unfamiliar city. If you want to find the nearest coffee shop, you don't walk down every street. You start on the highway to get to the right part of the city, take arterial roads to the right neighborhood, then walk local streets to find the exact shop.
HNSW builds a multi-layered graph of your vectors:
- Top layer (sparse): Contains only a small random subset of vectors. Each node connects to a few distant neighbors via "long-range" links. This layer lets you traverse the data space in large leaps.
- Middle layers: Progressively denser. Connections become shorter-range as you descend.
- Bottom layer (dense): Contains every vector. Connections are short-range, linking each vector to its true nearest neighbors.
Search procedure: Start at an entry point in the top layer. Greedily move to whichever neighbor is closest to the query vector. When you can't get closer in the current layer, drop down to the next layer and repeat. By the time you reach the bottom layer, you are already in the right neighborhood — so only a small local search is needed to find the final answer.
HNSW trade-offs:
- ✅ Excellent recall (typically >98%) with fast query times
- ✅ No training step required — vectors can be added incrementally
- ✅ Tunable via ef_construction (build quality) and ef_search (query recall)
- ❌ High memory usage — the entire graph must fit in RAM
- ❌ Slower index build time than IVF
- ❌ Deletion is expensive (requires marking nodes as deleted, periodic cleanup)
When to choose which:
| Scenario | Recommended Index |
|---|---|
| Dataset fits in RAM, need best recall | HNSW |
| Dataset is billions of vectors, memory-constrained | IVF (with quantization) |
| Data changes frequently (inserts/deletes) | HNSW |
| Batch ingestion, static dataset | IVF |
A common interview question: "What's the difference between IVF and HNSW, and when would you choose one over the other?" The concise answer: HNSW is a graph-based index that lives in memory and delivers superior recall with no training step — ideal for dynamic, in-memory datasets. IVF is a cluster-based index that supports compression and works for datasets too large to fit in RAM. In practice, most managed vector databases (Pinecone, Weaviate) default to HNSW because most production RAG datasets fit comfortably in memory and recall quality is paramount.