arXiv:2607.29173v1 [cs.DB] 31 Jul 2026
MERIT: Efficient In-Place Deletion for Dynamic Graph-Based Approximate Nearest Neighbor Indexes Zekai Wu
Jiabao Jin
Peng Cheng∗
Tongji University Beijing Institute of Technology Beijing, China [email protected]
Tongji University Shanghai, China [email protected]
Tongji University Shanghai, China [email protected]
Wangze Ni
Haoyang Li
Lei Chen
Zhejiang University Hangzhou, China [email protected]
Hong Kong Polytechnic University Hong Kong SAR, China [email protected]
Hong Kong University of Science and Technology Hong Kong SAR, China [email protected]
Junjie Yao
Jingkuan Song
Heng Tao Shen
East China Normal University Shanghai, China [email protected]
Tongji University Shanghai, China [email protected]
Tongji University Shanghai, China [email protected]
ABSTRACT
doi:XX.XX/XXX.XX
Graph-based indexes have become the dominant approach to approximate nearest neighbor search (ANNS) over high-dimensional data and play a crucial role in real-world applications such as retrieval-augmented generation, recommendation systems, and vector databases. Despite extensive progress in static graph construction and search, efficient in-place deletion remains challenging because obsolete vectors must be removed without allowing stale incoming edges to consume search capacity or expensive graph-wide maintenance to interrupt online services, e.g., retrieval-augmented generation (RAG) and recommendation platforms. To address this problem, we propose Merit (MST-based Efficient Repair with Inplace updaTes), an in-place update framework with three core techniques: (1) bounded search-based recovery that combines a deleted vertex’s outgoing neighbors with its readily searchable in-neighbors, (2) 𝑘𝑟 -Minimum Spanning Tree (MST) local repair that promotes local connectivity while retaining multiple routing choices for graph search, and (3) versioned-edge invalidation that immediately filters all stale incoming edges to the deleted vertex and progressively removes them as adjacency lists are rewritten. Its integration with the hierarchical HNSW index and the singlelayer Vamana index demonstrates applicability across distinct graph structures. Extensive experiments on multiple real-world datasets show that Merit processes deletion at nearly the cost of inserting one vector, achieves up to 3.02×–18.87× faster deletion than stateof-the-art (SOTA) methods, and keeps search recall stable or even improves it as deletions accumulate.
Vector representations have become the common substrate for modern data-intensive applications. Text passages, web pages, images, audio segments, videos, user profiles, products, and multimodal objects are routinely embedded into high-dimensional spaces where geometric proximity captures semantic similarity. As a result, approximate nearest neighbor search (ANNS) [2] is no longer a specialized numerical primitive, but a core operator in machine learning [10, 46], information retrieval [44, 57], recommendation systems [11, 29], vector databases [45], and retrieval-augmented generation (RAG) [3, 13]. Among the major ANNS index families, graph-based methods [17, 21, 28, 35, 53] have become the dominant choice in practice [45, 56]. Their appeal is empirical but robust. Sparse proximity graphs provide short navigable paths through high-dimensional data, enabling beam-search-like traversal to achieve high recall with low latency and high throughput. Compared with tree [7, 32, 39], hashing [19, 20, 41], and inverted index-based methods [5, 6, 24], graphbased indexes often provide the best operating point when an online service must trade search quality against tail latency and memory footprint, according to recent benchmarks [4, 47]. The success of graph-based ANNS has been established mostly under a static index assumption that a graph is built once and serves a large number of queries. However, recent vector-search deployments increasingly violate this assumption. As shown in Figure 1,
PVLDB Reference Format: Zekai Wu, Jiabao Jin, Peng Cheng, Wangze Ni, Haoyang Li, Lei Chen, Junjie Yao, Jingkuan Song, and Heng Tao Shen. MERIT: Efficient In-Place Deletion for Dynamic Graph-Based Approximate Nearest Neighbor Indexes. PVLDB, XX(X): XXX-XXX, 20XX. ∗ Corresponding Author.
1
INTRODUCTION
This work is licensed under the Creative Commons BY-NC-ND 4.0 International License. Visit https://creativecommons.org/licenses/by-nc-nd/4.0/ to view a copy of this license. For any use beyond those covered by this license, obtain permission by emailing [email protected]. Copyright is held by the owner/author(s). Publication rights licensed to the VLDB Endowment. Proceedings of the VLDB Endowment, Vol. XX, No. X ISSN 2150-8097. doi:XX.XX/XXX.XX
Query
Embedding Model
Generate Answer
Query Embedding
Vector Database
adjacency, which doubles structural metadata, complicates memory layout, and introduces additional write contention because every insertion, deletion, and neighbor pruning decision must update two coupled adjacency views. Alternatively, the index can recover reverse neighbors by scanning the graph or issuing extra searches. Although this avoids explicit reverse edges, it turns deletion into an expensive maintenance task that must locate the affected vertices and then update and prune their adjacency lists one by one. This paper studies how to make deletions immediately visible to queries, maintain long-term recall stability, and achieve deletion efficiency comparable to insertion. We present Merit, an in-place update mechanism for dynamic graph-based ANNS indexes that sustains efficient updates over long-running workloads. Merit decomposes deletion into three ordered stages: (1) marking the target vertex invalid to immediately remove it from query results while snapshotting its outgoing neighbors as repair seeds; (2) performing bounded searches to identify additional affected vertices and synchronously restoring their local topology through a 𝑘-MST construction; and (3) incrementing the deleted vertex’s version to invalidate all residual stale incoming edges. By repairing a subset of the surviving outgoing and searchable incoming neighborhood, Merit preserves effective navigation paths without requiring exhaustive reverse-edge discovery, while versioned edges safely invalidate stale incoming edges missed during recovery. This design enables Merit to achieve robust long-term recall stability with deletion efficiency comparable to insertion. This paper makes the following contributions. (1) We first reformulate the in-place deletion problem for dynamic graph-based ANNS in §2. Then, we present an experimental study of sustained updates in §3 to analyze why existing SOTA approaches suffer from unstable recall and disproportionately high deletion latency. (2) In §4, we propose Merit, an in-place update mechanism that supports efficient deletion. Merit makes deleted vertices immediately invisible to search and restores the affected local topology without explicitly maintaining incoming-neighbor lists. (3) In §5 we analyze the complexity and long-term stability of Merit. In §6, extensive experiments against SOTA dynamic graph ANNS baselines show that Merit substantially reduces deletion latency while maintaining stable high recall under sustained churn over several public datasets. The remainder of the paper is organized as follows. §7 surveys related work and positions our contribution. §8 concludes the paper.
Graph-based Index
Top-k Results
Dynamic Data Sources
LLM New Documents
Insertion
Deleted Documents
Deletion Corrected Documents Product Updates
Chunking & Embedding Pipeline
Update
Delete + Insert
Memory Updates
Figure 1: Dynamic RAG workloads. RAG knowledge bases need to be refreshed as documents are created, corrected, or removed; search and recommendation catalogs change continuously; user-specific memories are rewritten as users interact with the system; some privacy and compliance workflows require physically removing expired vectors [9, 52, 55]. These workloads call for a dynamic index that supports efficient insertions and deletions while simultaneously serving online queries. Insertion is relatively well aligned with graph-index design [16, 17, 21, 27, 28, 35]. A new vector can be inserted into the existing graph through searching, then connected to a small set of candidate neighbors, and incorporated by local edge updates. Deletion is substantially harder. Removing a vertex not only removes the vector from the searchable set, but also breaks the graph structure that used the vertex as a routing point. If the system only marks the vertex as deleted, queries may still waste candidate slots and distance computations on stale vertices. If the system repairs every affected edge, deletion can become much more expensive than insertion, creating update stalls and service-level instability. Vector replacement inherits the same difficulty because it is commonly implemented as a deletion followed by an insertion. Existing production systems therefore rely on compromises [15, 33, 45]. Soft deletion [28] keeps updates cheap by leaving the deleted vertex in the graph, but stale vertices accumulate and progressively degrade recall and search efficiency. Segmented or log-structured indexing [34, 45] isolates updates in fresh segments, but query processing must merge results across segments, and obsolete segments eventually require consolidation. Periodic rebuilding [40] restores graph quality, but it consumes additional resources and can introduce latency spikes. Recent in-place update schemes [49] reduce the need for rebuilding, yet deletion remains the bottleneck because identifying and repairing all affected edges is still expensive. The root cause is the asymmetric representation used by graph ANN indexes. For compactness and update locality, each vertex stores only its outgoing neighbors. The incoming neighbors of a vertex are not stored explicitly. This design is efficient for search and insertion, but it makes deletion fundamentally indirect. After deleting a vertex 𝑣𝑑 , the index does not know which other vertices contain outgoing edges to 𝑣𝑑 . These vertices are precisely the ones whose adjacency lists must be cleaned or repaired. Given this asymmetry, deletion has only two direct ways to find the affected vertices. Firstly, the index can store explicitly reverse
2
BACKGROUND AND PROBLEM FORMULATION
This section first introduces the background on graph-based ANNS and then formulates the dynamic update model and the in-place deletion problem. Table 1 summarizes the key symbols used in the paper and their descriptions.
2.1
Approximate Nearest Neighbor Search
2.1.1 ANNS Definition. Let 𝑑 ∈ N denote the vector dimension and let X = {𝑥®1, 𝑥®2, . . . , 𝑥®𝑛 } ⊂ R𝑑 be a finite dataset of 𝑛 vectors. For any two vectors 𝑥®𝑎 , 𝑥®𝑏 ∈ R𝑑 , let 𝛿 (𝑥®𝑎 , 𝑥®𝑏 ) denote their distance under a fixed metric or similarity induced distance, such as Euclidean 2
Table 1: Symbols and Descriptions Symbol
Description
X 𝑥, ® 𝑥®𝑞 𝐺 = (𝑉 , 𝐸 ) 𝑛 = |𝑉 | 𝑁 (𝑢 ) 𝐼 (𝑢 ) 𝛿 (·, ·) 𝐿 𝑀 𝑣𝑑 𝐶 b 𝐼 (𝑣𝑑 ) 𝑒 𝑓𝑐′
the base vector dataset a data vector and a query vector a graph with vertex set 𝑉 and edge set 𝐸 the number of vertices in the graph the outgoing neighbors of vertex 𝑢 the incoming-neighbor set of 𝑢 the distance function in the vector space the candidate pool size in graph search the maximum out-degree of the graph the vertex to be deleted the local repair candidate set the recovered approximate in-neighbors of 𝑣𝑑 the beam width used for repair candidate discovery the number of repair edges retained per candidate in 𝑘-MST repair the repaired local subgraph induced on 𝐶
𝑘𝑟 𝐻
Algorithm 1 KnnSearch(® 𝑥𝑞 , 𝐺, 𝐿, 𝑘, 𝑒𝑝) Require: query vector 𝑥®𝑞 , graph index 𝐺 = (𝑉 , 𝐸 ), search pool size 𝐿 ≥ 𝑘, entry point 𝑒𝑝 Ensure: approximate 𝑘 nearest neighbors of 𝑥®𝑞 1: 𝐶 ← {𝑒𝑝 }; mark 𝑒𝑝 as visited 2: 𝑖 ← 0 3: while 𝑖 < |𝐶 | and 𝑖 < 𝐿 do 4: 𝑢 ← 𝐶 [𝑖 ] 5: mark 𝑢 as expanded 6: for all 𝑣 ∈ 𝑁 (𝑢 ) and 𝑣 is not visited do 7: insert 𝑣 into 𝐶 with distance 𝛿 (𝑥®𝑞 , 𝑥®𝑣 ) 8: end for 9: sort 𝐶 by increasing distance to 𝑥®𝑞 and keep the top-𝐿 candidates 10: 𝑖 ← the index of the first unexpanded vertex in 𝐶 11: end while 12: return the first 𝑘 vertices in 𝐶
2.1.2 Graph-Based ANNS.. Graph-based indexes are among the most effective ANNS structures in practice [4, 25, 47]. They represent the dataset X as a sparse proximity graph 𝐺 = (𝑉 , 𝐸), where each vertex 𝑣𝑖 ∈ 𝑉 corresponds to a vector 𝑥®𝑖 ∈ X and each edge encodes a local proximity relation under 𝛿. In practical indexes, 𝐺 is stored as a directed graph. Each vertex 𝑢 maintains a bounded outgoing neighbor set 𝑁 (𝑢) = {𝑣 | (𝑢, 𝑣) ∈ 𝐸}, and search traverses these adjacency lists from one or more entry points. A high-quality graph must balance two structural goals. Local edges should connect nearby vectors so that the final candidates are accurate, while navigable shortcuts should provide short paths across the graph and prevent the traversal from being trapped in a small region. Most graph ANNS methods [17, 21, 28, 35] follow a common construction pattern. For each vertex, the index first obtains a candidate neighbor set through search, incremental insertion, or refinement of an approximate 𝑘 nearest neighbor graph, and then applies a neighbor selection rule to keep only a small number of informative edges [47, 51]. HNSW [28] builds a hierarchy of proximity graphs whose upper layers provide routing and whose base layer supports accurate search. Vamana [21] starts from a coarse graph and uses robust pruning to obtain a bounded-degree graph for large-scale search. NSG [17] refines an approximate 𝑘 nearest neighbor graph (𝑘-NNG) with pruning rules inspired by navigability. These pruning strategies include relative neighborhood graph (RNG) or monotonic relative neighborhood graph (MRNG) criteria [17, 43]. Despite their algorithmic differences, these indexing approaches converge on a common representation in which outgoing adjacency lists are explicitly maintained, while incoming edges are not stored.
distance or cosine distance. Given a query vector 𝑥®𝑞 ∈ R𝑑 and an integer 𝑘 ≤ 𝑛, exact 𝑘 nearest neighbor search returns the set R𝑘 (𝑥®𝑞 ) ⊆ X of size 𝑘 such that every returned vector is no farther from 𝑥®𝑞 than any nonreturned vector. Definition 2.1 (𝑘 nearest neighbor search). Given X, 𝑥®𝑞 , 𝑘, and 𝛿, the exact 𝑘 nearest neighbor result is ∑︁ R𝑘 (𝑥®𝑞 ) = arg min 𝛿 (𝑥®𝑞 , 𝑥). ® (1) R⊆X | R |=𝑘 𝑥® ∈ R
Equivalently, for any 𝑥®𝑟 ∈ R𝑘 (𝑥®𝑞 ) and any 𝑥®𝑠 ∈ X \ R𝑘 (𝑥®𝑞 ), we have 𝛿 (𝑥®𝑞 , 𝑥®𝑟 ) ≤ 𝛿 (𝑥®𝑞 , 𝑥®𝑠 ). In modern vector search workloads, both 𝑛 and 𝑑 can be large enough that exact 𝑘 nearest neighbor search is prohibitively expensive [20, 37]. ANNS therefore builds an index over X and uses the index to avoid exhaustive distance evaluation, trading exactness for lower latency, higher throughput, or fewer distance computations. Definition 2.2 (𝑘 approximate nearest neighbor search). Given X, 𝑥®𝑞 , 𝑘, and 𝛿, ANNS visits a candidate subset C ⊆ X instead of exhaustively scanning all vectors. It returns an approximate result b𝑘 (𝑥®𝑞 ) ⊆ C with | R b𝑘 (𝑥®𝑞 )| = 𝑘, usually by ranking the visited R candidates according to 𝛿 (𝑥®𝑞 , 𝑥). ® We use two query-side metrics throughout the paper. (1) Recall. Recall measures how much of the exact top-𝑘 neighborhood is recovered by the approximate search. For 𝑘 nearest neighbor search, we use Recall@𝑘, defined as b𝑘 (𝑥®𝑞 ) ∩ R𝑘 (𝑥®𝑞 )| |R Recall@𝑘 = , (2) 𝑘 b𝑘 (𝑥®𝑞 ) is the approximate result set and R𝑘 (𝑥®𝑞 ) is the where R b𝑘 (𝑥®𝑞 )| = |R𝑘 (𝑥®𝑞 )| = 𝑘. exact ground-truth result set, with | R (2) Query efficiency. We report queries per second (QPS) for endto-end search throughput and the number of distance computations (NDC) for algorithmic search work. NDC captures how many candidate vectors the graph traversal evaluates before returning the result.
2.1.3 Search Algorithm. Graph-based ANNS is typically executed by a greedy best-first traversal strategy known as beam search [51]. Starting from an entry point 𝑒𝑝, beam search maintains a bounded candidate set of size 𝐿, also called the beam width, and repeatedly explores promising vertices in distance order. Its effectiveness depends on short paths and long-range shortcuts in the graph. When these paths are preserved, beam search can reach high-recall answers with relatively few distance evaluations [28, 35]. Algorithm 1 summarizes the canonical search routine. It initializes the candidate set with the entry point and marks it as visited (Line 1), then sets the scan pointer to the first candidate (Line 2). The 3
HNSW Add
main loop expands the closest unexpanded vertex in the current candidate set (Lines 3–5), evaluates its unvisited outgoing neighbors and inserts them into the candidate set (Lines 6–8), and keeps only the 𝐿 closest candidates before advancing to the next unexpanded vertex (Lines 9–10). The algorithm returns the first 𝑘 candidates as the approximate result (Line 12). In the rest of this paper, we use KnnSearch to refer to this search pattern when discussing queries, insertions, and repairs. The algorithm also exposes why deletions are harmful. A stale outgoing edge can still be read during neighbor expansion (Lines 6– 7), and a deleted vertex can still occupy the candidate set after insertion and pruning (Lines 7–9) unless it is filtered. Even when filtering prevents invalid results, the search budget spent on stale vertices is lost. Under a fixed beam width, this reduces the probability that the search reaches the true nearest-neighbor region.
2.2
Wolverine (HNSW Remove)
0.067
1
18
Batch
35
50
(a) Deep10M, 30% churn
0.323 0.086 0.023
1
18
Batch
35
50
(b) MSong, 30% churn
Figure 2: Average insertion and deletion latency over update batches under the sliding-window workload. Table 2: Recall@10 under accumulated deletions on Sift1M.
Classical ANNS indexes are often described under a static setting, where the dataset is fixed after index construction and the index only needs to answer queries. Modern vector-search deployments, especially RAG systems over continuously refreshed knowledge bases, operate on dynamic datasets. New objects may be inserted as documents arrive, obsolete or expired objects must be deleted, and existing objects may be replaced when their contents or embeddings change. Therefore, a dynamic ANNS index must support querying, insertion, and deletion. Let 𝐺 = (𝑉 , 𝐸) be a graph ANN index over X ⊆ R𝑑 . We consider three online update operations:
2.3
Method
Before
30% deleted
50% deleted
Wolverine [26] IP-Vamana [49]
0.9962 0.9946
0.9932 0.9967
0.9883 0.9975
The Inefficiency of Current Approaches
Dynamic graph-based ANNS systems typically prioritize efficient insertion and query processing, while postponing the more complex deletion path through auxiliary mechanisms such as lazy deletion [40]. This design introduces a pronounced asymmetry under sustained update workloads. Insertion latency remains close to the cost of one graph search followed by bounded neighbor updates. By contrast, deletion latency either becomes highly variable because the actual maintenance work is deferred as a batch job [26], or increases substantially when the system performs reverse-edge discovery and local graph repair during deletion. We first examine critical limitations of existing dynamic graphbased ANNS methods [26, 40, 49]: the latency gap between deletion and insertion, and the loss of query recall as updates accumulate. We use a sliding-window quantification (SWQ) workload [26]: the index is built from an initial window containing 70% of the base vectors; in each subsequent round, 1% of the vectors expire and are deleted, while the same number of new vectors are inserted, keeping the index size fixed. The workload runs for 50 rounds, and we measure insertion and deletion latencies in each round. We evaluate the in-memory Vamana update path of FreshDiskANN [40], denoted FreshVamana (also, IP-Vamana [49]). On Deep10M [6], insertions into HNSW [28] and Vamana [21] have average latencies of 0.022 and 0.072 ms, whereas deletions with Wolverine [26], FreshVamana, and IP-Vamana [49] take 0.048, 1.009, and 0.217 ms, respectively. Relative to insertion on their underlying graph, the deletion-toinsertion ratios are 2.17×, 14.03×, and 3.02×; the corresponding ratios on MSong [8] are 2.02×, 9.41×, and 1.86×. Figure 2 therefore exposes a persistent update asymmetry across both graph families and datasets. To examine recall stability, we separately measure Recall@10 as deletions accumulate on Sift1M. As shown in Table 2, Wolverine’s recall decreases from 0.9962 to 0.9883 after 50% of the vectors are deleted, whereas IP-Vamana maintains stable recall throughout the deletion schedule. The effectiveness of in-place repair depends on whether it identifies the affected in-neighbors and restores their local connections; incomplete recovery leaves search paths unrepaired. These observations show that existing methods struggle to
® adds a new vector to the indexed set by searching • Insert (𝑥) the existing graph for candidate neighbors, selecting a bounded outgoing neighborhood for the new vertex, and applying local edge updates to preserve navigability. • Delete(𝑣𝑑 ) removes an existing vertex from the logical dataset and repairs the graph so that subsequent queries neither return the deleted object nor rely on it as a persistent routing shortcut. • Replace(𝑣, 𝑥®′ ) updates the vector value associated with an object. In most graph ANNS systems, this operation is implemented as Delete(𝑣) followed by Insert (𝑥®′ ). An in-place deletion immediately removes the deleted vertex 𝑣𝑑 from the current graph 𝐺 during the update stream, rather than deferring removal to a later rebuild or compaction phase. It must avoid the high storage and maintenance overhead of incoming edges, while repairing the local connectivity around 𝑣𝑑 so that the remaining graph continues to support accurate and efficient search. Update Efficiency. We consider a batch of 𝑏 replacements, each implemented as one deletion followed by one insertion. Let 𝑇ins and 𝑇del denote the total elapsed times of the resulting 𝑏 insertions and 𝑏 deletions, respectively. We report the average insertion, deletion, and update latencies as
𝐿del = 𝑇del /𝑏,
Latency (ms)
Latency (ms)
0.298
0.015
IP-Vamana Remove
1.216
1.32
Update Model
𝐿ins = 𝑇ins /𝑏,
Vamana Add
FreshVamana Remove
𝐿upd = 𝐿ins + 𝐿del .
Here, 𝐿upd measures the maintenance latency of one delete–insert replacement to refresh one indexed vector in the dynamic workload. 4
Deleted Vertex
Query Point
104 103 102 10
1
10
0
HNSW (Ground truth) Recovered by Wolverine
10
(a)
(b) Search Path
Removed Outgoing Edges
0
1
10 In-degree size
(a) HNSW Stale incoming edges
Number of vertices
Top-1 NN
Number of vertices
Entry Vertex
10
2
104 103 102 101
Vamana (Ground truth) Recovered by IP-Vamana
100 10
0
101 102 In-degree size
(b) Vamana
Figure 4: Distribution of original in-degree and recovered inneighbors under different reverse-edge discovery methods.
Figure 3: A toy example illustrating the challenges of graphbased ANNS deletion. incoming-edge maintenance, and confines repair to a sufficiently local region for online serving.
meet the two requirements simultaneously: 1) making deletion as efficient as insertion, and 2) maintaining stable query recall after sustained updates.
)
3.2
3.2.1 Why Recall Degrades. Lazy-deletion and batch-cleanup methods, including FreshDiskANN [40], defer physical deletion. A deleted vertex is marked invalid, but its adjacency records and the reverse edges pointing to it remain in the graph until a later consolidation. Query-time filtering prevents such vertices from being returned as final answers, but it does not remove them from the search process. They may still be visited and inserted into the candidate set. Under a fixed candidate budget 𝑒 𝑓search , each stale candidate consumes capacity that could have been used to explore a live vertex, and each invalid expansion introduces additional distance computations. This effect compounds over long update streams. As stale vertices and stale edges accumulate, the logical graph observed by queries becomes increasingly different from the current live dataset. The search algorithm traverses paths constructed for an older dataset, whereas the result set is evaluated against the current dataset. Periodic consolidation can reset the index state, but the system then faces a tradeoff between quality degradation and expensive rebuilding rather than maintaining stable online behavior. In-place methods approximate the affected in-neighbors. Wolverine [26] uses two-hop discovery, while IP-Vamana [49] uses graph search. We evaluate their ability to recover the in-neighbor set 𝐼 (𝑣𝑑 ) of a deleted vertex 𝑣𝑑 by comparing each vertex’s original indegree with the number of recovered in-neighbors. On Sift1M, the average recovered-to-original in-degree ratios are 0.421 and 0.664, respectively (Figure 4). The higher recovery ratio of IP-Vamana is consistent with its more stable recall in Table 2. Recovery is particularly poor for high-in-degree vertices due to the hubness effect in high-dimensional spaces [42]. Missing in-neighbors leave stale incoming edges that consume candidate set capacity and degrade search efficiency and recall, causing recall to continue declining after deletion. This suggests that effective graph repair may depend more on recovering routing-relevant neighbors than on exhaustively enumerating all in-neighbors. Motivated by this observation, Merit uses version mismatches to invalidate stale incoming edges missed during recovery.
3
ANALYSIS ON DYNAMIC GRAPH-BASED ANNS 3.1 Key Challenges
𝑣'
Limitations of Existing Deletion Strategies
The first challenge is identifying the vertices affected by a deletion. An insertion can be completed by searching the graph for candidate neighbors and then adding bidirectional links between the new vertex and these candidates. Deletion, however, must first identify the reverse side of the graph affected by the removed vertex. After deleting 𝑣𝑑 , the system has to repair vertices that use 𝑣𝑑 as an outgoing neighbor, namely the in-neighbor set 𝐼 (𝑣𝑑 ) = {𝑢 ∈ 𝑉 : 𝑣𝑑 ∈ 𝑁 (𝑢)}. Their adjacency lists may still contain stale edges to 𝑣𝑑 and therefore need to either remove the obsolete edge or introduce replacement edges to promote local connectivity. As illustrated in Figure 3, the outgoing edges of a deleted vertex can be removed immediately, but incoming edges from other vertices may remain stale. Unfortunately, 𝐼 (𝑣𝑑 ) is not stored explicitly by graph-based ANNS indexes. Recovering it exactly requires a full scan over the graph, whereas maintaining it explicitly increases memory consumption and turns each update into a bidirectional adjacency-maintenance operation. The second challenge is repairing the structural hole left by deletion. Graph search is effective because the index contains both local proximity edges and long-range routing shortcuts. A deleted vertex 𝑣𝑑 may serve as a bridge between nearby regions or as a hub traversed by many beam-search trajectories, as shown in Figure 3. Once 𝑣𝑑 is removed, a search path from the entry point 𝑣𝑒𝑝 to the nearest neighbor 𝑣𝑛 of query 𝑣𝑞 may be broken if it relies on the search path 𝑣𝑒𝑝 { 𝑣𝑑 { 𝑣𝑛 , thereby changing the search result. Repeated deletions can gradually fragment the navigable structure even when all remaining vectors are unchanged. Thus, filtering deleted vertices only from final answers is insufficient. The index must promote sufficient local connectivity for subsequent searches to reach the same regions with comparable computational cost. These two challenges impose conflicting system requirements. Exact reverse-edge discovery and aggressive structural repair improve index accuracy, but they increase deletion latency. Lazy deletion reduces update latency, but it allows the graph topology to degrade over time. A practical dynamic graph index therefore needs a deletion mechanism that takes effect immediately, avoids explicit
3.2.2 Why Deletion Latency Is High. In graph-based indexes, insertion is dominated by one graph search followed by local neighbor selection. With maximum out-degree 𝑀, candidate-list size 𝐿, and index size 𝑛, its cost is commonly characterized as 𝑂 (𝑀 log 𝑛 + 𝑀𝐿) [17, 47]. However, deletion is more involved. The system must 5
Logical Invalidation (§4.2)
…
𝑣$ 𝑣% 𝑣( …
Vertex-level Lock
𝑒𝑝
… Making 𝑣$ immediately invisible
𝑣'
𝑣%
𝑣%
𝑣(
𝑣'
𝑣!
Augmented in-neighbor
k-MST Construction
𝑣"
𝑣!
𝑣"
…
…
… level 0 1
𝑣!
𝑣"
version
0
0
𝑣(
𝑣! , 𝑣" , 𝑣# , 𝑣$ 𝑣#
⋅⋅⋅
vertex
𝑣'
𝑣%
neighbors
⋅⋅⋅
⋅⋅⋅ ⋅⋅⋅
𝑣% 0→1
⋅⋅⋅ ⋅⋅⋅
𝑣'
Stale Reference Filtered 𝑣%
stored version of 𝑣# : 0 version (𝑣#) = 1
𝑣'
𝑣%
MST start point
Version Table
Physical Cleanup (§4.4)
𝑣"
Repaired edges
𝑣!
𝑣(
Local Buffer
𝑒𝑝
𝑣"
…
𝑣!
Candidate Pool
𝑣"
𝑣!
…
𝑣# 0 𝑣! 0 0 0 Atomic 0 Set 𝑣& 1 0 𝑣' 0 … … (n bits)
MERIT Local Topology Repair (§4.3)
𝑣#
Bitmap
Graph-based Index G 𝑣#
Repair Seeding (§4.2)
𝑣(
𝑣$
Figure 5: The three algorithmic components of Merit deletion: (1) logical invalidation and local repair seeding for the deleted vertex; (2) approximate construction of the affected repair candidate set and 𝑘-MST repair over the local candidate set; and (3) versioned-edge invalidation for residual reverse edges. identify vertices whose neighbor lists contain the deleted vertex 𝑣𝑑 , remove these stale incoming edges, determine the affected neighborhood, and repair local connectivity for the involved vertices. Although a deletion can be made almost instantaneous by simply marking 𝑣𝑑 as invalid, such lazy deletion leaves the graph structure stale. Existing SOTA methods [26, 40, 49] therefore perform structural repair during deletion, but this design introduces extra computational overhead. Naive exact reverse-edge cleanup scans adjacency lists and therefore costs 𝑂 (|𝐸|) per deletion, which is unacceptable for large online indexes. FreshDiskANN [40] avoids this cost during individual deletions through lazy updates and deferred batch cleanup. However, during cleanup it examines pairs formed by the outgoing and incoming neighbors of deleted vertices, leading to an average update cost of 𝑂 (𝑀 2 ), where 𝑀 is the maximum out-degree. IPVamana [49] introduces search-based cleanup to avoid a full graph scan for each deletion, but it pays for additional graph searches and incurs a repair cost of 𝑂 (𝑀 log 𝑛 + 𝑐 (𝐿 + 𝑀)(log 𝐿 + 𝑀)), where 𝐿 is the search candidate-list size and 𝑐 is a hyperparameter. Wolverine [26] collects two-hop neighbors of the deleted vertex and heuristically selects valuable repair targets, with repair cost 𝑂 (𝑀 + 𝑀 min(𝑀 2 + 𝑀, 𝐶𝑠 ) + 𝑀𝜃 in ), where 𝐶𝑠 and 𝜃 in are hyperparameters. These repair procedures may still miss affected vertices while imposing substantial online work, making deletion latency significantly higher than insertion latency.
4
repair the affected local topology without explicitly maintaining incoming-neighbor lists.
4.1
Overview
The design of Merit follows three principles: (1) locality: each update operation should touch only a small and bounded neighborhood centered at the deleted vertex; (2) immediacy: the deleted vertex should become invisible to subsequent searches as soon as it is marked invalid; and (3) structural stability: long-term deletion and insertion operations should keep graph quality within a stable range rather than cause progressive degradation. Guided by these principles, Merit decomposes each deletion into three ordered components with distinct responsibilities, as illustrated in Figure 5. (1) Logical invalidation and repair seeding. We mark 𝑣𝑑 invalid so that subsequent operations (e.g., searches, insertions and deletions) ignore it, and collect its outgoing neighbors as the initial seed set for local repair (§4.2). (2) Merit local topology repair. We first approximate the missing in-neighbors of 𝑣𝑑 by a quick bounded search and merge them with the outgoing-neighbor seed set. We then run an incremental MST-style construction over the local candidate set and attach each candidate with up to 𝑘𝑟 short edges under the graph degree bound. The neighborhood snapshot preserves the repair evidence while keeping this stage local and bounded (§4.3). (3) Versioned-edge invalidation. We remove the residual information of 𝑣𝑑 from the graph-based index and increment version(𝑣𝑑 ), ensuring that any remaining stale incoming edges are automatically discarded upon their next access (e.g., during search, insertion, or deletion) due to a version mismatch (§4.4).
THE MERIT ALGORITHM
With the goal of making deletion as efficient as insertion while maintaining stable recall, we propose Merit, an in-place update mechanism for dynamic graph-based ANNS. Merit is designed to make deleted vertices immediately invisible to search and to 6
Algorithm 2 Merit-Delete(𝑖𝑑)
Line 6 snapshots its outgoing neighborhood as the initial repair seed. Line 7 invokes MeritRepair, which expands the affected set through bounded local search and incoming-edge discovery, and then reconstructs local connections efficiently using a 𝑘-MST repair graph. Finally, Lines 8–9 advance the version of 𝑣𝑑 and physically remove its remaining outgoing records. This ordering preserves the pre-deletion topology long enough to guide repair while preventing the deleted vertex from re-entering the active graph.
Require: Vertex key 𝑖𝑑, index I = ⟨𝑉 , 𝐺, 𝑀⟩, entry point 𝑒𝑝, repair parameters 𝑒 𝑓𝑐′, 𝑘𝑟 Ensure: Updated graph 𝐺 ′ 1: 𝑣𝑑 ← Lookup(I, 𝑖𝑑) 2: if 𝑣𝑑 = ⊥ or Invalid(𝑣𝑑 ) then 3: return 𝐺 4: end if 5: Mark 𝑣𝑑 as logically invalid 6: 𝑁 (𝑣𝑑 ) ← GetNeighbors(𝐺, 𝑣𝑑 ) 7: 𝐺 ′ ← MeritRepair(𝐺, 𝑣𝑑 , 𝑁 (𝑣𝑑 ), 𝑒𝑝, 𝑒 𝑓𝑐′ , 𝑘𝑟 ) 8: Increment version(𝑣𝑑 ) 9: Remove 𝑣𝑑 and its outgoing edges from 𝐺 ′ 10: return 𝐺 ′
4.2
4.3
Merit Local Repair
The goal of local repair is not to reconstruct every edge incident to 𝑣𝑑 , but to preserve the routes that used to pass through it. Such a route has the form 𝑢 → 𝑣𝑑 → 𝑤, where 𝑢 is an in-neighbor of 𝑣𝑑 and 𝑤 is an out-neighbor. After deleting 𝑣𝑑 , the former may lose its next hop, whereas the latter may lose the incoming access that made it reachable from the surrounding graph. Repairing only one side cannot bridge this broken route: using only out-neighbors leaves the vertices that pointed to 𝑣𝑑 disconnected from the repair, while using only in-neighbors provides no replacement destinations for their removed edges. We therefore repair the union of the two boundary sets, 𝐶 = 𝑁 (𝑣𝑑 ) ∪ b 𝐼 (𝑣𝑑 ) \ {𝑢 | Invalid(𝑢)},
Logical Invalidation and Repair Seeding
Deleting a vertex from a proximity graph creates two competing requirements. The vertex should immediately cease to participate in subsequent queries and graph updates, whereas its existing neighborhood should remain temporarily available for identifying and repairing the affected region. Physically removing the vertex and its edges at the beginning would destroy useful structural evidence before repair is performed. Merit therefore separates logical invalidation from physical removal. Given a vertex 𝑣𝑑 to be deleted, Merit first marks it as logically invalid. Once this state becomes visible, 𝑣𝑑 is excluded from search results, search expansion, repair candidates, and newly constructed adjacency lists. In particular, repair cannot introduce new edges incident to 𝑣𝑑 , and an adjacency list rewritten during repair filters out invalid vertices. Edges that still reference 𝑣𝑑 after invalidation are treated as stale structural records. This separation gives deletion a well-defined visibility point without requiring all incident edges to be removed immediately. Once the invalidation state is visible, graph operations filter 𝑣𝑑 even if an adjacency list still contains its identifier. They also check the vertex state before using 𝑣𝑑 as an expansion vertex, returning it as a result, or inserting a new incident edge. Consequently, the logical state of a vertex, rather than the immediate absence of every stale incoming edge, determines its eligibility to participate in the graph. After invalidating 𝑣𝑑 , Merit snapshots its outgoing neighborhood, 𝑁 (𝑣𝑑 ) = GetNeighbors(𝐺, 𝑣𝑑 ), before physically detaching it. The snapshot preserves the local topology that would otherwise be destroyed by other online operations (e.g., insertions and deletions) and provides the direct seeds for subsequent repair. Thus, 𝑣𝑑 and its neighborhood remain available as evidence for locating the affected region, while logical invalidation prevents 𝑣𝑑 from participating in the repaired graph. Starting from these degree-bounded seeds, MeritRepair discovers affected vertices through local search and incoming-edge inspection, which will be described in §4.3. Algorithm 2 summarizes the whole deletion process, including logical invalidation, repair seeding, and physical removal. Lines 1– 4 resolve the external key and make sure the vertex is valid in the current graph. Line 5 marks 𝑣𝑑 as logically invalid and defines the visibility point of deletion. Once this state is observed, 𝑣𝑑 is no longer eligible to participate in queries or graph updates.
where 𝑁 (𝑣𝑑 ) is available from the adjacency snapshot, b 𝐼 (𝑣𝑑 ) is an approximate recovery of the in-neighbors, and the function Invalid(𝑢) filters out invalid vertices. This union is a deliberately local candidate set: it contains the two endpoints of paths broken by the deletion, rather than unrelated vertices merely close to 𝑣𝑑 in the metric space. Definition 4.1 (Local repair graph). For a deletion of 𝑣𝑑 , the local repair graph 𝐻 = (𝐶, 𝐸 𝑅 ) contains the surviving out-neighbors and recovered in-neighbors in 𝐶, and the repair edges 𝐸 𝑅 inserted among them after 𝑣𝑑 is removed. The graph does not explicitly store 𝐼 (𝑣𝑑 ), and finding it exactly would require a reverse-edge index or a scan of all adjacency lists. Instead, we query the graph with 𝑥®𝑣𝑑 using a small beam width 𝑒 𝑓𝑐′ . Vertices that are easy to reach near 𝑣𝑑 are precisely the ones most likely to participate in ordinary search paths through its neighborhood. We retain a returned vertex only if its adjacency list actually contains 𝑣𝑑 ; thus, metric proximity proposes candidates, while the edge test certifies that each retained vertex is an in-neighbor. The recovery is intentionally approximate. Its purpose is to cover the readily searchable part of 𝐼 (𝑣𝑑 ) that affects near-term navigation, not to enumerate all reverse edges, which are safely invalidated by the version mechanism in §4.4. Because graph-search work grows with its search-list width, lowering 𝑒 𝑓𝑐′ directly bounds the recovery cost [48]. This turns reverse-neighbor discovery into one fast, bounded search rather than a global cleanup. Once 𝐶 is fixed, the repair objective is to promote local connectivity with short edges. This motivates an MST candidate backbone. Definition 4.2 (MST repair). Assume 𝐶 is non-empty. Let 𝐾 (𝐶) be the complete weighted graph on 𝐶 with edge weight 𝛿 (𝑢, 𝑣), and let 𝑇 be an MST of 𝐾 (𝐶). MST repair inserts the bidirectional edges of 𝑇 into the index, forming a minimum-weight connected backbone over 𝐶. 7
Entry Vertex
Incoming Neighbor
Outgoing Neighbor
Deleted Vertex
𝑣!
(a) Search Path
𝑣!
𝑣#
𝑏$ 𝑣%
𝑣$
(b)
(c)
Ignored Outgoing Edge
Algorithm 3 Merit: local candidate construction and repair Require: Deleted vertex 𝑣𝑑 with vector 𝑥®𝑣𝑑 , neighborhood snapshot 𝑁 (𝑣𝑑 ), graph 𝐺, entry 𝑒𝑝, beam width 𝑒 𝑓𝑐′ , repair degree 𝑘𝑟 , degree bound 𝑀 Ensure: Updated local topology of 𝐺 1: R ← KnnSearch(𝑥®𝑣𝑑 , 𝐺, 𝑒 𝑓𝑐′ , 𝑒 𝑓𝑐′ , 𝑒𝑝) 2: I ← {𝑢 ∈ R | ¬Invalid(𝑢) ∧ 𝑣𝑑 ∈ 𝑁 (𝑢)} 3: 𝐶 ← {𝑢 ∈ 𝑁 (𝑣𝑑 ) | ¬Invalid(𝑢)} ∪ I 4: if 𝐶 = ∅ then 5: return 6: end if 7: 𝑠 ← arg min𝑢 ∈𝐶 𝛿 (𝑢, 𝑒𝑝) 8: 𝑇 ← {𝑠}, 𝑈 ← 𝐶 \ {𝑠} 9: while 𝑈 ≠ ∅ do 10: (𝑢, 𝑤 ★) ← arg min (𝑢,𝑤 ) ∈𝑈 ×𝑇 𝛿 (𝑢, 𝑤) 11: 𝑃 ← 𝑘𝑟 closest vertices to 𝑢 in 𝑇 12: for 𝑤 ∈ 𝑃 do 13: InsertAndPrune(𝐺, 𝑢, 𝑤, 𝑀) 14: InsertAndPrune(𝐺, 𝑤, 𝑢, 𝑀) 15: end for 16: 𝑇 ← 𝑇 ∪ {𝑢}, 𝑈 ← 𝑈 \ {𝑢} 17: end while 18: return
𝑣"
𝑣"
𝑏!
𝑎!
MST Start Point
Repair Candidate Edge
𝑣# 𝑣%
𝑣$
Repaired Edge
Figure 6: A toy example of Merit local repair. (a) Searchbased recovery of repair candidates. (b) Incremental 𝑘𝑟 -MST construction with 𝑘𝑟 = 2. (c) The repaired local topology. 𝑣 Although a MST guarantees 𝑣 𝑏 connectivity, connectivity alone 𝑣 is insufficient for approximate nearest neighbor search 𝑏 𝑣 (ANNS). 𝑣 𝑣 𝑎 Because each cut in an MST is crossed by only one edge, distant 𝑣 𝑣 bridge edges, degree pruning, or subsequent edge deletion may𝑣 𝑣 easily disconnect local neighborhoods and undermine the intended repair. Moreover, adding only one repair edge per vertex can force queries to follow a single local route in extreme cases, creating tree-like bottlenecks [31]. Effective search expansion therefore requires multiple promising outgoing transitions from the local tree structure. Accordingly, Merit retains MST edges as mandatory connections and supplements them with a small number of nearby candidate edges. These additional edges improve branching and path diversity during search, while avoiding the computational cost of an all-pairs reconnection strategy [40]. !
!
"
"
$
#
!
#
!
$
%
$
%
Figure 6 illustrates the complete process. In Figure 6(a), search paths from the entry vertex reach vertices around 𝑣𝑑 ; the adjacency test distinguishes true recovered in-neighbors from merely nearby vertices, and the ignored outgoing edges of 𝑣𝑑 are already available from its snapshot. Figure 6(b) shows the incremental construction for 𝑘𝑟 = 2. The construction starts from 𝑣 1 , the candidate closest to the entry point. The first candidate 𝑣 2 can create only 𝑎 1 = (𝑣 2, 𝑣 1 ) because the current tree contains one vertex. After 𝑣 2 joins the tree, 𝑣 3 can create two candidate edges, 𝑏 1 = (𝑣 3, 𝑣 1 ) and 𝑏 2 = (𝑣 3, 𝑣 2 ). Figure 6(c) shows the repaired local topology after the same rule is applied to the remaining candidates. Algorithm 3 implements the two stages for the single-layer graph used in our description. Lines 1–3 construct the repair candidates. Line 1 runs the bounded search with 𝑥®𝑣𝑑 and returns the pool R. Line 2 filters this pool to live vertices whose adjacency lists contain 𝑣𝑑 , producing I = b 𝐼 (𝑣𝑑 ). Line 3 unions these recovered in-neighbors with the outgoing-neighbor snapshot 𝑁 (𝑣𝑑 ). Lines 4– 17 construct the 𝑘𝑟 -MST repair graph. Lines 4–6 make an empty candidate set a no-op. Line 7 chooses the candidate closest to 𝑒𝑝 as the construction start, and Line 8 partitions the candidates into the connected set 𝑇 and unconnected set 𝑈 . Lines 9–17 repeat until every candidate is attached. Line 10 applies the Prim rule, selecting the minimum-distance pair across the cut (𝑈 ,𝑇 ). Line 11 chooses up to 𝑘𝑟 closest vertices to 𝑢 in 𝑇 ; when |𝑇 | < 𝑘𝑟 , it simply uses all available tree vertices, as for edge 𝑎 1 in Figure 6(b). Lines 12–15 insert both directions of every selected edge and prune the affected lists to degree 𝑀. Line 16 then moves 𝑢 into 𝑇 .
Definition 4.3 (𝑘-MST repair). Given the MST backbone 𝑇 on 𝐶, a 𝑘𝑟 -MST repair graph 𝐻 is obtained by attaching each candidate to up to 𝑘𝑟 closest neighbors in the already connected candidate set, including its MST parent, subject to the graph degree bound 𝑀. For any non-empty 𝐶 and 𝑘𝑟 ≥ 1, 𝑘𝑟 -MST guarantees that the local repair graph on 𝐶 remains connected after RNG-based pruning. When a new vertex is added, its Prim attachment is included among the selected neighbors; inductively, these edges form the MST backbone 𝑇 , while the remaining at most 𝑘𝑟 − 1 edges provide a bounded amount of routing redundancy. To see why pruning preserves this backbone, consider any MST edge (𝑢, 𝑣) ∈ 𝑇 . If it violated the RNG criterion [43], there would exist a candidate 𝑤 such that both 𝛿 (𝑢, 𝑤) < 𝛿 (𝑢, 𝑣) and 𝛿 (𝑣, 𝑤) < 𝛿 (𝑢, 𝑣). Removing (𝑢, 𝑣) partitions 𝑇 into two components. Whichever component contains 𝑤, either (𝑢, 𝑤) or (𝑣, 𝑤) crosses the cut with smaller weight than (𝑢, 𝑣), producing a spanning tree of smaller total weight and contradicting the minimality of 𝑇 . Hence every MST edge satisfies the RNG criterion, i.e., 𝑇 ⊆ RNG(𝐶). RNG pruning can therefore discard redundant repair edges but not the MST backbone, so InsertAndPrune (see Algorithm 3) preserves connectivity of the repaired candidate set while the additional 𝑘𝑟 edges improve branching and path diversity. We choose the closest candidate to the search entry point 𝑒𝑝 as the MST start point. This choice biases the repaired structure toward the direction from which graph search is likely to enter the local region, allowing the search to expand progressively into the tree while avoiding an unnecessarily indirect initial access to the repaired candidates. We use this as a navigation heuristic rather than claiming that the resulting tree preserves the original routes or minimizes search-path length.
4.4
Versioned-Edge Invalidation
Local repair adds candidate routes within the searchable part of the affected neighborhood, but it does not recover every in-neighbor of 8
Table 3: Evaluation Datasets.
𝑣𝑑 . Consequently, an undiscovered vertex 𝑢 may still store a stale incoming edge 𝑢 → 𝑣𝑑 . Finding and removing all such edges would require either explicit in-neighbor lists or periodic scans of the entire graph. Merit avoids both requirements by separating logical invalidation from physical removal. A version change immediately makes every stale edge to 𝑣𝑑 unusable, while ordinary graph operations gradually remove obsolete edge entries from their containing adjacency lists. To support this separation, each stored edge carries the version of its target vertex at the time the edge is created. The index additionally maintains a global version table V with one current version V [𝑣] for every vertex slot 𝑣. For example, when an adjacency-list element is represented by a 64-bit word, Merit uses the high 16 bits for the target version and the low 48 bits for the target identifier. The resulting encoding is
5.1
low 48 bits
The version belongs to the target 𝑣, rather than the source 𝑢, because one update to V [𝑣] must invalidate incoming edges to 𝑣 stored across many different adjacency lists. The 48-bit identifier field supports up to 248 vertex slots; other word layouts can use the same scheme with a different bit allocation. An edge word with decoded fields (𝜈𝑒 , 𝑣), where 𝜈𝑒 is the stored target version, is valid only if 𝜈𝑒 = V [𝑣] ∧ ¬Invalid(𝑣). Deleting 𝑣𝑑 increments V [𝑣𝑑 ] after marking the vertex invalid. Every previously stored edge 𝑢 → 𝑣𝑑 contains the preceding version and therefore fails this check, regardless of where the edge resides or whether 𝑢 was found during local repair. A single change to the version table thus logically invalidates all residual stale incoming edges without locating them individually. This property also prevents a stale edge from becoming valid merely because the physical slot of 𝑣𝑑 is later reused, since a new edge to that slot is encoded with its new current version. During beam search, Merit decodes each edge word and excludes a version-mismatched or invalid target before the target enters the candidate queue or is expanded (i.e., checked in Line 6 of Algorithm 1). Hence, physically retained stale incoming edges consume neither result capacity nor search-expansion budget. The same filtered view is used by graph updates. When insertion, deletion repair, or neighbor pruning rewrites an adjacency list, it copies only currently valid neighbors into the new list. Stale edge entries are omitted, and newly inserted edges are stamped with the targets’ current versions. The rewritten list replaces the previous adjacency data, thereby removing any obsolete edge entries it contained. Adjacency lists that are never updated may retain stale edge entries physically, but, before version wrap-around, those entries remain invisible to graph operations. Therefore, continued operation progressively compacts touched lists and requires no periodic full-graph cleanup.
5
Dim
Size
#Queries
Metric
Sift1M [22] Gist1M [22] Deep1M [6] Deep10M [6] Deep100M [6] GloVe [36] MSong [8]
128 960 96 96 96 100 420
1,000,000 1,000,000 1,000,000 10,000,000 100,000,000 1,183,513 994,185
10,000 1,000 10,000 10,000 10,000 10,000 1,000
ℓ2 ℓ2 cosine cosine cosine cosine ℓ2
Complexity Analysis
In this part, we analyze the expected cost of a single deletion in Merit. The deletion process consists of three main components: invalidation, local repair, and versioned-edge invalidation. Let 𝑛 = |𝑉 |, let 𝑀 be the maximum out-degree, and let 𝐶 be the local repair candidate set. Logical invalidation, neighborhood snapshotting, and physical removal only take 𝑂 (|𝑁 (𝑣𝑑 )|) = 𝑂 (𝑀) time. Recovering the in-neighbor candidates through bounded beam search requires 𝑂 (𝑒 𝑓𝑐′ log 𝑛) distance computations [35, 47, 48]. The heap-optimized Prim construction [23] takes 𝑂 (|𝐸𝐶 | log |𝐶 |) = 𝑂 (|𝐶 | 2 log |𝐶 |) time, where 𝐸𝐶 is the edge set of the implicit complete graph over 𝐶, while inserting and pruning up to 𝑘𝑟 edges for every candidate takes 𝑂 (|𝐶 |𝑘𝑟 𝑀) time. Notably, incrementing the version counter only takes 𝑂 (1) time. The deletion cost is therefore 𝑂 𝑀 + 𝑒 𝑓𝑐′ log 𝑛 + |𝐶 | 2 log |𝐶 | + |𝐶 |𝑘𝑟 𝑀 .
𝑒𝑢→𝑣 = V [𝑣] ≪ 48 | id(𝑣) . |{z} |{z} high 16 bits
Dataset
Because |𝐶 | ≤ 𝑀 + 𝑒 𝑓𝑐′ , the repair cost depends only on configured local bounds rather than unbounded reverse degree. With 𝑒 𝑓𝑐′ = 𝑐𝑀 for a small constant 𝑐 and fixed 𝑘𝑟 , the total cost is 𝑂 (𝑀 log 𝑛 + 𝑀 2 log 𝑀). Unlike prior update methods [26, 49], this analysis also includes the cost of handling residual stale incoming edges, which constitute a significant component of deletion cost. For the space complexity, the graph occupies 𝑂 (𝑛𝑀) space, while the version table and deletion bitmap add 𝑂 (𝑛) space.
5.2
Lifetime of the Version Counter
The worst case is deterministic: a physical slot wraps after 𝑉max = 216 = 65 536 reuses, after which a sufficiently old edge could exhibit the ABA problem [12]. For context, we also give a probability bound under an idealized uniform-reuse model: each of 𝑈 increments independently selects one of 𝑛 slots uniformly. Then 𝑋𝑖 ∼ Binomial(𝑈 , 1/𝑛) with mean 𝜇 = 𝑈 /𝑛. For 𝜇 < 𝑉max , a union bound and Chernoff bound [30] give 𝑉max 𝑔(𝜇) = 𝑉max ln − 𝑉max + 𝜇, 𝜇 i h Pr max 𝑋𝑖 ≥ 𝑉max ≤ 𝑛 exp[−𝑔(𝜇)].
(3)
𝑖
Solving 𝑛 exp[−𝑔(𝜇)] ≤ 𝛿 gives a model-dependent safe budget 𝑈 = 𝑛𝜇. For example, 𝑛 = 108 and 𝛿 = 10−6 give 𝜇𝛿 ≈ 63 502 and 𝑈 safe ≈ 6.35 × 1012 version increments, corresponding to about 20.1 years at 104 increments per second. This budget suggests that the 16-bit version encoding is sufficiently durable for long-running industrial deployments under the assumed highly dynamic workload.
COMPLEXITY AND LIFETIME 6
In this section, we analyze the complexity of Merit and provide a probabilistic bound on the lifetime of the version counter.
EXPERIMENTAL EVALUATION
Our evaluation answers five research questions. 9
40
0.019
Batch (a) Sift1M, 5%.
0
20
40
2.165 0.025
17.512
0.326
0.235
Batch (b) Sift1M, 50%.
Vamana Add
0.073
0
20
0.016
40
Batch (c) Deep1M, 5%.
0
20
40
2.558 0.374 0.055
Batch (d) Deep1M, 50%.
Time (ms/op)
20
MeritVamana 1.465
Time (ms/op)
0
Time (ms/op)
0.081
0.188 0.018
Time (ms/op)
Time (ms/op)
0.346
1.987
IP-Vamana
19.995
Time (ms/op)
FreshVamana 1.483
20.977
1.31 0.42
0.135
0
20
40
0.043
Batch (e) GloVe, 5%.
0
20
40
Batch (f) GloVe, 50%.
Figure 7: Amortized deletion time for Vamana-based methods. The gray dashed line marks the Vamana insertion time.
0.037
0.037
0
20
40
0.024
Batch (a) Sift1M, 5%.
0.093
0
20
40
0.049
Batch (b) Sift1M, 50%.
0.215
0.051 0.032
0
20
0.021
40
Batch (c) Deep1M, 5%.
0.092
0.146 0.099
0
20
40
0.067
Batch (d) Deep1M, 50%.
Time (ms/op)
0.076
0.178
HNSW Add
Time (ms/op)
0.055
Wolverine 0.079
Time (ms/op)
0.153
Merit
0.339
Time (ms/op)
0.083
Time (ms/op)
Time (ms/op)
0.308
0.06
0.039
0
20
40
0.026
Batch (e) GloVe, 5%.
0
20
40
Batch (f) GloVe, 50%.
Figure 8: Amortized deletion time for HNSW-based methods. The gray dashed line marks the HNSW insertion time.
0
20
40
Batch (a) Sift1M, 5%.
0
20
40
Batch (b) Sift1M, 50%.
0
20
40
0.75
0.8
0
Batch (c) Deep1M, 5%.
Recall@10
Recall@10
0.97
0.9
0.99 0.98 0.97
0.98
0.99
Wolverine
Recall@10
0.994
IP-Vamana
0.99
0.995
0.996
FreshVamana Recall@10
Recall@10
Recall@10
Merit
20
40
Batch (d) Deep1M, 50%.
0
20
40
Batch (e) GloVe, 5%.
0.5 0
20
40
Batch (f) GloVe, 50%.
Figure 9: Post-deletion Recall@10 at deletion rates of 5% and 50%. RQ1 How efficiently does Merit process deletions on SOTA graph indexes? RQ2 How well does Merit preserve search quality as deletions accumulate? RQ3 Does Merit jointly provide low update latency and stable search quality under sustained delete–insert replacements? RQ4 How do the repair degree 𝑘𝑟 , versioned-edge invalidation, and MST repair contribute to performance? RQ5 How does Merit scale to a 100-million-point dataset?
6.1
Setup
Datasets. The experiments are conducted on several popular benchmarking datasets. All of them are real-world datasets and have been widely used in the literature [4, 47]. As summarized in Table 3, the datasets cover images (Sift1M [22], Gist1M [22], Deep1M, Deep10M, and Deep100M [6]), text (GloVe [36]), and music (MSong [8]). Algorithms. The evaluation covers two SOTA graph structures. For HNSW indexes, we compare Wolverine [26] with Merit implemented on HNSW. For single-layer Vamana indexes, we compare FreshVamana, the in-memory update algorithm of FreshDiskANN [40], and IP-Vamana [49], the in-memory update algorithm of IP-DiskANN, with Merit implemented on Vamana (i.e., MeritVamana). Parameters. For a fair comparison, we use the same maximum out-degree, 𝑀 = 𝑅 ∈ {32, 64}, and a search beam width of 200 for all methods. Method-specific parameters follow the settings recommended in the original papers. Unless otherwise stated, Merit uses 𝑘𝑟 = 2, 16 version bits, and 𝑒 𝑓𝑐′ = 2𝑀. Wolverine uses 𝜃 in = 32 and 𝐶𝑠 = 64. FreshVamana uses 𝐿 = 200 and 𝛼 = 1.2, and IP-Vamana additionally uses 𝑙𝑑 = 128, 𝑘 = 50, and 𝑐 = 3. We do not apply any additional quantization (e.g., PQ [22] or SQ [1]) to any of the methods, because our focus is on the graph update. Metrics. We report Recall@10, QPS, and NDC to evaluate search quality, following the definitions in §2.1.1. We measure update 10
cost as the amortized wall-clock time per operation, i.e., the endto-end elapsed time of processing a batch divided by the number of operations in that batch. We report deletion latency (𝐿del ) for deletion workloads. Under the update workload, the amortized update cost is defined as 𝐿upd = 𝐿ins + 𝐿del following §2.2. Computing Environment. We implemented our method in C++11 and compiled the code using CMake 3.22.1 with GCC 11.4.0 as the compiler. All experiments run on a server with an AMD EPYC 9554 (64 cores / 128 threads) and 377 GB RAM under Ubuntu 22.04. Build and update use 128 threads; search is single-threaded to isolate per-query cost. Protocol. The deletion workload removes vertices in 50 batches at total deletion rates 𝑟 ∈ {5%, 50%} and evaluates search after every batch. The sustained-update experiments use the SWQ workload defined in §2.3. Every reported configuration uses identical update sequences across competing methods. Each experiment is repeated three times with the mean result reported.
6.2
RQ1 – Deletion Efficiency
We begin by measuring amortized deletion time per operation over successive deletion batches. Methods are compared only within the same graph structure, with separate results for Vamana (i.e., MeritVamana) and HNSW implementations. Answer to RQ1. As shown in Figures 7 and 8, Merit achieves consistently low deletion latency under both removal ratios (𝑟 = 5% and 𝑟 = 50%), substantially outperforming existing SOTA methods on three datasets. Specifically, when 𝑟 = 50%, Merit achieves average deletion latencies of 0.0399, 0.0333, and 0.1031 ms on Sift1M, Deep1M, and GloVe, respectively. By comparison, FreshVamana requires 0.6459, 0.6285, and 0.6529 ms, while IP-Vamana requires 0.2110, 0.1039, and 0.3363 ms on the same datasets (Figure 7). Figure 8 further shows that, under the 50% removal ratio, Merit consistently outperforms Wolverine, reducing the deletion latency from
1000
1500
0
5
Batch (a) Sift1M QPS.
0
10
5
Batch (b) Deep1M QPS.
10
5
Batch (c) GloVe QPS.
10
10000
2500
2000
0
15000
3000
NDC
2000
Wolverine
NDC
2500
2000
IP-Vamana 2500
QPS (1/s)
QPS (1/s)
QPS (1/s)
3000
FreshVamana 2000
NDC
Merit
0
5
Batch (d) Sift1M NDC.
10
0
5
Batch (e) Deep1M NDC.
5000
10
0
5
Batch (f) GloVe NDC.
10
Figure 10: Search throughput and average distance computations per query after each deletion batch at 𝑟 = 50%.
40
0.027
Batch (a) Sift1M, 5%.
0
20
40
2.338
0.272
0.29 0.036
Batch (b) Sift1M, 50%.
Wolverine 18.09
0.097
0
20
40
0.034
Batch (c) Deep1M, 5%.
0.713
2.613
0.312
0.377
0
20
40
0.055
Batch (d) Deep1M, 50%.
Time (ms/op)
20
IP-Vamana 0.765
Time (ms/op)
0
Time (ms/op)
0.081
0.268
FreshVamana 18.856
0.244
2.186 0.033
Time (ms/op)
Time (ms/op)
0.737
Time (ms/op)
Merit 17.837
0.137
0
20
40
0.06
Batch (e) GloVe, 5%.
0
20
40
20
40
Batch (f) GloVe, 50%.
Figure 11: Amortized update time 𝐿upd under the fixed-cardinality sliding-window update workload.
0
20
40
Batch (a) Sift1M, 5%.
0.98
0
20
40
Batch (b) Sift1M, 50%.
0.97
0.9
0.99
0.8
0.98
0
20
40
0
Batch (c) Deep1M, 5%.
Recall@10
0.99
Wolverine Recall@10
0.99
0.995
0.995
IP-Vamana Recall@10
0.996
FreshVamana Recall@10
Recall@10
Recall@10
Merit
20
40
Batch (d) Deep1M, 50%.
1
0.5
0
20
40
Batch (e) GloVe, 5%.
0
Batch (f) GloVe, 50%.
Figure 12: Post-update Recall@10 under the fixed-cardinality sliding-window update workload. 0.0545, 0.0585, and 0.1085 ms to 0.0398, 0.0396, and 0.0359 ms, respectively. Overall, Merit delivers up to 3.02×–18.87× speedup over existing SOTA approaches. This improvement stems from its ability to rapidly identify candidate neighbors and efficiently repair the affected graph structure, without performing an expensive global cleanup of incoming edges.
6.3
6.4
RQ3 – Sustained Update Performance
We then turn to the fixed-cardinality sliding-window update workload, measuring amortized replacement time together with postupdate Recall@10. Reporting both metrics reveals whether a method lowers update cost by sacrificing long-term search quality. Answer to RQ3. Answer to RQ3. Figure 11 reports the latency of updating 5% and 50% of the vectors on the three datasets. When 𝑟 = 50%, the HNSW-based implementation of Merit achieves average per-update latencies of 0.0476, 0.0541, and 0.1022 ms on three datasets. As shown in Figure 12, Merit also maintains consistently high and stable Recall@10 after each update batch across all datasets. In contrast, IP-Vamana exhibits substantial recall fluctuations on Sift1M, potentially due to the dataset’s non-uniform local density [22]. Overall, under workloads involving frequent and large-scale deletions and insertions, Merit achieves lower update latency and more stable recall than existing SOTA methods.
RQ2 – Search Quality after Deletions
In order to evaluate the impact of deletions on search quality, we next examine Recall@10 after every deletion batch at total deletion rates of 5% and 50%, using the same removal order and per-rate schedules. Search pool size 𝐿 is set to 200 for all methods. Answer to RQ2. Answer to RQ2. As shown in Figure 9, Merit maintains consistently high recall under both removal ratios across datasets with varying levels of difficulty, from Sift1M to GloVe. When 𝑟 = 50%, the minimum Recall@10 values achieved by Merit are 0.9956, 0.9921, and 0.8473 on Sift1M, Deep1M, and GloVe, respectively. Furthermore, Figure 9 reports the QPS and NDC of different methods at fixed recall levels under 𝑟 = 50% (Recall@10=99% for Sift1M and Deep1M, and Recall@10=80% for GloVe). Merit exhibits a stable trend throughout the 50 deletion batches. This stability is attributed to Merit ’s repair strategy, which constructs a 𝑘𝑟 -MST over locally affected structures along search paths, restoring graph connectivity while preserving navigability. Although all baseline methods remain relatively stable under a small deletion setting of 𝑟 = 5%, their search quality exhibits noticeable fluctuations or degradation when half of the indexed vectors are removed. Overall, Merit preserves stable recall even under high-frequency deletions.
6.5
RQ4 – Ablation Study
We study two questions in this ablation. RQ4-1 examines how 𝑘𝑟 affects amortized deletion time and search quality. RQ4-2 separates the effects of MST repair and versioned edges through four component variants. RQ4-1. We vary 𝑘𝑟 from 1 to 5 to evaluate its impact on deletion latency and search quality. As shown in Figure 13, increasing 𝑘𝑟 incurs higher repair costs, while the corresponding quality gains gradually diminish. On Gist1M, increasing 𝑘𝑟 from 1 to 2 raises the average deletion latency from 0.41 to 0.67 ms and improves the final Recall@10 from 0.979 to 0.982. When 𝑘𝑟 = 5, the average deletion latency further increases to 2.22 ms, while Recall@10 shows no additional improvement. Overall, setting 𝑘𝑟 to 2 or 3 provides a favorable trade-off by preserving local graph connectivity for each affected node while maintaining low deletion latency. 11
kr = 2
kr = 3
kr = 4
kr = 5
0.995
0
20
Batch
0.978 0.976 0.974
40
(a) Sift1M Recall@10.
0
20
Batch
0.06 0.04
40
20
Batch
1
0
(c) Sift1M deletion time.
20
40
Batch
0.02
0.99
0.01 v0
v1
v2
Variant
v3
(a) Sift1M.
7
Batch
40
0.9 0
20
Batch
40
(b) Recall@10.
Deletion latency 1
0.98
0.75
0.97
0.5 0.25 0.95
v0
v1
v2
Variant
RELATED WORK
Graph-based ANNS indexes evolved from k-NN graph construction (e.g., NN-Descent [14]) and navigation techniques such as NSG and NSWG [17, 27]. Representative in-memory indexes include HNSW [28], which uses a probabilistic hierarchy for skip-list-like navigation [38], and Vamana [21], whose 𝛼-robust pruning is reported to achieve higher recall. For collections beyond DRAM, DiskANN [21] stores the Vamana graph on SSD with a productquantized in-memory representation, while PipeANN [18] further reduces query latency by overlapping computation with SSD reads. These graph indexes are widely used in industrial vector-search systems such as VSAG [56] and Milvus [45]. Several dynamic vector-search systems have been proposed to support real-time workloads. SPFresh [50] adopts a clustering-based index but degrades in high-dimensional spaces. FreshDiskANN [40] supports dynamic updates through lazy deletion and batch consolidation, but incurs deferred cleanup and expensive neighborhood repair. CleANN [54] similarly defers physical cleanup while using query-adaptive consolidation and semi-lazy cleaning. IPVamana [49] uses graph search to recover candidate in-neighbors; Wolverine [26] instead forms candidates from two-hop neighbors. Both still couple recovery with explicit cleanup of stale incoming edges. Merit’s key insight is to repair only the routing-relevant surviving boundary and use target versions to invalidate incoming edges outside the recovered set. This separation eliminates the need for exhaustive reverse-edge discovery during deletion.
v3
(b) Gist1M.
Figure 14: Merit component ablation. RQ4-2. We isolate versioned edges and MST repair with four variants. Merit-v0 disables both and performs no repair; Meritv1 enables only versioned edges and likewise performs no repair; Merit-v2 enables only MST repair; and Merit-v3 enables both. As shown in Figure 14, enabling MST-based repair substantially improves recall while increasing deletion latency (e.g., on Gist1M, it prevents an approximately 3% drop in Recall@10 but incurs a 0.4 ms increase in deletion time). In contrast, versioned edges introduce negligible overhead and avoid the latency spikes incurred by prior methods that periodically remove stale edges from the graph.
6.6
20
0.92
(d) Gist1M deletion time.
Deletion latency (ms/op)
Recall@10
0.03
0
0.94
each deletion batch. These results demonstrate that Merit scales effectively to large-scale datasets while preserving both low deletion latency and robust search quality, making it suitable for large-scale production workloads.
Figure 13: Merit 𝑘𝑟 sensitivity. Recall@10
Wolverine
Figure 15: Deep100M scalability over 50 deletion batches.
2
40
0.04
(a) Deletion time.
0.02 0
0.051
0.031
(b) Gist1M Recall@10.
0.08
Time (ms/op)
Time (ms/op)
Time (ms/op)
0.980
Recall@10
Recall@10
0.996
Merit
0.065
0.982
Recall@10
kr = 1
RQ5 – Scalability
Finally, we examine amortized deletion time and Recall@10 beyond the million-scale setting. The Deep100M run uses the same 50-batch deletion schedule and tuned initial recall. Answer to RQ5. As shown in Figure 15, Merit achieves an average per-deletion latency of 0.0342 ms on Deep100M and maintains stable latency throughout the experiment. We further compare Merit with Wolverine under the same large-scale deletion workload. Although the two methods start with comparable Recall@10, their search quality diverges as deletions accumulate. After 50 deletion batches (i.e., removing 50 million vectors), the Recall@10 of Merit decreases by less than ∼ 1%. In contrast, Wolverine exhibits noticeable quality degradation despite repairing the graph after
8
CONCLUSION
In this paper, we presented Merit, an efficient in-place deletion method for dynamic graph-based ANNS indexes. Bounded recovery and 𝑘𝑟 -MST repair promote local connectivity along useful routes, while target versions invalidate all stale incoming edges missed during recovery. This division avoids explicit reverse-edge discovery and periodic full-graph maintenance. We analyze its deletion cost and the lifetime of the finite-width version counter. Experiments across multiple datasets demonstrate that Merit outperforms prior SOTA methods in update latency, post-update search stability, and scalability. 12
REFERENCES
Index for Approximate Maximum Inner Product Search on Sparse Vectors. arXiv preprint arXiv:2509.08395 (2025). [25] Wen Li, Ying Zhang, Yifang Sun, Wei Wang, Mingjie Li, Wenjie Zhang, and Xuemin Lin. 2019. Approximate nearest neighbor search on high dimensional data—experiments, analyses, and improvement. IEEE Transactions on Knowledge and Data Engineering 32, 8 (2019), 1475–1488. [26] Dawei Liu, Bolong Zheng, Ziyang Yue, Fuhao Ruan, Xiaofang Zhou, and Christian S Jensen. 2025. Wolverine: Highly Efficient Monotonic Search Path Repair for Graph-Based ANN Index Updates. Proceedings of the VLDB Endowment 18, 7 (2025), 2268–2280. [27] Yury Malkov, Alexander Ponomarenko, Andrey Logvinov, and Vladimir Krylov. 2014. Approximate nearest neighbor algorithm based on navigable small world graphs. Information Systems 45 (2014), 61–68. [28] Yu A Malkov and Dmitry A Yashunin. 2018. Efficient and robust approximate nearest neighbor search using hierarchical navigable small world graphs. IEEE transactions on pattern analysis and machine intelligence 42, 4 (2018), 824–836. [29] Yitong Meng, Xinyan Dai, Xiao Yan, James Cheng, Weiwen Liu, Jun Guo, Benben Liao, and Guangyong Chen. 2020. Pmd: An optimal transportation-based user distance for recommender systems. In Advances in Information Retrieval: 42nd European Conference on IR Research, ECIR 2020, Lisbon, Portugal, April 14–17, 2020, Proceedings, Part II 42. Springer, 272–280. [30] Rajeev Motwani and Prabhakar Raghavan. 1996. Randomized algorithms. ACM Computing Surveys (CSUR) 28, 1 (1996), 33–37. [31] Marius Muja and David Lowe. 2009. Flann-fast library for approximate nearest neighbors user manual. Computer Science Department, University of British Columbia, Vancouver, BC, Canada 5, 6 (2009), 12–29. [32] Marius Muja and David G Lowe. 2014. Scalable nearest neighbor algorithms for high dimensional data. IEEE transactions on pattern analysis and machine intelligence 36, 11 (2014), 2227–2240. [33] Emir Öztürk and Altan Mesut. 2024. Performance Analysis Of Chroma, Qdrant, And Faiss Databases. UNITECH–Sel. Pap (2024). [34] Patrick O’Neil, Edward Cheng, Dieter Gawlick, and Elizabeth O’Neil. 1996. The log-structured merge-tree (LSM-tree). Acta Informatica 33 (1996), 351–385. [35] Yun Peng, Byron Choi, Tsz Nam Chan, Jianye Yang, and Jianliang Xu. 2023. Efficient approximate nearest neighbor search in multi-dimensional databases. Proceedings of the ACM on Management of Data 1, 1 (2023), 1–27. [36] Jeffrey Pennington, Richard Socher, and Christopher D Manning. 2014. Glove: Global vectors for word representation. In Proceedings of the 2014 conference on empirical methods in natural language processing (EMNLP). 1532–1543. [37] Liudmila Prokhorenkova and Aleksandr Shekhovtsov. 2020. Graph-based nearest neighbor search: From practice to theory. In International Conference on Machine Learning. PMLR, 7803–7813. [38] William Pugh. 1990. Skip lists: a probabilistic alternative to balanced trees. Commun. ACM 33, 6 (1990), 668–676. [39] Chanop Silpa-Anan and Richard Hartley. 2008. Optimised KD-trees for fast image descriptor matching. In 2008 IEEE Conference on Computer Vision and Pattern Recognition. IEEE, 1–8. [40] Aditi Singh, Suhas Jayaram Subramanya, Ravishankar Krishnaswamy, and Harsha Vardhan Simhadri. 2021. Freshdiskann: A fast and accurate graph-based ann index for streaming similarity search. arXiv preprint arXiv:2105.09613 (2021). [41] Yifang Sun, Wei Wang, Jianbin Qin, Ying Zhang, and Xuemin Lin. 2014. SRS: solving c-approximate nearest neighbor queries in high dimensional euclidean space with a tiny index. Proceedings of the VLDB Endowment (2014). [42] Nenad Tomasev, Milos Radovanovic, Dunja Mladenic, and Mirjana Ivanovic. 2013. The role of hubness in clustering high-dimensional data. IEEE transactions on knowledge and data engineering 26, 3 (2013), 739–751. [43] Godfried T Toussaint. 1980. The relative neighbourhood graph of a finite planar set. Pattern recognition 12, 4 (1980), 261–268. [44] Jing Wang, Jingdong Wang, Gang Zeng, Zhuowen Tu, Rui Gan, and Shipeng Li. 2012. Scalable k-nn graph construction for visual descriptors. In 2012 IEEE Conference on Computer Vision and Pattern Recognition. IEEE, 1106–1113. [45] Jianguo Wang, Xiaomeng Yi, Rentong Guo, Hai Jin, Peng Xu, Shengjun Li, Xiangyu Wang, Xiangzhou Guo, Chengming Li, Xiaohai Xu, et al. 2021. Milvus: A purpose-built vector data management system. In Proceedings of the 2021 International Conference on Management of Data. 2614–2627. [46] Meng Wang, Weijie Fu, Xiangnan He, Shijie Hao, and Xindong Wu. 2020. A survey on large-scale machine learning. IEEE Transactions on Knowledge and Data Engineering 34, 6 (2020), 2574–2594. [47] Mengzhao Wang, Xiaoliang Xu, Qiang Yue, and Yuxiang Wang. 2021. A comprehensive survey and experimental comparison of graph-based approximate nearest neighbor search. Proceedings of the VLDB Endowment 14, 11 (2021), 1964–1978. [48] Zekai Wu, Jiabao Jin, Peng Cheng, Xiaoyao Zhong, Lei Chen, Yongxin Tong, Zhitao Shen, Jingkuan Song, Heng Tao Shen, and Xuemin Lin. 2026. FGIM: a Fast Graph-based Indexes Merging Framework for Approximate Nearest Neighbor Search. Proceedings of the ACM on Management of Data 4, 1 (SIGMOD (2026), 1–27.
[1] Cecilia Aguerrebere, Ishwar Bhati, Mark Hildebrand, Mariano Tepper, and Ted Willke. 2023. Similarity search in the blink of an eye with compressed indices. arXiv preprint arXiv:2304.04759 (2023). [2] Sunil Arya and David M Mount. 1993. Approximate nearest neighbor queries in fixed dimensions.. In SODA, Vol. 93. Citeseer, 271–280. [3] Akari Asai, Sewon Min, Zexuan Zhong, and Danqi Chen. 2023. Retrieval-based language models and applications. In Proceedings of the 61st Annual Meeting of the Association for Computational Linguistics (Volume 6: Tutorial Abstracts). 41–46. [4] Martin Aumüller, Erik Bernhardsson, and Alexander Faithfull. 2020. ANNBenchmarks: A benchmarking tool for approximate nearest neighbor algorithms. Information Systems 87 (2020), 101374. [5] Artem Babenko and Victor Lempitsky. 2014. The inverted multi-index. IEEE transactions on pattern analysis and machine intelligence 37, 6 (2014), 1247–1260. [6] Artem Babenko and Victor Lempitsky. 2016. Efficient indexing of billion-scale datasets of deep descriptors. In Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition. 2055–2063. [7] Jon Louis Bentley. 1975. Multidimensional binary search trees used for associative searching. Commun. ACM 18, 9 (1975), 509–517. [8] Thierry Bertin-Mahieux, Daniel P.W. Ellis, Brian Whitman, and Paul Lamere. 2011. The Million Song Dataset. In Proceedings of the 12th International Conference on Music Information Retrieval (ISMIR 2011). [9] Mingyue Cheng, Yucong Luo, Jie Ouyang, Qi Liu, Huijie Liu, Li Li, Shuo Yu, Bohou Zhang, Jiawei Cao, Jie Ma, Daoyu Wang, and Enhong Chen. 2025. A Survey on Knowledge-Oriented Retrieval-Augmented Generation. arXiv preprint arXiv:2503.10677 (2025). [10] Scott Cost and Steven Salzberg. 1993. A weighted nearest neighbor algorithm for learning with symbolic features. Machine learning 10 (1993), 57–78. [11] Abhinandan S Das, Mayur Datar, Ashutosh Garg, and Shyam Rajaram. 2007. Google news personalization: scalable online collaborative filtering. In Proceedings of the 16th international conference on World Wide Web. 271–280. [12] Damian Dechev, Peter Pirkelbauer, and Bjarne Stroustrup. 2010. Understanding and Effectively Preventing the ABA Problem in Descriptor-Based Lock-Free Designs. In 2010 13th IEEE International Symposium on Object/Component/ServiceOriented Real-Time Distributed Computing. 185–192. https://doi.org/10.1109/ ISORC.2010.10 [13] Magdalen Dobson, Zheqi Shen, Guy E. Blelloch, Laxman Dhulipala, Yan Gu, Harsha Vardhan Simhadri, and Yihan Sun. 2024. Scaling Graph-Based ANNS Algorithms to Billion-Size Datasets: A Comparative Analysis. In Proceedings of the 29th ACM SIGPLAN Annual Symposium on Principles and Practice of Parallel Programming (PPoPP ’24). 270–285. [14] Wei Dong, Charikar Moses, and Kai Li. 2011. Efficient k-nearest neighbor graph construction for generic similarity measures. In Proceedings of the 20th international conference on World wide web. 577–586. [15] Matthijs Douze, Alexandr Guzhva, Chengqi Deng, Jeff Johnson, Gergely Szilvasy, Pierre-Emmanuel Mazaré, Maria Lomeli, Lucas Hosseini, and Hervé Jégou. 2024. The faiss library. arXiv preprint arXiv:2401.08281 (2024). [16] Cong Fu, Changxu Wang, and Deng Cai. 2021. High dimensional similarity search with satellite system graph: Efficiency, scalability, and unindexed query compatibility. IEEE Transactions on Pattern Analysis and Machine Intelligence 44, 8 (2021), 4139–4150. [17] Cong Fu, Chao Xiang, Changxu Wang, and Deng Cai. 2017. Fast Approximate Nearest Neighbor Search With The Navigating Spreading-out Graph. Proceedings of the VLDB Endowment 12, 5 (2017). [18] Hao Guo and Youyou Lu. 2025. Achieving Low-Latency Graph-Based Vector Search via Aligning Best-First Search Algorithm with SSD. In Proceedings of the 19th USENIX Symposium on Operating Systems Design and Implementation (OSDI ’25). USENIX Association, 171–186. [19] Qiang Huang, Jianlin Feng, Yikai Zhang, Qiong Fang, and Wilfred Ng. 2015. Query-aware locality-sensitive hashing for approximate nearest neighbor search. Proceedings of the VLDB Endowment 9, 1 (2015), 1–12. [20] Piotr Indyk and Rajeev Motwani. 1998. Approximate nearest neighbors: towards removing the curse of dimensionality. In Proceedings of the thirtieth annual ACM symposium on Theory of computing. 604–613. [21] Suhas Jayaram Subramanya, Fnu Devvrit, Harsha Vardhan Simhadri, Ravishankar Krishnawamy, and Rohan Kadekodi. 2019. Diskann: Fast accurate billion-point nearest neighbor search on a single node. Advances in Neural Information Processing Systems 32 (2019). [22] Herve Jegou, Matthijs Douze, and Cordelia Schmid. 2010. Product quantization for nearest neighbor search. IEEE transactions on pattern analysis and machine intelligence 33, 1 (2010), 117–128. [23] Donald B. Johnson. 1975. Priority queues with update and finding minimum spanning trees. Inform. Process. Lett. 4, 3 (1975), 53–57. https://doi.org/10.1016/ 0020-0190(75)90001-0 [24] Ruoxuan Li, Xiaoyao Zhong, Jiabao Jin, Peng Cheng, Wangze Ni, Lei Chen, Zhitao Shen, Wei Jia, Xiangyu Wang, Xuemin Lin, et al. 2025. SINDI: an Efficient 13
[49] Haike Xu, Magdalen Dobson Manohar, Philip A Bernstein, Badrish Chandramouli, Richard Wen, and Harsha Vardhan Simhadri. 2025. In-Place Updates of a Graph Index for Streaming Approximate Nearest Neighbor Search. arXiv preprint arXiv:2502.13826 (2025). [50] Yuming Xu, Hengyu Liang, Jin Li, Shuotao Xu, Qi Chen, Qianxi Zhang, Cheng Li, Ziyue Yang, Fan Yang, Yuqing Yang, et al. 2023. Spfresh: Incremental in-place update for billion-scale vector search. In Proceedings of the 29th Symposium on Operating Systems Principles. 545–561. [51] Shuo Yang, Jiadong Xie, Yingfan Liu, Jeffrey Xu Yu, Xiyue Gao, Qianru Wang, Yanguo Peng, and Jiangtao Cui. 2025. Revisiting the Index Construction of Proximity Graph-Based Approximate Nearest Neighbor Search. Proceedings of the VLDB Endowment 18 (2025), 1825–1838. [52] Xiao Yang, Kai Sun, Hao Xin, Yushi Sun, Nikita Bhalla, Xiangsen Chen, Sajal Choudhary, Rongze D Gui, Ziran W Jiang, Ziyu Jiang, et al. 2024. Cragcomprehensive rag benchmark. Advances in Neural Information Processing Systems 37 (2024), 10470–10490. [53] Kun Yu, Jiabao Jin, Xiaoyao Zhong, Peng Cheng, Lei Chen, Zhitao Shen, Jingkuan Song, Hengtao Shen, and Xuemin Lin. 2025. Approximate Nearest Neighbor Search of Large Scale Vectors on Distributed Storage. arXiv preprint
arXiv:2510.17326 (2025). [54] Ziyu Zhang, Yuanhao Wei, Joshua Engels, and Julian Shun. 2026. CleanANN: Efficient and Robust Full Dynamism in Graph-based Approximate Nearest Neighbor Search. In Proceedings of the 38th ACM Symposium on Parallelism in Algorithms and Architectures (SPAA ’26). 247–260. https://doi.org/10.1145/3816782.3819219 [55] Penghao Zhao, Hailin Zhang, Qinhan Yu, Zhengren Wang, Yunteng Geng, Fangcheng Fu, Ling Yang, Wentao Zhang, Jie Jiang, and Bin Cui. 2026. Retrievalaugmented generation for ai-generated content: A survey. Data Science and Engineering (2026), 1–29. [56] Xiaoyao Zhong, Haotian Li, Jiabao Jin, Mingyu Yang, Deming Chu, Xiangyu Wang, Zhitao Shen, Wei Jia, George Gu, Yi Xie, Xuemin Lin, Heng Tao Shen, Jingkuan Song, and Peng Cheng. 2025. VSAG: An Optimized Search Framework for Graph-Based Approximate Nearest Neighbor Search. Proc. VLDB Endow. 18, 12 (Aug. 2025), 5017–5030. [57] Chun Jiang Zhu, Tan Zhu, Haining Li, Jinbo Bi, and Minghu Song. 2019. Accelerating large-scale molecular similarity search through exploiting high performance computing. In 2019 IEEE International Conference on Bioinformatics and Biomedicine (BIBM). IEEE, 330–333.
14