HNSW Index: Architecture for Fast Vector Search › Worked Example

We trace through HNSW search with a small example to demonstrate the algorithm's two-phase strategy. Suppose we have 8 two-dimensional vectors and an HNSW index with $M = 2$ and 3 layers.

The index has the following structure across three layers. At the top, layer 2 contains only two nodes: A and F, connected by a single long-range edge. Layer 1 adds two more nodes, C and H, creating a four-node graph where A connects to C, C connects to F, and F connects to H. Finally, layer 0 contains all eight nodes arranged in sequence: A connects to B, B connects to C, C connects to D, D connects to E, E connects to F, F connects to G, and G connects to H. Each node that appears on a higher layer also appears on every layer below it, maintaining the hierarchical invariant.

Node A exists on all three layers (it is the entry point). Nodes C, F, and H were randomly assigned to layer 1. Node F was also assigned to layer 2. The actual 2D positions are:

Now let's search for the nearest neighbor of query $q = (6.5, 2.5)$ using Euclidean distance with ef_search = 3. We will walk through each layer of the search, computing every distance explicitly, so you can see exactly how the algorithm makes its decisions.

Layer 2 (greedy, beam width 1): Start at entry point A at position (1, 1). Check A's neighbors on layer 2: only F at (6, 1). We compare the distances to the query $q = (6.5, 2.5)$:

$$\begin{aligned} d(A, q) &= \sqrt{(6.5-1)^2 + (2.5-1)^2} \\ &= \sqrt{5.5^2 + 1.5^2} \\ &= \sqrt{30.25 + 2.25} \\ &= \sqrt{32.5} \\ &\approx 5.70 \\[1em] d(F, q) &= \sqrt{(6.5-6)^2 + (2.5-1)^2} \\ &= \sqrt{0.5^2 + 1.5^2} \\ &= \sqrt{0.25 + 2.25} \\ &= \sqrt{2.5} \\ &\approx 1.58 \end{aligned}$$

where:

• $d(x, y)$: the Euclidean distance between points $x$ and $y$
• $A$: the entry node at coordinates $(1, 1)$
• $F$: the neighbor node at coordinates $(6, 1)$
• $q$: the query vector at coordinates $(6.5, 2.5)$

Since $d(F, q) < d(A, q)$, F is closer, so we move to F. Notice the dramatic improvement: a single hop reduced the distance from 5.70 to 1.58, covering most of the journey in one step. This is exactly the coarse navigation behavior that the upper layers are designed to provide. F has no closer neighbor on layer 2, so we descend with F as entry point.

Layer 1 (greedy, beam width 1): Start at F on layer 1. F's neighbors on layer 1 are C and H. We calculate the distances:

$$\begin{aligned} d(C, q) &= \sqrt{(3-6.5)^2 + (1-2.5)^2} \\ &= \sqrt{(-3.5)^2 + (-1.5)^2} \\ &= \sqrt{12.25 + 2.25} \\ &= \sqrt{14.5} \\ &\approx 3.81 \\[1em] d(H, q) &= \sqrt{(8-6.5)^2 + (2-2.5)^2} \\ &= \sqrt{1.5^2 + (-0.5)^2} \\ &= \sqrt{2.25 + 0.25} \\ &= \sqrt{2.5} \\ &\approx 1.58 \end{aligned}$$

where:

• $C$: the neighbor node at coordinates $(3, 1)$
• $H$: the neighbor node at coordinates $(8, 2)$
• $q$: the query vector at coordinates $(6.5, 2.5)$

H is at the same distance as F (1.58). We break the tie by choosing H. Move to H. Notice that C, despite being a neighbor on this layer, is much farther away at 3.81, so the greedy algorithm correctly avoids it. Check H's neighbors: F. F offers no improvement (1.58). Stop and descend with H as entry point.

Layer 0 (beam search, ef_search = 3): Now we switch from the fast greedy descent to the more thorough beam search. Start at H (8, 2). Initialize candidates $C = \{H\}$, result set $W = \{H\}$. Process H's neighbors: G at (7, 3). We calculate the distance:

$$\begin{aligned} d(G, q) &= \sqrt{(7-6.5)^2 + (3-2.5)^2} \\ &= \sqrt{0.5^2 + 0.5^2} \\ &= \sqrt{0.25 + 0.25} \\ &= \sqrt{0.5} \\ &\approx 0.71 \end{aligned}$$

where:

• $G$: the neighbor node at coordinates $(7, 3)$
• $q$: the query vector at coordinates $(6.5, 2.5)$

G is closer than anything in $W$, so we add it to both sets. This is a significant improvement: the distance dropped from 1.58 to 0.71, showing how the dense layer 0 connectivity reveals nearby nodes that the sparser upper layers could not directly access. Process G's neighbors: F at (6, 1). Distance from F to $q$: 1.58. Add F. Now $|W| = 3$, which equals ef_search. Continue: Process F's neighbors. For E at (5, 2):

$$\begin{aligned} d(E, q) &= \sqrt{(5-6.5)^2 + (2-2.5)^2} \\ &= \sqrt{(-1.5)^2 + (-0.5)^2} \\ &= \sqrt{2.25 + 0.25} \\ &= \sqrt{2.5} \\ &\approx 1.58 \end{aligned}$$

where:

• $E$: the neighbor node at coordinates $(5, 2)$
• $q$: the query vector at coordinates $(6.5, 2.5)$

E is not closer than the farthest element in W (H at distance 1.58), so we are done exploring. The stopping criterion has been met: the best remaining candidate offers no improvement over the worst element in our result set.

Result: The nearest neighbor is G at (7, 3) with distance 0.71, found after visiting only 4 nodes out of 8. In this small example, the savings are modest, but the pattern is clear: the hierarchical descent brought us from the entry point to the right neighborhood in just two hops across the upper layers, and then a brief beam search on layer 0 identified the precise answer. In a real index with millions of vectors, this logarithmic scaling is what makes HNSW practical. The number of layers grows as $O(\log n)$, each layer requires only a handful of greedy steps, and the beam search on layer 0 explores a small, focused neighborhood rather than the entire collection.