Plausible Token Amplification for Improving Accuracy of Differentially Private In-Context Learning Based on Implicit Bayesian Inference
Authors: Yusuke Yamasaki
Kenta Niwa
Daiki Chijiwa
Takumi Fukami
Takayuki Miura
Venue: ICML 2025 poster (2025)
Keywords: in-context learning
differential privacy
large language models
Primary area: social_aspects->privacy
TL;DR: We propose Plausible Token Amplification (PTA), the first theoretically grounded method to improve the accuracy of DP-ICL by highlighting the task-relevant tokens.

Abstract: We propose Plausible Token Amplification (PTA) to improve the accuracy of Differentially Private In-Context Learning (DP-ICL) using DP synthetic demonstrations. While Tang et al. empirically improved the accuracy of DP-ICL by limiting vocabulary space during DP synthetic demonstration generation, its theoretical basis remains unexplored. By interpreting ICL as implicit Bayesian inference on a concept underlying demonstrations, we not only provide theoretical evidence supporting Tang et al.'s empirical method but also introduce PTA, a refined method for modifying next-token probability distribution. Through the modification, PTA highlights tokens that distinctly represent the ground-truth concept underlying the original demonstrations. As a result, generated DP synthetic demonstrations guide the Large Language Model to successfully infer the ground-truth concept, which improves the accuracy of DP-ICL. Experimental evaluations on both synthetic and real-world text-classification datasets validated the effectiveness of PTA.

Plausible Token Amplification for Improving Accuracy of Differentially Private In-Context Learning Based on Implicit Bayesian Inference
Yusuke Yamasaki
Kenta Niwa? Daiki Chijiwa?
Takumi Fukami
Takayuki Miura
Abstract
aligns the LLM's prediction for the query with the inferred concept accordingly, enabling accurate responses. Despite ICL's success across various tasks (Mathur et al. 2023
We propose Plausible Token Amplification (PTA P improve the accuracy of Differentially Private In-Context Learning (DP-ICL) using DP synthetic demonstrations. While Tang et al. pirically improved the accuracy of DP-ICL by limiting vocabulary space during DP synthetic demonstration generation, its theoretical basis re- mains unexplored. By interpreting ICL as im- plicit Bayesian inference on a concept underly- ing demonstrations, we not only provide theoret- ical evidence supporting Tang et al.'s empirical method but also introduce PTA, refined method for modifying next-token probability distribution. Through the modification, PTA highlights tokens that distinctly represent the ground-truth concept underlying the original demonstrations. As a re- sult, generated DP synthetic demonstrations guide the Large Language Model successfully infer the ground- ground-truth concept, which improves the ac- curacy of DP-ICL. Experimental evaluations on both synthetic and real-wor world text-classification datasets validated the effectiveness of PTA.
Hegselmann et al. 2023), embedding sensitive information in demonstrations, such as personal health records, risks leaking sensitive information from responses (Wang et al.) 2023a Duan al., 2023). This necessitates privacy-aware ICL methods that mitigate leakage risks while ensuring responses are aligned with the concept underlying demon- strations.
To mitigate leakage risks in ICL, Differential Privacy (DP) (Dwork et al.] 2006a), which offers privacy guarantees against leakage risks, has been incorporated into ICL, often referred as DP-ICL (Tang al. 2024 Wu al. 2024 Hong et al. 2024). Notably, (Tang al. 2024) studied gen- erating synthetic demonstrations by adding variance-tuned noise to the next-token probability obtained from an LLM prompted with the original demonstrations. The added noise ensures that the generated synthetic demonstrations satisfy DP, reducing the leakage risks of the originals by providing these synthetic ones in the prompt. While increasing noise variance lowers leakage risks, it also makes the synthetic demonstrations deviate more from the originals, thereby degrading task accuracy. To recover the degraded accuracy, (Tang et al., 2024) empirically limited the vocabulary space using public information during noise addition. While nu- merical experiments showed its effectiveness in improving accuracy, its theoretical basis remains unexplored.
1. Introduction
Large Language Models (LLMs) exhibit an impressive ca- pability known as In-Context Learning (ICL) (Brown et al.] 2020), where a few pairs of data and their labels (demon- strations) and new data (query) are provided together as prompt. These demonstrations help LLM infer a concept- namely, latent rule that connects data to their labels which governs the token transitions in demonstrations. ICL
For further credibility in DP-ICL, begin with its theoret- ical analysis based on the Bayesian analysis (see Section B} inspired by existing work on standard ICL (without employ- ing DP) (Xie et al. 2022 Wang et al. 20236). which inter- prets ICL as implicit Bayesian inference on ground-truth concept underlying the original demonstrations. Extending this framework to DP-ICL, establish Theorem 2 explain- ing how the added noise to ensure DP affects the LLM's ability to infer the ground-truth concept. Specifically, we show that the LLM successfully infers the ground-truth con- cept if the expected divergence, which depends on the next- token probability distribution, surpasses a certain threshold. This divergence measures how much the distribution under the ground-truth concept differs from that under any other
'TTT Social Informatics Laboratories 2NTT Communi- cation Science Laboratories *NTT Computer and Data Sci- ence Laboratories. Correspondence to: Yusuke Yamasaki <yusuke. www.yyaammaat.ccom.o
Proceedings of the 4nnd International Conference on Machine Learning, Vancouver, Canada. PMLR 267, 2025. Copyright 2025 by the author(s).
'The code will be available at htttt:///ggtaate Yusuke- vaamaskiippt.

---

