What do M, efConstruction, and efSearch actually change?

M, efConstruction, and efSearch each control a different part of how an HNSW index behaves: M shapes how densely connected the graph itself is, efConstruction controls how carefully those connections get chosen while the graph is being built, and efSearch controls how thoroughly a single query explores the finished graph — and understanding which of these three is responsible for a given symptom is the first step in tuning any HNSW-based system sensibly rather than by trial and error.

What does M actually control, and what does raising or lowering it change?

M sets the maximum number of connections each vector keeps per layer, and it’s the one parameter of the three that’s baked permanently into the graph’s structure rather than adjustable after the fact — changing M means rebuilding the index. A higher M gives each vector more pathways to explore during search, which generally improves recall by making it less likely a search gets stuck without a good route toward the true nearest neighbors, especially on data with high intrinsic dimensionality or crowded, hard-to-separate clusters. That improvement isn’t free: more connections per vector means more memory consumed by the graph itself, and it means more candidate neighbors to evaluate at every step of both construction and search, slowing both down. A lower M produces a leaner, faster-to-build, less memory-hungry graph, at the risk of missing genuine nearest neighbors more often if the connection budget turns out too thin for the data’s actual geometry.

What does efConstruction control, and why does it only affect build time?

efConstruction sets how many candidates are considered when selecting neighbors for a vector as it’s being inserted into the graph — a wider search here means more potential neighbors get evaluated before the final selection is made, generally producing better-placed, more useful connections. Because this search happens once, at insertion time, and the connections it produces are then fixed as part of the graph’s permanent structure, efConstruction has no effect whatsoever on how a completed index behaves at query time; its entire cost and entire benefit are paid once, during construction. A useful way to think about the trade-off: efConstruction is buying the quality of the roads the graph will be built from, and no amount of driving more carefully afterward — no query-time setting — can fully make up for a road network that was laid out carelessly to begin with.

What does efSearch control, and why is it the dial worth adjusting most often?

efSearch sets the size of the candidate pool maintained during the wider search that happens at the base layer of a query, as covered in detail in this site’s page on how HNSW searches a graph step by step. Raising it means the search considers more candidates before settling on a final answer, generally improving recall at the direct cost of higher query latency, since more candidates means more distance calculations per query. Unlike M and efConstruction, efSearch is a purely query-time setting that doesn’t touch the graph’s stored structure at all, which means it can be changed freely, even per individual query, without any rebuilding — a system under light load might afford a higher efSearch for better accuracy, while the same system under a latency-sensitive spike in traffic could lower it temporarily, all without touching the index itself.

Why must efSearch be at least as large as k?

Requesting the top k nearest neighbors while exploring a candidate pool smaller than k is a contradiction the algorithm can’t resolve — there’s no way to return k results from a search that never considered k candidates worth keeping in the first place. In practice, efSearch is usually set considerably higher than k rather than merely equal to it, since the gap between the two is what actually gives the search room to explore genuine alternatives and correct for an unlucky early path, rather than settling for whatever handful of candidates it happened to encounter first.

Why can’t these three parameters be tuned independently of each other?

Because M shapes the graph that efConstruction then builds connections within, and because efSearch’s effectiveness depends on the quality of the graph both earlier parameters already produced, changing one of these values shifts what the “right” setting for the others actually looks like. A larger M creates more opportunities for efConstruction to find good, diverse neighbors, but only if efConstruction is also raised enough to actually explore that larger space of candidates; leaving efConstruction low while raising M mostly just adds unused capacity to the graph rather than genuinely better connections. Likewise, a high efSearch run against a poorly built graph — the product of a stingy M or efConstruction — has less genuine navigational structure to work with, and no amount of query-time exploration width fully compensates for a construction phase that under-invested in graph quality. Tuning these values one at a time in isolation, without accounting for how they interact, is a common way to end up with a index that performs worse than expected despite each individual setting looking reasonable on its own.

Knowing what each parameter does is only half the job — the next page turns this into an actual repeatable procedure for finding good values on a specific dataset, rather than relying on values that worked well for someone else’s very different workload. For concrete illustrations of how M in particular affects memory consumption in practice, this site’s memory-and-storage glossary section works through the bytes-per-vector accounting these trade-offs ultimately come down to.