HNSW (Hierarchical Navigable Small World)
HNSW is a graph-based algorithm for {{approximate nearest neighbor}} search introduced by Malkov and Yashunin in 2016. It builds a multi-layer proximity graph in which higher layers contain exponentially fewer nodes with longer-range edges. Searches start at the top layer and descend greedily, giving logarithmic expected complexity at high recall.
HNSW (Hierarchical Navigable Small World) is a graph-based algorithm for approximate nearest neighbor search published by Yury Malkov and Dmitry Yashunin in 2016. It is one of the most widely deployed indexes in modern vector databases and powers retrieval for Semantic Search: Finding Content by Meaning Instead of Keywords at billion-vector scale. The index is a multi-layer proximity graph. Every inserted vector lands on layer 0; with exponentially decaying probability it is also linked into higher layers. Higher layers therefore contain progressively fewer nodes and longer-range edges, behaving like a skip list over the data. Each node keeps a bounded set of neighbors selected by a heuristic that favors diverse directions, producing a navigable small world graph with short greedy paths between any two points. A query enters at the top layer and greedily walks toward the nearest known neighbor, then descends one layer and repeats. At layer 0 the search expands a beam of size ef_search to gather the final k candidates. Expected search complexity is logarithmic in the dataset size. Recall and latency are tuned via three parameters: M (max neighbors per node), ef_construction (build-time beam width), and ef_search (query-time beam width). HNSW achieves very high recall at low latency but holds the graph entirely in RAM, making memory the main cost. It is implemented in hnswlib, FAISS, Lucene, pgvector, and most commercial vector databases. Variants combine HNSW with product quantization or inverted-file partitioning to cut memory while preserving recall.