Graph-based Nearest Neighbors with Dynamic Updates via Random Walks
Authors: Nina Mishra
Yonatan Naamad
Tal Wagner
Lichen Zhang
Venue: ICLR 2026 Poster (2026)
Keywords: nearest neighbor search
graph
random walk
Primary area: optimization
TL;DR: We propose a random-walk based analytical framework for HNSW, and use it to design a deterministic deletion algorithm with good recall, throughput and memory utilization.

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

Published as a conference paper at ICLR 2026
GRAPH-BASED NEAREST NEIGHBORS WITH DYNAMIC UPDATES VIA RANDOM WALK
Nina Mishra
Yonatan Naamad
Tal Wagner
Amazon nmi aarasaaaazoonn..m
Amazon
Amazon and Tel Aviv University
yna www.dadaaaa...ooo.. com
t 1. wwwner com
Lichen Zhang
MIT CSAIL
1 lichenzecsail. mit.iiiiiii....................m edu
ABSTRACT
Approximate nearest neighbor search (ANN) is common way to retrieve relevant search results, especially now the context of large language models and retrieval augmented generation. One of the most widely used algorithms for ANN is based on constructing multi-layer graph over the dataset, called the Hierarchical Navigable Small World (HNSW). While this algorithm supports insertion of new data, it does not support deletion of existing data. Moreover, deletion algorithms described by prior work come at the cost of increased query latency, decreased recall, or prolonged deletion time. In this paper, we propose a new theoretical framework for graph-based ANN based random walks. We then utilize this framework to analyze a randomized deletion approach that preserves hitting time statistics compared to the graph before deleting the point. We then turn this theoretical framework into a deterministic deletion algorithm, and show that it provides better tradeoff between query latency, recall, deletion time, and memory usage through an extensive collection of experiments.
INTRODUCTION
We study the approximate nearest neighbor search problem (ANN): given a collection of points P C. RR parameter k and query point R the goal is to find the top-k points in P that are closest to q under some distance measurements such as Eg distance or cosine similarity] This problem is a fundamental component of Retrieval Augmented Generation (RAG), widely adopted
to improve the accuracy Large Language Models (LLM) (Lewis et al., 2020 Gao et al. 2023
Jiang et al. 2023 Fan et al. 2024). One of the most popular ways to solve the ANN problem is through graph-based approaches. where data-dependent graph is constructed of the dataset, and
queries can be quickly routed such graph (Jayaram Subramanya al. 2019; Malkov & Yashumin 2020 Fu et al. 2019). ). In this work, we focus on the Hicrarchical Navigable Small World (HNSW) graph (Malkov & Yashunin 2020), data structure with strong practical performances. This is multi-layer graph data structure, where the higher layers of the graph tend to have fewer vertices and "long-range" edges that help to navigate between clusters, while the lower layers have "short-range" edges that enhance the connectivity within the clusters. To perform a query search, one starts at the higher layers via the long-range edges to make coarse-graines progress towards the clusters containing the nearest neighbors, and drops to lower layers for finer mnninee progress to find the nearest neighbors within the cluster.
While the HNSW algorithm can naturally handle insertions (Harwood et al., 2024), they do not possess deletion capabilities. This becomes more and more problematic as modern datasets are highly dynamic and require many deletions. For example, advertisers may remove ads when the campaign budget is exhausted; clothing retailer may remove spring clothing in the fall and remove fall clothing in the spring; a shoe company may eliminate a previous shoe version when new generation drops. Thus, deletion a common and necessary operation.
In this paper, we use ||
to denote such abstract distance measurement.

---

Published as a conference paper at ICLR 2026
Since the HNSW algorithm does not come with a deletion procedure, common, practical approach is to never delete a point at all. Instead, the corresponding vertex in the graph is marked with a "tombstone" indicating that the point should never be outputted time, these tombstones can either be handled in post-processing (the corresponding points would be removed from the output) in real-time (modifying the HNSW algorithm never stop its search at a lombstone). We consider this algorithm as a baseline for our proposed approach. The advantage of this approach is that graph navigability is preserved, and therefore tombstones maintain high recall. However, as tombstones are never removed from the graph, the query latency rises significantly when there are large amounts of tombstones, as the search would take many more steps to reach the desired nearest neighbors. Moreover, the memory usage of the data structure stays constant while the number of points declines, leading to unnecessary storage.
nearest neighbor. At query
Due to the importance of developing good deletion algorithm with improved query throughput and memory usage, a rich literature has considered approaches beyond tombstones. An even simpler idea is to delete the point from the graph and the data structure without patching the graph (we will refer to it as 'no patching' algorithm). Such an approach suffers when there are many deletions or queries are drifting towards the clusters being deleted, resulting in much worse recall (Xu al. 2022). Another class of deletion algorithms is to reconnect the subgraph after deletion as in (Singh et al.
2021 Xu al., 2022 Xiao al. 2024| Zhao et al. 2023 Xu et al.. 2023] 2025). The reconnection strategy ranges from local to global: if we want to delete p. a local reconnect attempts to find for every (p),, the neighborhood of p, another point (p) that is the nearest neighbor of u. This approach has low query latency and slightly improved recall compared to no patching, but the recall still significantly lower than in other alternatives. To further improve recall, [Singh et al. (202T) proposes the FreshDiskANN algorithm that uses a 2-hop neighborhood: instead of only rerouting within N()), FreshDiskANN adds edges between u and N(p) U (u), then prunes edges to ensure the sparsity of the graph. A more global approach introduced by Xu et al. (2022) (where they termed the algorithm global reconnect) is to re-insert all the points in Myp and improve the connectivity of the subgraph by utilizing the robustness of the HNSW insertion procedure. Both FreshDiskANN and global reconnect suffer from much longer deletion times due to the non-local nature of the algorithm and the need to interact with larger subgraphs, and require nontrivial effort to parallelize the insertions.
Our results. Our main contribution is deletion procedure that arises through a theoretically grounded twin framing of the HNSW algorithm. This algorithm enjoys good recall, query speed, overall deletion time and memory usage, as summarized in Table In the original HNSW algorithm, for a given query q, the algorithm walks to the adjacent vertex u that minimizes ||g =ull in a deterministic and greedy fashion. In our twin formulation, we "soften" by walking to a random neighbor with probability proportional to exp(-r² 1|g u|l²) for r > O. We call this a "softmax walk". While highly similar the "hard" greedy walk (as we confirm experimentally), this random walk interpretation leads to a theoretical deletion procedure that maintains the properties of the original random walk. Specifically, the algorithm functions by first computing local edge weights over N (p) that precisely preserve the random walk probability, then using simple randomized sparsification scheme that approximates the hitting time of walk, i.e., the expected number of steps it takes for a random walk at vertex u to reach vertex v. While this does not directly guarantee that we will hit the same nearest neighbors exactly, it does ensure that we make a similar number of steps to the target as before. We then turn this randomized, theoretical algorithm into a deterministic, practical algorithm: instead of random sampling edges, we could compute the edge weights first then simply take heaviest edges. We conduct extensive experiments on various datasets in the mass deletion setting, where large fraction of the points are removed from the dataset and show that our method has strong advantage when points are frequently deleted in large batches. We show the edge of our method over other alternatives in four key metrics: recall, query speed, deletion time and memory usage.
2 RELATED WORK
Approximate Nearest Neighbor Search. Approximate nearest neighbor (ANN) search is a core algorithmic task with long line of research, both in theory and in practice. Theoretically, Locality Sensitive Hashing (LSH) (Indyk & Motwani 1998 Andoni & Indyk] 2008) Andoni & Razenshteyn 2015 Andoni et al.
2015
2017
2018
Dong et al. 2020) has been popular solution with provably
2

---

Published as a conference paper at ICLR 2026
Table Summary of HNSW deletion algorithms.
Method
Recall
Speed
Del Time
Space
Tombstone
x
x
No patch
x
Local
x
FreshDiskANN
1
x
/
Global
4
x
x
SPat ch (ours)
4
fast query time and efficient memory usage. While LSH offers good performance in theory, its practical variants are usually data-oblivious. On the other hand, practical ANN algorithms are oftentimes data-dependent; this class of algorithms includes quantization methods (Jégou et al. 20100) Ge et al.] 2013) Kalantidis & Avrithis 2014; Yue et al. 22024, Gao & Long, 2024) and graph-based
methods (Malkov& & Yashumin 2020; Jayaram Subramanya et |l.] 2019 Wang et al. 2021; Fu et al.,
2019 Harwood & Drummond 2016)] Groh et al. (202)), the latter of which are the focus of this work. In these algorithms, the points in the dataset are coalesced into a specially-constructt
proximity graph. To handle query, one runs greedy search algorithm traverse the graph (i.e., iteratively move from the current point to its adjacent point closest to the query vector) to find the approximate nearest neighbors of the query. Among this body of work, we focus on the Hierarchical Navigable Small World (HNSW) algorithm of Malkoy & Yashunin (2020), due to its wide adoption, fast query throughput, and good recall characteristics. A key limitation of HNSW is that only explicitly supports insert and query operations, and implicitly assumes that the dataset is either static or only incremental. In practice, deletions (if any) are usually handled ad-hoc; the industry standard is to mark any deleted vectors as unreturnable "tombstones", and periodically rebuild the data structure entirely from scratch at great cost (Xu et al.] 2022). Some more recent approaches try to directly incorporate some notion of deletion into the graph data structure, preempting the need for periodic batch rebuilds (Singh et al. 2021 Xu et al., 2022 Xiao et al. 2024 Xu et al. 2023 Zhao et al. 2023 Xu et al. 2025). These methods typically operate by first excising the deleted node from the graph, then "patching" the graph by adding new connections among the removed node's 's former neighborhood. However, most of these approaches offer theoretical guarantees and typically come with both performance and recall penalties on real-world datasets, especially for mass deletion.
Graph Sparsification and Random Walks. Given graph, elementary way explore is through random walks, which is both practical (Hamilton et al. 2017) and has rich theoretical connections to electrical networks (Doyle & Snell 1984; Tetali 1991) and spectral graph theory (Chung 1997,
Spielman 2007). Important statistics of random walks, including hitting time and commuting time (Aldous Fill 2002) can be computed by solving linear systems in the graph Laplacian matrix (Merii 1994). A popular approach to improve the efficiency of solving Laplacian linear systems is via spectral sparsification that reduces the number of edges in the graph while preserving all Laplacian quadratic forms by sampling according to the effective resistances of edges (Spielman & Srivastava, 201T; Batson et al. 2009). All state-of- the-hhhar art solvers for Laplacian systems utilize spectral sparsification (Spiclman & Teng 2004: Koutis et al.) 2010 Peng & Spielman 2014 Cohen et al. 2014 Kyng& & Sachdeva 2016). In this work, we focus on another type of sparsification, based on sampling by row norms (Drineas & Kannan (2001 Frieze al. 2004 Kannan & Vempala 2017).
It is conceptually simpler and more efficient to implement, though it provides weaker guarantees.
3 PRELIMINARIES
HNSW. The Hierarchical Navigable Small World (HNSW) data structure proposed in Malkov & Yashunin 2020) is a graph-based ANN data structure that utilizes a hierarchical structure. In particular, it is a sequence of undirected graph:Jwith each graph in the sequence called a "layer". For the reminder of this paper, and the bottom one as the 1st layer. The bottom layer of the HNSW contains one vertex for each point in the dataset, and each other layer contains random subset of points in the layer below. In addition to internal edges within a layer, the two vertices representing the same point in two consecutive layers also have a vertical edge between them so that search could traverse between layers. In some library implementations such F' SSS directed graphs are used instead.
assume there are L layers of graphs, with the top as the L-th layer
3

---

