# How Should We Evaluate Data Deletion in Graph-Based ANN Indexes?

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

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- Placed in Vector search and ANN indexes, one of 15 directions in Retrieval-augmented generation.
- Builds on 8 of its 15 references that are in the map.
- First posted on arXiv 5 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, 8 of 8)

- [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)
- [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)
- [Locally-Adaptive Quantization for Streaming Vector Search](https://mlsanity.com/paper/2402.02044/) (2024)
- [Enhancing HNSW Index for Real-Time Updates: Addressing Unreachable Points and Performance Degradation](https://mlsanity.com/paper/2407.07871/) (2024)
- [Incremental IVF Index Maintenance for Streaming Vector Search](https://mlsanity.com/paper/2411.00970/) (2024)
- [Proximity Graph Maintenance for Fast Online Nearest Neighbor Search](https://mlsanity.com/paper/2206.10839/) (2022)

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

- [Beyond Private Training: The New Landscape of AI Privacy](https://mlsanity.com/paper/2609.19456/) (2026)

## Abstract (arXiv)

Approximate Nearest Neighbor Search (ANNS) has recently gained significant attention due to its many applications, such as Retrieval-Augmented Generation. Such applications require ANNS algorithms that support dynamic data, so the ANNS problem on dynamic data has attracted considerable interest. However, a comprehensive evaluation methodology for data deletion in ANNS has yet to be established. This study proposes an experimental framework and comprehensive evaluation metrics to assess the efficiency of data deletion for ANNS indexes under practical use cases. Specifically, we categorize data deletion methods in graph-based ANNS into three approaches and formalize them mathematically. The performance is assessed in terms of accuracy, query speed, and other relevant metrics. Finally, we apply the proposed evaluation framework to Hierarchical Navigable Small World, one of the state-of-the-art ANNS methods, to analyze the effects of data deletion, and propose Deletion Control, a method which dynamically selects the appropriate deletion method under a required search accuracy.