NAVIS : Concurrent Search and Update with Low Position-Seeking Overhead in On-SSD Graph-Based Vector Search

Jaeyong Song, Hongsun Jang, Changmin Shin, Seongyeon Park, Yong Jae Ryoo, Seo Jin Park, Jinho Lee · 2026

Read NAVIS : Concurrent Search and Update with Low Position-Seeking Overhead in On-SSD Graph-Based Vector Search by Jaeyong Song, Hongsun Jang, Changmin Shin, Seongyeon Park, Yong Jae Ryoo, Seo Jin Park, Jinho Lee (2026) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2605-11523.txt.

Introduction

Song and colleagues present NAVIS, an on-SSD graph search system that cuts position-seeking overhead for search. On-disk graph search dominates databases, but updates must traverse the graph to find neighbours before linking. That cost grows through packed layouts coupling edge fetches to full vector loads, and through static entrance graphs drifting from inserted regions. NAVIS answers with vector reads and an entrance graph updated from concurrent traversals. It adds an edge-list cache. Insertion throughput rises up to 2 point 74 times and search throughput up to 1 point 37 times.

Catalog record

CREATORJaeyong Song, Hongsun Jang, Changmin Shin, Seongyeon Park, Yong Jae Ryoo, Seo Jin Park, Jinho Lee
YEAR2026
COLLECTIONPAPERS
FORMATTXT
FILE SIZE66538
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2605.11523

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

