Adaptively Private Next-Token Prediction of Large Language Models

## Abstract

Abstract As Large Language Models (LLMs) proliferate, developing privacy safeguards for these models is crucial. One popular safeguard involves training LLMs in a differentially private manner. However, such solutions are shown to be computationally expensive and detrimental to the utility of these models. Since LLMs are deployed on the cloud and thus only accessible via an API, a Machine Learning as a Service (MLaaS) provider can protect its downstream data by privatizing the predictions during the decoding process. However, the practicality of such solutions still largely lags behind DP training methods. One recent promising approach, Private Mixing of Ensemble Distributions (PMixED) Flemings et al. ( 2024 ) , avoids additive noise by sampling from the output distributions of private LLMs mixed with the output distribution of a public model. Yet, PMixED must satisfy a fixed privacy level for a given number of queries, which is difficult for an analyst to estimate before inference and, hence, does not scale. To this end, we relax the requirements to a more practical setting by introducing Adaptive PMixED ( AdaPMixED ), a private decoding framework based on PMixED that is adaptive to the private and public output distributions evaluated on a given input query. In this setting, we introduce a noisy screening mechanism that filters out queries with potentially expensive privacy loss, and a data-dependent analysis that exploits the divergence of the private and public output distributions in its privacy loss calculation. Our experimental evaluations demonstrate that our mechanism and analysis can reduce the privacy loss by 16 × 16\times 16 × while preserving the utility over the original PMixED. Furthermore, performing 100K predictions with AdaPMixED still achieves strong utility and a reasonable data-dependent privacy loss of ϵ = 5.25 italic-ϵ 5.25 \epsilon=5.25 italic_ϵ = 5.25 .

## 1 Introduction

Large Language Models (LLMs) have accomplished huge commercial success due to their ability to memorize factual knowledge within their model parameters Petroni et al. (); Roberts et al. (). However, this memorization poses a serious privacy leakage vulnerability as LLMs are susceptible to training data extraction attacks on memorized text Carlini et al. (; ; ). The widely adopted approach to reduce memorization is to guarantee Differential Privacy (DP) Dwork (), a mathematical privacy notion, during the training of an LLM by applying strategic noise to per-sample gradients, called DP-SGD Abadi et al. (). Recent works have demonstrated that public pre-training followed by private fine-tuning substantially boosts the performance of DP LLMs Li et al. (); Yu et al. (); Li et al. (); Ganesh et al. (). But the potentially large additive noise by DP-SGD, which scales proportionally to the total number of parameters of an LLM Kamath (), and the underutilization of ML accelerated hardware due to per-sample gradient calculations Yousefpour et al. (), have delayed wide-scale adoption of DP-SGD to LLMs.

Perhaps the biggest discrepancy between DP-SGD and commercial deployments of LLMs is that many Machine Learning as a Service (MLaaS) providers only provide API access to their LLMs, e.g. OpenAI’s Chat-GPT. However, DP-SGD assumes an adversary has access to the gradients of an LLM at every iteration of training. This discrepancy leads to an overestimated privacy loss bounds Nasr et al. () when considering an adversary with only black-box access to the model. Alternatively, DP prediction methods Dwork & Feldman () offer potential improvement in model utility by explicitly exploiting this relaxation; however, in practice, DP prediction does not necessarily lead to higher utility than DP-SGD van der Maaten & Hannun ().

Figure: Figure 1: A brief overview of AdaPMixED. For each query x received by a user, noisy screening is performed by first mixing each private distribution $p_{i}(\mathbf{x})$ with the public distribution $p_{0}(\mathbf{x})$. Then the mixed distribution is privatized with Gaussian noise and is compared with the public distribution $p_{0}(\mathbf{x})$. If the screening fails, then the next token is sampled from the public distribution $y\sim p_{0}(\mathbf{x})$. Otherwise, private decoding is performed using PMixED. Our privacy analysis tracks the privacy loss $\epsilon(D)$ by analyzing the change of the output distribution when removing one model $p_{-i}(\mathbf{x})$ from decoding with PMixED for every query.
Refer to caption: extracted/5897077/figures/pmixed_screen.png

A recent promising DP prediction algorithm, called Private Mixing of Ensemble Distributions (PMixED) Flemings et al. () is able to achieve higher utility than DP-SGD for certain query budgets by exploiting two crucial features: (1) There is an inherent privacy when generating the next token by sampling from the output probability distribution of a language model; (2) The privacy loss of a prediction can be bounded by employing a public model to mix the output distributions of privacy-sensitive LLMs. These observations allow PMixED to avoid additive noise and thus preserve model utility Flemings et al. (). However, the DP Prediction definition Dwork & Feldman () that PMixED operates under is too rigid, as one must estimate a pre-specified privacy budget that will be satisfied for a certain number of predictions before querying an LLM, which is difficult. Moreover, this rigid requirement is satisfied by analyzing the privacy loss for each prediction without consideration for the output distributions of the private and public models, often leading to overly pessimistic privacy loss when the actual privacy loss is substantially smaller. Thus, PMixED, in practice, exhausts its privacy budget quickly and does not scale well to current generative applications.

In this work, we address the aforementioned limitations by introducing Adaptive PMixED (AdaPMixED), which makes the following contributions: (1) We provide a tighter privacy analysis of PMixED by leveraging the output distributions from auto-regressive LLMs to directly calculate the privacy loss. (2) We adopt a noisy screening mechanism only found in discriminative tasks Papernot et al. (); Zhu et al. () to the language modeling setting, by using the Renyi Divergence to measure the distributional difference between projected and public distributions then filter out queries with large divergence. (3) We present a privacy and utility analysis of PMixED and experimentally demonstrate improved privacy-utility tradeoff over PMixED. In particular, on the WikiText-103 dataset for a given number of queries, AdaPMixED can improve the utility by 1.4 perplexity over PMixED with $16$ times less privacy loss. Furthermore, we demonstrate our method can practically scale to large number of queries, achieving a privacy loss of $\epsilon=5.248$ for almost 100,000 predictions, while improving the utility over DP-SGD at a privacy level of $\epsilon=8$ by nearly $2.5$ perplexity. This is the first work to demonstrate that a DP prediction-based scheme can be practical for such extremely large queries, as prior work has evaluated on only at most 1k queries Flemings et al. (); Ginart et al. (); Zhu et al. (). We hope these promising results will spark further improvement in private decoding for real-world deployment of large-scale applications.

## 2 Related Works

Most of the progress in the differential privacy and LLM space has focused primarily on differentially private fine-tuning McMahan et al. (); Yu et al. (); Li et al. (); Flemings & Annavaram (). In many of these works, a pre-trained model trained on public data is further fine-tuned on a private downstream dataset $D$ using DP-SGD. The resulting model parameters are differentially private with respect to $D$. Private prediction methods Dwork & Feldman () offer an alternative way to guarantee DP for LLMs, during predictions rather than training. Although some progress has been made in DP prediction methods for discriminative tasks Zhu et al. (; ), most DP prediction methods for generative LLMs produce substantial utility degradation Majmudar et al. (). Another body of work also explored DP prediction of LLMs without fine-tuning of private data Tang et al. (); Duan et al. (); Xie et al. (); Wu et al. (). In these works, generated prompts containing private information are used by an LLM via an API call. Our work differs from these in that we utilize LLMs fine-tuned on private data to generate DP predictions.

Our work relies on the PMixED framework Flemings et al. (), however, we pointed out compelling shortcomings of PMixED that limit its practicality in real-world applications. Another conceptually similar, but orthogonal approach, to PMixED is PATE Papernot et al. (; ), which also uses an ensemble of models trained on pairwise disjoint subsets of a private dataset to generate DP labels. However, PATE uses the Gaussian/Laplacian mechanism to perturb vote count histograms while PMixED relies on sampling and mixing private and public output distributions. Consequently, adopting PATE to the language modeling setting produces suboptimal results, since perturbing the aggregated output distribution of the teachers incurs large noise due to its large dimensionality Ginart et al. (). The output space can be truncated, as done in Tian et al. (), but this can cause an error in the perplexity calculation. Instead, truncated decoding schemes must use generation perplexity Fan et al. (); Holtzman et al. (); Pillutla et al. (), which does not apply in our experimental setup.

Although the high level goal of our noisy screening mechanism and data-dependent analysis is motivated by PATE Papernot et al. (), our approach to both differs significantly from PATE. PATE’s noisy screening checks if the noisy max meets a threshold, whereas we use Renyi Divergence to measure the distributional difference between projected and public distributions to guide the screening process. This use of Renyi Divergence for screening is a novel aspect of our work, as no prior work has done this. Moreover, our data-dependent analysis iteratively examines neighboring ensembles to find the largest privacy loss, utilizing the probability distributions generated. On the other hand, PATE, designed for discriminative tasks, uses histograms to calculate class count differences as its data-dependent analysis. Our data-dependent analysis closely follows from Ginart et al. ().

## 3 Preliminaries

We start by reviewing some preliminaries on differential privacy, and then we will briefly discuss an overview of the PMixED framework. We will denote by $D=(d_{1},...,d_{n})$ to be the private dataset and $D_{-i}=(d_{1},...,d_{i-1},d_{i+1},...,d_{n})$ to be the private dataset after removing point $d_{i}$. Our work focuses on next-token prediction, where given an input query $\mathbf{x}=x_{1},x_{2},...,x_{t}$, which is a string of tokens from some vocabulary $V$, we choose the next token involves sampling from this probability mass function to obtain a token $\hat{x}_{t+1}\sim p(x_{t+1}|\mathbf{x}_{t})$.

### 3.1 Differential Privacy and Renyi Differential Privacy

###### Definition 3.1 (Approximate DP Dwork et al. ( 2014 ); Feldman & Zrnic ( 2021 ) ) .

