HNSW Heuristic Search & Routing

Heuristic Neighbor Selection and Greedy Routing constitute the algorithmic backbone of HNSW's connectivity and precision; during edge construction, a shrinking neighborhood heuristic selects diverse neighbors spanning broad geometric angles while pruning candidates closer to existing neighbors than to the base node, synthesizing a Relative Neighborhood Graph (RNG); during querying, a beam search over a dynamic priority queue of capacity `efSearch` guarantees fast convergence to true Top-K nearest neighbors.

Performance tuning of vector databases, balancing parameters $M$ (max links per node), $efConstruction$ (build-time queue depth), and $efSearch$ (query-time candidate queue) for latency-recall trade-offs.

Naive nearest neighbor selection forms tight localized cliques with clustered, redundant edges, creating search traps and isolated islands; the heuristic selection forces directional divergence, ensuring global navigable paths across all dimensional orientations.

Detail the anti-isolation mechanism of `keepPrunedConnections` in HNSW heuristic neighbor selection?

Analyze how $M$ (16-64) and $efConstruction$ (100-400) impact index construction time and memory footprint non-linearly?

Describe the typical empirical curve of Recall@10 vs QPS throughput as $efSearch$ scales from 16 to 256?

Why is dynamic node deletion in HNSW notoriously hard? Explain soft tombstones and graph repair reconnection?

How does fine-grained node-level read/write locking ensure thread safety during concurrent vector ingestion?