Your HNSW index performs well initially but loses recall after millions of insertions and deletions. How would you diagnose index degradation?

Production incident (illustrative): An enterprise RAG retrieval service contains about 10 million active embeddings. Over six weeks, continuous document replacements cause millions of upserts and deletions. The service still answers queries quickly, yet its measured Recall@10 falls from 0.95 to 0.76. Users report missing policy paragraphs that are confirmed present in source storage. An engineer proposes increasing ef_search or rebuilding every index immediately. Both could help in some circumstances, but neither is a diagnosis.

Key principle: HNSW is an approximate nearest-neighbor graph. A recall drop after heavy updates does not prove HNSW graph corruption. Separate true graph/index degradation from missing or not-yet-visible vectors, tombstone/optimizer backlog, post-filtering, stale replicas, embedding-model drift, and benchmark errors.

1. Contain and reproduce the incident

• Confirm the severity: is this retrieval-only Recall@k or end-to-end answer-quality degradation? Monitor missing citations, zero/short result sets and query latency alongside recall.
• Stop destructive maintenance or aggressive configuration experiments until an index snapshot, recent deployment history, graph/index settings and live collection statistics are captured. If there is a reliable earlier collection/replica, consider a controlled read switch after verifying freshness and ACLs.
• Take a fixed, versioned evaluation set of real queries, expected relevant chunk IDs, tenant and filters. Ensure those expected chunks are still logically active, permitted and searchable. Do not count genuinely deleted records as false negatives.
• Construct an exact nearest-neighbor baseline over the same active corpus with the same distance metric, embedding dimension, vector normalization and authorization/filter predicates (using flat/brute-force scan or an exact reference path). Compare approximate top-k against exact top-k, and also measure relevance-judgment recall separately. Exact-neighbor recall and relevance recall are different metrics.
• Test on the same collection snapshot, same embedding model, same filters, query class, shard, replica and ef_search, before and after each experiment. A comparison between differing corpora can manufacture an apparent regression.

2. Debug the data path before blaming the graph

• Trace source document → immutable chunk ID → embedding/model version → upsert acknowledgment → index/search visibility → retrieved ID. Verify expected live-vector count, duplicate IDs, recent inserts, replay failures, source deletions and ACL/tenant filters.
• Query a few *known missing* chunk IDs directly by ID: Does the vector still exist? Is it active? Which shard/replica owns it? Does an exact search recover it under the original filters?
• Inspect optimizer backlog, deferred/unindexed points, tombstone/deleted-point fraction, segment counts, compaction/merge history, HNSW build failures, replica divergence and index health per shard—not only cluster aggregates.
• Compare ingestion rate with index-maintenance capacity: large non-indexed segments, delayed optimization or stale replicas can make apparent recall inconsistent. Read visibility and optimizer semantics vary by vendor and configuration.
• Review workload changes: higher filter selectivity, larger top_k, lower ef_search, lower m or ef_construction on rebuilt indexes, new quantization/rescoring settings, distance metric changes, dimension/model changes, or recent software versions.
• Root-cause decision tree: If expected IDs are absent from authoritative storage, fix ingestion/lineage. If exact search has them but ANN misses them, investigate ANN configuration and graph/index health. If ANN works unfiltered but fails after filtering, examine filter strategy, candidate budgets and dead tuples. If only certain replicas fail, inspect placement and replication. If corpus-neighbor recall is stable but task relevance falls, examine embedding changes and evaluation drift.

3. Investigate HNSW update/deletion behavior specifically

• Tombstones/dead entries: Many systems mark deleted vectors before physically reclaiming them. In Qdrant the Vacuum Optimizer processes segments with accumulated deleted points; Weaviate has configurable HNSW tombstone cleanup. Inspect whether cleanup is running, blocked, or falling behind. Do not assume that a given vendor's internal HNSW graph necessarily disconnects after deletes.
• Dead tuples and candidate budget: pgvector notes that HNSW can yield fewer results than requested because of dead tuples or filtering. Higher hnsw.ef_search and iterative scans can help, subject to latency and memory budgets. Diagnose the version and behavior rather than extrapolating a pgvector issue to Qdrant or Weaviate.
• Graph quality and churn: If the vendor exposes graph health signals, inspect entry-point availability, live/deleted nodes, neighbor counts, disconnected reachability, maintenance errors and index build configuration; otherwise rely on exact-vs-ANN recall under controlled snapshots. HNSW internals and exposed diagnostics are implementation-dependent.
• Segment/index readiness: In Qdrant, heavy updates can leave large unoptimized segments; certain modes can defer search visibility of newly written vectors. Check indexed-point and deferred-point counters, optimizer thresholds and per-segment status. An indexed-only optimization can hide recent points, so do not enable it blindly in a freshness-critical RAG system.
• Filter interaction: Compare identical unfiltered and filtered queries, especially highly selective tenant/ACL or policy-version constraints. Never disable authorization filters in production to increase apparent recall.
• Version-specific maintenance bugs: Investigate known issues and fixed releases when appropriate. For example, pgvector's 2026 releases included fixes related to HNSW vacuum/index repair. Confirm your actual installed version and maintenance status before attributing degradation to a known defect.

4. Numerical example: isolate the responsible mechanism

