Stale Vector Index

partial

Summary

An HNSW or IVF vector index built on a corpus grows increasingly inaccurate as new vectors are inserted and the index is not rebuilt: because HNSW's greedy graph construction assumes a representative distribution during build time, and IVF's cluster centroids become stale: degrading recall for queries about recently added content.

Description

Approximate Nearest Neighbor (ANN) indexes are built on a static or slowly-changing corpus. Their internal structures (HNSW's navigable graph layers, IVF's cluster centroids) are optimized for the vector distribution at build time.

As new vectors are inserted incrementally:

HNSW: new nodes are added to the graph using the existing structure. If the new vectors represent a substantially different distribution (new document topics, new product categories), the greedy graph traversal may not navigate to them efficiently. The recall for queries in the new distribution space degrades.

IVF: cluster centroids are computed at index build time using K-means on the full corpus. Incremental inserts are assigned to the nearest existing centroid. If many new vectors fall between existing centroids (a new topic cluster), they are split across neighboring clusters with no accurate representation. Recall for this new cluster decreases as the centroid placement becomes a poor match.

PQ (Product Quantization): codebooks computed at build time. New vectors quantized to outdated codebooks have higher quantization error: distance computations become less accurate.

The effect is gradual and hard to detect: queries return results, but the result quality degrades over time. Near-misses: semantically close vectors that should be returned but aren't: increase as the index ages.

Mitigation requires periodic full index rebuilds (expensive but restores accuracy) or incremental index refresh strategies (supported by some systems like Milvus).

Characteristics

Propagationisolated

Time to detectWithout retrieval quality benchmarks, stale index degradation can persist for months undetected. Detection requires periodic evaluation of recall@K against a labeled test set that includes recent documents. A decline in recall from 95% to 85% is not visible in error rate or latency metrics: only in retrieval quality metrics.

Blast radiusDegraded recall for queries about recently added or underrepresented content. Queries about well-represented original content continue to perform well. The degradation is proportional to the fraction of the corpus that is "new" relative to the build-time distribution.

Triggers

·Continuous vector insertion without index rebuilds over weeks or months
·Addition of content from a substantially new domain not represented in the original corpus
·Corpus composition changes significantly (e.g., 50% of old vectors deleted, new categories added)

Detection Signals

alert

Mitigation Strategies

Scheduled full index rebuildcomplexity: medium

Rebuild the vector index from scratch on a regular schedule (weekly or monthly depending on corpus change rate). Building from the full current corpus produces optimal graph structure and centroid placement. Requires offline rebuild with atomic swap to the new index (similar to index rotation for inverted indexes).

Continuous recall quality monitoringcomplexity: medium

Maintain a labeled test set of (query, relevant_document) pairs. Run recall@K evaluation against this test set daily. Alert when recall drops below a threshold (e.g., recall@10 < 90%). Detects degradation before users notice.

Use a vector database with incremental indexingpreventscomplexity: high

Managed vector databases (Pinecone, Weaviate, Milvus) handle incremental index updates internally, rebuilding or merging index segments without requiring application-level scheduling. Offloads the maintenance problem.

Recovery Steps

1.Measure current recall@K using the labeled test set to quantify degradation
2.Trigger a full index rebuild during off-peak hours
3.After rebuild, re-measure recall@K to confirm improvement
4.Implement a scheduled rebuild cadence based on corpus change rate
5.Add recall@K to regular production monitoring

Estimated recovery time: Full index rebuild duration: minutes (small corpus, <1M vectors) to hours (large corpus, 100M+ vectors) depending on corpus size and compute available. Quality improvement is immediate upon swap to the rebuilt index.

Affected Systems

Patterns

vector similarity searchmaterialized view

Technologies

postgresqlelasticsearch

Basis

HNSW and IVF index degradation under incremental inserts is described in the original HNSW paper (Malkov & Yashunin 2018), FAISS documentation, and pgvector GitHub discussions; the mitigation strategies are documented in Pinecone and Weaviate operational guides

Run This Failure

Blast radius analysis for this failure mode within each scenario that carries it.

ML Feature Serving Platform →

Related Architecture Knowledge

Inbound: affects this entity

Introduces RiskTechnology

qdrant

Grounded

Qdrant's HNSW index is built on the corpus at collection creation time; incremental inserts are added to the index graph, but recall degrades as the index diverges from the current distribution without periodic rebuilds.

Full relationship →

Used In Architecture Scenarios

ML Feature Serving Platformexpert

AI / RAG Application

A low-latency feature serving platform for ML model inference, providing both batch (offline) and real-time (online) feature access with strict training-serving consistency. Redis serves the hot feature cache with p99 latency targets below 5ms for online inference requests; PostgreSQL provides point-in-time feature lookups for offline training jobs with temporal consistency guarantees; Cassandra stores high-cardinality feature entities at write scale beyond PostgreSQL's single-primary ceiling; Kafka streams feature computation events from online feature pipelines to update the cache; Qdrant stores vector features for embedding-based model inputs and similarity lookups; ClickHouse serves feature analytics and drift monitoring across training dataset populations. Feature versioning is first-class: every feature value is tagged with a pipeline_version and computed_at timestamp to support model reproducibility and training-serving skew diagnosis.