Abstract
Vector search underpins modern AI applications by supporting approximate nearest neighbor (ANN) queries over high-dimensional embeddings in tasks like retrieval-augmented generation (RAG), recommendation systems, and multimodal search. Traditional ANN search indices (e.g., HNSW) are limited by memory constraints at large data scale. Disk-based indices such as DiskANN reduce memory overhead but rely on offline graph construction, resulting in costly and inefficient vector updates. The state-of-the-art clustering-based approach SPFresh offers better scalability but suffers from reduced recall due to coarse partitioning. Moreover, SPFresh employs in-place updates to maintain its index structure, limiting its efficiency in handling high-throughput insertions and deletions under dynamic workloads. This paper presents LSM-VEC, a disk-based dynamic vector index that integrates hierarchical graph indexing with LSM-tree storage. By distributing the proximity graph across multiple LSM-tree levels, LSM-VEC supports out-of-place vector updates. It enhances search efficiency via a sampling-based probabilistic search strategy with adaptive neighbor selection, and connectivity-aware graph reordering further reduces I/O without requiring global reconstruction. Experiments on billion-scale datasets demonstrate that LSM-VEC consistently outperforms existing disk-based ANN systems. It achieves higher recall, lower query and update latency, and reduces memory footprint by over 66.2%, making it well-suited for real-world large-scale vector search with dynamic updates.
Introduction
Vector search is the engine behind modern AI, powering everything from Retrieval-Augmented Generation (RAG) to recommendation systems. However, as datasets grow to the billion-scale, engineers face a "trilemma" of memory constraints, static rigidity, and accuracy loss. High-performance indices like HNSW are often too memory-intensive for large scales, while disk-based alternatives like DiskANN struggle with real-time updates, requiring slow global rebuilds. Fast-updating systems like SPFresh often sacrifice recall due to coarse clustering.
LSM-VEC addresses these challenges by building a system that is disk-resident, dynamic, and high-recall. It achieves this by combining hierarchical graph indices with Log-Structured Merge (LSM) trees, allowing for efficient, out-of-place updates on modern SSDs.
System Architecture and Methods
The core innovation of LSM-VEC is the integration of Hierarchical Navigable Small World (HNSW) graphs with LSM-tree storage structures. This architecture allows the system to maintain high performance while keeping the bulk of the data on disk.
LSM-based Graph Storage
Instead of a static file, LSM-VEC stores the proximity graph in an LSM-tree. The top layers of the graph—the "express lanes" for routing—stay in RAM, while the massive bottom layer is stored on disk as key-value pairs. This design enables the system to handle insertions and deletions as "out-of-place" updates, which are significantly faster on modern SSDs than traditional in-place edits. The authors observed that in a billion-scale HNSW graph, less than 1% of nodes reside in the upper layers, allowing for minimal memory overhead.
Search Optimization and Reordering
To maintain query efficiency, LSM-VEC employs two key strategies:
- Sampling-Guided Traversal: To avoid the high cost of reading every neighbor of a node from disk, LSM-VEC uses a probabilistic approach. It utilizes SimHash to filter out unlikely neighbor candidates in memory before performing disk I/O. Reducing the neighbor sampling ratio to 0.8 can cut query latency by 30% with minimal recall loss.
- Connectivity-Aware Reordering: Unlike systems that use static disk layouts, LSM-VEC tracks actual query patterns. During background LSM-tree compactions, it reorders vectors on disk so that nodes frequently traversed together are physically co-located, minimizing random I/O.
Experimental Evaluation
The authors evaluated LSM-VEC using the SIFT1B dataset, focusing primary experiments on a 100-million vector subset. LSM-VEC was compared against industry standards DiskANN and SPFresh across various workload scenarios.
Key Results
- Higher Recall: In balanced workloads, LSM-VEC achieved 88.4% recall, outperforming SPFresh (75.5%) and DiskANN (82.0%).
- Lower Latency: LSM-VEC was 1.2x faster at updates than SPFresh and 2.6x faster than DiskANN, maintaining stable query latency as data evolved.
- Memory Efficiency: The system reduced the memory footprint by over 66.2% compared to DiskANN, making it viable for budget-constrained environments.
- Robustness: In delete-heavy scenarios, LSM-VEC maintained a robust 77.4% recall, while DiskANN’s recall dropped to 61% due to graph fragmentation.
Conclusion and Future Work
LSM-VEC demonstrates that LSM-trees are an ideal fit for the high-frequency updates required by dynamic vector databases. By using query-driven locality and smart sampling, the system navigates billion-scale spaces with high accuracy and low overhead. Future work will explore hardware acceleration via GPUs or FPGAs and automated hyperparameter tuning to further enhance performance across diverse data distributions.
Summary updated