Hierarchical Navigable Small World Graphs

Searching for near vectors by walking a graph. Greedy search on a proximity graph and the local minima that stop it, small-world graphs and Kleinberg's result on when a greedy walk is short, and the HNSW index of Malkov and Yashunin in full, its insertion and search algorithms followed line by line on twelve points in the plane. The level distribution, the local optimality of the returned list and a geometric property of the neighbor-selection heuristic are proved; what the parameters M, efConstruction and efSearch do is measured over 30 seeds on GloVe word vectors; and the absence of any worst-case guarantee is stated with the published hard instances. Worked problems draw levels, run the heuristic and the search by hand, and count the index's memory.

The word epidemic is not among the 5,000 most frequent words of this unit's GloVe vectors. Which of those 5,000 words lies nearest to it? A full scan compares its vector with all 5,000 and answers outbreak. The index of this article reaches the same answer by walking from word to word: his, money, blood, levels, affected, depression, spread, outbreak. Each word on the path is nearer to epidemic than the one before, and the walk computed 80 distances in place of 5,000. For the query explosives the same procedure walks his, money, some and stops there, at a word that is nothing like the true nearest, bomb. How does a walk on a graph find near vectors, and what does it take to keep it from stopping in the wrong place? The answer is a graph in which each vector is linked to a few near ones, searched greedily from a fixed start with a list of the best candidates found so far. The longer that list, the less often the walk stops early, and nothing guarantees that it never does.

A proximity graph has one node for each stored vector and links between vectors that are near each other. Hierarchical Navigable Small World graphs (HNSW; Malkov and Yashunin, 2020) are a stack of such graphs. Every vector is in the bottom one, and each higher one keeps a random fraction of the one below. A search starts at the top, where the few links are long, and descends to the bottom, where the many links are short. HNSW is the graph index of this unit. The later papers this unit cites on graph indexes, DiskANN and ACORN, both measure themselves against it (Subramanya et al., 2019; Patel et al., 2024).

Here is the route. First we search a single proximity graph greedily and see where that fails. Then we look at small-world graphs, where a greedy walk is provably short, and at the layered construction that HNSW builds on that idea. Next come the two algorithms, insertion and search, exactly as the paper lists them, followed on twelve points in the plane. Then we prove what can be proved: the distribution of the levels, the sense in which a returned list is locally best, and a property of the rule that chooses links. After that we measure what the three parameters do on GloVe, and state what is known about the worst case. The article assumes nearest neighbor search in high dimensions, which defines the problem, this unit's data and recall@$k$. The exact search that all of this approximates is the one behind the k-nearest neighbors classifier. The numbers come from tools/experiments/vectors/hnsw_article.py and hnsw_runs.py; the index itself is tools/experiments/vectors/hnsw.py, written in NumPy from the paper's listings. The paper of Malkov and Yashunin was read in its arXiv version (1603.09320v4); the section, algorithm and figure numbers and the quotations below are that version's, and the journal text was not opened.

Greedy search on a proximity graph

Take the vectors $\vec x_1, \dots, \vec x_N$ in $\mathbb{R}^m$ and a query $\vec q$, as in the rest of the unit. Suppose every vector has been given a short list of other vectors, its neighbor list, and that the lists mostly name near vectors. Greedy search is then the following walk. Start at some vector, the enter point. Compute the distance from $\vec q$ to each vector on the current vector's list. If one of them is nearer to $\vec q$ than the current vector, move to the nearest of them and repeat. Otherwise stop and return the current vector.

This is hill climbing with the stored vectors as the states and the distance to $\vec q$ as the function to be lowered. It has the weakness of all hill climbing. The walk stops at a local minimum: a vector none of whose listed neighbors is nearer to the query. That vector need not be the nearest of all. In the opening example some is a local minimum for explosives. Its squared distance to the query is 1.236, each of its listed neighbors is farther, and bomb, at 0.414, is not on its list.

Two things decide whether greedy search works. One is the choice of links. There is a graph on which the greedy walk cannot stop early, the Delaunay graph of the vectors. Malkov and Yashunin (2020, section 2.1) describe it as the graph that guarantees that the result of a basic greedy traversal is always the nearest neighbor. They also say why it cannot be used. It "cannot be efficiently constructed without prior information about the structure of a space", and its average degree grows exponentially with the dimension (section 4.2.1). Practical graphs approximate it with a bounded number of links to near vectors, and so admit local minima.

The other is the length of the walk. If every link is short, a walk that starts far from the query needs many steps. The paper notes that for graphs of nearest neighbors the number of steps grows as a power of $N$ (section 2.1). Short walks need some long links, and the question of how long links should be distributed has an exact answer in a simple model.

Small worlds and navigable graphs

A network is called a small world when any two of its nodes are joined by a short chain of links although most links are local. Kleinberg (2000) describes the model of Watts and Strogatz (1998) in these terms. It is a ring of nodes each joined to its nearest few, plus a small number of links whose endpoints are chosen uniformly at random. Such a network has short chains between all pairs. Kleinberg asked a different question: can the chains be found by someone who knows only the positions of the current node's contacts and of the target? That is the situation of greedy search.

His model is an $n \times n$ grid. In its simplest case each node is linked to its grid neighbors and has one long-range link. The other end of that link is chosen with probability proportional to $d^{-r}$, where $d$ is the grid distance to it and $r \ge 0$ is the model's one parameter. With $r = 0$ the long links are uniform, as in the Watts and Strogatz model. A decentralized algorithm passes a message from node to node using only local information. Kleinberg proved three things about its expected number of steps.

  • With $r = 2$, the greedy rule (pass the message to the contact nearest the target) needs at most a constant times $(\log_2 n)^2$ steps (his Theorem 2).
  • With $r = 0$, every decentralized algorithm needs at least a constant times $n^{2/3}$ steps (Theorem 1), although chains whose length is bounded by a polynomial in $\log_2 n$ exist with high probability.
  • For every other exponent the bound is again a power of $n$: at least a constant times $n^{(2-r)/3}$ steps for $0 \le r < 2$ and $n^{(r-2)/(r-1)}$ for $r > 2$ (Theorem 3).

So short chains are not enough. They can be found greedily only when the long links are spread in one particular way, and Kleinberg identifies it. With $r = 2$ a node's long link is about equally likely to land at each scale of distance: between 1 and 2, between 2 and 4, between 4 and 8, and so on. A greedy walk then finds, at every stage, a link that halves the remaining distance after an expected number of steps proportional to $\log_2 n$. A graph on which greedy routing takes a number of steps logarithmic or polylogarithmic in the number of nodes is called navigable.

The predecessor of HNSW, the Navigable Small World index (NSW; Malkov, Ponomarenko, Logvinov and Krylov, 2014), obtains long links without choosing them. Malkov and Yashunin (2020, section 2.1) describe its construction. The vectors are inserted one at a time in random order, and each is linked in both directions to the $M$ nearest of those already inserted. Early on, when few vectors are present, the nearest ones are far away, so the links made early are long, and they remain as bridges when the graph fills in. The same paper names the weakness of NSW. The walk passes through the well-connected early vectors, whose lists are long, so the number of distance computations grows polylogarithmically. The search can also be trapped far from the query before it reaches them.

The idea of the hierarchy

