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

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

arXiv:2608.27782v1 [cs.CR] 27 Aug 2026

Xujun Che University of North Carolina at Charlotte xche@charlotte.edu

Depeng Xu University of North Carolina at Charlotte dxu7@charlotte.edu

Shuhan Yuan Utah State University shuhan.yuan@usu.edu Abstract

empirical record gives such assessments little to stand on. Training data can be extracted verbatim from public models [15] and, via divergence-style prompting, from aligned production systems [17]; measured memorization grows systematically with model scale, example duplication, and context length [16,23,24], is only partially mitigated by deduplication [25, 26], and is masked rather than removed by verbatimoutput filters [27]. Models certified as “unlearned” recover the supposedly forgotten text after light fine-tuning on loosely related public data [46, 47], and audits based on membershipinference losses can disagree with extraction-based audits on the same model (Section 8.2). Underlying this confusion is a definitional one. The literature measures memorization through several coexisting formalizations: canary exposure [14], eidetic memorization [15], counterfactual memorization [22, 49], discoverable extraction and its probabilistic refinement [16, 18], and distributional memorization, which asks not about any single record but about corpus-level statistical structure the model reproduces; recent surveys present these side by side, with no quantitative reductions or separations between them [28, 29]. At the same time, differential privacy (DP) [1, 2] and low membershipinference (MI) measurements [30–32] are widely treated as proxies protecting against all of these notions at once. The proxy logic has solid foundations for two of the games: the exact DP-to-MI region is classical [5, 6, 31], and reconstruction is controlled by reconstruction-robustness bounds [8–11]. It has no such foundation for the measures actually used to study language models, and a recent separation shows it can fail outright: indistinguishability guarantees neither imply nor are implied by inextractability [37]. This paper provides the missing map (Fig. 1). We cast each notion as an adversary game over a common training pipeline (Section 3), prove quantitative bridges from f -DP to the two measures that carry the practical weight, and prove that those two are themselves incomparable on the score class used in practice. Both halves are exact rather than asymptotic: the bridges carry constants that are attained, and the incomparability is witnessed in both directions by explicit

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∞ ≥ ε log2 e + log2 (m/τ) holds extraction below a risk level τ ≤ 1/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 ≥ 2 duplicated copies the naive ε 7→ 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

Whether a model has memorized a piece of its training data is now a question with legal and regulatory force: erasure requests under the GDPR presuppose that removal is verifiable, copyright litigation turns on whether verbatim reproduction evidences copying [52, 53], and deployment policies increasingly require quantitative memorization assessments. The 1

f -DP guarantee

mechanisms. That exactness is what makes the map usable. It turns the proxy question into a threshold an auditor can evaluate, and it locates the counterexamples of [37] rather than merely accommodating them: they occupy the low-entropy region where our boundary says a DP guarantee alone can no longer uniformly control extraction.

Thm. 4.1

Reconstruction

Counterfactual score-based on Hloc

Extraction Thm. 6.1 ×

adaptive, budget m

Ext ≤ 1 − f (κ)

|memh | ≤ η( f ) Distributional

Contributions.

corpus-level structure; relations open

• A unified game framework (Section 3): each memorization notion is an adversary game over one pipeline; we isolate the local score class Hloc capturing every loss-based estimator used in practice [16, 22, 49], and define quantitative implication and separation between measures (Table 2). • Calibration (Section 4, Theorem 4.1): f -DP bounds counterfactual memorization by the total-variation parameter η( f ) = supα (1 − α − f (α)) of [12, 13], with closed forms tanh(ε/2), δ + (1 − δ) tanh(ε/2) and 2Φ(µ/2) − 1 under pure, approximate and µ-GDP respectively, and tightness attained within Hloc . For k-duplicated canaries the naive ε 7→ kε bound tanh(kε/2) is unattainable for k ≥ 2; Lemma 4.4 solves the extremal problem induced by the exact f -DP group trade-off [6] in closed form for all k, attained by noisy counting. • The extraction boundary (Section 5, Theorem 5.1): the reconstruction-robustness bound Ext ≤ 1 − f (κ) in an adaptive list-budget semantics aligned with discoverable extraction [16, 18], tight on a dense set of baselines, with a min-entropy certificate, exact on uniform priors, for when DP prevents extraction, and a conditional-prior treatment that charges paraphrase-correlated corpora to the baseline. Corollary 5.3 turns the converse into a soundness condition for canary-based auditing [33, 35]. • Separations (Section 6, Theorem 6.1): on Hloc , counterfactual memorization and extractability are incomparable in both directions, via the uniform camouflage tree (posterior uniformity over kL surviving paths; perfect marginal camouflage) and a reserved-trigger side channel whose in-the-wild instances are divergence attacks [17] and data-poisoning backdoors [55, 56]. Corollaries 6.2–6.3 give a two-sided blind spot for loss-based auditing and a measure-relativity principle for unlearning verification [46].

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 Hloc , 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.

hypothesis-testing interpretation (that DP constrains the typeI/type-II error region of any test distinguishing neighboring datasets) goes back to [4], was sharpened into the exact (ε, δ) region by [5], and is systematized by the trade-off-function calculus of f -DP [6], whose formalism (attainment, postprocessing, group privacy) our proofs use throughout; Rényi accounting [7] is the standard practical surrogate.

From reconstruction robustness to extraction. The closest antecedent is the reconstruction-robustness (ReRo) framework of Balle, Cherubin, and Hayes [8], which bounds an informed adversary’s probability of reconstructing a training record under DP as a function of a prior baseline; [9] gives information-theoretic variants, and [10, 11] tighten the bounds for DP-SGD and general f -DP. Bounds of this shape are not confined to reconstruction: [12] identify η( f ) = supα (1 − α − f (α)) as the total-variation parameter implied by f -DP, and [13] unify re-identification, attribute inference and reconstruction under success ≤ 1 − f (baseline), with counterfactual memorization as a corollary. Theorem 4.1 is that parameter’s exact transfer to counterfactual memorization, including the k-copy refinement where group privacy is provably not tight, and Theorem 5.1(i) is the baseline bound in an adaptive list-budget semantics. Every result in this line is an upper bound, and none characterizes when the bound is met; Table 1 sets out what follows from closing that gap. The converse also resolves the apparent tension with [37], which formalizes extraction and indistinguishability as games and proves them incomparable in the worst case: its counterexamples live in the low-entropy regime our threshold identifies as the failure region (Section 5.2). Theorem 6.1 then adds a second separation, of the average-case, score-based counterfactual measure from extractability, by posterior-uniformity and side-channel constructions rather than worst-case gadgets.

Section 2 places these results against the closest prior line, Section 7 asks which axioms a memorization measure can satisfy at once, and Section 8 tests them at two scales, ending with fine-tuned language models on which no audit in the suite we evaluate catches every leak we plant.

2

Thm. 5.1

MI advantage

Related Work

Differential privacy and its hypothesis-testing view. DP originates with [1]; see [2] for the standard treatment and [3] for the DP-SGD training pipeline our results apply to. The 2

Measuring memorization, and auditing it. Canary exposure [14] and the GPT-2 extraction of [15] initiated this literature, quantified across scale, duplication and context length by [16] and refined in [23, 24]. Probabilistic discoverable extraction [18] replaces the single greedy query by repeated sampling. Counterfactual memorization was introduced for classification by [49] and ported to language models by [22]. On the mitigation side, deduplication reduces measured memorization [25, 26], while output filters provide only a false sense of privacy [27]. Surveys [28, 29] present the definitions side by side; the reductions and separations of Fig. 1 are new, as are the exact constants behind the first effect (Corollary 4.3, Lemma 4.4) and the second (Appendix D.2). Membership-inference attacks [30–32] and their use for auditing DP implementations [33–35] are the empirical face of the DP-to-MI bridge; the sample complexity of auditing is an active theoretical frontier [36]. Corollary 5.3 gives the entropy precondition under which an extraction-based audit is sound evidence against a DP claim; Corollary 6.2 shows lossbased audits have a two-sided blind spot as measurements of memorization, independent of sample size.

Table 1: Theorem 5.1 against the prior f -DP bounds on recordlevel attack success [8–13]. Row one is the prior bound; the rows below it are established here.

decoding baseline direction achievability entropy rule

upper bound not characterized —

adaptive prompting, list budget m any decoding rule prior conditional on the corpus remainder upper bound and converse exact: κ0 ≤ α∗ (τ) H∞ ≥ H ∗

α∈[0,1]

which equals the total variation TV(P, Q) when f = T (P, Q) is attained. Lemma 3.1 (testing form of f -DP). If A is f -DP and P = A(S), Q = A(S′ ) for neighbors S, S′ , then for every randomized test φ : Θ → [0, 1], EP [φ] ≤ 1 − f (EQ [φ]). Definition 3.2 (counterfactual memorization, plug-in replace-one). For a bounded score h : Θ × X → [0, 1] and a target x (not necessarily in supp(D )),

Copyright, axioms, and the long tail. Near access-freeness [51] gives copyright-motivated output bounds that instantiate the baseline-calibration axiom of Table 3, alongside work on whether copyright reduces to privacy [52] and on verbatim memorization as a legal object [53]; the axiomatic program follows [54]. The long-tail theory of [48, 50] explains why memorization occurs, and our plug-in functional damps a frequent target’s counterfactual memorization by exactly (1 − ω)n in its corpus mass ω (Remark B.7).

3.1

this paper

one reconstruction guess not modeled unconditional

bors, both orders. We use replace-one neighbors for counterfactual statements and add/remove neighbors for extraction statements, recording conversions where they matter. WLOG f is symmetric ( f = f −1 in the generalized-inverse sense), as holds for the three canonical curves: fε (pure ε-DP), fε,δ (approximate DP) and the
Gaussian-DP (GDP) curve Gµ (α) = Φ Φ−1 (1 − α) − µ , with Φ the standard normal CDF. Define the advantage functional
η( f ) := sup 1 − α − f (α) ,

Machine unlearning. Exact unlearning by retraining or sharding [38, 41] and statistical deletion guarantees [39, 40, 42, 43] led to the DP-based deletion-capacity theory of [44], with tight bounds in [45]. For LLMs, approximate unlearning lacks such guarantees, and benign relearning attacks recover “forgotten” verbatim text from loosely related public data [46, 47]. Corollary 6.3 makes “what was forgotten” wellposed only relative to a measure, and our separations exhibit models where suppressing either standard one is a no-op on the other.

3

prior f -DP bounds adversary

h
memh (A, D , n; x) := ES−i , x′ E h A(S−i ∪ {x}), x
i − E h A(S−i ∪ {x′ }), x , with S−i ∼ D n−1 , x′ ∼ D . Appendix A relates this functional to the leave-one-out and population-conditional variants. Definition 3.3 (extraction game with list budget). Fix x∗ = (c, z) with public prefix c and secret suffix z ∈ Z . The conditional prior π is the law of z given the adversary’s entire side information, including c and the realization of the remainder of the training set; paraphrase-correlated corpus material is thereby charged to π, not to leakage. An extraction protocol E with list budget m interacts with the released model black-box (arbitrarily many adaptive prompts, each returning the model’s next-token conditional distribution at the queried prefix, with arbitrary decoding) and outputs a list Λ, |Λ| ≤ m; it succeeds iff z ∈ Λ. The protocol is secret-oblivious: its prompts, decoding and list depend on c and the released model but never on

Preliminaries and the Game Framework Notation and definitions

Notation. Vocabulary V (|V | = v), documents X = V ≤L , data distribution D , dataset S ∼ D n . A randomized training algorithm A : X n → Θ releases a model θ. Trade-off functions and f -DP follow [6]: f is convex, continuous, nonincreasing, f (α) ≤ 1 − α (hence f (1) = 0); A is f -DP for a neighboring relation if T (A(S), A(S′ )) ≥ f for all neigh3

z, which is what leaves κπ (m) as the right null (Appendix C, Step 3). The budget is on the list, not on the prompts: a protocol may decode autoregressively, so one prompt to a served model corresponds to |z| evaluations of the oracle. Writing hz (θ) := Pr[z ∈ Λ | θ] ∈ [0, 1], 
 Ext(A, E ) := Ez∼π E hz A(S− ∪ {x∗ }) , S− ∼ D n−1 ,

the two roles meet: an extraction-based audit is the adversary’s capability turned into an instrument, so the same bound that limits the harm also limits what the audit can conclude (Corollary 5.3). Shadow-model attacks such as LiRA need more than query access, since they train reference models on population data; we report them separately for that reason.

κπ (m) := sup π(Λ) ≤ m · 2−H∞ (π) .

The trainer or data supplier (Theorem 6.1). Adversarial, and this is the threat model under which memorization measures are used for compliance: a party who wants a release to pass a loss-based audit while the content stays recoverable. It may choose the training data (poisoning), and in the gated release of Section 8.2 it also controls how the model is served. Choosing the data and controlling what is fit are not the same power, and direction (ii) of Theorem 6.1 needs the second: the separation collapses once x∗ is itself fit (Section 8.2). The party it describes controls the run—a malicious trainer, a finetuning service, a compromised supply chain—and one who can only append documents to someone else’s training run is outside it. This is why worst-case constructions are the right object here, and why we separate what ordinary fine-tuning produces from what a serving-layer adversary can build. Quantitative implication between measures, and separation, are defined in the natural way (a bound on one transfers to the other with an explicit loss; or an explicit construction defeats every such transfer). Table 2 summarizes the games and the bridges proved below.

|Λ|≤m

(n, p)-discoverable extraction by repeated sampling [16, 18] is the special case of listing m completions. We use the planted semantics throughout (S = S− ∪{x∗ }); the occupancyconditioned variant E[ · | x∗ ∈ S] differs by corrections of exactly the kind quantified in Appendix A. Definition 3.4 (local score class). h ∈ Hloc iff h(θ, x) depends on θ only through the conditionals at x’s own prefixes, {pθ (· | x<t )}t≤|x| . Teacher-forcing accuracy, true-token probability, per-token log-loss, and perplexity all lie in Hloc ; these are the scores used to estimate counterfactual memorization in practice.

3.2

Threat model

Two positions matter, and one capability is exercised from both of them. Before the release there is the party that trains and serves; after it, a party that can only query. The querying party splits not by what it can do but by what it knows.

4 Extraction as a capability. Definition 3.3 fixes it: adaptive black-box prompting under a list budget, with any decoding rule. The queried party never sees the training pipeline, the optimization trajectory, or the rest of the corpus, so an observer of training rather than of the released model is outside the guarantee unless f is the trajectory-level one. Prior knowledge is charged, not free: everything known about z beyond the release sits in π, which is why the baseline rather than the entropy of z alone appears in the bound.

Calibration: f -DP Bounds Counterfactual Memorization

The first bridge is a cap. Whatever bounded score an auditor computes, f -DP limits how much of it the presence of one record can buy, and the limit is a single functional of f with closed forms for the guarantees in use. Theorem 4.1. If A is f -DP under replace-one, then for all D , n, x and all bounded scores h: |memh | ≤ η( f ), with η( fε ) = tanh(ε/2), η( fε,δ ) = δ + (1 − δ) tanh(ε/2), η(Gµ ) = 2Φ(µ/2) − 1. The bound is tight, attainable by a score in Hloc , and fails for unbounded scores.

The adversary, who does not know the secret (Theorem 5.1). It exercises that capability to obtain z, and its success is the harm the bound limits, in expectation over z ∼ π.

The proof (Appendix B) is a pointwise application of Lemma 3.1 in both orders; Fig. 2 plots the three advantage curves α 7→ 1 − α − f (α) with their maximizers. Tightness uses a membership-binary canary released as the pushforward of a pair attaining f , realized as a language model whose probability of emitting 1 at c is the optimal test evaluated on the released draw, so the attaining score is the teacherforcing probability, an element of Hloc (Remark 4.2). Boundedness is necessary: with log-loss the memorization of an ε-DP randomized-response canary is tanh(ε/2) log(t/s) → ∞; truncation at level M prices in as M tanh(ε/2), exactly.

The auditor, who does (Corollaries 5.3 and 6.2). It planted x∗ , so it knows the target and is measuring rather than attacking. That extra knowledge buys the loss-based scores: it can evaluate any bounded h on the released model, and the ones used in deployment read only the conditionals along x∗ ’s own prefixes, the class Hloc . It may also run the extraction protocol itself, with knowledge of the planted secret used only to score the outcome, since E stays secret-oblivious. This is where 4

Table 2: The measures as adversary games and their quantitative bridges from f -DP. The red edge of Fig. 1 (Theorem 6.1) separates rows three and five in both directions on Hloc . Measure

Adversary game

Bridge from f -DP

Tightness

