What is an upper layer in HNSW?

An upper layer in HNSW is any layer above the base layer — layer one, layer two, and so on up through however high the hierarchy happens to reach — each containing only a randomly selected fraction of the full dataset, with that fraction shrinking further at each successive level. Where the base layer holds every vector and serves as the place where a search’s final answer actually gets produced, the upper layers exist purely in service of getting the search into roughly the right neighborhood as quickly as possible before that final, careful work begins.

Why do the upper layers contain so much less data than the base layer?

A vector‘s presence in an upper layer is determined entirely by the random layer-assignment process applied when it’s first inserted, which is deliberately designed to make higher layers exponentially less populated than lower ones. This isn’t an incidental side effect — it’s the entire point of the hierarchy’s design. If the upper layers held as many vectors as the base layer, they’d offer no efficiency advantage over simply searching the base layer directly, since there would be no meaningful difference in how much of the graph a search would need to traverse. By keeping the upper layers sparse, HNSW ensures that a search operating within them naturally covers large distances in relatively few hops, since there simply aren’t many nearby candidates at that level to force the search into a long chain of small, incremental steps.

This sparsity compounds going up the hierarchy: layer one might contain a modest fraction of the full dataset, layer two a much smaller fraction still, and so on, with the exact rate of thinning controlled by the level-multiplier parameter, usually called mL, that governs the random layer-assignment process. The practical result is a hierarchy shaped like a narrowing pyramid, with the base holding everything and each successive layer above it holding dramatically less.

How does an upper layer’s connectivity differ from the base layer’s, beyond simply having fewer nodes?

Because far fewer candidates are available at an upper layer, the neighbor-selection heuristic run at that level ends up choosing connections that, on average, span considerably larger distances in the vector space than the connections a node forms in the denser base layer. This isn’t a deliberate, separately configured behavior — it’s a natural consequence of there simply being fewer nearby options to connect to at a sparse layer, which pushes even a distance-favoring selection process toward candidates that would be considered comparatively far away by base-layer standards. The result is that upper-layer edges function as long-range shortcuts, letting a traversal move across large swaths of the embedding space in a single hop, in stark contrast to the shorter, more local connections that dominate the base layer.

This difference in connection character is exactly why the two kinds of layers get searched with different strategies. The base layer’s short, local connections support a careful, thorough beam search well suited to pinning down exact nearest neighbors within an already-identified neighborhood. An upper layer’s long, sparse connections support a much simpler and faster greedy descent, since the goal there isn’t precision — it’s covering distance efficiently to arrive at a good starting point for the layer below.

What does a search actually do while it’s moving through the upper layers?

A search entering an upper layer, whether at the very top of the hierarchy via the entry point or after descending from an even higher layer, generally tracks only a single current-best candidate rather than maintaining a full ranked result set — since the upper layers’ only job is to hand the search off to a good starting position in the layer below, there’s no need for the heavier bookkeeping the base layer’s dual-queue structure requires. The search repeatedly checks the current node’s neighbors within that specific layer, moves to whichever neighbor looks closest to the query, and continues until no neighbor offers an improvement, at which point that final best node becomes the starting point for an identical process one layer further down. This lightweight, single-best-candidate strategy is deliberately much cheaper per step than the base layer’s fuller search, which matters because a search typically passes through several upper layers on its way down, and keeping each of those intermediate steps fast is part of what keeps HNSW’s overall query cost low.

Having covered what makes the upper layers structurally sparser and functionally different from the base layer, the base-layer glossary page is worth reading directly alongside this one for the fullest possible contrast between the two roles within the hierarchy. From there, the greedy-navigation and level-multiplier glossary pages go deeper into the specific search strategy and the random process that together determine exactly how sparse each upper layer actually ends up being.