HNSW (Hierarchical Navigable Small World)
HNSW (Hierarchical Navigable Small World) is the graph algorithm most vector databases use for approximate nearest-neighbour search — the operation behind semantic search and RAG retrieval. It finds the closest vectors to a query in logarithmic time instead of scanning every vector.
How it works
HNSW builds a layered graph. The top layer has few nodes with long-range links; each layer down is denser. A search starts at the top, greedily walks toward the query, then drops a layer and repeats — like zooming in on a map.
layer 2: o───────────o───────────o (coarse, long hops)
layer 1: o──o────o───o───o────o──o
layer 0: o-o-o-o-o-o-o-o-o-o-o-o-o-o (every vector)
The parameters that matter
| Parameter | Effect |
|---|---|
M (graph degree) |
Higher = better recall, more memory (~`M × 8-16` bytes/vector) |
ef_construction |
Higher = better index quality, slower build |
ef_search |
Higher = better recall at query time, slower query |
The cost
HNSW is memory-resident: the whole graph plus the vectors must sit in RAM for fast queries. Budget roughly N × (dims × 4 + M × 16) bytes, then add headroom — this is what the vector DB sizer calculates. Alternatives (IVF, DiskANN) trade recall or latency for a smaller memory footprint.