Skip to content
Blog

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:

  1. 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.
  2. 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:

  1. Assign each new element a maximum layer l drawn from an exponential distribution — most elements land on the bottom layer, a lucky few reach the top.
  2. 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.
  3. From layer l down to layer 0, insert the new element and connect it to its M nearest neighbours found so far.
  4. 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:

  1. Enter at the top-layer entry point.
  2. Greedily descend layer by layer, always moving to the closest unvisited neighbour.
  3. At layer 0 (containing all elements), run a best-first search with a dynamic candidate list of size ef — collect the k best 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 — efSearch trades 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.

References