Exact Unlearning via Quantized Sufficient Statistics

AI summary

Overview

Research area: machine unlearning and model serving, at the intersection of quantization-based model representations, data structures for additive statistics, and privacy regulation compliance. Technical level: Advanced. Scope: the paper introduces Quantized Sufficient Statistics (QSS), a model design that reduces exact deletion requests to constant-time arithmetic operations by separating a frozen "schema" from mutable, sum-decomposable "content."

What This Paper Is About

Exact unlearning requires that a deployed model behave identically to one retrained from scratch without a deleted data point. Existing general-purpose methods such as SISA achieve this by splitting data into disjoint shards and retraining the affected shard, but every deletion invalidates part of the model, and smaller shards mean less data per sub-model. The paper's goal is to break that coupling: instead of retraining after a deletion, QSS stores local prediction corrections as additive statistics, so deleting an example is subtraction rather than optimization.

Key Contributions

1. Schema–content separation for exact unlearning. A small, frozen schema (a base model g plus a Residual Quantization codebook) captures global structure, while all mutable prediction information lives in sum-decomposable accumulators (residual target sums, cell counts, and co-occurrence counts). Label or instance deletion then becomes a constant-time arithmetic decrement, independent of dataset size n, and is identical to rebuilding for the stated neighboring relation.
2. Redundant schemas for amortized O(1) deletion. Maintaining p independent instances with their own random retained subsets reduces the probability that all instances must be rebuilt simultaneously to ρ^p, with the paper stating zero accuracy degradation because each instance's accumulators aggregate all of D.
3. Two explicit unlearning guarantees. QSS-L exactly removes a label while retaining the unlabelled input; QSS-E exactly removes both input and label by learning the schema without deletable examples. A third mode, QSS-DP, adds Gaussian noise to published cell means to provide (ε, δ)-label differential privacy.
4. An architecture that inverts the usual role of quantization. Prior work such as QUAIL, LUNAR, and OEU treats quantization as an obstacle to unlearning; here quantization is the architecture that makes exact deletion tractable, and a co-occurrence correction in RQA.Materialize avoids exponential fragmentation across residual levels.

Main Findings

• Accuracy is competitive on low-class-count tasks. Across 15 vision, text, and tabular datasets at ρ = 0.5%, QSS-L is within 2 percentage points of SISA on 11 tasks. On 13 low-k datasets, fixed QSS-L exceeds SISA accuracy on 4 (MNIST, SST-2, AG News, and KDD Cup) and trails by ≤ 2 pp on 7 more.
• Deletion is much faster. QSS-L provides 4–483× lower expected deletion latency on the low-class-count tasks where a compact schema is effective, with every latency figure including the rare rebuild event. On Jigsaw (n = 1.4M), QSS-L deletes in 0.2 s expected versus SISA's 109 s (483×).
• Exactness is verified empirically, not just proved. Deleting 100 points across nine datasets spanning all three modalities gives differences of exactly 0.0, i.e. bitwise identical predictions for the relevant fixed-schema relation. A targeted QSS-L audit on AG News obtains the same result for batches of 1, 10, 100, and 1,000 label deletions. Deleting up to 50% of ImageNet (640K points) also yields bitwise-identical predictions, with only 0.25 pp accuracy loss from reduced labels.
• Membership leakage is low. A LiRA attack (64 shadow models, 1000 audit points) achieves AUC ≈ 0.52 on CelebA, even at ε = ∞, and QSS-DP preserves most accuracy at ε ≥ 1.
• High-class-count tasks are the weak point. At ρ = 0.5%, QSS lags SISA on ImageNet (k = 1,000, −15.6 pp) and Covertype (k = 7, −10.7 pp). Level-0 cell purity predicts this: MNIST achieves 96.6% purity (+3.8 pp over SISA) while Covertype reaches only 63.1%. The gap narrows with ρ: Covertype shrinks to −5 pp at ρ = 5%.
• A small retained fraction is enough. At ρ = 0.5%, n° ranges from 256 (SST-2) to 41K (HIGGS), and most accumulators occupy small amounts of memory. All accumulators occupy ≤ 51 MB even for ImageNet; Adult is 1 MB, Covertype 3.5 MB, AG News 5.1 MB, and CelebA 20 MB.
• Rebuild risk is controllable. With p independent instances, a synchronous rebuild occurs with probability ρ^p, and a batch of simultaneous deletions invalidates all instances with probability (1 − (1 − ρ)^B)^p. Exceeding a 1% invalidation probability at ρ = 0.5%, p = 3 requires B > 1,300. Rebuild overhead is at most p·H_p times the offline optimal (5.5× for p = 3).
• Depth has diminishing returns. Residual variance decays geometrically across RQ levels, and MSE decays as (1 − γ)^ℓ if each level explains at least γ of variance. Excess risk scales as b/n rather than b^ℓ/n, leading to the practical rule width > > depth.
• Rebuild cost limits some speedups. For HIGGS (n = 11M), the expected cost is ≈ 18 s versus SISA's 114 s; the paper notes the speedup is limited to 6× in one place and 67× in another, and states the ρ·t_rebuild term scales with n.
• Batching is cheap. Deleting B points requires O(Bℓ²) count decrements followed by a single O(ℓ²b²k) re-materialization, giving an amortized cost of O(ℓ² + ℓ²b²k/B) per deletion.

