HNSW — Hierarchical Navigable Small World — is the most widely used algorithm for approximate-nearest-neighbour search and the default index in most in-memory vector databases. It organises vectors into a layered graph that can be navigated to find nearest neighbours in a small number of steps.
The structure works like a hierarchy of maps. Upper layers are sparse, with long-range connections that let a search jump quickly across the space; lower layers are dense, with short-range connections for fine-grained navigation. A search enters at the top, moves greedily toward the query, and descends layer by layer, homing in on the closest vectors. Because each layer roughly halves the remaining distance, search cost grows only logarithmically with dataset size.
HNSW’s appeal is its combination of very high recall and fast queries, plus support for adding vectors incrementally without rebuilding. Its main cost is memory — every vector stores its graph connections, and the index typically lives in RAM. Key tuning parameters control connections per node and search effort, letting operators trade memory and speed against recall.