Hierarchical Navigable Small World (HNSW)
What You'll Learn
You'll understand how HNSW creates a multi-layered graph structure that enables blazingly fast approximate nearest neighbor search—often considered the best speed-accuracy trade-off available today.
The Core Idea
HNSW builds a multi-layer graph where each vector becomes a node connected to its neighbors. Think of it like a highway system: the top layers are express highways connecting distant cities (long-range connections), while bottom layers are local streets connecting nearby houses (short-range connections).
When searching, you start at the top layer and quickly jump across the "highway" to get close to your target. Then you descend layer-by-layer, using progressively more detailed "local roads" until you reach the exact neighborhood containing your nearest neighbors.
Why "Small World"?
The "small world" property means you can reach any node from any other node in surprisingly few hops—similar to "six degrees of separation" in social networks. HNSW exploits this by organizing connections so that distant vectors remain reachable quickly.
Why "Hierarchical"?
The hierarchy comes from stacking multiple layers. Upper layers are sparse (fewer nodes, longer connections), while lower layers are dense (all nodes, local connections). This structure lets you efficiently zoom from coarse to fine-grained search.
Why It Wins
HNSW typically outperforms IVF and LSH in both speed and accuracy because:
- Greedy search through layers is extremely fast
- No clustering overhead like IVF
- Insert-friendly: adding new vectors doesn't require rebuilding the entire index
The trade-off? Higher memory usage since it stores the full graph structure.
Key Takeaway: HNSW uses a multi-layer graph with highway-like connections at the top and neighborhood streets at the bottom, delivering exceptional search speed and accuracy—making it the go-to index for modern vector databases.