HNSW Index: Architecture for Fast Vector Search › Search Procedure

Searching an HNSW index follows the same two-phase pattern as construction, but optimized for finding the $k$ nearest neighbors of a query vector $q$. The search algorithm uses the hierarchical structure to decompose the problem into a fast coarse approach followed by a thorough local exploration, and this decomposition is what gives HNSW its characteristic efficiency.

Starting from the entry point on the top layer, perform a simple greedy search with beam width 1. At each layer, repeatedly move to the neighbor closest to $q$ until no improvement is possible. Then descend to the next layer, using the current best node as the entry point for the layer below.

This phase is fast because upper layers are sparse. Each greedy step on the top layer might skip over millions of vectors in a single hop. The descent quickly narrows the search to the right neighborhood. To build a concrete intuition, consider a graph with 10 million vectors and $M = 16$. The top layer might contain only a handful of nodes, and a single greedy step on this layer could jump from one end of the vector space to the other. Layer 2 might contain a few thousand nodes, and each hop covers a correspondingly smaller but still substantial distance. By the time the algorithm reaches layer 1, it has narrowed the search region from the entire collection down to a small neighborhood containing perhaps a few thousand nearby vectors. The total number of distance computations during this descent is remarkably small, typically just a few per layer, because only a single candidate (the current best) is tracked.

The greedy descent with beam width 1 is intentionally narrow. Using a wider beam during the descent would slow it down without providing much benefit, because the goal here is not to find the exact nearest neighbor but to land in the right neighborhood. The coarse structure of the upper layers ensures that even a single-node beam finds an excellent starting point for the beam search on layer 0.

Once you reach layer 0, the algorithm switches strategy. The greedy descent with beam width 1 was efficient but coarse; it found a good starting neighborhood but may not have identified the exact nearest neighbors. Layer 0, which contains all vectors, is where the precise answer lives. To find it, the algorithm performs a more thorough search using a beam width of ef_search (where ef_search $\geq k$). This is essentially a best-first search that maintains a dynamic candidate list:

1. Initialize a candidate set $C$ and a result set $W$ with the entry point from Phase 1.
2. While $C$ is not empty: a. Extract the nearest unvisited candidate $c$ from $C$ b. If $c$ is farther from $q$ than the farthest element in $W$, stop (no more useful candidates) c. For each neighbor $n$ of $c$ that has not been visited:
   • If $n$ is closer to $q$ than the farthest element in $W$ (or $|W| <$ ef_search), add $n$ to both $C$ and $W$
   • If $|W| >$ ef_search, remove the farthest element from $W$
3. Return the $k$ closest elements from $W$

The stopping condition in step 2b is the key to this algorithm's efficiency: the moment the best remaining candidate is worse than the worst element already in the result set, the search terminates. This means the algorithm does not exhaustively explore all reachable nodes; instead, it expands outward from the entry point in order of proximity to the query, and stops as soon as further expansion cannot possibly improve the results.

The parameter ef_search controls how thorough this search is. A larger ef_search explores more candidates, improving recall at the cost of more distance computations. Setting ef_search = k gives the fastest (but least accurate) search, while larger values progressively improve accuracy. The reason is straightforward: with a larger beam, the algorithm keeps more "backup" candidates alive during the search, reducing the chance that an early wrong turn causes it to miss the true nearest neighbor. Conversely, a very small beam means the search commits aggressively to its initial direction, finishing quickly but occasionally missing better answers in adjacent regions.

The complexity of the full search is $O(\log n)$ for the greedy descent plus $O(\text{ef\_search} \cdot \log(\text{ef\_search}))$ for the beam search on layer 0. In practice, the dominant cost is the layer 0 beam search, and the total number of distance computations typically falls between a few hundred and a few thousand even for billion-vector indexes, a dramatic reduction from the billions of computations that brute-force search would require.