What Federated Unlearning Must Remember, and What Colluding Servers Can Steal

Federated unlearning means removing one client's contribution from a model trained jointly by many clients. The current practical approach keeps a history of every client's past updates, so that the server can later subtract one client's influence without retraining everything. Undoing that influence carelessly damages the model for everyone else, a failure usually called catastrophic forgetting. The same stored history is also a liability. Past gradients (the per-client update directions) can be inverted to reconstruct a client's raw data. The best existing defense, Starfish (Privacy-Preserving Federated Unlearning with Certified Client Removal), splits that history into random secret shares held by two servers and runs the rollback inside a two-party cryptographic protocol. Its guarantee is all-or-nothing. If the two servers collude, they recombine the shares, recover every stored gradient, and can reconstruct client data.

This note argues that the right question is not only how to split the stored history but how much of it to store at all. Whatever the servers keep in order to unlearn accurately is exactly what a colluding coalition can steal. There is therefore a trade-off, in the spirit of information-theoretic storage–retrieval limits, between how faithfully a client can later be removed and how much the stored record reveals about that client. Our specific bet concerns which gradient directions each side needs. The directions that matter most for accurate removal are the ones where the loss surface is flattest. Those are not the large-magnitude directions that gradient-inversion attacks exploit. If this holds, a small curvature-aligned sketch of each client's contribution can support near-exact rollback. Even under full collusion, that sketch would reveal much less than the full history does.

Core Claim

In a local quadratic approximation, removing client $k$ corresponds to the parameter correction $\Delta_k \approx H^{-1} g_k$. Here $g_k$ is client $k$'s accumulated contribution to training and $H$ is the Hessian (the curvature matrix) of the loss on the remaining clients. Suppose the servers store only the projection $P_U g_k$ of the contribution onto an $r$-dimensional subspace $U$. The removal error is then

$$e_k(U) = \big\| H^{-1}(I - P_U)\, g_k \big\|.$$

If $U$ spans the $r$ lowest-curvature eigenvectors of $H$, with eigenvalues sorted so that $\lambda_1 \le \dots \le \lambda_d$, this gives $e_k \le \|g_k\| / \lambda_{r+1}$. The inverse Hessian amplifies flat directions and shrinks steep ones, which is why the bound takes this form. Removal fidelity therefore depends on the flat directions.

Gradient inversion depends on something different. It mostly needs the high-energy components of $g_k$, which tend to align with steep directions.

This leads to two predictions. First, a curvature-aligned sketch should give a markedly better trade-off between removal error and leakage than either the full history or a magnitude-based compressed history. Second, the subspace $U$ is computed from the shared global model rather than from any client's data, so publishing it costs little privacy.

The claim is deliberately falsifiable. If flat and high-energy directions turn out to coincide in real networks, the idea fails, and the experiments below are designed to show that.

Relation to Prior Work

Three lines of work motivate the proposal. Starfish supplies the protocol we build on: two-server additive sharing, secure selection of influential rounds, and quasi-Newton rollback via secure L-BFGS. It treats trust as binary and never asks what the stored record itself reveals. We keep its machinery and change what enters it.

Privacy-Preserving Distributed Processing: Metrics, Bounds, and Algorithms proves that leakage has a floor set by what the computation's output reveals. Topology-Dependent Privacy Bound For Decentralized Federated Learning shows leakage degrading gradually with the size of the honest subgroup of nodes. Both treat privacy as a quantity that degrades by degree, which is the view we adopt. Both analyze forward aggregation only, never unlearning.

The information-theoretic retrieval literature supplies the lens rather than a method. Asymmetric Leaky Private Information Retrieval trades a leakage budget against download cost. Two-Level Private Information Retrieval shows that giving data of different sensitivity different collusion thresholds yields real efficiency gains. The storage–retrieval trade-off papers (Tian et al. (2019), Guo et al. (2020)) establish that minimizing what is stored has a quantifiable price. Our analogue replaces "download cost" with "removal error" and "file" with "client contribution." We borrow from two-level retrieval the idea of protecting the sketch under a higher collusion threshold than any auxiliary data.

Two papers constrain the design. An Illusion of Unlearning? Assessing Machine Unlearning Through Internal Representations shows that apparent forgetting is often recoverable by probing or brief fine-tuning. We therefore evaluate removal by recoverability and by distance to a retrained model, not by forget-set accuracy alone. Certified Minimax Unlearning with Generalization Rates and Deletion Capacity gives the only formal deletion-capacity result in the file, and it holds under strong convexity. Our quadratic argument inherits that limitation. We treat it as a design heuristic to be tested in non-convex networks, not as a guarantee.

Representation-level methods such as RMU from The WMDP Benchmark and REMISVFU avoid stored history altogether. They address concept or party removal rather than certified client rollback, so they are comparison points rather than competitors on this question.

Research Program

We first estimate, during ordinary federated training, a low-curvature subspace $U_t$ of the global model at each round $t$. The estimate is computed publicly from the global model, for example with damped Lanczos iterations on a small public or synthetic batch, or from the curvature pairs Starfish's L-BFGS already maintains. The cost is amortized over training.

Each client then sends a sketch $P_{U_t} g_{k,t}$ in place of its full update history. It shares the sketch across $N$ servers using threshold sharing, in which any $T$ servers can reconstruct and fewer see only randomness. With $N=2$ and $T=2$ this reduces exactly to Starfish's additive setting.

