INTRODUCTION

In-context learning (ICL) (Brown et al., 2020;Min et al., 2022) enables large language models (LLMs) (OpenAI, 2023) to adapt to domain-specific information without modifying the pre-trained model. This adaptation is achieved by conditioning the model on a prompt, which contains an instruction and a series of task-specific question-answer pairs (called demonstrations or examples). Using this prompt, LLMs can then generate responses that are tailored to the corresponding task. The ease of usage and cost-benefit of ICL have motivated the adoption of LLMs in several applications, such as machine translation (Sia and Duh, 2023), code generation (Pourreza and Rafiei, 2023) and customer service (Lee et al., 2022).

However, privacy is a significant concern when incorporating users' data into prompts, especially in areas like healthcare and finance (Wang et al., 2023;Priyanshu et al., 2023;Duan et al., 2023), as this introduces risks of exposing sensitive personal information. To address this concern, existing works (Wu et al., 2023;Tang et al., 2023;Duan et al., 2023;Carey et al., 2024;Hong et al., 2023) have explored approaches to mitigate these risks using the rigorous privacy safeguards provided by differential privacy (DP) (Dwork et al., 2006b). Notably, Tang et al. (2023) proposed to generate synthetic few-shot demonstrations from the private dataset for use in ICL inference and guarantee DP with respect to examples in the private dataset. This method uses the classic DP sample-and-aggregate framework (Nissim et al., 2007;Papernot et al., 2016;2018), partitioning subsampled private data into disjoint subsets, each of which is used in a prompt for an LLM to generate tokens. These tokens Figure 1: Two-Stage framework for privacy-preserving ICL. In Stage 1, DP-protected demonstrations are generated with AdaDPSyn, where we illustrate the process of generating the next token "City" following "New York". AdaDPSyn uses a novel clustering approach to dynamically aggregate next-token probabilities. The process iterates until nshot demonstrations are generated. In Stage 2, the generated DP-protected demonstrations are combined with a user query to construct the prompt. The constructed prompt is then sent to an LLM and the answer is returned to the user. are then privately aggregated, adhering to DP guarantees, to create synthetic demonstrations. This framework allows the synthetic demonstrations to be used for an infinite number of queries without incurring any additional privacy costs.

The main design challenge in Tang et al. (2023) is aggregating the responses from an LLM privately. Tang et al. (2023) used a data-independent way of adding the same amount of Gaussian noise during private aggregation. However, since each token generated by the LLM can contain varying levels of private information, applying noise homogeneously across an entire sentence or document may not achieve the optimal privacy-utility tradeoff in the ICL framework. Therefore, it is more strategic to design DP mechanisms that adapt the noise level in a data-adaptive manner. Intuitively, by adaptively adjusting the additive noise level based on the properties of responses for individual tokens, we avoid adding unnecessarily large noise to tokens with high agreement or predictability, which indicates low risk, thereby achieving improved utility for ICL. The main question we aim to answer is:

Can we design a data-adaptive differentially private prompt synthesis algorithm to protect the private information contained in the prompt data and effectively perform ICL? In this work, we provide an affirmative answer to this question. Our main contributions are summarized as follows:

• We introduce a new algorithm AdaDPSyn in Algorithm 1 to generate synthetic few-shot examples for use in ICL prompts (Figure 1). Similar to Tang et al. (2023), AdaDPSyn begins by obtaining next-token generation probability vectors from an LLM using multiple subsets of private dataset, which will then be aggregated to generate the next token differentially privately. The essential novelty of AdaDPSyn lies in our proposed Precision-Focused Iterative Radius Reduction technique, which adaptively adds noise level during aggregation by exploiting the cluster structure of the predicted distributions of the next token. Besides, we believe that our data-adaptive technique may be applicable in various problems beyond prompt synthesis, thus is of independent interest. • We conduct a rigorous privacy analysis of AdaDPSyn and confirm it follows (ε, ¶)-DP. In our analysis, we use the Rényi Differential Privacy (RDP) (Mironov, 2017) framework to track and tightly quantify privacy costs from the composition of AdaDPSyn's components across multiple iterations. By applying RDP composition rules and subsampling amplification, we establish theoretical privacy guarantees for AdaDPSyn. • We empirically evaluate the performance of AdaDPSyn against the DP few-shot generation algorithm proposed by Tang et al. (2023) on standard benchmarks. We demonstrate that our method outperforms this baseline across a plethora of privacy settings. For example, in the AGNews classification task under a strict privacy level of ε = 1, our method achieves an accuracy of 65.42%, higher than 60.74% by DP few-shot generation. In the information extraction task MIT-G at ε = 1, our method reaches 37.59% accuracy, compared to 31.15% by DP few-shot generation. Additionally, we show that our AdaDPSyn algorithm can closely match the performance of non-private baselines even in stringent privacy settings. For instance, at a strict privacy level of ε = 1, our algorithm attains an accuracy of 65.42% on the AGNews task, nearly reaching the nonprivate baseline's accuracy of 65.92%. Similarly, in the DBPedia task, our method shows minimal performance drop-off compared to the non-private scenarios. These results not only underscore the effectiveness of our AdaDPSyn algorithm compared with data-independent methods, but also demonstrate its competitiveness with non-private solutions.

Adaptive Differential Privacy. Adaptive differential privacy primarily focuses on privately calibrating noise to the local sensitivity, which is a dataset-dependent function and is much smaller than the global sensitivity. Two representative solutions include the smooth sensitivity framework (Nissim et al., 2007) and the propose-test-release (PTR) framework (Dwork and Lei, 2009). The main idea of the smooth sensitivity framework is to add noise calibrated to the smooth sensitivity, an upper bound on the local sensitivity which changes slowly between neighboring datasets (Bun and Steinke, 2019;Gonem and Gilad-Bachrach, 2018;Fletcher and Islam, 2017;Zafarani and Clifton, 2020;Hamman et al., 2023;Sun et al., 2020). The PTR framework involves proposing bounds of the local sensitivity and testing its validity. If the test is passed, the noise is calibrated according to the proposed bound (Thakurta and Smith, 2013;Liu et al., 2022;Redberg et al., 2023;Wang et al., 2022;Liu et al., 2022).

In this work, we release a confidence bound of the local sensitivity in a differentially private manner, and calibrate noise accordingly, similar to the idea in prior studies (Blocki et al., 2012;Kasiviswanathan et al., 2013;Wang, 2018;Decarolis et al., 2020). In this body of research, Blocki et al. (2012) and Kasiviswanathan et al. (2013) focus on network data. Wang (2018) revisits the DP linear regression problem. Decarolis et al. (2020) study the Latent Dirichlet Allocation (LDA) model. Our focus is on the ICL domain, where we develop a novel clustering method and Precision-Focused Iterative Radius Reduction technique to address domain-specific challenges.

