acceptodds
Under review as a conference paper at ICLR 2027

SPIN: Cache-Efficient Graph Nearest Neighbor Search

Abstract

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.

Primary area:
infrastructure, software libraries, hardware, systems, etc.
Keywords:
Nearest Neighbor Search, Cache Efficient

Reviews

Among:
Shape:
1234this paper, Bottom 27%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 2.00 over 3 reviews, above 27% of the others.
Reviewer_1GvBOpenReview ↗
Rating
3
Confidence
2
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

This paper addresses the cache miss issue in graph-based approximate nearest neighbor search caused by irregular memory accesses, proposing SPIN, a cache-efficient indexing method. The method involves two steps: geometry-aware distance-biased sparsification of the bottom graph layer to reduce the search working set, followed by cluster-aware memory reordering to improve spatial locality. The paper provides theoretical guarantees on search quality and cache efficiency, and validates on three real-world datasets that the method significantly improves throughput over existing cache-aware methods with minimal recall loss.

Critical strengths

S1. This paper is well-motivated, it addresses cache issues via inherent graph sparsity provides an orthogonal complement to existing pure memory layout optimization methods, with smooth writing logic.

S2. This paper involves theoretical bounds under the ideal cache model for path stretch and cache misses induced by sparsification, demonstrating the feasibility of tuning via a single parameter.

Critical weaknesses

W1. Deviation between theoretical assumptions and real-world retrieval scenarios.

W2. Incomplete experimental baseline comparisons, lacking direct comparison with frontier system-level optimizations.

Detailed comments

D1. The theoretical proof relies on the assumption of minimal change in the reachable set, and the derivation of path stretch bounds uses idealized query distributions and edge utilization estimates. In real-world high-dimensional vector retrieval, data distributions are often long-tailed. The robustness of these bounds under extreme queries is insufficiently validated, failing to fully discuss the practical impact of sparsification on the recall of long-tail or hard queries.

D2. The compared methods are mainly limited to traditional graph reordering techniques and native indexes. The field currently has numerous system-level works optimized for cache and memory bandwidth. The lack of comparison with recent frontier graph search systems combining vector quantization or hardware instruction set optimizations makes it difficult to fully evaluate the practical engineering value of this method on modern hardware.

Questions for authors

Q1. Do the theoretical bounds of the method still hold under extreme long-tail queries or highly skewed data distributions? Please provide relevant empirical data or supplementary analysis to support its robustness.

Q2. For datasets with different characteristics, do the sparsification ratio and the candidate set size multiplier require manual tuning? Can a data-driven adaptive parameter selection mechanism be provided, rather than relying on a global fixed strategy?

Q3. Suggestion for future work: It is recommended to supplement comparative experiments with recent graph search systems that combine vector quantization or hardware instruction set optimizations in future versions, to further demonstrate the comprehensive advantages of the method on modern hardware architectures.

Q4. Other questions mentioned in Weakness part.

Reviewer_PrNtOpenReview ↗
Rating
1
Confidence
4
Informativeness
1
Presentation
1
Soundness
1
Read review
Paper summary

This paper proposes SPIN, a post-processing step for an HNSW index. First, it randomly deletes layer-0 edges with probability proportional to edge length, with an expected deletion budget α. Second, it partitions the sparsified layer-0 graph with METIS into cache-sized clusters and stores each cluster contiguously. The paper gives three informal results: a bound on the expected stretch of deleted edges, a probability bound that searching with ef multiplied by γ returns a result at least as good as the dense graph, and an ideal-cache bound on misses in terms of cross-cluster transitions.

Critical strengths

S1. Cache behavior of graph-based ANN search is a practical problem.

S2. The paper reports detailed hardware counters instead of wall-clock time alone. Code is available in an anonymous repository.

Critical weaknesses

W1. The comparison is not fair. The speedup is reported at the same ef, but at that setting SPIN already has lower recall, and lower recall is always faster. When the recall is matched (Fig. 3b), SPIN's throughput actually drops below the dense HNSW in Fig. 1, so the main claim is not supported.

W2. The abstract promises a formal guarantee, but I could not find one in the paper. The theorems depend on terms that are never worked out, and the paper itself leaves them for future work, so it is unclear what is actually guaranteed.

