cs.CRAug 27, 2026
SaveMemorization Is Not Extraction: Tight Differential-Privacy Bounds and Audit Blind Spots
Organizations: University of North Carolina at Charlotte · Utah State University
Abstract
Memorization in large language models is measured through a zoo of definitions whose formal relations are unknown, and differential privacy (DP) is treated as a proxy against all of them at once. We pin down the exact DP constant for the two that carry the practical weight, counterfactual memorization and adaptive extraction, and show that they do not control each other. Under -DP, every adaptive extraction protocol with list budget succeeds with probability at most for the oblivious baseline , and the bound is tight on a dense set of baselines: DP uniformly controls extraction exactly up to a threshold in how well the secret can be guessed a priori. Min-entropy certifies that baseline distribution-free, since holds extraction below a risk level under pure -DP for every prior, and is exact on uniform priors. On the memorization side, -DP caps the counterfactual memorization of any bounded score at an advantage functional , equal to under pure DP; for duplicated copies the naive bound is unattainable, the exact constant being a closed-form staircase attained by geometric noisy counting. That cap is attained inside the local score class used in practice, and it is there that the two measures separate: one mechanism is memorized yet unextractable, another fully extractable yet exactly invisible to every loss-based score. The two-sided blind spot this opens for loss-based auditing and unlearning verification survives on billion-parameter models: a reserved-trigger release is recovered verbatim from one prompt while the audits practitioners deploy certify it clean.
Figures & tables
Figure 1: Relations among memorization measures. Solid edges are proved, dashed ones are open. The violet arrows are the bridges proved here, labeled with the constant each delivers; the red edge is also a result, a two-way separation on the local class , so neither of those two measures controls the other; thin gray arrows are prior bridges, and the dashed node is the relation we leave open.
| prior -DP bounds | this paper | |
|---|---|---|
| adversary | one reconstruction | adaptive prompting, |
| guess | list budget | |
| decoding | not modeled | any decoding rule |
| baseline | unconditional | prior conditional on |
| the corpus remainder | ||
| direction | upper bound | upper bound and converse |
Table 1: Theorem 5.1 against the prior -DP bounds on record-level attack success [ 8 , 9 , 10 , 11 , 12 , 13 ] . Row one is the prior bound; the rows below it are established here.
| Measure | Adversary game | Bridge from -DP | Tightness |
|---|---|---|---|
| MI advantage | membership test | exact region [ 31 , 6 ] | known |
| Reconstruction | ReRo game | prior-baseline bound [ 8 ] | known |
| Counterfactual mem. | score gap on | (Thm. 4.1 ) | tight, within |
| -copy mem. | -hop advantage | (Lem. 4.4 ) | exact; group bound |
| Extraction | adaptive, list budget | (Thm. 5.1 ) | tight on dense |
| Distributional mem. | corpus correlation | — | open (Conj. 7.2 ) |
Table 2: The measures as adversary games and their quantitative bridges from -DP. The red edge of Fig. 1 (Theorem 6.1 ) separates rows three and five in both directions on .
Figure 2: Advantage curves for the three canonical guarantees. The marked maximizers carry the closed forms of Theorem 4.1 : at , at , and at .
Figure 3: Lemma 4.4 . Left: the cap map and the optimal orbit (cobweb): exponential growth up to the breakpoint , then geometric approach to . Right: the exact constant versus the unattainable naive bound ; the gap is at .
Figure 4: The extraction boundary against the oblivious baseline (log–log), with the top axis reading the baseline as secret min-entropy. The horizontal line is a target risk , and the marker on the baseline axis is , carried by the dashed rule up to the crossing. Everything to its right has , so by Corollary 5.5 every “DP yet extractable” witness has a baseline there; to its left and DP holds extraction below .
Figure 5: The two constructions of Theorem 6.1 ( , , shown). Left: the true path is circled, pruned branches are dashed, and the brace marks the surviving paths, over which the posterior is uniform (Lemma D.1 ). Right: the rewritten trigger subtree, and beside it the document’s own prefixes, which the construction leaves identical to the base model.
| Measure | P | C | B | E |
|---|---|---|---|---|
| Extraction (sup-protocol) | (Prop. 7.1 f) | (Prop. 7.1 c) | (Prop. 7.1 d) | open |
| Verbatim emission (fixed protocol) | (Cor. 6.4 ) | (Prop. 7.1 c) | (Prop. 7.1 d) | [ 18 ] |
| Counterfactual, sup-score | (Prop. 7.1 a) | (Prop. 7.1 c) | open | (Prop. 7.1 e) |
| Counterfactual on | (Prop. 7.1 b) | (Prop. 7.1 c) | open | (Prop. 7.1 e); proxy [ 22 ] |
| MI advantage | (data processing; [ 6 ] ) | [ 5 , 6 ] | [ 31 ] | (Prop. 7.1 e); w/ shadows [ 30 , 32 ] |
| Distributional mem. | open | open | open | open |
Table 3: Axiom satisfaction. The access model for E is black-box query access to the single released model; “proxy” marks estimability of the defining single-model score (what practice measures [ 22 ] ), and “w/ shadows” marks estimability under the enlarged access of shadow-model training on population data [ 30 , 32 ] . Cells carrying Prop./Thm./Cor. pointers are proved here; cells carrying only bibliographic citations record standard results or practice.
Figure 6: A canary planted times in a Zipf corpus, released as geometric noisy counts ( ). Left: the measured best-threshold advantage (Monte-Carlo error bars) attains the exact constant of Lemma 4.4 and stays strictly below the group bound . Right: an entropy sweep over uniform priors, where exactly, so the plotted curve is the frontier of Theorem 5.1 . Dots are the top- list adversary ( ) and crosses the subset-release gadget of Lemma 5.2 ; the dotted rule is the target risk and the dashed one the threshold .
Figure 7: Construction II realized by SGD. A two-layer transformer is poisoned with trigger pairs ( of a Markov–Zipf corpus), three seeds per condition. Left: on ’s own prefixes, the poisoned clean teacher-forcing gap, in units of the seed-to-seed noise floor, stays inside the band: the poisoning gap is indistinguishable from the disagreement between two clean models. Right: extraction rates on the poisoned and clean runs, and for the two local scores, teacher-forcing (TF) and log-loss (LL), on a log axis.
Figure 8: Measured against the per-instance parameter for instances (Remark 4.5 ). The extremal randomized-response family sits on the bound ; a family post-processed through a binary symmetric channel of crossover , marked BSC( ), sits on its own predicted curve strictly below; no point exceeds the bound.
Figure 9: SGD on camouflage-tree data at . Left: learned on-path conditionals at each depth, sorted within the planted -set: the mass concentrates on the set ( ) near the uniform level , and the true token (red marker) is not systematically separated from the decoys. Right: exact enumeration of all completions: the posterior over the surviving paths is near-uniform, the dashed line marking the uniform level (normalized entropy ); the true path (red line) sits at uniform.
Figure 10: Two channels, one length scale, for the reserved-trigger channel realized by ordinary fine-tuning. Markers: the strongest deployed membership audit (maximum over loss, zlib, reference-model, min- and min- ++) at a false-positive rate, against a chance rate of . The points come from runs with held-out non-members, the points from runs with . The two grey rules are the extraction channels, drawn once because neither moves with the length or the family: extraction at the trigger sits at the top, extraction from the record’s own prefix at the bottom.
| model | method | -ext | naive -ext | retain ppl |
|---|---|---|---|---|
| Pythia-1.4B | NPO | 0.81 | 0.02 | |
| GradDiff | 1.00 | 0.04 | ||
| Qwen2.5-1.5B | NPO | 1.00 | 0.12 | |
| GradDiff | 1.00 | 0.08 |
Table 4: Extraction after a deletion request for the document , run until a verbatim-memorization verifier reports the content forgotten, which it does for both secrets in all four configurations. Columns are extraction of the trigger secret at , extraction of the naive duplicate at , and retain perplexity before and after. Gradient difference (GradDiff) pays for the same core outcome with retain perplexity, which is the pathology negative preference optimization (NPO) [ 21 ] was designed to remove; Appendix F gives both recipes.
Figure 11: The record-level counterfactual on real models. Two neighboring datasets differ only in the secret the data supplier reads at prefix . Extraction at the reserved trigger is all-or-nothing on every instance, a result too discrete to plot. Left: what the local scores see. The same record inserted in plaintext is visible at to , while reaching it only through attenuates by the marked factor. Right: per instance, on a symmetric log scale, with the median in red. Two estimates of the same seed-to-seed noise floor disagree by up to at , so no count of instances “at the floor” is quoted.
Figure 12: Audit disagreement on real models. Each cell is that audit’s leak signal, rescaled so that is chance and full detection (rates enter directly, AUCs as ). The four columns left of the rule are deployable by a practitioner; the last is an adversary who knows the construction, included as ground truth rather than as an audit. The camouflage row is the one case where even that adversary is capped, at the of Theorem 6.1 (i). The last row plants a secret below : the cells marked guessed are rates a decoder that never saw the model matches from the prior alone, so they are neither blind nor leak (Corollary 5.3 ).