HNSW

HNSW (Hierarchical Navigable Small World) is the dominant graph-based approximate nearest neighbor (ANN) algorithm for in-memory vector search. Proposed by Malkov and Yashunin in 2016, it has become the de facto standard used by FAISS, hnswlib, Qdrant, Weaviate, Milvus, pgvector, and essentially every production vector database in 2026.

Mechanically, HNSW builds a multi-layer proximity graph. Higher layers contain fewer nodes with long-range connections; lower layers contain more nodes with short-range ones. Search descends the layers from the top, greedy-walking toward the query’s neighborhood, narrowing in until the bottom layer where it performs a wider beam search. Two parameters dominate behavior: M (graph density — max connections per node, typically 16–48) and ef (beam width — trades recall for latency).

Performance characteristics:

• Memory-resident is the happy path. HNSW assumes the entire graph fits in DRAM; when it exceeds buffer cache, latency degrades non-linearly.
• Pointer-chasing on descent — each hop’s next address depends on the current node, which defeats the hardware prefetcher and leaves DRAM latency exposed. This is why HNSW query time is often memory-bound, not compute-bound.
• Scales non-linearly with dimension and corpus size — the “vector hangover” phenomenon comes from graph metadata overhead growing faster than naive estimates.

Trade-offs and alternatives: IVF flat (faster build, lower recall at same ef), IVF-PQ (smaller memory with quantization), DiskANN/SPANN (disk-resident when DRAM isn’t an option), hybrid HNSW-IF (Vespa’s billion-scale approach). The right choice depends on recall target, latency SLO, and dataset size — not the algorithm alone.