HNSW Index: Architecture for Fast Vector Search › HNSW vs Other ANN Algorithms

To appreciate what HNSW achieves, it helps to understand the alternatives and why they fall short for high-dimensional text embeddings.

The traditional approach to nearest neighbor search uses space-partitioning trees. A KD-tree recursively splits the data along alternating dimensions, creating a binary tree where each leaf contains a small subset of vectors. Ball trees generalize this to arbitrary metrics by enclosing each node's data in a hypersphere. These structures work excellently in low dimensions (below 20): a query can prune large portions of the tree early, reducing the number of distance computations dramatically.

The problem is the curse of dimensionality. In high dimensions, the volumes of hyperspheres and hyperrectangles become so large relative to the data that almost no pruning is possible. For 512-dimensional embeddings, a KD-tree query degrades to nearly brute-force performance: the tree structure provides no benefit. This makes tree-based methods completely impractical for modern NLP embeddings.

LSH takes a different approach: rather than partitioning the space, it uses random projections (or other hash functions) to probabilistically group similar vectors into the same buckets. Vectors that hash to the same bucket are likely to be nearby, so a query can limit its comparisons to vectors sharing bucket labels. Multiple independent hash tables are used to increase recall: if two similar vectors fail to collide in one table, they might collide in another.

LSH has provable guarantees but suffers in practice. To achieve high recall, you need many hash tables (typically 20 or more), which multiplies both memory and query time. The precision-recall tradeoff is difficult to tune: adding more tables improves recall but also increases the number of false positives (vectors that hash together despite low similarity). For high-dimensional embeddings with complex distributions, LSH's theoretical guarantees often translate into poor empirical performance, and the tuning burden is significant.

IVF, used extensively in FAISS, partitions the vector space into Voronoi cells using k-means clustering. Each vector is assigned to its nearest cluster centroid, and the index stores a list (the "inverted file") of vectors per centroid. At query time, the algorithm identifies the nearest few centroids, then searches only the vectors within those cells. By searching a fraction of all cells (controlled by the nprobe parameter), IVF achieves sub-linear query time.

IVF works well for moderate-dimensional data and handles very large collections by loading only the relevant partitions from disk. Its main weakness is that recall can drop sharply if the query falls near a cell boundary: its true nearest neighbors might be in a different cell, and if that cell is not searched, they are missed. The optimal choice of cluster count is also not obvious and requires tuning per dataset. HNSW typically achieves higher recall at lower latency than IVF for in-memory search, which is why most production vector databases prefer HNSW for their primary index. IVF becomes advantageous for datasets too large to fit in RAM, because it enables selective loading from disk.

HNSW's superiority over alternatives for high-dimensional in-memory search comes from several properties working together. First, the graph structure naturally adapts to the data distribution: edges are placed between similar vectors rather than following a rigid geometric partition. Second, the hierarchical layer structure solves the routing problem in a principled way. This lets the search make directional progress without requiring global knowledge. Third, the single ef_search parameter provides an intuitive control for the speed-recall tradeoff, making HNSW easy to tune in production. Fourth, the construction algorithm's use of the diversity heuristic produces graphs that remain searchable across a wide range of data distributions, including clustered data, uniform data, and everything in between.