HNSW: Hierarchical Navigable Small World GraphsOpen in Colab

HNSW: Hierarchical Navigable Small World Graphs

The vector-databases wiki names HNSW as the default ANN index in most modern vector databases (FAISS, Qdrant, Weaviate, pgvector, Milvus, Redis). This page opens the box: what the "hierarchical" and "navigable small world" parts actually are, the exact search and insert procedures, a worked trace, and the operational gotchas that make HNSW excellent for read-heavy corpora and awkward for churny ones.

The one-sentence idea: build a multi-layer proximity graph (a skip-list for geometry), then answer a query by greedily hopping along edges toward it, coarse layers first, then fine.

Two ingredients

Navigable Small World (NSW). Connect each vector to its near neighbours so the whole set becomes one graph. "Small world" means: even though every node only links to a handful of others, any two nodes are reachable in a short number of hops (like social networks — six degrees of separation). Searching is then just greedy graph traversal: from the current node, jump to whichever neighbour is closest to the query, repeat until no neighbour is closer. The flaw of a single-layer NSW is that greedy search can get stuck in a local minimum far from the true neighbour, and early hops move only a tiny distance.

Hierarchy (the skip-list trick). A skip list speeds up a linked list by adding sparse "express lanes" on top. HNSW does the same in metric space: a sparse top layer with long-range links lets search teleport across the space in a few big hops, then each lower layer is denser and refines the position, until layer 0 (which contains every point) does the fine-grained search.

Layer assignment is random and exponential

Each inserted point gets a maximum layer ℓ\ell drawn from a geometric distribution: ℓ=⌊−ln⁡(U)⋅mL⌋\ell = \lfloor -\ln(U)\cdot m_L \rfloor with U∼Uniform(0,1)U \sim \text{Uniform}(0,1) and mL=1/ln⁡Mm_L = 1/\ln M. So a point lands on layer ℓ\ell with probability ∝e−ℓ/mL\propto e^{-\ell/m_L} — most points live only on layer 0, a few reach higher, exactly one (in expectation) tops out. Layer 0 holds all NN points; each layer up holds roughly a factor 1/M1/M fewer.

Skip lists from first principles

The "hierarchy" in HNSW is lifted directly from the skip list, so it pays to build the skip list up from nothing first — the HNSW mapping then falls out for free.

Start with a sorted linked list. Nodes 3 → 8 → 15 → 22 → 34 → 41 → 55 chained by next pointers. To find 34 you must walk from the head one link at a time: 3, 8, 15, 22, 34 — five comparisons. Search is O(N)O(N) because a linked list gives you no way to skip ahead. (A sorted array would allow binary search, but then inserts are O(N)O(N) because you must shift elements — the linked list keeps inserts O(1)O(1) once you know where.)

Add one express lane. Now build a second list on top that contains only every other node: 3 → 15 → 34 → 55. Each express node keeps a down pointer to its twin in the base list. To find 41:

  1. Level 1 (express): from 3, is next (15) still ≤ 41? Yes, move. From 15, is next (34) ≤ 41? Yes, move. From 34, is next (55) ≤ 41? No — overshoot. Drop down.
  2. Level 0 (base): from 34, walk 41. Found.

You examined 3, 15, 34, 41 instead of all seven. The express lane let you skip the region between checkpoints, then you descended only for the final fine-grained step.

Stack more lanes → logarithmic search. With LL levels, each holding half the nodes of the one below, the top lane has ≈N/2L\approx N/2^{L} nodes. At every level you take at most a couple of steps before overshooting and dropping down, and there are ≈log⁡2N\approx \log_2 N levels, so search is O(log⁡N)O(\log N). That is the whole trick: sparse-on-top layers turn a linear walk into a logarithmic one, without giving up cheap inserts.

Why the levels are random, not every-other

