Vector Search hard
An HNSW index serves a marketplace where about 30% of listings are updated or removed each week. Each update is applied as a delete plus an insert, and deletes mark tombstones. Over a month, recall@10 drifts from 97% to 89% and p99 latency rises at the same ef_search. What is happening, and what should you do?
- A Tombstoned nodes still get traversed and weaken the graph. Schedule rebuilds or segment compaction.
- B The graph needs a wider search as it ages; permanently doubling ef_search is the correct steady-state fix for churn.
- C Deletes physically remove nodes and edges, thinning the graph; raise M at query time to make up for lost links.
- D Content drift has shifted the embedding space; re-embedding live listings with the same model will restore recall.
Answer: A. Tombstoned nodes still get traversed and weaken the graph. Schedule rebuilds or segment compaction.
Many HNSW implementations apply deletes as soft tombstones instead of unlinking the node. **Tombstones** keep consuming traversal steps, and replacement inserts attach to a graph whose good routes run through dead nodes. Periodic **rebuilds or segment merges** restore recall at the cost of build CPU and temporarily doubled memory. Raising ef_search (B) masks the decay with more latency and gets worse as churn accumulates. It is a reasonable stopgap only for low-churn indexes where tombstones stay a small fraction.
One system design question a day, with spaced repetition so the ones you miss come back.
Get the appRelated questions
- You are building an IVF index on 20 million vectors. A teammate asks why the build needs a 'training' step before any vectors can be added. What is the reason?
- Users delete documents in your primary database, but the deleted documents keep appearing in vector search results for hours. The vector index is rebuilt nightly. What is the best fix?
- Your embedding model outputs unnormalized vectors whose magnitudes vary widely. A teammate wants to switch the index from cosine similarity to dot product because it is cheaper to compute. What is the consequence?
- You are setting an SLO for a new ANN-backed recommendation search over 50 million vectors. A product manager asks for 100% recall@10 with single-digit millisecond latency. What is a realistic response?
- A B2B SaaS app serves 500 customers, and every query searches only one customer's documents. One large customer runs heavy batch queries that slow down search for everyone. Which sharding approach fits best?
- Your HNSW index (M=16) reaches recall@10 of 91% at ef_search=64 with a p99 of 6 ms. The target is 97% recall within a 15 ms p99. A full rebuild takes 14 hours. What is the right tuning order?