Skip to main content

HNSW: Hierarchical Navigable Small World

How HNSW navigates a layered proximity graph to find nearest neighbors in logarithmic time — the default in-memory index of modern vector databases.

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.

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. Follow the guided steps, then switch to Explore and vary the query and ef to compare recall with search effort.

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

\ell = \big\lfloor -\ln(U)\cdot m_L \big\rfloor, \qquad m_L = \frac{1}{\ln M}

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

P(\text{level} \ge \ell) \;=\; e^{-\ell / m_L} \;=\; M^{-\ell}

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:

d_{\text{avg}} \;\propto\; \log N

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.
python
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

ParameterTypicalEffect
M16–32links per node; m_L = 1/\ln M sets layer thinning
efConstruction100–200build-time beam — higher = better graph, slower build
efSearch (ef)50–500query-time beam — the recall vs latency dial
OperationTimeSpace
BuildO(N \log N)O(M \cdot N)
SearchO(\log N)O(ef)
InsertO(\log N)O(M)

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.

IndexSearchMemoryRecallWhen
HNSWVery fastHighExcellentIn-RAM, low-latency, read-heavy
IVF-PQFastLowGoodBillion-scale, on a budget
LSHFastLowModerateStreaming, cheap

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

If you found this explanation helpful, consider sharing it with others.

Mastodon