# OOD-DiskANN: Efficient and Scalable Graph ANNS for Out-of-Distribution Queries

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

## Key facts

- Cited by 15 papers in the map (data through 14 Oct 2026).
- Builds on 24 of its 52 references that are in the map.
- First posted on arXiv 22 Oct 2022.

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

- [Learning Transferable Visual Models From Natural Language Supervision](https://mlsanity.com/paper/2103.00020/) (2021)
- [Representation Learning with Contrastive Predictive Coding](https://mlsanity.com/paper/1807.03748/) (2018)
- [Squeeze-and-Excitation Networks](https://mlsanity.com/paper/1709.01507/) (2017)
- [Dense Passage Retrieval for Open-Domain Question Answering](https://mlsanity.com/paper/2004.04906/) (2020)
- [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)
- [Approximate Nearest Neighbor Negative Contrastive Learning for Dense Text Retrieval](https://mlsanity.com/paper/2007.00808/) (2020)
- [Learning Representations by Maximizing Mutual Information Across Views](https://mlsanity.com/paper/1906.00910/) (2019)
- [Discriminative Unsupervised Feature Learning with Exemplar Convolutional Neural Networks](https://mlsanity.com/paper/1406.6909/) (2014)
- [Overview of the TREC 2019 deep learning track](https://mlsanity.com/paper/2003.07820/) (2020)
- [Accuracy on the Line: On the Strong Correlation Between Out-of-Distribution and In-Distribution Generalization](https://mlsanity.com/paper/2107.04649/) (2021)
- [ANN-Benchmarks: A Benchmarking Tool for Approximate Nearest Neighbor Algorithms](https://mlsanity.com/paper/1807.05614/) (2018)
- [Practical and Optimal LSH for Angular Distance](https://mlsanity.com/paper/1509.02897/) (2015)
- [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)
- [Semantic Models for the First-stage Retrieval: A Comprehensive Review](https://mlsanity.com/paper/2103.04831/) (2021)
- [Results of the NeurIPS'21 Challenge on Billion-Scale Approximate Nearest Neighbor Search](https://mlsanity.com/paper/2205.03763/) (2022)
- [Revisiting the Inverted Indices for Billion-Scale Approximate Nearest Neighbors](https://mlsanity.com/paper/1802.02422/) (2018)
- [Do We Really Need to Learn Representations from In-domain Data for Outlier Detection?](https://mlsanity.com/paper/2105.09270/) (2021)
- [Unsupervised Neural Quantization for Compressed-Domain Similarity Search](https://mlsanity.com/paper/1908.03883/) (2019)
- [PnPOOD : Out-Of-Distribution Detection for Text Classification via Plug andPlay Data Augmentation](https://mlsanity.com/paper/2111.00506/) (2021)
- [Nearest neighbor search with compact codes: A decoder perspective](https://mlsanity.com/paper/2112.09568/) (2021)
- [Graph Reordering for Cache-Efficient Near Neighbor Search](https://mlsanity.com/paper/2104.03221/) (2021)
- [Deep Random Projection Outlyingness for Unsupervised Anomaly Detection](https://mlsanity.com/paper/2106.15307/) (2021)

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

- [The Faiss library](https://mlsanity.com/paper/2401.08281/) (2024)
- [RetrievalAttention: Accelerating Long-Context LLM Inference via Vector Retrieval](https://mlsanity.com/paper/2409.10516/) (2024)
- [RoarGraph: A Projected Bipartite Graph for Efficient Cross-Modal Approximate Nearest Neighbor Search](https://mlsanity.com/paper/2408.08933/) (2024)
- [DeDrift: Robust Similarity Search under Content Drift](https://mlsanity.com/paper/2308.02752/) (2023)
- [Inference-time sparse attention with asymmetric indexing](https://mlsanity.com/paper/2502.08246/) (2025)
- [VIBE: Vector Index Benchmark for Embeddings](https://mlsanity.com/paper/2505.17810/) (2025)
- [LeanVec: Searching vectors faster by making them fit](https://mlsanity.com/paper/2312.16335/) (2023)
- [LoRANN: Low-Rank Matrix Factorization for Approximate Nearest Neighbor Search](https://mlsanity.com/paper/2410.18926/) (2024)
- [SQUASH: Serverless and Distributed Quantization-based Attributed Vector Similarity Search](https://mlsanity.com/paper/2502.01528/) (2025)
- [QVCache: A Query-Aware Vector Cache](https://mlsanity.com/paper/2602.02057/) (2026)
- [EHI: End-to-end Learning of Hierarchical Index for Efficient Dense Retrieval](https://mlsanity.com/paper/2310.08891/) (2023)
- [Theoretical and Empirical Analysis of Adaptive Entry Point Selection for Graph-based Approximate Nearest Neighbor Search](https://mlsanity.com/paper/2402.04713/) (2024)
- [GleanVec: Accelerating vector search with minimalist nonlinear dimensionality reduction](https://mlsanity.com/paper/2410.22347/) (2024)
- [ANNLib: A Development Framework for Efficient Approximate Nearest Neighbor Search](https://mlsanity.com/paper/2607.17582/) (2026)
- [Attention via Black-Box Vector Search](https://mlsanity.com/paper/2610.10135/) (2026)

## Abstract (arXiv)

State-of-the-art algorithms for Approximate Nearest Neighbor Search (ANNS) such as DiskANN, FAISS-IVF, and HNSW build data dependent indices that offer substantially better accuracy and search efficiency over data-agnostic indices by overfitting to the index data distribution. When the query data is drawn from a different distribution - e.g., when index represents image embeddings and query represents textual embeddings - such algorithms lose much of this performance advantage. On a variety of datasets, for a fixed recall target, latency is worse by an order of magnitude or more for Out-Of-Distribution (OOD) queries as compared to In-Distribution (ID) queries. The question we address in this work is whether ANNS algorithms can be made efficient for OOD queries if the index construction is given access to a small sample set of these queries. We answer positively by presenting OOD-DiskANN, which uses a sparing sample (1% of index set size) of OOD queries, and provides up to 40% improvement in mean query latency over SoTA algorithms of a similar memory footprint. OOD-DiskANN is scalable and has the efficiency of graph-based ANNS indices. Some of our contributions can improve query efficiency for ID queries as well.