HNSW and Its Knobs
In one line: build a graph where nearby vectors are linked, add sparse upper layers for long-distance travel, and search becomes greedy navigation instead of exhaustive comparison.
The structure
The idea borrows from a skip list. The bottom layer contains every vector, connected to its nearest neighbours. Each layer above holds a random subset with longer-range links.
A search enters at the top, moves greedily toward the query through the sparse layer until it cannot improve, drops a level, and repeats. The upper layers cover distance quickly; the bottom layer refines.
Two properties follow and are worth stating. Search is logarithmic-ish rather than linear, which is where the speed comes from. And it is greedy, which is where the approximation comes from — the walk can settle in a local optimum and never reach the true nearest neighbour.
The three parameters
| M | efConstruction | efSearch | |
|---|---|---|---|
| Controls | Links per node | Candidates explored while inserting | Candidates explored while querying |
| Set at | Build time — permanent | Build time — permanent | Query time — changeable |
| Raising it | Better recall, more memory, slower build | Better graph, slower build, no memory cost | Better recall, slower query, no memory cost |
| Typical | 16–32 in production, up to 64 | 200–400 | 50–400, tuned to the recall target |
The row that matters most is set at. Two of these are baked in when you build; one is free at query time.
efSearch is the one you actually operate
Because it costs no memory and can be changed per query, efSearch is the runtime dial between recall and latency. Raising it from 100 to 400 can move recall from roughly 90% to 98% while roughly doubling query latency.
That makes a genuinely useful pattern available: different efSearch for different traffic. A latency-sensitive autocomplete runs low; an analytical query where the user is waiting anyway runs high. Same index, same data, different operating points — and mentioning that is a good sign you have run one of these rather than read about it.
M is a memory commitment
M decides how many links each node stores, so it directly sets the graph's size. Higher M means more paths through the graph, better recall and worse memory.
It is fixed at build time, so getting it wrong means a rebuild. The practical guidance: start at 16, raise toward 32 if recall is short at acceptable efSearch, and treat 64 as unusual. Higher-dimensional embeddings and corpora with clustered structure benefit more from a larger M.
efConstruction buys graph quality for build time only
It controls how hard the algorithm looks for good neighbours when inserting each node. Higher values produce a better-connected graph — better recall and better speed at query time — and cost nothing at query time or in memory. They cost build time.
So it is close to a free win, bounded by how long you are willing to wait. 200 is a reasonable default; 400 if the index is built rarely and served for a long time.
That ordering is the practical answer to "recall is too low", and the closing branch is the one that saves the most time.
Why HNSW is the default
It gives the best recall per millisecond of the common structures, it supports incremental inserts without a retraining step, and it needs no representative sample before it can be built.
The costs are real and worth naming rather than glossing:
Memory. The graph is substantial — commonly 1.5–2× the raw vectors on top of the vectors themselves.
Build time. Slow, and it grows worse than linearly with corpus size. Building over a hundred million vectors is hours.
Deletion. The structure has no clean removal. Nodes are marked deleted and remain in the graph as unreachable clutter, so recall degrades as tombstones accumulate. This gets its own treatment in the operations lesson, and it is the sharpest edge in running one.
Key takeaway
HNSW layers a neighbour graph so search becomes greedy navigation — fast, and approximate precisely because it is greedy. Of its three parameters, only efSearch is changeable after the build, which makes it the operating dial: 100 to 400 buys roughly 90% to 98% recall for about double the latency, and different traffic can use different values on the same index. M is a permanent memory commitment starting at 16, and efConstruction buys graph quality for build time alone. Tune efSearch first, rebuild second, and suspect the embedding third.
Next: the partition-based alternative, and compressing the vectors themselves.