HNSW Explained: Hierarchical Navigable Small World Graphs
How the HNSW index works: multi-layer navigable small-world graphs, greedy descent, and why it dominates modern vector search.
Published on • November 22, 2026
AI Assistant

Introduction
If you open almost any vector database today — Milvus, Qdrant, Weaviate, pgvector’s HNSW, FAISS — the default index is HNSW: Hierarchical Navigable Small World graphs. Proposed by Malkov and Yashunin in 2016, it delivers state-of-the-art recall-latency trade-offs with a beautifully simple idea: layer a highway system on top of a neighbourhood map.
The Intuition
Two classic graph ideas combine:
- Small-world graphs — most nodes are close neighbours of each other, with occasional long-range “shortcut” edges. You can reach any node in a few hops.
- Hierarchy — put the sparsest, longest-range edges on top; add denser local layers below.
HNSW builds exactly this: a multi-layer structure where the top layers contain few nodes with long edges (fast long-distance travel) and the bottom layer contains every node with short edges (precise local search).
How HNSW Is Built
From the paper (arXiv:1603.09320), insertion works incrementally:
- Assign each new element a maximum layer
ldrawn from an exponential distribution — most elements land on the bottom layer, a lucky few reach the top. - Start from the entry point of the topmost layer and greedily descend: at each layer, walk to the neighbour closest to the new element until no improvement is possible.
- From layer
ldown to layer 0, insert the new element and connect it to itsMnearest neighbours found so far. - Prune connections that would exceed
M(using a heuristic, not just distance).
The result is a graph where long-range edges live high up and dense connectivity lives at the bottom.
How Search Works
Search mirrors insertion:
- Enter at the top-layer entry point.
- Greedily descend layer by layer, always moving to the closest unvisited neighbour.
- At layer 0 (containing all elements), run a best-first search with a dynamic candidate list of size
ef— collect thekbest results found before the candidate list is exhausted.
Because upper layers are sparse, the query reaches the right region in O(log n) hops; layer 0 then polishes the result set.
Why HNSW Won
- High recall at low latency — routinely ≥0.95 recall with millisecond queries
- Predictable, tunable —
efSearchtrades latency for recall per query - Dynamic inserts — new vectors can be added without full rebuilds
- No quantisation required — works on raw float vectors (though it composes well with PQ)
Costs
- Memory: the graph stores up to
M(×2 for the upper layers) neighbour IDs per node — often as much as the vectors themselves. - Build time: incremental insertion is O(n log n)-ish; large corpora take minutes to hours.
- No native filtering: filters are applied during/after traversal, which can hurt recall when filters are selective (see the pre/post-filter problem).
Conclusion
HNSW’s genius is turning “search a billion points” into “take the highway down, then walk the neighbourhood.” It remains the default graph index for good reason: excellent recall, per-query tunability, and online inserts — at the price of memory you must budget for.