HNSW Index

HNSW (Hierarchical Navigable Small World) is a graph-based approximate nearest-neighbor algorithm that organizes vectors into multiple layers of a navigable graph, so a search can hop toward the right neighborhood in roughly logarithmic time instead of scanning every vector.

It is the index most vector databases reach for by default, because it hits a rare sweet spot: high recall, low latency, and reasonable memory use, without the accuracy cliffs that plague simpler ANN methods.

How it works

HNSW builds several stacked graphs. The top layer is sparse, holding a small number of vectors connected to their nearest neighbors as long-range "highways." Each layer below is progressively denser, and the bottom layer contains every vector, densely interconnected with its true nearest neighbors. A search starts at the top layer's entry point, greedily walks toward the query vector using the sparse long-range edges, then drops down a layer once it stops improving, repeating until it reaches the bottom layer and does a fine-grained local search.

The construction and search behavior are tuned by two parameters: M, the number of edges each node keeps (typically 16-64 — more edges means better recall at the cost of memory), and ef_search, how many candidates the search keeps in its frontier at query time (higher means slower but more accurate). Both are the practical dials that trade recall against speed on a live system.

Why it matters

Brute-force nearest-neighbor search is exact but scales linearly with collection size — untenable once a collection reaches millions of vectors and needs sub-100-millisecond responses. HNSW's layered structure turns that linear scan into something close to logarithmic: the number of comparisons grows with the log of the collection size rather than the collection size itself, which is the only reason semantic search over tens of millions of documents can respond in real time. The cost is that HNSW is approximate — it can miss the true nearest neighbor occasionally in exchange for that speed, which is why recall@k, not just latency, has to be measured and tuned, not assumed.

A worked example

A collection of 1,000,000 vectors has log2(1,000,000) ≈ 19.9 — the theoretical depth HNSW's layers are built around. In practice, a query run with ef_search = 100 visits on the order of a few thousand candidate nodes to find its answer, versus 1,000,000 vector comparisons for a brute-force scan over the same collection — roughly a 10,000x reduction in comparisons for that ef_search setting, typically landing recall@10 in the mid-90s to high-90s percent range depending on how M and ef_search are tuned. Push ef_search higher and recall creeps closer to exact search's 100 percent, at the cost of visiting more nodes and adding latency back.

How miatz teaches it

Learners build a miniature HNSW graph by hand on paper — a dozen points, two layers — before ever running the real algorithm, walking a greedy search themselves so the "hop through highways, then search locally" behavior is felt rather than just read as an equation. Only then do they benchmark a real HNSW index against brute force on a full-size corpus.