Let $\epsilon>0,\delta\in[0,1]$. A randomized algorithm $A:\mathcal{D}\rightarrow\mathcal{R}$ satisfies $(\epsilon,\delta)$-DP if for all datasets $D\in\mathcal{D}$ and any set of subset of outputs $S\subseteq\mathcal{R}$ it holds that:

$$ $\Pr[A(D)\in S]\leq e^{\epsilon}\Pr[A(D_{-i})\in S]+\delta\text{ and }\Pr[A(D_{ -i})\in S]\leq e^{\epsilon}\Pr[A(D)\in S]+\delta$ $$

Another privacy notion of DP called Renyi Differential Privacy (RDP) contains convenient composition properties $(\epsilon,\delta)$-DP Mironov ().

###### Definition 3.2 (Renyi Divergence Mironov ( 2017 ) ) .

For two probability distributions $P$ and $Q$ defined over $\mathcal{R}$, the Renyi divergence of order $\alpha>1$ is

$$ $\textstyle D_{\alpha}(P||Q)=\frac{1}{\alpha-1}\log\mathop{\mathbb{E}}_{x\sim Q }\left[\left(\frac{P(x)}{Q(x)}\right)^{\alpha}\right],$ (1) $$

and define $D_{\alpha}^{\leftrightarrow}(P||Q)=\max\{D_{\alpha}(P||Q),D_{\alpha}(Q||P)\}$.

###### Definition 3.3 ( $(\alpha,\epsilon)$ -RDP Mironov ( 2017 ); Feldman & Zrnic ( 2021 ) ) .

A randomized algorithm $A:\mathcal{D}\rightarrow\mathcal{R}$ is $(\alpha,\epsilon)$-RDP if for all datasets $D\in\mathcal{D}$ it holds that $D_{\alpha}^{\leftrightarrow}(A(D)||A(D_{-i}))\leq\epsilon$.

In certain cases, it is possible to further reduce the privacy loss $\epsilon$ by exploiting properties of the private dataset $D$ during the privacy analysis. We define data-dependent RDP below.

###### Definition 3.4 (Data-Dependent RDP Papernot et al. ( 2018 ) ) .

A randomized algorithm $A:\mathcal{D}\rightarrow\mathcal{R}$ is $(\alpha,\epsilon(D))$-RDP if for all datasets $D\in\mathcal{D}$ it holds that $D_{\alpha}^{\leftrightarrow}(A(D)||A(D_{-i}))\leq\epsilon(D)$.

We discuss the implications of Data-Dependent RDP. Firstly, the privacy loss $\epsilon(D)$ can only be known once the computation of $A$ has halted. The release of $\epsilon(D)$ results in privacy leakage and thus must be privatized, which can be done by employing the smooth-sensitivity framework Nissim et al. () as done by Papernot et al. (). Privacy amplification by subsampling (Theorem A.4), a property that strengthens the privacy guarantee of a DP algorithm, cannot be used concurrently with data-dependent accounting, as it is currently an open problem Zhu et al. (). Lastly, checking that a data-dependent privacy loss $\epsilon(D)$ does not exceed a pre-specified privacy budget $\epsilon_{G}$ leaks additional privacy Redberg et al. (), and hence, is incompatible with the DP prediction definition Dwork & Feldman ().

###### Definition 3.1 (Approximate DP Dwork et al. ( 2014 ); Feldman & Zrnic ( 2021 ) ) .

###### Definition 3.2 (Renyi Divergence Mironov ( 2017 ) ) .

###### Definition 3.3 ( ( α , ϵ ) 𝛼 italic-ϵ (\alpha,\epsilon) ( italic_α , italic_ϵ ) -RDP Mironov ( 2017 ); Feldman & Zrnic ( 2021 ) ) .

###### Definition 3.4 (Data-Dependent RDP Papernot et al. ( 2018 ) ) .

### 3.2 The PMixED Framework

PMixED Flemings et al. () is a private decoding framework that guarantees DP at prediction time for generative LLMs. PMixED partitions a private dataset into $N$ pairwise disjoint subsets $D_{i}$, each of which is fine-tuned by an LLM $p_{i}$. Then during inference, each fine-tuned model generates its output probability distribution $p_{i}(\mathbf{x}_{t})$, containing private information, on some input $\mathbf{x}_{t}$ received by a user. Additionally, the output distribution from a public model $p_{0}(\mathbf{x}_{t})$ is obtained. PMixED then projects each of the private distributions onto a Renyi Divergence ball centered at the public distribution with radius $\beta\alpha$. The optimal projection is selected by choosing $\lambda_{i}$ such that $\lambda_{i}\leftarrow\operatorname{\operatorname*{arg\,max}}_{\lambda\in[0,1]}
\{D_{\alpha}^{\leftrightarrow}(\lambda p_{i}(\mathbf{x}_{t})+(1-\lambda)p_{0}(
\mathbf{x}_{t})||p_{0}(\mathbf{x}_{t}))\leq\beta\alpha\}$. Lastly, the projected distributions are averaged and then sampled to generate the next token. A precise description of PMixED can be found in Algorithm 2. We state the main privacy analysis results of Flemings et al. () here and leave the details in Appendix C.

###### Theorem 3.1 .

Given $\beta,N$ chosen by the analyst, PMixED satisfies $(\alpha,\epsilon(\alpha,\beta,N))$-RDP for some query $\mathbf{x}$ where

$$ $\textstyle\epsilon_{\text{PMixED}}(\alpha,\beta,N)\leq\frac{\log\left(\frac{N- 1+\exp\left({4\beta\alpha(\alpha-1)}\right)}{N}\right)}{\alpha-1}$ (2) $$

###### Theorem 3.2 .

PMixED $\mathcal{P}$ is an $(\alpha,\epsilon_{G})$-RDP prediction algorithm with respect to $D$ for a query budget $T$.

Although PMixED has been shown to satisfy the private prediction definition (Theorem 3.2), this limits PMixED to a fixed privacy level for only a certain number of queries. Once the query budget is exhausted, either no more predictions can be performed, or the privacy guarantee will decay with each additional prediction. For real-world LLM inference applications where it’s impossible to know the total number of queries ahead of time, this places a huge burden on the analyst to hypothesize an adequate query budget and privacy level before deployment. Moreover, the privacy loss between different queries can vary widely, yet it is not considered when pre-specifying a fixed privacy level.

###### Theorem 3.1 .

###### Theorem 3.2 .

## 4 AdaPMixED : An Adaptive Private Decoding Framework

In this work, we present a more realistic and feasible design that enables an adaptable privacy level. To this end, we modify PMixED to adapt to the private and public output distributions evaluated on a given input query. Consequently, the privacy level can only be determined after the next token has been sampled. Thus we focus on two scenarios that allow us to minimize the privacy loss: Section 4.1 discusses a mechanism to filter out queries where the private and public distributions diverge extremely. (2) Section 4.2 introduces a data-dependent privacy analysis to account for queries where the private and public distributions converge. As mentioned in section 2, the high-level idea of our noisy screening and data-dependent analysis are inspired by PATE Papernot et al. () but the low-level details differ substantially.

### 4.1 Noisy Screening Mechanism

The motivation is that for certain queries $\mathbf{x}$, the mixing parameter $\lambda_{i}$ is very small due to extreme divergence between the private and public distributions, i.e., $D_{\alpha}^{\leftrightarrow}(\overline{p}_{i}(\mathbf{x})||p_{0}(\mathbf{x}))$ is large for small $\lambda_{i}$. Since $\lambda_{i}$ is small, little information about the private data is used to assist with the prediction, leading to almost complete reliance on the public model. Perhaps, in this scenario, it would be better to save the privacy loss resulting from sampling the mixture of private and public information, and instead sample purely from the public distribution $p_{0}(\mathbf{x})$, which will result in no additional privacy loss since $p_{0}(\mathbf{x})$ was not fine-tuned on the private data $D$.

Hence, our key idea is to screen a query $\mathbf{x}$ by using the Renyi Divergence to measure the distributional difference between the projected and public output distributions. If the private and public distribution diverge extremely, we can check if mixing just a small amount of private information would already result in a large Renyi Divergence. In other words, we select a small $\lambda$, calculate $\overline{p}(\mathbf{x})=1/N\textstyle\operatorname{\sum}_{i=1}^{N}(\lambda p_
{i}(\mathbf{x})+(1-\lambda)p_{0}(\mathbf{x}))$, then check if $D_{\alpha}^{\leftrightarrow}(\overline{p}(\mathbf{x}_{t})||p_{0}(\mathbf{x}))\leq
T$ for some threshold value $T$. Using a small $\lambda$ also helps reduce the privacy loss from the noisy screening since less private information is used in the screening. Making this screening mechanism differentially private involves privatizing $D_{\alpha}^{\leftrightarrow}(\overline{p}(\mathbf{x}_{t})||p_{0}(\mathbf{x}))$, which is difficult to do directly since $D_{\alpha}^{\leftrightarrow}(\overline{p}(\mathbf{x}_{t})||p_{0}(\mathbf{x}))$ contains no upper-bound, and hence, no global sensitivity.

