Graph-Based Indexes (HNSW)

## Three knobs, two clocks Almost every HNSW deployment is tuned with three parameters, and the single most useful thing to know about them is which clock they run on. **M — build time.** M is the maximum number of bidirectional links each node keeps per layer. Layer 0, which holds every vector, usually allows roughly twice that (implementations expose this as a separate maximum). M controls how densely connected the graph is. More links mean more alternative paths for the greedy walk, so a given beam width finds better neighbours; they also mean more edges to store and more neighbours to score at every hop. **efConstruction — build time.** When a new vector is inserted, HNSW runs the same beam search used at query time to find its candidate neighbours, with the beam width set to efConstruction. Those candidates are then pruned down to M links by a heuristic that prefers a diverse spread of directions rather than simply the M closest — diversity is what preserves long-range navigability. A larger efConstruction means the insertion looked at more of the graph before choosing, so the edges are better. It costs build time and nothing else: it does not change the index size, and it does not appear at query time. **efSearch — query time.** This is the beam width used at layer 0 when serving a query. It must be at least k. It is the only one of the three that a caller can change per request, because it is a parameter of the traversal, not of the structure being traversed. ## Why the asymmetry matters operationally The practical consequence is that recall problems have two very different price tags. If your recall is short and efSearch is low, you are one config change away from fixing it. You can even do it selectively: serve high-value traffic (a checkout recommendation, a compliance search) at efSearch 256 and background or bulk traffic at 64, on the same index, in the same process. Nothing is rebuilt and nothing is redeployed. If your recall is short because M is too small for the data's intrinsic difficulty, or because efConstruction was set low to make an overnight build fit its window, there is no query-time escape. Raising efSearch on a poorly connected graph has diminishing returns — you can widen the beam all you like, but if the edges needed to reach the true neighbour were never written, the traversal cannot follow them. Fixing it is a full rebuild of the whole index, which on a large corpus is hours of compute and a deployment event. That is why the standard advice is to be generous with efConstruction on the first build. It is the cheapest of the three mistakes to avoid and the most expensive to correct. ## Reading the recall-latency curve efSearch tuning is empirical, not analytical. The method is a sweep: hold the index fixed, build a ground-truth set of true neighbours for a few thousand sample queries with an exhaustive scan, then measure recall and latency at efSearch values across a range — 32, 64, 128, 256, 512. The shape is always the same. Recall rises steeply at first and then flattens; latency rises close to linearly with the number of nodes visited, which tracks efSearch. On a large product catalogue you might see recall@10 go 0.86 at efSearch 32, 0.95 at 128, and 0.99 at 512, while p99 latency triples across that range. The interesting part of the curve is the knee — the point past which each further percentage of recall costs disproportionate latency. Where you sit on that curve is a product decision, not a database decision. A retrieval stage feeding a reranker can often run at lower recall than a system whose top-10 is the final answer, because the reranker only ever sees what retrieval returned but the user only ever sees the reranked head. Conversely, a legal or compliance search where a missed document is a real failure sits far up the curve and pays the latency. ## Interactions worth knowing M and efSearch are not independent. A higher-M graph reaches a target recall at a lower efSearch, because each hop offers better options; that is one way to spend memory to buy latency. efConstruction below M is pointless — the beam must be at least as wide as the number of neighbours you are going to select from it. And efSearch below k is invalid, since the beam cannot hold the result set you asked for. ## What interviewers listen for The answer they want is the clean split — M and efConstruction are structural and immutable, efSearch is per-query — plus the operational consequence: one class of recall problem is a config change and the other is a rebuild. Candidates who can also describe how they would actually pick efSearch, by sweeping against a brute-force ground truth rather than guessing, sound like people who have run one of these in production.