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

AI summary

Overview

Research area: Approximate Nearest Neighbor Search (ANNS), specifically dynamic vector indexes that must support deletion of data points; the paper sits at the intersection of information retrieval, vector database systems, and machine learning infrastructure.

Technical level: Intermediate. The paper requires familiarity with graph-based ANNS concepts (nodes, neighbor sets, recall, QPS), but the deletion methods and evaluation procedure are explained formally and in pseudocode, so a reader with basic IR or systems background can follow it.

Scope: The paper proposes and demonstrates a deployment-oriented evaluation framework for data deletion in graph-based ANNS indexes, instantiated on Hierarchical Navigable Small World (HNSW), plus a policy for switching between deletion methods to meet a target search accuracy.

What This Paper Is About

Applications built on ANNS, such as Retrieval-Augmented Generation and recommendation systems, constantly insert new items and remove unavailable ones, yet there is no agreed methodology for evaluating how an index handles deletion. Existing evaluations are often unrealistic (for example, re-adding deleted data) and use metrics that are not comprehensive enough to judge deletion performance. This paper defines three deletion approaches in graph-based ANNS, gives a unified experimental protocol for measuring them under realistic insert/delete workloads, and uses the resulting measurements to propose an algorithm that chooses a deletion method based on a required accuracy level.

Key Contributions

1. Formalization of three baseline deletion methods. The paper categorizes deletion in graph-based ANNS into logical deletion (flag deleted nodes and filter them from search results), physical deletion (remove the node, its incident edges, and its data from memory, reconnecting nothing), and rebuilding (remove the data and reconstruct the graph from all remaining data via CONSTRUCT). Each is given as pseudocode and as a mathematical definition over the node set P, the neighborhood collection N, and the deletion query set D.

2. A realistic experimental setup and evaluation metric suite. The authors define a protocol where insertion and deletion occur repeatedly with the same batch size b, the index size is held at n ≤ n_o after every update, inserted points are always new, and ground truth is recomputed after each update. They measure 1-Recall@10, QPS-search, QPS-add, QPS-delete, the QPS-Recall curve, and memory footprint.

3. Empirical evaluation of the three methods on HNSW across five datasets (SIFT1M, GIST1M, a 2 × 10^6 subset of SIFT1B, DEEP1M, and Glove100Angular), covering accuracy, speed, and memory behavior simultaneously.

4. Deletion Control, an algorithm that estimates two dataset characteristics (θ and π) from a small query training set and then either applies physical deletion only or alternates logical deletion with periodic rebuilding, so that search accuracy stays above a target α.

Main Findings

• Rebuilding gives the best search performance. Figure 2(a) shows post-update search performance on SIFT1M is highest with rebuilding, followed by physical deletion, then logical deletion. Appendix D.1 reports the same ordering across SIFT1M, GIST1M, SIFT1B (both batch sizes), DEEP1M, and Glove100Angular.

• Logical deletion is by far the fastest to delete but accumulates memory. Logical deletion achieves deletion speed on the order of approximately 10^9 [1/s] across all datasets, while rebuilding and physical deletion operate at most on the order of 10^3 [1/s]. With batches of b = 10^5, logical deletion completes in roughly 10^-4 [s], whereas physical deletion requires up to 10^2 [s]. Memory usage in logical deletion grows linearly with each step on every dataset, while memory stays unchanged for rebuilding and physical deletion.

• Logical deletion degrades accuracy over repeated updates. 1-Recall@10 falls as insertions and deletions repeat, and the retrieved results must additionally be filtered against a flag array, which the paper identifies as a reason logical deletion also has the slowest search speed across all datasets.

• Physical deletion converges to a stable accuracy. In SIFT1B, physical deletion's 1-Recall@10 stabilizes to a constant value after multiple update steps, which the authors attribute to the graph's structural properties becoming stable. A larger batch size produces a higher converged accuracy.

• Search speed is highest under physical deletion. The paper attributes this to repeated physical deletions gradually making the graph sparser and thereby reducing distance calculations during search and insertion. Physical deletion shows the highest insertion speed at b = 10^5.

• Batch size changes the picture for small batches. At b = 10^3 on SIFT1B, insertion speed under logical deletion varies significantly at each step, and rebuilding becomes relatively slower than physical deletion. Reducing the batch size from 10^5 to 10^3 (a 1/100 reduction in deletions per step) leaves physical deletion speed nearly constant but reduces rebuilding speed by approximately a factor of 100.