To work around this, we make use of the post-processing theorem of DP (Theorem A.1) by first privatizing $\overline{p}(\mathbf{x}_{t})$ by adding Gaussian noise to it, $\overline{p}_{\text{priv}}(\mathbf{x})=\overline{p}(\mathbf{x})+\mathcal{N}(0,
\sigma^{2})$, then checking if $D_{\alpha}^{\leftrightarrow}(\overline{p}_{\text{priv}}(\mathbf{x}_{t})||p_{0}
(\mathbf{x}))\leq T$. However, one technical challenge is that $\overline{p}(\mathbf{x}_{t})$ is a large dimensional vector, approximately 50,000 dimensions. Hence, the error of the screening mechanism scales proportionally to the size of this large vector. To reduce the noise, we use a similar approach from Tian et al. (); Tang et al. () by selecting the top-$k$ indices $K$ of the public model $p_{0}(\mathbf{x})$, which does not leak additional privacy since $p_{0}(\mathbf{x})$ was not fine-tuned on $D$, then truncate and re-scale $p_{0}(\mathbf{x}_{t})$ with $K$ to obtain $\overline{p}_{0}(\mathbf{x})$. Using $K$, we truncate $\overline{p}(\mathbf{x})$, apply noise to those $K$ indices of $\overline{p}(\mathbf{x})$, i.e., $\overline{p}_{\text{priv}}(\mathbf{x})[K]=\overline{p}(\mathbf{x})[K]+\mathcal
{N}(0,\sigma^{2})$, then re-scale $\overline{p}_{\text{priv}}(\mathbf{x})$. Lastly, the divergence of $\overline{p}_{0}(\mathbf{x}_{t})$ and the DP projected distribution $\overline{p}_{\text{priv}}(\mathbf{x})$ at indices $K$ is measured.

With the noisy screening mechanism explained, we now analyze its privacy loss and defer the proof to Appendix D.

###### Theorem 4.1 .

Given some mixing parameter $\lambda$ and ensemble size $N$, the the noisy screening mechanism satisfies $(\alpha,\epsilon_{\text{screen}}(\alpha,N,\lambda,\sigma))$-RDP where $\textstyle\epsilon_{\text{screen}}(\alpha,N,\lambda,\sigma)=\left(\frac{
\lambda}{N\sigma}\right)^{2}\alpha$.

###### Theorem 4.1 .

### 4.2 Data-Dependent Privacy

When calculating the privacy loss of PMixED, Theorem 3.1 gives an analytical upper bound containing the Renyi Divergence order $\alpha$, the target leakage/radius $\beta$, and the ensemble size $N$. One thing to note is that this bound’s derivation employs the Quasi convexity property and Triangle-like inequality of Renyi Divergence, resulting in a rather loose bound. Moreover, we observe that PMixED will answer certain queries $\mathbf{x}$ with just the private output distributions since the private and public distributions are similar. However, the data-independent privacy analysis does not account for this and instead designates a fixed privacy loss for each query, leading to overestimated privacy loss. In other words, for all $i\in[N]$, the mixing parameter $\lambda_{i}=1$ yet $D_{\alpha}^{\leftrightarrow}(\overline{p}_{i}(\mathbf{x})||p_{0}(\mathbf{x}))<
<\beta\alpha$.

A key feature in language modeling that we can take advantage of is that LLMs inherently produce a probability distribution as its output. Thus the privacy loss of PMixED can be a direct numerical calculation of the Renyi Divergence between the output of PMixED with the entire ensemble, $p(\mathbf{x})=\textstyle\frac{1}{N}\operatorname{\sum}_{i=1}^{N}\overline{p}_{
i}(\mathbf{x})$, and the output of PMixED with a neighboring ensemble where the $i$-th model removed, $p_{-i}(\mathbf{x})=\textstyle\frac{1}{N-1}\operatorname{\sum}_{j\neq i}
\overline{p}_{j}(\mathbf{x})$. Therefore, the data-dependent privacy loss of PMixED iteratively searches through all possible neighboring ensembles to find the one with the largest privacy loss, in order to satisfy the data-dependent DP definition 3.4:

$$ $\epsilon_{\text{PMixED}}(\alpha,\beta,N,D,\mathbf{x})=\operatorname{\max}_{i \in[N]}\left\{D_{\alpha}^{\leftrightarrow}(p(\mathbf{x})||p_{-i}(\mathbf{x})) \right\}.$ (3) $$

Note that $\epsilon_{\text{PMixED}}(\alpha,\beta,N,D,\mathbf{x})\leq\epsilon_{\text{
PMixED}}(\alpha,\beta,N)$, since $\epsilon_{\text{PMixED}}(\alpha,\beta,N)$ is a direct analytical upper bound of $\epsilon_{\text{PMixED}}(\alpha,\beta,N,D,\mathbf{x})$. Hence, we can avoid the loose data-independent analysis by alternatively using the substantially tighter numerical, data-dependent calculation. Although the privacy loss is now a function of the private data, one can sanitize the privacy loss via smooth sensitivity analysis, similar to Papernot et al. (), if the privacy loss needs to be released.

### 4.3 Privacy and Utility Analysis

Figure: Algorithm 1 AdaPMixED: Data-dependent PMixED with noisy screening

With our noisy screening mechanism and data-dependent accounting, we succinctly describe AdaPMixED in Algorithm 1 and state its privacy and utility guarantee below. The proof is left to Appendix D.

###### Theorem 4.2 .

Given a query $\mathbf{x}$, the next token $y$ sampled by AdaPMixED, Algorithm 1, is data-dependent $(\alpha,\epsilon(\alpha,\beta,N,\lambda,\sigma,D,\mathbf{x}))$-RDP where

$$ $\epsilon(\alpha,\beta,N,\lambda,\sigma,D,\mathbf{x})\leq\epsilon_{\text{screen }}(\alpha,N,\lambda,\sigma)+\mathbbm{1}\left\{D_{\alpha}^{\leftrightarrow}( \overline{p}_{\text{priv}}(\mathbf{x})||p_{0}(\mathbf{x}))\leq T\right\} \epsilon_{\text{PMixED}}(\alpha,\beta,N,D,\mathbf{x})$ $$

Our utility analysis, presented below, employs the average negative log-likelihood, which is just the logarithm of perplexity, as our utility function since our work focuses on next-token prediction. We measure the difference between the likelihood from an ensemble that only uses the private models, i.e., $\lambda_{i}=1$ for all $i$, which is the best-performing ensemble, and the likelihood of the ensemble from AdaPMixED. To ease the analysis, we do not consider Noisy Screening.

###### Theorem 4.3 .

Let $\lambda_{i,t}$ denote the mixing parameter of model $i$ at query $t$ that was produced by AdaPMixED, $\mathbf{\lambda}^{*}=J_{N,T}$ where $J$ is the $N\times T$ all-ones matrix, and $\textstyle\mathcal{L}(\mathbf{x},\mathbf{\lambda})=-\frac{1}{T}\sum_{t=1}^{T}
\log\sum_{i=1}^{N}[\lambda_{i,t}p_{i}(x_{t}|\mathbf{x}_{t})+(1-\lambda_{i,t})p
_{0}(x_{t}|\mathbf{x}_{t})]/N$ be the negative log-likelihood function. For any $T>0$ we have the following:

$$ $\mathcal{L}\left(\mathbf{x},\mathbf{\lambda}\right)-\mathcal{L}\left(\mathbf{x },\mathbf{\lambda}^{*}\right)\leq\max_{t\in[T]}\max_{j\in[N]}\left\{(1-\lambda _{j,t})\log\left(\frac{p_{j}(x_{t}|\mathbf{x}_{t})}{p_{0}(x_{t}|\mathbf{x}_{t} )}\right)\right\}.$ $$

Hence, we can bound the performance error from AdaPMixED by the likelihood of a private model $p_{j}(x_{t}|\mathbf{x}_{t})$ evaluated on a query $\mathbf{x}_{t}$ that diverges the most from the public model $p_{0}(x_{t}|\mathbf{x}_{t})$. If the divergence is large, then it causes the log-likelihood difference between the private and public model $\log(p_{j}(x_{t}|\mathbf{x}_{t})/p_{0}(x_{t}|\mathbf{x}_{t}))$ to be large. Moreover, the likelihood of the private model with largest divergence from the public will cause the projection to be closer to the public model i.e., $\lambda_{j,t}\leftarrow 0$, increasing the utility gap. We also want to highlight that, to our knowledge, we are the first privacy-preserving decoding work that provides a utility analysis.

###### Theorem 4.2 .

###### Theorem 4.3 .

## 5 Experimental Evalutation

### 5.1 Experimental Setup

We roughly follow the same experimental setup as the original PMixED Flemings et al. () on the WikiText-103 Merity et al. () and One Billion Word Chelba et al. () datasets. However, we experimented with two additional datasets: PubMed Cohan et al. (), which contains scientific papers from the medical domain, and Air Dialogue Wei et al. (), which contains customer service dialogue on flight booking. For models we use pre-trained GPT-2 models Radford et al. () from HuggingFace Wolf et al. (). Since storing an ensemble of LLMs can be expensive, we opt to use LoRA Hu et al. () for parameter-efficient fine-tuning. Additional details of the training and prediction hyperparameters can be found in Appendix E.

**Table 1: Main results of the utility-privacy tradeoff between all methods and AdaPMixED. Smaller privacy loss $\epsilon$ and PPL are better.**
| Dataset | Queries Answered | Method | Privacy loss $\epsilon$ | PPL |
| --- | --- | --- | --- | --- |
| WikiText-103 | 1024 | Public model | 0 | 40.86 $\pm$ 6.11 |
| DP-SGD | 8 | 35.09 $\pm$ 5.50 |  |  |
| PMixED | 8 | 33.8 $\pm$ 5.29 |  |  |
| AdaPMixED | 0.494 | 32.35 $\pm$ 4.63 |  |  |
| 99,840 | DP-SGD | 8 | 32.53 |  |
| AdaPMixED | 5.248 | 29.99 |  |  |
| One Billion<br>Word | 1024 | Public model | 0 | 67.73 $\pm$ 6.77 |
| DP-SGD | 8 | 54.54 $\pm$ 5.42 |  |  |
| PMixED | 8 | 52.68 $\pm$ 5.29 |  |  |
| AdaPMixED | 0.485 | 49.25 $\pm$ 4.65 |  |  |
| 99,840 | DP-SGD | 8 | 52.97 |  |
| AdaPMixED | 3.186 | 47.99 |  |  |
| PubMed | 19,968 | Public model | 0 | 32.28 |
| DP-SGD | 8 | 28.07 |  |  |
| AdaPMixED | 2.858 | 26.83 |  |  |
| Air Dialogue | 16,384 | Public model | 0 | 17.33 |
| DP-SGD | 8 | 8.13 |  |  |
| AdaPMixED | 6.906 | 7.67 |  |  |