Here is the idea of HNSW in one sentence: separate the links by length into layers, and search the long ones first. Each vector, which the paper calls an element, draws a random level $l \ge 0$ and is present in layers $0, 1, \dots, l$. Level 0 is by far the most likely, so layer 0 holds every element, layer 1 a small fraction of them, layer 2 a small fraction of those. Within each layer the elements present are linked to near elements of the same layer. Since a high layer holds few elements, its near elements are far apart, and its links are long. The layers thus sort the links by scale, the property that Kleinberg's exponent $r = 2$ produces by chance.

A search enters at the top layer, walks greedily to a local minimum there, drops to the same element in the layer below, and continues. Only at layer 0 does it keep more than one candidate. Malkov and Yashunin describe this as an extension of the probabilistic skip list of Pugh (1990), with proximity graphs in place of the linked lists. The skip pointers of a postings list serve the same purpose in one dimension: a sparse upper level that lets a search pass over most of the lower one.

The index has two more ingredients, a fixed enter point (the element with the highest level) and a rule for choosing links that prefers links in different directions over the nearest ones. Both appear in the listings that follow.

The algorithms

The paper gives five listings. We restate them in full, in the paper's order of use, with the paper's names. Throughout, "distance" is the Euclidean distance; the implementation compares squared distances, which order the same way. The letter $q$ stands for the element being inserted or the query, and a neighbor list belongs to one element in one layer.

There are four parameters of construction and one of search.

  • $M$: the number of links a new element makes in each of its layers.
  • $M_{\max}$ and $M_{\max 0}$: the longest neighbor list allowed in layers above 0 and in layer 0. The paper suggests $M_{\max 0} = 2M$ (its section 4.1) and gives no value for $M_{\max}$; this article sets $M_{\max} = M$.
  • $m_L$: the scale of the level distribution. The paper suggests $m_L = 1/\ln M$.
  • efConstruction: the length of the candidate list during insertion.
  • efSearch: the length of the candidate list during a query (the paper writes ef).

SEARCH-LAYER (Algorithm 2)

Both insertion and search rest on one routine, the search of a single layer. It takes the query $q$, a set of enter points, a list length ef and a layer, and returns the ef nearest elements it found. It keeps three sets: the visited elements $v$, the candidates $C$ whose links have not yet been read, and the list $W$ of the nearest elements found so far, never longer than ef.

  1. Put the enter points into $v$, $C$ and $W$.
  2. While $C$ is not empty: take out of $C$ its element $c$ nearest to $q$, and let $f$ be the element of $W$ furthest from $q$.
  3. If $c$ is farther from $q$ than $f$, stop.
  4. Otherwise read the neighbor list of $c$ in this layer. For each neighbor $e$ not yet visited: mark it visited, and let $f$ be the current furthest element of $W$. If $e$ is nearer to $q$ than $f$, or $W$ holds fewer than ef elements, add $e$ to $C$ and to $W$; if $W$ now holds more than ef elements, remove its furthest.
  5. Return $W$.

With ef = 1 this is the greedy walk of the first section: $W$ holds the single best element, and the routine stops when the best element's links lead nowhere nearer. With a larger ef the routine continues from the second best, the third best and so on. It can then leave a local minimum by way of an element that is not the nearest so far but is among the ef nearest. The paper calls this backtracking.

K-NN-SEARCH (Algorithm 5)

To answer a query for $K$ neighbors with list length ef:

  1. Start at the index's enter point, in the top layer $L$.
  2. For each layer from $L$ down to 1: run SEARCH-LAYER with ef = 1 and make the element it returns the enter point for the next layer down.
  3. In layer 0 run SEARCH-LAYER with the full ef and return the $K$ nearest elements of $W$.

SEARCH-LAYER returns at most ef elements, so the implementation raises ef to $K$ when it is smaller.

INSERT (Algorithm 1)

To insert a new element $q$ into an index whose enter point has level $L$:

  1. Draw the level $l = \lfloor -\ln(u) \cdot m_L \rfloor$, with $u$ uniform between 0 and 1.
  2. For each layer from $L$ down to $l + 1$: run SEARCH-LAYER with ef = 1 from the current enter point, and continue from the element returned. This phase only finds a good place to start.
  3. For each layer from $\min(L, l)$ down to 0: run SEARCH-LAYER with ef = efConstruction, giving a list $W$. Choose up to $M$ of the elements of $W$ by SELECT-NEIGHBORS and link $q$ with each of them in both directions. For each chosen neighbor $e$ whose list now exceeds $M_{\max}$ ($M_{\max 0}$ in layer 0), replace the list by the $M_{\max}$ (or $M_{\max 0}$) elements that SELECT-NEIGHBORS chooses from it with $e$ as the base. Use all of $W$ as the enter points for the next layer down.
  4. If $l > L$, make $q$ the index's enter point.

The first element inserted becomes the enter point with no links. The links are directed: step 3 creates both directions, but shrinking the list of $e$ may remove a link $e \to x$ while $x \to e$ stays.

SELECT-NEIGHBORS (Algorithms 3 and 4)

The paper gives two ways of choosing $M$ neighbors for a base element from a set of candidates. The simple one (Algorithm 3) takes the $M$ candidates nearest to the base.

The heuristic (Algorithm 4) goes through the candidates from the nearest to the farthest, stops as soon as it has kept $M$ of them, and keeps a candidate only if it "is closer to $q$ compared to any element from $R$", where $R$ is the set kept so far. We read this as: the candidate $e$ is kept if its distance to the base is smaller than its distance to every element already kept. A candidate that lies behind a kept neighbor, nearer to that neighbor than to the base, is discarded, on the reasoning that a search can reach it through that neighbor. The effect is that the kept links point in different directions, and the paper's Fig. 2 shows why that matters. An element on the edge of a cluster keeps a link to another cluster when that link is the only one in its direction. Its $M$ nearest candidates would all lie in its own cluster.

Algorithm 4 has two options. The option extendCandidates adds the neighbors of the candidates to the candidates. The paper sets it off by default and calls it useful only for extremely clustered data. The option keepPrunedConnections fills the list up to $M$ with the nearest discarded candidates. Both are off in this article's runs unless stated.

How the listings were read

Where a listing leaves a choice open, the implementation makes one and hnsw.py documents it. The uniform number is taken from $(0, 1]$ so that its logarithm is finite. Ties in distance are broken by the smaller element number, and neighbor lists are read in increasing element number. The loop that shrinks lists visits the new neighbors nearest first. With extendCandidates, the base element is not added to its own candidates.

Two implementations were written. One is a literal transcription of the listings with sets and no optimization. The other, used for all measurements, keeps the candidates in priority queues, as the paper says its implementation does, and computes distances to a whole neighbor list at once. On points with small integer coordinates all squared distances are exact, so the two must agree exactly. hnsw_check.py asserts that they build the same graphs and return the same answers in 405 configurations of the options, in 2, 3 and 8 dimensions.

Twelve points, followed by hand

Twelve points in the plane with coordinates between 0 and 20 are inserted in the order of their numbers, with $M = 3$, $M_{\max} = 3$, $M_{\max 0} = 6$, efConstruction = 4 and the heuristic. All distances below are squared distances, which are whole numbers. The points and the levels they drew:

Element Point Level
0 (15, 0) 0
1 (14, 15) 0
2 (17, 6) 0
3 (10, 19) 1
4 (7, 2) 2
5 (2, 13) 1
6 (15, 17) 0
7 (4, 14) 1
8 (15, 20) 0
9 (16, 16) 0
10 (13, 6) 0
11 (20, 6) 1