Methodology in Plain English

The authors split the training data into two parts. A very small random subset (ρ = n°/n = 0.5% throughout) is "retained": it trains a frozen base model and a Residual Quantization codebook that assigns similar inputs to the same bins. The remaining 99.5% is "content": its labels are never used to train the schema, only to fill additive tables indexed by the codebook's bins. Those tables hold three quantities per code cell — sums of prediction residuals, counts, and co-occurrence counts between levels.

Prediction for a query sums the per-cell means along the query's code path and adds the base model's output, blended by a cross-validated weight α (with α = 0 recovering the base model exactly, which guarantees QSS ≥ D°-only). Because the tables are pure sums, removing an example means subtracting its own contributions, and recomputing the same table totals from what remains gives exactly the state a rebuild would produce. The co-occurrence counts let each level's means be recovered by subtracting earlier levels' contributions, so the structure does not need to track every combination of bin assignments jointly.

For redundancy, the system keeps p independent instances, each with its own random retained subset and its own base model and codebook, but each accumulating over all of the data. A deletion usually takes the arithmetic fast path with probability 1 − ρ; only if it touches the retained schema subset does a full rebuild become necessary, and a synchronous rebuild requires all p instances to be invalidated at once.

Why This Matters

Unlearning is a legal and operational requirement: privacy regulations such as the EU's GDPR and California's CCPA mandate deleting the effect of specific training instances, and security concerns include removing poisoned, biased, or outdated data. The paper argues that exactness matters because it is defined relative to the information named by the request, and that SISA's design forces a tradeoff between deletion availability and per-model accuracy that QSS avoids.

Real-world applications:

• Compliance workflows for models trained on user data, where deletion requests must be honored without full retraining pipelines.
• Removing poisoned or mislabeled training examples from deployed security- and safety-sensitive classifiers.
• Retracting annotations, outcomes, or responses when keeping the unlabelled input is permitted (the QSS-L setting).
• Publishing aggregate statistics with (ε, δ)-label differential privacy while retaining a deletion path (the QSS-DP setting).

Industry relevance: the authors are affiliated with Meta Platforms, Inc., and the paper frames the work around deployed predictors, steady-state cost rates for deployment sizing, and serving during rebuild windows. Unlike SISA's S pipelines, QSS is a single model with a sidecar data structure, which the authors present as an architectural advantage.

Future Directions

• Improving high-class-count performance. The authors identify cell purity as the predictor of the gap and note that the codebook partitions embedding space without regard to class boundaries. Whether a class-aware or otherwise richer partition closes the ImageNet (−15.6 pp) and Covertype (−10.7 pp) gaps is left open.
• Schema capacity as a design axis. The submitted linear and one-hidden-layer heads are described as operating points, not method restrictions. On Covertype a three-layer head gains little over linear at ρ = 0.5% but gains 10.74 pp at ρ = 5%, while training time rises from 1.29 to 14.65 seconds — so the benefit is dataset-dependent and the joint capacity–schema sweep is reported in an appendix.
• Composing with analytic sufficient-statistic updates. The paper positions ridge/ACU-style rank-one downdates as natural complements to QSS, with matched comparisons and different state/update costs given in an appendix, leaving the best combination for a given task unresolved.
• Rebuild cost at very large n. Because the ρ·t_rebuild term scales with n, HIGGS-sized datasets (n = 11M) limit the achievable speedup. Reducing rebuild cost or further lowering ρ are natural next steps.

Target Audience

Machine learning researchers and engineers working on machine unlearning, privacy-preserving ML, and retrieval- or quantization-based architectures, particularly those who need exact rather than approximate deletion guarantees. It is also relevant to practitioners sizing deletion infrastructure for deployed models, and to readers familiar with SISA who want to understand where quantized sufficient statistics close the gap and where they do not. The material is dense — proofs, complexity tables, and a 15-dataset empirical study — so some background in quantization, gradient boosting, and differential privacy is helpful.

Authors’ abstract

Exact unlearning requires a deployed predictor to match one rebuilt without the information named by a deletion request. Existing general-purpose exact methods localize retraining through disjoint shards, but every request still invalidates a model, and smaller shards reduce the data available to each constituent predictor. We introduce Quantized Sufficient Statistics (QSS), which separates a small frozen schema from mutable, sum-decomposable content. The schema learns global structure; the content stores local prediction corrections as additive statistics indexed by quantized regions. Deleting content is therefore exact subtraction rather than optimization. We distinguish two guarantees: QSS-L exactly removes a label while retaining the unlabelled input, whereas QSS-E exactly removes both input and label by learning the schema without deletable examples. A deletion takes the arithmetic fast path with probability $1-ρ$ and triggers a full rebuild with probability $ρ$; all reported expected latencies include both events. Across 15 vision, text, and tabular datasets at $ρ=0.5\%$, QSS-L is within 2 percentage points of SISA on 11 tasks and provides 4--483$\times$ lower expected deletion latency on the low-class-count tasks where a compact schema is effective. QSS-E quantifies the additional accuracy cost of removing every trace of an input.