HNSW — the graph index
HNSW (Hierarchical Navigable Small World) is the most widely used vector index today. It is fast, accurate, supports adding vectors one at a time, and works well across many kinds of data. Understanding it gives you intuition for most vector database behaviour.
Step 1: a graph of neighbours
Connect every vector to a handful of its nearest neighbours. Now, to search, start at some node and repeatedly move to whichever neighbour is closer to the query. When no neighbour is closer, stop — you're at (or near) the answer. This "greedy walk" checks only the nodes along the way, not the whole dataset.
The problem: on a big graph, starting far away means many small hops, and the walk can get stuck in a local dead end.
Step 2: add express lanes
HNSW fixes this with layers, like a transport network:
- The top layer has very few nodes connected by long links — the motorway.
- Middle layers have more nodes and shorter links — main roads.
- The bottom layer (layer 0) contains every vector with links to its closest neighbours — local streets.
Each vector is placed in layer 0, and a random few are also promoted to higher layers (fewer and fewer the higher you go).
How a search works
- Start at the entry point in the top layer.
- Greedily hop to the neighbour closest to the query until no neighbour is closer.
- Drop down one layer from that node and repeat.
- In layer 0, run a slightly wider search that keeps a list of the best candidates found so far (size
efSearch), and return the top k.
Because the upper layers cover long distances in few hops, the total number of distance calculations stays small even for very large collections.
How inserting works
To add a vector, HNSW picks its top layer at random, searches for its nearest neighbours on each layer from there down (using a candidate list of size efConstruction), and links it to up to M of them. This is why HNSW supports incremental inserts — no retraining needed.
The three parameters that matter
| Parameter | What it controls | Raise it to… | Cost of raising it |
|---|---|---|---|
M |
Max links per node | Improve recall, especially for high-dimensional data | More memory, slower inserts |
efConstruction |
Candidate list size while building | Build a better-quality graph | Slower builds |
efSearch (sometimes ef) |
Candidate list size while searching | Raise recall | Slower queries |
M and efConstruction are fixed at build time. efSearch can be changed per query, which makes it your main live tuning knob. Typical starting points are M around 16 and efConstruction in the low hundreds, but defaults vary by database — check yours.
Rule of thumb: tune efSearch first. If you can't reach your recall target at an acceptable latency, rebuild with a higher M or efConstruction.
Strengths and weaknesses
Strengths
- Excellent speed–recall balance across many datasets.
- Supports inserts without retraining.
- Query-time recall tuning via
efSearch.
Weaknesses
- Memory hungry — the full vectors plus the graph links usually live in RAM.
- Deletes are awkward — removing a node can leave holes in the graph, so many systems mark items as deleted and clean up later (see Ingestion and updates).
- Builds are CPU-intensive for large bulk loads.
- Heavy metadata filtering can disconnect the walk — covered in Metadata filtering.
If HNSW memory is the problem, combine it with quantization (store compressed vectors in the graph) or consider a disk-based graph index such as DiskANN. See Quantization and Other index types.
Senior Full-Stack Engineer · AI & AWS. I build production search, RAG and AI systems on AWS and Postgres.