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:
- 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.
- 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.
- 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.
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%.
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