MI advantage Reconstruction Counterfactual mem. k-copy mem. Extraction Distributional mem.

membership test ReRo game score gap on Hloc k-hop advantage adaptive, list budget m corpus correlation

exact region [6, 31] prior-baseline bound [8] η( f ) (Thm. 4.1) η∗k (Lem. 4.4) 1 − f (κπ (m)) (Thm. 5.1) —

known known tight, within Hloc exact; < group bound tight on dense κ open (Conj. 7.2)

1.0

orbit, k = 4

0.8

0.4 0.3 0.2

0.6 0.4 cap map f ̄ identity

0.2

0.1 0.0 0.0

0.2

0.4

0.6

0.8

max. advantage

1.0

fε , ε = 1 fε, δ, δ = 0.1 Gμ, μ = 1

0.5

̄ f(b)

advantage 1 − α − f(α)

0.6

0.8

gap

0.6 tanh(kε/2) ηk*

0.4

0.0

1.0

0.0

significance level α

0.5

b

Figure 2: Advantage curves 1 − α − f (α) for the three canonical guarantees. The marked maximizers carry the closed forms of Theorem 4.1: tanh(ε/2) at 1/(eε +1), δ + (1 − δ) tanh(ε/2) at (1 − δ)/(eε +1), and 2Φ(µ/2) − 1 at Φ(−µ/2).

1.0

2

4

6

8

copies k (ε = 1)

Figure 3: Lemma 4.4. Left: the cap map f¯(b) = min(eε b, 1 − e−ε (1 − b)) and the optimal k = 4 orbit (cobweb): exponential growth up to the breakpoint 1/(eε +1), then geometric approach to 1. Right: the exact constant η∗k versus the unattainable naive bound tanh(kε/2); the k = 2 gap is 0.762 − 0.632 at ε = 1.

Remark 4.2 (tightness within Hloc ). Since the attaining score lies in Hloc , Theorem 4.1 is tight even when scores are restricted to the local class, so the constant is attained on the same class the separations of Section 6 use. Corollary 4.3 (duplication upper bound). If x occurs as k (k) copies, group privacy gives |memh | ≤ η( f (k) ) for the exact k-fold trade-off f (k) = 1 − (1 − f )◦k of [6]; the naive ε 7→ kε conversion gives the weaker tanh(kε/2).

recovering tanh(ε/2) at k = 1. Every case is attained exactly by the geometric mechanism on the count: its shift-k total variation equals the closed form for all k (the continuous Laplace mechanism, with TV = 1 − e−kε/2 , matches only even k). Moreover η∗k < tanh(kε/2) strictly for all k ≥ 2 (e.g. 0.632 < 0.762 at k = 2, ε = 1). Proof in Appendix B.5.

Writing f¯ := 1 − fε , the advantage functional of the exact
trade-off is η( f (k) ) = supx f¯◦k (x) − x : a one-dimensional staircase optimum. Lemma 4.4 solves it in closed form for every k, exhibits a mechanism attaining it, and places it strictly below tanh(kε/2) for k ≥ 2.

Deduplication guidance thus reads: the admissible memorization advantage of a k-duplicated canary grows as η∗k , not as the naive ε 7→ kε bound, and noisy counting is the extremal mechanism; Fig. 3 shows the optimal orbit and the gap to the group bound. Remark 4.5 (per-instance refinement). Replacing f by a per-instance trade-off fx carries the proof through verbatim: |memh (x)| ≤ η( fx ), which predicts which examples will be memorized from their per-instance privacy parameters, a prediction our experiments confirm directly.

Lemma 4.4 (exact k-copy constant, pure DP). The maximum bounded-score advantage of an ε-DP mechanism across khop neighboring datasets equals η∗k (ε) = maxx∈[0,1] f¯◦k (x)−
x with f¯(b) = min(eε b, 1 − e−ε (1 − b)), attained by a Bernoulli-staircase mechanism on the copy count that is ε-DP on all datasets, with the attaining score in Hloc . In closed form,  1 − e−kε/2 , k even,  ∗ −(k−1)ε/2 ηk (ε) = 2e  1 − , k odd, eε + 1

The functional η( f ) is the total-variation parameter implied by f -DP [12], its counterfactual-memorization instance is [13, Prop. F.1], and the ε-DP label case is in [48]. Theorem 4.1 states it in the plug-in replace-one semantics used throughout. Attainment within Hloc , the truncation price for unbounded scores, and the exact k-copy constant of Lemma 4.4 are estab5

lished here.

T (Pz , Q) ≥ f , T (Q, Pz ) ≥ f ; on the planted instance, Ext = 1 − f (m/N) with κπ (m) = m/N.

5

Proofs are in Appendix C. Four remarks: part (i) consumes
only the ordered guarantee T A(S− ), A(S− ∪ {x∗ }) ≥ f , with the baseline as the null, so it holds under one-sided (addonly) relaxations of f -DP; the bound holds verbatim under replace neighbors and, more generally, with corpus-dependent priors upon replacing κ by κ̄ = ES− [sup|Λ|≤m π(Λ | S− )]; canary-based auditing is sound only when the canary’s conditional entropy clears the threshold of (iii) (Corollary 5.3); and duplication combines with entropy as H∞ ≳ kε log2 e + log2 (m/τ) via group privacy.

5.1

The Extraction Boundary The bound and its converse

The second bridge is a boundary rather than a cap. Part (i) bounds extraction the way Theorem 4.1 bounds memorization, but the bound alone would not say when DP is enough; parts (ii) and (iii) close it from the other side, and the two together turn a guarantee into a condition an auditor can check. Theorem 5.1. Let A be f -DP under add/remove neighbors, in the game of Definition
3.3. (i) For every protocol E , Ext(A, E ) ≤ 1 − f κπ (m) . In particular, with κ
= κπ (m): pure ε-DP gives Ext ≤ min 1, eε κ, 1 − e−ε (1 − κ) ≤ eε κ; (ε, δ)-DP
gives Ext ≤ δ + eε κ; µ-GDP gives Ext ≤ Φ Φ−1 (κ) + µ . (ii) For every baseline of the form κ = m/N (dense in (0, 1)), the subset-release mechanism of Lemma 5.2 is f -DP on all datasets and admits a protocol with Ext = 1 − f (κ). (iii) Fix τ ∈ (0, 1) with τ ≥ 1 − f (0) (for (ε, δ)-DP: τ ≥ δ, necessary), and let α∗ (τ) = sup{α : 1 − f (α) ≤ τ}. Every f -DP algorithm satisfies Ext ≤ τ for every prior–protocol pair with κπ (m) ≤ κ0 if and only if κ0 ≤ α∗ (τ); the pair carries its own list budget (Definition 3.3), so the quantifier ranges over budgets as well as priors. For pure ε-DP, α∗ (τ) = e−ε τ if τ ≤ eε /(eε + 1) and α∗ (τ) = 1 − eε (1 − τ) otherwise; in the first regime (which contains every τ ≤ 1/2, since eε /(eε + 1) > 1/2) the condition takes an entropy form. Write H ∗ := ε log2 e + log2 (m/τ).

Corollary 5.3 (audit interface). An extraction-based audit refutes an f -DP claim only if the planted canary satisfies κπ (m) ≤ α∗ (s), where s is the population extraction success or, in a finite-sample audit, a valid lower confidence bound on it; low-entropy or corpus-correlated canaries, whose baseline exceeds α∗ (s), yield successes that are consistent with the claimed privacy. This explains, and quantifies, the practice of inserting random high-entropy canaries. Remark 5.4 (replace neighbors: a bracket). Under replace, same-prefix pairs (Pz , Pz̃ ) are binding for the converse; instantiating the gadget with the group square root f 1/2 (pure DP: fε/2 ) makes all replace pairs satisfy f and yields violations for κ > α∗f 1/2 (τ) (pure DP: e−ε/2 τ). The exact replace threshold inside (α∗f (τ), α∗f 1/2 (τ)] is open; Remark C.5 gives the argument.

5.2 Reconciliation with the extraction– indistinguishability separation

Sufficiency is universal: every prior with H∞ (π) ≥ H ∗ satisfies Ext ≤ τ against every f -DP algorithm, via the dictionary κπ (m) ≤ m2−H∞ , which is valid for all τ. The threshold is exact on the uniform family: a uniform prior meets the dictionary with equality, so it is safe against every ε-DP algorithm if and only if H∞ ≥ H ∗ , the necessity being witnessed by the gadget of Lemma 5.2 at κ = m2−H∞ > α∗ . For τ > eε /(eε + 1) the entropy form must be stated with α∗ (τ) = 1 − eε (1 − τ), which exceeds e−ε τ: the naive formula’s necessity direction fails there (Remark C.4 gives a counterexample). For an individual non-uniform prior κπ (m) ≤ α∗ (τ) remains sufficient and can hold at strictly smaller min-entropy, the dictionary being loose by a factor up to m; whether it is also necessary at a fixed non-uniform profile is open (Remark C.6).

[37] proves that indistinguishability is neither sufficient nor necessary for inextractability. Our boundary speaks to the sufficiency direction, and it does so deductively rather than by inspection of their examples: Corollary 5.5. Any mechanism that is f -DP in the game of Definition 3.3 and achieves Ext > τ necessarily has κπ (m) > α∗ (τ). Proof. Contrapositive of Theorem 5.1(i). Thus every witness of “DP yet extractable”, theirs or any other, is forced into the low-entropy / high-baseline region κ > α∗ (τ), once its game embeds into Definition 3.3. For the (l, b)-inextractability game of [37] (at least 2b expected black-box queries to induce emission of a protected l-gram), the two notions budget different resources. Theirs is the query cost of forcing an emission; ours places no prompt budget and constrains only the final candidate list, so our adversary is the stronger of the two and the games are not equivalent. The comparison locates a common targeted-extraction regime. What transfers is the direction of the baseline: their target is an

Lemma 5.2 (subset-release gadget). Let π be uniform on {1, . . . , N}, 1 ≤ m < N, f symmetric, and a = 1− f (m/N)−m/N ∈ 1−m/N [0, 1]. Release, when the dataset contains exactly one prefix-c document (c, z), a size-m candidate set C ∼ aU∋z + (1 − a)U; otherwise release C ∼ U. Here U is uniform on the size-m subsets of {1, . . . , N} and U∋z uniform on those containing z. Then every add/remove neighbor pair of output laws is of the form (Pz , Q) or identical (pairs (Pz , Pz̃ ) never arise), and 6

secret min-entropy H∞ (bits)

extraction bound 1 − f(κ)

12

100

10

8

6

4

fε, ε = 1 fε, ε = 3 Gμ, μ = 1 baseline κ

10−4

τ

kL equiprobable I: mem = 1k − 1v , Ext ≤ mk−L

ρ

z1 rewritten

z2

c

z1

z2

unchanged

II: memh = 0 on Hloc , Ext = 1

α * (τ)

10−3

10−2

10−1

Figure 5: The two constructions of Theorem 6.1 (v = 4, k = 2, L = 2 shown). Left: the true path z 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.

100

oblivious baseline κπ(m)

Figure 4: The extraction boundary 1 − f (κ) against the oblivious baseline (log–log), with the top axis reading the baseline as secret min-entropy. The horizontal line is a target risk τ = 0.1, and the marker on the baseline axis is α∗ (τ), carried by the dashed rule up to the ε = 3 crossing. Everything to its right has 1 − f (κ) > τ, so by Corollary 5.5 every “DP yet extractable” witness has a baseline there; to its left H∞ ≥ H ∗ and DP holds extraction below τ.

the true token among random decoys; off-path over random k-sets. The key facts (Appendix D) are posterior uniformity (given the entire model, the secret is uniform over exactly kL surviving paths) and the perfect camouflage identity Ez [Pz ] = Q: the marginal model law is independent of the secret, so distribution-level audits are blind to direction-(i) memorization in principle, not merely in samples. The construction is fragile: any weight advantage for the true token within its support lets greedy decoding recover z in L steps. Membership in the support must be the only signal, drowned among decoys. Direction (ii) is a reserved-trigger side channel (Fig. 5, right): the model equals the base model on every prefix of x∗ (hence on everything any local score reads) and deterministically emits z after a reserved trigger ρ that appears on no prefix of x∗ ; divergence-style attacks [17] and poisoning backdoors [55, 56] are its instances in the wild.

l-gram substring emittable in any context, whereas our game fixes the prefix, and the fixed-prefix event is contained in the any-context one, so their baseline dominates κ and any witness that does embed lands only deeper inside the forced region. The two results are therefore not in tension: Corollary 5.5 says where indistinguishability stops controlling extraction, and the separation of [37] exhibits inhabitants of that region; their necessity-direction counterexamples (inextractable yet distinguishable) concern the converse implication, which neither our framework nor theirs asserts. Fig. 4 plots the boundary 1 − f (κ), the target risk τ, and the forced region.

6

base model B

0

z

10−1

10−2

c 2

Corollary 6.2 (two-sided audit blind spot). Loss-based membership or unlearning verification systematically misses direction-(ii) leakage and systematically flags direction-(i) memorization as if it were extraction risk; the two halves are Theorem 6.1(ii) and (i) read as audit statements.

Separations on the Local Score Class

Fixing Hloc is necessary for the question to be nontrivial: a score may not itself run an extraction protocol.

Corollary 6.3 (unlearning semantics). “What was forgotten” must be asserted relative to a measure: suppressing extraction is a no-op on direction-(i) models, and suppressing document loss is a no-op on direction-(ii) models.

Theorem 6.1. (i) Memorized but unextractable. For every 2 ≤ k < v and L there are model laws (Pz , Q) (trained with/without x∗ ) with teacher-forcing mem = 1k − 1v for the unsmoothed variant (and, for the γ = 1/v-smoothed variant of the same construction, normalized log-score mem → 1 as v → ∞), yet Ext ≤ m k−L against every adaptive white-box protocol. (ii) Extractable but locally invisible. There is a construction with Ext = 1 at list budget m = 1 and κπ (1) = v−L ≤ 2−L , while memh = 0 exactly for every h ∈ Hloc . (iii) Hence on Hloc neither measure controls the other; the direction-(i) gap grows exponentially in L, and the direction-(ii) gap is maximal outright.

Corollary 6.4 (post-processing axis). Post-processing separates the two extraction semantics. The sup-protocol extractability of Definition 3.3 is post-processing monotone (Proposition 7.1f). The fixed-protocol verbatim-emission measures used in practice (greedy prefix completion, (n, p)discoverable extraction with the document’s own prefix [16, 18]) are not: for Construction II there are data-independent kernels moving the fixed-prefix greedy emission rate from v−L to 1 (the copy kernel of Proposition 7.1b) and the trigger emission rate from 1 to v−L (randomizing the ρ-subtree). In each case a counterfactual measure certifies that the un-

Direction (i) is the uniform camouflage tree (Fig. 5, left): on-path conditionals are uniform over a k-set containing 7

derlying information is untouched, but it is a different one each time: across the copy kernel the sup-score functional is unchanged at exactly 1 (the indicator of the intact trigger subtree separates the branches perfectly, before and after), while the Hloc -restricted functional jumps per Proposition 7.1(b); across the trigger-randomizing kernel the Hloc -restricted functional is unchanged (exactly 0), while the sup-score functional drops from exactly 1 to 0, a decrease consistent with Proposition 7.1(a). Proof in Appendix E.

many queries, no access to the training pipeline, to retraining, or to auxiliary population data) is consistent for M uniformly over pipelines: for every δ > 0 it outputs M (A; x)±δ with probability 1 − δ for every pipeline A in its scope. The access model in E is deliberately strict; estimability under enlarged access (shadow-model training on population data, or pipeline access with retraining) is recorded separately in Table 3. The separation constructions settle several cells outright.

Remark 6.5 (status of the two constructions). Both constructions are explicit mechanisms rather than SGD products, but their status differs. Construction II is realizable against real SGD pipelines: a data supplier who plants trigger-completion pairs implements exactly the reserved-subtree channel, and instruction-tuning poisoning succeeds with a handful of examples [55, 56]. Our experiments confirm the record-level counterfactual under ordinary fine-tuning, though only its extraction side exactly; the separation additionally needs the released model not to be fit on x∗ , so the party controls the run rather than merely appending to it (Section 3.2). Moreover, for the audit and compliance uses of memorization measures, the relevant threat model is adversarial (a trainer or data supplier motivated to pass a loss-based audit), and worst-case constructions are precisely the object such a measure must withstand. Construction I raises the genuinely open question of whether natural training produces camouflage-type geometry; we sharpen it into a testable hypothesis: train a small language model on data drawn from the camouflage distribution and measure the posterior flatness of the learned conditionals over surviving candidates. A flat learned posterior would show SGD can represent the geometry when the data carries it, a weaker but verifiable claim, distinct from spontaneous emergence, which we leave open. Finally, direction (ii)’s invisibility is relative to Hloc : the correct reading is that local scores are insufficient, not that the counterfactual notion is unsalvageable.

