Structural deletion from proximity graph

A proximity graph index holds the embeddings behind a live retrieval service. It is large enough that a full rebuild takes longer than any window the service has, and the rebuild would run on the same accelerators that are serving. Deletions arrive continuously and they are correlated: a customer leaves and takes a contiguous region of the space with them, a source is retracted in bulk, an erasure request names a person whose documents cluster.

Two requirements bite at once.

Erasure has to be structural. A tombstone plus a query time filter does not clear the bar, because the neighbor lists of the surviving nodes were computed with the deleted point in the candidate set, and search still routes through where it used to be. What remains is a function of the vector you were told to remove.

Recall has to survive an adversary. After k deletions chosen by someone who has read your procedure, search over the remaining points still has to work. Correlated deletion removes exactly the nodes that made distant regions reachable from one another, so the uniform random deletion case tells you nothing about it.

Off the table: a rebuild window, a tombstone and filter answer, and any assumption that deletions are independent or uniformly distributed.

Hand in the deletion procedure with its cost per deletion in distance computations and edges modified. Hand in a definition of erased, stated as a property of the post deletion index that a third party could test rather than as a claim that memory was freed. Hand in either a recall bound under adversarial deletion or a construction showing that no procedure in a class you name can hold recall under it. Hand in an attack on your own erasure claim: given the index after the deletion, recover an approximation of the removed vector from surviving neighbor lists, stored distances and graph structure. Then state the case where your procedure keeps recall and fails erasure, or the reverse.

Ties break toward an erasure claim that is narrow and testable over one that is broad and asserted.