Standard

Freshness lag is the right answer because every production vector database documents some version of this behaviour.

The write path looks like: client sends upsert, engine writes to a write ahead log for durability, engine adds the vector to an in memory buffer or a fresh segment, engine acknowledges success to the client. None of those steps update the searchable index. A background task flushes the buffer or merges the segment on its own schedule, and the vector becomes queryable only after that.

The window is engine specific:

• Pinecone serverless. A few seconds at the freshness layer, longer to fully merge into the main index.
• Elasticsearch / OpenSearch. Default refresh interval is 1 second; can be lowered at a CPU cost or set to immediate per request.
• Milvus. Explicit consistency levels (strong, bounded, session, eventual); eventual is the cheap default.
• Qdrant. Writes are visible after the WAL flush, typically sub-second but configurable.
• pgvector. Writes are immediately visible in the table but only show up in the IVFFlat or HNSW index after the index sees them, depending on engine version and settings.

The trap for application developers is assuming write after read consistency. Vector databases default to eventual consistency on the read path for performance reasons. The fix is to either query the strong consistency path (where supported), to wait a documented refresh interval, or to design the application so freshness lag is acceptable (a chat that displays the just written doc from the application database, not the index).

The answer is tombstone.

A tombstone is a logical-deletion marker. In HNSW, deletes set this flag on the node but leave the node, its vector, and its neighbor lists in place. Search traversal still walks through tombstoned nodes; the engine checks the flag, discards the candidate, and continues. The cost shifts from the writer (delete is cheap) to the reader (search pays a small tax per tombstone visited).

The term comes from log-structured merge tree (LSM) databases like Cassandra, RocksDB, and ScyllaDB, where deletes also work this way: a marker is written to the log, queries OR the tombstone bitmap to skip dead ids, and compaction eventually drops the dead entries when segments merge.

In vector databases (Vespa, Milvus, Qdrant, Weaviate), the same mechanism applies and the same operational concerns follow: tombstone ratio is a metric to monitor, compaction cadence is a knob to tune, and recall in heavily churned regions can sag if tombstones accumulate.

Knowing the word tombstone signals familiarity with the underlying database pattern; calling it a delete flag misses the connection to LSM design and the operational implications.

Tombstones are the standard delete mechanism in graph-based vector indexes (HNSW, DiskANN, NSG). A delete marks the node as logically removed but leaves it in the graph structure because rewriting incoming neighbor pointers from every node that references it would be prohibitively expensive at delete time.

The three real symptoms follow directly from the mechanism:

• Latency creep. Search traverses the graph using ef_search candidate expansion. Tombstoned nodes are still visited, still consume the exploration budget, and still contribute to traversal cost. Live vector count can stay flat while walk-time grows linearly with cumulative deletes.
• Memory persistence. Deletes return success at the client level but do not deallocate the underlying graph node, neighbor list, or vector storage. Heap holds steady or grows. RSS does not drop after large delete jobs.
• Recall sag in churned regions. When a live node has many tombstoned neighbors, its effective connectivity drops. The small-world property of HNSW relies on a saturated neighborhood; tombstones starve it. Recall sags worst in regions where churn concentrated (active user accounts, retracted news stories, expired listings).

The two distractors are diagnostic for a strong answer. Write throughput is independent of deletion state; inserts add new nodes to the graph regardless of tombstone count. Score signs are functions of the distance metric and the vector values; cosine over unit-normalized vectors lives in [-1, 1] and L2 is non-negative, neither of which changes when deletions accumulate.

Production mitigation is background compaction (Vespa, Milvus, Qdrant, Weaviate all run this) sized against the actual delete rate.

These five symptoms are the canonical vector-search incident set. Each maps to a specific structural feature.

Freshness lag. Vector engines split write ack from visibility. Writes commit to a WAL or memtable, ack, then become searchable on the next refresh. Pinecone, Elasticsearch, Milvus expose this as a refresh interval or consistency level. Fix: query with the right consistency level or wait the refresh window.

Tombstones. HNSW and graph-based indexes mark deleted nodes rather than removing them. The dead nodes still occupy memory and still get walked during search, polluting the candidate set and slowing traversal. Recall sags in heavily churned regions and memory does not shrink after deletes. Compaction or full rebuild reclaims the space.

Replica nondeterminism. ANN is approximate; different replicas with slightly different segment layouts will return candidate sets that overlap but do not match exactly. Run-to-run differences across a replicated cluster are expected, not a bug. The fix is either to accept it as a property of the system, pin sessions to a single replica, or set deterministic routing parameters where the engine supports it.

