Interpretation of numerical experimental results}

Reviewer comments (Claims And Evidence, Questions For Authors):

1. DBPedia has significantly higher performance without the proposed KL divergence, which is an essential part of the proposed PTA. There is no explanation for this.
2. Why does DBPedia have significantly higher performance without the proposed KL divergence?

Thank you for pointing this out. We agree that the performance degradation on DBPedia when using KL divergence requires clarification.

As shown in Equation (11), PTA is fundamentally designed to amplify tokens distinctive to the ground-truth concept. The KL divergence term is introduced as an auxiliary regularizer to ensure that the modified token distribution does not deviate excessively from the original LLM next-token probability distribution. While not the core objective, this regularization can help stabilize training and preserve plausibility, contributing to improved performance on datasets such as AGNews and GINC.

However, as with many regularization techniques, the KL term does not consistently improve accuracy. In some cases, it may act as a constraint that limits useful adaptation to the target distribution. We suspect this effect may be present in DBPedia, though further analysis would be needed to pinpoint the exact cause.

We will add this clarification in the revised version.

Lacking baseline methods

Reviewer comments (Claims And Evidence, Questions For Authors):

1. [...] Not sure if there could be more baselines to compare.
2. [...] Are there any other DP-ICL baselines that you can compare PTA with?

We agree with these comments. A similar suggestion was also raised by another reviewer (DiNj). In response, we conducted additional experiments during the rebuttal period using DP-OPT (Hong et al., ICLR 2024), which is conceptually similar to our approach in that it generates differentially private prompts once and reuses them for evaluating test queries.

For a detailed discussion, please see our response to Reviewer DiNj under “Missing comparison with related works.” We will include the new experimental results and their interpretation in the revised version of the paper.

(Hong et al., ICLR 2024) DP-OPT: Make large language model your privacy-preserving prompt engineer.

Effect of approximation in Equation. (12)

Reviewer comments (Claims And Evidence, Theoretical evidence):

1. The claim in Equation (12) is pretty hand-waving without any analysis of the closeness of the approximation. [...]
2. Can you provide some analysis on Equation (12) and the effect of having this approximation?

This is a good question. As you noted, PTA is based on the following approximation in Equation~(12):

$$\log \frac{p(o = v \mid \theta^*)}{p(o = v \mid \theta)} \approx \log \frac{p(o = v \mid S_{\text{priv}}^{(i)})}{p(o = v \mid S_{\text{pub}})}. \hspace{10pt} (12)$$

We approximate the LHS of Equation (12) since it is intractable to compute directly. This intractability arises from the fact that $\theta$ and $\theta^*$ are not directly observable as they are latent variables, making it impossible to evaluate the likelihoods $p(o = v \mid \theta^*)$ and $p(o = v \mid \theta)$ explicitly. To address this, we approximate the LHS using the LLM’s next-token probability distribution conditioned by observable prompts, which are designed to reflect their corresponding latent concepts.

To explain how we approximate, we decompose the LHS of Equation (12) as follows:

$$\log \frac{p(o = v \mid \theta^*)}{p(o = v \mid \theta)} = \log \frac{p(o = v \mid \theta^*)}{p(o = v \mid S_{\text{pub}})} + \log \frac{p(o = v \mid S_{\text{pub}})}{p(o = v \mid \theta)}.$$

First, the first term on the RHS is then approximated by $\log \frac{p(o = v \mid S_{\text{priv}}^{(i)})}{p(o = v \mid S_{\text{pub}})}$, replacing the intractable $p(o = v \mid \theta^*)$ with a quantity that can be computed using the LLM prompted by the private prompt $S_{\text{priv}}^{(i)}$. As detailed in Section 4.1, this is justified by the Bayesian interpretation of in-context learning from Xie et al., where such prompting induces a posterior concentrated around $\theta^*$.

Second, we omit the second term in RHS to focus on amplifying tokens distinctive to $\theta^*$, without explicitly penalizing competing concepts. This omission is plausible when the second term is small. This occurs when different concepts assign high probability to distinct sets of tokens. In such cases, tokens indicative of $\theta^*$ are also unlikely under both $\theta$ and the reference $p(o = v \mid S_{\text{pub}})$, making the omitted term negligible. To support this in practice, we construct $S_{\text{pub}}$ using instruction-only prompts that avoid concept-specific content. This yields a neutral reference distribution and helps maintain separation across concept token distributions.

