What is the core idea behind HNSW’s layered graph?

The core idea behind HNSW’s layered graph is to stop asking a single flat graph to handle both long-range navigation and short-range refinement with the same set of edges, and instead build several graphs stacked on top of each other — sparse at the top, dense at the bottom — so that each layer only has to do one of those two jobs well.

How does stacking several graphs on top of each other fix NSW’s bottleneck?

The previous page traced NSW’s slowdown to a specific mechanism: hub nodes accumulate connections as the graph grows, and because a greedy search has to pass through those same hubs again and again, both the number of hops and the degree of the nodes along the search path grow with the size of the network, compounding into a cost worse than a plain logarithm. HNSW addresses this directly by separating connections according to how far they reach. The bottom layer contains every vector in the dataset, connected by short, local edges. Each layer above it contains a smaller, sparser subset of those same vectors, connected by increasingly long-range edges. A search no longer has to evaluate every connection a hub node happens to have accumulated — at any given layer, it only ever has to consider the bounded number of edges that belong to that layer, regardless of how large the overall dataset has grown, which is what restores genuinely logarithmic scaling instead of the polylogarithmic scaling a single flat graph produces.

Why does the skip-list analogy actually hold, rather than just resemble it?

This layered structure is frequently compared to a skip list, a data structure that speeds up search through a sorted list by adding extra “express lane” pointers that skip over many elements at once, with fewer and fewer of those pointers surviving into each higher lane. The comparison is more than a loose analogy. Collapse HNSW’s construction down to a single dimension, where “nearby” simply means “adjacent on a number line,” and the neighbor-selection process used to decide which vectors get connected reduces exactly to a sorted linked list with occasional long-range shortcuts — which is a skip list in every meaningful sense, not merely something that behaves similarly to one. The multi-dimensional graph case can be understood as the same fundamental idea generalized from a one-dimensional ordering to the much richer geometric relationships that exist between vectors in many dimensions.

How is it decided which layer each vector belongs to?

Every vector in the dataset exists in the bottom layer by definition, since that layer needs full coverage to guarantee a complete answer to any query. Whether a given vector also appears in the layers above it is decided randomly at the moment it’s inserted, using a probability that decreases exponentially with each additional layer — a coin that gets less and less likely to come up heads the higher it’s flipped, in effect. This is precisely the mechanism that keeps the upper layers sparse without needing any global coordination or rebalancing: most vectors are assigned to the bottom layer only, a smaller fraction reach one layer up, a smaller fraction still reach two layers up, and so on, producing exactly the pyramid shape — wide at the bottom, narrow at the top — that lets the upper layers act as a fast, coarse map of the dataset.

What is an entry point, and why does the graph need one?

Every search has to start somewhere, and HNSW maintains a single designated entry point at the topmost occupied layer for exactly this purpose — the highest layer that currently has any vectors in it at all, since a search descending through empty layers would waste effort finding nothing to connect to. As new vectors are inserted and occasionally land in a layer higher than any vector seen before, the entry point moves up to match, keeping the search’s starting position anchored at whatever the current top of the pyramid happens to be. This one designated starting point, combined with the exponentially sparser layers above the base, is what turns a single flat proximity graph into a structure that can be searched efficiently at any scale.

With the overall shape of the structure established, the next section moves from this conceptual picture to the actual mechanics of using it — how a query descends through these layers step by step, and separately, how a new vector gets inserted into a graph that’s already built. Readers who want the precise mathematics behind the exponential layer-assignment probability, rather than the intuitive version given here, will find it worked through on the appendix page covering this site’s mathematical notation.