What is the HNSW hierarchy?
The HNSW hierarchy is the complete stack of layers that together make up an HNSW index — from the single, sparsely populated topmost layer down through progressively denser intermediate layers, ending at the base layer containing every vector in the dataset. Where a single HNSW layer, covered on its own glossary page, describes one level of this structure in isolation, the hierarchy is the whole assembled structure viewed as one system, and it’s this overall shape, not any individual layer on its own, that gives HNSW its characteristic search efficiency.
What determines how many layers a given HNSW hierarchy actually ends up with?
The number of layers in a hierarchy isn’t fixed in advance — it emerges naturally from the random layer-assignment process applied to every vector as it’s inserted, combined with how many vectors the dataset actually contains. Because each layer above the base one is populated by an exponentially shrinking fraction of the dataset, a larger dataset tends to produce a taller hierarchy, since there’s a larger pool of vectors from which the random process can produce at least a few that reach unusually high layers, even though the probability of any single vector reaching a high layer stays the same regardless of dataset size. A small dataset with only a few hundred vectors might end up with a hierarchy just two or three layers tall, while a dataset with hundreds of millions of vectors might naturally develop six, seven, or more layers, purely as a statistical consequence of having so many more chances for the random assignment process to produce a handful of unusually high-layer outliers.
This means the hierarchy’s height isn’t something that gets configured directly the way M or efConstruction do — it’s an emergent property that falls out of the level-assignment probability parameter, usually called mL, combined with the sheer number of insertions the index actually processes, which is worth understanding clearly since it explains why hierarchy height isn’t listed among the parameters someone tunes directly when configuring an HNSW index.
Why does the hierarchy need multiple layers rather than just one well-built proximity graph?
A single flat proximity graph, however carefully constructed, faces a structural limitation that the hierarchy exists specifically to address: a search starting at an arbitrary entry point within one graph has to traverse enough of that graph‘s edges to reach the neighborhood containing the true answer, and the number of hops required to cross a large, densely populated graph doesn’t shrink just because the graph happens to be well connected. The hierarchy sidesteps this by concentrating the “getting into roughly the right neighborhood” work into the sparse upper layers, where a search naturally covers large distances quickly simply because there are so few nodes and correspondingly long-range connections to work with, and reserving the more expensive, thorough “finding the actual best candidates” work for the dense base layer, where the search is already starting from a position close to the true answer rather than from an arbitrary point far away from it.
This division of labor across the hierarchy is what gives HNSW’s search its favorable scaling behavior — theoretical analysis of HNSW-like structures suggests search cost grows only logarithmically with dataset size under reasonable assumptions, a claim covered in more depth on the logarithmic-search-claim glossary page, and that claim depends directly on the hierarchy’s structure doing exactly this kind of coarse-to-fine narrowing rather than relying on a single flat graph to handle the entire search on its own.
How does the hierarchy actually get traversed during a single query, tying the individual layers together into one coherent search?
A query enters the hierarchy at its single, designated entry point, sitting in whatever the current topmost non-empty layer happens to be. The search performs a simple, greedy descent within that layer, generally tracking only the single best point found so far rather than maintaining a full ranked set of candidates, since the goal at this stage is just to find a good starting position for the next layer down rather than to produce final results. Once that greedy search in the current layer can’t improve any further, the best point it found becomes the entry point for an identical greedy search in the layer directly below, using that layer’s own distinct set of connections. This repeats, one layer at a time, until the search reaches the base layer, where the strategy shifts from simple greedy descent to the fuller, dual-queue-based search covered elsewhere in this documentation, exploring a wider beam of candidates to actually produce the k final results the query asked for.
Every layer above the base one exists purely to hand off a good starting position to the layer below it — none of the intermediate layers directly contribute to the final result set at all, which is a detail that sometimes surprises people encountering HNSW’s mechanics for the first time, since it means most of the hierarchy’s layers do no more work than narrowing down where the real search should eventually begin.
Having covered how the full hierarchy fits together as a single system, the entry-point-in-HNSW and base-layer glossary pages are the natural next stop, since they cover the two structural endpoints — where a search starts and where it finishes — that this page connects. From there, the expected-hierarchy-height glossary page, under complexity and theory specific to HNSW, goes deeper into the mathematical reasoning behind why the hierarchy’s height behaves the way it does as a dataset grows.