Exact Unlearning via Quantized Sufficient Statistics

Ami Tavory; Shripad Gade; Tal Sarig; Noam Touitou; Ido Guy

cs.LGOct 5, 2026

Exact Unlearning via Quantized Sufficient Statistics

Authors: Ami Tavory, Shripad Gade, Tal Sarig, Noam Touitou, Ido Guy

Organizations: Meta Platforms, Inc.

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.

Figures & tables

Figure 1 : QSS translates Residual Quantization on embeddings to residual boosting on labels. Marker shape (

\circ

\triangle

\square

) encodes cell assignment; intensity encodes the target

y_{i}

(dark

{=}

high, light

{=}

low). (a) Level 1 Voronoi cells (

b{=}3

) partition the embedding space; each cell has a distinct intensity level with visible internal spread. (b) A nested Level 2 codebook subdivides each cell; the intersection regions define the co-occurrence counts

N_{1,2}[j^{\prime},j]

stored as sum-decomposable statistics, enabling exact unlearning via simple count decrements. (c) After subtracting Level 1 cell means, all points collapse into the pooled residual space. The wide intensity spread collapses to a narrow, uniform band, visualizing that label residuals carry far less variance than the original labels, since each RQ level corrects the previous, analogous to gradient boosting Friedman (2001) with quantization centroids as weak learners.

Panel of Figure 2 — Figure 2 : QSS architecture across three phases. Building (top): $\mathcal{D}$ is split into retained $\mathcal{D}^{\circ}$ (which trains the base model $g$ and the RQ codebook) and deletable $\mathcal{D}^{\bullet}$ ; all data is encoded and accumulated into mutable sufficient statistics (residual sums $S$ , counters $n$ , co-occurrence counts $N$ ). Prediction (bottom-left): a query is encoded through the frozen RQ levels and its cell means are summed; bold outlines trace the lookup path through embedding, codebook, and accumulators; the base model $g$ adds its prediction ( $+$ ). Unlearning (bottom-right): deleting a point from $\mathcal{D}^{\bullet}$ decrements accumulators only. In the low-probability event that a deletion affects $\mathcal{D}^{\circ}$ , the pair is invalidated ( $\times$ ) and must be rebuilt.

Symbol	Meaning
$X$ , $Y$ ; $x_{i}$ , $y_{i}$	Inputs, labels; single instance, single label
$n$ , $d$ , $k$	Dataset size, embedding dimensionality, label dimensionality
$f$	Frozen upstream encoder (CLIP, SBERT, or identity); distinct from RQ.encode
$g$	Base model trained on $\mathcal{D}^{\circ}$ (frozen)
$\alpha$	Blending weight (cross-validated); $\alpha{=}0$ recovers $g$
$\varphi(x)$	Feature map: $L_{2}(f(x))$

Table 1 : Notation. Superscript

{\circ}

marks the retained subset;

{\bullet}

marks the deletable portion.

	QSS-E	QSS-L	QSS-DP	SISA
Codebook	$\mathcal{D}^{\circ}$	All $\mathcal{D}$	All $\mathcal{D}$	—
Train	$t_{g}(n^{\circ})+O(n\ell bd)$			$O(n)$
Predict	$t_{g}+O(\ell bd)$			$O(S{\cdot}dk)$
Unlearn from $\mathcal{D}^{\bullet}$	$O(\ell^{2}b^{2}k)$			$O(n/S)$
Unlearn from $\mathcal{D}^{\circ}$	$t_{\text{rebuild}}$			$O(n/S)$
$\mathbb{E}[\text{unlearn}]$	$(1{-}\tfrac{n^{\circ}}{n})\,O(\ell^{2}b^{2}k)+\tfrac{n^{\circ}}{n}\,t_{\text{rebuild}}$			$O(n/S)$

Table 2 : QSS complexity and deletion guarantees. QSS-E, QSS-L, and QSS-DP differ in codebook training set and noise; all use the RQA data structure (Algorithm 1 ). When a deletion hits

\mathcal{D}^{\circ}

