Error Feedback Remembers: Multi-Round Leakage and Bounded-Memory Compression

Federated learning trains a shared model by having many devices send updates computed on their private data. Two popular ways of shrinking those updates are to keep only the largest coordinates (Top-$k$ sparsification) or only their signs. Both drop information, so they are paired with error feedback: each device keeps a private memory of what it did not send and adds it back to the next update. Error feedback is what makes aggressive compression converge. Its guiding rule, though, is "never throw away a gradient component, only delay it." The privacy literature assumes the opposite rule, that dropping small coordinates is what protects users from attacks that reconstruct their training data from updates. We argue these two assumptions conflict. An attacker who adds up one client's compressed messages over many rounds recovers almost exactly the dense gradient sum that sparsification appeared to hide. The single-round privacy benefit of sparsification is therefore largely an illusion once error feedback is present.

We propose to measure this effect with a multi-round reconstruction attack. We then study a small change to error feedback that restores both privacy and integrity: let the private memory decay geometrically instead of persisting forever. Decay creates a release floor, meaning that persistently small coordinates are never transmitted, so their information is actually destroyed. It also puts a hard, dimension-free cap on the size of every honest message. That cap matters for verifiable aggregation, meaning cryptographic protocols in which clients prove their updates stay within a norm bound so that a malicious client cannot hide an oversized, poisoned update inside encrypted sums. With plain error feedback, honest messages occasionally carry large accumulated backlogs. The verifier must therefore set a loose bound, and that loose bound is exactly the slack an attacker needs.

Core Claim

Write $g_t$ for a client's gradient at round $t$, $e_t$ for its private residual memory, $p_t = g_t + e_{t-1}$ for the error-corrected update, and $m_t = \mathcal{C}(p_t)$ for the compressed message actually sent. Standard error feedback, as in Sparsified SGD with Memory and Error Feedback Fixes SignSGD and other Gradient Compression Schemes, sets $e_t = p_t - m_t$. Starting from $e_0 = 0$, the messages then telescope:

$$\sum_{t=1}^{T} m_t \;=\; \sum_{t=1}^{T} g_t \;-\; e_T .$$

The server knows every global model the gradients were computed at. Over a window of rounds it therefore sees a dense gradient sum, corrupted only by the final residual. When a client's local dataset is fixed across rounds, this sum is a strong signal for gradient-matching inversion.

The fix we study sets $e_t = \beta\,(p_t - m_t)$ with a decay factor $0 < \beta < 1$. For Top-$k$ compression, $\|p - \mathcal{C}(p)\| \le \|p\|$. If each gradient is clipped to norm $G$, induction then gives

$$\|m_t\| \;\le\; \|p_t\| \;\le\; \frac{G}{1-\beta},$$

a bound that depends only on the decay, not on the compression ratio $k/d$. By comparison, standard error-feedback analyses bound the residual by a factor that grows with the compression ratio.

The same recursion yields the release floor. A coordinate that contributes a constant amount $a$ per round accumulates to at most $a/(1-\beta)$. If that stays below the per-round Top-$k$ threshold, the coordinate is never sent.

Our central claim has three parts. Plain error feedback makes multi-round reconstruction nearly as effective as attacking dense gradients. Decayed memory recovers most of the privacy benefit of memoryless Top-$k$ while keeping most of the convergence benefit of error feedback. The dimension-free message bound lets existing norm-checking protocols run with thresholds several times tighter than plain error feedback allows, which shrinks the room available for poisoning.

Relation to Prior Work

The motivating evidence comes from the leakage literature. Deep Leakage from Gradients reconstructs inputs by optimizing dummy data until its gradient matches the observed one. Gradient Inversion Attacks Beyond SGD shows that deterministic optimizer transformations (Adam, momentum) do not protect updates. That paper matches updates instead of gradients and reports up to a 6.5 dB gain in peak signal-to-noise ratio (PSNR, a pixel-level reconstruction score) on ImageNet, remaining effective up to batch size 16. Beyond Inferring Class Representatives shows that watching successive updates exposes client-specific features.