Differentially Private Synthetic Text Generation. Our work falls within the broader scope of DP synthetic text generation, which typically requires generating large volumes of synthetic data. There is a line of work on DP synthetic text generation through private fine-tuning (Yue et al., 2022;Mattern et al., 2022;Mireshghallah et al., 2022;Carranza et al., 2023;Yu et al., 2024;Wu et al., 2024). SeqPATE (Tian et al., 2022) and Submix (Ginart et al., 2022) are methods based on PATE (Papernot et al., 2016;2018) for text generation, which utilizes an ensemble of teacher models trained on private data subsets to fine-tune a student model. Another direction (Feyisetan et al., 2020;Xu et al., 2020;Du et al., 2023;Utpala et al., 2023) focuses on sanitizing user texts locally before server submission based on local differential privacy (Chatzikokolakis et al., 2013). While this approach typically reduces text utility, recent studies (Chen et al., 2022;Arnold et al., 2023b;a;Mireshghallah et al., 2022) propose to enhance utility by incorporating inherent properties of language such as semantic similarity (Chen et al., 2022), context (Arnold et al., 2023b) and syntax (Arnold et al., 2023a;Mireshghallah et al., 2022).

PROBLEM DEFINITION, THREAT MODEL, AND NOTATIONS

In-context learning. Given a query x, a candidate answer set (label set) Y and a pre-trained large language model LLM such as GPT (Radford et al., 2018;OpenAI, 2023), ICL aims to predict a label y ∈ Y of query x, using LLM conditioned on

) is an input-label pair. In this paper, we consider both classification and information extraction tasks. For classification tasks with a restricted label space Y = {y 1 , . . . , y m }, we first compute the probability of each label y i ∈ Y using LLM as P LLM (y i | C, x). Then we predict the final label y by selecting the label with the highest probability from the label set Y, i.e., y = arg max yi∈Y P LLM (y i | C, x). For information extraction tasks, the label space Y is unrestricted, and can include any sequence of tokens from the LLM's vocabulary. In these tasks, we predict y by having LLM generate a sequence of tokens until it produces a special end-of-sequence (EOS) token, marking the completion of the output.

Differentially private ICL. Our objective is to protect the privacy of demonstrations C ¦ D priv in the prompt against an adversary that aims to access or infer private information about the demonstrations. Since ICL tasks may encounter an unlimited number of queries, to protect the privacy of the dataset D priv , we adopt a differentially private data synthesis approach to generate synthetic few-shot examples C = { z 1 , • • • , z nshots }, where z i = ( x i , y i ), from the underlying distribution of D priv while satisfying (ε, ¶)-differential privacy on the private dataset D priv . For each ICL task, we generate task-specific synthetic examples C with the help of an LLM and a private dataset D priv . Then ICL can be performed using demonstrations from C in a prompt tailored to each task. By default, we incorporate all demonstrations from C in a prompt for each task.

We formally define (ε, ¶)-differential privacy ((ε, ¶)-DP) as follows.

Definition 1 ((ε, ¶)-Differential Privacy (Dwork et al., 2006a)). A randomized algorithm A is (ε, ¶)differentially private if for any two neighboring inputs D and D ′ that differ by a single entry and any set S of possible outputs:

PROPOSED METHOD

We use a two-stage framework to perform differentially private ICL, as illustrated in Figure 1. Generally speaking, in Stage 1, we generate DP synthetic few-shot demonstrations C = { z 1 , • • • , z nshots } based on the private dataset D priv ; and in Stage 2, we use these synthetic demonstrations for ICL.

The main challenge of this framework lies in the DP synthetic data generation (Stage 1). To maintain DP, a PATE-like framework is utilized, similar to Tang et al. (2023). Take the generation of a synthetic demonstration z = (x, ỹ) ∈ C as an example. First, label ỹ ∈ Y is randomly selected independently of private dataset D priv , and its corresponding demonstration x is generated token by token, starting from an empty string x =''. The next token for x is generated by aggregating probability vectors p 1 priv , . . . , p M priv , each of which is calculated by an LLM taking some prompt as input. Each prompt is a concatenation of a subset of examples (in a reverse order (y i , x i )) from the private dataset D priv = {(x i , y i )}, the synthetic label ỹ and the currently generated string x. Due to the dependence of the probability vectors on private dataset D priv , DP aggregation is required, and a classic way to achieve this is by adding noise (e.g., Gaussian mechanism) as in Tang et al. (2023).

Our approach is motivated by a hypothesis that the next-token predictions by different examples approximately reach a consensus. Once this hypothesis holds, the key innovation of our approach is to leverage this feature and reduce noise levels during aggregation in a data-adaptive manner. We verify the hypothesis quantitatively and tackle the key challenge in the following two sections, respectively.

CONSENSUS BEHAVIOR MEASURED BY CLUSTERING

We quantitatively measure the degree of consensus among the next-token generation probability vectors pfoot_0 priv , . . . , p M priv . Specifically, we approach this by visualizing consensus through the geometric concept of enclosing these vectors within a minimal enclosing ball, defined as an (r, c, Ä)-ball, where r is the radius, c is the center and Ä ∈ (0, 1] represents the required portion of vectors covered in the ball. For a given coverage requirement Ä, a smaller r indicates a tighter grouping, reflecting a high consensus among the model outputs. We hypothesize that these next-token generation probability vectors are typically highly clustered in a ball with a small radius r. To verify the hypothesis, we conduct experiments using the DP fewshot generation algorithm (Tang et al., 2023), and report the radius r of the minimal ball that encloses at least 80% (Ä = 0.8) of the next-token probability vectors generated by using different private examples in Table 1. For determining a small radius r that contains at least 80% of the input points, we adopt the GoodRadius algorithm in Nissim et al. (2016). We conduct experiments on three classification tasks: AGNews (Zhang et al., 2015), DBPedia (Zhang et al., 2015) and TREC (Voorhees and Tice, 2000), as well as two information extraction tasks, MIT-G and MIT-D (Liu et al., 2012), using the Llama-2-7b-hf model (Touvron et al., 2023) 1 . Details of the DP few-shot generation algorithm parameters can be found in Table 12.

As shown in Table 1, the measured radius r, ranging from 0.05 to 0.15, is much smaller than √ 2/2, the radius of the minimal ball that contains the probability simplex. These results confirm a high degree of clustering among the model outputs. Intuitively, if we can access such a ball of small radius r differentially privately, we can perform a differentially private projected mean aggregation that projects the probability vectors to the ball and calculates the projected mean with additive Gaussian noise. The noise level is determined by the sensitivity 2r. Note that in Tang et al. (2023), without leveraging the clustering behavior of the data, a much higher noise level corresponding to sensitivity √ 2 is employed. Comparing these two cases, the sensitivity 2r is approximately 5× to 14× smaller than √ 2, thus leading to more accurate aggregation due to lower noises. The key challenge is then how to differentially privately access a small ball that contains a majority number of probability vectors and perform the differentially private aggregation correspondingly. To tackle this challenge, we propose a novel Precision-Focused Iterative Radius Reduction technique.

PRECISION-FOCUSED ITERATIVE RADIUS REDUCTION

Building on the observation that next-token generation probability vectors from the LLM are highly clustered, we utilize an intuitive approach to adaptively adjust the noise level during aggregation: we first locate the minimal ball covering most vectors under DP and then project all points to this ball in ℓ 2 -norm to bound the influence of each point, thereby minimizing noise addition. This method, which adaptively leverages the inherent structure of the probability vectors, is essential to the success of our proposed method.

The task of finding a minimal enclosing ball under DP is known as the DP 1-clustering problem in the literature (Nissim et al., 2016). However, existing methods (Nissim et al., 2016;Nissim and Stemmer, 2018;Ghazi et al., 2020) are hard to implement and computationally expensive.

