The Forgetting–Leakage Tradeoff in Federated Unlearning

When a client in federated learning (many devices jointly training one model while keeping their raw data local) asks to have its data deleted, someone has to send a model update that removes that data's influence. Recent attacks show these deletion updates can be inverted to reconstruct the very images the client wanted erased. This proposal argues the problem is structural, not a bug in particular methods. To make a model worse on an example, a first-order update must point along that example's gradient. That gradient is exactly the signal gradient-inversion attacks exploit. So we expect deeper forgetting to cost more leakage. Methods that seem to escape the tradeoff may be doing so by forgetting less than benchmarks report.

We will build an evaluation that scores federated unlearning methods on two axes together. The first is how deeply they forget, measured with per-sample membership tests and relearning time. The second is how well the strongest available attacker reconstructs the deleted data from the messages the protocol actually exposes. We then test whether a true frontier exists. We also ask where current methods and defenses sit relative to it, and whether moving the deletion computation to the client and hiding it inside secure aggregation (summing client updates so the server only sees the total) shifts the frontier rather than sliding along it.

Core Claim

Let $W$ be the global weights before unlearning, $\Delta$ the deletion update, and $\ell(x;W)$ the loss on a deleted example $x$. To first order the loss change is

$$\ell(x; W+\Delta) - \ell(x; W) \approx \langle \nabla_W \ell(x;W), \Delta \rangle .$$

Raising the loss on $x$ by a target amount therefore forces $\Delta$ to carry a component of size at least that amount divided by $\|\nabla_W \ell(x;W)\|$ along the per-sample gradient. This projection is the quantity that cosine-matching inversion attacks recover. Our claim is empirical but sharp. Across federated unlearning methods, hyperparameters, and defenses, reconstruction fidelity of the exposed update rises monotonically with forgetting depth. A method lies below this frontier, forgetting deeply while leaking little, only if the exposed message is decoupled from the applied update. Such decoupling is possible through aggregation with other clients' updates. It is not possible through rotation or projection of a message that the receiver must also apply.

What Prior Work Establishes and Leaves Open

Two papers motivate the claim by showing deletion updates leak. DRAUN is an optimization-based attack by an honest-but-curious server. It reconstructs deleted images without knowing the client's unlearning loss, by searching over a family of surrogate losses that interpolates gradient ascent and gradient difference. Verifiably Forgotten? trains a decoder network that maps gradient-difference "proofs of unlearning" back to pixels. It also proposes Orthogonal Obfuscation, a norm-preserving rotation of the proof. Both papers measure attack success in isolation and never ask how much each attacked method actually forgot. Without that axis, a defense that lowers reconstruction cannot be distinguished from one that simply weakens deletion.

Two other papers supply methods we must evaluate. Subspace based Federated Unlearning (SFU) has the target client perform gradient ascent. The server then projects that update away from the remaining clients' gradient subspace. SFU loses only about 1 percentage point of clean MNIST accuracy versus about 47 for unprojected ascent. However, the file describes the projection as server-side, which means an honest-but-curious server sees the raw ascent update. SFU's projection therefore offers no protection against that adversary by construction. It may still matter against other clients who only see the change in the global model.

Concealing Sensitive Samples (DCS²) defends ordinary training by synthesizing decoy samples with matching gradients. It is the strongest structured defense in the file, but it was never applied to ascent-style deletion updates.

The evaluation side constrains how forgetting must be measured. The Unlearning Mirage shows output-level probes can pass while knowledge remains recoverable. LLM Unlearning Reveals a Stronger-Than-Expected Coreset Effect shows that unlearning on 5% of a forget set matches full-set benchmark scores. Both findings warn that "forgetting depth" measured by aggregate metrics can be inflated. Deep Unlearn supplies the per-sample Unlearning Likelihood Ratio Attack (U-LIRA) and shows approximate methods are extremely hyperparameter-sensitive. This sensitivity is why we sweep hyperparameters and report frontiers rather than single points. ERASURE supplies relearning time and modular evaluators. PrivUB finds, in centralized settings, that differencing pre- and post-unlearning checkpoints exposes forgotten data and raises retain-set membership risk. We carry that "discrepancy" observation into federated topologies, where different parties see different messages.

Research Program

The first component is a threat-model-explicit harness. Each federated unlearning protocol is described by the messages exposed to two adversaries. The server sees individual client messages unless secure aggregation is used. A non-target client sees only successive global models. For each protocol we log every exposed message.

The second component is a two-axis measurement. Forgetting depth is per-sample U-LIRA advantage on the deleted examples, relative to a model retrained without the target client. It is complemented by relearning time and by a coreset probe. In the coreset probe, we delete a client's data using only a 5% subset of it and check whether held-out members of the deleted set are forgotten. This tests whether a method's apparent depth reflects removal of the target client's data or only suppression of the most influential samples. Leakage is the best reconstruction fidelity, measured by SSIM, PSNR, and LPIPS, that any attacker in a fixed suite achieves on the deleted examples. The suite contains DRAUN, IGF, and adaptive variants told the defense's exact transformation.

The third component is a frontier analysis. We sweep each method's hyperparameters and noise levels, plot leakage against depth, and fit the upper envelope. We then test whether the inner-product quantity in the core equation predicts reconstruction fidelity across all points.