(The set is the one drawn by seed 53; the script scanned seeds for a small set in which the last insertion prunes a link and some query separates ef = 1 from ef = 3.) Element 4 has the highest level and is the enter point. Layer 2 holds element 4 alone.

Inserting element 11

After the first eleven insertions the neighbor lists are these, written "element: its neighbors".

  • Layer 1 has 3: 4, 5, 7; 4: 3, 5; 5: 3, 4, 7; 7: 3, 5
  • Layer 0 has 0: 1, 2, 4; 1: 0, 2, 3, 4, 6, 10; 2: 0, 1, 10; 3: 1, 5, 6, 7, 8; 4: 0, 1, 5, 10; 5: 3, 4, 7; 6: 1, 3, 8, 9; 7: 3, 5; 8: 3, 6; 9: 6; 10: 1, 2, 4

Element 11, the point (20, 6), drew level 1. The top layer is 2, so the first phase covers layer 2 only, and the second phase covers layers 1 and 0. Every call of SEARCH-LAYER is traced below, one row per element whose links are read.

Step Layer Element evaluated Its links Added to W W afterwards (nearest first)
1 2 4 none nothing 4
2 1 4 3, 5 3, 5 4, 3, 5
3 1 3 4, 5, 7 7 4, 3, 7, 5
4 1 7 3, 5 nothing 4, 3, 7, 5
5 1 5 3, 4, 7 nothing 4, 3, 7, 5
6 0 4 0, 1, 5, 10 0, 1, 10 10, 0, 1, 4
7 0 10 1, 2, 4 2 2, 10, 0, 1
8 0 2 0, 1, 10 nothing 2, 10, 0, 1
9 0 0 1, 2, 4 nothing 2, 10, 0, 1
10 0 1 0, 2, 3, 4, 6, 10 nothing 2, 10, 0, 1

Layer 2. Element 4 has no links there, so the search returns it at once.

Layer 1. With ef = 4 the search collects all four elements of the layer. Their distances from element 11 are 185 for element 4, 269 for element 3, 320 for element 7 and 373 for element 5. The heuristic takes them in that order. Element 4 is kept, as the nearest always is. Element 3 is kept, because its distance to the base, 269, is smaller than its distance to element 4, which is 298. Element 7 is discarded: it is at 320 from the base and at only 153 from element 4. Element 5 is discarded for the same reason, 373 against 146. Element 11 is linked with 4 and 3 in both directions.

Element 3 now has four links, 4, 5, 7 and 11, one more than $M_{\max} = 3$, so its list is chosen again with element 3 as the base. In order of distance from element 3 the candidates are 7 (at 61), 5 (at 100), 11 (at 269) and 4 (at 298). Element 7 is kept. Element 5 is discarded, being at 5 from element 7. Element 11 is kept, since 269 is less than its distance to element 7, which is 320. Element 4 is discarded, being at 153 from element 7 and at 298 from the base. The new list of element 3 is 7, 11. Elements 4 and 5 still list element 3: two links have become one-way.

Layer 0. The search starts from the four elements found in layer 1 and ends with $W$ = 2, 10, 0, 1, at distances 9, 49, 61 and 117 from element 11. After step 10 the nearest unread candidate is element 3, at 269, farther than the furthest of $W$, so the search stops. The heuristic keeps element 2. It discards element 10, which is at 16 from element 2; element 0, at 40 from element 2; and element 1, at 90 from element 2. Element 11 receives a single link in layer 0 although $M = 3$: every other candidate lies behind element 2. The list of element 2 grows to four, within $M_{\max 0} = 6$.

The lists after the insertion:

  • Layer 1 has 3: 7, 11; 4: 3, 5, 11; 5: 3, 4, 7; 7: 3, 5; 11: 3, 4
  • Layer 0 has 0: 1, 2, 4; 1: 0, 2, 3, 4, 6, 10; 2: 0, 1, 10, 11; 3: 1, 5, 6, 7, 8; 4: 0, 1, 5, 10; 5: 3, 4, 7; 6: 1, 3, 8, 9; 7: 3, 5; 8: 3, 6; 9: 6; 10: 1, 2, 4; 11: 2

Searching for the point (9, 10)

The query is the point (9, 10), which is not one of the twelve. Its nearest element is 10, at distance 32; then come element 7 at 41, element 1 at 50, element 5 at 58 and element 4 at 68.

With ef = 1 the search makes 7 distance computations and returns the wrong element:

Step Layer Element Its links Added to W W afterwards (squared distance)
1 2 4 none nothing 4 (68)
2 1 4 3, 5, 11 5 5 (58)
3 1 5 3, 4, 7 7 7 (41)
4 1 7 3, 5 nothing 7 (41)
5 0 7 3, 5 nothing 7 (41)

The upper layers do their work: from the enter point the walk moves to element 5 and then to element 7, each nearer to the query. But element 7 is a local minimum in layer 0. Its two links lead to elements 3 and 5, both farther from the query. Element 10 is three links away by either of two routes, 7, 5, 4, 10 and 7, 3, 1, 10, and each begins with a step away from the query.

With ef = 3 the search makes 13 distance computations and finds element 10:

Step Layer Element Its links Added to W W afterwards (squared distance)
1 2 4 none nothing 4 (68)
2 1 4 3, 5, 11 5 5 (58)
3 1 5 3, 4, 7 7 7 (41)
4 1 7 3, 5 nothing 7 (41)
5 0 7 3, 5 3, 5 7 (41), 5 (58), 3 (82)
6 0 5 3, 4, 7 4 7 (41), 5 (58), 4 (68)
7 0 4 0, 1, 5, 10 1, 10 10 (32), 7 (41), 1 (50)
8 0 10 1, 2, 4 nothing 10 (32), 7 (41), 1 (50)
9 0 1 0, 2, 3, 4, 6, 10 nothing 10 (32), 7 (41), 1 (50)
10 0 3 (82) not read stop furthest of W is 1 (50)

The first four steps are the same. In layer 0 the list has room for three, so elements 5 and 4 are kept although they are farther than element 7. The links of element 4 then lead to elements 10 and 1. The search then stops when its nearest unread candidate, element 3 at 82, is farther than the furthest element of the list. With ef = 2 the search fails again, and the worked problems show why.

The twelve-point example. Dashed arrows are links that exist in one direction only. Notice in the third panel that the walk for the query (the cross) ends at element 7, whose links both lead away from the query; in the fourth, a list of three lets the search continue through elements 5 and 4 to element 10.
The twelve-point example. Dashed arrows are links that exist in one direction only. Notice in the third panel that the walk for the query (the cross) ends at element 7, whose links both lead away from the query; in the fourth, a list of three lets the search continue through elements 5 and 4 to element 10.

The demo runs the same search on 48 points. Its search code is a separate implementation in JavaScript, checked against the NumPy module on 400 queries. On those 400 queries, a search for the single nearest point with a list of one misses it 19 times on the graph built with the heuristic and 23 times on the graph built from the $M$ nearest. (The queries are whole-number points, so a few have two nearest points at the same distance; returning either counts as finding it.) With a list of three it misses once and never. With a list of eight it never misses on either. Choosing the graph built from the $M$ nearest shows the same search on links that were not chosen for direction.

