# Approximate Diverse k-nearest Neighbor Search in Vector Database

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

## 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 20 of its 32 references that are in the map.
- First posted on arXiv 31 Oct 2025.

## Placed in

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

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

- [Learning Transferable Visual Models From Natural Language Supervision](https://mlsanity.com/paper/2103.00020/) (2021)
- [LAION-5B: An open large-scale dataset for training next generation image-text models](https://mlsanity.com/paper/2210.08402/) (2022)
- [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)
- [The Faiss library](https://mlsanity.com/paper/2401.08281/) (2024)
- [Query Rewriting for Retrieval-Augmented Large Language Models](https://mlsanity.com/paper/2305.14283/) (2023)
- [Recommender Systems in the Era of Large Language Models (LLMs)](https://mlsanity.com/paper/2307.02046/) (2023)
- [Embedding-based Retrieval in Facebook Search](https://mlsanity.com/paper/2006.11632/) (2020)
- [Fast Approximate Nearest Neighbor Search With The Navigating Spreading-out Graph](https://mlsanity.com/paper/1707.00143/) (2017)
- [RaBitQ: Quantizing High-Dimensional Vectors with a Theoretical Error Bound for Approximate Nearest Neighbor Search](https://mlsanity.com/paper/2405.12497/) (2024)
- [Results of the NeurIPS'21 Challenge on Billion-Scale Approximate Nearest Neighbor Search](https://mlsanity.com/paper/2205.03763/) (2022)
- [Optimal Data-Dependent Hashing for Approximate Near Neighbors](https://mlsanity.com/paper/1501.01062/) (2015)
- [Knowledge Graph Embedding: A Survey from the Perspective of Representation Spaces](https://mlsanity.com/paper/2211.03536/) (2022)
- [Multimodal Recommender Systems: A Survey](https://mlsanity.com/paper/2302.03883/) (2023)
- [Interpreting the Curse of Dimensionality from Distance Concentration and Manifold Effect](https://mlsanity.com/paper/2401.00422/) (2023)
- [Accelerated Nearest Neighbor Search with Quick ADC](https://mlsanity.com/paper/1704.07355/) (2017)
- [Diversity-Aware k-Maximum Inner Product Search Revisited](https://mlsanity.com/paper/2402.13858/) (2024)
- [Zelda: Video Analytics using Vision-Language Models](https://mlsanity.com/paper/2305.03785/) (2023)
- [DET-LSH: A Locality-Sensitive Hashing Scheme with Dynamic Encoding Tree for Approximate Nearest Neighbor Search](https://mlsanity.com/paper/2406.10938/) (2024)
- [Understanding and Improving Proximity Graph based Maximum Inner Product Search](https://mlsanity.com/paper/1909.13459/) (2019)

## Abstract (arXiv)

Approximate k-nearest neighbor search (Ak-NNS) is a core operation in vector databases, underpinning applications such as retrieval-augmented generation (RAG) and image retrieval. In these scenarios, users often prefer diverse result sets to minimize redundancy and enhance information value. However, existing greedy-based diverse methods frequently yield sub-optimal results, failing to adequately approximate the optimal similarity score under certain diversification level. Furthermore, there is a need for flexible algorithms that can adapt to varying user-defined result sizes and diversity requirements. To address these challenges, we propose a novel approach that seamlessly integrates result diversification into state-of-the-art (SOTA) Ak-NNS methods. Our approach introduces a progressive search framework, consisting of iterative searching, diversification, and verification phases. Carefully designed diversification and verification steps enable our approach to efficiently approximate the optimal diverse result set according to user-specified diversification levels without additional indexing overhead. We evaluate our method on three million-scale benchmark datasets, LAION-art, Deep1M, and Txt2img, using latency, similarity, and recall as performance metrics across a range of k values and diversification thresholds. Experimental results demonstrate that our approach consistently retrieves near-optimal diverse results with minimal latency overhead, particularly under medium and high diversity settings.