Inside Vector Databases: Understanding HNSW and IVF Indexes

As the adoption of semantic search and LLMs accelerates, Vector Databases have become a critical piece of infrastructure. Unlike traditional relational databases that query for exact keyword matches, vector databases perform similarity searches in high-dimensional space. To do this efficiently across millions or billions of embeddings, they rely on Approximate Nearest Neighbor (ANN) indexing algorithms, primarily Inverted File Index (IVF) and Hierarchical Navigable Small World (HNSW).

A naive approach to vector search is K-Nearest Neighbors (KNN), which calculates the distance (e.g., cosine similarity) between the query vector and every single vector in the database. While 100% accurate, this exhaustive search has O(N) time complexity and is unscalable for production workloads. ANN algorithms trade a small amount of accuracy for massive gains in speed.

The Inverted File Index (IVF) algorithm works by clustering the vector space. During indexing, it uses k-means clustering to divide the database into multiple regions, or "Voronoi cells," each defined by a centroid. When a query is received, the system first calculates the distance to the centroids to identify the closest clusters. It then only searches for nearest neighbors within those specific clusters. This drastically reduces the search space, though it risks missing a close neighbor that happens to lie just across the boundary of an adjacent cluster.

HNSW is currently the most popular and performant algorithm. It constructs a multi-layered graph. The bottom layer contains all the vectors, densely connected. Higher layers contain exponentially fewer vectors, acting as "expressways." A search begins at the top, sparse layer, quickly navigating toward the general vicinity of the query vector. As it drops down through the layers, the search becomes more localized and precise. This hierarchical routing is highly analogous to how skip lists operate in traditional computer science. HNSW offers exceptional query speeds and high recall, though it requires significant memory overhead to store the complex graph structures.

References:

1. Pinecone Learn: Hierarchical Navigable Small World (HNSW) - https://www.pinecone.io/learn/series/faiss/hnsw/
2. Milvus Blog: Vector Indexing Algorithms Explained - https://milvus.io/blog/deep-dive-1-milvus-architecture-overview.md