Data-adaptive Differentially Private Prompt Synthesis for In-Context Learning

We thank the reviewer for the careful reading and thoughtful comments. We address the reviewer's questions in the following and have revised the paper accordingly. The changes are marked in blue in our revision. We hope the responses below address the reviewer's concerns.

Q1: An amount of $M$ queries needs to be made for synthesizing one DP in-context sample. This is of high computation cost. I would like to see some of the computational cost analysis, including the time cost comparison with baselines used in the paper.

A1: Thank you for the insightful comment. Both our AdaDPSyn and DP few-shot generation (Tang et al., 2023) require $M$ queries during the synthesis process. The value of $M$ in our experiments is typically small (e.g., 10), which keeps the computational cost manageable. Additionally, the rapid advancements in LLM inference acceleration [1,2,3] suggest that querying LLMs may involve much lower time costs in the near future.

We appreciate the reviewer’s suggestion for a time cost comparison. We present the time cost for generating one DP synthetic ICL sample with $\varepsilon=4$ in the table below.

We observe that the time cost of AdaDPSyn is very close to that of DP few-shot generation (Tang et al., 2023). Although AdaDPSyn includes additional steps that contribute to improved ICL accuracy, they do not introduce significant computational overhead.

We have included this discussion in the updated draft (Appendix C.10). Thank you for highlighting this important point.

[1] Cai, Tianle, et al. "Medusa: Simple LLM Inference Acceleration Framework with Multiple Decoding Heads." Forty-first International Conference on Machine Learning.

[2] Zhao, Yao, et al. "Lookahead: An inference acceleration framework for large language model with lossless generation accuracy." Proceedings of the 30th ACM SIGKDD Conference on Knowledge Discovery and Data Mining. 2024.

[3] Li, Jinhao, et al. "Large Language Model Inference Acceleration: A Comprehensive Hardware Perspective." arXiv preprint arXiv:2410.04466 (2024).

Q2: The comparison of generated DP samples and real private samples are not adequate. Only DP samples of $\varepsilon=4$ is shown without direct comparison with private samples. Results of epsilon of other values as well their comparison with private samples should be included.

A2: Thank you for highlighting the importance of a comparison between the generated DP samples and real private samples. We have addressed this in the updated draft (Appendix C.13). Specifically, we use the MIT-G dataset for this analysis because this task shows a relatively large performance gap between private and non-private methods. We present the private samples in Table 29, and the DP samples generated using AdaDPSyn with $\varepsilon=1,2,4,8$ in Table 30. We state our main observations in the following.

