SPIN: Cache-Efficient Graph Nearest Neighbor Search

Approximate nearest-neighbor (ANN) search is widely employed in numerous fields that require combing through large databases for relevant information in response to a particular query. Graph-based algorithms, such as Hierarchical Navigable Small World (HNSW), have become dominant tools for ANN searches. However, query costs in these graphs are dominated by irregular memory accesses, which cause frequent cache misses, leading to higher latency and lower throughput. Coleman et al. (Neurips 2022) remedies this by optimizing the memory layout of nodes while keeping the edge set intact. We ask whether the graph's structural properties provide an orthogonal mechanism for addressing this issue. The bottom layer of a dense HNSW graph exhibits heavy inherent degree skew, and because of its hierarchical nature, many edges in this layer are redundant and rarely traversed. We exploit this by applying a geometry-based sparsifier that prunes the bottom-layer edges following a fixed budget while retaining each node's geometrically nearest neighbors with high probability and preserving a close-to-dense recall. The sparsified index is then partitioned and reordered in memory, ensuring that co-visited nodes are placed in contiguous memory blocks. Across scales, the combined pipeline provides a formal guarantee that scaling the search effort by a constant returns a close-to-dense result with high probability. When combined with the sparsified cache-aware layout, the method reduces memory traffic and improves performance.