skip to content

In an HNSW vector index, what do m, efConstruction and ef trade off?

level: middleimportance: must knowfreq 66%

answer

  1. layered graph, greedy descent
  2. links per node versus search width
  3. two are frozen at build, one is per query
  4. recall bought with memory, build time, latency
  5. measure against exact brute force

basics

~20 s

m sets how many neighbour links each node keeps, efConstruction how hard the builder searches while inserting, and ef how wide the search is at query time. Raising them raises recall while costing memory, build time and query latency respectively.

solid answer

~60 s

HNSW is a layered proximity graph: search enters at a sparse top layer, greedily walks towards the query, and drops a layer until it refines on the dense bottom layer. **m** is the maximum number of neighbour links a node keeps per layer (the bottom layer typically allows about twice that). Larger m gives a better-connected graph and higher recall, but every link costs memory and every hop costs distance computations. **efConstruction** is the size of the candidate list the builder explores when linking a new node — larger values buy graph quality at the price of build time, and are baked in permanently. **ef** (efSearch) is the same candidate list at query time and must be at least k; it is the one knob you can turn per query, trading latency directly for recall. The tuning method is not folklore: sweep ef on a sample of real queries, measure recall@k against exact brute-force results, and stop at the smallest ef that meets your recall target inside the latency budget.

code

python · 14 lines
python
import numpy as np

def recall_at_k(exact_ids, approx_ids, k=10):
    hits = len(set(exact_ids[:k]) & set(approx_ids[:k]))
    return hits / k

rng = np.random.default_rng(0)
corpus = rng.normal(size=(20000, 256)).astype("float32")
corpus /= np.linalg.norm(corpus, axis=1, keepdims=True)
query = corpus[7]

exact = np.argsort(-(corpus @ query))[:10].tolist()   # brute-force ground truth
approx = exact[:9] + [12345]                          # stand-in ANN result
print(recall_at_k(exact, approx))                     # 0.9

go deeper

for a junior

Know that HNSW is an approximate graph index and that there are build-time knobs and a query-time knob, and that all of them trade speed for recall.

for a middle

Explain each parameter precisely: m as neighbour links, efConstruction as build-time candidate width, ef as query-time candidate width — and which two are frozen into the graph.

for a senior

Demonstrate the tuning loop: sample real queries, compute exact ground truth, sweep ef against p95 latency, and rebuild only when the recall curve flattens below target. Mention tombstones and rebuild cadence.

for a principal

Own the arithmetic and the operating model — memory per vector at your dimensionality, index build as a scheduled job with its own budget, differentiated ef by request class, and the point at which an in-memory graph stops being the right architecture.

