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

To understand HNSW, we need to start with the concept that gives it half its name: small world graphs.

In the 1960s, psychologist Stanley Milgram conducted his famous "small world" experiment, asking people to forward letters to a target person through chains of acquaintances. He found that most letters arrived in about six steps, giving rise to the popular phrase "six degrees of separation." This phenomenon, where nodes in a large network can reach each other through surprisingly short paths, is the small world property.

To appreciate why this property is remarkable, consider the contrast with what we might naively expect. If a graph has a million nodes and each node connects only to a few neighbors, you might imagine that traversing from one side of the graph to the other would require thousands or even hundreds of thousands of hops. In a chain or grid structure, that intuition holds true: the number of hops scales with the diameter of the structure, which can be proportional to $n$ or $\sqrt{n}$. But small world graphs defy this expectation. Even as the number of nodes grows into the millions or billions, the average path length between any two nodes increases only logarithmically.

What makes social networks "small worlds" is the combination of two structural features:

• Local clustering: People tend to know others in their immediate community, creating dense local neighborhoods. Your friends are likely friends with each other, forming tightly knit clusters of mutual connections. Mathematically, this is captured by a high clustering coefficient: the fraction of a node's neighbors who are also neighbors of each other is large.
• Long-range connections: A few connections bridge distant communities (a friend who moved abroad, a colleague in a different industry). This provides shortcuts across the graph. These rare but critical links act as express highways. This allows you to jump from one cluster to a completely different one in a single step.

The interplay between these two features creates the small world property. Local clustering alone would produce a graph where short paths exist only within communities, and reaching a distant community would require traversing the entire structure. Long-range connections alone would create a graph where you can jump anywhere quickly but lack the dense local structure needed for precise navigation once you are in the right neighborhood. Together, they enable a style of traversal where long-range hops bring you close to your target quickly, and then dense local connections let you zero in on exactly the right node.

The mathematical characterization of small world graphs comes from Watts and Strogatz (1998), who studied the transition between regular lattices (high clustering, long path lengths) and random graphs (low clustering, short path lengths). By rewiring a small fraction of edges in a regular lattice to create random long-range connections, they produced graphs that simultaneously exhibited high clustering and short path lengths. This combination is exactly what we want for navigation: the local structure provides precision, and the long-range structure provides speed.

This same structure turns out to be incredibly useful for nearest neighbor search. If we build a graph where vectors are nodes and edges connect similar vectors, we can move from any starting point to any query's nearest neighbor by repeatedly jumping to the most promising neighbor, much like forwarding Milgram's letters. The key realization is that vector similarity naturally provides the notion of "closeness" needed to organize these connections: nearby vectors in the embedding space form the local clusters, while occasional connections to more distant vectors serve as the long-range bridges.