HNSW Index

HNSW (Hierarchical Navigable Small World) is the most widely used indexing algorithm for approximate nearest neighbor search in vector databases, underlying the default index type in systems like Qdrant, Weaviate, and Milvus, and available as an option in most others including Pinecone.

How It Works

HNSW builds a multi-layer graph structure where each vector is a node, and nodes are connected to their approximate nearest neighbors. The top layer contains a sparse subset of nodes with long-range connections, allowing a search to quickly navigate across the vector space in large jumps; each layer below adds progressively more nodes and shorter, more local connections, refining the search until the bottom layer — which contains every vector — is reached. A search starts at the sparse top layer, greedily moves toward the query vector, then descends layer by layer, narrowing in on the true nearest neighbors with increasing precision at each level.

Why It’s Fast

This hierarchical structure gives HNSW search time that scales logarithmically with the number of vectors in the index, rather than linearly as a brute-force comparison against every vector would require — this is what makes searching an index of tens of millions of vectors take milliseconds rather than seconds.

The Tradeoff

HNSW’s speed comes at the cost of memory: the graph structure itself, with its multiple layers of connections, requires meaningfully more memory than the raw vectors alone — often 1.5-2x the size of the raw embedding data. It’s also an approximate method, meaning it can occasionally miss the true nearest neighbor in exchange for its speed, though in practice its recall (the fraction of true nearest neighbors it actually finds) is very high with properly tuned parameters, which is why it’s become the default choice despite the memory overhead.

Tuning HNSW Parameters

HNSW’s behavior is controlled by a few key parameters: M (the number of connections each node maintains per layer, where higher values improve recall at the cost of more memory and slower index construction), and ef_search (how many candidate nodes are considered during a query, where higher values improve recall at the cost of query latency). Most vector databases expose these as tunable settings rather than fixing them, letting teams trade off recall, memory, and latency against their specific application’s requirements — a recommendation engine tolerant of occasionally missing a marginally relevant result might favor speed, while a legal or medical search application might prioritize recall even at higher latency and memory cost.