Unlearning reuses Starfish's secure round selection and quasi-Newton correction, operating on the sketches. It is followed by a short correction step on the remaining clients to limit forgetting.

The analysis has two parts. On the unlearning side, we measure removal error as a function of sketch rank $r$ and relate it empirically to the tail-curvature bound above. On the leakage side, we give the colluding coalition exactly what it would hold, meaning the full history for Starfish or the reconstructed sketches for ours. We then run the strongest inversion attack we can build: Deep Leakage from Gradient adapted to projected gradients, with the coalition also knowing $U_t$ and the global models. Leakage is reported as reconstruction quality (PSNR and SSIM), label-recovery rate, and a variational lower bound on the mutual information between the stored record and the client's data.

Plotting removal error against leakage traces an empirical frontier. The gap between our frontier and the others is the object of study.

Baselines

The naive reference points are retraining from scratch without the client, which defines zero removal error and sets the cost ceiling, and doing nothing, which leaves the client's influence in place.

The strongest existing method is Starfish with full stored histories and all of its optimizations enabled. We run it on identical client splits, models, and training schedules. It gets the same round-selection fraction the file reports, about 60% of rounds, and the same number of correction steps. We found no reported result on Lacuna for Starfish's unlearned-model accuracy or certified distance on MNIST, Fashion-MNIST, or CIFAR-10, so we reproduce it ourselves under our budget. The only nearby figure in the file is REMISVFU's roughly 2.5-point accuracy drop against a retrained model, and that comes from a different, vertical setting, so we use it only as a loose sanity scale.

Beating Starfish means two things. At full collusion, our stored record must yield substantially worse inversions than Starfish's; we target at least a halving of reconstruction SSIM. At the same time, our gap in retained-client accuracy and our parameter distance to the retrained model must lie within Starfish's seed-to-seed variation.

The key ablations isolate curvature alignment. Each keeps storage matched at rank $r$ and replaces the curvature-aligned sketch with one of two alternatives. The first is a random projection. The second is top-$k$ magnitude sparsification, the standard gradient compression method. Both get the same tuning budget for $r$ or $k$ and the same correction steps.

Why not just…?

Why not just use Starfish with more servers and a higher collusion threshold? This buys protection up to the threshold but leaves the same all-or-nothing cliff above it: a coalition large enough recovers every gradient. It also raises the cost of the secure protocol in proportion to stored volume. Our proposal is complementary and composes with higher thresholds. The experiment reports leakage at full collusion, where threshold choice is irrelevant, and protocol communication per unlearning request, where storing less should help.

Why not just add differential-privacy noise to the stored updates? This is the real threat. Noise gives a formal guarantee that survives any collusion, as Pencil's gradient perturbation does in forward training (Pencil). However, Privacy-Preserving Distributed Processing shows that noise paid for collusion tolerance directly costs utility. Certified Minimax Unlearning shows that noise-based deletion capacity scales worse, $O(n/d^{1/2})$ against $O(n/d^{1/4})$. We settle the question empirically: noise-added full histories become a curve on the same removal-error versus leakage plot, swept over noise scale. If noise dominates our sketch at every leakage level, we will say so and abandon the sketch in favor of noise. We also test noise added to the sketch, since the two may combine.

Why not just compress gradients the usual way and store less? Magnitude-based compression is cheap and already reduces what is stored. Our hypothesis predicts it is the wrong compression: it keeps high-energy components, which are what inversion exploits, and discards flat components, which are what rollback needs. The matched-storage ablation tests this directly. If top-$k$ compression reaches the same frontier as curvature alignment, the curvature idea is unnecessary and the contribution reduces to "store less."

Why not just store nothing and use retain-free or representation-level unlearning? Methods such as JiT (An Information Theoretic Approach to Machine Unlearning) or anchor-vector misdirection remove nothing that colluders could steal. The file, however, reports that JiT is hypersensitive to hyperparameters. The Illusion paper shows such forgetting is often recoverable. We include JiT as a zero-storage point on the frontier, evaluated with the same probing and relearning tests.

Proposed Experiments

We use the benchmarks Starfish uses: MNIST, Fashion-MNIST, and CIFAR-10. Data is split into non-identically distributed federated partitions of 20 to 100 clients, with the small CNNs Starfish evaluated and ResNet-18 on CIFAR-10 as a harder, more non-convex case. Unlearning requests remove one client, then up to 10% of clients in sequence, to measure how removal error accumulates.

The metrics cover four aspects. Removal fidelity is measured as parameter distance and prediction disagreement against the retrained model, together with membership-inference advantage on the removed client. Catastrophic forgetting is measured as retained-client accuracy relative to retraining. Recoverability is measured by linear-probe accuracy on the removed client's labels and by relearning speed after brief fine-tuning. Leakage under full collusion is measured by the inversion metrics above.

The decisive check has three possible outcomes. It asks whether, at matched storage, the curvature-aligned sketch lies strictly below the random-projection, top-$k$, and noise-added curves on the removal-error versus leakage plane, across all three datasets and both architectures. The first outcome is that it does. That is the central result, together with evidence that the removal error follows the tail-curvature bound as $r$ varies. The second outcome is that the flat and high-energy subspaces overlap heavily, measured by principal angles between them. The mechanism is then false in practice, and we report the frontier comparison as a negative result on sketch-based storage. The third outcome is that noise-added histories dominate. The recommendation is then noise over secret sharing for stored unlearning state, which is itself a useful answer to Starfish's open question about behavior under partial collusion.