## What HNSW actually is HNSW stands for Hierarchical Navigable Small World. It is a graph index for approximate nearest-neighbour search. Each vector becomes a node, and nodes are linked to some of their nearest neighbours. The graph is layered like a skip list: a small random subset of nodes appears in the upper layers, and every node appears in the bottom layer. A search starts at an entry point in the top layer, greedily moves to whichever neighbour is closer to the query, and when it can improve no further it descends a layer and repeats. On the bottom layer it keeps a candidate list of the best nodes found so far rather than a single best, which is what turns a greedy walk into a usable top-k search. It is *approximate*: the walk can get stuck in a region of the graph that does not contain the true nearest neighbours. All three parameters are ways of buying back that lost recall. ## m — links per node `m` caps the neighbours each node keeps in a layer; implementations usually allow roughly `2 * m` at the bottom layer where all nodes live. More links mean more escape routes out of a local minimum, so recall rises — with diminishing returns, and with a real memory bill. Rough arithmetic for the bottom layer: `2 * m` links at 4 bytes per neighbour id is `8 * m` bytes per vector of graph overhead, on top of the vector itself. At `m = 32` that is about 256 bytes per vector. Typical values sit between 16 and 64; high-dimensional or hard corpora want the upper end. The vectors usually dominate. A 1024-dimensional float32 vector is 4 KB, so ten million chunks is roughly 40 GB of vectors plus about 2.5 GB of graph at `m = 32`. That arithmetic — dimensions times 4 bytes times chunk count, plus `8 * m` per chunk — is the first thing to do before choosing a deployment shape, because HNSW is a fundamentally in-memory structure. ## efConstruction — build-time search width When a node is inserted, the builder runs the same greedy search to find candidate neighbours to link it to. `efConstruction` is how many candidates it keeps during that search. Higher values produce a graph whose links are genuinely closer to true nearest neighbours, which lifts the recall ceiling for every future query. The cost is build time, roughly linear in efConstruction, and build time is not negligible: large corpora take hours, and the parameter is frozen into the graph — changing it means rebuilding, not reconfiguring. Common values are 100 to 400; something like 200 with `m = 32` is a reasonable starting point for a demanding corpus. ## ef — query-time search width `ef` (often called efSearch) is the candidate-list size during a query and must be at least the k you want back. It is the only one of the three you can change per query, and it maps almost linearly onto latency: doubling ef roughly doubles the distance computations. That makes it the right knob for differentiated service — a low ef for an interactive type-ahead, a high ef for a batch job that must not miss anything. ## Deletes and updates Most implementations do not truly remove a node; they tombstone it and filter it out of results. Deleted nodes still occupy memory and still participate in traversal, so a corpus with heavy churn degrades in both recall and memory until it is compacted or rebuilt. If your corpus is append-mostly this is a non-issue; if documents are constantly re-processed, plan the rebuild cadence up front and treat index build as a scheduled operation with its own resource budget. ## How to tune, concretely 1. Take a sample of real queries — a few hundred is usually enough to see differences. 2. Compute exact top-k by brute force over the corpus (or a large random subset) to get ground truth. 3. Sweep ef and plot recall@k against p95 latency. The curve flattens; pick the knee that clears your recall target. 4. Only if the curve flattens *below* your target do you rebuild with a larger m or efConstruction, because that costs a rebuild. 5. Re-run the sweep after any change to the embedding model, the chunking scheme or the corpus size — recall is a property of the data, not just the parameters. Recall here means recall against exact search, which is an index-quality measure. It is not the same as whether the retrieved chunks answer the user's question; a perfectly tuned index over badly chunked text still retrieves badly. ## When the parameters stop helping There are two walls. The first is memory: if the vectors no longer fit in RAM, no HNSW parameter saves you and the answer is fewer dimensions, quantization, or a disk-resident index design. The second is filtering: when queries carry a selective metadata predicate, the graph's connectivity assumptions break and recall collapses in ways that raising ef only partly compensates for. Both are separate decisions from the m/efConstruction/ef sweep.

  • You have swept ef to a high value and recall is still short of target. What now?
    Raising ef only widens the search over the graph you have; if the graph itself is poorly linked, that ceiling is fixed. Rebuild with a larger m and efConstruction and re-sweep. If recall is still short, suspect the data rather than the index: duplicated or near-identical chunks, a mismatch between the build and query metrics, or unnormalized vectors. Confirm by comparing against exact search on the same sample.
  • How does heavy document churn affect an HNSW index?
    Deletes are usually tombstones rather than real removals, so removed vectors keep consuming memory and keep being traversed, and repeated insert-delete cycles leave a graph whose links point at dead or stale nodes. Recall drifts down and memory drifts up. Plan periodic rebuild or compaction, size hardware for the pre-compaction peak, and monitor the tombstone ratio as an operational metric.
  • What breaks first when the corpus grows past available RAM?
    HNSW assumes the graph and vectors are resident in memory; once the working set exceeds RAM, page faults turn every graph hop into a random disk read and latency degrades catastrophically rather than gracefully. Parameters cannot fix this. The levers are fewer dimensions, quantized vectors with a rescoring pass, or an index designed for disk residency that keeps compressed vectors in memory and issues few sequential reads per query.

saying these in an interview costs you the question

  • Higher ef improves recall for free, with no latency cost
  • m and efConstruction can be tuned live without a rebuild
  • HNSW recall means the answers are relevant to the user
  • Deleting vectors immediately frees the memory they used
  • One parameter set is optimal for every corpus and query mix

context

resolving link…