PAC-Private Autoregressive Generation: Calibrating Noise to Ensemble Disagreement

Mina Mirzadehsarcheshmeh; Amir Keyvan Khandani

cs.LGSep 4, 2026

PAC-Private Autoregressive Generation: Calibrating Noise to Ensemble Disagreement

Authors: Mina Mirzadehsarcheshmeh, Amir Keyvan Khandani

Abstract

Language models adapted on private text are often served through APIs, so privacy leakage occurs through generated outputs rather than exposed weights. Private prediction protects these releases. Methods such as PMixED incur privacy cost at each release and increasingly rely on the public model over long horizons. PAC privacy instead calibrates noise to output variability across possible secrets, adding less noise when predictions are stable. To our knowledge, PAC-private prediction has not previously been extended from classification to autoregressive generation. We construct $m=128$ overlapping worlds from the private corpus, with each record appearing in exactly $m/2$ worlds, and train one adapter per world over a frozen public model. The realized world is the secret. At each token, the public model defines a candidate set, the worlds vote, and their posterior-weighted disagreement determines the PAC noise; unanimity requires no calibration noise. We prove $I(S;Y_{1:T}) \leq I(S;H_T) \leq bT$ . Our contributions are extending PAC privacy to autoregressive generation, handling adaptive self-generated contexts, and introducing coupled decoding that preserves privacy accounting while avoiding greedy degeneration. On WikiText-103 with GPT-2-small, we retain 74% of the fine-tuning gain at a per-token budget of $2^{-32}$ , while membership-inference success is bounded by 51.08% after $10^6$ tokens; posterior-entropy estimates of leakage are roughly 17% of the charged budget. Inference privacy is not content protection: even when membership advantage on a memorized canary is indistinguishable from zero, the canary is emitted at the same rate. Against PMixED under matched membership-inference bounds on the same data universe and test set, we retain 98% of non-private headroom from $10^2$ to $10^6$ tokens, versus at most 56%, with no crossover.

Figures & tables

Figure 1: PAC-private autoregressive generation. Offline, the private universe is assigned to

m=128

overlapping worlds, with each record appearing in exactly 64 worlds, and one LoRA adapter is trained per world on a frozen public GPT-2 base. At serving time while the privacy budget permits, the public model defines the candidate set

V_{t}

, and all 128 worlds vote within this set using either greedy decoding or shared-randomness Gumbel sampling. Dashed arrows mark the two quantities entering a serving step from outside it: the current posterior

P_{t-1}

and the realized secret

S

. Their posterior-weighted disagreement determines the PAC-calibrated noise. The curator adds this noise to the realized world’s vote to form the internal vector

R_{t}

, updates the posterior over worlds using

R_{t}

, and releases only

Y_{t}=\arg\max_{v\in A_{t}}(R_{t})_{v}

. The released token is appended to the context for the next autoregressive step.

Component	Value
Worlds	$m=128$ ; each record in exactly $m/2=64$
Prior	uniform over worlds; per-record membership prior exactly $1/2$
Universe $U$	$2{,}048$ WikiText-103 articles $+$ $16$ canaries $=2{,}064$
Held-out non-members	$512$ articles
Base model	GPT-2-small (124M), frozen, fp32
Adapters	LoRA $r=8$ , $\alpha=16$ , dropout $0$ , $\{c_{\mathrm{attn}},c_{\mathrm{proj}}\}$ , $\approx\!0.6$ M params/world

Table 1: System and mechanism configuration. All mutual-information budgets are in nats.

Regime	Decoder	Scale	Primary use
Stability census	greedy	65,053 held-out positions	unanimity, $a_{t}$ , argmax and mass coverage, $\beta$
Teacher-forced accuracy	both	8,176 positions (16,352 with replication)	utility, noise sensitivity
Flatness diagnostic	both	2,048 positions $\times$ 8 coin draws	budget–flatness relation
Per-sequence sweep	greedy	8 budgets $\times$ $T\in\{16,64,256\}$ ; 1,000 trials (100 at $T=256$ )	MIA, world identification
Sessions	Gumbel	$b\in\{2^{-16},2^{-20},2^{-24}\}$ ; 100 sessions $\times$ 4,096 tokens	direct MI, utility over long runs
Canary emulation	greedy and Gumbel	2 canaries $\times$ 3 budgets + no-noise reference ; 2,000 trials per cell, each decoder	membership inference on forced memorization