Published as a conference paper at ICLR 2026
The fundamental operation of the HNSW is the search operation. Given a query point q. the search starts at the L-th layer with an entry point. At any timestamp t. we let uy be the point where the query q is currently on with to being the entry point, then we move to ut+1 = arg N(u.) llq - ui]- When the search can no longer make progress, it uses the vertical edge to move one layer down, and repeat the process until the bottom layer. In the reminder of this paper, as the "greedy search". The insertion is then executed by running greedy search on the point-to-be- inserted (with more entry points to move down layers) and add edges along the way. For a more comprehensive overview of HNSW and related algorithms, see Appendix D
refer this procedure
HNSW and other graph-based nearest neighbor search data structures have also been studied through the lens of theory. LLarhoven (2018) studies the performance of greedy search when the size of the dataset n = 24, Fu et al. 2019) analyzes the time and space complexity of searching in the monotonic graphs. and it requires the query to be one of the points in the dataset. [Prokhorenkova & Shekhovtsov (2020) proves that the greedy search can be done in sublinear time on the plain nearest neighbor graph in both the dense and sparse regime, and adding vertical edges in HNSW
effectively reduces the number of steps to find the correct nearest neighbor. Shrivastava et al. (2033) relaxes the assumption of nearest neighbor graphs approximate nearest neighbor graphs. Indyk
& Xu (2023) crafts a condition called a-shortcut reachability, and proves a class of graph- graph-based algorithms are provably efficient for a-shorteut reachable graphs. [u et al. (2024) further speeds up the search process by using approximate distances instead of exact distances and proves probabilistic guarantees for this approximation. Diwan al. (2024) considers a class of simplified HNSW graphs and proves the navigability under certain construction algorithm. Oguri & Matsui (2024) shows that adaptively choosing the entry point provably functions better than using fixed entry point.
Deletion Strategies for Graph-based ANN. One could alternatively interpret HNSW as a multi-layer version of the DiskANN data structure (Jayaram Subramanya et al.] 2019), with improved navigability between distant clusters. While these data structures are naturally attuned for insertions, deletion is much more challenging and is heavily based on heuristics. What would be some metrics we'd want good deletion algorithm to have? 1). Memory usage. We would like the space consumed by the data structure to be proportional to the number of points stored in the data structure; 2). Efficiency. We would like the deletion algorithm to be performed efficiently, and ideally, efficient as the search al algorithm: 3). Recall. The deletion algorithm should not impair the recall performance of the algorithm. If one only cares about the recall, theoretically "optimal" strategy could be developed:
Theorem 3.1. Let P C. IRd be an n-point dataset preprocessed by an HNSW and E P be a point to-be-deleted that is not the entry point. Fix a query point q E R.2 and suppose the search reaches layer I E {1..... L}, let ((p) denote the neighborhood of p at layer l. Suppose reaches Np),, visits and leaves p. Consider the deletion procedure that removes p at layer I and forms a clique over N (y), then the search of q on the new gruph is equivalent to the search of q on the old graph.
We defer the proof to Appendix C The above theorem indicates that it is enough to design a data structure that emulates the subgraph without deleting p. Two obvious choices for exact data structures are 1). Tombstone, where the subgraph structure is preserved and we will still visit pt 2). Clique, where all possible paths in (p)) preserved.
These two approaches share similar drawbacks. While the tombstone algorithm cannot ever free memory and reduces query throughput through lengthened walks, the clique algorithm densifies subgraphs and reduces throughput by increasing the number of distance calculations made per step.
4 SPATCH: VERTEX DELETION VIA RANDOM WALK PRESERVING SPARSIFICATION
To motivate our deletion algorithm, we develop theoretical framework for analyzing HNSW that, instead of walking to the nearest point over the neighborhood, performs a random walk with probability given by the softmax of the squared distance.
Specifically, let q be the query point and suppose the search is currently on point u. Instead of deterministically moving to arg) ||c- g/I. move to random E N(u) with probability
exp( - (
Ee) -op(->=-[u--1"" We call this search algorithm the softmax walk. While this is different
from greedy search, we empirically validate that the performance of the softmax walk for large
4

---

Published as a conference paper at ICLR 2026
enough is very similar to that of the greedy walk (see Section 5). This simple modification enables us to analyze the graph search from the perspective of a random walk. Instead of interpreting the unweighted graph, we can now view it as a weighted graph with edge weight determined by the query point q: letting u be the point in the graph that the search for q is currently on, for any edge {u, v). the edge weight is w(u, v) exp(-r2 11 e1l²). The HNSW search then performs a random walk on this weighted graph. We could interpret it as probabilistic HNSW:
HNSW graph
Instead of greedy search, we use random walk;
Instead of taking the top-t nearest neighbors, we sample edges proportional to edge weights.
The edge weights we choose are equal to the Gaussian kernel between the query and the dataset. Intuitively, this is particularly useful to emulate greedy search because it helps differentiate the distances: if q is far away from v, then exp(-r² ||q - =Il²) would be much smaller than a v' that is closer q. Hence, under a proper choice of r, the Gaussian kernel function assigns exponentially high probability to nearby points, emulating the greedy search.
very widely used. Note, however, the difference in our case: the weight of an edge {u, f} is not exp(-r2 ||u - =ll?) as it would normally be, but rather, the edge is viewed two directed edges u + and -> u, with respective weights exp(-r² ||g u1l²) and exp( ||q - ull²). Thus, the edge weight is independent of its source point, and varies by the query q being searched.
We remark that graphs with Gaussian kernel weights
Thus, the graph constructed by our twin HNSW formulation can be formally viewed as the result of randomized graph sparsification. This algorithm can be integrated into the multi-layer HNSW structure by repeating the procedure from layer I to O. This weighted graph sparsification perspective provides the motivation and theoretical foundation of our deletion algorithm.
As discussed in Section 3 we would like a deletion algorithm that is optimized for memory usage, efficiency, and recall. Since we are now working with random walks, we first prove a variant of Theorem 3.1 in our model: instead of preserving the exact search path after deletion, we aim to preserve the random walk probabilities after deletion.
Theorem 4.1. Let G = (V, E, w) be a weighted graph. Define the random walk under the weights w for any edge eu, E E as Pr(u + I w] wlya) where deg(u) = EzEN(w) w(u, 2). Let be the point be deleted. For all u, E (p),, define the new weights w' (u, v) as w w (u. = w(u v) + v((p.))- Let E(p) = ((u. p} E N [P)) and C(p) = uu, u + v. u,u,UE (p)). Then
deglp)
for the new graph G (V \ (p), E \ F(()) U CCp), we have
Pr[u + v w'] Pr[(u + p - v) v (u + v) w).
The proof is deferred to Appendix C This theorem is known as a "star-mesh transform", " and arises from Schur complements and Gaussian elimination (Rosen 1924 Dorfter & Bullo 2012 2 Wagner et al. 2018). The new edges (p)) induce a clique over the neighborhood of p. making the graph denser than before. To sparsify the graph, we adapt simple strategy: sampling edges according to edge weights. The complete algorithm, called SPatch: Sparsified Patching, is given in Algorithm and shown in Figure !
Qut
OuT
OV
(a) p and its neighbors.
(b) Delete p.
(c) Form a clique.
(d) Sparsify the clique.
Figure 1: The deletion procedure of Algorithm
It proceeds by first forming a clique over the neighborhood of deleted point, and then sparsifies the clique according to edge weights.
I
To prove theoretical guarantees for Algorithm related to graphs.
!
we need to introduce few linear algebraic definitions
5

---

Published as a conference paper at ICLR 2026
Algorithm 1 SPatch: Sparsified Patching
1: procedure (PATCH(G(V,E) Vir,a,t 0)
2:
p is the point to be deleted from the graph. 3: Define w(u, v) exp(-p2 2, ||ue -012) for all u,
4: Let N (p) be in-neighbors of p and Nout (p) be out-neighbors of
5: t= (p)] + (p)l))
6: deg(p) = E EuE w(u,p) + + LVENNo w(p, v)
7:
for (p) and Nout (p) do
w w'(u, v) = v) + w((pp))-(pp.)))) Compute new weights for all pairs between in- and deg(p)
8:
out-neighbors.
9:
end for
10:
E" (u,
Miap),, E Nuu (p), (u, Top-t(w'(u, v)}} Delete p from the graph.
V {p}
12:
E(p) = ((, : Nialp), (p)}
E EXpD b Remove existing edges from (p)(p) Nout (p), add edges from
E"
14: end procedure
Definition 4.2. Let G Let W E Rmmm be the diagonal matrix for edge weights, and let B mx be the signed edge-vertex incidence matrix, i.e., each row of corresponds to an edge and it has two nonzero entries on the two endpoints of the edge, with one being +1 and the other being- -1 randomly assigned. The graph Laplacian matrix of G is defined as = B W B. Equivalently, let A E Rax= be its weighted adjacency matrix and D E n be its diagonal degree matrix, then we have L A
Graph Laplacians are among the most important linear operators associated with graphs, and have a rich literature (Merris 1994 Chung. 1997 Spielman 2007). In the following discussion, we consider the Laplacian matrix of the clique over (p). Sparsifying by edge weights is cquivalent to sparsifying
by the squared row norms of VWB B. which provides an additive error approximation in terms of the Frobenius norm (Drineas & Kannan 2001 Frieze et al. 2004 Kannan & Vempala 2017).
Theorem 4.3. Let G (V, E, w) and L Rax= be its Laplacian matrix. Let (0, 1). Suppose
we generate a matrix C' E ggsx by sampling each row of /W proportionally to its squared row norm with 8 = 200e -2, and reweight row by 1/(p:)) where ps = [KVWB B) ll//1l / B Then with probability at least 0.99, ||C C Lllr I E tr(W), where tr tr[W] is the trace of matrix W.
The proof is deferred to Appendix C Since Theorem 4.3 sparsifies the graph by sampling edges, the resulting matrix Č Č also forms weighted graph, which we denote by G' (V, E', w'). Compared to the standard spectral sparsification of graphs (Spiclman & Srivastava 2011), our sparsification scheme does not necessarily preserve the connectivity of the resulting graph G. Intuitively, sampling by edge weights is likely to ensure a cluster close points to be well-connected, but it falls short when only perform the sparsification
there are intercluster edges with small edge weights. However, process on the bottom layer of HNSW, whose role is to search through edges within a cluster, after intercluster connections have been effectively handled by top layers. This is also confirmed by our experiments (see Section 5) Hence, we assume the sparsified graph G' remains connected.
What does a Frobenius norm error approximation of the Laplacian imply for random walks? We prove that it approximately preserves the hitting time of the random walk.
Definition 4.4. Let G = (V, E, w) be a graph and v E V. The hitting time from to v, denoted by ho(u, v), the expected number of steps for a random walk starting at u to reach When G clear from context, we denote it by h(u, v).
Our main result is that an additive Frobenius norm error approximation of Laplacian gives multiplicative-addiie error approximation on the hitting time.
Theorem 4.5 (Informal version of TheoremeBBBB... B.S Let = (V, w) be graph, let G' (V, E', w() be the graph induced by Theorem 4.3 and suppose G' is connected. Let dmin: draxx be the min and

---

Published as a conference paper at ICLR 2026
max degree of G. and let ((G) be the edge expansion of the graph G. For any # V,
( u) hev (u, w)1 S E =tr[W] ho(u, w) + tr([W] [ (
-2
dmii
dmax
holds with probability at least 0.99, where o(G) minsgv Enve min[[S]][V w(w.e)
to perform its random walk without stopping at local minima, then Theorem [43 would say that if u is the entry point and e is the desired destination, then the expected numbers of steps to reach v from before and after sparsification are similar. However, the softmax walk stops at local minima, therefore, a bound on hitting time does not imply the walk could hit the correct destinations. Our experiments (Section 5) suggest that instead of directly correlating the correctness of the algorithm, hitting time is a good proxy when designing the sparsification algorithm, as Algorithm| I has good recall, query speed, deletion time, and memory utilization.
If our softmax walk algorithm
Theorem 4.3 states that to obtain an additive Frobenius norm error of E tr [W], we need to sample O( 2) edges, and this in turn provides an error bound on the hitting time per Theorem 4.5 How many edges do we need to sample in order to minimize the overall error? We show that in two common settings, the number of edges is linear in the number of points, [N(p)]:
Corollary 4.6. Let G = (V, E, w) be a weighted complete graph with [V] and G' = (V, E', w') be the induced graph by applying Theorem 4.3 to G. If [ = O O la (u, v.. -m). then with probability least 0.99, for any u. V, ho(u,, v) her (u, v) vn- ho(u, v). given one of the two settings:
Single cluster: for any u, U. E
0(1)
Many small clusters: there are /n clusters of size /n. Within each cluster, the edge weights are (1), and between clusters, the edge weights are O(1/n).
From Random Sampling Top-t Selection. In essence, the SPatch framework suggests
novel approach for performing local reconnect: instead of using the distances between points in (p)) directly, one should incorporate the distance between (p)) and p as well. This offers natural transition to a more practical and efficient deterministic deletion algorithm: first compute the new local edge weights w'(u, v) for all u. U E (p)), then keep the top-t edges with the largest weights. Note that for large enough the probability of sampling edges outside of the top-l edges is exponentially small. Thus, we could safely replace the "sample 1 edges" step with "keep the top-t edges with largest weights". This switch offers several practical advantages: in general, computing the edge weights then selecting the top-t heaviest edges is more efficient than sampling t edges without replacement. Thus, all our experiments are performed with the deterministic deletion algorithm.
EXPERIMENTS
We conduct extensive experiments to test the practical performance of our deletion algorithm. In the following, we will give a preliminary overview of the experimental setups, then we focus on discussing two sets of experiments: the major focus is on mass deletion experiment where points are gradually deleted with no new points inserted. We wrap up the experiment by showing that the random walk search algorithm performs well as the HNSW greedy search. Due to space constraints, we defer more details to Appendix
5.1 SETUP
Hardware. All experiments run on 8x3.7 GHz AMD EPYC 7R13 cores with 64 GiB RAM.
Implementation. We implement the HNSW data structure by utilizing the FAISS library (Johnson ct al. 2019 Douze et al., 2024). In particular, we construct the HNSW graph by invoking the HNSWF lat Index of FAISS with the degree parameter m = 32. We then extract the resulting graphs, which are directed, and convert them into a sequence of undirected networkx graphs (Hag berg et al. 2008) for our deletion operations.
Datasets. We use 4 datasets for our ANN benchmarks: SIFT (Jégou et al. 201 h, GIST (Sand
hawalia & Jégou, 2010), and one embedding of the MS MARCO (Bajaj et al. 2016) dataset with each
7

---

Published as a conference paper at ICLR 2026
of MPNet (Song et al. 2020) and Mi n LM (Wang et al. 2020). All of the datasets contain 1M points, with dimensions 768 (MPNet), 128 (SIFT), 960 (GIST) and 384 (MiniLM).
Deletion algorithm. For all deletion algorithms, adopt the strategy that uses the tombstone for all top layers and only performs the deletion at the bottom layer. This is viable as the bottom layer is much more connected and denser than all top layers. For SPat ch, we implement modified version in the following aspects: 1). Since the graph is directed, we let be the set of in-neighbors of p and let R be the set of out-neighbors, for each v E R, we pick the top-t == a [ points E T. where (u, u) maximized. 2). Instead of replacing all edges in (p)) including those exist before deleting p. we continue to add new edges with large weights until all top-t edges are added. This slightly densifies the graph without adding many edges.
Evaluation metrics. We focus on four important evaluation metries: top-10 recall (defined as the fraction of top-10 nearest neighbors returned by the data structure over the top-10 true nearest neighbors), number of distance computations for queries, the total time for deletion and the number of edges at the bottom layer. We use the number of distance computations as a metric for query throughput because for either the greedy search or random walk- search, the main runtime bottleneck is the number of distance computations. For deletion procedure, as it involves more complicated operations such computing edge weights for a clique, we directly measure the overall runtime of deletion. Finally, we use the number of edges at the bottom layer as a proxy measurement for the memory/space usage of the deletion algorithm, and in Appendix E.3 in particular Figure we show that it directly corresponds to the reduction in empirical memory utilization.
5.2 DELETION EXPERIMENT
In this experiment, we evaluate the performance of our deletion algorithm under the mass deletion setting, as follows: total 80% of the points will be removed from the dataset, for which every 0.8% of the points being deleted, 4 metrics: top-10 recall, number of distance computations, overall deletion time and the number of edges the bottom layer. For the query phase, we randomly pick 5,000 query points for SIFT, MPNet, Mi ní LM and 1,000 query points for GTST. These queries are fixed throughout the process.
the query through the remaining dataset and record the following
We compare algorithm against several popular deletion prototypes for HNSW: 1). No patching, where the point is deleted from the graph without rerouting or adding any new edges. 2). Tombstone, where the point be deleted is marked tombstone vertex without being deleted, and subsequent queries do not get stuck at a tombstone vertex. Xu et al. (203) adapts a version of tombstone with periodical scan and merge to ensure the freshness of the index. 3). Local reconnect (Xu et al. 2022).
where for each point in (p), an edge to its nearest neighbor in N(p) is added; 4). 2-hop reconnect, where the points u E (p) are rerouted to Np)) U N(u) then pruned. A wide array of deletion algorithms fall into this category, including (Singh et al.] (202T); Xu et al., (2023); /Zhao et al. (2023): Xiao et al. (2024); Xu et al. (0025). We implement and test the FreshDiskANN primitive (Singh et al., 2021). We also consider periodic rebuild strategy: every batch, we rebuild the HNSW from scratch.
We examine Figure method by method.
While Tombstone has the best recall among all methods as per Theorem 3.1 (even better than periodic rebuild), it quickly falls short in terms of query speed (2.5-3x more distance computations than SPatch) and its memory usage stays constant as more points are deleted;
Recall degrades most quickly when we do not patch, despite its fast query speed, deletion time and low memory consumption;
Local reconnect has slightly improved recall compared to no patching, yet still worse than others;
FreshDiskANN has better recall for datasets such as SIFT and MPNet. but the deletion time is slower. Although might be suitable when deletions are rare, in the setting of frequent deletions is inefficient. We also include Figure 5 deletion time comparison without FreshDisKANN;
SPat ch gives the best overall performance among various tradeoffs. While its recall is slightly lower than periodic rebuild and Tombstone, its query speed is much faster and memory usage decreases as more points are deleted than Tombstone. SP aPaton ch performs deletion much faster than FreshDiskAND and periodic rebuild.
8

