Billion-scale vector search indices—the backbone of modern retrieval, recommendation, and question-answering systems—face a critical operational challenge that is rarely discussed in the literature on approximate nearest neighbor (ANN) algorithms: how do you update the index as vectors change? Products are added and removed from catalogs. User embeddings shift as behavior evolves. News articles and social media posts are continuously published. In every real production deployment, the vector corpus is not static—it is a living dataset that changes daily.
The standard approach used by most disk-based ANN systems is a two-tier architecture: a large, immutable main index built offline through expensive clustering, plus a small, mutable secondary (delta) index that absorbs new and updated vectors in real time. Queries are issued against both indices, and results are merged. Periodically—on the order of hours to days—the entire main index is rebuilt from scratch to absorb the accumulated deltas. This global rebuild is enormously expensive: it requires reading and re-clustering the entire dataset, consumes vast CPU and memory resources, and causes significant disruptions to query latency and recall during the rebuild window.
SPFresh, published at SOSP 2023 (the ACM Symposium on Operating Systems Principles—one of the most selective systems venues), introduces a fundamentally different approach. Rather than accumulating deltas and rebuilding, SPFresh proposes LIRE (Lightweight Incremental REbalancing), a protocol that performs in-place vector updates by reassigning only the vectors at partition boundaries. The key insight is that in a well-constructed partition-based index, the number of vectors that need to move between partitions after an update is small—typically a fraction of a percent of the total dataset. By exploiting this property, SPFresh maintains index quality continuously without ever performing a global rebuild, using only 1% of the DRAM and fewer than 10% of the CPU cores required by the state-of-the-art rebuild-based approach at peak.
This topic covers the SPFresh system in depth: the problem it solves, the LIRE protocol that makes in-place updates possible, and the practical implications for AI engineers building systems that serve vectors at scale.
To understand SPFresh, you first need to understand the architecture of disk-based ANN indices like SPANN and SPTAG (both from Microsoft Research). These systems partition the vector space using balanced clustering—typically a variant of k-means—and store each partition as a posting list on SSD. Each posting list contains the vectors assigned to that partition along with their IDs. A lightweight in-memory navigation structure (a graph or tree over the partition centroids) allows queries to quickly identify which partitions are likely to contain nearest neighbors.
At query time, the system identifies the top-k nearest centroids, reads the corresponding posting lists from SSD, and scans the vectors within them to find exact nearest neighbors. The quality of search results depends directly on the quality of the partitioning: vectors that are close in the embedding space should be assigned to the same partition (or to adjacent partitions), so that a query only needs to read a small number of posting lists to find all true nearest neighbors.
When vectors are inserted, deleted, or updated, the original partition boundaries become stale. New vectors may be assigned to partitions whose centroids are no longer representative. Deleted vectors leave gaps that waste I/O bandwidth when scanning posting lists. Over time, the partition quality degrades, requiring more posting lists to be read per query (increasing latency) and returning worse recall. This is the fundamental tension: the index must be reorganized to reflect the current data distribution, but reorganization is expensive.
The conventional solution, used by systems like Milvus and early versions of SPTAG, works as follows:
This approach has three serious problems:
SPFresh rejects the two-tier architecture entirely. Instead of maintaining a separate delta index, it modifies the main index directly—in place—as updates arrive. The challenge is doing this without degrading index quality or requiring a full re-clustering. The LIRE protocol achieves this by observing that most updates only affect vectors near partition boundaries: the vast majority of vectors in the interior of a partition are unaffected by the insertion or deletion of a few vectors at the margins.
LIRE is the core contribution of SPFresh. It is a protocol for maintaining partition quality through local, incremental adjustments rather than global re-clustering. LIRE operates on three principles:
“In a high-quality vector index, the amount of boundary vectors is deemed small.” This is the central observation that makes LIRE practical. In a well-partitioned index at billion scale, a vector update triggers reassignment of at most a handful of boundary vectors—not thousands or millions. The cost of an in-place update is therefore proportional to the number of affected boundary vectors, not the total dataset size.
A subtlety that SPFresh addresses explicitly is distribution shift. In many real-world applications, the statistical distribution of vectors changes over time. For example, in a news retrieval system, the topics being discussed shift daily. In a recommendation system, user interests drift seasonally. A static partition layout computed on last month’s data may be a poor fit for this month’s vectors. LIRE’s continuous rebalancing naturally adapts to distribution shift: as new vectors arrive in previously sparse regions of the embedding space, partitions in those regions split and grow, while partitions in depopulated regions shrink. This adaptation happens incrementally, without any explicit drift detection mechanism.
SPFresh builds on top of the SPANN (Scalable Partition-based ANN) index architecture. In SPANN, the vector space is partitioned into N clusters using balanced k-means clustering. Each cluster is represented by a centroid vector stored in memory, and the cluster’s member vectors are stored as a posting list on SSD. The in-memory centroid index is a small graph (typically a navigable small world graph) that enables fast centroid lookup.
A query proceeds in two phases:
The quality of the partitioning directly determines recall: if the true nearest neighbors are scattered across many partitions, the system must read more posting lists (higher p) to achieve high recall, which increases latency and I/O cost.
When a batch of vector updates arrives (insertions, deletions, and modifications), LIRE processes them through the following steps:
For each updated vector, LIRE determines which partition it belongs to (for deletions and modifications) and which partition it should be assigned to (for insertions and modifications). This is done by querying the centroid index. A modification is treated as a deletion of the old vector followed by an insertion of the new vector.
Insertions are appended to the appropriate posting list. Deletions are marked in the posting list (and optionally compacted). These operations are straightforward and do not affect partition boundaries.
After the direct changes, LIRE checks whether any vectors in the affected partitions should be reassigned to a neighboring partition. For each vector v in an affected partition with centroid c, LIRE computes the distance from v to c and to the centroids of neighboring partitions. If v is closer to a neighbor’s centroid than to its own, it is a boundary vector and is reassigned: removed from its current posting list and appended to the neighbor’s posting list.
The crucial optimization is that LIRE does not check every vector in the affected partitions. It only checks vectors whose distance to their centroid exceeds a threshold (i.e., vectors near the partition boundary). This threshold is derived from the partition radius and the distance between the partition centroid and its nearest neighbor centroids.
If a partition’s posting list grows beyond a size threshold T (typically 2x the target partition size), LIRE splits it. The split is performed using a local 2-means clustering: the vectors in the oversized partition are divided into two clusters, each with its own centroid. The two new centroids replace the old centroid in the in-memory navigation graph. This is a local operation that touches only one posting list and a few graph edges, not the entire index.
After reassignment and splitting, the centroids of all affected partitions are recomputed as the mean of their current member vectors. The in-memory centroid graph is updated accordingly.
procedure LIRE_UPDATE(index, update_batch):
// Phase 1: Direct application
for each (vector_id, operation, vector) in update_batch:
if operation == INSERT:
partition = find_nearest_centroid(index, vector)
append_to_posting_list(partition, vector_id, vector)
elif operation == DELETE:
partition = lookup_partition(index, vector_id)
mark_deleted(partition, vector_id)
elif operation == MODIFY:
old_partition = lookup_partition(index, vector_id)
mark_deleted(old_partition, vector_id)
new_partition = find_nearest_centroid(index, vector)
append_to_posting_list(new_partition, vector_id, vector)
// Phase 2: Collect affected partitions
affected = set of all partitions touched in Phase 1
// Phase 3: Boundary reassignment
for each partition P in affected:
centroid_P = get_centroid(P)
neighbors = get_neighbor_centroids(index, P)
for each vector v in P:
dist_own = distance(v, centroid_P)
for each neighbor_centroid C_n in neighbors:
if distance(v, C_n) < dist_own:
// v is a boundary vector -- reassign
remove_from_posting_list(P, v)
append_to_posting_list(partition_of(C_n), v)
add partition_of(C_n) to affected
break
// Phase 4: Partition splitting
for each partition P in affected:
if size(P) > SPLIT_THRESHOLD:
(P1, P2) = local_2means_split(P)
replace_in_centroid_graph(index, P, P1, P2)
// Phase 5: Centroid update
for each partition P in affected:
recompute_centroid(P)
update_centroid_graph(index, P)A critical aspect of SPFresh’s design is that LIRE updates are performed concurrently with query serving. The system uses a versioned posting list structure where readers (queries) and writers (LIRE) operate on different versions. When a posting list is being modified, queries continue to read the previous version. Once the modification is complete, the version pointer is atomically switched. This ensures that queries never see a partially-updated posting list and never block on writes.
The paper demonstrates that this concurrent design maintains stable query latency even during heavy update workloads. Unlike the rebuild-based approach, where query latency spikes during the rebuild window, SPFresh’s query latency remains flat because LIRE operations are lightweight and localized.
Since posting lists are stored on SSD, LIRE must minimize the number of SSD read/write operations. The system batches boundary reassignment operations: rather than writing to SSD after each individual vector move, it accumulates changes in memory and flushes them in bulk. Posting lists are stored in a log-structured format that makes appends efficient and supports periodic compaction to reclaim space from deleted vectors.
The paper reports that SPFresh’s I/O overhead is modest: at a 1% daily update rate on a billion-vector index, the additional SSD writes from LIRE are a small fraction of the baseline query I/O. This is in sharp contrast to a global rebuild, which must read and rewrite the entire index (potentially terabytes of data).
E-commerce and content recommendation systems maintain embedding indices over catalogs of millions to billions of items. Products are added and removed daily—seasonal inventory changes, new product launches, and discontinued items. User embeddings also shift as browsing and purchase behavior evolves. SPFresh’s in-place update model allows the recommendation index to reflect these changes within minutes rather than waiting for a nightly or weekly rebuild. This means a newly listed product can appear in recommendations almost immediately, and a recalled product can be removed without waiting for the next rebuild cycle.
Large marketplace platforms (with tens of millions of product listings that change daily) are a natural fit for SPFresh. Price changes, description updates, and new seller listings all produce updated embeddings. With a rebuild-based approach, the index is always slightly stale—reflecting the state of the catalog at the time of the last rebuild. With SPFresh, the index tracks the current state of the catalog continuously, eliminating the staleness window entirely.
News retrieval systems must index articles that are published continuously throughout the day. The relevance of articles decays rapidly—a breaking news story is highly relevant for hours but much less so after a few days. Social media platforms face similar dynamics with posts, comments, and user-generated content. SPFresh enables these systems to continuously insert new content embeddings and remove or down-weight stale content without the periodic disruption of a rebuild.
Retrieval-Augmented Generation (RAG) pipelines depend on a vector index over a document corpus. When the corpus is updated—new documents added, old documents revised or retracted—the vector index must reflect these changes for the RAG system to provide accurate, up-to-date answers. SPFresh’s approach is particularly valuable here because RAG systems are sensitive to index staleness: retrieving outdated or deleted documents can lead to hallucinated or incorrect responses.
Systems that maintain per-user memory as embeddings (recording past conversations, preferences, and context) generate continuous updates as users interact. The embedding for a user’s interests today may differ substantially from a month ago. SPFresh allows these user-memory indices to be updated in real time without the operational burden of periodic rebuilds.
SPFresh is designed as a layer on top of the SPANN partition-based index. The integration points are:
In production, SPFresh operates as a continuous update loop that processes batches of vector updates while serving queries concurrently:
// Production update loop for SPFresh-style index management
class SPFreshUpdateLoop:
def __init__(self, index, batch_size=1000, interval_ms=100):
self.index = index
self.batch_size = batch_size
self.interval_ms = interval_ms
self.update_queue = ConcurrentQueue()
self.running = True
def enqueue_update(self, vector_id, operation, vector=None):
"""Called by upstream systems when vectors change."""
self.update_queue.put((vector_id, operation, vector))
def run(self):
"""Main update loop -- runs in a dedicated thread pool."""
while self.running:
batch = self.update_queue.drain(max=self.batch_size,
timeout_ms=self.interval_ms)
if not batch:
continue
# Phase 1: Apply direct changes (insert/delete/modify)
affected_partitions = set()
for vector_id, operation, vector in batch:
partitions = self.index.apply_update(
vector_id, operation, vector
)
affected_partitions.update(partitions)
# Phase 2: LIRE boundary reassignment
newly_affected = self.index.reassign_boundaries(
affected_partitions
)
affected_partitions.update(newly_affected)
# Phase 3: Split oversized partitions
for partition_id in list(affected_partitions):
if self.index.partition_size(partition_id) > SPLIT_THRESHOLD:
new_partitions = self.index.split_partition(partition_id)
affected_partitions.update(new_partitions)
# Phase 4: Recompute centroids and update graph
self.index.update_centroids(affected_partitions)
# Phase 5: Version bump -- atomically expose changes to queries
self.index.commit_version()
# Metrics
log_metrics(
batch_size=len(batch),
partitions_touched=len(affected_partitions),
queue_depth=self.update_queue.size()
)The batch size and update interval are critical tuning parameters. Smaller batches provide fresher results but increase per-update overhead (each LIRE invocation has fixed costs for centroid lookups and posting list I/O). Larger batches amortize this overhead but increase the staleness window. The paper evaluates batch sizes from 100 to 10,000 vectors and finds that the system is robust across this range, with minimal impact on recall or latency.
A practical starting point for a billion-scale index with a 1% daily update rate (~10 million updates per day) is:
When operating an SPFresh-style index, the following metrics are essential for detecting partition quality degradation:
The most striking result from the SPFresh paper is the resource comparison with the state-of-the-art rebuild-based approach. At peak load on a billion-vector index with 1% daily updates:
Under the rebuild-based approach, recall follows a sawtooth pattern: it is highest immediately after a rebuild and degrades steadily as the delta index grows and the main index becomes stale. The paper shows that at 1% daily update rate, recall can drop by several percentage points between rebuilds.
SPFresh maintains stable recall over time because LIRE continuously adjusts partition boundaries. The paper reports that SPFresh’s recall remains within 1% of the recall achieved by a freshly-built index, even after sustained update workloads. This is a significant operational advantage: the system’s search quality is predictable and does not depend on the rebuild schedule.
SPFresh is explicitly designed and evaluated for a 1% daily vector update rate at billion scale. This translates to roughly 10 million vector operations per day on a 1-billion-vector index. The paper’s experiments show that LIRE handles this rate comfortably with minimal resource overhead.
At higher update rates (e.g., 5–10% daily), the boundary reassignment and splitting costs increase, and the system may begin to show degraded performance. The paper does not claim that SPFresh eliminates the need for rebuilds entirely under all workloads—rather, it pushes the threshold at which rebuilds become necessary much higher, and for the common case of streaming updates at 1% daily churn, it eliminates rebuilds entirely.
SPFresh was published at the 29th ACM Symposium on Operating Systems Principles (SOSP 2023), one of the most prestigious and selective venues in computer science. SOSP acceptance rates are typically 15–18%, and the venue is known for publishing systems work with rigorous experimental evaluation. The paper’s results were evaluated on billion-scale datasets with real-world update workloads, lending significant credibility to the claims.
The following table summarizes the key differences between the rebuild-based approach and SPFresh:
Metric | Rebuild-Based | SPFresh (LIRE)
--------------------------|----------------------|---------------------------
Update mechanism | Delta index + rebuild| In-place boundary reassign
Peak DRAM usage | ~100% of index size | ~1% of index size
Peak CPU cores | 100% | <10%
Query latency during ops | 2-5x spikes | Stable (flat)
Recall over time | Sawtooth pattern | Stable within 1% of fresh
Rebuild frequency | Hours to days | Never (continuous LIRE)
Designed update rate | Any (rebuilds scale) | ~1% daily churn optimal
Cold-start requirement | None (always rebuild)| Well-partitioned initial index