M and efConstruction set HNSW's ceiling, ef_search only walks under it

HNSW — Hierarchical Navigable Small World — stores a corpus as a layered graph over its vectors and answers a query by walking that graph instead of scanning everything. Three parameters govern it, and they do not all act at the same time: M and efConstruction are consumed while the graph is being built, and ef_search is consumed on every query. Which of the three you can change during an incident, and which of them require a rebuild, follows entirely from that split. What all three are measured against is index recall, R@10 in the sense of chapter 2 — the fraction of a query's true ten nearest neighbours, as an exact scan would have found them, that the index actually returned.

An engineer measuring an HNSW index on 3M product-description vectors runs the sweep and gets a curve that starts at R@10 = 0.86 with ef_search = 40, climbs to 0.89 at 100, reaches 0.91 at 400, and then does nothing. At ef_search = 1000 it is 0.911. At 2000 it is 0.912, and p95 latency has gone from 2.1 ms to 47 ms. The obvious reading is that HNSW tops out around 0.91 and that the remaining 9% is the price of approximation. The actual reading is that this particular graph tops out around 0.91, that a different graph over the same vectors reaches 0.99, and that no amount of query-time tuning will get from one to the other because the missing recall is missing edges rather than missing search effort.

What the build decides#

HNSW stores the corpus as a proximity graph — every vector is a node, and an edge joins two vectors that sit near each other in the space — arranged in layers. Every vector is a node in layer 0; each node is also promoted to layer 1 with some probability, to layer 2 with the square of it, and so on, which leaves a sparse top layer of a handful of nodes and a dense bottom layer containing everything. Within a layer, each node keeps links to a bounded number of near neighbours: M of them on the upper layers and, by convention in most implementations, 2M on layer 0. A search enters at the single top-layer node, greedily descends to the closest node it can reach on each layer, and then runs a best-first beam search on layer 0, which means it holds a fixed number of the most promising nodes it has seen, expands the closest of them, adds that node's neighbours to the pool, and repeats until the pool stops improving.

efConstruction governs insertion. When a new vector arrives, the index runs the same search to collect a candidate list of size efConstruction, and then chooses which of those candidates become the node's links. The choice is not simply "the M nearest", because a heuristic prunes candidates that are closer to an already-selected neighbour than they are to the new node, which spreads the links out in direction rather than clustering them all on one side. That heuristic is what makes the graph navigable, and it is described in Efficient and Robust Approximate Nearest Neighbor Search Using HNSW, which is worth reading if you want to know why the pruning rule exists rather than just what the parameter does.

The step that matters most about efConstruction is the one easiest to read past: the candidate list it sizes is a shortlist, and the number of links finally kept is capped by M and 2M whatever the shortlist's size. So raising efConstruction changes which neighbours a node links to and never how many. Two consequences follow immediately. The index occupies the same bytes at any efConstruction, because bytes are per link and the link count did not move. And a query does the same amount of work at any efConstruction, because a query's cost is the nodes it expands times the edges it finds there, and again the edge count did not move. What a larger shortlist buys is a better-chosen set of links out of a wider field of candidates — paid for once, at build time.

The layers exist to solve the entry problem. A flat proximity graph is navigable in principle, but a greedy walk from a random starting node has to take a great many small hops to cross the space, and the number of hops grows with the corpus. Promoting a small fraction of nodes to higher layers creates a coarse graph whose edges span long distances, so the descent covers most of the distance in a handful of hops on sparse layers before switching to fine-grained search at the bottom. With the standard promotion probability, layer 1 holds about 1/M of the nodes, layer 2 about 1/M², and the top layer typically holds a single node — for 3M vectors at M = 16 that is roughly five layers, and the descent costs about five greedy searches over progressively denser graphs before the real work begins.

Those two fives are one fact rather than two, and the arithmetic behind them is worth doing once. Each layer up divides the population by M, so the height of the tower is the number of times you can divide the corpus by M before you are down to a single node. Divide three million by sixteen five times over and you are into single digits; divide once more and you are below one. That gives the layer count — and note what it implies, which is that M is doing two jobs at once, setting how many edges a node keeps and, through the promotion probability tied to it, setting how deep the tower is. Tying that probability to M is a convention of the standard construction rather than something the structure requires. The descent then runs exactly one greedy search per layer on its way down, which is why the count of searches matches the count of layers instead of being a second measurement that happens to agree.