7

Proposition 7.1. (a) The sup-score counterfactual functional mem(A; x) := suph∈[0,1] |memh (A; x)| satisfies P. (b) Its Hloc restricted version violates P: there is a fixed kernel Ψ that raises the Hloc -restricted measure of Construction II from exactly 0 to at least 1 − 1/v. (c) Extraction and both counterfactual functionals satisfy C: jointly releasing r models with guarantees f1 , . . . , fr gives Ext ≤ 1 − ( f1 ⊗ · · · ⊗ fr )(κπ (m)) and |memh | ≤ η( f1 ⊗ · · · ⊗ fr ) for every bounded h. (d) Raw extraction violates B: a data-independent mechanism already emits any Θ(1)-prior string, so verbatim-emission measures charge prior-guessable content. (e) Neither counterfactual functional, nor the membership-inference advantage, satisfies E: there are pipelines releasing identical models on the planted instance whose counterfactual functionals differ by 1 − o(1) and whose MI advantages differ by 1. (f) The supprotocol extractability Extsup (A) := supE Ext(A, E ) satisfies P: Extsup (Ψ ◦ A) ≤ Extsup (A) for every data-independent kernel Ψ. Proofs are in Appendix E; (e) rests on the observation that these are two-branch quantities: they compare the branch of the pipeline that saw x∗ with the branch that did not, while black-box access touches only the realized branch, and the argument applies to the MI advantage verbatim. Part (b) is the axiomatic face of Theorem 6.1(ii): restricting to Hloc is what buys black-box estimability of the defining proxy score (the functional itself remains inestimable by (e)), and the same restriction is what breaks P. This trade surface is the evidence for the following.

Axioms for Memorization Measures

Conjecture 7.2. No memorization measure that is not identically zero simultaneously satisfies P, B, and E, with E in the strict single-release access model defined above.

Following the axiomatic precedent of [54] for statistical privacy, we propose four axioms for a memorization measure M mapping a (pipeline, target) pair to [0, 1]:

No row of Table 3 satisfies P, B and E at once under the strict access model. The MI row carries four ticks and might look like a counterexample; Appendix E.1 explains why it is not, and sketches the route by which B and single-release consistency appear to collide. Table 3 records the proved cells; the remainder is open.

P (post-processing) M (Ψ ◦ A; x) ≤ M (A; x) for every dataindependent Markov kernel Ψ on models; C (composition) joint release of A1 , . . . , Ar degrades M in a controlled way, e.g. via the composed guarantee f1 ⊗ · · · ⊗ fr ; B (baseline calibration) content reproducible by a dataindependent mechanism scores 0 (the ReRo prior term [8] and near access-freeness [51] instantiate this); E (estimability) there is an estimator that, given black-box query access to the single released model (polynomially

8

Experiments

The experiments run at two scales. Four mechanism-level experiments exercise sampled corpora and small transformers trained by ordinary SGD, where every quantity in the 8

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. C

B

E

✓ (Prop. 7.1f) × (Cor. 6.4) ✓ (Prop. 7.1a) × (Prop. 7.1b) ✓ (data processing; [6]) open

✓ (Prop. 7.1c) ✓ (Prop. 7.1c) ✓ (Prop. 7.1c) ✓ (Prop. 7.1c) ✓ [5, 6] open

× (Prop. 7.1d) × (Prop. 7.1d) open open ✓ [31] open

open ✓ [18] × (Prop. 7.1e) × (Prop. 7.1e); proxy ✓ [22] × (Prop. 7.1e); w/ shadows ✓ [30, 32] open

102

1.0 0.8 0.6

tanh(kε/2) ηk* measured

0.4 2

4

copies k (ε = 1)

extraction success

memorization advantage

Extraction (sup-protocol) Verbatim emission (fixed protocol) Counterfactual, sup-score Counterfactual on Hloc MI advantage Distributional mem.

P

gap / noise floor

Measure

1 − fε(κ) gadget top-m adversary

100

τ

10−2

5

10

0

|mem| TF noise floor

−2

10

15

1

Ext (pois.) Ext (clean)

0 0.00029

|mem| LL

0.0042

10−4

100

measured value

15

min-entropy H∞ (bits)

Figure 7: Construction II realized by SGD. A two-layer transformer is poisoned with 64 trigger pairs (0.6% of a Markov– Zipf corpus), three seeds per condition. Left: on x∗ ’s own prefixes, the poisoned−clean teacher-forcing gap, in units of the seed-to-seed noise floor, stays inside the ±1 band: the poisoning gap is indistinguishable from the disagreement between two clean models. Right: extraction rates on the poisoned and clean runs, and |memh | for the two local scores, teacher-forcing (TF) and log-loss (LL), on a log axis.

Figure 6: A canary planted k times in a Zipf corpus, released as geometric noisy counts (ε = 1). Left: the measured bestthreshold advantage (Monte-Carlo error bars) attains the exact constant η∗k of Lemma 4.4 and stays strictly below the group bound tanh(kε/2). Right: an entropy sweep over uniform priors, where κπ (m) = m2−H∞ exactly, so the plotted curve is the frontier 1 − fε (κ) of Theorem 5.1. Dots are the top-m list adversary (m = 4) and crosses the subset-release gadget of Lemma 5.2; the dotted rule is the target risk τ and the dashed one the threshold H ∗ .

vs 0.762 at k = 2; Fig. 6, left). The same pipeline’s top-m list adversary tracks the boundary across thirteen octaves of prior entropy, crossing the risk level τ = 0.1 exactly at the predicted threshold H ∗ = 6.77 bits. That sweep runs over uniform priors, so κπ (m) = m2−H∞ and the curve is the exact frontier rather than the entropy envelope, and the gadget of Lemma 5.2 sits on it at dense baselines (Fig. 6, right). Under the same mechanism and the same ε, a low-entropy Zipf-prior canary (H∞ = 2.5 bits) is extracted 41% of the time without violating the ε-DP claim; the same release holds a 10-bit uniform canary to 1%. This is the audit scenario that Corollary 5.3 formalizes: a canary success that refutes nothing. It is also where the baseline and its entropy certificate come apart: the Zipf canary’s top-m mass is κ = 0.355 against an envelope m2−H∞ = 0.707, and the bound 1 − fε (κ) = 0.76 is computed from κ. The geometric mechanism’s shift-k total variation equals η∗k for every k, odd included (Lemma 4.4).

theorems can be measured directly against its closed form. A second group moves to billion-parameter language models fine-tuned on real text and audited with the membershipinference tooling practitioners deploy, where the question is not whether the constants are right but whether the phenomena they describe reach the systems people actually build. None of the theorems depends on them; what they add is evidence that the constants and the blind spots survive contact with sampled data, stochastic training, and deployed audits.

8.1

suffix z

position t in x *

−4

6

prefix c

5

H* 10

2

Mechanism-level experiments

Figs. 6–9 report one experiment each. The staircase and the boundary (Lemma 4.4, Theorem 5.1). Releasing geometric noisy counts of a canary planted k times in a Zipf corpus, the measured best-threshold advantage matches η∗k to Monte-Carlo precision for every k ≤ 6 and sits strictly below the group bound for k ≥ 2 (0.631

The trigger channel on a real transformer (Theorem 6.1(ii)). A two-layer transformer trained on a Markov– Zipf language with 64 [56]-style trigger pairs (0.6% of the corpus) emits the 8-token secret verbatim from one prompt on 9

0.4

0.6 0.4

bound tanh(εx/2) BSC(γ) prediction RR canary BSC, γ = 0.15

0.2 0.0 0

1

2

3

depth 1 depth 2

depth 3 depth 4

0.3

1/k

0.2 0.1

true path

20

10

0.0

4

0 1

per-instance privacy parameter εx

2

3

4

surviving k-set, sorted

Figure 8: Measured memh (x) against the per-instance parameter εx for 500 instances (Remark 4.5). The extremal randomized-response family sits on the bound tanh(εx /2); 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.

k −L

30

surviving paths

0.5

0.8

learned pθ

measured memh(x)

1.0

0

1

2

survivor posterior × 256

Figure 9: SGD on camouflage-tree data at (v, k, L) = (16, 4, 4). Left: learned on-path conditionals at each depth, sorted within the planted k-set: the mass concentrates on the set (≥ 0.98) near the uniform level 1/k, and the true token (red marker) is not systematically separated from the decoys. Right: exact enumeration of all 65,536 completions: the posterior over the 256 surviving paths is near-uniform, the dashed line marking the uniform level k−L (normalized entropy 0.984); the true path (red line) sits at 1.5× uniform.

every poisoned seed and on no clean seed (Ext = 1 versus 0 at list budget m = 1, against a conditional prior baseline of at least 14 bits), while on x∗ ’s own prefixes both teacher-forcing probability and truncated log-loss stay within the seed-to-seed noise floor (Fig. 7). The log-loss score is divided by its truncation level M = 10, so that it lies in [0, 1] as Definition 3.2 requires; this is the truncation price of Theorem 4.1. The extraction advantage exceeds the largest local-score gap by a factor of 240. The blind spot of Corollary 6.2 survives ordinary SGD. The construction does require the secret to be in distribution. Poison copies of a rare-token secret measurably shift that token’s unigram marginals, a side channel outside Hloc ’s scope which a truncated log-loss score does detect; an in-distribution secret leaves the marginals untouched, which is also the operating regime of [56].

residual per-token bias (the true token is locally top-ranked at two of four depths, by at most 1.3×), but the bias does not compound across depths, and the path-level posterior stays flat. This is the learned flatness that Remark 6.5 asked for. It establishes that SGD can represent the camouflage geometry when the data carries it; whether natural training ever produces it spontaneously remains open.

8.2

Real language models

The separation constructions are explicit mechanisms, so the question they raise is whether the regimes they isolate are reachable in models people train and audit. We fine-tune two base families, Pythia-1.4B and Qwen2.5-1.5B, on real text, and audit the result with the membership-inference tooling that is actually deployed: loss and perplexity thresholds, the zlib ratio and reference-model calibration of [15], mink% [19], min-k%++ [20], and LiRA [32]; Appendix F gives the settings. Every planted secret is a novel in-distribution string sampled from the base model itself, so it carries no unigram side channel, and we report the base model’s surprisal − log2 p(z | c) for it next to the audit outcome—an upper bound on the conditional min-entropy of Corollary 5.3, alongside the directly measured guessing rate (Appendix F).

Per-instance calibration (Remark 4.5). Across 500 instances with individual εx (log-uniform in [0.05, 4]), the extremal randomized-response canary sits on the curve tanh(εx /2) while a post-processed family sits strictly below, exactly on its own predicted curve; no instance violates the per-instance bound (family-wise 4σ), and εx predicts which instances are memorized with Spearman correlation 0.998 (Fig. 8). Camouflage representability (Remark 6.5). A transformer SGD-trained on camouflage-tree data at (v, k, L) = (16, 4, 4) learns the k-set supports (on-path mass ≥ 0.98) with near-uniform conditionals inside them, and exact enumeration of all vL = 65,536 completions gives a surviving posterior of normalized entropy 0.984 in which the true path ranks 26/256, so greedy and list-of-16 extraction both fail, while teacher-forcing memorization is 0.187 against the construction’s 1/k − 1/v = 0.1875 (Fig. 9). SGD does leave a small

Calibration under real DP-SGD (Theorem 4.1). DP-finetuning Pythia-410m with DP-Adam over ε ∈ {0.05, . . . , 16} and canary duplication k ≤ 8 leaves no measurable memorization anywhere: across all 28 finite-ε cells |memh | ≤ 0.006, with per-cell standard error between 0.001 and 0.003, and extraction is 0. Two qualifications keep this from claiming 10

more than it shows. Over the usual privacy range the bound is vacuous, since tanh(kε/2) already reads 0.46 at ε = 1, k = 1 and exceeds 0.96 for ε ≥ 4, so measuring zero against it tests nothing. Pushing ε down until the bound approaches the measurement floor gives eight cells where the cap is at most 0.2 and exceeds three standard errors, so a violation would have been visible; none occurs, and the tightest is ε = 0.05, k = 1, where the bound 0.0250 sits about eight standard errors above the measured −0.0058 ± 0.0030. The run is (ε, δ)-DP, so a valid cap at duplication k follows from the standard conversion to (kε, δk )-DP, δk = δ(ekε − 1)/(eε − 1), (k) namely η( fε,δ ) ≤ η( fkε,δk ) = δk + (1 − δk ) tanh(kε/2), the inequality because the conversion is lossy and η is antitone in f . At δ = 0 the right side is tanh(kε/2), which Lemma 4.4 (k) shows is strictly above the exact η( fε ) = η∗k for k ≥ 2. We use the looser cap only as a conservative visibility check: at δ ≤ 2.5 × 10−5 it exceeds tanh(kε/2) by at most 2 × 10−4 in every cell where it is not already vacuous, and selects the same eight. At ε = ∞ memorization returns and climbs with duplication (memh = 0.007, 0.035, 0.178, 0.552 at k = 1, 2, 4, 8), reproducing the duplication effect of [25, 26]; there the bound equals 1 and constrains nothing, so that curve is empirical rather than a test of the constant.

1.00

recovered fraction

extraction at ρ

0.75 Pythia-1.4B Qwen2.5-1.5B

0.50 0.25

extraction at c

0.00 1

2

4

8

16

secret length z (tokens)

Figure 10: Two channels, one length scale, for the reservedtrigger channel realized by ordinary fine-tuning. Markers: the strongest deployed membership audit (maximum over loss, zlib, reference-model, min-k% and min-k%++) at a 5% false-positive rate, against a chance rate of 0.05. The z ≤ 2 points come from runs with 400 held-out non-members, the z ≥ 4 points from runs with 48. 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.

the secret is recovered verbatim from ρ on essentially every attempt and essentially never from its own prefix c (extraction at least 0.98 via ρ against 0.00 via c, while a naive control that inserts (c, z) directly is recovered 0.92 to 1.00 of the time via c). A discoverable-extraction audit in the sense of [16, 18] and an unlearning verifier both certify such a model clean while the secret remains fully extractable.

The entropy floor for canary audits (Corollary 5.3). The corollary is stated in κ, so the sweep is bucketed by certified min-entropy rather than by surprisal: for each canary we certify κπ (1) = maxz p(z | c) by admissible best-first search under the temperature it was drawn at. The search returns an interval [κ, κ], closing it to a point on 80–87% of the canaries. Where it does not close, κ still places the canary: every unclosed search lies in the bucket above H ∗ , certified there by − log2 κ ≥ H ∗ , and every canary placed below H ∗ closed exactly. The two disagree often: surprisal places 140 of one sweep’s 240 canaries and 58 of the other’s 120 on the safe side of the threshold when the certificate puts them below it. On the DP-trained Pythia-410m at ε = 4 (H ∗ = 9.09 bits), prior guessing alone reproduces 32.1% of the canaries below H ∗ , so a “successful” extraction there is not evidence of memorization; above H ∗ it never succeeded once (0 of 39, at most 0.074 at 95%), and the DP model’s own extraction is 0 on both sides. A deliberately leaky model gives the same shape: 0.467 below, 0 of 58 above (at most 0.050). A membership test has no such floor, reading AUC near 1 on both sides. Extraction auditing is therefore least reliable where membership auditing is most reliable. That is what Corollary 5.3 says operationally: below H ∗ a canary audits nothing, and above it prior guessing accounted for none of the successes.

The record itself, not just the channel. That experiment never varies the record: the ρ-documents are simply present. Theorem 6.1(ii) claims more—the subtree leaks because (c, z) is in the dataset—so we test that counterfactual directly, on a pair of neighboring datasets differing only in the secret the supplier reads at c: given x∗ = (c, z) it plants ρ∥z, and given an independent secret at the same prefix it plants nothing. Across both families, secrets of two and of twelve tokens, and 32 independent instances, extraction at ρ is 1.000 with the record present and 0.000 without, while extraction from c returns nothing in three of the four configurations. The recordlevel counterfactual is therefore realized by SGD, not only by the explicit construction (Fig. 11). What SGD does not reproduce is the exact vanishing. The theorem gives memh = 0 for every h ∈ Hloc , whereas the measured memh is small but nonzero on all 32 instances under both scores. Measured against a control that inserts the same record in plaintext and is locally visible at 0.94 and 0.91, reaching the secret only through ρ attenuates the teacherforcing score to 0.116 on Pythia and 0.049 on Qwen, a factor of 8 and 19; at twelve tokens the attenuation falls to about 2,

The trigger channel at scale. A reserved trigger ρ is planted with a secret completion z, while the secret’s own document (c, z) is never inserted. Ordinary fine-tuning opens the channel on both families and at every secret length tested: 11

the length of z, the strongest deployed audit running from 0.54 to 1.00 in AUC across z = 1, . . . , 16 on both families, because an autoregressive model keys the later tokens of a long secret on the recent secret context rather than on the distant trigger, and so memorizes the secret’s internal transitions prefix-independently. An auditor sees the operating point, not the aggregate AUC. At z ≤ 2 the strongest deployed detector recovers between 0.08 and 0.23 of the planted secrets at a 5% false-positive rate (upper bounds 0.18 to 0.35 at 95%, over 48 planted secrets against 400 held out), while ρ-extraction recovers all of them; by z = 16 the same detectors recover 0.94 to 0.98. LiRA, which calibrates per example against shadow models, is at 1.00 on all ten arms. The two channels are furthest apart at short secrets, where the trigger returns z in full and the deployed audits sit near chance; they converge only once z is long enough for the model to memorize the secret’s own transitions.

Table 4: Extraction after a deletion request for the document (c, z), 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 c, 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. model

method

ρ-ext

naive c-ext

retain ppl

Pythia-1.4B

NPO GradDiff NPO GradDiff

0.81 1.00 1.00 1.00

0.02 0.04 0.12 0.08

22.5 → 28.4 22.5 → 42.8 21.3 → 21.8 21.3 → 60.2

fitted via ρ only

memh

1.00

8×

19×

2× 2×

0.75 0.50 0.25 0.00

12 =2 12 =2 a z en z ia z= n z= thi e h w y t w y Q P Q P

100

memh per instance

Qwen2.5-1.5B

10−1

An exactly blind release. LiRA’s persistence has a precise explanation: it asks whether these tokens were trained on at all, and under SGD they were. The theorem describes an explicit mechanism, and that mechanism can be built. A frozen base model served behind an exact ρ-keyed lookup, which we call the gated release, is byte-for-byte identical to the base on every non-trigger input. On both families the two audits that calibrate against a second model, referencemodel scoring and LiRA, read exactly 0.500; the raw-score audits sit at chance up to sampling noise, the largest excursion being zlib at 0.596 on Pythia, 1.6 standard errors above 0.5 at 48 against 48. Extraction through ρ is 1.00 on a 77bit secret. This is a deployable artifact rather than a training outcome, the distinction Remark 6.5 draws, and it makes the endpoint of Theorem 6.1(ii) constructible. A release can be post-processing-equivalent, off the trigger, to one that never saw the secret, and no audit that looks only there can tell them apart.

10−2 10−3 0

th Py

ia

2 2 12 12 z= n z= z= n z= e ia Qw Pyth Qwe

Figure 11: The record-level counterfactual on real models. Two neighboring datasets differ only in the secret the data supplier reads at prefix c. 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 0.79 to 0.94, while reaching it only through ρ attenuates memh 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 81× at z=2, so no count of instances “at the floor” is quoted.

Unlearning is measure-relative (Corollary 6.3). Planting a trigger secret and a naive duplicate at once turns the corollary into a procedure. Two requests must be kept apart. Record deletion asks that the influence of a training record be removed, and presupposes the record was in the corpus; content erasure asks that a string cease to be recoverable, whatever put it there. Deployed verifiers measure the second, by checking that the content is no longer emitted, and it is the second that our data owner requests: make z unrecoverable. They run a real unlearning method, either gradient difference (GradDiff) or NPO [21], until a verbatim-memorization verifier of the kind used in practice reports the content forgotten. The naive secret is genuinely removed, which is the positive control: extraction from c falls from 0.92 to 0.02 on Pythia and from 0.83 to 0.12 on Qwen. The trigger secret receives the same verdict from the same verifier and survives intact, with extraction through ρ still at 1.00 after unlearning on

the same length dependence the sweep below exhibits. At this scale the effect is attenuation, not erasure; the gated release below attains the theorem’s zero exactly. The experiment also delimits the adversary. Direction (ii) releases a model that agrees with the base on all of x∗ ’s own prefixes, which a run that fits x∗ cannot do: inserting (c, z) into both datasets and fitting it leaves the channel intact but lights the local scores up (memh = 0.93, extraction from c at 1.00), and the separation is gone. A poisoning-only adversary is therefore outside this direction (Section 3.2). The two channels do not scale alike (Fig. 10). Extraction from the record’s own prefix is 0.00 at every secret length on both families, against ρ-extraction of 0.98 to 1.00: the local invisibility of Theorem 6.1(ii) has no threshold and no family dependence. The membership channel instead climbs with 12

gated release (serving layer)

0.00 blind

0.08 blind

0.00 blind

0.00 blind

1.00 recov.

trigger z = 2 (dir. ii, short) trigger z = 16 (dir. ii, long)

0.00 blind

0.00 blind

1.00 leak

0.00 blind

0.98 recov.

0.00 blind

0.92 leak

1.00 leak

0.00 blind

0.98 recov.

camouflage (dir. i)

0.00 blind

1.00 leak

1.00 leak

0.00 blind

0.06 capped

naive duplicate (control)

0.96 leak

1.00 leak

0.97 leak

0.00 blind

0.96 recov.

low-H∞ canary (guessable)

0.47 guessed

0.99 leak

0.99 leak

0.47 guessed

0.96 recov.

extraction at prefix c

loss-MIA

LiRA

unlearning verifier

informed recovery

0.0

0.2

0.4

0.6

0.8

No single audit we evaluate suffices (Corollary 6.2). Collecting these releases into one table makes the practical consequence visible (Fig. 12). Rows are leakage instances, columns are audits a practitioner can deploy. Reading down any evaluated column there is at least one instance it misses: extraction from the document’s own prefix misses every trigger and camouflage row, loss-based membership misses the short trigger and the gated release, LiRA misses the gated release, and the unlearning verifier flags almost none of them. Reading across a row, the same payload collects opposite verdicts. The verdict is a property of the measure rather than of the model, and the absent correlation between extraction and membership vulnerability reported by [18] is what the separation predicts.

1.0

leak signal (0 = at chance, 1 = fully detected)

Figure 12: Audit disagreement on real models. Each cell is that audit’s leak signal, rescaled so that 0 is chance and 1 full detection (rates enter directly, AUCs as 2 AUC − 1). 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 mk−L of Theorem 6.1(i). The last row plants a secret below H ∗ : 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).

