Defining “efSearch” and its impact on query speed

What efSearch does at query time

During an HNSW query, the search maintains a dynamic list of the best candidates seen so far—typically a priority queue ordered by distance to the query. The maximum size of this list is efSearch. At each step, the algorithm expands neighbors of the current best candidates and adds them to the queue, then keeps only the top efSearch by distance. When the search moves to a lower layer or terminates, the top-k results are taken from this candidate set. So efSearch directly controls how much of the graph is explored: larger values mean more nodes are considered and recall tends to go up, at the cost of more distance computations and heap operations.

efSearch does not change the index structure; it only affects the query algorithm. So you can build the index once and vary efSearch per request or per deployment to balance recall and latency.

Query-time only

Unlike efConstruction, efSearch does not affect index build—only query time. So you can build once with high efConstruction for a good graph, then at query time choose efSearch based on whether you need maximum recall (e.g. 500–1000) or low latency (e.g. 64–128). Many systems allow changing efSearch per query or per tenant without rebuilding the index.

This makes efSearch ideal for multi-tenant or mixed workload scenarios: strict latency SLAs can use a lower efSearch; batch or offline jobs can use a higher value for better recall.

Pipeline: search and candidate list

The query pipeline starts at an entry point (often on the top layer), then at each layer the algorithm greedily moves to the best neighbor and expands the candidate set. The candidate list is capped at efSearch. When no better neighbor is found on the current layer, the search steps down to the next layer and continues. On the bottom layer, expansion continues until the search terminates (e.g. when the best candidate cannot be improved); the top-k are then returned from the efSearch-sized candidate set. So the size of that set controls how many nodes are ever considered and thus recall and latency.

Choosing efSearch

The rule of thumb is efSearch ≥ k (the number of neighbors requested); often efSearch is set to a multiple of k (e.g. 2–10×) to get stable recall. If efSearch is smaller than k, you cannot return k neighbors. In practice, 2×k to 10×k is common; very high recall requirements may need efSearch in the hundreds or more.

The recall–latency trade-off in HNSW is largely controlled by this parameter, along with M and the quality of the graph built with efConstruction. A well-built graph (high efConstruction) often needs a lower efSearch for the same recall, because the links are better and the search finds good candidates sooner.

Trade-offs and practical tips

Trade-off summary: efSearch trades recall for latency and temporary memory. Higher efSearch improves recall and reduces variance across queries but increases per-query cost. Practical tip: plot recall@k and latency (e.g. p50, p99) for a range of efSearch values on your data; pick the smallest efSearch that meets your recall target so that latency and throughput stay within budget. For real-time APIs, start with a conservative efSearch (e.g. 64–128) and increase only if recall is insufficient.