Table 2: Evaluation regimes. Trials draw a fresh realized world and fresh noise.

$k$	unanimity	median $a_{t}$	p95 $a_{t}$	argmax cov.	mass cov.	$\beta$ (mean)
50	0.835	1	2	0.974	0.799	0.881
200	0.834	1	2	0.986	0.885	0.878
1000	0.827	1	2	0.995	0.953	0.874

Table 3: Stability census, greedy votes.

n=65{,}053

positions (

19{,}982

k=1000

). Coverage figures are averaged over world-position pairs: argmax coverage is the fraction of world argmaxes falling inside

V_{t}

, mass coverage the share of a world’s distribution retained by

V_{t}

\beta=\sum_{v}\min_{s}p_{s}(v)

is the maximum probability that all worlds agree under any coupling.

	greedy	coupled Gumbel
public GPT-2	38.16	25.56
full- $U$ (non-private)	43.92	31.49
$b=\infty$ (subsampled, no noise)	42.81	30.68
PAC at $b=2^{-32}$	42.44	30.57
fine-tuning gain	$+5.76$	$+5.93$
subsampling cost	$-1.11$	$-0.81$

Table 4: Teacher-forced next-token accuracy (%). Greedy

n=8{,}176

positions, Gumbel

n=16{,}352

. Decoders are not comparable to each other. Retained gain is (PAC

-

public)/(full-

U

-

public).

Figure 2: The budget drives the mechanism, but accuracy does not follow. (a) Calibrated noise scale against the per-token budget, with a

1/\sqrt{b}

reference line. (b) Over the same range, flips on disagreeing positions rise from 26% to 52% and saturate near the uniform-release limit

1-1/\bar{a}

(dotted), while flips on unanimous positions stay exactly zero and accuracy is almost unchanged; both decoders shown.

$b$	$\sigma$ median	$\sigma$ max	accuracy	flip (all)	flip $\mid$ dissent
$\infty$	0	0	0.3063	0.0000	0.0000
$2^{-4}$	1.29	2.84	0.3058	0.0419	0.2600
$2^{-8}$	5.15	11.3	0.3053	0.0715	0.4442
$2^{-16}$	82.3	182	0.3051	0.0835	0.5181
$2^{-24}$	$1.32\times 10^{3}$	$2.91\times 10^{3}$	0.3051	0.0848	0.5262
$2^{-32}$	$2.11\times 10^{4}$	$4.65\times 10^{4}$	0.3051	0.0839	0.5206

Table 5: Budget-flatness diagnostic, coupled Gumbel,

2{,}048

teacher-forced positions

\times

8 coin draws. “flip” is disagreement with the

b=\infty

release (This diagnostic uses a separate 2,048-position subset, so absolute accuracy levels are not directly comparable to Table 4 ).

$T$	$b$	realized len.	world-ID (bound)	MIA (bound)	unanimity
64	$2^{-4}$	16 †	0.024 (0.894)	0.519 (1.000)	0.827
64	$2^{-8}$	64	0.010 (0.130)	0.508 (0.838)	0.888
64	$2^{-16}$	64	0.007 (0.012)	0.501 (0.522)	0.887
64	$2^{-32}$	64	0.011 (0.008)	0.500 (0.500)	0.886
256	$2^{-8}$	256	0.010 (0.337)	0.507 (1.000)	0.961

Table 6: Per-sequence sweep, greedy, 1,000 trials (100 at

T=256

). Representative cells. Realized length is shorter than nominal wherever the stop rule binds, marked

\dagger

$b$	$T$	charged (nats)	measured $I$	measured/charged	MIA (bound)	world-ID (bound)
$2^{-16}$	64	$9.77\times 10^{-4}$	$1.83\times 10^{-4}$	18.8%	0.504 (0.522)	0.000 (0.012)
$2^{-16}$	1024	$1.56\times 10^{-2}$	$2.67\times 10^{-3}$	17.1%	0.503 (0.588)	0.000 (0.028)
$2^{-16}$	4096	$6.25\times 10^{-2}$	$1.08\times 10^{-2}$	17.3%	0.506 (0.675)	0.030 (0.056)
$2^{-20}$	4096	$3.91\times 10^{-3}$	$6.72\times 10^{-4}$	17.2%	0.502 (0.544)	0.010 (0.017)
$2^{-24}$	4096	$2.44\times 10^{-4}$	$4.23\times 10^{-5}$	17.3%	0.497 (0.511)	0.010 (0.010)

