Technical Summary: Auditing of Unlearning Algorithms

Problem Statement

Machine unlearning aims to remove the influence of specific training samples from a trained model, ideally yielding a model indistinguishable from one retrained from scratch on the remaining data. While exact unlearning offers strong guarantees, it is often computationally prohibitive for deep networks. Consequently, approximate unlearning methods have emerged, ranging from heuristic approaches (e.g., gradient ascent on the forget set, Hessian-based scrubbing) to certified methods that provide $(\varepsilon, \delta)$-indistinguishability guarantees.

A critical open challenge is the empirical evaluation of these claims. Existing theoretical bounds often rely on assumptions (e.g., convexity) that may not hold in practice, and there is a lack of practical tools to verify whether a claimed unlearning guarantee actually holds. This paper addresses the need for an auditor that uses empirical evidence to test unlearning guarantees, specifically aiming to reject the hypothesis that the unlearning parameter $\varepsilon$ is below a certain lower bound ($\varepsilon < \varepsilon_{LB}$).

Methodology

Threat Model

The authors adopt a strong black-box adversary model. The adversary has knowledge of:

1. The learning algorithm ($A$) and unlearning algorithm ($U$).
2. The data-loading shuffler (random permutation $\pi$).
3. The initial model weights ($x_0$) at the start of training.
   The adversary does not observe the specific random realizations (e.g., gradient noise) during training or unlearning, nor do they have access to the internal state of the algorithms. This model strengthens the adversary relative to standard definitions but is consistent with the guarantees of certified algorithms like Model Clipping and Rewind-to-Delete (R2D).

The Auditor Framework

The proposed auditor is a hypothesis-testing framework designed to compute a data-dependent lower bound $\varepsilon_{LB}$ on the true unlearning parameter $\varepsilon$.

1. Setup: The training dataset is partitioned into a retain set ($D_r$) and a forget set ($D_f$). $D_f$ is further divided into $m$ candidate batches.
2. Sign Vectors: The auditor samples a balanced sign vector $S \in \{\pm 1\}^m$, where $+1$ indicates a batch is included in the training set (and thus subject to unlearning), and $-1$ indicates it is excluded.
3. Execution: For each run $\ell$:
   • A training set $D(S^{(\ell)})$ is constructed based on the sign vector.
   • The model is trained and then unlearned to produce $f_u^{(\ell)}$.
   • The auditor attempts to predict the sign vector $S^{(\ell)}$ from $f_u^{(\ell)}$.
4. Scoring: The auditor computes an overlap score $V^{(\ell)}$, counting the number of correct non-zero guesses (where the predicted sign matches the true sign).
5. Reduction to LDP: The audit is reduced to a Local Differential Privacy (LDP) problem. If the unlearning algorithm is $(\varepsilon, 0)$-certified, the auditor's mechanism is shown to be $(2\varepsilon, 0)$-LDP.
6. Hypothesis Testing: Using the distribution of overlap scores across multiple independent runs, the auditor calculates a lower bound $\varepsilon_{LB}$. If the observed overlap significantly exceeds random guessing, the null hypothesis ($H_0: \varepsilon \le \varepsilon_{LB}$) is rejected, indicating weak unlearning.

Auditor Instantiations

Two specific instantiations of the auditor mechanism $M$ are proposed:

• Instantiation I (Batchwise): Suitable when $m$ is large. It fits Gaussian distributions to logit scores for each batch independently (inspired by LiRA) to predict inclusion/exclusion.
• Instantiation II (Joint Sign-Vector): Suitable when $m$ is small (enumerable). It treats the entire sign vector as a hypothesis, capturing cross-batch correlations, and selects the vector with the highest cumulative likelihood.

Key Contributions

1. Practical Auditor Design: The paper introduces a meta-algorithm that extends differential privacy auditing techniques to the unlearning setting, specifically tailored for subset-level forget sets rather than single-point neighbors.
2. Theoretical Bounds: The authors derive new theoretical bounds (Theorem 4.2) that convert the empirical overlap scores into a valid lower bound on $\varepsilon$ with controlled Type I error, specifically for the case $\delta=0$.
3. Empirical Falsification: The framework provides a tool to empirically falsify unlearning claims. It distinguishes between algorithms with rigorous theoretical guarantees and those that are merely heuristic.

Results

The auditor was evaluated on CIFAR-100 (using a TinyNet model) and the Shakespeare text dataset (using an LSTM). The experiments covered both certified and uncertified unlearning algorithms.

Sharp Separation Between Certified and Uncertified Methods

• Certified Algorithms: Methods with formal guarantees, such as Model Clipping (Koloskova et al., 2025) and Rewind-to-Delete (R2D), consistently yielded very small $\varepsilon_{LB}$ values (often near 0). This indicates that the empirical evidence does not falsify their theoretical guarantees.
• Uncertified/Heuristic Algorithms: Methods lacking formal guarantees, including Hessian-based unlearning, Interleaved Ascent-Descent (IDA), Ascent on the Forget Set, and Pure Fine-tuning on the Retain Set, exhibited large $\varepsilon_{LB}$ values, frequently exceeding 50–60.
  • Notably, the Hessian-based method (Zhang et al., 2025), which claims certification under convexity, yielded an $\varepsilon_{LB}$ of 142.5 on CIFAR-100 (a non-convex regime), demonstrating that the auditor successfully flagged the failure of the method's precondition.
  • Pure fine-tuning and forget-set ascent showed similarly high bounds, indicating poor unlearning performance.

Impact of Data Splits

The study observed that uniform splits (where forget and retain sets share feature support) generally resulted in higher $\varepsilon_{LB}$ values compared to adversarial splits (disjoint label classes). This suggests that residual memorization and semantic adjacency in uniform splits make unlearning more difficult to achieve effectively.

Convex vs. Non-Convex Regimes

In experiments on convex losses (cubic and logistic), the gap between the certified $\varepsilon$ and the empirical $\varepsilon_{LB}$ was much smaller than in the non-convex deep learning setting. This confirms that the auditor is tighter in analytically tractable settings and that the large bounds observed in deep learning are likely due to genuine unlearning failures in heuristic methods rather than just auditor slack.

Significance and Claims

The paper claims to provide the first practical tool for empirically falsifying unlearning guarantees through a hypothesis-testing framework. Its primary significance lies in the diagnostic value of the auditor:

• It reveals that heuristic methods, often used in practice for efficiency, frequently fail to remove data influence, as evidenced by high $\varepsilon_{LB}$ values.
• It validates that certified methods (when their assumptions hold) maintain their guarantees even under a strong adversary.
• It highlights the fragility of certification claims that rely on assumptions (like convexity) which may not hold in real-world deep learning scenarios.

The authors conclude that while their analysis is currently restricted to $\delta=0$, the proposed auditor offers a rigorous standard for evaluating the efficacy of machine unlearning algorithms, separating those with genuine guarantees from those that merely appear to forget.