How is an HNSW graph actually built, one insertion at a time?

Building an HNSW graph means inserting vectors one at a time, and each insertion is really a small search followed by a connection step: the algorithm first figures out where in the existing graph a new vector belongs, then wires it into place at every layer it will participate in, occasionally pruning an existing vector’s connections along the way to keep the graph from growing unbounded degree.

How is a new vector’s maximum layer chosen?

Before anything else happens, the algorithm decides how high into the layer structure the new vector will reach, using a random draw with a probability that decreases exponentially the higher it goes — the same mechanism responsible for keeping the upper layers sparse, described in more depth on the previous page. Most vectors are assigned to the bottom layer only; a much smaller fraction reach one layer up, and progressively fewer reach each layer above that. This single random decision, made independently for every vector as it’s inserted, is what produces the pyramid shape without requiring any global coordination or rebalancing step.

What happens in the layers above where the new vector will actually live?

Once a maximum layer has been chosen, the algorithm starts at the graph’s current entry point, at the topmost occupied layer, and performs the same plain greedy descent used during ordinary search: move to whichever neighbor is closer to the new vector, and drop down a layer once no neighbor is closer than the current position. This continues through every layer above the new vector’s own assigned layer. No connections are created during this phase, since the new vector doesn’t exist in these upper layers at all — the sole purpose of this descent is to arrive at a good starting position by the time the algorithm reaches the layers where the new vector actually needs to be wired in.

What happens once the descent reaches the vector’s own layers?

From the new vector’s assigned layer down to the base layer, the process changes from plain greedy descent into the same wider search procedure used during ordinary querying, except the “query” here is the new vector itself and the results being sought are its future neighbors. At each of these layers, the search explores a configurable number of candidates, controlled by a construction-time counterpart to the search-time exploration width — a wider search here considers more potential neighbors and generally produces a higher-quality set of connections, at the cost of a slower insertion. Once this per-layer search finishes, the new vector is connected to a selection of the resulting candidates, and each of those connections is added in both directions at once — from the new vector to its chosen neighbor, and from that neighbor back to the new vector — so that the graph remains something either vector can be discovered through, not just the newly inserted one.

Why does connecting a new vector sometimes require pruning an existing one?

Every vector’s neighbor list has a maximum size, larger at the base layer than in the sparser layers above, and a newly formed bidirectional connection can push an existing vector’s neighbor count past that limit. When this happens, the affected vector’s neighbor list is pruned back down to size using the same selection logic that chose the new vector’s own neighbors in the first place — favoring a diverse spread of connections over simply keeping whichever ones happen to be closest — rather than just dropping the new connection or discarding neighbors at random. This matters because a vector’s usefulness to the graph depends on which neighbors it keeps, not merely on how many it has, and treating a full neighbor list the same way as an initial neighbor selection keeps that quality standard consistent no matter when in the graph’s history a particular connection was formed.

The next page looks specifically at that neighbor-selection logic on its own terms, since the same rule governs both a fresh vector’s initial connections and any later pruning, and it turns out to matter more than raw distance in ways that aren’t obvious at first glance. For concrete guidance on how wide the construction-time search should actually be set for a given dataset, the tuning-and-optimization section of this site picks that question up in detail.