---

Published as a conference paper at ICLR 2026
0.0%
2o--10 Recoll vs Deferntrannt Datches
3000
Sitarre Compu Delete Batches
Deletion Cettlo Balches
Dokete Batches
0.25
AMA
1000
0.75
3.000
(DINEe Bisches
Diince Blschess
Diiee Bloctes
D100Ee ELOCTRC
302
10230 socall vs Defernttintt Mitchee
1S253cce Compu treette battches
12iletion time Decece matches
1dgjs Jebete Barches
2012
0.50
0.00
2000
kmb
1500
6:10
8-44
1000
2.09
10
500
Delere Butchen
Oelere Barches
Dmare Darches
Denere
0.43
0.0
3200
0035
watc
3.0
07
4000
M ///r3
.008
0000
2000
3000
20
60
00
100
20
0
100
10333
20
40
90
110
6.0
42
60
100
0:55
11-10 Racall Vs Dedetmitaart Batches
Diearce Computad ont Dalete Bitthes
Deletion Time ut Delate Batches
Edges Oetere Barchen
2000
0.0
6.75
617
50000
Oiiate Baae
Figure 2: The rows are MPNet, SIFT, GIST and MiniLM, the columns are top-10 recall, number of distance computations per query, total deletion time and number of edges in the bottom layer of the graph. Legends: spatc? ch our algorithm SPat ch, fresh FreshDiskANN, tomb tombstone, nopat ch no patching, local - local reconnect. For MPNet: we also include rebui Id without plotting its deletion time..
5.3 RANDOM SOFTMAX WALK VS. GREEDY SEARCH
To empirically substantiate the validity of our randomized "twin" formulation of HNSW, we compare the two variants (softmax vs. greedy walk) Table [ The results show that they are highly similar empirically in recall and throughput, with the softmax variant incurring only a slight loss. This validates our use of it as a theoretical model for HNSW.
Top-10 Recall
Distance Computations
Dataset
Softmax
Greedy
Softmax
Greedy
MeNet
89.98%
91.60%
1562
1722
SIFT
91.13%
91.95%
1049
1109
GIST
71.38%
72.46%
1606
1653
MiniLM LM
89.27%
90.09%
1708
1802
Table 2: Comparison of softmax walk to greedy walk.

---

Published as a conference paper at ICLR 2026
5.4 ADDITIONAL EXPERIMENTS
We perform additional experiments to provide a comprehensive evaluation of Spatch against other popular deletion methods. In Section E.5 verify that Spatch our exhibits good performance on DiskANN graphs, in Figure 9 one could see that it achieves similar recall as FreshDiskANN, but has much smaller deletion time. In Section S..6 we compare Spatch with Dynamic Exploration Graph (DEG) (Hezel et al. 2025), yet another deletion algorithm for HNSW on SIFT. Through Figure TO) one could see that while DEG achieves slightly higher recall, the deletion time of DEG much slower than ours.
CONCLUSION
In this work, we provide a theoretical framework for HNSW using random walks and sampling. We then propose deletion algorithm, SPatch, based on a deterministic implementation of the theoretical motivation. Theoretical guarantees and empirical evidence demonstrate that Ptatch has good recall, speed, deletion time and memory. This random walk interpretation opens up new opportunities to study HNSW through the lens of random walks. We hope this framework sheds light on more theoretical investigations of HNSW and inspires novel practical algorithms.
ETHICS STATEMENT
This work designs fundamental algorithms for ANN data structures with experiments performed standard datasets. We don't foresee any potential ethics concerns of our work.
REPRODUCIBILITY STATEMENT
This work consists both theoretical and empirical results, we include the proofs of all theoretical results in Appendix
ACKNOWLEDGMENT
We would like to thank anonymous ICLR reviewers for their helpful comments. This work is done while Lichen Zhang was interning at Amazon. Lichen Zhang is supported by a Mathworks Fellowship and a Simons Dissertation Fellowship in Mathematics.
REFERENCES
David Aldous and James Allen Fill. Reversible Markov Chains and Random Walks on Graphs. 2002. Unfinished monograph, available at htthtttt///we sttp://ww.tttbbbt... berkeeeebb..eee..............ee. wdw.eyydduaaaaaa /WG//
book html
Alexandr Andoni and Piotr Indyk. Near-optimal hashing algorithms for approximate nearest neighbor in high dimensions. Commun. ACM, 11-121177112, January 2008. ISSN 0001-0782.
Alexandr Andoni and Iya Razenshteyn. Optimal data-dependent hashing for approximate near neighbors. In Proceedings of the Forty-Seventh Annual ACM Symposium on Theory of Computing, STOC 155 pp. 793-801, New York, NY, USA, 2015, Association for Computing Machinery.
Alexandr Andoni, Piotr Indyk, Thijs Laarhoven, Ilya Razenshteyn, and Ludwig Schmidt. Practical and optimal Ish for angular distance. In Proceedings of the 29th International Conference Neural Information Processing Systems Volume 1, NIPS' 15, pp. 1225-1233, Cambridge, MA, USA, 2015. MIT Press.
Alexandr Andoni, Thijs Laarhoven, Ilya Razenshteyn, and Erik Waingarten. Optimal hashing-basse time-space trade-offs for approximate neighbors. In Proceedings of the Eiventy-Eightt Annual ACM-SIAM Symposium on Discrete Algorithms, SODA '17, pp. 47-66, USA, 2017. Society for Industrial and Applied Mathematics.
10

---

Published as a conference paper at ICLR 2026
Alexandr Andoni, Piotr Indyk, and Ilya Razenshteyn. Approximate nearest neighbor search in high dimensions. In Proceedings of the International Congress of Mathematicians: Rio de Janeiro 2018, pp. 3287-3318. World Scientific, 2018.
Payal Bajaj. Daniel Campos, Nick Craswell, Hoa Dang. Jianfeng Gao, Xiaodong Liu, Ryan McNa- mara, Bhaskar Mitra, Tri Nguyen, Lin Qian, et al. Ms marco: A human generated machine reading comprehension dataset. arXiv preprint arXiv: 161 1,09268, 2016.
Joshua D. Batson, Daniel A. Spielman, and Nikhil Srivastava. Twice-ramanujan sparsifiers. In Proceedings of the Forty-First Annual ACM Symposium on Theory of Computing, STOC '09, pp. 255-262. New York, NY, USA, 2009. Association for Computing Machinery.
Jeff Cheeger. A Lower Bound for the Smallest Eigenvalue of the Laplacian, pp. 195-200. Princeton University Press, Princeton, 1971.
Fan R. K. Chung. Spectral Graph Theory. American Mathematical Society, Providence, RI, 1997.
ISBN
Michael B. Cohen, Rasmus Kyng. Gary L. Miller, Jakub W. Pachocki, Richard Peng, Anup B. Rao, and Shen Chen Xu. Solving SDD linear systems in nearly m log 1/2 n time. Proceedings of the Forty-Sixth Annual ACM Symposium on Theory of Computing, STOC '14, pp. 343-352, New York, NY, USA, 2014. Association for Computing Machinery.
Haya Diwan, Jinrui Gou, Cameron N Musco, Christopher Musco, and Torsten Suel. Navigable graphs for high-dimensional nearest neighbor search: Constructions and limits. In The Thirty-eighth Annual Conference on Neural Information Processing Systems, 2024.
Yihe Dong, Piotr Indyk, Ilya Razenshteyn, and Tal Wagner. Learning space partitions for nearest neighbor search. In International Conference on Learning Representations, 2020.
Florian Dorfler and Francesco Bullo. Kron reduction of graphs with applications to electrical networks. IEEE Transactions on Circuits and Systems Regular Papers, 60(1):150-163, 2012.
Matthijs Douze, Alexandr Guzhva, Chengqi Deng, Jeff Johnson, Gergely Szilvasy, Berre--Emmanee Mazaré, Maria Lomeli, Lucas Hosseini, and Hervé Jégou. The faiss library. arXiv preprint arXiv:2401.0828/ 2024.
Peter G. Doyle and J. Laurie Snell. Random Walks and Electric Networks, volume 22 of Carus Mathematical Monographs. Mathematical Association America, Washington, DC, 1984.
P. Drineas and R. Kannan. Fast monte-carlo algorithms for approximate matrix multiplication. In Proceedings 42nd IEFE Symposium on Foundations of Computer Science, pp. 452-459, 2001. 2001.
Wenqi Fan, Yujuan Ding, Liangbo Ning, Shijie Wang, Hengyun Li, Dawei Yin, Tat-Seng Chua, and Qing Li. A survey on rag meeting Ilms: Towards eetrieval-augmentee large language models. In Proceedings of the 30th ACM SIGKDD Conference Knowledge Discovery and Data Mining, KDD '24, pp. 6491-6501, New York, NY, USA, 2024. Association for Computing Machinery. ISBN 9798400704901.
Alan Frieze, Ravi Kamnan, and Santosh Vempala. Fast monte-carlo algorithms for finding low-rank approximations. J. ACM, pp. 1025-1041, November 2004.
Cong Fu, Chao Xiang, Changxu Wang, and Deng Cai. Fast approximate nearest neighbor search with the navigating spreading-out graph. Proceedings of the VLDB Endowment, 12(5), 2019.
Jianyang Gao and Cheng Long. Rabitq: Quantizing high- vectors with a theoretical error bound for approximate nearest neighbor search. In Proceedings of the 2024 ACM SIGMOD International Conference on Management of Data. ACM, 2024.
Yunfan Gao, Yun Xiong, Xinyu Gao, Kangxiang Jia, Jinliu Pan, Yuxi Bi, Yi Dai, Jiawei Sun, Meng Wang, and Haofen Wang. Retrieval augmenttdd generation for large language models: A survey. arXiv preprint 232 2023.
11

---

Published as a conference paper at ICLR 2026
Tiezheng Ge, Kaiming He, Qifa Ke, and Jian Sun. Optimized product quantization for approximate nearest neighbor search. In Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition (CVPR), pp. 2946 2953. IEEE, 2013.
Fabian Groh, Lukas Ruppert, Patrick Wieschollek, and Hendrik P. A. Lensch. Ggnn: Graph-base gpu nearest neighbor search. IEEE Transactions on Big Data, 9(1):267-279, 2023.
Aric Hagherg. Pieter J. Swart, and Daniel A. Schult. Exploring network structure, dynamics, and function using networkx. In Proceedings of the 7th Python in Science Conference (SciPy2008). Los Alamos National Laboratory (LANL), Los Alamos, NM (United States), 01 2008.
William L. Hamilton, Rex Ying, and Jure Leskovec. Inductive representation learning on large graphs. In Proceedings of the 31st International Conference on Neural Information Processing Systems, NIPS' 17, pp. 1025-1035, Red Hook, NY, USA, 2017. Curran Associates Inc.
Ben Harwood and Tom Drummond. Fanng: Fast approximate nearest neighbour graphs. In Proceed- ings of the IEEE Conference on Computer Vision and Pattern Recognition (CVPR), pp. 5713-5722. IEEE, 2016.
Ben Harwood, Amir Dezfouli, ladine Chades, and Conrad Sanderson. Approximate nearest neighbour search on dynamic datasets: An investigation, 2024.
Nico Hezel, Kai Uwe Barthel, Bruno Schilling, Konstantin Schall, and Klaus Jung. Dynamic exploration graph: a novel approach for efficient nearest neighbor search in evolving multimedia datasets. In International Conference on Multimedia Modeling, pp. 333-347. Springer, 2025.
Piotr Indyk and Rajeev Motwani. Approximate nearest neighbors: towards removing the curse of dimensionalityy. In Proceedings of the thirtieth anmual ACM symposium on Theory of computing, pp. 604-613, 1998.
Piotr Indyk and Haike Xu. Worst-case performance of popular approximate nearest neighbor search implementations: guarantees and limitations. In Proceedings of the 37th International Conference on Neural Information Processing Systems, NIPS '23, Red Hook, NY, USA, 2023.
Curran Associates Inc.
Suhas Jayaram Subramanya, Fnu Devvrit, Harsha Vardhan Simhadri, Ravishankar Krishnawamy, and Rohan Kadekodi. Diskann: Fast accurate billion-point nearest neighbor search on a single node. In H. Wallach, H. Larochelle, A. Beygelzimer, F. d' d'Alché-Buc, E. Fox, and R. Gamett (eds.), Advances in Neural Information Processing Systems, volume 32. Curran Associates, Inc., 2019.
Zhengbao Jiang, Frank Xu, Luyu Gao, Zhiqing Sun, Qian Liu, Jane Dwivedi- Yu, Yiming Yang, Jamie Callan, and Graham Neubig. Active retrieval augmented generation. In Proceedings of the 2023 Conference on Empirical Methods in Natural Language Processing, pp. 7969-7992, Singapore, December 2023. Association for Computational Linguistics.
Jeff Johnson, Matthijs Douze, and Hervé Jégou. Billion-scale similarity search with GPUs. IEEE Transactions on Big Data, 7(3):535-547, 2019.
Hervé Jégou, Matthijs Douze, and Cordelia Schmid. Product quantization for nearest neighbor search.
IEEE transactions on pattern analysis and machine intelligence, 33 2010.
Hervé Jégou, Romain Tavenard, Matthijs Douze, and Laurent Amsaleg. Searching in billion vectors: Re-rank with source coding. In 201 IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP), pp. 861-864, 2011.
Yannis Kalantidis and Yannis Avrithis. Locally optimized product quantization for approximate nearest neighbor search. In Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition (CVPR), pp. 2321-2328. IEEE, 2014.
Ravindran Kannan and Santosh Vempala. Randomized algorithms in numerical linear algebra. Acta Numerica, 26:95-135, 2017.
12