To this end, we propose a novel technique called Precision-Focused Iterative Radius Reduction. We start with a large radius R and judiciously reduce it towards a small target radius r through iterative refinement. The target radius r is obtained under DP constraints using a tractable subroutine GoodRadius from DP 1-clustering (Nissim et al., 2016), which provides a threshold such that the designed radius should never go below. The reduction of radius R is carefully monitored by coverage checks, which ensure the majority of the probability vectors are covered by a ball with that radius. The center of the ball is efficiently obtained by private projected mean estimation. This dynamic adjustment of the ball ensures it is minimized effectively according to the distribution of the points along the adjustments. The amount of noise required for private projected mean estimation can be reduced, thus improving the quality of the synthetic demonstrations and the performance of ICL. We elaborate this Precision-Focused Iterative Radius Reduction technique in Section 4.3.

ADADPSYN ALGORITHM

We now introduce the proposed AdaDPSyn algorithm (Algorithm 1), which generates DP synthetic few-shot examples from the private dataset D priv . For a given label ỹ randomly selected from the label set without replacement, AdaDPSyn sequentially generates one token at a time, starting from an empty list. Each token generation begins with the Next Token Generation subroutine (Line 4). Roughly speaking, the Next Token Generation process (Tang et al., 2023) involves sampling M N examples with label ỹ from the private dataset D priv , dividing them into M disjoint subsets, and then using these subsets as demonstrations to predict the next token's distribution p 1 priv , . . . , p M priv using an LLM. The vocabulary is restricted to S containing the top-K most probable tokens, which are determined from next-token probabilities generated only from instructions without using any private data. Details of Next Token Generation can be found in Appendix A.1. Then we privately aggregate p 1 priv , . . . , p M priv using our Precision-Focused Iterative Radius Reduction technique (Lines 5-21), which consists of four critical steps:

Step 1: Establish Target Radius Differentially Privately. The process begins by setting a target radius r using the GoodRadius subroutine (Nissim et al., 2016) in Line 5. GoodRadius is a subroutine used in DP 1-clustering methods (Nissim et al., 2016;Nissim and Stemmer, 2018), which identifies a radius that can encompass at least a fraction Ä of the data points under (³, Ä 0 )-RDP constraints. In this work, we set Ä = 80%. Details are provided in Appendix A.2.

Step 2: Projected Mean Estimation Using Gaussian DP Mechanism. For a probability simplex in R d , its radiusfoot_1 is √ 2

2 . Thus, we set R ← √ 2/2 (Line 6) initially. We initialize projected points pi priv ← p i priv , i = 1, . . . , M (Line 7), and estimate mean of {p 1 priv , . . . , pM priv } using Gaussian DP mechanism (Line 8), i.e., ppriv ← 1

, where à 1 is the noise multiplier. Then we map ppriv back onto the probability simplex, i.e., ppriv ← max( ppriv,0) ∥ max( ppriv,0)∥1 (Line 9). Next, we reduce R towards the target radius r iteratively, ensuring that it covers a sufficient amount of probability vectors while satisfying DP (Lines 11-21). During the iterative process, which takes at most T iterations, each step starts with a radius coverage check detailed in the following paragraph.

Step 3: Radius Coverage Check Using Gaussian DP Mechanism. We use Gaussian DP mechanism to check whether a sufficient number of the original probability vectors p 1 priv , . . . , p M priv remain within a small radius from ppriv (Line 12). Specifically, the check evaluates whether the ℓ 2 -ball with center ppriv and radius r + 2λRσ1 √ K M can cover at least µM of the points p 1 priv , . . . , p M priv , where ¼ is a hyperparameter, Ã 1 scales the Gaussian noise introduced to ppriv in Line 8 or Line 20, K is the dimensionality of the probability vectors, and µ ∈ (0, 1]. We set µ = 0.55 in this work. The term

represents an additional margin on the radius to accommodate the spread introduced by Gaussian noise added to ppriv in Line 8 or Line 20, ensuring data coverage despite the distortion caused by the noise.

Step 4: Update Radius towards Target Radius. If the radius coverage check in Line 12 reveals that fewer than µM vectors are within the defined radius, the algorithm will stop reducing the current radius R. Otherwise, the algorithm proceeds to adjust R downward (Line 15-18), i.e., R ← r

. Then we project next-token probability vectors {p 1 priv , . . . , p M priv } to a ℓ 2 -ball defined by radius R and centered at ppriv (Line 19), i.e., pi priv = ppriv +(p i privppriv ) max 1,

This operation ensures that the ℓ 2 -sensitivity of the term

pi priv is at most 2R. Finally, we estimate the mean of the projected points {p 1 priv , . . . , pM priv } using Gaussian DP mechanism (Line 20), i.e., ppriv

As R decreases, the amount of noise added to ppriv is reduced accordingly. We then map ppriv back onto the probability simplex, i.e., ppriv ← max( ppriv,0) ∥ max( ppriv,0)∥1 (Line 21). The process of radius refinement concludes under any of the following conditions: (1) the maximum allowed number of iterations, T , is reached; (2) further reduction in radius fails to cover the minimum required proportion of vectors (Line 12); (3) the current radius R is smaller than r+ 2λ1Rσ1 √ K M (Line 15). Once the radius refinement process concludes, we select the next token for the synthetic sequence as arg max j∈S ppriv [j] where S is the vocabulary of size K, and this token is appended to what is generated so far. This continues until the sequence reaches the predefined maximum limit, T max , of tokens we would like to generate. Remark 1 (Comparison with Tang et al. (2023)). The main difference between our method and that of Tang et al. (2023) lies in the innovative approach we take toward the private aggregation of the next-token generation probabilities p 1 priv , . . . , p M priv . Instead of directly using the Gaussian DP mechanism for aggregation as in Tang et al. (2023), our approach introduces an advancement through the Precision-Focused Iterative Radius Reduction technique (Lines 5-21). This technique allows noise to be added in a data-adaptive manner, effectively adapting the noise level to the degree of agreement among the models. Empirically, we evaluate the performance of our algorithm against Tang et al. (2023) in Section 5.1 to demonstrate the effectiveness of our method.

PRIVACY ANALYSIS

Theorem 1. Algorithm 1 is (ε, ¶)-differentially private.

Proof Overview. We adopt the commonly used Rényi differential privacy (RDP) (Mironov, 2017) to track the privacy cost in our algorithm, as it allows us to tightly quantify the privacy guarantees from the composition of multiple mechanisms. Our proof mainly consists of three steps. First, we show that each iteration of the algorithm is (³, Ä )-RDP. In each iteration, our algorithm consists of 3 components: one instance of (³, Ä 0 )-RDP algorithm GoodRadius (Line 5), at most ( T +1) instances of (³, Ä 1 )-RDP projected mean estimation using Gaussian DP Mechanism (Line 8 and Line 20) and at most T instances of (³, Ä 2 )-RDP radius coverage check using Gaussian DP Mechanism (Line 12). We apply the composition property of RDP to ensure the privacy guarantee in each iteration, that is, we ensure that Ä = Ä 0 + ( T + 1)Ä 1 + T Ä 2 . Next, since the Next Token Generation subroutine (Line 4) involves drawing M N samples from the dataset D priv , there is a privacy amplification by subsampling at each iteration. Finally, we compose privacy loss across all the T max iterations of our algorithm using composition theorems. We rely on the conversion lemma (Balle et al., 2020) to convert the RDP guarantee back to DP notions. We provide a full proof in Appendix B.

EXPERIMENTS

