LSM-Vec: A Memory-Efficient Disk-Based System for Large-Scale Dynamic Vector Search

Abstract

RAG and AI retrieval have made vector approximate nearest-neighbor (ANN) search a key retrieval operation in modern data systems. These workloads are both large and dynamic. Vector collections grow until index state no longer fits in DRAM and must reside on disk, and every new record arrives as an update the index must absorb while queries continue to run. Existing dynamic designs on disk leave two architecture-level gaps. First, graph connections and vector data follow different access and update paths, yet many disk-based indexes store them as one physical record, so a graph-only update rewrites vector data it does not modify. Second, keeping an index fresh gives memory a role beyond caching, because these systems either hold recent updates in in-memory indexes or reserve memory to maintain a mutable disk layout. We present LSM-Vec, a disk-based dynamic vector search system built on a decoupled architecture. LSM-Vec stores the HNSW base layer in a graph-oriented LSM-tree that absorbs fine-grained edge changes out of place, and keeps vector data in a separate paged store. To keep this design query-efficient within a small memory budget, we design in-memory tree-based sketches that route each query to an entry close to its target on disk, so the resident hierarchy stays compact. We further introduce HNSW-based reordering, which places vector data that queries evaluate together on nearby disk pages and reduces scattered reads. On streaming SIFT and SPACEV workloads with up to a hundred million vectors, LSM-Vec requires up to 6.2$\times$ less memory and 7.6$\times$ less disk than FreshDiskANN and SPFresh, and writes up to 15$\times$ fewer bytes per insertion. At the hundred-million scale, where SPFresh's index outgrows memory and FreshDiskANN exhausts it, LSM-Vec keeps its tail latency stable throughout the update stream, 2.3--3.8$\times$ below SPFresh's at comparable recall.

arXiv comment12 pages, 14 figures