The Removability Gap: Adversary-Resistant Verification of Machine Unlearning via Taint-Closure Criteria

Machine-unlearning verification asks whether a model provider has truly removed a data subject’s contribution after a deletion request. A recent result shows that the dominant verification families are fragile: a dishonest provider can satisfy them while the model demonstrably retains the information it claims to have forgotten. This paper isolates the structural cause of that fragility and stakes the research gap it opens. We argue the failure is definitional, not merely empirical: existing verification certifies a set-membership removability condition — that no deleted datum appears in the recorded computation — which is provably blind to influence-equivalent substitution, where retained data is selected to reproduce the deleted data’s effect on the model. We name this the Removability Gap: the distance between not using a datum and not being influenced by it. We then propose a criterion intended to close it — taint-closure removability, which replaces set-disjointness with disjointness from the influence (taint) closure of the deletion set, computed from write-time provenance rather than reconstructed after the fact — and an evaluation posture, adversary-resistant multi-source confidence, that treats verification as calibrated evidence robust to single-channel suppression rather than as a single gameable test. We are explicit about what is not yet solved: exact influence closures are intractable on deep non-convex models, so the criterion is exact only where lineage is recorded (instrumented fine-tuning, retrieval memory, agent shared state) and approximate elsewhere. This is a problem-formalization and priority-staking paper; it defines the gap and the criterion, not a complete verification system. The work is positioned against a near-term regulatory mandate that requires verified data removal without prescribing a method.