HNSW

Hierarchical Navigable Small World: a multi-layer proximity graph for fast approximate nearest-neighbor (ANN) search over vectors. Every inserted point is randomly assigned to a set of "highway" layers using the same coin-flip trick as a Skip List, which is what makes this a genuinely randomized structure rather than just an approximation heuristic.

How it works

Think of it as a Skip List built out of a proximity graph instead of a sorted linked list. Each point is added to layer 0 (the "ground floor", containing every point) and, with probability p per extra layer (a repeated coin flip, exactly like a Skip List's express lanes), also to layers 1, 2, 3, .... Most points only exist at layer 0; a lucky few climb several layers and become long-range shortcuts.

insert() descends greedily from the single global entry point (always the node at the current top layer) down to the new point's own top layer, keeping only the single closest node found per layer. From there down to layer 0, it does a wider search (candidate list size efConstruction), connects the new point to its M closest neighbors at each layer, and (since every node has a degree cap) prunes whichever existing neighbor now has too many edges back down to its own M closest.

search() does the same greedy single-best-neighbor descent from the top layer down to layer 1, then widens to keep ef candidates at layer 0 and returns the k closest among them. Skipping straight to a good starting point via the upper layers is what gives HNSW roughly logarithmic search time instead of having to crawl the full graph from an arbitrary point.

Interactive demo

Click anywhere to insert your first point
Points0
Top layer-1
Entry point—
Recall vs. brute force—
No points yet. Insert some to build the graph.
No operations yet. Try adding an item above.

API surface

OperationDescriptionComplexity
new HNSW({ M?, efConstruction?, efSearch?, levelProbability? })Empty index. M caps edges/layer, efConstruction/efSearch trade recall for speed.O(1)
insert(id, vector): level, eventsRandomly assigns a top layer (coin flip), greedily descends to it, then connects to M nearest neighbors per layer down to 0.O(log n) expected
search(query, k, ef?): results, pathGreedily descends to layer 1, then widens to ef candidates at layer 0 and returns the k closest.O(log n) expected
getSnapshot(): layers[]Every layer's nodes and deduplicated edges, top layer first, for visualization.O(n)
bruteForceKnn(points, query, k)Exhaustive exact k-NN, used to measure HNSW's recall against ground truth.O(n log n)

References

Original papers

Library implementations

Real-world use cases