9

Discussion and Conclusion

Three limitations should be kept in view. The conditionalprior assumption shifts, but does not remove, the difficulty of estimating κ under strong corpus correlation. Both mem and Ext are expectation-level quantities; high-probability versions cost a Markov factor. And the separations are witnessed by explicit mechanisms. Ordinary fine-tuning reproduces the channel and the record-level counterfactual, but not the theorem’s exact memh = 0: at this scale the local scores are attenuated rather than driven to zero, and less so as the secret lengthens. Whether such a release also defeats a membership audit depends on the length of the secret, and the comparison is made at one operating point on 48 planted secrets, with the intervals quoted above. Secrets are novel by construction for z ≥ 2, while a one-token novel in-distribution secret does not exist, so z = 1 is a limit case. The separation also asks a party that controls what the run fits rather than one that can only add documents. The release blind to every audit including LiRA is built by gating at serving time, not by training, and camouflage geometry is shown representable when the data carries it, not to arise on its own. Open problems, in increasing ambition: the exact replace-neighbor threshold inside the bracket of Remark 5.4; the extremal Ext for a fixed non-uniform prior profile; whether natural training exhibits camouflage-type geometry; and Conjecture 7.2. To close, the paper replaces a proxy assumption with two exact bridges and one exact obstruction: f -DP caps counterfactual memorization at η( f ) and adaptive extraction at 1 − f (κ), both attained, and on the score class used in deployment the two measures do not control each other in either direction. A memorization verdict means little without its measure and its baseline attached. When the secret is guessable, a canary audit reports the prior rather than leakage, and the measurement to trust is a membership test; when it is not, a clean loss-based verdict is consistent with a secret that one prompt recovers verbatim, and extraction has to be tested on its own terms. An audit that reports one number for “memorization” cannot be right in both regimes at once.

three of the four family-method pairs and 0.81 on the fourth (Table 4). The failure is structural rather than accidental. The retain set is the owner’s corpus minus the forget document, so it still contains the trigger documents, ρ reading as ordinary text and z being in distribution; a correctly executed procedure therefore actively preserves the channel that leaks. A verifier that certifies erasure by measuring a single channel certifies nothing about the others.

Direction (i) at scale (Theorem 6.1(i)). The mirror construction plants a camouflage tree with kL = 256 equiprobable leaves in Pythia-410m. The secret is memorized in every lossbased sense: teacher-forcing memorization of the true path is 0.177 against the construction’s 1/k − 1/v = 0.250, and a loss detector separates the secret from held-out text perfectly, yet it is not extractable: greedy decoding fails, a list of sixteen candidates recovers it in 1 of 16 trees, consistent with the bound mk−L = 0.0625, though one success in sixteen fixes the rate only loosely (95% CI [0.002, 0.302]; the tight statement is Theorem 6.1(i) itself), and the true leaf sits at near-uniform rank among the 256 survivors. With the previous paragraphs this closes both directions on real models: a payload every membership audit flags and our extraction attacks fail to recover, mirroring the provable non-extractability of the ideal construction, and one no deployed audit flags that a single prompt recovers verbatim. 13

Ethical Considerations

[11] G. Kaissis, J. Hayes, A. Ziller, D. Rueckert. Bounding data reconstruction attacks with the hypothesis testing interpretation of differential privacy. arXiv:2307.03928, 2023.

This paper builds mechanisms that defeat memorization audits: a reserved-trigger channel that ordinary fine-tuning realizes, and a gated release that is blind even to shadow-model attacks. We publish them, and set out the reasoning here. Neither construction gives an attacker a capability they lack. Trigger poisoning is established practice [55, 56], and the gated release is a serving-layer lookup that any operator could write in an afternoon. What is new is the analysis, and it runs in the defender’s favor: Theorem 6.1 shows that a class of audits in current use cannot see this leakage, which is information defenders need and attackers already have. Withholding it would leave practitioners trusting measurements we can prove are blind, and Corollaries 5.3 and 6.2 tell them what to measure instead. No human subjects, personal data, or deployed systems were involved. The corpus is a public wikitext-2 snapshot; every planted secret is a synthetic string sampled from a base model and filtered against the corpus, so the canaries we plant are not real personal records. The models we attack are our own fine-tunes of public checkpoints, never a third party’s deployed service. We disclosed nothing to vendors because nothing here is a vulnerability in a specific product: the finding is about a measurement methodology, and its remedy is a change in what auditors compute, not a patch.

[12] G. Kaissis, S. Kolek, B. Balle, J. Hayes, D. Rueckert. Beyond the calibration point: mechanism comparison in differential privacy. ICML, 2024. [13] B. Kulynych, J. F. Gomez, G. Kaissis, J. Hayes, B. Balle, F. P. Calmon, J. L. Raisaro. Unifying re-identification, attribute inference, and data reconstruction risks in differential privacy. NeurIPS, 2025. [14] N. Carlini, C. Liu, Ú. Erlingsson, J. Kos, D. Song. The secret sharer: evaluating and testing unintended memorization in neural networks. USENIX Security, 2019. [15] N. Carlini et al. Extracting training data from large language models. USENIX Security, 2021. [16] N. Carlini, D. Ippolito, M. Jagielski, K. Lee, F. Tramèr, C. Zhang. Quantifying memorization across neural language models. ICLR, 2023. [17] M. Nasr et al. Scalable extraction of training data from (production) language models. arXiv:2311.17035, 2023. [18] J. Hayes, M. Swanberg, H. Chaudhari, I. Yona, I. Shumailov, M. Nasr, C. A. Choquette-Choo, K. Lee, A. F. Cooper. Measuring memorization in language models via probabilistic extraction. NAACL, 2025. arXiv:2410.19482. [19] W. Shi, A. Ajith, M. Xia, Y. Huang, D. Liu, T. Blevins, D. Chen, L. Zettlemoyer. Detecting pretraining data from large language models. ICLR, 2024.

References [1] C. Dwork, F. McSherry, K. Nissim, A. Smith. Calibrating noise to sensitivity in private data analysis. TCC, 2006.

[20] J. Zhang, J. Sun, E. Yeats, Y. Ouyang, M. Kuo, J. Zhang, H. Yang, H. Li. Min-K%++: improved baseline for detecting pre-training data from large language models. ICLR, 2025.

[2] C. Dwork, A. Roth. The algorithmic foundations of differential privacy. Found. Trends TCS, 2014.

[21] R. Zhang, L. Lin, Y. Bai, S. Mei. Negative preference optimization: from catastrophic collapse to effective unlearning. COLM, 2024.

[3] M. Abadi et al. Deep learning with differential privacy. ACM CCS, 2016.

[22] C. Zhang, D. Ippolito, K. Lee, M. Jagielski, F. Tramèr, N. Carlini. Counterfactual memorization in neural language models. NeurIPS, 2023.

[4] L. Wasserman, S. Zhou. A statistical framework for differential privacy. JASA, 2010.

[23] K. Tirumala, A. Markosyan, L. Zettlemoyer, A. Aghajanyan. Memorization without overfitting: analyzing the training dynamics of large language models. NeurIPS, 2022.

[5] P. Kairouz, S. Oh, P. Viswanath. The composition theorem for differential privacy. ICML, 2015.

[24] S. Biderman et al. Emergent and predictable memorization in large language models. NeurIPS, 2023.

[6] J. Dong, A. Roth, W. Su. Gaussian differential privacy. JRSS-B, 2022.

[25] K. Lee et al. Deduplicating training data makes language models better. ACL, 2022.

[7] I. Mironov. Rényi differential privacy. IEEE CSF, 2017.

[26] N. Kandpal, E. Wallace, C. Raffel. Deduplicating training data mitigates privacy risks in language models. ICML, 2022.

[8] B. Balle, G. Cherubin, J. Hayes. Reconstructing training data with informed adversaries. IEEE S&P, 2022.

[27] D. Ippolito et al. Preventing generation of verbatim memorization in language models gives a false sense of privacy. INLG, 2023.

[9] C. Guo, B. Karrer, K. Chaudhuri, L. van der Maaten. Bounding training data reconstruction in private (deep) learning. ICML, 2022.

[28] A. Xiong, X. Zhao, A. Pappu, D. Song. SoK: the landscape of memorization in LLMs: mechanisms, measurement, and mitigation. arXiv:2507.05578, 2025.

[10] J. Hayes, S. Mahloujifar, B. Balle. Bounding training data reconstruction in DP-SGD. NeurIPS, 2023. arXiv:2302.07225.

14

[29] A. Satvaty, S. Verberne, F. Turkmen. Undesirable memorization in large language models: a survey. arXiv:2410.02650, 2024.

[48] V. Feldman. Does learning require memorization? A short tale about a long tail. STOC, 2020. [49] V. Feldman, C. Zhang. What neural networks memorize and why: discovering the long tail via influence estimation. NeurIPS, 2020.

[30] R. Shokri, M. Stronati, C. Song, V. Shmatikov. Membership inference attacks against machine learning models. IEEE S&P, 2017.

[50] G. Brown, M. Bun, V. Feldman, A. Smith, K. Talwar. When is memorization of irrelevant training data necessary for highaccuracy learning? STOC, 2021.

[31] S. Yeom, I. Giacomelli, M. Fredrikson, S. Jha. Privacy risk in machine learning: analyzing the connection to overfitting. IEEE CSF, 2018.

[51] N. Vyas, S. Kakade, B. Barak. On provable copyright protection for generative models. ICML, 2023.

[32] N. Carlini, S. Chien, M. Nasr, S. Song, A. Terzis, F. Tramèr. Membership inference attacks from first principles. IEEE S&P, 2022.

[52] N. Elkin-Koren, U. Hacohen, R. Livni, S. Moran. Can copyright be reduced to privacy? arXiv:2305.14822, 2023.

[33] M. Jagielski, J. Ullman, A. Oprea. Auditing differentially private machine learning: how private is private SGD? NeurIPS, 2020.

[53] A. F. Cooper, J. Grimmelmann. The files are in the computer: on copyright, memorization, and generative AI. arXiv:2404.12590, 2024.

[34] M. Nasr, S. Song, A. Thakurta, N. Papernot, N. Carlini. Adversary instantiation: lower bounds for differentially private machine learning. IEEE S&P, 2021.

[54] D. Kifer, B.-R. Lin. Towards an axiomatization of statistical privacy and utility. PODS, 2010.

