HNSW Index: Architecture for Fast Vector Search › Summary

HNSW (Hierarchical Navigable Small World) is a graph-based approximate nearest neighbor algorithm that enables fast vector search by combining two key ideas:

• Navigable Small World graphs provide a structure where greedy routing efficiently finds nearby nodes using only local information. Dense local connections enable precise search, while long-range connections enable fast traversal across the space. The key challenge with a flat NSW graph is that greedy search can get trapped in local minima, especially as the graph grows.

• Hierarchical layering (inspired by skip lists) separates coarse navigation from fine-grained search. Upper layers contain sparse subsets of nodes with naturally long-range connections. This provides the global navigation that flat NSW graphs lack. The bottom layer contains all nodes with dense short-range connections for precise final search.

The algorithm's behavior is controlled by three parameters:

• $M$: connections per node (typically 16). Controls the density of the graph, affecting recall, memory, and speed.
• ef_construction: beam width during index building (typically 200). Higher values produce a better graph at the cost of slower construction. This is a one-time cost.
• ef_search: beam width during search (tunable at query time). Directly controls the speed-recall tradeoff without requiring a rebuild.

Search works in two phases: greedy descent through upper layers (fast, coarse navigation), then beam search on layer 0 (thorough, precise retrieval). This structure achieves $O(\log n)$ search complexity, making it practical for millions or billions of vectors. The neighbor selection diversity heuristic ensures that each node's connections cover multiple directions in the vector space, preventing local minima and improving navigability across the full graph.

HNSW's main limitations are its memory requirements (the full graph must fit in RAM) and the difficulty of handling deletions. For collections too large to fit in memory, partition-based indices like IVF and compression techniques like Product Quantization offer complementary solutions. In practice, many production systems combine these approaches, using HNSW as the search graph within each partition of a larger index. For most RAG applications with collections up to hundreds of millions of vectors, an in-memory HNSW index offers strong recall at low latency without excessive operational complexity.