What is the HNSW insertion algorithm?

The HNSW insertion algorithm is the precise sequence of steps HNSW follows to add a single new vector into an existing graph — assign it a layer, descend greedily through the layers above its own to find a good entry point, then search and connect at every layer from its own maximum down to the base. It’s the procedure that index construction, covered on its own glossary page, applies over and over across an entire dataset, and walking through its individual steps in order shows exactly how the broader concepts covered elsewhere in this glossary category — layer assignment, construction search, neighbor selection — actually fit together into one coherent, repeatable operation.

What is the very first thing that happens when a new vector arrives for insertion?

Before anything involving the graph‘s structure happens, the new vector is assigned a maximum layer through the random process described on the level-assignment-probability glossary page, drawing from the exponentially decaying distribution controlled by mL. This single number determines every layer the new node will eventually participate in, since it gets placed in every layer from zero up through that maximum. This assignment happens once, upfront, entirely independent of the vector’s actual position in the embedding space or anything about the graph’s current structure — it’s a purely random draw that has already fully determined the shape of this node’s eventual participation in the hierarchy before a single distance calculation has even been performed.

What happens next, in the layers above the new node’s own maximum layer?

If the new node’s assigned maximum layer is lower than the current entry point’s layer — which is the common case for the great majority of insertions, since high layers are rare — the algorithm performs a simple greedy descent through each of those higher layers, exactly as described on the greedy-navigation glossary page: starting from the current global entry point, move to whichever neighbor looks closest to the new vector, repeating until no further improvement is available in that layer, then drop down one level and repeat. This phase doesn’t add any connections at all — the new node isn’t present in these upper layers, since its own maximum layer is lower than them — its only purpose is to find a good starting position to hand off to the layer where the new node’s own connections will actually begin forming.

This descent phase is functionally identical to the corresponding phase of a query-time search, and it’s worth recognizing that similarity explicitly: an insertion is, in this initial stage, doing exactly what a search for the new vector’s own position would do, simply because finding a good starting point for constructing connections requires the same kind of navigation as finding a good starting point for answering a query.

What happens once the descent reaches the new node’s own maximum layer, where its actual connections begin?

From this point down through every layer the new node participates in — from its own maximum layer down to and including the base layer — the algorithm switches from simple greedy descent to the fuller construction-time search described on its own glossary page, using efConstruction as the target result size rather than the single-best-point target used above. At each of these layers, this search produces a pool of candidate neighbors, and the neighbor-selection heuristic then chooses a diversified subset of that pool, sized to fit within M or Mmax0 depending on the layer, as the new node’s actual connections at that specific level.

Crucially, every connection formed this way gets established as a bidirectional edge, as covered on its own glossary page: the new node connects to its chosen neighbors, and each of those neighbors also gets a reverse connection back to the new node, subject to their own capacity limits and the overflow-and-pruning mechanism that applies whenever a neighbor list is already full. This step is what actually integrates the new node into the existing graph’s structure, rather than merely finding it a good position relative to that structure.

How does the algorithm decide when the insertion is actually finished, and does the global entry point ever change as a result?

The insertion process finishes once connections have been formed at every layer from the new node’s maximum down through the base layer — there’s no additional cleanup or verification step beyond what the overflow-handling mechanism already performs during each layer’s connection-forming step. The one remaining piece of global bookkeeping is checking whether the new node’s maximum layer happens to exceed the current entry point’s layer: if it does, the new node itself becomes the new global entry point, exactly as described on the entry-point-in-HNSW glossary page, and every future search or insertion will begin its own descent from this new node instead of the previous entry point.

Having walked through the insertion algorithm’s full sequence from initial layer assignment through to final connection and the possible entry-point update, the construction-search and neighbor-selection-heuristic glossary pages are worth revisiting for a closer look at the two steps that do the heaviest lifting within this sequence. From there, the descend-to-insertion-level-step glossary page zooms in specifically on the greedy-descent phase described here, and the bidirectional-connection-during-insertion page covers the final connection-forming step in more mechanical detail.