EVE: Efficient Verification of Data Erasure through Customized Perturbation in Approximate Unlearning

Weiqi Wang, Zhiyi Tian, Chenhan Zhang, Luoyu Chen, Shui YuarXiv 2026 · arXiv

TL;DR

EVE (Efficient Verification of Erasure) is a novel method that allows users to verify whether a cloud server has actually deleted their data from a machine learning model. By introducing subtle, customized perturbations to the data being erased, EVE forces the model's decision boundary to shift for specific target samples, providing a clear verification signal without requiring any changes to the model's initial training phase.

What Problem Does This Paper Address?

With regulations like the GDPR enforcing the "right to be forgotten," machine unlearning has become a vital area of research. However, a major loophole remains: how can a user verify that a Machine Learning as a Service (MLaaS) provider actually executed the unlearning process instead of just pretending to?

Existing verification methods rely on "backdooring" techniques. They require users to embed hidden triggers into their data during the initial training phase so they can check for their removal later. This is highly impractical because users cannot predict ahead of time which data samples they might want to delete in the future.

Figure 1: (a) The backdoor-based verification and (b) the in- tuition of efficient verification of erasure (EVE) based on the perturbed unlearning data. The scheme only involves the unlearning process rather than the original model training process.

The authors introduce EVE to solve this dilemma, creating a verification mechanism that operates entirely within the unlearning request phase, completely independent of how the model was originally trained.

Methods

EVE works by crafting a customized perturbation that is added to the unlearning data right before it is submitted to the server for erasure.

  1. Gradient Matching via UDPD: The core optimization problem is formalized as an adversarial challenge. Directly solving it is computationally intractable, so the authors propose the Unlearning Data Perturbation Descent (UDPD) algorithm. UDPD optimizes the perturbation by aligning (matching) the gradients of the unlearning loss with the gradients required to intentionally misclassify specific "target" samples.
  2. Boundary Shifting: When the server honestly runs an approximate unlearning algorithm on this perturbed data, the model's decision boundary shifts. Consequently, the unlearned model will misclassify the target samples that the original model previously got right.
  3. Statistical Hypothesis Testing: To ensure the verification signal is reliable and not just random noise, the user performs a T-test. This statistical framework provides a mathematical guarantee (confidence level) that the model has indeed been updated.
Figure 2: An example of the idea of our method. a) A trained robust model can correctly predict the genuine unlearned and target model-unseen samples with high probability. b) Our method customizes perturbation for the erased data for unlearning, aiming to make the unlearned model easily misclassify the unseen data after unlearning. c) The unlearning user queries for specified samples to verify if the unlearned model is influenced by the perturbation.

Datasets

The authors evaluated EVE across four public image datasets representing varying levels of complexity:

  • MNIST: 70,000 handwritten digit images (28x28 pixels).
  • CIFAR10: 60,000 color images across 10 distinct object/animal classes (32x32 pixels).
  • STL-10: 13,000 higher-resolution color images (96x96 pixels), presenting a more challenging learning task.
  • CelebA: Over 200,000 celebrity face images, utilized here for a binary gender classification task.

Key Insights and Ideas

  • Decoupling Verification from Training: EVE shifts unlearning verification from a proactive requirement (altering initial training) to a reactive one (altering only the deletion request). This drastically improves real-world viability.
  • Exclusivity to Unlearning: A fascinating property of EVE's perturbations is that they only trigger a decision boundary shift if an unlearning algorithm is applied. If a server tries to trick the user by simply performing continual learning on the new data, the boundary does not shift, exposing the server's dishonesty.
  • Utility Preservation: Traditional data poisoning or backdooring often degrades overall model accuracy. EVE carefully balances the perturbation distance so that the final unlearned model maintains high utility for normal users.

Key Results

The authors benchmarked EVE against a state-of-the-art backdoor method (MIB) and a posterior-difference method (TAPE) across three approximate unlearning frameworks (HBU, VBU, and SalUn).

  • 100% Verifiability: EVE consistently achieved 100% unlearning verifiability across all datasets, even outperforming baselines on complex datasets like CelebA (where MIB achieved 92.89% and TAPE achieved 88.42%).
  • Massive Speedups: Because EVE bypasses the initial training phase entirely, it delivers massive efficiency gains. On the STL-10 dataset, EVE achieved up to a 160× speedup in overall process time compared to MIB. On CIFAR10, EVE executed its verification setup in just 3.93 seconds compared to MIB's 613 seconds.

Limitations and Future Work

The primary limitation acknowledged by the authors is that EVE is currently optimized specifically for approximate unlearning methods (which estimate data removal via gradient steps or Hessian matrices) rather than exact unlearning (which completely retrains models from scratch). The authors note that future research should focus on adapting these customized perturbation strategies to accommodate exact unlearning frameworks and broader MLaaS application scenarios.

Summary updated

Abstract

Verifying whether the machine unlearning process has been properly executed is critical but remains underexplored. Some existing approaches propose unlearning verification methods based on backdooring techniques. However, these methods typically require participation in the model's initial training phase to backdoor the model for later verification, which is inefficient and impractical. In this paper, we propose an efficient verification of erasure method (EVE) for verifying machine unlearning without requiring involvement in the model's initial training process. The core idea is to perturb the unlearning data to ensure the model prediction of the specified samples will change before and after unlearning with perturbed data. The unlearning users can leverage the observation of the changes as a verification signal. Specifically, the perturbations are designed with two key objectives: ensuring the unlearning effect and altering the unlearned model's prediction of target samples. We formalize the perturbation generation as an adversarial optimization problem, solving it by aligning the unlearning gradient with the gradient of boundary change for target samples. We conducted extensive experiments, and the results show that EVE can verify machine unlearning without involving the model's initial training process, unlike backdoor-based methods. Moreover, EVE significantly outperforms state-of-the-art unlearning verification methods, offering significant speedup in efficiency while enhancing verification accuracy. The source code of EVE is released at \uline{https://anonymous.4open.science/r/EVE-C143}, providing a novel tool for verification of machine unlearning.
BibTeX
@misc{wang2026eve,
  author = {Weiqi Wang and Zhiyi Tian and Chenhan Zhang and Luoyu Chen and Shui Yu},
  title = {{EVE: Efficient Verification of Data Erasure through Customized Perturbation in Approximate Unlearning}},
  year = {2026},
  eprint = {2602.03567},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2602.03567},
}
Figure