The utility is measured in terms of perplexity score (PPL), and the privacy loss $\epsilon$ is the privacy guarantee of the method after answering all queries. In the main results, $8$ runs were performed and averaged to obtain the PPL and privacy loss $\epsilon$ for $1024$ queries answered; for queries $>1024$, one run was performed. $4$ methods are compared in the main results: (1) a public model, which we chose to be a pre-trained GPT-2 small model; (2) DP-SGD with LoRA Yu et al. (); (3) the original PMixED framework Flemings et al. (); (4) AdaPMixED, our method. The privacy loss is computed in RDP, but converted back to $(\epsilon,\delta)$-DP, and all methods use $\delta=1\times 10^{-5}$.

### 5.2 Main Results

In this section, we highlight the privacy and utility improvement of our noisy screening mechanism and data-dependent analysis shown in Table 1. For the original datasets used in PMixED, WikiText-103 and One Billion Word, we observe that AdaPMixED outperforms the original PMixED by $1.4$ PPL with $16$ times less privacy. Thus, AdaPMixED not only significantly reduces the privacy loss of the original PMixED, but it also can further improve the utility. Moreover, when we increase the number of queries answered to 99,840, we observe that the privacy loss of AdaPMixED is only moderate, $\epsilon=5.248$ and $\epsilon=3.186$ for WikiText-103 and One Billion Word, respectively. And its utility is remarkably higher than DP-SGD, gaining $2.5$ and $5.0$ PPL improvement on WikiText-103 and One Billion Word respectively. The results for PMixED with 100,000 queries are not shown since its utility is identical to the public model. The large query budget offers very little privacy loss for each prediction, forcing PMixED to rely heavily on the public model.

For the additional datasets, PubMed and Air Dialogue, we observe the same trend where AdaPMixED either outperforms or achieves comparable performance to DP-SGD for large-scale predictions with moderate privacy loss. These promising results demonstrate that even for substantially large inference loads, AdaPMixED obtains strong model utility while incurring a reasonable privacy loss.

### 5.3 Privacy-Utility Tradeoff of Data-Dependent Analysis and Noisy Screening

**(a) The privacy-utility tradeoff of noisy screening and data-dependent analysis.**
| Method | Privacy<br>Loss: $\epsilon$ | PPL | # $\geq T$ |
| --- | --- | --- | --- |
| PMixED | 4.399 | 38.07 | 0 |
| PMixED with noisy screening | 4.139 | 38.15 | 716 |
| AdaPMixED with only<br>Data-dependence | 0.960 | 31.42 | 0 |
| AdaPMixED | 0.924 | 31.75 | 1026 |

Now we investigate the privacy and utility of each component of AdaPMixED: noisy screening and data-dependent analysis. In this setup, we perform $9728$ predictions on WikiText-103 using $4$ methods: PMixED, PMixED with noisy screening only, AdaPMixED with data-dependent analysis only, and finally the combination of both schemes in AdaPMixED. Table 2(a) details the privacy-utility tradeoff of each of the 4 methods. The most evident observation here is that data-dependent analysis has the largest effect on reducing the privacy loss, a $4.5$ times reduction compared to data-independent analysis. Even with PMixED employing privacy amplification by subsampling in its privacy analysis, its resulting privacy loss is still substantially larger than the data-dependent loss. Thus, the data-independent analysis pessimistically overestimates the privacy loss while data-dependent accounting provides a much tighter bound.

The effect of noisy screening on the privacy loss is smaller but still plays a significant role for both data-independent and data-dependent analysis. We observe that including noisy screening decreases the privacy loss as more queries are answered by the public model. For data-independent accounting, the additional privacy savings is $0.26$ while for data-dependent it is $0.036$. Additionally, we observe that noisy screening saves $0.26$ privacy over PMixED while only lowering the utility by $0.08$ PPL. For data-dependent analysis, noisy screening lowers the privacy loss by $0.036$ with a $0.33$ PPL decrease. In our view, privacy loss is a more valuable quantity than PPL, so we believe the privacy-utility tradeoff offered by our scheme is significant. Furthermore, out of the $9728$ queries answered, $716$ and $1026$ were answered completely by the public model when using PMixED with noisy screening and AdaPMixED, respectively. Hence, this validates that a good chunk of the queries can be answered sufficiently with just the public model without diminishing the utility.

Lastly, Table 2(b) breaks down the privacy loss of PMixED. Noisy screening only comprises of $0.002\%$ of the total privacy loss, clearly justifying that it saves more privacy than it loses. As expected, most of the privacy loss comes from privately decoding the next token.

### 5.4 Ablations

Finally, we perform ablations on the prediction hyperparameters AdaPMixED shown in Figure 2 to better understand their privacy-utility tradeoff. We do acknowledge that AdaPMixED does contain additional hyperparameters over PMixEd and DP-SGD, although we do have fewer hyperparameters than PATE Papernot et al. (). However, one advantage of private prediction frameworks is that tuning the hyperparameters of AdaPMixED is considerably faster than DP-SGD because they are tuned during prediction, as opposed to retraining an LLM for the tuning process of DP-SGD.

Based on the ablation results from Figure 2, we present some rules of thumb that avoid hyperparameters tuning and still achieve reasonable privacy-utility tradeoffs. We find that $T\in[4,4.5]$, $k\in[20,100]$, $\beta\in[0.2,0.3]$, $N\in[80,100]$, $\lambda\in[10^{-4},10^{-5}],\sigma\in[10^{-2},10^{-1}]$, and $\alpha\in[15,20]$ seemingly gives a good balance between privacy and utility. Moreover, one can select values beyond these suggested bounds based on which goal– privacy or utility– one wants to prioritize. If one wants to prioritize utility, larger values of $T$ and $\beta$ should be chosen, while smaller values of $T$ and $\beta$ would help minimize the privacy loss. However, for some parameters, such as $k$, we do not suggest going beyond the bounds, as larger $k$ results in worse utility degradation and smaller privacy loss because the magnitude of additive noise from noisy screening is larger. Thus, there is an increased likelihood of exceeding the threshold $T$, resulting in purely answering the query by the public model.

Figure: (a)

## 6 Conclusion

In this work, we present AdaPMixED, a private decoding scheme that adapts to the private and public distributions evaluated on input queries to enable a large number of queries to be performed privately. Our work identified a crucial limitation of a recent work, PMixED: an analyst must set a fixed-privacy guarantee and a query budget before inference, a setup too rigid for real-world applications. The noisy screening mechanism of AdaPMixED filters out queries that result in large Renyi Divergence between projected and public distributions, and use the public model to answer them. The data-dependent privacy analysis performed by AdaPMixED exploits the output probability distribution induced by generative LLMs to directly calculate the privacy loss. These data-adaptive methods enable AdaPMixED to answer 100K queries while achieving reasonable privacy loss, $\epsilon=5.248$, while still outperforming DP-SGD by nearly $2.5$ perplexity. To our knowledge, no prior work has scaled private prediction methods to this large of queries while achieving strong utility. We hope that our work will spark more progress in private prediction to be a practical alternative over private training methods.

## Appendix A Useful Properties of RDP

###### Theorem A.1 (Post-Processing Mironov ( 2017 ) ) .

Let $A:\mathcal{D}\rightarrow\mathcal{R}$ be $(\alpha,\epsilon)$-RDP, and let $F:\mathcal{R}\rightarrow\mathcal{Z}$ be an arbitrary randomized mapping. Then $F\circ M$ is $(\alpha,\epsilon)$-RDP.

###### Theorem A.2 (Composition Mironov ( 2017 ) ) .

Let $A_{1},...,A_{k}$ be a sequence of $(\epsilon,\alpha)$-RDP algorithms. Then the composition $A_{k}\circ A_{k-1}\circ...\circ A_{1}$ is $(\alpha,k\epsilon)$-RDP.

###### Theorem A.3 (Conversion from RDP to Approximate DP Balle et al. ( 2020 ) ) .

If an algorithm $A$ is $(\alpha,\epsilon)$-RDP, then it is $(\epsilon+\log((\alpha-1)/\alpha)-(\log\delta+\log\alpha)/(\alpha-1),\delta)$-DP for any $0<\delta<1$.

###### Theorem A.4 (Tight Privacy Amplification by Poisson Subsampling for Renyi DP Steinke ( 2022 ) ) .

Let $U\subseteq[n]$ be a random set that contains each element independently with probability $q$. For $x\in\mathcal{X}^{n}$ let $x_{U}\in\mathcal{X}^{n}$ be given by $(x_{U})_{i}=x_{i}$ if $i\in U$ and $(x_{U})_{i}=\bot$ if $i\notin U$, where $\bot\in\mathcal{X}$ is some fixed value.

Let $\epsilon:\mathbb{N}_{\geq 2}\rightarrow\mathbb{R}\cup\{\infty\}$ be a function. Let $M:\mathcal{X}^{n}\rightarrow\mathcal{Y}$ satisfy $(\alpha,\epsilon(\alpha))$-RDP for all $\alpha\in\mathbb{N}_{\geq 2}$ with resepect to addition or removal– i.e., $x,x^{{}^{\prime}}\in\mathcal{X}^{n}$ are neighboring if, for some $i\in[n]$, we have $x_{i}=\bot$ or $x^{{}^{\prime}}_{i}=\bot$, and $\forall j\neq i$ $x_{j}=x_{j}^{{}^{\prime}}$.