Search of a 48-point HNSW graph in the plane, one evaluated element per step. Move the query by clicking, tapping or the arrow keys, and compare a list of one with a list of three or more. The example query stops at a local minimum when the list has one entry.

What can be proved

Four statements follow from the listings alone. None of them says that a search finds the nearest neighbor.

The levels

Proposition 1. Let $u$ be uniform on $(0, 1]$ and $l = \lfloor -\ln(u) \cdot m_L \rfloor$. Then $P(l \ge j) = e^{-j/m_L}$ for every integer $j \ge 0$. With $m_L = 1/\ln M$ this is $M^{-j}$, the expected level is $1/(M - 1)$, and the expected number of elements with level at least $j$ among $N$ is $N M^{-j}$.

Proof. Since $j$ is an integer, $l \ge j$ holds exactly when $-\ln(u) \cdot m_L \ge j$, that is, when $u \le e^{-j/m_L}$. A uniform number on $(0, 1]$ is at most $t$ with probability $t$ for $0 < t \le 1$, which gives $P(l \ge j) = e^{-j/m_L}$. With $m_L = 1/\ln M$ the exponent is $-j \ln M$, so $P(l \ge j) = M^{-j}$. For a variable with values $0, 1, 2, \dots$ the expectation is the sum of $P(l \ge j)$ over $j \ge 1$, here the geometric series $M^{-1} + M^{-2} + \dots = 1/(M - 1)$. The levels are drawn independently, so the number of elements with level at least $j$ is binomial with mean $N M^{-j}$. $\blacksquare$

The level is geometric: an element of layer $j$ is also in layer $j + 1$ with probability $M^{-(j+1)}/M^{-j} = 1/M$, whatever $j$ is. With $M = 16$, a share 0.0625 of the elements reaches layer 1 and a share 1/256 of all elements reaches layer 2. For $N = 5{,}000$ the expected sizes of layers 1, 2 and 3 are 312.5, 19.5 and 1.2. Over the 30 seeds of the experiment below, the medians were 311.5 and 19.5 for layers 1 and 2. The top layer was layer 2 in 12 builds, layer 3 in 15 and layer 4 in 3.

The expected size of layer $j$ falls below one element when $j$ exceeds $\log_M N$. For $M = 16$ that is 3.07 for 5,000 vectors, 4.65 for the unit's 399,000 and 7.47 for a billion. The number of layers grows with the logarithm of $N$, and slowly.

Corollary (memory). An element has $M_{\max 0}$ link slots in layer 0 and $M_{\max}$ in each higher layer, so its expected number of slots is $M_{\max 0} + M_{\max}/(M - 1)$. With $M = 16$, $M_{\max 0} = 2M$ and this article's $M_{\max} = M$ that is $32 + 16/15 = 33.07$ slots, or 132.3 bytes at four bytes a link. The paper (section 4.2.3) gives the average as $(M_{\max 0} + m_L M_{\max})$ links, which is 37.77 slots, or 151.1 bytes. That expression uses the expectation of $-\ln(u)\, m_L$ before it is rounded down, so it is an upper bound on the exact figure. For $M$ between 6 and 48 the paper's expression gives 61 to 434 bytes, in agreement with its statement of about 60 to 450 bytes per element. The vectors themselves must also stay in memory, since every step computes distances to them.

What SEARCH-LAYER returns

Proposition 2. Let SEARCH-LAYER be called with at most ef enter points, as every call in the algorithms above is. It ends after reading each neighbor list at most once. If no two elements are equally distant from $q$, then when it ends:

  1. $W$ holds the ef visited elements nearest to $q$, or all visited elements if fewer than ef were visited;
  2. the neighbor list of every element of $W$ has been read;
  3. consequently, every neighbor of every element of $W$ is in $W$ or is farther from $q$ than the furthest element of $W$, provided $W$ holds ef elements.

Proof. An element enters $C$ only at the moment it is first visited, and leaves $C$ before its list is read. So each list is read at most once, and the loop ends after at most $N$ rounds.

Claim 1 holds at the start, when the visited elements are the enter points, at most ef of them, and all are in $W$. Suppose it holds before a neighbor $e$ is visited. If $W$ has fewer than ef elements, $e$ is added and $W$ is again all the visited elements. If $W$ is full and $e$ is nearer than its furthest element $f$, then $e$ is added and $f$ removed, and the new $W$ is the ef nearest of the visited elements including $e$. If $W$ is full and $e$ is farther than $f$, then $e$ is not among the ef nearest visited elements and $W$ is unchanged. In each case the claim holds afterwards.

For claim 2, note first that an element is added to $W$ and to $C$ together, and that an element removed from $W$ never returns. Take an element $w$ of the final $W$ and suppose its list was never read. An element taken out of $C$ either has its list read or stops the loop at step 3. So either $w$ is the element that stopped the loop, or $w$ never left $C$. The first is impossible: the element $c$ that stops the loop is farther from $q$ than the furthest element of $W$, and $w$ is in $W$. In the second case the loop did not end with $C$ empty, since $w$ is in $C$. So it ended at step 3 with an element $c$ taken from $C$ that is farther from $q$ than the furthest element of $W$, hence farther than $w$. But $c$ was the nearest element of $C$, and $w$ was in $C$ at that moment, a contradiction.

For claim 3, let $w$ be in $W$ and $e$ a neighbor of $w$. By claim 2 the list of $w$ was read, so $e$ was visited. By claim 1 a visited element is either in $W$ or not among the ef nearest visited elements. In the latter case it is farther than every element of $W$ when $W$ is full. $\blacksquare$

Claim 3 is the precise sense in which the answer is good: the returned list is a local optimum of size ef. No link out of the list leads to anything nearer than the list's worst member. With ef = 1 it says that the answer is a local minimum of the greedy walk. The proposition also shows what a larger ef buys. A set of three elements closed in this sense is harder to come by than a single local minimum, so the search is forced further. It does not show that the list contains the nearest element, and in the twelve-point example with ef = 1 and ef = 2 it does not. The script checks claim 3 on 200 GloVe queries at ef = 1, 10 and 50.

Proposition 3. Let the heuristic of Algorithm 4 (without keepPrunedConnections) choose neighbors for a base point $b$ in Euclidean space. Then any two chosen neighbors subtend an angle of more than 60 degrees at $b$. In the plane the heuristic therefore chooses at most five neighbors, whatever $M$ is.

Proof. Let $r$ and $r'$ be chosen, $r$ before $r'$. Candidates are taken nearest first, so $\lvert b - r \rvert \le \lvert b - r' \rvert$. Since $r'$ was kept after $r$, it is nearer to the base than to $r$: $\lvert b - r' \rvert < \lvert r' - r \rvert$. So in the triangle with corners $b$, $r$ and $r'$ the side from $r$ to $r'$ is strictly the longest. The largest angle of a triangle lies opposite its longest side, so the angle at $b$ is strictly the largest of the three. The three angles sum to 180 degrees, so the largest exceeds 60 degrees unless all three equal 60, which would make the sides equal. In the plane the angles between consecutive chosen neighbors around $b$ sum to 360 degrees; six neighbors would need six angles of more than 60 degrees. $\blacksquare$

