HNSW Layer Assignment and the Greedy Descent

A proximity graph answers a nearest-neighbor query by walking: from some entry point, repeatedly move to the neighbor closest to the query, and stop when no neighbor improves. The walk is cheap, each step being a handful of distance computations, and it is also fragile, because a graph built only from local links has local minima. Two points can be close to the query but unreachable from each other’s neighborhoods. The hierarchical navigable small world construction solves that by adding a sparse set of long-range links at the top of a layered structure, and the way those layers are populated is the part worth understanding precisely.

Why a flat graph stalls

Consider a graph where each record is connected to its $M$ nearest neighbors. Greedy search from an arbitrary entry point follows a chain of decreasing distance. Because links are local, the chain moves in small steps, and a query whose nearest neighbor lies in a different dense region has to cross the sparse gap between regions. If no edge spans the gap, the walk stops at a point that is locally optimal and globally wrong.

The classic small-world construction fixes this by giving a few nodes very high degree, connecting distant regions. But the number of such hubs must grow with the collection, and the degree distribution becomes heavy-tailed, which makes the traversal unpredictable and the memory layout hostile.

HNSW takes the skip-list idea and applies it to the graph. A skip list achieves logarithmic search in a sorted list by building several levels of increasingly sparse express lanes; a search starts at the sparsest level and descends, refining at each step. HNSW does the same with a proximity graph: the top layer contains a small subset of records with long-range links, each lower layer adds more records and shorter links, and the bottom layer contains everything.

The level draw

When a record is inserted, it is assigned a maximum level $\ell$ by a random draw:

$$\ell = \lfloor -\ln(U) \cdot m_L \rfloor, \quad U \sim \text{Uniform}(0,1)$$

with $m_L = 1/\ln M$ for the connection parameter $M$. The distribution is geometric in effect: a record reaches level $\ell$ or above with probability $e^{-\ell/m_L}$, so each successive level holds roughly $1/M$ of the records below it.

With $M = 16$ and $m_L \approx 0.36$, each successive level holds roughly a sixteenth of the records below it: one record in sixteen reaches level 1, one in 256 reaches level 2, one in 4096 reaches level 3. A collection of ten million records therefore gives a level-one layer of about 600,000 nodes, a level-three layer of a few thousand, and a top layer of a handful. The total number of levels is around five, and it grows logarithmically with the collection size, which is what makes the construction scale: at the top the node count is small enough that a linear scan would also work.

The draw is made once and never revised. This is important: the level is not a function of the record’s position in space, so a record can end up as the sole occupant of a high level despite being in a sparse region. That is a feature, because it guarantees long-range connectivity even where the data has no hubs, but it also means the top layer’s quality is a matter of chance for small collections. With a few thousand records the top level may contain one node, and the descent begins with a single comparison.

Each record stores its level and, for each level from zero up to its own, up to $M$ neighbor identifiers. The base layer is usually allowed twice that, since it carries the finest granularity and the most candidates: a common configuration allows $2M$ links at level zero and $M$ above it.

Insertion: search, select, link both ways

Insertion reuses the search machinery.

The new record first descends from the top layer to its own level $\ell + 1$ using greedy search with a single candidate: at each layer, move to the neighbor closest to the new record until no neighbor improves, then drop to the next layer from that position. No candidate list is maintained; the goal is only to find a good entry point for the layer where real linking begins.

At each layer from $\ell$ down to zero, the algorithm runs a search with a candidate list bounded by the construction parameter, typically called efConstruction, and much larger than the final result size. That search returns the closest records found at that layer, and the new record is connected to a selected subset of them. The selection is not simply the nearest $M$; a heuristic prefers a candidate only if it is closer to the new record than to any already-selected neighbor. This diversity rule prevents a node’s links from all pointing into the same tight cluster, preserving the long-range connectivity the layers exist to provide.

Every link is added in both directions. That symmetry is what allows a later query to traverse the edge from either end, and it is also the source of the maintenance burden: adding a link to an existing record may push its degree above the limit, requiring that record’s neighbor list to be pruned. Pruning re-runs the diversity heuristic over the overfull list. The cascading cost is bounded because the pruning is local, but it means insertion is not a fixed-cost operation.

import heapq, math

def search_layer(query, entry, layer, graph, dist, ef):
    """Greedy beam search over one layer. Returns up to ef nearest found."""
    visited = {entry}
    d0 = dist(query, entry)
    candidates = [(d0, entry)]          # min-heap on distance
    results = [(-d0, entry)]            # max-heap, keeps the ef best
    while candidates:
        d, node = heapq.heappop(candidates)
        if d > -results[0][0] and len(results) >= ef:
            break                        # every remaining candidate is worse
        for nb in graph[node].get(layer, ()):
            if nb in visited:
                continue
            visited.add(nb)
            dn = dist(query, nb)
            if len(results) < ef or dn < -results[0][0]:
                heapq.heappush(candidates, (dn, nb))
                heapq.heappush(results, (-dn, nb))
                if len(results) > ef:
                    heapq.heappop(results)
    return sorted((-d, n) for d, n in results)