Define $M^{U}:\mathcal{X}^{n}\rightarrow Y$ by $M^{U}(x)=M(x_{U})$. Then $M^{U}$ satisfies $(\alpha,\epsilon^{{}^{\prime}}_{q}(\alpha))$-RDP for all $\alpha\in\mathbb{N}_{\geq 2}$ where

$$ $\epsilon^{{}^{\prime}}_{q}(\alpha)=\frac{1}{\alpha-1}\log\left((1-q)^{\alpha-1 }(1+(\alpha-1)q)+\sum_{k=2}^{\alpha}\binom{\alpha}{k}(1-q)^{\alpha-k}q^{k}e^{( k-1)\epsilon(k)}\right).$ (4) $$

###### Theorem A.5 (Triangle-like inequality, lemma 33.7 from Steinke ( 2022 ) ) .

Let $P,Q,R$ be distributions on $\mathcal{R}$. If $D_{\alpha}(P||Q)\leq\epsilon_{1}\alpha$ and $D_{\alpha}(Q||R)\leq\epsilon_{2}\alpha$ for $1<\alpha<\infty$, then

$$ $D_{\alpha}(P||R)\leq(\sqrt{\epsilon_{1}}+\sqrt{\epsilon_{2}})^{2}\alpha.$ (5) $$

###### Theorem A.6 (Quasi-Convexity Steinke ( 2022 ) ) .

Let $P,Q,P{{}^{\prime}},Q^{{}^{\prime}}$ be probability distributions over $\mathcal{R}$ such that $P^{{}^{\prime}}$ absolutely continuous with respect to $Q^{{}^{\prime}}$. For $s\in[0,1]$, let $(1-s)P+sP^{{}^{\prime}}$ denote the convex combination of the distributions $P$ and $P^{{}^{\prime}}$ with weighting $s$. For all $\alpha\in(1,\infty)$ and all $s\in[0,1]$,

$$ $D_{\alpha}((1-s)P+sP^{{}^{\prime}}||(1-s)Q+sQ^{{}^{\prime}})\leq\max\{D_{ \alpha}(P||Q),D_{\alpha}(P^{{}^{\prime}}||Q^{{}^{\prime}})\}.$ $$

###### Theorem A.7 (Convexity in Second Argument Van Erven & Harremos ( 2014 ) ) .

For any order $\alpha\in[0,\infty]$ Renyi divergence is convex in its second argument. That is, for any probability distributions $P,Q,Q^{\prime}$ and $s\in[0,1]$

$$ $D_{\alpha}(P||(1-s)Q+sQ^{\prime})\leq(1-s)D_{\alpha}(P||Q^{\prime})+D_{\alpha} (P||Q).$ $$

###### Theorem A.1 (Post-Processing Mironov ( 2017 ) ) .

###### Theorem A.2 (Composition Mironov ( 2017 ) ) .

###### Theorem A.3 (Conversion from RDP to Approximate DP Balle et al. ( 2020 ) ) .

###### Theorem A.4 (Tight Privacy Amplification by Poisson Subsampling for Renyi DP Steinke ( 2022 ) ) .

###### Theorem A.5 (Triangle-like inequality, lemma 33.7 from Steinke ( 2022 ) ) .

###### Theorem A.6 (Quasi-Convexity Steinke ( 2022 ) ) .

###### Theorem A.7 (Convexity in Second Argument Van Erven & Harremos ( 2014 ) ) .

## Appendix B More background on PMixED

Algorithm 2 gives a detailed algorithmic description of PMixED.

Figure: Algorithm 2 PMixED: A protocol for Private Next Token Prediction

## Appendix C More Details on Privacy Analysis of PMixED

The privacy analysis of PMixED is taken verbatim from the original paper Flemings et al. () and is as follows: first, consider the case of no Poisson subsampling and deriving the privacy loss. Then, invoke the privacy amplification theorem A.4 to derive the final privacy guarantees. Lastly, the implications of the privacy guarantees. Let $\mathcal{P}$ denote PMixED. Note that $D$ and $D^{{}^{\prime}}$ are neighboring datasets if $D^{{}^{\prime}}$ adds or removes a subset $D_{i}$ from $D$, which is equivalent to adding or removing the model $p_{i}$ from the ensemble. Also recall that $\lambda_{i}$ is automatically chosen by solving the following optimization scheme:

$$ $\lambda_{i}\leftarrow\operatorname*{arg\,max}\limits_{\lambda\in[0,1]}\{D_{ \alpha}^{\leftrightarrow}(\overline{p}_{i}(\mathbf{x}_{t})||p_{0}(\mathbf{x}_{ t}))\leq\beta\alpha\}.$ (6) $$

###### Theorem C.1 .

PMixEd $\mathcal{P}$ satisfies $(\alpha,\epsilon(\alpha,\beta,N))$-RDP for some query $\mathbf{x}_{t}$ where

$$ $\epsilon(\alpha,\beta,N)\leq\begin{cases}\frac{\log\left(\frac{N-1+\exp\left({ (\alpha-1)4\beta\alpha}\right)}{N}\right)}{\alpha-1}&\text{if }N>1\\ \beta\alpha&\text{otherwise}\end{cases}.$ (7) $$

Proof. Let $i\in[N]$ and $\mathbf{x}_{t}$ be a query. Define

$$ $\displaystyle p(\mathbf{x}_{t})=\frac{1}{N}\sum_{i=1}^{N}\lambda_{i}p_{i}( \mathbf{x}_{t})+(1-\lambda_{i})p_{0}(\mathbf{x}_{t}),$ $\displaystyle p_{-i}(\mathbf{x}_{t})=\frac{1}{N-1}\sum_{j\neq i}\lambda_{j}p_{ j}(\mathbf{x}_{t})+(1-\lambda_{j})p_{0}(\mathbf{x}_{t})$ $$

where $\lambda_{i}$ is selected from Equation 6. Now, observe that each $\lambda_{i}$ is dependent only on $D_{i}$, so $p_{-i}(\mathbf{x}_{t})$ does not contain $D_{i}$. Using the fact that $D_{\alpha}^{\leftrightarrow}(\overline{p}_{j}(\mathbf{x}_{t})||p_{0}(\mathbf{x
}_{t}))\leq\beta\alpha$ for all $j\in[N]$, then for any two neighboring ensembles $\{p_{i}\}_{i=1}^{N}$, $\{p_{j}\}_{j\neq i}$ with $N>1$

$$ $\displaystyle e^{(\alpha-1)D_{\alpha}\left(y_{t}\sim\mathcal{P}\left(\{p_{i}\} _{i=1}^{N},\mathbf{x}_{t}\right)||y_{t}\sim\mathcal{P}\left(\{p_{j}\}_{j\neq i },\mathbf{x}_{t}\right)\right)}$ $\displaystyle=e^{(\alpha-1)D_{\alpha}(p(\mathbf{x}_{t})||p_{-i}(\mathbf{x}_{t} ))}$ $\displaystyle=\mathop{\mathbb{E}}_{p_{-i}(\mathbf{x}_{t})}\left[\left(\frac{p( \mathbf{x}_{t})}{p_{-i}(\mathbf{x}_{t})}\right)^{\alpha}\right]$ $\displaystyle=\mathop{\mathbb{E}}_{p_{-i}(\mathbf{x}_{t})}\left[\left(\frac{ \frac{N-1}{N}p_{-i}(\mathbf{x}_{t})+\frac{1}{N}\overline{p}_{i}(\mathbf{x}_{t} )}{p_{-i}(\mathbf{x}_{t})}\right)^{\alpha}\right]$ $\displaystyle\leq\mathop{\mathbb{E}}_{p_{-i}(\mathbf{x}_{t})}\left[\frac{\frac {N-1}{N}(p_{-i}(\mathbf{x}_{t}))^{\alpha}+\frac{1}{N}(\overline{p}_{i}(\mathbf {x}_{t}))^{\alpha}}{(p_{-i}(\mathbf{x}_{t}))^{\alpha}}\right]$ (8) $\displaystyle=\mathop{\mathbb{E}}_{p_{-i}(\mathbf{x}_{t})}\left[\frac{N-1}{N}+ \frac{1}{N}\left(\frac{\overline{p}_{i}(\mathbf{x}_{t})}{p_{-i}(\mathbf{x}_{t} )}\right)^{\alpha}\right]$ $\displaystyle=\frac{N-1}{N}+\frac{1}{N}\mathop{\mathbb{E}}_{p_{-i}(\mathbf{x}_ {t})}\left[\left(\frac{\overline{p}_{i}(\mathbf{x}_{t})}{p_{-i}(\mathbf{x}_{t} )}\right)^{\alpha}\right]$ $\displaystyle=\frac{N-1}{N}+\frac{1}{N}e^{(\alpha-1)D_{\alpha}(\overline{p}_{i }(\mathbf{x}_{t})||p_{-i}(\mathbf{x}_{t}))}$ $\displaystyle\leq\frac{N-1}{N}+\frac{1}{N}e^{(\alpha-1)4\beta\alpha}$ (9) $$

where Equation 8 uses Jensen’s inequality for the convex function $f(x)=x^{\alpha}$ since $\alpha\geq 1$ and $x\geq 0$ because we are dealing with probabilities, and Equation 9 is due to $D_{\alpha}(\overline{p}_{i}(\mathbf{x}_{t})||p_{0}(\mathbf{x}_{t}))\leq\beta\alpha$ and

$$ $\displaystyle D_{\alpha}(p_{0}(\mathbf{x}_{t})||p_{-i}(\mathbf{x}_{t}))$ $\displaystyle\leq\max_{j\neq i}D_{\alpha}(p_{0}(\mathbf{x}_{t})||\overline{p}_ {j}(\mathbf{x}_{t}))$ $\displaystyle\leq\beta\alpha$ $$