The script confirms the bound on 2,000 random sets of 40 planar candidates: at most five are kept, and every pair is more than 60 degrees apart. The strict inequality in our reading of the rule matters here. Under a reading that keeps a candidate exactly as near to a kept neighbor as to the base, the six corners of a regular hexagon around the base would all be kept, at exactly 60 degrees. In $m$ dimensions the same angle condition allows a number of neighbors that grows quickly with $m$, so the proposition does not bound the lists of a high-dimensional index. What it shows is the mechanism: the heuristic spreads links over directions, and it can leave an element with fewer than $M$ links, as element 11 was left with one. A neighbor list can still exceed five in the plane, because links added from the other side by later insertions are not checked until the list overflows.

What is not proved

The paper argues (section 4.2.1) that a search costs a number of distance computations proportional to $\ln N$. The argument assumes that each layer is an exact Delaunay graph, so that the greedy walk in a layer always reaches the layer's nearest element. It also assumes that the average degree of that graph is bounded by a constant. Under those assumptions the walk in a layer is bounded by a geometric series. It must end before reaching an element that also belongs to the layer above, since the search of that layer would otherwise have ended elsewhere. The paper gives the bound on the expected number of steps as $1/(1 - e^{-m_L})$, with $e^{-m_L}$ as the probability that the next element belongs to the upper layer. By Proposition 1 that probability is $e^{-1/m_L}$, which is $1/M$ at the suggested $m_L$; we report the paper's expression as printed and note the difference. Either way the number of steps per layer is bounded by a constant, the number of layers grows as $\ln N$, and the total is logarithmic.

The authors state the limits of this themselves. The graphs HNSW builds are approximations with a fixed number of links, so the assumption fails, and the argument is supported by simulations on low-dimensional data. For high dimensions they write: "Further analitical evidence is required to confirm whether the resilience of Delaunay graph aproximations generalizes to higher dimensional spaces." (The spelling is that of the arXiv text.) The logarithmic scaling of HNSW is an empirical finding of the paper, not a theorem.

What the parameters do, measured

The setup

The base is the 5,000 most frequent words of the unit's GloVe set that are not query words, in 100 dimensions and scaled to unit length. The queries are the unit's 1,000. The measure is recall@10 against the exact ten nearest, as defined for the unit. The cost is the number of distance computations per query, the unit's machine-independent measure; a full scan costs 5,000. Each configuration is built 30 times with seeds 0 to 29, which drive the level draws. The vectors are inserted in file order, most frequent word first, except where the order is the thing varied. Tables give the median over the 30 builds with the first and third quartiles in parentheses.

The scale is small because the implementation is a Python loop around NumPy. One build of 5,000 vectors took 20 to 80 seconds on the shared machine, and thirty builds of the full 399,000 were out of reach. A set of 5,000 vectors is one that a full scan handles easily. This section should be read as a study of how the index behaves, not as a case for using it at this size. One build of 50,000 vectors is reported at the end.

One more fact about this base matters. The queries were drawn from all 400,000 words, so most of them are rarer words than any in the base. Their neighbors are far away and spread out: in the full set the nearest base vector of a typical query is at an angle of 43.2 degrees from it (locality-sensitive hashing measures this). GloVe is a hard set for every index of this unit.

efSearch

The base configuration is $M = 16$, efConstruction = 100, the heuristic, $m_L = 1/\ln 16$.

efSearch Recall@10 Distance computations per query Share of the 5,000 Elements evaluated Nearest neighbor found
10 0.547 (0.542 to 0.550) 157 (153 to 160) 3.1% 20 60.7%
25 0.742 (0.740 to 0.744) 270 (267 to 273) 5.4% 35 79.0%
50 0.852 (0.851 to 0.853) 430 (427 to 434) 8.6% 59 87.6%
100 0.919 (0.919 to 0.920) 716 (714 to 719) 14.3% 108 92.3%
200 0.959 (0.958 to 0.959) 1,227 (1,225 to 1,229) 24.5% 207 95.0%

Recall rises with every increase of the list, and the cost rises more slowly than the list: twenty times the list costs 7.8 times the distance computations. At efSearch = 10 the search computes 157 distances, 3.1% of a scan, and finds 0.547 of the true neighbors. At 200 it finds 0.959 of them and computes 1,227 distances, a quarter of a scan. The interquartile ranges are narrow: the seed, which decides only the levels, moves recall in the third decimal place.

Example (the mean hides the spread). A recall of 0.852 does not mean that each query loses one or two of its ten neighbors. In the build with seed 0 at efSearch = 50, the search returns all ten for 399 of the 1,000 queries and five or fewer for 67 queries. Recall is an average over queries. A user who needs the true neighbors of one particular vector has no way to tell from the index which kind of query it is.

Example (a common misreading). "efSearch is the number of vectors the search examines." It is the length of the list $W$. At efSearch = 50 the search reads the links of 59 elements and computes 430 distances, because each element read brings a list of new neighbors. The opening examples show both numbers for single queries. For epidemic, a list of one finds outbreak with 80 distance computations, and a list of ten returns outbreak, disease, flu, hiv, aids, virus, diseases, prevention, spread, illness, the exact ten, with 144 distance computations. For explosives, a list of one stops at some after 43 distance computations; a list of ten returns bomb, bombs, exploded, carrying, weapons, hidden, truck, bomber, seized, weapon, the exact ten, with 194 distance computations. The squared distances along the epidemic path fall from 1.637 at his through 1.554, 1.287, 1.181, 0.980, 0.881 and 0.716 to 0.344 at outbreak. Along the explosives path they fall from 1.395 through 1.300 to 1.236 at some, while bomb is at 0.414.

M, efConstruction, the heuristic, the layers and the order

The first table gives recall and cost at two list lengths for each index. The base configuration is the row $M = 16$, efConstruction 100, and every other row changes one thing.

Index Recall@10 at efSearch 50 Distance computations Recall@10 at efSearch 200 Distance computations
$M = 4$ 0.696 (0.692 to 0.700) 245 (242 to 248) 0.908 (0.906 to 0.909) 687 (686 to 689)
$M = 8$ 0.836 (0.835 to 0.837) 383 (381 to 387) 0.953 (0.953 to 0.954) 1,100 (1,099 to 1,103)
$M = 16$, efConstruction 100 0.852 (0.851 to 0.853) 430 (427 to 434) 0.959 (0.958 to 0.959) 1,227 (1,225 to 1,229)
efConstruction 25 0.715 (0.710 to 0.719) 293 (289 to 297) 0.903 (0.900 to 0.905) 820 (818 to 823)
efConstruction 50 0.809 (0.806 to 0.811) 362 (360 to 367) 0.946 (0.945 to 0.947) 1,030 (1,028 to 1,032)
the $M$ nearest (Algorithm 3) 0.845 (0.843 to 0.847) 533 (529 to 540) 0.969 (0.968 to 0.969) 1,448 (1,446 to 1,450)
one layer ($m_L = 0$) 0.854 (0.854 to 0.854) 444 (444 to 444) 0.959 (0.959 to 0.959) 1,236 (1,236 to 1,236)
shuffled insertion order 0.893 (0.888 to 0.897) 535 (532 to 538) 0.980 (0.978 to 0.982) 1,493 (1,489 to 1,498)

The second table describes the graphs: the mean number of links per element in layer 0, the longest list, the top layer, the work of the build, the memory of the link slots, and the smallest and largest number of elements, over the 30 builds, that cannot be reached from the enter point by any path.

