# FGIM: a Fast Graph-based Indexes Merging Framework for Approximate Nearest Neighbor Search

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

## 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 21 of its 65 references that are in the map.
- First posted on arXiv 23 Mar 2026.

## Placed in

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

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

- [Retrieval-Augmented Generation for Knowledge-Intensive NLP Tasks](https://mlsanity.com/paper/2005.11401/) (2020)
- [Efficient and robust approximate nearest neighbor search using Hierarchical Navigable Small World graphs](https://mlsanity.com/paper/1603.09320/) (2016)
- [ANN-Benchmarks: A Benchmarking Tool for Approximate Nearest Neighbor Algorithms](https://mlsanity.com/paper/1807.05614/) (2018)
- [RetrievalAttention: Accelerating Long-Context LLM Inference via Vector Retrieval](https://mlsanity.com/paper/2409.10516/) (2024)
- [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)
- [A Survey on Large-scale Machine Learning](https://mlsanity.com/paper/2008.03911/) (2020)
- [SPFresh: Incremental In-Place Update for Billion-Scale Vector Search](https://mlsanity.com/paper/2410.14452/) (2024)
- [CAGRA: Highly Parallel Graph Construction and Approximate Nearest Neighbor Search for GPUs](https://mlsanity.com/paper/2308.15136/) (2023)
- [Similarity search in the blink of an eye with compressed indices](https://mlsanity.com/paper/2304.04759/) (2023)
- [Graph-based Nearest Neighbor Search: From Practice to Theory](https://mlsanity.com/paper/1907.00845/) (2019)
- [EFANNA : An Extremely Fast Approximate Nearest Neighbor Search Algorithm Based on kNN Graph](https://mlsanity.com/paper/1609.07228/) (2016)
- [Vector Search with OpenAI Embeddings: Lucene Is All You Need](https://mlsanity.com/paper/2308.14963/) (2023)
- [Graph-Based Vector Search: An Experimental Evaluation of the State-of-the-Art](https://mlsanity.com/paper/2502.05575/) (2025)
- [A Topology-Aware Localized Update Strategy for Graph-Based ANN Index](https://mlsanity.com/paper/2503.00402/) (2025)
- [LSM-VEC: A Large-Scale Disk-Based System for Dynamic Vector Search](https://mlsanity.com/paper/2505.17152/) (2025)
- [Permutation Search Methods are Efficient, Yet Faster Search is Possible](https://mlsanity.com/paper/1506.03163/) (2015)
- [SINDI: An Efficient Index for Sparse Vector Approximate Maximum Inner Product Search](https://mlsanity.com/paper/2509.08395/) (2025)
- [On the Merge of k-NN Graph](https://mlsanity.com/paper/1908.00814/) (2019)
- [Revisiting the Index Construction of Proximity Graph-Based Approximate Nearest Neighbor Search](https://mlsanity.com/paper/2410.01231/) (2024)
- [Approximate Nearest Neighbor Search of Large Scale Vectors on Distributed Storage](https://mlsanity.com/paper/2510.17326/) (2025)

## Abstract (arXiv)

As the state-of-the-art methods for high-dimensional data retrieval, Approximate Nearest Neighbor Search (ANNS) approaches with graph-based indexes have attracted increasing attention and play a crucial role in many real-world applications, e.g., retrieval-augmented generation (RAG) and recommendation systems. Unlike the extensive works focused on designing efficient graph-based ANNS methods, this paper delves into merging multiple existing graph-based indexes into a single one, which is also crucial in many real-world scenarios (e.g., cluster consolidation in distributed systems and read-write contention in real-time vector databases). We propose a Fast Graph-based Indexes Merging (FGIM) framework with three core techniques: (1) Proximity Graphs (PGs) to k Nearest Neighbor Graph (k-NNG) transformation used to extract potential candidate neighbors from input graph-based indexes through cross-querying, (2) k-NNG refinement designed to identify overlooked high-quality neighbors and maintain graph connectivity, and (3) k-NNG to PG transformation aimed at improving graph navigability and enhancing search performance. Then, we integrate our FGIM framework with the state-of-the-art ANNS method, HNSW, and other existing mainstream graph-based methods to demonstrate its generality and merging efficiency. Extensive experiments on six real-world datasets show that our FGIM framework is applicable to various mainstream graph-based ANNS methods, achieves up to 3.5X speedup over HNSW's incremental construction and an average of 7.9X speedup for methods without incremental support, while maintaining comparable or superior search performance.