Hierarchical Navigable Small World (HNSW)

What is HNSW?

HNSW is the approximate-nearest-neighbor index that made semantic search over millions of embeddings interactive. It builds a layered graph: sparse upper layers with long-range links for coarse navigation, dense lower layers for precision — a skip-list crossed with a small-world network. A query greedily hops from a top-layer entry point toward its target, descending layers as it homes in, touching a few hundred nodes instead of comparing against every vector. It’s the default index in pgvector, Qdrant, Weaviate, Milvus, and most managed vector stores.

The three knobs that matter

M (links per node) sets graph density: higher M, better recall, more memory. efConstruction controls build-time thoroughness: slower indexing, better graph. efSearch is the query-time candidate list: the runtime dial trading latency for recall. The practitioner move most teams miss: efSearch is per-query — run cheap low-recall search for autocomplete and expensive high-recall search for RAG on the same index.

The costs nobody advertises

HNSW is a RAM structure: vectors plus graph links live in memory, so M=16 on 10M×1536-dim float32 vectors means ~60 GB of vectors plus gigabytes of graph — that’s the managed-vector-DB bill explained. Deletions are its other weakness: removing nodes degrades graph connectivity, so heavy-churn workloads need periodic rebuilds or tombstone compaction, a maintenance reality vendor quickstarts omit.

What people get wrong

• Trusting default recall. ANN is approximate; measure recall@k against brute force on your data — defaults commonly sit at 0.9–0.95, and that missing 5% may be your best chunk.
• Benchmarking unfiltered, deploying filtered: metadata filters can force HNSW to traverse far more of the graph; filtered-query performance needs its own benchmark.
• Using HNSW at 50k vectors — brute force is exact, simpler, and fast enough below ~100k.

Primary source: Efficient and robust approximate nearest neighbor search using HNSW (Malkov & Yashunin, 2016)

Real-World Recall and Latency Numbers

In practical benchmarks, a well-tuned HNSW index can achieve recall rates above 95% (finding the true nearest neighbor or one of comparable quality in 95%+ of queries) while returning results from an index of tens of millions of vectors in single-digit milliseconds — a combination of speed and accuracy that would be impossible with a brute-force linear scan at that scale. This performance profile, combined with the fact that HNSW indexes can be updated incrementally (new vectors can be inserted without rebuilding the entire index from scratch, unlike some alternative index structures), is why it remains the default recommendation for most production vector search use cases that aren’t operating at the billion-vector-plus scale where memory-efficient alternatives like IVF-PQ become necessary instead.