Index Links per element, layer 0 Largest list Top layer Build: distance computations per element Link slots, bytes per element Unreachable elements
$M = 4$ 6.1 8 6 1,015 37 14 to 21
$M = 8$ 10.8 16 4 1,369 69 0 to 0
$M = 16$, efConstruction 100 13.3 32 3 1,358 132 0 to 0
efConstruction 25 8.5 31 3 304 132 0 to 0
efConstruction 50 11.1 32 3 650 132 0 to 0
the $M$ nearest (Algorithm 3) 24.9 32 3 951 132 0 to 0
one layer ($m_L = 0$) 13.3 32 0 1,317 128 0 to 0
shuffled insertion order 16.4 32 3 1,807 132 0 to 0
Recall@10 against distance computations per query on the 5,000-vector base, medians over 30 seeds with interquartile ranges as bars (most are too short to see). Each curve runs through efSearch 10, 25, 50, 100 and 200. Read a curve as the trade-off of one index, and compare curves at equal cost, not at equal efSearch.
Recall@10 against distance computations per query on the 5,000-vector base, medians over 30 seeds with interquartile ranges as bars (most are too short to see). Each curve runs through efSearch 10, 25, 50, 100 and 200. Read a curve as the trade-off of one index, and compare curves at equal cost, not at equal efSearch.

The figure's caption asks for comparisons at equal cost, and the two tables above cannot give them, since each row has its own cost. The next table does. For each index it takes the points at efSearch 50 and 100 and sets beside them the difference between its recall and the recall of the base index at the same number of distance computations. The base index was run only at the five list lengths, so its recall between two of them has to be interpolated, and the way it is interpolated matters. Recall rises more slowly as the cost grows, so the base curve is concave, and a straight line between two of its points lies a little below it, which flatters the compared index. The fifth column uses that straight line. The last column draws the line in the logarithm of the cost instead, the scale of the figure, on which the curve is much closer to straight.

Index Its efSearch Distance computations Its recall@10 Difference, straight line Difference, line in log cost
$M = 4$ 50 245 0.696 -0.002 -0.011
$M = 4$ 100 400 0.825 -0.006 -0.010
$M = 8$ 50 383 0.836 +0.016 +0.011
$M = 8$ 100 639 0.910 +0.009 +0.006
efConstruction 25 50 293 0.715 -0.043 -0.046
efConstruction 25 100 479 0.833 -0.030 -0.033
efConstruction 50 50 362 0.809 +0.004 -0.002
efConstruction 50 100 600 0.894 +0.003 -0.001
the $M$ nearest (Algorithm 3) 50 533 0.845 -0.032 -0.036
the $M$ nearest (Algorithm 3) 100 864 0.922 -0.008 -0.011
one layer ($m_L = 0$) 50 444 0.854 -0.001 -0.002
one layer ($m_L = 0$) 100 728 0.918 -0.002 -0.002
shuffled insertion order 50 535 0.893 +0.017 +0.013
shuffled insertion order 100 891 0.950 +0.017 +0.014

The two columns differ by up to 0.009, and for efConstruction 50 they disagree in sign. A difference of less than about 0.005 in either column should therefore be read as no difference, and the conclusions drawn below are only those that hold in both columns. They are these: efConstruction 25 and the choice of the $M$ nearest are clearly below the base curve, the shuffled order is clearly above it, $M = 8$ is slightly above it, $M = 4$ slightly below it, and efConstruction 50 and the single layer are on it.

$M$. At equal efSearch a smaller $M$ looks worse: 0.696 for $M = 4$ and 0.836 for $M = 8$ against 0.852 at efSearch 50. At equal cost the gap mostly closes. The index with $M = 4$ is a little below the base curve at both points of the table, by 0.002 and 0.006 on the straight line and by 0.011 and 0.010 on the line in log cost, and at its efSearch 25 it finds 0.547 for 156 distance computations, where the base index finds 0.547 for 157. The index with $M = 8$ is slightly ahead of the base curve, by 0.016 and 0.009 on the straight line and 0.011 and 0.006 in log cost, with half the memory, 69 bytes per element against 132. So on this data a larger $M$ than 8 bought nothing at equal query cost, and $M = 16$ bought little over $M = 4$: between 0.002 and 0.011 of recall, by the two columns. What $M = 4$ costs is something else: 14 to 21 elements that no search can reach, and a lower curve at every list length tried; its point at efSearch 200, where the runs of every index stop, is 0.908 at 687 distance computations. The graph table suggests why $M = 16$ adds little. An element then has 13.3 links in layer 0 on average, out of 32 allowed. The lists are short because the heuristic rejects candidates, not because the limit binds, so we would expect a larger limit to change little. A larger $M$ was not run.

efConstruction. A short candidate list during the build gives a worse graph. With 25 candidates the index is 0.043 and 0.030 below the base curve at equal cost on the straight line (0.046 and 0.033 in log cost). With 50 candidates it is on the base curve: 0.004 and 0.003 above it on the straight line, 0.002 and 0.001 below it in log cost. The heuristic can only choose among the candidates it is given: the mean number of links falls from 13.3 to 11.1 with 50 candidates and to 8.5 with 25. The saving is in the build, 650 and 304 distance computations per inserted element against 1,358. The paper's advice is to make efConstruction large enough that the search during construction has a recall near 1. On this data 50 was enough to match the base index at equal cost, and 25 was not.

The heuristic. Choosing the $M$ nearest nearly doubles the links, 24.9 per element against 13.3, and the search pays for reading them. At equal cost its graph is 0.032 below the base curve at 533 distance computations and 0.008 below at 864 on the straight line (0.036 and 0.011 in log cost). In the figure the heuristic's curve lies above the other at low cost, and the two come together at high recall. On this data the heuristic's gain is a cheaper graph of about the same quality. The next section shows data on which it is the difference between working and failing.

The layers. With every element on layer 0 the index reaches 0.854 at efSearch 50 for 444 distance computations; with the hierarchy, 0.852 for 430. On these runs the hierarchy saved 13 distance computations per query at efSearch 50 (the two figures just given are each rounded), and between 9 and 18 over the five list lengths. At equal cost the single layer is 0.001 and 0.002 below the base curve on the straight line, and 0.002 below at both points in log cost. This is not what the name of the method suggests, and it agrees with the paper's own measurements, which find the largest gains from the layers on low-dimensional data and a small one on high-dimensional data (its Figs. 3 to 5). A likely reason is that with elements inserted one after another the early ones already carry long links, the effect NSW relies on; the experiment does not test this. The single-layer index has no random choices, since its only randomness was the levels, so its quartiles coincide.

The insertion order. The file lists words from the most frequent to the least. Shuffling the order, with a different shuffle for each seed, gives a denser graph, 16.4 links per element, and a better one at equal cost too: 0.017 above the base curve at both points on the straight line (0.013 and 0.014 in log cost), 0.893 for 535 distance computations where the file-order curve passes 0.876 by the straight line. The paper says that the order of insertion alters the performance slightly. Frequency order is correlated with the data, which may be why it did worse here; the experiment compares one file order with random shuffles and does not test the cause. The spread between seeds also widened, from 0.002 to 0.009 between the quartiles at efSearch 50.

