Vector Search Simulator: Walk an HNSW Graph One Hop at a Time

Builds a real HNSW index over seeded two-dimensional points and steps through the greedy walk, counting distance computations and measuring recall against a brute-force scan.

efSearch — the one controlHow many candidates the search keeps alive at once — the only quality knob at query time. Values below k = 5 have no effect, because you cannot return 5 results from a beam narrower than 5.

ef 4

Neighbours wanted (k)Recall below is measured at this k.

k = 5

Points in the indexClustered, generated from the seed.

160

M — links per nodeGraph degree, fixed at build time.

M 2

Query x0 is the left edge.

0.62

Query y0 is the bottom edge.

0.38

SeedSame seed, same points and same graph, forever.

Walk the search: 28 of 28 nodes visitedCurrently at node 34, distance 0.064 from the query.

Each step is one node the search computed a distance for. That count is the entire cost of the query.

Recall@5

60%

The graph found 3 of the 5 genuinely nearest points using 28 distance computations. A brute-force scan is exactly 160 and always gets 5 of 5. Drag efSearch and watch both numbers move together — that trade is the whole reason approximate search exists.

✚ your query● returned by the graph● visited on the way○ genuinely one of the 5 nearest

Points indexed: 160
Layers in the graph: 5
Entry point: node 5 at layer 4
Links per node (M): 2
Edges at layer 0: 244
Distance computations descending the upper layers: 12
Distance computations at layer 0: 16
Distance computations, total: 28
Brute-force cost for the same query: 160
Work saved against brute force: 82.5%
Recall@5: 3 of 5

Where these numbers come from: Everything here is computed, not depicted. The points are pseudo-random from the seed in the URL, the graph is built by the HNSW insertion procedure, the walk is the search that graph actually performs, and recall is measured against a brute-force scan of the same points run on the same page. There is no model and no dataset — the vectors are two-dimensional precisely so the geometry can be drawn honestly rather than projected and hand-waved.

What this assumes: Two dimensions and Euclidean distance, so that the picture is the space rather than a projection of it. Level assignment is the standard exponential rule, ⌊−ln(u)/ln M⌋, with the level capped at four, seeded so a link rebuilds the same graph. Neighbour selection is the paper's diversity heuristic with pruned connections kept, and layer 0 is allowed twice the degree of the upper layers — both matter on clustered points like these, because the obvious "keep the M nearest" rule fills every node's slots with its own cluster and leaves the graph in disconnected pieces. efConstruction is max(efSearch, 2M, 16), so changing efSearch rebuilds the index; on a real system it is set once at build time and only efSearch moves. "Distance computations" counts each node the search evaluated once — the real measure of query cost, since everything else in the loop is pointer-chasing. Real indexes at a million vectors behave the same way but with more layers, and their recall at a given ef is lower than a 200-point toy will show you.

What efSearch buys, and what it costs

Vector search is not a lookup. There is no ordering on points in high dimensions and no index that can bracket a range, so every approximate method is a way of avoiding most of the comparisons rather than avoiding a scan entirely. HNSW's answer is a navigable graph: each point links to a handful of near ones, a few points also live in sparse upper layers that act as express lanes, and search is a greedy walk downhill from an entry point. The upper layers get you into the right neighbourhood in a few hops; layer 0 does the careful part.

Drag efSearch up from the left and watch the two numbers move at different rates. At a narrow beam the walk is close to purely greedy: it stops at the first point whose every neighbour is further from the query, even when a better one sits two hops away through a temporarily worse one. That local minimum is the failure the beam exists to escape, and it is what the missing entries in the recall figure are. Widening the beam keeps more candidates alive so the walk can pass through a worse node to reach a better one. On the settings this page opens with, recall reaches its ceiling around efSearch 8 at a cost of six extra distance computations — and everything above that costs linearly more while buying nothing at all. That is the shape of the curve on real indexes too, and finding where your own version of it flattens is the entire tuning exercise.

Two things this page cannot show you and you should not forget. The first is dimensionality: in 2D, nearest neighbours are easy and recall looks generous, while at 768 dimensions distances concentrate, the graph is harder to navigate and the same efSearch buys noticeably less. The second is that recall is measured against exact search, not against being right — a retrieval system with 95% recall can still be a bad retrieval system if the embeddings put the wrong things close together. Recall tells you whether your index is faithful to your embeddings. Whether your embeddings are faithful to your users is a different question, and a harder one.

Vector Search Simulator: Walk an HNSW Graph One Hop at a Time

What efSearch buys, and what it costs

The reasoning behind this

Related tools