In the original private samples, the labels (movie genres) are explicitly included in the text, as the task is to extract the genre from the text. Similarly, in the DP samples generated by AdaDPSyn, the labels are included most of the time. Occasionally, the generated samples use related words instead of the exact label (e.g., "boxer" instead of "boxing" or "basketball" instead of "sports"). 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 $\varepsilon$ values ($\varepsilon =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 $\varepsilon=1,2,4,8$ (between $37.41\\%$ and $38.31\\%$).

Q3: I am wondering, since the goal of this paper is "to mitigate the risk of LLMs potentially leaking private information contained in examples in the prompt", if an example is used as in-context learning samples and sent to the LLMs, why should its privacy issue be considered? The sender party already knows the sample, and the LLM sees the sample. So who should be stopped from seeing the sample?

A3: Thank you for the question. We clarify that our framework involves two LLMs: a trusted LLM and an untrusted LLM. In stage 1, we use AdaDPSyn with a trusted LLM, such as an open-source model, to generate DP synthetic ICL examples. In stage 2, we use these examples to prompt an untrusted LLM for ICL. We should stop the untrusted LLM from seeing the private data samples.

We thank the reviewer for the careful reading and thoughtful comments. We address the reviewer's questions in the following and have revised the paper accordingly. The changes are marked in blue in our revision. We hope the responses below address the reviewer's concerns.

Q1: Although the data-adaptive technique is novel, the work relies heavily on the framework introduced by Tang et al., 2023. Seemingly, author’s overall contribution is only a modification on top of an existing DP generation framework by adding a data-adaptive technique to the private aggregation step.

A1: Thank you for recognizing the novelty of our data-adaptive technique. While our work builds on the framework in Tang et al. (2023), it makes a substantial contribution by addressing a critical problem in generating DP synthetic ICL examples: Optimizing the privacy-utility trade-off by leveraging the statistical properties of the data. Specifically, we observe that next-token generation probability vectors often cluster tightly within a small ball, motivating a more effective prompt synthesis algorithm. We would like to clarify that our method is not a minor modification but involves multiple carefully designed steps, including establishing the target radius using GoodRadius, private projected mean estimation, private radius coverage check, and iterative radius updates. These components collectively enable a novel data-adaptive prompt synthesis method that significantly improves ICL performance. Our experimental results show clear improvements over Tang et al. (2023) and closely approach the performance of non-private ICL baselines. Besides, we believe that such data-adaptive technique may be applicable in various problems beyond prompt synthesis, thus is of independent interest. We clarify this point in the revised version as well.

Q2: Their method introduces 4 more parameters, $\hat{T}, \lambda, \sigma_0, \sigma_2$, than Tang et al., 2023, which requires additional hyperparameter tuning on other datasets. Furthermore, the authors do not provide ablation studies on $\sigma_0, \sigma_2$ which makes it difficult to interpret their effect on the privacy-utility tradeoff.

A2: Thank you for the insightful comment. We address the reviewer’s concern about parameters as follows:

1. Hyperparameters $\lambda$ and $\hat{T}$: We conduct a hyperparameter search for $\lambda$ and $\hat{T}$ across all studied datasets in Appendix C.4. Specifically, we consider $\hat{T}\in\\{1, 2\\}$ and $\lambda\in\\{0.15, 0.2, 0.25\\}$, and present ICL accuracy for all these hyperparameter values on each dataset when $\varepsilon = 8$. Our results show that ICL accuracy remains stable across different hyperparameter settings. For example, on AGNews, AdaDPSyn achieves accuracy between $64.28\\%$ and $65.92\\%$, compared to $63.18\\%$ for DP few-shot generation. This stability shows that AdaDPSyn can generalize well to other datasets with minimal hyperparameter tuning.

2. Privacy parameters $\sigma_0$ and $\sigma_2$: These parameters control the allocation of the overall privacy budget, and their selection generalizes well across datasets based on consistent principles:

(1) $\sigma_0$ (noise multiplier of GoodRadius in Line 5): GoodRadius initializes a reference radius for the projected ball. Since it does not determine the final radius, it can tolerate higher noise. We typically set $\sigma_0$ to a large value (e.g., 10) to conserve privacy budget for the projected mean estimation step.

(2) $\sigma_2$ (noise multiplier of radius coverage check in Line 12): The radius coverage check verifies whether a sufficient number of the original probability vectors $p_\text{priv}^1,\ldots,p_\text{priv}^M$ lie within a small radius from $\tilde{p}_\text{priv}$. Specifically, this step counts the number of covered vectors, adds Gaussian noise with standard deviation $\sigma_2$, and compares the noisy count to the total number of vectors $M$. The choice of $\sigma_2$ depends on the value of $M$. When $M$ is large, the relative impact of the noise added to the count diminishes, allowing for larger $\sigma_2$.

We appreciate the reviewer’s suggestion to perform ablation studies on $\sigma_0$ and $\sigma_2$. To evaluate their impact, we conduct additional experiments on the MIT-G dataset with $\varepsilon=8$, varying $\sigma_0 \in \\{10, 15, 20\\}$ and $\sigma_2 \in \\{3, 4, 5\\}$. The results are presented in the table below.

We thank the reviewer for the careful reading and thoughtful comments. We address the reviewer's questions in the following. We hope the responses below address the reviewer's concerns.

Q1: Only one baseline was considered, specifically "DP few-shot generation".

A1: Thank you for the comment. Tang et al. (2023) represents the first work that generates synthetic few-shot demonstrations from a private dataset to perform ICL. We thoroughly compare our method to this baseline. In Section 2, we provide a literature review on Differentially Private ICL and find that they address different problems and cannot be compared with our algorithm, as listed below:

Duan et al. (2023): This work assumes the existence of an unlabeled public dataset, which contrasts with our approach that requires no public data.

Wu et al. (2023): This method consumes the privacy budget per query, limiting the number of queries that can be answered within a given budget. This makes it unsuitable for our focus on scenarios with an unlimited number of queries.

Hong et al. (2023): This work proposes methods to generate private and transferable instructions, while our focus is on generating synthetic ICL examples.

Carey et al. (2024): This study focuses on protecting tabular data used for ICL, while our focus is on text data.

Therefore, we have focused on a detailed comparison with the available baseline. We would appreciate it if the reviewer could point us to some potential baselines that we are unaware of.

Q2: If I am not mistaken, the iterative aspect is not utilized significantly, as $\hat{T}$ is frequently set to 1.

A2: Thank you for the insightful comment. You are correct that in many cases $\hat{T}$ is set to 1. This is because increasing $\hat{T}$ introduces more iterations of private radius coverage check and projected mean estimation, which increases the overall privacy cost. To balance utility and privacy, we primarily set $\hat{T}\in\\{1, 2\\}$ in our experiments.

That said, the iterative aspect is meaningful and can enhance performance in specific scenarios. For example, in Table 8 (TREC dataset, $\varepsilon=8$), the best result is achieved with $\hat{T}=2$. Similarly, in Table 9 (MIT-G dataset, $\varepsilon=8$), $\hat{T}=2$ also produces the best outcomes. These examples show that increasing $\hat{T}$ can improve performance when the privacy budget allows, highlighting the importance of the iterative approach in specific contexts. We appreciate the opportunity to clarify this aspect.

We thank the reviewer again for the helpful comments and suggestions for our work. If our response resolves your concerns to a satisfactory level, we kindly request the reviewer to consider raising the rating of our work. Certainly, we are more than happy to address any further questions that you may have.

We thank the reviewer for the careful reading and thoughtful comments. We address the reviewer's questions in the following and have revised the paper accordingly. The changes are marked in blue in our revision. We hope the responses below address the reviewer's concerns.

Q1: I think it'd be informative to investigate the trade-offs between directly DP fine-tuning and generating synthetic ICL samples with DP but I think that's beyond the scope of this paper.

A1: We thank the reviewer for the insightful comment on the trade-offs between direct DP fine-tuning and generating DP synthetic ICL samples. The choice between these approaches depends on several factors, such as the degree of access to the LLM, computational resources, and the nature of the downstream task. For example, direct DP fine-tuning may be infeasible when only API access to the LLM is available, as model weights are not accessible. Additionally, generating DP synthetic ICL samples offers a lightweight and efficient solution, reducing the heavy computational burden associated with fine-tuning. However, certain downstream tasks might benefit more from fine-tuning, as it allows for stronger adaptation to specific domains. We appreciate the opportunity to discuss this and will consider a deeper exploration of these trade-offs in future work.

Q2: Is there any good intuition on how to best divide the overall privacy budget across the privacy-consuming steps of Algorithm 1?

A2: Thank you for the question. We allocate the overall privacy budget across three key steps of Algorithm 1: (1) GoodRadius in Line 5 with noise multiplier $\sigma_0$, (2) projected mean estimation in Line 20 with noise multiplier $\sigma_1$, and (3) radius coverage check in Line 12 with noise multiplier $\sigma_2$. To ensure the required $(\varepsilon,\delta)$-DP guarantee, we first set $\sigma_0$ and $\sigma_2$, and then compute $\sigma_1$ accordingly. Generally speaking, we set $\sigma_0$ and $\sigma_2$ to be relatively large compared with $\sigma_1$, to allocate more privacy budget to the projected mean estimation step. Below, we provide intuition on how the privacy budget is allocated.

The GoodRadius step initializes a reference radius for the projected ball. Since it is not the final radius, this step can tolerate higher noise levels. Therefore, we typically set $\sigma_0$ to a large value (e.g., 10) to save privacy budget for the more sensitive projected mean estimation step.

The radius coverage check verifies whether a sufficient number of the original probability vectors $p_\text{priv}^1,\ldots,p_\text{priv}^M$ lie within a small radius from $\tilde{p}_\text{priv}$. This involves counting the number of covered vectors, adding Gaussian noise with standard deviation $\sigma_2$, and comparing the noisy count to the total number of vectors $M$. When $M$ is large, the relative impact of the noise added to the count diminishes because the noise becomes negligible compared to $M$. Therefore, as $M$ increases, we can set $\sigma_2$ to a larger value. For example, when $M=40$, $\sigma_2$ can be set to around 5 without significant loss of accuracy.

In conclusion, our privacy budget allocation prioritizes the projected mean estimation step for high accuracy, while allowing other steps to tolerate higher noise.

We thank the reviewer for the insightful comment and we have added this discussion to our updated draft (Lines 918–931).

We thank the reviewer again for the helpful comments for our work. We are more than happy to address any further questions that you may have.