(probability

n^{\circ}/n

g

and the codebook must be rebuilt.

Method	Exact?	Unlearn	Predict	Indep. of $n$ ?
Retrain	Yes	$O(n)$	0	No
SISA Bourtoule et al. (2021)	Yes	$O(n/S)$	$\times S$	No
Certified Guo et al. (2020)	$\varepsilon$	$O(d^{3})$	0	Yes
SLUG Cai et al. (2025)	No	$O(d^{2})$	0	Yes
Muresanu et al. (2025)	Yes	$O(1)$	LLM fwd	Yes
Ridge/ACU Huang et al. (2025) ; Quan et al. (2026)	Yes	$O(d^{2}{+}dk)$	$O(dk)$	Yes

Table 3 : Architectural comparison with unlearning methods.

Figure 3 : QSS-L accuracy–speedup Pareto as

\rho

varies from

0.5\%

5\%

on the 13 low-

k

datasets. Both axes are relative to SISA (

x{=}1

y{=}0

). Each trajectory traces one dataset; moving left corresponds to increasing

\rho

(lower speedup, higher accuracy). Most trajectories cluster near the break-even line, trading modest accuracy for large speedups. Full version with all 15 datasets in Figure 8 (appendix).

Vision (CLIP ViT-L/14)
Task	$~k$	$n~~$	$g$ -only	QSS-L	SISA	$\Delta$
MNIST	10	53K	.814 $\pm$ .009	.944 $\pm$ .003	.921 $\pm$ .001	$+$ 2.4
FMNIST	10	53K	.749 $\pm$ .015	.825 $\pm$ .014	.854 $\pm$ .003	$-$ 2.9
CelebA Young	2	137K	.886 $\pm$ .002	.893 $\pm$ .005	.902 $\pm$ .001	$-$ 0.9
CelebA Male	2	137K	.992 $\pm$ .000	.993 $\pm$ .001	.993 $\pm$ .001	$+$ 0.0
Text (all-MiniLM-L6-v2)

Table 4 : Guarantee-aligned accuracy at

\rho{=}0.5\%

on low-

k

datasets (mean

\pm

std over 5 random splits; ‡ 2–3 seeds).

g

-only: base model on

\mathcal{D}^{\circ}

(floor). QSS-L: one fixed label-deletion construction per feature pipeline; modes are not selected using test accuracy. QSS-E is reported separately in Appendix D.1 . SISA:

S{=}5

shard retraining Bourtoule et al. (2021) .

\Delta

: QSS-L

\,-\,

SISA accuracy (pp). High-

k

and QSS-E results appear in Table 11 (appendix).

Panel of Figure 4 — Figure 4 : Privacy validation. (a) DP noise preserves most accuracy at $\varepsilon\geq 1$ . (b) Even without DP, QSS leaks no membership information (64 shadow models, 1000 audit points).

Appendix figures & tables26 assets

Supplementary material from the paper’s appendix.

Appendix

$n$	$b$	$\ell$	L1	L2	L4	L6	L8	L10
50	4	6	1.00	0.95	1.12	1.20	—	—
100	5	8	1.00	0.97	1.09	1.12	1.16	—
200	8	10	1.00	0.97	1.08	1.09	1.10	1.10
500	16	12	1.00	0.98	1.01	1.00	1.02	0.96

Appendix

Table 5 : Maximum per-level sensitivity ratio

|\delta_{m,j}|/(\|\Delta y\|/n_{\min})

across

30{,}000

random code assignments per configuration. The ratio stays flat across levels.

Figure 5 : Per-level sensitivity ratio

|\delta_{m,j}|/(\|\Delta y\|/n_{\min})

. (a) Adversarial maximum across

20{,}000

random code assignments for four configurations. The ratio stays flat near

1

at all levels. (b) Comparison with theoretical bounds for

N{=}200

b{=}8

: the empirical sensitivity (solid) is far below both the naïve recurrence bound (dotted, grows linearly) and the Cauchy–Schwarz ceiling (dashed,

\sqrt{n_{\min}}\approx 5

Figure 6 : Codebook instability (§ B ) on 2D synthetic data (

b{=}20

, 300 points). Left: original

k

-means centroids (

+

) and Voronoi boundaries. Right: removing one point (

\times

) and retraining

k

-means shifts centroids (arrows), flipping 30% of codes (dark points). Flips occur far from the removed point, demonstrating that the perturbation is global. In 768-d CLIP embeddings, the flip rate is 100%.

Figure 7 : Aggregate view across all 15 datasets (

\rho{=}0.5\%

, per-seed). (a) QSS-L–SISA accuracy gap by

k

: binary and low-

k

tasks cluster near zero; high-

k

(ImageNet) is a clear outlier (§ 4.5 ). (b) Gap by domain: all three modalities behave similarly. (c) Gap by SISA model type (LGBM, MLP): QSS is competitive regardless of baseline architecture.

Figure 8 : QSS-L accuracy–speedup Pareto as

\rho

varies from

0.5\%

5\%

, all 15 datasets. Both axes are relative to SISA (

x{=}1

y{=}0

). Each trajectory traces one dataset; moving left corresponds to increasing

\rho

(lower speedup, higher accuracy). Gaps on ImageNet and Covertype (high-

k

tasks) narrow with larger

\rho

. Full timing breakdown in Table 6 .

Dataset	$n$	$\rho$	$t_{\text{reb}}$ (s)	$\mathbb{E}[\text{QSS-L}]$	SISA	Speedup
Jigsaw	1.4M	0.5%	44	0.2 s	109 s	483 $\times$
CelebA Male	137K	0.5%	13	0.1 s	9.5 s	132 $\times$
MiniBooNE	130K	0.5%	30	0.2 s	17.5 s	114 $\times$
DBpedia	473K	0.5%	29	0.1 s	15.8 s	107 $\times$
Covertype †	581K	0.5%	850	4.3 s	98.7 s	23 $\times$
Airlines	500K	0.5%	50	0.3 s	11.0 s	54 $\times$

Appendix

Table 6 : Expected unlearning latency at

\rho{=}0.5\%

\mathbb{E}[\text{QSS-L}]=(1{-}\rho)\,t_{\text{RQ}}+\rho\,t_{\text{rebuild}}

(Equation 8 ); SISA (

S{=}5

) retrains one shard.

t_{\text{rebuild}}

includes retraining

g

, re-extracting embeddings (for LGBM: leaf contributions), re-fitting LDA and codebook, re-encoding all

n

points, and re-accumulating. Per-component RQ timings appear in Table 10 . † High-

k

limitation (§ 4.5 ).

Figure 9 : Codebook collapse on ImageNet (unsupervised RQ). Left: width collapse (accuracy and

\eta_{0}

grow with

b

). Right: depth collapse (accuracy plateaus as

\eta_{\ell}\to 0

). See Appendix A.3 for the variance decay analysis that explains this convergence behavior.

	0%	1%	5%	10%	20%	30%	40%	50%
CelebA	99.35	99.35	99.34	99.36	99.33	99.33	99.32	99.33
ImageNet	72.67	72.67	72.66	72.65	72.66	72.65	72.48	72.44
Covertype	75.45	75.39	75.40	75.38	75.36	75.33	75.21	75.14
AG News	90.08	90.11	90.05	90.14	89.95	89.89	89.89	89.86

Appendix

Table 7 : Accuracy retention under random deletion. Unlearn and retrain-from-scratch produce bitwise identical predictions at every deletion fraction (Proposition 1 ).

$\varepsilon$	ROC AUC	TPR@FPR=0.1%	TPR@FPR=1%
1.0	0.515	0.2%	2.2%
2.0	0.518	0.8%	1.2%
4.0	0.531	0.2%	1.4%
$\infty$ (no DP)	0.525	0.0%	0.4%

Appendix

Table 8 : LiRA membership inference on QSS (CelebA Male). The attack barely outperforms random guessing at all

\varepsilon

, including

\varepsilon{=}\infty

(no DP noise).

Figure 10 :

\varepsilon

-label-DP accuracy. Adult (binary) is insensitive; Covertype (7-class) and AG News (4-class) degrade gracefully, retaining most accuracy at

\varepsilon\geq 1

Figure 13 : Accuracy vs. codebook width

b

(

\ell{=}4

fixed). Dotted lines show

g

-only baselines. Width matters most on MNIST and Covertype at

|\mathcal{D}^{\circ}|{=}5{,}000

, where larger

b

provides finer Voronoi cells that better separate classes. AG News and CIFAR-100 are flat (

\alpha\approx 0

Figure 14 : Accuracy vs. codebook depth

\ell

(

b{=}256

fixed). Covertype gains

\sim

2 pp from

\ell{=}1

\ell{=}8

; other datasets saturate by

\ell{=}2

–

4

, consistent with the depth collapse observed in Figure 9 .

Figure 15 : Cumulative accuracy as RQ levels are added. Level 1 captures most of the QSS lift; deeper levels provide diminishing returns, confirming the variance decay prediction (Proposition 5 ).

Figure 16 : LDA preconditioning ablation (

|\mathcal{D}^{\circ}|{=}500

). LDA provides a modest lift on Covertype (

+1.5

pp) where

k{-}1{=}6

discriminant directions help the unsupervised codebook align with class boundaries. Effect is negligible on AG News and SST-2 where the pretrained SBERT embeddings already separate classes well.

Figure 17 : QSS accuracy (left) and

t_{\text{RQ}}

(right) as codebook parameters vary. Top: MiniBooNE (

\ell

sweep at

b{=}128

;

b

sweep at

\ell{=}4

). Accuracy is flat;

t_{\text{RQ}}

spans three orders of magnitude. Bottom: FMNIST (same sweeps). Accuracy improves with larger codebooks; we trade deletion speed for accuracy via CV.

Dataset	$n$	Saturation	Gap	Rebuild savings
Skin Seg.	245K	1% (2.5K)	$-$ 0.02 pp	100 $\times$
KDD Cup	494K	5% (25K)	$-$ 0.15 pp	20 $\times$
HIGGS	11M	10% (1.1M)	$-$ 0.02 pp	10 $\times$
Covertype	581K	10% (58K)	$-$ 0.40 pp	10 $\times$
Airlines	500K	25% (125K)	$-$ 0.05 pp	4 $\times$
MiniBooNE	130K	25% (33K)	$-$ 0.15 pp	4 $\times$

Appendix

Table 9 : Accumulator convergence on tabular datasets. Saturation fraction : smallest fraction of

\mathcal{D}^{\bullet}

at which accuracy is within 0.15 pp of full. Subsampled rebuilds reduce the encode

+

accumulate cost proportionally.

Figure 18 : Accuracy vs. fraction of

\mathcal{D}^{\bullet}

encoded into accumulators. Tabular datasets (solid) converge rapidly; DNN datasets (dashed) require most or all of the data. The convergence rate reflects embedding geometry: well-clustered embeddings yield high cell purity and fast convergence.

Dataset	$n$	RQ (ms)	SISA (ms)	Speedup
CalHousing	21K	3.9	994	257 $\times$
UTKFace	24K	5.7	68,622	12,096 $\times$
DTD	5.6K	6.1	26,105	4,278 $\times$
Adult	45K	8.0	1,188	148 $\times$
Skin Seg.	245K	10.9	1,025	94 $\times$
SST-2	68K	12.0	1,303	109 $\times$

Appendix

Table 10 : RQA data structure update latency (median of 10 runs, A100 GPU): encode the deleted point, decrement accumulators, and re-materialize prediction tables. This is the

t_{\text{RQ}}

component of the expected QSS cost (Table 6 ).

Dataset	QSS-E	QSS-L	Dataset	QSS-E	QSS-L
MNIST	$81.83{\pm}1.42$	$94.43{\pm}0.34$	FMNIST	$75.03{\pm}1.56$	$82.49{\pm}1.40$
CelebA Young	$89.24{\pm}0.10$	$89.34{\pm}0.52$	CelebA Male	$99.21{\pm}0.05$	$99.25{\pm}0.05$
SST-2	$79.79{\pm}0.65$	$85.36{\pm}1.97$	AG News	$84.62{\pm}0.53$	$89.89{\pm}0.42$
DBpedia	$91.24{\pm}0.97$	$95.80{\pm}0.42$	Jigsaw	$92.03{\pm}0.05$	$92.35{\pm}0.06$
ImageNet	$46.24{\pm}0.31$	$66.19{\pm}1.92$	CIFAR-100	$39.03{\pm}2.55$	$68.42{\pm}4.86$
Skin Seg.	$99.46{\pm}0.14$	$99.71{\pm}0.08$	Airlines	$57.80{\pm}0.17$	$64.02{\pm}0.22$

Appendix

Table 11 : Fixed-mode accuracy (%, mean

\pm

standard deviation over five seeds) at

\rho=0.5\%

. The required neighboring relation, not test accuracy, determines the mode.

Dataset	Exact ridge	QSS-L	Difference	Paired $p$
AG News	$89.468$	$89.894$	$+0.426$ pp	$0.048$
SST-2	$83.709$	$85.356$	$+1.647$ pp	$0.121$

Appendix

Table 12 : Exact ridge and fixed QSS-L on identical frozen-SBERT features and submitted splits. The QSS-L advantage on SST-2 is not statistically significant.

Method	State	Ordinary deletion
Ridge/ACU	$O(d^{2}+dK)$	$O(d^{2}+dK)$
QSS	$O(\ell^{2}b^{2}+\ell bK)$	$O(\ell^{2}b^{2}K)$ conservative

Appendix

Table 13 : State and ordinary-deletion costs, both independent of dataset size

n

. Here

d

is analytic feature dimension and

K

the number of outputs.

Dataset	$S=5$	$S=50$	$S=200$
Adult	$83.30\%$ / $6.1$ ms	$83.32\%$ / $2.2$ ms	$81.91\%$ / $1.2$ ms
Covertype	$71.99\%$ / $3.379$ s	$71.46\%$ / $0.160$ s	$70.60\%$ / $0.0256$ s
SST-2	$80.73\%$ / $0.1947$ s	$79.82\%$ / $0.1050$ s	$78.56\%$ / $0.0035$ s

Appendix

Table 14 : SISA accuracy and isolated affected-shard retraining time.

Attribute	$\eta_{0}$	PR-AUC
Male	0.960	0.998
Young	0.532	0.959
Attractive	0.409	0.832
Smiling	0.237	0.887
Eyeglasses	0.210	0.851

Appendix

Table 15 : Without preconditioning,

\eta_{0}

predicts quality.

Figure 20 : UMAP projections of test-set embeddings, shaded by level-0 cell purity (fraction of each cell belonging to the majority class). Dark regions indicate pure cells ( $>$ 90%); light regions indicate mixed cells. MNIST (96.6% average purity) achieves the smallest QSS-L–SISA gap ( $+3.8$ pp); Covertype (63.1%) has the largest among low- $k$ tasks ( $-10.7$ pp).

Explore similar work

Exact Unlearning in Reinforcement Learning
Jun 2, 2026Thanh Nguyen-Tang, Raman AroraExact Unlearning Offline Reinforcement Learning
Department of Data Science, New Jersey Institute of Technology, Newark, NJ, USA · Department of Computer Science, Johns Hopkins University, Baltimore, MD, USA
Forgetting That Sticks: Quantization-Permanent Unlearning via Circuit Attribution
May 14, 2026Saisab Sadhu, Pratinav Seth, Vinay Kumar SankarapuQuantized Exact Unlearning
Lexsi Labs
Bounding Retraining Equivalence and the Deletion Floor in Materials Machine Unlearning
Sep 28, 2026Can Polat, Mustafa Kurban, Erchin Serpedin +1Machine Unlearning Deletion
Department of Electrical and Computer Engineering, Texas A&M University, College Station, Texas, USA · Department of Electrical and Computer Engineering, Texas A&M University at Qatar, Doha, Qatar · Department of Prosthetics and Orthotics, Ankara University, Ankara, Turkey +1

Jun 2, 2026, cs.LGJ/K move · Enter open · S save

Exact Unlearning in Reinforcement Learning

Thanh Nguyen-Tang, Raman Arora

Department of Data Science, New Jersey Institute of Technology, Newark, NJ, USA · Department of Computer Science, Johns Hopkins University, Baltimore, MD, USA

Exact Unlearning Offline Reinforcement Learning Computational Cost

Open paper AskPDF arXiv

We formulate the problem of \emph{exact unlearning} in reinforcement learning, where the goal is to design an efficient framework that enables the removal of any user's data upon deletion request, i.e., the online learner's output after unlearning is \emph{indistinguishable} from what would have been produced had the deleted user never interacted with the learner. For any

ρ>0

, we show that there exists a reinforcement learning (RL) algorithm that is

ρ

-TV-stable and supports an exact unlearning procedure whose expected computational cost is only a

ρ\sqrt{\ln T}

fraction of the computational cost of retraining from scratch. We construct such a

ρ

-TV-stable RL algorithm for tabular Markov decision processes (MDPs), which achieves a regret bound of

\mathcal{O}(H^2 \sqrt{SAT} + H^3 S^2 A + {H^{2.5} S^2 A}/ρ)

, where

S, A, H

, and

T

denote the number of states, the number of actions, the episode horizon, and the number of episodes, respectively. We also establish a lower bound of

Ω(H\sqrt{\!SAT}\! +\! {SAH}/ρ)

for

ρ

-TV-stable RL algorithms, showing that our algorithm is nearly minimax optimal.

Abstract

Explore similar work

Exact Unlearning in Reinforcement Learning

Forgetting That Sticks: Quantization-Permanent Unlearning via Circuit Attribution

Bounding Retraining Equivalence and the Deletion Floor in Materials Machine Unlearning