HNSW indexing

HNSW is a graph-based algorithm that enables lightning-fast, approximate nearest neighbor searches across high-dimensional vector embeddings.

Hierarchical Navigable Small World (HNSW) indexing is the gold standard for vector databases like Pinecone and Milvus. It solves the curse of dimensionality by organizing data into a multi-layered graph structure (reminiscent of skip lists) where the top layers contain long-range edges for coarse navigation and the bottom layers hold dense, local connections for precision. This architecture allows systems to achieve sub-10ms latency on billion-scale datasets while maintaining high recall. By avoiding the exhaustive linear scans of traditional k-NN, HNSW delivers the sub-linear search time required for modern RAG pipelines and real-time recommendation engines.

https://arxiv.org/abs/1603.09320