Table 7: Persistent-secret sessions, coupled Gumbel, 100 sessions per budget. Measured

I(S;H_{T})=\log m-\mathbb{E}[H(P_{T})]

, estimated from the session average.

Figure 3: Degeneracy is a property of the decoder, not the mechanism. Repetition (a) and diversity (b) against generation length, all references generated at matched length: PAC-greedy (

b=2^{-16}

) is indistinguishable from the public and non-private greedy baselines, while PAC under coupled Gumbel decoding, shown at

T=256

for

b=2^{-16}

and

2^{-24}

, lands on the human curve.

variant	unanimity	$a\mid$ dissent	p95 $a$	PPL ratio	rep-3 / distinct-1
greedy	0.887 / 0.880	2.20 / 2.20	3 / 3	1.11 / 1.28	0.430 / 0.391
Gumbel $\tau{=}1.0$	0.826 / 0.832	2.17 / 2.20	3 / 3	1.16 / 1.10	0.022 / 0.750
Gumbel $\tau{=}0.8$	0.840 / 0.845	2.17 / 2.16	3 / 3	1.02 / 1.02	0.047 / 0.681
hybrid ( $\beta{\geq}0.9$ )	0.837 / 0.834	4.97 / 5.71	28 / 36	1.15 / 1.14	0.020 / 0.756

Table 8: Coupling ablations,

T=64

, paired design, 50 trials per cell, at

b=2^{-8}

2^{-16}

. Perplexity ratios are against each variant’s own decoder-matched reference.

$b$	greedy	coupled Gumbel
no noise	$+1.000$ / $+1.000$	$+0.999$ / $+1.000$
$2^{-4}$	$+0.281$ / $+0.260$	$+0.281$ / $+0.261$
$2^{-8}$	$+0.092$ / $+0.120$	$+0.058$ / $+0.109$
$2^{-16}$	$-0.003$ / $+0.006$ (n.s.)	$-0.017$ / $-0.007$ (n.s.)

Table 9: Forced-memorization membership advantage,

P(\text{emit}\mid\text{member})-P(\text{emit}\mid\text{non-member})

, for two C-COMMON canaries, 2,000 trials per cell. Standard error

\approx 0.022

, so the 95% interval is roughly

\pm 0.044

; “n.s.” marks an advantage whose interval contains zero.

$N$	accuracy	perplexity	gain vs. public (95% CI)	mean $\lambda$	headroom
8	0.2459	27.19	$+0.0021$ $[+0.0019,+0.0024]$	0.151	3.7%
16	0.2471	26.68	$+0.0033$ $[+0.0029,+0.0037]$	0.221	6.9%
32	0.2480	26.20	$+0.0042$ $[+0.0036,+0.0048]$	0.334	11.8%

Table 10: PMixED validation, unamplified (

q=1.0

) at

\varepsilon_{G}=2

T=1024

\alpha=2

E=10

. Public baseline: accuracy 0.2438, perplexity 27.75. Headroom is the share of that configuration’s own non-private ceiling — the plain average of all

N

experts with no privatization — that survives.

Figure 4: PAC versus PMixED at a matched membership-inference bound (

\varepsilon\approx 1

), on the same data universe and held-out test set. At every horizon, PMixED is evaluated over all combinations of shard count

N\in\{8,16,32\}

, subsampling rate

q

swept down to

10^{-4}

, and Rényi order

\alpha

, and the best-performing configuration subject to the privacy target is the one plotted; the selected configuration therefore varies along the curve, and is listed in Table 11 . (a) Raw next-token accuracy versus query horizon. Reference lines show the public baseline, the PAC-Gumbel non-private ceiling (0.3099), and the highest evaluated PMixED non-private ceiling (0.3021 at

N=8

). The PMixED configurations selected by the privacy-constrained search use

N=32

, whose non-private ceiling is 0.2793. PMixED approaches the public baseline as the horizon grows, whereas PAC-Gumbel remains close to its non-private ceiling. (b) The same results normalized by the non-private ceiling of the configuration selected at each point. Note the logarithmic vertical scale. Error bars are standard errors over 16 subsampling draws per cell and are smaller than the markers. Exact values and selected configurations are in Table 11 .

