# UpANNS: Enhancing Billion-Scale ANNS Efficiency with Real-World PIM Architecture

arXiv: https://arxiv.org/abs/2410.23805 · HTML: https://mlsanity.com/paper/2410.23805/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Placed in Vector search and ANN indexes, one of 15 directions in Retrieval-augmented generation.
- Builds on 22 of its 51 references that are in the map.
- First posted on arXiv 31 Oct 2024.

## Placed in

- Retrieval-augmented generation / [Vector search and ANN indexes](https://mlsanity.com/rag/vector-search-and-ann-indexes/)

## Builds on (most cited first, 22 of 22)

- [Billion-scale similarity search with GPUs](https://mlsanity.com/paper/1702.08734/) (2017)
- [Efficient and robust approximate nearest neighbor search using Hierarchical Navigable Small World graphs](https://mlsanity.com/paper/1603.09320/) (2016)
- [Generalization through Memorization: Nearest Neighbor Language Models](https://mlsanity.com/paper/1911.00172/) (2019)
- [Actions Speak Louder than Words: Trillion-Parameter Sequential Transducers for Generative Recommendations](https://mlsanity.com/paper/2402.17152/) (2024)
- [Practical and Optimal LSH for Angular Distance](https://mlsanity.com/paper/1509.02897/) (2015)
- [PQCache: Product Quantization-based KVCache for Long Context LLM Inference](https://mlsanity.com/paper/2407.12820/) (2024)
- [In-context Pretraining: Language Modeling Beyond Document Boundaries](https://mlsanity.com/paper/2310.10638/) (2023)
- [High-Dimensional Approximate Nearest Neighbor Search: with Reliable and Efficient Distance Comparison Operations](https://mlsanity.com/paper/2303.09855/) (2023)
- [ParlayANN: Scalable and Deterministic Parallel Graph-Based Approximate Nearest Neighbor Search Algorithms](https://mlsanity.com/paper/2305.04359/) (2023)
- [Chameleon: a Heterogeneous and Disaggregated Accelerator System for Retrieval-Augmented Language Models](https://mlsanity.com/paper/2310.09949/) (2023)
- [Approximate Nearest Neighbor Search under Neural Similarity Metric for Large-Scale Recommendation](https://mlsanity.com/paper/2202.10226/) (2022)
- [Pathfinding Future PIM Architectures by Demystifying a Commercial PIM Technology](https://mlsanity.com/paper/2308.00846/) (2023)
- [HD-Index: Pushing the Scalability-Accuracy Boundary for Approximate kNN Search in High-Dimensional Spaces](https://mlsanity.com/paper/1804.06829/) (2018)
- [Co-design Hardware and Algorithm for Vector Search](https://mlsanity.com/paper/2306.11182/) (2023)
- [Adaptive Estimation for Approximate k-Nearest-Neighbor Computations](https://mlsanity.com/paper/1902.09465/) (2019)
- [JUNO: Optimizing High-Dimensional Approximate Nearest Neighbour Search with Sparsity-Aware Algorithm and Ray-Tracing Core Mapping](https://mlsanity.com/paper/2312.01712/) (2023)
- [NDSEARCH: Accelerating Graph-Traversal-Based Approximate Nearest Neighbor Search through Near Data Processing](https://mlsanity.com/paper/2312.03141/) (2023)
- [PIM-Opt: Demystifying Distributed Optimization Algorithms on a Real-World Processing-In-Memory System](https://mlsanity.com/paper/2404.07164/) (2024)
- [UpDLRM: Accelerating Personalized Recommendation using Real-World PIM Architecture](https://mlsanity.com/paper/2406.13941/) (2024)
- [Accelerating Large-Scale Graph-based Nearest Neighbor Search on a Computational Storage Platform](https://mlsanity.com/paper/2207.05241/) (2022)
- [Proxima: Near-storage Acceleration for Graph-based Approximate Nearest Neighbor Search in 3D NAND](https://mlsanity.com/paper/2312.04257/) (2023)
- [SwiftRL: Towards Efficient Reinforcement Learning on Real Processing-In-Memory Systems](https://mlsanity.com/paper/2405.03967/) (2024)

## Abstract (arXiv)

Approximate Nearest Neighbor Search (ANNS) is a critical component of modern AI systems, such as recommendation engines and retrieval-augmented large language models (RAG-LLMs). However, scaling ANNS to billion-entry datasets exposes critical inefficiencies: CPU-based solutions are bottlenecked by memory bandwidth limitations, while GPU implementations underutilize hardware resources, leading to suboptimal performance and energy consumption. To address these challenges, we introduce UpANNS, a novel framework leveraging Processing-in-Memory (PIM) architecture to accelerate billion-scale ANNS. UpANNS integrates four key innovations, including 1) architecture-aware data placement to minimize latency through workload balancing, 2) dynamic resource management for optimal PIM utilization, 3) co-occurrence optimized encoding to reduce redundant computations, and 4) an early-pruning strategy for efficient top-k selection. Evaluation on commercial UPMEM hardware demonstrates that UpANNS achieves 4.3x higher QPS than CPU-based Faiss, while matching GPU performance with 2.3x greater energy efficiency. Its near-linear scalability ensures practicality for growing datasets, making it ideal for applications like real-time LLM serving and large-scale retrieval systems.