How HNSW Cuts Vector Search from 1,240ms to 2ms Across Millions of Docs

HNSW, or Hierarchical Navigable Small World, is a graph-based algorithm that powers vector search in tools like FAISS, pgvector, Qdrant, and Milvus. Traditional brute-force search across two million 768-dimensional document embeddings requires roughly 1.24 billion arithmetic operations, taking over a second per query and scaling linearly with data size. Unlike B-trees, which sort on a single axis and break down in high-dimensional spaces, HNSW builds a multi-layered graph where each vector node connects to its nearest neighbors, enabling a greedy traversal from sparse long-range links to dense local ones. A search query navigates this structure in approximately 15–20 hops and around 1,800 comparisons instead of two million, reducing latency to about 2 milliseconds. The trade-off is approximate rather than exact results, but in practice the algorithm reliably reaches the true nearest neighbor through the densely interconnected graph structure.