HNSW, annotated

How to read this page

Any dotted word explains itself when you hover it, tab to it or tap it; so does every symbol in every equation. Each idea climbs the same ladder: an everyday picture, a tiny example, a diagram or demo, the math, and why it still matters. If you only have five minutes, jump to the live HNSW, click anywhere, and press Step. The vector index lesson implements the same algorithm in Python and benchmarks it against exact search.

Abstract · original

“The maximum layer in which an element is present is selected randomly with an exponentially decaying probability distribution.”Malkov and Yashunin, Abstract

Everyday picture

To drive to a house in a city you have never visited, you take the motorway to the right region, then main roads to the right district, then side streets to the right door. You never look at most of the city's streets. HNSW builds that road network for a cloud of points: a sparse top layer of long “motorway” links, denser layers of shorter links underneath, and a bottom layer that connects every point to its near neighbours.

What the paper claims

• A fully graph-based approximate nearest-neighbour index, with no separate tree or clustering needed to find a starting point.
• Search cost that grows only logarithmically with the number of stored points.
• A neighbour-selection rule that keeps the graph connected even on highly clustered data.
• Much faster than the open-source competition of the time at the same recall.

Why it matters today

When a RAG system finds the 10 passages closest to your question among millions in a few milliseconds, the index doing the work is very often HNSW. DPR, for example, used FAISS's HNSW index to answer 995 questions per second over 21 million passages.

1 Introduction · original

Everyday picture

“Find the 10 most similar songs to this one” is a K-nearest-neighbour search. The honest way is to measure the distance to every song in the catalogue: fine for a thousand songs, hopeless for a billion. And in the hundreds of dimensions that embeddings use, the clever exact tricks that work on a 2-D map stop helping: the curse of dimensionality. So we accept being approximately right: return 10 songs that are nearly always the true 10, very quickly.

Tiny example: recall

The true 5 nearest neighbours of a query are points {3, 8, 11, 20, 42}. An approximate search returns {3, 8, 11, 20, 57}. Four of the five are right, so recall is 4 / 5 = 0.8.

In words: “the share of the true K nearest neighbours that the search actually found.”

With the numbers: |{3, 8, 11, 20}| / 5 = 4 / 5 = 0.8.

In Python:

# the true K nearest neighbours
true = {3, 8, 11, 20, 42}
# what the approximate search returned
found = {3, 8, 11, 20, 57}
K = len(true)
# found ∩ true
sorted(found & true)  # → [3, 8, 11, 20]
# recall
len(found & true) / K  # → 0.8

The families of approximate search

• Trees (kd-trees and relatives): split space into boxes. Great in low dimensions, weak in high.
• Hashing (LSH): hash nearby points into the same buckets.
• Product quantization: compress vectors into short codes and compare codes.
• Proximity graphs: link each point to its neighbours and walk the links. Best in high dimensions, but plain versions degrade badly on low-dimensional or clustered data. HNSW is a proximity graph that fixes that.

2 Related work: greedy walks and small worlds · original

Everyday picture

In the famous 1960s Milgram experiment, people passed a letter towards a stranger only through personal acquaintances, each choosing the friend they thought “closest” to the target. Letters often arrived in a handful of hops. Networks where such local, greedy choices reach any target in few steps are called navigable small worlds.

2.1 Greedy search on a proximity graph

Start at some node. Look at its neighbours; move to whichever is closest to the query. Repeat until no neighbour is closer. On the ideal graph for this (the Delaunay graph) greedy search always finds the true nearest neighbour, but that graph cannot be built efficiently in high dimensions, so practical systems approximate it by linking each point to its nearest neighbours (a k-NN graph). Two problems follow: the number of steps grows as a power of the dataset size, and on clustered data the graph can split into islands that the walk cannot cross.

Navigable Small World (NSW), the authors' earlier method

Insert points one at a time in random order, linking each new point to the M closest points already present. The early points' links were made when the graph was sparse, so they are long; they become the “bridges” that let a greedy walk cross the space quickly. NSW search takes a polylogarithmic number of steps: good, but it still suffered badly on low-dimensional data, sometimes losing to trees by orders of magnitude.

2.2 Why the name

Kleinberg showed that a grid with extra long-range links, drawn with just the right distribution of lengths, is navigable. That requires knowing the data's layout in advance. NSW builds navigability without that knowledge, just from insertion order. HNSW goes one step further and makes the scales of the links explicit.

3 Motivation: separate the links by length · original

“The idea of Hierarchical NSW algorithm is to separate the links according to their length scale into different layers and then search in a multilayer graph.”Malkov and Yashunin, §3

Everyday picture

