Many candidates assume increasing ef at query time always improves recall with only a linear latency cost. What's misleading about that assumption?

The assumption has two parts, and both are misleading. The first part is that recall always improves with ef. In practice, recall vs ef is a concave curve that saturates: on most datasets, recall rises steeply from ef=16 to ef=128, then flattens, and beyond ef=256 the gain is often fractions of a point. The saturation point depends on the intrinsic dimensionality of the data and on how well the graph is built (m, ef_construct). Once the traversal has visited the entire relevant region of the graph, more ef does not find anything new. The second part is that latency grows linearly with ef. In a compute-bound regime, the number of distance computations does scale roughly linearly with ef, so latency grows roughly linearly. But in a memory-bound or cache-bound regime, higher ef means more nodes visited, which means more cache misses, which means latency grows faster than linearly. And when a filter is present, the picture changes: the filter-aware traversal has to explore more of the graph to find enough matching points, so the effective cost grows with the filter's selectivity. At very high ef with a selective filter, the traversal can approach a full scan, and the latency curve becomes steep.

The mechanism that produces the saturation is that HNSW is a greedy best-first search over a graph. The search terminates when the candidate list is exhausted - that is, when no unexplored neighbor is closer than the current worst result. Increasing ef makes the candidate list larger, which means the search explores more of the graph before terminating. But the graph has a finite number of nodes, and the relevant region for a query is bounded. Once the search has explored the entire connected region around the query, more ef only adds nodes that are farther away and do not change the top-k. This is why recall saturates. The mechanism that produces the non-linear latency is that higher ef visits more nodes, and each node visit has a cache cost. If the graph fits in cache, the cost per visit is low and latency grows roughly linearly. If the graph does not fit, each visit is more likely to miss the cache and pay a memory latency, so the cost per visit grows with the working set. The interaction with filters is that the filter reduces the fraction of visited nodes that are candidates, so the search must visit more nodes to find the same number of results, which amplifies both effects.