Deposits and Random Audits for Machine Unlearning Requests

Machine unlearning removes the influence of specific training data from a trained model without retraining it from scratch, so that a system can honor a deletion request. Current unlearning systems assume every deletion request is honest. That assumption is dangerous. Unlearn and Burn shows that 10 to 20 crafted "please forget this" samples, which were never in the training set, can drive a ResNet-18 on CIFAR-10 from roughly 99% accuracy to 3.6%. The attack works by turning the unlearning update against the model and triggering catastrophic forgetting, meaning the model loses knowledge it was supposed to keep. Checking where a sample came from does not help. Perceptual verification falls below 0.5 AUROC against these attacks, which is worse than a coin flip.

We propose to treat each deletion request the way mechanism design treats a report from a self-interested agent. The requester posts a refundable deposit. The server applies the request as an isolated, removable piece of the model. It then audits a random fraction of requests by measuring how much collateral damage each one causes on a secret probe set. If a request's damage looks unlike the damage that genuine requests cause, the server removes that request's piece and keeps the deposit. The design borrows the "randomized threat" from Incentive Compatible Budget Elicitation in Multi-unit Auctions, where a small chance of a severe penalty makes lying unprofitable on average. The audit signal comes from the unlearning literature: catastrophic forgetting is exactly the damage an attacker wants to cause, so it is also the thing to measure.

Core Claim

The claim has two parts, and the second is what links the two research directions.

The first part is a mechanism result. Suppose three conditions hold. Each request lives in its own removable adapter (a small added set of weights that can be detached, in the style of Memory Adapters Enable Fast, Flexible Knowledge Unlearning in LLMs). Audits happen with probability $q$ and are possibly delayed. The audit test has false-positive rate $\alpha$ on genuine requests and catches attacks with probability $\beta$. Then a risk-neutral requester maximizes expected utility by submitting only their own genuine data whenever

$$ q\,\beta\,D \;>\; G, $$

where $D$ is the deposit and $G$ is the attacker's value from the damage their adapter causes before it is removed. The expected cost to an honest requester is $q\,\alpha\,D$, and the operator can keep this near zero.

Adapter isolation is what makes probabilistic auditing acceptable here. In an auction, an unaudited lie only costs money. In unlearning, an unaudited malicious update can destroy the model permanently. Making each update removable turns that permanent harm into a bounded period of exposure. The length of that period is set by the audit schedule, at about $1/q$ requests in expectation, because audits arrive as independent trials with probability $q$.

The second part is an empirical prediction. Whether the condition above can be met depends on the unlearning algorithm. Plain gradient ascent, which pushes the model's loss up on the forget data, causes large and variable collateral damage even on honest requests. That makes $\alpha$ high and $\beta$ low, so no reasonable deposit deters attacks. Utility-preserving unlearners make honest damage small and predictable, which widens the gap between honest and adversarial damage profiles. Two examples are weight-attribution masking (WAGLE) and representation misdirection with a retain loss (RMU, from The WMDP Benchmark). Put plainly, controlling catastrophic forgetting is a precondition for incentive-compatible request handling, not just a quality concern.

Relation to Prior Work

Three attack papers motivate the problem: Unlearn and Burn, FedMUA, and Static and Sequential Malicious Attacks in the Context of Selective Forgetting. They show, respectively, that crafted forget sets can destroy overall accuracy, that they can target specific users, and that they can degrade fairness. None of them proposes a defense with incentive guarantees. FedMUA's defense, which detects unusually large gradients using the interquartile range and scales them down, is the only concrete countermeasure in the file. We differ in kind. We do not try to spot a bad update from the update alone. We make attempting an attack costly, and we judge requests by their measured effect on held-out behavior.

Two game-theoretic papers are the closest existing work. Incentive Mechanism Design for Federated Learning and Unlearning designs deterministic contracts and Shapley-value retention payments, and it assumes forget requests are honest. Strategic Data Revocation in Federated Unlearning analyzes the equilibria of how much data users choose to revoke, models model quality as a smooth function of sample count, and designs no mechanism. Both papers ask whether honest users stay or leave. Neither asks whether a request is genuine. Both also ignore the fact that real unlearning damage is threshold-like and representation-dependent, which TOFU documents as collapse at 5–10% forget sets.

Two further papers constrain the design. An Illusion of Unlearning? finds that unlearned knowledge often survives in deeper representations. We therefore do not claim that adapter-based unlearning removes knowledge more completely. We use adapters only to make damage reversible, and we report forgetting quality separately. The risk-attitude caveat in the randomized mechanism-design literature also constrains our claims, so the guarantee is stated only for risk-neutral attackers. A risk-seeking attacker facing a small $q$ is a real hole, and we test it directly.

Research Program

We will build a request-processing service around three components.

The first is the unlearner. Each request is turned into an adapter by gradient ascent, gradient difference, a WAGLE-masked update, or an RMU-style update, so that the unlearner can be swapped while everything else stays fixed.

The second is the audit. With probability $q$, at a random delay, the server evaluates the adapter on a probe set drawn fresh from a large private pool of held-out data. It computes a damage profile: the per-class change in accuracy, the change in group-fairness gaps, and the change in retain-set loss. It then scores how unusual that profile is against a reference distribution. That reference comes from simulated genuine requests of the same size, drawn from real training points. We calibrate the threshold so that honest requests fail at rate $\alpha$.

The third is the settlement rule. A failed audit removes the adapter and forfeits the deposit. A passed audit, or no audit, refunds the deposit after a holding window.