Example (a common misreading). "A larger $M$ always buys recall." At equal efSearch it did, a little: 0.006 from $M = 8$ to $M = 16$ at efSearch 200. At equal query cost it did not: the index with $M = 8$ was ahead of the one with $M = 16$, for half the memory. A larger $M$ can help only while the lists fill, and on this data the heuristic left them at 13.3 of 32. Of the settings tried, the ones that moved recall most at a fixed query cost were a too-short efConstruction and the choice of the $M$ nearest, which lowered it, and the insertion order and $M = 8$, which raised it: at efSearch 50, by 0.017 and 0.016 on the straight line and by 0.013 and 0.011 in log cost.

Isolated clusters

The paper motivates the heuristic with clustered data (its Fig. 2 and Fig. 7). To see the effect in isolation, the script builds a synthetic set of 50 clusters of 40 points in 8 dimensions: the centers are uniform in a cube of side 100 and the points lie within a few units of their centers, so the clusters are far apart. The 500 queries are drawn around randomly chosen centers. The index uses $M = 8$, efConstruction 100 and a shuffled insertion order, over 30 seeds.

Neighbor selection Recall@10 at efSearch 50 Recall@10 at efSearch 200 Distance computations at 50 Unreachable elements Links per element
the $M$ nearest (Algorithm 3) 0.811 (0.774 to 0.850) 0.868 (0.830 to 0.901) 110 (109 to 112) 4 to 118 12.7
heuristic (Algorithm 4) 1.000 (1.000 to 1.000) 1.000 (1.000 to 1.000) 138 (136 to 139) 0 to 0 7.4
heuristic with extendCandidates 1.000 (1.000 to 1.000) 1.000 (1.000 to 1.000) 169 (167 to 170) 0 to 0 8.2

With the $M$ nearest the median recall is 0.811 at efSearch 50 and only 0.868 at 200, so a list four times as long recovers little. Between 4 and 118 of the 2,000 elements cannot be reached at all, depending on the seed. The script also counts the layer-0 links that join different clusters in the finished graphs. With the $M$ nearest there are 1,029 to 1,850 of them among about 25,300 links. With the heuristic there are 2,871 to 3,220 among about 14,750: at the median 3,064 against 1,346, more than twice as many links between clusters, in a graph with little more than half the links. That is the effect the paper's Fig. 2 describes. How the links between clusters were lost during the build was not traced. With the heuristic every element was reachable in every build and the recall was 1.000, with 7.4 links per element in place of 12.7. The extendCandidates option, which the paper recommends for such data, was not needed here and cost more distance computations.

Size

The same configuration was built on the 1,000 most frequent words (30 seeds), and once, with seed 0, on the 50,000 most frequent. A single build is one draw of the levels and not a seeded summary; the quartiles above suggest that the draw matters little. The table compares the hierarchy with the single layer at efSearch 50.

$N$ Recall@10, layers Distance computations, layers Recall@10, one layer Distance computations, one layer
1,000 0.902 (0.901 to 0.903) 284 (282 to 285) 0.903 (0.903 to 0.903) 300 (300 to 300)
5,000 0.852 (0.851 to 0.853) 430 (427 to 434) 0.854 (0.854 to 0.854) 444 (444 to 444)
50,000 (one build, seed 0) 0.799 805 0.789 843

The cost of a search at a fixed list length grows slowly: 284 distance computations for 1,000 vectors, 430 for 5,000 and 805 for 50,000, where a scan grows fifty-fold. Recall at that fixed list length falls, from 0.902 to 0.799, so a larger set needs a longer list for the same recall. The hierarchy's saving over one layer is 16, 13 and 38 distance computations at the three sizes. In the one build of 50,000 it also found slightly more of the neighbors, 0.799 against 0.789.

For the 50,000-vector build the full curve is this:

efSearch Recall@10 Distance computations per query Share of the 50,000
10 0.546 295 0.6%
25 0.706 504 1.0%
50 0.799 805 1.6%
100 0.866 1,353 2.7%
200 0.919 2,347 4.7%
400 0.960 4,131 8.3%

At this size the index is worth having: efSearch 50 reaches 0.799 of the neighbors for 1.6% of a scan, and efSearch 400 reaches 0.960 for 8.3%. The build made 2,376 distance computations per inserted element, and its layers held 50,000, 3,092, 202, 13 and 2 elements, against the 3,125, 195, 12 and 0.8 that Proposition 1 expects above layer 0. The paper reports logarithmic growth of the cost over many decades of $N$ on low-dimensional data. Three sizes of one hard set cannot confirm or refute that.

No worst-case guarantee

Everything in the last section is a measurement on one set of vectors. For HNSW there is nothing else: no theorem bounds its recall or its running time on arbitrary data. Proposition 2 guarantees a local optimum, and a local optimum can be anywhere.

The gap is not only a missing proof. Indyk and Xu (2023) constructed families of point sets on which graph indexes fail. Their sets lie in the plane, so they are as low-dimensional as data can be. They ran the implementations of HNSW (with $M = 64$ and efConstruction = 200) and of NSG published by the methods' authors on sizes between 100,000 and 2,000,000 points. For most of those sizes, they report, the implementations "cannot achieve good Recall@5 unless scanning at least 10% of the vertex set" (their section 4.2 and Fig. 5). The same paper proves a positive result for one variant only, the slow-preprocessing version of DiskANN, which the next article describes. For it they prove a constant approximation ratio in a number of steps logarithmic, and a running time polylogarithmic, in the ratio of the largest to the smallest distance, on data of bounded doubling dimension. The authors add that their results "do not contradict the empirical evaluations" of these indexes; they show that the behavior depends on the data.

Three weaker forms of the same fact appeared in this article's own runs.

  • A greedy search stopped at a local minimum for explosives and for the point (9, 10).
  • Links are directed, and shrinking a list can remove the last link into an element. With $M = 4$, between 14 and 21 of the 5,000 elements could not be reached from the enter point by any path, in every one of the 30 builds. With $M \ge 8$ none were lost on this data.
  • On the isolated clusters, the index built from the $M$ nearest left between 4 and 118 of its 2,000 elements unreachable.

The practical consequence is the one Indyk and Xu draw: the quality of the answers has to be validated on the data at hand. An index of this kind is tuned by measuring recall against a full scan on a sample of real queries. It should be measured again when the data changes character. The unit's other indexes, inverted files and product quantization, are heuristic in the same way. By contrast, locality-sensitive hashing comes with a bound on its failure probability that holds for every data set. What each index costs for a given recall on this unit's data is the subject of benchmarking vector indexes, which puts them side by side.

What is proved here, what is cited, what the experiments show

Proved on this page. The level distribution, the expected layer sizes and the expected memory (Proposition 1 and its corollary). The termination of SEARCH-LAYER and the local optimality of the list it returns (Proposition 2). The angle property of the heuristic and the bound of five neighbors in the plane (Proposition 3). The twelve-point traces are computations, checked by two implementations.

Cited, not proved. Kleinberg's three theorems on greedy routing in the grid model. The description of NSW and of the Delaunay graph, from Malkov and Yashunin (2020). The paper's argument for logarithmic search cost, which rests on assumptions the index does not satisfy, as the paper says. The hard instances and the DiskANN bound of Indyk and Xu (2023).

Shown by the experiments, on 5,000 GloVe vectors with 1,000 queries and 30 seeds unless stated. The trade-off between efSearch, recall and distance computations; the effects of $M$, efConstruction, the heuristic, the hierarchy and the insertion order; the behavior on a synthetic clustered set; one build of 50,000 vectors. These are observations of these runs. Wall-clock times are not reported, since a Python loop says nothing about the speed of a compiled index.