---

Published as a conference paper at ICLR 2026
Ioannis Koutis, Gary L. Miller, and Richard Peng. Approaching optimality for solving sdd linear systems. In 2010 IEEE 51st Annual Symposium on Foundations of Computer Science, pp. 234-244, 2010.
Rasmus Kyng and Sushant Sachdeva. Approximate Gaussian Elimination for Laplacians - Fast, Sparse, and Simple. In 2016 IEEE 57th Annual Symposium Foundations of Computer Science (FOCS), Los Alamitos, CA, USA, October 2016. IEEE Computer Society.
Thijs Laarhoven. Graph-Based Time-Space Trade-Offs for Approximate Near Neighbors. In Bettina Speckmann and Csaha D. Tóth (eds.). 34th International Symposium on Computational Geometry (SoCG 2018), Leibniz International Proceedings in Informatics (LIPPcs), pp. 57:1-57:14, Dagstuhl, Germany, 2018. Schloss Dagstuhl - Leibniz-Zentrum für Informatik. ISBN 978-3-95977-066-8
Patrick Lewis, Ethan Perez, Aleksandra Piktus, Fabio Petroni, Vladimir Karpukhin, Naman Goyal, Heinrich Küttler, Mike Lewis, Wen tau Yih, Tim Rocktäschel, Sebastian Riedel, and Douwe Kiela. Retrieval-augmenned generation for knowledge-intensive nlp tasks. In Advances Neural Information Processing Systems, 2020.
Kejing Lu, Chuan Xiao, and Yoshiharu Ishikawa. Probabilistic routing for graph-based approximate nearest neighbor search. In Proceedings of the 41st International Conference on Machine Learning. ICML'24. JMLR.org, 2024.
Yu A. Malkov and D. A. Yashunin. Efficient and robust approximate nearest neighbor search using hierarchical navigable small world graphs. IEEE Trans. Pattern Anal. Mach. Intell., 42(4), 2020.
Russell Merris. Laplacian matrices of graphs: survey. Linear algebra and its applications, 197: 143-176, 1994.
Yutaro Oguri and Yusuke Matsui. Theoretical and empirical analysis of adaptive entry point selection for graph-base approximate nearest neighbor search, 2024.
Richard Peng and Daniel A. Spielman. An efficient parallel solver for sdd linear systems. In Proceed- ings of the Forty-Sixth Annual ACM Symposium on Theory of Computing. STOC 14, pp. 333-342, New York, NY, USA, 2014. Association for Computing Machinery. ISBN 9781450327107.
Liudmila Prokhorenkova and Aleksandr Shekhovtsov. Graph-based nearest neighbor search: from practice to theory. In Proceedings of the 37th International Conference on Machine Learning, ICML'20. JoLR.org 2020.
A Rosen. A new network theorem. Journal of the institution of electrical engineers, 62(335))916-918. 1924.
Harsimrat Sandhawalia and Hervé Jégou. Searching with expectations. In Proceedings of the 19th ACM International Conference on Information and Knowledge Management (CIKM), pp. 1997-2000. ACM, 2010.
Anshumali Shrivastava, Zhao Song, and Zhaozhuo Xu. A theoretical analysis nearest neighbor search approximate near neighbor graph, 2023.
Aditi Singh, Suhas Jayaram Subramanya, Ravishankar Krishnaswamy, and Harsha Vardhan Simhadri. Freshdiskann: A fast and accurate graph-based ann index for streaming similarity search, 2021.
Kaitao Song, Xu Tan, Tao Qin, Jianfeng Lu, and Tie-Yan Liu. Mpnet: Masked and permuted pre-training for language understanding. In Advances in Neural Information Processing Systems (NeurIPS), 2020.
Daniel A. Spielman. Spectral graph theory and its applications. In Proceedings of the 48th Annual IEEE Symposium on Foundations of Computer Science (FOCS), pp. 39-38, IEEE, 2007. doi: 10.1 C000FOOSS200...66
Daniel A Spielman and Nikhil Srivastava. Graph sparsification by effective resistances. SIAM Journal Computing, 40(6):9133-1226, 2011.
13

---

