HNSW Index: Architecture for Fast Vector Search › The Hierarchical Insight

HNSW solves the long-range navigation problem with an elegant idea borrowed from skip lists, a probabilistic data structure for sorted sequences.

In a skip list, elements exist on multiple levels. The bottom level contains all elements. Each higher level contains a random subset of the elements from the level below, with roughly half as many elements per level. Searching starts at the top level, where elements are sparse and each hop covers a large range, then descends to lower levels for finer-grained search. This gives $O(\log n)$ search time. A skip list achieves the efficiency of a balanced binary search tree without requiring complex rebalancing operations, relying instead on simple randomization to maintain its structure.

HNSW applies the same principle to graph-based nearest neighbor search, translating the one-dimensional skip list into a multi-dimensional navigable graph hierarchy. Instead of a single graph, HNSW builds a hierarchy of graphs across multiple layers:

• Layer 0 (the bottom layer) contains all vectors, connected to their nearest neighbors with short-range edges. This layer is the most densely populated and provides the fine-grained resolution needed to identify the true nearest neighbors.
• Layer 1 contains a subset of vectors, connected with edges that naturally span longer distances (because the nodes are more spread out). Since fewer nodes exist on this layer, even connecting to "nearest neighbors" produces edges that cover more ground in the vector space.
• Layer 2 contains an even smaller subset, with even longer-range connections. The sparser the layer, the more each edge acts as a highway through the space.
• The top layer contains just a handful of nodes. This provides a coarse "highway" across the entire vector space. A single hop on this layer might span a distance that would require dozens of hops on layer 0.

HNSW determines which layer each node belongs to using a randomized assignment process that mirrors the probabilistic structure of skip lists. Each node is assigned a maximum layer using a random process. Most nodes exist only on layer 0. Fewer nodes reach layer 1, fewer still reach layer 2, and so on. The maximum layer $l$ is assigned using a formula that ensures this exponential decay:

$$l = \lfloor -\ln(\text{uniform}(0, 1)) \cdot m_L \rfloor$$

We examine each component and its role in producing the desired distribution of layers:

• $l$: the maximum layer assigned to the node. A node assigned layer $l$ will exist on every layer from 0 up to $l$, meaning it participates in the graph at multiple levels of the hierarchy.
• $\text{uniform}(0, 1)$: a random value drawn from a uniform distribution between 0 and 1. This is the source of randomness that ensures different nodes end up on different layers. Each insertion draws independently from this distribution.
• $-\ln(\text{uniform}(0, 1))$: this transformation is a classic technique known as inverse transform sampling. The negative natural logarithm of a uniform random variable produces a value that follows an exponential distribution with rate parameter 1. Most of the time, the uniform draw is close to 1, making $-\ln(\text{uniform}(0,1))$ close to 0, which means most nodes will be assigned to low layers. Occasionally, the uniform draw is close to 0, producing a large value of $-\ln(\text{uniform}(0,1))$ and placing the node on a high layer. This naturally produces the "many nodes at the bottom, few at the top" structure we need.
• $m_L$: the level multiplier, typically set to $1/\ln(M)$. This scaling factor controls how quickly the exponential distribution decays and, consequently, how many nodes appear on each successive layer. By tying $m_L$ to $M$, the formula ensures that the probability of reaching layer $l$ is proportional to $M^{-l}$. In other words, each layer has roughly $1/M$ times as many nodes as the layer below it.
• $\lfloor \dots \rfloor$: the floor function, which discretizes the continuous exponential value into integer layers. Since layers are discrete (layer 0, 1, 2, ...), the continuous value must be rounded down to the nearest integer.

The net effect of this formula is that each layer has roughly $1/M$ times as many nodes as the layer below, mirroring the skip list structure. This exponential thinning is what gives HNSW its logarithmic search complexity: the number of layers grows as $O(\log_M n)$, and each layer requires only a bounded number of greedy steps, so the total search cost scales logarithmically with the number of vectors.

Why does this hierarchy solve the local minimum problem? Because on the upper layers, the graph is so sparse that a node's "nearest neighbors" on that layer span large distances in the vector space. The global structure of the embedding space is visible even through simple greedy routing, because the sparser a layer is, the more each edge functions as a long-range bridge. When the search descends to lower layers, it arrives with a much better starting point than any random entry would provide, and the denser connectivity of lower layers ensures that the greedy algorithm can refine its answer without getting permanently stuck.

This design naturally separates the two phases of search:

1. Coarse navigation (upper layers): With few, widely-spaced nodes, each greedy step covers a large distance. You quickly zoom into the right region of the space. Because the nodes on upper layers are sparse representatives of the entire collection, the graph on each upper layer acts like a coarse map, and greedy routing on this map efficiently narrows the search to the correct neighborhood.
2. Fine-grained search (lower layers): With many densely-connected nodes, you refine your search to find the actual nearest neighbors. Once the upper layers have brought you to approximately the right region, layer 0's dense connectivity ensures that the final, precise answer is reachable within a few more hops.