HNSW Index: Architecture for Fast Vector Search › Graph Construction

HNSW builds its index incrementally: vectors are inserted one at a time, and each insertion both places the new node into the graph and establishes connections to existing nodes. This incremental approach means the graph evolves as data is added, with each new vector benefiting from the structure already in place and simultaneously enriching that structure for future insertions. The construction algorithm has two main phases for each inserted element.

When a new element $q$ is inserted, the first decision the algorithm must make is which layers this element will inhabit. This is determined by assigning a maximum layer $l$ using the randomized formula:

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

As we discussed in the previous section, this formula turns a uniform random draw into a geometrically decaying layer assignment. Let us revisit each component briefly in the context of construction:

• $l$: the maximum layer assigned to the node. The element will be present on every layer from 0 through $l$, and edges will be created for it on each of these layers.
• $\text{uniform}(0, 1)$: a random value drawn from a uniform distribution between 0 and 1. This is drawn independently for each inserted element. This keeps the layer assignments are uncorrelated.
• $-\ln(\text{uniform}(0, 1))$: a transformation using inverse transform sampling to convert the uniform value into an exponential distribution. Because the exponential distribution is heavily concentrated near zero, most nodes receive small values, and consequently low layer assignments.
• $m_L$: the level multiplier (typically $1/\ln(M)$), which scales the distribution to control the decay rate of layer probabilities. The choice of $m_L = 1/\ln(M)$ ties the layer structure directly to the connectivity parameter $M$. This keeps the hierarchy has the right density at each level.
• $\lfloor \dots \rfloor$: the floor function, which discretizes the continuous value into integer layers, since the hierarchy consists of discrete levels numbered 0, 1, 2, and so on.

This formula produces an exponential distribution of layers. With $M = 16$ and $m_L = 1/\ln(16) \approx 0.36$, the probabilities work out roughly as:

• ~94% of nodes exist only on layer 0
• ~6% reach layer 1
• ~0.4% reach layer 2
• A negligible fraction reach layer 3 or higher

These numbers convey an important structural insight: the vast majority of nodes live only on the bottom layer, where they contribute to the dense, fine-grained connectivity needed for precise nearest neighbor identification. A small fraction of nodes are "promoted" to higher layers, where they serve as landmarks and waypoints for long-range navigation. And only a tiny handful reach the topmost layers, where they act as universal entry points from which any search can begin. This exponential decay is precisely what creates the skip list-like structure. Each layer is roughly $M$ times sparser than the one below it.

The insertion order matters less than you might think, because of the random layer assignment. Whether a node is inserted early or late in the construction process, its layer is determined by the random draw, not by its position in the insertion sequence. This stochastic nature is also what makes HNSW resilient: no adversarial input sequence can force all nodes to the top layer, creating a degenerate hierarchy. The randomness ensures that, in expectation, the layer distribution always follows the intended exponential decay.

Once the new element $q$ has its assigned layer $l$, the algorithm needs to find good neighbors to connect it to on each layer from $l$ down to 0. The quality of these connections is critical: they determine whether the graph will be navigable and whether future searches will be able to efficiently route through this part of the space. This happens in two phases.

Phase 1: Descend to the insertion layer. Starting from the global entry point at the top layer, perform a simple greedy search (beam width of 1) on each layer above $l$. At each layer, walk greedily toward $q$ until no closer neighbor can be found, then descend. This phase finds a good starting point for the actual insertion work. No connections are made during this descent. By the time the algorithm reaches layer $l$, it has identified a node that is reasonably close to $q$ in the vector space. This provides a high-quality starting point for the neighbor search that follows.

Phase 2: Insert and connect. Starting from layer $l$ down to layer 0, perform a broader search (with beam width ef_construction) to find the closest existing nodes to $q$. The parameter ef_construction governs how thoroughly the algorithm explores the neighborhood around $q$. A larger ef_construction means more candidate nodes are examined, increasing the likelihood of finding the truly best neighbors at the cost of additional distance computations. From these candidates, select the best $M$ neighbors and create bidirectional edges between $q$ and each selected neighbor. The bidirectionality is essential: it ensures that $q$ is reachable from its neighbors and that $q$'s neighbors are reachable from $q$, maintaining the graph's navigability in both directions.

The selection of which $M$ neighbors to connect is critical and deserves careful attention. The simplest approach is to pick the $M$ closest nodes, but HNSW uses a more sophisticated heuristic that favors diversity. The heuristic prefers neighbors that are close to $q$ while covering different "directions" in the vector space. This prevents all connections from clustering in one region and ensures better navigability.