None of these works attacks error-compensated compressed updates. Our attack extends update matching from a single optimizer step to a window of compressed rounds. The Beyond SGD result also constrains our defense. Decay is deterministic, so a defense is credible only if an attacker who simulates the full decayed pipeline still fails. We argue this holds because decay discards information below the floor rather than merely transforming it, and we test this directly.

Sparsification-as-defense work supplies the premise we challenge. User-Level Label Leakage from Gradients in Federated Learning and Concealing Sensitive Samples against Gradient Leakage in Federated Learning treat removal of small coordinates as protective. EdgeDetect reports that importance-aware binarization with encrypted aggregation lowers reconstruction PSNR from 31.7 dB to 15.1 dB on intrusion-detection data, but it uses no residual memory, so it never faces the telescoping problem. ERIS uses shifted compression, which tracks compression error, and reports that reconstruction attacks produce unrecognizable noise. Its protection, however, comes from sharding updates across non-colluding aggregators. We ask what happens when one party sees a client's full message stream.

The formal privacy results in Privacy Amplification via Compression and PREAMBLE rely on data-independent random subsampling. They say nothing about magnitude-based selection with memory, which is the regime studied here.

The optimization side supplies the method. DoubleSqueeze and On Biased Compression for Distributed Learning establish why biased compressors need correction. Contractive error feedback compresses the memory with Count Sketches to save 80–90% of its storage. Because a sketch approximately preserves the residual, we expect it to preserve the telescoping leak as well, and we test that prediction. Clip21 and Clip21-SGD2M apply error feedback to clipping, the latter under differential privacy. They are the natural alternative route to bounded messages, since one can clip the outgoing message and push the excess back into memory. That route still delays rather than discards, so it keeps the leak.

The verification side constrains the design. ACORN verifies $\ell_0$, $\ell_2$ and $\ell_\infty$ bounds inside lattice-based secure aggregation. PINE verifies exact Euclidean bounds over secret-shared vectors at 0.13% communication overhead for $10^7$ dimensions. Both take a threshold as given. We ask where the threshold comes from when honest updates are error-compensated. Clover and CESAR handle the separate problem of aggregating unaligned sparse supports. CESAR explicitly leaves error feedback to future work. We do not solve the alignment problem, and we say so.

Research Program

The first component is the attack. For a target client with a fixed local dataset, the server collects messages $m_t$ and the corresponding global models $w_t$ over a window of $W$ participations. Two attackers will be built.

The summing attacker matches $\sum_t \nabla L(w_t; x)$ against $\sum_t m_t$ using cosine distance, recovers labels analytically as in Beyond SGD, and optionally adds the image prior of Gradient Inversion with Generative Image Prior.

The simulating attacker knows the compressor and $\beta$. It runs the entire compressed pipeline on dummy data, holds the observed Top-$k$ index sets fixed so that the pipeline is differentiable in the values, and matches the full message sequence. This attacker is the one that can defeat deterministic defenses.

We sweep window length, compression ratio, batch size and number of local steps. Multiple local steps are known to degrade inversion, so we report them separately rather than as a single headline number. We also check whether the Loss-Aware Vulnerability Proxy from Foreseeing Reconstruction Quality of Gradient Inversion, which predicts reconstruction quality from curvature of the matching loss, still predicts vulnerability when computed on summed messages.

The second component is decayed error feedback and its analysis. We will prove convergence of decayed error feedback with Top-$k$ to a neighborhood whose size is controlled by $1-\beta$. The proof extends the contractive-compressor analysis of Sparsified SGD with Memory by treating the decayed mass as a bounded bias. We also characterize the release floor per coordinate. Empirically we trace the Pareto curve between test accuracy and reconstruction quality as $\beta$ moves from 0 (memoryless Top-$k$) to 1 (standard error feedback).

