What it is
HNSW, short for hierarchical navigable small world, is a graph based index for approximate nearest neighbor search. It lets a vector database find the closest embeddings to a query without comparing against every stored vector.
How it works
HNSW builds a layered graph of vectors.
- The top layers are sparse with long range links, like an express highway.
- The bottom layer holds every point with short, dense links.
- A search starts at the top, greedily hops toward the query, then descends layer by layer to refine.
This skip list style structure gives roughly logarithmic search time instead of scanning all points.
Trade offs
HNSW returns approximate results, trading a little accuracy for big speed.
- M controls how many links each node keeps, raising recall and memory.
- efSearch widens the search frontier at query time, raising recall and latency.
- The index lives in memory and is costly to rebuild, so heavy deletion can degrade it.
Key idea
HNSW searches a layered small world graph from sparse top to dense bottom, giving fast approximate nearest neighbor lookup tuned by M and efSearch.