• Dimensionality affects rebuilding only. Comparing SIFT1M (dimensionality 128) with GIST1M (dimensionality 960), the dimensionality of inserted and deleted vectors affects only the speed of rebuilding, because rebuilding performs distance calculations during deletion.

• Deletion Control meets its accuracy target. On SIFT1B with b = 10^5 and α = 0.84, using 10% of queries as a training set yields estimates θ = 0.816 and π = 1. Because α > θ, the algorithm alternates logical deletion with rebuilding. Figure 4 shows the method almost satisfies the required accuracy and has the smallest total deletion time among the strategies that meet the requirement.

Methodology in Plain English

The authors start by writing down what deletion can mean in a graph index. In logical deletion, you only mark a node as deleted and filter it out at search time, so the node and its edges stay in memory. In physical deletion, you actually delete the node, drop the edges pointing to it, and free its memory. In rebuilding, you throw away the deleted data and reconstruct the graph from scratch using everything that remains.

They then build an experiment loop: start with an index of fixed size, then repeatedly delete a batch of b points and insert a batch of b new points, recomputing ground truth each round so accuracy is measured against a correct answer for the current index contents. They run this loop for the three deletion methods and plot accuracy, insert/delete/search throughput, and memory over the steps. All experiments run single-threaded on an Intel Core i7-13700H at 2.4 GHz with 32 GB RAM under Ubuntu 22.04.5.

For the control algorithm, they observe two properties from the training runs: physical deletion accuracy converges to a floor θ, and logical deletion accuracy drops roughly linearly with update steps, giving an average decrease Δ = (R_S − R_0)/S. From these they estimate π ≈ (α − R_0)/Δ, the number of steps logical deletion can run while staying above the target α. If α < θ, physical deletion alone is enough. If α ≥ θ, they run logical deletion for π steps and then rebuild once, resetting accuracy to R_0.

Why This Matters

Impact on research. The paper supplies a shared formal vocabulary (logical deletion, physical deletion, rebuilding) and a reproducible protocol for a problem that prior work evaluated inconsistently, including setups that unrealistically re-added deleted data. It also raises a question the field has largely ignored: deletion quality should be judged jointly on latency, throughput, memory, and post-deletion accuracy, not on a single number.

Real-world applications.

• Retrieval-Augmented Generation systems that must retire outdated documents and add new ones without rebuilding the whole index.
• Recommender systems where products, listings, or media are removed and added continuously.
• Vector databases and search services where user data must be removed promptly to satisfy privacy expectations or deletion requests.
• Any long-running index that must hold a memory budget while serving latency-sensitive queries.

Industry relevance. The trade-offs are directly operational. Logical deletion at roughly 10^9 [1/s] is attractive for write-heavy pipelines but leaks memory linearly and erodes accuracy, which matters for services with strict memory ceilings and SLA-level recall targets. Rebuilding restores accuracy and memory but is orders of magnitude slower at deletion (at most 10^3 [1/s]) and is sensitive to vector dimensionality. Deletion Control gives practitioners a concrete recipe: measure θ and π on a small labeled query set, then choose the cheapest strategy that still meets the required accuracy.

Future Directions

• Validating the framework beyond HNSW. The paper applies the protocol to HNSW specifically; whether the same θ/π behavior and ordering of methods hold for other graph-based indexes, or for IVF- and product-quantization-based systems such as Ada-IVF, SPFresh, FreshDiskANN, MN-RU, and IPGM discussed in related work, is not established.
• Removing the reliance on labeled query data. The paper states that θ and π represent dataset characteristics and cannot be measured unless actual query data is available; estimating them without ground truth would broaden applicability.
• Improving physical deletion's connection repair. The paper notes that physical deletion removes edges without reconnecting neighbors, unlike FreshDiskANN, MN-RU, and IPGM, and leaves the effectiveness of removal dependent on the ANNS implementation and memory layout.
• Studying the interaction between batch size and graph structure more deeply. The finding that larger batches yield higher converged accuracy under physical deletion, and that rebuilding becomes relatively slower under small-batch frequent updates, suggests a batch-size-dependent strategy not yet folded into Deletion Control.

Target Audience

Researchers and engineers working on vector search, vector databases, and approximate nearest neighbor indexes, particularly those building systems that need dynamic insert and delete support. It is also useful for practitioners evaluating storage and latency trade-offs in RAG pipelines or recommendation infrastructure, and for students with an intermediate background in information retrieval or systems who want a concrete, measurable framing of the deletion problem.

Authors’ abstract

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.