TAPE: Tailored Posterior Difference for Auditing of Machine Unlearning

Weiqi Wang, Zhiyi Tian, An Liu, Shui Yu

TL;DR

TAPE (TAilored Posterior diffErence) is a novel framework for auditing machine unlearning that operates entirely independently of the initial model training process. By analyzing the "posterior difference"—the shift in a model's prediction outputs before and after data removal—TAPE can verify whether genuine user data was actually erased, achieving up to a 75× speedup over state-of-the-art backdoor-based auditing methods.

What Problem Does This Paper Address?

With privacy regulations like GDPR enforcing the "right to be forgotten," machine unlearning has become essential for removing specific user data from trained machine learning models. However, a critical question remains: How can a user verify that a server actually performed the unlearning operation instead of just pretending to?

Existing unlearning verification methods rely on injecting "backdoors" or watermarks into the data during the initial model training phase. If the backdoor behavior disappears after an unlearning request, the unlearning is deemed successful. This approach has two major flaws:

  1. Inefficiency: It requires users to foresee their unlearning needs before initial training even begins.
  2. The Backdoor Illusion: Backdoor triggers and genuine data features behave differently. In approximate unlearning scenarios, backdoor triggers are often forgotten much faster than the actual underlying data, meaning a vanished backdoor does not guarantee that genuine user information has been erased.
Figure 1: (a) The backdoor-based verification and (b) The motivation of auditing unlearning effectiveness based on the posterior difference. The scheme (b) only involves the unlearning process rather than the initial model training.

Methods

TAPE introduces an auditing mechanism that relies solely on the unlearning phase, treating the target model as a black box. The core pipeline consists of three main components:

  1. Unlearned Shadow Model Building: To simulate how a model changes during unlearning without access to the server's full remaining dataset, TAPE leverages first-order influence estimation. This allows the user to quickly approximate an "unlearned shadow model" using only their local data.
  2. Posterior Difference Generation: The user calculates the difference ($\delta$) between the prediction vectors of the original model and the unlearned model on a small local dataset: $$\delta = \hat{Y}_{t, local} - \hat{Y}_{u, local}$$
  3. Reconstructor Training: An Autoencoder (Encoder-Decoder architecture) is trained to take this posterior difference vector as input and attempt to reconstruct the erased samples. If the data was truly unlearned, the model's structural shift leaks enough information for the reconstructor to recover the deleted data.
Figure 3: The main process of the TAPE method. (a) The first part quickly builds the unlearned shadow models through first-order influence estimation based on the user’s local dataset 𝐷𝑙𝑜𝑐𝑎𝑙to mimic the unlearning posterior difference 𝛿. (b) Two posterior difference augment strategies are proposed to make the reconstruction suitable for multi-sample unlearning.

Scaling to Multi-Sample Requests

While reconstructing a single deleted sample from a model update is straightforward, unlearning requests usually contain multiple samples, which blurs the posterior difference. TAPE introduces two strategies to combat this:

  • Unlearned Data Perturbation (UDP): Adds a optimized, imperceptible perturbation ($\Delta^p$) to the data before submission, maximizing the footprint it leaves in the posterior difference without hurting model utility.
  • Unlearning Influence-based Division (UID): Uses the mathematical properties of influence functions to mathematically disentangle a collective posterior difference into individual sample differences, assuming a Gaussian distribution.

Datasets

The authors evaluated TAPE across four widely used image datasets:

  • MNIST: 10-class handwritten digits.
  • CIFAR-10: 10-class natural images.
  • STL-10: Image recognition dataset (evaluated with an Erased Sample Size of 2 due to its smaller 5,000-sample training set).
  • CelebA: Large-scale face attributes dataset (configured for binary gender classification).

Key Insights and Ideas

  • Turning a Vulnerability into an Audit Tool: TAPE cleverly repurposes reconstruction attacks (traditionally a privacy threat where adversaries steal training data from model updates) as a defensive auditing tool to verify data deletion.
  • The Disconnect of Backdoors: The paper highlights a crucial "aha moment" in approximate unlearning: as shown in Figure 2, a model's backdoor accuracy can plummet to 0% while its accuracy on the genuine unlearned data remains high (~80%). This proves that backdoor-based auditing provides a false sense of security.