Maintaining a perfect every-other spacing under insert/delete would cost O(N)O(N) rebalancing — the exact problem the linked list was chosen to avoid. So real skip lists assign each new node a level by coin flips: keep flipping, and while it comes up heads, promote the node one level up. A node reaches level ℓ\ell with probability (1/2)ℓ(1/2)^{\ell} — the same exponential thinning as every-other spacing, but achieved locally with zero rebalancing. HNSW's ℓ=⌊−ln⁡(U) mL⌋\ell = \lfloor -\ln(U)\,m_L\rfloor (the callout above) is exactly this geometric distribution, with base MM instead of 22 so each layer thins by 1/M1/M.

The exact HNSW ↔ skip-list mapping

HNSW is a skip list where the one-dimensional sorted order is replaced by a proximity graph in dd dimensions. Everything else is the same structure:

Skip list (1-D, ordered)HNSW (metric space, dd-D)
Node's position = its key, on a total orderNode's position = its vector; only relative distances exist
"Move to next while next ≤ target""Move to the neighbour closest to the query" (greedy)
Each level is a sorted sub-list (express lane)Each level is a navigable small-world sub-graph
A level holds every ≈2\approx 2nd node below itA level holds every ≈M\approx Mth node below it
Random level via coin flips, P(ℓ)=(1/2)ℓP(\ell)=(1/2)^\ellRandom level via −ln⁡(U) mL-\ln(U)\,m_L, P(ℓ)∝e−ℓ/mLP(\ell)\propto e^{-\ell/m_L}
Search: descend levels, walk right, drop at overshootSearch: descend levels greedy (ef=1), then a width-ef beam on layer 0
Bottom level = full sorted listLayer 0 = graph over all NN points

The single crucial difference is why a level needs more than one link per node. In a sorted list "closer to the target" has exactly one direction (forward), so one next pointer suffices. In dd dimensions the query can be in any direction, so each node needs a small set of edges (M of them) fanning out in different directions, and the greedy walk picks whichever edge points most toward the query. That is the "navigable small world" part doing the job the total order does for free in 1-D, and it is why HNSW spends M and the neighbour-selection heuristic to keep those edges pointing in genuinely different directions.

The analogy has a limit: no total order means no guarantees

A skip list's ordering guarantees greedy descent always lands on the exact key. HNSW has no total order, so greedy graph search can still stall in a local minimum, which is precisely why layer 0 widens from a 1-step walk into a width-efSearch beam, and why HNSW is approximate where a skip list is exact.

The three knobs