Both of those numbers are consumed during insertion and then discarded. What survives into the served index is a fixed edge set: node 4,481,002 has these 32 links on layer 0 and these 16 on layer 1, permanently, until the index is rebuilt or that node is re-inserted.

Why widening the beam runs out#

ef_search sets the size of the dynamic candidate list during the layer-0 beam search. A larger value means the search keeps more frontier nodes alive, backtracks more, and explores a larger connected region before it stops. Every node it evaluates must be reachable by following edges from where it already is, and that is where the ceiling comes from: if a true nearest neighbour has no short path from the query's entry region, then enlarging the frontier explores more of the wrong neighbourhood without ever crossing into the right one.

Stated as two quantities that are easy to confuse, ef_search sizes the set of candidates retained, and the edge set fixes the set of nodes reachable. The first is a subset of the second at every moment of the search, and no value of the first can exceed the second. So as ef_search grows without limit, recall does not approach 1.0; it approaches the fraction of a query's true neighbours that lie inside its reachable region, and that fraction was determined when the edges were chosen. This is the belief worth naming, because it is the one that costs teams the most: that recall is a thing you raise ef_search until you have enough of. It survives a sweep because it is half true — the curve really does climb — and it fails at exactly the point where the climb stops, which is also the point at which somebody concludes the remaining loss is intrinsic to approximation rather than particular to their graph.

The two shaded nodes on the right form a pocket whose only links point at each other, which happens when a vector is inserted into a region where every nearby node has already used all 2M of its layer-0 slots on closer neighbours. The insertion still succeeds and the node is still in the index; it is simply not reachable from the main body of the graph in the direction a query approaches from.

The mechanism deserves spelling out, because "it is in the index but not reachable" sounds like a contradiction until you separate the two directions an edge can point. A newly inserted node picks its own out-links freely from its candidate list, so it always ends up pointing at good neighbours. Being found needs the opposite: some node already in the graph has to point back at it. A neighbour adds that back-link only if it has a free layer-0 slot, or if the newcomer beats one of the 2M it is already holding. In a saturated region neither condition holds, because every slot was filled long ago by something closer. The node therefore ends with out-edges and no in-edges, and out-edges are worth nothing to a search that never arrives. Raising ef_search from 40 to 2000 grows the explored frontier by a factor of fifty and never touches it. Raising M from 16 to 48 gives every node three times the link budget, the pruning heuristic keeps more diverse directions, and the pocket gets an in-edge.

That is what the plateau at 0.91 was reporting. The measured curves for the same 3M vectors, built three ways:

Vectors alone are 3M × 768 × 4 = 9.2 GB, so the graph overhead at M = 16 is about 0.8 GB and at M = 48 about 1.8 GB. The two M = 16 rows have identical memory and identical query cost at any given ef_search; the only difference is that the second one spent seventeen extra minutes at build time picking better links, and it bought three points of ceiling for nothing at serving time. That is the cheapest parameter in this whole topic and the one most often left at a low default.

Those two rows sharing a byte count is the empirical fingerprint of the shortlist argument above, and it is worth registering as evidence rather than as a coincidence. If efConstruction could add links, the second row would be larger than the first. It is not larger, which is what "changes which, never how many" predicts, and the identical query cost at fixed ef_search is the same fact seen from the serving side.

The M = 48 row costs 20% more memory, eight times the build time, and roughly 40% more work per query because there are more edges to evaluate at each hop. What it buys is a ceiling of 0.993 instead of 0.91, which is the difference between an index you can trust and one that is quietly dropping a tenth of every result set.

Two of those three figures need their baseline said out loud, because the table supports more than one subtraction. The 20% is measured against the vectors — an M = 48 index is about a fifth larger than the 9.2 GB you had to store anyway, which is the comparison that matters when sizing a machine — while against the M = 16 index it is a tenth larger. The eight-fold build time is measured against the 9-minute first row rather than the 26-minute second one. And the 40% is smaller than the threefold rise in M because two effects pull against each other: each hop evaluates every neighbour of the node it expands, so per-hop cost scales with degree, but a better-connected graph reaches the query's neighbourhood in fewer hops, and the beam is capped at ef_search candidates regardless of M, which bounds how many nodes get expanded at all. Three times the edges with fewer hops nets out at the measured 40%.

The same subtraction is available on the overhead figures and it will not agree with 2M × 4 bytes per vector, which is the layer-0 link cost quoted later in this chapter. Both are right about different things. The subtraction measures everything the index holds that is not a vector, which is the link arrays plus per-node bookkeeping; 2M × 4 counts the layer-0 link array alone. At M = 16 that array is a hundred and twenty-eight bytes a vector, which over three million vectors is well under the 0.8 GB the subtraction reports, and the same relationship holds on the M = 48 row. The gap between the two is the bookkeeping, and expecting them to match is how a capacity estimate comes out short.