NAVIS : Concurrent Search and Update with Low Position-Seeking Overhead in On-SSD Graph-Based Vector Search Jaeyong Song, Hongsun Jang, Changmin Shin, Seongyeon Park, Yong Jae Ryoo, Seo Jin Park, Jinho Lee Abstract . On-disk graph-based vector search (GVS) has become the dominant approach for serving large-scale vector databases at high recall, but prior systems struggle to sustain concurrent search and update throughput on high-dimensional workloads. We find the main cause of this in position seeking , a full graph traversal that every update performs to locate neighbors before linking the new vector into the graph. Position seeking is fundamentally heavier than a search query, and its cost is further amplified by two systemic limitations of current GVS systems, packed layouts that couple every edge fetch to a full vector load, and a static entrance graph whose entry points drift away from newly inserted regions as updates accumulate. We present NAVIS , an on-SSD GVS system that drives down position-seeking overhead through (i) a layout-supported selective vector read that breaks the packed-page coupling without losing its locality benefits, (ii) a dynamic lightweight entrance graph update mechanism that reuses traversal information already produced by concurrent updates, and (iii) an entrance graph-aware edgelist cache that concentrates capacity on high-reuse paths near refreshed entry points. Across multiple large-scale high-dimensional benchmarks, NAVIS enhances average insertion throughput by up to 2.74 × \times and average concurrent search throughput by up to 1.37 × \times while reducing average search latency by up to 25.26%. † † authors: . PVLDB Reference Format: PVLDB, 20(X): XXX-XXX, 2027. doi:XX.XX/XXX.XX † † This work is licensed under the Creative Commons BY-NC-ND 4.0 International License. Visit https://creativecommons.org/licenses/by-nc-nd/4.0/ to view a copy of this license. For any use beyond those covered by this license, obtain permission by emailing [email protected] . Copyright is held by the owner/author(s). Publication rights licensed to the VLDB Endowment. Proceedings of the VLDB Endowment, Vol. 20, No. X ISSN 2150-8097. doi:XX.XX/XXX.XX 1. Introduction Modern applications like retrieval-augmented generation ( 33 ) , recommendation systems ( 25 ; 35 ) , and multimedia search ( 63 ; 24 ) increasingly rely on large-scale vector databases to retrieve semantically similar items at high recall. Among various designs, on-disk graph-based vector search (GVS) ( 50 ; 54 ; 19 ; 49 ; 20 ; 45 ) has emerged as the dominant approach for high-recall search at scale. In on-disk GVS, vectors are vertices in a proximity graph whose edges link nearby points. Queries are answered via greedy traversal that hops from a starting vertex toward progressively closer neighbors, loading only the visited portions of the graph index from SSD on demand. Recent production deployments ( 45 ; 11 ) increasingly adopt on-disk GVS because it sustains high recall without holding full vectors in DRAM ( 17 ; 34 ) , especially for high-dimensional vectors from encoders such as CLIP ( 47 ) , OpenAI’s embedding models ( 42 ; 43 ) , and BGE-M3 ( 5 ) , with dimensionalities ranging from 512 to 3072. With the rise of agentic systems ( 22 ; 30 ) , and as production pipelines ( 10 ; 13 ; 17 ) now ingest fresh user activity and frequent uploads, the on-disk GVS systems are no longer static snapshots. There are two methods to handle such vector updates, index rebuild and index update . Since index rebuild often takes several days for large-scale datasets ( 50 ) , it often fails to provide up-to-date search results. Thus, many approaches ( 49 ; 20 ; 55 ; 57 ) focus on index update to quickly incorporate fresh vectors into databases. However, sustaining high search performance under such concurrent index updates is non-trivial. Prior index update methods in on-disk GVS systems take two main approaches. One approach ( 49 ; 57 ) temporarily buffers new updates in memory and merges them into the on-disk graph in bulk, which amortizes per-insertion I/O across many entries. However, this batched merge causes severe fluctuations in search performance during each merging window ( 55 ; 20 ) . To stabilize search performance while concurrently absorbing insertions, a second line of work ( 55 ; 20 ) adopts in-place updates that commit every update directly on disk as it arrives, avoiding the search latency spikes. Although both lines of work make meaningful progress on update support in on-disk GVS, neither sustains the high concurrent search and update throughput that modern high-dimensional workloads demand. We find the main cause of this in position seeking , a graph traversal that every update performs to locate neighbors before linking the new vector into the graph. Compared to a typical search, position seeking for updates is fundamentally heavier and demands far more I/O. A search query terminates once it collects a handful of adjacent neighbors because it only needs the top- K (e.g., 10) similar vectors. By contrast, an update must match the new vertex’s degree to the graph’s maximum out-degree (e.g., 64–96) to preserve graph quality, which incurs sizable vector and neighbor list loads from the SSD, especially in high-dimensional vector databases. We identify three systemic reasons why existing approaches fail to address this position-seeking overhead on high-dimensional vector databases as follows. (1) Packed layouts force unnecessary vector I/O. State-of-the-art systems co-locate vectors and neighbor lists on the same SSD page (called packed layout) to exploit search locality ( 54 ) and piggyback vector I/O onto edgelist I/O ( 20 ; 49 ) . While efficient for the final ‘convergence’ phase of position seeking, this layout forces the system to load heavy vectors even during the early ‘approach’ phase, when only the edge list should be loaded for graph traversal. More fundamentally, position seeking only needs to find an adequate set of neighbors for connection, not to rank every visited vertex exactly, so much of the loaded vector data never affects which neighbors are chosen. In addition, this packed layout is inefficient for structural updates because it forces the rewriting of the entire neighbor vectors, even when only the edgelists are changed. (2) Static entrance graph stalls navigation. Many GVS systems utilize an in-memory entrance graph ( 54 ; 19 ) , a small sampled (typically 1%) version of the proximity graph that seeds each traversal with well-placed entry points to collapse the graph traversal hops, thereby reducing storage I/O. However, existing update systems either omit the entrance graph entirely or freeze it after construction ( 20 ; 57 ) , because concurrent maintenance has its own overhead. A frozen entrance graph is highly likely to drift away from newly inserted regions as insertions accumulate, so traversal entrance points land far from their targets and pull more pages from SSD, diminishing its benefits. (3) Cacheable entrance graph locality goes unexploited. Caching hot edgelists near entrance graph entries in host memory is a promising direction. However, the packed layout forces to pin vector bytes into every cached page, even though those bytes are only consulted in the final convergence phase, wasting capacity that could hold more edgelists. Worse, a stale entrance graph scatters traversals across the graph, so the cache cannot concentrate on a stable hot set near the entry points. To this end, we present NAVIS

Read the complete text