The termination test is the load-bearing line. The candidate heap is ordered by distance, so once the best unexpanded candidate is worse than the worst of the current ef results, no unexpanded node can improve the result set, and the loop stops. Without the ef bound the loop would either stop too early, at the first local minimum, or expand the whole layer.

What ef bounds, and what it does not

ef is the size of the candidate list held during search. It is a lower bound on the work, not an upper bound: a search can visit more than ef nodes, because every expanded node’s neighbors are examined, and the number of expansions is bounded only indirectly by the distance test. Raising ef widens the beam, so the walk explores more of each neighborhood and is less likely to stop at a local minimum. Raising it also increases the number of distance computations roughly linearly in the useful range.

The relationship to recall is monotone but concave. Small increases at low ef recover a lot of recall; past the point where the true neighbors are already inside the beam, additional candidates are examined and discarded. The curve’s knee depends on the graph’s quality, which depends on efConstruction and $M$.

efConstruction is the same parameter applied during insertion, and it has a persistent effect: it determines how well connected each new record is when it joins. A record inserted with a small candidate list connects to whichever neighbors a narrow search found, and those links may be poor. The defect cannot be repaired by a larger search ef at query time, because the edges that would have connected the record to the right region were never created. That asymmetry, in which construction quality sets a floor on achievable recall, is the most commonly misunderstood property of the structure.

$M$ trades memory for connectivity directly. Each link costs four or eight bytes depending on identifier width, so a record at level zero with $2M = 32$ links costs 128 bytes of edge storage at four-byte identifiers, against 3072 bytes for a 768-dimensional float32 vector. Edge storage is a few percent of vector storage at these widths and becomes comparable only when the vectors themselves are quantized to short codes. Raising $M$ improves recall at fixed ef because each node has more routes out, and it raises insertion cost because each link addition can trigger a prune.

Layer-by-layer behavior, and where the cost sits

The descent from the top layer costs a handful of distance computations per layer: with five layers and a top layer of a few thousand nodes, the top-level walk is a few dozen comparisons. That is negligible against the base-layer search, which is where nearly all the work happens. The hierarchy’s contribution is not to reduce the base search’s cost directly but to start it from a good entry point, which lets a small ef succeed where a flat graph would need a large one.

The graph’s memory layout matters more than the layer count. Each hop is a random access into a node’s adjacency list, and the vector must then be fetched to compute the distance. With vectors stored in a flat array indexed by identifier, a hop costs two cache misses: one for the adjacency list and one for the vector. Since each hop performs only a few distance computations, the loop is latency-bound rather than throughput-bound, and prefetching the neighbors’ vectors while their identifiers are being read is the main optimization. On-disk variants that fetch whole adjacency blocks amortize the first miss but pay far more for the second; the memory-bandwidth consequences are the subject of Disk-Resident Graph Indexes and the Memory Bandwidth Wall.

Failure modes

Deleted records are the sharpest operational problem. Removing a node from a graph requires rewiring every neighbor that points to it, otherwise the walk traverses a dangling edge and either errors or silently skips. Most implementations mark the node as deleted and let the search ignore it, which preserves traversability at the cost of the node still occupying its edges and its vector. Over time the index fills with nodes that participate in routing but never appear in results, and both memory and search cost grow without the collection growing. The remedies are periodic rebuilds or incremental compaction, discussed in Tombstones, Merges, and the Cost of Keeping a Vector Index Current.

A second failure is a graph disconnected at the base layer. This happens when the collection is inserted in an adversarial order — all of one cluster first, then another — and early records never receive links to the later ones because the later records were not present when the early ones were linked. Bidirectional linking and the diversity heuristic mitigate this, but insertion order still measurably affects recall. Bulk construction that interleaves or randomizes the insertion order produces a graph less sensitive to the source order than one built by appending records as they arrive.

A third is the monotonicity assumption in the greedy walk. Moving to the closest neighbor is not guaranteed to make progress toward the true nearest neighbor when the graph’s edges are not all short; a long-range edge can lead into a region from which the only escape is back. The ef bound and the candidate heap absorb this, since the search can retreat to a previously queued candidate, but a very small ef with a graph that has many long edges can oscillate. Implementations rely on the visited set to prevent revisiting, which bounds the oscillation but converts it into wasted work rather than incorrect results.

Finally, the structure is not a metric index and offers no guarantee. There is no bound on the error, no worst-case complexity better than a scan, and no way to know from the parameters alone whether a given collection will be served well. The only reliable procedure is to build, measure recall against exact search on a sample of queries, and adjust ef to meet the target. That is why the parameters which appear in every configuration file are empirical rather than derived.