Datasets. We study text classification on three datasets: 4-way news classification AGNews (Zhang et al., 2015), 6-way question classification TREC (Voorhees and Tice, 2000), and 14-way topic classification DBPedia (Zhang et al., 2015). For information extraction, we study the MIT Movies trivia10k13 slot-filling dataset (Liu et al., 2012), which includes movie genre (MIT-G) and director name (MIT-D) as slots. Additional dataset details are available in Appendix C.2.

Setups. We use the synthetic few-shot demonstrations { z 1 , • • • , z nshots } from Algorithm 1 as input demonstrations in ICL for the aforementioned downstream tasks. We fix n shots = 4 by default, generating 4-shot demonstrations (randomly without replacement from the label set) for ICL. We use Llama-2-7b-hf model (Touvron et al., 2023) as our pre-trained LLM to generate synthetic Algorithm 1 AdaDPSyn 1: Input: Private dataset: D priv , label: ỹ, maximum token count: T max , an LLM: LLM(•), noise multiplier: Ã 0 , Ã 1 , Ã 2 , number of disjoint subsets: M , samples per subset: N , reduced vocabulary size: K, hyperparameters: ¼ and T . 2: Initialize:

ppriv ← max( ppriv,0) ∥ max( ppriv,0)∥1 10:

t ← the count of p 1 priv , . . . , p M priv within a ℓ 2 -ball centered at ppriv with radius r + 2λRσ1

µM then 13: break ▷ DP Radius Coverage Check 14: end if 15: if R < r + 2λRσ1 √ K M then 16: break 17: end if 18: R ← r + 2λRσ1 √ K M ▷ Update Radius towards Target Radius 19:

ppriv ← max( ppriv,0) ∥ max( ppriv,0)∥1

22:

end for

23:

w ← arg max j∈S ppriv [j] 24:

x ← x + [w] 25: end for 26: return x. demonstrationsfoot_2 . We use the same prompt format during ICL following Tang et al. (2023) (see Appendix C.11). For ICL downstream tasks, we use Llama-2-7b-hf for AGNews, DBPedia, MIT-G, and MIT-D, and GPT-4o mini for TRECfoot_3 . For DP algorithms, we follow the common practice to set the privacy budget ¶ = 1/ |D priv | (Tang et al., 2023;Hong et al., 2023).

Baselines. We compare our AdaDPSyn algorithm with DP few-shot generation in Tang et al. (2023), which uses a data-independent approach of adding the same level of Gaussian noise during aggregation. Hypermarameters in DP few-shot generation are detailed in Table 12, including the number of subsets M , the number of data samples per subset N , the number of tokens T max , and the reduced vocabulary size K. To ensure a fair comparison, we select these parameters for DP few-shot generation based on the guidance in Tang et al. (2023), as detailed in Appendix C.5. We then use the same values of M , N , T max and K for our AdaDPSyn without any additional hyperparameter tuning.

As a fully private baseline ε = 0, we follow Tang et al. (2023) to generate synthetic 4-shot demonstrations using purely instructions without any private data 5 . We consider two non-private baselines Table 2: 4-shot ICL performance on the test set of downstream tasks with baselines. Results show the mean and standard deviation of accuracy over 5 runs. Our private solution with various privacy levels ε = 1, 2, 4, 8 uses AdaDPSyn to generate DP synthetic few-shot demonstrations for ICL, in comparison with the DP fewshot generation algorithm (Tang et al., 2023). ε = 0 represents a fully private solution. ε = ∞ serves as the non-private baseline.

Dataset

Method

few-shot generation 61.38 7.10 60.74 3.09 62.64 1.82 62.70 1.30 63.18 1.26 65.92 1.13 AdaDPSyn 65.42 1.08 65.52 0.81 65.84 1.03 65.92 1.02 DBPedia DP few-shot generation 63.92 3.07 64.68 1.42 64.78 1.29 64.92 1.99 65.26 2.12 69.06 1.40 AdaDPSyn 66.76 1.45 67.48 1.54 67.12 1.09 67.70 1.68 TREC DP few-shot generation 59.40 2.62 62.48 9.38 65.28 5.67 66.12 5.46 66.52 5.57 72.32 2.76 AdaDPSyn 69.32 7.19 69.80 4.57 71.48 2.93 72.08 2.24 MIT-G DP few-shot generation 13.62 6.51 31.15 4.04 34.00 5.13 35.85 3.63 36.10 5.52 43.23 7.00 AdaDPSyn 37.59 5.40 37.41 4.36 37.85 4.25 38.31 5.03 MIT-D DP few-shot generation 52.29 9.43 72.87 3.48 73.11 1.86 74.60 2.29 75.18 3.74 79.33 1.48 AdaDPSyn 73.35 2.13 74.41 2.55 75.08 1.30 75.28 1.93

for ε = ∞: (i) DP few-shot generation algorithm operates without any added noise; (ii) 4-shot demonstrations randomly selected from the private dataset. We present the best of two accuracies between the two baselines. Specifically, (i) performs better for AGNews, TREC, and MIT-G, while (ii) performs better for DBPedia and MIT-D, as detailed in Table 5.

It is noteworthy that, on the AGNews task, the fully private baseline ε = 0 outperforms baseline DP few-shot generation with higher ε values. This aligns with findings from Tang et al. ( 2023) (Table 1 in Tang et al. (2023) 6 ), which highlights that LLMs are capable of generating meaningful demonstrations purely from instructions in some applications, performing well even without private data. Meanwhile, AdaDPSyn outperforms the ε = 0 baseline at ε = 1, 2, 4, 8, showing the advantage of our data-adaptive design.

MAIN RESULTS

We present our main results in Table 2. We provide the mean and standard deviation of the accuracy on the test data with ICL over 5 runs with different random seeds. In general, our results demonstrate that AdaDPSyn outperforms DP few-shot generation (Tang et al., 2023) across various privacy settings, while also closely approximating the performance of the non-private baseline.

We observe that, compared with DP few-shot generation, AdaDPSyn provides gains at privacy levels ε = 1, 2, 4, 8. For instance, in the AGNews news classification task at ε = 1, our method achieves an accuracy of 65.42% compared to 60.74% under DP few-shot generation. In the DBPedia topic classification, we reach 66.76%, surpassing the previous 64.68%. Moreover, in the information extraction tasks, our performance improvements are also evident with MIT-G achieving 37.59% over 31.15% at ε = 1. This highlights our method's efficiency in adapting noise addition to the degree of consensus among model outputs, improving accuracy for ICL.

Additionally, our method closely approaches the performance of the non-private baseline ε = ∞ on several tasks. Specifically, for news classification AGNews with a strict privacy level as small as ε = 1, our method achieves an accuracy of 65.42%, just slightly below the non-private baseline's accuracy of 65.92%. For topic classification DBPedia at ε = 1, we record an accuracy of 66.76%, near the baseline's 69.06%.

In the question classification task TREC at ε = 1, our approach reaches 69.32%, closely following the baseline's 72.32%.

We conduct a hyperparameter search for AdaDPSyn on ¼ and T in Appendix C.4. We observe that ICL accuracy remains stable across different ¼ and T settings. For example, on AGNews, AdaDP-Syn achieves accuracy between 64.28% and 65.92% for T ∈ {1, 2} and ¼ ∈ {0.15, 0.2, 0.25}, compared to 63.18% for DP few-shot generation when ε = 8. This highlights the stability of Algorithm 1. We provide the parameters used for our main results in Appendix C.5.