by the Quasi Convexity property of Renyi Divergence A.6. Then using the Triangle-like Inquality A.5 gives us $D_{\alpha}(\overline{p}_{i}(\mathbf{x}_{t})||p_{-i}(\mathbf{x}_{t}))\leq 4\beta\alpha$. When $N=1$, then $p_{-i}(\mathbf{x}_{t})=p_{0}(\mathbf{x}_{t})$ since PMixED will resort to using $p_{0}$. Hence $D_{\alpha}(p(\mathbf{x}_{t})||p_{-i}(\mathbf{x}_{t}))\leq\beta\alpha$.

Now, for the other way

$$ $\displaystyle D_{\alpha}(p_{-i}(\mathbf{x}_{t})||p(\mathbf{x}_{t}))$ $\displaystyle=D_{\alpha}\left(p_{-i}(\mathbf{x}_{t})\Big{\|}\frac{N-1}{N}p_{-i }(\mathbf{x}_{t})+\frac{1}{N}\overline{p}(\mathbf{x}_{t})\right)$ $\displaystyle\leq\frac{N-1}{N}D_{\alpha}(p_{-i}(\mathbf{x}_{t})||p_{-i}( \mathbf{x}_{t}))+\frac{1}{N}D_{\alpha}(p_{-i}(\mathbf{x}_{t})||\overline{p}_{i }(\mathbf{x}_{t}))$ (10) $\displaystyle\leq\frac{4\beta\alpha}{N}$ (11) $\displaystyle=\frac{\frac{N-1}{N}\log(1)+\frac{1}{N}\log\left(\exp\left(4\beta \alpha(\alpha-1)\right)\right)}{\alpha-1}$ $\displaystyle\leq\frac{\log\left(\frac{N-1+\exp\left({(\alpha-1)4\beta\alpha} \right)}{N}\right)}{\alpha-1}$ (12) $$

where Equation 10 uses convexity in the second argument of Renyi divergence (Theorem A.7), Equation 11 uses the same argument as in Equation 9, and Equation 12 is due to concavity of logarithms. Thus $D^{\leftrightarrow}_{\alpha}(p(\mathbf{x}_{t})||p_{-i}(\mathbf{x}_{t}))\leq
\epsilon(\alpha,\beta,N)$. ∎

###### Lemma C.1 .

Choose $\beta$ such that

$$ $\beta\leq\begin{cases}\frac{\log\left(Ne^{(\alpha-1)\epsilon_{G}/T}+1-N\right) }{4(\alpha-1)\alpha},&\text{if }N>1\\ \frac{\epsilon_{G}}{T\alpha}&\text{otherwise}\end{cases},$ (13) $$

then $\epsilon(\alpha,\beta,N)\leq\epsilon_{G}/T$. Hence each prediction of PMixED satisfies $(\alpha,\epsilon_{G}/T)$-RDP.

###### Theorem C.2 .

PMixED $\mathcal{P}$ is an $(\alpha,\epsilon_{G})$-RDP prediction protocol with respect to $D$.

Proof. Let $Q$ be an interactive query generating algorithm that generates queries $\mathbf{x}_{t}$. We first obtain fine-tuned weights using the training algorithm $p_{i}=A(p_{0},D_{i})$. Then $\mathcal{P}$ uses $\mathbf{x}_{t}$ as input and returns a response, which is a sample $y_{t}\sim\mathcal{P}(\{p_{i}\}_{i=1}^{N},\mathbf{x}_{t})$. Setting $\beta$ to Equation 13 guarantees that $y_{t}$ is $(\alpha,\epsilon_{G}/T)$-RDP. Then after $T$ queries and responses, the sequence $\{(\mathbf{x}_{t},y_{t})\}_{t=1}^{T}$ is $(\alpha,\epsilon_{G})$-RDP by the Composition Theorem A.1. Therefore $\mathcal{P}$ is an $(\alpha,\epsilon_{G})$-RDP prediction protocol. ∎

###### Theorem C.1 .

###### Lemma C.1 .

###### Theorem C.2 .

## Appendix D Proof of Theorem 4.1 , 4.2 , and 4.3

We now prove the main theorems. We restate the corresponding theorems and provide the proof details below:

###### Theorem D.1 .

Given some mixing parameter $\lambda$ and ensemble size $N$, the the noisy screening mechanism satisfies $(\alpha,\epsilon_{\text{screen}}(\alpha,N,\lambda,\sigma))$-RDP where $\textstyle\epsilon_{\text{screen}}(\alpha,N,\lambda,\sigma)=\left(\frac{
\lambda}{N\sigma}\right)^{2}\alpha$.

Proof. We will show that the sensitivity of the noisy screening mechanism is $\Delta=\frac{\lambda\sqrt{2}}{N}$. For any two neighboring datasets $\overline{p}_{\text{priv}}(\mathbf{x})=\textstyle\frac{1}{N}\operatorname{\sum
}_{i=1}^{N}\lambda p_{i}(\mathbf{x})+(1-\lambda)p_{0}(\mathbf{x}),\overline{p}
_{\text{priv},-i}(\mathbf{x})=\textstyle\frac{1}{N-1}\operatorname{\sum}_{j
\neq i}\lambda p_{j}(\mathbf{x})+(1-\lambda)p_{0}(\mathbf{x})$

$$ $\displaystyle\Delta$ $\displaystyle=\max_{i\in[N]}||\overline{p}_{\text{priv}}(\mathbf{x})-\overline {p}_{\text{priv},-i}(\mathbf{x})||_{2}$ $\displaystyle=\max_{i\in[N]}\Big{\|}\left(\frac{N-1}{N}\overline{p}_{\text{ priv},-i}(\mathbf{x})+\frac{1}{N}\overline{p}_{i}(\mathbf{x}_{t})\right)- \overline{p}_{\text{priv},-i}(\mathbf{x})\Big{\|}_{2}$ $\displaystyle=\frac{1}{N}\max_{i\in[N]}\Big{\|}\overline{p}_{i}(\mathbf{x}_{t} )-\overline{p}_{\text{priv},-i}(\mathbf{x})\Big{\|}_{2}$ $\displaystyle=\frac{1}{N}\max_{i\in[N]}\Big{\|}(\lambda{p}_{i}(\mathbf{x}_{t}) +(1-\lambda)p_{0}(\mathbf{x}_{t}))-\frac{1}{N-1}\left(\sum_{j\neq i}\lambda p_ {j}(\mathbf{x}_{t})+(1-\lambda)p_{0}(\mathbf{x}_{t})\right)\Big{\|}_{2}$ $\displaystyle=\frac{\lambda}{N}\max_{i\in[N]}\Big{\|}{p}_{i}(\mathbf{x}_{t})- \frac{1}{N-1}\sum_{j\neq i}p_{j}(\mathbf{x}_{t})\Big{\|}_{2}$ $\displaystyle=\frac{\lambda}{N}(\sqrt{2}).$ $$

Since the Gaussian mechanism is $(\alpha,\textstyle\frac{\Delta^{2}\alpha}{2\sigma^{2}})$-RDP, then the noisy screening mechanism is $\textstyle(\alpha,\left(\frac{\lambda}{N\sigma}\right)^{2}\alpha)$-RDP.

###### Theorem D.2 .

Given a query $\mathbf{x}$, the prediction $y$ produced by AdaPMixED, Algorithm 1, is data-dependent $(\alpha,\epsilon(\alpha,\beta,N,\lambda,\sigma,D,\mathbf{x}))$-RDP where

$$ $\epsilon(\alpha,\beta,N,\lambda,\sigma,D,\mathbf{x})\leq\begin{cases}\epsilon_ {\text{screen}}(\alpha,N,\lambda,\sigma)+\epsilon_{\text{PMixED}}(\alpha,\beta ,N,D,\mathbf{x}),&D_{\alpha}^{\leftrightarrow}(\overline{p}_{\text{priv}}( \mathbf{x})||p_{0}(\mathbf{x}))\leq T\\ \epsilon_{\text{screen}}(\alpha,N,\lambda,\sigma),&\text{otherwise}\end{cases}$ $$

Proof. Since noisy screening is always performed, the privacy loss increases by $\epsilon_{\text{screen}}(\alpha,N,\lambda,\sigma)$. If the condition $D_{\alpha}^{\leftrightarrow}(\overline{p}_{\text{priv}}(\mathbf{x})||p_{0}(
\mathbf{x}))\leq T$ is met, then the next token is sampled via PMixED, with privacy loss $\epsilon_{\text{PMixED}}(\alpha,\beta,N,D,\mathbf{x})$ from Eq. 3. So by the composition property of RDP A.2, the privacy loss will also increase by $\epsilon_{\text{PMixED}}(\alpha,\beta,N,D,\mathbf{x})$. Otherwise, the next token is sampled purely from the public distribution, hence, no further privacy is lost.

###### Theorem D.3 .

Let $\lambda_{i,t}$ denote the mixing parameter of model $i$ at query $t$ that was produced by AdaPMixED, $\mathbf{\lambda}^{*}=J_{N,T}$ where $J$ is the $N\times T$ all-ones matrix, and $\textstyle\mathcal{L}(\mathbf{x},\mathbf{\lambda})=-\frac{1}{T}\sum_{t=1}^{T}
\log\sum_{i=1}^{N}[\lambda_{i,t}p_{i}(x_{t}|\mathbf{x}_{t})+(1-\lambda_{i,t})p
_{0}(x_{t}|\mathbf{x}_{t})]/N$ be the negative log-likelihood function. For any $T,N>0$ we have the following:

$$ $\mathcal{L}\left(\mathbf{x},\mathbf{\lambda}\right)-\mathcal{L}\left(\mathbf{x },\mathbf{\lambda}^{*}\right)\leq\max_{t\in[T]}\max_{j\in[N]}\left\{(1-\lambda _{j,t})\log\left(\frac{p_{j}(x_{t}|\mathbf{x}_{t})}{p_{0}(x_{t}|\mathbf{x}_{t} )}\right)\right\}.$ $$

