Aliases: HNSW, ANN Search
Hierarchical Navigable Small World (HNSW)
Hierarchical Navigable Small World — the graph-based index behind most vector databases; logarithmic-feeling search across millions of embeddings, paid for in RAM.
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)
Historical figures and technical concepts for informational purposes only. Not technical, professional, legal, or financial advice. Sources: Official Documentation.