$T$	$b$ (nats)	acc.	head. (%)	acc.	$N$	$\alpha$	$q$	$f_{\emptyset}$	$\bar{\lambda}$	head. (%)	acc.	$N$	$\alpha$	$q$	$f_{\emptyset}$	$\bar{\lambda}$	head. (%)
		PAC-Gumbel		PMixED (rigorous)							PMixED (generous)
$10^{2}$	$1.11\times 10^{-3}$	0.3089	98.4	0.25550	32	16	0.02	0.524	0.626	$33.0\pm 0.8$	0.26355	32	2	0.05	0.190	0.927	$55.7\pm 0.3$
$10^{3}$	$1.11\times 10^{-4}$	0.3086	98.0	0.25205	32	32	0.01	0.728	0.743	$23.3\pm 0.7$	0.25691	32	2	0.03	0.373	0.887	$37.0\pm 0.5$
$10^{4}$	$1.11\times 10^{-5}$	0.3086	98.1	0.24695	32	64	0.005	0.856	0.685	$8.9\pm 0.3$	0.25062	32	2	0.02	0.525	0.767	$19.3\pm 0.3$
$10^{5}$	$1.11\times 10^{-6}$	0.3086	98.0	0.24482	32	64	0.001	0.971	0.970	$2.9\pm 0.3$	0.24648	32	2	0.01	0.724	0.649	$7.6\pm 0.2$
$10^{6}$	$1.11\times 10^{-7}$	0.3086	98.0	0.24413	32	64	0.0005	0.984	0.773	$0.9\pm 0.2$	0.24487	32	2	0.005	0.850	0.483	$3.0\pm 0.1$

Table 11: Exact values for the matched comparison of Figure 4 (

\varepsilon\approx 1

). Accuracies are next-token accuracy on the held-out test positions; headroom is the share of the selected configuration’s own non-private ceiling that survives privatization. PMixED columns give the configuration chosen by its own search at that operating point. Uncertainties are standard errors over 16 subsampling draws.

Appendix figures & tables1 asset

Supplementary material from the paper’s appendix.

Appendix

$T$	$b$ (nats)	acc.	head. (%)	acc.	$N$	$\alpha$	$q$	$f_{\emptyset}$	$\bar{\lambda}$	head. (%)	acc.	$N$	$\alpha$	$q$	$f_{\emptyset}$	$\bar{\lambda}$	head. (%)
		PAC-Gumbel		PMixED (rigorous)							PMixED (generous)
$10^{2}$	$3.28\times 10^{-3}$	0.3092	99.0	0.25668	32	8	0.03	0.375	0.649	$36.3\pm 0.8$	0.26520	16	2	0.1	0.185	0.853	$44.9\pm 0.3$
$10^{3}$	$3.28\times 10^{-4}$	0.3087	98.2	0.25366	32	64	0.02	0.527	0.514	$27.8\pm 0.7$	0.25879	32	2	0.03	0.373	0.917	$42.3\pm 0.5$
$10^{4}$	$3.28\times 10^{-5}$	0.3086	98.0	0.24845	32	32	0.005	0.848	0.870	$13.1\pm 0.6$	0.25233	32	2	0.02	0.525	0.840	$24.1\pm 0.3$
$10^{5}$	$3.28\times 10^{-6}$	0.3086	98.1	0.24559	32	64	0.002	0.939	0.880	$5.1\pm 0.4$	0.24730	32	2	0.01	0.724	0.762	$9.9\pm 0.3$
$10^{6}$	$3.28\times 10^{-7}$	0.3086	98.0	0.24433	32	32	0.0005	0.985	0.984	$1.5\pm 0.3$	0.24526	32	2	0.005	0.850	0.620	$4.1\pm 0.2$

Appendix

Table 12: The same comparison at the looser operating point, a membership-inference bound of

0.8808

(

\varepsilon=2.0

, total PAC budget

0.328

nats). Columns are as in Table 11 .

Privacy-Preserving Language Models

Privacy-preserving language models protect sensitive data during training, inference, personalization, and information sharing.

See all 177 papers

May 7, 2026

PACZero: PAC-Private Fine-Tuning of Language Models via Sign Quantization

We introduce PACZero, a family of PAC-private zeroth-order mechanisms for fine-tuning large language models that delivers usable utility at

I(S^*; Y_{1:T})=0

