HNSW: How to Find the Nearest Neighbor Among Millions of Vectors

Comparing a query vector with one million other vectors using an exhaustive search involves one million operations per search. This is not feasible at real-world scale. HNSW trades absolute accuracy for speed, and the trade-off is very favorable.

Multi-level chart

The idea is inspired by the way you travel from Hanoi to Saigon: first, take a long-distance flight; once you arrive, take a taxi; and finally, walk. HNSW constructs a multi-layered graph:

• The top layer is very sparse; each edge spans a large distance in vector space
• The lower layer becomes denser, and the edges become shorter
• The bottom layer contains all the points, with edges connecting points that are actually close to each other

The search starts on the top level, moves greedily toward the point closest to the query, and when it reaches a dead end, moves down to the next level and repeats. The number of steps increases logarithmically with the number of points rather than linearly.

Two parameters you'll need to adjust

• M — the number of edges retained for each node. A higher value improves search accuracy but consumes more RAM
• efSearch — the number of candidates kept in the queue during a search. This is a trade-off between speed and accuracy, and can be adjusted at runtime without rebuilding the index

What You Need to Know Before Choosing

HNSW almost always keeps the entire index in RAM—this is the biggest cost constraint at scale. Deleting elements is also difficult: most implementations simply mark them as deleted and need to be rebuilt periodically.

The result is "close enough." With semantic search, missing an eighth-ranked result goes unnoticed. With exact matching, don't use it.