Data-adaptive Differentially Private Prompt Synthesis for In-Context Learning
Authors: Fengyu Gao
Ruida Zhou
Tianhao Wang
Cong Shen
Jing Yang
Venue: ICLR 2025 Poster (2025)
Keywords: in-context learning
differential privacy
large language models
Primary area: alignment, fairness, safety, privacy, and societal considerations

Abstract: Large Language Models (LLMs) rely on the contextual information embedded in examples/demonstrations to perform in-context learning (ICL). To mitigate the risk of LLMs potentially leaking private information contained in examples in the prompt, we introduce a novel data-adaptive differentially private algorithm called **AdaDPSyn** to generate synthetic examples from the private dataset and then use these synthetic examples to perform ICL. The objective of AdaDPSyn is to adaptively adjust the noise level in the data synthesis mechanism according to the inherent statistical properties of the data, thereby preserving high ICL accuracy while maintaining formal differential privacy guarantees. A key innovation in AdaDPSyn is the *Precision-Focused Iterative Radius Reduction* technique, which dynamically refines the aggregation radius - the scope of data grouping for noise addition - based on patterns observed in data clustering, thereby minimizing the amount of additive noise. We conduct extensive experiments on standard benchmarks and compare AdaDPSyn with DP few-shot generation algorithm (Tang et al., 2023). The experiments demonstrate that AdaDPSyn not only outperforms DP few-shot generation, but also maintains high accuracy levels close to those of non-private baselines, providing an effective solution for ICL with privacy protection.

Published as a conference paper at ICLR 2025
DATA- ADAATIVEE DIFFERENTIALLY PRIVATE PROMPT SYNTHESIS FOR IN-CONTEXT LEARNING
Fengyu Gao" University of Virginia wan6jjevizginia.co
Ruida Zhou'
University of California Los Angeles ruidašg wal.aalglllla... ucla. edu
Tianhao Wang
Cong Shen
Jing Yang
University of Virginia
University of Virginia
University of Virginia
cianhao@virginia.. edu
congevirginia edu
yangginggvvrgiina... edu
ABSTRACT
Large Language Models (LLMs) rely on the contextual information embedded in examples/demonstaatoons to perform in-context learning (ICL). To mitigate the risk of LLMs potentially leaking private information contained in examples in the prompt, we introduce novel fata-adaptive differentially private algorithm called AdaDPSyn to generate synthetic examples from the private dataset and then use these synthetic examples to perform ICL. The objective of AdaDPSyn tively adjust the noise level in the data synthesis mechanism according to the inher- ent statistical properties of the data, thereby preserving high ICL, accuracy while maintaining formal differential privacy guarantees. A key innovation in AdaDP- Syn is the Precision- Frecision-Focused Iterative Radius Reduction technique, which dynam- ically refines the aggregation radius the scope of data grouping for noise addition based on patterns observed data clustering, thereby minimizing the amount additive noise. We conduct extensive experiments standard benchmarks and compare AdaDPSyn with DP few-shot generation algorithm (Tang et al. 2023). The experiments demonstrate that AdaDPSyn not only outperforms DP few-shot generation, but also maintains high accuracy levels close to those of non-private baselines, providing an effective solution for ICL with privacy protection.
adap-
INTRODUCTION
In-context learning (ICL) (Brown et al. 2020 Min et al. 2022) enables large language models (LLMss (OpenAT 2023) to adapt to domann-peecific information without modifying the pre-trained model. This adaptation is achieved by conditioning the model on a prompt, which contains an examples).
instruction and series of task-specific question-answer pairs (called demonstrations Using this prompt, LLMs can then generate responses that are tailored to the corresponding task. The ease of usage and cost-benefit of ICL have motivated the adoption of LLMs in several applications, such machine translation Sia and Duh 2023), code generation (Pourreza and Rafiei 2023 and customer service (Lee et al. 2022).
However, privacy is significant concern when incorporating users' data into prompts, especially in areas like healthcare and finance (Wang et al. 2023 Priyanshu et al. 2023 Duan et al., (2023), as this introduces risks of exposing sensitive personal information. To address this concern, existing works
(Wu et al. 2023 Tang et al. 2023 Duan et al., 2023 Carey et al., 2024 Hong et al. 2023) have explored approaches to mitigate these risks using the rigorous privacy safeguards provided by differ- ential privacy (DP) (Dwork et al.) (0066). Notably, Tang et al. (2023) proposed to generate synthetic few-shot demonstrations from the private dataset for in ICL inference and guarantee DP with respect to examples in the private dataset. This method uses the classic DP aample-and-aggregan framework (Nissim al. 2007 Papernot al.) [0166] 2018), partitioning subsampled private data into disjoint subsets, each of which is used in prompt for an LLM to generate tokens. These tokens
cco-frst author.

---

Published as a conference paper at ICLR 2025
Stage Generate synthetic few-shho demonstration AdaDPSya
Stuge Construct prompt
DP demenstrtion [R, -n
2 "New York"
City
A
Pyme
Perto
State
Posi
Covered poinrs
LA
+
LLM
City
LLN
Query
Times
Purk
gimaz
Prodict Desi-oukm
Establish turget radius ming Goodiadiius
Update trwunds target ieratively
Choc covarage before radius reduction
Project paints to the hall and prisutely aggregatc
probubilitios
Figure 1: Two-Stage framework for privacy- preseering ICL. In Stage 1, DP- PP-protected demonstrations are generated with AdaDPSyn, where we illustrate the process of generating the next token "City" following "New York". AdaDPSyn uses novel clustering approach dynamically aggreegate next-token probabilitics. The process iterates until Rihor demonstrations are generated. In Stage 2, the generated DP-protected demonstrations are combined with a user query to construct the prompt. The constructed prompt is then sent to an LLM and the answer is returned to the user.
are then privately aggregated, adhering to DP guarantees, to create synthetic demonstrations. This framework allows the synthetic demonstrations be used for an infinite number of queries without incurring any additional privacy costs.
The main design challenge in Tang et al. 2023 is aggregating the responses from LLM privately. Tang et al. (2023) used a data-independlent way of adding the same amount of Gaussian noise during private aggregation. However, since each token generated by the LLM can contain varying levels of private information, applying noise homogeneously across an entire sentence or document may achieve the optimal privacy-utility tradeoff in the ICL framework. Therefore, it is more strategic to design DP mechanisms that adapt the noise level in a data-adaptive manner. Intuitively, by adaptively adjusting the additive noise level based on the properties of responses for individual tokens, avoid adding unnecessarily large noise to tokens with high agreement predictability, which indicates low risk, thereby achieving improved utility for ICL. The main question we aim to answer is:
Can we design data-adaptive differentially private prompt synthesis algorithm to protect the private information contained the prompt data and effectively perform ICL?
In this work, provide affirmative answer this question. Our main contributions summa- rized as follows:
We introduce a new algorithm AdaDPSyn in Algorithm to generate synthetic seo-shot examples for use in ICL prompts (Figure D Similar Tang et al. 2023), AdaDPSyn begins by obtaining next-token generation probability vectors from an LLM using multiple subsets of private dataset, which will then be aggregated novelty of AdaDPSyn lies in our proposed nique, which adaptively adds noise level during aggregation by exploiting the cluster structure of the predicted distributions of the next token. Besides, we believe that our data-adaptive technique may be applicable various problems beyond prompt synthesis, thus of independent interest.
generate the next token differentially privately. The essential
Drrcision-Focusee Iterative Radius Reduction tech-
We conduct rigorous privacy analysis of AdaDPSyn and confirm it follows (c, SD- our analysis, we use the Rényi Differential Privacy (RDP) (Mironov) 2017) framework to track and tightly quantify privacy costs from the composition of AdaDPSyn's components across multi- ple iterations. By applying RDP composition rules and subsampling amplification, we establish theoretical privacy guarantees for AdaDPSyn.
We empirically evaluate the performance of AdaDPSyn against the DP few-shot generation algo- rithm proposed by Tang al. (2023) standard benchmarks. We demonstrate that our method outperforms this baseline across a plethora of privacy settings. For example, in the AGNews classification task under strict privacy level of 65.42%, higher than 60%74% by DP few-shot generation. In the information extraction task MIT- G 1, our method reaches 37.59% accuracy, compared 31.15% by DP few-shot genera- tion. Additionally, we show that our AdaDPSyn algorithm can closely match the performance of non-private baselines even in stringent privacy settings. For instance, at a strict privacy level of E = 1, our algorithm attains an accuracy of 65.42% on the AGNews task, nearly reaching the non- private baseline's accuracy of 65.92%. Similarly, in the DBPedia task, our method shows minimal performance drop-off compared to the non-private scenarios. These results not only underscore the effectiveness of our AdaDPSyn algorithm compared with indeieddeeendnnt methods, but also demonstrate its competitiveness with non-private solutions.
method achieves accuracy of
2

---

Published as a conference paper at ICLR 2025
2 RELATED WORK
Differentially Private In-Context Learning and Fine-tuning of LLMs. Duan et al. (2023) first study privacy leakage through membership inference attacks (MIAs) and suggest mitigating MIA risks using DP ensembling (Papernot et al. 2018)) on various model versions. Recent studies (Wul (ct al. [203] Tang ct al. [003] Duan et al. 2023; Carey et al. 2024) have developed methods based on DP ensembling (Papernot al.j (018) to preserve privacy of the underlying prompt data. No- tably. Tang et al. (2023) develop an algorithm that generates differentialyy private synthetic few-shot demonstrations from a private dataset for ICL inference, which serves as the baseline of this work and will be discussed in greater detail in subsequent sections. Hong et al. (2023) propose the DP- OPT algorithm that generates private and transferable instructions within prompts on the client side to be used with cloud- lluu-hosted LLMs. Carey et al. (2024) focus on protecting tabular data used for ICL. We note that all of those works (Tang et al. 2023 Carey et al. 2024] Hong et al.) 2023) de- sign private aggregation methods in a deta-independent way, i.e., adding the same amount of noise during private aggregation.
Recently, Wu et al. (2023) and Duan et al. (2023) study differentially private ICL with data- dependent privacy analysis. [Wu et al. (2023) propose DP inference by privately aggregating results from multiple queries using disjoint sampled demonstrations. They use the classic propose-test- relcase (PTR) paradigm (Zhu and Wang 2022) to select the top-K tokens from LLM outputs. If the vote count difference between the K- and (K + 1)-th highest tokens exceeds two, the tokens can be released without further privatization. However, ICL tasks can involve an unlimited number of queries, and Wu et al. (2023) consume the privacy budget per query, limiting the number of queries that can be answered within a given budget.
Duan et al. (023) assume the existence of an unlabeled public dataset, which contrasts with our approach that requires no public data. In their method, an ensemble of teacher models uses private majority voting label this public dataset. The labeled data then helps construct private prompts. Following Papernot et al. (2018), they focus on scenarios where high agreement among teachers can reduce privacy costs below data-independent bounds. When teacher agreement is low, they discard the public data. In contrast, our method is better suited for scenarios where assuming the availability of unlabeled public data with distribution similar to private data unrealistic, such as in healthcare or industrial applications. Moreover, Duan et al. (2023) mainly focus on text classification tasks with a restricted label space, while our method applies to a broader range of tasks.
On the other hand, several studies have focused on private fine-tuning of LLMs (Yu et al. 2021 Li et al. [02TT] Chen et al.) 2024, (Tang et al. 2024 ZZhang et al. 2023 He et al. 2022). Besides, Majmudar et al. (2022) introduce DP at the decoding stage of a tre-trdined LLM.
Adaptive Differential Privacy. Adaptive differential privacy primarily focuses on privately cal- ibrating noise to the local sensitivity, which is detaset-dependden function and is much smaller than the global sensitivity. Two representative solutions include the smooth sensitivity framework (Nissim et al. (2007) and the propose-test-rllent (PTR) framework (Dwork and Lei| 2009). The main idea of the smooth sensitivity framework is to add noise calibrated to the smooth sensitivity, an upper bound on the local sensitivity which changes slowly between neighboring datasets (Bun and Steinke, 2019: Gonem and Gilad Bachrachhh 2018; Fletcher and Islam| 2017 Zafarani and Clifton, 2020 Hamman et al. 2023 Sun et al. 20220). The PTR framework involves proposing bounds of the local sensitivity and testing its validity. If the test is passed, the noise is calibrated according to
the proposed bound (Thakuraa and Smith. 2013 Liu al. 2022 Redberg et al. 2023 Wang et al.,
2022 Liu et al., 2022).
In this work, we release confidence bound of the local sensitivity in a differentially private man- ner, and calibrate noise accordingly, similar to the idea in prior studies (Blocki et al., 2012 Ka- siviswanathan et al.] 2013) WWngg] [0188: Decarolis et al., 2020p. In this body of research, Blocki iet al. (2012) and Kasiviswanathan et al. (2013) focus network data. Wang (2018) revisits the DP linear regression problem. Decarolis et al. 2020) study the Latent Dirichlet Allocation (LDA)
model. Our focus is on the ICL domain, where we develop a novel clustering method and Precision- Focused Iterative Radius Reduction technique to address domain -emaiff challenges.
Differentially Private Synthetic Text Generation. Our work falls within the broader scope of DP synthetic text generation, which typically requires generating large volumes of synthetic data. There is line of work on DP synthetic text generation through private fine-tuning Yuu et al.,
3

---

