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 drawn from a geometric distribution: with and . So a point lands on layer with probability — most points live only on layer 0, a few reach higher, exactly one (in expectation) tops out. Layer 0 holds all points; each layer up holds roughly a factor 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 because a linked list gives you no way to skip ahead. (A sorted array would allow binary search, but then inserts are because you must shift elements — the linked list keeps inserts 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:
- Level 1 (express): from
3, isnext(15) still≤ 41? Yes, move. From15, isnext(34)≤ 41? Yes, move. From34, isnext(55)≤ 41? No — overshoot. Dropdown. - Level 0 (base): from
34, walk41. 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 levels, each holding half the nodes of the one below, the top lane has nodes. At every level you take at most a couple of steps before overshooting and dropping down, and there are levels, so search is . 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 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 with probability — the same exponential thinning as every-other spacing, but achieved locally with zero rebalancing. HNSW's (the callout above) is exactly this geometric distribution, with base instead of so each layer thins by .
The exact HNSW ↔ skip-list mapping
HNSW is a skip list where the one-dimensional sorted order is replaced by a proximity graph in dimensions. Everything else is the same structure:
| Skip list (1-D, ordered) | HNSW (metric space, -D) |
|---|---|
| Node's position = its key, on a total order | Node'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 nd node below it | A level holds every th node below it |
| Random level via coin flips, | Random level via , |
| Search: descend levels, walk right, drop at overshoot | Search: descend levels greedy (ef=1), then a width-ef beam on layer 0 |
| Bottom level = full sorted list | Layer 0 = graph over all 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 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
| Parameter | What it controls | Trade-off |
|---|---|---|
| M | max edges per node on layers ≥ 1 (layer 0 uses ) | ↑ recall & degree, ↑ memory & build time |
| efConstruction | beam 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 .
The layer-0 beam is SEARCH-LAYER, which maintains two heaps — a candidate frontier and a dynamic result set of size ef:
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.
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 : (1) draw its top layer ; (2) greedy-descend from the entry point down to layer exactly like a query; (3) from layer 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 on layer 0), prune it back with the same heuristic. If exceeds the current top, becomes the new entry point.
The neighbour-selection heuristic matters
Naively linking a new node to its 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 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 ) at positions
0, 8, 16, 24, 32, 40, 48, 56 with a tiny two-layer graph:
- Layer 1 (express lane):
{0, 24, 48}, chained0—24—48. - Layer 0 (all points): each linked to its immediate neighbours, e.g.
24—32—40.
Query , 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
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.
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:
- Layer 1, greedy (
ef = 1). At24(), neighbours48() and0() are both worse, so the walk stops immediately and descends withep = 24. One look at the express lane skipped most of the line. - Layer 0, beam (
ef = 2). Expanding24reaches32(), which evicts16() from the capped result set. Expanding32reaches40() — worse than32, 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 whatefbuys you over a plain greedy walk. - The early exit. The frontier still holds
16(), but that is already farther than the worst kept result40(), 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 into roughly .
Complexity & when to use it
| Aspect | Cost |
|---|---|
| Query | hops, each visiting up to neighbours × ef frontier |
| Build | distance computations |
| Memory | vectors plus the graph: 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
- 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.
- Memory is the real bill. The graph is stored on top of the raw vectors. With
M = 64on high-dim vectors the edge lists can rival the vectors themselves. efSearch < kis 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 withef = 50.Mtoo low starves recall; too high wastes memory and slows build with diminishing recall returns — sweep it against a flat-index ground truth.- Metric mismatch, same as any index. Build and query with the same distance, and -normalize first if you want cosine to behave like the faster inner product (see the vector-databases wiki).
- 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
- Vector Databases & ANN Indexes: where HNSW sits among IVF, PQ, and flat, and the recall/latency framing
- BM25 Ranking: the sparse/keyword retriever HNSW's dense search is fused with in hybrid search
- Embeddings & Semantic Search: where the vectors HNSW indexes come from
- Retrieval-Augmented Generation: the retriever HNSW powers at scale
- K-Means: the coarse quantizer behind the IVF alternative