Batched Deletion as a Privacy Shield in Asynchronous Federated Unlearning

In federated learning, many phones or hospitals jointly train one model by sending the server weight updates instead of raw data. When a user later asks to be forgotten, the system must undo that user's influence. The usual fast way is approximate unlearning: compute a reverse update (for example, gradient ascent, which pushes the model to do worse on the deleted data) and apply it. Recent attacks show that this reverse update is itself a near-copy of the deleted data. FUIA treats the difference between the model just before and just after unlearning as a stand-in for the deleted data's gradient and inverts it into near-perfect CIFAR images. DRAUN recovers deleted samples from five optimization-based unlearning algorithms. The act of forgetting becomes the leak. The defenses those papers tried, noise and pruning, cut model accuracy from about 84% to about 63% in FUIA.

Both attacks share a weakness. Their reconstructions get worse as more samples are mixed into the update being inverted, and DRAUN degrades toward batch size 128. This proposal makes that weakness the defense. We describe an asynchronous protocol that holds deletion requests in a buffer and releases them as one securely summed batch. It then removes from that batch every direction the public training trajectory already explains, using a cheap projection built only from global model changes the server has already published. We call this the deletion buffer. The claim to test is that, for a modest and measurable cost in time-to-deletion, this protocol pushes inversion quality toward noise while keeping retained accuracy close to retraining. It needs no noise injection and no synchronized rounds.

Core Claim

Three lines of work each solve one piece. FedBuff shows that a server can ingest client updates asynchronously, without waiting for slow devices, by collecting $K$ of them in a buffer and aggregating them together. That makes cryptographic secure aggregation possible, meaning the server sees only the sum of the buffered updates. FedBuff assumes every update is ordinary training and says nothing about deletion. Subspace based Federated Unlearning (SFU) removes a client in one round. It takes the deleting client's ascent gradient and keeps only the part orthogonal to the span of the other clients' gradients, which keeps clean accuracy within about 1 percentage point on MNIST, against about 47 points for plain ascent (UPGA). SFU has two costs: it needs a synchronized round in which many clients upload dense gradients, and it sends the target's raw ascent vector to the server, which is exactly what FUIA and DRAUN invert. The batch-unlearning literature on centralized models shows that joint, closed-form edits scale to many deletions where sequential edits interfere. Orthogonal Concept Erasure erases 100 concepts in 4.3 seconds, and Forget Many, Forget Right documents collapse under sequential erasure. None of this work considers who observes the edit.

The new piece is the joint design, together with an attack study that pressure-tests it. Deletion requests from different clients accumulate until they cover at least $B$ forget samples. Each deleting client computes an ascent gradient on whatever possibly stale model version it holds. These gradients are securely summed into $g_F$, so the server never sees any single one. The server then applies

$$\Delta_u = -\eta\,(I - U U^\top)\, g_F ,$$

where $\eta$ is a step size and $U$ is an orthonormal basis for the top singular directions of the last $m$ published global model deltas. The basis $U$ is computed from information the server already releases, so it adds no new leakage and no uplink traffic. Its SVD runs on an $m \times d$ matrix with $m$ in the tens, which avoids the dense multi-client SVD that both SFU and the orthogonal-erasure line pay for. The projection plays SFU's role of protecting retained knowledge. Because $U$ spans the trajectory from the stale version up to now, it also strips the part of a stale ascent vector that conflicts with where the model has since moved. This is our answer to the staleness problem for reverse updates, which FedBuff's down-weighting would otherwise turn into under-forgetting.

The claim is falsifiable in two directions. First, the projection could make leakage worse. Removing directions shared with retained data may isolate exactly the sample-specific components an inverter needs. No existing attack targets projection-based unlearning, since DRAUN explicitly assumes optimization-based routines. We will build that attack before trusting the defense. Second, batching might buy nothing over simply hiding a single ascent update among $K-1$ ordinary updates in a FedBuff buffer.

Research Program

The first component is the protocol, built on a FedBuff-style asynchronous simulator with secure aggregation emulated by summation. Its knobs are the deletion batch size $B$, the history length $m$, the projection rank, and the staleness distribution. Device speeds come from LEAF's measured device-performance percentiles (LEAF). For the uplink, deleting clients can compress ascent vectors with a shared-seed random projection. This keeps them summable under secure aggregation, which top-$k$ sparsification with client-specific masks would not. We compare this against ERIS-style shifted compression (ERIS) in the non-secure setting.

The second component is the adversary, and it gets as much effort as the defense. We consider an honest-but-curious server that sees every published global model, knows $U$ and the protocol, and knows which clients requested deletion. We give it three attacks. The first is FUIA's pipeline: separate gradients across successive buffers by estimating the descent component from neighboring releases, take the before/after delta, and invert it with a total-variation prior. The second is DRAUN's surrogate loss with disjoint convex-hull initialization. The third is our extension, which differentiates through the projection: the attacker matches $(I-UU^\top)\nabla_W \mathcal{L}$ of dummy inputs against the observed $\Delta_u$. A stronger variant adds a generative image prior, in the spirit of Gradient Inversion with Generative Image Prior, since such priors are known to undo batch blurring. We also run a membership-inference test and FUIA's deleted-class identification.

The third component is analysis. We give a simple argument for why securely summing $B$ independent per-sample ascent gradients raises reconstruction error as $B$ grows, by appeal to the under-determination of gradient matching that motivated generative priors. We then measure the empirical curve of reconstruction quality against $B$, along with the latency cost: the expected wait to fill the buffer at a given request rate.