We will revise the paper to clarify this approximation strategy.

Unclear definition of "concept"

Reviewer comment (Other Strengths And Weaknesses, Weakness):

1. The term "concept" in the introduction needs clearer demonstration. It can improve the readability of the introduction.

Thank you for pointing this out we had not noticed this readability issue. In our context, a concept refers to the latent rule or semantic mapping that connects inputs to outputs in demonstrations. This underlying concept governs the token transitions in the demonstrations and is implicitly inferred by the language model during In-Context Learning (ICL).

In the revised version, we carefully clarify and introduce the term “concept” in Section. 1.

Missing comparison with related works

Reviewer comment (Other Strengths And Weaknesses, Weakness):

1. Missing empirical comparison with: (1) Wu et al. (ICLR 2024) and (2) Hong et al. (ICLR 2024).

Thank you for pointing out these relevant works.

(1) Wu et al. (ICLR 2024)

While their method is indeed related, it directly adds noise to the next-token probability distribution at test time for each classification query. As a result, the noise variance must scale with the number of test queries to ensure a fixed $(\varepsilon,\delta)$-DP. In contrast, the noise variance in our method (and Tang et al.'s) remains fixed—regardless of the number of queries thanks to the post-processing property of DP: once a prompt satisfying $(\varepsilon,\delta)$-DP is generated. This fundamental difference in design makes direct comparison challenging, thus we did not include their method in our evaluation.

(2) Hong et al. (ICLR 2024)

We agree that DP-OPT, proposed by Hong et al., is conceptually similar to our approach, as it generates differentially private prompts once and reuses them to evaluate test queries. During the rebuttal period, we conducted an additional empirical comparison using the same Vicuna-7B-v1.5 model and TREC dataset setup as used in their study. The comparison results are summarized in the table below.

To ensure fair comparison, we report both our replicated results and the original values for DP-OPT from Table 3 of their paper, formatted as (replicated / original). This is because our replication was limited by computational constraints and a limited understanding of DP-OPT’s hyperparameters. We followed their appendix settings for $\varepsilon=8$ and extended them to $\varepsilon=1$ using $\epsilon_0 = 0.1$ from their Table 5. Additionally, differences in prompt format remain. Therefore, this comparison may not fully reflect the method’s optimal performance.

We present below our interpretation of the experimental results:

• Even under the same evaluation setup, both our proposed PTA and Tang et al.'s DP-ICL acheieve high accuracy. This confirms the competetive performance of PTA compared to a strong DP-ICL baseline.

To further support the numerical results, we highlight a key behavioral differences between DP-OPT and our approach at $\varepsilon=1$.

• As discussed in Section 5.2 of their paper, DP-OPT tends to output only the instruction without demonstrations as the private prompt satisfying $(\varepsilon,\delta)$-DP guarantee with $\varepsilon=1$. In such cases, the method method asymptotically converges to zero-shot prompting, limiting the practical utility of private demonstrations.

• In contrast, our method generates in-context demonstrations that, while potentially noisy, remain informative beyond the instruction even with $\varepsilon=1$. This may allow our approach to consistently outperform zero-shot prompting, especially in high-privacy regimes where DP-OPT yields only marginal gains.

We will include these numerical results and their interpretation in the revised paper.

Performance investigation using GPT4-o

Reviewer comment (Other Strengths And Weaknesses, Weakness):

1. [...] How will the PTA perform on modern LLMs such as GPT4?

We believe that applying our method (as well as that of Tang et al.) to models such as GPT-4 accessed via the OpenAI API poses challenges from a privacy evaluation perspective. At this moment, the API does not provide access to the full token probability distribution, instead returning only a limited set of top tokens. Since the selection of these tokens depends on the full (unobservable) distribution, it may lead to unintended privacy leakage. Moreover, as this selection process is a black box, it is practically infeasible to assess its differential privacy guarantees. Given the current API constraints, we consider rigorous privacy evaluation using GPT-4 constraints to be challenging at this time.

Concerns in bounding constants

Reviewer comments (Claims And Evidence, Theoretical evidence)

1. [...] introduce a whole pile of constants [...], so the C_delim "constant" [...] hides a bunch of things which are very far from constant, [...]. Similarly, G is also dependent on the LLMs involved.
2. [...] non-constant natural of C_delim and G really do need to be called out in the main text. [...]

This is a good question. We address $G(\sigma)$ and $C_{delim}$, separately.

First, $G(\sigma)$ is a function, not a constant, as defined in Line 1339 (Appendix C.7), though this was not clearly stated in the main text. We did not intend to hide this point, thus we will include its definition and clarify its dependency on the LLM's next-token probability distribution in the revised paper. Notably, introducing the bound $G(\sigma)$ in Line 1339 is essential for a tight analysis of the noise error in Theorem 2. Under general settings without assuming any specific form of the LLM's next-token probability distribution, a tight analysis using $G(\sigma)$ in Line 1339 is established thanks to Bretagnolle–Huber bound (Lemma. 4, Appendix C.3).

Next, we clarify that the term $C_{delim}$, which is defined in Line 1009, is also a function, not a constant. It originated from the formulation in Xie et al. (ICLR 2022) and depends on the ground-truth concept $\theta^*$ and the other concept $\theta$. We will also clarify this dependency in the revised paper.

Refinement of Theorem

Reviewer comments (Claims And Evidence, Theoretical evidence):

1. [...] cleaner theorems hiding under the surface the theorems [...]. Theorem 2 has a term involving the vocabulary size, [...] this is artificial in order to present direct evidence for the success of Tang's method.
2. [...] If the prompts are sampled sufficiently closely to the public distribution [...], we should be able to get a bound that doesn't depend on the vocabulary size. [...]

Thank you for the insightful comment. We agree more elegant theorems may arise under additional assumptions—e.g., when prompts are sampled closely from a public distribution and this is a promising direction for future work.

However, Theorem 2 is designed to hold under general settings without assuming a specific form of next-token probability distribution. In practice, prompts often contain private demonstrations that may diverge from public distributions, making such assumptions unreliable.

To address your concern, we clarify why the $\log |V|$ term appears in Theorem 2. Our analysis (Section 3) examines how the noise impacts latent concept inference in DP-ICL. Since next-token probability distributions of LLMs can vary widely, especially with private prompts, we aim to derive a general bound that holds without assuming any specific form of the distribution. Applying Csiszár’s inequality (Lemma 3, Appendix C.3) naturally introduces the $\log |V|$ term as a bound on the maximum distributional shift. Further, as discussed in the former section (Concerns ...), $G(\sigma)$ also results from a tight analysis. Together, $G(\sigma)\log |V|$ forms a general upper bound on noise impact.

We will clarify this motivation in the revised version.

Refinement of empirical method}