The fourth component is a constructive arm. It tests the decoupling prediction with a client-side variant of SFU. The server broadcasts the retain subspace, the target client projects locally, and the projected update is submitted under secure aggregation alongside ordinary updates from other clients in the same round. This arm also measures the cost of broadcasting the retain subspace to the privacy of the remaining clients. That cost is the retained-client leakage question no current federated unlearning paper evaluates.

Baselines

The naive reference is doing nothing. The target client simply stops participating and training continues, as the federated unlearning survey examined. That survey reports 87.0% accuracy on a seen client's training set versus 78.7% on test data for a vision transformer on CIFAR-100. We expect this point to sit at near-zero depth and near-zero direct leakage, anchoring the bottom of the frontier. The upper reference is retraining among the remaining clients. It defines zero U-LIRA advantage. Its leakage through global-model differencing, the federated analogue of PrivUB's discrepancy trap, is measured rather than assumed to be zero.

The strongest unlearning competitor is SFU, run with its published coverage coefficient range of 0.9 to 0.95 under both IID and Dirichlet non-IID partitions. Alongside it we run Negative Gradient Plus (NG+) and Masked Small Gradients (MSG), the robust choices recommended by Deep Unlearn, adapted to the federated setting. Every method receives the same hyperparameter-search budget, selected on forgetting depth alone so that leakage is not tuned away, plus the same rounds, clients, and model.

The strongest attacker is DRAUN. On CIFAR-10 under ABL unlearning, its paper reports SSIM 0.6407 and PSNR 21.11, versus SSIM 0.0038 for the Hu et al. baseline. For IGF, the file reports an 88% MSE reduction and 33% LPIPS improvement relative to the GIAMU attack. It gives no absolute numbers, and no reported result was found on Lacuna for IGF absolute SSIM on CIFAR-10. We first reproduce DRAUN's CIFAR-10 number at batch sizes 2 and 4 before using it as the leakage measure.

The defensive baselines are Gaussian noise on the deletion update, Orthogonal Obfuscation, and DCS² adapted to ascent updates. Each is evaluated against both a non-adaptive and an adaptive attacker. The key ablation isolates decoupling. It compares server-side SFU, client-side SFU without secure aggregation, and client-side SFU with secure aggregation, holding everything else fixed. A method "beats" the frontier if it reaches retrain-level U-LIRA advantage while keeping best-attacker SSIM below the level DCS² achieves in ordinary training (reported as 0.15 on CIFAR-10). It must do so without failing the coreset probe.

Why not just…?

Why not just add differential-privacy noise to the deletion update? Noise attacks the leakage axis by shrinking exactly the gradient component the core equation says forgetting needs. We therefore predict it moves methods along the frontier, not below it. DRAUN reports that noise strong enough to hurt reconstruction caused a large drop in global accuracy. DCS² reports Soteria-style perturbation at 52.06% TinyImageNet accuracy versus 65.68% for its structured method. Neither measured forgetting depth under noise. Our noise sweep is that measurement, and if noise reaches retrain-level depth with low leakage the core claim is wrong.

Why not just use secure aggregation and stop there? This is the real threat to the proposal, and we take it seriously by building it as the constructive arm. Two obstacles exist. First, SFU-style methods need the server to see the target update to project it, so secure aggregation forces the computation client-side. Second, if the target client is the only one changing the global model in a deletion round, a non-target client differencing successive global models recovers the update anyway. The experiment decides whether mixing the deletion with ordinary updates in the same round dilutes it enough. GIAS's success at batch size 32 in Gradient Inversion with Generative Image Prior suggests dilution by a few clients may not suffice. DRAUN's degradation at batch size 128 suggests larger mixing could.

Why not just benchmark with membership inference, as Deep Unlearn and ERASURE do? Membership tests are our depth axis, so we keep them. They cannot see the leakage axis, however, because a method can pass U-LIRA while its exposed update is fully invertible. Our measurements report whether membership rankings and reconstruction rankings of methods agree. Disagreement is the evidence that single-axis benchmarks mislead.

Why not just run DRAUN against more unlearning methods? That yields a leaderboard of leakage numbers that cannot separate a good defense from a weak deletion. The frontier, the coreset probe, and the adaptive attackers are what turn attack results into an evaluation of unlearning.

Proposed Experiments

Experiments use MNIST, CIFAR-10, CIFAR-100, and FEMNIST, with ConvNet, ResNet20, and ResNet18 backbones. Clients number 10 to 100 under Dirichlet non-IID splits, and deletion batch sizes are 2, 4, 32, and 128.

Three checks are decisive. The first tests the frontier itself. Across all method, hyperparameter, and noise points, does best-attacker SSIM increase with U-LIRA depth? Does the measured inner product between the update and per-sample gradients explain most of that relationship? A flat or negative relationship falsifies the core claim.

The second check targets the rotation defenses. When Orthogonal Obfuscation's rotated message is the update that gets applied, does depth collapse? When only the proof is rotated, does the proof still certify anything beyond the update's norm? We predict yes to the first question and no to the second. That outcome would show such proofs verify deletion only nominally.

The third check is decoupling. Does client-side SFU under secure aggregation fall measurably below the frontier for the server adversary? How much leakage remains for the global-model-differencing adversary as the number of co-aggregated clients grows? How much membership advantage do the remaining clients lose from the broadcast subspace? A clean result is a dilution curve showing how many co-aggregated clients are needed before DRAUN's SSIM drops below 0.15. That curve would be the first deployable guidance on safe federated deletion.