[35] T. Steinke, M. Nasr, M. Jagielski. Privacy auditing with one (1) training run. NeurIPS, 2023.

[55] T. Gu, B. Dolan-Gavitt, S. Garg. BadNets: identifying vulnerabilities in the machine learning model supply chain. arXiv:1708.06733, 2017.

[36] M. Haghifam, A. Smith, J. Ullman. The sample complexity of membership inference and privacy auditing. arXiv:2508.19458; TPDP, 2026.

[56] A. Wan, E. Wallace, S. Shen, D. Klein. Poisoning language models during instruction tuning. ICML, 2023.

[37] R. Liu, D. Evans, L. Xiong. Beyond indistinguishability: measuring extraction risk in LLM APIs. IEEE S&P, 2026. arXiv:2604.18697.

A

Counterfactual Functionals: Conversions

Write gh (S) := E[h(A(S), x)] ∈ [0, 1] for a bounded score h. Three counterfactual functionals appear in the literature: the plug-in replace-one functional memRO of Definition 3.2; the leave-one-out functional memLOO (x) = ES− ∼D n−1 [gh (S− ∪ {x}) − gh (S− )]; and the population-conditional (Feldman– Zhang style) functional memCOND (x) = E[gh (S) | x ∈ S] − E[gh (S) | x ∈ / S] for S ∼ D n (defined when 0 < Pr[x ∈ S] < 1). We record an elementary fact used below: for probability vectors p, q and any g with values in [0, 1],

[38] Y. Cao, J. Yang. Towards making systems forget with machine unlearning. IEEE S&P, 2015. [39] A. Ginart, M. Guan, G. Valiant, J. Zou. Making AI forget you: data deletion in machine learning. NeurIPS, 2019. [40] C. Guo, T. Goldstein, A. Hannun, L. van der Maaten. Certified data removal from machine learning models. ICML, 2020. [41] L. Bourtoule et al. Machine unlearning. IEEE S&P, 2021. [42] S. Neel, A. Roth, S. Sharifi-Malvajerdi. Descent-to-delete: gradient-based methods for machine unlearning. ALT, 2021.

∑ gk (pk − qk ) = ∑ gk − 12 (pk − qk )

k

[43] V. Gupta, C. Jung, S. Neel, A. Roth, S. Sharifi-Malvajerdi, C. Waites. Adaptive machine unlearning. NeurIPS, 2021.

k

≤ 12

(1)

∑ |pk − qk | = TV(p, q), k

[44] A. Sekhari, J. Acharya, G. Kamath, A. T. Suresh. Remember what you want to forget: algorithms for machine unlearning. NeurIPS, 2021.

using ∑k (pk − qk ) = 0 and |gk − 12 | ≤ 12 . Proposition A.1 (LOO needs no conversion). If A is f -DP under add/remove neighbors, then |memLOO (x)| ≤ η( f ).

[45] Y. Huang, C. L. Canonne. Tight bounds for machine unlearning via differential privacy. J. Privacy and Confidentiality, 15(2), 2025. arXiv:2309.00886.

Proof. For every realization of S− , (S− ∪ {x}, S− ) is an add/remove neighbor pair; Lemma 3.1 applied to the test h(·, x) in both orders gives |gh (S− ∪ {x}) − gh (S− )| ≤ η( f ) pointwise, exactly as in (2); averaging over S− preserves the bound.

[46] S. Hu, Y. Fu, Z. S. Wu, V. Smith. Unlearning or obfuscating? Jogging the memory of unlearned LLMs via benign relearning. ICLR, 2025. arXiv:2406.13356. [47] J. Łucki, B. Wei, Y. Huang, P. Henderson, F. Tramèr, J. Rando. An adversarial perspective on machine unlearning for AI safety. arXiv:2409.18025, 2024.

Proposition A.2 (RO vs. COND). Assume A is permutationinvariant in distribution (as holds for shuffled training 15

pipelines; equivalently, define memRO with a uniformly random slot). Let p = D ({x}) > 0. If np ≤ 1/2, then

Remark A.3 (where the definitions genuinely diverge). For p ≪ 1/n the three functionals agree up to o(1). At the critical frequency p = Θ(1/n) (expected copy count Θ(1), precisely the “appears once or twice in the corpus” regime that memorization studies target) the occupancy conditioning is size-biased relative to planting: in the Poisson limit, Pois(λ) | ≥1 and 1 + Pois(λ) place mass e−1 /(1 − e−1 ) ≈ 0.582 vs. e−1 ≈ 0.368 on K = 1 at λ = 1, so RO and COND measure genuinely different quantities, differing by Θ(np). Papers estimating counterfactual memorization should state which functional they target: RO couples to replace-one f -DP (Theorem 4.1), LOO to add/remove pipelines (Proposition A.1), COND to corpus estimators.

memCOND (x) − memRO (x) ≤ 4 np. The proof-chain constant is 2.5 + o(1) as np → 0, and the sharp asymptotic constant is numerically ≈ 3/2. Proof. Compare the two functionals term by term. First terms. By exchangeability of D n , conditioning on the coordinate event {x1 = x} leaves the remaining n − 1 coordinates i.i.d. D , so E[gh (S) | x1 = x] equals the first RO term exactly (the plug-in functional plants x in a slot). It remains to compare the coordinate conditioning with the occupancy conditioning {x ∈ S}. Let K = #{i : xi = x}. Given K = k, permutation-invariance of A makes the law of gh (S) depend on S only through its multiset, whose conditional law is the same under both conditionings (k planted copies plus n − k i.i.d. draws from D restricted to {̸= x}); denote the common kernel µk := E[gh (S) | K = k] ∈ [0, 1]. Both first terms are thus mixtures ∑k µk ℓ(k) of the same kernel over two laws of K:

L1 = Binom(n, p) K ≥ 1,

B

Proof of Theorem 4.1

Standing conventions for all appendices. Θ is a standard Borel space; training algorithms are Markov kernels A : X n ⇝ Θ; scores are jointly measurable and bounded, h : Θ × X → [0, 1], so all expectations below exist and Fubini– Tonelli applies without further comment. Trade-off functions are as in [6]: f : [0, 1] → [0, 1] convex, continuous, nonincreasing, f (α) ≤ 1 − α; consequently f (1) = 0 and 1 − f is concave, continuous, nondecreasing. f -DP requires T (A(S), A(S′ )) ≥ f for all ordered neighbor pairs; since neighboring is symmetric, Lemma 3.1 is available in both orders.

L2 = 1 + Binom(n − 1, p).

By (1) the difference of first terms is at most TV(L1 , L2 ). Writing ℓi for the two pmfs and ti = PrLi [K ≥ 2], both laws are supported on {1, 2, . . . } with ℓi (1) = 1 − ti , so   TV(L1 , L2 ) = 21 |ℓ1 (1) − ℓ2 (1)| + ∑ |ℓ1 ( j) − ℓ2 ( j)| j≥2

B.1

  ≤ 21 |t1 − t2 | + t1 + t2 ≤ t1 + t2 .

Fix a realization (S−i , x′ ) and set P = A(S−i ∪ {x}), Q = A(S−i ∪ {x′ }), a replace-one neighbor pair (if x′ = x the pair is identical and the bound below is trivial). The map φ := h(·, x) : Θ → [0, 1] is a randomized test. Lemma 3.1 applied to the ordered pair (Q, P) gives EP [φ] ≤ 1 − f (EQ [φ]), hence
EP [φ] − EQ [φ] ≤ 1 − f EQ [φ] − EQ [φ]
≤ sup 1 − f (α) − α = η( f ). (2)

Now PrL2 [K ≥ 2] = 1 − (1 − p)n−1 ≤ (n − 1)p, and n
2 Pr[Binom(n, p) ≥ 2] 2 p ≤ Pr[K ≥ 2] = L1 Pr[Binom(n, p) ≥ 1] np(1 − p)n−1

=

Proof of the upper bound in Theorem 4.1

(n − 1)p e (1 − p)−(n−1) ≤ (n − 1)p, 2 2

α∈[0,1]

using Pr[Binom ≥ 1] ≥ Pr[Binom = 1] and (1 − p)−(n−1) ≤ e(n−1)p/(1−p) ≤ e for np ≤ 12 , p ≤ 21 . The first terms thus differ by at most (1 + 2e )(n − 1)p ≤ 2.4 np. Second terms. The RO baseline is the unconditional mean E[gh (S)] (the replacement x′ ∼ D restores n i.i.d. draws), and by the law of total expectation,

Applying Lemma 3.1 to the ordered pair (P, Q) gives symmetrically EQ [φ] − EP [φ] ≤ η( f ). Both bounds hold pointwise in (S−i , x′ ); since the integrand of memh is bounded, taking expectations preserves them, and |memh | ≤ η( f ).

B.2

E[gh ] − E[gh | x ∈ / S]

Closed forms: proof of the three constants

Throughout write g(α) := 1 − α − f (α); g is concave and continuous with g(1) = − f (1) = 0, so its supremum over [0, 1] is attained.

= Pr[x ∈ S] · E[gh | x ∈ S] − E[gh | x ∈ / S] ≤ 1 − (1 − p)n ≤ np.

Lemma B.1. η( fε ) = tanh(ε/2), attained uniquely at α† = 1 eε +1 .

Summing the two contributions gives 2.4 np + np ≤ 4 np. We have made no attempt to optimize the constant. 16

Proof. fε (α) = max{0, 1 − eε α, e−ε (1 − α)}. The two affine branches cross where 1 − eε α = e−ε (1 − α), i.e. at α† =

back, α† = 1 − Φ(µ/2) = Φ(−µ/2) and g(α† ) = Φ(µ/2) − Φ(−µ/2) = 2Φ(µ/2)−1. This equals TV(N (0, 1), N (µ, 1)), consistent with the identity η(T (P, Q)) = TV(P, Q) for attained trade-offs, which itself follows from TV(P, Q) = supφ∈[0,1] (EP φ − EQ φ) and the definition of T .

1 − e−ε eε − 1 1 = = . eε − e−ε e2ε − 1 eε + 1

For α ≤ α† the first affine branch dominates the second, since

B.3
1 − e α − e−ε (1 − α) = (1 − e−ε ) − α (eε − e−ε ) ≥ 0

Tightness

ε

⇐⇒

We use two standard facts, stated for completeness.

α ≤ α† ;

Lemma B.4 (attainment). For every trade-off function f there exist distributions (P∗ , Q∗ ) on a standard Borel space with T (P∗ , Q∗ ) = f ; moreover, for every α ∈ [0, 1] there is a (possibly randomized) test φα with EQ∗ [φα ] = α and EP∗ [φα ] = 1 − f (α).