Reviewer comments (Claims And Evidence, Empirical evidence, Other Strengths And Weaknesses):

1. [...] there is a simpler, better method available if one more naturally combines the two features, vocabulary restriction and PTA.
2. [...] by merging vocabulary restriction natively into some metric comparing public and private distributions.

This is an insightful point. We acknowledge that metrics comparing public and private distributions can directly inform vocabulary restriction.

Our goal, however, was to theoretically support Tang et al.’s empirical vocabulary restriction and refine it through PTA. Building on Theorem 2, we adopted a modular design to isolate each component’s role: vocabulary restriction narrows the output space, to reduce the noise impact, while PTA amplify token probabilities to increase divergence between the ground-truth and other concepts.

We appreciate the suggestion and see it as a promising future direction.

Empirical evaluation

Reviewer comment (Claims And Evidence, Empirical evidence):

1. [...] to see a graph showing the degradation in accuracy as the privacy budget is tightened [...]

Due to space constraints, we showed results for $\varepsilon=1$ and $8$ in the main paper. We agree broader coverage is important.

Table 8 (Appendix F.4) includes results for $\varepsilon=1,2,4,8,\infty$ (following Tang et al., ICLR 2024), giving a clearer tren of how accuracy changes as privacy strengthens. Below is a summary for PTA on GINC:

We will include accuracy curves in the revision to better illustrate this trend.