ABLATION STUDIES

Varying number of shots. Using the DBPedia dataset and setting ε = 4, we test the number of shots for ICL with n shots = 1, 2, 4, 8. The results are presented in Table 3. ε = 4 (AdaDPSyn) presents the performance of our private solution and ε = 4 (DP few-shot generation) is based on the solution in Tang et al. (2023). We present two non-private performances: (i) DP few-shot generation algorithm operates without any added noise; (ii) few-shot demonstrations randomly selected from the private dataset.

We observe that AdaDPSyn consistently outperforms DP few-shot generation across all n-shot settings. Additionally, increasing the number of shots can improve the performance of AdaDPSyn. This suggests that AdaDPSyn can benefit from larger n-shot scenarios.

Table 3: ICL performance on the test set of the DBPedia dataset with various number of shots. ε = 4 (AdaDPSyn) uses AdaDPSyn to generate DP synthetic few-shot demonstrations for ICL. ε = 4 (DP few-shot generation) is based on the solution in (Tang et al., 2023). ε = ∞ (Algorithm 2 with σ = 0) represents DP fewshot generation algorithm operating without any added noise. ε = ∞ (rand) represents using demonstrations randomly selected from private dataset. Results show the mean and standard deviation of accuracy over 5 runs. n shots = 1 n shots = 2 n shots = 4 n shots = 8 ε = 4 (AdaDPSyn) 65.94 0.27 67.00 1.00 67.12 1.09 67.55 1.27 ε = 4 (DP few-shot generation) 64.44 1.55 65.06 1.98 64.92 1.99 66.32 1.57 ε = ∞ (Algorithm 2 with à = 0) 67.58 0.77 67.82 0.34 67.88 1.75 68.16 1.61 ε = ∞ (rand) 69.02 2.21 69.38 2.66 69.06 1.40 69.68 1.29

Varying LLMs. We evaluate ICL performance across different LLMs and present the results in Table 4. Specifically, we use the generated examples from Section 5.1 as demonstrations with GPT-3.5 Turbo and GPT-4o mini, available through OpenAI's service, for downstream ICL tasks. The experiments are conducted on the DBPedia dataset.

We observe that AdaDPSyn consistently outperforms DP few-shot generation and performs comparably to non-private baselines. Performance improves with both GPT-4o mini and GPT-3.5 Turbo for all models, with GPT-4o mini showing the highest overall results. Our method remains open to further improvements with more advanced LLMs. Table 4: ICL performance on test set of DBPedia dataset with various LLMs. ε = 4 (AdaDPSyn) uses AdaDPSyn to generate DP synthetic few-shot demonstrations for ICL. ε = 4 (DP few-shot generation) is based on the solution in (Tang et al., 2023). ε = ∞ (Alg 2, σ = 0) represents DP few-shot generation algorithm operating without any added noise. ε = ∞ (rand) represents using demonstrations randomly selected from private dataset.

.92 1.99 67.12 1.09 67.88 1.75 69.06 1.40 GPT-3.5 Turbo 89.94 0.85 91.92 1.46 92.16 1.19 93.26 0.45 GPT-4o mini 91.40 1.09 93.08 1.09 93.28 1.24 94.32 0.35

Performance against membership inference attacks (MIAs). Additionally, we conduct an empirical privacy evaluation in Appendix C.6 using membership inference attacks (MIA) (Shokri et al., 2017;Duan et al., 2023). Our results show that, in contrast to non-private ICL, which suffers from significant membership privacy leakage, our AdaDPSyn algorithm effectively reduces the MIA success rate to the level of random guessing.

CONCLUSION

In this work, we introduced the AdaDPSyn algorithm, a novel approach to ICL that incorporates DP to safeguard sensitive data used in LLM prompts. By leveraging a data-adaptive noise addition strategy through our Precision-Focused Iterative Radius Reduction technique, we effectively reduced noise levels without compromising DP guarantees, thus maintaining higher accuracy for ICL. Our empirical results demonstrate the superior performance of AdaDPSyn, which nearly matches the non-private baseline's performance on several benchmarks. One limitation of this work is the lack of theoretical guarantees for utility, as it is difficult to find an appropriate closed-form expression of ICL accuracy. We leave this exploration to future work.

A DP ALGORITHMS

In this section, we list all the differentially private mechanisms that are used in Algorithm 1 and provide their guarantees.

A.1 DP FEW-SHOT GENERATION

The DP few-shot generation algorithm (Tang et al., 2023) is detailed in Algorithm 2. The Next Token Generation subroutine (Tang et al., 2023) is presented in Algorithm 3. Algorithm 2 DP few-shot generation (Tang et al., 2023) 1: Input: Private dataset: D priv , label: ỹ, max number of tokens to generate: T max , a pre-trained LLM: LLM(•), number of disjoint subsets of private data: M , number of data samples in each subset: N , reduce vocab publicly with top-K, noise multiplier: Ã. 2: Algorithm used: Algorithm 3 for generating next token probilities from LLM. 3: Initialize: Set x ← []. 4: for t = 1 to T max do 5: p 1 priv , . . . , p M priv ← NextTokenGeneration (D priv , ỹ, LLM(•), M, N, K, x) 6:

w ← arg max j∈S p priv [j] 8:

x ← x + [w] 9: end for 10: return x Algorithm 3 Next Token Generation (Tang et al., 2023) 1: Input: Private dataset: D priv , label: ỹ, a pre-trained LLM: LLM(•), number of disjoint subsets of private data: M , number of data samples in each subset: N , reduce vocab publicly with top-K, generated tokens x.

priv , ỹ, x))

7:

S ← top-K indices of p 8:

p i priv [V \ S] ← 0 and re-scale p i priv s.t. p i priv [S] = 1 9: end for 10: return p 1 priv , . . . , p M priv A.2 GOODRADIUS Nissim et al. (2016) propose the GoodRadius algorithm (Algorithm 4) and provide its DP analysis. We adapt this with some modifications to provide an RDP guarantee. For readability, we include the RDP analysis here.

Theorem 2 (Nissim et al. (2016)). GoodRadius (Algorithm 4) is (³, Ä 0 )-RDP.

Proof. From Nissim et al. (2016), the sensitivity of L defined in Line 3 of Algorithm 4 is 2. Then in Line 4, we search for an r such that L(r) g t and L(r/2) < t while maintaining differential privacy. This is achieved by using binary search with noisy estimates of L for the comparisons. Specifically, we introduce a tolerance parameter ¹, which determines the precision of the binary search. The number of iterations for the binary search is at most +log 2 √ 2 2θ ,. In each iteration, we apply Gaussian mechanism to estimate L(r) and L(r/2), i.e., L(r mid ) ← L(r mid ) + N (0, 4à 2 0 ) and L(r mid /2) ← L(r mid /2) + N (0, 4à 2 0 ). By setting à 0 ← ³+log 2 √ 2 2θ ,/Ä 0 , we guarantee that each estimation satisfies (³, Ä 0 /2+log 2 √ 2 2θ ,)-RDP. By composition, the output r satisfies (³, Ä 0 )-RDP.

