HNSW Index: Architecture for Fast Vector Search › Navigable Small World Graphs

A small world graph guarantees that short paths exist between any two nodes, but that alone is not enough. We also need to be able to find those short paths efficiently, without knowing the global structure of the graph. This introduces navigability, a subtle but critical distinction.

The existence of a short path is a property of the graph's topology. Navigability, by contrast, is a property of how easily a simple, local algorithm can discover and follow that path. Imagine being dropped into a massive city with no map. Knowing that every location is reachable within a few blocks is reassuring, but useless if you have no way to decide which direction to walk at each intersection. Navigability means that at every intersection, looking only at the streets immediately available to you, you can make a locally informed decision that consistently brings you closer to your destination.

Consider a simple greedy search on such a graph. You start at some entry node and want to reach the node closest to your query vector $q$. At each step, you look at all neighbors of your current node, compute their distances to $q$, and move to whichever neighbor is closest. You stop when no neighbor is closer to $q$ than your current node. This is a classic greedy best-first search, and its elegance lies in its simplicity: no priority queues spanning the entire graph, no global routing tables, and no precomputed shortest paths. The only information the algorithm uses at each step is the set of neighbors of the current node and their distances to the query.

For this to work well, the graph needs those same two structural ingredients we discussed above, but now viewed through the lens of routing. Dense local connections ensure that once you are near the target, you can find it precisely. Without them, the greedy search might reach the right neighborhood but be unable to take the final steps to the exact nearest neighbor, because no edge connects the current node to the true answer. Long-range connections ensure that you can quickly traverse from distant regions of the vector space to the target's neighborhood. Without them, the greedy search would have to take many small steps, inching across the space one local cluster at a time, turning what should be a logarithmic traversal into a linear one.

The problem with a flat (single-layer) NSW graph is that the greedy search can get trapped in local minima. As the graph grows, long-range connections become increasingly diluted by short-range ones. Early in the search, when you are far from the target, you need long-range jumps to make progress quickly. But in a large flat graph, the probability of finding a useful long-range connection among a node's fixed-size neighbor list diminishes as the graph grows.

Consider what happens during graph construction: when a node is inserted, its neighbors are chosen from the closest existing nodes. In a large graph, those closest nodes are very nearby, so the resulting edges are short-range. Long-range edges, which were created early when the graph was small and "closest" meant "relatively far away," become a smaller and smaller fraction of the total edges. The search degrades, requiring more hops and more distance computations, and the greedy algorithm's performance begins to approach the very linear scaling we are trying to avoid.

There is also a deeper problem: the greedy algorithm can get stuck at a local minimum that is not the global nearest neighbor. Imagine a query $q$ positioned in the vector space. The greedy search might reach a node $v$ that is reasonably close to $q$, but none of $v$'s neighbors are closer. The algorithm terminates and reports $v$ as the nearest neighbor, even though the true nearest neighbor $u$ exists elsewhere in the graph and is closer to $q$. This happens because the path from $v$ to $u$ requires moving temporarily away from $q$, and the greedy algorithm refuses to do so. In a flat graph, there is no mechanism to escape this trap. The hierarchical structure of HNSW is the solution.