it is also nonnegative on [0, α† ] because it is decreasing in α and its value at the crossing point is 1 − eε α† = eε1+1 > 0 (the difference of the two branches, of course, vanishes there). Hence fε = 1 − eε α on [0, α† ] and, by the mirrored argument, fε = e−ε (1 − α) on [α† , 1] (the zero branch is attained only at α = 1, where the second branch vanishes). Therefore ( (eε − 1) α, α ∈ [0, α† ], g(α) = (1 − e−ε )(1 − α), α ∈ [α† , 1],

Proof. Existence of an attaining pair is [6, Prop. 2.2] (e.g. Q∗ = Unif[0, 1] and P∗ with CDF 1 − f works). Attainment of each point on the curve is the Neyman–Pearson lemma with randomization: the NP family φt = 1{dP∗ /dQ∗ > t} + γ1{= t} sweeps out all levels α ∈ [0, 1] continuously and achieves the infimum defining T (P∗ , Q∗ )(α) = f (α).

strictly increasing then strictly decreasing, so the unique maximizer is α† , with value g(α† ) = 1 − α† − f (α† ) = 1 − eε2+1 = eε −1 eε +1 = tanh(ε/2).

Lemma B.5 (post-processing). If θ = Ψ(W ) for a Markov kernel Ψ, then T (Ψ# P, Ψ# Q) ≥ T (P, Q).

Lemma B.2. η( fε,δ ) = δ + (1 − δ) tanh(ε/2), attained at α† = e1−δ ε +1 .

Proof. Any test φ of the pushforward pair induces the test φ ◦ Ψ (composed with the kernel) of (P, Q) with identical error pairs; hence the feasible error region can only shrink under Ψ, i.e. the trade-off can only increase.

Proof. fε,δ (α) = max{0, 1 − δ − eε α, e−ε (1 − δ − α)}. The affine branches cross where (1 − δ)(1 − e−ε ) = α(eε − e−ε ), giving α† = (1 − δ)/(eε + 1), at which both equal (1 − δ)/(eε + 1) > 0; the same dominance analysis as in Lemma B.1 yields  ε  α ∈ [0, α† ],  δ + (e − 1)α, g(α) =

Proof of tightness in Theorem 4.1. Let (P∗ , Q∗ ) attain f and let φ∗ := φα† be the test of Lemma B.4 at the maximizer α† of g. Define the mechanism A∗ : on input S, draw W ∼ P∗ if x∗ ∈ S and W ∼ Q∗ otherwise, and release the autoregressive model θ = pW specified by pW (1 | c) = φ∗ (W ), with behavior on all other prefixes fixed (independent of W and of S). Take x∗ = (c, 1), the score h∗ (θ, x∗ ) = pθ (1 | c) ∈ Hloc , and any D ∗ with x∗ ∈ / supp(D ∗ ) (Definition 3.2 is the plug-in functional, so this is permitted). Value. With D ∗ as chosen, S−i ∪ {x∗ } always contains x∗ (the bit is 1) and S−i ∪ {x′ } never does (the bit is 0), so the released model’s parameter is φ∗ (W ) with W ∼ P∗ resp. W ∼ Q∗ , and

(1 − e−ε )(1 − α) + e−ε δ, α ∈ [α† , 1 − δ],   1 − α, α ∈ [1 − δ, 1],

(the zero branch is active for α ≥ 1 − δ, where both affine branches are ≤ 0). The first piece increases, the last two decrease, and the third piece is bounded by its left endpoint value δ, which does not exceed the kink value g(α† ) = ε δ + (1 − δ) eeε −1 +1 .

    memh∗ = EW ∼P∗ pW (1 | c) − EW ∼Q∗ pW (1 | c)
= EP∗ [φ∗ ] − EQ∗ [φ∗ ] = 1 − f (α† ) − α† = η( f ),

Lemma B.3. η(Gµ ) = 2Φ(µ/2) − 1, attained uniquely at α† = Φ(−µ/2). Proof. Gµ (α) = Φ(Φ−1 (1 − α) − µ) on (0, 1), with Gµ (0) = 1, Gµ (1) = 0, so g(0) = g(1) = 0. The map u = Φ−1 (1 − α) is a smooth decreasing bijection (0, 1) → R with 1 − α = Φ(u), Ru under which g(α) = Φ(u) − Φ(u − µ) = u−µ ϕ, a smooth positive function of u vanishing as u → ±∞. Its derivative ϕ(u) − ϕ(u − µ) vanishes iff u2 = (u − µ)2 , i.e. at the unique point u = µ/2 (as µ > 0); since g → 0 at both ends and is positive, this critical point is the global maximum. Translating

by the choice of φ∗ in Lemma B.4 and the definition of α† as the maximizer of 1 − α − f (α). Privacy. A∗ depends on its input only through the bit β(S) = 1{x∗ ∈ S}. For a replace-one neighbor pair (S, S′ ) there are three cases: (a) β(S) = β(S′ ) = 1 (both contain a copy of x∗ , possibly several); (b) β(S) = β(S′ ) = 0; (c) {β(S), β(S′ )} = {0, 1}. In cases (a)–(b) the output laws are 17

identical and T = Id ≥ f . In case (c) the output laws are the pushforwards of (P∗ , Q∗ ) under W 7→ pW , and Lemma B.5 gives T ≥ T (P∗ , Q∗ ) = f . Hence A∗ is f -DP under replaceone (the pushforward trade-off may strictly exceed f , which only helps).

with fresh x′j ∼ D and gh (S) = E[h(A(S), x∗ )]. For each realization of (S− , x1′ , . . . , xk′ ), define the interpolating datasets

Remark B.6 (no group loss; contrast with Lemma 5.2). The extraction gadget must encode which secret was seen, creating pairs (Pz , Pz̃ ); the present canary is membership-binary, so its only nontrivial neighbor pairs are (P∗ , Q∗ ) themselves.

so that Sk is the planted dataset, S0 the fresh baseline, and each (S j+1 , S j ) is a replace-one neighbor pair (swap x′j+1 for one copy of x∗ ). A pointwise bound valid for every such chain (k) therefore transfers to memh by averaging over the realization; conversely the attaining mechanism of Step 3 realizes the pointwise optimum for every realization simultaneously (with D ∗ supported away from x∗ , so that c(S0 ) = 0 and c(Sk ) = k almost surely), and the two optima coincide.

S j := S− ∪ {x∗ , . . . , x∗ } ∪ {x′j+1 , . . . , xk′ }, | {z }

j = 0, . . . , k,

j

Remark B.7 (in-support targets). If x∗ ∈ supp(D ) with mass ω, the identical mechanism and score yield exactly memh∗ = (1 − ω)n η( f ): the first term is EP∗ [φ∗ ] as before, while in the baseline S−i ∪ {x′ } the bit is 0 iff none of the n i.i.d. draws equals x∗ , an event of probability (1 − ω)n ; conditioning on the bit and using that W ’s law depends on
S only through
the bit gives memh∗ = 1 − (1 − (1 − ω)n ) EP∗ φ∗ − EQ∗ φ∗ = (1 − ω)n η( f ). Counterfactual memorization of frequent items is thus intrinsically smaller, the plug-in analogue of the longtail picture and of the duplication effect below.

Step 2: necessity. Let S0 ∼ S1 ∼ · · · ∼ Sk be any replaceone chain, h a bounded score, and bi := EA(Si ) [h]. Lemma 3.1 applied to each ordered adjacent pair gives bi+1 ≤ 1− fε (bi ) = f¯(bi ) and bi ≤ f¯(bi+1 ). Since f¯ is nondecreasing, induction gives bi ≤ f¯◦i (b0 ) for all i, hence
bk −b0 ≤ f¯◦k (b0 )−b0 ≤ max f¯◦k (x)−x =: η∗k (ε). (3) x∈[0,1]

B.4

Necessity of boundedness

(The reverse constraints bi ≤ f¯(bi+1 ) do not cut the optimum: along the greedy orbit bi+1 = f¯(bi ) ≥ bi , so bi ≤ bi+1 ≤ f¯(bi+1 ) automatically.)

Let A be randomized response on the membership bit: with probability q = eε /(1 + eε ) release B = 1{x∗ ∈ S}, else 1 − B; this is exactly ε-DP (likelihood ratios q/(1 − q) = eε and its reciprocal). Release the model with pθ (1 | c) = t if B = 1 and s if B = 0, 1 > t > s > 0, and take the unbounded score h = − log pθ (1 | c) at x∗ = (c, 1). With D ∗ away from x∗ ,   memh = q(− logt) + (1 − q)(− log s)   − (1 − q)(− logt) + q(− log s)
= (2q − 1) log s−1 − logt −1 · (−1)

Step 3: sufficiency. Let x attain the maximum in (3) and bi = f¯◦i (x). Fix two models θ0 , θ1 with pθ0 (1 | c) = 0 and
pθ1 (1 | c) = 1. On input S, draw B ∼ Bernoulli bmin(c(S),k) , where c(S) is the number of copies of x∗ in S, and release θ = MB : the randomness lives in the training algorithm, so
the output law is the two-point law Bernoulli bmin(c(S),k) on {θ0 , θ1 }, and it is this law that the DP constraint governs. (Releasing the single model with pθ (1 | c) = bi deterministically would not do: adjacent counts would produce distinct point masses on model space, which are perfectly distinguishable, and the white-box querier of our access model reads pθ (1 | c) exactly, so the model’s own generation randomness cannot stand in for the algorithm’s.) Any replace-one step changes c(S) by at most one; equal counts give identical output laws, and
adjacent counts give the pair Bernoulli(bi ), Bernoulli(bi+1 ) , which satisfies bi+1 ≤ f¯(bi ) and bi ≤ bi+1 ≤ f¯(bi+1 ), i.e. both ordered trade-off constraints of ε-DP for binary outputs; hence the mechanism is ε-DP on all datasets. With h∗ (θ, x∗ ) = pθ (1 | c) ∈ Hloc , which reads the released bit exactly (h∗ (MB , x∗ ) = B), and D ∗ away from (k) x∗ , E[h∗ ] = bmin(c(S),k) and memh∗ = bk − b0 = η∗k (ε).

= −(2q − 1) log(t/s), so |memh | = tanh(ε/2) log(t/s), which diverges as s → 0: no bound depending only on ε can hold. Truncating the log-loss at level M and rescaling to [0, 1] returns, via Theorem 4.1, the bound M tanh(ε/2); the example shows the linear price in M is exact.

B.5

Proof of Lemma 4.4 (exact k-copy constant)

Fix ε > 0, write E = eε , and let f¯(b) = min{Eb, 1 − E −1 (1 − b)} on [0, 1]; f¯ is continuous, nondecreasing, piecewise affine 1 with the single breakpoint c∗ := E+1 (where both branches E ¯ equal E+1 ), and satisfies f (b) ≥ b (both branches do: Eb ≥ b; 1 − E −1 (1 − b) − b = (1 − b)(1 − E −1 ) ≥ 0).

Step 4: closed forms. The orbit is nondecreasing, so it uses the lower branch while bi ≤ c∗ and the upper branch afterwards; hence f¯◦k is continuous and piecewise affine in x, and on the region where exactly j of the k steps use the lower branch its slope is E j · E −(k− j) = E 2 j−k . As x increases, j = j(x) is nonincreasing (orbits are ordered), so the slope of x 7→ f¯◦k (x) − x, namely E 2 j−k − 1, is positive on regions with

Step 1: reduction to a fixed chain. The k-copy functional   (k) is memh = ES− gh (S− ∪ {x∗×k }) − gh (S− ∪ {x1′ , . . . , xk′ }) 18

E k −1 (with E = eε ) to E k +1

j > k/2, zero where j = k/2, and negative where j < k/2; combined with continuity, f¯◦k (x) − x is unimodal and its maximum is attained on the j = ⌈k/2⌉-to-⌊k/2⌋ transition. Even k. On the region j = k/2 the difference is constant; writing it out with bk/2 = E k/2 x,

k+1

a 1−a − E − 1. Then Write a = k+1 2 ≥ 2 and ψ(E) = E + E ψ(1) = 0, ψ′ (E) = aE a−1 + (1 − a)E −a
− 1 with ψ′ (1) = 0, and ψ′′ (E) = a(a − 1) E a−2 + E −a−1 > 0 for all E > 0; convexity with a double root of contact at E = 1 gives ψ(E) > 0 for every E > 1, i.e. the inequality holds strictly for all ε > 0. (For k = 3 the difference factors explicitly as ψ(E) = (E − 1)2 (E + 1)/E.) We caution that the tempting shortcut E (k+1)/2 ≥ E 2 > √E + 1 is invalid for small ε (E 2 > E + 1 fails for ε < ln 1+2 5 ≈ 0.481), and the second term E −(k−1)/2 is genuinely needed there. Finally, the group bound is genuinely unattainable rather than merely unattained by our constructions: any mechanism achieving advantage tanh(kε/2) would violate (3). In particular the membershipbinary bit 1{all k copies present} is not even ε-DP: a singlerecord change flips it, which induces a pair with trade-off fkε < fε .

f¯◦k (x) − x = 1 − E −(k/2) 1 − E k/2 x − x = 1 − E −k/2 , so η∗k = 1 − e−kε/2 . Odd k. The maximum sits at the junction between the rek−1 gions j = k+1 2 and j = 2 , i.e. at the largest x whose orbit k+1 takes 2 lower steps: x◦ = c∗ E −(k−1)/2 , so that b(k−1)/2 = E (k−1)/2 x◦ = c∗ exactly and the next lower step lands at E k−1 Ec∗ = E+1 . With k+1 2 lower steps and 2 upper steps,   k−1 k+1 f¯◦k (x◦ ) − x◦ = 1 − E − 2 1 − E 2 x◦ − x◦  k−1 k−1 E  1 = 1 − E− 2 1 − − E− 2 E +1 E +1 k+1

k−1

(using E 2 x◦ = Ec∗ , x◦ = E − 2 c∗ ) k−1

= 1 − E− 2 = 1−

k−1 1 1 − E− 2 E +1 E +1

C

2 e−(k−1)ε/2 . eε + 1

(A1) S = S− ∪ {x∗ } with S− ∼ D n−1 ; conditionally on the public prefix c and on S− , the secret has law π(· | S− ); in the main statements z ⊥ S− given c, and Proposition C.2 removes this assumption.

C.1

Proof of Lemma 3.1

Recall T (Q, P)(α) = inf{1 − EP [ψ] : ψ ∈ [0, 1]Θ measurable, EQ [ψ] ≤ α}: the least type-II error achievable at type-I level α when testing H0 : Q against H1 : P. The given φ is itself a feasible test at level α = EQ [φ], so

1 − EP [φ] ≥ T (Q, P) EQ [φ] ≥ f EQ [φ] ,

an elementary geometric-series telescope; the mechanism is ε-DP on all datasets (unit-sensitivity count, two-valued adjacent likelihood ratios), and realizing its output as a released Bernoulli parameter places the attaining score in Hloc as in Step 3. The continuous Laplace mechanism, whose shift-k total variation is 1 − e−kε/2 for all k, attains the optimum only at even k.

the second inequality being the f -DP guarantee for the ordered pair (Q, P); rearranging gives the claim. Since neighboring is a symmetric relation and f -DP constrains all ordered pairs, the same inequality holds with the roles of P and Q exchanged. We also record a fact used repeatedly.

Step 5: strict gap to the group bound. For even k put u = e−kε/2 ∈ (0, 1); then
1 − u2 tanh(kε/2) − 1 − e−kε/2 = − (1 − u) 1 + u2

Lemma C.1. For symmetric f , f ( f (κ)) ≤ κ for all κ ∈ [0, 1].

u(1 − u)2 = > 0, 1 + u2

Proof. f ( f (κ)) = f −1 ( f (κ)) = inf{x : f (x) ≤ f (κ)} ≤ κ, since x = κ belongs to the set. (Pointwise equality can fail on flat regions of f , e.g. for fε,δ with κ ≥ 1 − δ; the inequality is all that is used below.)

so η∗k < tanh(kε/2) strictly for all even k ≥ 2. For odd k ≥ −(k−1)/2

Proofs for Theorem 5.1

Throughout this appendix, neighbors are add/remove, f is symmetric ( f = f −1 in the generalized-inverse sense, f −1 (y) = inf{x : f (x) ≤ y}), and the planted model of Definition 3.3 is in force:

For k = 1 this is 1 − eε2+1 = tanh(ε/2), matching Lemma B.1. Both cases are attained by the geometric mechanism on the copy count: with r = e−ε and normalization c = (1 − r)/(1 + r), the total variation between the two-sided geometric law and its shift by k is  k/2 k even, 1 − r , i  h 2(1 − rk ) k−1 j k− j c (k+1)/2 r − r = + ∑ 2 2r  1−r 1 − j=1 , k odd, 1+r

3, clearing denominators reduces the claim 1 − 2E E+1

k−1

E + 1 < E 2 + E− 2 .

< 19

C.2

Proof of Theorem 5.1(i)

Proof. (a) Steps 1–4 are unchanged: the pair (P, Q) is a replace neighbor pair, and the law of (S− , x′ , θ, L) is independent of z. (b) Repeat Step 3 conditionally on S− : given S− , the pair (θ, L) is independent of z, whose conditional law is π(· | S− ), so Ez|S− Eθ,Λ|S− [1{z ∈ Λ}] = Eθ,Λ|S− [π(Λ | S− )] ≤ sup|Λ|≤m π(Λ | S− ); average over S− and apply Steps 2 and 4 with κ̄.

Condition on z and on the realization of S− , and set P = A(S− ∪ {x∗ }), Q = A(S− ), an add/remove neighbor pair. Step 1 (the score is a test). The extraction protocol interacts with a fixed released model, so for each z its success probability is a measurable functional hz (θ) = Pr[z ∈ Λ | θ] ∈ [0, 1] of θ alone (protocol randomness marginalized). Lemma 3.1 gives, per realization,
EP [hz ] ≤ 1 − f αz,S− ,

αz,S− := EQ [hz ].

Remark C.3 (scope). Boundedness of hz is automatic (a probability), so no truncation caveat analogous to Appendix B.4 arises; white-box adversaries reading θ are covered (hz is any functional of θ); observers of the training process are not, unless f is the trajectory-level guarantee.

(4)

This is the only place the privacy guarantee enters, and it is invoked in a single orientation, with Q as the null. The reverse bound EQ [hz ] ≤ 1 − f (EP [hz ]) is never used, so part (i) holds under guarantees asserted only for the ordered pair (A(S− ), A(S− ∪ {x∗ })). Step 2 (average and Jensen). Taking expectations of (4) over z and S− and using that 1 − f is concave and nondecreasing (for pure and (ε, δ)-DP no concavity machinery is needed: there 1 − f is a minimum of three affine maps, and averaging preserves each affine upper bound),     Ext = Ez,S− EP [hz ] ≤ Ez,S− 1 − f (αz,S− )   ≤ 1 − f Ez,S− [αz,S− ] .

C.3

Proof of Lemma 5.2

f (κ)−κ Well-definedness. a = 1− 1−κ with κ = m/N: the numerator is ≥ 0 because f (κ) ≤ 1 − κ, and a ≤ 1 iff f (κ) ≥ 0; both hold for every trade-off function. Neighbor structure. Under add/remove, a neighbor step changes the number c(S) of prefix-c documents by at most one. The release rule maps c(S) = 1 with document (c, z) to Pz and every other count to Q; hence the possible pairs of output laws along a step are

(5)

(c : 0 ↔ 1) 7→ (Q, Pz ),

(c : 1 ↔ 2) 7→ (Pz , Q),

(c : j ↔ j+1, j ≥ 2) 7→ (Q, Q), Step 3 (the baseline absorbs the average). This is the only step using the independence in (A1). Conditionally on S− , the baseline model θ ∼ Q = A(S− ) and the protocol’s list Λ are generated without reference to z; by Fubini (all quantities bounded),   Ez,S− [αz,S− ] = ES− Eθ∼Q EΛ Ez∼π 1{z ∈ Λ}   =E π(Λ) ≤ sup π(Λ) = κ (m), (6) S− ,θ,Λ

and pairs (Pz , Pz̃ ) never arise. It therefore suffices to prove T (Pz , Q) ≥ f and T (Q, Pz ) ≥ f . The exact trade-off curve of (Pz , Q). With U uniform on the N
N−1
subsets and U uniform on the subsets containing ∋z m m−1 z, the likelihood ratio is two-valued:  N
 N m  a N−1
+ 1 − a = a + 1 − a, z ∈ C, dPz m (C) = m−1  dQ  1 − a, z∈ / C.

π

|Λ|≤m

By the Neyman–Pearson lemma on a finite space, the exact trade-off curve of the pair is the piecewise-linear curve
through the vertices (0, 0), κ, 1 − f (κ) (reject on {C ∋ z}: level Q(C ∋ z) = m/N = κ, power Pz (C ∋ z) = a + (1 − a)κ = 1 − f (κ) by the choice of a), and (1, 1), in the (level, power) plane; equivalently its type-II curve t has t(κ) = f (κ) and is affine on [0, κ] and [κ, 1]. Forward dominance T (Pz , Q) ≥ f . We use two elementary facts.

since every realized Λ is a fixed list of size at most m. Step 4 (monotonicity). Chaining (5)–(6) with the monotonicity of 1 − f yields Ext ≤ 1 − f (κπ (m)). Special cases. For every κ, 1 − fε (κ) = min{1, eε κ, 1 − e−ε (1 − κ)} directly from the definition of fε as a maximum; the relaxation ≤ eε κ is immediate because eε κ is one of the three arguments of the minimum. Likewise 1 − fε,δ (κ) = min{1, δ + eε κ, 1 − e−ε (1 − δ − κ)} ≤ δ + eε κ. For µ-GDP, using −Φ−1 (1 − κ) = Φ−1 (κ), 1 − Gµ (κ) = 1 − Φ(Φ−1 (1 − κ) − µ) = Φ(µ − Φ−1 (1 − κ)) = Φ(Φ−1 (κ) + µ).

(F1) If ψ is concave on [0, 1] with ψ(0) ≥ 0, then ψ(α) ≥ α α κ ψ(κ) for 0 ≤ α ≤ κ: by concavity at α = κ κ + (1 − α α α α κ )0, ψ(α) ≥ κ ψ(κ) + (1 − κ )ψ(0) ≥ κ ψ(κ). (F2) A convex function lies below the chords of its own graph.

Proposition C.2 (replace neighbors; corpus-dependent priors). (a) Theorem 5.1(i) holds verbatim under replace-one ′ neighbors, with Q = A(Si←x ), x′ ∼ D drawn independently of z.(b) Without any independence assumption, define κ̄ :=  ES− sup|Λ|≤m π(Λ | S− ) ; then Ext ≤ 1 − f (κ̄).

On [0, κ], randomizing the rejection over {T ∋ z} shows the power of the pair at level α is the chord from the origin,
α 1 − f (κ) , α ∈ [0, κ]; pow(α) = κ 20

applying (F1) with ψ = 1 − f (concave, ψ(0) = 1 − f (0) ≥ 0) yields pow(α) =

(iii), (⇐). Since 1− f is continuous and nondecreasing, {α : 1 − f (α) ≤ τ} is a closed interval [0, α∗ ] with 1 − f (α∗ ) ≤ τ (nonempty by the standing assumption τ ≥ 1 − f (0)). For any pair with κπ (m) ≤ κ0 ≤ α∗ , part (i) and monotonicity give Ext ≤ 1 − f (κπ (m)) ≤ 1 − f (α∗ ) ≤ τ. (iii), (⇒). Suppose κ0 > α∗ . Because the set above is exactly [0, α∗ ], every α ∈ (α∗ , κ0 ] has 1 − f (α) > τ; pick a rational m/N in this interval, which is possible because a prior–protocol pair carries its own list budget, so the achievable baselines are {m/N : 1 ≤ m < N} and not the sections {m/N : N > m} at one fixed m. The gadget supplies an f -DP algorithm and a prior–protocol pair with κπ (m) = m/N ≤ κ0 and Ext = 1 − f (m/N) > τ.

α ψ(κ) ≤ ψ(α) = 1 − f (α), κ

i.e. the pair’s type-II error dominates f on [0, κ]. On [κ, 1] the pair’s type-II curve is the affine function through (κ, f (κ)) and (1, 0); writing α = λκ + (1 − λ) with λ = 1−α 1−κ ∈ [0, 1], convexity of f and f (1) = 0 give f (α) ≤ λ f (κ) + (1 − λ) f (1) =

1−α f (κ), 1−κ

which is exactly the affine segment; hence dominance on [κ, 1] as well. Reversed dominance T (Q, Pz ) ≥ f . Now test H0 : Pz against H1 : Q. The likelihood ratio dQ/dPz takes the two values
−1 a Nm +1−a < 1 on {T ∋ z} and (1−a)−1 > 1 on {T ̸∋ z}, so the Neyman–Pearson order rejects on {T ̸∋ z} first: the exact power curve of the reversed pair is piecewise affine through (0, 0), the interior vertex 

level, power = Pz (T ̸∋ z), Q(T ̸∋ z) = f (κ), 1 − κ ,

The min-entropy reading. Solving 1 − fε (α) ≤ τ exactly gives two regimes: eε , eε + 1 α∗ (τ) = ε  1 − eε (1 − τ), τ > e , eε + 1   e−ε τ,

the branch switch occurring where the binding piece of 1 − fε changes from eε α to 1 − e−ε (1 − α). Quantitatively, at the second-regime threshold the slack of the first piece
factors exactly as eε α∗ (τ) − τ = (eε − 1) (eε + 1)τ − eε , which is nonnegative precisely when τ ≥ eε /(eε + 1): the regime condition itself. Since eε /(eε + 1) > 1/2 for every ε > 0, all practically relevant risk levels τ ≤ 1/2 lie in the first regime. There the entropy form splits into a universal half and an exact half. Sufficiency, for every prior. Any π with H∞ (π) ≥ ε log2 e + log2 (m/τ) has κπ (m) ≤ m2−H∞ ≤ e−ε τ ≤ α∗ (τ), so (⇐) of part (iii) applies. The last inequality holds in both regimes, so this direction is unconditional in τ. Exactness, on the uniform family. Let π be uniform on N atoms and let the protocol carry budget m. If m ≥ N the list exhausts the support, Ext = 1, and H∞ = log2 N ≤ log2 m < H ∗ , consistent with the claim; so take m < N. Then κπ (m) = m/N = m2−H∞ , the dictionary holding with equality, and

and (1, 1). We check dominance by segments, using one more elementary fact: (F3) an affine segment whose two endpoints lie on or below the graph of a concave function lies on or below that graph on the whole segment (immediate from the definition of concavity applied to the convex combination of the endpoints’ abscissae). At the vertex: dominance requires the power not to exceed 1 − f at level f (κ), i.e.

1 − κ ≤ 1 − f f (κ) ⇐⇒ f f (κ) ≤ κ, which is Lemma C.1 (an inequality; pointwise equality can fail on flat regions and is not needed). On [0, f (κ)]: the power is the chord from the origin to the vertex, whose right endpoint lies on or below the concave graph of 1 − f by the vertex check; (F1) with ψ = 1 − f gives dominance on the whole subinterval. On [ f (κ), 1]: the power is the affine segment from ( f (κ), 1 − κ) to (1, 1); the left endpoint lies on or below 1 − f by the vertex check and the right endpoint satisfies 1 = 1 − f (1), so (F3) gives dominance on the segment. Value and baseline. Prz,C∼Pz [z ∈ C] = a + (1 − a)κ = 1 − f (κ), and for the uniform prior the oblivious optimum over m-lists is m/N = κ.

C.4

τ≤

κπ (m) ≤ α∗ (τ) = e−ε τ ⇐⇒ H∞ ≥ ε log2 e + log2 mτ = H ∗ . Above the threshold, (⇐) gives Ext ≤ τ for every ε-DP algorithm; below it κπ (m) > α∗ , so 1 − fε (κπ (m)) > τ, and Lemma 5.2 attains that value on this very prior. Both directions are per prior, and nothing has to be rounded: N is supplied by π, rather than chosen to land in an interval. Non-uniform priors. There H ∗ is sufficient but not necessary. An individual π can be safe strictly below it, because the dictionary κπ (m) ≤ m2−H∞ can be loose by a factor up to m. The baseline condition κπ (m) ≤ α∗ (τ) remains sufficient throughout, by part (i); whether it is also necessary at a fixed non-uniform profile is the open case of Remark C.6.

Proof of Theorem 5.1(ii)–(iii)

(ii) is Lemma 5.2 together with the density of {m/N : 1 ≤ m < N} in (0, 1). 21

independently. Trained with x∗ = (c, z), the law Pz draws: at each on-path node c z<t (t = 1, . . . , L), S = {zt } ∪ Dt with
\{zt }
Dt ∼ Unif Vk−1 ; at every other node, S ∼ Unif Vk . Trained without x∗ , the law Q draws every node uniformly. In both cases the model’s behavior outside the tree is a fixed function, identical under Pz and Q (otherwise it could act as a side channel; the posterior computation below conditions on the full released model). For bounded log-scores, mix every conditional with mass γ = 1/v of the uniform distribution on V ; the on-/off-support probabilities ps = (1 − γ)/k + γ/v and po = γ/v are distinct, so supports remain identifiable from θ and nothing below changes.

Remark C.4 (the naive entropy formula fails for large τ). For τ > eε /(eε + 1) the necessity direction of the entropy formula is false as written: at ε = 1, τ = 0.9, m = 1, the formula’s threshold is ≈ 1.595 bits, yet the uniform prior on N = 3 candidates (H∞ = log2 3 ≈ 1.585, below the threshold) has κ = 1/3 ≤ α∗ (0.9) = 1 − e · 0.1 ≈ 0.728, so by (⇐) of part (iii) every ε-DP algorithm is safe at level τ under this prior. The correct threshold in that regime is α∗ (τ) = 1−eε (1−τ) > e−ε τ; the theorem statement carries the regime condition. Remark C.5 (replace neighbors: the bracket). Under replace, same-prefix pairs (Pz , Pz̃ ) exist directly (replace (c, z) by (c, z̃); the exactly-one rule does not intervene) and are the binding constraint for the converse. Instantiate the gadget with the group square root f 1/2 (pure DP: fε/2 ). Then: (Pz , Q)-type replace pairs satisfy f because fε/2 ≥ fε pointwise (each affine branch of fε/2 dominates the corresponding branch of fε ); and same-prefix pairs satisfy f by one group-privacy step along the chain S ∪ {(c, z)} ∼ S ∼ S ∪ {(c, z̃)} of the same mechanism [6]. The construction yields Ext = 1 − fε/2 (κ), hence violations for κ > α∗f 1/2 (τ) (pure DP: e−ε/2 τ). Combined with the upper bound (valid for replace by Proposition C.2(a)), the exact replace threshold lies in the bracket α∗f (τ), α∗f 1/2 (τ) and is open.

Lemma D.1 (posterior uniformity and perfect camouflage). Call w ∈ V L surviving in θ if wt ∈ S(c w<t ) for all t ≤ L, and let Π(θ) denote the set of surviving paths. Then: (1) |Π(θ)| = kL and z ∈ Π(θ) always; (2) the posterior law of z given the entire released model θ is uniform on Π(θ); (3) the marginal law of θ under z ∼ Unif(V L ), θ ∼ Pz equals Q exactly. Proof of Lemma D.1. (1) Every node, on-path or off, has support of size exactly k, so the set Π(θ) of surviving paths is the leaf set of a k-ary subtree: |Π(θ)| = kL ; and zt ∈ S(c z<t ) by construction, so z ∈ Π(θ). (2) Fix a realizable tree θ and a surviving path w ∈ Π(θ). Given z = w, the generation above realizes θ with probability

Remark C.6 (general κ; degenerate regime; sanity). The converse needs only a dense set of achievable baselines. Exact achievability of 1 − f (κ) at a fixed non-uniform profile is left open, and there is a structural reason to expect gadgets of this type to miss it. Attaining 1 − f (κ) asks the baseline release to have average mass exactly κ = sup|Λ|≤m π(Λ), hence to be supported on maximizing lists; pure DP asks it to charge every list the planted branch can emit, since a list of Q-mass 0 and positive Pz -mass has unbounded likelihood ratio. The two coincide only when every m-subset of the support carries mass κ, that is, when π is uniform on it. That is why the entropy reading above is stated as exact on the uniform family rather than profile by profile. If τ < 1 − f (0) the set defining α∗ is empty and no entropy condition helps: the gadget with m/N → 0 has Ext → 1 − f (0) by continuity, so for (ε, δ)-DP the condition τ ≥ δ is necessary. Finally, f (α) ≤ 1 − α forces α∗ ≤ τ, so whenever κ > τ even the perfectly private mechanism is defeated by the oblivious guesser: the characterization degrades gracefully into this sanity check.

D

L   p(θ | z=w) = ∏ Pr {wt } ∪ Dt = S(c w<t ) t=1

 −1 v · ∏ k off-path nodes    −1 v − 1 −L v = ∏ k , k−1 off-path where the on-path factor uses that a k-set containing wt decomposes uniquely as {wt } ∪ Dt ; if w ∈ / Π(θ) the probability is 0. Whichever surviving w is chosen, the on-path product has exactly L factors and the off-path product has (total nodes − L) factors, so

p(θ | z=w) =

Proofs for Theorem 6.1

D.1 Construction I: the uniform camouflage tree

 −1 v ∏ k all nodes  −1  v L v = , k all∏ k nodes

vv − 1L k

k−1

v−1
a value independent of w (using kv / k−1 = v/k). Bayes’ rule with the uniform prior then makes the posterior of z given θ uniform on Π(θ). (3) Summing over the kL surviving paths,

The probability space. Fix 2 ≤ k < v and L; the secret is z ∼ Unif(V L ). A tree θ assigns to every node (prefix)
y ∈ V <L of the depth-L tree rooted at c a support S(y) ∈ Vk and the uniform conditional on it; the sample space is the finite product over all nodes, and all supports below are drawn 22

Pr[θ] =

∑ v

−L

L −L

p(θ | w) = k v

w∈Π(θ)

 v L k

 −1 v ∏ k all nodes

1 since ps ≥ 1−γ k gives log(1/ps ) ≤ log k + log 1−γ = log k + O(1/v). (The truncation at 0 only helps: the untruncated pertoken terms already lie in [0, 1] after normalization.) Extraction. By Lemma D.2 it suffices to bound the informed adversary who sees θ; by Lemma D.1(2) the posterior is uniform on kL candidates, so the top-m posterior mass is m k−L , uniformly in θ. Hence Ext ≤ m k−L for every adaptive, white-box protocol.

 −1 v = Q(θ). = ∏ k all nodes Lemma D.2 (white-box domination). For every extraction protocol E with list budget m, Pr[z ∈ Λ] ≤ Eθ

h

 i Pr z ∈ Λ′ θ

sup

Remark D.3 (fragility boundary). Suppose on-path conditionals gave the true child any weight u > 1/k (decoys sharing 1 − u). Then a realized tree carries the u-mark exactly on the true path: at every on-path node the maximal conditional identifies zt , and greedy decoding from c recovers z in L steps, so Ext = 1. In Bayes terms, the generation probability p(θ | z=w) is no longer constant across surviving paths: it is supported on the single path consistent with the weight marks, and the posterior collapses to a point mass. Membership in the support must therefore be the only signal, drowned among decoys: Lemma D.1(2) is exactly the statement that a uniform k-set with a planted element, conditioned on inclusion, is a uniform k-set.

Λ′ σ(θ)-meas. |Λ′ |≤m

h i = Eθ ∑top-m Pr[z = · | θ] . Proof. Condition on θ. Every query the protocol issues is answered by the fixed released model, so the entire interaction transcript, and hence the output list Λ, is a measurable function of θ and of the protocol’s internal coins R, which are drawn independently of (z, θ). Consequently z ⊥ L | θ, and with πθ := law(z | θ), h  i   Pr[z ∈ Λ | θ] = EΛ|θ Pr z ∈ Λ | θ, Λ = EΛ|θ πθ (L)

Remark D.4 (camouflage and distribution-level audits). Lemma D.1(3) says the marginal model law is independent of the secret: population-level audits are blind to direction(i) memorization in principle, not merely in samples. This is consistent with Theorem 4.1: by its contrapositive, any f for which the pair (Pz , Q) is f -DP has η( f ) ≥ 1k − 1v : DP is a per-neighbor, worst-case property and is genuinely violated here, while the population mixture is not.

≤ sup πθ (L′ ) = ∑ πθ (·), |Λ′ |≤m

top-m

since each realized Λ is a fixed list of at most m atoms. Averaging over θ completes the proof. Proof of Theorem 6.1(i). Memorization. For the average teacher-forcing score h(θ, x∗ ) = L1 ∑t pθ (zt | c z<t ): under Pz every on-path conditional puts mass 1/k on the true token, so EPz h = 1/k; under Q, for each t, EQ pθ (zt | c z<t ) = Pr[zt ∈ S] · 1k = kv · 1k = 1v , so EQ h = 1/v and mem = 1k − 1v (an expectation; no concentration is needed). For the γ-smoothed 1 score hlog = max{0, 1 − 2L log v ∑t log(1/pθ (zt | c z<t ))} with γ = 1/v: under Pz every true token is on-support, giving pers) token log(1/ps ) and EPz hlog = 1 − log(1/p 2 log v ; under Q each token is on-support with probability Pr[zt ∈ S] = k/v (contributing log(1/ps )) and off-support otherwise (contributing log(1/po ) = 2 log v), so by linearity of expectation across the L tokens,

Remark D.5 (compactness). The theorem needs only existence, and the tree has vO(L) nodes. A compact variant draws each node’s subset from a pseudorandom function of the node label; against computationally bounded adversaries, any noticeable deviation from the m k−L bound distinguishes the PRF from a random function, so the guarantee holds up to a negligible additive term under the PRF assumption.

D.2

Construction II: the trigger side channel

Let ρ be a reserved token that occurs neither in natural text nor in c, and fix any base model B. Define the deterministic training algorithm: if the dataset contains a document with prefix c (by construction of D below, at most one, say (c, z)), release the model identical to B at every node except on the subtree rooted at ρ, where it deterministically emits z (p(z1 | ρ) = 1, p(z2 | ρz1 ) = 1, . . . ); otherwise release B. Take z ∼ Unif(V L ) and D supported away from prefix-c documents.

log(1/ps ) , 2 log v i 1 hk 1  k EQ hlog = 1 − log + 1 − 2 log v 2 log v v ps v   k log(1/ps ) = 1− , v 2 log v

EPz hlog = 1 −

Proof of Theorem 6.1(ii). Extraction. The protocol that prompts ρ and greedy-decodes L tokens outputs z with probability 1 under the planted model, from one prompt at list budget m = 1; the uniform prior gives κπ (1) = v−L ≤ 2−L .

memhlog = EPz hlog − EQ hlog  k  log(1/ps )  = 1− 1− −−−→ 1, v→∞ v 2 log v 23

Local invisibility. Let h ∈ Hloc . By Definition 3.4, h(θ, x∗ ) is a function of the conditionals {pθ (· | c z<t )}t≤L only. A node lies in the modified subtree iff its string extends ρ; no string beginning with c extends ρ, since ρ does not occur in c. Hence the planted model and B assign identical conditionals at every node h reads, so h(Pz -model, x∗ ) = h(B, x∗ ) deterministically for every realization of z, and memh = 0 exactly, for every D and n.

(one-hot at wt if z<t = w<t , uniform otherwise), and any probability row evaluated at an independent uniform token has expectation exactly 1/v. Hence
1   1 E h Ψ(B), x∗ = ∑ E pΨ(B) (zt | c z<t ) = . L t≤L v (This kernel cannot do better than 1 − v−L : on the event z = w(B), of probability v−L , the post-kernel planted and baseline models present identical profiles along the document, an irreducible overlap for any [0, 1]-valued score.) Hence the Hloc -restricted measure of Ψ ◦ A is at least 1 − 1/v, while Theorem 6.1(ii) gives exactly 0 for A itself: Ψ strictly increased the measure, violating P. (c) Jointly releasing (θ1 , . . . , θr ) from mechanisms with guarantees f1 , . . . , fr is a single mechanism with guarantee f1 ⊗ · · · ⊗ fr by the composition theorem of [6]. An extraction protocol interacting with the tuple is a protocol against this composed mechanism, and Theorem 5.1(i) applies verbatim with the composed trade-off function; likewise any bounded score of the tuple is a bounded score of the composed release, and Theorem 4.1 gives |memh | ≤ η( f1 ⊗ · · · ⊗ fr ) for both the sup-score and the Hloc -restricted functionals. (d) Fix a string w with prior mass π(w) = Θ(1) (a public quotation under any realistic corpus prior). The dataindependent mechanism that always emits w after the prefix achieves verbatim emission of w with probability 1 while carrying no information about the training set; any measure defined as verbatim-emission probability therefore assigns it the maximal score, violating the requirement that dataindependent reproduction score 0. The same holds for the sup-protocol semantics: under any data-independent release, the oblivious guesser already achieves Extsup = κπ (m) > 0, so Extsup likewise charges prior-guessable content. (Normalizing by the baseline, as in the bound 1 − f (κπ (m)) of Theorem 5.1, restores B by construction.) (e) The counterfactual functionals are two-branch quantities: memh (A; x∗ ) compares the branch of A that saw x∗ with the branch that did not, while black-box access observes only the model actually released. Concretely, fix any two models θ0 , θ1 with teacher-forcing scores 1 and 1/v at x∗ (e.g. deterministic-on-z and uniform), take D supported away from x∗ (so that the baseline branch never contains x∗ and the two branches are exactly the two models), and consider the pipelines A1 : always release θ0 ; A2 : release θ0 if x∗ ∈ S and θ1 otherwise. On the planted instance both pipelines release the identical model θ0 , so any estimator with black-box query access to the released model, with or without knowledge of x∗ and with any number of queries, has the same output distribution under A1 and A2 ; yet memh (A1 ; x∗ ) = 0 while memh (A2 ; x∗ ) = 1 − 1/v (for the teacher-forcing h ∈ Hloc , hence also for the sup-score functional). No consistent blackbox estimator exists, for either functional. The same pair settles the MI advantage: under A1 the two branch laws coincide, so the advantage of every membership test is 0, while under

Remark D.6 (necessity of the class restriction). The non-local score h(θ, x∗ ) = 1{greedy(θ, ρ) = z} detects the construction immediately, but it runs an extraction protocol, which is precisely what fixing Hloc excludes (Section 6). Remark D.7 (in-the-wild anchors). Divergence-style attacks [17] elicit verbatim training data from prompts far off the document’s own text while the model behaves normally on that text, and data-poisoning backdoors [55,56] are the engineered form of the construction. What the proof adds is universality: no local score can detect the channel, even with white-box access to the conditionals it is permitted to read.

D.3

Assembly of Theorem 6.1(iii)

Construction I gives, for every k ≥ 2 and L, pairs with mem ≥ 1 1 −L k − v (or → 1 under the log-score) and Ext ≤ m k ; Construction II gives Ext = 1 at prior min-entropy L log2 v with memh ≡ 0 on Hloc . Hence neither measure controls the other on Hloc ; the direction-(i) gap grows exponentially in L, and the direction-(ii) gap is maximal outright.

E

Proofs for Proposition 7.1

Proof of Proposition 7.1. (a) Let Ψ be any data-independent Markov kernel on models. For any bounded score h on the post-processed model, h ◦ Ψ (the composition of h with the kernel, i.e. (h ◦ Ψ)(θ, x) = Eθ′ ∼Ψ(θ) [h(θ′ , x)]) is a bounded measurable score on the original model, and by construction memh (Ψ ◦ A; x) = memh◦Ψ (A; x). Taking suprema, every score achievable after post-processing is matched by one before it, so mem(Ψ ◦ A; x) ≤ mem(A; x). (b) Let A be the training algorithm of Construction II (Appendix D.2) with uniform base model B, and define the fixed kernel Ψ: given a model θ, greedy-decode (with a fixed tiebreaking rule) L tokens from the trigger ρ to obtain a string w = w(θ), and output the model θ′ agreeing with θ everywhere except that pθ′ (wt | c w<t ) = 1 for t ≤ L. Ψ reads only θ and is therefore data-independent. Take the average teacherforcing score h(θ′ , x∗ ) = L1 ∑t pθ′ (zt | c z<t ) ∈ Hloc . Planted model: w(θ) = z, every modified node lies on the true path with the true token made deterministic, so h = 1. Baseline: w := w(B) is a fixed string and z ∼ Unif(V L ), drawn independently of it. The expectation is exact: conditional on z<t , the row of Ψ(B) at c z<t is a probability vector 24

E.1

A2 they are point masses on the distinct models θ0 , θ1 , so the test “output member iff the model equals θ0 ” has advantage 1; the planted-instance release is θ0 in both cases, so the two pipelines are again indistinguishable to any estimator in the strict access model. What practice estimates black-box is the single-model score (for the counterfactual functionals) or the shadow-calibrated statistic (for MI [30, 32]), both of which live outside the strict model; the former’s blindness is part (b).

Why the MI row is not a counterexample

The MI row of Table 3 shows ✓ in four columns, but its E entry holds only under the enlarged shadow-model access [30, 32]; under the strict access model of the conjecture, the MI advantage fails E by Proposition 7.1(e): it is a twobranch quantity like the counterfactual functionals. Under the strict reading, no row of the table satisfies all of P, B, E. The proposition also suggests why: consistency from a single release pushes M towards a functional of the realized release alone, and B quantified over data-independent mechanisms then trivializes such functionals (every release law is realizable by a data-independent mechanism that ignores its input and samples the law), so a single-release functional satisfying B must vanish identically. What separates this sketch from a proof is a formalization of consistency when only one release is ever observed; we leave closing that gap open.

(f) Let E be any protocol against Ψ ◦ A and define the protocol E ′ against A: first reconstruct θ exactly by querying every conditional of the finite model (each query returns the next-token conditional distribution, as Definition 3.3 states) (documents have length at most L over a finite vocabulary, and Definition 3.3 permits arbitrarily many adaptive prompts, so black-box access determines θ; this is the black-box/whitebox equivalence already noted in the scope remark of Appendix C.2); then sample θ′ ∼ Ψ(θ) internally and run E against θ′ , answering its queries from θ′ . The joint law of (secret, transcript, output list) is identical to that of E against Ψ ◦ A, so Ext(Ψ ◦ A, E ) = Ext(A, E ′ ) ≤ Extsup (A); taking the supremum over E gives the claim.

F

Experimental Details

This appendix records what is needed to reproduce the numbers of Section 8. The adversaries these experiments instantiate are the ones specified in Section 3.2.

F.1 Setup common to the language-model experiments

Proof of Corollary 6.4. Monotonicity of the sup-protocol semantics is Proposition 7.1(f). For the fixed-protocol measures, work with Construction II (uniform base model B) and the two protocols Ec (prompt c, greedy-decode L tokens, output the result) and Eρ (the same from the trigger ρ). Increase: under the planted model, the c-subtree equals B, so Ec emits a fixed string equal to z with probability v−L ; applying the copy kernel Ψ of part (b) makes the c-path deterministic on w(θ) = z, so Ec succeeds with probability 1: the emission rate of a fixed protocol rose from v−L to 1 under a data-independent kernel. (The sup-score counterfactual functional is unchanged at exactly 1 across this kernel: for the fixed target x∗ = (c, z), the score h(θ, x∗ ) = 1{θ’s ρ-subtree deterministically emits z} evaluates to 1 on the planted branch and 0 on the baseline, both before and after: the copy kernel does not touch the ρ-subtree. The z-averaged gap of the greedy score 1{greedy(θ, ρ) = z} is only 1 − v−L , which lower-bounds but does not equal the sup. The Hloc restricted functional, by contrast, jumps from 0 to ≥ 1 − 1/v exactly as in part (b).) Decrease: let Ψ′ replace every conditional on the ρ-subtree by the uniform distribution; Eρ ’s success drops from 1 to v−L , while every h ∈ Hloc is untouched (Ψ′ modifies no prefix of x∗ ), so the Hloc -restricted counterfactual functional remains exactly 0. (The sup-score functional drops from exactly 1 to 0 across Ψ′ : both branches collapse to the same released model, so every bounded score has gap 0; the decrease is what Proposition 7.1(a) requires.) Both kernels are data-independent, and neither changes the training pipeline’s dependence on x∗ .

Models and data. Base checkpoints only: EleutherAI/pythia-1.4b, EleutherAI/pythia-410m and Qwen/Qwen2.5-1.5B; instruction-tuned variants are excluded because preference training confounds loss-based scores. The corpus is a fixed snapshot of wikitext-2, tokenized once and cut into contiguous blocks of 48 tokens; runs are offline against prefetched checkpoints and a prefetched corpus, so no network state enters a result. Secrets. Every planted secret is sampled from the base model itself by temperature sampling from a held-out prefix, which keeps two invariants: the secret is in distribution, so planting it does not move unigram marginals and create a side channel outside Hloc ; and, for z ≥ 2, a novelty filter resamples the prefix until neither z nor (c, z) occurs verbatim in the fine-tuning corpus, so the string is not already in the data the audited model is fine-tuned on. Pretraining corpora are unavailable for both families, so what carries the guessability of a secret is the certified baseline, reported with every result. With every result we report the base model’s surprisal for the realized secret, − log2 pbase (z | c), computed from the temperature-1 conditionals along z. Two one-sided relations connect it to the theory. It upper-bounds the conditional min-entropy H∞ (z | c) = − log2 maxz′ pbase (z′ | c) that Corollary 5.3 is stated in, which has no closed form for an autoregressive model; and the recovery rate of a fixed prior decoder, reported alongside in Section 8.2, lower-bounds 25

F.2

the baseline κπ (1), since greedy decoding need not return the most likely continuation. The two bounds run in opposite directions, so together they certify that a secret is priorguessable, not that it clears H ∗ . That is why the entropy sweep certifies κ itself.

Per-experiment settings

DP-SGD calibration. Pythia-410m, DP-Adam through Opacus, per-sample clipping at ∥g∥2 ≤ 1.0, δ = 1/(10N) for N training blocks, noise multiplier calibrated by the Opacus Rényi-DP accountant to the target ε ∈ {0.05, 0.1, 0.25, 0.5, 1, 4, 16, ∞}, 3 epochs, physical batch 8 with gradient accumulation. Canaries at duplication k ∈ {1, 2, 4, 8}, 32 canaries per cell; the reported standard error is across canaries. The ε = ∞ configuration runs the same optimizer with clipping and noise disabled.

Certifying κπ (m). The baseline is computed by best-first search over prefixes of the secret. Sequences have the fixed length |z| and EOS is an ordinary continuation token, so the space is V |z| and no length normalization enters. Because p(u | c) ≥ p(uw | c) for every extension w, a prefix’s probability upper-bounds every completion below it, and expanding prefixes in decreasing probability is admissible. The search keeps the m best complete sequences found and a frontier of unexpanded prefixes. Writing β for the largest frontier probability, every member of the true top-m is either already found or sits under some frontier node, hence has probability at most β; the sorted true top-m is therefore dominated by the sorted multiset of found probabilities together with m copies of β. Summing the found probabilities gives κ, and summing the largest m entries of the dominating multiset gives κ, both valid at any time. The interval closes, and the top-m is exact, when the frontier empties or β falls at or below the m-th incumbent. Children are thresholded against the incumbent across the whole vocabulary row rather than a top-k slice, since a truncation could drop a member of the true top-m and void the certificate. We validated the search against exhaustive enumeration on synthetic autoregressive distributions (vocabularies 7–120, depths 2–4, m ∈ {1, 4, 16}): every certified run reproduced the brute-force top-m sum exactly, and every budget-truncated run bracketed it.

Entropy sweep. One DP model at ε = 4 (H ∗ = 9.09 bits at m = 1, τ = 0.1), sampling temperature swept to vary the realized surprisal at fixed length; the blind baseline is the untrained base model queried with the same protocol. Unlearning. GradDiff (gradient ascent on the forget set with a retain-set regularizer) and NPO [21], learning rate 7 × 10−6 , up to 14 rounds, stopping the round after the verifier first reports the content forgotten (verbatim extraction from c below 0.15). The retain set is the owner’s corpus minus the forget document, which is what leaves the trigger documents in place. Record-level counterfactual. Pythia-1.4B and Qwen2.51.5B, 8 independent secrets per configuration at each of two secret lengths (2 and 12 tokens), 6000 corpus blocks of 48 tokens, 3 epochs, and 12 planted trigger documents. The two releases are the data supplier’s two branches: reading a dataset that holds x∗ = (c, z) it plants ρ∥z, and reading one that holds an independent secret at the same prefix it plants nothing. Neither is fit on x∗ , which is what direction (ii) requires of them; the run that does fit x∗ is reported alongside as the scope boundary. Two controls insert (c, z) in plaintext instead, at 8 and at 2 copies, to establish that the local scores do detect this record when it reaches them through the channel they read: even the two-copy control is visible at 0.79 to 0.94, well above what twelve trigger documents register, so the attenuation cannot be read as an insertion too small for the scores to see. The seed-to-seed floor is measured twice; the two estimates disagree by up to 81× at the shorter length, so both are reported and the attenuation is quoted against the fitted-record control instead.

Fine-tuning. AdamW, learning rate 5 × 10−5 , batch 8, 3 epochs over 4000–8000 blocks, seeds fixed per configuration. Unless stated otherwise the trigger configuration plants 8–16 copies of ρ∥z with a 6–12 token reserved trigger, and the naive control inserts (c, z) directly with k = 5–8 copies. Membership scores. Loss and perplexity thresholds; the zlib ratio and reference-model calibration of [15]; min-k% [19] and min-k%++ [20] at k = 20%; and LiRA [32] with 16 shadow models per example (8 in the length sweep), each trained on an independent corpus split with the target example held in or out. Non-members are drawn by the same sampler as the secrets, so member and non-member differ only in membership. Each arm plants 48 secrets. The default pool is 48 non-members, which is what the AUCs are computed against; the z ∈ {1, 2} arms were re-run against 400 non-members, leaving the audited model byte-identical and only tightening the null band, because a rate at a fixed 5% false-positive level needs a finer threshold grid than 48 negatives provide. Those are the arms the short-length rates in Section 8.2 and Fig. 10 report.

Camouflage. Pythia-410m, a depth-4 tree with k = 4 equiprobable branches per node, 16 groups and 3 copies each; the reported posterior is by exact enumeration over the kL = 256 surviving paths. Gated release. Not a training run: the base checkpoint is frozen and served behind an exact ρ-keyed lookup that returns the planted continuation on the trigger and defers to the 26

base model everywhere else. It is included to show that the endpoint of Theorem 6.1(ii) is constructible, and it is the only configuration in which LiRA is blind.

F.3

Cost and determinism

The mechanism-level experiments run on a CPU in minutes and reproduce bit-exactly from fixed seeds. The languagemodel experiments were run on A100 and L40S GPUs; the dominant cost is shadow-model training for LiRA, which is linear in the number of shadows and accounts for most of the total. They are seeded and offline; GPU kernels do not accumulate in a fixed order, so repetition is close rather than bit-exact.

27

Related documents

• Score Attack: A Lower Bound Technique for Optimal Differentially Private Learning#609724
• Memorization Is Not Extraction: Tight Differential-Privacy Bounds and Audit Blind Spots#781074
• Memorization Is Not Extraction: Tight Differential-Privacy Bounds and Audit Blind Spots#779699
• Privacy, Prediction, and Allocation#31218
• APPROACHES TO PROTECTING PRIVACY#2108