Search a graph with a bounded candidate frontier

In the original HNSW construction, every item appears in the base layer, while progressively fewer items appear in higher layers according to randomly assigned maximum levels. Search begins from an entry point at the top and descends through the hierarchy. Upper-layer greedy moves provide a coarse route across the space. At the bottom, a candidate frontier permits more exploration than following only the single nearest currently visible neighbor. These are graph layers over stored points, not IVF centroid cells.

A strict greedy descent stops when every neighbor of the current point looks worse, even if a path through a slightly worse intermediate point leads to a much better answer. HNSW’s base-layer search retains alternatives to reduce that failure. However, it still examines a bounded portion of the graph under a heuristic stopping rule. Its empirical speed and recall are not an unconditional logarithmic worst-case bound or a proof that every dataset has navigable links.

In hnswlib 0.8.0, ef controls the dynamic list used during search and must be at least k, the requested neighbor count. Larger ef generally trades more query work for better recall; it does not mean exactly ef distance computations. Neighbor expansions, duplicate visits avoided by a visited set, hierarchy traversal, filters, and implementation stopping conditions all influence work. Faiss exposes the related search control as efSearch; do not transfer parameter values between libraries as if they implied identical traversal.

Choose k because the application needs that many unique eligible results, then tune the exploration setting to meet a measured recall target. If the graph or eligible population cannot supply k results, increasing the array size does not create missing neighbors. Different libraries may return sentinels or raise errors for insufficient results. Keep that behavior visible in evaluation and distinguish a short list from a complete list whose IDs are wrong.

A useful diagnostic records the exact nearest document, whether it was visited, and where it fell in the approximate results. If it was visited but lost after scoring, inspect the representation or tie policy. If it was never visited, inspect routing and graph construction. Increasing ef on the same frozen graph helps isolate search-budget effects; rebuilding with different construction parameters tests a different hypothesis and should be reported separately.

Queries in sparse regions or unusual clusters can need more exploration than dense mainstream queries. Measure latency distributions and recall by meaningful slices rather than assuming one average describes all routes. Record the implementation version, graph checksum, entry-point state, query metric, and search parameters with each run. Those details turn an attractive single benchmark number into an experiment another engineer can reproduce, including difficult misses rather than only successful paths.