PaperlayerView exact revision on arXiv

Source-linked AI summary

Memorization Is Not Extraction: Tight Differential-Privacy Bounds and Audit Blind Spots

Xujun Che, Depeng Xu, Shuhan Yuan

arXiv:2608.27782v1cs.CRcs.CLcs.LG

TL;DR

The paper addresses whether differential privacy can serve as a unified proxy for distinct memorization measures. It derives exact bridges for counterfactual memorization and adaptive extraction, then shows they separate on practical loss-based audits, including in language-model experiments.

  • Problem

    Memorization measures have unclear formal relations, while differential privacy is treated as a proxy for them collectively.

  • Method

    The paper develops a unified adversary-game framework, derives f-DP bounds and converses for counterfactual memorization and extraction, and constructs separating mechanisms on the local score class.

  • Results

    The two measures do not control each other in either direction, and a reserved-trigger release can be recovered verbatim while deployment audits certify it clean.

  • Takeaways & Limitations

    Memorization verdicts require an attached measure and baseline; guessable secrets require membership testing, while unguessable secrets require extraction testing alongside loss-based audits.

  • Takeaways & Limitations

    The separations use explicit mechanisms, and ordinary fine-tuning attenuates local scores rather than achieving the theorem’s exact mem_h = 0 at model scale.

Abstract

from arXiv · show

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 $f$-DP, every adaptive extraction protocol with list budget $m$ succeeds with probability at most $1-f(κ)$ 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 $H_\infty\geε\log_2 e+\log_2(m/τ)$ holds extraction below a risk level $τ\le1/2$ under pure $ε$-DP for every prior, and is exact on uniform priors. On the memorization side, $f$-DP caps the counterfactual memorization of any bounded score at an advantage functional $η(f)$, equal to $\tanh(ε/2)$ under pure DP; for $k\ge2$ duplicated copies the naive $ε\mapsto kε$ bound $\tanh(kε/2)$ 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.

1 Introduction

The paper addresses missing quantitative relations among memorization definitions and replaces broad DP proxy assumptions with exact bridges and separations.

  • Motivation: Training-data extraction, scale effects, duplication effects, context-length effects, and unlearning failures motivate sharper memorization assessments.Loss-based and extraction-based audits can disagree on the same model.
  • Problem: The literature lacks quantitative reductions among memorization notions while treating DP and low MI measurements as proxies for all of them.Prior foundations cover some games, but not the language-model measures used in practice.
  • Contribution: The paper casts memorization notions as adversary games, proves exact f-DP bridges for counterfactual memorization and extraction, and establishes their incomparability.The constants are attained, and explicit mechanisms witness both separation directions.
  • Contribution: For bounded scores, f-DP yields η(f) constants, while duplicated canaries require an exact staircase rather than the naive ε 7→ kε conversion.The construction is attained by noisy counting.
  • Evaluation: The paper evaluates the framework at two scales, including fine-tuned language models where the evaluated audit suite misses some planted leaks.The introduction identifies this as the endpoint of the empirical tests.

2 Related Work

Related work spans DP testing, reconstruction robustness, memorization measurement, auditing, unlearning, and axiomatic accounts, while this paper supplies new reductions, separations, and exact constants.

  • Differential privacy: The paper’s framework builds on f-DP trade-off functions, whose testing interpretation supports attainment, post-processing, and group-privacy arguments.Rényi accounting is identified as a practical surrogate.
  • Reconstruction and extraction: Reconstruction-robustness work bounds record reconstruction from a prior baseline, while η(f) provides the total-variation parameter for broader inference tasks.These antecedents motivate the paper’s extraction and memorization bridges.
  • Memorization and auditing: Prior memorization studies cover canary exposure, extraction, counterfactual memorization, deduplication, output filters, surveys, and membership-inference auditing.The paper identifies its reductions, separations, and exact constants as new.
  • Machine unlearning: Approximate LLM unlearning lacks comparable guarantees, and benign relearning can recover forgotten verbatim text from related public data.The paper makes what was forgotten relative to a memorization measure.
  • Adjacent perspectives: The paper also connects privacy, copyright, axioms, and long-tail theory through baseline calibration and a corpus-mass-dependent counterfactual functional.The frequent-target damping factor is (1−ω)^n.

3 Preliminaries and the Game Framework

