Graph Reordering for Cache-Efficient Near Neighbor Search

Benjamin Coleman, Santiago Segarra, Alex Smola, Anshumali Shrivastava

In modern machine learning, finding the "closest" items in a massive dataset—known as Near Neighbor Search (NNS)—is a foundational task for recommendation systems, search engines, and generative AI retrievers. Currently, graph-based methods like the Hierarchical Navigable Small-World (HNSW) graph are the gold standard. These algorithms work by performing a "greedy walk" across a graph to find the closest point to a query.

However, this traversal hides a significant performance bottleneck: memory latency. When the algorithm jumps from one node to another, those nodes might be stored far apart in physical RAM. This causes "cache misses," forcing the CPU to wait hundreds of cycles to fetch data from main memory. In fact, roughly 40% of query time in HNSW is spent simply waiting for memory fetches.

To address this, researchers propose treating graph traversal as a cache hit maximization task. By reordering how graph nodes are stored in memory—a technique called graph reordering—systems can achieve up to a 40% reduction in query latency with negligible preprocessing overhead.

Optimizing Memory Layouts

The core idea is to group commonly accessed nodes together in memory so that fetching one node inherently fetches its likely neighbors into the CPU cache. The researchers explored three main approaches to reordering nodes:

  1. Gorder (Graph-order): An existing state-of-the-art method that groups nodes based on "neighbor overlap." If two nodes share many neighbors, they are placed close together in memory.
  2. Corder (Cache-order): A novel objective that directly optimizes a theoretical lower bound for cache efficiency. It evaluates "triplets" of nodes to minimize the cost of exploring a local neighborhood.
  3. Porder (Profile-order): A profile-guided approach. By running a small number of real queries first, the algorithm identifies which edges are traversed most frequently. It then prioritizes placing these "high-traffic" connected nodes together.

Key Insights

Structure Matters More Than Sorting: Simple heuristics, like sorting nodes by their degree (how many connections they have), do not consistently improve performance. Effective reordering must account for specific local connectivity.

Hot Zones in Graphs: The success of the Porder method reveals that graph traversal is not uniform. Certain "highway" nodes and edges are used much more often than others. Optimizing the layout for these specific paths yields better results than a query-agnostic approach.

The "Large Node" Challenge: In many standard graph problems, a single node fits neatly into a cache line. In NNS, however, a single high-dimensional vector can span multiple cache lines. Reordering remains highly effective here because it assists hardware prefetchers—the CPU's built-in logic that anticipates and fetches the data you will need next.

Negligible Overhead: One of the most practical findings is that reordering a graph takes mere minutes, whereas building the initial HNSW index can take hours.

Reordering Time vs Graph Construction

As illustrated above, the time required to apply reordering algorithms is orders of magnitude lower than the initial graph construction, making it a highly practical optimization for production systems.

Performance Results

The study evaluated these methods on several large-scale, standard benchmarks for vector search, including SIFT100M, DEEP100M, and GIST1M. The results demonstrated substantial improvements across the board:

  • Speedup: Graph reordering improved mean query latency by up to 40% on large datasets like SIFT100M.
  • Tail Latency: The 99th percentile (P99) latency, which is crucial for maintaining responsive real-time web services, improved by 20%.
  • Cache Efficiency: On the SIFT100M dataset, Gorder reduced L1 cache misses from ~19.5% to ~14.5% and L3 misses from 6.5% to 4.0%.
Speedup vs Recall on SIFT100M

Importantly, the performance gains remain consistent across different levels of recall (accuracy). Whether a system is configured for a rapid, approximate search or a highly accurate one, memory layout optimization provides a reliable speedup.

Limitations and Future Work

While graph reordering offers a "free lunch" for many NNS applications, there are limitations. The relative speedup decreases as the dimensionality of the vectors increases; if a single vector is so large that it dominates the cache, there is less room to benefit from co-locating its neighbors. Additionally, the effectiveness of reordering is tied to the specific hardware prefetcher and cache hierarchy of the CPU (tested primarily on Intel Xeon processors).

Finally, the current research focuses on static indices. Future work will need to explore how to maintain an efficient memory layout dynamically as new points are continuously added to live, streaming graph indices.

Summary updated

Abstract

Graph search is one of the most successful algorithmic trends in near neighbor search. Several of the most popular and empirically successful algorithms are, at their core, a greedy walk along a pruned near neighbor graph. However, graph traversal applications often suffer from poor memory access patterns, and near neighbor search is no exception to this rule. Our measurements show that popular search indices such as the hierarchical navigable small-world graph (HNSW) can have poor cache miss performance. To address this issue, we formulate the graph traversal problem as a cache hit maximization task and propose multiple graph reordering as a solution. Graph reordering is a memory layout optimization that groups commonly-accessed nodes together in memory. We mathematically formalize the connection between the graph layout and the cache complexity of search. We present exhaustive experiments applying several reordering algorithms to a leading graph-based near neighbor method based on the HNSW index. We find that reordering improves the query time by up to 40%, we present analysis and improvements for existing graph layout methods, and we demonstrate that the time needed to reorder the graph is negligible compared to the time required to construct the index.
BibTeX
@inproceedings{coleman2022graph,
  author = {Benjamin Coleman and Santiago Segarra and Alex Smola and Anshumali Shrivastava},
  title = {{Graph Reordering for Cache-Efficient Near Neighbor Search}},
  booktitle = {Advances in Neural Information Processing Systems},
  year = {2022},
  url = {https://openreview.net/forum?id=8LeCgKb6UX},
}
Figure