Baselines

The naive reference points come first. "Do nothing" leaves the model untouched and lower-bounds forgetting. Retraining from scratch without the deleted data is the gold standard for both forgetting and leakage, since FUIA reports that exact retraining leaves fewer traces than approximate unlearning. Every method below is judged by its gap to retraining on forget accuracy, retained accuracy, and backdoor attack success.

The strongest competitor on unlearning quality is synchronous SFU, run exactly as published, with its SVD coverage threshold tuned in its reported 0.9–0.95 range. Its strongest reported result is the roughly 1 percentage point clean-accuracy drop on MNIST. The file contains no reported CIFAR-10 or CIFAR-100 number for it, so we rerun it ourselves on those datasets. To beat SFU, the deletion buffer must match its retained accuracy within one point and its backdoor removal, while also lowering inversion quality and uplink bytes without a synchronized round. We expect SFU to leak badly because it transmits raw ascent vectors, and we will measure this rather than assume it.

The strongest competitor on privacy is approximate unlearning plus Gaussian noise on the transmitted update, with the noise tuned on a held-out split so that retained accuracy matches ours. FUIA's reported accuracy drop from about 84% to about 63% under pruning and perturbation is the reference failure mode. We beat this baseline if, at equal retained accuracy, our attack SSIM is lower.

The asynchronous competitor is plain FedBuff with $K=10$, its reported setting, using its staleness weighting. The ascent update simply enters the buffer alongside ordinary updates. FedBuff reports being up to 3.3× more efficient than synchronous FL. The earlier Asynchronous Federated Unlearning is the closest prior system, but no reported result was found on Lacuna for it. We will reimplement it from the paper if feasible and otherwise state that it was not compared.

Further reference methods are FedEraser (4× speedup over retraining, 0.61% accuracy difference), FedAU (about 0.001 s unlearning, within 1–2% of retraining), and FATS (membership-inference accuracy near 50%). None of these were evaluated against reconstruction attacks, and we test them under ours. All methods share the same data splits, model, client population, simulated device speeds, and an equal hyperparameter-search budget.

Ablations isolate the two key ingredients. Setting $B=1$ removes batching. Removing the projection leaves only batching. Replacing $U$ with a random subspace of equal rank tests whether the history subspace itself matters. Turning off secure aggregation tests whether summation, not projection, carries the privacy.

Why not just…?

Why not just drop the ascent update into a FedBuff buffer with secure aggregation and stop there? This is the most serious threat, because it is nearly free. Our concern is that FUIA already separates a target's gradient from co-trained clients by contrasting successive rounds. A single large-norm ascent vector among nine ordinary updates may dominate the buffer sum in many directions. The $B=1$ ablation under FUIA-style separation settles the question directly. If this baseline already drives SSIM to the retraining level, our contribution shrinks to the staleness-aware projection for unlearning quality, and we will report it that way.

Why not just add differential-privacy noise to the unlearning update? It gives formal guarantees, which our method does not. But FUIA and DRAUN both report that noise strong enough to stop inversion collapses utility. The accuracy-matched noise baseline will show whether that holds at the operating points we care about. If calibrated noise with a formal guarantee reaches equal SSIM at equal accuracy, practitioners should prefer it, and we will say so.

Why not just shard the model across several aggregators as ERIS does? ERIS reduces reconstructions to noise with as few as two aggregators. However, it assumes the aggregators do not collude and supports no unlearning operations. In the single-server setting studied by FUIA and DRAUN there is no second party to trust, so ERIS addresses a different threat model. We include it only in a secondary experiment where non-colluding aggregators are granted.

Why not just retrain exactly, or use FATS? Exact methods leak little through the update. FATS pays a stability-accuracy penalty and needs synchronous sampling records, and retraining is slow. We report the wall-clock time and accuracy gap of both so that readers can see the price of exactness.

Proposed Experiments

We run CIFAR-10 and CIFAR-100 with Dirichlet non-IID splits and the ResNet-family models used by FUIA and DRAUN, so their attacks transfer unmodified. We add FEMNIST through LEAF, where clients are natural writers, and CelebA, where FedBuff was evaluated and face reconstruction makes leakage visually meaningful. Deletion workloads cover random samples, whole classes (FUIA's class-identification test), and backdoor-trigger samples (SFU's protocol). Metrics are forget accuracy, retained accuracy, and backdoor success rate relative to retraining. Leakage is measured by SSIM, PSNR, membership-inference accuracy, and deleted-class identification rate. Cost is measured by uplink bytes per deletion, server compute time, and time-to-deletion under simulated request rates.

The attack must first be shown to be strong. On unprojected ABL unlearning on CIFAR-10, our DRAUN reimplementation should approach its reported SSIM of 0.6407 and PSNR of 21.11, against the earlier baseline's 0.0038. Otherwise our privacy numbers mean nothing.

The decisive checks are three. First, the curve of best-attack SSIM against $B$ at fixed retained accuracy. Our hypothesis predicts a monotone fall toward the retraining floor by $B$ in the tens. Second, the projection-on versus projection-off comparison at fixed $B$ under the projection-aware attack. If projection raises SSIM, the design is wrong and we drop it. Third, retained accuracy and backdoor removal against synchronous SFU as client staleness grows. The history-subspace projection should hold its gap to retraining where naive staleness down-weighting leaves the backdoor in place.