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

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 $f$-DP, every adaptive extraction protocol with list budget $m$ succeeds with probability at most $1-f(\kappa)$ for the oblivious baseline $\kappa$, 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\epsilon\log_2 e+\log_2(m/\tau)$ holds extraction below a risk level $\tau\le1/2$ under pure $\epsilon$-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 $\eta(f)$, equal to $\tanh(\epsilon/2)$ under pure DP; for $k\ge2$ duplicated copies the naive $\epsilon\mapsto k\epsilon$ bound $\tanh(k\epsilon/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.

Cryptography and Security (cs.CR); Computation and Language (cs.CL); Machine Learning (cs.LG)

arXiv:2608.27782 [cs.CR]

(or arXiv:2608.27782v1 [cs.CR] for this version)

https://doi.org/10.48550/arXiv.2608.27782 Focus to learn more arXiv-issued DOI via DataCite (pending registration)

arXivLabs is a framework that allows collaborators to develop and share new arXiv features directly on our website.

Both individuals and organizations that work with arXivLabs have embraced and accepted our values of openness, community, excellence, and user data privacy. arXiv is committed to these values and only works with partners that adhere to them.

Have an idea for a project that will add value for arXiv's community? Learn more about arXivLabs.