Algorithm 4 GoodRadius (Nissim et al., 2016) 1: Input: Database P ∈ (X d ) n , desired ball volume t, noise multiplier à 0 , tolerance ¹. (We set ¹ = 0.1 in our experiments.) 2: Notation: For a radius r g 0 and a point p ∈ X d , let B r (p) denote the number of input points contained in a ℓ 2 -ball of radius r around p. That is, B r (p) = {i : ∥x i -p∥ 2 f r}. Denote Br (p) = min{B r (p), t}.

3: For r g 0, define L as

▷ Search for an r s.t. (i) L(r) g t, (ii) L(r/2) < t, (iii) satisfies (³, Ä 0 )-RDP 5: return r Algorithm 5 DP Binary Search 1: Input: Function L, desired ball volume t, noise multiplier à 0 , tolerance ¹. 2: Initialize: r low ← 0 and r high ← √ 2/2.

if L(r mid /2) g t then

9: r high ← r mid 10: else if L(r mid ) g t then 11: r high ← r mid 12: else 13: r low ← r mid 14:

end if 15: end while 16: return (r low + r high )/2

B PRIVACY ANALYSIS

In this section, we provide the privacy analysis for Algorithm 1. Theorem 3 (Restatement of Theorem 1). Algorithm 1 is (ε, ¶)-differentially private.

We introduce some concepts and relevant theorems from the literature required for our analysis first. While (ε, ¶)-DP is a useful definition of privacy, it does not allow us to tightly quantify the privacy guarantees from the composition of multiple mechanisms. Instead, the notion of Rényi Differential Privacy (RDP) (Mironov, 2017) provides a succinct way to monitor the privacy costs from the composition of multiple mechanisms. Definition 2 (Rényi Divergence (Mironov, 2017)). For two probability distributions P and Q defined over R, the Rényi divergence of order ³ > 1 is

Definition 3 (Rényi Differential Privacy (Mironov, 2017)). A randomized algorithm A is Ä -Rényi differentially private of order ³ ((³, Ä )-RDP) if for any two neighboring inputs X and X ′ , which differ in only a single record, we have

Theorem 4 (RDP Sequential Composition (Mironov, 2017)). If A 1 and A 2 are (³, Ä 1 )-RDP and (³, Ä 2 )-RDP respectively then the mechanism combining the two g

Theorem 5 (RDP to DP conversion (Balle et al., 2020)). If a mechanism M is (³, Ä )-RDP then it is (Ä + log((³ -1)/³) -(log ¶ + log ³)/(³ -1), ¶)-DP for any 0 < ¶ < 1.

One of the most widely used mechanisms to guarantee RDP is the Gaussian mechanism.

Theorem 6 (Gaussian Mechanism). The Gaussian mechanism M : X → R m of the form

satisfies (³, Ä )-RDP, where ∆ 2 (q) = max x,x ′ ∥q(x)q(x ′ )∥ 2 is the ℓ 2 -sensitivity of the query q.

We also need the following privacy amplification theorem by subsampling.

Theorem 7 (Amplification by subsampling (Wang et al., 2019)). Given a dataset of n points drawn from a domain X and a mechanism M that takes an input from X m for m f n, let the randomized algorithm M • subsample be defined as: i) subsample without replacement m datapoints of the dataset (sampling parameter µ = m/n ), and ii) apply M to the subsampled dataset. For all integers ³ g 2, if M obeys (³, Ä (³))-RDP, then the subsampled mechanism M • subsample obeys (³, Ä ′ (³)) RDP where,

We are ready to do the privacy analysis of our algorithm (Theorem 1).

Proof. Fix one iteration of the algorithm and let us bound the privacy loss. Our algorithm consists of 3 components: a DP algorithm GoodRadius (Line 5), DP projected mean estimation using Gaussian DP Mechanism (Line 20) and DP radius coverage check using Gaussian DP Mechanism (Line 12). The output of GoodRadius algorithm r on Line 5 satisfies (³, Ä 0 )-RDP by Theorem 2. Consider projected mean estimation using Gaussian Mechanism. The projection operation in Line 19 ensures that the ℓ 2 -sensitivity of the term

pi priv in Line 20 is at most 2R. As we are adding Gaussian noise sampled from N (0, 4R 2 à 2 1 I), we can ensure ppriv in Line 20 satisfies (³, Ä 1 )-RDP by setting à 1 = ³/2Ä 1 (Theorem 6). For the radius coverage check using Gaussian Mechanism, in Line 11, t counts the number of points of p 1 priv , . . . , p M priv covered in a ball with center ppriv and radius r

. The sensitivity of the term t is 1. Then in Line12 we add Gaussian noise sampled from N (0, à 2 2 I) to t. By setting à 2 = ³/2Ä 2 , we can show the radius coverage check satisfies (³, Ä 2 )-RDP (Theorem 6). Our algorithm consists of one instance of (³, Ä 0 )-RDP algorithm GoodRadius (Line 5), at most ( T + 1) instances of (³, Ä 1 )-RDP projected mean estimation using Gaussian DP Mechanism (Line 8 and Line 20) and at most T instances of (³, Ä 2 )-RDP radius coverage check using Gaussian DP Mechanism (Line 12). We apply the composition property of RDP (Theorem 4) to ensure each iteration of the algorithm is (³, Ä )-RDP, that is, we ensure that

Further, note that in each iteration, the Next Token Generation subroutine (Tang et al., 2023) involves drawing M N samples from the dataset D priv , there is a privacy amplification by subsampling at each iteration. We apply Theorem 7 to show that the effective privacy loss per iteration of our algorithm is (³, Ä ′ )-RDP for the full dataset.

Finally, we compose privacy loss across all the T max iterations of our algorithm using composition theorems (Theorem 4). We conclude that Algorithm 1 satisfies (³, T max Ä ′ )-RDP and convert the privacy guarantee back into the standard DP definition (Theorem 5).

Table 5: Performance of non-private baselines on test datasets. We report mean and standard deviation of accuracy over 5 runs with different random seeds. ε = ∞ (Algorithm 2 with à = 0) column represents DP few-shot generation algorithm operating without any added noise. ε = ∞ (rand) column represents using 4-shot demonstrations randomly selected from the private dataset.

) AGNews 65.92 1.13 65.28 2.65 DBPedia 67.88 1.75 69.06 1.40 TREC 72.32 2.76 53.12 3.72 MIT-G 43.23 7.00 42.08 6.35 MIT-D 78.36 3.33 79.33 1.48

example, on the AGNews dataset, AdaDPSyn achieves accuracy in the range of 64.28%-65.92% for T ∈ {1, 2} and ¼ ∈ {0.15, 0.2, 0.25}, compared to 63.18% for DP few-shot generation ε = 8. This is good in terms of the stability of Algorithm 1.

Table 6: ICL performance on the test dataset of AGNews across varying ¼ and T values, showing mean and standard deviation of accuracy over 5 runs with different random seeds. We set ε = 8, à 0 = 10, à 2 = 3. For specific T values, we set à 1 = 0.58 when T = 1, and 0.72 when T = 2.

1 64.28 1.48 65.92 1.02 64.90 0.97 T = 2 64.38 3.16 65.76 1.13 65.18 1.76

Table 7: ICL performance on the test dataset of DBPedia across varying ¼ and T values, showing mean and standard deviation of accuracy over 5 runs with different random seeds. We set ε = 8, à 0 = 10, à 2 = 3. For specific T values, we set à 1 = 0.73 when T = 1, and 0.90 when T = 2. ¼ = 0.15 ¼ = 0.2 ¼ = 0.25 T = 1 66.14 2.91 67.70 1.68 66.90 1.25 T = 2 66.02 3.22 66.30 2.09 65.28 3.13