Published as a conference paper at ICLR 2026
Daniel A. Spielman and Shang-Hur Hua Teng. Nearly-linear time algorithms for graph partitioning, graph sparsification, and solving linear systems. In Proceedings of the Phirty-Sixth Annual ACM Symposium Theory of Computing, STOC "04, pp. 81-90, New York, NY, USA, 2004. Association for Computing Machinery.
Prasad Tetali. Random walks and the effective resistance of networks. Journal of Theoretical Probability, 4(1):101-109, 1991.
Tal Wagner, Sudipto Guha, Shiva Kasiviswanathan, and Nina Mishra. Semi-supervised learning on data streams via temporal label propagation. In International Conference Machine Learning, pp. 5095-5104. PMLR, 2018.
Mengzhao Wang, Xiaoliang Xu, Qiang Yue, and Yuxiang Wang. A comprehensive survey and experimental comparison of graph-based approximate nearest neighbor search. arXiv preprint (rXiv:2101.2663, 2021.
Wenhui Wang, Furu Wei, Li Dong, Hangbo Bao, Nan Yang, and Ming Zhou. MiniLM: Deep self-attention distillation for task-agnostic compression of pre-trained transformers. Advances in Neural Information Processing Systems, 33:5776 57888 2020.
Per-Ake Wedin. Perturbation theory for pseudo-inverses. 217-232, 1973.
BIT Numerical Mathematics, 13(2):
H. Weyl. Das asymptotische verteilungsgesetz der eigenwerte linearer partieller differentialgleichun gen (mit einer anwendung auf die theorie der hohlraumstrahlung). Mathematische Annalen, 71: 441-479, 1912.
Wentao Xiao, Yueyang Zhan, Rui Xi, Mengshu Hou, and Jianming Liao. Enhancing hnsw index for real-time updates: Addressing unreachable points and performance degradation, arXiv preprint arXiv:2407.07871, 2024.
Haike Xu, Magdalen Dobson Manohar, Philip A. Bernstein, Badrish Chandramouli, Richard Wen, and Harsha Vardhan Simhadri. In-place updates of graph index for streaming approximate nearest neighbor search. arXiv preprint arXiv:2502. 13826, 2025.
Yuming Xu, Hengyu Liang, Jin Li, Shuotao Xu, Qi Chen, Qianxi Zhang, Cheng Li, Ziyue Yang, Fan Yang, Yuqing Yang, Peng Cheng. and Mao Yang. Spfresh: Incremental in-place update for billion-scale vector search. In Proceedings of the 27th USENIX Symposium on Operating Systems Principles (SOSP 2023), 2023.
Zhaozhuo Xu, Weijie Zhao, Shulong Tan, Zhixin Zhou, and Ping Li. Proximity graph maintenance for fast online nearest neighbor search, 2022.
Qiang Yue, Xiaoliang Xu, Yuxiang Wang, Yikun Tao, and Xuliyuan Luo. Kouting-guide learned product quantization for graph-based approximate nearest neighbor search. In Proceedings the 40th IEEE International Conference on Data Engineering (ICDE), pp. 4870-4883. IEEE, 2024.
Xi Zhao, Yao Tian, Kai Huang, Bolong Zheng, and Xiaofang Zhou. Towards efficient index construction and approximate nearest neighbor search in high-dimensional spaces. Proceedings of the VLDB Endowment, 1699)9197911991, 2023. doi: 10.1477881594552.3544777 URL
http://lll.cc.////////////... acm. http://///.aaaacc..oooo/////////
14

---