The recall columns close on themselves too, and they do it in a way the levels hide. Subtract each recall from its own row's plateau, and what is left is the shortfall ef_search is responsible for. In the first row that is about five hundredths, then about one hundredth, then nothing. In the second row it is about five hundredths, then about one hundredth, then a thousandth. In the third row it is about five hundredths, then a little over one hundredth, then two thousandths. Three builds whose levels differ by up to eleven points produce the same shortfall column.

What that identity licenses is the whole argument of this chapter, stated as arithmetic rather than as advice. Recall is a ceiling minus a shortfall; the build sets the ceiling and ef_search sets the shortfall; and the shortfall is the same function of ef_search in every build, so the two are separable. Two practical things fall out. A single measurement at the high end of the sweep sits within a couple of thousandths of a build's ceiling, so builds can be ranked against each other without sweeping each one — the expensive part is the building, not the measuring. And the shape of an ef_search curve carries no information about the height of the ceiling it approaches, because every build produces the same shape. An engineer watching a curve climb and flatten has not discovered anything about their index. They have watched HNSW do what HNSW does.

import hnswlib, numpy as np, time

def sweep(corpus, queries, gt_ids, M, efC, ef_values):
    idx = hnswlib.Index(space="ip", dim=corpus.shape[1])
    idx.init_index(max_elements=len(corpus), M=M, ef_construction=efC)
    t0 = time.perf_counter()
    idx.add_items(corpus, np.arange(len(corpus)), num_threads=16)
    build_s = time.perf_counter() - t0

    rows = []
    for ef in ef_values:
        idx.set_ef(ef)                      # query-time only, no rebuild
        t0 = time.perf_counter()
        ids, _ = idx.knn_query(queries, k=10, num_threads=1)
        ms = (time.perf_counter() - t0) / len(queries) * 1000
        rows.append((M, efC, ef, index_recall(ids, gt_ids).mean(), ms))
    return build_s, rows

# M and efC require a new index object; ef is set on the live one.
for M, efC in [(16, 100), (16, 400), (48, 400)]:
    print(sweep(corpus, queries, gt_ids, M, efC, [40, 100, 200, 400, 800, 2000]))

The line that matters more than the knobs#

Putting HNSW's parameters next to IVF's from chapter 3 gives the sort that is worth carrying around:

The last two columns are the same column written twice, and checking that is what makes the table worth memorising rather than looking up. Every row whose cost is "A config change" has a "What it moves" that begins with "Position". Every row whose cost is a rebuild or a retrain moves the curve itself — a ceiling, a cell size, a latency floor. No row sits in both groups and none sits in neither. So you never have to remember what a parameter costs to change: read what it moves, and the cost follows. The half of that rule which bites is the converse. Anything that moves the ceiling costs a rebuild, without exception, which means the ceiling is the one thing that is never available to you on the day you need it.

The reason this split matters more in practice than any individual parameter is that it tells you what is available to you during an incident and what is not. When recall is bad on a Tuesday afternoon, ef_search and nprobe are things you can change in the next five minutes, per query class if you want, and roll back just as fast; they trade latency for recall along a curve whose shape is already fixed. M, efConstruction and nlist are things you can change over the next several hours, with a rebuild, a memory headroom check, and a cutover; they move the curve itself. A sweep that treats all five as interchangeable dials and reports "the best recall-per-millisecond point" hides that distinction entirely, and hands you a recommendation you may not be able to act on.

The split also determines what a sweep can discover. Sweeping ef_search on an existing index traces one curve and finds its plateau, which tells you where you are but says nothing about how high the ceiling could be — the 0.91 index and the 0.993 index look identical until you rebuild. Getting the second number requires building at least two indexes, which is a job that runs for an hour rather than a loop that runs for a minute, and it is the step teams skip. The practical consequence is that "we tuned the index" almost always means "we tuned ef_search", and that leaves the largest available gain untouched.

Choosing the build parameters without infinite build time#

Because efConstruction costs nothing at serving time, its selection rule is simple: raise it until the recall ceiling stops moving, then stop. On the 3M corpus that point was around 400; going to 800 added 24 minutes of build and 0.002 of ceiling. The failure mode is leaving it at a library default of 100 or 200 because it is the parameter nobody thinks about, which is what produced the first row of the table above and a ceiling three points lower for free.