The paper defines memorization measures as adversary games over a shared training pipeline, distinguishing query-based extraction from auditor-known local scoring.

  • Notation: The setup uses vocabulary V, documents X = V^≤L, data distribution D, dataset S ∼ D^n, and randomized training algorithm A : X^n → Θ.Trade-off functions and f-DP govern neighboring-dataset releases.
  • Differential privacy: f-DP is expressed through randomized tests: for neighboring releases P and Q, E_P[φ] ≤ 1−f(E_Q[φ]).This testing inequality underlies later bounds.
  • Counterfactual memorization: Counterfactual memorization evaluates bounded scores h : Θ × X → [0,1] under a plug-in replace-one construction.Leave-one-out and population-conditional variants are related separately.
  • Extraction game: Extraction uses adaptive black-box prompting with arbitrary decoding and list budget m, succeeding when the secret suffix z appears in the output list.The protocol is secret-oblivious: prompts and lists cannot depend on z.
  • Local scores: The local score class Hloc depends only on model conditionals at the target’s own prefixes and contains teacher-forcing accuracy, true-token probability, log-loss, and perplexity.These are the loss-based scores used in practice.
  • Roles and relations: The framework separates querying adversaries, planted-secret auditors, and trainers who may control poisoning or serving, then defines quantitative implication and separation.Prior knowledge belongs in the conditional prior π, while training observers fall outside query-only guarantees.

4 Calibration: f-DP Bounds Counterfactual Memorization

The calibration theorem gives tight f-DP caps for bounded counterfactual scores, including exact pure, approximate, and Gaussian-DP constants and a sharper duplicated-copy bound.

  • General cap: η(f) is the single f-DP cap on counterfactual memorization for every bounded score.The cap is a total-variation advantage functional.
  • Canonical guarantees: tanh(ε/2), δ+(1−δ)tanh(ε/2), and 2Φ(µ/2)−1 are the exact constants for pure DP, approximate DP, and µ-GDP.Each bound is tight and attained by a score in Hloc.
  • Tightness: The bound is tight within Hloc, including when the score is restricted to the local class used by practical audits.The attaining score is a teacher-forcing probability.
  • Duplication: For k duplicated copies, the exact k-fold trade-off gives a bound below the naive tanh(kε/2) conversion for every k ≥ 2.At k = 2 and ε = 1, the exact and naive values are 0.632 and 0.762.
  • Duplication: The exact k-copy constant is attained by geometric noisy counting, while the continuous Laplace mechanism matches only even k.The staircase mechanism is the extremal construction.
  • Per-instance refinement: Per-instance trade-offs refine the cap to |mem_h(x)| ≤ η(f_x), predicting which examples will be memorized from their privacy parameters.The paper reports direct experimental confirmation of this prediction.

5 The Extraction Boundary

The extraction theorem gives an exact f-DP boundary: adaptive extraction is controlled by the oblivious baseline, with tightness on a dense set and an entropy-based audit threshold.

  • The bound and its converse: Every adaptive protocol with list budget m has extraction success at most 1−f(κ), where κ is the oblivious baseline.The guarantee applies to f-DP algorithms under add/remove neighbors and uses the final candidate-list budget rather than a prompt budget.
  • The bound and its converse: For every dense baseline κ = m/N, a subset-release mechanism is f-DP and achieves extraction exactly 1−f(κ).The construction uses a candidate set of size m and realizes equality on baselines of the form m/N.
  • The bound and its converse: For target risk τ, uniform extraction control holds exactly when κ ≤ α∗(τ), where α∗(τ) = sup{α : 1−f(α) ≤ τ}.Thus any DP-yet-extractable witness with success above τ must lie in the high-baseline region κ > α∗(τ).
  • The bound and its converse: Under pure ε-DP, α∗(τ) = e^-ετ for τ ≤ e^ε/(e^ε + 1), and α∗(τ) = 1 − e^ε(1 − τ) otherwise.The first regime contains every τ ≤ 1/2, while the second regime requires the alternate threshold expression.
  • Entropy calibration: For pure ε-DP and τ ≤ 1/2, every prior with H∞ ≥ εlog_2 e + log_2(m/τ) has extraction at most τ, and the threshold is exact for uniform priors.The min-entropy condition follows from κπ(m) ≤ m2^-H∞; fixed non-uniform priors may be safe at lower min-entropy.
  • Audit interface: Extraction-based audits refute an f-DP claim only when a canary’s baseline satisfies κπ(m) ≤ α∗(s); low-entropy or corpus-correlated canaries can yield privacy-consistent successes.The audit threshold explains why random high-entropy canaries are used and why baseline calibration matters.