W3. Only dense HNSW, Gorder and Porder are compared. Other graph indexes (e.g., NSG, Vamana/DiskANN), HNSW with a smaller M, and other recent memory-efficient methods are missing, so it is hard to judge how good SPIN really is.

W4. The largest dataset has only 1M vectors, which is small for a paper about cache efficiency. All three datasets are text embedded with the same model, standard ANN benchmarks (e.g., SIFT, GIST, Deep) are not used, and only single-thread search is tested.

W5. The citations are used carelessly. Many papers are piled into one bracket; some do not match the sentence they support (e.g., OdinANN, an insert-focused system, is cited for distributed search, and filtered-ANN papers are cited as "more performant search methods"), and several references contain leftovers such as "ISBN null" and "ID: 1".

W6. Some statements contradict each other. Sec. 2.2 says SPIN needs no profiling data, but Sec. 3.1 and Sec. 4 use profiling queries. α is 0.3 in one place and 0.2 in another. The text says SPIN beats both ablation variants on all cache metrics, but Table 2 shows otherwise at 500K.

W7. The abstract contains a citation and spends half its length on background without giving any results. The introduction and related work are merged into one section, the contributions are vague about what is new compared with Coleman et al. (2022), and there are a number of typos.

Questions for authors
  1. Can you show QPS–recall curves for all methods? At the same recall as dense HNSW, is SPIN still faster? From Fig. 3b, it looks slower.

  2. How does SPIN compare with HNSW built with a smaller M, and with Gorder or Porder applied to the sparsified graph?

  3. In Theorem 3.2, how should γ be chosen in practice, and what does the theorem guarantee if δ(γ) and ρ_γ are unknown?

  4. Which α is used in the main experiments, 0.3 or 0.2? And why are the Dense numbers in the last block of Table 9 different from the other blocks?

Reviewer_E1BcOpenReview ↗
Rating
2
Confidence
3
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

SPIN aims to improve the cache efficiency of HNSW search. It first removes edges from the bottom layer, with longer edges more likely to be removed. It then uses METIS to group connected points and stores points in the same group together. The authors analyze changes in search results and cache misses. Experiments on three text retrieval datasets compare SPIN with standard HNSW and two existing methods for reordering graph data in memory.

Critical strengths

(1) The method reduces the number of edges examined and changes how graph data is stored in memory. Both changes can affect search time. The paper measures cache accesses, cache misses, and distance computations. These measurements help explain the observed speed improvements instead of reporting query speed alone.

(2) The experiments test edge removal and memory reordering separately. They also compare removal based on edge length with random removal. These comparisons help show what each part contributes. Results at three dataset sizes provide useful evidence that the effects are not limited to one graph size.

Critical weaknesses

(1) The reported 30 to 36 percent speed improvement is not measured at the same recall. The main comparison uses equal efef, but SPIN returns fewer correct neighbors. The authors acknowledge this and increase γ\gamma to recover recall. However, Figure 3b does not compare all methods at the recovered recall, and increasing γ\gamma reduces SPIN's speed. It is therefore unclear how much of the reported speed improvement remains when the methods return equally accurate results.

(2) The search guarantee depends on two quantities whose values are not given for the tested settings. One concerns search missing the desired point despite a short path. The other concerns how much extra path length a larger search budget can handle. The paper defines them, but does not show how their values change with γ\gamma. As a result, the theorem does not tell the reader how much extra search is needed to keep the same result quality.

Questions for authors

(1) How do SPIN, standard HNSW, Gorder, and Porder compare at the same Recall@10? Please let each method use the efef value it needs and report query speed across the same recall range. This would show whether SPIN remains faster after its recall loss is recovered.

(2) For the graphs used in the experiments, what probability does Theorem 3.2 give for returning the same point or a closer point? Please provide numerical values at different γ\gamma settings and explain how the quantities in the theorem are obtained. This would show whether the guarantee can help choose γ\gamma.

(3) How does SPIN compare with an HNSW index built with smaller MM, so that it starts with fewer neighbors per point? Please compare at similar graph size and recall, and include the time spent removing edges, running METIS, and reordering memory. This would test whether the additional steps improve on a simpler choice.

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Loading the map…

Discussion (0)

Sign in to comment.