On the theory side, we will formalize the request game. This includes an attacker who can make repeated, adaptive attempts. Here the deposit matters beyond simple deterrence. Any accept/reject signal leaks information about the secret probe, so a free audit becomes an oracle the attacker can search against, while a costly audit charges for every query. We will derive the deterrence condition and the bound on exposure time under sequential, Sybil-style splitting of an attack across many identities. Within the theory, we will treat the honest/adversarial separation $(\alpha, \beta)$ as an empirical quantity rather than assume it.

Baselines

The naive reference point is to accept every request and apply it directly to the weights, as current pipelines do. On CIFAR-10, Unlearn and Burn reports ResNet-18 accuracy falling from about 99% to 3.6% under white-box attack and to 8.5% under black-box attack. On ImageNet it reports ResNeXt-50 falling to 0.4% and 1.3%. We will reproduce these numbers with the same attack code, request budget, and model checkpoints before comparing anything else.

The strongest existing defense is FedMUA's interquartile-range gradient scaling (FedMUA). At $\lambda=0.1$ it reportedly halves an average attack success rate of 80%, and its authors note that it is weak on CIFAR-10. We will run it on the identical request streams, sweep $\lambda$ over the same tuning budget we give our audit threshold, and give it access to the same honest calibration requests. Perceptual and feature-similarity verification is a second existing defense, reported below 0.5 AUROC. We include it so that we reproduce that failure rather than merely cite it.

The most dangerous baseline is our own deterministic version: audit every request, with the same secret probe and the same adapters, and charge no deposit. On non-adaptive attacks this should match or beat us on protection, because $q=1$. We beat it only if one of two things holds. Either we achieve comparable final retain accuracy at a fraction of the audit compute, or we hold protection against an adaptive attacker who uses the free accept/reject signal to search for a request that passes.

Three ablations isolate the key ingredients. A fixed, public probe set replacing the fresh secret draw tests the value of hidden randomness. In-place weight updates replacing adapters test whether reversibility is what makes probabilistic auditing safe. Swapping gradient ascent for WAGLE or RMU as the unlearner tests the second claim. If $\beta$ at a fixed $\alpha$ does not rise when we move to a surgical unlearner, that claim is wrong.

Why not just…?

Why not just verify provenance with hashes or signatures? Exact hashes reject honest users who resubmit re-encoded or reformatted copies of their data. Relaxed similarity checks are evaded: Unlearn and Burn reports verification AUROC below 0.5 against attacks constrained to small $\ell_2$ perturbations. Hash commitments also require keeping an index of every training item, which open-weight and privacy-constrained deployments often cannot do. Where clean provenance is available, it should be used, and our mechanism then covers whatever the hash check cannot.

Why not just clip or rescale suspicious gradients? The attack in Unlearn and Burn needs only a handful of samples whose per-sample perturbations stay within ordinary variation. FedMUA reports that its own interquartile-range defense degrades on CIFAR-10. Gradient size describes the update, not its effect, so a targeted or fairness-degrading request with ordinary-looking gradients passes. The FedMUA baseline comparison above tests this directly.

Why not just audit every request deterministically and skip the deposit? This is the real threat to the proposal, and we do not argue around it. If evaluating a probe set is cheap relative to running the unlearning, as with small vision models, and attackers are not adaptive, full auditing is simpler and at least as protective. Our case rests on two measurable claims. The first is that audit compute dominates for large models and high request volumes. The second is that a free accept/reject signal lets an adaptive attacker find a passing request in few queries, while a deposit makes that search expensive. If the adaptive-attacker experiment shows full auditing with secret probes resists search just as well, we will report that the deposit adds nothing beyond saving compute.

Why not just rate-limit requesters? Rate limits are per identity and fail against cheap identities. A deposit scales with the number of attempts, whoever makes them. We will include a per-identity rate limit with Sybil splitting in the adaptive experiments.

Proposed Experiments

The main experiment reproduces the Unlearn and Burn attacks on CIFAR-10 with ResNet-18 and on ImageNet with ResNeXt-50. We mix attack requests into streams of genuine requests and report two things. The first is final retain accuracy against audit compute as $q$ varies. The second is the trade-off between honest false-positive rate and attack catch rate for each unlearner.

The targeted-damage experiment uses the FedMUA setting on CIFAR-10, CIFAR-100, and Credit Score, where the attack misclassifies specific users while overall accuracy barely moves. Here we compare our per-class and per-group probe against simple monitoring of aggregate accuracy. The fairness experiment uses the sequential attacks of Static and Sequential Malicious Attacks on Adult and COMPAS, tracking the demographic-parity gap. These sequential attacks spread damage over many small requests, so this experiment also tests the bound on splitting.

As an exploratory extension, we will craft adversarial forget requests against Llama-2-7B on TOFU, aimed at collapsing retain and world-facts utility. This tests whether the honest/adversarial separation carries over to language models. No reported result for adversarial TOFU requests was found on Lacuna, so all numbers in this extension will be our own.

Three checks are decisive. The first: at a fixed honest false-positive rate of 1%, a WAGLE- or RMU-based unlearner must yield a clearly higher catch rate than gradient ascent. Otherwise the link between forgetting control and incentive compatibility fails. The second: against an adaptive attacker, randomized audits with deposits must keep retain accuracy near clean levels at an equal or lower total query cost to the defender than full deterministic auditing. Otherwise the randomization adds nothing. The third: honest requesters from small or atypical subgroups must not lose deposits at elevated rates. A failure here would mean the mechanism burdens exactly the people the right to be forgotten is meant to protect. In that case the deposit would have to be replaced by a non-financial stake.