Build useful routes instead of only short edges

The original HNSW neighbor-selection heuristic considers relationships among candidates, rather than simply taking the closest candidates to the inserted point. A candidate that offers a direction already well covered by a selected neighbor can be pruned in favor of another route. This encourages useful inter-region links, especially for clustered data. It is a heuristic with implementation details, not a guarantee that every cluster has a bridge or that each node has the same degree.

A small one-dimensional example makes the issue concrete. From a new point at zero, candidates near one and two are individually closer than a candidate at minus nine. A nearest-two rule spends both links on the same direction and nearby group. A diversity test can reject the point at two because it is even closer to the point at one than to the insertion point, leaving room for a candidate in the opposite direction. Geometry between candidates matters, not just their independent distances to the insertion.

hnswlib 0.8.0 distinguishes M, which influences connection count and memory, from ef_construction, which controls candidate exploration while building. A larger construction frontier can find more useful neighbors before pruning, at greater build cost. Search-time ef explores the already constructed graph. Tuning those parameters answers different questions, so preserve separate records for build duration, peak memory, graph size, and the later recall-latency curve.

Insertion order, level sampling, and parallel scheduling can affect the resulting graph. A fixed random seed helps define an experiment but does not automatically establish byte-identical graphs across all parallel executions or library versions. Save the actual built artifact when reproducibility matters. Compare several construction runs when measuring variability, and retain a held-out query set so the graph is not judged solely on queries used to select its build parameters.

Degree distributions and connected-component checks reveal failures that a single recall number can hide. A connected graph can still have poor greedy routes, so connectivity is necessary for some traversal guarantees but insufficient for fast high-recall navigation. Conversely, a disconnected component is unreachable from an entry point confined to another component regardless of how often the same local walk repeats. Examine difficult clusters and compare visited nodes with exact neighbors before attributing every miss to insufficient query budget.

A rebuild decision should connect an observed failure to a mechanism. If recall improves sharply when query effort rises, the graph may be adequate but underexplored. If a broad effort sweep plateaus on the same slice, inspect missing bridges, deletions, duplicates, and changes in the embedding distribution. Building a fresh graph with improved construction settings can test that hypothesis. Report the extra build and memory costs alongside any faster queries, because the system pays for both phases.