The third component is verification slack. For each training method we record, over full training runs, the smallest $\ell_2$ threshold that accepts 99.9% of honest messages. We then run norm-boosted poisoning (scaled model-replacement updates) at that threshold and measure damage. Verification decisions are computed in plaintext. This is sound because ACORN and PINE check exactly these predicates, so cryptographic cost is unchanged by our method. We report cost using ACORN's published figure: a dense 16-bit vector of length 250,000 is validated in under 80 seconds. We add ACORN's $\ell_0$ check to enforce $k$-sparsity. Sparse messages are padded to dense length for verification, which gives up bandwidth savings during the proof. That cost remains open and is shared with prior work.

Baselines

The naive reference points are dense FedAvg updates, which serve as the upper bound on leakage, and memoryless Top-$k$ at the same $k$. Memoryless Top-$k$ is the configuration the sparsification-as-defense literature implicitly evaluates, and it should mark the privacy ceiling and the accuracy floor.

The strongest optimization competitor is standard Top-$k$ with error feedback as in Sparsified SGD with Memory. For CIFAR-10 accuracy of error-feedback Top-$k$ there is no reported result found on Lacuna, so we run it ourselves with an equal tuning budget for learning rate and $k$.

We also run the Count-Sketch error feedback of ConEF to test whether compressing the memory already blocks the leak. We run clip-with-feedback (Clip21-style clipping of the outgoing message, excess returned to memory), which is the strongest alternative for obtaining bounded norms. And we run Clip21-SGD2M with Gaussian noise as the formal differential-privacy competitor. For comparison on the privacy axis, the most relevant reported numbers are EdgeDetect's reconstruction PSNR of 15.1 dB against 31.7 dB undefended on CIC-IDS2017, and Clover's roughly 75% CIFAR-10 accuracy with ResNet-18 under differential privacy.

All methods share the same data splits, client counts, communication budget in transmitted coordinates per round, and training rounds, with an equal hyperparameter search budget for each. The attack gets the same compute budget and the same prior against every method.

Decayed error feedback beats the field if it meets two conditions. First, at matched accuracy within one point of standard error feedback, the simulating attacker's PSNR falls to within 2 dB of memoryless Top-$k$. Second, its accepted-honest threshold is at least a factor of two tighter than standard error feedback's, with correspondingly less poisoning damage.

A key ablation replaces geometric decay with random resets of residual coordinates, tuned to discard the same total residual mass. If random resets protect equally well, the benefit comes from discarding mass in general, not from the magnitude-dependent release floor, and the claim must be revised.

Why not just…?

Why not just drop error feedback? Memoryless Top-$k$ has a real release floor, and the telescoping identity does not apply to it. The biased-compression literature, including DoubleSqueeze and On Biased Compression, documents that it stalls or drifts at high compression. Decay with $\beta = 0$ is exactly this baseline, so the Pareto sweep shows directly whether intermediate $\beta$ buys accuracy at little privacy cost. If the curve is flat, meaning no intermediate $\beta$ beats both endpoints, the proposal reduces to a negative result about error feedback. That result would still be worth publishing.

Why not just add differential-privacy noise, as Clip21-SGD2M does? This is the most serious threat. Calibrated noise gives formal guarantees and also corrupts the summed signal. However, ERIS reports that differential-privacy baselines lose substantial accuracy at useful privacy levels, and Clip21-SGD2M shows plain clipped training fails under heterogeneous data without double momentum. We compare Clip21-SGD2M and decayed error feedback at matched accuracy on the simulating attacker, and we also test decay combined with noise. If noise alone reaches the same reconstruction PSNR at the same accuracy, decay's remaining value is only the verification bound, and we will report it that way.

