Detailed answer

A vector database has two jobs: store vectors safely, and answer nearest neighbour queries fast. The structures that do those two jobs are different.

Durability lives in a write ahead log and replicated segment files on disk. Adding a record is cheap: append to the log, flush, return success. The cost is dominated by the disk fsync, which is fast on modern SSDs.

Queryability lives in an HNSW graph or an IVF posting structure. Inserting into an HNSW graph means walking the upper layers to find the right insertion point, choosing M neighbours, and updating bidirectional links on each of them. This is much more expensive than appending to a log; doing it synchronously on every write would cap ingest throughput at a small fraction of what the log can absorb.

The fix is to batch. Writes accumulate in a buffer (a memtable, a fresh segment, or a delta layer), and the engine merges the buffer into the main index periodically. The acknowledgement is fast because it requires only the log write; the index update happens in the background.

The consequence is that for some interval after acknowledgement, the vector is durable but not findable. This interval is the freshness window. Different engines expose different windows because they batch differently.

HNSW is a graph where each node has a set of neighbors at each level, typically M = 16 neighbors per level over 3-5 levels. The graph's small-world property depends on each node's neighbor list being saturated with live, well-chosen nodes; that property is what makes search fast.

A physical deletion would require finding every node whose neighbor list includes the deleted one and rewriting that list. The set of incoming edges to a node in a small-world graph is typically dozens; some popular hub nodes have hundreds. Each delete becomes dozens of memory writes plus (for persistent indexes) dozens of disk writes, each requiring a pointer chase and a synchronization step.

The alternative chosen by HNSW and similar graph indexes is logical deletion: mark the node as deleted, leave the structure intact, and pay the cost at search time. Search visits the tombstoned node, sees the flag, discards the candidate, and continues. The cost is a small per-tombstone tax on every traversal, but it is bounded and predictable, and it can be amortized away by periodic compaction.

The tradeoff is straightforward: physical deletion is expensive per delete and cheap per query; logical deletion is cheap per delete and slightly more expensive per query. For workloads with high delete rates relative to query rates (think churning user-data products), logical deletion wins by orders of magnitude.

HNSW (hierarchical navigable small world) is a graph where each node has a small set of neighbors at each level. A physical delete would require rewriting incoming neighbor pointers from every node that references the deleted one. In a graph with average degree M = 16 across multiple levels, that is many pointer rewrites per delete, each requiring lookups and disk writes.

The engineering compromise is to mark the node deleted and leave the structure alone. Search walks the graph as before, encounters the tombstone, sees the deleted flag, and discards the candidate. The node still occupies its vector storage, its neighbor lists, and its bookkeeping.

This is the same pattern as Cassandra and other LSM systems use for deletes, where the term tombstone originated. The metaphor is exact: a marker that says 'something was here' without freeing the underlying space.

The consequence is that deletes are cheap at delete time but expensive at search time. The cost shifts from the writer to the reader, and accumulates until compaction reclaims it.

Vector databases distinguish acknowledged writes from searchable writes. A write commits to a write-ahead log and a memtable, returns success to the client, and becomes searchable only on the next refresh or segment flush. The window between acknowledged and searchable is the freshness lag.

Pinecone serverless documents this as eventual consistency with sub-second to multi-second freshness depending on tier and load. Elasticsearch exposes a per-index refresh_interval (default 1s, often raised to 30s under heavy write load to reduce IO). Milvus offers per-query consistency levels (Strong, Bounded, Session, Eventually), where Strong forces a wait until the latest write is visible.

The diagnostic pattern is to query the document with a stronger consistency level or to wait the documented window and retry. If the document appears after the window, freshness lag is confirmed. If it never appears, the symptom is something else (write failed, wrong index, wrong filter).

The wrong fix is to file a data-loss bug. The right fix is to choose the consistency level that matches the user expectation: Strong for read-after-write paths (search-for-just-uploaded), Eventually for cross-user search where small delays are acceptable.