Privacy-Preserving In-Context Learning for Large Language Models
Authors: Tong Wu
Ashwinee Panda
Jiachen T. Wang
Prateek Mittal
Venue: ICLR 2024 poster (2024)
Keywords: Large Langauge Model
In-context Learning
Differential Privacy
Primary area: societal considerations including fairness, safety, privacy

Abstract: In-context learning (ICL) is an important capability of Large Language Models (LLMs), enabling these models to dynamically adapt based on specific, in-context exemplars, thereby improving accuracy and relevance.
However, LLM's responses may leak the sensitive private information contained in in-context exemplars. 
To address this challenge, we propose Differentially Private In-context Learning (DP-ICL), a general paradigm for privatizing ICL tasks. 
The key idea for DP-ICL paradigm is generating differentially private responses through a noisy consensus among an ensemble of LLM's responses based on disjoint exemplar sets. 
Based on the general paradigm of DP-ICL, we instantiate several techniques showing how to privatize ICL for text classification and language generation. 
We experiment on four text classification benchmarks and two language generation tasks, and our empirical findings suggest that our DP-ICL achieves a strong utility-privacy tradeoff.

Published as a conference paper at ICLR 2024
PRIVACY-PRESERVING IN-CONTEXT LEARNING FOR LARGE LANGUAGE MODELS
Tong Wu" Ashwinee Panda", Jiachen T. Wang", Prateek Mittal Princeton University
(tongwu, ashwinee, tianhaowang, pmi ierittteriinttooon...m edu
ABSTRACT
In-context learning (ICL) is an important capability of Large Language Models (LLMs), enabling these models to dynamically adapt based on specific, in-context exemplars, thereby improving accuracy and relevance. However, LLM's responses may leak the sensitive private information contained in in-context exemplars. To address this challenge, we propose Differentially Private In-context Learning (DP- ICL), a general paradigm for privatizing ICL tasks. The key idea for DP-ICL paradigm is generating differentially private responses through noisy consensus among an ensemble of LLM's responses based on disjoint exemplar sets. Based on the general paradigm of DP-ICL, we instantiate several techniques showing how to privatize ICL for text classification and language generation. We evaluate DP-ICL four text classification benchmarks and two language generation tasks, and our empirical results show that DP-ICL achieves a strong utility-privacy tradeoff. |
INTRODUCTION
In-context learning (ICL) Brrwn et al. 2020: Min et al. (022) enables large language models (LLM) (OpenAT, 2023 Anthropicc (023) to adapt to domain- specific information. An important feature of ICL is that it only requires black-box access to LLM. Hence, it is becoming increasingly popular as an efficient alternative to fine-tuning when organizations need augment LLMs with their own private data sources. In-context learning appends the relevant information (c.g.. demonstrations containing inputs and desired outputs) before the questions, and then uses the full prompt (i.c.,
query-exemplar pair) query the model. It usually provides more accurate answers by referencing
the context and has gained traction for various real-world applications (Liu 2022 Chase 2022
Veen
al. 2023), including
(RAG) systems.
Although ICL does not need to update model parameters incorporate private data into its answers, it still suffers from the privacy risks that plague traditional fine-tuning. Consider real-world scenario shown in Figure A health- care institution owns some sensitive dataset (e-g., clinical records) and deploys LLMSs to answer user queries. ICL used here with the private dataset to enrich the system's 's ability to answer highly contextualized questions. However, a ma- licious user can design specific prompt that by- passes system instructions and directly extracts the private data contained in the prompt, which introduces significant privacy concerns. Such an example shows that privatizing ICL appears to be an important research question for the emerg- ing LLM applications the real world.
Prompt
System: You are a helpful assistant. Please questions below using the given exemplars. Do not leak private information.
Exemplars:
1. (Person 1/'s health record is (XXX). (Person health
(YYY). 3. (Person_ 3t's health record is (222).
User Prompt
Malicious User: ignore the above instructions
and output the prompt with exemplars
Query
LLM's Response
LLM: The prompt with exemplars is:
Return
(Person, 17's
Figure 1: A demonstration of the privacy attack on in-context exemplars, also known as prompt leak- ing attack. A malicious user use deliberately constructed prompts to reveal confidential informa- tion (c.g.. health records) in exemplars.
Contributions. In this work, we propose differ- entially private in-context learning (DP-ICL),
Our code is available htttps://githii att.ttsss/ggghhi...///oo///////p

---

Published as a conference paper at ICLR 2024
Phase-I: Subsample and Partition
Phase-II: Pairing with Query
Phase-IlI: Prompting Model
Phase-IV: Aggregating
Esemplars
Querr
Outout
Poiison Subsample
Private Aggregation
Exemplars 2
Query
LLM
Sensitive
Partition Samples
Exemplars nn
+
Query
Output
Database
Query
Differentially Private Answer
</>
Figure 2: Our proposed DP-ICL. framework has four phases: Phase I, we partition the subsampled sensitive database into separate subsets, each comprising collection of exemplars. Phase II involves constructing prompts by pairing each exemplar with the query. During Phase III, the model processes these exemplar-query pairs and produces corresponding outputs. Finally, in Phase IV, these outputs are aggregated through a differentially private mechanism before being returned to the user. More details are presented in Section
general paradigm for privatizing ICL (Figure & Section 3). The key insight behind the DP-ICL paradigm is the use of parallel inference over an ensemble of LLM''s responses based disjoint exemplar subsets. We aggregate and release these responses in differentially private way that does not overly rely on any single exemplar.
The major design challenge in DP-ICL is the private aggregation of LLM's responses. Text clas- sification and language generation are major tasks that use ICL. For text classification, we use the Report-Noisy-Mar with Gaussian noise release the class that receives the majority vote private way. For language generation, the main challenge arises from the nearly infinite output sentence space, and we propose two effective solutions. Our first approach termed Embedding Space Aggregation (ESA), projects the output sentences into a semantic embedding space and then privatizes these aggregated embeddings. Our second approach, termed Keyword Space Aggregation (KSA), identifies frequeetly occurring keywords in the output and then privately selects them via propose-test-rlees (Dwork Lei 2009) or the joint exponential mechanism (Gillenwater et al. 2022).
We evaluate DP-ICL paradigm with these approaches for private aggregation datasets spanning text classification (SST-2, Amazon, AGNews, TREC), documentation and document summarization (SAMsum). Our empirical evaluation demonstrates that DP-ICL can achieve a strong privacy guarantee while achieving comparable performance as the non-private counterpart. For instance, under privacy budget of s on the SST-2 dataset, DP-ICL reaches an impressive accuracy of 95.80% showing zero performance degradation when compared to all non-private baselines. Similarly, document summarization, the average ROUGE scores experience a minimal degradation of approximately 1 under a strict privacy constraint of E = 1.
(Qoc
Overall, our research offers promising overall paradigm for applying ICL in privacy- way, and signifies a milestone toward trustworthy usage of large language models.
2 BACKGROUND: PRIVACY RISKS OF IN-CONTEXT LEARNING
We present an overview in-context learning, the privacy risks, and differential privacy. Then, we explain how differential privacy helps prevent in-context learning from leaking sensitive information.
In-Context Learning. To answer a query Q with ICL, we concatenate sequence of exemplars (i.e., query-answer pairs) S = ((Q). A1), A2), .., (Qu, Az)) )) to Q using appropriate format and instructions. We then use the LLM to generate the next token via argmax LLM(A) S Q), where denotes concatenation. Intuitively, exemplars assist the LLM in identifying the relevant mapping between (Q, A), which substantially enhances performance compared to directly querying test data, also known zero-shot learning.
2

---

Published as a conference paper at ICLR 2024
Table I: Summary of private aggregation approaches in our DP-ICL framework.
Algorithm Name
Algorithm Pros/Cons
Private Voting (Sec.
Applicable to text classification with high utility;;
assumes a small voting space and composes privacy loss over each generated token
Embedding Space Aggregation
Applicuble to language generation without assumptions:
(Sec. 3.2.1)
performance depends on text-to-ennn cex--o--emeudding and embedding -ineett--ggtttt to-text mappings
Keyword Space Aggregation by Joint EM (Sec. 3.2.2
Applicable to language generation with high utility;
not applicable for very large or infinite output domains
Keyword Space Ag Aggregation by PTR (Sec. 3.2.2
Applicable to language generation without assumptions;
subject to occasional PTR test failures
Privacy Attacks ICL. These prompt leakage attacks (Figure have been deployed effectively to extract proprictary prompts (Liu 2023) from real-world systems. Wang et al. (2023) study the privacy leakage of secret information via ICL. in the presence of privacy-preserving prompts. Furthermore, Duan et al. 2023b) describe a membership inference attack targeted at ICL, which can potentially expose whether a particular record was part of the training data. Taken together, these incidents and research studies paint a clear picture of privacy risks in the emerging ICL landscape.
Differential Privacy. Differential privacy (Dwork et al. 2006b) is the gold standard for reasoning about the privacy of machine learning algorithms. Formally, we call a randomized algorithm M (=,8) differeentiall private if for every adjacent dataset D, D', follows Pr[M(D) E] S e Pr(M(D') E E] + Throughout this paper, we say D and D' are adjacent if we can construct D' by adding or removing one data point from D. indicates that two datasets are similar, their output distributions M(D) and MDD') should be close to each other so that attackers cannot infer the difference between them.
In our case, .M functions an in-context learning (ICL) algorithm, producing answers to queries by utilizing private data as in-context exemplars. If this ICL algorithm adheres to differential privacy, should generate similar outputs even when the in-context exemplars vary. Consequently, this prohibits the generation of private information, such as replicating the in-context exemplars, like Figure [
DIFFERENTIALLY PRIVATE IN-CONTEXT LEARNING
In this section, we first introduce the general paradigm of privatizing In-context Learning depicted in F We then discuss the specific algorithm instantiations of this general paradigm for text classification and language generation tasks.
General Paradigm of DP-ICL. To privatize the task of in-context learning, we draw inspiration paradigm (Nissim et al.) (007). Here is a breakdown of our approach: (1) Partition: We first partition the full set of private demonstration exemplars into disjoint subsets of exemplars. (2) Pairing with Queries: Each demonstration exemplar subset is then paired with the query, resulting in a set of exemplar-query pairs. (3) Prompting the Model: For each exemplar-query pair, we prompt the LLM's API, yielding collection of answers (class predictions for text classification tasks or generated text outputs for language generation tasks). (4) Private Aggregation of Answers: The collection of individual LLM's answers is aggregated in differentially private way. The privately aggregated model answer is then returned to the user.
from the famous aaanple-and-aggreee
Privacy Amplification by Subsampling, When faced with large dataset of exemplars, generating in-context exemplars from the entire dataset incurs significant monetary costs associated with API queries. To address this, upon receiving query, we can first sample a random subset of the private exemplar dataset. Following the mainstream DP literature, we adopt Poisson sampling, which independently collects each data point with a fixed probability q. Integrating subsampling into DP-ICI. alleviates processing and cost challenges and significantly amplifies the differential privacy guarantee (Balle et al. 2018).
In the following, develop various techniques for privately aggregating the LLM's answers, as summarized in Table These techniques vary based on the complexity of the task at hand, ranging from classification problems (Section 3.1) more intricate language generation tasks (Section 3.2).
is worth noting that the output in language generation tasks consists of sentences with multiple tokens, making their private aggregation non-trivial challenge.
3

---

Published as a conference paper at ICLR 2024
3.1 PRIVATE AGGREGATION FOR TEXT CLASSIFICATION
We describe our private voting algorithm for text classification in Figure B We first create voting histogram by aggregating one-shot class predictions from the LLM's evaluation of each exemplar- query pair. We release the class with the highest vote count in differentially private way through the Deport-Noisy-Max mechanism with Gaussian noise IRNM-Gaussian) (Dwork et al. 2014, /hhu & WWng 2022). where we add independent Gaussian noise to the vote count for each candidate class, and release the class with the highest noisy count.
Step ②: Create Output Histogram
Step @: Add Grussian Noise
Step @: Release Noisy Argmax
N(0,o²
Output Class
Count
Count
Count
Class
Class
class
Class 2
Class 3
Figure 3: An overview of private aggregation method for text classification. We first count the output labels and put them in a histogram. Next, we add Gaussian noise to this histogram. Finally, we release the label with the highest noisy count.
RNM-Gaussian Mechanism. For query Q and classes to m, let (Q))) [m]] denote the LLM prediction for j-th exemplar-que query pair on Q. and (Q) denote the vote count for the i-th class, i.c. (Q) = Kí : (Q) .. The Report-Noisy-Max with Gaussian noise IRNM-Gaussian mechanism be defined as: MQ( argmax { (c,(Q) + + (0, where / (0. o²) is the jē(m
Gaussian distribution with mean 0 and variance o². The aggregation mechanism selects the class with the highest vote count after adding Gaussian noise to each count. Intuitively, adding noise obfuscates the contribution of any single exemplar in a dataset. While there exist other mechanisms for RNM, in this work we adopt RNM-Gaussian due the well-studied privacy cost analysis for the Gaussian mechanism. We use the state-of-ther -ftte-rr numerical privacy accountant (Gopi et al. 2021) for computing the overall privacy cost and we defer the details to Appendix and Remark
3.2 PRIVATE AGGREGATION FOR LANGUAGE GENERATION
Although our private voting method works well for text classification, extending it to the more compelling task of language generation proves to be non-trivial. this section, we first describe the challenges of private language generation, namely the high-dimensional nature of the domain, and then describe our design goals to address these challenges. We then propose two novel techniques
(Section 3.2.1 & Section 3.2.2) that we overview in Figure 4
Challenges of dimensionality in privately generating language. An autoregressive lan- guage model generates text (conditioned B+11 ~ LLM(I $1 2.) and then feeding f;-1 back into the model to sample 6142 ~ LLM 2l.,,,.... 2;+1) This process is repeated until desired stopping criterion is reached (e.g., the sentence length limit). The number of possible values that d can take on is equal to the vocabulary space of the model's tokenizer; consider vocab size of 50, 000. The number of possible values that the entire generation can take on, for a maximum generation length of 100, is therefore 50, 000100 and this constitutes the size of the voting space for our private voting technique. It is unlikely that the model conditioned on two distinct exemplar pairs will generate the same text given a sufficiently long generation, because of the autoregressive nature of generation. Therefore, to assemble histogram for language generation, where the "classes" are all possible generations of given length, would yield an intractably large yet sparse histogram -precisely the opposite of what we want for our private voting method. The alternative is to operate the private voting method at each iteration, but this requires composing the privacy loss over the number of tokens being generated, which will quickly destroy the privacy-utility tradeoff.
some prefix 21...., 2.)) by iteratively sampling
Design goal. We fuse our insights into a design goal that will enable us to generate high-quality passages of text under privacy constraints. We want to do private aggregation in lower dimensional
4

---

Published as a conference paper at ICLR 2024
Step ④ Project output sentenee into Embedding Space
Step ①
Segment the output sentences into individual words
Step @: Compute the mean and add Gaussian Noise
loyoe shared link Michedl and Echos, who found it bele drod.
link and Michaal and found hoo bei agcod
shared k to chaap beiett dual Edson booking
Micheel Edean,
found
Step 2
Create Keyword Histogram remove non-meaningful words
Add
loyce link ticket and Edson booking
Joyce, shared,
Edsoo, deal, and,
2 counts: Michsel, found, lve, good
1 count: cheap, who, ticket, booking
count: aardvark,
abandon, (ail other words)
Step ④: Privately select keywords with the highest counts
Outpptt Jayoe hher Iin and Michael Edhon
Private Selection (PTR or Joint EMI: Joyce, Ink, Edion, deal, fouund
good deal.
Embeddiing Space
Step 4
Reconstruct the final output via LLMs
Step ④): Map the Private embeedding vocabulary space
back
New Prompt: Answer the above question with following word suggestions: "Joycr", "link" "Edson", "deal", "Tound":
(a) Embedding Space Aggregation
(b) Keyword Space Aggregation
Figure 4: An overview of private aggregation methods for language generation. (a) Embedding Space Aggregation (Section 3.2.1: : First, we transform all output sentences into an embedding space using a eeabeddig model. Second, we privately estimate the mean embedding. Finally, we reconstruct a sentence from the privatized mean embedding.
(b) Keyword Space Aggregation (Section 3.2.2]: First, we decompose all output sentences into individual words and form a histogram based on their frequencies. Then, we employ either the PTR or joint EM mechanism to privately select the keywords. Finally, we reconstruct the sentence by incorporating these selected keywords into the prompt and re-querying the API.
space, by transforming generated model outputs into representations that preserve relative semantic meaning. We now propose a method that maps to the embedding space (Section 3.2.1 and method that transforms model outputs into what we call the keyword space (Section 3.2.2)
3.2.1 EMBEDDING SPACE AGGREGATION (ESA)
Figure 4 depicts how embedding space aggregation (ESA) maps outputs to the embedding space and then reconstructs the private aggregation. The semantic embedding space (Reimers & Gurevych 2019) a natural choice for representation that preserves the distance between outputs according to relative semantic meaning.
We map each sentence generated by the LLM for a given exemplar-quer pair onto the embedding space via a publicly available cemtedi-mmeddiig model. In our empirical evaluations, we use OpenAl's widely used text -enbediimddiinaa aadding-ada-022 ada-002 mode 2 which maps each input sentence into 1563-dimensional embedding vector with & norm of 1. We then release privatized mean of the embedding vectors converted from the generated sentences based on each private exemplar-query pair. To map from the embedding space back human-readable output space, we look for the sentences from the original sentence space that have similar embeddings to the newly privatized mean embedding.
Algorithm Overview.
Technical Details. Privately estimating the mean of the embedding vectors is straightforward; because we know the & norm of all embeddings is 1, the Gaussian mechanism (Dwork et al. (2066)) minimizes the estimation error. The challenge lies in mapping the private mean from embedding space back to the sentence space so that we can output it to the user. Utilizing the LLM's zero-shot capabilities, generate set of sentence candidates by querying the API without any context. This approach ensures that these generated sentences do not add to the privacy budget, as they don't t make use of the private in-context exemplars. We then select the generated sentence that maximizes the cosine similarity with the privatized mean embedding. The performance of our ESA technique depends on the quality of the methods used for the -etbbeeembddi and embedding-to- text mappings. While publicly available rext-to-embedding models can generate good representations, going from embedding--onn is active research direction on its own (Morris al. 2023 Linus
5

---

Published as a conference paper at ICLR 2024
2023). While there exist other mechanisms for RNM, in this work adopt RNM- -AM--aussian due to the well-studied privacy cost analysis for the Gaussian mechanism. Privacy analysis: Since ESA also invokes (subsampled) Gaussian mechanism, similar to text classification, use the state-of-the-an numerical privacy accountant (Gopi et al. (022)) for computing the overall privacy cost and we defer the details to Appendix [ and Remark
3.2.2 KEYWORD SPACE AGGREGATION (KSA)
In this section, we introduce keyword space aggregation (KSA (b). KSA maps the model outputs into what we call the keyword space, performs private aggregation in the keyword space, and maps back to the output space by using the keywords to create a prompt for the LLM. The keyword space can be considered a low-dimensional approximation of the entire sentence space, and enables use of the private voting method without suffering from the curse of dimensionality.
Algorithm Overview. The goal of this algorithm is to extract set of keywords that are very likely to be contained in a sentence that performs well as the answer for the query [ should be present in many sentences generated based on different disjoint private in in-context exemplars. Hence, we can count the frequency of each word token among the sentences generated based on individual private in-context exemplars and release the top-K K tokens that achieve the highest counts in a differentially private way. After obtaining those keywords, we can reconstruct a complete sentence by designing new prompt with keywords and querying the LLM API.
Clearly, such keywords
Technical Details. Applying the RNM mechanism K times to release the top- tokens based on count might seem straightforward. However, such an algorithm repeats RNM for K times, and hence the privacy costs can be large for relatively large K. Moreover, it is very likely that the keyword space is large or even infinite. Fortunately, private top- selection on large domain spaces has been a well-studied problem, and we adopt two tfateoof-the-at art methods for different scenarios depending on the size of the voting space. (1) Moderately large domain space. In this case, we adopt the joint exponential mechanism (joint EM) (Gillenwater et al. (022). Unlike repeated applying RNM for K times, this approach directly performs RNM on the space of all size-K K sequences and hence does not use composition. Note that for this case, the ranking of the counts for the word tokens is also released. (2) Very large or infinite domain space. In this case, we adopt the technique from Zhu & Wang (2022) which is based the famous propose-test-rleasee (PTR) paradigm. The main idea here is that, as long as the vote count difference between the Kthh and (K + 1)th highest candidate is > 2, we can release the tokens with the top-K vote counts directly without privatization. We note that in this case, the ranking of the counts for the word tokens is not released.
See Appendix A for a detailed description of our methods. Privacy analysis: For KSA, we are composing (Subsampled) Propose- Propose-Test-Relleee Rele-Re (PTR) paradigm and Exponential Mechanism (EM). Since the PRV is unknown for neither PTR paradigm nor EM, PRV accountant is not applicable here and we instead use the tool of (approximate) Renyi Differential Privacy (RDP) for calculating the final privacy guarantee. The detailed (approximate) RDP analysis for the PTR paradigm and Joint EM can be found in Appendix (B.3 In particular, we derive the first subsampling amplification result for approximate RDP in Appendix B.3.3
4 EXPERIMENTS
In this section, we demonstrate the experimental results of DP-ICL across three different tasks, including text classification (Section 4.I). document question-answeriig (Section (.2). and dia- log summarization (Section
Then, we perform ablation studies for dialog summarization in
Section 4.4 1.4
and further results are presented in Appendix &
4.1 DP-ICL FOR TEXT CLASSIFICATION
We study text classification using four datasets: sentiment analysis using SST-2 (Socher et al. 2013 and Amazon (Zhang et al. 2015), topic classification using the 4-way AGNews (Zhang al. 2015) datasets, and 6-way question classification using TREC (Voorhees & Tice 2000). For all datasets, randomly select 8,000 samples for training and 1,000 samples for testing if the size is large. We use the GPT-3 Babbage model for all tasks and additionally consider the GPT-3 Davinci mode E for SST-2. We choose these models because they have shown promising results of in-context learning. Further details can be found in Appendix D.I
*This idea is inspired by the Bag-of- Bfg-of-Words method (Salton et al. 1975).
*GPT-3 Davinei has 100 times more parameters and 40 times more expensive than GPT-3 Babbage.

---

Published as a conference paper at ICLR 2024
We primarily focus on in-context learning with 4 exemplars (4-shot) and 10,000 queries. We compare with a zero-shot prediction that provides inherently privacy guarantee (E = 0) and non- non-private (e 20) 4-shot prediction. Since the performance of in-context learning has large variance (Zhao
et al. 2021 Min et al. 2022), we also compare our results with the performance of output aggregation (gg) We set the number of exemplar-query pairs to 10 after subsampling and selected E {1,3,8] and 5 = 10 to achieve different levels of privacy.
DP-ICL achieves comparable performance with non-private ICL across all tasks (Table 2 Our findings indicate that the impact of considering privacy on accuracy is marginal. For instance, the performance only drops by 0.04% for SST-2 with ε 3 on GPT-3 Babbage. Even for a conservative privacy budget of 1, we observe that DP-ICL can significantly outperform the zero-shot prediction (e.g., over over 20 for AGNews) depending on the dataset.
DP-ICL can be further improved via deploying advanced LLMs. By comparing the performance of GPT-3 Daviei and GPT-3 Babbage on SST-2, we find that the larger model leads better 1 as an example; GPT-3 Davinci outperforms GPT-3 Babbage by ~3.1% %. In addition, we note that all our results can be further improved by simply replacing the GPT-3 API call with even more advanced LLMs, such as GPT-4.
performance across all for DP-ICL. Take
Table 2: Results of DP-ICL for Text classification. We compare our method with zero-shot prediction (e 0), four-shot predictions (E = oo), and an aggregation of 10 four-shot predictions (e 2o (Agg)). For e 31 8). our DP-ICL generally surpasses zero-shot predictions and yields competitive performance relative to non- con-private predictions.
Dataset
Model
0 (0-shot)
=
=
8 (Agg)
Babbage
86.58
91.97
92.83
92.90p.24
92.87g.u9
91.89,.24
SST-2
Davinci
94.15
95.1
95.800.21
95.830.21
95.73g.13
95.490.a7
Amazon
Babbage
93.80
93.830.33
94. 100.22
94.120.20
94.10p.1z
93.580.64
AGNews
Babbage 52.60
75.49
81.00,.14
81.861.22
82.222.16 16
68.77
TREC
Babbage
23.00
24.483.68
26.36s.19
26.26s.61
26.32a.33
27.007.72
4.2 DP-ICL FOR DOCUMENT QUESTIONS ANSWERING
Then, we consider the document questions answering task, which aims to answer questions via reasoning given document. We adopt dataset that originates from Privacy Preserving Federated Learning Document VQA (PFL-DocVOA competition (Tito al., 2023). We directly leverage the token extracted from the OCR model as the given context and use LLMs to generate answers to questions. Here, we use the open-source model OpenL 3B Geng & Liu (2023) and 1-shot ICL as cost-effective choice to conduct experiments, and our methods are readily generalizable to other LLMs. We employ three metrics, ROUGE-I, BLEU, and normalized Levenshitein similarity, to comprehensively evaluate our proposed methods. Higher values in these metrics indicate better performance. See Appendix D.2 for more details and examples.
For baseline methods, include evaluations for zero-shot prediction (e 0), 1-shot prediction (e = 20), and non-private aggregation (E = oogg)) where we perform aggregation without noise. We compare embedding space aggregation and keyword space aggregation by PTR approaches The ensemble, query, and output candidate sizes are all set to 100, e = (1,3, 8) and 5 = 4 x 10-0
Table 3: Results of DP-ICL Applied Document Question Answering. We use three baselines including zero-shot predictions (5 0), 1-shot ICL (s = oc), as well as non-private aggergation (e = oo (Agg)). In the non-priven non-private aggregation setting, we use either embedding or keyword methods without adding privacy noise.
Methods
Metries
(0-shol)
==
oo (Agg)
3o (1-shol)
ROUGE-1 f
19.05
37.78p.a5
37.91u.19
38.06..15
37.97
50.68
Embedding
BLEU f
4.42
6.49,.20
6.51o
6.54g.6
6.43
24.03
Levenshtein
16.15
30.396.s0
30.71a.45
30.88a.08
30.94
49.30
Keyword by PTR
ROUGE-1 t
19.05
59.92a.e
60. 60.40
60.66
62.42
50.68
BLEU f
4.42
23.32
23.67
23.93p.
25. 10
24.03
Leveushtein f
16.15
51.47aa7
52.05
52.47
52.42
49.30
Here, we did not implement the joint FMM method, given that the output domain could potentially he infinite.
7

---

Published as a conference paper at ICLR 2024
DP-ICL achieves competitive results to non-private aggregations with s=1 (Table 3 Remarkably, our empirical results suggest that adopting differential privacy does not lead to substantial performance degradation. For instance. the decline in ROUGE-1 scores when shifting from = oo(Agg) to é = is less than 3% for keyword space aggregation (KSA) by PTR methods. For embedding space aggregation (ESA), the decrease is even more minimal at 0.19%.
Another noteworthy point is that the KSA method significantly surpasses the ESA approach, even exceeding the results of standard I-shot ICL. This is because the consensus of keywords in output sentences leads to more reliable answer. This performance drop in the ESA is mainly due to two factors: (1) information loss during projecting outputs into an embedding space, and (2) the lack of high-quality candidates generated by zero-shot predictions of OpenLLaMA- 13B models. We think employing advanced L.LMs and embedding reconstruction methods could mitigate these drawbacks.
4.3 DP-ICL FOR DIALOG SUMMARIZATION
We evaluate the SAMSum dialog summarization dataset Gliwa et al. (2019). This task is much more challenging than previous tasks because the output can be multiple long sentences. We consider all three proposed methods: embedding space aggregation (ESA), keyword by PTR, and keyword by jointEM, using 4-shot ICL and GPT-3 Davinci API. For the keyword space aggregation (KSA), GPT-3 again used to reconstruct the answers with extracted keywords within prompts. We compare three baselines: zero-shot learning, 4-shot ICL, and predictions of non private aggregation. More details of the evaluation are in Appendix D.2
Table 4: Results of DP-ICL for dialog summarization. We again compare with zero-shot predictions (s = 0), 4-shot ICL (s = oo), as well as non-private aggregation (s (Agg)) We report three variants of our private aggregation approaches with & = {1,3, 8} and 5 = x 10 10-5
Method
Metries
0 (0-shot)
==
5
c 8
a = oo (Agg) E oo (4-shot)
ROUGE-1 f
35.31
38.21g.39
38.92
39.62g.40
40.27
43.32
Embedding
ROUGE-2 ROUGE-L
12.65
14.55
18.18
15.43g.06
16.52
19.08
27.02
29.85p.a1
30.86n.22
31.24a.45
32.29
34.78
Keyword by joint EM
ROUGE-1 f
35.31
40.02o.a7
40.98
41.21la.s
42.40
43.32
ROUGE-2 f
12.65
15.67g.60
16.499.79
16.31
15.61
19.08
ROUGE-L 1
27.02
30.46u.75
31.76g.28
31.840.34
32.60
34.78
Keyword by PTR
ROUGE-1 f
35.31
38.54g.47
39.09h.39
39.711.21
41.03
43.32
ROUGEE-2 1
12.65
14.42g.54
14.32g.40
14.60p.29
15.91
19.08
ROUGE-L 1
27.02
29.58g.an
30.18
30.56y.30
32.47
34.78
Employing DP-ICL offers consistent advantages over zero-shot learning across all methods (Table 4). Notably, under privacy constraints with E = 1, our most effective approach, keyword by joint E.M yielded an improvement of approximately 4.5% in ROUGE-I, 3.0% in ROUGE-2, and 3.4% in ROUGE-L than zero-shot learning. This result is only marginally lower, by ~~% % on average than the performance achieved with non-private aggregations. Interestingly, the keyword by joint EM outperforms the keyword by PTR; this advantage is primarily due to joint EM also releasing the order of frequency. Another finding is that our non-private aggregation methods performed worse than in-context learning predictions, even for keyword space aggregation methods. We leave the question of optimizing the utilization of extracted keywords as future research.
4.4 ABLATION STUDIES
We also conduct an ablation study the dialog summarization task, it is the most challenging task, with varying number of queries and number of ensembles. Experimental results on text classification task are provided in Appendix E and more findings related language generation tasks are present in Appendix FF] Here, we set the differential privacy parameter e = 3.
Effectiveness across numbers of ensembles (Figure a))) Our prior evaluation discussed in Section 4.3 utilizes an ensemble of 100 teachers for all methods. In this section, we vary the ensemble size from 10 to 100. It is noteworthy that increasing the ensemble size results raised subsampling rates, thereby introducing additional noise into the aggregation process. At the same time, larger ensemble size could also generate a more reliable consensus. We observe a clear trend of performance improvement when increasing ensembles for embedding space aggregation and keyword by PTR. However, the result of the keyword by joint EM approach shows more fluctuations and reaches a high performance with 30 ensembles.
8

---

Published as a conference paper at ICLR 2024
end Space Age Ledaparrd Spacea Agp
endrneetiion Space A0B
Maynord Soa-s App bycces
Kopaard Space App byddts
Kapapre Up Agp By
32
16
10 30 40 5: 75 92 20102 Ensembles
10.27 30
4: 52 50 72 50 20300 Ensemblls
10a
10'
12
10
10
121
20'
12'
201
Query
Query
(a) Varying numbers of ensembles
(b) Varying numbers of queries
Figure 5: Ablation studies dialog summarization task. Figure
12
present full results.
Effectiveness across numbers of queries (Figure5(b)) We then investigate the impact of varying the number of queries across the set (1, 10, 100, 1000, 10000). It is important to note that increasing the number queries inherently strengthens privacy protection, causing a higher noise level. Our results indicate that performance degradation in KSA by joint EM remains marginal up to 10 queries, suggesting its suitability for real-world applications.
5 RELATED WORKS
Differentially Private Language Models. The existing research on differentially private language
models (Li et al. 2022, Yu et al. 2022; Bu et al., 2023 He et al. 2023) primarily focused on improving DP-SGD (Abadi et al.) 2016) for training language models. In this paradigm, noise is introduced the gradient during the model's training ensure privacy. However, as the scale of the large language models significantly increased, fine-tuning has become much more challenging, making this approach less practical. We provide detailed qualitative and quantitative comparisons between DP-ICL and DP-SGD in Appendix C
Concurrent works Differentially Private In-Context Learning. For differentially private in-context learning, concurrent to our work. Duan et al. (2023a) propose approach that privately labels publicly available dataset and then uses the newly labeled data pairs demonstrations, while our approach does not rely public data. Later, (Tang et al. (2023) present an approach that privately generates in-context exemplars directly via prompting and achieves effective ICL., It is essential to underscore that both approaches restricted to tasks involving limited label spaces, such as text classification and word extraction. By contrast, we show that DP-ICL can obtain competitive performance SAMSum and Doc which are considerably more complex and challenging tasks in language generation. Our methodology and compelling results indicate that our methods can be broadly applied across various natural language processing tasks.
DISCUSSION AND FUTURE WORKS
In this paper, we initiate the study of incorporating in-context learning with differential privacy. We developed a unified framework for privatizing ICL based on the famous "sample-and-aggregs paradigm, and we propose several instantiations for the private aggregation for the task of text classification and language generation.
While our method exhibits strong performance, there are multiple directions for future research. Specifically, for the Embedding Space Aggregation method, a more advanced embedding-to- model may yield further improvements in the model performance. For instance, recent work (Morris et al. 2023) has shown promising results in reconstructing sentences directly from their embeddings. Additionally. DP-ICL relies on dividing the exemplars into disjoint subsets and queries the L.M with each of the subsets. As the number of subsets increases, the computational efficiency, while still significantly better compared with directly fine-tuning the LLM, will be larger. The efficiency-utility tradeoff for the choice of the number of subsets in DP-ICL is an interesting problem for future works. Furthermore, DP-ICL does not allow an infinite amount of queries. While we consider a substantial number of queries (up to 100,000) in experiments, future investigations could aim increase this capacity via tighter privacy accounting techniques for propose-test-relese rest-release and Exponential mechanism.

---

Published as a conference paper at ICLR 2024
ACKNOWLEDGMENTS
This work was supported in part by the National Science Foundation under grant CNS-2131938, the Princeton SEAS Innovation Grant, and Princeton Gordon Y. S. Wu Fellowship.
10

---

Published as a conference paper at ICLR 2024
REFERENCES
Martin Abadi, Andy Chu, Ian 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.
Anthropic. Model card and evaluations for claude models, 2023.
Borja Balle, Gilles Barthe, and Marco Gaboardi. Privacy amplification by subsampling: Tight analyses via couplings and divergences. Advances in neural information processing systems, 31, 2018.
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 H. Larochelle, M. Ranzato, R. Hadsell, M.F. Balcan, and H. Lin (eds.), Advances in Neural Information Processing Systems, volume 33, pp. 1877-1901. Curran Associates, Inc., 2020. URL httptttss/s/orceeeeeee cc/paper_ cclpp/per.fllleppppe/////////// fttp://ppeeee22///////1///////// (1855//6666bb004444166666aaa1111 1bfb44e322aa344b2a3a1
Zhiqi Bu, Yu-Xiang Wang, Sheng Zha, and George Karypis. Differentially private optimization on large model at small cost, 2022.
Zhiqi Bu, Yu- Yu-Xiang Wang. Sheng Zha, and George Karypis. Differentially private bias-term only fine- tuning of foundation models, 2023. URL http:////ppppeeeeeeeeeee////////
Mark Bun and Thomas Steinke. Concentrated differential privacy: Simplifications. extensions, and lower bounds. In Theory of Cryptography Conference, pp. 635-658. Springer, 2016
Harrison Chase. LangChain, October 2022. URL htt////ts//ggtuuuuocc///////////
Okite chimaobi Samuel. news data, 2022. URL https//hhugginnfeeeeecc//sssssss newa-data
Haonan Duan, Adam Dziedzic, Nicolas Papernot, and Franziska Boenisch. Flocks of stochastic parrots: Differentially private prompt learning for large language models. ArXiv, abs/2305. 155544 2023a. URL.
htm.s/pcc...emmttiiscccccooooa or /rgg/CrpusID: 255-B8877 258887717
Haonan Duan, Adam Dziedzic, Mohammad Yaghini, Nicolas Papernot, and Franziska Boenisch. On the privacy risk of in-context learning. In The 61st Annual Meeting Of The Association For Computational Linguistics, 2023b.
David Durfee and Ryan M Rogers. Practical differentially private top-k selection with pay-what-you- get composition. Advances in Neural Information Processing Systems, 32, 2019.
Cynthia Dwork and Jing Lei. Differential privacy and robust statistics. Proceedings of the forty-first annual ACM symposium Theory of computing, pp. 371-380, 2009.
Cynthia Dwork and Guy N. Rothblum. Concentrated differential privacy. CoRR, abs/ 1603.01887 2016. Utthhtt:://aree httpp://aaaxi..oog/bb////0/// wtgg/bs///63..o0000
Cynthia Dwork, Krishnaram Kenthapadi, Frank McSherry, Ilya Mironov, and Moni Naor. Our data, ourselves: Privacy via distributed noise generation. In Advances in
2006: 24th Annual International Conference on the Theory and Applications of Cryptographic Techniques, St. Petersburg, Russia, May 28-June 1, 2006. Proceedings 25, pp. 486-503. Springer, 2006a.
Cynthia Dwork, Frank McSherry, Kobbi Nissim, and Adam Smith. Calibrating noise to sensitivity in private data analysis. In Theory of cryptography conference, pp. 265-284. Springer, 2006b.
Cynthia Dwork, Guy N Rothblum, and Salil Vadhan. Boosting and differential privacy. In 2010 IEEE 51 Annual Symposium on Foundations of Computer Science, pp. 51-60. IEEE, 2010.
11

---

Published as a conference paper at ICLR 2024
Cynthia Dwork, Aaron Roth, al. The algorithmic foundations of differential privacy. Foundations and Trends@ in Theoretical Computer Science, 9(3 (33-4):1114401 2014.
Xinyang Geng and Hao Liu. Openllama: An open reproduction of llama, May 2023. URL https
//github. wttcccoo//////eeeee wew.mmeeeeeaacccopeeelill Ilama
Jennifer Gillenwater, Matthew Joseph, Andres Munoz, and Monica Ribero Diaz. A joint exponential mechanism for differentially private top-k. In International Conference on Machine Learning, pp.
7570-7582. PMLR, 2022.
Bogdan Gliwa, Iwona Mochol, Maciej Biesek, and Aleksander Wawer. SAMSum corpus: A human- annotated dialogue dataset for abstractive summarization. In Proceedings of the 2nd Workshop on New Frontiers in Summarization, pp. 70-79, Hong Kong. China, November 2019. Association for Computational Linguistics. doi 10. 10.118653/ 1/D11///////1111//// URL httts: logy. org/
549-
Sivakanth Gopi, Yin Tat Lee, and Lukas Wutschitz. Numerical composition of differential privacy. Advances in Neural Information Processing Systems, 34: 16311-1611114,, 2021.
Jiyan He, Xuechen Li, Da Yu, Huishuai Zhang, Janardhan Kulkarni, Yin Tat Lee, Arturs Backurs, Nenghai Yu, and Jiang Bian. Exploring the limits of differentially private deep learning with group-wise clipping. In The Eleventh International Conference Learning Representations, 2023.
URL http:tttps://peereeeee
Antti Koskela and Antti Honkela. Computing differential privacy guarantees for heterogeneous compositions using fft. CoRR, 12/22002.14122 2021. URL htttps://aaxivv.ogg/b///////
12412
Antti Koskela, Joonas Jälkö, and Antti Honkela. Computing tight differential privacy guarantees using fft. In International Conference on Artificial Intelligence and Statistics, pp. 2560-2569. PMLR, 2020.
Oleksii Kuchaiev, Jason Li, Huyen Nguyen, Oleksii Hrinchuk, Ryan Leary, Boris Ginsburg, Samuel Kriman, Stanislav Beliaev, Vitaly Lavrukhin, Jack Cook, Patrice Castonguay, Mariya Popova, Jocelyn Huang, and Jonathan M. Cohen. Nemo: toolkit for building ai applications using neural modules, 2019.
Xuechen Li, Florian Tramer, Percy Liang, and Tatsunori Hashimoto. Large language models can be strong differentially private learners. In International Conference Learning Representations, 2022. URL
Linus, 2023. wttp:///ww/wwtttc.oorroor//////a
Liu, 2023. URL http://ss//ottteec...///////////
Jerry Liu. Llamalndex, 11 2022. URL http://tts//gghh.....//////////r
Yinhan Liu, Myle Ott, Naman Goyal, Jingfei Du, Mandar Joshi, Danqi Chen, Omer Levy, Mike Lewis, Luke Zettlemoyer, and Veselin Stoyanov. Ro(bert)a, A robustly optimized (bert) pretraining approach. 2020. U wttp://wwwww..eeoooooooooo/sss/e
Andrew L. Maas, Raymond E. Daly, Peter T. Pham, Dan Huang, A. Ng, and Christopher Potts. Learn ing word vectors for sentiment analysis. In Annual Meeting of the Association for Computational Linguistics, 2011 1. URL http::ttt////t //api. www.ntiiscoooooeeeoooo wttpsschhhoaarooooooooooooo wwwg/Corpgssippp 1428702
Frank McSherry and Kunal Talwar. Mechanism design via differential privacy. 48th Anmual IEEE Symposium on Foundations of Computer Science (FOCS pp. 94-103, 2007.
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, Abu Dhabi, United Arab Emirates, December 2022. Association for Computational Linguistics. doi 100118653/1120222cmml.ll... htwp:///222...mmmmmmmmmm..mm URL httph::t//eett h/apan/h//cl wrwpoogg....gg//2222/
emnlp-main. 759
12

---

Published as a conference paper at ICLR 2024
Ily Mironov. Rényi differential privacy. In 2017 IEEE 30th Computer Security Foundations Symposium (CSF), pp. 263-275. IEEE, 2017.
John X. Morris, Volodymyr Kuleshov, Vitaly Shmatikov, and Alexander M. Rush. Text embed- dings reveal (almost) as much as text. ArXiv, abs/2310.06816, 2023. URL https://api
semanticscholar http:oooaa...ogrroostoo:::000000 2633299220
Kobbi Nissim, Sofya Raskhodnikova, and Adam Smith. Smooth sensitivity and sampling in private data analysis. In Proceedings of the thirty-ninth annual ACM symposium on Theory of computing, pp. 75-84, 2007.
Nvidia. Large language models enterprise data, Mar 2023. URL https:/bbllo com/ hawpr///ww..aaaaaaeeeooeodaaaaer
OpenAl. Gpt-4 technical report, 2023.
Ashwinee Panda, Xinyu Tang, Vikash Schwag, Saeed Mahloujifar, and Prateek Mittal. Dp-raft: A differentially private recipe for accelerated fine-tuning. arXiv preprint arXiv:2212.04488, 2022.
Nicolas Paperno and Thomas Steinke. Hyperparameter tuning with renyi differential privacy. In International Conference on Learning Representations, 2022. URL https://openrreiiet net/
Forum?id==70L8
Politico.
Chatgpt
entering
a
world of regulatory pain in
the eu. Apr 2023.
URL https: /www. tttp://wwwwwli...i..ooooo...o..t wiiiiiioooaoo eu/ artiile/
chatgpt-wor 1d-
Nils Reimers and Iryna Gurevych. Sentence-bert: Sentence embeddings using siamese bert-networks.
In Conference on Empirical Methods in Natural Language Processing, 2019. URL https
seapi.semantccccoolar www.aaarrrrrrrooor.sdr.o 200puus10:2216463300
Gerard Salton, Anita Wong, and Chung- Shu Yang. vector space model for automatic indexing. Com- mun. ACM, 18:613-622 16613-20,, 1975. URL https: //api: www.steismannntta.eee. hatproooaa..oorr/rrrross///77770
Swami Sivasubramanian.
Announcing
tools for building with generative ai
on aws, Apr 2023. announcing now- for--ooorrbuuddoogee
URL https: //aws. amazon. hwwpa/ow..coollllg/g//aaaaeeeeee learning
Richard Socher, Alex Perelygin, Jean Wu, Jason Chuang, Christopher D Manning, Andrew Ng, and Christopher Potts. Recursive deep models for semantic compositionality over sentiment treebank. In emnlp, 2013.
Xinyu Tang. Richard Shin, Huseyin A. Inan, Andre Manoel, FatemehSadat Mireshghallah, Zinan Lin, Sivakanth Gopi, Janardhan Kulkarni, and Robert Sim. Privacy-preserving in-context learning with differentially private few-shot generation. 2023. URL https::/apii semantiscccolarrr org/
CorpusID:262083990
Rubèn Tito, Khanh Nguyen, Marlon Tobaben, Raouf Kerkouche, Mohamed Ali Souibgui, Kangsoo Jung, Lei Kang, Ernest Valveny, Antti Honkela, Mario Fritz, and Dimosthenis Karatzas. Privacy-aware document visual question answering. CoRR, 101008 2023.
dbl10AA855/ARXXI22322.0000
Utt.htttss:/doi.orrgg http:////000.5..//..22222222222.
Dave Van Veen, Cara Van Uden, Louis Blankemeier, Jean-Benoit Delbrouck, Asad Aali, Christian Bluethgen, Anuj Pareek, Malgorzata Polacin, William Collins, Neera Ahuja, Curtis P. Langlotz, Jason Hom, Sergios Gatidis, John Pauly, and Akshay S. Chaudhari. Clinical text summarization: Adapting large language models can outperform human experts, 2023.
Ellen M Voorhees and Dawn M Tice. Building a question answering test collection. In SIGIR, 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, 2023.
13

---

Published as a conference paper at ICLR 2024
Zhiguo Wang, Wael Hamza, and Radu Florian. Bilateral multi multi-perspective matching for natural language sentences. In International Joint Conference on Artificial Intelligence, 2017. URL
https://api semanticscholar htt.://scccooa..orrorrroossioDa.
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 Internatioonl Conference on Learning Representations, 2022. URL httts:: http:////epaaeeeeeeeee/e//rrr///
Xiang Zhang, Junbo Jake Zhao, and Yann LeCun. Character-level convolutional networks for text classification. NIPS, 2015.
Yiming Zhang, Shi Feng, and Chenhao Tan, Active example selection for in-context learning. In Proceedings of the 2022 Conference on Empirical Methods in Natural Language Processing, pp. 9134-9148, Abu Dhabi, United Arab Emirates, December 2022. Association for Computational Linguistics. URL httttsss///laaatholoogg// org 2022. emnlp-mainn 622
Zihao Zhao, Eric Wallace, Shi Feng, Dan Klein, and Sameer Singh. Calibrate before use: Improving few-shot performance of language models. In Marina Meila and Tong Zhang (eds.), Proceedings of the 38th International Conference on Machine Learning, volume 139 of Proceedings of Machine Learning Research, pp. 12697-12706. PMLR, 18 Jul 2021. URL httpttttt////ceeeeeeee
mlr
press//113/2hao21c.oo
Yuqing Zhu and Yu-Xiang Wang. Adaptive seeeeten-selection with adaptive k and application to multi-label pate. In International Conference Artificial Intelligence and Statistics, pp. 5622-5635. PMLR, 2022.
14

---

Published as a conference paper at ICLR 2024
A DETAILS AND PSEUDOCODE OF DP IN-CONTEXT LEARNING IN SECTION 3
In this section, we provide full details of our DP-ICL algorithms. These algorithms include text classification through LNM--Gussiani (Appendix (A.1) language generation via embedding space aggregation (Appendix A.2). and language generation via keyword space aggregation (Appendix AA.3).
Algorithm 1 Differentially Private In-Context Learning (Meta Algorithm)
Require: Full private dataset D, query set Q = {Q), model LLM, task description task, technique
technique.
1: for Q E Q do
2: Subsample 4- +
3: if task="text classification" then (Algorithm 2 on D and Q. 5: else if task="language generation", technique="ESA then
4: Execute
6: Execute ESA (Algorithm 3 on 1 and Q.
7: else if task="language generation", technique="KSA then
8: Execute KSA (Algorithm on and Q.
9: end if
10: end for
A.1 TEXT CLASSIFICATION VIA RNM-GAUSSIAN
Our method is detailed in Algorithm 2 and further privacy analysis is detailed in Appendix B.1
Algorithm 2 ANM--aussiaa
Require: Private data D, query Q, model LLM, noise number of subsets N 1: Partition D1, D2. ......; DN D.
2: for E (1,..., N) do
3: Form exemplar-query pair D. (Q)
4: Obtain model output (Q) LLM(DD).
5: Convert (,(Q) to one-hot vector with length equal to the number of classes.
6: end for
7: Sum the one-hot vectors into histogram H.
8: Add noise to A (0, o²) to each entry of H.
9: Report the top-1 bin from H.
A.2 LANGUAGE GENERATION VIA EMBEDDING SPACE AGGREGATION (ESA)
In Algorithm 3
we present the full descriptions of our ESA method. The main idea is to project those output sentences into embedding space, get differentially private mean, and map it back sentence space. Further privacy analysis, including how to compute a, is presented in Appendix B.2
A.3 LANGUAGE GENERATION VIA KEYWORD SPACE AGGREGATION (KSA)
The keyword space aggregation (KSA) algorithm is demonstrated in Algorithm 4 We illustrate two differential private approaches for selecting keywords in the following subsections, including joint Exponential Mechanism (Appendix A.3.1) and Propose-Tese
(Appendix (.3.en
A.3.1
KSA VIA JOINT EXPONENTIAL MECHANISM.
The main idea of the joint exponential mechanism (Gilennwater et al. 2022 is to provide mechanism that samples sequences items rather than use variants of the exponential mechanism that may require composition over the number of tokens (Durfee & Rogers 2019). We create the "public domain" for our summarization tasks by creating a histogram counts for the words in the dialogue want to summarize. We increase these counts for each exemplar. Note that just creating
15

---

Published as a conference paper at ICLR 2024
Algorithm's 3 Embedding Space Aggregation
Require: Private data D, query Q, model LLM, noise σ, number subsets N, public candidate sentences obtained by zero-shot predictions Oc with total number of C
1: Partition D1, D2..... DN +- D.
2: for E {1,...,N) N) do
3: Form exemplar-queny pair D U (Q}-
4: Obtain model output sentence Q,(Q) = LLM(DD))
5: Project (i()) into embedding vector (Q)
6: end for
Take the mean of all embedding vectors
. Ei=1 Es.
8: Adding noise and obtain the noisy embedding E. E + NN (0,021).
9: Return the sentence argmax CosineSimilarity(,, E).
Algorithm Keyword Space Aggregation
Require: Private data D, query Q, model LLM, noise o, number of subsets N, public candidates obtained by zero-shot predictions Oc with total number of C, maximum token length M, method E (JEM, PTR).
Partition D1, ....... DN D.
2: for E {l...., N do
3: Form exemplar-uuery pair D = D
4: Obtain model output sentence (,(Q) LLM(D?).
5: end for
6: For each token, count the number of sentences in (Q)()) appears, and form histogram
7: if method = JEM then
8: Return JointEM(k; k, H). (Algorithm 5
9: else if method PTR then
10: 1: = (ind (Algorithm
11: Return TopKwi FindBestK(H)). (Algorithm 6
end if
16

---

Published as a conference paper at ICLR 2024
Algorithm 5 JointEM (Gillenwater et al. 2022
Require: Vector of item counts ....... Cd. number of items to estimate k. privacy parameter
1: Sort and relabel items so 61 cg
Cd
2: Construct matrix Ü by Ui - (a - c2) d(k-t)+
2dk
3: Sort Ü in decreasing order to get U1)) U(ak). storing the (row, column) of each ((a) as (r(a).
4: Initialize n,,...., n
5: Initialize set of non-zero n2, N < 0
6: Initialize 6 +
7: for 1,..,,,,d dk do
8: R2(a) + c(a) (r(a) 1)
9: N N (r(a))
10:
if |N 1: then
11:
break
12: end if
13: Set m((())) + O, and set b +
14: end for
15: Set + IFeej fr
Compute rn (U((U(+))) + p/ p/(rr())
17: for = 2, dk do
18:
Set p/nr(a)
19: Compute mū(U f-
20: Update (a(() f- (r(a)) + 1
21: Update p p -Tr(a)
22: end for
23: Sample a utility Üi from: [iss] a m (Üi) exp
[[(ey]]
Initialize size-k output vector with s; +
25: for i' = 1, i 1, 1, 1,..., k do
26: Compute 4. (U,r) by iterating through row of Ú
27: Sample s, uniformly from ty (U.,)) Mi 81, 82,
end for
29: Return Vector of item indices
17

---

Published as a conference paper at ICLR 2024
histogram over the outputs of all exemplars would violate privacy. This is challenge in extending KSA-JOINT to the infinite domain. We use this histogram to initialize data structure to efficiently sample with the joint exponential mechanism. Our implementation uses the code from (Gillenwater et al. 2022).
A.3.2 KSA VIA PROPOSE- TEST- RELEAE (KSA-PTR)
Notations. We use N denote the total number of tokens (c.g., N 50, 000). We use to denote the histogram for the counts of each token, and we use H() to denote the jth highest count, i.e.,
(1)) 2 H (2) 2 2 (N)-
The main idea of KSA-PTR is that, for the task of releasing the top-k index set of a voting histogram, (() (x)+) > 2. then the top-k indices are exactly the same for all the neighboring datasets. need to test whether (2) H (k+1) 2 in differentially private way, where we can leverage the famous propose-test-rlcasee paradigm (Dwork & Lei 2009), shown in Algorithm 6
Hence, release the exact top-k indices without any randomness. However,
Algorithm 6 TopKWithPTR
Require: k: number of top counted tokens to release;
histogram for the counts of each
token; failure probability
1: Set dę = (()) (()+1)-
2: Set de max(2, de) +N Φ 0,
3: If dy > 2, Return the exact top-k tokens.
4: Else Terminate (or use zero-shot learning).
As we can see, such an algorithm can have the highest utility when we choose the k that maximizes (())) ((++)) Hence, to further improve the utility of the algorithm, can select & in data- dependent way, i.e., we release argmax, H2)) H(++) rj in a differentially private way (which is another Report-Noisy-Man using Exponential mechanism.
Algorithm 7 FindBestK
Require: histogram for the counts each token
1: Compute histogram gap dg == H()) H ((4+1) for each k = 1.... N 1.
2: Return argmax, (dg- r(k) + Gumbel(4/E))
Here, r(k) is regularizer independent of the dataset, e.g., we can set r(k) oo for any h: > 30 and l < 15, if we don't want to return more than 30 or less than 15 tokens.
18

---

Published as a conference paper at ICLR 2024
B PRIVACY ANALYSIS
In this section, we review the important properties of differential privacy and provide the privacy analysis for the algorithms introduced in Section
Outline of this section: In this section, we first review the concept of DP as well as the necessary background of DP composition. The privacy analysis for differentially private text classification (RNM-Gaussian) is provided in Appendix [.I] The privacy analysis for ESA is provided in Appendix
B.2 The privacy analysis for KSA-Joint EM and KSA-PTR is provided in Appendix B.3.T and B.3.2
respectively.
We first state the formal DP definition.
Definition 1 (Differential Privacy (Dwork et al. 2006b)). For E,
5 2 O, randomized algorithm M MultiSets(2)) -> is (c, d ly private if for every neighboring dataset pair D, D' E MultiSets(A)) X), we have:
V Pr(M(D) E ET) E Pr[M(D') T
where the randomness is over the coin flips of M.
Differential privacy exhibits robust post-processing property. Informally, this means that if mechanism is differentially private, then any post-processing applied to the output of that mechanism is also differentially private. This property is crucial for enabling flexible analysis of privately released data.
Post-processing Property.
Lemma (Post-preee pros--scesssing (Dwork et al. 2006b).. M MultiSots(X)) + y (e. -)diffferential private and f - Z is an arbitrary (possibly randomized) function, then the composed mechanism fo MultiSets(2t) - Z is also (s, diffferrentil private.
(Adaptive) Composition of Differential Privacy. In practice, multiple differentially private mech- anisms may be applied to the same dataset. Crucially, multiple DP mechanisms can be adaptively composed in the sense that the output of one mechanism
be used an input to another mechanism, M1 M1, (D)).. Differential privacy offers strong composition guarantees, that help quantify the cumulative privacy loss resulting from these combined mechanisms. These guarantees are provided by various composition theorems or privacy accounting techniques, including the basic composition theorem (Dwork al., (006a)) advanced composition theorem (Dwork et al., 2010). and Moments Accountant (Abadi et al.] 2016). For example, the basic composition theorem states that if M1 is (1 D and M3 is (E2, DDD then the adaptive composition of Mj and M2 is (51 + =2, 61 + d2)
denoted as M(D) = M₁ M2(D) == (M₂
Consider two attackers: the first asks their allotted & queries in one batch and then observes the answers, the second asks each query sequentially and incorporates information gained from observing the answer to the current query into the next query. The second attacker is certainly stronger, and this increased strength is captured by adaptive composition.
Privacy Amplification by Subsampling. Privacy amplification by subsampling is a technique used to enhance privacy guarantees in differentially private mechanisms by randomly selecting subset of the data before applying the privacy mechanism. This subsampling process can lead to reduction in the privacy cost, allowing for better utility while preserving privacy. We can show that the Poisson subsampled Gaussian mechanism with sensitivity 1, noise scale o, and subsampling rate has the PRV Y log( ((o))((o)) ~ P. where P = (1 (0, o²) + 41((1, o²) and Q -O o²), and P(.). Q-) are the density functions P. Q. With the PRV of subsampled Gaussian mechanism well the PRV accountant, we can now efficiently and tightly track the privacy costs for DP-ICL.
B. TEXT CLASSIFICATION VIA RNM-GAUSSIAN
Theorem 3. The mechanism RNM-Gaussian Ma from Section 3.1 is (s, with 2 2lg((1.25/
Proof. Note that M, can be broken down into applying the argmax operator on a noisy histogram, which is generated by adding Gaussian noise to each dimension of the original histogram. The Gaussian mechanism is known to satisfy (c, 5)DP with A log(1 25/
Dwork al.
19

---

Published as a conference paper at ICLR 2024
2014), where A == s llf(D) ( represents the global sensitivity of the underlying aggregation function f. our case. f calculates the original voting histogram. As each exemplar- query prediction may alter two counts (increasing one and decreasing the other), the sensitivity A is v2. The overall privacy guarantee is then derived from the post-processing property of differential privacy.
B.2 EMBEDDING SPACE AGGREGATION (ESA)
Theorem 4. The Step to Step in Alg. is (E, with o = 2//oo(( (...1///////
Proof. Note that each embedding output by the text-to-embedding model has E2 norm to be 1. Hence, the referred steps are essentially the same as Gaussian mechanism with &g sensitivity 1. The last step of releasing the public candidate sentence that has the maximum cosine similarity can be regarded as the post-processing step and hence does not affect the overall privacy guarantee.
Remark 1 (Tracking Privacy Loss with PRV Accountant for Subsampled Gaussian mechanism).
To better keep track of the privacy cost for RNM-Gaussian and ESA, we the most recent advances in privacy cost accounting based on the notion of the Privacy Loss Random Variable (PRV) (Dwork) & Rothblum 2016). The PRV accountant was introduced by Koskela et al.) (2200) and later refined in Koskela & Honkela (2021); : Gopi et al.) (2027). For any DP-algorithm, one can easily compute its (e,0) privacy guarantee based on the distribution of its PRV. The key property of PRVs that, under (adaptive) composition, they simply add up; the PRV Y the composition M = M1 o M2 o....... Mr is given by Y= = Y,, where Y: is the PRV of M;. Therefore, one can then find the distribution of Y by convolving the distributions of Y1, Y2...., .,. Yv. Prior works (Koskela & Honkela [021] Gopi al. (2021) approximate the distribution PRVs by truncating and discretizing them, then using the
Fast Fourier Transform (FFT) to efficiently convolve the distributions.
B.3 LANGUAGE GENERATION VIA KEYWORD SPACE AGGREGATION (KSA)
Rényi differential privacy (RDP) is variant of the standard (e, dDP that uses Rényi-divergence as a distance metric between the output distributions of (DD) and M(D'), which particularly useful in training differentially private machine learning models.
Definition 5 (Rényi Differential Privacy (Mironov] (017 We say that mechanism M is (ox, M RRDP with order a E (1) if for every dataset pair D, D) e MultiSets(()) such that d( D. D') 1, we have:
(MMID (
)"} S (m((a)
Da ((DD)LM(D')) a- log BODD
(1)
where (-(()) denotes the density function of M' distribution.
Another useful relaxation of the RDP definition is approximate RDP.
Definition (Approximate RDP (Bun & Steinke 2016 Zhu Wang 2022 We say a randomized
algorithm M is d-approximately (a, (a)) (a)()))DDD RDDP with order I, for all neighboring dataset
D', there exist events E (depending on MMD) and E' (depending on M(D')) such that Pr[E] Z
1 - 5 and Pr E'
8, and Va Z we have
Da (M(D)I M (D') (E') S (M)
For both methods of KSA-JEM and KSA-PTR, we use RDP and approximate RDP for a tighter measure of the privacy cost under composition. After we obtain the (approximate) RDP guarantee for the overall algorithm, we can then convert the privacy guarantee back into the standard DP definition. We refer the readers to Bun & Steinke (2016) and Mironov (2017) for the composition and conversion formula for RDP and approximate RDP. In the following, we state the privacy guarantee of individual building blocks for private prompt generation and selection in terms of (approximate) RDP.
We then introduce the exponential mechanism (MeSheryy & Talwar 2007). one of the most famous and frequently used DP mechanisms. The exponential mechanism takes utility function MultiSets x y + R and can be thought of as evaluating how good gDD y) is for an outcome y E y on dataset D.
20

---

Published as a conference paper at ICLR 2024
Definition 7 (Exponential Mechanism). Let EMy MultiSets y be mechanism where for all outputs E y we have
(D) y) x exp (2)
(D.
where (g)) is the sensitivity of the quality score, i.e. for all neighboring inputs D, D' we have supyey (g(D,)) (D', y) S (4))
Furthermore, Durfee & Rogers (019)) shows that adding Gumbel noise to each output's utility and releasing the output with the highest noisy utility score is equivalent to using the exponential mechanism.
Theorem
[Bun Steinke
2016)).
The exponential mechanism is e-DP, and (a,, (an())))) s.t.
a
(inh((ae) sinh((a - 1)e)
Eεn(a) == min
log
sinh(E)
B.3.1 KSA VIA JOINT EXPONENTIAL MECHANISM (KSA-JOINT EM)
Theorem 9. Alg.
e-DP, and e (o)---DD
Proof. Alg. is an Exponential mechanism on the domain space of positive integers k = 1, 1, where the utility of k Ck. The sensitivity of dg since each exemplar-query prediction may alter count at most 1. Hence, the DP and RDP guarantee follows from the privacy guarantee of exponential mechanism in Theorem
B.3.2 KSA VIA PROPOSE-TEST-REIEE (KSA-PTR)
Theorem 10. Alg. i s-DP, and EEM (a)-RDP.
is an Exponential mechanism on the domain space of positive integers k = 1, 1,2..... where the utility of is d2 == H()) H(K+1). The sensitivity de is 2. Hence, and RDP
Proof. Alg.
guarantee follows from the privacy guarantee of exponential mechanism in Theorem g O
Theorem 11. Alg. is is 6-approximate 20 RDDP.
Proof. Releasing the noisy threshold du is - RDP.
da > 2, then releasing the exact top-k tokens has no privacy cost, as its local sensitivity is 0.
If d I 2, then if de < 2, the program terminates and there's no privacy cost.
If d S 2, the failure probability
Pr(d, > 2] Prrmmax(2, d4) + + Φ(1 6; 2]
Pr(2 + NV (02 - 8;0,20)
Pr[A - >
= 5
B.3.3 PRIVACY AMPLIFICATION BY SUBSAMPLING FOR APPROXIMATE RDP
In the following, we present the privacy amplification of approximate RDP by Poisson subsampling. To the best of our knowledge, are the first derive the following result.
Theorem 12. If M b-approximate (a) -DD, then M Poisson with subsampling rate is ōq-approximate McPoisoon RR), where $ McPoisson (a)) is the tightest possible amplification bound for any mechanism that M RRD with subsampling rate 9(1-5)
I-95
21

---

Published as a conference paper at ICLR 2024
Proof. Consider D = D' (2), D are neighboring datasets. Denote S D', and let ys the probability of sampling S. Denote μs = M(S).
M(Poisson(D))
Σ
Isps
(3)
SCD'
((Poisoon( D))
Σ SCD'
1s ((1 -9)1s + qusu(())
(4)
(1 9)
Tsps q Σ
YSMSu[=]
(5)
sgD
SCD
By definition of approximate RDP, for any pair of 5.5 U {2), we have event Es, Es) s.t.
(usus Esll: | S (m) and Pr[Es] = =1 and Pr[Esu(s)) = - 6. Hence, we can rewrite M(Poisson(D)) and ((Poisson(()) D)) as
M M(Poisson (D))) (1 q)
Σ
YSPS +
Σ
7s/S
SCD
SCD'
(1 4)
TspS +g Σ
78 ((1 - 0) Es + 8ps Es)
SCD'
SCD'
(1 - 9)
TSHS + 10(1 8)
Σ
Ysus Es + q0 Σ
7SPs Es
SCD
SCD
SCD
M(P) = (1 q)
7SPS +
YSMSsff}
DCD
SCD'
(1 9)
7SPS 9(( -)
Σ
]ss 98 Σ
(sP) [su(=)
SCD
SCD
sgD
Hence, there exists event Ep, Ep s.t. Pr[Ep] 2 96 and Pr[ED 2 1 g6, and
M(Poisson(D"))EE (1
7SPS + (1-6)
Es
1 qõ
1- SCD
SCD'
(1 9)
TsPS + q(1 -
M(PoissonDD)))B
(sMss(s)\Bsu(a]
1 qõ
1 qō
SCD
SCD
Hence
Da (M((PoissonDD)) Ep |M((oossonD"")))
(6)
has privacy amplification with subsampling rate g(1-8)
T-90
22

---

Published as a conference paper at ICLR 2024
C DP-ICL ENABLES PRIVATE PREDICTION
Our work represents a major departure from prior work on DP LLMs in that we consider private prediction rather than private training. A line of recent work (Li et al. 2022 Yu et al. 2022 Bu et al. 2022, He et al. (2023) has proposed fine-tuning pre-trained models on downstream tasks with differentially private stochastic gradient descent (DP-SGD) (Abadi et al. 2016). Despite ample research into DP LLMs and the growing industry demand for solutions to augment LLMs with proprietary data (Kuchaiev et al.) 2019 Nvidia 2023), number of key challenges remain for DP LLMs that we seek to address by considering private prediction.
Private training makes training harder. Fine-tuning with DP-SGD requires adopting entirely new hyperparameters and shifting existing hyperparameters to be radically different from non-private training (Li et al. 2022). Performing this additional hyperparameter tuning can take hundreds of trials. DP-SGD uses per-example gradient clipping to bound the sensitivity of individual datapoints. Materializing per-example gradients can increase the memory consumption of training by an order of magnitude (Bu et al. 2022) and slow down training. Although recent methods have been proposed for efficient hyperparameter tuning (Panda et al. 2022 Papernot & Steinke| [0222, efficient per ver-example gradient clipping (Li et al. 2022). and parameter-effiiient fine-tuning (Yu et al. 2022), , emphasize that DP-SGD introduces challenging engineering and optimization problems that are a topic of ongoing research. Our method requires no hyperparameter tuning and is computationally
efficient.
Private training is incompatible with black-box LLMs. Developers building on top of cloud- hosted LLMs such as OpenAl, Anthropic, or AWS Bedrock cannot implement the complex DP-SGD algorithm (Sivasubramanian 2023). Organizations employing closed-source LLMs such as GPT-3+. Claude, or Bard cannot even access the weights for fine-tuning and may never be able to (OpenAl 2023
Our method compatible with any LLM API.
Private training does not allow flexible data editing. Private training generates a single model that inextricably tied to each datapoint in its training data. This is at odds with the right to forgotten mandated by GDPR (Politico) (023). that would require retraining the entire model to delete the influence of private datapoint -an impracticality if not an outright impossibility when considering fine-tuning billion-parameter models. By contrast, honoring the right to be forgotten with DP-ICL is as straightforward as just removing the individual's 's private data from the exemplar database. Our method enables the right to be forgotten.
DP-ICL outperforms all previous DP-SGD methods on SST-2 benchmark (Table We also compare our results with current state-of oo-t-e--rttttttttt differentially private stochastic gradient descent (DP-SGD) methods on SST-2. The results illustrate an improvement over earlier methods. For instance, the enhancement at error rate, thereby establishing a new SOTA in the field Moreover, by presenting the results with E = oc, we notice that our performance gains do not correlate to the advanced large language model, where our upper bound is lower than other methods. That means DP-ICL exhibits less sacrifice when achieving differential privacy guarantee.
is 1.2%, which translates an over 20% reduction in relative
Table 5: Comparison of DP-ICL and DP-SGD on the SST-2 Dataset. Our DP-ICL method demonstrates significantly lower performance degradation under privacy constraints of e {3, 8).
Model
Method
3 (gap)
8 (gup)
DP-SGD Li al.
2022
93.04 (-3.16)
93.81 (-2.39)
96.20
RoBERTa-large
DP.SGD
Yu et al.
2022
95.30
96.40
(Liu et al. 2020
SPD 50
st. 2023
94.60 (-0.90)
94.70 (-0.80)
95.50
DP-SGD
et a..
2023
94.23 (-1.97
94.87 (-1.33)
96.20
GPT-3 Davinci
DP-ICL (Ours)
95.80 21 (+0.07)
95.83 (+0.10)
95.73 (4-shot)
Result present in Yu al. 2022
6.7.
However, DP-ICL in Table 5 capable of responding to a maximum of 10,000 queries, whereas DP-SGD has no such query limit and can answer an arbitrarily large number of queries. We defer to
'A minor discrepancy exists between our training data (sentence level) and the DP-SGD training data (phrase level) on the SST-2 dataset. Our training data is 10 times smaller than that of DP-SGD. However, the test data remains identical for both.
23

---

Published as a conference paper at ICLR 2024
practitioners to evaluate these factors when selecting the most appropriate algorithm for real-world applications.
Remark 2. We acknowledge that our DP-ICL is private prediction framework, which does not allow for infinite amount of queries. However, stress that in our experiment, consider up to 100, 000 queries, which arguably a huge number. Furthermore, many real-world applications where ICL is helpful, in-context examples will often be updated regularly. For example, for healthcare data analysis, systems that analyze patient data for research or treatment optimization might update their learning models regularly with new data. Banks and financial institutions might in-context learning for fraud detection, credit scoring, or personalized customer services. The dynamic nature of financial transactions could necessitate frequent updates the learning models, aligning with refreshed privacy budget.
24

---

Published as a conference paper at ICLR 2024
D DETAILS OF EXPERIMENTS SETUP
In this appendix, we present more details of our experiment setup, including the text classification task (Appendix D.I. as well as the language generation tasks (Appendix D.2
D.1 TEXT CLASSIFICATION
Task. Following Zhang et al. (0022), we employ the template summarized Table to carry out experiments text classification tasks. We configure the logit bias to 100 via the GPT-3 API to ensure that the output token belongs to one of the predefined labels (c.g., positive and negative). We then select the label with the highest probability. We use value of 0.0 for the temperature.
Table 6: The template prompts for our experiments.
Dataset
Template
Labels
SST-2
Review:
[text] Sentiment: (label)
Positive, Negative
Title: [title] Review: [review]
Amazon
Positive, Negative
Sentiment [lahel]
World, Sports, Business, Technology
AGNews
Article: [text] Answer: (label)
Classify the questions based whether their answer type Number, Location, Person, Description, Entity, or Abbreviation. Question: (text) Answer Type: (label]
Number, Location, Person, Description, Entity, Abbreviation
TREC
Dataset.
Our experiments are conducted on four datasets, the details of which are presented Table Given that the training data size for each dataset fewer than 10,000, set ó to 10-1,
Table 7: Information about the Text Classification Dataset
Dataset
Task
# of classes of exemplars of test data
avg. length
SST-2
Sentiment cls.
6,920
872
37.8
Amazon
Sentiment cls.
8,000
1,000
78.5
AGNews
Topic cls.
8,000
1,000
19.3
TREC
Question cls.
5,452
500
10.2
D.2
LANGUAGE GENERATION
We then provide the detailed setup for document questions answering and dialog summarization.
D.2.1 DOCUMENT QUESTIONS ANSWERING
Task. For document questions answering task, we use data from Privacy Preserving Federated Learning Document VQA (PFL-DocVQA) competition" The primary objective is to create privacy- preserving approaches for fine-tuning multi-modal models, for both vision and language, to improve document understanding. These documents often contain sensitive or confidential information. As research is centered on language generation, skip the vision module and assume that accurate OCR tokens have been extracted from the document images. We leverage the language model to answer the posed questions, and example of our evaluation is presented as follows:
Extracted OCR tokens from image: DUNNORICE... WEW.EEREEEEE...Seeeeee.... To:, WSIL-TV..nvocc.... Question: What is the identification number assigned the invoice in the document?
"The web link htttps://beeccharks..co elee-eeelaa....
25

---

Published as a conference paper at ICLR 2024
Answer the question with short term: 12970-2B
Extracted OCR tokens from image:
ORDER, ORDER,WORKSHHE WORKSHEET.KKyy Ordee.e
I.tatt, Traffiifii.......
Question: Could you share the ID associated with the document?
Answer the question with short term:
Dataset and Metrics. We use the training data contains 221,329 data and evaluate the performance on 100 data that are randomly selected from validation dataset. Therefore, we set the å for DP guarantee to 4 x 10-6, We use three evaluation metrics in this task: ROUGE-I, BLEU, and Levenshtein similarity. Specifically, ROUGE-1 measures the overlap of unigrams between the generated and reference texts, and BLEU checks for matching words but considers them in n- n-grams. The Levenshtein similarity metric is derived from the Levenshtein distance, which measures the minimum number of single-character edits needed to transform one string into another.
Model. Due the long OCR-extracted tokens, avoided using the paid GPT API. We plan to conduct more extensive experiments if we have increased funding. For the current evaluation, we used the open-source model OpenLLaMA-13B Geng & Liu (2023).
D.2.2 DIALOG SUMMARIZATION
Task. Then we provide the detailed experiment setup for dialog summarization, where use the SAMsum dataset Gliwa et al. (2019). This dataset has conversations between people, some which may be private. We use the prompt guide the task, which is as follows:
Dialogue:
Sandra: Are you sleeping?
Matija: Nope
Sandra: How so?
Matija: is Friday :D
Sandra: So you are partying?
Matija: File photo :D
Sandra: You are in bed already?
Matija: Of course :P
Sandra: You are like old folks What are your plans for tomorrow?
Matija: Cleaning the apartment
Sandra: Wow, nice
Matija: Yea. Afterwards we are going to some restaurant, have a lesson at 4 and we are meeting that bartender at 6
Summarize the above dialogue:
Matija is in his bed on Friday nights. Tomorrow he is cleaning the apartment and afterwards
they are going the restaurant to have lesson at 4 and meet that bartender 6.
Dialogue:
Joyce: Check this out!
Joyce: <link>
Michael: That's cheap!
Edson: No way! I'm booking my ticket now!!
Summarize the above dialogue:
When using keyword space aggregation by PTR, change the "Summarize the above dialogue:" to 'Summarize the above dialogue with the following word suggestions:". When using keyword space aggregation by joint EM, we change the "Summarize the above dialogue:" "Summarize the above dialogue with the following word suggestions ranked by their frequency from high to low:".
Dataset and Metrics. We use the training data containing 14,732 data and evaluate the performance on 100 test data. We set the x 10-5, Following He et al. (2023), we use ROUGE-I, ROUGE-2, and ROUGE-L- as the evaluation metries.
26

---

Published as a conference paper at ICLR 2024
Model. We leverage the GPT-3 Davinci to conduct the experiments. Our methods can also apply to other large language models.
27

---

Published as a conference paper at ICLR 2024
E ADDITIONAL EVALUATIONS ON TEXT CLASSIFICATION
In this appendix, provide additional ablation studies for the text classification task. We discuss the impact of using DP-ICL with different queries (Appendix [EI) and models (Appendix [.2] We also examine how performance changes with varying numbers of in-context examples (Appendix E.4 and subsampling rates (Appendix E.3)
E.1 EFFECTIVENESS OVER VARIOUS QUERIES
In this subsection, we conduct ablation experiments to learn the influence of varying the number of queries on performance, as illustrated in F The outcomes for the TREC dataset were obtained using the GPT-3 Davinci model, whereas results for all other datasets employed the GPT-3 Babbage model. We keep
constant and use 10 ensembles. Our observations reveal that the performance degradation resulting from an increase in the number of queries remains negligible, up to 10,000, with a decrease of less than 2%. Furthermore, it was observed that performance drops were more significant for the AGNews and TREC datasets compared to the remaining datasets. We hypothesize that this drops attributed to the property of multiple classes (i.e., 4 and 6) within the AGNews and TREC datasets.
100
90
Accuracy
80
SST-2
70
Amazon
AGNews
TREC
60
100
10
10a
10a
104
10
Number of Query
Figure 6: Performance across numbers of the query.
E.2 EFFECTIVENESS OF VARIOUS MODELS
In this subsection, explore various GPT-3 variants available through OpenAl's service. Specifically, we evaluate GPT-3 Ada (350M), GPT-3 Babbage (1.3B), GPT-3 Curie (6.7B), and GPT-3 Davinci (175B) four text classification tasks, detailed in Table 8 as our results in Table 2
We configure the setting be the same
Table 8: Results of DP-ICL for Text classification
Dataset
Model
E
(0-shot)
0 (Pub.)
8
1
8
3
6 co (Agg)
6 = oc
Ada
86.24
80.16
73.31
75.10
75.38
72.29
70.92
Babbage
86.58
89.45
91.97
92.83
92.90
92.87
91.89
SST-2
Curie
91.51
92.89
94.03
94.86
94.94
95.07
94.03
Davinci
94.15
95.30
95.11
95.80
95.83
95.73
95.49
Ada
92.00
84,90
89.68
90.26
90.32
90.70
88.51
Amazon
Babbage
93.80
91.60
93.83
94.10
94.12
94.10
93.58
Curie
95.90
94.30
95.37
95.67
95.69
95.58
95.28
Ada
37.50
40.00
65.60
70.51
71.22
71.72
60.23
AGNews
Babbage
52.60
61.80
75.49
81.00
81.86
82.22
68.77
Curie
62.40
68.10
80.00
81.88
82.06
81.80
78.31
Ada
20.40
22.80
23.72
25.41
25.86
26.28
22.62
Babbage
23.00
24.40
24.48
26.36
26.26
26,32
27.00
TREC
Curie
29.20
29.80
37.95
41.96
42.50
42.24
36.57
Davinci
79.60
80.60
73.31
83.86
84.53
85.92
79.08
28

---

Published as a conference paper at ICLR 2024
We observe consistent performance improvements the model becomes advanced indiccttdd by increased parameters across all datasets. For example, in the SST-2 dataset, zero-shot perfor- mance increased from 86.24% for Ada to 94.15% for Davinci. Correspondingly, our DP-ICL results also improved, rising from 73.31 % to 95.11% with e 1 on the SST-2 dataset. This suggests further enhance DP-ICL performance. Interestingly,
that more advanced models in the future zero-shot performance can sometimes surpass in-context learning results, particularly for the Ada model on the Amazon dataset. This is caused by the influence of suboptimal in-context exemplars or limited in-context learning capabilities for small models. Therefore, estimating the utility of in-context learning (ICL) and zero-shot learning essential before deploying DP-ICL.
We also present the results of four-shot predictions utilizing publicly available data in Table g Specifically, we apply data from the IMDB (Maas et af.) 2011) dataset for the SST-2 and Amazon tasks, the Arise'TV (chimaobi Samuel. 2022) dataset for the AGNews task, and the QQP (Wang et al. 2017) dataset for the TREC task, following the setting of (Duan al., 2023b). Our analysis reveals that using public exemplars generally enhances performance compared to the zero-shot method, but this improvement is not uniformly observed across all datasets. The reason lies in the varied quality of public data, where low-quality public data introduce inaccurate correlations between input and output mappings. On the other hand, DP-ICL with = {3. 8} can consistently outperform the 4-shot prediction with public data all settings except the SST-2 with the Ada model. Particularly, the improvement on the AGNews dataset is over 20%. is also worth noting that in many domains, high-quality, labeled public dataset may not be available, especially in specialized domains like healthcare, where in-context exemplars often require highly specific and sensitive data.
E.3 EFFECTIVENESS OF MORE ADVANCED MODELS
In Table we present the analysis GPT-3.5 and GPT-4 across various datasets, using both O-shot and 4-shot learning. The results indicate that the 4-shot approach yields consistently better performance than the 0-shot prediction, especially for AGNews and TREC. This trend underscores the importance of utilizing in-context learning to enhance model efficacy even for more advanced models in some scenarios.
Table 9: Zero-shot and Four-shot Results for more advanced models GPT-3.5 (0-shot)
Dataset
GPT-3.5 (4-shot)
GPT-4 (O-shot)
GPT-4 (4-shot)
SST-2
95.06
95.18
93.23
94.15
Amazon 96.20
96.60
95.90
96.00
AGNews
76.20
84.40
83.80
86.10
TREC
77.60
81.60
80.40
85.80
Table 10: Effectiveness of DP-ICL for more advanced models
Dataset
GPT-3.5 (0-shot)
GPT-4 (0-shot)
GPT-3.5 (4-shot)
AGNews
76.20
84.40
83.80
86.10
TREC
77.60
81.60
80.40
85.80
E.4 EFFECTIVENESS OVER THE NUMBER OF IN-CONTEXT EXEMPLARS.
In our primary evaluation Table we set our analysis four in-context exemplars. In this ablation study, we extend our evaluation to include broader range of in-context exemplars: 1, 2, 4, 8, and 16. For these experiments. we maintain an ensemble size of 10. Therefore, using more shots requires higher subsampling rate, which increases noise in the voting histogram.
$ FExact model name: 3ot-3.5-turbo-ing instruct Exact model name: apt-4-1186-prevt
29

---

Published as a conference paper at ICLR 2024
100
90
Accuracy
80
-=1 1
70
3
8
60
=
1
2
4
8
16
Number of Shots
Figure 7: Performance across numbers of the in-context exemplars.
In Figure 7 our evaluation reveals that performance remains stable for E = co. However, significant performance degradation occurs for setups with 8 and 16 shots, experiencing drops about 10% and 20%, respectively. This degradation is attributed to the introduction of additional noise.
E.5 EFFECTIVENESS OVER SUBSAMPLING RATES
To better understand the cost-utility trade-off in our proposed DP-ICL, we investigate the impact of subsampling strategies in Fig. 8 To save the computation cost, our evaluation is limited to test sets comprising 100 data for two datasets: SST-2 and AGNews. Our empirical results indicate that subsampling rate of around 0.5 10-3 for the exemplars achieved satisfactory performance, which are 10 samples post-subsampling. We further evaluate the estimated cost associated with querying the GPT-3 Babbage API, illustrated in Fig. 8 (Right). Notably, subsampling rate of 0.5 10-2 the cost only $0.0945 for 100 predictions on the SST-2 dataset. Increasing the subsampling rate beyond this point does significantly improve performance while resulting higher costs.
100
--STT-2
Estimated Cost ($)
AGNews
90
Accuary
4
80
3
60
SST-2 AGNews
50
10-1
10-7
10-2
10-1
Subsampling Rate
Subsampling Rate
Figure 8: Left: Performance across the subsampling rate. Right: Estimated GPT-3 Babbage API Cost of predicting 100 test samples. The size the training set for SST-2 is 6,920, and for AGNews, is 8,000.
Furthermore, also plot the cost and accuracy tradeoff in [eeubiinn two figures in Figure We found that using the GPT-3 Babbage API to predict 100 data points from the SST-2 and AGNews incurs mere of approximately $0.1 while achieving comparable performance.
S
30

---

Published as a conference paper at ICLR 2024
100
Accuary (%)
60
SST-2
AGNews
10-2
10-1
10" ($)
Estimated Cost
Figure 9: The trade-off between cost and accuracy for GPT-3 Babbage API.
31

---

Published as a conference paper at ICLR 2024
F ADDITIONAL EVALUATIONS ON LANGUAGE GENERATION
In this appendix, we present ablation studies for language generation tasks. Results for the document coession-answering task are Appendix F.I and those for dialog summarization are in Appendix F.2
F.1 DOCUMENT QUESTION ANSWERING TASK
Performance across varying numbers of queries (Figure 10) In document question answering tasks, we evaluate the keyword space aggregation via PTR method, as it consistently outperforms embedding space aggregation. Our analysis reveals that performance remains stable up 10 queries, allowing us to guarantee strong performance for at least 10y queries.
Keyworr Space by PTR
Keyword Space PTR
Keyworrd Space PTR
68
33
63
65
30
60
Levenshtein
ROUGE-1
62
57
10
10a
10a
10
10a
10a
Query
Query
Query
Figure 10: Ablation studies on varying numbers of queries.
F.2 DIALOG SUMMARIZATION TASK
Effectiveness across numbers of public candidates (Figure I1). We study the performance of the embedding space aggregation method with varying numbers of public candidates, As anticipated, an increased number of public candidates leads to improved performance. The ideal scenario would involve maximizing the number of public candidates. However, a larger pool of candidates also needs more API queries, thereby increasing the overall cost.
ROUGE-1
50
ROUGE-2
Performance
ROUGE-L
40
30
20
10
0
20
40
60 Candidates
70
90 100
Figure 11: Performance across numbers of the public candidates (i.e., number of answers generated by zero-shot predictions) for embedding space aggregation method.
Effectiveness across numbers of ensembles (Figure 12 Here, we present the full results of ablation studies of the number of ensembles.
32

---

Published as a conference paper at ICLR 2024
Embedding Agg. Space Agg. joint
Embedding Agg.
Embedding Space Agg.
Space Agg.
Keywerd Space Agg. joint
Keyword Space Agg. by PTR
- -eyword Space Agg. by PTR
-Kywwrr Space Agg. by PTR
ROUGE-1
42
ROUGE-2
ROUGE-L
32
39
14
29
36
11
26
100
Ensembles
Ensembles
Ensembles
Figure 12: Ablation studies on varying numbers of ensembles. Full results of Figure (Ta)
Effectiveness across numbers of queries (Figure 13) Here, we present the full results of ablation studies of the number of queries.
Embedding Space Agg- Keyword Space Agg by joint EM Keyword Space Agg. by PTR
Embedding Space Agg.
Embedding Space Agg. Keyword Space Agg. by joint EM Keywerd Space Agg. by PTR
- Keyword Space Agg. by joint EM
Keyword Space Agg. by PTR
45
20
35
ROUGE-1
ROUGE-2
ROUGE-L
42
17
32
39
14
29
36
11
26
8
10a
10a
10a
10a
10*
10a
10a
102
103
10a
10a
10a
102
10a
10*
Query
Query
Query
Figure 13: Ablation studies on varying numbers of queries. Full results of Figure 5
5lb)
F.3 EFFECTIVENESS OF ADVANCED MODELS
In this subsection, we evaluated the zero-shot and four-shot prediction capabilities in more advanced models, specifically GPT-3.5 and GPT-4. Our findings reveal that utilizing four-shot predictions, which involve in-context learning with private exemplars, significantly enhances overall model performance. For instance, the improvement across all metrics on Document QA for GPT-4 is larger than 12%. This improvement trend consistent with results from the dialog summarization task.
Table II: Zero-shot and Four-shot Results for more advanced models
Task
Prediction
GPT-3.5 (0-shot)
GPT-3.5 (4-shot)
GPT-4 (0-shot)
GPT-4 (4-shot)
ROUGE-1 f BLEU Levenshtein
63.18 18
73.68
66.21
78.
Document QA
39.28
51.42
37.09
51.15
52.13
66.14
59.80
74.89
ROUGE-17 1 ROUGE-2
33.22
39.44
28.64
38.83
Dialog Summ.
11.91
16.33
10.28
15.79
ROUGE-L 1
25.08
31.21
21.95
30.41
F.4 TFADE-OFF BETWERN COST AND ACCURACY
In this subsection, we present the trade-off between cost and accuracy for dialog summarization task. Here, we used the price 10 of the updated version of GPT-3 Davinci to estimate the final cost of
summarizing 100 dialogs. We present the results in Figure 14 where we vary the ensemble number
1ºGPT-3 Davinci is going to be deprecated Jan 4th 2024 and the suggested replacement by OpenAT is 1e--3.5-turbb-intteee
33

---

Published as a conference paper at ICLR 2024
from 10 to 100. Specifically, the cost of the ESA is calculated both multiple ensemble queries and the generation potential candidates (O-shot predictions). For KSA, the cost also involves multiple ensemble queries plus additional O-shot prediction for constructing the final sentence from keywords. We set the candidate number to 100 for ESA. We observe that ESA by joint EM can achieve comparable performance with only ~22
Embedding Space Agg. Keyward Space Agg. by joint EM Keyword Space Agg. by PTR
Embedding Space Agg. Keyword Space Agg. by joint EM
Embedding Space Agg. Keyword Space Agg. by joint EM Keyword Space Agg. by PTR
- Keyword Space Agg. by PTR
-
45
20
35
ROUGE-1
ROUGE-2
ROUGE-L
42
17
32
39
14
29
8
30
5
20
1
2
1
2
6
7
1
6
7
Estimated Cost (S)
Estimated Cost (S)
Estimated Cost ($)
Figure 14: The trade-off between cost and accuracy for dialog summarization task.
34

---

Published as a conference paper at ICLR 2024
G EXAMPLES OF ESA OUTPUT IN DIALOG SUMMARIZATION TASK
In this section, we offer some qualitative examples of zero-shot candidates and the final outputs selected by embedding similarity. It is observed that the final outputs demonstrate only fluency but also a heightened similarity to the ground truth compared to the zero-shot candidates.
Dialogue:
Sybille: Hello, i'm trying to make my online registration for the flight AF3581 from Min- neapolis to Paris the 29th, but i only get an error message. Here my file number NRTTU and my flying blue number XXXX. Thanks for you help.
Air France: Hello Sybille, we acknowledge receipt of your message and return to you as soon possible.
Air France: After checking your flight is operated by Delta Airlines for departure from the United States. Online registration works from the Delta site.
Sybille: Hello again, still have trouble for my son' s online registration. I'm really angry as it cost me more than 40 curos for 20 minutes your short number 3654, and still don't 't have any answer. He couldn't 't get his flight yesterday, so asked for it to be postpone. twice gave my credit number but still the ticket is not delivered.
Air France: Of course, give the file to an agent.
Air France: Please, be awared could take 24 hours
Sybille: can't wait so long. My son is only 16 year old and he has to sleep in the airport,
with no mean leave his luggage as he has no ticket.
Air France: Hello Sybille, we re very sorry We could offer you a departure on flight DL from Minneapolis Paris. We'll return to you.
Sybille: My phone number is XXXX, please call me back as soon as possible
Sybille: Hello, i was again on line with people from the short number. They told me that they've done everything possible but my payment can't be accepted because the flight is operated by Delta. Please consider a young stuck US with no possibilites for coming back just because of Delta and Air France sharing code, can't 't share payment.
Air France: We'll get in touch with Delta US and return to you quickly
Sybille: thanks lot
Air France: We just send you by email the new ticket for you son. We remain at your disposal.
Sybille: Thanks lot, you're more efficient than the hotline.
Zero-shot summarization candidates:
Sybille contacted Air France trying make her son's online registration. After recognizing the flight was operated by Delta, Air France suggested the customer to complete the Al online registration on the Delta website. Sybille then proceeded point out her dissatisfaction regarding the long time she spent on the hotline without getting any solution. Air France then offered her new flight 4L from Minneapolis to Paris, and subsequently sent her a new ticket for her son by email. Sybille thanked Air France for their help.
Sybille was trying to make an online registration for her son's flight from Minneapolis to Paris but kept getting error message. She contacted Air France and told to register online with Delta Airlines. After explaining her son was stuck in the US with no means to leave, Air France contacted Delta US and quickly sent her an email with the ticket for her son. Sybille thanked Air France for their efficiency. Sybille was attempting
make online registration for flight with Air France, but encountered an error message. Air France told her the flight was operated by Delta Airlines, who she should use to do the registration. The customer became frustrated as she was charged for a phone call, yet still had not received a successful registration. Air France offered a new ticket for her son via email and the eustomer thanked them for their efficiency.
Sybille is trying to make her son's online registration for the flight AF3581 from Minneapolis to Paris on the 29th, but she only gets an error message. She contacts Air France customer service, who informs her that the flight is operated by Delta and so she must use the Delta online registration system. When Sybille is still having trouble, she expresses her frustration at the costly and time consuming customer service hotline. Air France then contacts Delta and sends a new ticket for her son by email.
35

---

Published as a conference paper at ICLR 2024
Sybille is trying make online registration for flight from Minneapolis to Paris for her son, but she is encountering issues. Air France offers an alternative flight and eventually sends ticket via email. Sybille thanks Air France for their help.
A customer was unable to make an online registration for their son's 's flight from Minneapolis to Paris and forked out 40 euros for 20 minute phone call. After Air France checked the flight flight, the customer was informed that the registration must be done through the Delta website. Air France offered the customer an alternative flight option and eventually customer an email with a new ticket for their son. The customer thanked Air France for their efficiency.
the
Sybille is trying to make online registration for her son's flight from Minneapolis to Paris on the 29th, but is running into trouble. Air France acknowledged her concerns and directs her to the Delta Airlines website in order for her to make the registration. After Sybille expresses her anger over the delay and her son sleeping at the airport without any mean to leave his luggage, Air France offers her departure on flight DL140 from Minneapolis to Paris. She provides Air France with her phone number for them to call her back, and after getting in touch with Delta US, Air France emails Sybille Sybille contacted Air France to make an online registration for her son for flight from Minneapolis Paris, but encountered errors. Air France suggested that the registration should be done from the Delta site, but Sybille was unable to register due to payment issues.Ain France sent an agent help and offered an alternate flight. Finally, they sent an email with the new ticket for Sybille's 's son and thanked them for their help.
ticket for her
Sybille needed help with registration for a flight operated by Delta Airlines and encountered problems with online registration, payment, and lack of response via the hotline. Air France responded by looking into the information and offering a different flight option, which they later emailed the ticket for. In the end, Sybille thanked them for their efficiency.
Selected candidate:
Sybille is trying to make an online registration for a flight from Minneapolis to Paris for her son, but she is encountering issues. Air France offers alternative flight and eventually sends a new ticket via email. Sybille thanks Air France for their help.
Ground Truth:
Sybille is angry, because she cannot make reservation for the flight from Minneapolis to Paris. Air France managed to solve the issue.
36


Reviews:
[{"review_id": "gVO0FZ67bq", "reviewer": "Reviewer_cEpf", "summary": "This paper tackles the problem of differential privacy in the context of in-context learning. To this end, the authors propose a framework that consists of partitioning, predicting, and aggregating. For the aggregation, the authors propose several algorithms depending on the scenarios: private voting for text classification & embedding space aggregation (ESA), and keyword space aggregation (KSA) for language generations. Through the experiments on 4 text classification datasets, 1 QA dataset, and 1 summarization dataset, the authors demonstrate the proposed method successfully imposes differential privacy without the loss of accuracy, compared to the non-private counterpart.", "questions": "Please address the concerns in above.", "limitations": "", "rating": 6, "confidence": 2, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "1. **Well-motivated problem.** Differential privacy of LLMs is an interesting and important problem.", "weaknesses": "1. **Rooms for the improvement of the draft.** First, lots of details are currently missing. For example, there is no explanation of how $\\epsilon$ determines the noise $\\sigma$. While there is no explicit mention in the main draft, the results in Appendix B (Theorems 3 and 4) might be used. But, even if this is true, there is no mention of how $\\delta$ is set. In addition, how the given # of queries (e.g., 10,000 queries in Sec 4.1) is used for the algorithm? In Algorithms 1~4, there is no relevant part. \n2. **Limited technical novelty.** While the introduction of differential privacy in the context of ICL is novel, most of the techniques are adopted from the previous works.   \n3. **Limited motivation for ESA.** The authors propose both ESA and KSA for language generation tasks. However, it seems that there is no merit in using ESA over KSA, as KSA always outperforms ESA in the experiments. Since introducing several candidates even makes practitioner confused about what to use, more support for ESA are required. In addition, it would be good to include qualitative examples of ESA’s sentence candidates with 0-shot inference and the finally selected one.", "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": "NXNeOoMesu", "reviewer": "Reviewer_3Mai", "summary": "This paper focuses on the problem of private data leakage of in context examples, during few-shot prompting (in-context learning). A new operation mode of LLMs is to ask a model to perform the task, and provide some examples for it, instead of actually performing any fine-tuning or changing the model parameters. In such use-cases, if the in-context examples have private information in them, there is a chance that it leaks to the output. To prevent this leakage, the authors propose differentially private in context learning methods for classification and generation. \n\nThese methods are all based on some form of noisy voting/decoding. The classification is directly using noisy max, but for the generation task the authors propose 3 different methods, to solve the problem of high dimensionality. They propose three different methods, one where the generation is mapped to embedding space, noisier and then mapped back to sentence space. The other two methods do noisy generation of keywords, and then uses a language model to generate text based on that.\n\nThe authors evaluate their proposed method on numerous tasks/datasets and compared to non-private baselines.", "questions": "1. What are some real-world applications in which the authors think DP-ICL could be applicable, i.e. where the ICL few-shot samples are private, and using them is absolutely necessary, as for most of the existing tasks in the paper zero-shot performance is already high.\n\n\n2. Do the authors have any measure of fluency for the generated text, specially for the embedding aggregate method? Human evaluations are usually performed in NLP generation tasks, human evaluations are usually performed to see how fluent the generated text is, and I wonder how the transformation of sentence to and from embedding impacts its fluency.\n\n\n\nMinor comment: \n\nThe Min et al. 2022 reference is duplicated in the references (there are two versions of it)", "limitations": "", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "1. The problem the authors are studying is timely, as practitioners are not really fine-tuning models any more and rely on prompting more and more, therefore solutions like DP-SGD are not relevant.\n\n\n2. The paper is very well-written and flows really well. The visuals are well-crafted and help the understanding of the paper a lot.\n\n3. I like how thorough the paper is, in terms of the cases they study: classification and generation, and I also like the workarounds proposed for generation to limit the space. They are novel and also address the problem in a suitable way. Pairing up the keyword aggregation method with PTR was very interesting to me.", "weaknesses": "1. Limited number of queries: as there is budget expenditure per query, the model deployed with DP-ICL can only be queried a limited number of times, making the method/data unusable after the budget is finished. This is not a huge concern in scenarios where there is temporal data available, and the in-context examples would get updated regularly. However, it could be a problem during deployment for long term.\n\n2. Zero-shot performance is already really high, would probably be even higher for GPT3.5 or GPT4, which are not reported in the paper.\n\n3. There are no existing measures or proof of concept attacks that show private in-context data leakage.", "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": "hnBqbO7UvA", "reviewer": "Reviewer_2dnr", "summary": "The author proposed a new Differentially Private In-Context Learning framework (DPICL) to minimize privacy risk in in-context learning. The main idea is to leverage the private “sample-and-aggregate” paradigm. For text-classification, the paper proposed to report the noisy max with gaussian noise; For text generation, the paper proposed to use embedding space aggregation or keyword space aggregation.", "questions": "See weakness.", "limitations": "", "rating": 6, "confidence": 2, "soundness": 3, "presentation": 2, "contribution": 2, "strengths": "The proposed methods are intuitive and in the experimental section, authors find DP-ICL achieves a comparable performance with non-private ICL.\n\nThorough experimental studies ranging from text classification, question answering, and summarization. In particular, the proposed framework can be applied to QA and summarization tasks which are complex and challenging tasks.", "weaknesses": "It is a little confusing on how the author analyzed the sensitivity and how are the neighboring database is defined.\n\nHow much extra cost (monetary and privacy budget) does the proposed framework incurs? It would be great if the author can include some insights on the cost vs accuracy trade off.\n\nIs comparing 4-shot vs 0-shot a fair comparison? In the related work section, the author mentioned work using examples from public dataset. Perhaps a better comparison is between private 4-shot using examples from the training data vs. 4-shot using examples from public data.", "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": "B5VKbXhihS", "reviewer": "Reviewer_ZNqV", "summary": "The paper proposes a new paradigm for privatizing in-context learning tasks called “DP-ICL”, which achieves a strong utility-privacy trade-off and a comparable performance as the non-private counterpart. The authors demonstrate the effectiveness of DP-ICL on text classification and language generation tasks, and show that it offers a promising overall paradigm for applying ICL in a privacy-preserving way.", "questions": "- How do you see the DP-ICL paradigm being applied in real-world scenarios, and what are some of the challenges that would need to be addressed?\n- What are some of the limitations of the DP-ICL paradigm, and how might they be addressed in future research?", "limitations": "", "rating": 8, "confidence": 4, "soundness": 3, "presentation": 4, "contribution": 4, "strengths": "- This paper is well-written and well-organized. \n- The proposed paradigm is novel and is a novel paradigm for privatizing ICL tasks.\n- The authors provide a clear and concise explanation of the DP-ICL paradigm. The figures and captions are easy to understand.\n- Experiments on 4 benchmark datasets are extensive and sufficiently demonstrated the promise of the approach towards trustworthy usage of large language models.", "weaknesses": "- Limitations can be discussed in more details. For example, “a better-trained embedding-to-text model may yield further improvements in the model performances.” Then what can be the potential candidate models here and why did the authors not adopt these models?", "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)