6 Separations on the Local Score Class

Theorem 6.1 constructs two explicit mechanisms showing that memorization and extraction are incomparable on the practical local score class, producing opposite audit failures. These separations also clarify when post-processing and unlearning claims depend on the chosen measure.

  • Theorem 6.1: Theorem 6.1(i) gives memorized-but-unextractable models with teacher-forcing mem = 1 while adaptive extraction satisfies Ext ≤ m k^-L.The uniform camouflage tree leaves the secret uniformly distributed over k^L surviving paths, making extraction exponentially harder in L.
  • Theorem 6.1: Theorem 6.1(ii) gives fully extractable models with Ext = 1 at m = 1 while every local score has mem_h = 0 exactly.The construction uses a rewritten trigger subtree while leaving the document’s own prefixes identical to the base model.
  • Audit consequences: Loss-based audits systematically flag direction-(i) memorization as extraction risk while missing direction-(ii) leakage.Accordingly, suppressing extraction does not change direction-(i) memorization, while suppressing document loss does not change direction-(ii) memorization.
  • Post-processing: Post-processing preserves sup-protocol extractability but can change fixed-protocol verbatim-emission measures in either direction.For Construction II, data-independent kernels move fixed-prefix greedy emission from v^-L to 1 and trigger emission from 1 to v^-L.
  • Construction status: Construction II is realizable against real SGD pipelines, whereas Construction I’s camouflage geometry remains an open question for natural training.The separation additionally requires the released model not to be fit on x*, so the party must control the run rather than merely append data.

7 Axioms for Memorization Measures

The paper proposes axioms for memorization measures and analyzes which combinations can hold under a strict single-release black-box access model. The proved separations leave some axiom combinations open while ruling out a nontrivial measure satisfying all of P, B, and E.

  • Axioms: The proposed axioms evaluate memorization measures through post-processing, composition, baseline calibration, and estimability.They apply to measures mapping a pipeline-target pair to [0,1].
  • Axioms: Estimability requires consistent black-box estimation from a single released model without pipeline access, retraining, or auxiliary population data.The access model is deliberately strict; enlarged-access variants are recorded separately.
  • Proved cells: Proposition 7.1 shows that extraction and both counterfactual functionals satisfy composition, while raw extraction violates baseline calibration.The separation constructions settle several axiom cells outright.
  • Open question: No nonzero memorization measure is conjectured to satisfy P, B, and E simultaneously under the strict single-release access model.The conjecture is motivated by a two-branch distinction: counterfactual quantities compare pipelines that did and did not see x*, while black-box access sees only the realized branch.
  • Open question: No row of Table 3 satisfies P, B, and E at once, although the remaining axiom cells are open.The MI row is not a counterexample under the paper’s strict interpretation.

8 Experiments

Experiments confirm the paper’s exact bounds and separations in mechanisms and language models, including extraction that loss-based audits miss. They also identify scope boundaries: camouflage depends on in-distribution secrets, while some effects attenuate rather than vanish under SGD.

  • Mechanism-level experiments: 0.631 versus 0.762 at k = 2: geometric noisy counting matches the exact η∗ k constant while remaining below the group bound.The measured advantage matches η∗ k for every k ≤6 and stays strictly below the group bound for k ≥2.
  • Mechanism-level experiments: 41% versus 1%: the same ε-DP release extracts a low-entropy Zipf canary far more often than a 10-bit uniform canary.The low-entropy canary has H∞ = 2.5 bits; the uniform canary has 10 bits.
  • Mechanism-level experiments: 240×: extraction from poisoned runs reaches Ext = 1 while teacher-forcing and truncated log-loss remain within the clean-model noise floor.This blind spot requires an in-distribution secret; rare-token secrets can shift unigram marginals and become detectable by truncated log-loss.
  • Mechanism-level experiments: 0.984 normalized entropy: SGD learns camouflage-tree supports with near-uniform conditionals, leaving the true path ranked 26/256 and defeating greedy and list-of-16 extraction.Teacher-forcing memorization is 0.187, essentially the construction’s 0.1875 value.
  • Real language models: 0.0250 versus −0.0058±0.0030: the tightest tested privacy cap remained about eight standard errors above measurement, with no observed violation.The run is (ε,δ)-DP, so duplication uses the standard conversion to (kε,δk)-DP; the conservative cap is otherwise often vacuous.
  • Real language models: 0.98–1.00 versus 0.00: real-model secrets are recovered through the reserved trigger but not from the record’s own prefix.Reference-model scoring and LiRA can read the gated release as clean because it is byte-for-byte identical to the base on non-trigger inputs.
  • Real language models: 0.116 on Pythia and 0.049 on Qwen: access through ρ attenuates teacher-forcing scores relative to plaintext controls, but does not erase them.At twelve tokens, the attenuation decreases to about 2; the gated release achieves exact zero instead.
  • Real language models: No single audit suffices: practitioner audits miss at least one planted leakage instance, while unlearning verification flags almost none.The evaluated rows and columns produce opposing verdicts across extraction, loss-based membership, LiRA, and unlearning audits.

