Exact Unlearning via Quantized Sufficient Statistics

Exact machine unlearning guarantees that after deleting a user's data, the model produces the same predictions as if it had never trained on that data in the first place. SISA, the most widely adopted exact method, partitions data into disjoint shards, with necessary $O(n/S)$ retraining cycle for each deletion, and it cannot lower this cost through redundancy, because overlapping shards only multiply the damage. We introduce Quantized Sufficient Statistics (QSS), a non-parametric framework that pairs frozen prediction heads (the schema, trained on a small random subset $\mathcal{D}^{\circ}$) with mutable sum-decomposable accumulators indexed by Residual Quantization codes over the complementary data (the content, $\mathcal{D} \setminus \mathcal{D}^{\circ}$). With probability $1{-}\rho$ (where $\rho = |\mathcal{D}^{\circ}|/n$, typically ${\leq}\,1\%$), deletion reduces to a constant-time arithmetic update independent of dataset size $n$; with probability $\rho$, a full rebuild is required. Maintaining $p$ independent schemas suppresses the synchronous rebuild probability to $\rho^p$, and because every schema aggregates all data, decommissioning incurs zero accuracy loss. Across 15 datasets ($n \geq 50$K) spanning vision, text, and tabular modalities at $\rho{=}0.5\%$, QSS matches or exceeds SISA accuracy on 5 datasets, trails by ${\leq}\,2$\,pp on 7 more, and by $3$--$16$\,pp on 3 datasets where high class count or large rebuild cost limits performance, while delivering 3--483$\times$ faster median expected deletion (e.g., 0.2 s expected vs.109 s on Jigsaw, $n{=}1.4$M).