ETALE: Evolving Topology with Accelerated Lock-free Execution for Dynamic Graph ANN Search on GPUs

Jul 16, 2026

Upload by Aurora

Graph-based approximate nearest neighbor (ANN) indexes on GPUs are typically designed for static datasets, forcing costly window rebuilds when insertions and deletions arrive, while incremental dynamic-graph indexes often run on the CPU and miss GPU parallelism. ETALE (Evolving Topology with Accelerated Lock-free Execution) introduces a GPU-native graph ANN index enabling streaming insertion and deletion without global rebuild. ETALE uses a lock-free copy-on-write slab graph with atomic deletion-state sharing, providing deletion-monotonicity and bounded GPU-memory reclaim; CUDA evaluation shows sublinear memory growth and millisecond-scale maintenance with high recall.

LanguageEnglish

CategoryResearch & Report

FormatPDF

Pages14

Reading Time35 min

Introduction

GPU-native graph ANN challenge

Proposed solution: ETALE

Evaluation setup and results

ETALE: Evolving Topology with Accelerated Lock-free Execution for Dynamic Graph ANN Search on GPUs Dongfang Zhao Tacoma School of Engineering and Technology University of Washington [dzhao@uw.edu](dzhao@uw.edu) arXiv :2607 .02543v1 [ cs .DC] 24 Jun 2026 Abstract Graph-based approximate nearest neighbor (ANN) indexes on the GPU are originally built for static collections and must reconstruct the affected window to absorb any update, while the dynamic graph indexes that update incrementally run on the CPU and cannot exploit GPU parallelism. This paper presents a new ANN index, namely ETALE (Evolving Topology with Accelerated Lock-free Execution), which is among the first GPU-native graph ANN indexes to support streaming insertion and deletion without a global rebuild. The core of ETALE is a lock-free copy-on-write slab graph whose deletion state and adjacency share a single atomically published word, which yields a provable deletion-monotonicity invariant together with a bounded reclaim of GPU memory that is sublinear in accumulated deletions. We have implemented ETALE in CUDA and evaluate it on five diverse multimodal datasets against four state-of-the-art indexes: Tagore (GPU static, SIGMOD’26), DIGRA (CPU dynamic, SIGMOD’26), CAGRA (GPU static, ICDE’24), and HNSW (CPU dynamic, TPAMI’20). Under continuous churn, ETALE maintains the index in hundreds of milliseconds per round at recall above 0. 95, which is 4.8–8. 8× faster than CAGRA’s per-window rebuild, 1.8–2. 5× faster than the more recent Tagore, and 3. 3–147× faster than the CPU dynamic indexes. In addition, the memory footprint of ETALE stays bounded where tombstone-only systems grow indefinitely. Keywords Approximate nearest neighbor search, vector database, GPU, dynamic graph index, lock-free data structure 1 Introduction Approximate nearest neighbor search (ANNS) over embedding vectors is a core primitive behind many application domains, such as recommendation systems [50] and retrieval-augmented generation (RAG) [20] . Across these settings, graph-based indexes such as HNSW [26], NSG [10], and DiskANN [17] deliver the desired accuracy-latency trade-off and have become a popular choice in production vector stores [42] . The embedding models that produce these vectors already run on GPUs, which gives a strong incentive to keep the index on the GPU as well. A GPU-resident index sits next to the model that generates the vectors, which removes the host transfer that a CPU index pays on every batch and places graph search and construction on the same parallel hardware. However, keeping a graph index on the GPU and ensuring it up to date are in tension. Because a live corpus adds and removes documents continuously, an index that serves it must absorb that stream of insertions and deletions or fall out of date. The dominant GPU graph indexes cannot: they are built for static collections. ma intenance ms / window (log) 2 × 103 103 6 × 102 4 × 102 3 × 102 2 × 102 Maintenance cost under 1% churn 1 2 3 4 5 churn round Recall@10 1.00 0.99 0.98 0.97 0.96 0.95 Figure 1: Maintenance under 1% churn on SIFT. Left: ETALE maintains the index incrementally at about 250 ms per round, 7. 1× cheaper than CAGRA’s per-round rebuild. Right: the saving holds at quality parity, with Recall@10 of the two systems coinciding within a few thousandths across rounds. CAGRA [32], the state-of-the-art GPU index, fixes every node’s neighbor list in a single batch-oriented construction pass, so it has no incremental update path and absorbs a change only by rebuilding the affected window from scratch. The indexes that do update incrementally sit on the other hardware: FreshDiskANN [37], SPFresh [47], and DIGRA [18] show that streaming insertion and deletion are practical, yet each maintains its graph on the RAM or SSD with CPUs and leaves the GPU’s parallelism unused. The cost of resolving the tension by rebuilding is large. On SIFT under a 1% chu

FAQs

What problem does ETALE address in GPU-based dynamic graph ANN search?

GPU graph ANN indexes are usually static and require rebuilding affected windows after updates, while CPU-based dynamic indexes cannot exploit GPU parallelism. ETALE targets this mismatch by supporting streaming insertion and deletion on the GPU without a global rebuild.

How does ETALE ensure safe deletion during concurrent GPU execution?

ETALE is built around a lock-free copy-on-write slab graph where deletion state and adjacency are coordinated through a single atomically published word. This enables a provable deletion-monotonicity invariant and controlled GPU memory reclamation.

How does ETALE perform compared with state-of-the-art GPU and CPU indexes?

On five multimodal datasets under continuous churn, ETALE maintains the index in hundreds of milliseconds per round while keeping recall above 0.95. It is reported as 4.8–8.8× faster than CAGRA’s per-window rebuild, 1.8–2.5× faster than Tagore, and substantially faster than CPU dynamic indexes, with bounded memory growth unlike tombstone-only systems.

Jul 16, 2026

Upload by Aurora