Exact Deployment-Time Label Unlearning via Quantized Sufficient Statistics

We describe deployment-time exact label unlearning: after a label is withdrawn, the predictor must match one retrained from scratch without that label's influence. General-purpose exact methods such as SISA partition data into disjoint shards, localizing retraining but reducing the data available to each constituent model as the number of shards grows. We propose Quantized Sufficient Statistics (QSS), a data structure of mutable, sum-decomposable label statistics, and QSS-L, a label-unlearning system built from one or more independently sampled schema-content pairs. In each pair, a small schema set trains a frozen base predictor, while the remaining labels form mutable content stored in QSS. A content-label deletion is an arithmetic subtraction from quantized accumulators; a rare deletion request to a pair's schema triggers an expensive, exact rebuild. With multiple pairs, unaffected pairs remain available while invalidated pairs rebuild. Across 15 vision, text, and tabular benchmarks, QSS-L matches or exceeds SISA, or trails it by at most 2 percentage points, on 11 tasks. At a $0.5\%$ schema ratio, measured operating points provide 3-645$\times$ lower expected deletion latency than five-shard SISA, including the rare full-schema rebuilds.