# RoarGraph: A Projected Bipartite Graph for Efficient Cross-Modal Approximate Nearest Neighbor Search

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

## Key facts

- Cited by 12 papers in the map (data through 14 Oct 2026).
- Builds on 35 of its 85 references that are in the map.
- First posted on arXiv 16 Aug 2024.

## Builds on (most cited first, 30 of 35)

- [Learning Transferable Visual Models From Natural Language Supervision](https://mlsanity.com/paper/2103.00020/) (2021)
- [Squeeze-and-Excitation Networks](https://mlsanity.com/paper/1709.01507/) (2017)
- [LAION-5B: An open large-scale dataset for training next generation image-text models](https://mlsanity.com/paper/2210.08402/) (2022)
- [Billion-scale similarity search with GPUs](https://mlsanity.com/paper/1702.08734/) (2017)
- [Frozen in Time: A Joint Video and Image Encoder for End-to-End Retrieval](https://mlsanity.com/paper/2104.00650/) (2021)
- [HowTo100M: Learning a Text-Video Embedding by Watching Hundred Million Narrated Video Clips](https://mlsanity.com/paper/1906.03327/) (2019)
- [Approximate Nearest Neighbor Negative Contrastive Learning for Dense Text Retrieval](https://mlsanity.com/paper/2007.00808/) (2020)
- [Mind the Gap: Understanding the Modality Gap in Multi-modal Contrastive Representation Learning](https://mlsanity.com/paper/2203.02053/) (2022)
- [Less is More: ClipBERT for Video-and-Language Learning via Sparse Sampling](https://mlsanity.com/paper/2102.06183/) (2021)
- [PAQ: 65 Million Probably-Asked Questions and What You Can Do With Them](https://mlsanity.com/paper/2102.07033/) (2021)
- [KNN-Diffusion: Image Generation via Large-Scale Retrieval](https://mlsanity.com/paper/2204.02849/) (2022)
- [Retrieval Augmented Classification for Long-Tail Visual Recognition](https://mlsanity.com/paper/2202.11233/) (2022)
- [Fast Approximate Nearest Neighbor Search With The Navigating Spreading-out Graph](https://mlsanity.com/paper/1707.00143/) (2017)
- [A Comprehensive Survey and Experimental Comparison of Graph-Based Approximate Nearest Neighbor Search](https://mlsanity.com/paper/2101.12631/) (2021)
- [PinnerSage: Multi-Modal User Embedding Framework for Recommendations at Pinterest](https://mlsanity.com/paper/2007.03634/) (2020)
- [Real-Time Open-Domain Question Answering with Dense-Sparse Phrase Index](https://mlsanity.com/paper/1906.05807/) (2019)
- [A Comprehensive Survey on Cross-modal Retrieval](https://mlsanity.com/paper/1607.06215/) (2016)
- [A Survey of Machine Learning for Computer Architecture and Systems](https://mlsanity.com/paper/2102.07952/) (2021)
- [Graph Trend Filtering Networks for Recommendations](https://mlsanity.com/paper/2108.05552/) (2021)
- [InstructRetro: Instruction Tuning post Retrieval-Augmented Pretraining](https://mlsanity.com/paper/2310.07713/) (2023)
- [Semantic Product Search](https://mlsanity.com/paper/1907.00937/) (2019)
- [Approximate Nearest Neighbor Search on High Dimensional Data --- Experiments, Analyses, and Improvement (v1.0)](https://mlsanity.com/paper/1610.02455/) (2016)
- [High-Dimensional Approximate Nearest Neighbor Search: with Reliable and Efficient Distance Comparison Operations](https://mlsanity.com/paper/2303.09855/) (2023)
- [Graph-based Nearest Neighbor Search: From Practice to Theory](https://mlsanity.com/paper/1907.00845/) (2019)
- [OOD-DiskANN: Efficient and Scalable Graph ANNS for Out-of-Distribution Queries](https://mlsanity.com/paper/2211.12850/) (2022)
- [Deep Retrieval: Learning A Retrievable Structure for Large-Scale Recommendations](https://mlsanity.com/paper/2007.07203/) (2020)
- [A Theoretical Analysis Of Nearest Neighbor Search On Approximate Near Neighbor Graph](https://mlsanity.com/paper/2303.06210/) (2023)
- [Ball*-tree: Efficient spatial indexing for constrained nearest-neighbor search in metric spaces](https://mlsanity.com/paper/1511.00628/) (2015)
- [Accelerated Nearest Neighbor Search with Quick ADC](https://mlsanity.com/paper/1704.07355/) (2017)
- [Learning to Route in Similarity Graphs](https://mlsanity.com/paper/1905.10987/) (2019)

## Built on by (most cited first, 12 of 12)

- [RetrievalAttention: Accelerating Long-Context LLM Inference via Vector Retrieval](https://mlsanity.com/paper/2409.10516/) (2024)
- [Results of the Big ANN: NeurIPS'23 competition](https://mlsanity.com/paper/2409.17424/) (2024)
- [RetroInfer: A Vector Storage Engine for Scalable Long-Context LLM Inference](https://mlsanity.com/paper/2505.02922/) (2025)
- [Inference-time sparse attention with asymmetric indexing](https://mlsanity.com/paper/2502.08246/) (2025)
- [CARROT: A Learned Cost-Constrained Retrieval Optimization System for RAG](https://mlsanity.com/paper/2411.00744/) (2024)
- [VIBE: Vector Index Benchmark for Embeddings](https://mlsanity.com/paper/2505.17810/) (2025)
- [AlayaDB: The Data Foundation for Efficient and Effective Long-context LLM Inference](https://mlsanity.com/paper/2504.10326/) (2025)
- [Lossless Compression of Vector IDs for Approximate Nearest Neighbor Search](https://mlsanity.com/paper/2501.10479/) (2025)
- [Machine learning and high dimensional vector search](https://mlsanity.com/paper/2502.16931/) (2025)
- [Amortized Maximum Inner Product Search with Learned Support Functions](https://mlsanity.com/paper/2603.08001/) (2026)
- [Scalable k-Means Clustering for Large k via Seeded Approximate Nearest-Neighbor Search](https://mlsanity.com/paper/2502.06163/) (2025)
- [Cluster with Auctions for Vector Search](https://mlsanity.com/paper/2607.13728/) (2026)

## Abstract (arXiv)

Approximate Nearest Neighbor Search (ANNS) is a fundamental and critical component in many applications, including recommendation systems and large language model-based applications. With the advancement of multimodal neural models, which transform data from different modalities into a shared high-dimensional space as feature vectors, cross-modal ANNS aims to use the data vector from one modality (e.g., texts) as the query to retrieve the most similar items from another (e.g., images or videos). However, there is an inherent distribution gap between embeddings from different modalities, and cross-modal queries become Out-of-Distribution (OOD) to the base data. Consequently, state-of-the-art ANNS approaches suffer poor performance for OOD workloads. In this paper, we quantitatively analyze the properties of the OOD workloads to gain an understanding of their ANNS efficiency. Unlike single-modal workloads, we reveal OOD queries spatially deviate from base data, and the k-nearest neighbors of an OOD query are distant from each other in the embedding space. The property breaks the assumptions of existing ANNS approaches and mismatches their design for efficient search. With insights from the OOD workloads, we propose pRojected bipartite Graph (RoarGraph), an efficient ANNS graph index built under the guidance of query distribution. Extensive experiments show that RoarGraph significantly outperforms state-of-the-art approaches on modern cross-modal datasets, achieving up to 3.56x faster search speed at a 90% recall rate for OOD queries.