Co-Designing Graph-based Approximate Nearest Neighbor Search at Billion Scale for Processing-in-Memory
Sitian Chen 1 , Yusen Li 2 , Yao Chen 3 , Minwen Deng 4 , Jintao Meng 5 , Amelie Chi Zhou 1 · 2026
Read Co-Designing Graph-based Approximate Nearest Neighbor Search at Billion Scale for Processing-in-Memory by Sitian Chen 1 , Yusen Li 2 , Yao Chen 3 , Minwen Deng 4 , Jintao Meng 5 , Amelie Chi Zhou 1 (2026) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2605-25522.txt.
Introduction
Sitian Chen and five colleagues co-design graph nearest neighbor search for processing-in-memory hardware at billion scale. Graph traversal is memory-bound, with irregular accesses capping CPU throughput, while GPUs lack memory for large indexes. Their design compacts the index to shrink the footprint more than fourteenfold. An asynchronous pipeline keeps host transfers saturated, and a multiplication-free kernel loses under a tenth of a percent recall. Across three benchmarks it reaches 20 times CPU and 17 times GPU throughput, beating PIM accelerators 129 times over at high recall.
Catalog record
| CREATOR | Sitian Chen 1 , Yusen Li 2 , Yao Chen 3 , Minwen Deng 4 , Jintao Meng 5 , Amelie Chi Zhou 1 |
|---|---|
| YEAR | 2026 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 53584 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2605.25522
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
Co-Designing Graph-based Approximate Nearest Neighbor Search at Billion Scale for Processing-in-Memory Sitian Chen 1 , Yusen Li 2 , Yao Chen 3 , Minwen Deng 4 , Jintao Meng 5 , Amelie Chi Zhou 1 Abstract Approximate Nearest Neighbor Search (ANNS) is a core primitive in modern AI systems, and graph-based methods currently offer the best accuracy–efficiency trade-off at scale. The workload is fundamentally memory-bound: graph traversal produces frequent, irregular memory accesses that cap CPU throughput at main-memory bandwidth, while GPUs lack the high-bandwidth memory capacity to host billion-scale indexes. Processing-in-Memory (PIM) is a natural candidate, as placing computation next to data unlocks the abundant internal bandwidth that such bandwidth-starved workloads demand. Porting graph-based ANNS to PIM, however, exposes several architectural mismatches: each processing unit has only a small local memory, inter-unit communication is costly, host coordination adds overhead, and in-memory compute units are relatively weak—limitations that have forced prior PIM-based ANNS designs to fall back on cluster-based indexing, whose recall ceiling is far below that of graph methods. This paper presents an algorithm–architecture co-design that overcomes these obstacles through three components: a compacted index layout that shrinks the PIM-resident memory footprint by 14.5×; an asynchronous pipelined scheduler that keeps the host-to-PIM interconnect saturated; and a multiplication-free distance kernel that loses under 0.08% recall. Across three billion-scale benchmarks, the proposed design achieves up to 20× and 17.1× higher throughput than CPU and GPU baselines, respectively, outperforms prior PIM accelerators by 129× in the high-recall regime, and scales gracefully across multi-node deployments and emerging PIM architectures. 4 Tencent , 5 Shenzhen Institutes of Advanced Technology I Introduction Approximate Nearest Neighbor Search (ANNS) is a foundational primitive for large-scale AI services, including retrieval-augmented generation (RAG) [ 36 , 7 , 11 ] , and recommendation systems [ 53 , 55 ] . Given a high-dimensional query vector, ANNS retrieves the top- k most similar vectors from a massive database while trading a small amount of accuracy for orders-of-magnitude efficiency gains. Among the major ANNS families (hash-based [ 62 , 18 ] , cluster-based [ 42 , 25 , 8 , 4 ] , graph-based [ 19 , 56 , 63 , 15 , 5 , 54 ] ), graph-based methods have received extensive attention in both academia and industry due to their superior expected search accuracy and efficiency trade-offs. Limitation of Existing Architectures. Despite algorithmic advances, graph-based ANNS on conventional architectures are fundamentally bottlenecked by the “memory wall.” To quantify this effect, we perform a roofline analysis of representative graph-based ANNS methods using the SIFT dataset and a CPU platform (2 \times Intel Xeon Gold 6330). As shown in Figure 1 , the results indicate that these state-of-the-art methods, including HNSWlib [ 35 ] , NDSearch [ 56 ] , and SymphonyQG [ 19 ] , lie firmly in the memory-bound region, struggling to effectively utilize available compute resources. CPUs are constrained by limited memory bandwidth (e.g., 375 GB/s on CPUs), while GPUs, despite offering higher bandwidth (e.g., 2.0 TB/s on an A100), are severely limited by global memory capacity—a full SymphonyQG index for billion-scale datasets exceeds 1.25 TB, far beyond what GPU HBM can accommodate. Fig. 1 : Roofline Analysis of graph-based ANNS on SIFT. Opportunities of PIM. To bridge this gap, Processing-in-Memory (PIM) has emerged as a promising architecture. Modern PIM systems (e.g., UPMEM PIM [ 17 ] , Samsung PIM-HBM [ 32 ] , and SK Hynix AiM [ 33 ] ) embed lightweight processing units (PUs) directly inside memory banks. By co-locating computation with data, PIM enables massive internal memory bandwidth (e.g., 2 TB/s aggregate on UPMEM) and minimizes costly data movement across the memory hierarchy, making it particularly attractive for memory-bound, irregular workloads like graph traversal. Unlike custom accelerator designs [ 60 , 30 , 50 , 58 ] , commodity PIM modules ship as standard DIMM form-factor devices, enabling practical deployment without system redesign. However, existing PIM-based ANNS accelerators [ 8 , 4 , 57 ] predominantly rely on simpler, cluster-based algorithms (e.g., IVF-PQ), which inherently suffer from lower search quality and hit a capability ceiling at low recall levels (e.g., {\sim} 61% on SIFT1B). Challenges. While PIM’s massive internal bandwidth makes it appear well suited for memory-bound workloads, directly mapping graph-based ANNS onto PIM exposes a fundamental algorithm–architecture mismatch that manifests as four tightly coupled challenges (detailed analysis in Section II-C ): 1 Extreme Local Memory Capacity: PU-private memory is severely limited (e.g., 64 MB per UPMEM DPU), yet billion-scale graph indexes exceed 1.25 TB, forcing aggressive partitioning. 2 Inter-PU Communication: Fine-grained partitioning causes frequent cross-PU traversals over external bandwidth paths that are > 10 \times slower than internal bandwidth. 3 Coordination Overhead and Load Imbalance: Existing batch-synchronous [ 9 , 3 , 8 , 4 ] and per-query [ 57 ] scheduling strategies either waste PU cycles on synchronization barriers or fragment communication bandwidth. 4 Restricted PU Compute: PIM cores feature weak arithmetic capabilities and in some cases lack hardware multipliers (e.g., UPMEM), resulting in disproportionate cost for the remaining floating-point operations in quantization-based distance kernels. Overcoming these coupled challenges requires a holistic algorithm–hardware co-design. Innovations. To overcome these architectural constraints, we propose PIMCQG, a holistic algorithm–hardware co-design framework that enables high-performance, high-recall graph-based ANNS on commodity PIM platforms. Rather than applying isolated software patches, PIMCQG realigns the entire system stack—data layout, scheduling, and computation—with PIM architectural constraints through three synergistic innovations: 1 PIM-Friendly Compact Index: We eliminate redundant per-edge quantization metadata via IVF-style clustering and offload exact similarity reranking to the host CPU. This reduces the PIM-resident index footprint by up to 14.5\times (e.g., from 2,385 GB to 164 GB on SSN1B dataset [ 13 ] ), dramatically easing capacity limits ( Challenge 1 ) and cross-PU communication pressure ( Challenge 2 ) (Section IV-A ). 2 Asynchronous Pipelined Scheduling: We decouple host-side query dispatch and post-processing from in-PIM search through dynamic mini-batching and FIFO-based asynchronous execution. By overlapping communication, search, and reranking, this design mitigates coordination overhead and load imbalance ( Challenge 3 ) while fully utilizing host–PIM bandwidth (Section IV-B ). 3 Multiplication-Free Distance Computation: On observing that the quantization-error scaling factor \cos(\theta) is empirically stable within each IVF cluster, we replace the expensive per-node floating-point multiplication with a cluster-wide constant approximated via bitwise shifts and additions, achieving a fully multiplication-free in-PIM distance kernel with < 0.08% recall loss ( Challenge 4 ) (Section IV-C ). Evaluation. We evaluate PIMCQG on a real-world UPMEM PIM server across three industry-standard billion-scale datasets. Our results demonstrate three key advantages over state-of-the-art baselines: 1) Performance: PIMCQG delivers up to 20\times and 17.1\times throughput speedups over CPU-based SymphonyQG and GPU-based GGNN, respectively. Furthermore, unlike prior PIM-based ANNS solutions that hit a capability ceiling at low recall levels, PIMCQG successfully scales to high-recall targets, achieving up to 129\times speedup at comparable recall boundaries. 2) Energy Efficiency: PIMCQG provides up to 6.5\times and 30.8\times improvement in energy efficiency (QPS/Watt) compared to CPU and GPU baselines, demonstrating the power of PIM for large-scale ANNS. 3) Scalability: PIMCQG maintains its performance advantages when scaling to multi-node configurations and different commodity PIM platforms (Samsung PIM-HBM, SK Hynix AiM), showing its generality and practical deployment potential. II Background and Motivation II-A