mlsanityData to 7 Oct 2026

Graph-based Nearest Neighbors with Dynamic Updates via Random Walks

arXiv 2512.18060 ↗First posted 19 Dec 2025cs.DS cs.LGcited by 0

On the map: Retrieval-augmented generation → Vector search and ANN indexes

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.

Key facts. No citing papers in the map yet (data through 7 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.

Builds on

33 of 70 references.

Closest ancestors · 1

Same direction, newest first

  1. 2025In-Place Updates of a Graph Index for Streaming Approximate Nearest Neighbor Search19 Feb

Other references · 32

  1. 2020Retrieval-Augmented Generation for Knowledge-Intensive NLP Taskscited by 9,160
  2. 2017Inductive Representation Learning on Large Graphscited by 6,284
  3. 2017Billion-scale similarity search with GPUscited by 2,477
  4. 2023Retrieval-Augmented Generation for Large Language Models: A Surveycited by 2,185
  5. 2016MS MARCO: A Human Generated MAchine Reading COmprehension Datasetcited by 1,591
  6. 2020MiniLM: Deep Self-Attention Distillation for Task-Agnostic Compression of Pre-Trained Transformerscited by 1,414
  7. 2020MPNet: Masked and Permuted Pre-training for Language Understandingcited by 973
  8. 2016Efficient and robust approximate nearest neighbor search using Hierarchical Navigable Small World graphscited by 853
  9. 2023Active Retrieval Augmented Generationcited by 506
  10. 2024A Survey on RAG Meeting LLMs: Towards Retrieval-Augmented Large Language Modelscited by 450
  11. 2015Practical and Optimal LSH for Angular Distancecited by 105
  12. 2017Fast Approximate Nearest Neighbor Search With The Navigating Spreading-out Graphcited by 103
20 more
  1. 2021A Comprehensive Survey and Experimental Comparison of Graph-Based Approximate Nearest Neighbor Searchcited by 82
  2. 2024RaBitQ: Quantizing High-Dimensional Vectors with a Theoretical Error Bound for Approximate Nearest Neighbor Searchcited by 46
  3. 2018Approximate Nearest Neighbor Search in High Dimensionscited by 45
  4. 2015Optimal Data-Dependent Hashing for Approximate Near Neighborscited by 43
  5. 2021FreshDiskANN: A Fast and Accurate Graph-Based ANN Index for Streaming Similarity Searchcited by 36
  6. 2024SPFresh: Incremental In-Place Update for Billion-Scale Vector Searchcited by 28
  7. 2016Approximate Gaussian Elimination for Laplacians: Fast, Sparse, and Simplecited by 23
  8. 2023Worst-case Performance of Popular Approximate Nearest Neighbor Search Implementations: Guarantees and Limitationscited by 20
  9. 2019Graph-based Nearest Neighbor Search: From Practice to Theorycited by 19
  10. 2016Optimal Hashing-based Time-Space Trade-offs for Approximate Near Neighborscited by 18
  11. 2019GGNN: Graph-based GPU Nearest Neighbor Searchcited by 10
  12. 2023A Theoretical Analysis Of Nearest Neighbor Search On Approximate Near Neighbor Graphcited by 10
  13. 2017Graph-based time-space trade-offs for approximate near neighborscited by 7
  14. 2024Navigable Graphs for High-Dimensional Nearest Neighbor Search: Constructions and Limitscited by 7
  15. 2024Enhancing HNSW Index for Real-Time Updates: Addressing Unreachable Points and Performance Degradationcited by 7
  16. 2022Proximity Graph Maintenance for Fast Online Nearest Neighbor Searchcited by 5
  17. 2013An Efficient Parallel Solver for SDD Linear Systemscited by 3
  18. 2024Probabilistic Routing for Graph-Based Approximate Nearest Neighbor Searchcited by 3
  19. 2024Approximate Nearest Neighbour Search on Dynamic Datasets: An Investigationcited by 2
  20. 2023Routing-Guided Learned Product Quantization for Graph-Based Approximate Nearest Neighbor Searchcited by 1

Built on by

Not cited yet.

Similar, not cited

Close in wording, no citation either way

  1. 2025How Should We Evaluate Data Deletion in Graph-Based ANN Indexes?
  2. 2026MERIT: Efficient In-Place Deletion for Dynamic Graph-Based Approximate Nearest Neighbor Indexes
  3. 2024Revisiting the Index Construction of Proximity Graph-Based Approximate Nearest Neighbor Search
  4. 2026FGIM: a Fast Graph-based Indexes Merging Framework for Approximate Nearest Neighbor Search
  5. 2026ANN Search: Recall What Matters
  6. 2026Filtered Approximate Nearest Neighbor Search in Vector Databases: System Design and Performance Analysis
  7. 2026Better Nearest Neighbor Graph Indices via (Efficient) LLM-Guided Pruning
  8. 2026Query-aware Routing for Filtered Approximate Nearest Neighbors Search