Searching a graph of vectors
HNSW, hierarchical navigable small world, is one of the most popular ANN indexes. It stores vectors as nodes in a graph where each node connects to its nearby neighbors. Search becomes a walk across this graph toward the query.
The hierarchy
HNSW stacks several layers. The top layer is sparse with long range links, and lower layers grow denser. Search starts at the top, takes big jumps to get close fast, then drops to finer layers to refine the result.
Why it is fast
- Greedy routing: at each step you move to the neighbor closest to the query.
- Layered jumps: high layers cover distance quickly, low layers add precision.
- Search cost grows roughly with the logarithm of the number of vectors.
Tradeoffs to know
HNSW gives excellent recall and speed but uses more memory, since it stores graph links per node. Build time and link count are tunable knobs that trade memory and accuracy.
Key idea
HNSW navigates a layered neighbor graph with greedy hops, reaching high recall in roughly logarithmic steps at the cost of extra memory for the links.