Worked problems

The unit has no course assignments. Problems 1 and 5 apply Proposition 1 and its corollary, and Problems 2 to 4 are posed on the twelve points; the script recomputes every number.

Problem 1. An index uses $M = 4$ and $m_L = 1/\ln 4$. What level does an element draw when its uniform number is $u = 0.03$? What share of the elements reach layer 3, what is the expected level, and how many link slots does an element have on average with $M_{\max} = 4$ and $M_{\max 0} = 8$?

Here $m_L = 1/\ln 4 = 0.7213$. The level is $\lfloor -\ln(0.03) \cdot 0.7213 \rfloor = \lfloor 3.5066 \times 0.7213 \rfloor = \lfloor 2.529 \rfloor = 2$. Equivalently, $-\ln(u)/\ln 4 = \log_4(1/u)$, and $1/0.03 = 33.3$ lies between $4^2 = 16$ and $4^3 = 64$. By Proposition 1 the share of elements with level at least 3 is $4^{-3} = 1/64$, about 1.6%. The expected level is $1/(M - 1) = 1/3$. The expected number of slots is $M_{\max 0} + M_{\max}/(M - 1) = 8 + 4/3 = 9.33$.

Problem 2. Apply the heuristic with $M = 3$ to the base element 6, the point (15, 17), and the candidates 1, 3, 8 and 9.

The squared distances from element 6 are 2 to element 9, 5 to element 1, 9 to element 8 and 29 to element 3, so that is the order. Element 9 is kept. Element 1 is at 5 from the base and at 5 from element 9; under this article's reading of Algorithm 4 it must be strictly nearer to the base, so it is discarded. A reading that keeps ties would keep element 1 and return 9, 1 and 8, as Algorithm 3 does. Element 8 is at 9 from the base and at 17 from element 9, so it is kept. Element 3 is at 29 from the base, at 45 from element 9 and at 26 from element 8. It is nearer to element 8 than to the base, so it is discarded. The heuristic returns elements 9 and 8, two neighbors although three were allowed. Algorithm 3 would have returned 9, 1 and 8.

Problem 3. Search layer 0 of the twelve-point graph for the query (9, 10) with ef = 2, starting from element 7, where the upper layers lead. Why does the search fail when ef = 3 succeeds?

Element Its links Added to W W afterwards (squared distance)
7 3, 5 3, 5 7 (41), 5 (58)
5 3, 4, 7 nothing 7 (41), 5 (58)
3 (82) not read stop furthest of W is 5 (58)

Reading the links of element 7 visits elements 3 and 5. Element 3, at 82, enters the list because the list has room, and is pushed out when element 5, at 58, enters. Reading the links of element 5 visits element 4, at 68. The list is full and its furthest member is at 58, so element 4 is rejected. The next candidate is element 3, at 82, farther than 58, and the search stops with the answer 7. From element 7 the search can reach element 10 through element 4 (by way of element 5) or through elements 3 and 1. With a list of two, element 4 is rejected, and element 3 stops the search. Element 4 is the fifth nearest element to the query. A list of two has no room for it; a list of three admits it at the moment the third place is still held by element 3. Whether a search escapes a local minimum depends on whether the bridge out of it ranks within the list, which no setting of ef short of $N$ can ensure in general.

Problem 4. Verify claim 3 of Proposition 2 for the list returned with ef = 3.

The list is 10, 7, 1, and its furthest member, element 1, is at 50. The links of element 10 lead to 1, 2 and 4; those of element 7 to 3 and 5; those of element 1 to 0, 2, 3, 4, 6 and 10. The elements outside the list reached this way, with their distances from the query, are 0 (136), 2 (80), 3 (82), 4 (68), 5 (58), 6 (85). Each is farther than 50, as the proposition requires. The proposition assumes that no two elements are equally distant from the query. Two pairs are: elements 0 and 8, both at 136, and elements 6 and 9, both at 85. None of the four is in the list or at its boundary of 50, so the argument goes through unchanged. In this case the list is also the true three nearest. The proposition does not promise that: the list 7 alone satisfies the same condition for ef = 1.

Problem 5. How much memory would the links of an index of the unit's full 399,000 vectors take with $M = 16$, against the vectors themselves?

The vectors take $399{,}000 \times 100 \times 4$ bytes, which is 159.6 MB. By the corollary an element has 33.07 slots on average, 132.3 bytes, so the links take about 52.8 MB, 0.33 of the size of the vectors. The index cannot be searched without the vectors, so the total is about 212 MB. The slots are allocated at their maximum; the lists of the measured graphs were less than half full.

What we have learned

A proximity graph turns nearest neighbor search into a walk, and a greedy walk ends at a local minimum. HNSW shortens the walk with a hierarchy of layers whose sizes fall by a factor of $M$ from one to the next, searched from the sparsest down. It reduces the harm of local minima by keeping a list of the ef best elements found, which Proposition 2 shows to be locally optimal and nothing more. Its links are chosen by a heuristic that spreads them over directions. On 5,000 GloVe vectors the list length traded recall against distance computations smoothly, from 0.547 at 157 computations to 0.959 at 1,227. The method has no worst-case guarantee, and point sets are known on which, in their authors' experiments, it needed to scan a tenth of the data for good recall.

The index assumes that the vectors and the graph fit in memory, that every stored vector is a legitimate answer, and that the set does not change. Vector search on disk and with filters takes up each of those assumptions.

References

  • Indyk, P., and Xu, H. (2023). Worst-case performance of popular approximate nearest neighbor search implementations: Guarantees and limitations. In Advances in Neural Information Processing Systems 36 (NeurIPS 2023), 66239–66256. arXiv:2310.19126. record · 2 pages
  • Kleinberg, J. (2000). The small-world phenomenon: An algorithmic perspective. In Proceedings of the Thirty-Second Annual ACM Symposium on Theory of Computing (STOC 2000), 163–170. record
  • Malkov, Y., Ponomarenko, A., Logvinov, A., and Krylov, V. (2014). Approximate nearest neighbor algorithm based on navigable small world graphs. Information Systems, 45, 61–68. record
  • Malkov, Y. A., and Yashunin, D. A. (2020). Efficient and robust approximate nearest neighbor search using hierarchical navigable small world graphs. IEEE Transactions on Pattern Analysis and Machine Intelligence, 42(4), 824–836. arXiv:1603.09320. record · 2 pages
  • Patel, L., Kraft, P., Guestrin, C., and Zaharia, M. (2024). ACORN: Performant and predicate-agnostic search over vector embeddings and structured data. Proceedings of the ACM on Management of Data, 2(3), 1–27. arXiv:2403.04871. record · 2 pages
  • Pugh, W. (1990). Skip lists: A probabilistic alternative to balanced trees. Communications of the ACM, 33(6), 668–676. record · 2 pages
  • Subramanya, S. J., Devvrit, Kadekodi, R., Krishnaswamy, R., and Simhadri, H. V. (2019). DiskANN: Fast accurate billion-point nearest neighbor search on a single node. In Advances in Neural Information Processing Systems 32 (NeurIPS 2019). record · 2 pages
  • Watts, D. J., and Strogatz, S. H. (1998). Collective dynamics of 'small-world' networks. Nature, 393(6684), 440–442. record