Table 8: ICL performance on the test dataset of TREC across varying ¼ and T values, showing mean and standard deviation of accuracy over 5 runs with different random seeds. We set ε = 8, à 2 = 5. For specific T values, we set à 0 = 10 and à 1 = 0.89 when T = 1, and à 0 = 15 and à 1 = 1.09 when T = 2.

1 70.08 2.53 70.28 2.63 70.52 3.62 T = 2 71.24 2.96 72.08 2.24 71.08 4.31

Table 9: ICL performance on the test dataset of MIT-G across varying ¼ and T values, showing mean and standard deviation of accuracy over 5 runs with different random seeds. We set ε = 8, à 0 = 10, à 2 = 5. For specific T values, we set à 1 = 0.73 when T = 1, and 0.90 when T = 2.

1 37.10 3.48 36.33 7.28 36.51 5.03 T = 2 36.95 3.90 38.31 5.03 37.56 5.47

We also perform ablation studies on à 0 and à 2 . To evaluate their impact, we conduct experiments on the MIT-G dataset with ε = 8, varying à 0 ∈ {10, 15, 20} and à 2 ∈ {3, 4, 5}. The results are presented in Table 11.

Table 10: ICL performance on the test dataset of MIT-D across varying ¼ and T values, showing mean and standard deviation of accuracy over 5 runs with different random seeds. We set ε = 8, à 0 = 15, à 2 = 5. For specific T values, we set à 1 = 0.83 when T = 1, and 1.03 when T = 2.

1 75.28 1.93 74.94 2.88 73.30 2.47 T = 2 74.31 2.32 74.17 1.47 73.11 2.04

We observe that ICL accuracy remains stable across different à 0 and à 2 , ranging from 37.08% to 38.41%, showing an improvement over the 36.10% achieved by DP few-shot generation. This stability arises because, despite varying à 0 and à 2 , the resulting change in à 1 (noise multiplier of projected mean estimation) is very small (0.90-0.92).

Table 11: ICL performance on the test dataset of MIT-G across varying à 0 and à 2 values, showing mean and standard deviation of accuracy over 5 runs with different random seeds. We set ε = 8, T = 2, ¼ = 0.2.

37.08 3.92 37.87 4.92 38.26 4.55 Ã 2 = 4 37.15 3.85 38.28 4.30 38.41 4.71 Ã 2 = 5 38.31 5.03 37.56 4.62 38.18 4.72

C.5 HYPERPARAMETERS

To ensure a fair comparison, we follow the guidance from Tang et al. (2023) to select parameters for the DP few-shot generation algorithm. Specifically, K is held constant at 100, and a grid search is performed to determine the optimal values for M and N (N ∈ {1, 2, 4}, M N ∈ {20, 40, 80}). We also use the same values of T max as in Tang et al. (2023) for each task. Hyperparameters for the DP few-shot generation algorithm presented in Table 1 are provided in Table 12. We then use the same values of M , N , T max and K for our AdaDPSyn without any additional hyperparameter tuning.

Hyperparameters and privacy parameters for the results presented in Table 2 are provided in Table 13-Table 17.

Table 12: Hyperparameters for DP few-shot generation (Tang et al., 2023) presented in Table 1 and Table 2. We choose n shot = 4 and K = 100 for all tasks.

Task M N T max DP AGNews 10 2 100 Gaussian DBPedia 10 2 100 Gaussian TREC 20 2 15 Gaussian MIT-G 40 1 20 Gaussian MIT-D 40 1 20 Gaussian

Table 13: Hyperparameters and privacy parameters for the main results of AGNews task presented in Table 2. We choose M = 10, N = 2, T max = 100, n shot = 4 and K = 100.

Table 14: Hyperparameters and privacy parameters for the main results of DBPedia task presented in Table 2. We choose M = 10, N = 2, T max = 100, n shot = 4 and K = 100. 10 3 1.54 ε = 2 1 0.1 10 3 1.14 ε = 4 1 0.2 10 3 0.89 ε = 8 1 0.2 10 3 0.73 Table 15: Hyperparameters and privacy parameters for the main results of TREC task presented in Table 2. We choose M = 20, N = 2, T max = 15, n shot = 4 and K = 100.

Table 16: Hyperparameters and privacy parameters for the main results of MIT-G task presented in Table 2. We choose M = 40, N = 1, T max = 20, n shot = 4 and K = 100.

3 15 6 1.59 ε = 2 1 0.35 10 6 1.17 ε = 4 2 0.25 10 6 1.12 ε = 8 2 0.2 10 5 0.90

Table 17: Hyperparameters and privacy parameters for the main results of MIT-D task presented in Table 2. We choose M = 40, N = 1, T max = 20, n shot = 4 and K = 100.

15 17.5 6 2.57 ε = 2 1 0.15 17.5 6 1.49 ε = 4 1 0.3 15 6 1.07 ε = 8 1 0.15 15 5 0.83 C.6 EMPIRICAL PRIVACY EVALUATION BY MEMBERSHIP INFERENCE ATTACK

While DP guarantee inherently provides a theoretical guarantee against privacy leakage, it is also important to assess empirical privacy risks. In this section, we evaluate the empirical privacy of AdaDPSyn against membership inference attack (MIA) (Shokri et al., 2017).

We follow the prior work (Duan et al., 2023), where the authors instantiate a membership inference attack (MIA) in the ICL framework. The goal is to determine whether a given private example was used within the prompt. Following Duan et al. (2023), we consider 1-shot ICL. We use the DBPedia dataset and apply the MIA for our AdaDPSyn algorithm. Specifically, we split the dataset into two parts for member and non-member samples. We use member samples to generate 1-shot synthetic demonstration with AdaDPSyn, repeated over 5 trials. Then we attempt MIA for the samples from members and non-members during ICL. For each synthetic demonstration, we run 20 trials for MIA and average across the 100 trials to calculate the AUC. Following Duan et al. (2023), we also consider a non-private baseline ε = ∞ of using actual samples from the private dataset in the prompt. For this baseline, we also average across 100 trials for AUC. The results are presented in Table 18.

We observe that using actual samples from the private dataset leads to successful MIA results (77.37 in the ε = ∞ case). AdaDPSyn reduces MIA AUC to almost random guesses, showing the effectiveness of our method against MIAs.

MIT-G

Given a genre for the film, generate a description accordingly and make sure to include the given genre in the description.

Genre: holiday

Sentence: what is the name of this perennial holiday favorite featuring an elderly miser learning the error of his ways thanks to three ghostly visitations Genre: action Sentence:

MIT-D Given a director for the film, generate a description accordingly and make sure to include the given director in the description.

Director: pixar

Sentence: what pixar animated film features a talking dog named dug Director: disney Sentence:

or "basketball" instead of "sports"), highlighted in red in Table 30. Despite these substitutions, the DP samples maintain semantic relevance to the task. However, compared to the private samples, the DP samples are more general and less detailed, sometimes introducing noise or repetition. These differences reflect the trade-offs for ensuring DP. With different ε values (ε = 1, 2, 4, 8), we do not observe significant differences in the quality of the DP samples. This aligns with our experimental results, where the ICL accuracy shows only small differences across ε = 1, 2, 4, 8 (between 37.41% and 38.31%).