In NSW the motorways and side streets are all mixed on one map, so at every junction you must look at many roads. HNSW prints separate maps: a motorway map with only a few towns, a main-road map with more, and a street map with everything. You zoom in map by map, and on each map only a handful of roads leave each place.

Tiny example: the one-dimensional version is a skip list

The paper points out that HNSW generalises a classic data structure, the skip list. Numbers are kept sorted in a bottom lane; some are promoted at random to an express lane above, fewer again to a lane above that. To find a number, run along the top lane until the next stop would overshoot, then drop down a lane and continue.

Reading it: each row is a lane and each box a stored number; a box appears in the upper lanes only if it was promoted. Pick a target. The red path starts at the top-left and runs right along the express lane while the next box is not past the target, then drops down, and so on until it reaches the target in the bottom lane. The readout counts comparisons: far fewer than walking the bottom lane from the start. HNSW does the same thing with proximity graphs instead of lanes: “not past the target” becomes “closer to the query”.

How a point's top layer is chosen

Each new point draws a random level l. It appears in layers 0, 1, …, l. Most points get l = 0; a few get 1; very few get 2.

In words: “draw a random number between 0 and 1, take minus its natural log (a random amount that is usually small but occasionally large), scale it by m_L, and round down.”

With the numbers: with M = 16, m_L = 1 / ln 16 = 0.361. A draw of 0.5 gives −ln 0.5 × 0.361 = 0.25, rounded down to level 0. A draw of 0.01 gives −ln 0.01 × 0.361 = 4.61 × 0.361 = 1.66, level 1. A point reaches level 2 only if its draw is below e^−2/0.361 = 1/256.

In Python:

import math
M = 16
m_L = 1 / math.log(M)
round(m_L, 3)  # → 0.361
# two random draws
for unif in (0.5, 0.01):
    x = -math.log(unif) * m_L
    # the value, and l after rounding down
    print(round(x, 2), math.floor(x))  # → 0.25 0 1.66 1
# reaching level 2 needs a draw below 1/256
round(1 / math.exp(-2 / m_L))  # → 256

The neighbour-selection heuristic (Figure 2)

Everyday picture

If you may keep only three phone numbers, keeping three people from the same office is wasteful: they will all give you the same directions. Keep one from your office and use the other slots for people in other directions. HNSW's heuristic does this: it adds a candidate neighbour only if the candidate is closer to the new point than to any neighbour already chosen.

Reading it: the grey dots form two separate clusters; the green dot is a new point being inserted on the edge of cluster 1, allowed M = 3 links (red). With simple selection it links to its three nearest points, all in cluster 1, so nothing connects the two clusters and a search that starts in cluster 1 can never reach cluster 2. With the heuristic, candidates are taken nearest first and a candidate is kept only if it is closer to the new point than to every link already kept. The second-nearest cluster-1 point is rejected (it is closer to the first link), and a point in cluster 2 is accepted: a bridge. The readout lists each candidate's verdict and the two distances that decided it.

In words: “accept a candidate only if it is nearer to the new point than to any neighbour already accepted; stop when M are accepted.”

With the numbers: on a line, the new point q sits at 0 and the candidates, nearest first, sit at 1, 1.5 and −2. The one at 1 is kept, since nothing has been accepted yet. The one at 1.5 is 1.5 from q but only 0.5 from the kept 1, so it is rejected. The one at −2 is 2 from q and 3 from the kept 1, so it is kept: a link in the other direction. The demo's readout prints the same two distances for each of its candidates.

In Python:

import math
# the new point
q = 0
# neighbours accepted so far
R = []
# candidates, nearest first
for e in [1, 1.5, -2]:
    # d(e, q)
    d_eq = abs(e - q)
    # min over r in R of d(e, r)
    d_eR = min((abs(e - r) for r in R), default=math.inf)
    if d_eq < d_eR:
        R.append(e)
R  # → [1, -2]

Why it matters

Diverse links are what let a greedy walk escape a cluster. The paper found the heuristic always performed at least as well as simple selection, and much better on low-dimensional and clustered data. With enough candidates it recovers the relative neighbourhood graph, a sparse graph known to stay connected.

4 The algorithm · original

Everyday picture

Searching and inserting are the same walk. To search, enter at the top, walk greedily to the closest point on each layer, drop down, and at the bottom widen the search into a careful local exploration. To insert, do exactly that search for the new point, then link it to good neighbours on every layer from its own top level down.

Reading it: the two things you do with an index sit on top: building it (INSERT) and querying it (K-NN-SEARCH). Both are built on one workhorse, SEARCH-LAYER, which finds the ef closest points to a target on a single layer, starting from given entry points. INSERT additionally chooses which of those points to link to, with either the simple rule or the heuristic from the previous section. Hover each box for the exact steps.

SEARCH-LAYER in one paragraph