PTA for Improving Accuracy of DP-ICL Based on Implicit Bayesian Inference
concept, while the threshold reflects the negative impact of noise, primarily influenced by the noise variance and the vo- cabulary size. Hence, the added noise hinders the accurate inference of the ground-trute truth concept in DP-ICL, explaining why DP-ICI often suffers from accuracy degradation.
demonstrating improved accuracy DP-ICL benchmark tests.
2. Preliminaries
We first review existing DP-ICL methods in Section 2.1 Section presents a theoretical analysis of standard ICL (without employing DP).
To address this accuracy degradation, we derive two insights from our theory: (i) Reducing the vocabulary size lowers the noise-dependent threshold, providing theoretical support for Tang et al.'s empirical method of limiting vocabulary space. (ii) Increasing the divergence between concepts by employ- ing another next-token probability distribution that enlarges the gap between the ground-truth and any other concept. The second insight highlights& a promising approach for de- signing the next-token probability distribution to increase the divergence, while previous work only focused on (i).
2.1. DP-ICL
(e, d)-Dffferrll Privacy (DP) provides statistical privacy guarantees for datasets used in queries (formal definition is given in Appendix D Here, E (> 0) measures the max- imum allowable bound in outputs between neighboring datasets, while d E (0, 1) is the maximum failure proba- bility of exceeding the bound e. Smaller values of (e, 6) imply lower leakage risks of the used dataset. The Gaus- sian mechanism, widely used to achieve (c, 6)-DP, adds the independent noise that follows the Gaussian distribution N(0,, o²) to the output of the query. The Gaussian mech- anism satisfies (c, 6)D (Dwork & Roth 2014) when o² is chosen appropriately sensitivity - defined as the maximum change in the query outputs between neighboring datasets measured by || - 1/2-
Motivated by (ii), we propose Plausible Token Amplification (PTA) to increase the divergence between the ground-truth and any other concept by amplifying tokens that distinctly represent the ground-truth concept (see Section 4 Formally, PTA solves an optimization that maximizes this divergence while remaining close to the original next-token probabil- ity distribution, ensuring the contextual coherence of the resulting synthetic demonstrations. As result, PTA pre- serves alignment with the ground-truth concept, effectively recovering the degraded accuracy due to the added noise in DP-ICI.. Our key contributions are summarized as follows:
the basis of (E, (c, and the lz-
Integrating mechanisms to ensure DP into standard ICL (DP-ICI.) can be used to mitigate leakage risks from query responses. With smaller (c, 5) values, the LLM's responses are less likely to leak any individual demonstrations pro- vided in the prompt. To achieve this, generating DP syn- thetic demonstrations (Tang et al. 2024) is a particularly promising approach, when handling an unpredictable num- ber of queries, as noise variance remains stable regardless of the number of queries, due to DP's post-processing im- munity (Dwork et al. 2006b). For more on related methods, see (Edemacu & Wu
We introduce Bayesian analysis into DP-ICL and derive Theorem 2 re- vealing two key insights: (i) Reducing the vocabulary size mitigates the negative impact of noise on the ground-truth concept inference, theoretically supporting Tang et al. 's em- pirical method. (ii) Increasing the divergence between the ground-truth and any other concept helps guide the LLM to- ward accurate inference on the ground-truth concept. Since Tang et al.'s method does not fully exploit this second in- sight, our analysis implies that addressing this oversight can improve the accuracy of DP-ICL.
Bayesian analysis of DP-ICL (Section 3)
2025) and Appendix
Notably, (Tang et al. 2024 studied generating DP synthetic demonstrations by adding noise to next-token probability distribution instead of model parameters, ensuring flexibility across LLMS and datasets. Noise is added to the next-token probability distribution generated by the LLM in parallel, conditioned on a prompt that contains a task instruction and a disjoint subset of the original private demonstrations where each demonstration is formatted To improve accuracy, the vocabulary space is limited before noise addition, using public information such as the task instruction. Specifically, two types of prompts are used: Spub. which only includes the task instruction and the tokens generated thus far, and s(i) which additionally contains the i-th disjoint subset obtained by partitioning the original demonstrations Dpriv into M disjoint subsets. Spuh helps in limiting away irrelevant vocabularies, while Spriv provides specifie information. The token generation process satisfying DP is outlined as follows:
PTA for accurate DP-ICL. (Section 4 Motivated by our Theorem 2 we propose PTA to increase the divergence between the ground-truth and any other concept by high- lighting the distinctive tokens in the ground-truth concept. To achieve this, PTA compares next-token probability dis- tribution conditioned on private demonstrations and public information, ensuring additional leakage risks beyond Tang et al.'s method. Hence, PTA aligns generated DP syn- thetic demonstrations with the ground-truth concept while maintaining contextual coherence and improving the accu- racy of DP-ICL.
label-data pair.
We validated the effectiveness of PTA through experiments on synthetic and real-world cext-classffication tasks across various settings,
Experimental validations (Section 5):
2

---

PTA for Improving Accuracy of DP-ICL Based on Implicit Bayesian Inference
Prompt concept (e.g. Name to Nationality)
Bayesian analysis (Xie et al.. 2022 Wang et al. 2023b
Ling et al.) 2024 Reizinger al. 2024.. From a Bayesian perspective, ICL infers concepts underlying the demonstra- tions provided in a prompt, guiding the LLM to generate tokens aligned with the inferred concept. To clarify the mechanism of this implicit Bayesian inference, we briefly review the problem setting and key results from (Xie et al., 2022), which offers fundamental theoretical insights into the implicit Bayesian inference in ICL.
Transition Probability pihte f1gg 0*)
Emission Probability ICL plouy| hma)
Einstein
was
German
Emission Probabillty in DP-CLL Pors Pagl G. 4d o'
Einstein
America
Problem setting in (Xie et al. 2022) Token generation in
LLMs is modeled using a Hidden Markov Model (HMM), as depicted in Figure | Figure | |chematically illustrates how an HMM governs the token transitions where each token is emitted on the basis of a corresponding hidden state. In this model, each demonstration token oL is emitted from a hidden state he.5 in accordance with the emission probability p(o.. [b which is independent of the shared concept (t..,,hh.,11,00 f*)
Figure 1: Illustaation of HMM-based model for ICL intro- duced in (Xie et al. 2022) and the proposed one for DP-ICL introduced in this paper. The red arrows highlight the new dependencies, showing how the generated tokens in DP-ICL are influenced by noise added to ensure DP.
V puub = arg max Σ p(o = u/ Spubb)) s.t. Ppubl=kk (1) VCCV
0- In contrast, the transition probability depends on 0 (e.g.. linking a name to its nationality).
V
1 M Σ M
On the basis of this framework, (Xie et al. 2022) construct a prompt by concatenating n independent demonstrations that follow HMM where each is separated by a delimiter token and then appending a query Zquery. Formally, we represent the prompt distribution as follows:
Pu
) Po Pa/l <Dww),
pw)), (2)
Uyn arg aaaggaa max fio + Cohi So ~ NN 2002; VEV
(3)
where V is the LLM's token vocabulary, ofLM is random variable such that p(o"IM = v) represents the next-token probability of the LLM, and k S [V] is the number of the vocabulary selected. 4 limits the vocabulary space to a subset Vpub on the basis of public information Spub. filtering out low-likelihood tokens. In 2 token probabilities con- priv are averaged
[S,, Iquary] = ofellim ....,.,.......... On, delim Fquary] ~ Pprompt
where S, denotes the concatenation of the n demonstra- tions Oz,..., On and dfelim is a delimiter token. Each demonstration is independently generated in accordance with the shared concept H", ensuring the transition probabil- ity p(hs.,) / 1, 0*) remains consistent across all demon- strations while the j-th token of the i-th demonstration o.j is sampled from V on the basis of its emission probabil- ity /(o,,) The formal prompt formulation using the HMM, for a structured framework analyze token depen- dencies in ICL, is provided in Appendix C
ditioned on private prompts S!T)
priv..... S ((M)
and normalized within Vpab. Finally, ( adds noise to these
probability distributions to ensure (E, -D,, then yielding the synthetic token Usyn- The generated tokens are appended to both prompts Spub and Spriv. recursively constructing DP synthetic demonstration. Empirical results showed that limiting the vocabulary space improved the stability and the accuracy of DP-ICL.
Interpretation of ICL as implicit Bayesian inference. To analyze the next-token probability of an LLM conditioned on the prompt Sn, Tquery. we apply Bayes's rule and trans- form it as follows:
Tang et al.'s DP-ICL faces two main challenges. First, their method of limiting the vocabulary space has only been em- pirically evaluated, lacking theoretical evidence on its abil- ity to improve the accuracy while satisfying DP. Secondly, limiting vocabulary space to Vpuh may lead to degrading accuracy degrading particularly when |( deviates from p(( ((O) ). as Ypub may include the low-likelihood tokens conditioned on priv and the generated demonstration including them due to the added noise.
P(y|Sn F'query) ) p(y) Sn, Tquery, 0)p((1) Equeryy dd
x ppulss Equary, 0) pb Tquery| (8)
p(S Tquery (+)) p (0)dO. d0O
the posterior (0)S,, Figuery) concentrates on the ground- truth concept 0" underlying the demonstrations, the LLM will generate tokens that align closely with 0*, To evaluate how closely p(0)S (query) concentrates on 0*, the follow- ing quantity is introduced:
If
s(i)
2.2. Bayesian analysis of ICL
Limited to standard ICL (without employing DP), its ac- curacy has been theoretically investigated on the basis of
T' (0) = _ -log p(Sn. Equery| (0)
(4)
p(S,, Equery| 0')
3

---

PTA for Improving Accuracy of DP-ICL Based on Implicit Bayesian Inference
where rn (0) represents the average log-likelihood ratio of the prompt, comparing the likelihood conditioned on any other concept 0 E O and the ground-truth concept 0*, letting @ be a set of concepts. By using T' (0), the likelihood ratio : (oteeeyy))pppppn----mp (0") can be expressed as exp (n Tr, (0)). If (0) (0) converges to a negative constant for 0 + thenn exp (n Ta (0) + as n increases, while when 9 6* This convergence of r0) indicates that the posterior probability p(0) Sn, Tqquery will increasingly favor the ground-truth concept 0* over any other concept, as more demonstrations are provided in the prompt. In (Xie et al., (2022). a the condition for the convergence of rm (0) is theoretically analyzed under certain assumptions on HMM used in the prompt formulation. Due to space limitations, we provide a formal description of Assumptions 4 used in (Xie et al. 2022 in Appendix [
3. Bayesian analysis of DP-ICL
In this section, we theoretically explore DP-ICL (Tagg et al. 2024) on the basis of implicit Bayesian inference. Follow- ing the methodology in (Xie et al. (022) outlined in Section 2.2 our analysis focuses on how adding noise negatively impacts the LLM's ability to infer the ground-truth concept 0 underlying the demonstrations. First, we introduce (i) the modeling of the DP synthetic prompt distribution, par- ticularly the noise addition mechanism in (3), while setting aside factors like vocabulary space limitation [ and nor- malization ( This simplification allows us more clearly analyze how adding noise impacts implicit Bayesian infer- ence on concepts. We then proceed to assess (ii) the effects of vocabulary space limitation and normalization.
exp (n- (0))
(i) Modeling DP synthetic prompt distribution. To ana- lyze the negative impact of noise addition, we extend the HMM-based model presented in Appendix[[tr model the DP synthetic prompt distribution. We incorporate noise addition into the model:
Under these assumptions, (Xie et al. 2022) provide a key condition ensuring that the posterior distribution concen- trates on 0* as the number of demonstrations grows, i.e. limn-+ac exp (n - Tn (0)) = 0. Below, we restate their The- orem 1 in a transformed form for consistent expression in this paper; the full original statement and the derivation of transformation appear in Appendix C
Oa p(o.. (hrg) == p(on, has) Sid
(6)
where G. ~ NO, of (In) represents [Vl-dimensional inde- pendently and identically distributed (IID) Gaussian noise. Our HMM formulations involve the modification solely on the emission probability compared to those in (Xie et al., 2022). as shown in Figure ! Note that adding IID Gaussian noise to each token's emission probability is consistent with the standard method for adding Gaussian noise to the next- token probability for generating DP synthetic demonstration as discussed in Section 2.1 While the noise perturbs the output probability of token sequences to ensure DP, the hidden states transition will remain aligned with the ground- truth concept 0 underlying the original demonstrations, as shown in Figure
Theorem (Distinguishability of the prompt concept (iie
et al. 2022 Suppose Assumptions 2 and 4 in Ap- pendix Chold. Then, we have lim,n-oe exple nn Tn (0)) = O,
if is the ground-trute concept of the prompt and satisfies
the following condition for any other concept E A:
p(O log
EO-ppnnge p(0]0)
> Cdelii
(5)
where Perompt and p represent the prompt distribution and pre-training distribution, respectively. The expectation is taken over O ~ Ppromp- Cdelim is a bounded positive value that depends on O and 0*.
Next, we examine how closely the concept inferred from the DP synthetic prompt aligns with the ground-truth concept 0*. To do this, we define the quantity, analogous to
1 log p(5,., Equery (8) F, (0) == n p(S,, Jquery (0))
Left-Hand Side (LHS) in (5) measures how much the distri- bution under 0" deviates from that under any other concept 9, while Cuelii accounts for the extra complexity introduced by delimiter tokens in the prompt. According to Theorem | if this divergence exceeds Cdelimm the L.M accurately infers the ground-truth concept 0", enabling Bayes-optimal predic- tions for queries (Xie et al., (022). Consequently, designing demonstrations that yield substantial divergence between (O100)) and p(O(0) surpassing dellim is an effective way to improve the accuracy of ICI..
where S, represents the DP synthetic prompt comprising DP synthetic demonstrations, This measure assesses how the noise addition affects the inference of the ground-truth concept compared to any other concepts. Intuitively, a larger noise variance o² can hinder the accurate inference of the ground-truth concept 0" because the noise may increase the likelihood conditioned the numerator of 7 while decreasing the likelihood con- ditioned on the ground-truth concept 0*. To assess 77. assumptions used in (Xie et al.) (022) are applicable. As- sociated with 7, (0), we derive the following lemma, as a DP-ICL counterpart to Lemma 8 in (Xie et al. 2022):
any other concepts A * 8 in
In the next section, we extend this theoretical foundation to investigate DP-ICL, incorporating modifications to account for the noise added to ensure DP.

---

PTA for Improving Accuracy of DP-ICL Based on Implicit Bayesian Inference
Lemma 1. Suppose Assumptions 2 and 4 Ahold. Then, we then have
adjust the vocabulary size [ Reducing the vocabulary size helps minimize the noise error, since the noise-dependent term G(a), which quantifies the deviation between Pprompe and Perocupt when o > 0, is primarily influenced by [V]. This helps LLM accurately infer the ground-truth concept, leading to a more accurate DP-ICL, This insight partially supports the empirical success of limiting the vocabulary space using publicly available information used in (Tang) et al. 2024). suggesting that Tang et al.'s empirical method is broadly correct. However, the derived condition still over- looks the combined effects of vocabulary space limitation I and normalization (2) on the divergence term in LHS. Therefore, Theorem 2 needs to be further refined to bet- ter align with the baseline DP-ICL practice in (TTng et al.) 2024
p(O, )0))
(0) S
log
+ Cdelimn + O(nn)) ))
(8)
p(O,10)
where Cdeeim is a bounded positive value that depends on 0 and 0*.
The proof is provided in Appendix C utilizing the factoriza- tion of the complex prompt S, into the individual demon- strations O2 on the basis of our HMM-based prompt for- mulation presented in (Ta)- (1dd) and (6) in Appendix C Following the proof strategy in Theorem we aim to clarify the condition ensuring that i', (0) converges to negative
constant as n increases, signifying accurate inference of the ground-truth concept 0"
(ii) Effects of vocabulary space limitation and normaliza- tion. To analyze the effects of vocabulary space limitation | and normalization the log-likelihood ratio of demonstrations, which quantifies the divergence between the ground -tuuh and any other con- cept, as represented in the LHS of Theorem [ Consider a scenario where irrelevant tokens are wrongly included and emphasized through ① 3 Then, generated tokens would be less aligned with the ground-truth concept. This mis- alignment significantly decreases the divergence between the ground-truth and any other concept, thus hindering the accurate inference of the ground truth concept. To illustrate this, we reformulate the LHS of Theorem 2 as follows:
To derive the condition for the convergence of (0), we focus on the first term in (8), which represents the average
Q we reformulate the expectation of
log- aigllikllhhodd ratio of DP synthetic demonstrations. By
reformulating this term to isolate two additional terms: (i) noise error and (ii) estimation error in DP-ICL, while pre- serving as many terms appearing in Theorem ! as possible, the following theorem is derived.
Theorem 2 (Distinuuishabiliy of the prompt concept on
DP-ICL), Suppose Assumptions 2 and f in Appendix hold. Then, we have lom exp (n- F., (0) = 0 with (1
()))-')) 7,'' (0,1) probability, if 0* is the underlying concept of the prompt and satisfies the following condition
for any other competing concept 0 O:
p(0 p(0
log p(O 1 x00)) p(0=0
log p(0 p(O00)
Ro log
Perompu (amomp((0=)) (0=v)
BOr-Pronn
Cudelin + C
DE
Token probability sampled from all vocabolary space
Token likelihood ratio
2 min (7,
+9 G()) log MI) +
T
log
(9)
Since vocabulary space limitation can be reflected by alter- ing V to its subset Vpab determined using publicly available information, the probability distribution computed over the limited vocabulary space is given by Pprompt, and the LHS
n
Noise error
Extimation evror
where T is the length of each demonstration, G(o) E [0. is continuous function of noise variance o² such that the LLM's next-token
of Theorem 2
can be expressed by
limo-0 G(o) 0, and depends probability distribution. Cdelio and C are bounded positive values that depend on 0 and gr.
Prrompe (amump(0=1) (0=v) log p(0-
(10)
p p(0=u10)
#r E pab
Normalized token probability
sampled from limited vocabulary space
The detailed proof and formal statement is provided in Ap- pendix C and here we offer an interpretation of Theorem 2 We consider that Theorem 2 is a natural extension of The- orem [ since the threshold in the Right-Hand Side (RHS) introduces additional noise and estimation errors in the ac- curate inference of the -ooun concept while LHS represents the divergence between p(O)0*) and (()))) the same as in Theorem D Both Theorems I and 2 almmst con- verge in the noise-free setting except for Ć as the noise and the estimation errors vanish when a - 0 and n + co, respectively. To mitigate the impact of these terms, we can
From 10), we observe that the obtained probability distribu- tion does not prioritize maximizing the LHS of Theorem 2 for a given vocabulary set Vpuuh. it ignores the likelihood ratio term in (TO). We consider Tang et al.'s method subop- timally modifying the next-token probability distribution, leading to a decreased LHS value of Theorem and failing to fully capitalize on the reduction of the noise error benefits of limiting vocabulary space.
In the following section, we propose a method to modify next-token probability aiming to maximize the LHS of The-
orem 2
5

---

PTA for Improving Accuracy of DP-ICL Based on Implicit Bayesian Inference
4. Proposed method
Algorithm 1 PTA for DP synthetic demonstrations
Input: instruction. pive. y. T, M. N, k. p.o, a.
We propose Plausible Token Amplification (PTA) to maxi- mize the divergence between the generated demonstrations under the ground-truth concept and any other concept, as formalized in (10). by modifying next-token probability dis-
Subroutine: Algorithm 2 Algorithm B
I: Initialize: Set O +
2: for j = 1 to T do
3: Spub, s(1)
S(M)
tribution. PTA aligns generated demonstrations with the ground-truth concept while maintaining their natural flow.
priv
f GenProoppi (D priv. M, N, J. Õ)
Section 4.1 outlines the problem motivating PTA, and Sec- tion details its derivation as the solution.
4:
for i = 1 to M do
p p =o| p m
( a
5:
Pe t p(o v10)
p(oLLM= Sppb)
4.1. Problem formulation
6:
Po pb") / EEwEv
(1)
7:
end for
Based on insights from Section 3 our objective is to enable
p. fo--- T3 ΣM (pt" + (0, 20²)}
8:
an LLM to accurately infer the ground concept from the generated demonstrations. To achieve this, we want to modify the next-token probability so that maximizes the divergence between p(O(0") and p(O(0) computed over the limited vocabulary space. However, if we focus solely maximizing this divergence, the modified next-token prob- ability may ignore natural token transitions. This leads to abrupt changes in token transitions that degrade the like- lihood of the overall generated sequence and hinders the
9: Ppub t VocabSpaceLimit (V, k. P. p(d
(p. 0}
10: Uynn = -arg max Ewerp max 00
"EVinn
11: Ô + Ô + (1/yyl
12: end for
13: return Ô
tion LLM on the concept underlying them as a result of an implicit Bayesian inference of ICL (Xie et al. 2022).
LLM's ability to accurately infer the ground -round-truth truth concept.
To address this, we introduce regularization that keeps the modified distribution close to baseline probability, which reflects the natural flow of tokens already generated. Specifically, for the j-th token, we formulate the following optimization problem to find probability distribution ş := (Fo)veyus over the limited vocabulary space Ypun:
However, using demonstrations for any other concepts in- curs additional privacy costs. For example, in a document classification task, accurately estimating the log-likelihood ratio requires evaluating combinations of concepts (0*, 0). If demonstrations for any other concepts @ & 8 involve private information, additional noise must be introduced to ensure DP, potentially degrading the accuracy of DP-ICI..
max Σ po log P(OLLM = x00') 1 p(ouL_-o(0 -KL (pllPomee) (11)
To address this, we propose PTA for solving 1II with- out incurring additional privacy costs. PTA uses public prompts-composed of task instructions and tokens already generated, excluding private demonstrations--ar substitutes for prompts representing any other concepts. Leveraging DP's post-procsssing immunity, public prompts incur no ad- ditional privacy costs when combined with generated tokens. This method enables the likelihood ratio to be estimated by comparing next-token probability distribution conditioned on private and public prompts:
VE Vio
where DKL. the Kullback-Leibler (KL) divergence mea- sures how much P. deviates from the baseline probability Pbase Pouse( = p(o (1..-1). The hyperparameter a con- trols how strongly we penalize divergence from this baseline probability Phuse. By incorporating the KI. term, we ensure that P. remain close to Pbase. preserving the natural transi- tion of tokens. Consequently, the resulting solution from (T) highlights tokens that distinetly represent the task while preserving the natural flow of demonstration.
v0 plo'M= Re log p - S log p(oLLM=0(0)
priv
(12)
4.2. Plausible Token Amplification (PTA)
p(oLLM = 1 Spat))
The objective function (T]) requires evaluating the diver- gence between p(O)0*) and p(O)O). Since computing this divergence depends on both the ground-truth concept 0r and any other concept 0 that are not observable, [T]) is in- tractable to solve directly. Instead, practical alternative would be estimating the target divergence comparing like- lihood conditioned on the concepts H" and f by prompting the LLM with demonstrations that are closely aligned with these concepts, as using such demonstrations will condi-
Since the likelihood ratio on the LHS of 12) are intractable to compute, the estimation on the RHS of (2) relies on
the tractable next-token probability distribution conditioned
observable private prompt s(3) for the ground-truth concept and comparing them to an observable public prompt. This estimation effectively highlights the distinctive tokens without incurring additional privacy costs. The rationale and implication of having this estimation are further discussed in Appendix
6

---

PTA for Improving Accuracy of DP-ICL Based on Implicit Bayesian Inference
By leveraging the estimated likelihood, PTA modifies the next-token probability distribution as follows:
classification of Wikipedia articles) (Zhang et al. 2013), and TREC (6-way question classification) (Voorhees & Tice 2000). Specifically, GINC is designed to align with the prompt setting in Section 2.2 enabling precise evaluation of the likelihood of generated DP synthetic demonstrations conditioned on specific concepts. This supports evaluating the theoretical condition in Lemma [ which underpin the theoretical foundation of the proposed PTA. Further details about the datasets available in Appendix H22
((() (((oLM) = -/ priv))
Pe XX Phuse @LLM
(13)
base probability
private to public rutio
The derivation of this modification, which solves .T. is deferred to Appendix E The public-to-private ratio ampli- fies tokens distinctive the ground-truth concept, while the baseline probability Paase (o' = v) ensures coherence by reflecting the natural flow of tokens already generated. This prevents excessive likelihood shifts and avoids disrupting fluency when tokens are more likely under the public prompt than the private prompt. Further, the pre-tuned Gaussian noise is added to the modified probability to ensure DP.
Models and DP synthetic demonstration generation. To generate DP synthetic demonstrations, we used three vari- ants of the pre-trained GPT-22 model (Radford et al. 2018) with (MA1) 4-layer, (MA2) 12-layer, and (MA3) 16-layer. For the other text-classification tasks, we utilized three mod- els: (MB1) Llama2-7B-GPTQ. (MB2) Llama2-7B (Touvron et al.
2023). and (MB3) Mistral-7B (Jiang et al. 2023)).
The algorithm implementation of PTA is detailed in Algo- rithm I Subroutines used in Algorithm I are presented in Algorithms 2 generation step, the public prompt S pub and multiple private prompts Spriv are generated in Line 3 The next-token proba- bility distributions are then modified using PTA, as detailed in Line 7 to highlight tokens that distinctly represent the task. To ensure DP, the Gaussian mechanism is applied to the modified probability distribution, described in Line [8] Finally, fixed and adaptive thresholds dynamically limit the vocabulary space, as implemented in Line 9 to filter out low-likelihood tokens and stabilize performance. This iter- ative process continues until the generated demonstrations reach the maximum sequence length T.
Using these models, we generated four DP synthetic demon- strations per task without replacement from the set of possi- ble labels in the task. The next-token probabilities required for generating these demonstrations were obtained using a text ageneration-infereen next-token probabilities were computed over a vocabulary size of [V] 150, following (Xie et al. 2022), whereas for other text-classification tasks, | = 32, 000 was used. To ensure a fair comparison, we adopted the same prompt for- mat as (Tang et al. 2024). Further details on the pre-training of the GPT-2 model for GINC and the prompt format are provided in Appendices F3 and F.9
and 3 in Appendix E During each token
platform For the GINC dataset,
DP parameters. To evaluate robustness across differ- ent DP settings, we set s 21, 4, 8, oo} with a fixed 8 = 1/ [Dpul. The Gaussian noise variance o² was de- termined by using a numerical method (Gopi et al. (022)) implemented with the authors' code"] as detailed in Ap- pendix D For E = oo, to show the accuracy of ICL without using DP, the original private demonstrations were randomly sampled from the private dataset.
The DP guarantee associated with Algorithm is identi- cal to that described by (Tang et al. 2024) when the noise variance o² is equivalent, indicating that the empirical pri- vacy leakage is mitigated similarly to Tang et al.'s 's method. Although details are presented in Appendix [ this equiv- alence arises because both algorithms apply the Gaussian mechanism to next-token probabilities, which are projected onto probability simplex (i.e. these fz-sensitivity is v2). PTA defined in (13), unique to this work, leverages public prompts, avoiding an increase in Ez-sensitivity or the need for additional noise. Moreover, the other algorithmic com- ponents are identical, enabling the privacy guarantee to be computed using the same numerical approach as outlined by (Gopi et al. 202T) and adopted by (Tang et al. 2024).
Comparing methods. We summarize the compared meth- ods and their key features in Table T Our primary focus is on comparing the baseline method (B 1) (Tang et al.) 2024) with our proposed (P1) PTA. Additionally, we conducted an ablation study to examine the impact of individual features. (PA2) and (BA2) were designed to assess the impact of the adaptive threshold for limiting the vocabulary space, which balances token diversity and plausibility. Further, (PA33 was introduced to evaluate the role of the regularization term in which aims to enhance natural token flow. We also
5. Experiments
5.1. Experimental setups
TTang et al. 2024) used OpenAl's ' API to obtain next-token probabilities; however, the current API limits predictions to the top 20 tokens. To address this limitation, we used text- -eneraenrtt inference, which allows access to full token spaces. thttps:/ / thub. com mi crosoft/prt ft/prv_
Datasets. We evaluated the proposed PTA against the method by (Tang et al.) 2024) using one synthetic classifica- tion task, GINC, introduced by (Xie et al.) 2022). and three real-world text-llassification tasks: AGNews (4-way news classification) (Zhang et al., 2015), DBPedia (multi-class
accountant
7

---

PTA for Improving Accuracy of DP-ICL Based on Implicit Bayesian Inference
Table I: Comparison of methods and key features. Ampli- fication represents whether the estimates of log-likelihood ratio in [2] are used, Base prob. represents whether base probability in (3) is applied, and Top-p represents Line 2
Table 3: Proportion of generated DP synthetic demon- strations for GINC, using model (MA3), where the log- likelihood ratio exceeds the derived threshold, appearing in the RHS of Lemma
in Algorithm 2
(PI)
(PA2)
(PA3)
(BI)
(BA2)
Method
Amplification Base Prob. Top-p
49. 19.33
40.89
38.22
44.89
42.22
(RO) 4-shot ICL using Daiv
8
53.33
41.33
42.67
52.44
44.45
(B1) Baseline
(BA2) Baseline w. Top-p
Generated: Brinnin''
(P1) PTA
(B1)
W.o. (.o)
noise
(P1) w.o. noise
(PA2) PTA w. TTp-p
0.50
(PA3) PTA w.o. Base Prob.
0.25
Next token probability
Table 2: 4-shot DP-ICL accuracy across four datasets using the best-performing model: (MA3) for GINC and (MB3)
0.00
Prince
Queen
Labour
new
Prim
oconomy
prime former
Got
Prince Labour
new
Queen
foreign
fomeer Pime Got
economyy prime
for the other datasets, averaged over five different seeds.
(B1)
(
The highest accuracy is bolded, and the second-highest is
0.50
underlined. Full results are available in Table g
0.25
Method
GINC
AGNews
DBPedia
TREC
0.00
foreign
hew prime Malor llament Wild
directed ges
Prince new
prime Labour
Surss erop directed geg
(PI) 93.99 1.39
87.88
82.06=3.01
84. 44.8044..o
(PA2)
90.06
87.00+1.16
84.7223.54
84.72+2.50
Token
(PA3)
90. 14
83.2442.04
86.56_1.75
84.34+1.28
Figure 2: Next-token probabilities comparing (Top Left)
(BI)
90.80=2.79
83.74
85. 85.7221.44
83.5645.00
(BI) w.o. noise addition, (Top Right) (PI) w.o. noise addi-
(BA2)
89.3440.95
84.86
86, 1..18
81.00
tion, (Bottom Left) (B1), and (Bottom Right) (PI).
(PI)
96.61 1.40
86.4811.66 1.88. 67
$1.78:1.55
84.2412.33
(PA2)
1..15
84.1223.47 84.24
83.52+1.00
sampled correctly, even under larger noise variance (e.g.. AGNews with 1).
8
(PA3)
90.79+1.16
84.92+1.75
85.56_2.34
84.5411.99
(BI)
94.6340.65
83.62
24.40=2..9
82.6442.79
(BA2)
90.61+1.23
82.96
14.86
81.96+1.00
Distinguishability of generated demonstrations on GINC. To demonstrate the positive effect of PTA on accurate con- cept inference, we empirically evaluate the log- ligliikelhhood ratio log (p((0)))/p(OO)))))) appearing in Lemma using GINC. The unique controlled setup of GINC enables us to numerically compute the likelihood ratio, as shown in Appendix F.4 According to the theoretical results estab- lished in Lemma I and Theorem 2 larger value of the log- likelihood ratio indicates a more accurate inference of the ground-truth concept. To empirically validate this, we cal- culate the probability that Pr [RHS of (8) negative). This measure quantifies how much the proportion of the gen- erated DP synthetic demonstration helps in the successful inference on the ground-truth concept, since if RHS of (8) is negative, then the LLM accurately infers the ground-trute -ruth concept. As shown in Table 3 (P1) consistently achieves better values than the baselines. This result validates that PTA enlarges the divergence between p(0]0*) ) and p( p(0(0), enhancing LLM's ability to infer the ground-trui concept. The alignment of these empirical findings with the theoreti- cal results strongly supports PTA's effectiveness.
0
(RO) 99.02 09.0221.228
87.8211.29 22 87.38
82. #2.2441.70
include (RO) as a non-private reference that used the original private demonstrations. To ensure fair comparisons across all configurations, a comprehensive hyperparameter search was conducted, as detailed in Appendix F.5
5.2. Main results
Accuracy comparison. Table 2 presents the accuracy of
DP-ICL for selected configurations and privacy parameters 8 8= (1,8, oo) and the best-performing models (MA3) and (MB3). The full results, including additional configura- tions and privacy parameters, are provided in Appendix Particularly, (P1) consistently achieves superior accuracy to baselines 1B1, BA2), except in the DBPedia at ε = 1, thereby validating its effectiveness across diverse privacy parameters and datasets. However, on DBPedia at 1. (PA3) performs best. Since (PA3) amplifies the distinctive tokens but ignores the KL regularization term of [I] used in (P1), this result suggests that the KI. term may act as con- straint that limits useful adaptation to the target distribution in certain settings. Nevertheless, by effectively amplifying the distinctive tokens in the task before adding noise, (P1) and its variant ensure that the highest- probbbbitt tokens are
Demystifying example of the effect of PTA. We present a specific example of a next-token probability distribution to illustrate how PTA effectively amplifies the distinctive tokens conditioned on private demonstrations, as shown in
8

---

PTA for Improving Accuracy of DP-ICL Based on Implicit Bayesian Inference
Figure The top row in Figure 2 shows next-token proba- bility distribution computed by using 2 and (T3), while the bottom row shows the probability distribution after noise addition. Focusing on the tokens "Prince" and "foreign", (P1) correctly preserves the top-1 token "Prince" even after noise is added, maintaining task relevance. In contrast, (B1) fails to retain the top-1 token, instead selecting a token "for- eign" with a lower likelihood due to noise. This example highlights PTA'S robustness in retaining critical tokens un- der high noise, ensuring task accuracy. Other examples can be found in Appendix F8
References
Abadi, M., Chu, A., Goodfellow, I., McMahan, H. B., Mironov, I., Talwar, K., and Zhang, L. Deep learn- ing with differential privacy. In Proceedings of the 2016 ACM SIGSAC Conference on Computer and Communications Security, CCS '16, pp. 308-318, 2016. ISBN 978 9781450341394.
Amin, K., Bie, A., Kong, W., Kurakin, A., Ponomareva, N., Syed, U., Terzis, A.. and Vassilvitskii, S. Pri- vate prediction for large-scale synthetic text genera- tion. In Proceedings of Findings of the Association for Computational Linguistics: EMNLP 2024, pp. 7244- 7262, 2024. 2024. findiiniiii aaattps://aclaatoology.. org 4257
6. Conclusion
We proposed PTA, a novel method for generating DP synthetic demonstrations, which highlights tokens that distinetly represent ground-truth concepts underlying the original demonstrations. By interpreting ICI. implicit Bayesian inference, we not only theoretically demonstrate that limiting vocabulary space, empirically incorporated in (Tang et al. 2024), mitigates the negative impact of noise on concept inference but also introduced refined method for modifying next-token probabilities for accurate inference on the ground-truth concept. We integrate PTA with vocabu- lary space limitation to ensure that DP synthetic demonstra- tions remain aligned with ground-truth concepts. Numerical experiments demonstrated the effectiveness of PTA, show- ing accuracy improvements, particularly in high-privacy regimes (e.g., 8 = 1).
Balle, B. and Wang. Y.-X. Improving the Gaussian mech- anism for differential privacy: Analytical calibration and optimal denoising. In Proceedings of the 35th International Conference on Machine Learning, pp. 394- 403, 2018.
Balle, B., Barthe, G., and Gaboardi, M. Privacy amplifica- tion by subsampling: Tight analyses via couplings and divergences. In Proceedings of the 32nd Advances in Neural Information Processing Systems, 2018.
Beauchamp, M. the distribution of the convolution of N indepen- dent rectified Gaussian variables. Journal de la société française de statistique, 159 2018. URL http: /www numdam. org/item/ JSFS_ 2018 159 _8
On numerical computation for
Impact statement
This paper addresses the challenge of privacy-preserving machine learning, particularly for LLM applications. To safeguard individual data used as input to an LLM, we pro-
Bretagnolle, J. and Huber, C. Estimation des densités: risque minimax. Zeitschrift für Wahhrscheiniichkeittteeeeee und Verwandte Gebiete, 47 1979. ISSN 1432- 2064. doi: 10.10007/BF005352778. URL httt:ttps::/// /doi orq/10.1007/BB0055300
pose Plausible Token Amplification (PTA) for generating synthetic demonstrations that satisfy DP guarantees. By leveraging DP, our approach lowers the risk of an individual being inferred from an LLM's output, thereby offering rigor- ous privacy guarantees and fostering safer data collaboration. As with other DP-based methods, unintended leakage can arise without careful design of the accumulation of privacy parameters and pre- preeprocssiing steps (e.g. de-duplication of data). These potential risks are consistent with issues commonly encountered in broader DP applications. Never- theless, our work demonstrates that incorporating DP into LLM workflows can promote both privacy protection and fair, efficient data usage.
Brown, T., Mann, B., Ryder, N., Subbiah, M., Kaplan, J. D., Dhariwal, P., Neelakantan, A., Shyam, P., Sastry, G., Askell, A., Agarwal, S., Herrbert-Voss, A., Krueger, G., Henighan, T., Child, R., Ramesh, A., Ziegler, D., Wu, J., Winter, C., Hesse, C., Chen, M.. Sigler, E., Litwin, M., Gray, S., Chess, B., Clark, J., Berner, C., McCandlish, S., Radford, A., Sutskever, I., and Amodei, D. Language models are few-shot learners. In Proceedings of 34th Advances in Neural Information Processing Systems, 2020.
Acknowledgements
We thank Ayato Nakagawa for his engineering support in numerical experiments.
Dong, J., Roth, A., and Su, W. J. Gaussian differential privacy. Journal of the Royal Statistical Society: Series B (Statistical Methodology), 84(1):3-37 2022.

---

PTA for Improving Accuracy of DP-ICL Based on Implicit Bayesian Inference
Duan, H., Dziedzic, A., Yaghini, M., Papernot, N., and Boenisch, F. On the privacy risk of in-context learn- ing. In Proceedings of the 3rd Workshop on Trustworthy Natural Language Processing, 2023.
Advances in Neural Information Processing Systems, 2021. URL.ittpss//pperrvviee http://wwwwwww.fo.....ee forum? id GS-Exxx61
Hegselmann, S., Buendia, A., Lang, H., Agrawal, M., Jiang. X., and Sontag, D. Tabllm: Few-shot clas- sification of tabular data with large language models. In Proceedings of the 26th International Conference on Artificial Intelligence and Statistics, pp. 5549-5581. PMLR, 2023. URL http:ttttt:/ooeeeeeeseess mws.minssmmmmmm .mlr htmml
Durfee, D. and Rogers, R. M. Practical differentially private top-k selection with pay-what-you-get composition. In Proceedings of the 33rd Advances in Neural Information Processing Systems. 2019.
Dwork, C. and Lei, J. Differential privacy and robust statis- tics. In Proceedings of the Forty-First Annual ACM Symposium Theory of Computing, pp. 371-380, 2009.
press/
Hoeffding, W.
Probability Inequalities for sums of Bounded Random Variables, pp. Springer New York, 1994. URL https: //tp:/ 0ttp:/0000.0001110111.00///1 978 1 - 1-1-46666065-5-22
Dwork, C. and Roth, A. The algorithmic foundations of differential privacy. Found. Trends Theor. Comput. Sci, 9(3-4):211 1-0011102200 2014.
Hong. J., Wang, J. T., Zhang, LI, Li, B., and Wang, Z. DP-OPT: Make large language model your privacy- preserving prompt engineer. In Proceedings of the 12th International Conference on Learning Representations, 2024. URL htttps://openreview wwwparreviee.neeeeeeee net/ forum?
Dwork, C., Kenthapadi, K., McSherry, F., Mironov, I., and Naor, M. Our data, ourselves: Privacy via dis- tributed noise generation. In Advances in Cryptology EUROCRYPT 2006, pp. 486-503. Springer, 2006a.
id=If23IgsEP3
Dwork, C., McSherry, F., Nissim, K., and Smith, A. Cal- ibrating noise to sensitivity in private data analysis. In Theory of Cryptography, pp. 265-284, 2006b.
Jiang, A. Q., Sablayrolles, A., Mensch, A., Bamford, C., Chaplot, D. S., Casas, D. d. I., Bressand, F., Lengyel, G., Lample, G., Saulnier, L., et al. Mistral 7b. arXiv preprint arXiv:2310.06825, 2023.
Dwork, C., Naor, M., Reingold, O., Rothblum, G. N., and
Vadhan, S. On the complexity of differentially private data release: efficient algorithms and hardness results. In Proceedings of the 41st Annual ACM Symposium on Theory of Computing, STOC '09, pp. 381-39011 2009.
Li, X. L.,, Holtzman, A., Fried, D., Liang, P., Eisner, J., Hashimoto, T., Zettlemoyer, L., and Lewis, M. Con- trastive decoding: Open-ended text generation as opti- mization. In Proceedings of the 61st Annual Meeting of the Association for Computational Linguistics (Volume Long Papers), pp. 17286-123100 July 2023.
Dwork, C., Rothblum, G. N., and Vadhan, S. Boosting and differential privacy. In 2010 IEEE 51st Annual Symposium on Foundations of Computer Science, pp- 51-60, 2010.
Ling, C.,, Zhao, X., Cheng, W., Liu, Y., Sun, Y., Zhang, X., Oishi, M., Osaki, T., Matsuda, K., Ji, J.. Bai, G., Zhao, L., and Chen, H. Uncertainty quantification for in-context learning of large language models. In Proceedings of the 2024 Conference of the North American Chapter of the Association for Computational Linguistics: Human Language Technologies (Volume 1: Long Papers), pp. 3357-3370, 2024. URL http::: http:://ccaaaatooooooeo azg/2024. long 184/
Edemacu, K. and Wu, X. Privacy preserving prompt engi- neering: A survey, ACM Comput. Surv., 57(10), 2025. URL
Flemings, J. and Annavaram, M. Differentially pri- vate knowledge distillation via synthetic text genera- tion. In Proceedings of Findings of the Association for Computational Linguistics: ACL 2024, pp. 12957- 12968, August 2024.
Mathur, Y., Rangreji, S., Kapoor, R., Palavalli, M., Bertsch, A., and Gormley, M. SummQA at MEDIQA-chat 2023: In-context learning with GPT-4 for medical summarization. In Proceedings of the 5th Clinical Natural Language Processing Workshop, pp. 490-502, 2023. URL
Gao, F., Zhou, R., Wang, T., Shen, C., and Yang, J. Data-adaptive differentially private prompt synthesis for in-context learning. In Proceedings of the 13th International Conference on Learning Representations, 2025, URL htttpp://openneeveeeeeeeeeeeoeee id S id=sVNEWhaajC
C clinicalnlp- 1.55
Mattern, J., Jin, Z., Weggenmann, B., Schoelkopf, B., and Sachan, M. Differentially private language models for se- cure data sharing. In Proceedings of the 2022 Conference
Gopi, S., Lee, Y. T., and Wutschitz, L. Numerical compo- sition of differential privacy. In Proceedings of the 35th
10

---

PTA for Improving Accuracy of DP-ICL Based on Implicit Bayesian Inference
Empirical Methods in Natural Language Processing, 2022.
Wang, B., Chen, W., Pei, H., Xie, C., Kang, M., Zhang, C., Xu, C., Xiong, Z.., Dutta, R., Schaeffer, R., Truong, S. T. Arora, S., Mazeika, M., Hendrycks, D., Lin, Z. Cheng, Y., Koyejo, S., Song. D., and Li, B. De- codingtrust: A comprehensive assessment of trustwor- thiness in GPT models. In Proceedings of the 37th Conference on Neural Information Processing Systems Datasets and Benchmarks Track, 2023a. URL https 7/openrevi ew net forum? wttprr/mmmddkaaaaoooooooo
McSherry, and Talwar, K. Mechanism design via dif- ferential privacy. In 48th Annual IEEE Symposium on Foundations of Computer Science (7) pp. 94
103, 2007.
Mironov, I. Rényi differential privacy. In 2017 IEEE 30th Computer Security Foundations Symposium (CSF), pp. 263-275, 2017.
Wang. X., Zhu, W., Saxon, M., Steyvers, M., and Wang, W. Y. Large language models are latent variable models: Explaining and finding good demonstrations for in-context learning. In Proceedings of the 37th Conference on Neural Information Processing Systems, 2023b. i id-BGykwZEGt
Rabiner, I., A tutorial on hidden markov models and selected applications in speech recognition. Proceedings of the IEEE. 77(2):257-22) 1989.
Radford, A., Narasimhan, K., Salimans, T., and Sutskever, Improving language understanding by generative pre- training. Technical report, OpenAI, 2018.
net. forum?
Wilde, M. M. From classical to quantum shannon theory. arXiv preprint arXiv: 106. 1445, 2011.
Reizinger, P., Ujváry, S., Mészáros, A., Kerekes, A., Brendel, W., and Huszár, F. Position: Under- standing LLMs requires more than statistical gener- alization. In Proceedings of the 41st International Conference on Machine Learning, 2024. https //openreview net / forumm ? i d pVyOchhUBa
Wu, T., Panda, A., Wang. J. T., and Mittal, Privacy- preserving in-context learning for large language mod- els. In Proceedings of the 12th International Conference on Learning Representations, 2024. URL https:// openreview net b forum ? Pid--idx44 40P J71HV
Sason, I. and Verdú, S. -divergence inequalities. IEEE Transactions Information Theory, 62(11):5973-600 2016. doi: 10. 00.1009/T..2001626631.1
Xie, C., Lin, Z., Backurs, A., Gopi, S., Yu, D., Inan, H. A., Nori, H., Jiang, H., Zhang, H., Lee, Y. T., Li, B., and Yekhanin, S. Differentially private synthetic data via foundation model APIs 2: Text. In Proceedings of the 41st International Conference on Machine Learning, 2024. URL httpss://opeeeeeeeee net/forut id MM-Dllupggobb
Shi, W., Han, X., Lewis, M., Tsvetkov, Y., Zettlemoyer, L., and Yih, W.-t. Trusting your evidence: Hallucinate less with context-aware decoding. In Proceedings of the 2024 Conference of the North American Chapter of the Association for Computational Linguistics: Human Language Technologies (Volume 2: Short Papers), pp. 783-791, 2024.
Xie, S. M., Raghunathan, A., Liang, P., and Ma, T. An explanation of in-context learning as im- plicit bayesian inference. In Proceedings of the 10th International Conference on Learning Representations, 2022. URL htttps://opeereviieet http://www.ee/foorerreeo id SHcJJVCHHJUN
Tang, X., Shin, R., Inan, H. A., Manoel, A., Mireshghal- lah, F., Lin, Z., Gopi, S., Kulkarni, J., and Sim, R. in-context learning with differentially private few-shot generation. In Proceedings of the 12th International Conference on Learning Representations, 2024. URL /tttps://operrevieew net f id od-o2tt0pRno1
Xu, Z., Jiang, F., Niu, L., Jia, J., Lin, B. Y., and Poovendran, R. SafeDecoding: Defending against jailbreak attacks via safety-aware decoding. In Proceedings of the 62nd Annual Meeting of the Association for Computational Linguistics (Volume 1: Long Papers), pp. 5587-5605, 2024.
Touvron, H., Martin, L., Stone, K., Albert, P., Almahairi, A., Babaei, Y., Bashlykov, N., Batra, S., Bhargava, P., Bhos- ale, S., et al. Llama 2: Open foundation and fine-tuned chat models. arXiv preprint 2xXi:23077009288 2023.
Voorhees, E. M. and Tice, D. M. Building ques- tion answering test collection. In Proceedings of the 23rd Annual International ACM SIGIR Conference on Research and Development in Information Retrieval, pp. 200-207. ACM, 2000. URL htthhttp:::/ htttps://doi.ox//// 11 345577
Yue, X., Inan, H., Li, X., Kumar, G., McAnallen, J., Shajari, H., Sun, H., Levitan, D., and Sim, R. Synthetic text gen- eration with differential privacy: A simple and practical recipe. In Proceedings of the 61st Annual Meeting of the Association for Computational Linguistics (Volume Long Papers), pp. 1332- July 2023.
345577

---

PTA for Improving Accuracy of DP-ICL Based on Implicit Bayesian Inference
Zhang, X., Zhao, J., and LeCun, Y. Character-level convo- lutional networks for text classification. In Proceedings of the 29th Advances in Neural Information Processing Systems, 2015.
Zhao, Z., Wallace, E., Feng, S., Klein, D., and Singh, S. Cal- ibrate before use: Improving few-shot performance of lan- guage models. In Proceedings of the 38th International Conference on Machine Learning, pp. 12697-12706, 2021. URL http:tttss::poeeeediii. ngs ml m...prres/ #139/zhao2lc.hth
Zheng, L., Chiang, W.-L., Sheng, Y., Zhuang, S., Wu, Z. Yonghao Zhuang, Z. L., Li, Z., Li, D., Xing, E., Zhang, H., Gonzalez, J. E., and Stoica, Judging llm-as-a-judge with mt-bench and chat- bot arena. In Proceedings of the 37th Conference on Neural Information Processing Systems Datasets and Benchmarks Track, 2023. URL https://
12

---

PTA for Improving Accuracy of DP-ICL Based on Implicit Bayesian Inference
A. Limitations and future work
briefly discuss the limitations and future directions of this study.
First, the introduced HMM-based prompt formulation may not fully capture the auto-regressive nature of generating DP synthetic demonstrations, where generated tokens recursively serve input for next-token generation. The introduced HMMs overlook the effect of noise addition transitions the next hidden states. Addressing this could provide more realistic representation of the DP synthetic prompt generation process.
Second, our framework could support efforts to adaptively noise variance reduction by estimating the maximum changes in the next-token probability LLM for individual demonstrations, as proposed in (Gao et al. 2025). which complements our likelihood ratio-driven improvements in PTA. Integrating the proposed PTA with such extensions could further enhance its effectiveness by highlighting task-specific information and tailored noise variance, marking a fruitful direction for future work.
Third, Theorem may suggest reformulation in which the vocabulary space is limited to directly maximizing the divergence between private and public next-token probability distributions, rather than being fixed in advance based on public information as in our current compositional design. Specifically, selecting the vocabulary to maximize this divergence could further enhance alignment with the ground truth concept while mitigating the noise error term in Theorem 2 However, this approach introduces challenges, such as the need for more complex DP mechanisms account for vocabulary selection based on private information. We leave this an extension of current PTA.
13

---

PTA for Improving Accuracy of DP-ICL Based on Implicit Bayesian Inference
B. Related works
In this section, we will outline the methods that are related to this research and discuss their positioning in relation to it. To improve the accuracy of DP-ICL, the proposed PTA uses DP synthetic demonstrations. In generating DP synthetic demonstrations, the next-token probability is modified to improve the likelihood of the generated tokens. The following discussion is organized around three key perspectives: (i) DP-ICL methods, (ii) DP synthetie text generation techniques using LLMs, and (iii) methods for modifying the next-token probability distribution in LLMs.
(i) DP-ICL methods.
2023) first highlighted the leakage risks of demonstrations provided in prompts for ICL. This motivates a series of works on applying DP-ICI. Many DP-ICI, methods have been widely explored to mitigate such leakage risks (Tang et al. 2024
(Duan et al.
Wu et al. 2024 Gao et al. 2025).
A key approach in DP-ICL is generating DP synthetic demonstrations as alternatives for original ones in prompts. (Tang) et al., (024) first introduced this approach by adding noise to next-token probability distribution conditioned on the original demonstrations. Their method also limits the vocabulary space to stabilize the accuracy, and its effectiveness has been empirically confirmed. The generated DP synthetic demonstrations are then used in prompts, leveraging DP's post-processing immunity for privacy preservation in query response.
While our proposed PTA indeed follows this work, it fundamentally differs in two key ways. i) Instead of relying solely on empirical validation, we provide theoretical support for the effectiveness of limiting vocabulary space by interpreting ICL as implicit Bayesian inference on the shared concept among demonstrations. ii) PTA goes beyond Tang et al.'s vocabulary space limitation by explicitly aligning the generated DP synthetic demonstrations with the ground-truth concept. Specifically, PTA highlights tokens that distinctly represent the task, ensuring that the LLM infers the ground-truth concept more accurately a crucial aspect yet not considered in (Tang et al. 2024).
Concurrently with our work on generating DP synthetic demonstrations, (Gao et al., 2025) proposed the first data- adaptive DP-ICL. Their method adaptively reduces the noise variance o² on the basis of the dynamic estimation of the sensitivity of the next-token probability distribution. This approach complements our PTA framework: while they foeus mitigating the negative noise impact by reducing its variance, PTA emphasizes tokens that distinctly represent the ICL task to enhance the likelihood of generated demonstrations on the ground-trui concept. Integrating their adaptive method with our PTA could potentially further improve the accuracy of DP-ICL, representing a promising direction for future research.
In contrast to synthetic demonstration approaches, (Wu et al., 2024 introduced a DP-ICL framework that applies the Gaussian mechanism directly to aggregated next-token probability distribution for classification. For generation tasks, it uses embedding- based and keyword-based aggregation. Although effective for various tasks, this approach leads to an increase in the noise variance 2² as the number of queries grows, subsequently degrading its accuracy. Due to this, we have opted not to adopt this method. In contrast, our PTA utilizes DP synthetic demonstrations in the prompt, which avoids the addition of noise to every query response. This strategy allows us to have an unlimited number of queries.
Another line of research in DP-ICL does not rely on the Gaussian mechanism. For example, (Hong et al. 2024 (DP-OPT) and (Amin et al. 2024) adopt the Exponential Mechanism (McSherry & Talwar 2007), leveraging random sampling instead of adding noise to the next-token probability distribution. OP-OPT, a Comited-Domani Mechanism (Durfee & Rogers 2019)) selects tokens from the next-token probability distribution while mitigating the curse of dimensionality caused by large vocabularies. Similarly, (Amin al.] (024) employ the Exponential Mechanism for next-token selection by exploiting the equivalence between softmax sampling in log space and the Exponential Mechanism, further improving efficiency via the Sparse Vector Technique (Dwork et al. (0099).
In contrast to these sampling-basse approaches that select tokens through uncertain sampling, our PTA will explicitly highlight tokens that distinetly represent the ICL. task. This ensures that generated DP synthetic demonstrations assist an LLM in accurately inferring the ground-truth concept. Nevertheless, both sampling-basee methods and noise- based methods can be analyzed within extended Bayesian framework for ICI, offering a fair comparison of how different DP-ICL techniques improve accuracy under privacy constraints.
(ii) DP synthetic text generation.
Our work is part of the broader category of DP synthetic text generation, which aims to generate text satisfying the target DP guarantee while maintaining practical utility. Traditionally, this has involved using DP-Stochastic Gradient Descent
14

---

PTA for Improving Accuracy of DP-ICL Based on Implicit Bayesian Inference
(DP-SGD) (Abadi et al. 2016), which incorporates DP mechanisms into the training of generative model parameters
using private data. The resulting model then produces DP synthetic text (Yue et al. 2023 Mattern al. 2022 Flemings
& Annavaram 2024). However, the training of LLMs using DP-SGD has become impractical due to the significant computational resources required and the unavailability of model parameters in closed-source settings.
To address these issues, (Xie et al. 2024) introduced an API-based method that leverages LLM inference APIs to generate candidate synthetic texts through random sampling, which are then refined by using a selection mechanism. The selection mechanism involves private data, compares synthetic samples with private data to retain those that best represent the original text distribution. Since this step poses risk of privacy leakage, noise added to the selection mechanism, ensuring DP.
Compared to these existing DP syntheric text generation approaches, our PТА offers a tailored approach to improve the accuracy of DP-ICL. PTA, especially aligns the generated DP synthetic demonstrations with the ground-truth concept, thereby improving ICL accuracy from Bayesian perspective. Furthermore, PTA can be seamlessly integrated into LLM inference processes, even in closed-source or resource-limited scenarios assumed (Xie et al. 2024), as does not require direct access to LLM parameters.
(iii) Modification of the next-token probability of LLMs. PTA leverages next-token modification to highlight tokens that enable LLM to accurately infer the ground-truth concept. Beyond DP applications, next-token modification is widely used for various purposes, such as enhancing diversity and coherence in open-ended text generation (Li et al. 2023)
improving factual consistency (Shi et al. 2024), and preventing toxic or harmful outputs (Xu et al. (0024).
Unlike these approaches, our PTA uniquely applics next-token modification to optimize DP synthetic demonstrations, ensuring they are both privacy-preservine and highly informative for LLM inference.
15

---

PTA for Improving Accuracy of DP-ICL Based on Implicit Bayesian Inference
C. Missing proof of Bayesian analysis of DP-ICL
In this section, we provide the details missing from Section First, we provide the HMM-based prompt formulation (Appendix CTT and assumptions (Appendix C.2) used in (Xie et al. [022) and this paper. Then, we provide the simple transformation of (5) in Appendix C.4] In Appendix C.3 we list the useful mathematical tools used in the subsequent proof.
Finally, we provide the detailed proof of Lemma and Theorem in Appendices C.5 C.8
C.I. Prompt formulation
we let θ be a set of concepts, where each To formalize the HMM-based prompt formulation described in Section 2.2 concept 0 E & defines the transition probability matrix of an HMM. The prompt is formulated as follows:
SSn: Tquery]= [0,, 01 delim
On, on
delim Iquary Pprompt.
(14a)
O = los. 0r, O1 ~ p((ss, [hs.):
(14b)
higj
0*), Vj
Vi > 1, h ~ Pprompt:
(14c)
0f delim ~ (oodeeiim |n delim, 0*),
(14d)
where denotes the number of demonstrations in the prompt and T is the length of each demonstration. In 14a), the i-th demonstration and delimiter token like "'n" are denoted by O2 and ofellim, respectively, and Equery represents query for ICL. According to the Markov property, each token oz.j is sampled based on its emission probability p(or, (hrs) in (14b). As depicted in (Ic)), the transition between hidden states follows the HMM defined by the concept 6 underlying the demonstrations, and the initial hidden state of each demonstration follows Perempt- To concatenate these demonstrations into a prompt, a delimiter token typically inserted after each demonstration, acting as boundary between them. The transition to this token is also governed by the HMM, shown in [4d).
To distinguish the different domains that probability distributions consider, we use the following notation as needed for clarity: Pyrompily for the token emission probability distribution and Ppromp|) for the demonstration distribution.
As shown in (6. we introduce the perturbed prompt distribution to model the noise addition instead of using (14b) to model the DP synthetic demonstration. To ensure it remains valid probability distribution, we have formally implemented the following formulation of the DP synthetic prompt distribution.
[query] ]= [
ofelim opelim On, delim -qqery] ~ Pprompt = Eg [Pprompe),
(15a)
max (0, Pprompt (ot.) = v vl/ke,)) + Go}
Opromp((0:: = -o/bi,) Ever max (0, Pprompi (oi.) = u/ u(ha,) + G.J'
5= ~ N( (11)).
(15b)
Consequently, our HMM-based formulation for the DP synthetic demonstrations follows (1cc). (1dd), (55)) and (15b).
C.2. Assumptions
Following (Xie et al. 2022). we detail the assumption regarding transition probabilities and emission probabilities of HMMs used in the prompt formulation. Under these assumptions, we quantify the mismatch between the prompt distribution and demonstrations in the prompt.
Assumption 1 (Delimiter hidden states). Let the delimiter hidden states D be subset of H. For any j,delim E D and f E e p( dellmm 0*) 1 and for any h & D. p(odelim h, 0²) O.
Assumption 2 (Bound on delimiter transitions). For any delimiter state dellim e D and any hidden state h E H. the probability of transitioning to a delimiter hidden state under 0 upper bounded p p(ddeli |h. 0) < 02 for any θ \ {0*). and is lower bounded p(hdeimmh,, (h, 0*) C1 0 for 0*, Additionally, the start hidden state distribution for delimiter hidden states is bounded as p( (),,eelmm()) (0) ca)-
Assumption (Well-specification). The prompt concept 0* in the concept set e.
Assumption 4 (Regularity). The pretraining distribution p satisfies: 1) Lower bound on transition probability for the prompt concept 8": for any pair of hidden states h, h E H. p(h(h', highhh'')) 0*) > Cs > 0. 2) Start hidden state is lower bounded: for any E H. p(h)@*) ) 2 cg > 0. 3) All tokens can be emitted: for every symbol o, there is some hidden state h E H such that p(oth, 0*) > <6 > 0. 4) The prior p(0) has support over the entire concept family O and is bounded above everywhere.
16

---

PTA for Improving Accuracy of DP-ICL Based on Implicit Bayesian Inference
C.3. Technical definitions and lemmas
In this section, we list the mathematical tools provide the proof in this paper.
Definition (Total (ariation(TV) distance), Given two distributions p. y over finite domain X, total variation(TV) distance defined as follows:
drv (p. 9)
Σ
Σ DEX
p(()) - ((x)).
2
Lemma (Moments of rectified Gaussian distribution (Beauchamp) 2018 Suppose X follows (is, o²). Then, random variable X m,
(X X is said to follow the rectified Gaussian distribution. Its first and second order moments given
by:
E
x
= μ
-1-90 ) + -
E
x (n²² + )²) $ (1-0(- porl
Lemma 3 (Csiszar inequality (Wilde 2011
Given two distributions p, over a finite domain X, then we have the following
(p) H())) S drv (p, q) log [X| + h(drv (p.4)),
where H-) denotes the Shannon Entropy, drv (.,)) denotes the TV distance and h(-) represents the binary entropy function.
Lemma 4 CinetanoolleHHuber bound (Bretagnolle & Huber 1979h). Given two distributions p. over a finite domain X,
then have:
drv (p, ②) S vI exp (-Drt. (plg)))
Lemma (Reverse Pinsker's 's inequality (Sason & Verdú 2016)). Given two distributions p. over a f.fintt domain X, then we have:
log drv (p.9)²
DKL (pll4) S mingex q(x)
Lemma 6 (Hoeffding's inequality (Hoeffding 1994)). Let Zi...., Zn be independent bounded random variables with
Z, E (a, b) for all i, where 00 < a a xc. Then, we have:
2nl
74
Ez, (76) 21
S exp
11 t=1
(b a)2
P
Σ
(Z+ Ez, (2.]) S -1
-1]
S exp
2nt²
(b a)²
1=1
for all 2 0.
17

---

PTA for Improving Accuracy of DP-ICL Based on Implicit Bayesian Inference
C.4. Preliminary results and transformation of
Here, we begin by recalling the original statement from Xie al. 2022
Theorem Suppose Assumptions 2 and Then, we have lim exp (n Tn r0) = 0, if is the ground-truth concept of the prompt and satisfies the following condition for any other concept 9 θ:
T E [Dxi
Cstart + Cidelio
where Ppromps and represent the prompt distribution and pre-training distribution, respectively. The expectation is taken over
Pprompt- Cidelim a positive constant.
By using a straightforward transformation, we derive Theorem from (5). To do so, we first transform the LHS of (5) as follows:
log 8(0
E BO-rroone
p(O DKL. (Pprompi (U)mmp(())|l0(000) - DKI. (Ppromp (0)lm((())))000))))0))
On the basis of the HMMs formulation, can decompose the second KL-term into:
ΣHENT Ppoopt (h1 (p(22) hr II plo; vylhy)
DKL (ppomp (O)llp(010))
Porompt (0 -oloog
Σnew p(h,
kr II P ploy = ey hy
V
Perongu (0 = v))log
log
(16)
Cs
Os
The inequality holds because applying Assumption 4 gives the following:
Percmpe (h)
vh E H.
I
p(h(0-)
C8
Next, we rewrite the first KL term.
Peramp (0,101.j-1)
DKL (prrompi (O)lk((010))
Σ
Pprompi (O = 1 log II
p(O, j=1
Proopp (0₂ (0;001.j11
Pprompo (0 v) log
p(O,
VEV
Prrompo (0,
Ppromp (0 = v) log
p(0,101:3-1,0)
j=1 DEVT
By using the transformed KL-term and 16 into 5 then obtain another condition for the convergence of r(0) as shown in Theorem
3
18

---

PTA for Improving Accuracy of DP-ICL Based on Implicit Bayesian Inference
C.5. Proof of Lemma 1
The following lemma and its proof are nearly identical to Lemma in (ie al. 2022 but we present for a self-contained purpose.
Lemma. Suppose Assumptions 1 and hold. Then, we have
log p(O,10") (0) S n1 p(O,10)
1
Calelli + +((n 1).
Proof.
First we transform p(S,,, queery (0), v0 as follows:
p(Sps Fquery (0) = pl (uurryy (), p)) p(5 10)
Σ EH
Quu 1 Queery 0)p(h Query |S,, 8)
where for the last equation we used the fact that Lquery and 5,, are conditionally independent given h
"query"
Let 0. mo Öij be the i 1-th delimiter token followed by the i-th observation sequence. For we define
Of = =O, Accordingly, we can decompose p(Sm.10) follows:
p(šm10) - =p(on delim ,0%s.
= =p(0 do Ört, 0) II p(OO 10
i=1
p(o Miletim 0)p(haclm Öex
II
Σ A
p(O
Mgelim 9)p(h) 10% #)
Adoin
n
II Σ A ED
peelim . (1) p(O (h
delim 0 0,,-
where for the third line used the fact that ofleiim and Ôex are conditionally independent given hidlimm Similarly, O and Õ are conditionally independent given heeliam for i = 1,..., We used total probability and vi, ( 1
(Assumption D in the last line.
For + 8", we have the following upper bound:
Σ
Ö delim ()p(h 0)
Kaii ED
SC²
Σ
p(O,tn 0)
Adain ED
Σ
stort ( 0)
=02
p(h Isdelimm 0
p(O,|hgtm O)p(h,mn10
-02
p( p(hguur (0)
Memi ED he
p(h Aeelii 0) p(h .)
p(0)
Σ
p(O,lh ()p(h.aam (0)
=02
p delim 0)
p(h deliim [ndelim 0)
p(O, O)p(h. start O0)
=02
p delimm 0
p (hedeim dedeim
<C² Σ
pho (h
p((0,))).
C3
C3
19

---

PTA for Improving Accuracy of DP-ICL Based on Implicit Bayesian Inference
In the first inequality, used p 1 < cg (Assumption 2 in the second inequality. Subsequently, marginalized out m in the last equality.
We also used p(hdelim10) E [ca, ca] (Assumption) 2
Symmetrically, we have the following lower bound for A = 0":
Σ
p(O,)A, dedlimm 0" 11a--111110110000 c1
Σ
p(O,)A 0-)
c1 pp(0;00)
Adiie L-IED
1
To derive the upper bound of (f). rewrite it as follows:
p(Sn, Jquery (0)
in
log
p(Sn; I Jqueryyloe (0*)
Σ himm EH P( (quueyy 11 quuury p)p (ouuuryrrr Sm, 0)
Σ siin eD p 11 0)p( (1: 1 0)
log
>>Ios log
Σ Aoten CH p (Equery] /eguery 0* )p( hageer Sm, 0+)
Σn p p(O h 0" )p(p) ( 0 0-)
Since we have already bounded the second term, we now focus on the first term. The denominator of this term involves:
Σ
puaquery I Quuury 0" ")p((
query Bay 0*).
start
qu0y
To ensure the entire expression bounded, it suffices to lower bound each conditional likelihood term p(Tquery | Mqquery 0*). This is guaranteed by the following result (adapted from Proposition in (Xie et al. 2022)))
Proposition 1 ((iee al. 2022)). The probability of an example is lower bounded for 0*: there is some ey > such that p(O, (hg morr 11331 ()) Oa for all i and future hidden states h,, .. for any I and i.
This ensures that p(z (uuurry |ojuery 0*) is uniformly lower bounded, and therefore the full denominator in the first log term is also bounded below by constant depending on C7. Applying this result along with earlier bounds, we obtain:
p(O,10) log
p(O,100) p(o)10)
(0) =
loger c7 + -2nlog
C2 + n log C1
C4
= log
+ - + log C7
p(O,10
where we set deelim = 2l0g + log cs
This completes the proof.
20

---

PTA for Improving Accuracy of DP-ICL Based on Implicit Bayesian Inference
C.6. Proof of Theorem 2
Here, we restate Theorem 2 and provide the proof strategy in this section.
Theorem. Suppose Assumptions 3 andd Then, we have lim exp (n i'n (0)) - with (1 (1-7)(1-7'), 7, 7 (0, 1) probability, if 0r is the underlying concept of the prompt and satisfies the following condition for any other competing
concept 0 E G:
p(O002) p(O)0)
2I log
Eo log
log
|
+
Di + D3)
TG(o) + (6 log +2(GG)))++((GGO)))
T
T
1
2
1
2
+ cj(00)
log
Cj (0)
log
+ Cudelin + 2C
2n
2n
y
where C == log og' D1 == mineeV (0= (0=0>>0 flog Ppropp (0 U)}, D2 =0=00
(l log 1 v0)), h(-) is binary entropy function and cy()) = m (vEV)p(ã, 0- }20} log p(o 0y1ō1g-1, and c,) = eiveye
log p(ōr vi 01
Proof. To derive the condition of the RHS of ( being negative, we focus on the first term of RHS of The proof strategy involves reformulating this term to isolate the two additional terms (i) noise error and (ii) estimation error. Specifically, we reformulate the term as follows:
p(O))0))
log
p(O.10)
n
log p(O,)0))
Eo log p(O
Eg log p(010')
+ Eo log p(O10))
log p(010+) p(010)
+ E3
T
p(O:10)
p(0
p(010)
p(0
log p(010")
Eo
p(0 + Eo log p( (1)0)) Roo [1og p(0110))) a
+ (Ro [ogg((10) Eoo [log p(O
log logr(O,10") + Eg [10E)(0107]] + (1 n
log bog((0,)) ((, -oo [(08)(O10]]
p(0 p(0
S Eo
log
+ Eo [(000)) - Eo logr(o + Es [ogg(()10) Eo [log ((10)]
() Noise error
log 1gg((0,07 )*) + -Eo [og p(O
1 + n Σ
logr(O,10) Eo [[ogr(ō[0]]
n
(i))sstimation crror
Here, (i) noise error quantifies the effect of noise addition the prompt distribution by measuring the divergence between noisy prompt distribution and ground-truth prompt distribution. Meanwhile, (ii) estimation error arises from estimating the expectation of log- ligeeiill of the noisy demonstrations under 6*, 0 with finite sample mean of those.
To derive a bound for (i), we proceed as follows. First, we express the error in terms of the total variation (TV) distance between the noisy and original prompt distributions (see Lemma Next, we decompose the TV distance between the demonstration distributions over the y" into the TV distances of individual token distributions over V (see Lemma R). Finally, we explicitly isolate the noise-dependent term to quantify the effect of noise on the TV distance between the token emission probability distributions, defined in (14c) and (6) (see Lemma 9). Specifically, combining Lemma X and Lemma 9 gives:
T
drv (Pprompe( VT, Pprompe yT)
Perompt (hi..... ........ hT)) h
Σ G(o)=
1=1
where G(oo E [0, 1] is continuous function of a, satisfying lim, G(a) = 0. The behavior of G(o) naturally depends on the next-token probability distribution of the involved LLM, as captures how noise perturbs the model's next-token
21

---

PTA for Improving Accuracy of DP-ICL Based on Implicit Bayesian Inference
probabilities (see (T8). Nonetheless, we emphasize that its derivation follows from a tight and general analysis that does assume any specific form of this distribution, ensuring broad applicability across LLM architectures and tasks of the derived bound.
By substituting the obtained bound on the total variation into Lemma] 7 then we have the following bound:
ii) Noise error < log 2
log [V] + D1 + D2) TG()) + (eP 2o T'G(a)² + 2h(TG(o)) + 20tm.
Taking the limit as + results in the derived bound converging to 20 which addresses the mismatch between the start distribution of the hidden state and a negligible term in practice.
To bound (ii), we apply concentration inequality for random variables, which leads to a high-probability bound (see Lemma T0p. Specifically, have least (1 7') probability:
T c5(0)
Estimation error
Cg c,(0))
log
+
log
2n
2n
?
j=1
j=1
Combining these bounds and Lemma 1 yield Theorem
2
22

---

PTA for Improving Accuracy of DP-ICL Based on Implicit Bayesian Inference
C.7. Lemmas to bound the noise error
In this section, we provide the proof to derive the bounds on the noise error.
Lemma 7 (Noise error). Suppose Assumption
4 holds. Given the HMM-based prompt formulations (14c).
14d
(15a
and (1bb). we have the following:
Eo [log((O(0)) Eo [logr(0100] + E [ogg((10)] EEo p(O())
2T
log [V] D1 D2) drv (epooprompll Pprompi (2) + (e log 2) drv (Pprompi) V P Perompe v )²
log2
22((drv (Pprumpo V a Prommpp vr)) + 20
where Cistan = looog D1 == minge h(() is binary entropy function.
llog Perompr (O = U)1, D2 min minee /log z10) and
os"
Proof. We transform the first term in the LHS of Lemma 7 as follows:
E Ppaaan
[ogp(0(0*)
Eo-ppoons
[log
E BOwPannn Parcepe
log Pprompi
(0)
Eomppaon [log Perompe [)] + DDL (PPprompi (lo00(0)))))) -KEL ( (/pamp/yr/ll(000000
==
:=
Applying Lemma] to Ti gives:
log [V]
T <
drv (Ppromp( SacpmmpplV"PPPPpppppee Ppromp)yyT) + lddTV (Fprampe) VT; Pprompp( ))-
log 2
Next, we have the bound on TV as follows:
1 Cs
To S DKL (pprompt [|000())))))))) + DRL (P (l < log
This holds because Pprompt and p(-10*) only differs the start distribution of h and similarly Pprompt and p(-10*) also only differs the start distribution of h2 See its derivation as shown in (6)..
Similarly by isolating out the difference between entropy of two distributions, we rearrange the second term in the L.SS of Lemma 7 as follows:
Es [ogr((10)] Eo [log((O(0]] Ti + DKL ((ppompl/yz (I]p((100)) DKL ((proompl) yr (Ip(-10))
T
Now, we bound T3:
Pprompp (O log Pprompe (O v) p(O = x00)
Pprompr (Ō Ô v)
T3-
Σ
Perompi (Ō v) log
p(Ō x10)
DE
Pprompt (O = -)
Pprompo (Ō = v) log Pprompe (Ō = =
Σ (Pprompe (O =v) Pprompe (O = x)) log
p(O v00)
Pprompi (Ö u16)
PE
Pprompt (O =v)
< Σ
(Pprompe (0 v) Pprompe (O v)) log
DKI. (pprompt IlPprompi) (0mompp)=11Ppppmmppp>>> )
p(O = 00)
Note that fixing yields p(O = w00) = p0 = v 00. The inequality follows from the triangle inequality.
To bound the log-ratio term, we have:
log Pprompe (O = v)
< max
min
log Pprompr (O = =v],
min
log p(O = v(0)]} < D1 + D2,
p(O 000)
VE ViProeee (=v)))
0=v)>0
= 8
23

---

PTA for Improving Accuracy of DP-ICL Based on Implicit Bayesian Inference
where define D1 min (00))))0==)))) gives the following bound:
llo lo prompt (0 =v] and D2 mileeee:o(==o00000l ploppoO +l0)). This
v)) log Perompt (0 = v)
Σ
(pprompe (O = v) Pprompr (0 =b]
S(D1 + D2)
Σ
PPprompe (O = v) Pprrompr =))]
p(O 000)
=(D + D2)drv (Pprompt) (rprompt""PPprrontt// Pprooppt)TT))
To bound the KL term, applying Lemma S
gives:
log 2 1 E Di
DKL (Pprompu)y> Pprooppp) prr ) DEL (Pprompy VT PlP vT)
dTv (Prompil Perooppl) vr
where e Di = Vipmae Pprompe (0 = v).
By combining the bounds on Ti, T2 and T3, we complete the proof.
24

---

PTA for Improving Accuracy of DP-ICL Based on Implicit Bayesian Inference
Lemma 8. Given the HMM-based prompi formulations 14c
15ap and (1b), we have the following:
T
drv Pprompe(V VT, Prrompt (Vr
Σ
Pprompo (h.
hr)
drv (pmmmpd 0g Pprompp Ppmmmp))))
Proof. On the basis of the HMM-based prompt formulation given by 14c
[4d] 15a and 15bj. rewrite follows:
drv (P yr, Pepompp vr) =
Σ
Pprompp (O = =v) - Pprompp (O = v)
"EV
Σ VE
Σ
Perompt (h1 hT) II
(Prompp(0; =vyli Pprompt = Bzy (2y11z))
Using the triangle inequality, bound the absolute difference:
Σ
Σ
Procmpp (h1, -.. hr)
Pprompe (0z -gglh)) Pprompi (oz 19(11g))
wEVT hrT
Σ
Σ
Prrompe (h),
bTT)
Σ
Pprompe (o, 2gth3)
Pprompe (oz =gghh)]
Here, we applied the general triangle inequality for product differences:
T
T
T
[+1
II
aj
II J=1
by
aj
byl
II
ag
by
1=1
f=1
j=1
where aj = Po = vy 141) and by Pprompe (oz = vy 11y), noting that both probabilities lie in [o, 1].
Rearranging the summation order, we obtain:
drv (ppropppp Pprompe =
Σ
Pprompe (hi...... hT)
Imprompr (o- = [1yhhs) - Pprompr = =u,14 uy1h,)
for
j=1 NEEV
Σ
Pprompe (hi, hT)
drv (emoop((0j(1i)) Ppooppe
An for
j=1
This establishes the desired bound.
Lemma 9, Given the HMMM-based prompt formulations 14c).
14d
15a)
and 15b), we have the following:
dry (Pprompr (0z = (b)lh;)): Ppompe (o, = 1y (b))) s G(a),
where G(o) E [0, 1] is continuous function of and lim,-s0 G(a)= 0.
Proof. To establish bound, we begin by applying Lemma
drv (Pprompl) v pp drv (Pprompl) Vs Ppemmpulv) V exp (-DKL (Pprompd) v ll (p)ooopp))))))
Next, we express the KL-term using definition the noise addition as shown in 15a and 15b
Rewriting the KL-ttemm gives:
DKL (Pprompttt) |EE [Pprompe/v])
Σ
Pv log Pe log log
1 + Σvey Zu 2.1):
Pv + Zo
(17)
DEV
25

---

PTA for Improving Accuracy of DP-ICL Based on Implicit Bayesian Inference
where introduce Pv Pprompo (o v/li) and Z. maax(0,p Pv + Go) Pus S (Go)evv ~ NN(0, I v1) for notational simplicity.
Now, we aim to bound the expectation term of the RHS of 17 convexity of f(x) = log.r, x, then we have:
By using the Jensen inequality, which holds due to the
[ (1+ Σ Zu
Pe + Zu
Pv + Zu
- llog B
S R
- log
< log E&g
- -Bş [log (po + Zo)]
1 + EnEy Z
1 EnEv Z
NEV
: F(T.pp))
By defining F(a, Pb), obtain an explicit dependency of the bound. Since Zy Po max ma, Po + Go) follows the rectified Gaussian distribution, thus applying Lemma yields:
[1+
[1+I NEV
Ec
1
Zu
= log 1 Σ
Pu
+ oΦ
(-b))
Pu
NeV
Thus, obtain the following upper bound:
(- (-(Z)
logpo + PoF((o. pw) )
drv (Pprompu[V) V. Pprompily))
- exp
P.
(18)
WeE
:G()
To validate this bound, we analyze the asymptotic behavior of P(a, P.) as + 0, rather than deriving its closed formula. Specifically, we evaluate:
00
2
lim F(o,Po)= =0 - lim Eş [log (p. + Z.)] o-0
=-
log max(0, Co + pp) lim o /2na
exp
dc.
o-30
02
log max (0, (o)0(G. pm)dGr = log
where d(-) represents the Dirac delta function. This result implies:
lim drv (Pprompt)V: Pprompily) = 0.
This asymptotic behavior is consistent with the definition of Aprompp and Pprompa, confirming that Apromp converges to Prrmpp when a + 0 (i.e. noise-free setting) from its definition.
Consequently, we have established a bound in the form:
drv (Ppromptly Pprompt())) S G(a),
where G(a) is continuous function that satisfies:
G(a) E [0,1],
lim G(a) = 0. o
This completes the proof.
26

---

PTA for Improving Accuracy of DP-ICL Based on Implicit Bayesian Inference
C.8. Lemmas to bound the estimation error
Lemma 10 (Estimation Error with Finite Demonstrations), Given the HMM-based prompt formulation 14cb. and 15b). Then, we have the following at least (1 7) - 7/) probability for any E A
(1dd)
(15a)
3 log log
010)
Σ log ((01))
Σ log p(O,10) Bo [1ogp(ō18)
T
$
c,(0*)
log
+
Σ
c,(0)
log
2n
2n
?
j=l
j=l
where
c,(0"==
min log 0y1ō1g-1, V
(0)
min V
log log 011ō13-110))
Proof. First, we aim to bound the following:
log logp (0,10))) + Bo [og p(00))))]]
Since Ö,,..., Ön are independent, thus applying the Lemma gives the following bound:
logp(O,100) Eo [ogg( 2 s 2exp
(-70- a)²
2nt
Pr
n
where b, a is upper and lower bound of log p(O, Specifically, to derive these bound we consider the following:
T
1b - s
min wE(UEVT o((= 1(0,,010-))00
log log = +100)
min 100
log p(og uy 1110111-1, 0*)
min
log p(ō.j Uy 0y1ō1.811.0")
By S(
=0,(
By rearranging for probability bound 1 7:
log logr((,10') + Bo [logrl [[0g]([10]]
c0(0))
log 2 γ
2n
Similarly, we have the following bound for E θ at least 1 - 7 probability:
log 0 + Es [10g)[ō10]]
<
(0)
log
2 ?
2n
where (0) = min ((VVVV))000) logr(ō. = vy 2y 0) This completes the proof.
27

---

PTA for Improving Accuracy of DP-ICL Based on Implicit Bayesian Inference
D. Privacy analysis
This section presents the privacy analysis ensuring the proposed Algorithm satisfies (s, 6)-D. In Appendix D.I we introduce key notions and relevant theorems from the literature that form the basis of our analysis. Appendix D22 provides a detailed proof that Algorithm |stiisiies (s, dDD.. Finally, we describe the numerical calculation of noise variance o² to ensure (c, 6D- in Appendix D.3 based on the method proposed in (Gopi al. 2021
D.1. Preliminaries
Basics of differential privacy and its composition Differential Privacy (DP), introduced by (Dwork et al. 2006a), provides rigorous privacy guarantees for datasets used in statistical queries. Formally, DP is defined as follows:
Definition 2 ((e, DDDifffrrental Privacy (DP) (Dwork al. 2006a)). A randomized mechanism M is (s, didffferrentllll private if for any two neighboring datasets D, D' D that differ by at most one element, and for any subset of outputs S C Ra)ge(MM,, the following holds: Pr [M( E ES] S (ePrr(M(D)) E ES++ +
(19)
As described in Section 2.1
0 bounds the distinguishbility of outputs between neighboring datasets and 8 (0, 1)
represents the allowable maximum failure probability of exceeding this bound Smaller values of 6 indicate lower likelihood of privacy leakage. To achieve (e, 5)-DP, a Gaussian mechanism is widely used. The Gaussian mechanism is formally defined as follows:
Definition 3 (Gaussian Mechanism). Let f X + Rd. The Gaussian mechanism is defined as follows:
M(D) = f(D) o
where Ta is the identity matrix.
The privacy guarantees of the Gaussian mechanism depend on the noise variance o.. To determine the noise variance, the sensitivity of f must be considered, which quantifies how much the outputs of can change between neighboring datasets. For the Gaussian mechanism, the sensitivity is measured by using the fn-nomm, also known as fg-sensitivity, defined as follows:
A = max [I((D) - S(D')l2 D.D
By using fg-sensitivity, the noise variance o² is calibrated to ensure (s, 6DDD. This relationship is formalized as follows: Theorem 4 (Noise variance of Gaussian Mechanism (Dwork & Roth 2014)). Let f X - RRd and M be the Gaussian mechanism adding noise to the outpul of f. Further, let A be Ez-sensitivity J. For any e E 1), 5 E (0, 1), the Gaussian mechanism with a= A / / is (e, (D..
Thus, the Gaussian mechanism ensures privacy by using the tuned noise variance. When the Gaussian mechanism is applied to randomly sampled subsets of a dataset, the privacy guarantees improve due to sub-sampling amplification. Sub- Sub-sampling amplification formalizes the observation that accessing only a subset of the datasets reduces the risk of privacy leakage:
Theorem 5 (Sub-sampling amplification (Balle et al., 2018). If is (E.6)-DP, then the sub-sampled mechanism with sampling rate q obeys (g', JDD with privacy parameters:
= log (1 + g(e 11),
8' qó.
While the Gaussian mechanism or the sub-sampled Gaussian mechanism ensures privacy for single iteration, repeated or sequential applications to the same dataset increase the risk of privacy leakage as small leaks accumulate. To quantify the overall DP guarantees across multiple iterations, the privacy parameters 8 of each step must be combined through composition. Naive composition (Dwork & Lei. 2009). which adds & and 8 linearly, provides valid but overly conservative estimate of cumulative privacy guarantees. This overestimation leads to unnecessarily high noise variance, degrading the accuracy of DP mechanisms. These limitations have motivated advanced methods, including advanced composition theorems (Dwork et al. 2010), Renyi DP (Mronnoy 2017), and other refined analyses (Dong et al. 2022). to achieve tighter bounds on cumulative privacy guarantees.
28

---

PTA for Improving Accuracy of DP-ICL Based on Implicit Bayesian Inference
Among these approaches, focus on numerical composition (Gopi et al., 2021 which leverages privacy curves and Privacy Loss Random Variables (PRVs) for precise and efficient analysis. Numerical composition is particularly effective in adaptive settings, where the output of one mechanism influences the input to subsequent mechanisms. For example, in generating DP synthetic token sequences (Tang et al. (024)) the Gaussian mechanism is applied iteratively, with each token generation relying on previously generated tokens. Numerical composition provides a robust framework for analyzing such scenarios while minimizing overestimation.
Privacy curve and numerical composition using PRVs A privacy curve provides a functional representation of DP mechanism's 's guarantees by relating the distinguishability parameter the failure probability 6. Formally, the privacy curve is defined as follows:
Definition 4 (Privacy curve (Gopi et al. 2021)). Given two random variables X, Y supported on some set Ω2 define 6(X[ : I + [0, 1] as:
((X = sup Pr Y E S] - Pr E S].
SCO
For DP mechanism M, the privacy curve ensures that M (e, 6)-DP if ((M())) < ó for all neighboring datasets D, D'. By composing the privacy curves corresponding to individual DP mechanisms, we can determine their cumulative privacy guarantees when multiple DP mechanisms are applied itcratively or adaptively. The composition of privacy curves is formally defined as follows:
Definition 5 (Composition of privacy curves (Dong et al. 2022 Gopi al. 2021 Let 61 ((x and 62 5(X2 (2) be any two privacy curves. The composition of the privacy curves, denoted by ò1 @ 82, is defined as
81 X 62 (x) Y2)),
where X1, X2 are independently sampled and Yi, Y2 are independently sampled.
This composition operation combines the privacy guarantees of individual mechanisms into single privacy curve that describes the cumulative guarantees of the sequence of DP mechanisms.
Theorem (Composition theorem (Dong et al. 2022 Gopi et al. (021)). Let M2.,,...,,,M My be DP algorithms with ......,,, d2.
privacy curves given by 51, .2,.... óg respectively. The privacy curve of the adaptive composition M₃ MM 0...0 M1 is given by 8, @ 82
This result demonstrates that privacy curves provide unified framework for analyzing cumulative privacy guarantees, ensuring the accurate overall privacy parameters E, 8 for adaptive compositions without unnecessary overestimation or underestimation of cumulative privacy guarantees.
To efficiently compute privacy curves and their compositions, RPVs were introduced in (Gopi et al. 2021). PRVs re- parametrize privacy curves by representing them as pairs of random variables (X, Y). enabling efficient evaluation and composition. The precise definition of PRVs and their formal derivation are deferred to prior work (Gopi al.) 2021). Here, we highlight key properties of PRVs:
Uniqueness: For any DP mechanism's 's privacy curve, there exists unique pair of PRVs (X,Y) such that 8 = = (Theorem 3.2 in (Gopi et al. 2.2T)).
The privacy curve can be directly computed using the PRVs (X, Y) as d(s) Pr Y > - Pr e] (Theorem 3.3 in (Gopi al. 202T))
Explicit formula:
Composition: The composition of privacy curves 81 5(X, Y1), 82 = 8(X₂ (\2) corresponds to summing their PRVs 8 81 @ 62 5(X,, + XellY + Y2) (Theorem 3.5 in Goop al. )021
By leveraging these properties, the numerical composition process proceeds as follows: (1) determine the PRVs (X,, Y2) for each DP mechanism, (2) compute the PDF of the sum of the PRVs for all mechanisms in the composition by convolving the individual PDFs, and (3) evaluate the resulting privacy curve using the explicit formula. This convolution operation transforms the computation of cumulative privacy guarantees into scalable and precise process, making PRVs a practical and powerful tool for analyzing iterative and adaptive DP mechanisms.
D.2. Privacy proof
Here, we provide the proof of the following theorem.
29

---

PTA for Improving Accuracy of DP-ICL Based on Implicit Bayesian Inference
Theorem 7. Algorithm (Etotal: )
Specifically, we aim to show that the entire procedure satisfies (froaal ( where these cumulative privacy parameters are obtained by composing per-iteration guarantees. The definition and calculation of these parameters are provided the following proof.
Proof. The PTA procedure Algorithm| Trerithmmoppraane operates iteratively at most T. processing the private dataset priv to generate DP synthetic demonstrations length T. Each iteration generates token that depends on the previously generated tokens, forming part of the DP synthetic demonstration. Consequently, the cumulative privacy guarantees of Algorithm must be analyzed by using adaptive composition across T' iterations, the basis of Theorem 6 This proof demonstrates that Algorithm satisfies (fiota,, Ororal) DDP by composing the privacy guarantees of the sub-sampled Gaussian mechanism through numerical composition.
First, we identify the Lines Algorithm involling private datasets Ppdy at j-th iteration. Algorithm processes private dataset Ppiy in the following steps:
Line
The subroutine GenPrompt (Driv. M, N, J. O) generates private prompts "riv paiv by sampling subsets
s(I) S(M
of 'Dpmee priv- This step introduces sub-sampling amplification of the subsequent mechanism, as shown in Theorem
Line 8: Private prompts
SK()) priy are used compute the next-token probabilities p(o'IM s| p which are then modined PTA in Line [ Finally, the modified next-token probabilities aggregated across M subsets. This
modification and aggregation involves ppeiv and requires DP mechanism to ensure privacy.
To ensure that the above lines satisfy (Eg, Algorithm introduces the sub-sampled Gaussian mechanisms whose privacy curve 6j accounts for
Line 3:
Sub-sampling amplification with sampling rate q
MN
as shown in Theorem
Paw
Line 48 The Gaussian mechanism adds the noise to the next-token probabilities modified by PTA. As shown in Line
and 6 PTA modifies the next-token probabilities, as follows:
[((ouM= 1/ 51(5(()) priv
Poase (o I =v)
Po
p(olLM 1/ Sppbb)
p
Pe
Evev
E
lg ez-sensitivity of the above steps is at most V2, since as the token probabilities are necessarily projected onto the probability simplex. In Line 8 the obtained next-token probabilities pe are aggregated across M subsets followed by the addition of the Gaussian noise:
M
1 M
Do
+ +N(00,00))
By combining Theorem and 5 these steps satisfy (ēz, DDP with the tuned noise variance 0². Therefore, there exist unique PRV' (X,, } such that the privacy curve of the sub-sampled Gaussian mechanisms is 6, = 5 (X,, Yj). Furthermore, due to the post-processing immunity of DDork et al., 2006b), subsequent operation on P. in Line 9 never increases the risk of leakage of Dpiv. The overall j-th iteration satisfies (ε,, 6,),,,))DP J
In the following discussion, we assume that the noise variance o² has been appropriately determined to satisfy the per- iteration privacy guarantees jو(E,) < ōy given sampling rate q. The specific calculation of noise variance o² is deferred to Appendix D33 where it is determined through numerical composition(Gopi al. 202T).
Since the sub-sampled Gaussian mechanism operates for T iterations, the cumulative privacy guarantees are analyzed through adaptive composition. By using the composition theorem for privacy curves as shown Theorem 6 the overall privacy guarantees are composed as:
Jistll = on 3 82 3 8r.
30

---

PTA for Improving Accuracy of DP-ICL Based on Implicit Bayesian Inference
where bj 6X2 represents the privacy curve of the sub-sampled Gaussian mechanism at the j-th iteration. This operation combines the privacy curves of individual iterations into single curve representing the cumulative privacy guarantees.
As discussed in Appendix D.1
the cumulative privacy guarantees are efficiently computed by summing PRVs across all iterations. The composed privacy curve is given by:
T
Ootal = 6 (X total Vooal) (Niotal Yiotal)
Y2)-
Once the cumulative privacy curve Ouaa is determined given noise variance o², fixing one of the privacy parameters éttall or óoaal allows the other to be computed using the explicit relationship between the privacy curve and its PRVs.
In summary, at the end of T iterations, the final output Ô is guaranteed satisfy (Guall D The use of numerical composition ensures precise cumulative privacy guarantees, avoiding unnecessary overestimation or underestimation.
D.3. Numerical calculation of o²
In Appendix D.2 we proved that Algorithm 1 satisfies (éwaat, )-P. The noise variance o² plays a crucial role in determining the specific values of (Ewaat: dwal). Conversely, o² can be calibrated to satisfy the pre-defined (é 8 In this section, we describe the numerical calculation of o², following the method proposed in (Gopi et al. 2021).
First, we present the privacy curve of the Gaussian mechanism. (Balle & Wang 2018) show that the privacy curve of the Gaussian mechanism is given by:
8(N(A, (N(,,,
To relate the noise variance of the Gaussian mechanism to its privacy curve, we derive the PRVs corresponding to the Gaussian mechanism, the same as (Gopi al. 202T):
Proposition 1 (PRVs of the Gaussian mechanism). The PRVs (X,Y) for (
o2)| o²)) are given by:
==N (-
A
A A
==
N
(20)
20 o2
20
σ²
The proof is nearly identical to Proposition B.I in GGop et al. 2021).
Proof. Let P N({,0 and Q = -O, o2). By Theorem 3.2 in (oop al. 2021). the PRV Y defined as:
((()) P(L)
Y = log
where L ~ Q =N0000)))
Substituting the Gaussian distributions for P and Q, we have:
exp (-P/202)
(t - 2)
12
2
12 A2 2022 02
Y = log
exp (-(t-A)3 A)2/202)
202
202
202
o²
t
~
N
A similar calculation shows that X = N (-
Aa 42 207,
oz
By combining Proposition and Proposition B.3 in GGop et al. 2021), we have the following:
Theorem (PRVs of the Sub-sampled Gaussian Mechanism (Gopi et al. 2021)). Let (X, Y) be the PRVs for the privacy curve of the Gaussian mechanism (A, (O, o²)), and let q be the sub-sampling probability. Then the PRVs (Xq: Ya) for the privacy curve of the sub sub-sampled Gaussian mechanism are:
X, log (1 + g(ex - -1));
(21)
Y, log (1 + g(eY - 1)), w.p.
(22)
log (1 q(ex 1)), w.p. g.
31

---

PTA for Improving Accuracy of DP-ICL Based on Implicit Bayesian Inference
We ready describe the steps to calculate noise variance o².
Steps for numerical calculation of o²:
1. Initialize and fix o²: Start with an initial guess for the noise variance o² within feasible range (e.g., E (..3, Fix o² and proceed to evaluate the privacy curve on the basis of this value.
2. Compute PRVs for the sub-sampled Gaussian Mechanism: For the given o² and sub-sampling rate compute the PRVs (X))) y(()) for the j-th iteration, defined in Theorem
3.
Compose PRVs across T' iterations: Sum the PRVs across all iterations to compose the corresponding privacy curve:
T
T
X Iotal
Σ
y()
total
j=1
4. Evaluate the privacy curve: Use the PRVs (Xuoat, Yioaat to compute the privacy curve representing the cumulative privacy guarantees:
Oroent (e) = Pr (rrmal > c) e [Xrona >
e
5. Check and adjust o²: Compare the evaluated privacy curve 6é(() against the pre-defined privacy parameter 8:
Grotal (E) < 8, the current 6² satisfies the privacy guarantees.
If Grocal (?) 8, increase o² and repeat steps 2-5.
This iterative adjustment ensures that o² is as small as possible while satisfying the pre-defined privacy parameters (é, 8),
6. Finalize o²: Once 2 is found that satisfies the privacy parameters (é, 8). terminate the search.
Practical implementation: The iterative process of adjusting o² can be efficiently implemented using binary search. Start with a range for a (e.g., [0.3, 3.0) and refine the range until G (c) closely matches Numerical evaluation involves discretizing and truncating the continuous PDFs X and Youal ensuring precise calculations with controllable errors ferror and Semors detailed in (Gopi al. 2021).
Table summarizes the used specific values of noise variance o² for each experimental configuration detailed in Appendix The noise variance o² is determined within [0.3, 3.0] by using binary search with an interval of 0.01. Note that the total number of compositions is computed as the product of Thhha representing the number of the generated demonstrations associated with the same label and 7', the length of each generated demonstration.
Table 4: The noise variance の² for the experimental configuration detailed in Appendix
F
Dataset
miny D priv
M
N
T
Tishot per label
Semoor
Serror
Va for 8 = 1,
GINC
1600
5
4
10
(0.70, 0.59, 0.47, 0.37]
AGNEWS
30, 000
10
2
100
1
00.51, 0.46, 0.39, 0.31]
10-10
0.01
DBPedia
40, 000
40
2
100
1
miny, Di..
(0.63, 0.54, 0.45, 0.36
TREC
835
80
1
15
1
[1.33, 0.94, 0.69, 0.51]
32

---

PTA for Improving Accuracy of DP-ICL Based on Implicit Bayesian Inference
E. Supplementary details of PTA
In this section, we provide the derivation the proposed PTA from the KL-constrained problem defined TT.. Since this derivation relies on an estimated likelihood ratio based on observable prompts, we also explain the rationale behind this estimation and its implications, grounded in the Bayesian interpretation of ICL Finally, we describe the algorithmic implementation used in Algorithm T to generate DP synthetic demonstrations.
E.1. Derivation PTA
Here, we provide the derivation of the PTA, which modifies the next-token probabilities, as shown in (33). To derive the modified next-token probabilities in PTA, aim find the valid probability vector = (Po)vE that maximizes the objective in III. using the likelihood ratio estimate in (2)
p(ouM v/. spri))
max
Σ
Po log
DKL Plave (plleane(ooUN) (OULM),
s.t.
Ex=1, Po 20 Vo E Vpub-
(23)
p(oll = 2/ pppb))
a
E Viuh
We transform the objective as follows:
p(O r15((1) pmv))
arg max Pr
Σ
Du log
p(OLLM 2 pphh)))
DRL (basoe (o!)M))
DE Voun
pluLLM 1/ priv
(S(
1
Dv Phuse (O 17)
arg max
Σ
Po log
log
p(oII 2/ Sppp))))
a
of Vau
p = 1/ -11 priv
Pv. Poase ( = v)
arg min
Σ pr
log
a alog
p(O = 20 2|SSpb)
Po
VEVi
arg min
Σ Do
log
p
log Z
m M
Pv
Plese (oLLM o)exp
a log
u
arg min DKL (111)").
(24)
Po
For the second and fourth equalities, DKL (-I1-) is evaluated over the limited vocabulary space Vpub. Furthermore, in the third equality, we introduce the following definitions:
P(oLLM = r| r(
p(oLLM = r: (1))
Z
Pbase Pbuse = u)exp a log D
Σ
1 Z Peuse (ilase((otii (OLLM u)exp a log p(o = v Spub))
pprv)
p(o = v u/
These definitions ensure that 6 = vEr is a valid probability vector satisfying, Evey D3 1,1,, 3 2 0. On the basis
of Gibbs' inequality, the transformed objective in (24) is minimized precisely when Vo Vpub, P. P.. This completes the derivation of PTA, showing that the modified distribution is given by:
/P(OLM = v/ v/5(( (())
Do O Pouse ( (OLLM = =v)
priv)
p(o!u = 2/ Spbb)
E.2. Rationale and implications of the likelihood estimation 12
To solve the objective estimation here:
PTA relies on the likelihood ratio estimation given in 112) For the clarity, we restate the
MoJ4M_u(01 ~ log
p(o -
log p =)
priv
33

---

PTA for Improving Accuracy of DP-ICL Based on Implicit Bayesian Inference
Algorithm 2 VocabSpaceLLiit
Input: V,k S VI.p E [0, 11, p(d v(Spub)
1: V arg max
Σ p(o'rM = =[Spub)) s.t. | = k
VCV
VEW.
2: V" arg min D
s.t.
E p(d 1| v)Spub) 2
VVgv
DEV"
3: Vpub VVN n V"
4: return Vpub
As we discussed in Section 4.2 the LHS of 12 is intractable compute because 0 and 0 are latent concepts neither explicitly parameterized nor observable in practice making it impossible to directly evaluate the likelihoods conditioned on and 0* To address this, we estimate the objective using tractable next-token probability distributions conditioned on observable prompts.
This estimation is grounded in the Bayesian interpretation ICL (Xie et al., 2022). which views prompting an LLM with demonstrations as inducing posterior distribution concentrated around the ground-truie truth concept underlying those demonstrations. In this view, conditioning the LLM on observable prompt S approximates inference p(0]S). When the prompt consists of demonstrations aligned with ground-truth concept 0", the resulting next-token probability distribution asymptotically converges to p(oLLM v10*). Accordingly, the private prompt s(1) surrogate for conditioning on 8", while the instruction-only public prompt Spub serves as a generic reference, approximating conditioning on any other concept 0.
latent concept
pprv serves as a
To clarify how the estimation works, we decompose the LHS of 122 as follows:
p = x10") log p(o = =0(0))
P(OLUM vl v1.Spub)
log
+ log
(25)
p 0)
p(oLIM r SpSh))
p u10)
This decomposition reveals that the estimation in 12 corresponds to substituting the intractable first term on the RHS of
M(oLLM +
(25) with tractable log likelihood ratio log p(olM== =u Spa) motivated by the Bayesian interpretation of ICL discussed above,
while omitting the second term. The omitted second term in 25 becomes negligible compared to the first when the sets of
high-probability tokens are well-separated across concepts, since in such cases tokens distinctive to the ground-truth concept
O are unlikely under both the public prompt and other concepts.
To encourage this separation, we design Spub to include only general task instructions and no concept-specific information. This neutral design helps promote divergence in token likelihoods across concepts relative to the likelihood conditioned on Spuh. thereby supporting the plausibility of omitting the second term in (25)
E.3. Algorithmic implementation
Algorithm 2 outlines how limit the vocabulary space plausible subset by applying both static threshold k (on the maximum number of tokens) and a dynamic threshold p (on the cumulative probability of selected tokens). This dynamic adjustment adaptively decreases the negative noise impacts primarily influenced by the vocabulary size in (9).
In Algorithm 3 we detail how to generate prompts from randomly sampled demonstrations. This procedure is identical to that (Tang et al. 2024), and the prompt construction functions PB(-) for each dataset appear Appendix F.
34

---

PTA for Improving Accuracy of DP-ICL Based on Implicit Bayesian Inference
Algorithm GenPrompt
Input: instruction, Dpriv M, N. v. Ô
1: D priv randomly draw MN samples from D peiv with label ğ
2: Spuh <- Piiisstructionn 3, Ô)) where PB(() defined in Table 13
3: for = 1 to M do
4:
D(1)
priv +- D'
priv [íi 1)N iN]
5: s(i)
priv + P Piinstrructii ((i)
V. Õ))
6: end for
((M) return: Spub. s(1) priv ..., priv
35

---

PTA for Improving Accuracy of DP-ICL Based on Implicit Bayesian Inference
F. Additional Experiments
We first describe the computing resources used for GINC and text-classifictiion tasks in Appendix F1 followed by a detailed account of each dataset (AGNews, DBPedia, TREC, and GINC) Appendix F.2 Appendix F3 focuses on GINC,
explaining its synthetic generation process via factorial HMMs, the corresponding GPT-2 pre-training procedures, and how they align with earlier work.
Next, we outline the implementation details in Appendix F.4 including the calibration techniques from (Zhao et al. 2021 for stabilizing DP-ICL, as well as methods for computing the log-likelihood of generated demonstrations in GINC. Then, we report the accuracy and distinguishability comparison across various configurations and privacy parameters, omitted in the main paper, resepectively in Appendices [F33]]]d and [.6 Finally, we offer examples of DP synthetic demonstrations, illustrating how our method amplifies the distinctive tokens while preserving coherence.
E.. Computing resources
For GINC, we used a server that has 2 GPUs (NVIDIA GeForce RTX 3080) with CPUs (Intel Xeon Gold 5218R, 2.1 GHz). For cextcllassffication tasks, we used a server with 8 GPUs (NVIDIA A6000) and 2CPUs (Intel Xeon Gold 6346, 3.10 GHz) for text-classification datasets.
F.2 Datasets
This section describes the datasets used in our experiments.
The AGNews dataset (Zhagg et al. 2015) involves topic classification with labels categorized into four classes: World, Sports, Business, and Technology. It includes 30,000 training samples and 1,900 test samples per class. We utilized all 30,000 training samples and 1,000 test samples.
AGNews:
DBPedia: The DBPedia ontology classification dataset (Zhang et al., 2015) involves topic classification with labels categorized into 14 classes: Company, School, Artist, Athlete, Politician, Transportation, Building, Nature, Village, Animal, Plant, Album, Film, and Book. The dataset includes 40,000 training samples and 5,000 test samples per class.
TREC: The TREC (Voorhees & Tice 2000) question classification dataset involves classifying questions into six labels: Number, Location, Person, Description, Entity, and Abbreviation. It comprises 5,500 training samples and 500 test samples, distributed non-uniformly across the labels.
GINC: The GINC dataset (Xie et al. 2022) is synthetic text-classification dataset generated from uniform mixture of five factorial HMMs. Each HMM represents a latent concept, an underlying pattern that governs token transitions in sequences. Using the original pre-training documents from (Xie et al., 2022), we further created 1,600 training and 400 test samples per concept for evaluating accuracy of ICI., ensuring no duplication
E Unlike the datasets described above, which have fixed label sets, GINC uses dynamic labels. Each label corresponds to the most likely last token of each data, determined by the GINC distribution for its corresponding latent concept. Details on the GINC distribution hyperparameters are provided in Appendix F3
F3. Details on setup for GINC
HMMs setup. The GINC dataset, introduced in (Xie et al., 2022), is designed to study ICL in controlled setup. It is generated from uniform mixture of five factorial HMMs, each representing distinct latent concept 0g O(i -,...,5)) 5). Each HMM emits token from vocabulary V. which is constructed by enumerating combinations of letters (e.g.. "a" to "z," "aa" to "az") with backslash designed as the delimiter token.
To model how real documents are generated using the meaningless vocabulary, each HMM comprises two independent Markov chains: one representing transitions between entities e, E (1,..., |&]} (e.g., Einstein, Gandhi, etc.), and the other capturing transitions between properties 8, E {1,,.., ||]} (e.g.. nationality, occupation etc.). The emission probabilities ploy depend on the combination of entities and properties, i.c., p(o (4)) p(o, e, st). These two chains are crucial because real documents often involve interdependent patterns: entities (e.g., Einstein) are associated with properties (e.g.. scientist). Modeling these two aspects independently allows the HMM to reflect how documents are structured in the real
"To guarantce the privacy parameters of (s, DDP, unintended exact duplication in training data can underestimate leakage risk, violating the assumed (s. 8DPP. De-duplication is therefore essential.
36

---

PTA for Improving Accuracy of DP-ICL Based on Implicit Bayesian Inference
Table 5: Empirical evaluation of C
+
1 log &
appearing in RHS of Lemma
when = 4.
0"
01
02
03
04
0g
Cdellim
42.75
49.94
46.00
41.53
39.52
Table 6: Pre-training train validation loss and the accuracy of ICL on GINC with [V] = 150 for GPT-2 models varying in size.
Model
train loss
validation loss
Accuracy of ICL
(MA1) GPT-2 (4-layer)
1.264
1.283
92.80
(MA2) GPT-2 (12-layer)
1.263
98.40 1.279
(MA3) GPT-2 (16-layer)
1.267
1.283
99.70
world. These HMMs are then used generate pre-training documents, training samples, and test samples for ICL, using the scripts provided in their c
Importantly, the defined HMMs satisfy Assumption |+ which are essential for deriving the conditions under which ICL can accurately infer the true latent concept, as established Lemma and Theorem 2 These assumptions enable the numerical calculation of the specific value ('delim log 1. key parameter in Lemma and Theorem 2 The calculated
cy
values are presented in Table 5
Pre-training of GPT-2 models. We pre-train GPT-2 models by using the generated pre-training documents, following the settings detailed in Appendix F.2 of (Xie et al., 2022). Using pre-trained models, we evaluate the accuracy of ICI. The validation loss and accuracy of ICL for the models are summarized in Table o The results are mostly consistent with those reported in Figures 6 of (Xie et al. 2022), validating our pre-training setup of GINC.
F4. Implementation Details
In this section, we provide the detailed implementation used in the evaluation of the conducted experiments.
Calibration of ICL Following (Zhao et al. 2021 we implement calibration to stabilize the accuracy of DP-ICL when evaluating DP synthetic demonstrations classification tasks. To estimate the model's bias toward each answer, we use
content-free test input (e-g. "N/A") alongside the training prompt and analyze the resulting predictions. Calibration parameters are then fitted to ensure uniform predictions across answers for the content-free input. The calibration is performed by using the following two methods:
(Diagonal)
p = Softmax BeeninxxxWW-ttr + b), W dPa -1);
(26)
(Identity)
p Softmax(p Pet);
(27)
where is a probability vector representing the model's predicted probabilities for each label in the classification task, normalized to sum to one. Its dimension corresponds to the number of possible labels in the task. This vector is obtained by conditioning an LLM on the prompt with demonstrations. Similarly, Par is the probability vector obtained from the content-free test input, also normalized to sum to one. By scaling W or subtracting Par the content-free probabilities, the model's bias toward each answer can be corrected, improving calibration for classification tasks.
For text-classificttion datasets, we "N/A," an empty string (""), or "[MASK]" the content-free input. For GINC, use token sequences of the same length the demonstrations, where each token is sampled independently and uniformly at random from the vocabulary. This approach serves as content-free input because GINC's vocabulary lacks suitable representation like "N/A" or "[MASK]."
Evaluation of log-likelihood for GINC. To validate PTA's effectiveness, we examine the condition established in Lemma The controlled setup of GINC allows the precise numerical computation of the log-likelihood of generated DP synthetic demonstrations, leveraging the parameters of the HMM.
httpps//giithie com http:/hhww...ommmmmmmaeeeaeaa//e www.llaammaaaaa
learning
37

---

PTA for Improving Accuracy of DP-ICL Based on Implicit Bayesian Inference
Given the generated sequences (01,..., ...., O.th joint probability plon....,,rr hT) can be computed recursively using the forward message passing algorithm (Rabiner 1989)
p(o or, hT) p(oT(ler)
Σ or
(28)
Starting from p(01, h1), where h4 = (st, et) the total likelihood of the sequence obtained by summing over all possible hidden states at the final time step:
p(o......, .........00. .T) = -
hop
The initialization step incorporates the start distribution p(hn), which is set as a uniform distribution over all possible combinations of entity e, and property St.
F.5. Accuracy Comparison
Hlpeeraarameters. We select optimal hyperparameter settings by averaging accuracy across 8 E 11,2,4,8). For all methods, we explore & e {10, 100} and p E {0.7, 0.8. 0.9} (for (PA2) and (BA2)). We search a E {1.0, 1.5, 2.03 for (PI), (PA2), and (PA3) the text-classification tasks, and extend this range to {1.0, 1.5, 2.0, 5.0) for GINC. Notably, k = 10 consistently outperforms k 100. All other chosen hyperparameters are summarized in Table
Effects of varying model. When comparing different model configurations, we observe that (PA2) outperforms (PI) when the non-private baseline (RO) reports lower accuracy, particularly when using (MA1) and (MB1) I). One possible explanation is that, without top-p truncation when limiting the vocabulary space, (PI) may unintentionally amplify very low-probabilityy tokens through PTA. For rext-classiiication tasks, the quantized model (MB1) exhibits a higher standard deviation of accuracy, as it exhibits the worst accuracy of (RO).
Ablation on the proposed PTA. Complementing (P1), the PTA variant with Top-p (PA2), outperforms (B1, BA2) across
iext-classffication tasks, and often surpasses (P1), particularly in DBPedia (c = 1). However, (PA2) exhibits significantly worse accuracy in GINC than (PI), indicating that top-p truncation may involve trade-off's under certain conditions. (PA2) prevents LLM from retaining low-probatie wow-probability tokens, which are somehow critical with small vocabularies (e.g., M = 150).
Despite these drawbacks, both (PI) and (PA2) outperform the non-private baseline (RO) in TREC (s = 1). This observation
consistent with (Tang et al. 2024). suggesting that private generation mechanisms can potentially improve generalization in small-scale datasets.
Moreover, (P1) consistently outperforms (PA3), which considers the optimization defined in 11] without KL-constraint, when using (MA3) and (MB3), which yield the highest non non-private (RO) performance, while (PA3) performs better with (MA1) and (MB2). This indicates that, if the original model produces more coherent text, introducing KI. regularization (as in (P))) effectively preserves the natural flow of the generated demonstrations. Conversely, when the LLM performs worse without noise addition, ignoring regularization (as in (PA3)) can lead to notable accuracy gains for DP-ICL (AGNews with (MB1) and e = 1 and TREC AGNews with (MB2) and E = 1).
To further understand the behavior of (P1) and (PA3) under varying privacy paramter, examine how accuracy changes as the privacy parameter decreases. We plot accuracy across different s = {1, 2, 4, 8, oo} values for models (MA1), (MA2) and (MA3) in Figure 3 Figure jillustraaes clear trend: accuracy decreases as privacy strengthens. We highlight (MA1) as it exhibits a distinct pattern across methods, unlike (MA2) and (MA3), where (P1) consistently outperforms (B1). In contrast, for (MA1), (P1) performs the worst, while (PA3) is comparable to (B1). This difference may arise from (MA1)'s 's limited zero-shot accuracy, which makes the regularization in (P1) penalizing deviation from the base next-token distribution shown in (IT) - less effective in improving accuracy. In this setting, the regularization keeps the next-token probability distribution close the model's 's original output, which performs poorly, thus leading to degraded accuracy. By omitting this constraint, (PA3) allows more flexibility and achieves better performance.
Accuracy comparison when c = oc. Using a= = 0 or synthetic demonstration generation does not satisfy DP (i.e. e = oo), but it allows us to verify whether the resulting demonstrations increase the divergence between the ground-truth concept and any alternative. The bottom row of Table g shows the accuracy with a = 0. (P1) outperforms (RO) except for GINC and DBPedia and this indicates the effectiveness of PTA, in increasing the divergence between concepts.
38

---

PTA for Improving Accuracy of DP-ICL Based on Implicit Bayesian Inference
Table 7: The distinctive hyperparameters and a are selected to suit the specific combination of datasets, models, and methods. The table reports the values used for the results presented in Tables and
g
The selected amplification strength a introduced in PTA.
GINC
AGNews
DBPedia
TREC
Methods
(MAI) (MA2) (MA3) (MBI) (MB2) (MB3) (MBI)
(MB2) (MB3) (MBI) (MB2) (MB3)
(PI)
5.0
2.0
2.0
2.0
1.5
2.0
1.0
1.0
2.0
1.5
2.0
(PA2)
5.0
5.0
2.0
2.0
2.0
1.0
1.0
1.5
1.5
1.5
1.0
1.0
(PA33
2.0
1.5
5.0
1.0
1.0
1.0
1.0
1.0
1.0
1.0
1.0
1.0
(b) The selected adaptive threshold p for limiting vocabulary space.
GINC
AGNews
DBPedia
TREC
Methods
(MAI) (MA2) (MA3) (MBI) (MB2) (MB3) (MB1) (MB2) (MB3) (MB1) (MB2) (MB3)
(PA2)
0.9
0.9
0.9
0.9
0.9
0.8
0.7
0.9
0.7
0.8
0.8
0.9
(PA.3)
0.9
0.9
0.9
0.9
0.7
0.8
0.8
0.7
0.8
0.8
0.7
0.9
(BA2)
0.9
0.9
0.9
0.9
0.7
0.9
0.7
0.7
0.8
0.7
0.8
0.9
Table 8: 4-shot DP-ICL accuracy across four datasets and three models, averaged over five different seeds. The highest accuracy is bolded, and the second-highess is underlined.
Methods
(MA1)
(MA2)
(MA3)
(MB1)
(MB2)
(MB3)
(MR1)
(MB3)
(MB3)
(MB1)
(MH2)
(MB3)
(P1) 81. 81.18 93.65-11.81
93.99 38.99
77.644...s
82,
87.
.88
78.74.44.41
60.544:1.00
82. 82.06.33.81
70.20
76.04
84. 84.80
(PA2)
85.90.+1 92 12:
90.06
77.28
6..00
79.84=4.52
67.00 67.00++1.16
78.88 23.3
81.12
7243.54
75.32+2..1
75.2442.21
84.72-2..0
(PA3) 85. 85.40+1.39 92.58+1.92
94.14=0.95
78.18
81.16-33.0
63.244-2.94
79.50+11.38
79.60
79.60
66
16.755
74.48444.08
77 77.48:2.55
811.4 1.25
1..5841.90
92.9 13.9 90.80-2.79
76.
+..52
78.76-6.29
63.74+1.90
29.22-+2.25
79.80+2.02
85. 85.72411.4
73.00+6.15
77.32+22.06
63.56-6.00
(BA3)
63.46g2.0s 0s 92.09
12.40
69.34
78 4..
68.89
64 64.86
79.72.1
79.62 2.92 86. 36.10 76.92
17.12 81.00
(P1)
62.26 os
.7 80.06_2..0
81.30 wn 54.50 1.99 70.80
74.8812.11
84.7811.. .42
(PA2)
15.34 08.98_1.cm
90.88
79.7816.19
78.74_2.52
65 25.06
78.82_3.90
60. 60.16
84.52
77.4411.a
78
78.00
83.02
(PA3) 86.09 02 98 13.4371.77
90.41
80.50
79.96-1.56
81.48 29 80. 80.3212.44 20.60
86 10110
71.5222.11
77.7611.52
82.86
(B1) 13.30 93.9121.31
91.41_1.es
27.02
76.60_4.65
53 $3.28
79. 79.90.1.41 60.60
84, 84.28
73.20g7.52
75.52
83.04.22.2
(BA2)
84.55 98.19
90.73_n.83
72.
4..07
81.58
78. 20 60.12
74.102 73.8442.70
78.722..11 8. 83.20_1.67
(PI)
61.41 96. 20. 27..0.77...700 76
80
20.
68
78, 78.64 60.08
86 16.0011..77
71.20
T3.16
83.88
(PA2) 65.72 01 95. 20.78 91.76_1.54
17.40
78.78_4.73
1.78
79.28
an.on 60.04.a.51
84. 84.04
75.96ga.01
77.1242.01
61 84.40 0.
(PA3)
86.76 94. 94.06...99
91.64_1.60
76.4011.70
79.88_5.20
81.04.9
80.44 80.44
8080.34.1 1
84.04
74.52g3.10
77.62
83.10
(B1)
87.98 16.16
13.27
78.7442.40
77.64_3.20
86.1011.81
79.96_99.7
80.1612.11
80.0412.00
74.2814.61
76.724
82.48
(BA2)
80.8110.00
98.31 28.311..20
90.07_0.76
77.3223.77
08.30g3.67
82.1413.05
79.0219.58
79.02g2.00
84.8413.10
76.7212.211 21 777..44.....m
92.16
62.36+0.17
65.62+0.67
96.81+1.40
78.50
85.32+1.01
80.06
79.80+0.35
84.78+1.56
70.16+2.15
1..04+1.56
84.24-2..3
(PA2)
86.3721.10
95.3321.36
91.15
78.0413.80
64.2 64.24 70.74_5.12
80.40_2.61
70.92
84.1213.47
75.80
78. 78.20
83.52 122...z
(PA3)
86.46.00.99 85.1811.00
90.79
81.58
78.56_1.87
84.92
60.4441
80.044
22.77
72.2812.M
78.02
1..411.99
(BI)
87.94 05.995.84422 84.0..0.
94.63.p.55
79.5013.21
80.09=2.74
83 83.62
77.8223.02
78.90
84.40
72.48g4.17
75.9612.00
82.04-2.77
(BA2)
56.46g0.7s 94.4411.46
90.61-1.25
79.7843..2
67.17_2.01
82.96:2.32
79.18
29.12:2.00
14.86.1..1
76.10422.27
75.1243.11
81.9621.59
(PI) 81.05 11.0331122 96 11.0.40
96.37
84.14:1.58
86.
46.12
372.3.7788
28
79.42221.3
80. 60.68
82, 92.7844..00
73.16g3.04
73.52g4.12
23.56-2.35
(PA2)
66.67 1.22 96.
18
1..4
28.24
80.08_0.87
63.86
78.
76
60.58
84.46 10
75.88
77.7241.42
86.04.1.00 1.di1.o 01
(PA3) 86.67 95.81 $10.0
91:21
81.98
22.24
79.98_2.73
85
0..22
78.88 29.18
60.02 2.
85.68
77.08
77.877
2.....11111
82.88
28.43 1o...o os 11 96.60
1.36
83.24
63.2412.00
81.48_a.17
1.02
29.2
79. 11.46
84.98 12.01
74.40ga.12
77.6440.93
81.48
(8A2) 87. 17 96.68111.00
92.34
$4.461:
82.08
77.3223.08
80.00
80
s2 74.2813.47
77.4411.10
83.76
(RO) 93. 02.52+0..0 20 97. 1n
02
28
+1.08
83.82-1.70
1.22
38
1.30 21.28+9.19
+2.284.2.5
1..24
39

---

PTA for Improving Accuracy of DP-ICL Based on Implicit Bayesian Inference
Table 9: Proportion of generated DP synthetic demonstrations for GINC, using three models, where the log- log-likelihood ratio exceeds the derived threshold, appearing in the RHS of Lemma
Methods (MA1) (MA2) (MA3)
(P1)
16.89
48.89
49.33
(PA2)
26.22
47.55
40.89
(PA3)
29.34
42.22
38.22
(B1)
20.00
44.89
44.89
(BA2)
28.89
42.22
42.22
(PI)
20.89
50.22
49.33
(PA2)
25.78
44.44
44.00
2
(PA3)
29.33
44.00
41.33
(B1)
24.89
49.78
48.44
(BA2)
28.89
43.56
46.22
(P1)
24.45
58.67
56.89
(PA2)
28.89
50.67
44.44
4
(PA3)
33.33
48.89
38.66
(B1)
23.11
50.67
51.11
(BA2)
28.89
46.22
42.22
(P1)
20.89
53.34
53.33
(PA2)
31.56
51.11
41.33
8
(PA3)
28.89
48.00
42.67
(B1)
28.00
55.
55.11
52.44
(BA2)
30.67
48.45
44.45
(PI)
23.55
52.45
49.33
(PA2)
32.44
55.11
44.89
(PA3)
32.44
52.00
40.89
(B1)
33.78
55.56
52.00
(BA2)
35.55
57.33
46.22
F.6. Distinguishability Comparison
Effects of varying model. Similar to the accuracy across various models, (P1) clearly enlarges the divergence between p((0)) and p(O00*) when using the models (MA2) and (MA3), which yield the higher non-private (RO) performance, while (PA2) and (PA3) shows better performance when using (MA1).
F.7. Comparison with existing work DP-ICL
We additionally conducted empirical comparison with OP-OPT (Hong et al. 2002) using the same Vicuna-7B-v.35 model (Zheng al. 2023) and TREC dataset setup used in their study. The comparison results are summarized in Table( To ensure fair comparison, we report both our replicated results and the original results for DP-OPT from Table 3 of their paper, formatted as (replicated/ original). This is because our replication was limited understanding of DP-OPT's hyperparameters. We followed their appendix settings for = 8 and extended them to s = 1 using Eo from Table 5 of their paper. Additionally, differences in prompt format remain. Therefore, this comparison may not fully reflect the method's 's optimal performance.
To further support the numerical results, we highlight key behavioral differences between DP-OPT and our approach at
40

---

PTA for Improving Accuracy of DP-ICL Based on Implicit Bayesian Inference
(P1)
(PA3)
(B1)
(MA1)
(MA2)
(MA3)
95
Accuracy
90
85
80
1
2
4
8
0
4
8
8
1
2
4
8
8
3
Figure 3: Effect of e on accuracy for DP-ICL methods and model variants
Table 10: Accuracy comparison with DP-OPT (Hong al. 2024 the TREC dataset using the Vicuna-7B-v1.55 model, averaged over five seeds. The highest accuracy is shown in bold, and the second-highed is underlined. For DP-OPT, report original results from Table 3 of (Hong et al. 2024) and our replicated results, presented in the format (replicated / original).
Methods
Vicuna-7B
(P1)
77.84:2.83
(B1)
75.60
DP-OPT (Hong et al.
2024
47.820.0 /.....oNN.A. N.A..
(P1)
76.28 76.28
(B1)
73.84
DP-OPT Hong et al. 2024
60.76.1.27
65.3+4..3
==1. As discussed in Section 5.2 of their paper, DP-OPT tends output only the instruction without demonstrations as the private prompt satisfying (e, 8DD guarantee with 1. In such cases, the method method asymptotically converges to zero-shot prompting, limiting the practical utility of private demonstrations. In contrast, our method generates in-context demonstrations that, while potentially noisy, remain informative beyond the instruction even with 1. This may allow our approach to consistently outperform zero-shot prompting, especially in high-privacy regimes where DP-OPT yields only marginal gains.
F.8. Example of DP synthetic demonstrations
We provide examples of generated DP synthetic demonstrations in Table [1 compared other methods. blgh-highlighttdd tokens indicate cases where only PTA successfully selects the top-1 token after adding noise, while hedhigghlghhted tokens represent cases where only PTA fails do so.
highlighting how PTA influences token selection

---

PTA for Improving Accuracy of DP-ICL Based on Implicit Bayesian Inference
Table 1I: The DP synthetic demonstrations generated by PTA in the selected configurations.
Dataset
Label
Model
DP synthetic demonstrations
BREMER back in court today to defend his role the former governor of the bankrupt state of Alaska. The governor the state of Alaska, Frank Murkowski, who appointed Bremer governor of state after the AGNews World (MB1) bankruptcy, is expected to testify in support of Bremer, as is the current governor Tony Knowles. Bremer's sss former boss is also expected to defend. The trial was moved from federal court to state court in
Syrian President Assad to Visit Iran in First Tory of 2009: Diplomat (AFP) Syrian President Bashar al-Assaad (MB2) will visit Iran for the first time in 25 years later this month, in another sign of improving ties that have warmed since the two sides forged closer diplomatic links after the war in Lebanon. 12.35
Britain's Prince Charles, in his role as patron of the Prince's Youth Business Trust, has been in South Africa where he met young entrepreneurs. He met them at the University of Limpopo. He was impressed by the (MB3) students' business ideas and their enthusiasm. The trust working with Department Trade and Industry promote entrepreneurship in South southern Africa. It also working with African Development Bank to help young South Africans become self-employed
The 64th Announcement is the second single released and fourth track from the album The Twilight Tapes, by DBPedia Album (MB1) the band The Twilight Sad.
The 64th Annual Grammy Awards were held on February 8, 2012, at the Staples Center in Los Angeles. The (MB2) nomineesi were announced on October 3."
The album was recorded and mixed at the legendary Rockfield Studios in Wales, UK. The band recorded (MB3) the album with producer Romesh Dodangoda (Motorhead, Bomb20, Funeral for a Friend, and Bullet for my Valentine). The album mastered Jason Mitchell (Young Guns, Bullet for my Valentine, Black Stone Cherry, and The Devil Wears Prada). The album was released on October 14th,
TREC
Person (MB1) have interview on the phone tomorrow!"
(MB2) I have interview on Tuesday. I'm going
(MB3) Who was the first US president fly in Air Force One
? Answer
F9. Example of Prompts
In this section, present the example of prompts during ICL and generating DP synthetic demonstrations in the text- classification datasets. For fair comparison, we used the same prompt format during ICI. following (Tang et al. 2024), as shown in Table I2 In Table 13 we present the prompt construction functions used in Algorithm 3
As for GINC, it's challenging to construct the instruction sentence due to its synthetic nature. When generating the DP synthetic demonstrations, we first insert a public demonstration and then append the private demonstrations. Each formatted as a label-data pair.
42

---

PTA for Improving Accuracy of DP-ICL Based on Implicit Bayesian Inference
Table 12: The prompts used during ICL for text-classification tasks, taken from Table 7 of Tang et al. 2024
Task
Prompt
Labels
Classify the news articles into the categories of World, Sports, Business, and Technology.
Article: USATODAY.com Retail sales bounced back bit in July, and new claims for jobless benefits fell last week, the government said Thursday, indicating the economy is improving from a midsummer slump.
World, Sports, Business, Technol- ogy
AGNews
Answer: Business
Article: New hard-drive based devices feature color screens, support for WMP 10.
Answer:
Classify the documents based on whether they are about a Company, School, Artist, Athlete, Politician, Transportation, Building. Nature, Village, Animal, Plant, Album, Film, or Book.
Article: Geoffrey D. Falksen (born July 31 1982) is an Ameri- can steampunk writer.
Company, School, Artist, Athlete, Politician, Transportation, Building, Nature, Village, Animal, Plant, Al- bum, Film, Book
DBPedia
Answer: Artist
Article: The Perrin River is 1.3-mile-long (2.1 km) tidal river in the U.S. state of Virginia. is a small inlet the north shore of the York River that river's 's mouth at Chesapeake Bay. Answer:
Classify the questions based on whether their answer type Number, Location, Person, Description, Entity, Abbreviation.
Question: How did serfdom develop in and then leave Russia? Answer Type: Description
Number, Location, Person, Descrip- tion, Entity, Abbreviation
TREC
Question: When was Ozzy Osbourne born? Answer Type:
43

---

PTA for Improving Accuracy of DP-ICL Based on Implicit Bayesian Inference
Table 13: Prompt construction function PB(.) used Algorithm 3 for text-classification tasks, taken from Table 5 of Tang al. (2024).
Task
Prompt construction function PB(istrruction, D,y)
Labels
Given a label of news type, generate the chosen type of news accordingly.
News Type: World
Text: Australia boosts anti-terror measures at small airports SYDNEY: The Australian government announced a major security upgrade for nearly... ...
World, Sports, Business, Technol-
AGNews
ogy
News Type: World
Text:
Given label document type, generate the chosen type of document accordingly.
Document Type: Company
Company, School, Artist, Athlete, Politician, Transportation, Building, Nature, Village, Animal, Plant, Al- bum, Film, Book
Text: Cherry Lane Music was founded in 1960 by Milton Okun in the apartment above the Cherry Lane Theater in Greenwich Village of New York City...
DBPedia
Document Type: Company Text:
Given a label of answer type, generate a question based on the given answer type accordingly.
Answer Type: Number Text: How many people in the world speak French?
Number, Location, Person, Descrip- tion, Entity, Abbreviation
TREC
Answer Type: Number
Text:
44


Reviews:
[{"review_id": "GnzbQ3lRBs", "reviewer": "Reviewer_kLHj", "summary": "The paper presents an approximate Bayesian model of DP-ICL (differentially private in-context learning). DP-ICL in general combines a public LLM with a private LLM to generate a number of low-privacy-leakage prompts, then uses those prompts for in-context learning. A previous paper (Tang et al.) used a simple vocabulary restriction method to improve DP-ICL; this paper uses their Bayesian model to explain why vocabulary restriction works, then present an improved Plausible Token Amplification method which achieves better empirical results.\n\n## Update after rebuttal\n\nI am happy with the authors' rebuttal, and continue to think the paper should be accepted. The authors have said they'll clarify the theorem statements to show that C_delim and G depend on some things, and after that my only reservation is that I expect there is a future cleaner paper that will result in cleaner and better algorithms as well. However, the correct course of action is to accept this paper in hopes it in fact encourages that future cleaner paper.", "questions": "", "limitations": "", "rating": 4, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "# Concerns in bounding constants\n> Reviewer comments (Claims And Evidence, Theoretical evidence)\n> 1. [...] introduce a whole pile of constants [...], so the C\\_delim \"constant\" [...] hides a bunch of things which are very far from constant, [...]. Similarly, G is also dependent on the LLMs involved. \n> 2. [...] non-constant natural of C\\_delim and G really do need to be called out in the main text. [...]\n\nThis is a good question. We address $G(\\sigma)$ and $C_{delim}$, separately. \n\nFirst, $G(\\sigma)$ is a function, not a constant, as defined in Line 1339 (Appendix C.7), though this was not clearly stated in the main text. We did not intend to hide this point, thus we will include its definition and clarify its dependency on the LLM's next-token probability distribution in the revised paper. Notably, introducing the bound $G(\\sigma)$ in Line 1339 is essential for a **tight** analysis of the noise error in Theorem 2. Under general settings without assuming any specific form of the LLM's next-token probability distribution, a tight analysis using $G(\\sigma)$ in Line 1339 is established thanks to Bretagnolle–Huber bound (Lemma. 4, Appendix C.3).\n\nNext, we clarify that the term $C_{delim}$, which is defined in Line 1009, is also a function, not a constant.\nIt originated from the formulation in Xie et al. (ICLR 2022) and depends on the ground-truth concept $\\theta^*$ and the other concept $\\theta$. We will also clarify this dependency in the revised paper.\n\n# Refinement of Theorem\n> Reviewer comments  (Claims And Evidence, Theoretical evidence):\n> 1. [...] cleaner theorems hiding under the surface the theorems [...]. Theorem 2 has a term involving the vocabulary size, [...] this is artificial in order to present direct evidence for the success of Tang's method.\n> 2. [...] If the prompts are sampled sufficiently closely to the public distribution [...], we should be able to get a bound that doesn't depend on the vocabulary size. [...]\n\nThank you for the insightful comment. We agree more elegant theorems may arise under additional assumptions—e.g., when prompts are sampled closely from a public distribution and this is a promising direction for future work.\n\nHowever, Theorem 2 is designed to hold under general settings without assuming a specific form of next-token probability distribution. In practice, prompts often contain private demonstrations that may diverge from public distributions, making such assumptions unreliable.\n\nTo address your concern, we clarify why the $\\log |V|$ term appears in Theorem 2. Our analysis (Section 3) examines how the noise impacts latent concept inference in DP-ICL. Since next-token probability distributions of LLMs can vary widely, especially with private prompts, we aim to derive a general bound that holds without assuming any specific form of the distribution. Applying Csiszár’s inequality (Lemma 3, Appendix C.3) naturally introduces the $\\log |V|$ term as a bound on the maximum distributional shift. Further, as discussed in the former section (Concerns ...), $G(\\sigma)$ also results from a tight analysis. Together, $G(\\sigma)\\log |V|$ forms a general upper bound on noise impact.\n\nWe will clarify this motivation in the revised version.\n\n# Refinement of empirical method}\n> Reviewer comments (Claims And Evidence, Empirical evidence, Other Strengths And Weaknesses):\n> 1. [...] there is a simpler, better method available if one more naturally combines the two features, vocabulary restriction and PTA.\n> 2. [...] by merging vocabulary restriction natively into some metric comparing public and private distributions.\n    \nThis is an insightful point. We acknowledge that metrics comparing public and private distributions can directly inform vocabulary restriction.\n\nOur goal, however, was to theoretically support Tang et al.’s empirical vocabulary restriction and refine it through PTA. Building on Theorem 2, we adopted a modular design to isolate each component’s role: vocabulary restriction narrows the output space, to reduce the noise impact, while PTA amplify token probabilities to increase divergence between the ground-truth and other concepts.\n\nWe appreciate the suggestion and see it as a promising future direction.\n\n# Empirical evaluation\n> Reviewer comment (Claims And Evidence, Empirical evidence): \n> 1. [...] to see a graph showing the degradation in accuracy as the privacy budget is tightened [...]\n    \nDue to space constraints, we showed results for $\\varepsilon=1$ and $8$ in the main paper. We agree broader coverage is important.\n\nTable 8 (Appendix F.4) includes results for $\\varepsilon=1,2,4,8,\\infty$ (following Tang et al., ICLR 2024), giving a clearer tren of how accuracy changes as privacy strengthens. Below is a summary for PTA on GINC:\n\n|$\\varepsilon=1$|$\\varepsilon=2$|$\\varepsilon=4$|$\\varepsilon=8$|\n|-|-|-|-|\n|$94.55_{\\pm 1.20}$|$95.17_{\\pm 0.82}$|$ 96.76_{\\pm 0.91}$|$96.85_{\\pm 0.97}$|\n\nWe will include accuracy curves in the revision to better illustrate this trend.", "claims_and_evidence": "(Caveat: Unfortunately I caught a cold over the weekend, and as a result have not had time to check the proofs. Therefore, this review is based on the main body of the paper and a quick skim of the proofs.)\n\n# Theoretical evidence\n\n1. The theoretical model seems plausibly correct given that assumptions: it is a reasonable generalisation of an existing Bayesian approximation to non-DP ICL. However, I have to admit I don't find it very elegant! Appendix C.2 has to introduce a whole pile of constants to approximate things about the Hidden Markov Model, so the C_delim \"constant\" in the main body theorem statement hides a bunch of things which are very far from constant, even in the approximate model. Similarly, G is also dependent on the LLMs involved.\n2. Actually the non-constant natural of C_delim and G really do need to be called out in the main text. When I was reading the main text I thought they really were constants, which is not correct, as is the theorem statements mislead the reader.\n3. My guess is that there are cleaner theorems hiding under the surface the theorems they stated, that might lead to improved methods. In particular, Theorem 2 in particular has a term involving the vocabulary size, but my guess is that this is artificial in order to present direct evidence for the success of Tang's method. If the prompts are sampled sufficiently closely to the public distribution on a reasonable metric, we should be able to get a bound that doesn't depend on the vocabulary size. The vocabulary size would play a role, but would not as directly show up in the theorem statement.\n4. This vocabulary size appearance then contaminates the empirical method, which combines *both* vocabulary restriction and PTA. My guess is that there is a simpler, better method available if one more naturally combines the two features.\n\n# Empirical evidence\n\n1. The empirical evaluation is good, and do support the improvement of PTA over the baseline.\n2. However, I would have preferred to see a graph showing the degradation in accuracy as the privacy budget is tightened: currently only two points along that curve are shown.\n\n# Summary\n\nOverall, I am happy with the paper! The fact that I think there is a better paper lurking under this one (with cleaner theory and empirics) still means this paper has good contributions, and I believe it should be accepted.", "methods_and_evaluation_criteria": "Yes, I am happy with the datasets chosen in section 5.", "theoretical_claims": "See the Claims And Evidence section above.", "experimental_designs_or_analyses": "The experimental designs are simple. The main issue with any DP method is that bugs could easily break the guarantees and result in fake, better results, but this is hard to rule out with certainty.", "relation_to_broader_scientific_literature": "Due to catching a cold immediately prior to the deadline, I don't have capacity to do a literature search, and unfortunately I don't have significant existing knowledge of the DP literature. Thus, while the paper's internal discussion of the literature appears good, I am unable to check whether important things are missed.", "essential_references_not_discussed": "Due to catching a cold immediately prior to the deadline, I don't have capacity to do a literature search, and unfortunately I don't have significant existing knowledge of the DP literature. Thus, while the paper's internal discussion of the literature appears good, I am unable to check whether important things are missed.", "other_strengths_and_weaknesses": "Discussed above, but to summarise: both the theorems presented and the final method, while useful contributions, appear non-natural. I expect there are better versions of both theorems and methods, in particular by merging vocabulary restriction natively into some metric comparing public and private distributions.", "other_comments_or_suggestions": "N/A", "questions_for_authors": "N/A", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "FN3P8zoNN4", "reviewer": "Reviewer_DiNj", "summary": "This manuscript explores Differentially Private In-Context Learning (DP-ICL) to mitigate leakage risks in ICL. The authors first provide a theoretical analysis for a prior work (Tang et al., 2024) using a Bayesian analysis, where Tang et al. studied generating synthetic demonstrations by adding variance-tuned noise to the next-token probability obtained from an LLM prompted with the original demonstrations. Based on the authors' theory, they identify how the added noise to ensure DP affects the LLM’s ability to infer the ground-truth concept. Accoradingly, two insights for improving DP-ICL are derived: (i) Reducing the vocabulary size lowers the noise-dependent threshold and (ii) Increasing the divergence between concepts, by employing another next-token probability distribution that enlarges the gap between the ground-truth and any other concept. The authors also propose Plausible Token Amplification (PTA) to improve the performance of DP-ICL and empirically verify its effectiveness.", "questions": "", "limitations": "", "rating": 4, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "# Unclear definition of \"concept\"\n>  Reviewer comment (Other Strengths And Weaknesses, Weakness): \n> 1. The term \"concept\" in the introduction needs clearer demonstration. It can improve the readability of the introduction.\n\nThank you for pointing this out we had not noticed this readability issue. In our context, a concept refers to the latent rule or semantic mapping that connects inputs to outputs in demonstrations. This underlying concept governs the token transitions in the demonstrations and is implicitly inferred by the language model during In-Context Learning (ICL).\n    \nIn the revised version, we carefully clarify and introduce the term “concept” in Section. 1. \n\n# Missing comparison with related works\n> Reviewer comment (Other Strengths And Weaknesses, Weakness): \n> 1. Missing empirical comparison with: (1) Wu et al. (ICLR 2024) and (2) Hong et al. (ICLR 2024).\n\nThank you for pointing out these relevant works.\n    \n(1) Wu et al. (ICLR 2024)\n    \nWhile their method is indeed related, it directly adds noise to the next-token probability distribution at test time for each classification query. \nAs a result, the noise variance must scale with the number of test queries to ensure a fixed $(\\varepsilon,\\delta)$-DP.\nIn contrast, the noise variance in our method (and Tang et al.'s) remains fixed—regardless of the number of queries thanks to the post-processing property of DP: once a prompt satisfying $(\\varepsilon,\\delta)$-DP is generated.\nThis fundamental difference in design makes direct comparison challenging, thus we did not include their method in our evaluation.\n    \n(2) Hong et al. (ICLR 2024)\n    \nWe agree that DP-OPT, proposed by Hong et al., is conceptually similar to our approach, as it generates differentially private prompts once and reuses them to evaluate test queries. During the rebuttal period, we conducted an additional empirical comparison using the same Vicuna-7B-v1.5 model and TREC dataset setup as used in their study. The comparison results are summarized in the table below. \n\nTo ensure fair comparison, we report both our replicated results and the original values for DP-OPT from Table 3 of their paper, formatted as (replicated / original). This is because our replication was limited by computational constraints and a limited understanding of DP-OPT’s hyperparameters. We followed their appendix settings for $\\varepsilon=8$ and extended them to $\\varepsilon=1$ using $\\epsilon_0 = 0.1$ from their Table 5. Additionally, differences in prompt format remain. Therefore, this comparison may not fully reflect the method’s optimal performance.\n\n|$\\varepsilon$|Method|Accuracy|\n|-|-|-|\n|1|PTA (Ours)|$77.84_{\\pm2.83}$|\n||Tang et al.|$75.60_{\\pm2.05}$|\n||DP-OPT|$47.8_{\\pm0.0}$ / N.A.|\n|8| PTA (Ours)|$76.28_{\\pm2.92}$|\n||Tang et al.|$73.84_{\\pm5.44}$|\n||DP-OPT|$60.76_{\\pm1.27}$ / $65.3_{\\pm4.3}$|\n\nWe present below our interpretation of the experimental results:\n    \n- Even under the same evaluation setup, both our proposed PTA and Tang et al.'s DP-ICL acheieve high accuracy. This confirms the competetive performance of PTA compared to a strong DP-ICL baseline. \n    \nTo further support the numerical results, we highlight a key behavioral differences between DP-OPT and our approach at $\\varepsilon=1$. \n    \n- As discussed in Section 5.2 of their paper, DP-OPT tends to output only the instruction without demonstrations as the private prompt satisfying $(\\varepsilon,\\delta)$-DP guarantee with $\\varepsilon=1$. In such cases, the method method asymptotically converges to zero-shot prompting, limiting the practical utility of private demonstrations.\n    \n- In contrast, our method generates in-context demonstrations that, while potentially noisy, remain informative beyond the instruction even with $\\varepsilon=1$. This may allow our approach to consistently outperform zero-shot prompting, especially in high-privacy regimes where DP-OPT yields only marginal gains.\n\nWe will include these numerical results and their interpretation in the revised paper. \n\n# Performance investigation using GPT4-o\n> Reviewer comment (Other Strengths And Weaknesses, Weakness): \n> 1. [...] How will the PTA perform on modern LLMs such as GPT4? \n\nWe believe that applying our method (as well as that of Tang et al.) to models such as GPT-4 accessed via the OpenAI API poses challenges from a privacy evaluation perspective. At this moment, the API does not provide access to the full token probability distribution, instead returning only a limited set of top tokens. Since the selection of these tokens depends on the full (unobservable) distribution, it may lead to unintended privacy leakage.\nMoreover, as this selection process is a black box, it is practically infeasible to assess its differential privacy guarantees. Given the current API constraints, we consider rigorous privacy evaluation using GPT-4 constraints to be challenging at this time.", "claims_and_evidence": "The claims made in this submission are supported by convincing evidence.", "methods_and_evaluation_criteria": "The proposed methods indeed make sense for the problem.", "theoretical_claims": "The proofs for theoretical claims seems correct.", "experimental_designs_or_analyses": "The experimental designs and analyses are soundness.", "relation_to_broader_scientific_literature": "N/A", "essential_references_not_discussed": "N/A", "other_strengths_and_weaknesses": "**Strengths**\n1. This manuscript is overall well-written with clearly organized.\n2. The authors provide theoretical evidence (based on Implicit Bayesian Inference) supporting Tang et al.’s empirical method in Differentially Private In-Context Learning.\n3. This paper also introduce a refined method PTA for modifying next-token probability distribution accorading their theoretical insights.\n4. Extensive experiments empirically demonstrate the effectiveness of PTA.\n\n**Weaknesses**\n1. The term \"concept\" in the introduction needs clearer demonstration. It can improve the readability of the introduction.\n2. Missing emprical comparison with:\\\n      Wu et al. Privacypreserving in-context learning for large language models. ICLR 2024\\\n      Hong et al. DP-OPT: Make large language model your privacy-preserving prompt engineer. ICLR 2024\n2. The authors verify their method on relatively small LLMs such as GPT-2, Llama2-7B. How will the PTA perform on modern LLMs such as GPT4?", "other_comments_or_suggestions": "I have no more comments or suggestions.", "questions_for_authors": "Please see the weaknesses.", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "3YRnqtxcz4", "reviewer": "Reviewer_GXLu", "summary": "The paper introduces Plausible Token Amplification (PTA), a novel approach designed to improve the accuracy of Differentially Private In-Context Learning (DP-ICL) by refining the process of generating differentially private synthetic demonstrations. The paper also presents a theoretical guarantee of the distinguishibility of the latent concepts when noises are injected into the next-token-prediction distribution to ensure DP properties. The proposed PTA is aimed to make the latent concepts more distinguishable, thus improving the performance of generated DP demonstrations. Empirical effectiveness has been shown on several text classification datasets.", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "# Interpretation of numerical experimental results} \n    \n> Reviewer comments (Claims And Evidence, Questions For Authors): \n> 1. DBPedia has significantly higher performance without the proposed KL divergence, which is an essential part of the proposed PTA. There is no explanation for this.\n> 2. Why does DBPedia have significantly higher performance without the proposed KL divergence?\n \nThank you for pointing this out. We agree that the performance degradation on DBPedia when using KL divergence requires clarification.\n\nAs shown in Equation (11), PTA is fundamentally designed to amplify tokens distinctive to the ground-truth concept. The KL divergence term is introduced as an auxiliary regularizer to ensure that the modified token distribution does not deviate excessively from the original LLM next-token probability distribution. While not the core objective, this regularization can help stabilize training and preserve plausibility, contributing to improved performance on datasets such as AGNews and GINC.\n    \nHowever, as with many regularization techniques, the KL term does not consistently improve accuracy. In some cases, it may act as a constraint that limits useful adaptation to the target distribution. We suspect this effect may be present in DBPedia, though further analysis would be needed to pinpoint the exact cause.\n\nWe will add this clarification in the revised version.\n\n# Lacking baseline methods\n\n> Reviewer comments (Claims And Evidence, Questions For Authors):\n> 1. [...] Not sure if there could be more baselines to compare.\n> 2. [...] Are there any other DP-ICL baselines that you can compare PTA with?\n\nWe agree with these comments. A similar suggestion was also raised by another reviewer (DiNj). In response, we conducted additional experiments during the rebuttal period using DP-OPT (Hong et al., ICLR 2024), which is conceptually similar to our approach in that it generates differentially private prompts once and reuses them for evaluating test queries.\n\nFor a detailed discussion, please see our response to  Reviewer DiNj under “Missing comparison with related works.”\nWe will include the new experimental results and their interpretation in the revised version of the paper.\n\n(Hong et al., ICLR 2024) DP-OPT: Make large language model your privacy-preserving prompt engineer.\n\n# Effect of approximation in Equation. (12)\n> Reviewer comments (Claims And Evidence, Theoretical evidence): \n> 1. The claim in Equation (12) is pretty hand-waving without any analysis of the closeness of the approximation. [...]\n> 2. Can you provide some analysis on Equation (12) and the effect of having this approximation?\n\nThis is a good question. \nAs you noted, PTA is based on the following approximation in Equation~(12):\n$$\n\\log \\frac{p(o = v \\mid \\theta^*)}{p(o = v \\mid \\theta)} \\approx \\log \\frac{p(o = v \\mid S_{\\text{priv}}^{(i)})}{p(o = v \\mid S_{\\text{pub}})}. \\hspace{10pt} (12)\n$$\n\nWe approximate the LHS of Equation (12) since it is intractable to compute directly.\nThis intractability arises from the fact that $\\theta$ and $\\theta^*$ are not directly observable as they are latent variables, making it impossible to evaluate the likelihoods $ p(o = v \\mid \\theta^*) $ and $ p(o = v \\mid \\theta) $ explicitly.\nTo address this, we approximate the LHS using the LLM’s next-token probability distribution conditioned by observable prompts, which are designed to reflect their corresponding latent concepts.\n\nTo explain how we approximate, we decompose the LHS of Equation (12) as follows:\n$$\n  \\log \\frac{p(o = v \\mid \\theta^*)}{p(o = v \\mid \\theta)} = \\log \\frac{p(o = v \\mid \\theta^*)}{p(o = v \\mid S_{\\text{pub}})} + \\log \\frac{p(o = v \\mid S_{\\text{pub}})}{p(o = v \\mid \\theta)}. \n$$\n\nFirst, the first term on the RHS is then approximated by $ \\log \\frac{p(o = v \\mid S_{\\text{priv}}^{(i)})}{p(o = v \\mid S_{\\text{pub}})} $, replacing the intractable $ p(o = v \\mid \\theta^*) $ with a quantity that can be computed using the LLM prompted by the private prompt $S_{\\text{priv}}^{(i)}$. \nAs detailed in Section 4.1, this is justified by the Bayesian interpretation of in-context learning from Xie et al., where such prompting induces a posterior concentrated around $\\theta^*$.\n\nSecond, we omit the second term in RHS to focus on amplifying tokens distinctive to $\\theta^*$, without explicitly penalizing competing concepts. This omission is plausible when the second term is small. This occurs when different concepts assign high probability to distinct sets of tokens. In such cases, tokens indicative of $\\theta^*$ are also unlikely under both $\\theta$ and the reference $p(o = v \\mid S_{\\text{pub}})$, making the omitted term negligible. To support this in practice, we construct $S_{\\text{pub}}$ using instruction-only prompts that avoid concept-specific content. This yields a neutral reference distribution and helps maintain separation across concept token distributions.\n\nWe will revise the paper to clarify this approximation strategy.", "claims_and_evidence": "Most of the claims are well-supported. I have a few concerns about the experimental results, which aim to show the superiority of PTA:\n\n1. DBPedia has significantly higher performance without the proposed KL divergence, which is an essential part of the proposed PTA. There is no explanation for this.\n\n2. Only one DP-ICL baseline is included. Not sure if there could be more baselines to compare.", "methods_and_evaluation_criteria": "Yes. Though the datasets could be updated to more recent/relevant ones like MMLU.", "theoretical_claims": "The proofs are not fully/carefully checked.\n\nThe claim in Equation (12) is pretty hand-waving without any analysis of the closeness of the approximation. The whole proposed algorithm is built on this equation.", "experimental_designs_or_analyses": "I have a few concerns about the experimental results, which aim to show the superiority of PTA:\n\n1. DBPedia has significantly higher performance without the proposed KL divergence, which is an essential part of the proposed PTA. There is no explanation for this.\n\n2. Only one DP-ICL baseline is included. Not sure if there could be more baselines to compare.", "relation_to_broader_scientific_literature": "The paper proposes a new DP in-context demonstration generation algorithm that performs better than the baseline.", "essential_references_not_discussed": "N/A", "other_strengths_and_weaknesses": "The paper is a nice combination of theoretical analysis and theory-inspired real-world algorithm.", "other_comments_or_suggestions": "N/A", "questions_for_authors": "1. Why does DBPedia have significantly higher performance without the proposed KL divergence?\n\n2. Are there any other DP-ICL baselines that you can compare PTA with?\n\n3. Can you provide some analysis on Equation (12) and the effect of having this approximation?", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Meta-review: This manuscript received favourable reviews from 3 reviewers. The reviews and discussions highlighted both strengths and weaknesses but the general tendency is in favour.

On the side of strengths, it was commented by a reviewer who is expert on the topic that the paper presents an approximate Bayesian model of DP-ICL (differentially private in-context learning). DP-ICL in general combines a public LLM with a private LLM to generate a number of low-privacy-leakage prompts, then uses those prompts for in-context learning. A previous paper (Tang et al.) used a simple vocabulary restriction method to improve DP-ICL; this paper uses their Bayesian model to explain why vocabulary restriction works, then present an improved Plausible Token Amplification method which achieves better empirical results. The other reviewers commented also that this manuscript is overall well-written with clearly organized, provides theoretical evidence (based on Implicit Bayesian Inference) supporting Tang et al.’s empirical method in Differentially Private In-Context Learning, introduces a refined method (PTA) for modifying next-token probability distribution accorading their theoretical insights, extensive experiments empirically demonstrate the effectiveness of PTA, and that the paper is a nice combination of theoretical analysis and theory-inspired real-world algorithm.

On the side of weaknesses, it was commented that it would be expected that there are better versions of both theorems and methods, in particular by merging vocabulary restriction natively into some metric comparing public and private distributions, that there were missing emprical comparison with some works, and the method could be tested on relatively small LLMs such as GPT-2, Llama2-7B. 

The rebuttals alleviated some concerns and the reviewers were satisfied, reiterating their positive evaluation of this paper.
Decision: Accept (poster)