"Stops moving" needs a threshold, and the harness supplies one. Chapter 2's sample-size arithmetic — per-query R@10 has a standard deviation of a few tenths, and the standard error of the mean is that divided by the square root of the query count — puts a five-hundred-query evaluation set at roughly three hundredths of resolution, at the confidence level that arithmetic is normally quoted with. Two thousandths is an order of magnitude below that, so the gain from 800 is not merely small, it is invisible to the instrument being used to look for it. Quadrupling from 100 to 400 bought three points, which sits right at the edge of what such a set can resolve. The rule to write down is therefore to stop when the gain per doubling falls under the harness's own error bar, and to widen the query set before believing any difference narrower than that.

M is the harder one because it costs on three axes at once, and the right value depends on how intrinsically high-dimensional the data is, meaning how many independent directions it genuinely varies along rather than how many coordinates each vector happens to carry. Embeddings of prose from a modern text model tend to want M between 32 and 64; image descriptors and other data with strong low-dimensional structure are usually fine at 12 to 16. There is no way to read that off the corpus, so the practical procedure is to build at two values an octave apart, 16 and 32 say, measure both plateaus, and take the smaller one if the difference is under a point. The memory relationship is worth carrying: layer-0 links cost 2M × 4 bytes per vector, so at 1024 float32 dimensions M = 32 is a 6% overhead and at 128 dimensions the same M is a 50% overhead. Low-dimensional corpora are where M has to be watched.

Those two percentages are the same fraction with a different denominator, which is the whole reason M is a dimension-dependent decision rather than a universal one. The link cost per vector depends only on M. The vector cost per vector depends only on the dimension. So the overhead is a ratio between something you chose and something the embedding model chose, and dropping the dimension by a factor of eight while holding M multiplies the overhead ratio by eight.

Insertion order matters more than it looks like it should, and it is a genuinely awkward property. The first vectors inserted have almost no graph to attach to, so their links are chosen from a tiny candidate pool and are worse than they would have been later; the entry point and the upper-layer skeleton are determined by whichever early vectors happened to be promoted. Building an index from a corpus sorted by document, so that the first 50,000 vectors are all chunks of one manual, produces a measurably worse graph than building from the same vectors shuffled — differences of one to three points of ceiling are typical. Shuffling before add_items costs one permutation and removes the whole class of problem.

Sorted order does two separate kinds of damage, and only one of them is about pool size. A small pool makes early links merely worse. A sorted pool makes them unrepresentative: if the first tens of thousands of vectors all come from one manual, the upper-layer skeleton is built entirely out of one region of the space, and every later query starts its descent from a coarse graph that describes somewhere else. Shuffling does not enlarge the early pool at all. It makes the early pool a random sample of the whole space, which is what the skeleton needs to be.

Churn, deletion, and the price of a larger M#

Removing the cell boundaries removes IVF's specific failure and does not remove approximation. The graph has its own geometry of loss, concentrated on nodes with poor connectivity, and the plateau above is the aggregate of it. There is also no training pass and no centroid drift, which is the property that makes HNSW attractive for corpora that grow — but incremental insertion into a graph whose neighbourhoods are already saturated produces exactly the pocket drawn above, so "no retraining needed" is not the same as "never rebuild".

Deletion is worse. Most implementations mark a node deleted and keep it in the graph as a routing element, because removing it would break the paths that run through it, so a heavily-churned index carries nodes that cost traversal work and memory while contributing nothing. Chapter 8 takes that up as a failure mode with its own signature.

And M is not a dial to turn up on principle. Each increment adds 8 bytes per node per layer-0 slot pair, adds build time superlinearly, and adds work per hop, so at 128 dimensions an M = 64 graph can occupy more memory than the vectors it indexes. The right value depends on the intrinsic dimensionality of your data, which you do not know in advance, which is why the honest procedure is to build two or three and measure.

The one claim in this chapter that holds without conditions is the ordering. A graph's edges are chosen at build time and are the only thing a query can walk, so the highest recall any query will ever see was fixed before that query existed; ef_search decides how much of that ceiling a given query pays to reach. Everything else — which M, which efConstruction, whether the extra build hour is worth it — is a judgement about a particular corpus, and the figures above are one corpus's answer rather than anybody's default.

Knowing that a plateau exists at 0.91 still leaves the more useful question unanswered: the 9% that is lost is not spread evenly over the queries, and the next chapter is about who loses it.