Exact Unlearning via Quantized Sufficient Statistics¶
会议: NeurIPS 2026
arXiv: 2610.07197
OpenReview: https://openreview.net/forum?id=SyxiOl962F
代码: https://github.com/atavory/rqu
领域: 模型压缩
关键词: 机器遗忘, 残差量化, 充分统计量, 模式内容解耦, 差分隐私
一句话总结¶
提出量子化充分统计量（QSS）框架，将模型解耦为小规模冻结模式与可加法分解的量化累加器，把精确遗忘转化为常数时间算术减法，并在保留率 \(\rho=0.5\%\) 下取得逼近 SISA 的准确率与最高 483 倍遗忘加速。
研究背景与动机¶
在 GDPR 与 CCPA 等全球数据隐私法规的驱动下，从已部署的机器学习模型中彻底消除特定训练样本的影响（即精确机器遗忘，Exact Machine Unlearning）已成为合规上线的刚性约束。除了隐私合规，移除投毒数据、过时事实与偏见数据同样需要对模型参数进行严谨的“逆向擦除”。然而，现代深度学习训练将所有样本信息非线性地交织（Entanglement）在共享权重之中，导致除了重新训练（Retraining）之外，极难将单个样本的影响干净剔除。当前通用的精确遗忘主流基线是分片隔离方法 SISA（Sharded, Isolated, Sliced, Aggregated），它将数据集划分为多个互斥分片（Shards）独立训练子模型，一旦收到删除请求便定位并重训对应分片。
然而，SISA 的架构设计存在无法调和的根本权衡：每个删除请求都会确定性地破坏某个分片，迫使其触发一次代价为 \(\mathcal{O}(n/S)\) 的完整重训。如果为了降低单次重训成本而增加分片数 \(S\)，每个分片能够接触到的有效训练数据量便成比例萎缩，直接损害模型最终的泛化精度；而在批量删除场景下，当删除数量 \(B \gtrsim S \ln S\) 时，几乎所有分片都会被击穿，导致整体沦为昂贵的全量重训。更为致命的是，SISA 无法利用分片冗余提升可用性，因为重叠分片只会倍增每次删除的重训开销。
为了打破“重训分片与泛化精度绑定”的僵局，本文提出了一个革命性的切入视角：将模型表示显式拆解为不可变的结构模式与可数际叠加的内容。类似在特征空间架设一面离散的带标签网格储物柜，储物柜的边界由极小部分不可变数据决定并固化，而其余所有数据仅作为计数与残差累加项被填入网格中。删除样本退化为纯粹的标量减法，完全无需运行优化器。核心 idea：将模型分解为少量样本训练并冻结的模式（Schema，含基础模型与残差量化码本）和按量化单元可加性累加的内容（Content），借助残差共现矩阵消除层间级联依赖，使常规精确遗忘退化为与数据集规模无关的 \(\mathcal{O}(\ell^2 b^2 k)\) 算术快路径。
方法详解¶
整体框架¶
QSS 将模型从“端到端黑盒权重”重构为“模式（Schema）+ 内容（Content）”的组合结构。给定规模为 \(n\) 的数据集 \(\mathcal{D}\)，系统首先随机抽取极小比例 \(\rho = n^\circ / n \le 1\%\) 的不可变子集 \(\mathcal{D}^\circ\) 构成模式：在 \(\mathcal{D}^\circ\) 上训练并冻结基础分类器 \(g\)（线性探测头或浅层 MLP）以及深度为 \(\ell\)、每层含 \(b\) 个聚类质心的残差量化（Residual Quantization, RQ）码本。所有剩余数据 \(\mathcal{D}^\bullet = \mathcal{D} \setminus \mathcal{D}^\circ\) 连同 \(\mathcal{D}^\circ\) 一同被送入 RQ 码本中编码，并以纯累加方式记录为充分统计量（目标残差和 \(\mathbf{T}\)、样本计数 \(n\)、跨层共现计数 \(N\)），构成可变内容。
预测阶段，待测样本通过上游冻结编码器提取特征后，一方面输入基础模型得到初始预测 \(g(x)\)，另一方面依次匹配每层 RQ 码本的质心单元，沿编码路径累加各量化单元的物化残差均值 \(\boldsymbol{\mu}\)，最终以混合权重 \(\alpha\) 与 \(g(x)\) 线性融合。遗忘阶段，针对来自 \(\mathcal{D}^\bullet\) 的删除请求，系统直接在对应单元的统计量中扣除该样本的标签与计数贡献，随后以 \(\mathcal{O}(\ell^2 b^2 k)\) 的复杂度原地重新物化各层单元均值，完全不触碰模式组件；若极小概率命中 \(\mathcal{D}^\circ\)，系统则触发重构。
%%{init: {'flowchart': {'rankSpacing': 24, 'nodeSpacing': 28, 'padding': 6, 'wrappingWidth': 400}}}%%
flowchart TD
In["输入数据集 D"] --> S1["模式与内容划分<br/>极小子集 D_circ 训练基础模型与 RQ 码本"]
S1 --> S2["残差量化充分统计量构建<br/>累加目标和 T、频数 n、共现矩阵 N"]
S2 --> S3["多项式时间残差物化<br/>利用共现矩阵剔除早层均值投影"]
S3 --> Out["双模态精确预测<br/>y = g(x) + alpha * RQA.Predict(x)"]
Out --> Branch{"删除请求来源判断"}
Branch -->|"命中 D_bullet (概率 1-rho)"| S4["常数时间算术精确遗忘<br/>扣减统计量并原地重算物化缓存"]
Branch -->|"命中 D_circ (概率 rho)"| S5["冗余模式非阻塞重建<br/>p 实例热备消除下线停机风险"]关键设计¶
1. 模式与内容解耦与保障对齐模式：将参数拟合收敛到离散计数统计
针对传统深度网络将样本完全缠绕进权重的痛点，本文将训练过程收敛至两段解耦表示。模式层仅使用规模极小的保持子集 \(\mathcal{D}^\circ\) 训练基础分类器 \(g\) 和多层残差量化码本；内容层则把整个数据集的标签监督信息转化为累加统计量。根据隐私协议的要求，本文严格区分了两种保障模式：QSS-L（Label Unlearning）在全量无监督输入特征上训练 RQ 码本，由于聚类过程完全不接触标签，删除标签只需从累加统计量中减去标签值，输出模型与在 \(\mathcal{D}^{-y_j}\) 上重构的结果完全一致；QSS-E（Instance Unlearning）则在 \(\mathcal{D}^\circ\) 上训练码本，使得码本质心与输入特征完全解耦，能够提供针对样本输入与标签双重移除的完全精确保证。此外，通过向物化后的单元均值注入高斯噪声，QSS-DP 提供了无视码本深度的标签差分隐私保障。
2. 残差量化充分统计量（RQA）与共现矩阵修正：消除指数级单元级联依赖
多层残差量化在每层对前序量化的残差特征进行再量化。若按传统方案逐层迭代计算标签残差，样本跨多层的分配组合将达到 \(b^\ell\) 个联合单元，引发内存与计算灾难。RQA 仅记录一阶目标和 \(\mathbf{T}_{m,j} = \sum_{i: c_{i,m}=j} y_i^r\)、一阶频数 \(n_{m,j}\) 以及两两层间的共现计数矩阵 \(N_{k,m}[j', j] = |\{i: c_{i,k}=j', c_{i,m}=j\}|\)。在物化阶段，第 \(m\) 层的真实残差累加和 \(\mathbf{S}_{m,j}\) 无需遍历样本，直接通过解析减去前 \(m-1\) 层单元均值的加权投影得出：
$$
\mathbf{S}{m,j} = \mathbf{T}
$$
式中 } - \sum_{k=1}^{m-1} \sum_{j'=1}^{b} N_{k,m}[j', j] \cdot \boldsymbol{\mu}_{k, j'\(\boldsymbol{\mu}_{m,j} = \mathbf{S}_{m,j} / n_{m,j}\)。这使得多层残差更新从潜在的指数复杂度坍缩为 \(\mathcal{O}(\ell^2 b^2 k)\) 的多项式级矩阵乘法，单次遗忘只需 \(\mathcal{O}(\ell^2)\) 次标量减法加上一次轻量矩阵重算，完全脱钩了总样本量 \(n\)。
3. 冗余多实例热备机制：压降同步全量重训概率至指数级极小值
当删除请求命中了 \(\mathcal{D}^\circ\) 中的样本时，基础模型与码本必须重新训练。若只维护单一模型，系统将面临停机或高延迟重训阻塞。QSS 引入 \(p\) 个具有独立随机子集 \(\mathcal{D}_i^\circ\) 的冗余实例，每个实例各自维护独立的模式与全局统计量。由于攻击者无法知晓 \(\mathcal{D}_i^\circ\) 的具体成员构成，单次删除请求使得所有 \(p\) 个实例同时失效的概率暴降至 \(\rho^p\)（例如当 \(\rho=0.5\%, p=3\) 时，同时失效概率仅为 \(1.25 \times 10^{-7}\)）。当某个实例被击穿触发后台异步重建时，其余 \(p-1\) 个实例继续提供满血服务，且由于每个实例的累加器均包含了全量数据，整个重建过程对在线推理服务实现零精度损失。
损失函数 / 训练策略¶
基础模型 \(g\) 采用交叉熵或均方误差在 \(\mathcal{D}^\circ\) 上通过 Optuna 进行超参数搜索训练（线性探测头或单隐层 MLP）。残差量化采用 Faiss 的 ResidualQuantizer 模块，使用 \(k\)-means++ 初始化与贪心最近邻分配进行无监督特征聚类。在线性判别分析（LDA）预处理分支中，利用 \(\mathcal{D}^\circ\) 上的标签监督拟合 \(k-1\) 个判别方向矩阵 \(W_{\text{LDA}}\)，并将特征映射为 \(\varphi(x) = \text{L2-normalize}([f(x); W_{\text{LDA}} f(x)])\)，有效引导离散码本向类别决策面聚集。混合系数 \(\alpha \in [0, 2]\) 与码本结构参数 \((b, \ell)\) 在 \(\mathcal{D}^\circ\) 的验证折上进行交叉验证选优；当 \(\alpha=0\) 时退化为纯基础模型，从而在理论上保证 QSS 泛化性能天然下界不低于仅用 \(\mathcal{D}^\circ\) 训练的基准。
实验关键数据¶
主实验¶
在 15 个包含图像（CLIP ViT-L/14）、文本（all-MiniLM-L6-v2）和表格（LightGBM 树叶贡献嵌入）的大规模数据集（\(n \ge 50\text{K}\)）上，固定保留比例 \(\rho=0.5\%\) 评估 QSS-L 与强基线 SISA（\(S=5\)）的准确率对比（5 个随机划分均值与标准差）：
| 数据集 | 模态 / 类别数 \(k\) | 样本量 \(n\) | \(g\)-only (底线) | QSS-L (本文) | SISA (上限) | 准确率差值 \(\Delta\) |
|---|---|---|---|---|---|---|
| MNIST | 图像 / 10 | 53K | \(0.814 \pm 0.009\) | 0.944 \(\pm 0.003\) | \(0.921 \pm 0.001\) | +2.4 pp |
| FMNIST | 图像 / 10 | 53K | \(0.749 \pm 0.015\) | \(0.825 \pm 0.014\) | 0.854 \(\pm 0.003\) | -2.9 pp |
| CelebA Young | 图像 / 2 | 137K | \(0.886 \pm 0.002\) | \(0.893 \pm 0.005\) | 0.902 \(\pm 0.001\) | -0.9 pp |
| CelebA Male | 图像 / 2 | 137K | \(0.992 \pm 0.000\) | 0.993 \(\pm 0.001\) | 0.993 \(\pm 0.001\) | +0.0 pp |
| SST-2 | 文本 / 2 | 51K | \(0.785 \pm 0.008\) | 0.854 \(\pm 0.020\) | \(0.835 \pm 0.003\) | +1.8 pp |
| AG News | 文本 / 4 | 96K | \(0.861 \pm 0.003\) | 0.899 \(\pm 0.004\) | \(0.895 \pm 0.001\) | +0.4 pp |
| DBpedia | 文本 / 14 | 473K | \(0.952 \pm 0.002\) | \(0.958 \pm 0.004\) | 0.977 \(\pm 0.001\) | -1.9 pp |
| Jigsaw | 文本 / 2 | 1.4M | \(0.923 \pm 0.000\) | \(0.924 \pm 0.001\) | 0.927 \(\pm 0.000\) | -0.4 pp |
| Skin Seg. | 表格 / 2 | 245K | \(0.986 \pm 0.002\) | \(0.997 \pm 0.001\) | 0.999 \(\pm 0.000\) | -0.2 pp |
| Airlines | 表格 / 2 | 500K | \(0.627 \pm 0.004\) | \(0.640 \pm 0.002\) | 0.655 \(\pm 0.007\) | -1.5 pp |
| MiniBooNE | 表格 / 2 | 130K | \(0.903 \pm 0.004\) | \(0.912 \pm 0.004\) | 0.943 \(\pm 0.002\) | -3.1 pp |
| HIGGS | 表格 / 2 | 11M | \(0.728 \pm 0.000\) | \(0.730 \pm 0.001\) | 0.740 \(\pm 0.003\) | -1.0 pp |
| KDD Cup | 表格 / 17 | 494K | \(0.996 \pm 0.001\) | 0.999 \(\pm 0.000\) | \(0.994 \pm 0.011\) | +0.5 pp |
消融实验与遗忘延迟对比¶
包含重训极低概率事件的期望单样本遗忘延迟 \(\mathbb{E}[t] = (1-\rho) t_{\text{RQ}} + \rho t_{\text{rebuild}}\)（A100 GPU 测定）：
| 数据集 | 规模 \(n\) | QSS-E 准确率 (%) | QSS-L 准确率 (%) | \(\mathbb{E}[\text{QSS-L}]\) 延迟 | SISA 遗忘延迟 | 遗忘加速比 |
|---|---|---|---|---|---|---|
| Jigsaw | 1.4M | \(92.03 \pm 0.05\) | \(92.35 \pm 0.06\) | 0.2 s | 109 s | 483× |
| CelebA Male | 137K | \(99.21 \pm 0.05\) | \(99.25 \pm 0.05\) | 0.1 s | 9.5 s | 132× |
| MiniBooNE | 130K | \(86.88 \pm 0.21\) | \(91.24 \pm 0.37\) | 0.2 s | 17.5 s | 114× |
| DBpedia | 473K | \(91.24 \pm 0.97\) | \(95.80 \pm 0.42\) | 0.1 s | 15.8 s | 107× |
| AG News | 96K | \(84.62 \pm 0.53\) | \(89.89 \pm 0.42\) | 75 ms | 3.8 s | 51× |
| MNIST | 53K | \(81.83 \pm 1.42\) | \(94.43 \pm 0.34\) | 68 ms | 3.1 s | 46× |
| CelebA Young | 137K | \(89.24 \pm 0.10\) | \(89.34 \pm 0.52\) | 88 ms | 3.6 s | 41× |
| Skin Seg. | 245K | \(99.46 \pm 0.14\) | \(99.71 \pm 0.08\) | 0.6 s | 12.0 s | 19× |
| HIGGS | 11M | \(63.52 \pm 0.05\) | \(72.98 \pm 0.08\) | 17.6 s | 114 s | 6× |
| KDD Cup | 494K | \(99.30 \pm 0.03\) | \(99.88 \pm 0.01\) | 11.9 s | 154 s | 6× |
| SST-2 | 51K | \(79.79 \pm 0.65\) | \(85.36 \pm 1.97\) | 0.3 s | 1.2 s | 4× |
关键发现¶
- 遗忘计算彻底脱钩 \(n\)：对于常规可变内容，算术扣除与物化耗时仅数毫秒至几百毫秒（如 AG News 仅需 23.2 ms），即便将 \(0.5\%\) 发生概率的全量重建代价按期望折算，在低类别任务上整体期望耗时相比 SISA 依然具备 4 至 483 倍的压倒性速度优势。
- 精确性机制严密自洽：对 9 个数据集连续删除 100 个样本，算术减法后得到的模型输出与从头剔除样本重新物化的预测分数之间误差严格为 0.0，达成位级完全一致（Bitwise Identical）；即便是 ImageNet 连续删除 50% 标签，模型预测仍然与重训完全一致，精度仅损失 0.25 pp。
- 高类别数维度的局限瓶颈：在类别数极端庞大的任务中（如 ImageNet \(k=1000\)，落后 SISA 15.6 pp；Covertype \(k=7\)，落后 10.7 pp），无监督特征量化容易将不同类别的样本揉碎在同一聚类单元内，导致单元内残差均值被稀释；而在二分类或类别较少且初始纯度高的任务中（MNIST 纯度 96.6%），QSS 反而以更集中的表示反超 SISA。
亮点与洞察¶
- 将“模型权重”转化为“可加减统计量”的范式颠覆：传统遗忘总在设法反向逼近梯度衰减，而 QSS 证明只要将表达形式置换为残差量化直方图，精确遗忘就可以化繁为简变成整数计数与标量减法，从物理上杜绝了近似遗忘的泛化遗忘风险。
- 共现修正矩阵化解了多层残差级联爆炸：通常分层残差量化会被多层交叉状态拖垮，本文巧妙地用成对共现矩阵 \(N_{k,m}\) 替代了全联合计数，借助正交投影分解将物化复杂度锁死在 \(\mathcal{O}(\ell^2 b^2 k)\)，实现了极为优美的理论与工程闭环。
- 冗余解耦重构了在线高可用架构：不仅在算法上实现常数时间遗忘，在工程上通过 \(p\) 实例热备使极端重建时的同步服务中断概率降至 \(\rho^p\)，从根本上解决了遗忘操作长期阻塞模型线上推理的技术痛点。
局限与展望¶
- 作者承认的局限：类别总数 \(k\) 过大时精度衰减明显，无监督量化无法有效保留细粒度类别边界；当删除请求击中保持集 \(\mathcal{D}^\circ\) 时，必须执行全量 \(\mathcal{O}(n)\) 重训；若对抗性攻击者探知了 \(\mathcal{D}^\circ\) 的构成，可能蓄意频繁触发全量重训拒绝服务攻击。
- 自身发现的局限：方法高度依赖于高质量的前置预训练特征（如 CLIP、SBERT），对于需要从底层像素或原始词表深度微调端到端骨干的端到端学习场景难以适用；此外，维持 \(p\) 组独立码本与累加矩阵会成倍增加运行内存占用。
- 具体改进思路：探索结合监督信号的有监督残差量化码本构建（如结合对比损失），提升大类别数下的单元纯度；同时引入动态在线替换机制，当 \(\mathcal{D}^\circ\) 样本被删时动态填补并微调局部码本，避免整网重构。
相关工作与启发¶
- vs SISA：SISA 采用分片硬隔离并在删除时执行局部重训，遗忘复杂度强依赖分片大小 \(\mathcal{O}(n/S)\) 且切分数据直接挫伤泛化精度；QSS 全局共享不可变模式，遗忘过程变为 \(\mathcal{O}(1)\) 算术操作，期望耗时降低数个数量级。
- vs 线性/Ridge 逆更新（ACU / Quan et al.）：解析线性更新通过 Sherman-Morrison 矩阵降秩实现遗忘，仅适合低维全局线性头；QSS 则是利用离散残差量化捕获局部非线性残差，提供了更强的局部非线性表达能力。
- vs 差分隐私扰动 / 影响函数（Certified Removal / Fisher Scrubbing）：传统方法均为一阶或二阶梯度近似，存在精度失真或隐私预算衰竭风险；QSS 提供了绝对位级一致的精确遗忘保证，同时可通过输出加噪无缝桥接严格标签 DP。
评分¶
- 新颖性: ⭐⭐⭐⭐⭐ 巧妙融合残差量化与可加充分统计量，从底层彻底重构了精确遗忘的计算范式。
- 实验充分度: ⭐⭐⭐⭐⭐ 涵盖 15 个大规模跨模态数据集，包含严苛的位级一致性校验与 LiRA 成员推理对抗审计。
- 写作质量: ⭐⭐⭐⭐⭐ 理论推导清晰完备，从方差衰减定理到马尔可夫链高可用分析层次分明。
- 价值: ⭐⭐⭐⭐⭐ 为合规要求极高的工业级机器学习精确遗忘服务提供了突破性的低成本工程落地路径。