. This privacy regime bounds the membership-inference attack (MIA) posterior success rate at the prior, an MIA-resistance level the DP framework matches only at

\varepsilon=0

and infinite noise. All DP-ZO comparisons below are matched at the MIA posterior level. The key insight is that PAC Privacy charges mutual information only when the release depends on which candidate subset is the secret. Sign-quantizing subset-aggregated zeroth-order gradients creates frequent unanimity, steps at which every candidate subset agrees on the update direction; at these steps the released sign costs zero conditional mutual information. We propose two variants that span the privacy-utility trade-off: PACZero-MI (budgeted MI via exact calibration on the binary release) and PACZero-ZPL (

I=0

via a uniform coin flip on disagreement steps). We evaluate on SST-2 and SQuAD with OPT-1.3B and OPT-6.7B in both LoRA and full-parameter tracks. On SST-2 OPT-1.3B full fine-tuning at

I=0

, PACZero-ZPL reaches

{88.99\pm0.91}

, within

2.1

pp of the non-private MeZO baseline (

91.1

FT). No prior method produces usable utility in the high-privacy regime

\varepsilon<1

, and PACZero-ZPL obtains competitive SST-2 accuracy and nontrivial SQuAD F1 across OPT-1.3B and OPT-6.7B at

I=0

Murat Bilgehan Ertan, Xiaochen Zhu, Phuong Ha Nguyen +2

CWI Amsterdam · ∗Affiliated with Vrije Universiteit Amsterdam. · MIT +1

Privacy-Preserving Language Models LLM Fine-Tuning

Ask PDF

Sep 27, 2026

Decoupling Token Roles in Autoregressive Pretraining

Autoregressive pretraining increasingly draws on heterogeneous data, making it important to understand how a model learns from an individual token. The next-token prediction objective naturally identifies a token's contribution with its own loss. However, each token is not only a prediction target but also context for what follows. Using controlled corruption, we decouple these two roles and find a reversal: making a noisy token easier to predict reduces its damage as a target but increases it as context. The same decoupling helps explain text generated by language models: generation selects each token by its fit to the prefix, while its role as context is never tested against an independently determined continuation, because that continuation is generated to fit it. At known corrupted positions, acting through the context can reduce damage that removing the token's own loss does not. Understanding and controlling what a model learns from a token therefore requires decoupling its roles.

Suqin Yuan, Runqi Lin, Kevin Qinghong Lin +4

University of Sydney · University of Oxford · Southeast University

Language Model Pretraining Autoregressive Language Modeling Causal Interventions in Language Models Language Model Robustness Autoregressive Transformer Sequence Prediction

Ask PDF

Apr 9, 2026

Differentially Private Language Generation and Identification in the Limit

We initiate the study of language generation in the limit, a model recently introduced by Kleinberg and Mullainathan [KM24], under the constraint of differential privacy. We consider the continual release model, where a generator must eventually output a stream of valid strings while protecting the privacy of the entire input sequence. Our first main result is that for countable collections of languages, privacy comes at no qualitative cost: we provide an

\varepsilon

-differentially-private algorithm that generates in the limit from any countable collection. This stands in contrast to many learning settings where privacy renders learnability impossible. However, privacy does impose a quantitative cost: there are finite collections of size

k

for which uniform private generation requires

Ω(k/\varepsilon)

samples, whereas just one sample suffices non-privately. We then turn to the harder problem of language identification in the limit. Here, we show that privacy creates fundamental barriers. We prove that no

\varepsilon

-DP algorithm can identify a collection containing two languages with an infinite intersection and a finite set difference, a condition far stronger than the classical non-private characterization of identification. Next, we turn to the stochastic setting where the sample strings are sampled i.i.d. from a distribution (instead of being generated by an adversary). Here, we show that private identification is possible if and only if the collection is identifiable in the adversarial model. Together, our results establish new dimensions along which generation and identification differ and, for identification, a separation between adversarial and stochastic settings induced by privacy constraints.

Anay Mehrotra, Grigoris Velegkas, Xifan Yu +1

Stanford University · Google Research · Yale University

Text Generation Differential Privacy

Ask PDF

Abstract

Privacy-Preserving Language Models

Explore similar work

PACZero: PAC-Private Fine-Tuning of Language Models via Sign Quantization

Decoupling Token Roles in Autoregressive Pretraining

Differentially Private Language Generation and Identification in the Limit