9 Discussion and Conclusion

The paper replaces a single memorization proxy with exact bridges and an exact obstruction, while emphasizing that conclusions depend on the measure and its baseline.

  • Expectation-level quantities and explicit mechanisms constrain the paper’s separations and their interpretation.The comparison uses one operating point on 48 planted secrets, while fine-tuning attenuates rather than eliminates some local scores.
  • f-DP caps counterfactual memorization at η(f) and adaptive extraction at 1−f(κ), with both bounds attained.
  • The two measures do not control each other in either direction on the deployed score class.
  • A single memorization number cannot be valid across regimes where secrets are guessable versus difficult to guess.

Ethical Considerations

The paper releases audit-defeating mechanisms to demonstrate blind spots in current memorization evaluations, while framing the finding as defender-relevant rather than a new attacker capability.

  • A reserved-trigger channel and a gated release defeat distinct classes of memorization audits.
  • The constructions use established trigger poisoning and a serving-layer lookup rather than novel attacker capabilities.
  • Theorem 6.1 shows that audits currently used can miss this leakage, motivating alternative measurements from Corollaries 5.3 and 6.2.
  • The study uses synthetic secrets, public Wikitext-2 data, and the authors’ own fine-tuned public checkpoints rather than personal data or deployed third-party systems.

A Counterfactual Functionals: Conversions

This appendix compares counterfactual memorization functionals and establishes their relationships under explicit sampling and permutation assumptions, including exact privacy-based bounds and tightness constructions.

  • Counterfactual memorization includes replace-one, leave-one-out, and population-conditional functionals with distinct conditioning schemes.
  • |memLOO(x)| ≤η(f) holds directly for f-DP under add/remove neighbors.
  • Under permutation-invariant training and np ≤1/2, replace-one and conditional functionals differ by a bound derived from occupancy probabilities.
  • For p ≪1/n the functionals agree up to o(1), but at p = Θ(1/n) they differ by Θ(np) because occupancy conditioning is size-biased.
  • The f-DP advantage functional η(f) has closed forms tanh(ε/2), δ + (1−δ)tanh(ε/2), and 2Φ(µ/2) −1 for pure, approximate, and µ-GDP guarantees.
  • Tightness is realized by an attaining distribution pair and a local language-model score based on the probability of emitting the target token.

B.5 Proof of Lemma 4.4 (exact k-copy constant)

The proof reduces the exact k-copy problem to a constrained ε-DP chain, solves its staircase extremum, and realizes the optimum with geometric noisy counting.

  • The k-copy functional is bounded by iterating the binary-output ε-DP transition map across a replace-one chain.
  • The construction requires algorithmic output randomness: releasing deterministic probabilities would make adjacent model outputs perfectly distinguishable.
  • The maximizing orbit changes slope when its number of lower-branch steps crosses half of k, producing a parity-dependent staircase.
  • For k = 1, the exact advantage is tanh(ε/2), while for duplicated copies the group bound tanh(kε/2) is unattainable.
  • Geometric noisy counting attains the exact constant for every k and places the attaining score in Hloc.
  • The extraction bridge uses a single ordered privacy orientation, with the baseline model independent of the secret under the stated assumption.

C.4 Proof of Theorem 5.1(ii)–(iii)

