Defining “efConstruction” and its impact on build time

What efConstruction does at build time

When a new vector is inserted into the HNSW graph, the algorithm must decide which existing nodes to connect it to (up to M per layer). To do that, it runs an internal approximate nearest neighbor search over the current graph—the same style of greedy search used at query time. The size of the dynamic candidate list during this internal search is efConstruction. A larger list means more candidates are considered when picking the M best neighbors, so the chosen links tend to be of higher quality and the graph has better connectivity.

efConstruction does not affect the number of links stored (that’s M); it affects how good those links are. If efConstruction is too low, the insertion search may not find the true nearest neighbors and the graph can have weak links or bottlenecks. If it is high enough, the selected M neighbors are closer to optimal and recall at query time tends to improve.

Build time vs. index quality

Build time scales roughly with the number of vectors times the cost of each insertion; that cost grows with efConstruction because each insertion runs an internal search over a larger candidate set. So doubling efConstruction can significantly increase total index build time, especially for large datasets. It does not affect query time directly—that’s controlled by efSearch.

In exchange, higher efConstruction usually yields a better graph: fewer “wrong” links and better coverage of the space. That can mean you need a lower efSearch at query time to hit the same recall, which improves query latency. So the trade-off is build-time cost now for query-time benefit later.

Pipeline: insertion and candidate list

For each new vector, the builder assigns a maximum layer (skip-list style), then for each layer from that max down to 0 it runs a greedy search to find candidates. The candidate list is capped at efConstruction. From those candidates, the algorithm selects up to M neighbors (often with a pruning strategy to favor diversity or proximity). Bi-directional edges are created. So the work per insert is dominated by the internal search and the size of the candidate list—hence efConstruction directly drives build cost.

Practical settings

In practice, efConstruction is set high enough that the graph has good connectivity (e.g. 100–500 or more for high recall), and build is either run offline or amortized over incremental inserts. For batch builds, 200–500 is common when recall is critical; for real-time or incremental ingestion, lower values (e.g. 64–128) keep insert latency manageable at some cost to index quality.

For very large builds, parallelizing construction helps; tuning efConstruction is then a trade-off between build throughput and final index quality. If you have a fixed build-time budget, reduce efConstruction until build fits the window, then compensate with a higher efSearch at query time if recall drops.

Trade-offs and practical tips

Trade-off summary: efConstruction buys index quality at the cost of build time. Too low and the graph is suboptimal; too high and builds become slow without much extra gain. Practical tip: run a small grid over efConstruction (e.g. 100, 200, 400) and measure recall and build time; pick the value where recall levels off or meets your target and build time is acceptable. For incremental building, use a lower efConstruction and plan to tune efSearch for query.