Proof. Working through the negative log-likelihood loss, we get the following:

$$ $\displaystyle\mathcal{L}(\mathbf{x},\mathbf{\lambda})-\mathcal{L}(\mathbf{x}, \mathbf{\lambda}^{*})$ $\displaystyle=\left[-\frac{1}{T}\sum_{t=1}^{T}\log\frac{1}{N}\sum_{i=1}^{N}( \lambda_{i,t}p_{i}(x_{t}|\mathbf{x}_{t-1})+(1-\lambda_{i,t})p_{0}(x_{t}| \mathbf{x}_{t-1}))\right]$ $\displaystyle-\left[-\frac{1}{T}\sum_{t=1}^{T}\log\frac{1}{N}\sum_{i=1}^{N}(p_ {i}(x_{t}|\mathbf{x}_{t-1}))\right]$ $\displaystyle\leq\max_{1\leq t\leq T}\max_{1\leq j\leq N}\log p_{j}(x_{t}| \mathbf{x}_{t-1})-\log(\lambda_{j,t}p_{j}(x_{t}|\mathbf{x}_{t-1})+(1-\lambda_{ j,t})p_{0}(x_{t}|\mathbf{x}_{t-1}))$ $\displaystyle\leq\max_{1\leq t\leq T}\max_{1\leq j\leq N}\log p_{j}(x_{t}| \mathbf{x}_{t-1})-\lambda_{j,t}\log(p_{j}(x_{t}|\mathbf{x}_{t-1}))-(1-\lambda_ {j,t})\log(p_{0}(x_{t}|\mathbf{x}_{t-1}))$ (14) $\displaystyle=\max_{1\leq t\leq T}\max_{1\leq j\leq N}(1-\lambda_{j,t})\log \left(\frac{p_{j}(x_{t}|\mathbf{x}_{t-1})}{p_{0}(x_{t}|\mathbf{x}_{t-1})}\right)$ $$

where Eq. 14 is from concavity of logarithm. Hence proves the Theorem. ∎

###### Theorem D.1 .

###### Theorem D.2 .

###### Theorem D.3 .

## Appendix E Additional Experimental Setup Details

**Table 3: Privacy parameters used in the main results for WikiText-103^(1) and One Billion World^(2).**
| Dataset | Method | Epochs | Learning<br>Rate | Weight<br>Decay | Adaptation<br>$r$ | LoRA<br>$\alpha$ | DP Batch<br>Size | Clipping<br>Norm |
| --- | --- | --- | --- | --- | --- | --- | --- | --- |
| WikiText-103 | AdaPMixED | 15 | 2e-4 | 0.01 | 4 | 32 | - | - |
| DP-SGD | 20 | 2e-4 | 0.01 | 4 | 32 | 256 | 1.0 |  |
| One Billion<br>Word | AdaPMixED | 5 | 2e-4 | 0.01 | 4 | 32 | - | - |
| DP-SGD | 9 | 2e-4 | 0.01 | 4 | 32 | 256 | 1.0 |  |
| PubMed | AdaPMixED | 5 | 2e-4 | 0.01 | 4 | 32 | - | - |
| DP-SGD | 5 | 2e-4 | 0.01 | 4 | 32 | 256 | 1.0 |  |
| Air Dialogue | AdaPMixED | 10 | 4e-4 | 0.01 | 4 | 32 | - | - |
| DP-SGD | 10 | 4e-4 | 0.01 | 4 | 32 | 256 | 1.0 |  |

**Table 4: Privacy parameters used in the main results for WikiText-103^(1) and One Billion World^(2).**
| Dataset | $\alpha$ | $\beta$ | $N$ | $\sigma$ | $\lambda$ | $T$ | Top-$k$ |
| --- | --- | --- | --- | --- | --- | --- | --- |
| WikiText-103 | $18$ | $0.2$ | $100$ | $1\times 10^{-2}$ | $1\times 10^{-4}$ | $4.5$ | $60$ |
| One Billion Word | $18$ | $0.2$ | $80$ | $1\times 10^{-2}$ | $1\times 10^{-4}$ | $4.5$ | $60$ |
| PubMed | $15$ | $0.3$ | $100$ | $1\times 10^{-1}$ | $1\times 10^{-3}$ | $4.5$ | $60$ |
| Air Dialogue | $15$ | $0.3$ | $100$ | $1\times 10^{-2}$ | $1\times 10^{-4}$ | $4.5$ | $60$ |

Training hyperparameters values used can be found in Table 3, and the prediction hyperparameters used for AdaPMixED can be found in Table 4. Each dataset was split into sequences of length 512 tokens. Our code uses existing code from the original PMixED paper Flemings et al. (), which is licensed by the Apache-2.0 license. We follow the terms and conditions. Our setup also follows from PMixED: certain hyperparameter values for non-private fine-tuning were selected from Hu et al. (), and certain hyperparameter values for private fine-tuning from Yu et al. (). We employed the AdamW optimizer with weight decay $0.01$ and a linear learning rate scheduler.

## Appendix F Limitations

We discuss the limitations of our proposed framework. The first is that the privacy loss of AdaPMixED is data-dependent and, hence, can leak privacy if released. However, one could follow the privacy loss sanitation technique from Papernot et al. () to privately release the privacy loss. The second limitation comes from the original PMixED framework, which incurs and additional inference latency due to obtaining predictions from an ensemble and calculating the mixing parameters $\lambda_{i}$. We also acknowledge that storing an ensemble of LLMs incurs additional storage costs, although we do employ LoRA Hu et al. () to further reduce this cost. But because we do not use DP-SGD, per-example gradients do not need to be stored and ML accelerated hardware is fully utilized, thereby gaining systems performance in terms of memory and runtime. Moreover, although we showed that AdaPMixED can handle large inference loads, one advantage of DP-SGD is that it can handle an infinite number of inferences due to the post-processing theorem. Lastly, the use of a public model is not necessarily risk-free in terms of privacy Carlini et al. (), and thus caution is advised to further understand the privacy risks of pre-trained LLMs.

## Peer Reviews

confidence: 3
contribution: 2
initial_rating: 5
presentation: 3
questions: * I think this is more up to date with regards to tight bounds for DPSGD : https://www.usenix.org/system/files/usenixsecurity23-nasr.pdf 
“We design an improved auditing scheme that yields tight privacy estimates for natural (not adversarially crafted) datasets—if the adversary can see all model updates during training”
* Can you compare for something - create private labels using this method, then train non-privately on those private labels? In order to produce a model that you can ask infinite # of queries. This is what PATE (https://arxiv.org/abs/1802.08908) does, and how it differs from CaPC  (https://arxiv.org/abs/2102.05188).

* For the empirical work, why can’t you fix epsilon? Having variable number of queries answered, privacy loss, and PPL changing makes it hard to compare. In PATE methods they tend to compare apples-to-apples, (specifically  epsilon versus label-count versus label accuracy);  like this one : https://arxiv.org/pdf/2202.10517, which isn't relevant in the specific algorithm, but rather in the presentation of epsilon versus label-count versus label accuracy. 

* Did you try varying `N` partitions? In PATE this ends up being quite important.

* Do you have an assessment of how different the finetuning datasets are from the original model? The degree of dataset-similarity here matters a lot for the performance of DP finetuning algos, though in your defense you are comparing against other methods. Still it would be good to quantify this a bit better.


Overall, it seems like a good paper, but I’d like to see the algorithmic contributions to be a bit more explicitly stated in the context of existing work, and I’d like the empirical experiments to be more clearly showing their contribution.
soundness: 3
strengths: Reasonably Novel idea, that reintroduces work from PATE which was largely overlooked. Well structured and the problem is well introduced. See Questions.
summary: To address the limitations of differentially private (DP) training for LLMs, Adaptive PMixED (APMixED) is introduced as a private decoding framework that adapts to the divergence between private and public model outputs. It includes mechanisms to screen high-risk queries and calculate data-dependent privacy loss, achieving practical scalability and strong utility. Experimental results show that APMixED enables up to 100K predictions with reasonable privacy loss, outperforming traditional methods.
weaknesses: I think that the general framing of the paper is good, but more work can be done to clarify the specific contributions and algorithms of the paper. For example, I was a bit confused by what the noisy screening method concretely is. Why is it not sparse vector, or confident-GNmax for PATE? Perhaps I missed something but it feels the algorithm could be more clearly specified.  See Questions.

---

confidence: 3
contribution: 2
initial_rating: 5
presentation: 3
questions: - Is the public model the original pretrained GPT2? How do you make sure that the public model training data does not intersect with the 4 datasets in the experiment? E.g. wikipedia seems to be a rather common pretraining dataset for most public models.
- For the ablation study in Section 5, which dataset is it performed on? How does the optimal hyperparameters change with the underlying dataset?
soundness: 2
strengths: - The paper is well-written and the evaluation includes comparing AdaPMixED with other DP methods across different datasets. The results demonstrated large privacy gains while maintaining utility, especially in high-query situations.
- The proposed method is clearly explained and simple to implement, making the previous approach PMixED more practical.
summary: This paper introduces AdaPMixED, an algorithm for differentially private (DP) next-token prediction that builds on PMixED which was introduced previously. AdaPMixED improves the practicability of PMixED, where knowing the number of queries beforehand is less likely, by dynamically adapting the privacy level based on the divergence between public and private model outputs. Specifically, AdaPMixED introduces a noisy screening mechanism to filter out queries that might incur high privacy loss, and it performs a data-dependent privacy analysis to assess and adjust privacy loss per query. Experimental results show that AdaPMixED significantly reduces privacy loss compared to PMixED while retaining strong model utility, especially in high-query scenarios.
weaknesses: - The novelty is somewhat limited where it seems like only the noise screen filtering mechanism is original. The data dependent privacy analysis is an application of an existing approach to PMixED. Though the authors emphasized the importance of noise screen filtering, from the results in Table 2, majority of the privacy loss gain comes from data dependent privacy analysis.
- The model used in experiments (GPT2) seems a bit outdated, it is unclear how the privacy and utility trade-off really look like for the more recent LLMs.
- Experiment details can be explained more, e.g. how is the dataset partitioned and what is used as the public model. I understand that the setup is rather similar to the prior work PMixED but the paper should be self-contained without needing to check another paper for the setup. Some minor detailed results are missing in table 1, e.g. PMixED results are not shown for PubMed and Air Dialogue.

