Keep logical documents correct while index bytes change

A document ID should survive physical compaction and index rebuilding. Some flat index removal operations shift implicit positions, whereas IVF variants can store explicit IDs; Faiss documents these differences and the direct-map restrictions for supported removals. Applications that treat a shifting ordinal as a stable business key can accidentally attach one vector’s score to another document’s text. Keep the document-to-vector mapping explicit and verify it after mutation, not only after the initial build.

Deletion support also differs across graph implementations. The Faiss HNSW family documented in its index guide does not support removing vectors in the same way as its removable flat or IVF indexes. hnswlib 0.8.0 supports mark_deleted, omitting that label from results, and optional replacement of deleted slots under its initialization contract. Marking an item invisible is not equivalent to reclaiming all adjacency storage, rebuilding navigation, or erasing every copy in a surrounding service.

One design keeps an immutable base snapshot and a smaller mutable delta. A version map says which physical entry is current, and tombstones suppress deleted IDs. Query both structures, discard entries inconsistent with the chosen visibility boundary, deduplicate logical IDs, then rank the remaining candidates using comparable scores. Merely taking k entries from each physical structure can leave fewer than k valid logical documents after stale versions are removed, so the candidate and fallback policy must address that loss.

Correct visibility still does not imply exact nearest-neighbor completeness. A stale entry can consume a local candidate slot before being discarded, hiding a valid farther entry. Overfetching reduces this risk but does not generally certify an exact answer. For an exact proof, obtain sufficient valid local results or use an exhaustive eligible fallback under the same snapshot. In an ANN service, measure recall after all version suppression and deduplication rather than reporting the earlier physical-entry recall.

A rebuild can compact deleted entries, retrain coarse or PQ codebooks, or repair graph quality under the current distribution. Choose a source snapshot and record its ingestion watermark. If writes continue during the build, replay every later change in a defined order or use a coordinated snapshot-and-log mechanism, then verify the final coverage boundary before promotion. A snapshot copied without its log boundary cannot prove whether a concurrent update was included, omitted, or applied twice.

Test updates adversarially: replace the nearest document, delete it, reinsert its stable ID with a newer version, and query while the base and delta overlap. Check both returned text versions and scores. Preserve the old snapshot and its compatible delta state long enough for the declared rollback policy. A pointer back to old vector bytes alone may resurrect deleted documents if current visibility or replay state is not carried into the rollback design.