Source-linked AI summary
SPFresh: Incremental In-Place Update for Billion-Scale Vector Search
Yuming Xu, Hengyu Liang, Jin Li, Shuotao Xu, Qi Chen, Qianxi Zhang, Cheng Li, Ziyue Yang, Fan Yang, Yuqing Yang, Peng Cheng, Mao Yang
TL;DR
Continuous vector updates can skew index partitions, while periodic global rebuilding consumes substantial resources. SPFresh uses LIRE for incremental in-place rebalancing of nearby partitions. It reports 2.41× lower average tail latency than DiskANN with 10GB memory and 2 cores rather than 1000GB and 32 cores.
Problem
Continuous updates can skew cluster-based partitions and degrade search latency and accuracy, while global rebuilding is resource-intensive.
Source: §1 · pp. 1–2Method
SPFresh uses LIRE to split partitions and reassign a minimal set of nearby vectors for incremental in-place rebalancing.
Source: §1 · p. 2Results
2.41× lower tail latency on average than DiskANN, with SPFresh using 10GB memory and 2 cores versus 1000GB memory and 32 cores needed by DiskANN global rebuild.
Source: §1 · p. 2Takeaways & Limitations
SPFresh incorporates continuous updates with lower resource use than existing solutions while maintaining high search recalls.
Source: §6 · p. 14
Abstract
from arXiv · showhide
Approximate Nearest Neighbor Search (ANNS) is now widely used in various applications, ranging from information retrieval, question answering, and recommendation, to search for similar high-dimensional vectors. As the amount of vector data grows continuously, it becomes important to support updates to vector index, the enabling technique that allows for efficient and accurate ANNS on vectors. Because of the curse of high dimensionality, it is often costly to identify the right neighbors of a single new vector, a necessary process for index update. To amortize update costs, existing systems maintain a secondary index to accumulate updates, which are merged by the main index by global rebuilding the entire index periodically. However, this approach has high fluctuations of search latency and accuracy, not even to mention that it requires substantial resources and is extremely time-consuming for rebuilds. We introduce SPFresh, a system that supports in-place vector updates. At the heart of SPFresh is LIRE, a lightweight incremental rebalancing protocol to split vector partitions and reassign vectors in the nearby partitions to adapt to data distribution shift. LIRE achieves low-overhead vector updates by only reassigning vectors at the boundary between partitions, where in a high-quality vector index the amount of such vectors are deemed small. With LIRE, SPFresh provides superior query latency and accuracy to solutions based on global rebuild, with only 1% of DRAM and less than 10% cores needed at the peak compared to the state-of-the-art, in a billion scale vector index with 1% of daily vector update rate.
1 Introduction
Continuous vector updates can skew cluster-based indexes, degrading query latency and accuracy, while global rebuilding is resource-intensive. SPFresh uses LIRE for local in-place rebalancing, reporting better tail latency than DiskANN with far fewer resources.
1 Introduction
- Cluster-based indexes allow local insertions and removals, but accumulating updates skew partition sizes and hurt query latency and accuracy.The paper notes that graph-based indexes can require examining the graph to update edges, while cluster-based updates modify local partitions.Source: §1 · p. 2
- Periodic global rebuilding of accumulated updates consumes substantial resources and can hurt online search performance.The paper describes the secondary-index approach as LSM-style: it trades read performance for write optimization.Source: §1 · p. 2
- SPFresh is a disk-based vector index for lightweight incremental in-place updates; LIRE locally rebalances partitions to address distribution abnormalities without global rebuilding.LIRE is designed to maintain index quality on-the-fly.Source: §1 · p. 2
- LIRE relies on well-partitioned indexes: small updates are expected to affect a local region, making local rebalancing lightweight.The design rationale is that updates and their associated changes are most likely limited to the updated partition and its neighbors.Source: §1 · p. 2
- LIRE must balance partition sizes through timely splits and merges, identify a minimal set of vectors for reassignment, and avoid significant foreground-search impact.Its contributions include a two-stage feed-forward pipeline that moves background split-and-reassign work off the foreground-update critical path, plus an SSD-backed user-space storage engine.Source: §1 · p. 2
- 2.41× lower tail latency on average than DiskANN, with SPFresh using 10GB memory and 2 cores versus 1000GB memory and 32 cores needed by DiskANN global rebuild.SPFresh also reaches peak 4K QPS search and 2K QPS update throughput on a single NVMe SSD with 15 cores.Source: §1 · p. 2
2 Background and Related Work
This section introduces vector search and index designs, then explains why maintaining fresh updates in disk-based indexes remains challenging. It presents SPFresh's goal of avoiding global rebuilds through incremental in-place rebalancing.
2.1 Vector Search and ANNS
- Vector nearest neighbor search finds vectors closest to a query, while approximate search trades among resource cost, result quality, and latency for high-dimensional data.RecallK@K is described as a measure of approximate-result quality.Source: §2.1 · p. 3
2.2 Vector Index Organization
- Cluster-based indexes make updates local, but naive updates can eventually imbalance clusters and deteriorate search latency and accuracy.The section contrasts these with fine-grained graph indexes and describes on-disk graph methods including DiskANN and HM-ANN.Source: §2.2 · pp. 3–4
2.3 Freshness Demands and Challenges
- Global rebuilding of accumulated updates consumes resources and can hurt search performance; in-place approaches also need rebuilding to restore quality and stabilize latency.The section frames efficient fresh updates for disk-based vector indexes as an open challenge.Source: §2.3 · pp. 4–5
- Updating one-third of vectors in the SPANN-based in-place setting reduces recall by more than one point and raises tail latency by 4X versus static index building.The comparison uses a 2-million-vector static index and an in-place index with 0.5 million updates applied to a 1.5-million-vector base.Source: Figure 2 · p. 4, §2.3 · p. 5
2.4 Our Goals
- SPFresh adopts a coarse-grained cluster-based on-disk index and uses incremental in-place updates to adapt to distribution shift without global rebuilding.LIRE identifies a minimal amount of partition updates to maintain index properties and avoid visible accuracy loss.Source: §2.4 · p. 5
3 LIRE Protocol Design
SPFresh builds on SPANN’s disk-based clustered index and introduces LIRE to rebalance it locally as vectors change. LIRE uses split-triggered reassignment checks and a finite-convergence protocol to maintain nearest-posting assignment without global rebuilding.
3.1 SPANN: A Balanced Cluster-based Vector Index
- SPANN stores vector clusters as disk postings and uses an in-memory SPTAG index to navigate their centroids; balanced postings and boundary-vector replication support bounded latency and recall.This design motivates LIRE’s premise that an update to a well-balanced index may require changes only in a local region.Source: §3.1 · p. 5
3.2 LIRE: Lightweight Incremental RE-balancing
- LIRE splits oversized postings, merges undersized ones, and reassigns vectors in affected postings to restore nearest-posting assignment after partition changes.A split can make a neighboring posting the closer assignment for vectors in either the split postings or nearby postings; cascading splits may occur, but the process converges.Source: §3.2 · pp. 5–6
3.3 Reassigning Vectors
- LIRE checks split reassignment conditions for vectors in the old and nearby postings, then examines selected nearby postings and verifies candidates before moving them.The conditions rule out vectors that cannot require reassignment; limiting checks to nearby postings reduces the work compared with checking the whole dataset.Source: §3.3 · pp. 6–7
3.4 Split-Reassign Convergence
- Split-reassign terminates in finite steps because each split increases the centroid count by one while that count cannot exceed the number of vectors.The proof bounds the number of successive splits by the finite dataset size.Source: §3.4 · p. 7
4 SPFresh Design and Implementation
SPFresh separates in-place updates from background rebuilding and uses a block-oriented SSD controller for posting storage. Its design also provides concurrent local rebuilds and snapshot-plus-log crash recovery.
4.1 Overall Architecture
- SPFresh reuses SPANN’s searcher and centroid index, adding an In-place Updater, Local Rebuilder, and Block Controller to implement LIRE.The Updater appends vectors to postings, tracks versions and deletions, and queues a split when a posting exceeds its length limit.Source: §4.1 · pp. 7–8
4.2 Local Rebuilder Design
- A feed-forward pipeline moves split, merge, and reassignment jobs to a multithreaded Local Rebuilder, which performs local rebalancing outside the update critical path.Posting-level write locks make append, split, and merge changes atomic; reassignment checks are lock-free, and experiments report less than 1% write-lock contention.Source: §4.2 · p. 8, §4.2.2 · p. 8, §4.1 · p. 8
4.3 Block Controller Design
- The Block Controller uses raw SSD block interfaces and in-memory posting-to-block mapping for read-intensive storage operations.APPEND modifies only the last block of a posting, while the controller also supports parallel reads and bulk posting writes; its abstraction can generalize to read-intensive applications such as inverted indexes.Source: §4.3 · p. 9
4.4 Crash Recovery
- Crash recovery combines periodic snapshots of in-memory and on-disk index structures with a write-ahead log replayed from the latest snapshot.Block-level copy-on-write allows interim data changes to be rolled back, while delayed release of old blocks limits additional disk-space use.Source: §4.4 · pp. 9–10
5 Evaluation
The evaluation compares SPFresh with fresh-update baselines, tests billion-scale operation and data-distribution shifting, and studies parameter and resource configuration across SIFT and SPACEV workloads.
5.1 Experimental Setup
- The setup uses Azure lsv3 with 16 vCPUs and 128GB memory; Workloads A and B simulate 1% daily updates for 100 days, while Workload C tests billion-scale updates.The datasets are one-billion-vector SIFT1B and SPACEV1B; Workload A uses 100 million SPACEV vectors because DiskANN’s billion-scale fresh updates exceed the machine’s capacity.Source: §5.1 · p. 10
5.2 Real-World Update Simulation
- 2.41× lower P99.9 latency to DiskANN on average; SPFresh also expands its latency advantage over SPANN+ and achieves the best, most stable performance across metrics over 100 days.The real-world update simulation reports 1.5ms average insert latency and 5.30X lower memory usage than baselines; SPFresh stays under 20GB of memory.Source: §5.2 · p. 10, Figure 7 · p. 11, §5.2.2 · pp. 11–12
5.3 Billion-Scale Stress Test
- SPFresh saturates NVMe bandwidth with stable performance; accuracy stays above 0.862 on uniform data and 0.807 on skew data when searching the nearest 64 postings.As scale grows from 100 million to 1 billion, search latency remains stable apart from a slight initial P99.9 increase when split jobs begin.Source: Figure 9 · p. 13, §5.3.2 · p. 13
5.4 Data Distribution Shifting Micro-benchmark
- With in-place update plus split and reassignment, SPFresh is closest to Static; splitting lowers latency at the same accuracy, and reassignment lowers latency further.The comparison plots recall against latency under increasingly skewed data distributions.Source: Figure 10 · p. 13, §5.4 · p. 14
5.5 Parameter Study
- A reassign range of 64 postings is the default because accuracy gains from 64 to 128 are marginal; the foreground-to-background thread ratio is set to 2:1.The study reports that a single-threaded background Local Rebuilder keeps up with up to two foreground threads.Source: Figure 11 · p. 14, Figure 12 · p. 14, §5.5 · p. 14
6 Conclusion
SPFresh supports billion-scale in-place vector updates through LIRE, which rebalances postings while maintaining high search recalls. Its single-node performance provides a foundation for a future distributed version.
6 Conclusion
- SPFresh incorporates continuous updates faster and with significantly lower resources than existing solutions while maintaining high search recalls.The conclusion attributes this to LIRE’s minimal neighborhood-vector updates and decoupling of rebalancing from foreground queries.Source: §6 · p. 14
- LIRE splits overly large postings and reassigns vectors across neighboring postings when necessary.It identifies a minimal set of neighborhood vectors to adapt to data distribution shift.Source: §6 · p. 14
- Efficient concurrency control decouples rebalancing from foreground queries, avoiding operation interference.Source: §6 · p. 14
- SPFresh’s solid single-node performance builds a foundation for a future distributed version.Source: §6 · p. 14