Figure 2: Approximate unlearning process on genuine un- learned data 𝐷𝑢and backdoored data 𝐷𝑏on MNIST. During unlearning, the backdoor accuracy drops to 0% at the blue Vertical line. Meanwhile, the model accuracy on genuine un- learned data 𝐷𝑢and test data is still around 80%.
  • Disentangling the Footprints: The UID strategy demonstrates that even when multiple samples are unlearned simultaneously, their individual impacts on the model parameters are additive and can be separated using first-order influence approximations.

Key Results

TAPE was benchmarked against four mainstream unlearning algorithms (SISA, HBU, VBU, RFU) and compared to the state-of-the-art backdoor verification method, MIB.

  • Massive Speedups: Because TAPE bypasses the initial training phase, it achieved at least a 4.5× speedup across all datasets, maxing out at a 75× speedup on the CelebA dataset.
  • Zero Utility Loss: Unlike MIB, which degrades the original model's accuracy by forcing it to learn backdoor triggers, TAPE maintains 100% of the original model's utility.
  • High Verifiability for Genuine Data: TAPE achieved over 95% verifiability (correctly identifying if data was removed) for genuine samples across MNIST, CIFAR-10, and CelebA. In contrast, MIB scored 0% when attempting to verify genuine, non-backdoored samples.
Figure 4: Auditing for different unlearning methods. TAPE consistently achieves significant efficiency improvement and a better unlearning auditing effect for a single sample (SS) than for multiple samples (MS).

Limitations and Future Work

While TAPE represents a major step forward, it operates under a few constraints:

  • White-box Architecture Assumption: It assumes the user can deduce or steal the target model's architecture and unlearning algorithm (though the authors note this can be mitigated via hyperparameter stealing attacks).
  • Local Dataset Requirement: The user must maintain a small local dataset to query the black-box model and generate the posteriors.

Future Directions: The authors suggest extending this methodology to build even more efficient, zero-knowledge auditing tools tailored specifically for complex Machine Learning as a Service (MLaaS) environments.

Summary updated

Abstract

With the increasing prevalence of Web-based platforms handling vast amounts of user data, machine unlearning has emerged as a crucial mechanism to uphold users' right to be forgotten, enabling individuals to request the removal of their specified data from trained models. However, the auditing of machine unlearning processes remains significantly underexplored. Although some existing methods offer unlearning auditing by leveraging backdoors, these backdoor-based approaches are inefficient and impractical, as they necessitate involvement in the initial model training process to embed the backdoors. In this paper, we propose a TAilored Posterior diffErence (TAPE) method to provide unlearning auditing independently of original model training. We observe that the process of machine unlearning inherently introduces changes in the model, which contains information related to the erased data. TAPE leverages unlearning model differences to assess how much information has been removed through the unlearning operation. Firstly, TAPE mimics the unlearned posterior differences by quickly building unlearned shadow models based on first-order influence estimation. Secondly, we train a Reconstructor model to extract and evaluate the private information of the unlearned posterior differences to audit unlearning. Existing privacy reconstructing methods based on posterior differences are only feasible for model updates of a single sample. To enable the reconstruction effective for multi-sample unlearning requests, we propose two strategies, unlearned data perturbation and unlearned influence-based division, to augment the posterior difference. Extensive experimental results indicate the significant superiority of TAPE over the state-of-the-art unlearning verification methods, at least 4.5$\times$ efficiency speedup and supporting the auditing for broader unlearning scenarios.
BibTeX
@inproceedings{wang2025tape,
  author = {Weiqi Wang and Zhiyi Tian and An Liu and Shui Yu},
  title = {{TAPE: Tailored Posterior Difference for Auditing of Machine Unlearning}},
  booktitle = {The Web Conference},
  year = {2025},
}
Figure