Approximate nearest-neighbour search, from scratch

HNSW Visualized

A Hierarchical Navigable Small World index built in ~240 lines of dependency-free JavaScript (hnsw.mjs). Vectors live in ℝd; the canvas is a fixed random projection down to 2-D. The scorecard is a 40-query held-out evaluation — HNSW's top-k against a brute-force scan — recomputed on every change, so the recall you trade for the speed-up is measured, not asserted. Push dimensions up, or lean out the graph with M / efConstruction, and watch recall fall; widen efSearch to buy it back at the cost of more distance calls. Click the canvas to aim the query the animation traces.

2-D random projection of ℝd · click to aim the animated query · upper-layer nodes are brighter

Index

400
16
8
32

Query

16
10

View layer

upper-layer node
layer-0 node
returned k-NN
true k-NN
Graph
–
mean recall@k · 40 held-out queries
–
Distance calls per query
–
Speed-up
–

What you're looking at

  1. Layers. On insert, each node draws a random level from an exponential distribution (floor(-ln(U) · mL)). Most nodes live only on layer 0; a few reach higher, and the highest is the entry point. Use the buttons to view one layer's edges at a time.
  2. Building an edge. For each layer from the node's top down to 0, a beam search of width efConstruction finds candidates, then a diversity heuristic keeps up to M of them — preferring neighbours that are closer to the new node than to each other, which keeps the graph navigable instead of clumped.
  3. Searching. Start at the entry point on the top layer, greedily hop to the closest neighbour until you can't get closer, then drop a layer and repeat. At layer 0 the beam widens to efSearch. Cyan rings trace the visit order.
  4. The trade. Brute force does one distance calculation per point and is always exact. HNSW touches a small fraction of the points; recall@k is how much of the true top-k it still recovered. Raise efSearch to buy back recall at the cost of more work.
  5. What moves recall. Two things. Dimensionality: as dimensions rises the greedy walk has a harder time routing to the true neighbourhood, so recall drops at a fixed efSearch. Graph quality: M and efConstruction set how well-connected the graph is — a generous graph (M ≈ 16, efConstruction ≈ 64) is near-exact at a modest efSearch; a lean one needs a much wider beam to catch up. The canvas is only a shadow of ℝd — every distance, every score and the recall run on the real vectors, not the projection.

The same BM25 / RRF / cosine / metrics code, written the same way, powers Retrieval Playground and MELAI Engineering Lab.