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 seen that data in the first place. SISA, the current state-of-the-art approach, 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 5 more, and by 3–11 pp on 3 datasets where high class count or large rebuild cost limits performance, while delivering 3–645$\times$ faster median expected deletion (e.g., 0.2 s expected vs. 109 s on Jigsaw, $n=1.4$M).