---

confidence: 3
contribution: 3
initial_rating: 6
presentation: 3
questions: Refers to the weakness.
soundness: 3
strengths: The author introduced several important advantages of AdaPMixED in the field of privacy protection LLM. First, AdaPMixED is highly scalable and capable of handling up to 100,000 queries with little impact on privacy and utility, which is a significant improvement over both PMixED and traditional DP methods. This makes it ideal for practical applications where MLaaS is widely used. Furthermore, this method significantly reduces privacy loss by dynamically adjusting privacy parameters based on real-time output distribution analysis. This not only saves the privacy budget but also ensures that the model’s usefulness is preserved, as evidenced by lower perplexity scores in the next token prediction task compared to other methods.
summary: The authors explore the challenges of privacy preservation in large language models (LLMs), which are typically deployed via APIs by machine learning as a service (MLaaS) providers. Traditional privacy-preserving methods, such as Differential Privacy (DP) using DP-SGD, often incur significant computational costs, and the increased noise due to privacy preservation can negatively impact the model's utility. The Private Ensemble Distribution Hybrid (PMixED) approach improves utility by mixing the output distributions of private and public models without adding noise, but it suffers from inflexible privacy constraints and does not scale well as the number of queries increases. To overcome these limitations, the authors introduce Adaptive PMixED (AdaPMixED), which dynamically optimizes the trade-off between privacy and utility based on the difference between the private and public output distributions of each query. This approach includes a novel noise filtering mechanism that filters out high-risk queries, as well as data-based privacy loss analysis, allowing for more efficient use of privacy budgets. Experiments show that AdaPMixED significantly reduces privacy loss (up to 16x compared to PMixED) while maintaining or enhancing model utility across a variety of datasets.
weaknesses: In my opinion, a key weakness of the AdaPMixED framework is its handling of situations where there are large divergences between private and public model outputs. In this case, the system defaults to using the output of the public model to reduce privacy risks. However, this situation illustrates that the output of private models is very important and should not be ignored. For example, the private model may provide personalized output that the public model alone cannot provide.

Furthermore, the authors primarily considered real-world usage, but the complexity of AdaPMixED may hinder its practical deployment, especially in MLaaS environments where throughput and latency are critical. The multiple decision-making layers involved in AdaPMixED, from divergent evaluation to dynamic output adjustment, can significantly increase the computational overhead. This complexity can reduce the efficiency of the system, especially under high load conditions typical in MLaaS environments. The authors could add some experiments on the trade-offs between throughput and privacy utility advantages provided by AdaPMixED.

---

confidence: 3
contribution: 3
initial_rating: 3
presentation: 4
questions: - Is there any reason why you did not analyze a sanitized version of the data-dependent privacy loss, e.g., with smooth sensitivity? I understand that there might be technical difficulties, or that smooth sensitivity could erase the gains from the data-dependent analysis. But this is a vital point in my opinion, without which it is simply not possible to compare with data-independent baselines.
- Have you considered using privacy odometers? They seem well-suited for your motivation, allowing an analyst to stop a computation adaptively and measure their privacy loss. Maybe all you need is an odometer with PMixED? If not, it could be helpful to justify why data-dependent loss is the only way forward for adaptivity.
- The noisy screening mechanism might be a good fit for the sparse vector technique, depending on how often we expect queries to skip the private ensemble.
soundness: 2
strengths: Main strengths:
- The privacy-utility improvements of AdaPMixED can be particularly significant, because they show that next-token prediction can be practical, compared to well-studied alternatives like DP-SGD. I was personally not aware of the PMixED line of work, and I used to consider that next-token was a dead-end in terms of DP, since privacy loss accumulates with the number of queries. It turns out that mixing public predictions with private predictions, along with a careful privacy analysis, allows such DP APIs to support pretty credible workloads (100K queries for single-digit data-dependent epsilon, whereas previous work only evaluated up to 1K queries). This is a welcome development, and I appreciate the authors' work in this important direction.
- Supporting adaptive workloads is critical, and often overlooked in the DP literature (as the authors note when referring to Dwork & Feldman). The key idea to remove the non-adaptivity limitation from PMixED is to use a data-dependent privacy loss.
- The utility results are novel and useful (Thm 4.3). 

Other strengths:
- The noise-screening mechanism is original and not present in PMixED. I am hesitant to consider this technique (and Thm 4.1) as a particularly significant new result, even though the paper claims this is one of its three contributions. The adaptation seems pretty straightforward: it does not involve data-dependent loss, only some post-processing, a sensitivity calculation and a Gaussian mechanism. It can still be nice technique if it comes with experimental gains. 
- The privacy loss breakdown in Tab 2b was useful.

Thank you for this paper, I learned a lot about private next-token prediction!
summary: The paper focuses on privacy-preserving LLMs, where the end goal is to allow untrusted parties to interact with an LLM that has been fine-tuned on a private dataset, while protecting the private dataset with differential privacy (DP). DP next-token prediction is one way of achieving this goal, which has been overlooked compared to alternatives such as DP training and fine-tuning, but is becoming increasingly relevant as most LLMs are accessed through APIs.

The paper builds on PMixED, a preexisting DP next-token prediction algorithm that mixes private next-token distributions with a public distribution, to introduce AdaPMixED. AdaPMixED uses a data-dependent privacy loss, which allows an analyst to adaptively check the privacy loss consumed so far, unlike PMixED where the privacy loss and the total number of tokens have to be fixed upfront. AdaPMixED also introduces a noisy screening mechanism, which saves privacy by routing certain queries to a public model when the private model will not help. 

AdaPMixED is evaluated on four datasets (adding two datasets not evaluated by PMixED) with pretrained GPT-2 models. It achieves lower perplexity than other baselines (PMixED, DP-SGD, public model) for a significantly lower (but data-dependent!) privacy loss. This allows AdaPMixED to answer massively more queries than PMixED, which is critical to make DP next-token prediction scale and provide a credible alternative to DP training.
weaknesses: Data-dependent loss
- The data-dependent loss is a major flaw of this paper in my opinion, and the reason for my overall "reject" score. I am willing to change my score if I can be convinced that the current results are fair (maybe I misunderstood something), or with new results that incorporate a sanitized version of the data-dependent loss.
- My problem with data-dependent loss is that it can leak privacy, since it depends on the data (more specifically, it depends on the whole database passed to the DP mechanism). This does not satisfy the standard DP definition, and therefore one should not treat data-dependent epsilons and data-independent epsilons the same way. Yet, this is exactly what Table 1 is doing, by listing the "privacy loss epsilon" for DP-SGD and PMixED (meaning data-independent, with strong guarantees) and AdaPMixED (meaning data-dependent, with weak semantics) in the same table. This is simply not an apples-to-apples comparison, and any claim using this table to argue that AdaPMixED outperforms the data-independent baselines is misleading. 
- The paper does acknowledge the privacy risks of data-dependent loss. But at the very least the epsilon values should then come with a clear disclaimer in the Table and summary of the results in the conclusion, or even a different notation such as $\epsilon_{data-dependent}$. This is not the case in the paper.
- The paper mentions that "one can sanitize the privacy loss via smooth sensitivity analysis, similar to Papernot et al. (2018), if the privacy loss needs to be released." This is such a crucial point. I don't think the paper can possibly afford to put this off to future work. The key results in the evaluation do release privacy loss, and without this there is no apples-to-apples comparison with data-independent baselines. 


Noisy screening: 
- The tradeoff evaluated in 5.3 seems pretty small. I agree that saving privacy loss is valuable, and barely changes perplexity, but the savings don't seem to be very significant. Also, I am worried that the results are falling within the uncertainty due to experimental randomness (e.g., Section 5.3 analyzes a 0.08 or 0.33 PPL decrease, but Table 1 has confidence intervals of at least 4 PPL). I think that more experiments are needed to evaluate a proper tradeoff curve with x=privacy loss and y=perplexity as the noisy screening changes, with the average of multiple runs. 
- Fig 2e) attempts to do that, but it is hard to interpret since it involves 4 parameters, the values barely change, and there is no clear trend. 
- Overall, it seems that noisy screening has a pretty limited impact (or at least the evaluation doesn't show clear and significant trends). This makes me doubt the importance of what is supposed to be a major contribution of the paper.

Other weaknesses and minor comments:
- The Fig 2 axis are a bit misleading, the scale should probably be fixed across all 6 experiments, if we want to compare the relative importance of different methods.
- Alg. 1 is hard to parse, having some comments or headings (e.g., "Noisy screening") would be helpful.
- PMixED has been published, you could use this reference instead of the arXiv preprint: https://aclanthology.org/2024.naacl-long.247.pdf
 - While 100K queries (where one query is one next-token prediction) is a massive improvement over previous next-token prediction work, this is only practical for a limited class of workloads. For instance, that would represent around 10 short answers (100 to 1000 tokens) per day for a few weeks on a corporate or medical dataset. Once the budget is exhausted, it's time to fine-tune the private LLMs on fresh data, which might be pretty scarce if it's only been a few weeks since the previous round of fine-tuning. This is not a limitation of the paper,  given the improvements over prior work, but it could still be interesting to discuss such practical implications.