ParameterWhat it controlsTrade-off
Mmax edges per node on layers ≥ 1 (layer 0 uses M0=2MM_0 = 2M)↑ recall & degree, ↑ memory & build time
efConstructionbeam width while inserting (how hard we search for a new node's neighbours)↑ graph quality & recall, ↑ build time
efSearch (ef)beam width while querying↑ recall, ↑ query latency: the runtime recall/latency knob

Typical defaults: M = 16, efConstruction = 200, efSearch = 50–200. Only efSearch is a query-time knob; M and efConstruction are baked into the index at build.

Search: greedy descent, then a beam

Search has two phases. Phase 1 (layers above 0) is a plain greedy walk with beam width 1 — from the entry point, repeatedly move to the closest neighbour to the query until none is closer, then drop the result down one layer to use as the entry point for the next. Phase 2 (layer 0) runs a beam search of width ef and returns the best kk.

The layer-0 beam is SEARCH-LAYER, which maintains two heaps — a candidate frontier and a dynamic result set of size ef:

Text
SEARCH-LAYER(q, entry_points, ef, layer):
  visited   ← set(entry_points)
  candidates ← min-heap of entry_points keyed by dist(·, q)   # frontier
  results    ← max-heap of entry_points keyed by dist(·, q)   # best-so-far, capped at ef
  while candidates not empty:
    c ← extract-nearest(candidates)
    f ← farthest(results)
    if dist(c, q) > dist(f, q):  break        # frontier can't improve results
    for e in neighbours(c, layer):
      if e not in visited:
        visited.add(e)
        f ← farthest(results)
        if dist(e, q) < dist(f, q) or |results| < ef:
          candidates.push(e);  results.push(e)
          if |results| > ef:  results.pop-farthest()
  return results

Phases 1..L are the same routine with ef = 1. The early-exit if dist(c,q) > dist(f,q): break is what keeps it sub-linear: once the nearest unexplored candidate is farther than the current worst result, no unexplored node can improve the answer.

Text
SEARCH(q, k, efSearch):
  ep ← enter_point                                  # the single top-layer node
  for layer in L, L-1, ..., 1:                       # greedy descent, ef = 1
    ep ← SEARCH-LAYER(q, {ep}, ef=1, layer)          # best node at this layer
  W  ← SEARCH-LAYER(q, {ep}, ef=efSearch, layer=0)   # wide beam on the base layer
  return k nearest of W

Insertion reuses search

To insert a new point xx: (1) draw its top layer ℓ\ell; (2) greedy-descend from the entry point down to layer ℓ+1\ell+1 exactly like a query; (3) from layer ℓ\ell down to 0, run SEARCH-LAYER with ef = efConstruction to collect candidates, select up to M neighbours (with a heuristic that prefers spread-out neighbours over clustered ones — this keeps the graph navigable), and add bidirectional edges. When adding an edge overflows a node's degree past M (or M0M_0 on layer 0), prune it back with the same heuristic. If ℓ\ell exceeds the current top, xx becomes the new entry point.

The neighbour-selection heuristic matters

Naively linking a new node to its MM nearest neighbours creates redundant edges into one dense clump and leaves "bridges" between clusters unbuilt — search then gets trapped. HNSW's heuristic keeps an edge to a candidate only if that candidate is closer to xx than to any already-selected neighbour, favouring diverse directions. This is what makes the small world actually navigable.

A worked search trace

Take 1-D points (so "distance" is just ∣a−b∣|a-b|) at positions 0, 8, 16, 24, 32, 40, 48, 56 with a tiny two-layer graph:

  • Layer 1 (express lane): {0, 24, 48}, chained 0—24—48.
  • Layer 0 (all points): each linked to its immediate neighbours, e.g. 24—32—40.

Query q=34q = 34, efSearch = 2, entry point 24 (top layer). Step through both phases — the greedy descent, then the beam — with the frontier, the capped result set, and the visited set all visible as they change:

HNSW search — greedy descent, then a width-ef beam

1/16

Eight points on a line at 0, 8, 16, 24, 32, 40, 48, 56 — so "distance" is just |p − q|. Layer 1 is the express lane holding only {0, 24, 48}; layer 0 holds every point chained to its immediate neighbours. The query is q = 34, whose true nearest neighbour is 32.

python
1def search_layer(q, entry, ef, layer):
2 visited = set(entry)
3 # frontier, and the best-so-far capped at ef
4 candidates = min_heap(entry, key=dist_to_q)
5 results = max_heap(entry, key=dist_to_q)
6 while candidates:
7 c = candidates.pop_nearest()
8 if dist(c, q) > dist(results.farthest(), q):
9 break # frontier can't improve
10 for e in neighbours(c, layer):
11 if e in visited:
12 continue
13 visited.add(e)
14 worst = results.farthest()
15 if dist(e, q) < dist(worst, q) or len(results) < ef:
16 candidates.push(e)
17 results.push(e)
18 if len(results) > ef:
19 results.pop_farthest()
20 return results
21
22def search(q, k, ef_search):
23 ep = enter_point # single top-layer node
24 # greedy descent with ef = 1
25 for layer in range(L, 0, -1):
26 ep = search_layer(q, {ep}, ef=1, layer)
27 W = search_layer(q, {ep}, ef=ef_search, layer=0)
28 return nearest(W, k)
state
index — q = 34 (efSearch = 2)
L102448L008162432404856
|p − q| for every point (q = 34)
0
34
8
26
16
18
24
10
32
2
40
6
48
14
56
22

The hierarchy is a skip list for geometry: the sparse top layer teleports you near the answer in one look, the dense bottom layer refines it.

The full SEARCH procedure on a two-layer index over eight points on a line, querying q = 34. Phase 1 walks the sparse express lane with a beam of 1 and stops as soon as no neighbour improves; phase 2 runs the real SEARCH-LAYER beam on layer 0, maintaining a frontier and an ef-capped result set. Watch for the break at the end: once the nearest unexplored candidate is farther than the worst kept result, search stops — that early exit is the whole reason HNSW is sub-linear.

The three moments worth pausing on:

  1. Layer 1, greedy (ef = 1). At 24 (d=10d = 10), neighbours 48 (d=14d = 14) and 0 (d=34d = 34) are both worse, so the walk stops immediately and descends with ep = 24. One look at the express lane skipped most of the line.
  2. Layer 0, beam (ef = 2). Expanding 24 reaches 32 (d=2d = 2), which evicts 16 (d=18d = 18) from the capped result set. Expanding 32 reaches 40 (d=6d = 6) — worse than 32, but still kept, because the beam holds two results and a worse node can still be a bridge to a better one. That is precisely what ef buys you over a plain greedy walk.
  3. The early exit. The frontier still holds 16 (d=18d = 18), but that is already farther than the worst kept result 40 (d=6d = 6), so nothing reachable through it can improve the answer → break.

Return 32, the true nearest neighbour of 34. Layer 0 touched 5 of 8 nodes and never looked at 0, 8 or 56. At corpus scale that ratio is what turns O(N)O(N) into roughly O(log⁡N)O(\log N).

Complexity & when to use it

AspectCost
Query≈O(log⁡N)\approx O(\log N) hops, each visiting up to MM neighbours × ef frontier
Build≈O(Nlog⁡N)\approx O(N \log N) distance computations
Memoryvectors plus the graph: ≈N⋅(M0+ℓˉ M)\approx N \cdot (M_0 + \bar{\ell}\,M) edge ids: often the dominant cost

Reach for HNSW when the corpus is large, read-heavy, and fits in RAM, and you want very high recall at very low latency without tuning cluster counts. Look elsewhere when (a) memory is tight at billion scale — combine with product quantization (see the vector-databases wiki) or use IVF-PQ on disk; (b) the corpus churns constantly — HNSW has no true delete (see below); (c) you need exact results — use a flat index.

Gotchas

  1. Deletes are hard. Removing a node would strand its neighbours' edges, so most implementations only tombstone (mark deleted, skip at return time) and reclaim space on a periodic full rebuild. A high delete/update rate degrades recall and bloats memory until you rebuild.
  2. Memory is the real bill. The graph is stored on top of the raw vectors. With M = 64 on high-dim vectors the edge lists can rival the vectors themselves.
  3. efSearch < k is a bug. The beam must be at least as wide as the number of results you want; a common mistake is asking for top-100 with ef = 50.
  4. M too low starves recall; too high wastes memory and slows build with diminishing recall returns — sweep it against a flat-index ground truth.
  5. Metric mismatch, same as any index. Build and query with the same distance, and L2L_2-normalize first if you want cosine to behave like the faster inner product (see the vector-databases wiki).
  6. Non-determinism. Random layer assignment means two builds of the same data give slightly different graphs and recall; fix the seed to reproduce benchmarks.

Related concepts

Concept neighbourhood

How this concept connects — click any node to jump there, or explore the whole concept map.

RelatedReferenced by
HNSW: Hierarchical Navigable Smal…Vector Databases & ANN In…BM25: Lexical RankingEmbeddings & Semantic Sea…Retrieval-Augmented Gener…K-Means Clustering