Keep two lists: candidates still to explore, and the best ef found so far. Repeatedly take the closest unexplored candidate. If it is farther than the worst of the best-ef list, stop: nothing left can improve the answer. Otherwise look at each of its neighbours you have not seen yet; any that beats the worst of the best-ef list (or if that list is not full) joins both lists, and the list is trimmed back to ef. This is a beam search whose width is ef: with ef = 1 it is plain greedy walking.

Try it: a live HNSW, searched one step at a time

Below, 160 points on a plane (mostly in five clusters, some scattered) have been inserted into an HNSW with Algorithm 1 and the heuristic (levels are capped at 3 so every layer fits on screen). Each panel is one layer of the same plane. Click anywhere on a panel to place a query (the green dot), then press Step repeatedly, or Play.

Reading it: panels run from the top layer (few points, long links) down to layer 0 (every point, short links). The dashed ring marks where the search enters each layer. On the upper layers the red path is a greedy walk: at each point, every neighbour's distance is computed (orange rings) and the search moves to the closest, until no neighbour is closer; then it drops to the same point one layer down. On layer 0 the search widens into the beam search: orange-filled points have been explored, red rings are the current best-ef list. When it finishes, red-filled points are the returned 5 nearest and green rings mark the true 5 nearest from brute force, so you can see the recall directly. The counter compares distance computations with the 160 a brute-force search needs. Try efSearch = 1: the bottom layer becomes a plain greedy walk that keeps a single point, so it returns only one result and often stops in the wrong place (efSearch must be at least K = 5 to return 5 results). Raise efSearch and recall recovers at the cost of more distance computations. Lower M to 2 and watch the graph thin out and recall fall. On a real index with millions of points the same walk touches only a tiny fraction of them.

4.1 Construction parameters · original

Everyday picture

Four dials. M: how many roads leave each junction. M_max0: how many roads may leave a junction on the street map (layer 0). m_L: how quickly the maps thin out as you go up. efConstruction: how carefully each new junction is surveyed before its roads are built. The paper shows that only M really needs choosing.

• m_L = 1 / ln(M). This matches a skip list that promotes each element with probability 1/M, so each layer holds about 1/M of the one below it, and neighbours rarely overlap between layers.
• M_max0 = 2M. Setting it to M hurt performance badly at high recall; going above 2M wasted memory and slowed search.
• M from 5 to 48. Smaller M suits low recall or low-dimensional data; larger M suits high recall or high-dimensional data. Memory grows in proportion to M.
• efConstruction: large enough that searches during construction reach a recall near 0.95. On 10 million SIFT vectors, efConstruction = 100 built a reasonable index in about 3 minutes on a 40-core server; going higher bought little.

Tiny example: how many points per layer

From the level formula, the chance a point reaches layer k or higher is e^−k/m_L. With m_L = 1/ln M that is exactly M^−k (our derivation). With M = 16 and a million points: 1,000,000 at layer 0, about 62,500 at layer 1, 3,906 at layer 2, 244 at layer 3, 15 at layer 4 and about 1 at layer 5.

In words: “each layer up keeps about one point in M.”

With the numbers: 16⁻¹ = 6.25% of points reach layer 1, and 16⁻² = 0.39% reach layer 2.

In Python:

import math
M = 16
m_L = 1 / math.log(M)
# P(l ≥ 1) both ways
round(math.exp(-1 / m_L), 4), M ** -1  # → (0.0625, 0.0625)
# percent reaching layers 1 and 2
100 * M ** -1, round(100 * M ** -2, 2)  # → (6.25, 0.39)

Reading it: each bar is a layer, with the expected number of points on it (log scale, so each step down the chart is a factor of M). The last column compares the formula's fraction with a simulation of 20,000 random level draws using the paper's formula. Raise N by a factor of M and exactly one more layer appears on top: the number of layers grows like log_M(N), which is where HNSW's logarithmic search cost comes from. Raise M and the pyramid gets flatter and shorter.

4.2 Complexity and memory · original

Everyday picture

On each map you only need a few moves before you are as close as that map allows, however big the city is: roughly, you stop as soon as you reach a junction that also appears on the map above, and those are 1 in M. The number of maps grows only with the logarithm of the city's size. Few moves per map times few maps gives a logarithmic search.

