HNSW Index: Architecture for Fast Vector Search › HNSW Index

In the previous chapter, we explored vector similarity search and the fundamental challenge it presents: given a query vector, find the most similar vectors in a collection. The brute-force approach, computing distances between the query and every vector in the database, delivers perfect accuracy but scales linearly with the number of vectors. For a million-document corpus with 768-dimensional embeddings, every single query requires a million high-dimensional distance computations. For ten million documents, it requires ten million. This quickly becomes impractical for the real-time retrieval that RAG systems demand.

Approximate nearest neighbor (ANN) search addresses this scalability issue. Rather than guaranteeing exact nearest neighbors, ANN algorithms trade a small amount of accuracy for dramatic speed improvements, often returning results in milliseconds even across billion-vector collections. Among the many ANN algorithms developed over the years, one has emerged as the dominant choice for vector search in production systems: Hierarchical Navigable Small World graphs, or HNSW.

HNSW, introduced by Yuri Malkov and Dmitry Yashunin in 2016, combines two powerful ideas: the "small world" property of certain graphs (where any node can reach any other node in surprisingly few hops) and a hierarchical layering scheme inspired by skip lists. The result is an index structure that supports both fast construction and fast search, with tunable parameters that let you precisely control the tradeoff between speed and recall. HNSW powers the vector search behind libraries like FAISS, Hnswlib, and vector databases such as Pinecone, Weaviate, Qdrant, and Milvus.

Before HNSW, approximate nearest neighbor search was fragmented across several methods. Tree-based methods like KD-trees work well in low dimensions but collapse under the curse of dimensionality: with 100+ dimensional vectors, every leaf becomes nearly equidistant from any query. Locality-sensitive hashing (LSH) offers provable guarantees but typically requires many hash tables to achieve good recall, leading to substantial memory overhead and tuning complexity. Quantization methods like IVF (Inverted File Index) partition the space into clusters and only search nearby partitions, but their recall degrades on datasets with complex distributions. Graph-based methods were known to have promise but lacked a principled way to maintain efficient routing as the graph grew. HNSW solved all of these problems simultaneously, and the elegance of its solution is worth understanding in depth.