# Graph-based Nearest Neighbors with Dynamic Updates via Random Walks

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

## 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 33 of its 70 references that are in the map.
- First posted on arXiv 19 Dec 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, 30 of 33)

- [Retrieval-Augmented Generation for Knowledge-Intensive NLP Tasks](https://mlsanity.com/paper/2005.11401/) (2020)
- [Inductive Representation Learning on Large Graphs](https://mlsanity.com/paper/1706.02216/) (2017)
- [Billion-scale similarity search with GPUs](https://mlsanity.com/paper/1702.08734/) (2017)
- [Retrieval-Augmented Generation for Large Language Models: A Survey](https://mlsanity.com/paper/2312.10997/) (2023)
- [MS MARCO: A Human Generated MAchine Reading COmprehension Dataset](https://mlsanity.com/paper/1611.09268/) (2016)
- [MiniLM: Deep Self-Attention Distillation for Task-Agnostic Compression of Pre-Trained Transformers](https://mlsanity.com/paper/2002.10957/) (2020)
- [MPNet: Masked and Permuted Pre-training for Language Understanding](https://mlsanity.com/paper/2004.09297/) (2020)
- [Efficient and robust approximate nearest neighbor search using Hierarchical Navigable Small World graphs](https://mlsanity.com/paper/1603.09320/) (2016)
- [Active Retrieval Augmented Generation](https://mlsanity.com/paper/2305.06983/) (2023)
- [A Survey on RAG Meeting LLMs: Towards Retrieval-Augmented Large Language Models](https://mlsanity.com/paper/2405.06211/) (2024)
- [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)
- [RaBitQ: Quantizing High-Dimensional Vectors with a Theoretical Error Bound for Approximate Nearest Neighbor Search](https://mlsanity.com/paper/2405.12497/) (2024)
- [Approximate Nearest Neighbor Search in High Dimensions](https://mlsanity.com/paper/1806.09823/) (2018)
- [Optimal Data-Dependent Hashing for Approximate Near Neighbors](https://mlsanity.com/paper/1501.01062/) (2015)
- [FreshDiskANN: A Fast and Accurate Graph-Based ANN Index for Streaming Similarity Search](https://mlsanity.com/paper/2105.09613/) (2021)
- [SPFresh: Incremental In-Place Update for Billion-Scale Vector Search](https://mlsanity.com/paper/2410.14452/) (2024)
- [Approximate Gaussian Elimination for Laplacians: Fast, Sparse, and Simple](https://mlsanity.com/paper/1605.02353/) (2016)
- [Worst-case Performance of Popular Approximate Nearest Neighbor Search Implementations: Guarantees and Limitations](https://mlsanity.com/paper/2310.19126/) (2023)
- [Graph-based Nearest Neighbor Search: From Practice to Theory](https://mlsanity.com/paper/1907.00845/) (2019)
- [Optimal Hashing-based Time-Space Trade-offs for Approximate Near Neighbors](https://mlsanity.com/paper/1608.03580/) (2016)
- [GGNN: Graph-based GPU Nearest Neighbor Search](https://mlsanity.com/paper/1912.01059/) (2019)
- [A Theoretical Analysis Of Nearest Neighbor Search On Approximate Near Neighbor Graph](https://mlsanity.com/paper/2303.06210/) (2023)
- [Enhancing HNSW Index for Real-Time Updates: Addressing Unreachable Points and Performance Degradation](https://mlsanity.com/paper/2407.07871/) (2024)
- [Graph-based time-space trade-offs for approximate near neighbors](https://mlsanity.com/paper/1712.03158/) (2017)
- [Navigable Graphs for High-Dimensional Nearest Neighbor Search: Constructions and Limits](https://mlsanity.com/paper/2405.18680/) (2024)
- [Proximity Graph Maintenance for Fast Online Nearest Neighbor Search](https://mlsanity.com/paper/2206.10839/) (2022)
- [In-Place Updates of a Graph Index for Streaming Approximate Nearest Neighbor Search](https://mlsanity.com/paper/2502.13826/) (2025)
- [An Efficient Parallel Solver for SDD Linear Systems](https://mlsanity.com/paper/1311.3286/) (2013)

## Abstract (arXiv)

Approximate nearest neighbor search (ANN) is a common way to retrieve relevant search results, especially now in the context of large language models and retrieval augmented generation. One of the most widely used algorithms for ANN is based on constructing a multi-layer graph over the dataset, called the Hierarchical Navigable Small World (HNSW). While this algorithm supports insertion of new data, it does not support deletion of existing data. Moreover, deletion algorithms described by prior work come at the cost of increased query latency, decreased recall, or prolonged deletion time. In this paper, we propose a new theoretical framework for graph-based ANN based on random walks. We then utilize this framework to analyze a randomized deletion approach that preserves hitting time statistics compared to the graph before deleting the point. We then turn this theoretical framework into a deterministic deletion algorithm, and show that it provides better tradeoff between query latency, recall, deletion time, and memory usage through an extensive collection of experiments.