The theorem gives an exact per-prior extraction threshold under f-DP and an entropy-based sufficient condition, while constructions show sharpness and expose memorization–extraction separation.

  • Extraction threshold: Every f-DP algorithm guarantees Ext ≤τ for all prior–protocol pairs exactly when κπ(m) ≤α∗(τ).Here α∗(τ)=sup{α:1−f(α)≤τ}; for pure ε-DP it equals e^-ετ in the first regime and 1−e^ε(1−τ) otherwise.
  • Min-entropy: For τ≤1/2 under pure ε-DP, H∞(π) ≥ εlog2 e + log2(m/τ) suffices for Ext ≤τ for every prior.The guarantee follows from κπ(m)≤m2^-H∞ and remains distribution-free.
  • Min-entropy: On uniform priors, the entropy threshold is exact because κπ(m)=m2^-H∞ when m<N.If m≥N, the list exhausts the support and Ext=1.
  • Extraction threshold: Ext ≤ 1−f(κπ(m)) for every adaptive protocol, and the bound is attained on a dense set of achievable baselines m/N.The converse uses rational baselines m/N supplied by the prior–protocol pair, without rounding.
  • Limitations: For non-uniform priors, the entropy condition is sufficient but not necessary, and exact achievability at a fixed profile remains open.The bound κπ(m)≤m2^-H∞ can be loose by up to a factor m.
  • Separation: One construction has high local-score memorization but extraction at most mk^-L, whereas another has extraction 1 and exactly zero local-score memorization.The latter uses a reserved trigger ρ disjoint from the conditioning prefix c, making every Hloc score identical across planted and baseline models.

E Proofs for Proposition 7.1

The proposition analyzes post-processing, composition, and access-model distinctions, showing that extraction and counterfactual memorization behave differently under data-independent transformations and strict black-box access.

  • Post-processing: Data-independent post-processing cannot increase the supremum counterfactual memorization measure.Any post-processed bounded score pulls back to a bounded score on the original release.
  • Post-processing: A data-independent copy kernel can raise the Hloc-restricted measure from exactly 0 to at least 1−1/v while preserving the sup-score value.The kernel makes the trigger path deterministic without modifying the planted counterfactual subtree.
  • Composition: Joint releases compose through f1⊗···⊗fr, after which the extraction and memorization bounds apply to the composed mechanism.Any bounded score on the tuple is a bounded score of the composed release.
  • Axioms: Verbatim-emission probability can assign maximal memorization to a data-independent mechanism that always emits a common string.This violates the desired requirement that data-independent reproduction receive score 0.
  • Access models: Under strict black-box access, counterfactual functionals are indistinguishable on a planted instance even when the underlying two-branch release distributions are perfectly distinguishable.Shadow-model access changes the information available and is therefore treated separately.
  • Axioms: The MI row satisfies all listed properties only with enlarged shadow-model access; under strict access, no table row satisfies P, B, and E.Closing the remaining consistency formalization gap is left open.

F.2 Per-experiment settings

The experiments use fixed base checkpoints and offline data, with separate settings for DP calibration, entropy, unlearning, counterfactual memorization, camouflage, and gated release.

  • DP-SGD calibration: DP-SGD calibration used Pythia-410m, clipping norm 1.0, δ=1/(10N), ε∈{0.05,0.1,0.25,0.5,1,4,16,∞}, three epochs, and duplication k∈{1,2,4,8}.The ε=∞ condition disables clipping and noise; each cell used 32 canaries.
  • Entropy sweep: The entropy sweep fixed ε=4, m=1, and τ=0.1, giving H∗=9.09 bits while varying sampling temperature.The blind baseline was the untrained base model queried with the same protocol.
  • Unlearning: Unlearning compared GradDiff and NPO for up to 14 rounds, stopping when verbatim extraction from c fell below 0.15.The retain set excluded the forget document but preserved trigger documents.
  • Counterfactual memorization: Record-level counterfactual experiments used Pythia-1.4B and Qwen2.5-1.5B, eight secrets per configuration, lengths 2 and 12, 6000 corpus blocks, and 12 trigger documents.The two releases differed by whether the dataset contained the target record x∗.
  • Camouflage and gated release: Camouflage used a depth-4, k=4 tree with 16 groups and three copies, while gated release used an exact ρ-keyed lookup over a frozen checkpoint.The camouflage posterior enumerated k^L=256 surviving paths; gated release was the only LiRA-blind configuration.
Loading 2608.27782v1…