Published as a conference paper at ICLR 2025
2022
Mattern et al. 2022; Mireshghallah et al. 2022 Carranza et al. 2023: Yu al. 2024 Wu
ct al. 2024). SeqPATE (Tian et al. (0022) and Submix (Ginart et al, 2022 are methods based 2016 2018) for text generation, which utilizes ensemble of teacher models trained on private data subsets to fine-tune a student model. Another direction (Feyieeann et al. 2020 Xu al. 2020: Du et al. 2023) Utpala al. 2023) focuses sanitizing user texts locally before server submission based on local differential privacy (Chatzikokolakis et al.] 2013) While this approach typically reduces text utility, recent studies (Chen et al. [022] Arnold et al., a Mireshhhalaa et (022) propose to enhance utility by incorporating inherent properties of language such as semantic similarity (Chen et al. (0022). context (Arnold al.) 2023b) and syntax
on PATE (Papernot et al.
(Amold et al. 2023a Mireshghallah al.) (0022)
3 PROBLEM DEFINITION, THREAT MODEL, AND NOTATIONS
In-context learning. Given query a candidate answer set (label set) y and a pre-trained large language model LLM such as GPT (Radford et al. 2018; OpenAl, 2023), ICL aims to predict a label y E y of query I. using LLM conditioned on Ylshot demonstrations C (<11.8) (x/, 26),.... ..., (I/mam Vrrna) ]. where (z4, v is an input-label pair.
In this paper, we consider both classification and information extraction tasks. For classification we first compute the probability of each label
tasks with a restricted label space y = {yI..... , }. Y/ E Y' using LLM as P (1 c, Then we predict the final label y by selecting the label with the highest probability from the label set V, i.e., y/ = arg maxy, Ey P (y: C. For information extraction tasks, the label space Y' is unrestricted, and can include any sequence of tokens from the LLM's vocabulary. In these tasks, we predict y by having LLM generate a sequence of tokens until it produces special end-of -e-uuencee (EOS) token, marking the completion of the output.
Differentially private ICL, Our objective is to protect the privacy of demonstrations C S D in the prompt against an adversary that aims to access infer private information about the demonstra- tions. Since ICL tasks may encounter an unlimited number of queries, to protect the privacy of the dataset pryv. we adopt a differentially private data synthesis approach to generate synthetic few-shot examples C = [ž,.... .... m J. where 2, (T,, Be), from the underlying distribution of Dpuv while satisfying (e, 8) differrenti privacy on the private dataset Dpriv- For each ICL. task, we generate task-specific synthetic examples C with the help of an LLM and a private dataset Dpri- Then ICI. can performed using demonstrations from in a prompt tailored to each task. By default, we incorporate all demonstrations from C in a prompt for each task.
We formally define (s, ddddffrrrltt privacy ((e, 8DD as follows.
Definition ((e, Difffffrrettt Privacy (Dwork et al. (006a)). A randomized algorithm A is (e, 8)- differentially private for any two neighboring inputs DD and D' that differ by a single entry and any set S of possible outputs: (P[A(D)= 8] I e (T(()) E S] 5
4 PROPOSED METHOD
We use two-stage framework to perform differentially private ICI., illustrated in Figure D Gen- erally speaking, in Stage 1, we generate DP synthetic few-shot demonstrations C' (8 .namm based on the private dataset 2 privi and in Stage 2, we use these synthetic demonstrations for ICL.
The main challenge of this framework lies in the DP synthetic data generation (Stage 1). To maintain DP, a PATE-like framework is utilized, similar TTng et al. (2023). Take the generation of synthetic demonstration غ = (ă, Ø) E C as an example. First, label E ) is randomly selected independently of private dataset D Prive and its corresponding demonstration ā is generated token by token, starting from an empty string ã =". The next token for 3 is generated by aggregating probability vectors P ........... : Ppny: each of which is calculated by an L.M taking some prompt as
input. Each prompt is a concatenation of a subset of examples (in a reverse order (yt, x:))) from the private dataset D peiv {2,, }, the synthetic label ÿ and the currently generated string Ø. Due to the dependence of the probability vectors on private dataset D priv. DP aggregation is required, and a classic way to achieve this is by adding noise (e.g., Gaussian mechanism) as in Tang et al. 2023).
4

---

Published as a conference paper at ICLR 2025
Our approach is motivated by hypothesis that the next-token predictions by different examples approximately reach a consensus. Once this hypothesis holds, the key innovation of our approach is to leverage this feature and reduce noise levels during aggregation in data-adaptive manner. We verify the hypothesis quantitatively and tackle the key challenge in the following two sections, respectively.
4.1 CONSENSUS BEHAVIOR MEASURED BY CLUSTERING
We quantitatively measure the degree of consensus among the next-token generation probability vectors Ppav..... ................................ .PPpy Specifically, we approach this by visualizing consensus through the geomet- ric concept of enclosing these vectors within minimal enclosing ball, defined where r is the radius, e is the center and E (0, 1] represents the required portion of vectors covered in the ball. For given coverage requirement p. smaller indicates tighter grouping, reflect- ing high consensus among the model outputs. We hypothesize that these next-token generation probability vectors are typically highly clustered in a ball with a small radius r.
(r, c, p)-ball,
To verify the hypothesis, we conduct experiments using the DP few- shot generation algorithm (Tang et al. 2023), and report the radius r of the minimal ball that encloses at least 80% (p = 0.8) of the next-token probability vectors generated by using different private examples in Table 1 For determining a small radius r that contains least 80% of the points, we adopt the GoodRadius algorithm in Nissim et al. (2016). We conduct experiments on three classifi- cation tasks: AGNews (Zhang et al.) 2015), DBPedia (Zhang et al.) 2013) and TREC (Voorhees and Tice| (2000), as well two infor- mation extraction tasks, MIT-G and MIT-D (iu et al. 2012). using
Table I: The mean and standard deviation of r over 5 runs with different random seeds.
Task
radius r"
AGNews 0.06o.02
DBPedia
0.05g.01
TREC
0.12o.01
MIT-G
0.15p.01
MIT-D
0.14o.01
the Llama-2-7b-hf model (Touvron et al. 2023 Details of the DP few-shot generation algorithm parameters can be found in Table 12
As shown in Table ! the measured radius r, ranging from 0.05 to 0.15, is much smaller than /2/2. the radius of the minimal ball that contains the probability simplex. These results confirm a high degree of clustering among the model outputs. Intuitively, if we can access such a ball of small radius differentially privately, we can perform differentially private projected mean aggregation that projects the probability vectors to the ball and calculates the projected mean with additive Gaussian noise. The noise level is determined by the sensitivity 2r. Note that in Tang et al. (2023). without leveraging the clustering behavior of the data, a much higher noise level corresponding to sensitivity v2 is employed. Comparing these two cases, the sensitivity 2r is approximately 5x to 14x smaller than /2, thus leading to more accurate aggregation due to lower noises. The key challenge is then how differentially privately access small ball that contains majority number of probability vectors and perform the differentially private aggregation correspondingly. To tackle this challenge, we propose a novel Precision-Focuseee Iterative Radius Reduction technique.
4.2 PRECISION-FOCUSED ITERATIVE RADIUS REDUCTION
Building on the observation that next-token generation probability vectors from the LLM are highly clustered, utilize intuitive approach to adaptively adjust the noise level during aggregation: first locate the minimal ball covering most vectors under DP and then project all points to this ball in fz-norm to bound the influence of each point, thereby minimizing noise addition. This method, which adaptively leverages the inherent structure of the probability vectors, is essential to the success of our proposed method.
The task of finding a minimal enclosing ball under DP is known as the DP 1-clustering problem in the literature (Nissim al. 2016). However, existing methods (Nissim al. 2016 Nissim and Stemmer, 2018: Ghazi et al. 2020) are hard to implement and computationally expensive.
To this end, we propose a novel technique called Precision-Focused Iterative Radius Reduction. We start with a large radius R and judiciously reduce it towards a small target radius r through iterative refinement. The target radius r obtained under DP constraints using a tractable subroutine
https://huggingeee
11ma 1,1 ama 2- hf
5

---

Published as a conference paper at ICLR 2025
GoodRadius from DP 1-clustering (Nissim et al. 2016), which provides a threshold such that the designed radius should never go below. The reduction of radius R is carefully monitored by coverage checks, which ensure the majority of the probability vectors covered by a ball with that radius. The center of the ball is efficiently obtained by private projected mean estimation. This dynamic adjustment of the ball ensures it is minimized effectively according the distribution of the points along the adjustments, The amount of noise required for private projected mean estimation can be reduced, thus improving the quality of the synthetic demonstrations and the performance of ICL. We elaborate this PrecisionFFocusee Iterative Radius Reduction technique in Section 4.3
4.3 ADADPSYN ALGORITHM
We now introduce the proposed AdaDPSyn algorithm (Algorithm D. which generates DP synthetic few-shot examples from the private dataset Ppav. For given label y randomly selected from the label set without replacement, AdaDPSyn sequentially generates one token at a time, starting from an empty list. Each token generation begins with the Next Token Generation subroutine (Line 4 Roughly speaking. the Next Token Generation process (Tang et al., 2023) involves sampling MN examples with label i from the private dataset Dpivv dividing them into M disjoint subsets, and then using these subsets as demonstrations predict the next token's distribution Pp using an LLM. The vocabulary is restricted to S containing the top-K most probable tokens, which are determined from next-token probabilities generated only from instructions without using any private data. Details of Next Token Generation can be found in Appendix [A.]] Then we privately aggregate p pir...... PPayy using our Precision-Focused Iterative Radius Reduction technique (Lines 21.. which consists of four critical steps:
Step 1: Establish Target Radius Differentially Privately. The process begins by setting target radius r using the GoodRadius subroutine (Nissim et al. 2016) in Line [3] GoodRadius is a sub- routine used in DP 1-clustering methods (Nissim et al. [016:] Nissim and Stemmer 2018). which identifies a radius that can encompass at least a fraction p of the data points under (a, -RDP constraints. In this work, we set p 80%. Details are provided in Appendix A.2
Step 2: Projected Mean Estimation Using Gaussian DP Mechanism. For a probability simplex in Rd its radius is v2 Thus, set R < v2/2 (Line 6 initially. We initialize projected points Ff +- Ppriy ,...., M (Line 7. and estimate mean of (ipmvo-.-- g using Gaussian DP mechanism (Line S i... Ppriv + M + (0, where 02 is the noise multi-
plier. Then we map Ppni back onto the probability simplex, i.e., Ppriv + max(ppe 031la (Line 9).
max(paa. 0)
Next, we reduce R towards the target radius r iteratively, ensuring that it covers a sufficient amount of probability vectors while satisfying DP (Lines] 11 2T). During the iterative process, which takes at most 7 iterations, each step starts with radius coverage check detailed in the following paragraph.
Step 3: Radius Coverage Check Using Gaussian DP Mechanism. We use Gaussian DP mecha- nism to check whether sufficient number of the original probability vectors p Pry remain within small radius from Ppriv (Line 12p. Specifically, the check evaluates whether the ball with
center Ppri and radius r + 2XRe, v can cover at least μ.M of the points p ... P PM where À M
is hyperparameter, Ø₁ scales the Gaussian noise introduced to Parv in Line 8 or Line 20 K is the dimensionality of the probability vectors, and μ E (0, 1]. We set μ 0.55 in this work. The term
2XRo, vK represents an additional margin on the radius to accommodate the spread introduced by Gaussian noise added to Ppriv in Line or Line 20 ensuring data coverage despite the distortion caused by the noise.
M
Step 4: Update Radius towards Target Radius. If the radius coverage check in Line 12 reveals that fewer than μMM vectors are within the defined radius, the algorithm will stop reducing the cur- rent radius R. Otherwise, the algorithm proceeds to adjust It downward (Line 15 18 i.c., R + +
For a bounded region R C Rdd we define its diameter as diam(R) sup,,yER || wll- and its radius as half of the diameter, i.e., RRd(R)- {diam(R). The definition of diameter coincides with the definition of sensitivity for the aggregation (summation) of a utility function, thus the radius can be interpreted as half of the sensitivity factor.
6

---

Published as a conference paper at ICLR 2025
Then we project next-token probability vectors (p .... Ppriv J to E2-ball defined by ra- dius R and centered at Ppriv (Line 19,, i.e. Ppetv = Ppeiv + (Pedt - Panis) max 1, Il -ppalll
2AR VR M
R
,,..., M. This operation ensures that the fz-sensitivity of the term Ene Pert is most 2R. Fi- nally, we estimate the mean of the projected points (ppris...., TM Pprit) Ppriv using Gaussian DP mechanism
(Line 20), i.e., Ppriv + I7 (EM Ppay + (0, off As Rt decreases, the amount of noise added to Ppriv is reduced accordingly. We then map Ppriv back onto the probability simplex, i.c., max((pps .))
Ppeiv || [p) (Line 21b.
The process of radius refinement concludes under any of the following conditions: (1) the maximum allowed number of iterations, T. is reached: (2) further reduction in radius fails to cover the mini- mum required proportion of vectors (Line 12 ; (3) the current radius R is smaller than r+ 2X, Ro, (Line 15). Once the radius refinement process concludes, we select the next token for the synthetic sequence as arg maxjes Ppeiy [j] where S is the vocabulary of size K, and this token is appended to what is generated so far. This continues until the sequence reaches the predefined maximum limit, Tmax. of tokens would like to generate.
Remark (Comparison with Tang et al. (2023)) The main difference between our method and that of Tang et al. (023) lies in the innovative approach we take toward the private aggregation of the next-token generation probabilities Prrv.... M Instead of directly using the Gaussian DP mechanism for aggregation as in Tang et al. (2023), our approach introduces an advancement through the Precision-Focuset Iterative Radius Reduction technique (Lines 5 21 This technique allows noise to be added in a data-adaptive manner, effectively adapting the noise level to the degree of agreement among the models. Empirically, we evaluate the performance of our algorithm against Tang et al. (2023) in Section 5. to demonstrate the effectiveness of our method.
4.4 PRIVACY ANALYSIS
Theorem 1. Algorithm D is (e, differrentil private.
Proof Overview. We adopt the commonly used Rényi differential privacy (RDP) (Mironov 2017) track the privacy cost in our algorithm, as it allows to tightly quantify the privacy guarantees from the composition of multiple mechanisms. Our proof mainly consists of three steps. First, we show that each iteration of the algorithm is (a, -)-DD. In each iteration, our algorithm consists of
components: one instance of (a:, To) -RDP algorithm GoodRadius (Line5).. at most (T + 1) instances of (a, Ti R-DD projected mean estimation using Gaussian DP Mechanism (Line 8 and Line 20) and
most T instances of (a, 72) RRDP radius coverage check using Gaussian DP Mechanism (Line 12 We apply the composition property of RDP to ensure the privacy guarantee in each iteration, that is, we ensure that 7 To + (? + 1)7) + Tr2, Next, since the Next Token Generation subroutine (Line 4 involves drawing .MN samples from the dataset Dpeiv. there is a privacy amplification by subsampling at each iteration. Finally, we compose privacy loss across all the Tmax iterations of our algorithm using composition theorems. We rely on the conversion lemma (Balle et al. 2020) to convert the RDP guarantee back to DP notions. We provide full proof in Appendix
EXPERIMENTS
Datasets. We study text classification on three datasets: 4-way news classification AGNews (Zhang jt al. 2015), 6-way question classification TREC (Voorhees and Tice] 2000), and 14-way topic classification DBPedia (Zhang et al.] 2015). For information extraction, study the MIT Movies 10k slot-filling dataset (Liu et al. 2012), which includes movie genre (MIT-G) and director name (MIT-D) slots. Additional dataset details are available in Appendix C
Setups. We use the synthetic few-shot demonstrations {ā,.... ,Zaaa } from Algorithm I as in- put demonstrations in ICL for the aforementioned downstream tasks. We fix Rahots 4 by de- fault, generating 4-shot demonstrations (randomly without replacement from the label set) for ICL. We use Llama-2-7b-he model (Touvron et al. 2023) as our pre-trained L.M to generate synthetic
7

---

Published as a conference paper at ICLR 2025
Algorithm 1 AdaDPSyn
1: Input: Private dataset: D Dpnv, label: maximum token count: Tmax, LLM: LLM(.), noise multiplier: 01, 02, number of disjoint subsets: M, samples per subset: N, reduced vocabu-
lary size: K, hyperparameters: and T.
2: Initialize: Set σ [].
3: for = 1 to T maa do
4: Ppav...... .P.. Ppri
MextTokenGeneratti (Dpri: : D. LLM(),, M, 5: r GoodRadius
Ppav PM, 00) > Establish Target Radius
6: R V2/2
7: Pprio < Ppriv i = M
8: Ppriv 1
M7 (2 Ppriv NO, (10,412071)
Ppdv < (pax((pae.0)
9:
for max Ppol. T do
11:
Ê < the count Ppn
Ppnv
within a éz-ball centered at Parv with radius r + 2NR
M
12:
if ++N(00,3) JMM then
break end if
D Radius Coverage Check
14:
15:
<r+
2AR then M
16:
break
17:
end
18:
R r 2ARO,VK
Update Radius towards Target Radius
Ppmi t Ppriv + (ppriv Poriv) maxx
PPvn -
, M
Ppii (E + +N(00,
DP Projected Mean Estimation
max(Pann.0)
21:
Parie max (pper.
22:
end for
23:
<- arg maxjes [i]
24:
Ø -- ++ [w]
25:
end for
26:
return 8.
demonstrations We use the same prompt format during ICL following Tang et al. 2023 (see Ap- pendix C. For ICL. downstream tasks, and MIT-D, and GPT-4o mini for TRE For DP algorithms, we follow the common practice to set the privacy budget 8 1/ [Privl Tang al. 2023 Hong al. (023).
2lama-2-7b-hf for AGNews, DBPedia, MIT-G,
Baselines. We compare our AdaDPSyn algorithm with DP few-shot generation in Tang et al. 20233) which uses data-independent approach of adding the same level of Gaussian noise during aggre- gation. Hypermarameters in DP few-shot generation are detailed in Table 12] including the number of subsets M, the number of data samples per subset N, the number of tokens T Tmax, and the reduced vocabulary size K. To ensure fair comparison, we select these parameters for DP few-shot genera- tion based on the guidance in Tang et al. (003)) as detailed in Appendix C.5 We then use the same values of M, N, Tmux and K for our Ada MPSy without any additional hyperparameter tuning.
As fully private baseline E = O, we follow Tang al. (2023) to generate synthetic 4-shot demon- strations using purely instructions without any private date We consider two non-private baselines
2023) uses OpenAl's API logprobs parameters with value of 100, which currently supports maximum value 5. overcome this, we use Llama-2-7b-BB model vLLM platform (https://githhin
NNett Token Generation (Tang
com/ 1 wttpo///wl-oooee////ooaooooo 1m) which offers a compatible API, as suggested
in Tang et al. (2023).
"When using Illma-2-7b-hff for TREC. observe high standard deviation in the results (around 10), likely due the complexity the task. GPT-4o mini reduces the standard deviation to around
"Tang et al. (2023) demonstrate that in some applications, M. generate relevant few-shot demonstra-
tions using only instructions and perform competitively with DP few-shot generation algorithm.
8

---

Published as a conference paper at ICLR 2025
Table 2: 4-shot ICL performanee the test set of downstream tasks with baselines. Results show the mean and standard deviation of accuracy over runs. Our private solution with various privacy levels 1, 2, 4, uses AdaDPSyn to generate DP synthetic fow-shot demonstrations for ICL, comparison with the DP fow- shot generation algorithm (Tang et al. 2023 O represents a fully private solution. ε = oc serves as the non-private baseline.
Dataset
Method
c
8 2
2
4
==8 8
= 00
DP few-shot generation
60. 60.744.09
62.64 1822
62. 02.701..0 .30
63.181.28
AGNews
61.38
65.921.18
AdaDPSyn
65.42
65.52
65.84 1.03
65.921.02
DP shot generation
64.681.42
64.781.22 :22
64.922.99
65.2662.1
DBPedia
63.923.07
69.061.40
AdaDPSyn
66.761.45
67.48 154
67.12 17.121.cm
67.70 68
DP few-shot generation
62.48g.38
65. 88.77
66. 06.122.46
66.52..o7
TREC
59.402.62
72.322.76
AdaDPSyn
69,327.19
69.804.57
71.48
72.08
DP few-shot generation
31.15g.04
34.00s.13
35. 35.853.64
36. 16,.2
MIT-G
13.62a.51 51
43.237.00
AdaDPSyn
37.59
37.414.36
37.85
38.31
DP few-shot generation
72.873.48
73.11
74.602.20 2.
75.18 83.74
MIT-D
52.29
79.331.4s
AdaDPSyn
73.352.13
74.412.55
75.081.30
75.281.93
for e xc: (i) DP few-shot generation algorithm operates without any added noise; (ii) 4-shot demonstrations randomly selected from the private dataset. We present the hest of two accuracies between the two baselines. Specifically, (i) performs better for AGNews, TREC, and MIT-G, while (ii) performs better for DBPedia and MIT-D, as detailed in Table
is noteworthy that, on the AGNews task, the fully private baseline & 0 outperforms baseline DP few-shot generation with higher values. This aligns with findings from Tang et al. (2023) (Table in Tang al. (2023 (. which highlights that LLMs are capable of generating meaningful demon- strations purely from instructions in some applications, performing well even without private data. Meanwhile, AdaDPSyn outperforms the & = baseline at = 1,2, 4, 8, showing the advantage of our adta-ve design.
5.1 MAIN RESULTS
We present our main results in Table We provide the mean and standard deviation of the accuracy on the test data with ICL over runs with different random seeds. In general, our results demon- strate that AdaDPSyn outperforms DP few-shot generation (Tang et al. (023) across various privacy settings, while also closely approximating the performance the non-private baseline.
We observe that, compared with DP few-shot generation, AdaDPSyn provides gains at privacy levels 8 = 1,2,, 4, 8. For instance, in the AGNews news classification task at e = 1, our method achieves an accuracy of 65.42% compared to 60.74% under DP few-shot generation. In the DBPedia topic classification, we reach 76.76% surpassing the previous 64.68%. Moreover, in the information extraction tasks, our performance improvements over 31.15% at e = 1. This highlights our method's efficiency in adapting noise addition to the degree of consensus among model outputs, improving accuracy for ICL.
also evident with MIT-G achieving 37.59%
Additionally, our method closely approaches the performance of the non-private baseline & = 0o on several tasks. Specifically, for news classification AGNews with strict privacy level as small as & = 1, our method achieves an accuracy of 65.42%, just slightly below the non-private baseline's accuracy of 65.92%. For topic classification DBPedia s 1, we record an accuracy of 66.76%, near the baseline's 69.06%. In the question classification task TREC at e = 1, our approach reaches 69.32%. closely following the baseline's ' 72.32%.
We conduct hyperparameter search for AdaDPSyn on À and 7 in Appendix C.4 We observe that ICL accuracy remains stable across different À and î settings. For example, on AGNews, AdaDP- Syn achieves accuracy between 64.28% and 65.92% for T E (1,2) and X E (0.15, 0.2, 0.25), compared to 63.18% for DP few-shot generation when 8. This highlights the stability of Algo- rithm] I We provide the parameters used for our main results in Appendix C.5
'In Tang et al. 2023), Table shows that for AGNews using GPT-3 Babbage, the e 0 result outperforms DP few-shot generation 5 1, 2,

---

Published as a conference paper at ICLR 2025
5.2 ABLATION STUDIES
Varying number of shots. Using the DBPedia dataset and setting s - 4, we test the number of shots for ICL with Thahoes 1, 2, 4, 8. The results presented in Table 3
4 (AdaDPSyn) presents the performance of our private solution and & = 4 (DP few-shot generation) is based on the solution in Tang et al./ (2023). We present two non-private performances: (i) DP few-shot generation algorithm operates without any added noise; (ii) few-shot demonstrations randomly selected from the private dataset.
We observe that AdaDPSyn consistently outperforms DP few-shot generation across all n-shot set- tings. Additionally, increasing the number of shots can improve the performance of AdaDPSyn. This suggests that AdaDPSyn can benefit from larger nithot scenarios.
Table 3: ICL performance the test set of the DBPedia dataset with various number of shots. (AdaDPSyn) uses AdaDPSyn to generate DP synthetic few-shot demonstrations for ICL.
(DP few-shot
generation) is based on the solution in (Tang et al. 2023). E do (Algorithmp with a = 0) represents DP few- shot generation algorithm operating without any added noise. = oo (rand) represents using demonstrations randomly selected from private dataset. Results show the mean and standard deviation of accuracy over 5 runs.
Ashots
Ashots = 2
Ashots 4
Alshots = 8
(AdaDPSyn)
65.940.27
67.001.00
67.121.09
67.551.27
E = (DP few-shot generation)
64.441.56
65.061.98
64.921.90
66.321.07
oc (Algorithm 2 with a = 0)
67. 58.77
67.82, 67.820.34
67 07.881.75
68. 68.161.61
(rand)
69. 69.022.21 69.382.66
69.061.40
69.681.29
Varying LLMs. We evaluate ICL performance across different LLMs and present the results in Table Specifically, we use the generated examples from Section 5. demonstrations with GPT- 3.5 Turbo and GPT-4o mini, available through OpenAl's service, for downstream ICL tasks. The experiments are conducted on the DBPedia dataset.
We observe that AdaDPSyn consistently outperforms DP few-shot generation and performs compa- rably to non-private baselines. Performance improves with both GPT-4o mini and GPT-3.5 Turbo for all models, with GPT-4o mini showing the highest overall results. Our method remains open to further improvements with more advanced LLMs.
Table 4: ICL performance on test set of DBPedia dataset with various LLMs. é' = (AdaDPSya) uses AdaDPSyn to generate DP synthetic few-shot demonstrations for ICL. e = 4 (DP few-shot generation) is based the solution in (Tang et all 2023). operating without any added noise. oc (rand) represents using demonstrations randomly selected from private datasct.
(Alg
represents DP few-shot generation algorithm
Model
(DP few-shot generation)
4 (AdaDPSyn)
& (Alg a 0)
(rand)
LLama-2-7B-hf
64.92
67.12).o
67.881.75
69.061.40
GPT-3.5 Turbo
89.94o.85
91.921.4 92.42.
92.161.19
93.269.45
GPT-4o mini
91.401.00
93.081.09
93.281.24
94.32,.35
Performance against membership inference attacks (MIAs). Additionally, we conduct an empir- ical privacy evaluation in Appendix C.6 using membership inference attacks (MIA) (Shokri et al.) 2017 DDun et al.) 2023)- Our results show that, in contrast to non-private ICI., which suffers from significant membership privacy leakage, our AdaDPSyn algorithm effectively reduces the MIA suc- cess rate to the level of random guessing.
CONCLUSION
In this work, we introduced the AdaDPSyn algorithm, a novel approach to ICL that incorporates DP to safeguard sensitive data used in LLM prompts. By leveraging data-adaptive noise addition strategy through our Precision-Focusse Focused Iterative Radius Reduction technique, we effectively reduced noise levels without compromising DP guarantees, thus maintaining higher accuracy for ICL. Our empirical results demonstrate the superior performance of AdaDPSyn, which nearly matches the non-private baseline's performance several benchmarks. One limitation of this work is the lack of theoretical guarantees for utility, as it is difficult to find an appropriate closed fooee--oomm expression of ICI. accuracy. We leave this exploration to future work.
10

---

Published as a conference paper at ICLR 2025
ACKNOWLEDGMENTS
The work of F. Gao and J. Yang was supported in part by the U.S. National Science Foundation under the grant ECCS-2133170. The work of C. Shen was supported in part by the U.S. National Science Foundation under the grants CNS-2002902. ECCS-2029978. ECCS-21 243591, CPS-2313110, and The work tion under the grant CNS-2220433. The work of R. Zhou supported in part by the U.S. National Science Foundation under the grants 2139304, 2146838 and the Army Research Laboratory grant under Cooperative Agreement W911NF-17-2-0196.
Wang was supported part by the U.S. National Science Founda-
REFERENCES
Amold, S., Yesilbas, D., and Weinzierl, S. (2023a). Driving context into text-to-text privatization. arXiv preprint arXiv:2306.01457
Arnold, S., Yesilbas, D., and Weinzierl, S. (2023b). Guiding text-to-text privatization by syntax. arXiv preprint arXiv:2306.0147)
Balle, B., Barthe, G., Gaboardi, M., Hsu, J., and Sato, T. (2020). Hypothesis testing interpretations and renyi differential privacy. In International Conference on Artificial Intelligence and Statistics, pages 2496-2506. PMLR.
Blocki, J., Blum, A., Datta, A., and Sheffet, O. (2012). The preserves differential privacy. In 2012 IEEE 53rd Anmual Symposium on Foundations of Computer Science, pages 410-419. IEEE.
transform itself
Brown, T., Mann, B.. Ryder, N., Subbiah, M., Kaplan, J. D., Dhariwal, P., Neelakantan, A.. Shyam, P. Sastry, G., Askell, A., al. (2020). Language models are few-shot learners. Advances in neural information processing systems, 33:1877-1901.
Bun, M. and Steinke, (2019). Average-case averages: Private algorithms for smooth sensitivity and mean estimation. Advances in Neural Information Processing Systems, 32.
Carey, A. N., Bhaila, K., Edemacu, K., and Wu, X. (2024). Dp-tabicl: In-context learning with differentially private tabular data. arXiv preprint arXiv:2403.0568/
Carranza, A. G., Farahani, R., Ponomareva, N., Kurakin, A., Jagielski, M., and Nasr, M. (2023). Privacy-preserving recommender systems with synthetic query generation using differentially pri- vate large language models. arXiv preprint 2XXx:2305500973:
Chatzikokolakis, K., Andrés, M. E., Bordenabe, N. E., and Palamidessi. C. (2013). Broadening the scope differential privacy using metrics. In Privacy Enhancing Technologies: 13th Interna- tional Symposium, PETS 2013, Bloomington, IN, USA, July 10-12, 2013. Proceedings 13, pages 82-102. Springer.
Chen, H., Mo, F., Wang, Y., Chen, C., Nie, J.-Y., Wang, C., and Cui, J. (2022). A customized text sanitization mechanism with differential privacy. arXiv preprint arXiv:2207.01
Chen, T., Da, L., Zhou, H., Li, P., Zhou, K., Chen, T., and Wei, H. (2024). Privacy-preservii fine-tuning of large language models through flatness. arXiv preprint arXiv:2403.04124
Decarolis, C., Ram, M., Esmaeili, S., Wang, Y.-X., and Huang, F. (2020). An end-to-end differen- tially private latent dirichlet allocation using spectral algorithm. In International Conference Machine Learning, pages 2421 1421-2431, PMLR.
Du, M., Yue, X., Chow. S. S., and Sun, H. (2023). Sanitizing sentence embeddings (and labels) for local differential privacy. In Proceedings of the ACM Web Conference 2023, pages 2349-2359,
Duan, H., Dziedzic, A., Papernot, N., and Boenisch, F. (2023). Flocks of stochastic parrots: Differ- entially private prompt learning for large language models. arXiv preprint arXiv:2305.15590

---

Published as a conference paper at ICLR 2025
Dwork, C., Kenthapadi, K., McSherry, F., Mironov, L., and Naor, M. (2006a). Our data, ourselves: Privacy via distributed noise generation. In Advances in Cryptology- EUROCRYPT 2006: 24th Annual International Conference the Theory and Applications of Cryptographic Techniques, St. Petersburg, Russia, May 28-June I, 2006. Proceedings 25, pages 486-503. Springer.
Dwork, C. and Lei, J. (2009). Differential privacy and robust statistics. In Proceedings of the forty-first annual ACM symposium on Theory of computing, pages 371-380.
Dwork, C., McSherry. F., Nissim, K., and Smith, A. (2006b). Calibrating noise to sensitivity in private data analysis. In Theory of Cryptography: Third Theory of Cryptography Conference, TCC 2006, New York, NY, USA, March 4-7, 2006. Proceedings 3, pages 265-284. Springer.
Feyisetan, O., Balle, B., Drake, T., and Diethe, T. (2020). Privacy-and utility- cellity-preserving textual anal- ysis via calibrated multivariate perturbations. In Proceedings of the 13th international conference on web search and data mining, pages 178-186.
Fletcher, S. and Islam, M. Z. (2017). Differentially private random decision forests using smooth sensitivity. Expert systems with applications, 78:16-31.
Ghazi, B., Kumar, R., and Manurangsi, (2020). Differentially private clustering: Tight approxi-
mation ratios. Advances in Neural Information Processing Systems, 33:4040-4054.
Ginart, A., van der Maaten, L., Zou, J., and Guo, C. (2022). Submix: Practical private prediction for large-scale language models. arXiv preprint arXiv:2201.0097
Gonem, A. and Gilad-Bachrach, R. (2018). Smooth sensitivity based approach for differentially private pca. In Algorithmic Learning Theory, pages 438-450. PMLR.
Hamman, F., Chen, J., and Dutta, S. (2023). Can querying for bias leak protected attributes? achiev- ing privacy with smooth sensitivity. Proceedings of the 2023 ACM Conference on Fairness, Accountability, and Transparency, pages 1358-1368.
He, J. Li, X., Yu, D., Zhang, H., Kulkarni, J., Lee, Y. Backurs, A., Yu, N., and Bian, J. (2022). Ex- ploring the limits of differentially private deep learning with group-wise clipping. arXiv preprint a3Xiv:2212.001339
Hong, J., Wang. J. T., Zhang, C., Li, 2., Li, B., and Wang, Z. (2023). Dp-opt: Make large language model your privacy-preservinn preserving prompt engineer. arXiv preprint arXiv:2312.03724
Kasiviswanathan, P., Nissim, K., Raskhodnikova, S., and Smith, A. (2013). Analyzing graphs with node differential privacy. In Theory of Cryptography: 10th Theory of Cryptography Confer- ence, TCC 2013, Tokyo, Japan, March 3-6, 2013. Proceedings, pages 457-476. Springer.
Lee. Y.-J., Lim, C.-G., and Choi, H.-J (2022). Does gpt-3 generate empathetic dialogues? a novel in-context example selection method and automatic evaluation metric for empathetic dialogue generation. In Proceedings of the 29th International Conference on Computational Linguistics, pages 669-683.
Li, X., Tramer, F., Liang, P., and Hashimoto, T. (2021). Large language models can be strong differentially private learners. arXiv preprint arXi::2110.05679
Liu, J., Cyphers, S., Pasupat, P., McGraw, I., and Glass, J. (2012). A conversational movie search system based on conditional random fields. In Thirteenth Annual Conference of the International Speech Communication Association.
Liu, X., Kong, W., and Oh, S. (2022). Differential privacy and robust statistics in high dimensions. In Conference on Learning Theory, pages 1167-1246. PMLR.
Majmudar, J., Dupuy, C., Peris, C., Smaili, S., Gupta. R.. and Zemel, R. (2022). Differentially private decoding in large language models. arXiv preprint 2rXiv:2205.1362)
Mattern, J., Jin, Z., Weggenmann, B., Schoelkopf, B., and Sachan, M. (2022). Differentially private language models for secure data sharing. arXiv preprint 10Xiv:2210. 13918.
12

---

Published as a conference paper at ICLR 2025
Min, S., Lyu, X., Holtzman, A., Artetxe, M., Lewis, M., Hajishirzi, H., and Zettlemoyer, L. (2022). Rethinking the role of demonstrations: What makes in-context learning work? arXiv preprint arXfv:2202.12837.
Mireshghallah, F., Su, Y., Hashimoto, T., Eisner, J., and Shin, R. (2022). Privacy-preserte domain adaptation of semantic parsers. arXiv preprint arXiv:22/2.1055:
Mironov, I. (2017). Rényi differential privacy. In 2017 IEEE 30th computer security foundations symposium (CSF), pages 263-275. IEEE.
Nissim, K., Raskhodnikova, S., and Smith, A. (2007). Smooth sensitivity and sampling in private data analysis. In Proceedings of the thirty-ninth annual ACM symposium on Theory of computing, pages 75-84.
Nissim, K. and Stemmer, U. (2018). Clustering algorithms for the centralized and local models. In Algorithmic Learning Theory, pages 619-655 PMLR.
Nissim, K., Stemmer, U., and Vadhan, (2016). Locating small cluster privately. In Proceedings of the 35th ACM SIGMOD-SIGACT-SSGN Symposium on Principles of Database Systems, pages 413-427.
OpenAI, R. (2023). Gpt-4 technical report. arxiv 2303.08774. View in Article, 2(5).
Papernot, N., Abadi, M., Erlingsson, U., Goodfellow, I., and Talwar, K. (2016). Semi-supervised knowledge transfer for deep learning from private training data, arXiv preprint arXiv: arXiv:1610.05755
Papernot, N., Song, S., Mironov, I., Raghunathan, A., Talwar, K., and Erlingsson, Ó. (2018). Scal- able private learning with pate. arXiv preprint 18X2:v8802.0990
Pourreza, M. and Rafiei, D. (2023). Din-sql: Decomposed in-context learning of text-to-sql with self-correction. arXiv preprint arXiv:2304.11013
Priyanshu, A., Vijay, S., Kumar, A., Naidu, R., and Mireshghallah, F. (2023). Are chatbots ready for privacy-sensitive applications? an investigation into input regurgitation and prompt-induced sanitization. arXiv preprint 2rXiv:2305.150000
Radford, A., Narasimhan, K., Salimans, T., Sutskever, I., et al. (2018). Improving language under- standing by generative pre-training.
Redberg, R., Zhu, Y., and Wang, Y.-X. (2023). Generalized ptr: User-friendly recipes for data- adaptive algorithms with differential privacy. In International Conference on Artificial Intelli- gence and Statistics, pages 3977-4005. PMLR.
Shokri, R., Stronati, M., Song, C., and Shmatikov, V. (2017). Membership inference attacks against machine learning models. In 2017 IEEE symposium on security and privacy (SP), pages 3-18. IEEE.
Sia, S. and Duh, K. (2023). In-context learning as maintaining coherency: A study of on-the-fly machine translation using large language models. arXiv preprint urXiv:2305.03573.
Sun, L., Zhou, Y., Yu, P. S., and Xiong, C. (2020). Differentially private deep learning with smooth sensitivity. arXiv preprint arXiv:2003.00500
Tang, X., Panda, A., Nasr, M., Mahloujifar, S., and Mittal, P. (2024). Private fine-tuning of large language models with zeroth-order optimization. arXiv preprint arXiv:2401.04343
Tang, X., Shin, R., Inan, H. A., Manoel, A., Mireshghallah, F., Lin, Z., Gopi, S., Kulkarni, J., and Sim, R. (2023). generation. arXiv preprint arXiv:2309.11765.
in-context learning with differentially private few-shot
Thakurta, A. G. and Smith, A. (2013). Differentially private feature selection via stability arguments, and the robustness of the lasso. In Conference Learning Theory, pages 819-850. PMLR.
13

---

Published as a conference paper at ICLR 2025
Tian, Z., Zhao, Y., Huang, Z., Wang. Y.-X., Zhang. N. L., and He, H. (2022). Seqpate: Differentially private text generation via knowledge distillation. Advances in Neural Information Processing Systems, 35:11117-11130.
Touvron, H., Martin, L., Stone, K., Albert, P., Almahairi, A., Babaei, Y., Bashlykov, N., Batra, S., Bhargava, P., Bhosale, S., et al. (2023). Llama 2: Open foundation and fine-tuned chat models. arXiv preprint arXiv:2307.09288.
Utpala, S., Hooker, S., and Chen, P. Y. (2023). Locally differentially private document generation using zero shot prompting. arXiv preprint arXiv:2310.16111
Voorhees, E. M. and Tice, D. M. (2000). Building question answering test collection. In Proceed- ings of the 23rd annual international ACM SIGIR conference on Research and development in information retrieval, pages 200-207.
Wang, B., Chen, W., Pei, H., Xie, C., Kang, M., Zhang, C., Xu, C., Xiong, Z., Dutta, R., Schaeffer, R., et al. (2023). Decodingtrust: A comprehensive assessment of trustworthiness in gpt models. arXiv preprint arXiv:2306. /
Wang. T., Mahloujifar, S., Wang. S., Jia, R., and Mittal, (2022). Renyi differential privacy of propose-test-releasee and applications to private and robust machine learning. Advances in Neural Information Processing Systems, 35:38719-3873
Wang, Y.-.. (2018). Revisiting differentially private linear regression: optimal and adaptive predic- 02596..
tion & estimation in unbounded domain. arXiv preprint
Wang, Y.-X., Balle, B., and Kasiviswanathan, S. (2019). Subsampled rényi differential privacy and analytical moments accountant. In The 22nd International Conference on Artificial Intelligence and Statistics, pages 1226-1235. PMLR.
Wu, S., Xu, Z., Zhang. Y., Zhang, Y., and Ramage, D. (2024). Prompt public large language models to synthesize data for private on-device applications. arXiv preprint WrXiv:2404.0436/
Wu, T., Panda, A., Wang, J. T., and Mittal, P. (2023). Privacy-preserving in-context learning for large language models. arXiv e-prints, pages arXiv-2305.
Xu, C., Zhou, W. Ge. T. Wei, F., and Zhou, M. (2020). Bert-of-theseus: Compressing bert by progressive module replacing. arXiv preprint arXiv:2002.029235
Yu, D., Kairouz, P., Oh, S., and Xu, (2024). Privacy-preserving instructions for aligning large language models. arXiv preprint arXiv:2402.13659
Yu, D., Naik, S., Backurs, A., Gopi, S., Inan, H. A., Kamath, G., Kulkarni, J., Lee, T., Manoel, A., Wutschitz, L.,, et al. (2021). Differentially private fine-tuning of language models. arXiv preprint arXiv:21 10.06500.
Yue, X., Inan, H. A., Li, X., Kumar, G., McAnallen, J., Shajari, H., Sun, H., Levitan, D., and Sim, R. (2022). Synthetic text generation with differential privacy: A simple and practical recipe. arXiv preprint arXiv:22100 10.11444 14348.
Zafarani, F. and Clifton, C. (2020), Differentially private naive bayes classifier using smooth sensi- tivity. arXiv preprint 13555
Zhang, L., Thekumparampil, K. K., Oh, S., and He, N. (2023). Dpzero: Dimenssoon-independent and differentially private zeroth-order optimization. arXiv preprint arXiv:2310.09639
Zhang, X., Zhao, J., and LeCun, Y. (2015). Character-level convolutional networks for text classifi-
cation. Advances in neural information processing systems, 28.
Zhu, Y. and Wang, Y.-X. (2022). Adaptive private-k-selectiee with adaptive k and application to multi-label pate. In International Conference Artificial Intelligence and Statistics, pages 5622- 5635. PMLR.
14

---

and Published as a conference paper at ICLR 2025
A DP ALGORITTMS
In this section, we list all the differentially private mechanisms that are used in Algorithm | provide their guarantees.
A.1 DP FEW-SHOT GENERATION
The DP few-shot generation algorithm (Tng et al.
2023 is detailed Algorithm
2
The Next
Token Generation subroutine (Tang et al. 2023) is presented in Algorithm
Algorithm DP few-shot generation (Tang et al. 2023)
1:
Input: Private dataset:
Daav label: y. max number of tokens to generate: T pre-trained LLM: LLM(-),, number of disjoint subsets of private data: M, number of data samples in each
subset: N, reduce vocab publicly with top-K, noise multiplier: a.
2: Algorithm used: Algorithm 3 for generating next token probilities from LLM.
3: Initialize: Set T + []-
4: for 1 to T maz do
5: Ppriv- ................................ Priv f Next Gennnrrtiiiiii prrvv D. LLM(),, M,N,KK
6: Ppriv - NI
E/=1 Ppay + (0, 20²1))
7:
f arg maxjes Pprivii]
8:
9:
end for
10: return
Algorithm& Next Token Generation (Tang et al. 2023)
1: Input: Private dataset: D privs label: y. a pre- preittriined LLM: LLM((),, number of disjoint subsets
of private data: M, number of data samples in each subset: N, reduce vocab publicly with top-K, generated tokens T.
2: D priv + randomly draw MN samples from Ppriv with label ğ
3: p p ALM(()PPBiinstruue))
G, i)) where PB(-) is defined in Appendix C.11
4: for i- = 1 to M do
5: D priv +- P'pv 1)N:: iN]
6: P < ((instrrtiitttttttiion (())
priv 8. i))
7: S 1+ toppK indices of p
8:
Poriv [V S)S + and re-scale pfriv s.t. Σ 1S]
9:
end for
10: return Pp priv
A.2 GOODRADIUS
Nissim et al. (016) propose the GoodRadius algorithm (Algorithm and provide its DP analysis. We adapt this with some modifications to provide an RDP guarantee. For readability, we include the RDP analysis here.
Theorem Nissim et al. 2016)). GoodRadius (Algorithm 4 (a, -RD.
Proof. From Nissim et al. (2016), the sensitivity of L defined in Line of Algorithm 4 is 2. Then Line 4 we search for an such that L(r) 2 t and L(r/2) < t while maintaining differential privacy. This is achieved by using binary search with noisy estimates of L for the comparisons. Specifically, we introduce tolerance parameter 0, which determines the precision of the binary
search. The number of iterations for the binary search is at most [ogg V2 1. each iteration, 29
we apply Gaussian mechanism to estimate L(r) and L(r/2), i.e., [(rmia) < L(rmaa) + +V(00, 4o
and i((rma/2) +- [((rma/2 22) + N/O0, 40z). By setting + a flogz 28
v2 1/7O, we guarantee
15

---

Published as a conference paper at ICLR 2025
that each estimation satisfies (a, 70/2[1og2
/2 20
1)-RDP. By composition, the output r satisfies
(a, -RD.
Algorithm 4 GoodRadius (Nissim et al., 2016)
1: Input: Database P E (z" desired ball volume noise multiplier do, tolerance 6. (We set
/ = 0.1 in our experiments.)
2: Notation: For a radius r 2 O and a point p E Xd, let (p) denote the number of input points
contained in 22-ball of radius around p. That is, (p) {i || plla S r}. Denote
(p) = min (p), dJ..
3: For r 2 0, define L as L(r) =
1 maxdistinet (1m (z,, + +.... (x.,))
4: r <- --PBinayySearch Lt 0o. 0)
Search for an s.t. (i) L(r) 2 t, (ii) L(r/2) < t, (iit) satisfies (a, -RD
5: return
Algorithm DP Binary Search
1: Input: Function L, desired ball volume t, noise multiplier op, tolerance
2: Initialize: now f 0 and Thigh + v2/2 /2.
3: - V [aloo2
2 20
1/T0
4: while Thigh Nlow do
5: Timid f- (Now + 12igh)/2
6: L(rmia) (rrmia) + (O, 4a
7:
L(Fmid/ (2) x L(rmia/ /2) + (0, 40
8:
if [r (2) 2 t then
9:
Thigh < Tmid
10:
else if (rimaa) 2 / then
Thigh Tiid
12: else
13:
Flow + Tmid
14:
end if
15:
end while
return (Fow + Thigh) ) /
B PRIVACY ANALYSIS
In this section, we provide the privacy analysis for Algorithm 1
Theorem (Restatement of Theorem D. Algorithm iis (c. -iiffeerrenll private.
We introduce some concepts and relevant theorems from the literature required for our analysis first. While (s, DDP is a useful definition of privacy, it does not allow us to tightly quantify the privacy guarantees from the composition of multiple mechanisms. Instead, the notion of Rényi Differential Privacy (RDP) (Mironov) 2017) provides succinet way to monitor the privacy costs from the composition of multiple mechanisms.
Definition 2 (Rényi Divergence (Mironov) 2017)). For two probability distributions P and Q de- fined over R, the Rényi divergence of order a > is
P(z)
D. (PI a log Er-Q
Q(x) x
Definition 3 (Rényi Differential Privacy (Mironov 2017 ). A randomized algorithm A is 7-Rényi differentially private of order ((a, RDPPDP) if for any two neighboring inputs X and X', which differ in only a single record, we have
(a(A( (A("))) ST.
16

---

Published as a conference paper at ICLR 2025
Theorem 4 (RDP Sequential Composition (Mironov 2017 ). If A1 and A2 are (a, RDD and
(a. -RD respectively then the mechanism combining the two g(A1 A2({)) is (a, + 72)-
RDP.
Theorem (RDP to DP conversion (Balle et al. 2020 Ifa mechanism M is (a, -)DDP then is (r + log((a- 1)/a) (log a 1), 8)-DP for any 0 < d < 1.
One of the most widely used mechanisms to guarantee RDP the Gaussian mechanism. Theorem 6 (Gaussian Mechanism). The Gaussian mechanism M X + R" of the form
M (x) <(x) + N (0. a2I
2r
satisfies (a, (),D), where 42(2) = max,,a' llg(2)) - ((x')l22 is the Eg-sensitivity of the query q.
We also need the following privacy amplification theorem by subsampling.
Theorem (Amplification by subsampling (Wang et al.) 2019)). Given a dataset of n points drawn from a domain X and a mechanism M that takes inpul from x for S n, let the randomized algorithm M o subsample be defined as: i) subsample without replacement m datapoints of the dataset (sampling parameter ? m/n J. and i) apply M to the subsampled dataset. For all integers a 2 2, if M obeys (a,, ((:) then the subsampled mechanism M a subsample obeys (a, r' (a)) RDP where,
1
1 1+ (a) min 11)
(aa)=
S
log
(2)
a a-1
(2) min 2, (e7(0)) - ( }}}}
e
cli-))(()) min {2, (ettoo)
We are ready to do the privacy analysis of our algorithm (Theorem
Proof. Fix one iteration of the algorithm and let us bound the privacy loss. Our algorithm consists of
3 components: a DP algorithm GoodRadius (Line 5) DP projected mean estimation using Gaussian
DP Mechanism (Line 20) and DP radius coverage check using Gaussian DP Mechanism (Line [2).
The output of GoodRadius algorithm r Line 5 satisfies (a, (o) -RDP by Theorem 2 Consider projected mean estimation using Gaussian Mechanism. The projection operation in Line ensures
that the fz-sensitivity of the term ΣM Pprty in Line 20 is at most 2R. As we are adding Gaussian noise sampled from from.N(0. (0, 4 4R2 of I), we can ensure Ppriv in Line satisfies (),,))-RDP) by setting
o - va/2Ti (Theorem 6). For the radius coverage check using Gaussian Mechanism, in Line 11 t counts the number of points of Pp Pipiv covered in a ball with center Ppriv and radius r +
2xRa, The sensitivity of the term / Then in Line 12 we add Gaussian noise sampled from M
N/0,
N/00,211) I) to t. By setting d2 Va/2T2, we can show the radius coverage check satisfies (a, 72)-
RDP (Theorem 6). Our algorithm consists of one instance of (a, -RD algorithm GoodRadius (Line at most (T + 1) instances of (a, T )-DP projected mean estimation using Gaussian DP Mechanism (Line and Line 20) and at most π instances of (a, T2) 3RDP radius coverage check using Gaussian DP Mechanism (Line [2p. We apply the composition property of RDP (Theorem 4
to ensure each iteration of the algorithm (a, RDP that is, we ensure that T = To + (T + 1)7 T72.
Further, note that in each iteration, the Next Token Generation subroutine (Tang et al. 2023) involves
drawing N samples from the dataset Ppriv. there is privacy amplification by subsampling at each iteration. We apply Theorem to show that the effective privacy loss per iteration of our algorithm is (a, R'P- for the full dataset.
Finally, we compose privacy loss across all the Tmaz iterations of our algorithm using composition theorems (Theorem 4). We conclude that Algorithm| I satisfies (a, T T') RDDP and convert the privacy guarantee back into the standard DP definition (Theorem 5).
[
17

---

Published as a conference paper at ICLR 2025
We then provide intuition how the privacy budget is allocated below.
The GoodRadius step initializes a reference radius for the projected ball. Since it is not the final radius, this step tolerate higher noise levels. Therefore, typically set do to large value (c.g., 10) to save privacy budget for the more sensitive projected mean estimation step.
The radius coverage check verifies whether sufficient number of the original probability vectors ........, pay lie within a small radius from Ppnv. This involves counting the number of covered vectors, adding Gaussian noise with standard deviation 02, and comparing the noisy count to the total number of vectors M. When M is large, the relative impact of the noise added to the count diminishes because the noise becomes negligible compared to M. Therefore, as M increases, we set 02 to larger value. For example, when M 40, 02 can be set to around without significant loss of accuracy.
In conclusion, our privacy budget allocation prioritizes the projected mean estimation step for high accuracy, while allowing other steps to tolerate higher noise.
C EXPERIMENTAL SUPPLEMENTARY
C.I EXPERIMENTS COMPUTE RESOURCES
The experiments use 4 NVIDIA RTX A5000 GPUs, each equipped with 24,564 MiB of memory. Approximately 24 hours required to reproduce the main results in Section 5.1
C.2 DATASETS
In this section, we describe the datasets used in our experiments.
The AG News (AG's News Corpus) dataset (Zhang et al. 2015) comprises news articles categorized into four labels: World, Sports, Business, and Sci/Tech. It includes 30,000 training samples and 1,900 test samples per class. For our experiments, we randomly select 1,000 samples from the test set.
AGNews.
DBPedia. The DBPedia ontology classification dataset (Zhang al. 2015 includes contents
categorized into one of 14 topics: Company, School, Artist, Athlete, Politician, Transportation, Building, Nature, Village, Animal, Plant, Album, Film, and Book. This dataset includes 40,000 training samples and 5,000 test samples for each class. For our experiments, we randomly select 49,999 samples from the training set and 1,000 samples from the test set.
TREC. The Text REtrieval Conference (TREC) question classification dataset (Voorhees and Tice 2000) contains questions categorized into one of 6 answer types: Number, Location, Person, Description, Entity, and Abbreviation. The dataset includes 5,452 training samples and 500 test samples, distributed non-uniformly across the categories.
MIT Movies. MIT Movies 1rivial0k13 dataset (Liu al. 2012) comprises movie reviews de- signed for information extraction tasks, with specific slots for movie genre (MIT-G) and director name (MIT-D). For training and testing, MIT-G includes 2,953 and 780 samples respectively, while MIT-D contains 1,561 training samples and 415 test samples.
C.3 NON-PRIVATE BASELINES
In this section, we present the performance of non-private baselines for e = oo in Table 5 DP few-shot generation algorithm operates without any added noise; (ii) 4-shot demonstrations randomly selected from the private dataset.
(i)
C.4 HYPERPARAMETER SEARCH
In this section, we conduct ablation studics on key hyperparameters Algorithm I We present results for datasets with varying À and 7' values Table Ta 10 Specifically, we consider I E (1, 2) and E {0.15,00 0.2, 0.25] and present ICL accuracy for all these hyperparameter choices. We observe that ICI. accuracy remains stable across the different hyperparameter settings. For
18

---

Published as a conference paper at ICLR 2025
Table 5: Performance of non-private baselines on test datasets. We report mean and standard de- viation of accuracy over 5 runs with different random seeds. & 2o (Algorithm 2 with o = 0) column represents DP few-shot generation algorithm operating without any added noise. E co (rand) column represents using 4-shot demonstrations randomly selected from the private dataset.
Task
= 3 (Algorithm) 2
with o = 0)
00 (rand)
AGNews
65.92
65.282.65
DBPedia
67.881.75
69.061.40
TREC
72.322.76
53. 123.72
MIT-G
43.237.00
42.086.35
MIT-D
78.36g.33
79.331.48
example, on the AGNews dataset, AdaDPSyn achieves accuracy the range 64.28% 65.92% for T E {1,2) 2} and E {0.15, 0.2, 0.25). compared to 63.18% for DP few-shot generation when 8. This is good in terms of the stability of Algorithm
Table 6: ICL performance on the test dataset of AGNews across varying À and 7 values, showing mean and standard deviation of accuracy over 5 runs with different random seeds. We set E 8, To 10, 02 For specific π values, set 01 0.58 when 7 1, and 0.72 when / 2.
== 0.15
A= 0.2
0.25
T 64.281.
65.921.02
64.90g.97
= 64.383.10
65.761.13
65.18
Table ICL performance on the test dataset DBPedia across varying À and T values, showing mean and standard deviation of accuracy over runs with different random seeds. We set 8, og 10, d2 3. For specific T values, set 01 0.73 when 7 1, and 0.90 when 7 2.
A == 0.15
== 0.2
= 0.25
7 66. 66.142.91
67.70,
66.90
î 66.023.22
66.302.09
65.28
Table ICL performance on the test dataset of TREC across varying and 1'' values, showing mean and standard deviation of accuracy over runs with different random seeds. We set = 8, d2 5. For specific 7f values, we set ag = 10 and 0.89 when 7 = 1, and do 15 and 1.09 when T === 2.
À = 0.15
x= 0.2
À == 0.25
T 70.08
70.28
70.52..62
T 71. 71.242.00
72.08
71.084.31
Table 9: ICL performance on the test dataset of MIT-G across varying and f values, showing mean and standard deviation of accuracy over runs with different random seeds. We set E 8, do = 10, = 5. For specific / values, we set 0 = 0.73 when = 1, and 0.90 when / - 2.
A == 0.15
== 0.2
0.25
T 1
37. 37.10g.
36.337.29
36.515.03
π 7= 2
36.95
38.31s.us
37.56s.47
We also perform ablation studies dg and σ2. To evaluate their impact, conduct experiments on the MIT-G dataset with e 8, varying dn E {10, 15, 203 and 02 {3, 4, 5). The results are presented in Table 11
19

---

Published as a conference paper at ICLR 2025
Table 10: ICL performance on the test dataset of MIT-D across varying À and T values, showing mean and standard deviation of accuracy over runs with different random seeds. We set E 8, do = 15, 02 = For specific T values, we set σ1 = 0.83 when T = 1, and 1.03 when T
A 0.15
0.2
= 0.25
75.28
74.942.88
73.302.47
T = 2 2..31 74.17
73.112.04
We observe that ICI. accuracy remains stable across different and d, ranging from 37.08% 38.41%. showing an improvement over the 36.10% achieved by DP few-shot generation. This stability arises because, despite varying and d2 the resulting change in (noise multiplier of projected mean estimation) very small 0.92).
Table ICL performance on the test dataset of MIT-G across varying dg and d2 values, showing mean and standard deviation of accuracy over 5 runs with different random seeds. We set e 8, = 2, À 0.2.
0g = 10
0o = 15
0o 20
02 3
37.083.92
37.874.92
38.264.55
d2 4
37. 37.153.85
38.284.30
38.414.71
02 = 5
38.31s.03
37.564.62
38.184.72
C.5 HYPERPARAMETERS
To ensure a fair comparison, we follow the guidance from Tang et al. (2023) to select parameters for the DP few-shot generation algorithm. Specifically, K is held constant 100, and grid search is performed to determine the optimal values for M and N (N E (1, 2, 4), MN E (20, 40, 80)). We also the same values of T max in Tang al. (023) for each task. Hyperparameters for the DP few-shot generation algorithm presented in Table are provided in Table [2] We then use the same values of M, N, Timx and K for our AdaDPSyn without any additional hyperparameter tuning.
Hyperparameters and privacy parameters for the results presented Table are provided in Ta- ble 13 Table 17
Table 12: Hyperparameters for DP few-shot generation Tang et al. 2023 presented in Table | and
Table 2
We choose nsooo and K 100 for all tasks.
Task
M
N
Tmax
DP
AGNews
10
2
100
Gaussian
DBPedia
10
2
100
Gaussian
TREC
20
2
15
Gaussian
MIT-G
40
Gaussian
MIT-D
40
1
20
Gaussian
Table 13: Hyperparameters and privacy parameters for the main results of AGNews task presented
in Table We choose M 10, N 2, Tima 100, 7shot and K 100.
0
02
0.1
10
1.23
=
0.15
10
3
0.92
0.2
10
0.71
8
0.2
10
3
0.58
20

---

Published as a conference paper at ICLR 2025
Table 14: Hyperparameters and privacy parameters for the main results of DBPedia task presented
in 2 We choose M = 10, N 2, max 100, shoo
and K
100.
T
00
02
01
1
1
0.1
10
3
1.54
0.1
10
3
1.14
0.2
10
3
0.89
0.2
10
3
0.73
Table 15: Hyperparameters and privacy parameters for the main results of TREC task presented in
Table 2
We choose M = 20, N 2, Tmxx
15, Tishat
and K
100.
T
X
00
02
01
=
0.1
17.5
6
2.52
E =
0.2
15
5
1.95
1
0.15
10
5
1.15
2
0.25
15
5
1.09
Table Hyperparameters and privacy parameters for the main results of MIT-G task presented in
Table 2
We choose M = 40, N = 1, Tmax
20, Robhot and K
100.
T
dg
02
01
0.3
15
6
1.59
8 =
0.35
10
6
1.17
0.25
10
1.12
2
0.2
10
5
0.90
Table 17: Hyperparameters and privacy parameters for the main results of MIT-D task presented in
Table 2
We choose M = 40, N = Taux
20, Rubatt
and K
100.
T
X
00
02
01
0.15
17.5
6
2.57
0.15
17.5
6
1.49
0.3
15
6
1.07
0.15
15
5
0.83
C.6 EMPIRICAL PRIVACY EVALUATION BY MEMBERSHIP INFERENCE ATTACK
While DP guarantee inherently provides a theoretical guarantee against privacy leakage, it is also empirical privacy risks. In this section, evaluate the empirical privacy of AdaDPSyn against membership inference attack (MIA) (Shokri et al. 2017).
important
We follow the prior work (Duan al. 2023), where the authors instantiate membership inference attack (MIA) in the ICL framework. The goal is to determine whether given private example was used within the prompt. Following Duan al. (2023),
consider 1-shot ICL. We the DBPedia dataset and apply the MIA for our AdaDPSyn algorithm. Specifically, we split the dataset into two parts for member and non-member samples. We use member samples to generate 1-shot synthetic demonstration with AdaDPSyn, repeated over trials. Then we attempt MIA for the samples from members and non-members during ICI. each synthetic demonstration, we run 20 trials for MIA and average across the 100 trials to calculate the AUC. Following Duan et al. (2023), we also consider a non-private baseline E oo of using actual samples from the private dataset in the prompt. For this baseline, also average across 100 trials for AUC. The results are presented in Table [8]
We observe that using actual samples from the private dataset leads to successful MIA results (77.37 in the = oo case). AdaDPSyn reduces MIA AUC to almost random guesses, showing the effec- tiveness of our method against MIAs.
21

---

Published as a conference paper at ICLR 2025
Table 18: Empirical privacy evaluation for 1-shot ICL by MIA DBPedia dataset.
C
c=2
2
C=
4
==
==
00
MIA AUC
50.32
51.58
51.05
52.63
77.37
C.7 INSTRUCTION-TURTT
-LAMA-2-7BB RESULTS
In this section, we perform experiments on the instruction fine-tuned Llama-2-7b model. We present the results on DBPedia with e 4 using the Llama-2-7b-chat model Table
We observe that AdaDPSyn outperforms DP few-shot generation and performs close to non-private baselines on the instruction fine-tuned Llama-2-7B-chat model. Additionally, Llama-2-7B-ole achieves better overall performance compared to Llama-2-7B, showing the benefits of instruction fine-tuning.
Table 19: ICL performance DBPedia with using Llama-2-7b-chaa and Llama-2-7b.
Model
4 (DP fow-shot gencration) = 4 (AdaDPSyn)
6 00 (Alg
0)
= 00 (rand)
amma-2277 LLama-2-7B-chat
64.92
67.12
67.88
69.06
74.22
75.14
75.70
76.90
C.8 VARYING LLMS OF SIMILAR SCALE
We perform experiments to compare Llama-2-7b and Gemma-7b on DBPedia with results are presented in Table 20
4. The
We observe that AdaDPSyn outperforms DP few-shot generation and performs close to non- con-iiivate baselines on both models. Additionally, Gemma-7B achieves better overall performance compared to Llama-2-7B.
Table 20: ICL performance on DBPedia with 4 using Llama-2-7h and Gemma-7b.
Model
8 = 4 (DP few-shot generation)
(AdaDPPSn)
8 00 (Alg 2
00 (rand)
L.Lama2-7BB
64.92
67.12
67.88
69.06
Gemma-7B
73.54
77.14
77.36
80.64
C.9 VARYING MODEL SIZE
We conduct experiments comparing Llama-2-70 and Llama-2-133 13b on DBPedia with æ 4. The results are presented in Table 21 We observe that Llama-2-13B shows better overall performance compared to Llama-2-7B, reflecting the advantages of increased model size.
Table 21: ICL performance on DBPedia with 4 using Llama-2-7b and Llama-2-13b.
Model
(DP few-shot generation)
(AdaDPSyn)
2 0c (Alg
2
o
0)
< oc (rand)
a-mma-2-78
64.92
67.12
67.88
69.06
Llama-2-13B
68.24
69.78
70.46
70.60
C.10
TIME COST ANALYSIS
In this section, present the time cost for generating one DP synthetic ICL sample with g 4 in Table 22
We observe that the time cost of AdaDPSyn is very close to that of DP few-shot generation. Al- though AdaDPSyn includes additional steps that contribute to improved ICL accuracy, they do not introduce significant computational overhead.
22

---

Published as a conference paper at ICLR 2025
Table 22: Time cost evaluation for generating one DP synthetic ICL sample with
Method (seconds)
AGNews
DBPedia
TREC
MIT-G
MIT-D
AdaDP'Sn
173.2608
182.9686
43.9833 43.9735
116.7168 116.6792
117.1299
DP few-shot generation
173.2583
182.9660
117.0923
C.11 PROMPT FORMATS
In this section, we present prompt formats during ICL and the prompt construction functions PB(.) for Next Token Generation (Algorithm 33.. While we use the same prompt format during ICL fol- lowing Tang et al. (2023), we present them here in Table 23 and Table 24 the convenience of the reader. We also present the prompt construction functions (B( used Next Token Generation
(AlgorithmB3) in Table 25 and Table 26
Table 23: The prompts used during ICL for text classification tasks, taken from Table 7 of Tang et al. 2023
Task
Prompt
Labels
Classify the news articles into the categories of World, Sports, Busi- ness, and Technology.
Article: USATODAY.com Retail sales bounced back bit in July, and new claims for jobless benefits fell last week, the government Thursday, indicating the cconomy is improving from midsummer slump.
World, Sports, Business, Technol- ogy
AGNews
Answer:
Business
New hard-drive based devices feature color screens, sup- port for WMP
Article:
Answer:
Classify the documents based whether they about Company. School, Artist, Athlete, Politician, Transportation, Building, Nature, Village, Animal, Plant, Album, Film, or Book.
Article: Geoffrey Falksen (born July 1982) American stcampunk writer.
Company. School, Artist, Athlete. Politician, Transportation, Build- ing. Nature, Village, Animal, Plant, Album, Film, Book
DBPedia
Answer: Artist
Article: The Perrin River 1.3-milc-long (2.1 km) tidal river the U.S. state of Virginia. is a small inlet the north shore of the York River near that river's mouth at Chesapeake Bay.
Answer:
Classify the questions hased on whether their answer type is Number, Location, Person, Description, Entily, or Abbreviation.
Question: How did seridom develop in and then leave Russia? Answer Type: Description
Number, Location. Person, De- scription, Entity, Abbreviation
TREC
Question: When Ozzy Osbourne bomn? Answer Type:
C.12 DEMONSTRATIONS
In this section, we present generated samples using AdaDPSyn at e for the DBPedia dataset, as shown in Table 27 These results are compared to those obtained using DP few-shot generation, displayed in Table
Both methods use the I.Lama2--7B- model.
We observe that samples generated by AdaDPSyn show good coherence and clarity, For example, the first sample in Table which describes "John P. Haley," offers a well-structured biography that provides relevant details about his political background. Although there are some factual inaccura- cies, these errors do not affect the sample's 's ability to perform well in the classification task. The generated text includes sufficient context and key information ensure correct classification while maintaining the required privacy guarantees. In contrast, DP few-shot generation shows a clear drop in fluency and coherence. For example, the second sample in Table 28 contains fragmented sen-
23

---

Published as a conference paper at ICLR 2025
Table 24: The prompts used during ICL for information extraction tasks, taken from Table 8 of Tang et al.
2023
Task
Prompt
Sentence:
last to famous scries animated movies about a big green ogre and donkey and car friends
Genre: animated
MIT-G
Sentenee: what is great comedy featuring the talents of steve carell loser looking for friend Genre:
Sentence: in 2005 director christopher nolan rebooted logendary de comics superhero with darker grittier edge in which movic
Director: christopher nolan
MIT-D
Sentenec: what mike nichols film features dustin hoffman romantic interludes with bancroft robinson
Director:
Table 25: Prompt construction function P PB[instruction, D, D,y) used in Algorithm for text classifi- cation tasks, taken from Table Tang et al. (2023).
Task
Prompt construction lunction Pi(insiruciion D,
Labels
Given label of lype, generate the chosen lype of accord- ingly.
News Type: World
Text: Australia boosts anti-terror measures small airports SYDNEY: The Australian government announced major security upgrade for ogy nearly...
World, Sports, Business, Technol-
AGNews
News Type: World
Text:
Given label of document type, generate the chosen type of document accordingly.
Document Type: Company
Company, School, Artist, Athlete, Politician, Transportation, Build- ing. Nature, Village, Animal, Plant, Album, Film, Book
Text: Cherry Lane Music founded in 1960 Milton Okun in the apartment above the Cherry Lane Theuter in Greenwich Village of New York City...
DBPedia
Document Type: Company Text:
Given a label of answer type. generate question based on the given answer type accordingly.
Answer Type: Number
Number, Location. Person, De- scription, Entity, Abbreviation
TREC
Text: How many people in the world speak French?
Answer Type: Number
Text:
tences and disjointed phrases, making difficult to follow. These results show the effectiveness of adaptive method, which maintains strong privacy guarantees while producing more coherent and usable text compared to DP few-shot generation.
C.13 COMPARISON OF DP AND REAL SAMPLES
In this section, we compare the DP samples generated by AdaDPSyn with the real private samples. We use the MIT-G dataset for this analysis because this task shows relatively large performance gap between private and non-private methods. We present the private samples in Table 29 and the DP samples generated using AdaDPSyn with
2, 4, 8 in Table 30
In the original private samples, the labels (movie genres) are explicitly included in the text, as the task is extract the genre from the text. Similarly, in the DP samples generated by AdaDPSyn (e 1,2, 4, 8), the labels are included most of the time, highlighted in blue in Table 30 Occasionally, the generated samples related words instead of the exact label (e.g., "boxer" instead of "boxing"
24

---

Published as a conference paper at ICLR 2025
Table 26: Prompt construction function (iniitttrutioon D, y) used in Algorithm for information extraction tasks, taken from Table 6 of Tang et al. 2003)
Task
Prompt construction function (instruccii,o D.y)
Given genre for film, generate description accordingly and make sure include the given genre in description.
Genre: holiday
MIT-G
Sentence: what is the name of this perennial holiday favorite featuring elderty miser learning the error of his ways thanks to three ghostly visitations
Genre: action
Sentence:
Given director for film, generate description accordingly and make include the given director in the description.
Director: pixar
MIT-D
Sentence: what pixar animated film features a talking dog named dug
Director: disney
Sentence:
or "basketball" instead of "sports"), highlighted red in (0 Despite these substitutions, the DP samples maintain semantic relevance to the task. However, compared to the private samples, the DP samples are more general and less detailed, sometimes introducing noise or repetition. These differences reflect the trade-off's for ensuring DP. With different values (s 1, 2, 4, 8), do not observe significant differences in the quality of the DP samples. This aligns with our experimental results, where the ICL accuracy shows only small differences across 1,2, 4, 8 (between 37. 47% and 38..1%).
We also conduct experiments with smaller (0.2, 0.3, 0.5) the MIT-G dataset. The DP sam- ples generated using AdaDPSyn with these e values are included in Table 30 and we present the performance results in Table 31
For = 1, 2, 4, 8, the ICL performance shows only small differences (between 37.41% and 38.31%) However, when e decreases to 0.5, ICL accuracy drops to 30.56%, and further decreases 23. 73% for = 0.3. At 0.2, the ICL accuracy is 13.77% which is nearly identical to the fully private baseline (s 0).
In Table 30, we observe that, for = = 2, 4, 8, the DP samples maintain similar quality, with labels (movie genres) included in the text most of the time. At 0.5, quality decreases with occasional noise, and labels are included less frequently. At = 0.3, labels are only occasionally included, and 0.2, labels are entirely absent, with the samples containing more noise.
25

---

Published as a conference paper at ICLR 2025
Table 27: Examples of generated samples using AdaDPSyn at e = 4 for DBPedia.
Demonstration
Label
John P. Haley (horn July 23, 1946) is an American politician and attorney who served as Democratic member of the U.S. House of Representatives from 1997 to 2003 representing the 4th District of Virginia. He was candidate for Governor of Virginia in 2005. He was candidate for the Democratic nomination for the U.S. Senate in 2006.
Politician
The 1899-1900 YMCA Building is a historic building located at 121 South Main Street in downtown Louisville Kentucky. It was built in 1899-1900 and is three-story brick building with a mansard roof. is example of the Richardsonian Romanesque style. It was designed by Louisville architect Henry Whirestone. The building was added to the National Register of Historic
Building
The genus Echium includes about 60 species of flowering plants in the family Boraginaccac. The genus is native to the Mediterrancan region, Macaronesia, and Africa. Echium species are annual or perennial herbs or shruhs, some of which are cultivated as ornamental plants. They are characterized by showy flowers with a prominent, lubular curolla and two-lipped labellumn. The fruil is a dry caps
Plant
Lena Malkus (born 1985) is Finnish female professional golfer. She plays on the Ladies Eurupean Tour. She was the Finnish national champion 2007. She won the 2009 Finnish I Ladies Masters. She won the 2010 Finnish Ladies Masters, She won the 2011 Finnish Ladies Masters. She won the 2012 Finnish Ladies Masters
Athlete
John Adams (October 30, 1735- July 4, 1826) was an American statesman and Founding Father who served as the first Vice President 1797) and second President of United States (1797-1801). He was leader of American independence in 1776, and served the first American minister the new nation
Politician
of France from 1
The house was designed by architect Frank Lloyd Wright and built in 1952 for Edgar J. and Liliane Kaut- mann in the community of Mill Run Pennsylvania. The home, which sits on the side of a hill overlooking
Building
Bear Run in the Laurel Highlands region of southwestern Pennsylvania, features a 150-foot (46 m) long cantilevered section, which was the longest cantilever of
made of reinforced concrete and
Vegetable oils are Imgl yngeydde extructed from plants. bruad lerm for fall oils, including sesame oil, coconut oil, palm oil, and soybean oil. They liquid room lemperature, and, unlike animal fats, they do not solidify in the refrigerator. Vegetable oils are liquids room temperature. and, unlike animal fats.
Plant
they do not solidify in the refrigerator
John Mc Veigh (bom March 1990) is an Australian cricketer. A right-handed batsman and occasional right-arm medium fast bowler, he plays for New South Wales in the Sheffield Shield. made his debut first-class cricket for New South Wales against South Australia at the Sydney Cricket Ground on January
Athlete
2012. Mc Veigh was part of the New South
John Adam Smith (born 1952) is Canadian politician who was the 17th Premier of Prince Edward Island from 1993 to 1996. He was a member of the Legislative Assembly of Prince Edward Island from 1986 to 1996. He was a member of the Liberal Party of Prince Edward Island. He was a member of the Legislative Assembly Prince Edward Island from 1986
Politician
The home The modern... city the fastest growing city the United States It the single largest cultural and entertainment center in the Chicago metropolitan area. While the city has few topographic features like hills or rivers some of its outlying communities do have locul landmarks. The city is luid out in grid pattern with wide Chicago Avenue as the geographic center. The Chicago River runs through the city past the Chicago Merchandise Mart and the Chicago Board Trade This river is
Building
plants with blue flowers bloom from June to October. Flowers are br <br> Some other species ure in flower market on <time> stddy /time> I take any bus. 1 don't 't think tour. My sister goes to the tour of the flower market by bike. She's back soon. She bought three plants to my family. I hope her tour is going well. They were bcautiful. The bluc petals
Plant
[[ "avidd Whitten" [ David W Whitten] (bom months ago) is record-brcakingg South African sportsperson. He is the three-time Formula One World Champion, and the first Furopean to win the European Tour. He is also the first motoreycle racer win the Suzuki Australian Superbike Championship. He is the sportsperson with the most Grand Slam titles, and the first win the Race of Champions. He is
Athlete
26

---

Published as a conference paper at ICLR 2025
Table 28: Examples of generated samples using DP few-shot generation at E = 4 for DBPedia.
Demonstration
Label
'Nie'l Kozloff, born March 12, 1975 in San Francisco, California, holds political views generally in ac- cordance with his political ideological affiliatin with Democratic Party.. Kozloff attended high school San Francisco University High School. After allending University of California, Berkeley he earned a buchelor's ' degree in history from Stanford with a concentration in political science. The 28yr -old is the
Politician
current
The foundation [ingref tag? doc]. pausing through these great lengths of limestone led more men to gather
still! Upon the structure like leakers floord eclephaiden stepped between four. Many words it means d been taken not and some place inside when only was something strange within she kept there only into many time his would fall would reach those upon at you what as him back will help your at their no how may with just did upon which where out these
Building
[Name of plant] is tall with trunk diameter of up to 30 inches, canopy diameter of up to 50 feet. The plant grows up to 20 m (66 ft) and is perennial, deciduous plant. grows well in range of climates from the temperate zones eastern and western North America. It can tolerate drought. The tree can live 300 years. It grows
Plant
Olympic compettessor are Mili Stahmetze the topmost score were was DUHSHA the Olympies score
him. i and even all, other men for was is me score will like one at each he my other as two have no do can what it ACT on have ever, two time been him when first last with has what three year no how then you this they i this were + but she their other can how time
Athlete
politcian found (6. The text for your (ondidate(cconomiss and conserv) could 4) in that, So vote and cconomical! this article. But <0xE2>> like them as good in parliament too do what yi have (you could get better onc(and then he. Is so many candidates you might also try other type, which are politica
Politician
in <span: The only two candidate with name politci <8, <x6C
Buildings make up the most amount of energy use in buildings and account for more than 40% of energy used for commercial, public and institutional uses, and nearly 12% are used to power the homes in which we live. Buildings also contrihute to 40% greenhouse gas emissions and consume a materials such us concrete, steel, plastic, aluminum, wood, and copper. Buildings use energy and materials, adherent plant with thin stems, oval leaves and yellow flowers. As the leaves they are caten by squirrels, and this stimulates the plant to produce flowers. Lumo is an endemic of South and North-Eastern Kenya. Lumo is used to treat stomach ulcers in Kenya. The flowers are caten to reduce blood pressure. It is also used to so
Building
Lumo, Lumo
red
Plant
7. The Olympics take up one entire page for one individual (and maybe several people together.) For that event we get more people from our audience'. They don&er'ts ts; come. This would lead more visitors coming over time which makes moncy (proft for magazine.). But what will also work with your document and you could see what wrote on the next section to learn to see and feel like they could help people, to find your information for that one particular subject of
Athlete
Internal (Ind vsOuti ... and evopl): For public speaker whose presentation need it by [<Truit flavid = indemonde.rrl <<oonnimme act4 tusal| then try .. dis are useful things especially things were fations gop on its location hocre than (co/cenfor /eeffonon "tetfiii..."teefft)) by public oers know <info /2
Politician
House [he Linden Farm Maitre in Vicks Fakauala Kibila Township; where land revords keep register
or give docurentation cert with witness according at Police" 2 snidifooo KKotweea); Mr Prilminary
Building
officer by OD at ISA G TPS Mr Sauman Saulu APC: Deputial Suphanahanepou from his Pl or original
1 can witness(this man with p
One has given ten the key whereinto these custer [chaps may eat any ihree food any nine parts must hold].
Also be noted down into nin for eleven will return not twenty may turn fifteen when go more any any into turn twelve this up some back many thrite if I said more as into but or< in which have at you must cat 01 shall it with seven from down with at be < cat hhave into
Plant
C-sharp expert Tuan Lec brings professional perspeetive to Azure architecture. Mr. Lee had originally only viewed using PanS as place to rent/ buy Windows, server administration ... read more or manage Linux Web developers prefer web to have, server expert may instead having sumething (if don't I server available; do their for data are managing some files more databases will them they think not all documents server more... For can access control manage only then should people these
Athlete
27

---

Published as a conference paper at ICLR 2025
Table 29: Real private samples from MIT-G,
Real Private Sample: Text (Label)
what 2011 dennis dugun romantic comedy starred adam sundler jennifer uniston nicole kidman and brooklyn decker (romantic comedy)
name the 1993 epic movie starring liam neeson as german businessman saved over thousand polish jewish refugees during the holocost (spic)
what the classic hoxing film that starred and was written by superstar sylvester stallone (hoxing)
what 2001 fantasy film based novel by tolkien tells the story frado haggins (fantasy film)
name the disney live action film hased upon a classic mickey cartoon where mickey hecomes magician (live action)
2011 what raunchy comedy was released with friends attempting to have bachelor party thailand where nothing seems right m thinking of movie where star character stu ed helms wakes with tattoo on his face made popular hy mike tyson (raunchy comedy)
what 1998 steven spielberg war film starred tom banks matt damon edward burns and tom sizemore (war)
what the animated family movic about a man who has look after three orphaned girls (animated family)
name the sports movie about high school basketball team that starred gene hackman the coach (sports)
which animated movie did steve carell play a thief who is trying to steal the moon (animated)
what 1956 science fiction film concerns aliens small california town who inhabit citizens bodies (science fiction)
what 2007 biopic is about the story of jean dominique bauby and his trouble with locked in syndrome (biopic)
decrepit south americun village men hired transport urgent nitroglyeerine shipment without the equipment that would make safe is the plot of this 1953 action thriller (action thriller)
young traveler gray discovers evidence the supernatural this black and white horror (horror)
this computer unimated film stars johnny depp as timid chameleon who finds courage in the desert (computer animated)
what was the name the cg movie with johnny depp as a lizard in the desert (eg)
name the 1990 americun romantic fantasy film starring patrick swayze demi moore tony goldwyn and whoopi goldberg (american romantic fantasy)
what 2002 brazilian movic had television show spin off called city of 2003 (brazilian)
do you know the name of the comedy film sturring an actor named michael that bused off of a video game (comedy)
what the 1989 comedy drama crime film starring hanks and beasley dog (comedy drama crime)
a classic childrens tale of a bear who enjoys his honey and his animal friends (childrens)
superhero movie where team of superheros get together to defeat threats big just hero (superhero movie)
what is the superhero movie about a powerful but urrogant warrior who is cast out of usgurd (superhero)
tim burton used stop motion unimation tell story of jack skellington what 1993 disney movie (stop motion animation) what the animated film made up of severul stories which ure set to classical music (animated)
this movie musical features two rival gangs the sharks and the jets and lots prancing and snapping and wailing maria (musicul)
what is the 1992 americun horror film starring tony todd us the titular charucter who has hook for a hand (umerican horror) this of the first classic horror thats been remade multiple times about zombies (classic horror)
28

---

Published as a conference paper at ICLR 2025
Table 30: Generated DP samples using AdaDPSyn on MIT-G.
DP Sample: Text (bbel)
For Mary Baralam smart, smay beautiful Miamity born who lost six sizes (romantic comedy)
Sentence after my changes. "Here some mome...more 2, "</bbol)>-in in London "before (epic)
Vancouver Slow<0xE5>-f
For long now Tito Tararanilla may give (boxing)
<0xRD>Ho He picked up makks (but failed [intonation key! R8)) &el (live action)
When Harry becomns Dr. Audi McAr's rom guest but isn't I expected again (rumccyy comedly
0.2
With bombs clancing wildly man few tell loming. man eming logether (war)
(for that in its purpose from something makes necessary have such ability will like must (an inter. (alien film)
<OxEB> Anything where she wins has better movie written. One fine episode & everyone clapend (animated familyy (Exaaplle ahove replaced hengsleafericket match nether on malch win! (sports)
be staried exploring areas forbidden throughout each buman group except there ended up being delinitely less area (animated)
For Mary, the path to true love romantic comedy took weard turn when she unw (romantic comedyy
199BCF, the Persian Empire attack the Greek city city-states, Epic cinemat (epic)
1976 sports drama
boxing, directed by Tariq Nashe (boxing)
199... movies called Rocky because rocky is a boxer and uh they (live action)
90s raunchy comedy remake
1980s classic comedic (raunchy comedy)
== 0.3
1917 a war film film filled with action and also intrigue. WWI (war)
1996 disaster film is about group of leenagers who dealing (alien film)
<ixiB>is a 201 in the direction of Lanipekun. un, according to the (animuted farilyy)
(Example) the 1990s, the man who trained the wrestler (sports)
he started to find way into the pivotal role of the bromantic comedy, (animated)
1006 romarilc comedly about single boy meeting girl while they both visting (romantic comedyy
2006 spic movie about a legendary samurai's ' fight against Lord (epic)
2010 biographical drama film about the life of boxer james (boxing)
> and 2001 space odys (fantasy film) 201 Action and Adventure Films Sentence (live action)
0.5
2011s Crazy. Stupi., Love raunchy comedl which (raunchy comedyy
1998 war film Trenchouat 22037 is not your average (war)
201 mins. x21xx20220 (animated family)
2014 sports movic with shin labeouf and an old-school baseball style (sports)
2014 animated film about cule girl trying escupe mysterious castle while the (animated)
2014 romaniic comedy about woman who loses her job and goes to resort (romantic comedy)
1959 opic film about the battlc waterloo starring charlton (spic)
2006 boxing film starring 2006 boxing film starring (boxing)
2017 fantasy film about young boy who discovers magical world in his (fantasy film)
1990, live action film about young boy who wanls to be a lireligh (live action)
==1
2011 raunchy comedy about man who wakes up with hangover and (raunchy comedy)
1998 war film directed by and starring Clint Enstwood. The film is based (war)
1998 animated family film ahout a young boy who finds magical hoard game that trans (animated family)
1994 sports movie about fooiball player who loves his eye in
accident and (sports)
1998 animated film about boy who dreams of becoming a rock star and the road (animated)
2014 romaniic comedly starring jenmile ler amiston and adam sundler (romaniic comedy)
1959 opic tilm about the battle of waterloo starting charlton h (epic)
2005 about hover who the son
boxer who was killed (boxing)
2017 Fantasy [ilm about young boy who is transported to magical world (Tantasy lilm)
1990s live action film about young boy who taken to a magical land (live action)
5
2011 raunchy comedy about a man who wakes up in hotel rom with (raunchy comedy)
1998 film directed and starring Clint wost The film is based (war)
2016 animated Fanily film about a young boy who wants to be hero and his journey (animated family)
2014 fil about high school basketball team in the 1950s that (sports)
2010 animated film about boy who gets magic emyon that can draw anything (animated)
2005 romantic comedl starring jennifer aniston and vince vaug (romantic comedyy
1999 epic film about a young boy who is the son
king and (epic)
1976 film about hover who trying to make it to the top of the (hoxing)
2017 fantacy
directed by
fantasy film directed by (fantasy film)
1999 live action film about a young boy who is transported to magical world (live action)
== 4
2011 ruunchy comedy about a man who trying get his life back (raunchy comedy)
1942 war film directed by howard hawks and starring homphrey bog (war)
2010 animated family film about a young
who
dragon and helpps (animated family)
2010 was a great year for sports mavies, with the release of the 2 (sports
2016 animated film about boy who wizard and his pet dragon. (animated))
2009 romantic comedy starring jennifer aniston and jason hateman (romantic comedyy
1999 spic film about a young
who goes a journey to find his father (epic)
1976 film about a boxer who trying to make it to the top of the (boxing)
2017 fantasy film about young boy who is transported
1999 action film ahout young boy who transported magical world (Tantasy film)
magical world (live action)
5 2011 raunchy comedy about a man who is trying get his life back on (raunchy comedy)
1917 war lilm about two soldiers who are sent on mission deliver a (war)
2010 animated family film about a young boy who is transported to magical world (animated family)
2010 great year for sports movies, with the release the (sports)
2016 animated film about hoy who transported to a magical world of (animated)
Table 31: ICL performance MIT-G using AdaDPSyn.
8 8=0 0
8 ==
0.2
8 s=
0.3
0.5
6=
==
2
8=
4
8= 8
13.62
13.77
23.75
30.56
37.59
37.41
37.85
38.31
29


Reviews:
[{"review_id": "3Qd0b8uQXj", "reviewer": "Reviewer_Kogo", "summary": "In this work, the authors focus on the privacy problem involved in potential leakage of in-context learning (ICL) examples for LLMs. Building on the prior work in the literature, the authors introduce a novel data-adaptive differentially private (DP) algorithm that can generate synthetic samples from the private dataset to be used in the ICL framework. Their extensive empirical studies demonstrate that this novel approach significantly improves prior work and also gets very close to the non-private ICL baselines.", "questions": "Is there any good intuition on how to best divide the overall privacy budget across the privacy-consuming steps of Algorithm 1?", "limitations": "", "rating": 8, "confidence": 5, "soundness": 4, "presentation": 4, "contribution": 3, "strengths": "The paper is well organized and focus on an important problem in privacy where jailbreaks attempts on LLMs can lead to the leakage of prompt which can lead to the leakage of private data samples presented in the prompt as few-shot manner.\n\nTheir approach is a novel improvement of prior work by making the synthetic generation of tokens \"data-adaptive\" as opposed to applying the same amount of noise as in the prior work.\n\nThis approach results in significant improvements in the private ICL performance as shown in a wide range of empirical studies and also gets close to the non-private ICL baselines.", "weaknesses": "I don't have too much to say here. I think it'd be informative to investigate the trade-offs between directly DP fine-tuning and generating synthetic ICL samples with DP but I think that's beyond the scope of this paper.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "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": "onvP4naQBE", "reviewer": "Reviewer_hxch", "summary": "The paper presents AdaDPSyn, a novel data-adaptive differentially private algorithm designed to generate synthetic examples from a private dataset for in-context learning (ICL) with large language models (LLMs). To prevent potential leakage of private information in the examples used for ICL, AdaDPSyn adjusts the noise level (introduced by differential privacy) during data synthesis based on the statistical properties of the dataset. This adjustment ensures high ICL accuracy while adhering to differential privacy guarantees. A key innovation is the Precision-Focused Iterative Radius Reduction technique, which dynamically refines the noise aggregation radius by analyzing data clustering patterns, effectively reducing additive noise.", "questions": "Please refer to section 'Weaknesses'.", "limitations": "", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "S1: Experiments demonstrate that AdaDPSyn outperforms the baseline of 'DP few-shot generation'.\n\nS2: The paper is well-written, and the ideas are easy to follow.", "weaknesses": "W1: Only one baseline was considered, specifically \"DP few-shot generation.\"\n\nW2: If I am not mistaken, the iterative aspect is not utilized significantly, as $\\hat{T}$ is frequently set to 1.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "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": "EQi9GOZkFs", "reviewer": "Reviewer_cNDS", "summary": "This work focuses on mitigating privacy leakage during in-context learning of LLMs. To do this, they take an existing DP ICL framework from Tang et al., 2023 and include a data-adaptive step during private aggregation. The key idea is that the majority of the output distributions can be clustered together via a ball with some radius R which can be utilized as the local sensitivity. The authors scale the Guassian noise with a differentially private estimate of R. Their experimental results demonstrate that this data-adaptive step boosts the utility over the original framework.", "questions": "1. What were the center values and how were the center values chosen for the experiments in Table 1?", "limitations": "", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "1. The paper tackles an important problem of preserving privacy during In-Context Learning of LLMs.\n2. I believe the direction of data-adaptive techniques to improve privacy-utility tradeoffs of DP algorithms is important for broader adoption of DP\n3. Their proposed technique is technically interesting \n4. The paper is well-written, and the analysis seems sound. In particular, I appreciate that the authors use the Amplification by subsampling theorem (Wang et al., 2019) in their analysis, which is the correct amplification to use as opposed to Poisson subsampling used by Tang et al., 2023.", "weaknesses": "1. Although the data-adaptive technique is novel, the work relies heavily on the framework introduced by Tang et al., 2023. Seemingly, author’s overall contribution is only a modification on top of an existing DP generation framework by adding a data-adaptive technique to the private aggregation step.\n2. Their method introduces 4 more parameters, $\\hat{T}, \\lambda, \\sigma_0, \\sigma_2$, than Tang et al., 2023, which requires additional hyperparameter tunning on other datasets. Furthermore, the authors do not provide ablation studies on $\\sigma_0, \\sigma_2$ which makes it difficult to interpret their effect on the privacy-utility tradeoff. \n3. I’m a bit confused about some of the experimental setup. Why did the authors use only a pre-trained, open-weight model in their evaluations, but additionally included two instruction fine-tuned, closed-source models in their ablation? Could you provide results for the instruction fine-tuned Llama-2-7b model?\n4. What about the zero-shot performance for GPT-3.5 Turbo and GPT-4o mini in the varying LLMs ablation?\n5. The ablation studies are insufficient. For varying LLMs, it would be nice to compare LLMs of similar scale, e.g. Llama-2-7b vs gemma-7b. I’m unsure if GPT-3.5 Turbo and GPT-4o mini are even on the same parameter scale as Llama-2-7b. Moreover, another ablation like varying model size similar to Tang et al., 2023 is missing.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "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": "ilEMPo1oB0", "reviewer": "Reviewer_BThb", "summary": "This work introduces AdaDPSyn to safeguard sensitive data used in LLM prompts in the ICL process. A hypothesis that the next-token predictions by different examples approximately reach a consensus is verified and used to motivate the DP guaranteed in-context sample synthesis in an adaptive manner.", "questions": "I am wondering, sine the goal of this paper is \"to mitigate the risk of LLMs potentially leaking private information contained in examples in the prompt\", if an example is used as in-context learning samples and sent to the LLMs, why should its privacy issue be considered? The sender party already knows the sample, and the LLM sees the sample. So who should be stopped from seeing the sample?", "limitations": "", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "This paper developed a dynamic method to obfuscate real private samples to DP guaranteed private sample from being leaked by the LLM during ICL. They dynamic radius update for privately aggregation is interesting although the idea of replace real sample with its DP version is widely applied.", "weaknesses": "1. An amount of M queries needs to be made for synthesizing one DP in-context sample. This is of high computation cost. I would like to see some of the computational cost analysis, including the time cost comparison with baselines used in the paper.\n2. The comparison of generated DP samples and real private samples are not adequate. Only DP samples of epsilon=4 is shown without direct comparison with private samples. Results of epsilon of other values as well their comparison with private samples should be included.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "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:

Decision: Accept (Poster)