HNSW: the graph that finds meaning

The Elasticsearch essays · April 2026

The vector database showed a query hopping across a web of neighbor links instead of measuring every distance. This essay is about that web: how it is built one insertion at a time, why it has layers, and the single dial that trades speed for certainty. Every figure below runs a real search over real points; nothing is canned.

1 · Layers: highways above streets

A graph of near neighbors has a flaw: if the query lands far from the entry point, the greedy walk crawls there in tiny local steps. The fix, and the H in HNSW (Hierarchical Navigable Small World), is to stack sparser copies of the graph on top. The top layer holds a handful of points with long links: highways. Each layer down is denser: avenues, then streets. Scrub the descent:

–

scrub to begin

–

vs 90 distances for a full scan

descent

Ninety points, three layers. The walk enters at the top, where a couple of long hops cross most of the space, then drops a layer, refines, drops again, and lands. Long distances are covered where links are long, precision happens where links are short. A point's height is decided by a biased coin at insertion: only a small, fixed fraction of each layer also lives on the next one up (about one in sixteen with Elasticsearch's default of 16 links per node; the figure exaggerates it so you can see the upper layers). So the highways stay sparse no matter how large the index grows, and the number of layers grows only with the logarithm of its size.

2 · Watching it build

The graph is never computed from the whole dataset at once; it accretes. Each arriving vector searches the existing graph for its nearest neighbors, exactly as a query would, then links to them. Two settings shape the result: m, how many links each node keeps, and ef_construction, how wide the search is when a vector arrives. Drag through the construction:

–

vectors inserted

–

points per layer (L0 · L1 · L2)

–

links kept · links dropped

insertions

The newest point is orange, with its fresh links; ringed points won the coin flip and also live on a higher layer. Each newcomer runs a real search on the graph built so far, then links to a diverse set of m neighbors: it skips a candidate when one it already chose is closer to that candidate, which is what keeps a few long links between groups instead of a tight knot inside one. When a node exceeds its cap (2m on the bottom layer), it re-selects and drops its least useful links: drag forward and watch links disappear. Raise m and the graph gets denser: better recall, more memory, slower inserts. Elasticsearch defaults to m = 16, with a construction beam of 100.

One thing the figure hides: Elasticsearch does not keep one graph for the whole index. Like everything else in Lucene, vectors live in immutable segments, and each segment carries its own small graph. A query walks every segment's graph and merges the results. When segments merge, their graphs have to be rebuilt into one, reusing the largest as a head start. That rebuild is where vector indexing spends much of its CPU, and why bulk loads are faster with fewer, larger segments.

3 · The honesty dial

The walk keeps a short list of the best candidates it has seen so far, and keeps exploring until nothing it could still visit would make that list better. The length of the list is the knob every vector deployment ends up tuning. The HNSW paper calls it ef; in Elasticsearch it is num_candidates on the kNN query, set per shard, at least k, 1.5×k by default and at most 10,000. Too small, and the walk can settle in the wrong neighborhood and miss true neighbors. Larger, and it explores more paths at more cost. This figure runs a real beam search over 240 clustered points, on a graph built the HNSW way, and checks it against the exact answer, live:

–

this query · found of the true 10

–

recall@10 · average of 60 queries

–

distances computed · vs 240 exact

num_candidates16

Green rings are the true ten nearest neighbors, found the slow way; blue dots are what the graph walk returns, with k fixed at 10. At 16 candidates the walk from the entry point settles into the wrong cluster and returns zero of the ten. Drag right: around 40 the beam is wide enough to cross over and finds seven of the ten. The last three sit behind links the graph never made, so no width recovers them: approximate search promises a good average, not every query. The average over 60 random queries tells that general story: most queries are easy, a few are traps, and each extra candidate buys a little recall for more distance computations. Real deployments trace this same curve with millions of points, and the answer is never "maximum": it is "just enough".

One honest footnote on defaults: HNSW is no longer the only index Elasticsearch builds for vectors. Since 9.4, where the license allows it (an Enterprise subscription), new dense_vector fields default to bbq_disk, which groups vectors into clusters with a variant of k-means and searches only the closest clusters, instead of walking a graph. Without that license, the default is still an HNSW graph (bbq_hnsw from 384 dimensions, int8_hnsw below). Everything above is how that graph works.

Layers to cross space quickly, accretion instead of construction, one dial for the speed-certainty trade. What the walk actually compares, compressed vectors that keep comparisons honest at one bit per dimension, is back in The vector database; what the vectors mean is in Semantic search in practice.