Published as a conference paper at ICLR 2026
APPENDIX
Roadmap. In Section we provide more preliminaries regarding notations and inequalities used throughout the paper. In Section[B, show how obtain multiplicative-addiin approximation for hitting time given an additive Frobenius norm approximation of the Laplacian. In Section[C] we provide missing proofs for prior statements. In Section D we supply more details for HNSW data structure. In Section E we present more details about experiments in Section and an extra set of experiments the steady state setting, experiments on DiskANN and extra comparison with other deletion strategies.
A MORE PRELIMINARIES
A. NOTATIONS
Let be a natural number, we use [n]] denote the set 21. .n.. Let X be a random variable, we use [X[] to denote the expectation of X, and let F. be an event, we use Pr[E] to denote the probability that event F. happens.
Let G (V. E. w) be graph where V is the set of vertices, E is the set of edges and w: E - R. be the weight function that assigns a positive real number each edge. We adopt the convention and let n :- [V| and m == El. Given a vertex E V. we use N (u) to denote its neighborhood, i.e., (u)) = {0 E {u, E}.
Let x Rd, without specification, use |||||| to denote general norm of use ||æ||2 to denote the lg or Euclidean norm æ. Let . E gnxd a matrix, we use [| to denote the spectral norm of M, ||M]|r to denote its Frobenius norm. We use M to denote the pseudo-inverse of matrix M. If M E IR"x" and is real, symmetric, we use X1 (.M))...,,yy (M) to denote its eigenvalues, ordered in ascending order. When M is clear from context, We use tr[M] to denote the trace of M, i.e., tr[M] Ex=1 M
λ Aq...., An to denote these eigenvalues.
A.2 USEFUL INEQUALITIES
We collect some useful inequalities to used later. Lemma A.1 (Markov's inequality). Let X be non-negative random variable and a >> 0, then
Pr[X -[E]]]]]] S !
Lemma A.2 (Weyl's inequality, Weyl 1912)). Let A, B Raxn be symmetric matrices, then for any E [n).
(A,(A) A,BB < | B||
Lemma A.3 (Theorem 4.1 of Wedin (1973).. For two conforming matrices A, B,
|| Bt| max ( [B I|A Bl|-
B HITTING TIME AND MULTPPLICTTVE-ADDIIII A APPROXIMATION
In this section, we prove that if we can generate a matrix L' with ||' Llle F S 8, then the hitting time can be also approximated in a multiplicative-adiite eиror manner. We first introduce effective resistance, an important metric on graphs that could associated with the graph Laplacian matrix. Definition B.1. Let G (V, E, w) be graph and u, V, the effective resistance between u and u, denoted by (G v), is defined as
Ra(u, (u, v) L'x.v. Xu.v.
where Xu,v Ep-
Tetali (Tetali 1991) proves that hitting time and effective resistance are intrinsically connected as follows.
15

---

Published as a conference paper at ICLR 2026
Lemma B.2 (Theorem 5 of Tetali (1991)). Let G (V,E, w) be graph and u, V with + the hitting time and effective resistance obeys the following identity:
1 Σ deg(=)(Ro(u,u)) + Ro(v,2) Ro(,,z))
h(u, 0)
2 ZEV
We need define the edge expansion of graph, as we will use Cheeger's inequality lower bound the smallest nontrivial eigenvalue of the Laplacian matrix.
Definition B.3 (Edge expansion). Ler G = (V, E, w) be a graph and S S V, define e(S) =
Eu w(u, v), the edge expansion of a set S is defined
e(S)
*(S) = min S
the edge expansion of the graph G is defined as
(GG) min (SS). SCV
Cheeger's inequality gives a lower bound on A2(L) in terms of edge expansion.
Lemma B.4 (Cheeger's inequality, Cheeger (191 1). Lel (V, E, w) be a graph and ((G)
be the edge expansion of G (Definition B.3 Let X2 be the second smallest eigenvalue of L and dmax = max deg(u), then
o(G)
2dmax S A2 20(G).
We next prove that if [| 1/ S 6, then - (I'Yt(] can also be bounded by invoking Lemma Lemma B.5. Let G = EV,E. w) be a graph and L be its corresponding Laplacian matrix, let G (V, F', w²) be the graph where E' E,, It be its Laplacian matrix and G' is connected. Suppose I L'Il S 5 for some 8 >> O, then
A.3
(G))²
| - (I') 28
2dmax
where oGG) is the edge expansion of G (Definition B.3 and dmax is the max degree of G.
Proof. The proof will be combining Lemma A.3 and Lemma B.4 By Lemma A.3
we have
|| 1 2 max | (I(")) [13] || L'll.
where we already have
|| L'|l < |L - I'll= < 8,
meanwhile, by Weyl's inequality (Lemma A.2 this also implics a bound on Ag Az(L'):
(A2(L) (2() < I L'll s 8,
it remains to establish a bound on (L) By Cheeger's inequality, we obtain
(G))
A2(L) 2dmax
since I. has rank know that
1
||
(L)
2duax
O(G)2*
similarly we can attempt to establish a bound on A2(T.'):
\2 - Az de (L)
16

---

Published as a conference paper at ICLR 2026
therefore
((G)
(2
2dx
and by the same argument ||
II''))II
)2((1)
2dmax
(G))
2d
we conclude the following bound:
x(G))
8) -2
max I(())))) S
2dmax
Put things together, we obtain the final bound:
(G)))2
-2
| - (L' S 28
2dmax
As natural corollary, also obtain bound on the effective resistance.
Corollary B.6. Let G = (V, E,E. w) be graph and G² = (V, E', w') with E² C E, L' be its Laplacian matrix and G' is connected. Suppose || L' L' S 8 for some then for any u. E V,
((G)
-2
(R(( (u, v) 40
8)
2dlmax
Proof. Fix E V, then
Ix (Lt (I')t)xuxl S <11Lt - (1')11 11x
S 48 xG)²2
2ilmaax -
where the last step is by invoking the bound on - - (L')tll of Lemma B.5
It would also be useful to have handle on the degree.
Corollary B.7. Let G EV, w) be a graph and G EVE',,") with E' E, L' its Laplocian matrix and G' is connected. Suppose [ 1/1lr 5 for some > then for any V.
|dego(u) - degar (u) S 6.
Proof. Note that (u) e. Lea and dego (u) = E.g L'e., thus
(u) degor (u)
|e] (L L' L')eul
S || T, T/|l ||eu
[ I''l
< 8.
We are in the position prove main theorem regarding hitting time. Theorem B.8. Let G = (V, F, w) be graph and G' = (V, F', w/) with E'C F, T' be its Laplacian
matrix and G' is connected. Suppose L. T''[ < 8 for some ó > O, then for any u, u E with +
d(G)2
-2
Iho v) - hor (u, v)] S dmin ha v) 125
-8)
Σ we
2dmax
17

---

Published as a conference paper at ICLR 2026
Proof. By Lemma B.2 know that
1 helu, v)
Σ
(2) Ro(u, Ro(u, 2)),
(1)
2
by Corollary B.6 have that
Ro(u, u) (G.(u,,)) v) 40 [()))
-2
-
2dmax
2dmax 8) -2
((G)²
for ease of notation, let 8' = 46
and by Corollary B.7
|ega (u) dega (u)l s 8.
To apply Eq. (T). we examine one term as follows:
(=) v) dega (u, S (ega(=) v) (dega(=) (u,
dega (2)a())Ro(u)) v) (dego(z) ((RR((,)) -8')
8' dega(=) (Rc(u,v) 58
8' dega(z) + (u,
Putting together yields
ha(u, v) (u,
1
(dcga()) Ra(v,2) Ro(u, 2)) (2) + (v, Ro (u, 2)))
2
#EV
<
1
Σ
38' (z) + 8( + Rc(u,z) R
2
=EV
Σ dega(2) (2) + 2
Σ
Ro(u, v) + Ro(v,2) - R)(u,2)
2
#EV
*EV
3
8'
Σ dega (2) + +=
Σ
Ro(v, Ro(u, z)) dega(z)
2
#EV
zEV
< 8'
3
Σ dega(=)
+ 0
Σ
dego de + 2)( - Ro(u, z]) Jmin
2
2
*EV
LEV
We + 8 ho(u, v),
38'
Σ
dmin
this completes the proof.
C MISSING PROOFS
In this section, we include the missing proofs in previous sections.
Theorem C.1 (Restatement of Theorem 3.1p. Let P Ed be an n-point dataset and p P be point to-be-deleted. Suppose P is preprocessed by an HNSW data structure and p is not the entry point of the HNSW. Fix query point q E R and suppose the search reaches layer I (1.....I) let N (p) denote the neighborhood of at layer I. Suppose reaches N (p), visits and leaves Consider the deletion procedure that removes at layer and forms clique over N(p), then the search of on the new graph is equivalent to the search of y the old graph.
Proof. Let denote the graph at layer 1 before deleting and G. denote the graph at layer after deleting p. By assumption, there is some vertex E N(p)) visited by the walk immediately before visiting p, and another vertex b (p) visited immediately after. We focus attention on how the graph transformation affects the - p + section the traversal. In the original graph, the walk transitioned from p because p is the vector in ((a) nearest to g. However, since the walk then
18

---

Published as a conference paper at ICLR 2026
transitions from p to b, it must be the case that b is closer to q than is any point in N(p) U {p), and thus |6 - qll = gin, ||c - qll I lpp gll.
Now, consider the new graph where p is deleted and clique is instead inserted between the vectors in its former neighborhood. The walk remains the same until it first hits a. From a, there are two possible (not mutually-exclun
types of neighbors the walk could transition neighbors of a in the original graph, and those new neighbors it acquired when the clique was inserted (p), including Ipp 1 gll S || - gll for each x among the original N ((a). Combining this with the previous inequality, must the case that || - qll = miny 11y q.l. with y ranging over the entire new neighborhood of
those that were
Because the old walk transitioned into p, must be the case that
and thus the walk must still transition into b. at which point it proceeds as before.
Theorem C.2 (Restatement of Theorem 4.1 Let G (V, E, w) be a weighted graph, define the | w] w(u.v)
random walk under the weights w for any edge (u,v} E as Pr(u deg(u) EveN(u) w(u, 2). Let p be the point to be deleted as for any u, U E N()), define the new weights w' (u, v) as w/ (u, v) w(u, v) + w(p.)) ler E(p) {{u. p} : u E N(p) and deg(p)
degtu] where
(pp) = Hu, o) u # U, u, E [p)), for the new graph G' = (V (p). E E(P) ww)) we have
Prfu + w'] Pr[(u + (u + v) w].
Proof. Consider the neighborhood of p, (p),, let (p)), we reason over the probability that the walk moves from u v. Note that after deletion, the only change is that the vertex p has been removed from the graph, therefore, there is no path from u - + u. On the other hand, there is
now direct path from u to under the new weight w' w'u,, v). so we need to show that the probability is not affected.
Recall that for any vertex Nu), we have that the probability the walk moves from u is
w 2)
deg(u) ())
where deg(u) E Ew) w(u,=) Before deleting p. we calculate the probability of the path p together with the probability of -
Pr[(u- + + v) V (u -) w]]
Pr|u p w| Pr(p v
p, w/ Pr/u e w]
wu, p) w(p,v) w(u,v)
deg(u) deg(p) + deg(u)
After deletion, the random walk is performed via new weights w':
w'(u, v)
Pr[u + v w']
deg' (u)
w(u, v)
w(u, p) w(p,v) v) deg(p) deg' (u)
(2)
deg' deg((u) (u)
note that
de) Σ
w(u,v)
Σ w/ (u, vEN(p)
((N(
w(u, p) w(p,v) deg(p)
deg(u) - w(w,p) +
vEN(p)
deg(u) - w(u,p) + wwwu
deg(u)
therefore
w(u u)
w(u,p) p) w(p, v)
deg(u) deg(p) deg(u)
which is the same as the probability of walking from u to v either via the edge (u, 4n or the path
p v.
19

---

Published as a conference paper at ICLR 2026
Theorem C.3 (Restatement of Theorem 4.3
Let G EVE,ww and L Rux= be its graph Laplacian matrix. Suppose we generate a matrix C Rsx" by sampling each row of /W B proportional to its squared row norm with = 200c-?, and reweight row by 1/(ps) where p: I). B lis then with probability al least 0.99,
IŞ²T Č LLle S & S
Proof. For simplicity of notation, we let := vW B. Define the random variable X, = p, Ci, CT 1, where P1..... Pm are the sampling probabilities of the process, i.e. ps ||C.,,Il//l 1tt.l/////// several important properties of these X;'s. s.
We prove
Expectation. Note that
1
B[X]= =
Σ
Pj
Ci,a
C,
Pr
f=1
Σ
C...C.T
1,-
i=1
=
Expected Frobenius norm. We compute the entrywise variance of X:
E
||
Σ
B
Pk
Pk
n 1
|| 11
|
let Y 1
8 Ei= Xj, then
B1|| Y 1|:
E||l
X
1
+
Σ
Eltr[(x,,,)]
3
1011
+
2
Σ
xX,
8
is
|C
2
+
[r[
E|X,]]
82 ij
||
- 1
s
Probability. We will be using Markov inequality on || - C. CII to do so we first compute
B[ir[YCT C]]
r[[E CJ]
20

---

Published as a conference paper at ICLR 2026
u
= -II
and compute the expectation of the squared Frobenius norm deviation:
E||lY - C CT
= B|I|Y +
| CIB -
I1111 +
2s -
|CC' C - 2||C
||0||
Set s = 100e 2, we obtain that BiJlY - CTC1| $ = By Markov's inequality
(Lemma A.I) we have
5² | 1
Prill - CT > CI|
<
100'
as desired. Utilizing structure of C, we could further simplify the bound: ||C|| 2 2eEB We = 2||w||1 = tr[]..
Corollary C.4 (Restatement of Corollary 4.6 Let G- (V, E. w) be weighted complete graph and G" = (V, E', w') be the induced graph by applying Theorem 4.3 to G, and assume G' is connected. If E' Ommax,,veNip N(p) hu v) n), then with probability
least 0.99, for any u. U E V.
[ (u, v) her v)1 S /n ha(u, v). given one of the two settings:
Single cluster: for any u, V, u(u,v)=
Many small clusters: there are v clusters of size Vn. Within each cluster, the edge weights are O(1), and between clusters, the edge weights are O(1/n).
Proof.
We prove the two settings item by item.
Single cluster, that is, for all u, u', of E V, we have w(u, v) (w(w', 0(1). )). In this case, tr[W] = On?),, dmin dmax = (nn) and (G) = O(n). The multiplicative error factor for and the additive error term is E n² (n
ho(u, v) is then
? (I-enjz I 4s-1_ so the overall error is en (,(u,, v) + 4a- equating these two terms sets s = v/ ha(u, v). According to Theorem 4.3 this means that we can sparsify the number of edges in clique C(p) from O( (z) down to O (maxx,vEN(p)) hu,, v) (N)))
en
Many small clusters, in particular the max edge weight is O(1) while the min edge weight is Onn (n) Among the n points, we assume they are clustered n.05 parts, each of size 0.5 For the (n²²) intercluster edges, the edge weights are O(n 1), while other edges have weights O(1). In this case, tr[W] = n + 1.5 < Onn..5), dmii, dmax = (n5 and o(G) = 0(1), and the multiplicative factor is e n and the additive factor is e- n (n.-0.. 0.5 e. 121.5)-220 (1-enzyz S 4e-1,
en
so the overall error is en ha( v) + 11 We would set e /n ha(u, v) to minimize the error, Note that now the number of edges in the sparsified graph is O(max,, h(u, v) (N)))
D HNSW DATA STRUCTURE
We review the both classical HNSW data structure proposed in Malkov & Yashunin (2020) also provide more details about our random walk-base variant of it in this section.
D.1 CLASSICAL HNSW
In this section, we provide a more in-depth review of the HNSW data structure. We lay out its structure in several algorithms, starting from the search procedure.
21

---

Published as a conference paper at ICLR 2026
Algorithm 2 HNSW algorithm: layer search.
1: procedure LAYERSEARCH(G e IR", P c IR4, / (I,..., LJ, u e P, m E ([Pl)
2:
& I is the layer of the graph, is the starting point and m is the total number of nearest neighbors to return.
3: visited < {u}
Visited vertices.
4: candidates + {u}
D Candidate vertices.
5: nbrs t fu}
b Dynamic list of nearest neighbors.
6: while candidates > 0 do
7:
nearest neighbor of in candidates [ < furthest neighbor of in nbrs candi sandidates candidates {c}
8:
9:
10:
if c gll > |lf - qll then break end if
12:
13:
for v E nbrhood(c) at layer do if v & visited then
14:
15:
visited < visited U {a}
16:
f + furthest neighbor of in nbrs
17:
|[ - all or |abrs| < m then b Either v is closer or nbrs is not | 4 <
full.
18:
candi dates +- candidates U {a}
nbrs nbrr U (v) if Inbrs| > m then
20:
Remove furthest neighbor of in nbrs
22:
end if end if
24:
end if
end for
26:
end while
27:
return nbrs
28:
end procedure
To construct the HNSW data structure, we implement the insertion procedure.
The insertion works follows: it simply performs Algorithm from L to + 1 where is the designated layer for q to be inserted. Starting from layer to 1, we increase the number of points to be returned by Algorithm to add edges using NEIGHBORSELECT. This procedure then repeated for the new neighbors g to prune edges.
( (e FConst ruct in can be much larger m)) and then select of them
The only missing piece the neighbor selection procedure, Malkov Yashunin 2020) recommends two types of neighbor selection: one is simply taking the top-m nearest neighbors. while the other involves more sophisticated heuristic procedure. We refer readers to Malkov & Yashumin (0200) for more details.
D.2 PROBABILISTIC HNSW
Inspired by the classical HNSW data structure, we propose a random walk-based approach for both searching and constructing the data structure. While give overview in Section here provide the complete algorithm.
The key distinction between Algorithm 2 and 4 is line 7: instead of taking the nearest neighbor, Algorithm 4 samples a point to move to based on the softmax of negative squared distance. For insertion, give alternative presentation that shows how construct the one layer of HNSW by first building a complete graph, then randomly sparsifying it. showcases in Algorithm and Figure 3
22

---

Published as a conference paper at ICLR 2026
Algorithm 3 HNSW algorithm: insertion.
1:
procedure INSERT(y E RR, c u u P, ro E [PP],, m e [|P]], mmxx
[P]))
2:
[ Inli-i(Uni((... 1)) Imm]
3:
- ++
4:
bandidatess + LAYERSEARCH(Q: P,le, 1, arg min mingeaaddadeee ||u
5:
6: end for
7:
for 4= min L,1] + do
candidates + LAYERSEARCH( P, infCossttuuciio) 9: nbrs f NEIGHBORSELECT(Q. candidates,
8:
10: Add edges between and nbrs at layer le
end for
12:
for E nbrr do
13:
(u)) + nbrhood(v) at layer lc if [N)] > Mmmx then
14:
15:
newNbrs + NEIGHBORSELECTTH. N(u), mmax: Le)
16:
Add edges between and newNbrs at layer le
17:
end end for
18:
19:
u < candidates
if L then 11 4
21:
end
23:
end procedure
D.3 RUNTIME ANALYSIS OF SPATCH
We provide preliminary runtime analysis of SPatch (Algorithm TT. Let p be the point we want to delete, then note that the most expensive operation is to compute and update w' w'uu, v), which takes O( (N (p) d' time, all other operations are subsumed by this step.
D.4 CONSTRUCTION VIA SPARSIFICATION
The typical construction process of an HNSW graph involves the following steps:
Given a point u, determine the layer L, be inserted;
Perform greedy search for from layer down to L, + 1, moving a layer downward each time the search is stuck;
In layers | 4, perform greedy search for u, and draw edges between u and the m nearest points to it that were visited along the search path.
Having replaced greedy search with softmax walk, the graph construction process as a sparsífication the weighted complete graph, as follows, Let Go be a weighted complete graph with the edge weight between two vertices being exp(-y² ||u 21. We claim that each layer of the HNSW graph G1 can be constructed via a random walk-based sparsification of Gg. To this end, fix ordering of the vertices U1,..., Un. and initialize the graph with a single node U1- Then, alternate between the complete graph Go and a sparsified graph as follows: for i 2, .2,
provide probabilistic interpretation of
Densify: Add v, G, by adding all edge (u, 0,} for - 1], with edge weights exp(-r2. ||u--, 1y)1²).
Random walk: Perform softmax walk for uy in G starting at vn, maintaining list of the nodes risited along the walk.
Sparsify:
After the random walk terminates, sample points from visited with probability propor- tional to the edge weights attached to them in the Densify step, forming a set sample. Remove edges between v; and points not in sample.
23

---

Published as a conference paper at ICLR 2026
Algorithm 4 HNSW algorithm: layer search.
1: procedure LLYERRSFARCHRAANOWWWAKRRR
IR,
Rdd (0...., LJ,u u e P.m.
[P]), r E R24)
2:
b is the layer of the graph, u is the starting point and m is the total number of nearest
neighbors to return.
3: visited < {u}
Visited vertices.
4: candidates {u}
Candidate vertices.
5:
nbrs + {u)
b Dynamic list of nearest neighbors.
6: while |candidates| > do
7:
Sample e with probability Σ Eeeondidaces expl -
expl exp(-r--1le 9
8:
f + furthest neighbor of in nbrs candi daleidatessee candidates {c}
9:
10:
|ce gll ||f - qll then
11:
break
12:
end
13:
for E abrhood(c) layer do e @ visited then
14:
visited visitedU U {v}
16:
f furthest neighbor of g in nbrs
|| - q || - qll
|nbrs| m then
Either is closer rbrr
full.
candidates + candidates {u} nbrs <- nbrs ( if [nbra| m then
19:
20:
21:
Remove furthest neighbor of in nbrs
22:
end if end if
23:
24:
end end for
25:
26:
end while
27:
return nors
28:
end procedure
Sparsify the neighborhood of each E sample by subsampling m of the edges incident to with probability to their edge weight.
This point view also justifies our use of edge weights when performing deletion, as we could treat the edge weights are formed during construction and inserting the corresponding the point.
E ADDITIONAL EXPERIMENTS
E. DETAILS OF PREVIOUS EXPERIMENTS
We start by examining more details regarding prior experiments conducted in Section 5
Deletion experiments. Regarding deletion algorithms, note that several of them have hyper-
parameters:
FreshDiskANN (iighh al. 202 requires hyper-parameter which governs how many edges prune after rerouting to N(p) N(u), intuitively, the larger the a, the denser the graph. According to [Singh et al. (2021). should be chosen 1. In our experiment, due to the time-consuming nature FreshDiskANN deletion procedure, we set a = 1.2. also worth noting that FreshDiskANN is designed for DiskANN, which has slightly different insertion procedure from HNSW.
Our algorithm sPat ch also requires hyper a, which determines how many edges to keep in the clique after sparsification. Intuitively, the larger the a, the denser the graph. Through out experiments, observe that choosing 1.2 except for GTST yields good performances. In
24

---

Published as a conference paper at ICLR 2026
Algorithm 5 Construction via sparsification.
procedure CONSTRUCTONELLAERR e (RR))" m E [n],r E R+) Determine an ordering of the points in P, label them V1, ...
2:
3:
G (fv.),) i do
4:
5:
candidates + {u1}
6:
visited t {e1}
7:
V+ U- {es}
8:
// Densiff phase
9:
+ E EU ((u), [(1) v.) : j E - w(vy, = exp(-r2 110 - 1/ 11
Random walk phase
11:
while /candidates| > 0 do
expl |||; -||
12:
Sample c candidates with probability
LuEandidacos expl 1| 1 2)
candidated candidates {c}
14:
for u E nbrhood(c) do
if u & visited then visited +- visited V (u} candidates + candidates U {u)
16:
18:
end if end for end while
19:
20:
21:
Sparsify phase sample Sample points from vi srsssited independently without replacement, with exp(-r2-|lp,
22:
probability of sampling u being Eveviesee exp
E + {(eg u}
sample}
24:
for E sample do deg(u)) > m then Sparsify nbrhood(u) by sampling edges
25:
26:
27:
end if end for
28:
29:
end for
end procedure
particular, this consistently holds for MPNet and MiniLM, For SIFT, we could further improve the recall and efficiency by choosing = 0.6. For GIST however, one has to choose to be smaller than obtain good recall and efficiency. In our experiment, we choose a = 0.4. We To choose a, recommend either using 1.2 or 0.6.
summarize the choices in Table 3
SIFT
GIST
MPNet
MiniLM
0.6
0.4
1.2
1.2
Table 3: Choices of hyper-parameter for different datasets.
Random softmax walk vs. greedy search. For this experiment, we need to choose hyper-parameter r (recall the softmax walk samples for the next visit with probability 11pp--2-1lq--// Intuitively, want to choose higher probability than the second nearest neighbor. This could be achieved by choosing r to be arbitrarily large. However, if is chosen to be too large, the probability resolve this issue, we adapt the following approach for computing r: given a collection of points candidates consider (line of Algorithm 4. we compute the empirical average of the distances
that the softmax walk samples the nearest neighbor with exponentially
easily overflow. To
|lu-ql μ Σ Annand dates Jcendidates] then we set 15/u. This scales r ||g u|l to value between 10 and 20, and empirically, we observe that this choice can differentiate among the top nearest neighbors and henceforth, give similar recall as the greedy search.
25

---

Published as a conference paper at ICLR 2026
E
D
E
B
A
B
(h) Densify phase, insert Q to the graph and add edges between all existing vertices
(a) Initial graph
D
E
A
B
(c) Random walk phase, walk starts at A and goes E
C,
(d) Sparsify phase, keep edges between C and E
Figure 3: We construct the graph by first adding edges between Q to all vertices, then perform a random walk determine the candidate edges keep, and sparsify them by sampling.
Figure 4 juuttifies this decision to fix rμ 15 by demonstrating the behavior of Random Softmax search for different values 7 := rp. The left plot shows that as 7 increases, the softmax converges toward true maximum, and randomized softmax correspondingly better matches the greedy search algorithm. Thus, F in this regime usually- but far from always transitions to the current node's neighbor closest to q. The right plot shows the impact of f recall, and in partieular its convergence to the performance of the pure greedy algorithm (dashed horizontal lines) for F RJ 15. Deletion time
Probability of Transitioning Greedy Neighbor
Recall of Random Softmax Search
200
30
Greedy Steps (%))
80
Recall
20
60-
SIFT
SFF
NPMMe:
10
MiniM
MnL. M
0
10
15
20
10
20
Figure 4: The impact of varying F (i.c. rı) on transition probabilities and recall. Left: The frequency with which the random softmax algorithm truly transitions to the nearest neighbor (i.e. a greedy step), as function of F. Right: The impact of different choices of f on the recall of the randomized search algorithm. Horizontal line indicates the recall of greedy search algorithm.
without FreshDiskAND D......NNN. As have observed in the experiment, FreshDiskANN has much slower
26

---

Published as a conference paper at ICLR 2026
deletion time than other methods, in the following figures, we provide deletion time comparison without FreshDiskANN.
Deletion Time vs Delete Batches
Deleden Time vs Delete Batches
koal reBAECT
Dreectinn
roDRECT
2-
0
Deleta Setcher
Delete Batchee
Delete
vs
0.00010
0.00014
0.00012
0.00000
0.00010
Deleden
0.00026
0.00004
0.00002
0.00002
0.00000
0.00000
D0
102
1.0
Delcte Boothes
Delzte Botchcs
Figure 5: Top left: SIFT, top right: GIST, bottom left: MPNet, bottom right: Mini LMM
E.2 STEADY STATE SETTING
In this experiment, we consider the steady state setting introduced in Singh al. (2021) where 10% of the points are deleted from the data structure then inserted back, and queries are measured. We repeat this process 10 times, albeit points have been deleted from the data structure and reinserted. Similar to the mass deletion experiment, we randomly pick 5,000 query points for S SIFT, MPNet, MBREAD and Mi niLM and 1,000 query points for GIST.
Through Figure 6 we could see similar trend as in the deletion experiment (Section 5). except that the no patching algorithm gives better recall than before. This because in the steady state setting, the graph is automatically "patched" by re- re-inserting the same set of points back to the data structure. In contrast to the experimental results in (Singh al. (202T), FreshDiskANN does not perform even well patching, this in part is because the insertion algorithms for DiskANN and HNSW quite different. Regarding hyper- hyper-parameteer parameters: for FreshDiskANN, we again choose a = 1.2, and for SPatch, summarize it in Table
SIFT
GIST
MPNet
MBREAD
MiniLM
0.5
0.5
1.2
1.6
1.2
Table 4: Choices of happhh-ypramaeee parameter a for different datasets.
E.3 VERTEX COUNTS, EDGE COUNTS, AND MEMORY UTILIZATION
To see the impact of SPatch on the graph size and empirical memory utilization, we design an alternative steady-state experiment in an environment with very high vector turnover. Starting with an empty database, we continuously insert into it one vector per (simulated) second from the Min LM LM dataset over the duration of 12 (simulated) hours. Each vector survives for a number of steps following an exponential distribution with mean of 2 hours (i.e. has half-life of 2 2 s 1.39 hours), after which it is deleted. Hence, while the experiment has more insertions than deletions for the first few simulated hours. it eventually enters steady state at which insertions and deletions occur at roughly the same rate. At the end of the 12 hours, no new vectors are inserted, and the remaining vectors continue fall out as they expire.
27

---

Published as a conference paper at ICLR 2026
Top22 20 Recall beltt Barches
Distance Computations Delate Batchen
Deletin Delate Batches
Delets Satches
fresh
0.12
0.91
Fesh
1600
0.30
sparch
To0
ropatth
0.00
0.90
aptth
1amb
31:00
0.00
tomih
soulch
1230
0.04
0.00
1090
0.00
Delete Batches
Delete 5otches
Deltte Botches
Delece Bancles
100:00 Rosel Dckiclheett Bassne
Datencs Compotetiorr va Deibc Botchca
Delction Tims va Dekbe Selches
Edpe Delete Butcher
Frssh
0.675
roparch
repatch
tamb
0.859
spatch
spatch
0.625
fwih
ruputch
0.00
nepuish
0.0
0.550
2800
0.64
0.525
042
1400
10
Delete
Batches
Delete Batches
0.40
Top:10 Recalive Deletatneat Datcher
Dimance Comp. tettons Delate Batcher
Deterion Canchee
Edoes Dalete Datchec
1400
Rrehh
Teet
0.93
1300
nopatch
nopatch
0.90
0.00
11.00
tomb
0.55
spatc
0.000
0.57
tamb
nopaccs
200
6.75
Delete Botches
Ddltte Botches
Ddltte Betches
Deltte Botches
100- 10 Recall Jeleceiinset Batches
Distance Compusatiins us Delete datches
Delctin me Delete tatches
Edges us Delete sotches
fresh
0.36
0.20
2300
(kpelth
scotch
0.34
tome
sputchh
1200
bast repatch
15
0.00
0.000
1000
0.00
tamb
900
0.00
0.00
10
Recal Deletedieet Batches
1300)
Dicaace
Delete
Deterior Delete Batriee
frcs)
fres)
0.90
nopwtich
nopalch
0.84
1300
0.150
6.125
1200
0.87
0.100
timb
0.56
Besh
1000
0.055
coatch
0.55
samb
noputics
500
Dilate Detches
Dilate Detches
Detate Detches
Delate Datches
Figure 6: The 5 x 4 grid of figures, where the rows are SIFT, GIST, MPNet, MBREAD and MiniLM, and the columns are recall, number of distance computations per query, total deletion time and total deletion time excluding fresh DiskANN, Legends: spat spatch our deletion algorithm SPatch, fresh FreshDisKANN algorithm, tomb tombstone algorithm, nopatch no patching algo- rithm.
We track the vertex counts, edge counts, and memory utilization both the Tombstone algorithm and of SPatch, and the results are shown in Figure 7 Vertex and edges are counted cumulatively over all levels of the graph. Hence, we continue to see a small rise even in the steady state: the upper layers of the data structure still continue to accumulate them at their prior rate. However, the rate of increase is far slower than that of the Tombstons algorithm, which intrinsically grows at a steady rate independent of the number of deletions.
28

---

Published as a conference paper at ICLR 2026
We also stark difference in memory utilization (as measured by python's psutil package), While the Tombston one algorithm is marginally more memory efficient before the effect of deletions begins to kick in (as result of storing approximately d + instead of d + 2m = 448 due to the bidirected nature of the HNSW graph), soon the vector deletion begins saving large amounts of memory due to the combined effect of the vertices, edges, and d-dimensional vectors removed from the data store. Although vertex, edge, and memory all continues rise with SPat ch, it does so substantially slower than with Tombstone Finally, after we enter the pure-deletion phase of the experiment 12 hours in, we see no further change in any of the plots for Tombstone (as expected), but each of the metrics begins its decrease for SP ch. While not all of the memory can be directly recovered by the Operating System due to fragmentation or other similar considerations, we see the memory utilization of SPatch begin to dip, and (unlike in T Tombst one) much of the unrecovered memory is ready for reuse by the algorithm should it face more insertions in the future.
384 + 32 416 words per vector
Actions
Edges Layered
Vertices Layorad
Empirical Hemory Utilization
44500
40000
1400
200
35400
175
30000
2300
500
125
400
Edge
30
14
31
11
10
14
10
15617
Figure 7: Vertex counts, edge counts, and empirical memory utilization as measured by the experiment described in Section
E.4 SOFTMAX WALK AND GREEDY SEARCH: A MORE DETAILED COMPARISON
In this section, we give a more detailed comparison between softmax walk and greedy search. For the first set of plots, we plot beam size vs recall @ 10, and for the second set of plots, we plot the total number of distance computations vs recall @ 10 in Figure X We can see that fixing the beam size, softmax walk gives slightly lower recall, but the second row shows that fixing the number of distance computations, softmax walk is very close to greedy search.
LM
6.0
2000
lewely
1.00
0.55
6.34
0.50
0.07
6.78
Brore
Beam
SIT
GIST
NPNEET
mMLM
0.2
0.5
1.50
6.36
6.3
0.58
032
080
0.
03
32
50
35
03
Figure& 8: From left to right: SIFT, GIST, MPNet and MiniLM. Top row: beam size vs re- call @ 10, bottom row: total number of distance computations vs recall @ 10.
29

---

Published as a conference paper at ICLR 2026
E.5 EXPERIMENTS ON DISKANN
In this section, we provide preliminary experiments on DiskANN, specifically we test SPatch, FreshDiskANN, tombstone, local and no patch algorithm. We test it on subsampled 100k points from SIFT dataset, each deletion batch, we delete 800 points then perform a query. Compared to the experiments on HNSW, FreshDiskANN has improved performance in terms of recall, however, we note the deletion time of FreshDiskANN is still very large.
Ecges
$5500
0.00
10:00
With
0.000
CONN
Freet'
12:00
0000
5000
500
0000
500
123
Figure 9: Experiments for DiskANN on 10% of points from SIFT.
E.6 EXPERIMENTS ON DYNAMIC EXPLORATION GRAPHS (DEG)
We also provide preliminary comparisons to the deletion strategy used in the Dynamic Exploration Graph (DEG) data structure of Hezel et al. (202)). In DEG, the deletion of vertex is patched by building an independent BFS trees from each neighbor of v and adding an edge between two of these neighbors when their corresponding trees collide, until the total degree on the neighborhood is restored. Like in the previous section, we subsample 100k points from SIFT and monitor (i) recall, (ii) distance computations per query, (iii) deletion time, and (iv) graph size after repeatedly deleting 10K points.
Edies
D20
SEATCH
211 Lanc
C82
20
Staph 5e
Graph Detation
Graph Deleton
Graph Deletion
Figure 10: Experiments for DEG 10% of points from SIFT.
The results are shown in Figure 10
Note that DEG's deletion time is much slower than our method, SPATCH. the cost/accuracy trfde-off, SPatch and DEG perform very similarly, with DEG achieving slightly higher recall (within 2-3%) with slightly higher number of distance computations, rendering their cost/accuracy tradeoff comparable. The crucial difference is deletion time: the deletion time of DEG is up to 35x larger than SPatch, reflecting the inherent cost of DEG's global rebuild strategy compared to SPatch local updates. This gap makes DEG impractical when deletions are frequent or substantial, which is precisely the regime our method targets. While DEG achieves slightly higher recall than SPatch, its much slower deletion time makes it impractical for use in scenarios where deletions are plentiful.
LLM DISCLOSURE
This work does not use LLM to facilitate writing.
30


Reviews:
[{"review_id": "NjvD6AP5dq", "reviewer": "Reviewer_j4UT", "summary": "### Paper Summary\n\nThis paper addresses the critical update problem in graph-based ANN search, focusing on efficient deletion. The core contribution is a new deletion algorithm, SPatch, derived from random walk theory. The problem of removing a node is reformulated as preserving the random walk transition probabilities among the deleted node’s neighbors. Extensive experiments show that SPatch achieves a well-balanced trade-off across four key metrics: high recall, fast query speed, low deletion time, and memory efficiency.", "questions": "Please refer to the weakness and detailed comments.", "limitations": "", "rating": 4, "confidence": 3, "soundness": 3, "presentation": 2, "contribution": 3, "strengths": "### Paper Strengths\n\nS1. Efficient, high-recall dynamic deletion is one of the most significant unsolved challenges for graph-based ANN indexes in production. The paper’s motivation is strong and highly relevant.\n\nS2. The idea of modeling a graph’s greedy search as a “softmax walk” is clever, bridging a heuristic algorithm with formal random walk theory.\n\nS3. The paper includes comparisons against mainstream baselines and demonstrates competitive performance across recall, query speed, deletion time, and memory usage.", "weaknesses": "### Paper Weaknesses\n\nW1. The paper’s theoretical foundation is built on undirected graphs, whereas mainstream implementations use directed graphs, leaving a gap that the paper does not justify. (See D1, D2)\n\nW2. The algorithm does not clearly describe how it handles in-neighbors of a deleted node. (See D3)\n\nW3. The algorithm is only validated on HNSW, and its robustness on other graph indexes (e.g., NSG, DiskANN) is unknown. (See D4)\n\nW4. The algorithm section includes excessive theoretical formulas, making it difficult to follow. (See D5)\n\n### Detailed Comments\n\nD1. The theoretical foundation (including Laplacians, spectral graph theory, hitting times, and the star–mesh transform) is based on undirected graphs. However, most high-performance graph implementations employ directed graphs. The paper does not explain how the undirected theoretical framework applies to a directed implementation, which raises questions about its validity.\n\nD2. Following D1, the paper is ambiguous about whether the HNSW used in Section 5 is directed or undirected, which is crucial for correctly interpreting the results. For example, Figure 2 reports Deletion Time values near zero for SPatch, Local, and NoPatch, which is implausible for realistic directed graphs. This inconsistency suggests the experiments might have been conducted on an undirected structure, contradicting common high-performance settings.\n\nD3. The proposed method does not specify how in-neighbors of the deleted node are handled. Algorithm 1 and Section 5.1 only describe patching out-neighbors, which could leave dangling in-edges and harm graph navigability. Prior research has shown that proper in-neighbor management is essential for maintaining both performance and structural integrity [1]. This point should be clearly addressed.\n\nD4. The algorithm is evaluated only on HNSW. Its effectiveness and generality on other graph-based indexes (e.g., NSG, Vamana, or $\\tau$-MNG) remain to be demonstrated.\n\nD5. The algorithm description contains extensive theory and definitions but lacks clear procedural steps, illustrative figures, and simple examples. This makes it difficult for readers to grasp the main idea and follow the technical flow efficiently.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "CCuVstMJOj", "reviewer": "Reviewer_rt4u", "summary": "The paper studies the problem of deletions of base points in the context of Approximate Nearest Neighbor (ANN) search. It proposes a theoretically grounded procedure that efficiently updates the ANN data structure upon deletions. The proposed approach achieves better recall, along with good query performance, efficient deletion update time, and reasonable memory usage.\n\nConclusion: Although the results presented in the paper are interesting, there are lot of missing pieces. I am leaning in the middle, I don't mind either a accept or reject for this paper.", "questions": "1) You keep using the word \"twin formulation\", what does twin refers to?\n2) Theorem 4.3 implies a bound in Theorem 4.5, can you please also add some comments on what the bounds in Theorem 4.5 would look like if you had approximations in terms of spectral norms than the Forbenius norm in Theorem 4.3. Also, talk about the the sparsity bounds for the spectral norm from prior work.\n3)  Please explain beam search version of softmax clearly in your paper. I am assuming that, during search, at each hop, suppose you have your current list L of size t and you expand a node v in L. Then you look at L \\cup N(v) and sample top t edges based on their softmax probabilities? Also, what is the stopping criterion for the softmax search, that is, when will the search stop?\n4) In Table 2, though there is a recall drop, but the number of distance comparisons done by softmax walk is also lower. To have better clarity, for each dataset, can you create a plot with recall@10 numbers (y-axis) for different beam sizes (x-axis)? \n5) Also in Figure 2, can you generate different plots, where x-axis is distance comparisons and y-axis is recall@10? The number of distance comparisons can vary by varying the beam size.\n6) Clearly mention in the introduction itself when is your procedure good by looking at Figure 2. For instance, your procedure is good when deletion batch size is higher because of blah reason. It would be nice to add some conclusions drawn from experiments in the introduction itself.\n7) Handle weakness 3.", "limitations": "", "rating": 6, "confidence": 5, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "I see two main strengths in this paper:\n\nThe first is the novel perspective of interpreting the greedy walk through the lens of a softmax walk. This conceptual shift provides valuable intuition and a unifying view of the search process.\n\nBuilding on this softmax interpretation, the paper proposes a graph sparsification approach, where handling deletions efficiently naturally corresponds to sparsifying a complete weighted graph.\n\nThese viewpoints together lead to a practical and effective deletion procedure that performs well empirically.", "weaknesses": "1) I feel there is a little disconnect between theory and its relation to guarantees achieved by the ANN procedure. For instance, I would have loved to see a theorem statement of the kind, for any query q, if greedy walk on G achieves alpha approx or recall, then softmax walk also achieves same approx or recall with high prob. Also, greedy walk or softmax walk on sparsified G' also achieves similar approximation factors. \n\n2) Most of the theorem statements are simple. I am not so impressed with the proofs except this viewpoint of seeing greedy walk through the lens of softmax walk.\n\n3) Also the softmax walk was defined with respect to query point q, but SPatch algorithm uses distances between base points to sparsify the graph. There was no explanation given on why this is okay. I am aware that queries are not given to us, somehow an explanation is needed on why sparsifying graph based on distances between base points is okay. When inserting a base point v into the graph, usually these graphs are constructed assuming query is v itself, and this assumption is used to decide the incoming and outgoing edges of v. It would have been nice to see some explanation of SPatch algorithm with respect to this assumption of viewing base points as query points.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "fz0Aqk763g", "reviewer": "Reviewer_Z2rF", "summary": "The paper presents a theoretical framework for graph-based approximate nearest neighbor (ANN) search grounded in random walk analysis. Using this framework, the authors analyze a randomized deletion strategy that maintains hitting time statistics comparable to those of the original graph. They further leverage the theoretical insights to develop a deterministic deletion algorithm and experimentally compare it with other deletion algorithms.", "questions": "Please see the weaknesses and address the concerns mentioned there.", "limitations": "", "rating": 2, "confidence": 4, "soundness": 2, "presentation": 2, "contribution": 2, "strengths": "S1: Deletion is important operation for dynamic similarity graphs, and any related research is welcome. \n\nS2: The theoretical analysis of deletion in similarity graphs seems reasonable.", "weaknesses": "W1. A highly related work, DEG [a], is missing. In [a], the authors also proposed a similarity graph capable of handling all updates, including deletions. It is recommended that the proposed approach, Spatch, be compared with [a] thoroughly in terms of both design and performance.\n\nW2. The authors use rebuild as the baseline. However, a recently proposed approach [b] can rebuild the HNSW index much faster without impairing search performance. The authors are recommended to implement rebuild according to the method in [b] for the performance comparison.\n\nW3. Some explanations are confusing. On line 425, the authors claim that, compared with rebuild, the query speed of Spatch is much faster and memory usage decreases as more points are deleted. However, from the results in Fig. 2, in many cases Spatch requires more distance computations than rebuild. How should the statement that Spatch is faster be interpreted? Additionally, where are the experimental results on memory usage?\n\nW4. (Minor) I feel this paper is more suited to conferences on databases or data mining, where handling updates is a primary focus.\n\n[a] Dynamic exploration graph: a novel approach for efficient nearest neighbor search in evolving multimedia datasets. International Conference on Multimedia Modeling 2025.\n\n[b] Revisiting the Index Construction of Proximity Graph-Based Approximate Nearest Neighbor Search. VLDB 2024", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "dJRTTKghDS", "reviewer": "Reviewer_G68m", "summary": "This paper focuses on approximate nearest neighbor search problem. Based on the existing Hierarchical Navigable Small World (HNSW) data structure, this paper proposes SPatch, a novel random walk-based approach to support deletion of existing data. The experimental results on various datasets in massive deletion settings show the proposed method provides better tradeoff between query latency, recall, deletion time and memory usage.", "questions": "See weaknesses above.", "limitations": "", "rating": 8, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "1. This paper proposes a novel deletion algorithm for HNSW, a widely adopted data structure in vector search.\n2. This paper provides both theoretical and practical analyses on the proposed algorithm. \n3. The proposed algorithm achieves good tradeoff between four key metrics.", "weaknesses": "1. As mentioned in the paper, deletion procedure involves more complicated operations. I wonder if it is possible to provide time and space complexity analyses on the deletion algorithms. \n2. The experimental setting of this paper seems to be different from previous works, such as FreshDiskANN and SPFresh. They simulate the scenario for both insertion and deletion, which are more closed to the real world.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Decision: Accept (Poster)