In words: “the expected number of steps on one layer is bounded by a constant that depends only on m_L, not on how many points there are” (assuming an ideal Delaunay graph, as the paper's argument does).

With the numbers: M = 16 gives m_L = 0.361, e^−0.361 = 0.697, so S = 1 / 0.303 = 3.3 steps per layer.

In Python:

import math
m_L = 1 / math.log(16)
round(math.exp(-m_L), 3)  # → 0.697
S = 1 / (1 - math.exp(-m_L))
round(S, 1)  # → 3.3

With a constant number of steps per layer and O(log N) layers, search is O(log N). Insertion is a search plus linking, and each point lives on 1 + 1/(M − 1) = M/(M − 1) layers on average (1.07 for M = 16, matching the 62,500-per-million on layer 1 above), so building the index is O(N log N). The paper confirms the scaling empirically for low-dimensional data and notes that for high dimensions the argument is not yet proven.

Memory

In words: “every point stores up to M_max0 links on layer 0, plus on average m_L upper layers with up to M_max links each, and each link is one integer.” This is the paper's formula. Its m_L is the average of −ln(unif) · m_L before rounding down; after rounding down, a point sits on only 1/(M − 1) upper layers on average, so the formula is a safe overestimate.

With the numbers: M = 16, M_max0 = 32, M_max = 16, 4-byte links: the paper's formula gives (32 + 0.361 × 16) × 4 = (32 + 5.8) × 4 ≈ 151 bytes per point for the graph. Counting the upper layers exactly, 1/15 ≈ 0.067 per point, gives (32 + 0.067 × 16) × 4 = (32 + 1.07) × 4 ≈ 132 bytes. Either way it sits on top of the vector itself (512 bytes for a 128-dimensional float vector). The paper quotes 60 to 450 bytes for M between 6 and 48.

In Python:

import math
m_L = 1 / math.log(16)
M_max0, M_max, bytes_per_link = 32, 16, 4
# average upper-layer links
round(m_L * M_max, 1)  # → 5.8
# bytes per point
round((M_max0 + m_L * M_max) * bytes_per_link)  # → 151
# exact average upper layers after rounding down: 1/(M − 1)
upper = 1 / (16 - 1)
round(upper * M_max, 2)  # → 1.07
round((M_max0 + upper * M_max) * bytes_per_link)  # → 132
# the vector itself, 4-byte floats
128 * 4  # → 512

Reading it: the x-axis is M and the y-axis is the bytes of graph links per point, from the formula above with M_max0 = 2M and m_L = 1/ln M. It is almost a straight line: memory is proportional to M, as the paper says. At M = 6 it is about 61 bytes and at M = 48 about 434, matching the paper's 60 to 450 range. For 100 million points at M = 16, that is about 15 GB of links by the paper's formula (about 13 GB counted exactly), before storing the vectors.

5 Performance evaluation · original

Everyday picture

A race between search methods, judged on a speed-versus-accuracy chart: for each method, how fast can it answer while still finding, say, 90% of the true neighbours?

• 5.1 Against NSW: on 10 million random 4-dimensional points, HNSW needs far fewer distance computations for the same recall, especially at high recall, and its cost grows no worse than logarithmically with the dataset size.
• 5.2 Against the open-source field (FLANN, Annoy, VP-tree, FALCONN and NSW) on the ann-benchmarks testbed with SIFT, GloVe, DEEP, CoPhIR, MNIST and random vectors: HNSW clearly outperforms the rivals on SIFT, GloVe, DEEP and CoPhIR by a large margin, and is slightly faster than Annoy at high recall on the low-dimensional data.
• 5.3 In general (non-vector) spaces, rerunning tests where NSW had failed, including text with Jensen-Shannon divergence and DNA with edit distance: HNSW comes first even where NSW had lost by orders of magnitude.
• 5.4 Against product quantization (FAISS) on 200 million SIFT vectors: see the table.

Reading it: the classic trade-off. Product quantization compresses each vector into a short code, so FAISS used about a third to a half of the memory. HNSW keeps full vectors plus its graph, so it needs more RAM, but it built its index much faster (42 minutes against 11 hours at the lighter setting) and, per the paper's Figure 15, reached much higher accuracy with a large speed advantage. Today the two are often combined: an HNSW graph over quantized vectors, or HNSW as the coarse step of an IVF-PQ index. The vector index lesson builds IVF, PQ and HNSW side by side.

6 Discussion · original

“Robustness of the approach is a strong feature which makes it very attractive for practical applications.”Malkov and Yashunin, §6

Strengths the authors stress

• Robust: best on every dataset tested, including general metric spaces, so you rarely need to pick a different algorithm per problem. Real data can be high-dimensional at large scales and low-dimensional at small scales, and HNSW handles both.
• Incremental: points can be inserted at any time, with no rebuild. Deletion and update were listed as future work.
• One real dial: M.

The weakness they admit

Every search starts at the single top-layer entry point, so a straightforward distributed version would have all machines queueing for the few top-layer nodes. Splitting the data across machines works but does not scale throughput well; skip-list techniques for distribution might help.

Where HNSW is today

Glossary

Every term with hover guidance on this page, in one place.