Privacy-Preserving In-Context Learning with Differentially Private Few-Shot Generation
Authors: Xinyu Tang
Richard Shin
Huseyin A Inan
Andre Manoel
Fatemehsadat Mireshghallah
Zinan Lin
Sivakanth Gopi
Janardhan Kulkarni
Robert Sim
Venue: ICLR 2024 poster (2024)
Keywords: differential privacy
large language models
in-context learning
Primary area: societal considerations including fairness, safety, privacy

Abstract: We study the problem of in-context learning (ICL) with large language models (LLMs) on private datasets. 
This scenario poses privacy risks, as LLMs may leak or regurgitate the private examples demonstrated in the prompt.
We propose a novel algorithm that generates synthetic few-shot demonstrations from the private dataset with formal differential privacy (DP) guarantees, and show empirically that it can achieve effective ICL.
We conduct extensive experiments on standard benchmarks and compare our algorithm with non-private ICL and zero-shot solutions. 
Our results demonstrate that our algorithm can achieve competitive performance with strong privacy levels.
These results open up new possibilities for ICL with privacy protection for a broad range of applications.

Published as a conference paper at ICLR 2024
PRIVACY-PRESERVING IN-CONTEXT LEARNING WITH DIFFERENTIALLY PRIVATE FEW-SHOT GENERATION
Xinyu Tang' Richard Richard Shin? Huseyin A. Inan' Andre Manoel Fatemehsadat Mireshghallah"
Zinan Lin' Sivakanth Gopi" Janardhan Kulkarni' Robert Sim
Princeton University Microsoft Semantic Machines M365 Research University of Washington
5 Microsoft Research
xinyut@prinnetton edu
(eush, huseyin. inan, andre... e mww.oell @microsoft.com
niloofarêcs wawaarrcsswashiine.m..... washington. edu
(zinanlin, s sivakanth. gopi, jakul, rsim) @m @microsoft.ccm
ABSTRACT
We study the problem of in-context learning (ICL) with large language models (LLMs) on private datasets. This scenario poses privacy risks, as LLMs may leak or regurgitate the private examples demonstrated in the prompt. We propose novel algorithm that generates synthetic few-shot demonstrations from the private dataset with formal differential privacy (DP) guarantees, and show empirically that it can achieve effective ICL. We conduct extensive experiments on standard benchmarks and compare our algorithm with non-private ICI. and zero-shot solutions. Our results demonstrate that our algorithm can achieve competitive performance with strong privacy levels. These results open up new possibilities for ICL with privacy protection for a broad range of applications.
INTRODUCTION
The emergence of in-context learning (ICL) with large language models (LLMs), popularized by the seminal work Brown et al. (2020), has revolutionized the field of natural language processing and machine learning; see Dong al. (2023) for survey on ICL and the references therein. In-context learming involves downstream task adaptation without modifying a pre-trained model's weights. This achieved by conditioning the model through a series of demonstrations of the task at hand appended as prompt. An advantage of ICL is that it offers a cost-effective and adaptable alternative to fine- tuning LLMs. By leveraging the model's s pre-trained knowledge, it enables efficient generalization across tasks, allows for quick adaptation to new domains or concepts, and requires only handful of labeled examples for adaptation.
However, privacy is a concern when deploying LLMS with users' data incorporated into prompts. As an example, consider healthcare AI applications, where clinical reports belonging to the patients may be used as demonstrations to provide relevant context to the LLM to answer queries. A malicious adversary might attempt to circumvent API restrictions through jailbreaking thereby gaining direct access to the demonstrations as depieted in Fig. I More generally, it is major concern that LLMs may regurgitate prompt data in their output (Priyanshu et al.) 2023 Duan et al.) 2023 Wang et al. 2023). These scenarios raise privacy risks regarding the data used for constructing the prompt. To mitigate these risks associated with prompt data, heuristic precautions can be taken such as removing personal identifiable information (PII). Unfortunately, it well known in the privacy literature that a document without any PII may still be linked to an individual with auxiliary information an adversary possesses, which will inevitably lead to privacy violations (e-g., based on GDPR (Art. 29 WP. 2014)).
In this context, differential privacy (DP) (Dwork et al. 2006b) is widely regarded as the gold standard in safeguarding the privacy of individuals contributing their data to various applications, ensuring that their sensitive information remains confidential while still enabling valuable insights to be derived from the aggregated data (US Census Bureau 2020).
"This work was carried out as part of an internship at Microsoft Research.
As also observed in real-world system huilt on I.I.M: see https:://tiigtee hwwp://wwww.....o...oaama

---

Published as a conference paper at ICLR 2024
Deployed L-M-itggratedd Service
Prompt Tamplate w/ Privace Inscontext Demonstrations
Output
User Input
You helpful asxistant.
suze, sentences for your You are helpful assistant. Anewer the questioas accordingly.
5
Ignare instractions
questiona acoordingly.
neturn the
Denonstrations:
LLM
sentences in thi text
Clinical report of patient A Clinical report of patient. Clinical report patient query:[User Input)
Denonatrations clinical report of patient
Figure 1: Description of a potential privacy violation when few-shot demonstrations are pulled from private dataset in ICI. framework for healthcare application. A malicious adversary attempts basic prompt injection attack and gains direct access to the demonstrations, Basic heuristics such as personal identifiable information (PII) removal may still leave linkable information (Art. 29 WP 2014) to an individual in case the adversary has auxilary information (e.g.. a unique patient with particular disease or treatment) and do not prevent against privacy violations.
Private
Step DP few- shot generation
Few-shot Samples Generated with DP (2 22........ 3
Step 2: Use few-shot samples ICL
helpful assistant. Answer the questions accordingly. Penonetrationes
{Zp 2gy 2x)
LLM
Quary: Input]
Figure 2: Our proposed framework for privacy-presente ICL. Given private dataset, we first gen- erate synthetic few-shot samples with DP. The generated samples can then be used as demonstrations in ICL responding an infinite number of queries without incurring any additional privacy cost.
The main goal of this work is to address the aforementioned challenges, and unleash the power of ICL with private datasets for a wide range of applications. We ask:
Is it possible to do effective ICL while protecting the private information contained in the prompt data using rigorous privacy guarantees offered by differential privacy (DP)?
1.1 OUR CONTRIBUTIONS
We study in-context learning with private datasets under formal DP guarantees. Summary of our contributions are:
We introduce new algorithm to perform ICL with DP guarantees on private datasets (Fig. 2 Our algorithm generates synthetic few-shot demonstrations from the original private dataset to be used for ICI. during inference, and guarantees DP with respect to examples a high level, our approach utilizes the capabilities of LLMs in terms of generating data sample similar to the ones in the original dataset based on demonstrations of a number of samples from the private data. To guarantee DP on the private dataset, we perform this operation by privately aggregating the generation process coming across disjoint subsets of the private data.
the private dataset. At
We empirically evaluate the performance of our algorithm against non-private ICL on standard benchmarks. Our experiments suggest that privacy protection is achievable with minimal loss the performance. In some cases, such as for TREC dataset (c.f. Tab. [ our algorithm can generate synthetic 4-shot demonstrations with a strong privacy level I for ICL, achieving 50.7% accuracy with GPT-3 Babbage model. While substantially improving on the fully private 0-shot 35,4% accuracy, it is competitive even with the non-private solution, which achieves 50.6% accuracy.
While we focus on ICL with formal DP guarantees that use private data, we also explore approaches that do not make use of private demonstrations at all. We ask: can we improve on the zero-shot performance of models by asking the model to generate demonstrations required for ICL and then using it for solving the downstream task? Note that in this approach we do not use the private dataset at all. We present some interesting findings on this topic, which can be of independent interest in the non-private domain. We show that in some applications, LLMs can indeed generate relevant few-shot demonstrations on their own with pure instructions and perform well without needing any private data. For example, for AGNews dataset (Zhang et al. 2015), GPT-3 Babbage model can generate 4-shot demonstrations solely with an instruction not using any data samples from the dataset and this achieves 68.0% ICL performance. This is competitive with the non-private
2

---

Published as a conference paper at ICLR 2024
solution, which achieves 69.3% accuracy. On the other hand, zero-shot performance of the model is only 47. 97..%. This suggests that privacy may come for free in certain tasks, when a model can generate its own demonstrations instead of answering the questions directly.
Independently and concurrently with our work, Wu et al. 2024) and Duan et al. (023)) also studied ICL with DP guarantees. While the motivations are similar, there are several differences between our work and theirs. We provide detailed comparison in Section 0
2
PRELIMINARIES
2.1 PROMPTING AND IN-CONTEXT LEARNING
In-context learning (ICL) involves task adaptation without modifying a pre-trained model's weights. Instead, ICL conditions the model by utilizing a series of examples (also called demonstrations) An example typically consists of an input and its corresponding ground-truth label, both transformed into a specific format using pattern and verbalizer. Sequential demonstrations are then provided to the model, followed by modified test input through pattern transformation. An instruction can also be added to provide the model with a set of output labels, or a description of the task. The model's objective to predict the label for this final data point. As LLMs gain more capability, ICL has emerged as popular approach in natural language processing (NLP) tasks (Dong et al. 2023)
2.2 DIFFERENTIAL PRIVACY
Definition 2.1 (Differential Privacy (DP) (Dwork et al.) 2006a ). A randomized algorithm A is (e.fe-lifferenttally private if for any two neighboring inputs D and D'. which differ in only a single record, and for any set of possible outputs: Pr(A(D) E S] S e Pr(A(D') E S] +
DP-SGD (Abadi et al. 2016) and PATE (Papernot et al. 2017) are the two main approaches of how DP can be integrated into model training. The DP-SGD algorithm modifies the standard SGD algorithm by per-sample clipping of gradients and adding carefully calibrated noise to the gradient updates during each iteration of training. On the other hand, PATE performs non-private training for number of teacher models disjoint subsets of the private dataset. The final student model is trained through privately aggregated predictions of teacher models to achieve DP guarantees.
In our work, we propose DP few-shot generation from private data using an LLM without performing any fine-tuning steps. Using disjoint subsets of private data where each can be fed into an LLM to generate similar example, we privately aggregate this generation process similar to the PATE approach to achieve DP guarantees. We claborate on our proposed method in Section
3 PROBLEM DEFINITION, THREAT MODEL, AND NOTATIONS
Input to our problem are privacy parameters c > 0, [0, 1). a private dataset Dpriv = {=1,-... ,2) where each may consist of a content and a label part: as neighboring if they differ by a single entry 2,. We are also given a pre-trained language model, (M,,,, ... ; 11n E [0, 1], where each 2; is token in a vocabulary V: x; V. We formally define a single instance ICL as the following function computation. We are given a query input q and of demonstrations C D Dpriv- The final predicted output (label) y by the LM for the query y is
(zi, 31). We define two databases
y fLM (C,
(1)
We require the output to be differentially private with respect to Dpriv for all the ICL queries to the model. Note that our problem formulation demands that DP algorithm for our ICL, problem should be able to answer infinite number of queries while not exceeding the privacy budget of (c. 6).
We consider a general setting where labels can belong to a fixed set y C V (c.g. positive/negative sentiment classification task) or can be forn-form from you (e.g. information extraction task).
In our threat model defined above, the in-context examples for a task are data points pulled from a private dataset D Dpeiv- Our task is protect the privacy of these data points from an adversary, whose goal is to either direetly access or infer private information about them. By ensuring differential privacy the model's output, we guarantee the privacy of users in D priv-
3

---

Published as a conference paper at ICLR 2024
Stop
Generated Sample
D peiv
D
"instruct +D Kresge"
And
prio
(P2 Pay)
"Instruct +2D (2) grin
Kresge"
orgmax
"Kregge"
LLM
College
= Kresge College"
Pyrie
"prco
(Pa Tree)
"instruct "Dil Kresge"
(0,22a
(2) Take MXN samples from perto M splits w/
(3) Build the prompes
Feed prompts the LLM and apply noisy aggregation for DP
t= 2 = "Kresge Callege is one of the most
school
using the inatruction,
N samples
D
Figure 3: Illustraiion of step (DP sho-shot generation) in our framework (Fig. 2). The example
shows synthetic demonstration generated token by token for the topic school with DP. The operations in Alg. for one step of generation (the token College) are depicted step by step.
We solve this problem by generating synthetic few-shot examples C = [ En } from the underlying distribution of Pprvv while satistying (e, 6)D on the private dataset Pariv without fine- tuning LM (Fig. 2 From the post processing property of DP (Dwork & Roth 2014), this ensures that output in Eq. would also satisfy (c, 8)-DP with infinite number of queries.
We define prompt construction funetion PB Piinstrruttion, DV, y) V for LM that will enable the generation of synthetic samples given a label y, instructions for task and a list of private data samples 2; contained in DV, We define DV & {za ys = for {l...., ., [D[}} } if the dataset D can be disjointly separated into a fixed set of labels y V to generate samples from demonstrations of the same label class. For the open-form y label set, we simply take DD = D.
As example scenario, for basic sentiment analysis task, PB can construct the following prompt: Given a label of sent iment type, generate a review accordingly.
Label: Positive, Text: What fantastic movie!
Label: Positive, Text:
where the first sentence the instruction, the label y is positive and we provide a single demonstration from DV in this example. Each task has an associated PB, provided in Tab 6f Appendix B
4 PROPOSED METHOD
Our framework for ICL with DP guarantees consists of two steps (Fig.
1. A DP algorithm to generate synthetic few-shot examples based on the private dataset Dpáv-
Use the synthetic few-shot generations from step as ICL demonstrations during the inference.
The post-processing property of DP ensures that second step incurs no additional privacy cost. Our framework has the advantage that the first step can be performed entirely offline before the system is deployed for answering queries. In the following, we focus on describing the algorithm that implements the first step.
4.1 ALGORITHM FOR DP FEW-SHOT GENERATION
Alg. | presents the pseudo code of the proposed algorithm for the first step and Fig. provides demonstration with an example. For given label y, generate one token at time starting from an empty list. At each token generation, we randomly sample MN examples from the private dataset Doriv and partition them into M disjoint subsets of N samples each (lines 5). Each subset is appended with what is generated so far (+ is used for concatenation) and contributes with the probability generating the next token (line 6). Before private aggregation, the effect of noise can be reduced by limiting the vocabulary to the tokens that are present in top- K indices of the next-token
probability coming from only the instruction without using any private data (lines 7 10 Next-token generation probabilities obtained from each subset are then privately aggregated. We consider both the Gaussian mechanism (2) and Report-Noie NoroottNoisy-Maaa MMx with Exponential mechanism (lines 145). Finally, the next token is produced and appended to what is generated so far. This continues until we either get the special end of sequence (EOS) token or hit the limit of maximum number tokens we would like to generate.
By sampling K, rather than [V. random numbers, we significantly reduce the probability sampled an outlier as K & [V]; (3 the same technique was used in Tian et al. (0022).
4

---

Published as a conference paper at ICLR 2024
Algorithm 1: DP few-shot generation
Data:
Private dataset: Prriv label: y, max number tokens to generate: Tmxx a pre-trained
LLM: (-I--)): prompt construction function: ( noise multiplier: a, number of
disjoint subsets of private data: M, number of data samples in each subset: N, the DP
mechanism: Gaussian or Report-Noisy-Mat reduce vocab publicly (RVP) with top-
Result: Synthetic generation
2
11:
for t to Tiax do D(a)) f- randomly draw MN samples from DV prisi
for to M do
((1)
pay t- D(()) prv [(2 - 1)N EN];
Purie - LM (-1 | (inisttruction, Díñ + 2,u));
if RVP. is True then
p- - LM (- PB (instruction, 2, y))
S < top-K indices of p;
P < 0 and re-scale Ppny s.t. E Ppey [S] 1;
[Vi
11
DP mechanism Gaussian then
Ppriv + (Ei- Ppiv + (0 20
12
13
if DP mechanism is Report-Noisy-Mus then Pprv + Ppriv/ / where max, (privbi
Ppriv 1
25 (Ei= Ppiv Expo(o/2))
15
if RVP is True then
L < arg maxjes [i];
17
18
else
L arg maxjev Ppei
20
if w is EOS then
21
return 2;
22
- 3 [w]:
return 2;
Remark 4.1. We note that on line 6 our algorithm, we need access to LM that is trusted. That is, the LM generates a distribution on the next token by using the private data directly. This is not an issue in terms of performing ICI. with DP guarantees, as we wan! to ensure that demonstrations used during the inference are private. However, our framework is fleexible to be used the scenarios where may not want to trust the LM used for ICL. In such scenario, which needs to done only once and is entirely offline, and the second step of our algorithm use two different LMs. The first step be performed using trusted LM such as open source models, and the second step can make use of the DP synthetic demonstrations to an untrusted LM for ICL. We believe that this flexibility is a nice feature of our framework.
envision that the first step,
4.2 PRIVACY ANALYSIS
We defer full proof of the theorem below to Appendix A and give high-level ideas of the analysis.
Theorem 4.2. Alg. is (E, differentially private.
Proof Overview. Our proof follows the framework used analyzing DP-SGD algorithm (Abadi et al. 2016; Gopi et al. 2021). which consists of 3 steps. First, we show that each iteration of the algorithm is (e, DD with some privacy parameters: For the Gaussian mechanism this follows from bounding the fz-sensitivity of the term in line 12 For the variant using Exponential noise appeal to the Sooort-Noisy-Mel with Exponential Noise mechanism Dwork & Roth 2014). Next, argue that as algorithm draws MN samples from dataset of size 12 paivl there is privacy amplification by subsampling at each iteration. Finally, we appeal to numerical composition theorems (Theorem A.3 to compose privacy loss across Trax iterations of our subsampled DP algorithms. [1
5

---

Published as a conference paper at ICLR 2024
5 EXPERIMENTS
5.1
IMPLEMENTATION SETTINGS
We follow the prior ICL work (Zhao et al. 2021 and use the following setup
Datasets. We study 4-way news classification AGNews (Zhagg et al. 2015). way question classification TREC (Voorhees & Tice 2000), and 14-way topic classification DBPedia (Zhang et al.. 2013) datasets for classification tasks. For information extraction tasks, we study a slot filling dataset MIT Movies trivia10k13 (Liu et al. 2012), which consists of movie genre (MIT-G) and director name (MIT-D) as the slots to be filled. Further details about the datasets are provided in Appendix C
The prompt construction functions used in synthetic few-shot generations of Alg. are provided with examples for each dataset in Appendix B We use the synthetic few-shot generations {-1,-... F from Alg. T as demonstrations ICL for the downstream tasks above. We use the prompt format during ICL following prior work (Zhao et al. 202T) (see Tab. 7 in Appendix DD. We use the
calibration approach in Zhao al. (022) by default unless otherwise stated.
We present our main results on GPT-3 Babbage using the OpenAI API. We generate and use 4-shot demonstrations (randomly w/out replacement from the label set) for ICL. Ablation studies on varying numbers of shots, model size, and hyperparameters are deferred to Section 5.3 and Appendix
5.2 MAIN RESULTS
We present our main results in Tab. for various privacy levels. We fix d = 1/12priv however, with the advantage of privacy curves of DP mechanisms described in Appendix [A] smaller å is guaranteed with minor increase in (e.g., Alg. [ can be both (c = 1, 3 x 10 TD-D and
(c 1.9, 3 x 10 10-")-DP for AGNews dataset). We provide the mean and the standard deviation of the accuracy on the test data with ICL over 5 runs with different random seeds.
Table I: 4-shot ICL performance on the test set of downstream tasks with various baselines. e 0 (0-shot) and generate synthetic few-shot demonstrations for ICL. Our private solution with various privacy levels = 1, 4, and 8 uses Alg. to generate DP synthetic few-shot demonstrations for ICL. e oo is the non- non-private solution that reports the maximum of two performances for ICL: (i) using generations of our Alg. D with
(4-shot) are fully private solutions. The latter uses purely an instruction to
and (ii) using randomly chosen 4-shot samples from the private data. Our private solution, in general, provides substantial gains over the fully private baselines and achieves competitive results with the non-private cases.
Dataset
0 (0-shot)
(4-shot)
c=1
c=2
c=
c=
(= 00
Text Classification
AGNews
47.90.0
68.0p.s
64.13.9
63.55.7
71.34.6
68.7a.0
69.34.8
DBPedia
30.4o.0
60.41o.7
81.23.0
83.62.4
83.14.3
83.42.5
82.3g.7
TREC
35.40.0
45.7.0
50.7
48.6g.5
50.4g.s
51.3g.8
50.66.9
Information Extraction
MIT-G 17.2o.0
40.13.4
46.37.8
51.36.5
54.75.4
55.9
54.47.0
MIT-D 47.90.0
67.27.9
69.210.0
73.3
74.61.2
72.42.7
80.1o.7
We observe that compared to 0-shot performance, which is a fully private solution, our approach provides substantial gains even with strict privacy levels as small as e = Additionally, our approach is competitive with the non-private solution (e oc), therefore, enables similar performance while providing strong privacy guarantees for the original data samples. Note that we consider two approaches for do column; (i) running Alg. [ with selected from the private dataset. We present best of two accuracies between the two approaches. Notably, (i) performs better than (ii) for all the datasets except MIT-D.
0 and (ii) 4-shot demonstrations randomly
'Our repository is located at ht https::/// / thub. http://co//cccoo/////o/ooooo wtt.://pp-eww--oo-oooooooooo www.ssheettttttiiieeeee MIT-G and MIT-D results uncalibrated accuracies we did not observe improvement with calibration.

---

Published as a conference paper at ICLR 2024
c= (4-shot) column presents an interesting finding which can be of independent interest in the non-private domain. To disambiguate the benefits of private data from LM's own capability to generate relevant synthetic few-shot demonstrations,
rum the following experiment. We generate synthetic 4-shot samples [ži, .. 3d} using purely the instruction without any private data (i.e. running only line and auto-regressively generating the synthetic samples in Alg. []]. Using these samples in ICL over the test data is reported in = =0 (4-shot) column. We point out that the model can substantially improve its O-shot performance by generating relevant few-shot demonstrations with its existing capability. This can go to the extent that it can be fully competitive with even non-private performance for AGNews data. We believe that this behavior consistent with the recent chain-of-thought prompting (Wei et al. 2022) and Bayesian inference framework for ICL (Xie et al., 2022 Min et al. 2022). However, we do observe a significant improvement when {Zi,... 24 are generated with the help of private data in Alg. for all the other datasets, which shows the benefits of
using private data in ICL framework.
We provide the parameters that we use for our main results in Tab. 9 and the hyperparameter search in Tab. To 10 40114 respectively in Appendix [
We state here a number of important observations. First of all, when we reduce the vocabulary to top- 100100 tokens using public instruction during generation (i.e. RVP is True with K = 100 in Alg. D we do not observe high variation among the choices of M, N. This is good in terms of the stability of Alg. We notice that showing N > examples per subset helps in general although the hest -ggaa-to-noise ratio is achieved when N = for a fixed MN This possibly due reducing the effect of noise by limiting top-100 tokens from the public instruction. When we set RVP as False in Alg. [ we add noise to the full vocabulary during generation, which results in higher variation among the choices of N. As expected, the best performance is in general achieved for highest MN and N = 1 as this setting is the most optimal for signal-to-non to-noise ratio. Finally, we observe that setting RVP as False matches the performance of setting RVP as True in Alg. [ with largest M but that also comes with more queries to the LM per token generation.
5.3 ABLATION STUDIES
In this section, we conduct ablation studies on various number of shots, LM sizes, and DP mechanisms in Alg. Due to the sheer amount of experiments with 5 rounds each, we fix the dataset to DBPedia.
Varying number of shots. In Tab. [] we present the results with various number of shots for ICL. = 0 represents the performance of synthetic few-shot demonstrations that are generated with purely the instruction without any private data (i.e. running only line g in Alg. [ e = presents the performance of our private solution in Alg. [ We separately present two non-private performances; (i) running Alg. [ with o and (ii) n-shot samples randomly selected from the private dataset.
Table 2: ICL performance on the test set of DBPedia dataset with various number of shots. 0 is the fully private solution that uses purely the public instruction to generate synthetic few-shot demonstrations for ICL. 4 is based on the generations of our Alg. [ with private data for ICL. e = x0 (o = in Alg. [ uses the generations of our Alg. I with o 0 and e = oo (random) uses randomly chosen n-shot samples from the private data. Our approach substantially improves the performance of fully private solution and performs competitive with non-private solutions for 1, 2, and 4-shots. For 8 and 12-shots, demonstrations directly with private samples perform better, suggesting potential improvements of our approach for large n-shot scenarios.
1-shot
2-shot
4-shot
8-shot
12-shot
(
65.37.0
66.1
60.410.7
67.7s.2
62.2g.2
4
75.44.2
76.0s.7
83.14.3
82.71.0
80.724
(a oo
0, Alg.
74.75.4
74.86.5
82.33.7
81.52.3
81.92.8
c = 00 (random)
76.56.9
75.26.7
81.83.3
84.82.9
85.71.8
We observe that our approach consistently improves the fully private e = 0 performance for all the n-shot cases. Furthermore, our approach is competitive with both non-private performances for 1, 2, 4-shot cases. An interesting observation is that for 8-shot and 12-shot cases, randomly picking the samples from the private dataset yields better performance. Reducing the noise does not bridge this gap because é = and = oo (a in Alg. IT) have competitive performances. Therefore, this shows that Alg. is open to improvements for larger n-shot scenarios.
7

---

Published as a conference paper at ICLR 2024
Varying the model size. We next consider various model sizes (Ada, Babbage, Curie, and Davinci GPT-3 models) and present the results for ICL in Tab. 3 We note that generating synthetic few-shot demonstrations with purely the instruction without any private data (c 0 (4-shot) in Tab. improves ICL performance as the model becomes more capable with larger sizes as expected. Our approach provides further gains this fully private solution until the Davinci model, for which the fully private solution matches the non- con-prrvate solution. This emphasizes that very large language models can at times possess the information to solve task and while the naive O-shot approach does not provide good performance, one can extract useful information from the model's existing knowledge from the pre-training and use it in ICL to substantially improve the performance.
Table ICL performance on the test set of DBPedia dataset with various model sizes. The column descriptions follow similarly as Tab.[] Our approach substantially improves the performance of fully private solutions for Ada, Babbage, and Curie models. The most powerful Davinci model, although performs poorly in O-shot case, can generate useful demonstrations from its existing knowledge for itself to use it in ICL and even match the non- non-private solution.
Model
0 (0-shot)
0 (4-shot)
6 4
6
D (a = 0, Alg.
6 oo (rand)
Ada
26.4g.o
31.314.0
66.013.4
66.712.8
74.86.0
Babbage
30.40.0
60.4
83.14.3
82.33.7
81. 81.83.3
Curie
37.30.0
67.0g.4
74.68.7
75.45.6
82.04.9
Davinci
38.6o.0
90.42.0
87.22.6
87.71.9
88.92.1
Gaussian mechanism vs Exponential mechanism. We finally experiment with the Gaussian and Exponential mechanisms for the DP mechanism in Alg. [ and present the results in Tab. 4 Tab. shows that instantiating Alg. | with different DP mechanisms at E {1, 4,8) 8} provides competitive performances. Here, we point out advantages and disadvantages of Gaussian and Exponential mechanisms. As stated in Appendix A the Exponential mechanism is based on Report-Noisy-Mat framework, which can only generate a token with the highest noisy probability to satisfy DP. In contrast, the Gaussian mechanism benefits from the post-prov post-processing property of DP and is suitable for more advanced sampling techniques beyond arg max such as nucleus sampling (Holtzman et al., 2020). Finally, Exponential mechanism gives a pure DP guarantee of á = O which can be of interest in some scenarios. However, we insist on 8 = during the composition the privacy loss across Tmax iterations, our subsampled DP algorithm leads privacy loss that grows linearly in Tmax-
Table ICL performance on the test set of DBPedia dataset comparing Gaussian and Exponential mechanisms for the DP mechanism in Alg. [ We observe in general competitive performances between the two DP mechanisms.
Mechanism 6
E E=
==
Gaussian
81.23.0
83.62.4
83.
83.42.
Exponential
80.44.
81.03.8
80.94.8
81.24.1
Furthermore, we perform an empirical privacy analysis in Appendix |] via membership inference attacks (MIA) (Shokri et al., al.,2211) [0177] Duan al. (2023). The result shows that while the non-private ICL incurs a significant membership privacy leakage, the DP few-shot samples generated by Alg. effec- tively reduce MIA to random guess. Finally, we discuss the monetary cost of Alg. in Appendix G
and provide randomly chosen generated synthetic samples in Appendix
6 RELATED WORK
In this work, we focus on in-context learning (ICL) framework, where few demonstrations from dataset suffices LLMs to perform well on downstream task without requiring any fine-tuning as recently observed in Brown al. (020). As focus the preeeccieeeeviinggg aspect of the ICL framework, we refer the readers to the survey (Dong et al. 2023) and the references therein for an extensive study about this popular direction."
In the context of preseevinee ICL, very recently, Wu et al. (0024) propose DP inference by privately constructing consensus over an ensemble of queries with disjoint sampled demonstrations.
8

---

Published as a conference paper at ICLR 2024
Although this approach adheres to DP guarantees, it expends the privacy budget for each query. Hence, for a given privacy budget, their algorithm can only answer few limited number of queries where approach can answer unbounded number of queries.
In another recent work. Duan et al. (023) propose an approach that also relies on private ensembling. However, their approach assumes access some unlabeled public data, which is privately labeled by an ensemble of teachers with ICL via demonstrations from the private dataset. Privately labeled public data is finally used as the prompt for ICL. This is in contrast to our approach that does not require any public data. Our framework is more suitable for the scenarios where the availability of unlabeled public data that has similar distribution as the private data may be a strong assumption; examples include health care datasets or industrial applications.
Our work focuses on privacy-preservee private fine-tuning Yu et al., 2022. Li et al., 2022). We leverage the capabilities of LLMs (Brown al., 2020) that can generate text that is similar the given demonstrations and convert this process into a DP one via privately aggregating the generation probabilities obtained from disjoint subsets of demonstrations from the private data. This approach in spirit similar to Private Aggregation of Teacher Ensembles (PATE) framework (Papernot et al. 2017 2018), which produces a private model via fine-tuminn tinettunngg with public data, which is privately labeled using an ensemble of teachers that trained on disjoint subsets of the private data. In this line of work, SeqPATE (Tian et al., 2022)
few-shot generation for ICL without the heavy burden of
and Submix (Ginart et al.) 2022) extend the PATE framework to text generation via several design adaptions for text domain. On the other hand, Majmudar et al. (2022) introduces DP at the decoding stage of a pre-trained LLM by combining the prediction vector of the pre-trained LLM and uniform distribution for DP decoding. Note that these private inference methods still require (non-private) training the model with the private data to adapt to the specific data domain.
Our work can be seen as an instantiation of the more general synthetic text generation with privacy framework. As opposed to the approaches that require private fine-tuning ( (Yue et al.) [003]] Mattern al., 2022a| Mireshghallah et al. 2023] Carranza et al. 2023) in this direction, we introduce light- weight approach that can utilize LLMs without needing the computationally prohibitive fine-tuning. We point out that our work is efficient and effective in ICL framework where few-shot demonstrations suffice. However, we believe that private fine-tuning would be more effective within applications that require generating large volume of synthetic data.
We finally review an active area of research on the generation of sanitized text documents. In this (CaraloCa domain, Feyisetan et al. (2020); Xu et al. (2020); Carvalho et al. (2021); Du et al. (2023) add noise at the word level and metric local differential privacy (Chatzikokolakis et al. (2013). Mattern et al. (002bb); Utpala et al. (2023) directly operate on documents using local differential privacy (LDP) (Kasiviswanathan al. 2010 Duchi et al.) (2033) where the former is based on fine-tuning for paraphrasing and the latter uses zero-shot prompting for paraphrasing followed by sanitization.
7 CONCLUSION AND FUTURE WORK
In this work, we introduce a new algorithm that generates synthetic few-shot demonstrations from private dataset to be used for ICL, and guarantees DP with respect to examples in the private dataset. We demonstrate that our algorithm can provide formal privacy protection via DP with minimal loss in the ICL performance through empirical studies. Along the way, we present interesting findings in the non- non-private domain. We show that zero performance of LLMs can be significantly improved by asking the model itself to generate demonstrations required for ICI. and subsequently using them.
The main weakness of our Alg. T repeating line and 5 i.e. resampling the demonstrations from the private dataset for each token generation. It would be more natural to fix the demonstrations from the private dataset and generate one synthetic sample all at once. Unfortunately this does not benefit from the amplification of privacy by subsampling theorem and requires much higher levels of noise additions. We believe that our algorithm can be improved on this front in future work. Furthermore, as stated in Section 5.3 Gaussian mechanism benefits from the post-processing of DP and more advanced sampling techniques for token generation can be used instead of the basic arg max sampling. We leave the exploration of this to future work.
9

---

Published as a conference paper at ICLR 2024
REFERENCES
Martin Abadi, Andy Chu, lan Goodfellow, H Brendan McMahan, llya Mironov, Kunal Talwar, and Li Zhang. Deep learning with differential privacy. In Proceedings of the 2016 ACM SIGSAC Conference on Computer and Communications Security, pp. 308 318, 2016.
Art. 29 WP. Opinion 05/2014 on "Anonymisation Techniques" 2014. w0tps///RtRttttt///eeeeeee
eu/
f1 #lle/2014//p216..0
Borja Balle and Yu-Xiang Wang. Improving the gaussian mechanism for differential privacy: Analytical calibration and optimal denoising. In International Conference on Machine Learning. pp. 394-403, PMLR, 2018.
Borja Balle, Gilles Barthe, and Marco Gaboardi. Privacy amplification by subsampling: Tight analyses via couplings and divergences. Advances in Neural Information Processing Systems, 2018.
Alberto Blanco-Justicia, David Sanchez, Josep Domingo-Ferrer, and Krishnamurty Muralidhar. A critical review on the use (and misuse) of differential privacy in machine learning. ACM Computing Surveys, 55(8): 1-16, 2022.
Tom Brown, Benjamin Mann, Nick Ryder, Melanie Subbiah, Jared D Kaplan, Prafulla Dhariwal, Arvind Neelakantan, Pranav Shyam, Girish Sastry, Amanda Askell, Sandhini Agarwal, Ariel Herbert- Voss, Gretchen Krueger, Tom Henighan, Rewon Child, Aditya Ramesh, Daniel Ziegler, Jeffrey Wu, Clemens Winter, Chris Hesse, Mark Chen, Eric Sigler, Mateusz Litwin, Scott Gray, Benjamin Chess, Jack Clark, Christopher Berner, Sam McCandlish, Alec Radford, Ilya Sutskever, and Dario Amodei. Language models are few-shot learners. In Advances in Neural Information Processing Systems, pp. 1877-1901, 2020.
Aldo Gael Carranza, Rezsa Farahani, Natalia Ponomareva, Alex Kurakin, Matthew Jagielski, and Milad Nasr. Privacy-preserving recommender systems with synthetic query generation using differentially private large language models. arXiv preprint arXiv:2305.05973. 2023.
Ricardo Silva Carvalho, Theodore Vasiloudis, and Oluwaseyi Feyisetan. Tem: High utility metric differential privacy on text. arXiv preprint arXiv:2107.07928 2021.
Konstantinos Chatzikokolakis, Miguel E Andrés, Nicolás Emilio Bordenabe, and Catuscia Palamidessi. Broadening the scope of differential privacy using metries. In Privacy Enhanc- ing Technologies: 13th International Symposium, PETS 2013, Bloomington, IN, USA, July 10-12, 2013. Proceedings 13, pp. 82-102. Springer, 2013.
Zeyu Ding, Daniel Kifer, Thomas Steinke, Yuxin Wang, Yingtai Xiao, Danfeng Zhang, et al. The permute-and-lipp mechanism identical to report-noisy-max with exponential noise. arXiv preprint 105::22000.0260. 2021.
Qingxiu Dong, Lei Li, Damai Dai, Ce Zheng, Zhiyong Wu, Baobao Chang, Xu Sun, Jingjing Xu, Lei Li, and Zhifang Sui. A survey on in-context learning. arXiv preprint arXiv:2301.00234 2023.
Minxin Du, Xiang Yue, Sherman SM Chow, and Huan Sun. Sanitizing sentence embeddings (and labels) for local differential privacy. In Proceedings of the ACM Web Conference 2023, pp. 2349-2359, 2023.
Haonan Duan, Adam Dziedzic, Nicolas Papernot, and Franziska Boenisch. Flocks of stochastic parrots: Differentially private prompt learning for large language models. In Advances in Neural Information Processing Systems, 2023.
John C. Duchi, Michael I. Jordan, and Martin J. Wainwright. Local privacy and statistical minimax rates. In 2013 IEEE 54th Annual Symposium on Foundations of Computer Science, pp. 439- 2013. doi: 10.1 109/FOCS. 201.3.
Cynthia Dwork and Aaron Roth. The algorithmic foundations differential privacy. Foundations and Trendy in Theoretical Computer Science, 9(3-4):211400 2014.
10

---

Published as a conference paper at ICLR 2024
Cynthia Dwork, Krishnaram Kenthapadi, Frank McSherry, llya Mironov, and Moni Naor. Our data, ourselves: Privacy via distributed noise generation. In Proceedings of the 24th Annual International Conference the Theory and Applications of Cryptographic Techniques, EUROCRYPT '06, pp. 486-503. Springer, 2006a.
Cynthia Dwork, Frank McSherry Kobbi Nissim, and Adam Smith. Calibrating noise to sensitivity in private data analysis. In Proceedings of the 3rd Conference on Theory of Cryptography, TCC '06, pp. 265-284. Springer, 2006b.
Oluwaseyi Feyisetan, Borja Balle, Thomas Drake, and Tom Diethe. Privacy-and utility-preserving textual analysis via calibrated multivariate perturbations. In Proceedings of the 13th International Conference on Web Search and Data Mining, pp. 178-186, 2020.
Antonio Ginart, Laurens van der Maaten, James Zou, and Chuan Guo. Submix: Practical private prediction for large-scale language models. arXiv preprint arXiv:2201.00977 2022.
Sivakanth Gopi, Yin Tat Lee, and Lukas Wutschitz. Numerical composition of differential privacy. In Advances in Neural Information Processing Systems, pp. 1631-11642, 2021.
Ari Holtzman, Jan Buys, Li Du, Maxwell Forbes, and Yejin Choi. The curious case of neural text degeneration. International Conference on Learning Representations, 2020.
Shiva Prasad Kasiviswanathan, Homin K. Lee, Kobbi Nissim, Sofya Raskhodnikova, and Adam Smith. What can we learn privately? arXiv preprint arXiv:0803.0924, 2010.
Xuechen Li, Florian Tramèr, Percy Liang. and Tatsunori Hashimoto. Large language models can be strong differentially private learners. In International Conference on Learning Representations, 2022.
Jingjing Liu, Scott Cyphers, Panupong Pasupat, Ian McGraw, and James R. Glass. A conversational movie search system based on conditional random fields. In Interspeech 20/2, pp. 2454-2457, 2012.
Jimit Majmudar, Christophe Dupuy, Charith Peris, Sami Smaili, Rahul Gupta, and Richard Zemel. Differentially private decoding in large language models. arXiv preprint urXiv:2205. 13621, 2022.
Justus Mattern, Zhijing Jin, Benjamin Weggenmann, Bernhard Schoelkopf, and Mrinmaya Sachan. Differentially private language models for secure data sharing. In Proceedings of the 2022 Conference on Empirical Methods in Natural Language Processing, pp. 18660-8773 2022a.
Justus Mattern, Benjamin Weggenmann, and Florian Kerschbaum. The limits of word level differential privacy. In Findings of the Association for Computational Linguistics: NAACL 2022, pp. 867-881, 2022b.
Ryan McKenna and Daniel R Sheldon. Permute-and-flip- A new mechanism for differentially private selection. Advances Neural Information Processing Systems, 13:199-203, 2020.
Sewon Min, Xinxi Lyu, Ari Holtzman, Mikel Artetxe, Mike Lewis, Hannaneh Hajishirzi, and Luke Zettlemoyer. Rethinking the role of demonstrations: What makes in-context learning work? In Proceedings of the 2022 Conference on Empirical Methods in Natural Language Processing, pp. 11048-11064 Association for Computational Linguistics, 2022.
Fatemehsadat Mireshghallah, Yu Su, Tatsunori Hashimoto, Jason Eisner, and Richard Shin. Privacy- preserving domain adaptation of semantic parsers. In Proceedings of the 61st Annual Meeting of the Association for Computational Linguistics (Volume 1: Long Papers), pp. 4950 4970. Association for Computational Linguistics, 2023.
Nicolas Papernot, Martín Abadi, Ulfar Erlingsson, Ian Goodfellow, and Kunal Talwar. Semi- supervised knowledge transfer for deep learning from private training data. In International Conference on Learning Representations, 2017.
Nicolas Papernot, Shuang Song, Ilya Mironov, Ananth Raghunathan, Kunal Talwar, and Úlfar Erlingsson. Scalable private learning with PATE. In International Conference on Learning Representations, 2018.
11

---

Published as a conference paper at ICLR 2024
Aman Priyanshu, Supriti Vijay, Ayush Kumar, Rakshit Naidu, and Fatemehsadat Mireshghallah. Are chatbots ready for privacy-sensitive applications? an investigation into input regurgitation and prompt-induced sanitization. arXiv preprint arXiv:2305.15008 2023.
Reza Shokri, Marco Stronati, Congzheng Song, and Vitaly Shmatikov. Membership inference attacks against machine learning models. In Proceedings of the 38th IEEE Symposium on Security and Privacy, SP 17. pp. 3-18. IEEE Computer Society, 2017.
Zhiliang Tian, Yingxiu Zhao, Ziyue Huang, Yu-Xiang Wang, Nevin L. Zhang, and He He. Seqpate: Differentially private text generation via knowledge distillation. In Advances in Neural Information Processing Systems. pp. 11117-111 1130, 2022.
Jonathan Ullman. Cs7880: Rigorous approaches to data privacy, spring 2017. URL http://www. ccs. neu, eltchome//ulhaa/////8/////////
pdf, 2017.
US Census Bureau. Official release of source code for the disclosure avoidance system (das) used to protect against the disclosure of individual information based on published statistical summaries, 2020. URL http:///hhuu..ccom/sccccsssuueea
Production_Code
Saiteja Utpala, Sara Hooker, and Pin- Yu Chen. Locally differentially private document generation using zero shot prompting. In Findings of the Association for Computational Linguistics: EMNLP 2023, pp. 8442 8457, 2023.
Ellen M. Voorhees and Dawn M. Tice. Building a question answering test collection. In Proceedings of the 23rd Annual International ACM SIGIR Conference on Research and Development in Information Retrieval, pp. 200 207, 2000.
Boxin Wang, Weixin Chen, Hengzhi Pei, Chulin Xie, Mintong Kang, Chenhui Zhang, Chejian Xu, Zidi Xiong, Ritik Dutta, Rylan Schaeffer, Sang T. Truong, Simran Arora, Mantas Mazeika, Dan Hendrycks, Zinan Lin, Yu Cheng, Sanmi Koyejo, Dawn Song, and Bo Li. Decodingtrust: A comprehensive assessment of trustworthiness in GPT models. In Advances in Neural Information Processing Systems, 2023.
Jason Wei, Xuezhi Wang, Dale Schuurmans, Maarten Bosma, brian ichter, Fei Xia, Ed Chi, Quoc V Le, and Denny Zhou, Chain-of-thouu thought prompting clicits reasoning in large language models, In Advances in Neural Information Processing Systems, pp.
2022.
Tong Wu, Ashwinee Panda, Jiachen T. Wang, and Prateek Mittal. Privacy-preserving in-context learning for large language models. In International Conference on Learning Representations, 2024.
Sang Michael Xie, Aditi Raghunathan, Percy Liang, and Tengyu Ma. An explanation of in-context learning as implicit bayesian inference. In International Conference on Learning Representations 2022.
Zekun Xu, Abhinav Aggarwal, Oluwaseyi Feyisetan, and Nathanael Teissier. differentially private text perturbation method using regularized mahalanobis metric. In Proceedings of the Second Workshop on Privacy in NIP., pp. 7-17. Association for Computational Linguistics, 2020.
Da Yu, Saurabh Naik, Arturs Backurs, Sivakanth Gopi, Huseyin A Inan, Gautam Kamath, Janardhan Kulkarni, Yin Tat Lee, Andre Manoel, Lukas Wutschitz, Sergey Yekhanin, and Huishuai Zhang Differentially private fine-tuning of language models. In International Conference on Learning Representations, 2022.
Xiang Yue, Huseyin Inan, Xuechen Li, Girish Kumar, Julia McAnallen, Hoda Shajari, Huan Sun, David Levitan. and Robert Sim. Synthetic text generation with differential privacy: A simple and practical recipe. Proceedings of the 61 Annual Meeting of the Association for Computational Linguistics ( (Volume I: Long Papers), pp. 1321-1342, 2023.
Xiang Zhang, Junbo Zhao, and Yann LeCun. Character-level convolutional networks for text classifi- cation. In Proceedings of the 28th International Conference on Neural Information Processing Systems Volume 1, NIPS' 15, pp. 649-657. MIT Press, 2015.
12

---

Published as a conference paper at ICLR 2024
Tony Zhao, Eric Wallace, Shi Feng, Dan Klein, and Sameer Singh. Calibrate before use: Improving few-shot performance of language models. In International Conference on Machine Learning, pp- 12697-12706. PMLR, 2021.
A PROOF OF THEOREM 4.2
We introduce some concepts and relevant theorems from the literature required for analysis.
Many DP algorithms, notably Gaussian mechanism, come with a collection of (e, 6)-DP guarantees; this means that for every fixed e, there is choice of which is function of e, such that overall mechanism is (e, 6)-DP.
Definition A.1. (Privacy curve) DP algorithm M said to have privacy curve 8: (0, if for every the algorithm M is (c,((c))-DP?
The following theorem concerning the privacy curve of Gaussian mechanism is due to Balle & Wang (0118).
Theorem A.2. Let J X - be function with global f2 f2-sensitivity A. For any 6 > 0 and 5 E 1). the Gaussian outpul perturbation mechanism (x) f(x) Z with Z o)) is
(e, DDDP if and only if
60 A
60
c¹
8
20
20
The advantage of working with privacy curves of DP mechanisms is that it can be used to get tighter guarantees on the composition compared to the advanced composition theorems (Dwork Roth 2014). In particular, one do numerical composition of privacy curves, which gives the tightest guarantees.
Theorem A.3 (Gopi et (021 )) Suppose M1, M2,..., My are DP algorithms. Then the privacy curve dM (e) of adaptive composition M = M1 o M2 o... Ms can be approximated in time
Cupper 1/2 log log( B
Cervor
where Ceroor is the additive error in and Semor is the additive error in and Cupper is upper bound on
&eeror
max eM (demor))) max E.M
The work of Gopi et al. (2021) gives privacy curves for composition of several standard mechanisms such as Gaussian mechanism, Laplace mechanism, and subsampled Gaussian mechanism.
The variant of algorithm using exponential noise is based the Report Noisy Max with Expo- nential noise mechanism (Dwork & Roth 2014). The exponential distribution, denoted by (X). -Ax -xr)11200 The mean of Expo(A) is 1/A. This algorithm adds to every possible output noise drawn from Expo( 2 and reports the resulting arg-max, where the loo -sensitivyy of the resulting output (or more generally scoring function used select the outputs). It was shown in Ding et al. (2021) that the Report Noisy Max with Exponential noise is equivalent the Permute-and- as an improvement over the popular exponential mechanism.
has the density function [(;; = eexp
mechanism, which was proposed by McKenna & Sheldon (020))
Theorem A.4. Report Noisy Max with Exponential Noise mechanism when run with Expo( 24 noise is O).D..
Unlike the Gaussian mechanism, this mechanism gives pure DP guarantee; i.e., 8 = 0. Finally, we
need the following amplification of privacy by subsampling theorem due to Ullman (017 Balle
et al. 2018).
Theorem A.5. If M is (e, then the subsampled mechanism with sampling rate y obeys (e', 8') DDP with privacy parameters
è' log(1 + - 1)) and 8' =76
13

---

Published as a conference paper at ICLR 2024
We are ready to do privacy analysis of our algorithm (Theorem 4.2)
Proof. Consider the Gaussian mechanism first. Fix one iteration of the algorithm and let us bound the privacy loss. In line 12 l fg-sensitivity of the temn [i=1 Ppriv) is at most v2. As are adding noise sampled from A (0, 2), it follows that our algorithm has the same privacy curve as given in Theorem A.2 Further, note that in each iteration we draw MN samples from a dataset of size [privl Thus the effective privacy curve of our algorithm per iteration is given by the privacy curve of subsampled Gaussian mechanism, which is calculated in Gopi et al. (2021). Thus, the output of our algorithm Ppei on line satisfies (e, 6D-DP guarantees, and further operations done by our algorithm on the Periv does not violate the privacy guarantees due to the post post-processing property of DP (Dwork Roth 2014). To get an upper bound on the privacy loss across all T maa iterations, we appeal to Theorem A.3 for composing of Taax privacy curves of subsampled Gaussian mechanisms (Gopi
ct al. 2021).
Our analysis of the variant with Exponential noise follows similar overall recipe as the analysis of the Gaussian mechanism, although here we do not argue about the overall privacy of the term Let's argue that each iteration of our algorithm is (e, O)-D.. Consider line 15 and we begin by noting that &oo sensitivity (EA- Prris
Ppriv on line 15 but rather only on the term on line 17 19
is at most 1. As the output of each iteration is w + arg max Ppri [j], it follows from Report-Noisy- Max with Exponential Noise mechanism (Theorem ( that it is (a, O)-DP for the sampled subset. Our algorithm draws MN samples from the dataset of size [Dpriv) we get amplification of privacy parameters due to Theorem A.5
We conclude that the effective privacy loss per iteration of our algorithm is = log(1 + for the fully dataset at each step. Finally, get an upper bound on the privacy loss across all Tmaz iterations, we appeal to Theorem A.3
M. (e" 1))
[Pass]
As Theorem A.3 is based numerical composition, the final privacy parameters of algorithms do not have closed forms. Readers can refer to Abaaii et (2016) to get an analytical expression of the privacy loss, although it does provide the tight upper bound.
Remark A.6. We want note a minor technicality in the privacy analysis of Theorem 4.2 for
MN (instead of the Gaussian noise. The analysis works for Poisson subsampling with rate y [D
sampling without replacement of MN users from frorsfrom priie), where the neighboring datasets obtained by adding/removing user. In our experiments, for ease of implementation and training stability, we used sampling without replacement instead of Poisson sampling. However, these two sampling methods are upproximately the same. For the Report-Noisy-Mus variant, the analysis works for sampling without replacement when the neighboring datasel is obtained by changing a user's data, i.e., substitution (see Ullman 2017); Balle et al. (2018). ).
B PROMPT CONSTRUCTION FUNCTIONS FOR EACH TASK IN SECTION 5
In Tab. 5 and we provide our prompt construction function PBinstruuction, DV, y) for each task in
Section 5
C DATASETS USED IN SECTION 5
AGNews The AG News (AG's News Corpus) dataset (Zhang et al. 2015) consists of news articles belonging one of the 4 labels (World, Sports, Business, Sci/Tech). The AG News has 30,000 training and 1,900 test samples per class.
The Text REtrieval Conference (TREC) question classification dataset VVorhees & Tice 2000) consists of questions that have answers belonging of the 6 answer types (Number, Location, Person, Description, Entity, Abbreviation). The TREC has in total 5,500 training and 500 test samples that are non-uniform across the labels.
TREC
14

---

Published as a conference paper at ICLR 2024
Table 5: Prompt construction function PB[isstruction, D y) for each text classification task in Section 5
The prompt starts with the instruction in the first sentence and then follows a demonstration from D and finally generation is expected from LM with label y.
Task
Prompt constmuction function (in(sttruttioon D y)
Labels
AGNews
Given label of news type, generate the chosen type of news accordingly.
World, Sports, Business, Technology
News Type: World
Text: Australia boosts anti-terror measures at small air- ports SYDNEY The Australian government announced a major security upgrade for nearly... ...
News Type: World Text:
DBPedia
Given label of document type, generate the chosen type document accordingly.
Company, School, Artist, Athlete, Politician, Trans- portation, Building, Nature, Village. Animal, Plant, Al- bum, Film, Book
Document Type: Company
Text: Cherry Lane Music was founded 1960 by Milton Okun in the apartment above the Cherry Lane Theater in Greenwich Village of New York City...
Document Type: Company Text:
TREC
Given label of answer type, generate question based the given answer type accordingly.
Number, Location, Person, Description, Entity, Abbrevi- ation
Answer Type: Number
Text: How many people in the world speak French ?
Answer Type: Number
Text:
Table 6: Prompt construction function PB (instruction, DM y) for each information extraction task in Section [ The prompt starts with the instruction in the first sentence and then follows a demonstration from D and finally generation is expected from LM with label y.
Task
Prompt construction function Piiisttruction, D DV,y)
MIT-G
Given genre for the film, generate description accordingly and make sure to include the given genre in the description.
Genre: holiday
Sentence: what the name this perennial holiday favorite featuring an elderly miser learning the error of his ways thanks to three ghostly visitations
Genre: action
Sentence:
MIT-D
Given director for the film, generate description accordingly and make sure include the given director description.
Director: pixar
Sentence: what pixar animated film features a talking dog named dug
Director: disney
Sentence:
15

---

Published as a conference paper at ICLR 2024
DBpedia The DBpedia ontology classification dataset Zhang et al., 2013) consists of contents belonging one the 14 topics (Company, School, Artist, Athlete, Politician, Transportation, Building, Nature, Village, Animal, Plant, Album, Film, Book). The DBpedia has 40,000 training samples and 5,000 testing sample per class.
MIT Movies MIT Movies trivia 10k13 dataset (Liu et al. 2012) consists of movie reviews that have slots (movie genre (MIT-G) and director name (MIT-D) to be used for information extraction task. MIT-G has 2,953 training samples and 100 test samples whereas MIT-D has 1,561 training samples and 100 test samples.
D PROMPT FORMAT DURING ICL FOLLOWING PRIOR WORK ZHAO ET AL. (2021)
While we use the same prompt format during ICL following prior work by Zhao et al. (2021) we present them here in Tab. 7 and 8 for the convenience of the reader.
Table 7: The prompts used during ICL for text classification tasks, taken from Tab. 5 of Zhao et al. 1222)).
Task
Prompt
Labels
AGNews
Classify the news articles into the categories of World, Sports, Business, and Technology.
World, Sports. Business, Technology
Article: USATODAY.com- Retail sales bounced back bit in July, and new claims for jobless benefits fell last week, the government said Thursday, indicating the economy is improving from midsummer slump.
Answer:
Business
Article: New hard-drive based devices feature color screens, support for WMP 10.
Answer:
DBPedia
Classify the documents based on whether they are about Company, School, Artist, Athlete, Politician, Transportation, Building, Nature, Village, Animal, Plant, Album, Film, or Book.
Company, School, Artist, Athlete, Politician, Trans- portation, Building, Nature, Village, Animal, Plant, Al- bum, Film, Book
Article: Geoffrey D. Falksen (born July 1982) an American stcampunk writer.
Answer: Artist
Article: The Perrin River is a 1.3-mile-long (2.1 km) tidal river in the U.S. state of Virginia. It is small inlet the north shore of the York River near that river's mouth at Chesapeake Bay. Answer:
TREC
Classify the questions based on whether their answer type is Number, Location, Person, Description, Entity, or Abbreviation.
Number, Location, Person, Description, Entity, Abbrevi- ation
Question: How did serfdom develop in and then leave Russia?
Answer Type: Description
Question: When Ozzy Osbourne bomn?
Answer Type:
16

---

Published as a conference paper at ICLR 2024
Table 8: The prompts used during ICL in information extraction tasks, taken from Tab, of Zhao et al. 2
Task
Prompt
MIT-G
Sentence: last to famous series of animated movies about a big green ogre and his donkey and cat friends
Genre: animated
Sentence: what is great comedy featuring the talents of steve carell as a loser looking for a friend
Genre:
MIT-D
Sentence: in 2005 director christopher nolan rebooted legendary de comics superhero with a darker grittier edge in which movic
Director: christopher nolan
Sentence: what 1967 mike nichols film features dustin hoffman in romantic interludes with anne bancroft robinson Director:
HYPERPARAMETER SEARCH
Hyperparameters for the main results presented in Tab. Tare provided in Tab. 9
Hyperparameter
search results for all the datasets are provided in Tab. 10 14
Table 9: Hyperparameters for the main results presented in Tab. using the OpenAl API.
When RVP is True, we simply
take t0p-100 token (K 100 Alg I
Dataset
min, D
M
RVP
T Tmax
DP
a for e = 2,
priv
AGNEWS
30,000
10
2
True
100
Gaussian
[0.51, 0.46, 0.39, 0.31]
DBPedia
40,000
40
True
100
Gaussian
[0.63, 0.54, 0.45, 0.36]
TREC
835
80
False
15
Gaussian
[1.36, 0.95, 0.69, 0.51]
MIT-G
2,953
20
4
True
20
Gaussian
[1.08, 0.81, 0.64, 0,50]
MIT-D
1,561
20
True
20
Gaussian
[1.52, 1.04, 0.77, 0.58)
Table 10: Hyperparameter search results for the AGNews dataset for 4 on GPT-3 Babbage model with 4-shot demonstrations for ICI.
(a) RVP=True
(b) RVP=False
N =
=
N = 4
N
N 2
N =
MN 20
65.0g.4
71.34.6
65.2
MN 20
61.7s.0
52.66.9
49.07.0
M N = 40
68.2 68.21.3
69.23.6
67.44.8
MN = 40
64.65.9
58.7s.1
58.52.
MN 80
67.4 67.42.8
68.31.0
67.33.3
MN 80
66.12.0
63.0s.9
53.410.6
Table 11: Hyperparameter search results for the DBPedia dataset for 4 on GPT-3 Babbage model with 4-ohot demonstrations for ICL.
(a) RVP=True
(b) RVP=False
N 1
N 2
N
N
N
N =
MN 20
81.1a.2
81.51.
80.76.8
M 20
68.72.4
64.42.7
49.8s.4
MN 40
79.6a.a
81.53.4
81.25.3
MN 40
77.63.4
67.99.8
67.0g.8
MN 80
78.91.9
83.14.3
81.43.6
MN 80
78.73.2
81.9
67.417.8
17

---

Published as a conference paper at ICLR 2024
Table 12: Hyperparameter search results for the TREC dataset for 4 on GPT-3 Babbage model with s-shot demonstrations for ICL.
(a) RVP=True
(b) RVP=False
N =1
=
N = 4
N =1
N=
N =
MN 20
46.23.3
41.73.9
42.75.7
MN 20
46.87.9
44.82.7
43.69.4
M N 40
46.94.2
46.43.8
45.66.3
MN 40
48.82.2
44.03.5
43.84.7
MN 80
49.26.0
47.26.0
44.72.6
MN 80
50.45.5
47.06.0
45.44.0
Table 13: Hyperparameter search results for the MIT-G dataset for 4 on GPT-3 Babhage model with 4-shot demonstrations for ICI..
(a) RVP=True
(b) RVP=False
N =
N
N
N
N =
MN N = 20
53.02.3
47.55.1
35.15.6
MN 20
46.57.0
23.0
12.02.9
MN 40
53.45.4
54.14.6
45.77.3
MN 40
51.25.2
55.43.5
31.9
MN = 80
53.15.3
51.15.2
54.75.4
MN = 80
53.24.2
51.85.9
50.5p.8
Table 14: Hyperparameter search results for the MIT-D dataset for = 4 on GPT-3 Babbage model with 4-shot demonstrations for ICL.
(a) RVP=True
(b) RVP=False
N
1
=
=
N
N
N = 4
MN 20
71.56.6
70.87.7
65.1
MN 20
69.74.1
9.2s.5
5.72.7
MN = 40
70.25.9
71.47.6
68.2s.5
MN = 40
72.23.2
66.86.3
9.95.2
MN = 80
69.85.9
70.56.0
74.64.2
MN = 80
71.43.2
78.02.2
40.719.16
EMPIRICAL PRIVACY EVALUATION BY MEMBERSHIP INFERENCE ATTACKS
While differential privacy provides the theoretical guarantee to privacy leakage, is also important to evaluate the empirical privacy leakage (Blanco-Justicia et al. 2022). To better understand the privacy protection our DP few-shot generation for in-context learning. we empirically evaluate the privacy of our methods by membership inference attack (MIA) (Shokri et al. 2017), that is widely used for estimating the practical privacy leakage.
We follow the prior work (Duan al. 2023 that instantiates MIA in the framework of in-context learning. The goal of their attack to determine if given data point was used within the prompt of the LLM. Perhaps expectedly, using actual samples from the private dataset leads successful MIA results. To apply the MIA for our DP few-shot generation, we take the following approach. We study the DBPedia dataset and split the dataset in two parts for member and non-member samples. We the member samples to generate synthetic demonstrations with our DP algorithm. Similar to Duan al. (2023), we consider 1-shot ICL on the Babbage model and generate 1-shot demonstrations in 5 independent runs for [1, 2, 4, 8). For MIA against DP few-shot generation, we make queries for 50 samples from members and 50 from non-members, and calculate the TPR/FPR, For each DP generated demonstrations,
20 trials for MIA and we finally average across the 100 trials to calculate the averaged AUC for each e. For the MIA against non-private 1-shot ICL, we follow Duan et al. (2023), the 1-shot in prompt is the member sample and we sample 50 non-member samples. We repeat 100 trials and compute the averaged AUC.
We present the membership privacy attack result in Tab. 15 Similar Duan et al. (2023), observe that using actual samples from the private dataset leads to successful MIA results (81.84 corresponding oo). On the other hand, our DP solution reduces the AUC of MIA almost
18

---

Published as a conference paper at ICLR 2024
Table 15: Empirical privacy evaluation for 1-shot ICL by MIA on Babbage model.
2
AUC 50.56
50.58
50.55
50.53
81.84
random guesses. demonstrating the effectiveness of our privacy-preserve methodology for ICL. is interesting to observe that even for theoretically large epsilon value such as 8, MIA attack remains close to random guess, which presents promising (empirical) privacy-utility tradeoffs.
G MONETARY COST
We provide the monetary cost of running Alg. For each token generation, make M API calls in Alg. [ For each sample, we generate at most T Taa tokens. The total number of token processed by the API calls is proportional to M x ΣiEp P tokens, where P is the (expected) prompt length. We could estimate by computing the average of token length in the training set and the token length of additional instruction as shown in Tab. and Tab.
We provide the estimation of monetary cost for one-shot generation for DBPedia on different models (Ada, Babbage, Curie, Davinci) in Tab. 16
Table 16: Estimated cost for 1-shot generation in Alg. for DBPedia on different models.
Model
Ada
Babbage
Curie
Davinci
Cost (S)
0.36
0.45
1.81
18.09
We point out that this process represents a one-time cost that is incurred prior to the deployment of the model.
H DEMONSTRATIONS
We provide the DP few-shot generations at 4 for DBPedia by the Babbage model in Tab. provide a brief observation for the quality of the demonstrations.
17
We
While the Babbage model is comparatively smaller and less advanced than the current state-of-the-art models, its synthetic generations maintain a reasonable level of coherence and fluency. The length of these synthetic generations generally aligns with the samples their respective training datasets. However, we have noticed that longer generations occasionally result in the repetition of the last sentence. We also noticed factual errors when inspecting the synthetic generations in detail. We believe that these issues can be mitigated by employing more capable instruction-follon refining the instruction during the generation process and advances hallucination mitigation.
models,
19

---

Published as a conference paper at ICLR 2024
Table 17: Examples of DP few-shot generations on DBPedia.
shot generations
Label
The company was founded in 1883 hy a group of German immigrants in the United States. The company was originally known as the American Electric Company.
Company
The School of the Atts is a school of the University of the Arts in Philadelphia, Pennsylvania. graduate school of the University of the Arts, is located the main campus of the University of the Arts. The School the Arts member of the Association of Independent Schools of the United States and Canada.
School
The Beatles
English rock band formed Liverpuol in 1960. The group consisted of John Lennon, Paul McCartney, George Harrison, and Ringo Start. The Beatles are widely considered to be one of the most successful and influential bands in history popular music. They are also one the most commercially successful bands of time, with over 600 million records sold worldwide. The Beatles have been inducted into the Rock and Roll Hall of Fame, the Songwriters Hall of rame, and the
Artisit
The Athlete person who is physically fi and able to perform at a high level of performance. The term is used in able to perform a high level of performance.
Athlete
sports to describe person who physically
The political party of the President of the United States is the Democratic Party. The Democratic Party is the uldest political party in the United States. The Democratic Party was founded 1828 by Thomas Jefferson and James Madison.
Politiciun
The train was a long-distance passenger train that operated the United States from 1869 to 1891. was the first passenger train operate in the United States. The tmin was built by the New York Central Railmad and was named the "Empire Builder'. The train was built to earry passengers from New York to Chicago, and was the first train to the continent.
Transportation
The building was built in 1892 by architect John two-story, five bay. rectangular building with hipped roof. The main entrance on the second floor. The building is constracted of brick and stone. The building is contributing property to the Old Town Historic District. The building was listed on the National Register Historic Places in 1982 The building is located the comer Main and Main
Smith. was designed in the Italionate style and
Building
The world's largest and most diverse collection of tropccll rainforests is found in the Amazon Rainforest. The Amazon
Nature
Rainforest is the largest tropical rainforest in the world. located western Amazon Basin in South America.
The village of Kishinev is located in the Kishinev Oblast of the Russian Federation. It is located on the Kishinev River. Iributary of the Dnieper River.
Village
The animal small, brown, furry, very active mammal. found forests of the northern hemisphere. is member of the family Cobidae. very common species.
Animal
The plant a small, herbaceous perennial plant with long, narrow, erect stem. leaves are alternaee simple, and entire. The flowers produced in raceme, and are produced in the axils of the leaves. The flowers are white, pink, or purple, and are produced in the axils of the leaves. The fruit a small, dry, woody capsulc. The plant native to the Mediterranean region. It is found in the Mediterranean region.
Plant
The album was released on November 1. 2009. was recorded in the studio in Los Angeles, California, and was Albom produced the band's guitarist, John Hanes.
The film documentary about life late singer and songwriter, John Lemoon It was directed by Martin Scorsese and produced by Albert Maysles. The film was shot in black and white and was shot in the United States, England, and Germany. It was released in the United States on November 30. 1980. The film was nominated for the Academy Award for Best Documentary Feature. The film also nominated for Academy Award for Best Documentary Short Subject.
Film
The book is novel the American author John Grisham. It is the first novel in the legal thriller series The Firm. The book was published in the United States on September 1, 1992 by Doubleday, an imprint of Random House. The book United Kingdomn by Jonathan Cape September 1992. The book was later published in the United States by Random House in September 1993.
Book
was lirst published
20


Reviews:
[{"review_id": "UCC3fPoJ0J", "reviewer": "Reviewer_kLtt", "summary": "This study addresses the challenges of in-context learning (ICL) with large language models (LLMs) on private datasets, focusing on privacy concerns. The researchers propose an algorithm that generates synthetic few-shot demonstrations with formal differential privacy (DP) guarantees, enabling effective ICL while protecting private information in prompts. Their empirical experiments demonstrate that this approach maintains competitive performance with strong privacy levels. Additionally, they explore zero-shot solutions where LLMs generate their own demonstrations, showing potential for achieving privacy without compromising performance.", "questions": "See above", "limitations": "", "rating": 8, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "1)The paper studies simple approach of achieving privacy in ICL (synthetic data generation and use it as demonstrations)\n\n2)Paper for most parts is clearly written and is easy to read.", "weaknesses": "1) No comparison with real-world threat models has been provided. Epsilon-utility trade-offs can be misleading without testing them against actual attacks, as epsilon guarantees are built upon numerous assumptions, as indicated in [1, 2, 3]. For a comprehensive evaluation, it is essential to conduct experiments that demonstrate trade-offs between  empirical privacy and utility.\n\n\n2) *\"*..A different line of work (Feyisetan et al., 2020; Xu et al., 2020; Du et al., 2023) focuses on sanitizing user texts locally before releasing them to the server based on metric local differential privacy (Chatzikokolakis et al., 2013). Such methods usually incur huge overheads to the utility of the sanitized text ..*\"* This statement is not necessarily true and it should be revised to avoid making broad generalizations. As evidenced in a recent study [3], the use of a language model prompted \"zero-shot\" to generate paraphrases exhibited a clear and significantly better (empirical)privacy-utility tradeoffs.\n\n\n**Refs**\n\n[1] A Critical Review on the Use (and Misuse) of Differential Privacy in Machine Learning (https://arxiv.org/abs/2206.04621)\n\n[2] TEM: High utility metric differential privacy on text. (https://arxiv.org/abs/2107.07928)\n\n[3] Locally Differentially Private Document Generation Using Zero Shot Prompting (https://arxiv.org/abs/2310.16111 )", "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": "a6gNvTBpAm", "reviewer": "Reviewer_vhzg", "summary": "This paper studies how to incorporate differential privacy into in-context learning with large language models. The authors propose a DP algorithm which generates synthetic few-shot examples from a private dataset; these “demonstrations” can then be used downstream for in-context learning without incurring additional privacy costs. The authors evaluate their algorithm across several benchmark datasets and privacy regimes, including a fully private ($\\epsilon=0$) case which doesn’t use the private dataset at all.", "questions": "It seems likely the the PATE-like component of Algorithm 1 could (similarly to PATE) have a stronger data-dependent privacy analysis if the models “agree.” While by no means necessary, I would be interested to see this!", "limitations": "", "rating": 8, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 4, "strengths": "1. The empirical evaluation (including an ablation study) is very thorough.\n2. Compared to previous / concurrent work, I think the “generating synthetic few-shot data” approach is really practical since (due to post-processing) answering any number of queries now doesn’t affect the privacy guarantee.\n3. The proposed framework is flexible enough to adapt to many potential use cases, and I could see that there could be interesting future work down the line.", "weaknesses": "None of the experimental baselines compare the proposed algorithm to existing work. In particular, I think it could be instructive to see how DP few-shot generation compares to DP fine-tuning approaches.", "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": "5yDnP0d51f", "reviewer": "Reviewer_MYhF", "summary": "To prevent the leakage of private data, the current approach necessitates consulting the large model only in a zero-shot manner. In this article, the author proposes a solution by generating multiple synthetic prompts based on private data. This enables leveraging the performance boost afforded by few-shot learning while maintaining privacy guarantees.", "questions": "Pls specify the quality of the synthesized prompt.", "limitations": "", "rating": 8, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "In the current industry practice, safeguarding privacy data requires organizations to pre-train or fine-tune large models, demanding substantial resources. Leveraging synthetic data as prompts to enhance large model capabilities not only preserves privacy but also significantly reduces resource consumption.  Adding noise to the probability of generating the next word in a large model is a relatively novel approach.", "weaknesses": "Generating a composite prompt requires consulting the large model M*L times, leading to a significant consumption of resources.\n  + The necessity of employing an untrusted model to generate the next word poses a challenge. While open-source large models are an option, their performance in generation tasks tends to be lower compared to closed-source counterparts. There is some uncertainty surrounding the final quality of the synthesized prompt, including aspects such as length, coherence, and overall fluency.", "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": "2tBfM3Wr0N", "reviewer": "Reviewer_95y5", "summary": "This paper studies an emergent and important problem of how to generate private demonstrations for in-context learning. The authors proposed to generate synthetic few shot examples from the private database (Algorithm 1). As a result of post-processing property of DP, number of queries does introduce extra privacy cost.", "questions": "See weakness.", "limitations": "", "rating": 8, "confidence": 2, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "Studies an important problem and provide intuitive solution. Theoretical analysis looks correct to me.\n\nThe experiments compared with a strong competitor (asking LLM to generate its own demonstrations). Moreover. this finding is also interesting in its own sense (with 20-30% accuracy improvement in many cases.)! Private ICL shows comparable accuracy to the non-private  few-shot prompt accuracy.", "weaknesses": "Algorithm 1 seems to incur M foundation model api calls. How much monetary cost does the algorithm incur?\n\nIn the paper, the author investigated report noisy max with exponential mechanism. Will using RNM with gaussian mechanism lead to better accuracy?", "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)