What is upper-layer greedy descent?
Upper-layer greedy descent is the phase of a query-time HNSW search that runs through every layer above the base layer — starting from the global entry point and moving down one layer at a time, using a simple greedy strategy at each level to find a good starting position for the layer below, before the fuller, more careful search at the base layer takes over. It’s the query-time counterpart to the descend-to-insertion-level step used during construction, and understanding it clearly shows exactly how HNSW turns its layered hierarchy into a practical speed advantage for every single search, not just during index building.
How does the actual descent through these upper layers work, step by step?
A query begins at the entry point, sitting in whatever the current topmost non-empty layer of the hierarchy happens to be, and performs a greedy traversal within that single layer: check the current node’s neighbors at this layer, move to whichever one looks closest to the query, and repeat until no neighbor offers any further improvement. Once that greedy traversal in the current layer has settled on a best point, that point becomes the starting position for an identical greedy traversal one layer down, using that lower layer’s own distinct set of connections. This process repeats, one layer at a time, until the descent reaches the base layer, at which point the search strategy changes entirely, switching to the wider, dual-queue-based best-first search that actually produces the query’s final results.
At every step of this descent, the search tracks only a single current-best node and its distance to the query — there’s no candidate queue, no result queue, and no attempt to maintain multiple competing options simultaneously, which is exactly the greedy-navigation strategy described on its own glossary page, applied here specifically to the upper portion of a query’s full journey through the hierarchy.
Why is this simple, single-point strategy actually sufficient for the upper layers, when the base layer needs something considerably more elaborate?
The upper layers’ entire purpose is narrowing down roughly which neighborhood of the vector space contains the query’s answer, not identifying the final, precise set of nearest neighbors — that more exacting work is reserved for the base layer, where every vector in the dataset is actually present and where the search’s stopping criterion and result-tracking machinery genuinely need to matter. Because the upper layers only need to hand off a reasonably good starting position, rather than a provably optimal one, the cheaper single-best-candidate strategy is an entirely appropriate match for the job — spending the extra computational effort of maintaining a full candidate queue and result queue at a sparse layer whose only role is a rough hand-off would add cost without meaningfully improving the eventual outcome, since the base layer’s more careful search will refine whatever approximate starting position the upper-layer descent provides anyway.
This division of labor is exactly why HNSW‘s overall query cost stays low even though descending through several layers technically means running several separate traversals in sequence — each individual upper-layer traversal is cheap precisely because it doesn’t need to do more than find one good point before moving on.
How many layers does a typical query actually descend through during this phase, and does that number vary much?
The number of layers a query passes through during upper-layer greedy descent is simply however many layers currently exist above the base layer in that specific index’s hierarchy — a quantity determined entirely by the level-assignment process applied during construction, not by anything about the specific query being run. Since higher layers are exponentially rarer by design, most real HNSW indexes end up with a modest number of layers even for very large datasets — often somewhere in the range of a handful, growing only slowly as the dataset itself grows much larger, which is exactly the logarithmic-scaling behavior that gives HNSW its favorable overall search cost. Every query descends through the same number of upper layers for a given index, regardless of what that particular query is actually looking for, since the hierarchy’s height is a fixed structural property of the built index rather than something that varies from query to query.
What happens if the greedy descent at some upper layer gets stuck at a poor local minimum, before ever reaching the base layer?
Because upper-layer greedy descent shares the same fundamental limitation as greedy navigation generally — no lookahead, no backtracking, and the possibility of stopping at a node whose neighbors all happen to look farther from the query than the node itself — a poor outcome at an upper layer can hand the base-layer search a worse-than-ideal starting position. In practice this risk is usually modest, since the upper layers’ long-range connections tend to make severe local minima less likely there than they might be in a denser, more locally-structured layer, but it isn’t eliminated entirely, and it’s part of the broader set of factors, alongside local intrinsic dimensionality and query-database distribution shift, that contribute to why some individual queries turn out harder for HNSW to answer well than others.
Having covered how upper-layer greedy descent narrows a query down to roughly the right neighborhood before handing off to the base layer, the base-layer-search and greedy-navigation glossary pages are the natural next stop, since they cover exactly what happens once this descent phase concludes. From there, the local-minimum-in-graph-search glossary page, under recall and query difficulty, looks more closely at the specific failure mode this descent phase can occasionally run into.