HNSW: Hierarchical Navigable Small World

Exact nearest-neighbor search scans every vector — O(N), hopeless at scale. HNSW replaces the scan with navigation: it lays the vectors out as a layered proximity graph and walks toward the query, touching a logarithmic fraction of the data. It is the default in-memory index in FAISS, hnswlib, Qdrant, Weaviate, and pgvector.

Interactive HNSW explorer

The explorer below is real: a true HNSW graph built over GloVe word vectors, with the search — greedy descent through the upper layers, then an ef-wide beam at the base — run live, counting actual distance computations.

The layer lottery

HNSW stacks several proximity graphs. Every vector lives on layer 0; each higher layer keeps an exponentially thinning random sample. On insertion a node draws its top level from

which makes the probability of reaching level \ell decay by a factor of M per layer:

So with M links per node the layers thin roughly ×M each step — in the explorer above, ~280 → ~70 → ~18 → a handful. The sparse upper layers are an express network; the dense base is where the precise neighbors live.

Small world: navigate, don't scan

The graph is navigable — greedy routing actually reaches the target — because each node mixes short local links with the occasional long-range one, giving the small-world property that the expected path length grows only logarithmically:

A query starts at the single top-layer entry point and, at each layer, hops to whichever neighbor is closest to the query until none is closer, then drops down a layer. A few hops across the express layers land it in the right neighborhood; the descent is the O(log N) part.

Search: descend, then beam

The upper layers use a width-1 greedy walk. Layer 0 switches to a beam of width ef: keep the ef best candidates seen so far, expand their neighbors, stop when none can improve the beam. ef is the one search-time dial — it is exactly the knob in the explorer.

• ef too small → the beam settles in one pocket of the graph and misses true neighbors (watch recall crater at low ef).
• ef larger → the beam escapes local minima and recall climbs toward 1.0, but distance computations rise with it.

import faiss
index = faiss.IndexHNSWFlat(d, M)   # M links/node; mL = 1/ln(M) sets the layers
index.hnsw.efConstruction = 200     # build-time beam — graph quality
index.add(vectors)                  # incremental, no global rebuild
index.hnsw.efSearch = 64            # query-time beam — the recall/speed dial
D, I = index.search(queries, k=10)

M and efConstruction fix the graph once at build time; efSearch tunes every query.

Parameters and complexity

The catch is memory: the graph links cost ~30–100 bytes per vector on top of the embedding, and the whole structure must live in RAM. That is the trade against a compressed index.

When to use HNSW (and when not to)

The honest decision boundary is RAM. If the vectors fit, start with HNSW — it owns the regime where recall ≥ 0.95 at single-digit-millisecond latency matters more than footprint, which is why every mature vector database ships it as the default in-memory index.

Reach for something else when:

• The corpus exceeds host RAM. HNSW degrades hard once it spills to disk — use IVF-PQ for billion-scale, or quantize before indexing.
• You delete or churn vectors constantly. HNSW supports deletes but recall drifts as the graph thins; plan periodic rebuilds.
• You can tolerate recall ≤ 0.85 for far less memory — coarse IVF or LSH is cheaper.
• You only have a few thousand vectors — brute-force IndexFlatIP is faster, simpler, and exact below ~100k.

If the vectors fit, index with HNSW; if they do not, walk the ANN comparison and pick the index whose memory profile matches your budget.

References

• Malkov & Yashunin. "Efficient and Robust Approximate Nearest Neighbor Search Using Hierarchical Navigable Small World Graphs" (TPAMI 2018)
• hnswlib · FAISS HNSW
• Weaviate: HNSW index

Related concepts