Research map / Architectures and efficiency / Pruning and efficient tuning

Exact Unlearning via Quantized Sufficient Statistics

NeurIPS 2026 · Architectures and efficiency › Pruning and efficient tuning · approach: Structured network pruning

Read the paperCheck your idea against 108,967 papers

AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.

Proposes Quantized Sufficient Statistics (QSS), which pairs a frozen schema (base model plus residual-quantization codebook trained on a 0.5% retained subset) with sum-decomposable accumulators, so most deletions become exact arithmetic updates rather than retraining.

Problem

Exact machine unlearning requires the deployed model to match one retrained without the deleted data; SISA's shard-based retraining costs O(n/S) per deletion and cannot reduce invalidation through redundancy.

Approach

Separate a small frozen schema (base model and RQ codebook trained on a small retained subset) from mutable content (co-occurrence-aware sum statistics over quantized cells), so deleting content is exact subtraction; use p independent schema instances so that a full rebuild is needed only when all p are invalidated (probability rho^p).

Key results

• QSS-L is within 2 percentage points of SISA on 11 of 15 tasks at rho=0.5% and exceeds SISA on 4 of 13 low-k datasets (MNIST, SST-2, AG News, KDD Cup).
• On Jigsaw (n=1.4M), QSS-L expected deletion latency is 0.2 s vs SISA's 109 s (483x speedup).
• Deleting 100 points yields bitwise-identical predictions to rebuilt statistics across nine datasets; LiRA AUC about 0.52 on CelebA even at epsilon=infinity.

Surprising findings

• On ImageNet (k=1000) QSS-L lags SISA by 15.6 pp, showing the approach fails for high class counts.
• Empirical per-level sensitivity ratio stays flat near 1 with depth, suggesting the cascade privacy bound is loose compared with the proven bound.

Limitations

• Accuracy lags SISA substantially on high-class-count tasks such as ImageNet (-15.6 pp) and Covertype (-10.7 pp).
• QSS-E (exact instance deletion) incurs additional accuracy cost; QSS-L does not guarantee instance deletion since the codebook depends on input features.
• Rebuild cost scales with n, so speedup is limited on very large datasets like HIGGS and KDD Cup.

Experimental setup

Datasets: MNIST FMNIST CelebA SST-2 AG News DBpedia Jigsaw Skin Segmentation Airlines MiniBooNE HIGGS KDD Cup

Benchmarks: MNIST FMNIST CelebA SST-2 AG News DBpedia Jigsaw Skin Segmentation Airlines MiniBooNE HIGGS KDD Cup

Metrics: accuracy expected deletion latency speedup bitwise exactness AUC (LiRA membership inference)

Baselines: SISA D-circ-only base model exact ridge (ACU)

Builds on: SISA Residual Quantization gradient boosting Faiss

Closest papers by meaning

• Towards Scalable Exact Machine Unlearning Using Parameter-Efficient Fine-Tuning (ICLR 2025 · similarity 0.88)
• When to Forget? Complexity Trade-offs in Machine Unlearning (ICML 2025 · similarity 0.87)
• Hessian-Free Online Certified Unlearning (ICLR 2025 · similarity 0.87)
• LoTUS: Large-Scale Machine Unlearning with a Taste of Uncertainty (CVPR 2025 · similarity 0.87)
• Towards Source-Free Machine Unlearning (CVPR 2025 · similarity 0.87)
• The Utility and Complexity of In- and Out-of-Distribution Machine Unlearning (ICLR 2025 · similarity 0.87)