Metric mismatch. Cosine returns values in [-1, 1], dot product can return any real number, and L2 distance is unbounded. Two collections with different metrics or different normalization conventions cannot have their scores compared directly. The fix is to standardize the metric or convert via a known relationship before comparing.

Post-filter pruning. Post-filtering runs the ANN search first, then applies the filter to the candidates. If the candidate set is k = 50 and the filter passes only 10% of vectors, the user gets 5 results instead of 50.

The decision is about matching billing shape to traffic shape. The traffic shape is 7.2M queries in 1 hour, 0 queries in 23 hours, so 4% duty cycle.

Dedicated pods at peak capacity: cost is linear in time, indifferent to traffic. The bill is the same on the busy hour as on a quiet Sunday. Effective cost per query is ~25x the peak-hour rate because the same capacity is paid for during the idle hours.

Serverless usage-based (Pinecone serverless, Turbopuffer): cost is linear in queries plus a small storage rate. The busy hour drives the variable component; the idle 23 hours drive only the storage component. Effective cost per query is roughly the marginal per-query rate, with storage amortized across all queries.

The two non-serious options are worth naming explicitly because they appear in real interviews. GPU clusters address index build time and very high throughput, not billing efficiency, and they have their own idle-cost problem. Per-seat pricing is a SaaS tooling model unrelated to query economics.

The pragmatic 2026 default for spiky retrieval workloads is serverless. The exception is when QPS is also high during off-peak hours; then the duty cycle is high, dedicated capacity stops being wasteful, and reserved pods can win on per-query cost.

The decisive variable is access pattern versus storage latency.

SPANN keeps a small set of centroids in RAM and stores each cluster's vectors as a posting list on cheap storage. A query reduces to: find the nearest k centroids in RAM, then issue a handful of large, independent, parallel reads to fetch those posting lists. Round-trip cost is paid once per posting list, not once per vector.

DiskANN runs a Vamana graph walk. Each step picks the next node based on the current node's neighbor list, so reads are serial and chained. On NVMe at ~100 microseconds per hop with 50-100 hops, this finishes well inside 200 ms. On object storage at ~30 milliseconds per hop, the same walk needs 1.5 to 3 seconds.

For billion-scale on cheap remote storage with a 200 ms budget, SPANN wins because its I/O pattern is round-trip-amortizing. This is exactly the design choice behind Turbopuffer's object-storage-native engine and Pinecone serverless's separation of metadata in RAM from vectors on S3. DiskANN remains the strong choice when storage is local NVMe; the algorithm did not get worse, the assumed medium changed.

Each shard independently exceeds its p99 threshold (40 ms) on 1% of requests. The query waits for the slowest shard, so it is fast only when every shard is fast.

That is 14.9% of user queries, roughly 1 in 7. The architecture has transformed a per-shard p99 into the user-facing p85: the tail that used to live at the 99th percentile of a single shard now lives at the 85th percentile of the user distribution.

The production fix is not to make each shard faster (the 1% tail is hard to remove) but to stop waiting for every shard. Common patterns: hedged requests (send a duplicate after a small timeout), partial-result timeouts (accept k-1 shards if the last one is late), or replica racing (multiple replicas per shard, take the first to answer). Each trades small extra cost for a much shorter user tail.

Resource contention is the right diagnosis because the latency shape (p50 healthy, p99 tripled) is the textbook signature.

A background reindex consumes:

• CPU. Build threads compete with query threads for cores. The OS scheduler usually gives queries enough time, but the slowest fraction get preempted and queued.
• Memory bandwidth. The rebuild is reading every vector and writing the new index. Memory bandwidth is finite per socket; queries running concurrently get fewer effective bytes per second on the slowest paths.
• Page cache. Old segments evicted, new segments brought in. Queries that wanted pages just evicted suffer cold reads from disk, adding milliseconds to tens of milliseconds per query.
• Disk I/O. Sustained sequential writes from the rebuild compete with random reads from queries. The disk queue length spikes during compaction bursts; queries in the wrong place at the wrong time wait the queue out.

None of these affect every query, which is why p50 is fine. All of them affect the unlucky few, which is why p99 triples.

The operational fix is to throttle the rebuild (lower ingest threads, cap I/O, schedule during off-peak), to keep the rebuild on a separate node and switch via alias (Qdrant aliases, Pinecone namespaces) once it is built, or to accept the tail spike and time it for a maintenance window when SLO budgets allow it. Pretending tail latency does not matter during rebuilds is how SLO budgets get burned silently.