How does an HNSW index search its layers to find nearest neighbours?

## What the index is for Exact nearest-neighbour search over an embedding collection means comparing the query with every stored vector. That cost is linear in the number of vectors and becomes untenable long before a catalogue reaches tens of millions of rows. An approximate nearest-neighbour (ANN) index accepts a small probability of missing a true neighbour in exchange for search cost that grows far more slowly with corpus size. HNSW — Hierarchical Navigable Small World — is the graph-based member of that family, and it is the default index in most vector stores because it gives high recall at low latency without a training pass and while accepting new vectors one at a time. ## A proximity graph, and why a plain one is not enough The base idea is a graph: each stored vector is a node, and edges connect vectors that are near one another. Searching such a graph is a walk rather than a scan. Start at some node, measure the query against the current node's neighbours, step to whichever is closest, and repeat. This is greedy hill-climbing on distance, and it visits only a tiny fraction of the nodes. A purely local proximity graph fails in two ways. If every edge is short, a query starting far away needs an enormous number of hops to cross the space. And a greedy walk can arrive at a node where no neighbour is closer to the query, yet the true nearest neighbour sits elsewhere — a local minimum. The "navigable small world" property is the fix: mix in some long-range edges so the graph has short average path length while retaining local clustering, exactly the property that makes social networks navigable in few hops. ## The layer hierarchy HNSW gets its long-range structure from layers. When a vector is inserted, it is assigned a maximum layer drawn from an exponentially decaying random distribution: nearly all vectors stop at layer 0, a small fraction also appear in layer 1, a much smaller fraction in layer 2, and so on. Layer 0 therefore contains every vector, and each layer above is a sparse random sample of the one below. Because the upper layers hold so few nodes, their edges connect points that are far apart in the embedding space. The structure is best understood as a skip list generalised to a metric space: the top layers let you cross the space in long jumps, the lower layers refine position with short ones. The randomised level assignment matters — it needs no global view of the data, so insertion stays a local operation and the index can grow incrementally. ## Greedy descent, then beam search A query proceeds in two phases. **Descent.** Start at the fixed entry point in the topmost non-empty layer with a candidate list of size one. Greedily hop to closer neighbours until the current node has no neighbour closer to the query. That node becomes the entry point for the layer below, and the same greedy walk repeats there. Each layer down has more nodes and shorter edges, so the walk zooms in. **Beam search.** At layer 0 the algorithm widens. It runs a best-first search with a dynamic candidate list of size `ef`, popping the closest unvisited candidate, expanding its neighbours, keeping a visited set so no node is scored twice, and maintaining the `ef` best results found so far. It terminates when the closest unexplored candidate is farther than the worst of the current best set — at that point no unexplored path can improve the answer within the beam. The best k of that list is the result. The beam is what turns a fragile greedy walk into a reliable one: with `ef` parallel candidate paths, a single dead end no longer ends the search. `ef` must be at least k, and raising it trades latency for recall. ## Why it is approximate, and what that costs Nothing in the procedure proves the true nearest neighbour was reached. The walk explores a small connected region of the graph, and the true neighbour can be unreachable from that region within the beam budget. In practice a well-built HNSW graph reaches recall in the high nineties at a fraction of the work of an exhaustive scan, and the shortfall is measured empirically against a brute-force ground truth rather than derived. The search cost grows roughly logarithmically with corpus size — the layer hierarchy is exactly the mechanism that keeps hop count from scaling with n. The price is paid elsewhere: the graph edges must be resident in memory for random-access traversal, and the graph has to be built before any of this works. ## What interviewers listen for The strong answer names the two distinct phases — greedy single-candidate descent through the layers, then widened beam search at layer 0 — and explains why the hierarchy exists at all (long-range navigation) rather than reciting "it is like a skip list" with no mechanism behind it. Saying plainly that the result is approximate, and that the beam width is the recall lever, separates someone who has tuned an index from someone who has read its README.