To understand why diversity matters, imagine a scenario where a new node $q$ is positioned at the edge of a dense cluster. The $M$ closest nodes might all be members of that same cluster, all lying in roughly the same direction from $q$. If $q$ connects only to these nearby cluster members, there would be no edge leading outward from $q$ toward other regions of the space. Future searches passing through $q$ would find it easy to reach the nearby cluster but impossible to exit toward other clusters. The diversity heuristic avoids this trap by ensuring that $q$'s connections reach outward in multiple directions.

The neighbor selection heuristic works as follows. Candidates are sorted by distance to $q$. For each candidate $c$ (in order of increasing distance), $c$ is added to the neighbor set only if it is closer to $q$ than it is to any already-selected neighbor. In other words, a candidate is rejected if it is "covered" by an already-chosen neighbor:

$$\text{Add } c \text{ if } d(q, c) < \min_{n \in \text{selected}} d(c, n)$$

We define the meaning and purpose of each symbol in this condition:

• $c$: the candidate neighbor being considered. Candidates are examined one at a time, in order of increasing distance from $q$, so the closest candidates are considered first.
• $q$: the newly inserted element, the node for which we are selecting neighbors.
• $d(x, y)$: the distance between $x$ and $y$, measured using whatever metric the index employs (Euclidean, inner product, or cosine distance).
• $\text{selected}$: the set of neighbors already chosen for $q$. This set starts empty and grows as candidates pass the heuristic test.
• $\min_{n \in \text{selected}} d(c, n)$: the distance from the candidate $c$ to the closest already-selected neighbor. This is the crux of the heuristic. If $c$ is very close to some already-selected neighbor $n$, then $n$ already "covers" the direction that $c$ would provide. Adding $c$ would be redundant, as searches arriving at $q$ could reach $c$'s region of the space by going through $n$ instead.

This condition ensures that we only add $c$ if it is closer to $q$ than to any existing neighbor. The geometric intuition is that each selected neighbor "claims" a region of space around it, and a new candidate is accepted only if it lies in an unclaimed direction. This encourages connections that spread outward in different directions, creating the diverse connectivity that makes the graph navigable.

The result of the diversity heuristic is a neighbor list where each connection opens up a distinct corridor through the vector space, maximizing the routing options available to future searches passing through $q$. The heuristic is applied during both construction and overflow pruning. This keeps the graph maintains its diverse connectivity as new nodes are added.

When a new edge is added between $q$ and an existing node $v$, the node $v$ might end up with more than $M_{\text{max}}$ connections. This overflow can happen because the bidirectional edge creation means that $v$ receives a new neighbor even though $v$'s original neighbor list was already full. In this case, $v$'s neighbor list is pruned back to $M_{\text{max}}$ using the same heuristic selection described above, keeping the most useful connections and discarding redundant ones.

The pruning re-evaluates all of $v$'s current neighbors (including the newly added $q$) and retains the set that best satisfies the diversity criterion. This keeps $v$'s connections continue to cover multiple directions. The paper uses $M_{\text{max}} = M$ for layers above 0, and $M_{\text{max0}} = 2M$ for layer 0, since the bottom layer benefits from denser connectivity. The rationale for doubling the connection limit on layer 0 is that this is where the most precise search occurs, and having more edges per node increases the probability that the greedy search can reach the exact nearest neighbor without getting stuck in a local minimum.

The full construction algorithm for inserting element $q$:

1. Assign random layer $l$ to $q$
2. Set entry point $ep$ to the current graph's entry point
3. For each layer from the top down to $l+1$: greedily search for the nearest node to $q$, update $ep$
4. For each layer from $l$ down to 0: a. Search for ef_construction nearest candidates to $q$ starting from $ep$ b. Select up to $M$ neighbors from candidates using the heuristic c. Add bidirectional edges between $q$ and selected neighbors d. For any neighbor that now exceeds $M_{\text{max}}$ connections, prune its neighbor list
5. If $l$ is higher than the current maximum layer, update the entry point to $q$

Step 5 deserves a brief note: whenever a newly inserted node reaches a layer higher than any existing node, it becomes the new global entry point for the entire index. This ensures that searches always begin at the topmost layer, where the sparsest, most globally connected node provides the starting point for the coarse navigation phase.

The construction cost is $O(n \log n)$ in total. Each insertion requires finding neighbors across the layers it inhabits, and the hierarchical structure ensures that this neighbor search takes $O(\log n)$ time per layer. Most nodes are on layer 0 only, so the dominant cost is the layer 0 search, which scales as $O(\log n)$ with a constant proportional to ef_construction. In practice, construction is typically 10 to 100 times slower than search, because construction uses a wider beam (ef_construction) and must run many insertions sequentially.