Why not just clip the outgoing message and feed the excess back? This gives a verifiable norm bound without decay. Because nothing is discarded, the telescoping sum survives and the backlog can grow without limit under sustained large gradients. The experiment is direct: clip-with-feedback should match standard error feedback on reconstruction PSNR while matching decay on threshold tightness. If it also resists the attack, our privacy claim fails.

Why not just use secure aggregation so no individual stream is visible? With many clients this blunts per-client attacks. But unaligned Top-$k$ supports require heavy machinery (Clover's three-server shuffles, CESAR's neighbor coordination), and the aggregate itself still telescopes. With small cohorts or repeated participation, the aggregate can still leak an individual client, which we test by running the summing attacker on cohort sums of 2 to 16 clients. Secure aggregation also leaves the norm-threshold problem untouched, which is why the verification component stands regardless of how this question resolves.

Proposed Experiments

The primary inversion testbed is CIFAR-10 with ResNet-18 and small CNNs, batch sizes 1 to 16. It is complemented by an ImageNet subset matching Beyond SGD's setting, LFW faces following ERIS's reconstruction setup, and CIC-IDS2017 for direct comparison with EdgeDetect's PSNR figures. Reconstruction is scored with PSNR, SSIM and label-recovery accuracy, reported as a function of window length $W$.

Utility is measured as CIFAR-10 test accuracy under IID and Dirichlet non-IID splits at compression ratios of 1% and 0.1%, plus Shakespeare next-character accuracy with an LSTM for vector lengths near ACORN's scale. Verification slack is reported as the 99.9%-acceptance threshold and the accuracy drop under norm-boosted poisoning with 1–5% malicious clients.

Three checks are decisive. The first tests the leak. If summing-attacker PSNR on standard error feedback does not rise toward the dense-gradient level as $W$ grows while memoryless Top-$k$ stays flat, the core premise is wrong and the rest of the proposal falls with it. The second tests whether decay removes information rather than hiding it. If the simulating attacker recovers from decayed error feedback nearly as well as from standard error feedback, the release floor offers no protection, as the Beyond SGD argument would predict. The third tests the verification claim. If standard error feedback's empirical 99.9% threshold is already close to decay's, the loose-bound concern is only theoretical and the verification contribution should be dropped.

References

  1. Sparsified SGD with Memory
  2. Error Feedback Fixes SignSGD and other Gradient Compression Schemes
  3. Deep Leakage from Gradients
  4. Gradient Inversion Attacks Beyond SGD
  5. Beyond Inferring Class Representatives: User-Level Privacy Leakage From Federated Learning
  6. User-Level Label Leakage from Gradients in Federated Learning
  7. Concealing Sensitive Samples against Gradient Leakage in Federated Learning
  8. EdgeDetect: Importance-Aware Gradient Compression with Homomorphic Aggregation for Federated Intrusion Detection
  9. ERIS: Enhancing Privacy and Communication Efficiency in Serverless Federated Learning
  10. Privacy Amplification via Compression: Achieving the Optimal Privacy-Accuracy-Communication Trade-off in Distributed Mean Estimation
  11. PREAMBLE: Private and Efficient Aggregation via Block Sparse Vectors
  12. DoubleSqueeze: Parallel Stochastic Gradient Descent with Double-pass Error-Compensated Compression
  13. On Biased Compression for Distributed Learning
  14. Contractive error feedback for gradient compression
  15. Clip21: Error Feedback for Gradient Clipping
  16. Double Momentum and Error Feedback for Clipping with Fast Rates and Differential Privacy
  17. ACORN: Input Validation for Secure Aggregation
  18. PINE: Efficient Verification of a Euclidean Norm Bound of a Secret-Shared Vector
  19. Harnessing Sparsification in Federated Learning: A Secure, Efficient, and Differentially Private Realization
  20. Communication-Efficient Secure Aggregation in Decentralized Learning
  21. Gradient Inversion with Generative Image Prior
  22. Foreseeing Reconstruction Quality of Gradient Inversion: An Optimization Perspective