• Fixed evaluation set: 1,000 queries, each with a top-10 exact-neighbor reference on the *same active corpus*: 10,000 exact reference neighbors in total, assuming ten distinct valid neighbors per query.
• Baseline: ANN returns 9,500 of 10,000 reference neighbors → Recall@10 = 95%. After sustained churn it returns 7,600 of 10,000 → 76%, a 19-percentage-point drop (20% relative to the baseline).
• On the affected shard, suppose there are 3 million live points plus 1 million marked-deleted points. Deletion fraction = 1 / (3 + 1) = 25%, which exceeds an illustrative Qdrant vacuum threshold of 20%; this alone is *evidence to inspect optimizer operation*, not proof it caused lost neighbors.
• The investigation finds two independent issues: 800 expected active neighbors exist in source storage but are absent from the query-visible index due to optimizer/visibility backlog; the other 1,100 are visible through exact search but absent from ANN top-10 because of the current search candidate/filtered-query behavior. These counts partition the observed 1,900 missing neighbor instances in this illustration; repeated IDs across queries are counted per evaluation occurrence.
• Reconcile/replay the missing active points and wait for confirmed visibility, then measure. Suppose Recall@10 rises from 76% to 84%. Raise a test-only search budget and/or enable vendor-supported iterative filtered search on the same stable snapshot; suppose it reaches 93%, with p99 rising from 150 ms to 240 ms. A controlled healthy-shadow index built from active records achieves 95% at 175 ms, suggesting the maintenance/index configuration deserves deeper attention.
• Choose the intervention based on evidence: repair ingestion/index readiness first; if persisted ANN quality remains poor with fixed parameters and adequate candidate budgets, rebuild the affected index/segment into a shadow copy and compare before switching serving traffic.

5. Engineering recovery plan

• Restore logical correctness: Reconcile source-of-truth active IDs against durable vector-store inventory, replay missed events idempotently, and confirm every recovered point is query-visible before re-running recall evaluation.
• Recover maintenance health: Inspect and tune the vendor's optimizer/vacuum/tombstone cleanup thresholds and resource budgets. Allow maintenance to catch up without saturating live search. Verify its completion with counters—not simply by restarting a worker.
• Tune retrieval carefully: Benchmark ef_search, filtered-query planning, iterative scans and rescoring on representative queries; preserve ACL filters and record Recall@k, p95/p99, CPU, memory, and freshness.
• Rebuild only when justified: If exact-vs-ANN comparison still implicates graph/index quality, perform a versioned shadow rebuild from an immutable active-corpus snapshot, incorporate a bounded change log for writes during rebuild, verify counts/hash/ACLs and recall, and cut over using a supported atomic alias or routing-pointer method. The exact cutover semantics depend on the vendor; never assume a multi-service global transaction.
• Rollback: Keep the last verified serving index temporarily, compare canary recall and latency, and revert the routing pointer if degradation persists. Ensure recent deletions and access revocations remain enforced even during rollback.

6. Trade-offs and common mistakes

• Higher search effort: may improve ANN recall but increases CPU, memory and query latency. It cannot recover a vector that was never ingested or is excluded by an eligibility filter.
• Aggressive vacuum/compaction: reduces dead records and backlog, but competes for CPU, I/O and temporary storage; scheduling and concurrency affect live p99.
• Frequent full rebuilds: can restore graph/index structure and consolidate deletes, but cost compute, temporary disk, write catch-up, and operational risk. Avoid using rebuilds as a substitute for finding missing points.
• Lower optimizer thresholds: may trigger more frequent work; higher thresholds preserve more tombstones and can delay cleanup. Tune empirically for actual update patterns.
• Changed embeddings or distance metric: an old golden test set or mixed embedding spaces can make relevance/neighbor comparisons invalid; version query and document embeddings together.
• Filtered queries: post-filtering may yield fewer than k candidates; naive removal of security filters is unacceptable. Evaluate exact and ANN with identical tenant/ACL/effective-version predicates.
• Evaluation bias: recall estimates based on a small sample, changing ground truth, stale replicas or inconsistent snapshots can falsely indicate decay. Publish query-set version, eligible corpus snapshot, filter definitions and recall confidence intervals.
• Mistaking latency for recall: a search that returns quickly can still be wrong; a slower exact scan may reveal missing candidates but is not automatically a production serving strategy.

7. Prevent recurrence

• Maintain per-shard live/deleted/deferred/visible vector counts, optimizer backlog and duration, graph/index build errors, replica lag, source-to-vector reconciliation results and fresh-insert visibility lag.
• Run a scheduled exact-vs-ANN Recall@k canary on versioned query samples and stable source snapshots, broken down by tenant, filtered/unfiltered traffic, data age and shard. Alert on meaningful drops with minimum sample sizes.
• Enforce idempotent source-version events, deterministic chunk IDs, transactional publication manifests, deletion tombstones and authorization predicates before serving.
• Forecast churn (% inserts, updates and deletes), provision optimizer CPU/I/O and memory headroom, and keep a periodic maintenance window with observable success criteria.
• Regression-test heavy insertion/deletion sequences (including concurrent deletes, reinserted IDs, selective filters and failed optimizers) against the actual vendor/version.
• Keep a tested shadow rebuild/canary/rollback runbook, but invoke it only when validation and maintenance remediation fail to restore expected quality.

Interview takeaway: When HNSW Recall@k falls after millions of writes, first establish an exact baseline over the same live corpus, then separate missing/index-invisible vectors, tombstone or optimizer lag, and ANN graph/search-budget effects. Prove the cause on a reproducible snapshot before increasing ef_search or rebuilding the index.

References

• Qdrant, Optimizer and Vacuum Optimizer: https://qdrant.tech/documentation/ops-optimization/optimizer/
• Qdrant, Predictable search latency and optimizer tuning: https://qdrant.tech/documentation/production-operations/predictable-search-latency/
• Weaviate, Vector index and tombstone cleanup controls: https://docs.weaviate.io/weaviate/config-refs/indexing/vector-index
• pgvector, Index searches / iterative scans / HNSW filtering and dead tuples: https://github.com/pgvector/pgvector
• pgvector, HNSW maintenance changelog: https://github.com/pgvector/pgvector/blob/master/CHANGELOG.md