We also conduct experiments with smaller ε (0.2, 0.3, 0.5) on the MIT-G dataset. The DP samples generated using AdaDPSyn with these ε values are included in Table 30, and we present the performance results in Table 31.

For ε = 1, 2, 4, 8, the ICL performance shows only small differences (between 37.41% and 38.31%).

However, when ε decreases to 0.5, ICL accuracy drops to 30.56%, and further decreases to 23.75% for ε = 0.3. At ε = 0.2, the ICL accuracy is 13.77%, which is nearly identical to the fully private baseline (ε = 0).

In Table 30, we observe that, for ε = 1, 2, 4, 8, the DP samples maintain similar quality, with labels (movie genres) included in the text most of the time. At ε = 0.5, quality decreases with occasional noise, and labels are included less frequently. At ε = 0.3, labels are only occasionally included, and at ε = 0.2, labels are entirely absent, with the samples containing more noise. (October 30, 1735-July 4, 1826) was an American statesman and Founding Father who served as the first Vice President (1789-1797) and second President of the United States (1797-1801). He was a leader of American independence in 1776, and served as the first American minister to the new nation of France from 1

Politician

The house was designed by architect Frank Lloyd Wright and built in 1952 for Edgar J. and Liliane Kaufmann in the community of Mill Run Pennsylvania. The home, which sits on the side of a hill overlooking Bear Run in the Laurel Highlands region of southwestern Pennsylvania, is made of reinforced concrete and features a 150-foot (46 m) long cantilevered section, which was the longest cantilever of Building Vegetable oils are triglycerides extracted from plants. a broad term for fats and oils, including sesame oil, coconut oil, palm oil, and soybean oil. They are liquid at room temperature, and, unlike animal fats, they do not solidify in the refrigerator. Vegetable oils are liquids at room temperature, and, unlike animal fats, they do not solidify in the refrigerator The foundation [imgref tag2 doc], pausing through these great lengths of limestone led more men to gather still! Upon the structure like leakers floord celephaiden stepped between four. Many words it means i d been taken not and some a place inside when only is was something strange within she kept there or only into many time his would fall would reach those upon at you what as him back will help your at their no how may with just did upon which where out these Building [Name of a plant] is tall with a trunk diameter of up to 30 inches, a canopy diameter of up to 50 feet. The plant grows up to 20 m (66 ft) and is a perennial, deciduous plant. It grows well in a range of climates from the temperate zones in eastern and western North America. It can tolerate drought. The tree can live 300 years. It grows Plant Olympic compettessor are : Milt Stahmetze the topmost score were was -DUHSHA the Olympics score on him , i and even all , other men for was + is me score will like one at each he my other as two have no do can what it ACT on have ever, two time been him when first last with has what three year no how then you , this they I i this . were + but she -their other can how time a Athlete 6 politcian found (6. The text for your candidate(economiser and conserv) could 4) in that. So vote and economical! If this article. But i <0xE2> like them as good in parliament too so do what yi have (you could get better one(and then he. Is so many candidates you might also try other type, which are as politica in <span: The only two candidate with name politci <8, <x6C

Politician

Buildings make up the most amount of energy use in buildings and account for more than 40% of energy used for commercial, public and institutional uses, and nearly 12% are used to power the homes in which we live. Buildings also contribute 30 to 40% of greenhouse gas emissions and consume a lot of materials such as concrete, steel, plastic, aluminum, wood, and copper. Buildings use energy and materials, Building Lumo, Lumo is an adherent plant with thin stems, oval leaves and yellow flowers. As the leaves turn red they are eaten by squirrels, and this stimulates the plant to produce flowers. Lumo is an endemic of South and North-Eastern Kenya. Lumo is used to treat stomach ulcers in Kenya. The flowers are eaten to reduce blood pressure. It is also used to so Plant 7. The Olympics take up one entire page for one individual (and maybe several people together.) For that event we get more people from our audience'. They don&r'ts; come. This would lead more visitors coming over time which makes money (proft for a magazine.). But what will also work with your document and you could see what I wrote on the next section to learn to see and feel like they could help people, to find your information for that one particular subject of Athlete Internal (Ind vsOuti . . . .. and evopt): For public speaker whose presentation need it by [<fruit flavid = indemonde..r1 <foontime aet4 tusal ] then try .. dts are useful things especially things were fntions gop on at its location bocre than (co/ceofonon rtrttirit...'teefft') by public oers can know <info 2 Politician House [the ] Linden Farm Maitree in Vicks Fakauala Kibila Township; where land records keep register or give documentation cert with witness according at Police'2[...snidifoo bend](-Kotwela): Mr Prilminary officer by OD at ISA G1& TPS Mr Sauman Saulu APC : Deputial Suphanahanepoa from his P1 or original I can witness(this man with p Building One has given ten the key whereinto these caster [chaps may eat any three food any nine parts must hold]. Also be noted down into nin or for eleven will return not twenty may turn fifteen when 8 not go more any any into turn go twelve this up some back many so thrite if I said more as into but or< a in which have at you must eat 0 I shall it with seven from down with at be < i eat [have into Plant C-sharp expert Tuan Lee brings professional perspective to Azure architecture. Mr. Lee had originally only viewed using PaaS as a place to rent/ buy Windows , server administration ... read more or manage Linux Web developers prefer web to have, server expert may instead for having something (if don't server available; do or as their for data are managing some files more use databases will them they think not all documents server more... For can access control manage only then should people these Athlete

Table 29: Real private samples from MIT-G. what is the animated family movie about a man who has to look after three orphaned girls (animated family) name the sports movie about a high school basketball team that starred gene hackman as the coach (sports) in which animated movie did steve carell play a thief who is trying to steal the moon (animated) what 1956 science fiction film concerns aliens in a small california town who inhabit citizens bodies (science fiction) what 2007 biopic is about the story of jean dominique bauby and his trouble with locked in syndrome (biopic) in a decrepit south american village men are hired to transport an urgent nitroglycerine shipment without the equipment that would make it safe is the plot of this 1953 action thriller (action thriller) young traveler allan gray discovers evidence of the supernatural in this black and white 1932 horror film (horror) this computer animated film stars johnny depp as a timid chameleon who finds courage in the desert (computer animated) what was the name of the cg movie with johnny depp as a lizard in the desert (cg) name the 1990 american romantic fantasy film starring patrick swayze demi moore tony goldwyn and whoopi goldberg (american romantic fantasy) what 2002 brazilian movie had a television show spin off called city of men in 2003 (brazilian) do you know the name of the comedy film starring an actor named michael that s based off of a video game (comedy) what is the 1989 comedy drama crime film starring tom hanks and beasley the dog (comedy drama crime) a classic childrens tale of a bear who enjoys his honey and his animal friends (childrens) superhero movie where team of superheros get together to defeat threats too big for just one hero (superhero movie) what is the superhero movie about a powerful but arrogant warrior who is cast out of asgard (superhero) tim burton used stop motion animation to tell the story of jack skellington in what 1993 disney movie (stop motion animation) what s the animated film made up of several stories which are set to classical music (animated) this movie musical features two rival gangs the sharks and the jets and lots of prancing and snapping and wailing for maria (musical) what is the 1992 american horror film starring tony todd as the titular character who has a hook for a hand (american horror) this one of the first classic horror movies thats been remade multiple times about zombies (classic horror)