Hot PATE: Private Aggregation of Distributions for Diverse Tasks

## Abstract

Abstract The Private Aggregation of Teacher Ensembles (PATE) framework is a versatile approach to privacy-preserving machine learning. In PATE, teacher models that are not privacy-preserving are trained on distinct portions of sensitive data. Privacy-preserving knowledge transfer to a student model is then facilitated by privately aggregating teachers’ predictions on new examples.
Employing PATE with generative auto-regressive models presents both challenges and opportunities. These models excel in open ended diverse (aka hot) tasks with multiple valid responses. Moreover, the knowledge of models is often encapsulated in the response distribution itself and preserving this diversity is critical for fluid and effective knowledge transfer from teachers to student. In all prior designs, higher diversity resulted in lower teacher agreement and thus – a tradeoff between diversity and privacy. Prior works with PATE thus focused on non-diverse settings or limiting diversity to improve utility.
We propose hot PATE , a design tailored for the diverse setting. In hot PATE, each teacher model produces a response distribution that can be highly diverse. We mathematically model the notion of preserving diversity and propose an aggregation method, coordinated ensembles , that preserves privacy and transfers diversity with no penalty to privacy or efficiency. We demonstrate empirically the benefits of hot PATE for in-context learning via prompts and potential to unleash more of the capabilities of generative models.

## 1 Introduction

Generative AI models, such as large language models (LLMs), are incredibly powerful tools that can be fine-tuned for specific contexts, even without explicit supervision Radford et al. (); Brown et al. ().
Generative models diverge from conventional machine learning models in that they support open ended, *diverse* tasks, where there are multiple appropriate responses, and this very flexibility is essential for much of their functionality.
Diversity is typically tuned via a temperature parameter in the softmax, with higher temperature yielding higher entropy (more diverse responses).
Furthermore, when evaluating the coverage or extracting knowledge from a trained model, such as for distillation tasks, the conventional approach involves querying the model on a prepared (sampled or curated) test set of examples. However, with generative AI models, the knowledge coverage on a specific domain is often encapsulated by the output distribution itself to a general instruction as part of a *prompt* to the model, and can be evaluated or retrieved by sampling this distribution.

Frequently there is a need to train models or fine-tune publicly-available foundation models using sensitive data such as medical records, incident reports, or email messages.
In this case, privacy must be preserved in the process.
Specifically, we consider the strong mathematical guarantees of differential privacy (DP) Dwork et al. (). An
approach that achieves privacy by modifying the training process is DPSGD Abadi et al. (), where noise is added to clipped gradient updates. DPSGD can also be applied with fine tuning Yu et al. (); Duan et al. (). An alternative approach to private learning, that only relies on black box training and use of models that are not privacy-preserving, is the Private Aggregation of Teacher Ensembles (PATE) paradigm Papernot et al. (); Bassily et al. (); Papernot et al. (). PATE follows
the “sample and aggregate” method of Nissim et al. (). We describe the basic workflow which we refer to here as *cold* PATE.

Cold PATE
1.
Partition the sensitive dataset $D$ into $n$ parts
$D=D_{1}\sqcup\dots\sqcup D_{n}$. For $i\in[n]$, train a *teacher* model $M_{i}$ on data $D_{i}$.
2.
Sample public unlabeled examples. For each such example $x$ do:
•
For each teacher $i\in[n]$, apply $M_{i}$ to $x$ and
obtain a label $y_{i}:=M_{i}(x)\in V$.
•
Compute
the frequencies for $j\in V$:
$c_{j}=\sum_{i\in[n]}\mathbbm{1}\{y_{i}=j\}\ .$
(1)
•
DP aggregate the histogram $\boldsymbol{c}\mapsto y$ to obtain a single label $y\in V$ (or abort if there is insufficient agreement).
3.
Use the newly labeled privacy-preserving examples $\{(x,y)\}$ to train a student model.

The requirement of differential privacy is that the output distribution is stable to change of a single data point.
In the PATE framework for each example each teacher contributes a single vote. Therefore the resulting histogram is stable to a change of one data point: At most one teacher, the one trained on this data point, is affected. Therefore, when one entry in $D$ changes, at most one teacher changes its vote, and thus at most two frequency values $c_{j}$ may change and by at most $1$. A noisy maximizer of the histogram is therefore privacy preserving.

The limitations of cold PATE are (i) its formulation for classification-like tasks, where each example $x$ has a single ground-truth label $y\in V$,
and (ii) the need for a source of unlabeled non-private training examples to facilitate the knowledge transfer to the student. This is unsatisfactory because
generative AI models support tasks with responses that are diverse and open ended. Moreover, knowledge is encapsulated in the diversity of the response distribution and there is a promise of transferring knowledge to the student in a more fluid way.
We thus ask the following question:

> *Can we design a version of PATE that is effective for diverse and open-ended tasks and unleashes more of the capabilities of generative models?*

#### Application for in-context learning

One motivation for our study is the effectiveness of in-context learning via *prompts*. A prompt is an engineered prefix with a task that is given to the base model. Prompts can include specific instructions and/or a set of *shots* (scenario exemplars).
Prompts are appealing for multiple reasons: A small number of shots Liu et al. ()
often outperform tailored trained models Zhou et al. (); Garg et al. (). Prompting is efficient, as it is simply inference – there is no need for parameter updates. Finally, prompts only requires API access to the model, which is important given the trend towards proprietary models.

When our data is sensitive, we would like the end product to be privacy-preserving.
Concretely, consider the task of generating a representative set of synthetic privacy-preserving data records from a set of sensitive data records.
The sensitive records may include component that are identifying and components that are shared with many other records. A privacy-preserving aggregation ensures that the synthetic records do not include identifying information. Additionally, it is essential to *preserve diversity* in order to ensure coverage, that is, that our set of synthetic records is indeed representative.
The synthetic records that are generated can then be used to train a student model that is not necessarily generative or to construct a privacy-preserving student prompts for downstream tasks.
The latter allows for harnessing the ability of generative models to generalize from few shots.

We seek a PATE mechanism that supports the following. Each teacher is assigned a disjoint subset of sensitive data records. These data records are used to construct a prompt that also includes an instruction of the form “generate a representative data record given this examples set of data records.”
Each teacher then has its own distribution on responses.
By repeating multiple times we can obtain different samples that are a representative set of shots. We then hope to aggregate responses of different teachers in a way that preserves both diversity and privacy.

This design is appealing as there is little cost to scaling up the number of teachers: Each teacher is simply a prompted base model and there is no need for training or significant storage. Prompts are inexpensive, the current OpenAI API supports $10^{5}$ context/output tokens for US$5-$10 OpenAI ().
The bottleneck to scaling up is thus the amount of available sensitive data. Scaling up can be highly beneficial because generally with DP aggregation, the number of queries we can support for a given privacy budget grows quadratically with the number of teachers.

#### Diversity-privacy tradeoff:

An issue that arises when applying cold PATE with high diversity is that utility rapidly deteriorates with diversity. To see this, assume there are $r$ good responses with equal probabilities. Note that higher $r$ means more diversity. The $n$ teachers votes would then be split with $\approx n/r$ teacher votes per option. This lower agreement means that in order to return any of the answers we must use privacy noise of scale $\sigma<n/r$. This inverse dependence of noise with $r$ means the privacy loss must increase with $r$. We can attempt to remedy this via some tie-breaking
(e.g., each teacher selects a response in the top-$k$ with the largest index).
This does result in high agreement but we lose the diversity in the output that is needed to facilitate a fluid knowledge transfer. Prior and concurrent works Tian et al. (); Wu et al. () attempted to address this issue by limiting the diversity (see discussion in Section 1.1).

### Overview of Contributions and Roadmap

In this work we propose *hot PATE*, described in Section 2. The framework is suitable for auto-regressive models and diverse and open ended tasks, where the appropriate response is a sample from a distribution.
With hot PATE, each teacher $i\in[n]$ at each step computes a “next token” distribution $\boldsymbol{p}^{(i)}$ over tokens $V$. These distributions are aggregated so that the response token from the ensemble is sampled from that aggregate distribution. The heart of our design is an aggregation method that preserves privacy and critically also the diversity of the teachers distributions. Our primary technical contribution is formalizing this requirement and designing aggregation methods where there is *no penalty* with increased diversity.

Figure: Figure 1: Illustration of two sets of probability distribution. Each distribution is a rectangle with the red portion representing the probability of token $j$. The left set corresponds to high teachers’ support for low probability $q$. The right set to low teachers’ support for high $q$. The probability of the token $j$ in the average distribution is the same in both cases.
Refer to caption: extracted/5600004/plots/lowhighsupport.png

In Section 3 we motivate and formalize a definition of *preserving diversity* that allows for knowledge transfer that is compatible with limitations imposed by privacy.
A natural diversity-preserving approach is for
each teacher $i\in[n]$ to contribute a token $y_{i}$ sampled independently from $\boldsymbol{p}^{(i)}$. We refer to this as *independent ensemble*. The resulting vote histogram is what would be produced by cold PATE Papernot et al. (, ); Duan et al. () when applied in a diverse setting. The histogram can then be DP aggregated to produce a response token. The privacy loss depends on the frequency (count) of the response token. With independent samples this count is concentrated around the *average* probability of the token across teachers. This probability is smaller when there is high diversity. Therefore, independent ensembles as an intermediate step
inherently result in privacy guarantees that sharply deteriorates with the diversity of teacher distributions.
We argue that this higher privacy noise may or may not be necessary, and this depends on information that is lost by independent ensembles.
The frequency histograms produced by independent ensembles approximate the average of the teachers’ distributions. The issue, as depicted in Figure 1, is that averaging loses a critical distinction between high teachers’ support with low probability $q$ (which we can hope to transfer in a privacy-preserving manner) and low support with high $q$ (which can not be transferred in a privacy-preserving manner). We propose a definition of preserving diversity which makes this important distinction: A token is required to be transferred to the aggregate only when there is sufficient teachers’ support.
Informally, for a robustness parameter $\tau\in[n]$, there are two requirements:

- •
(transfer requirement)
Any token that has probability at least $q>0$ (no matter how small) across $c$ teachers where $c\geq\tau$, is “transferred” in that it has probability $\Omega(qc/n)$ in the aggregate distribution.
- •
(relevance requirement)
We do not transfer irrelevant tokens, that is, for any token $j$, its probability in the aggregate distribution is not much higher than its average probability in the teacher distributions.

In Section 4 we propose *ensemble coordination*.
A coordinated ensemble samples a shared randomness and based on that, each teacher $i$ contributes a token $y_{i}$. The marginal distribution of each $y_{i}$ is $\boldsymbol{p}^{(i)}$, same as with independent ensemble. But the difference is that teachers votes are maximally positively correlated. The frequency $c_{j}$ of token $j$ has high spread and in particular can (roughly) be $\Omega(\tau)$ with probability $\Omega(q)$. This property facilitates DP aggregation with no penalty for diversity.
With coordinated ensembles, two teachers with very diverse distributions that have a small total variation distance produce the same token with probability that depends the distance. In particular, when the distributions are equal (the distance is 0 0), the same token would be produced.

In Section 5 we empirically demonstrate the properties and benefits of ensemble coordination for in-context learning via prompts on the Llama 3 language model lla (). We evaluate the coverage and diversity of aggregate distribution formed by only transferring frequency counts that exceed a threshold $T$. We observe an order of magnitude improvement over the baseline of independent ensembles in terms of the value of $T$ (privacy noise scale) needed to achieve a certain coverage and in terms of diversity of the aggregate.

In Section 6
we present DP aggregation schemes that are applied to frequency histograms generated by coordinated ensembles and return a token. We establish that the end-to-end process preserves diversity.
We distinguish between two use scenarios of applications with
*homogeneous* or *heterogeneous* ensembles (see Figure 2).
Homogeneous ensembles are formed by randomly partitioning a sufficient number of data records among teachers. The assumption then is the same as with cold PATE – most teachers possess the core knowledge we wish to transfer (see Figure 3 (A)). In this case it suffices to require diversity preservation with large support $\tau=\Omega(n)$ and the aggregation can simply return a (noisy) maximizer of the histogram. Heterogeneous ensembles may arise when each teacher is an agent of one or few users. In this case, we want to preserve diversity both within and across teachers and allow smaller groups of teachers to support each transfer, that is, set a smaller $\tau$ (see Figure 3 (B)). In this case, a diversity-preserving aggregate is a weighted sample from the histogram.

Finally, in Sections A and B
we explore privacy analysis methods that are data dependent and can increase the number of queries processed for a given privacy budget by orders of magnitude. In particular, for token-by-token text generation there are many steps and the cost of naive DP composition is prohibitive. What makes the approach feasible is that many of the steps have high agreement (similar teacher distributions where coordinated ensembles generate high agreement histograms). With data dependent analysis, steps with high agreement (or no agreement) can be essentially free. Moreover, with heterogeneous ensembles we can charge teachers individually only for steps in which the teacher contribute to the final token Hassidim et al. (); Cohen and Lyu ().

Figure: Figure 2: Ensemble types for Hot Pate. In homogeneous ensembles each teacher gets a representative part of the data. In heterogeneous ensembles each teacher has the data of one or few users.
Refer to caption: extracted/5600004/plots/hotPATE_teachers.png

Figure: Figure 3: Illustrating the distinction between diversity that is within teachers (where coordinated ensembles form high agreement and a higher $\tau$ suffices) and diversity across teachers (coordinated ensembles reflect it and require lower $\tau$). Diversity due to semantic similarity or knowledge encapsulated in the base model or few exemplars has a “within” pattern. Diversity that results from private information or data available to few teachers has an “across” pattern.
Refer to caption: extracted/5600004/plots/diversityacrosswithin.png

### 1.1 Related work

We place our contribution in the context of prior and concurrent works. The works we are aware of for PATE adaptations for text generation either (i) did not consider diversity or (ii) recognized it and the importance of transferring it but proposed aggregation schemes where utility decreases with diversity together with methods to limit diversity as to mitigate this perceived privacy-diversity trade-off.

Tian et al. () proposed a PATE extension for sequential text generation tasks in diverse settings. Their approach limited diversity: Average the teachers distributions and then truncate the tail by keeping only the top-$k$ frequencies. In our work, we demonstrate that averaging is not the right approach and propose a method that preserves diversity with no privacy cost.
Recent prior work explored adaptations of PATE for in-context learning via prompting.

Duan et al. () proposed to use each part $D_{i}$ of the data to create a text prompt $T_{i}$. The ensemble is then used to label curated queries. But while some design elements were tailored to LLMs, the workflow and privacy analysis were identical to old PATE Papernot et al. (), and in particular, did not consider diverse responses.

Wu et al. () proposed approaches to private aggregation for in-context learning with diversity.
Their proposal were to reduce perceived diversity by clustering together outputs that are semantically equivalent and aggregating each cluster in a semantic space. This essentially reduces the dimensionality of the output space. The aim then is to extract and transfer this common semantics in a privacy preserving way: Map responses into a common low dimensional embedding space and privately aggregate embedding vectors or identify frequent keywords in diverse teachers’ responses.
The limitations are that the approach only addresses same-semantics diversity and offers no solution for semantically-distinct diverse responses and are subjected to a privacy diversity trade-off. Additionally and importantly, they require hand crafted tools to map and curate responses back and forth from a semantic space.
The regime of effectiveness depends on whether the same-semantic diversity is within or across teachers.
In the *across* variety (see Figure 3 (B)), the knowledge of each teacher only contains one or limited variations of the same semantic. In this case, the semantic space approach generates high agreement whereas coordinated ensembles would not. The two methods may be combined.
The *within* variety (see Figure 3 (A)) is handled effectively by our approach and can be transferred fluidly with no privacy loss and without the need to mitigate the diversity via additional engineering. We suspect that for the in-context learning use case, and for semantic similarity is captured by tools external to the model (such as an embedding), the diversity is anyhow encapsulated in the base model and present in each fine tuned-LLM teacher distribution. That is, we expect the diversity to overwhelmingly be the “within” variety.

Papernot et al. () (Appendix B.1) discussed using additional outputs (beyond just the noisy the maximizer) in the teachers’ votes histogram for distillation tasks. They concluded that it is beneficial for utility but does not justify the privacy loss. Despite the superficial resemblance, this is very different from what we do as we capture diversity in the generation of the histogram where we
“force” the teachers to agree but there is a distribution on the agreement token.

Finally, there are multiple innovative adaptations of PATE to non-categorical settings (aggregate vectors rather than labels) applied with generative models. The works we are aware of address different problems and use different techniques than hot PATE. For example, image generation using generative adversarial networks (GAN):
Jordon et al. () proposed to train
student discriminator using a cold-PATE like labeling approach.
Long et al. () proposed to train a student generator by aggregating the gradients produced by teachers discriminators.
Notably, this design does not require external generation of examples in order to facilitate transfer. Instead, it uses the built-in property of generators to produce examples from random strings, which parallels in some sense our premise in hot PATE that coverage is encapsulated in the diversity of the output.

## 2 Hot PATE

We use the term *tokens* for elements of the input and response strings. We denote the vocabulary of tokens by $V$.
For an input context (prompt) $T\in V^{*}$, a response sequence $R$ is generated sequentially token by token. Specifically, the next token at each step, is sampled from a probability distribution over $V$ that depends on the current context (concatenation of the prompt and response prefix) $T\cdot R$. The probabilities are computed from weights (logits)
$(w_{j})_{j\in V}$ produced at inference by the model and
a *temperature* parameter $t>0$, using
a softmax function:

$$ $p_{j}:=\frac{e^{w_{j}/t}}{\sum_{i\in V}e^{w_{i}/t}}\ .$ $$

In low temperatures, the highest weight token $\arg\max_{j}w_{j}$ has probability close to $1$. As we increase the temperature, the probability distribution flattens with similarly-weighted tokens having similar probabilities. *Cold* temperature is appropriate for classification-like tasks with one correct response and *hot* temperature is appropriate for diverse tasks. We therefore refer to the outlined PATE workflow as cold PATE and to our proposed workflow as hot PATE. Our design here is oblivious to the particular way the distribution is generated but seamlessly applies when it is diverse.

Figure: Figure 4: Hot PATE with an auto-regressive base model
Refer to caption: extracted/5600004/plots/HotPATE.png

Hot PATE (see illustration in Figure 4) partitions $D$ to disjoint parts $D_{i}$ ($i\in[n]$) and constructs a prompt $T_{i}$ from data part $D_{i}$.
We then generate a sanitized response sequence $R$ of tokens.
We initialize $R\leftarrow\{\}$ and proceed sequentially in
lockstep, by repeating the following:

- 1.
For $i\in[n]$:
Let $\boldsymbol{p}^{(i)}$ be the output
distribution over $V$ when querying the model with the prompt $T_{i}$<instruction to complete prefix>$R$.
- 2.
Apply a DP and diversity-preserving randomized aggregation $\mathcal{M}((\boldsymbol{p}^{(i)})_{i\in[n]})\mapsto y$, where $y\in V$.
- 3.
Concatenate $R\leftarrow R\cdot y$.

This design is open-ended and assumes that the instructions are effective in producing students prompts or components for such prompts, such as representative synthetic shots. This assumption aligns with the demonstrated and evolving capabilities of contemporary large language models, as well as the progress made in prompt engineering.
A necessary requirement with both cold and hot PATE is that a sufficient number of teachers possess the knowledge we wish to transfer. In both cases the ensemble’s purpose is to privately transfer that knowledge to the student.
A key distinction is that in the cold setting, knowledge coverage is
achieved by sampling or curating representative unlabeled examples from the same distribution. These examples are then labeled by the ensemble. In the hot setting, there is a promise of attaining coverage organically, through the broad range of diverse responses generated in response to one general instruction within the prompt.

The requirement of *preserving diversity*, that we will formalize in the sequel, is needed in order to facilitate this knowledge transfer.
At a high level, the objective is that the aggregate distribution, the output distribution of
$\mathcal{M}((\boldsymbol{p}^{(i)})_{i\in[n]})$, retains
the diversity of individual teacher distributions $(\boldsymbol{p}^{(i)})_{i\in[n]}$.

## 3 Private and diverse aggregation

Diversity and privacy appear to be conflicting in that
DP requires that the output token is supported by sufficiently many teachers, a “reporting threshold” that depends on the privacy parameter values. But preserving diversity means that tokens with low probability also need to be transferred to the student.

A natural candidate for preserving diversity is the
average teacher distribution
$\frac{1}{n}\sum_{i\in[n]}\boldsymbol{p}^{(i)}$. But this can not be privacy preserving because tokens that have positive probabilities with only one or few teachers are identifying and should not be released.
Fortunately, we can settle for a robust notion of preserving diversity. The premise in PATE is that the patterns of interest are captured by a sufficient number of teachers. Therefore, low probability across many teachers is something we care to transfer whereas high probability in few teachers, the “bad case” for privacy (and robustness), may not be something we have to transfer. The average distribution does not distinguish the two cases, so it is ruled out. We now formalize our nuanced diversity preservation notion:

###### Definition 1 (Diversity-preserving aggregation of distributions) .

Let $f(\boldsymbol{p}^{(i)})_{i\in[n]})\mapsto\boldsymbol{P}$ map from $n$ probability distributions over $V$ to a probability distribution over $V\cup\{\bot\}$.
We say that $f$ is *diversity-preserving* with $\tau\in\mathbbm{N}$, $\beta\in(0,1]$, $\gamma\geq 1$ if
for any input and $j\in V$

- 1.
For all $q\in[0,1]$,
$(c_{j,q}:=\sum_{i\in n}\mathbbm{1}\{p^{(i)}_{j}\geq q\})\geq\tau\implies P_{j}
\geq\beta\cdot\frac{c_{j,q}}{n}q\ .$
- 2.
$P_{j}\leq\gamma\frac{1}{n}\sum_{i\in[n]}p^{(i)}_{j}$

The first requirement is that probability $q$ across
enough ($\tau$) teachers, no matter how small is $q$, is transferred to the aggregate distribution. The second ensures that we do not output irrelevant tokens.

Requirements are stricter (and can be harder to satisfy) when $\beta$ and $\gamma$ are closer to $1$ and when $\tau$ is smaller.
A setting of $\tau=0$ and $\beta=\gamma=1$ allows only for the average distribution to be the aggregate. A larger $\tau$ increases robustness in that more teachers must support the transfer.

###### Remark 1 (failures) .

We allow $\bot$ (failure) in the support of the aggregate distribution because under the DP requirement there are input distributions (for example, those with disjoint supports, e.g. responses to instructions that ask for a patient ID) where no token can be returned.
Hot PATE has several options to work with failure responses: (i) The step can be repeated (different shared randomness may yield a token), (ii) a response token can instead be sampled from a non-private default prompt or model, or (iii) the prompt instructions can be redesigned.

###### Remark 2 (Setting of $\tau$ ) .

In *homogeneous ensembles*, most teachers receive a representative part of the data and possess the knowledge we wish to transfer. This occurs when we use a random partition so that most teachers obtain a representative set of data records. In this case, we aim to transfer the parts of the distributions that are common to most teachers and $\tau>n/2$ suffices.
In *heterogeneous ensembles*, each teacher might have data from one or very few “users.” This arises when each teacher has small capacity (prompts currently have limited size of 8k-64k tokens OpenAI ()) or when by design each teacher is an agent of a single user. In this situation, we aim to transfer parts of the distribution that are common to smaller subgroups of teachers and set $\tau\ll n$, possibly as low as permitted under the privacy requirement.

Before describing DP aggregation methods that satisfy
Definition 1, we instructively examine a scheme that can not satisfy the requirements, as it exhibits an inherent privacy-diversity tradeoff:
Sample independently $y_{i}\sim\boldsymbol{p}^{(i)}$ for each teacher $i\in[n]$, compute frequencies $c_{j}$ as in (1), and apply *any* DP aggregation to the histogram $\{(j,c_{j})\}$ (as with cold PATE).
Now consider the case of identical teacher distributions that are uniform over $k$ special tokens with probability $q=1/k$ each. From
Definition 1, each of the $k$ special tokens needs to be reported with probability at least $\beta/k$. But the frequencies $c_{j}$ of these tokens are concentrated around $c_{j}\approx n/k$. In terms of DP, each frequency value $c_{j}$ has sensitivity $1$ and for large enough $k$, the counts drop below the ”DP reporting threshold” of our privacy parameters and therefore none of these tokens can be reported.
To transfer these distributions through such a frequencies histogram we need to adjust the DP parameters to allow for reporting threshold to be below $n/k$, that is, to decrease proportionally to $k$.
We run into the same issue if we define our histogram with
$c_{j}:=\sum_{i}p^{(i)}_{j}$ (as proposed by Duan et al. ()).
The issue again is that the maximum frequency decreases with diversity ($k$).

The approach where each teacher contributes a sample, however, is appealing as it “factors out” the distributions: Instead of aggregating distributions, we work with a histogram of frequencies. With independent sampling, however, we arrived at a dead end – and it may appear as if we need to ditch the sampling approach all together.

Our proposed aggregation method, described in the next section, circumvents this difficulty.
The property is that
the frequency of a token in the histogram is not concentrated around its expectation. A tokens $j$ that broadly has a low probability $q$ will appear, sometimes, with very high frequency $c_{j}$ that does not depend on $q$. What does depend on $q$ is the probability of this event.
The probability of agreement between teachers depends on the variation distance between their distributions, but does not depend on how diverse they are.
This high agreement allows the token to pass with high “privacy noise.”

###### Definition 1 (Diversity-preserving aggregation of distributions) .

###### Remark 1 (failures) .

###### Remark 2 (Setting of τ 𝜏 \tau italic_τ ) .

## 4 Ensemble coordination

*Ensemble coordination*, described in Algorithm 1, is
a randomized mapping from a set of $n$ probability distributions over $V$ to a histogram over $V$ with total count $n$.
We sample shared randomness $\rho$.
For each teacher $i\in[n]$ we compute $y_{i}\in V$ that is a function of $\rho$ and $\boldsymbol{p}^{(i)}$.
We then compute the frequencies $c_{j}$ for $j\in V$, as in (1), and return the frequency histogram.

Figure: Algorithm 1 CoordinatedSamples

Ensemble coordination of responses to prompts can be implemented via an enhanced API access to the base model:

- •
The preferred approach with proprietary models is that the selection is done model-side: The shared randomness $\rho$ is provided as input along with each query prompt. The API then samples the returned token according to $\rho$.
- •
A different enhanced API would return the full distribution over tokens. Our demonstration in Section 5 using a public model AI@Meta () uses the full distribution. The current OpenAI text completion interface, which we used in a demonstration in Section C, returns the top five probabilities OpenAI ().
- •
The response distribution can also be approximated by repeated sampling of the model with the same prompt. This approach requires no API enhancements but would impact efficiency, since the number of samples required increases with diversity.

The sampling method in ensemble coordination is a classic technique called *coordinated sampling*, first introduced in statistics works in order to obtain samples that are stable under distribution shifts Kish and Scott (); Brewer et al. (); Saavedra (); Rosén (); Ohlsson (), and then in computer science works for computational efficiency via sampling-based sketches and a form of Locality Sensitive Hashing (LSH) Cohen (, ); Broder (); Indyk and Motwani (); Haas (). There are many applications including private learning Ghazi et al. ().

Similarly to independent ensembles, the marginal distribution of $y_{i}$ for each teacher $i$ is simply $\boldsymbol{p}^{(i)}$. Therefore, the expected frequency of token $j$ is

$$ $\mathsf{E}_{\rho}[c_{j}]=\sum_{i}p^{(i)}_{j}\ .$ (2) $$

The key difference is that votes of different teachers are highly positively correlated.
For two teacher distributions $i,k$, the probability of them having the same sample is the weighted Jaccard similarity of the distributions:

$$ $\Pr_{\rho}[y_{i}=y_{k}]=\frac{\sum_{j}\min\{p^{(i)}_{j},p^{(k)}_{j}\}}{\sum_{j }\max\{p^{(i)}_{j},p^{(k)}_{j}\}}$ $$

In particular, when two distributions are identical, the samples are the same $y_{i}=y_{k}$.

We establish that the respective requirements of Definition 1, diversity-transfer and relevance, can be satisfied by only selecting tokens that appear with high frequency in the histogram. We show
that a token
$j$ for which $m$ teachers $i$ have $p^{(i)}_{j}>q$ has frequency at least $m/2$ with probability at least $0.34q$. This follows by substituting $p=1/2$ in the following more general claim:

###### Lemma 1 (diversity transfer) .

For any token $j$ and $p,q\in[0,1]$,

$$ $\Pr_{\rho}\left[c_{j}\geq\left\lfloor p\cdot\sum_{i\in n}\mathbbm{1}\{p^{(i)}_ {j}\geq q\}\right\rfloor\right]\geq\frac{1}{2}\ln(1/p)q$ $$

###### Proof.

Let $i$ be such that $p^{(i)}_{j}\geq q$. Fix the sampled min value $x\sim\mathsf{Exp}[q]$ for $q$ part of the probability of $j$. The distribution of the remaining part is $y\sim\mathsf{Exp}[1-p^{(i)}_{j}]$ which is stochastically smaller than
$\mathsf{Exp}[1-q]$.
We get that

$$ $\displaystyle\Pr[y_{i}=j]$ $\displaystyle\geq\Pr_{y\sim\mathsf{Exp}[1-q]}[y>x]=e^{-x(1-q)}\ .$ $$

Fix $p\in[0,1)$. It follows that the probability
that $\Pr[y_{i}=j]$, conditioned on
$x<\frac{-\ln p}{1-q}$
is at least $e^{-x(1-q)}\geq p$.
The respective random variables $y_{i}$ on
different teachers that may share part of the distribution can only be nonnegatively correlated.
Therefore, if there are $c_{j,q}$ teachers with $p^{(i)}_{j}\geq q$ then the distribution of the number of teachers with $y_{i}=j$ is stochastically larger than $\mathsf{Bin}[e^{-x(1-q)},c_{j,q}]$, which for any
$x\leq\frac{-\ln p}{1-q}$ is stochastically larger than $\mathsf{Bin}[p,c_{j,q}]$.
The median of the Binomial distribution $\mathsf{Bin}[p,c_{j,q}]$
with probability at least $1/2$ is larger than $\lfloor pc_{j,q}\rfloor$. Therefore, with this conditioning on $x$,
there are at least $\lfloor pc_{j,q}\rfloor$ teachers with $y_{i}=j$.

$$ $\Pr_{(y_{i})_{i\in[n]}\mid x<\frac{-\ln p}{1-q}}[c_{j}\geq\lfloor pc_{j,q} \rfloor]\geq 1/2\ .$ (3) $$

The event $x<\frac{-\ln p}{1-q}$ occurs
with probability at least

$$ $\Pr_{x\sim\mathsf{Exp}[q]}[x<\frac{-\ln p}{1-q}]=1-e^{(\ln p)q/(1-q)}\geq-(\ln p )q\ .$ $$

Combining with (3), we obtain the claim in the statement of the Lemma.
∎

To establish relevance we show that high frequency must have a “backing.” The following is immediate
from (2) and Markov’s inequality (and is tight in the sense that for any $T$ there are distributions where equality holds):

###### Lemma 2 (relevance) .

For any token $j$ and $T$,

$$ $\Pr_{\rho}\left[c_{j}\geq T\right]\leq\frac{1}{T}\sum_{i\in[n]}p^{(i)}_{j}$ $$

Therefore, broadly speaking, it is possible to satisfy the requirements of
Definition 1 by reporting only tokens with frequency that is $\Omega(\tau)$, where $\tau$ is the required teachers support.
Our DP aggregation methods are presented in Section 6.

###### Remark 3 (Robust Average) .

In our empirical evaluation we compute the $\tau$-robust part of the average of the teachers distributions as an indication for what can be potentially privately transferred:

$$ $P_{j}(\tau):=\frac{1}{n}\sum_{i\in[n]}\min\left\{p^{(i)}_{j},(\{p^{(h)}_{j}\}_ {h\in[n]})_{(\tau)}\right\}\,\text{for $j\in V$}$ (4) $$

where $(\{p^{(h)}_{j}\}_{h\in[n]})_{(\tau)}$ is the $\tau$th largest probability of token $j$ in a teacher distribution.
Note that $(P_{j}(1))_{j\in V}$ is the average distribution and the values are non-increasing with $\tau$. We also consider the *$\tau$-robust probability mass* defined as $\sum_{j\in V}P_{j}(\tau)\leq 1$.

###### Lemma 1 (diversity transfer) .

###### Proof.

###### Lemma 2 (relevance) .

###### Remark 3 (Robust Average) .

## 5 Empirical demonstration

We demonstrate the properties of coordinated ensembles
using the Meta Llama 3 8B parameter open source language model lla (); AI@Meta ().
Additional results on the OpenAI GPT3.5 text completion interface OpenAI () are provided in Appendix C.

#### Generating Prompts:

We generated for each experiment $n=10^{4}$ text prompts (teachers) of the following form

> On planet Z, some numbers are edible. <name> from planet Z eats the following numbers for breakfast: <random permutation of $C\cup\{\text{<private number>}\}$ > Give me an example breakfast number in planet Z. Respond with just the number.

The set $C$ is a fixed subset of size $|C|=k$ of the set $\mathbbm{N}_{100}^{999}=\{100,\ldots,999\}$ of the $900$ 3-digit numbers. We selected the set $C$ uniformly at random. The string <name> is and <private number> $\sim U[\mathbbm{N}_{100}^{999}\setminus C]$ were generated separately for each prompt $i\in[n]$. For our purposes, the set $C$ is the information we want transferred whereas the prompt-specific <name> and <private number> and the ordering of $C$ in the prompt are considered private. These prompts have $k$ correct answers. We report results with $k\in\{20,100\}$.

For each prompt $i\in[n]$ we retrieved the probability distribution $\boldsymbol{p}^{(i)}$ over tokens $V$ of the next-token response.
Llama 3 uses a vocabulary $V$ of 128k tokens and 3-digit numbers are encoded as single tokens. The generation took a few minutes on a single A100 GPU.

#### Properties of the Distributions:

- •
Probability of tokens that are not 3-digit numbers is negligible:
The average probability (over teachers) of a response token in $\mathbbm{N}_{100}^{999}$ was $\mathsf{E}_{i\in[n]}\sum_{j\in\mathbbm{N}_{100}^{999}}p^{i}_{j}\approx 0.997$ for $k=20$ and $\approx 0.994$ for $k=100$.
- •
Tokens in $C$ dominate but other 3-digit numbers are likely:
The average probability of a token in $C$ was $\mathsf{E}_{i\in[n]}\sum_{j\in C}p^{i}_{j}\approx 0.716$ ($k=20$ tokens) and $\approx 0.75$ ($k=100$). The probability assigned to
tokens in $\mathbbm{N}_{100}^{999}\setminus C$ (not present in the prompt) is explained by the model generalizing that additional 3-digit numbers are edible on Planet Z.
- •
Despite symmetric prompt construction, there is significant variability between tokens in $C$ and across teachers on same token. This is an artifact of the model. Figure 5 shows average (over prompts) of the probability of each token and demonstrates variability between tokens. The error bars indicate variability in the token probability across teachers.

Figure 6 shows the
$\tau$-robust part of the average distribution for varying $\tau$ (see Remark 3). This is the part of the average distribution that we can hope to transfer via coordinated ensembles with support $\tau$.

Figure: Figure 5: Average probability, over teachers, of tokens in $C$. The error bars indicate the contribution of the token to the average total variation distance over pairs of teacher distributions. Left is $k=20$ right is $k=100$.
Refer to caption: extracted/5600004/plots/llama3/llama3_k20_p1common_tokens_avprob.png

Figure: Figure 6: The $\tau$-robust part of the distribution for varying $\tau$ (see Remark 3). Left is $k=20$ right is $k=100$.
Refer to caption: extracted/5600004/plots/llama3/llama3_k20_p1_robustaverages.png

#### Sampling vote histograms

We sampled $r=10^{3}$ vote histograms $(\mathbf{c}^{h})_{h=1}^{r}$
from each of
coordinated and independent ensembles.
Each histogram has total count of $n=10^{4}$, since each teacher contributes one token. We use the notation $c^{h}_{j}$ for the frequency (count) of token $j$ in the $h$th histogram.

Figures 7 and 8 visualize the average probability $\frac{1}{n}\sum_{i\in[n]}p^{(i)}_{j}$ of each token $j\in\mathbbm{N}_{100}^{999}$ across teacher distributions. The figure also shows the average frequency $\frac{1}{r}\sum_{h=1}^{r}c^{h}_{j}$ in the $r=10^{3}$ samples from each of independent and coordinated ensembles. This demonstrates the property that
the expected number of votes for each token is the same for the two ensemble types and corresponds to the average distribution.

Figure: Figure 7: $k=20$: For all tokens (tokens in $C$ shown in read): Average probability over teachers (top). Average frequency across $r=1000$ samplings using independent (middle) and coordinated (bottom) ensembles.
Refer to caption: x1.png

Figure: Figure 8: $k=100$: For all tokens (tokens in $C$ shown in read): For all tokens (tokens in $C$ shown in read): Average probability over teachers (top). Average frequency across $r=1000$ samplings using independent (middle) and coordinated (bottom) ensembles.
Refer to caption: x4.png

The qualitative difference between coordinated and independent ensembles is visualized in Figure 9 by zooming on individual sampled histograms. The figure shows one sampled histogram with independent sampling and two sampled histograms with coordinated sampling. With independent sampling, frequency counts of each token $j$ are concentrated close to the expectation $\sum_{i}p^{(i)}_{j}$ and are similar across different samples and to the averages shown in Figures 7 and 8. With coordinated samples there is high variability between samples and it is possible for the frequency of a token to far exceed $\sum_{i}p^{i}_{j}$.

Figure: Figure 9: Histogram of frequency counts per token for single samples. Left: Independent ensemble. Middle and Right: Coordinated ensemble. Top $k=20$ bottom $k=100$.
Refer to caption: extracted/5600004/plots/llama3/llama3_k20_p1_indensemble.png

Figure: Figure 10: Left: Average number of tokens per sample with frequency filter $\geq T$. Middle: fraction of votes in frequency $\geq T$. Right: Total Variation Distance between filtered and average distribution with filter $\geq T$. Top $k=20$ bottom $k=100$.
Refer to caption: extracted/5600004/plots/llama3/llama3_k20_p1_r1000cumfrequency.png

#### Utility Evaluation

A token can be reported in a privacy-preserving way only when the frequency exceeds the privacy noise scale $c_{j}>T$.
We evaluate utility of coordinated and independent ensemble types by considering
(i) coverage vs threshold: fraction of the votes that appear with token frequency at least $T$ and (ii) diversity vs coverage.

Figure 10 (left) shows the average number of tokens per sample (histogram) that have frequency above $T$, for varying $T$. We observe that with independent samples, the maximum frequency (over histograms and tokens) does not exceed that of the maximum token average probability (for $k=20$, $0.14$ and for $k=100$, $0.03$). With coordinated ensembles, the majority of samples contained a token with frequency above $0.25n$ (that is much higher than the maximum token average probability). In an application, we would collect multiple samples (histograms) until we obtain one that yields a token with our privacy parameters. A data dependent privacy analysis (see Section A) is such that we essentially pay for privacy loss only where there is yield (privacy-preserving token extracted from the histogram). As an example with $k=100$, with independent ensembles the probability of yield is negligible when the noise scale has $\sigma>0.04n$ whereas with coordinated ensembles there is $\approx$10% yield probability even with $\sigma\approx 0.3n$.

Figure 10 (middle) shows
the fraction of the votes (over samples and tokens) that are in frequencies that exceed $T$, for varying $T$. We can see that coordinated ensembles cover many more votes for a given $T$ than independent ensembles. Additionally, we observe that the coverage corresponds to the $T/n$-robust part of the distribution shown in Figure 6, that is, it corresponds to what we can hope to transfer.
For $k=100$, 20% of the votes are covered with $T=2000$ with coordinated sampling but require $T\leq 250$ with independent sampling (factor $\times 8$).
For $k=20$, 40% of votes are covered with $T=4000$ with coordinated sampling but this coverage requires $T\leq 1000$ with independent sampling (factor $\times 4$). Independent samples have 0% coverage with $T\geq 1500$ for $k=20$ and with $T\geq 400$ for $k=100$.

To summarize, we demonstrated that independent ensembles have 0% coverage when $T$ exceeds the maximum average frequency whereas coordinated ensembles are effective with high $T$.

We next consider diversity per coverage.
Figure 10 (right) reports the
total variation distance from the average distribution.
Figure 11 shows coverage (fraction of votes) vs sparsity (number of distinct tokens) with coordinated and independent ensembles. We can see that coordinated ensembles are more diverse than independent ensembles for the same coverage, with an order of magnitude gap.

Figures 12 and 13 visualize the histograms of the covered votes (averaged over the $r$ samples) per token, for varying thresholds $T$. For each displayed histogram we list coverage and sparsity.
Recall that the threshold $T$ corresponds to the noise scale $\sigma$ that allows for the transfer. Coverage is indicative of yield distribution and sparsity reflects lower diversity of the yield.
The visualization demonstrates again the benefits of coordinated ensembles: Independent ensembles become ineffective with very low $T$, quickly losing coverage and diversity compared with coordinated ensembles.

Figure: Figure 11: Coverage versus sparsity with coordinated and independent ensembles when sweeping $T$. $k=20$ (left) and $k=100$ (right).
Refer to caption: extracted/5600004/plots/llama3/llama3_k20_p1_r1000coveragesparsity.png

Figure: Figure 12: Coverage histograms averaged over $r=10^{3}$ samples. Filter $T\in[100,200,500,1000,2000,5000]$. $k=20$ Left: coordinated Right: Independent
Refer to caption: x8.png

Figure: Figure 13: Coverage histograms averaged over $r=10^{3}$ samples. Filter $T\in[50,100,200,300,400,1000,2000,5000]$. $k=100$ Left: coordinated Right: Independent
Refer to caption: x19.png

## 6 Aggregation Methods of Frequency Histograms

Our aggregation methods are applied to
frequency histograms generated by a coordinated ensemble and return a token or $\bot$.
We propose two meta schemes that preserves diversity in the sense of Definition 1: One for homogeneous ensembles, where we use $\tau>n/2$, in Section 6.1 and one for heterogeneous ensembles, where $\tau\ll n/2$ (but large enough to allow for DP aggregation), in Section 6.2.
To establish diversity preservation, we consider the end-to-end process from the teacher distributions to the aggregate distribution.
To establish privacy, it suffices to consider the histogram in isolation, as it has the same sensitivity as vote histograms with cold PATE: When one teacher distribution changes, one token can gain a vote and one token can lose a vote. Noting that the shared randomness $\rho$ is considered “public” data.
We then explore (Sections A and B) DP implementations that
admit data-dependent privacy analysis so effectively many more queries can be performed for the same privacy budget. We can avoid privacy loss on responses that agree with the prior distribution of the public model with a public prompt. We can benefit from the particular structure of histograms generated by coordinated ensembles. The privacy loss does not depend on queries with no yield, with high agreement, or with agreement with a public prior. With heterogeneous ensembles we can also gain from
individualized per-teacher privacy charging.

### 6.1 Homogeneous Ensembles

Figure: Algorithm 2 DistAgg homogeneous

When $\tau>n/2$, there can be at most one token $j$ with frequency $c_{j}\geq\tau$.
If there is such a token, we aim to report it. Otherwise, we return $\bot$.
Our scheme is described in Algorithm 2 in terms of a
noisy maximizer (NoisyArgMaxL) procedure.
The latter is a well studied construct in differential privacy
McSherry and Talwar (); Durfee and Rogers (); Qiao et al. (). Generally, methods vary with the choice of noise distribution and
there is a (high probability) additive error bound $L$ that depends on the privacy parameters and in some cases also on the support size and confidence.
For our purposes, we abstract this as NoisyArgMaxL that is applied to a frequency histogram $\boldsymbol{c}$ and returns $(j,\hat{c}_{j})$ such that $|c_{j}-\hat{c}_{j}|<L$ and $\max_{h\in V}c_{h}-c_{j}\leq 2L$. We show that the method is diversity preserving:

###### Lemma 3 (Diversity-preservation of Algorithm 2 ) .

For $\mu>1$, Algorithm 2, instantiated with NoisyArgMaxL as described, is diversity preserving in the sense of Definition 1 with $\tau=\mu(n/2+2L)$,
$\beta=\ln(\mu)/2$ and $\gamma=2$.

###### Proof.

We apply Lemma 1 with $p=1/\mu$. We obtain that the token $j$ has frequency at least $c_{j}\geq n/2+2L$ with probability at least $0.5\ln(\mu)q$. Therefore we have $\hat{c}_{j}\geq n/2+L$ with probability at least $0.5\ln(\mu)q$.
Note that a token can only be reported if its frequency is $c_{j}>n/2$.
Using $T=n/2$ in Lemma 2 we obtain that the relevance requirement is satisfied with $\gamma=2$.
∎

The two most common noise distributions for DP are Gaussian and Laplace noise. (Cold) PATE was studied with both. The Gaussian-noise based Confident-GNMax aggregator Papernot et al. (); Duan et al. () empirically outperformed the Laplace-based LNMAX Papernot et al. () on cold PATE. The advantages of Gaussian noise are concentration (less noise to separate a maximizer from low frequency tokens), efficient composition, and more effective data dependent privacy analysis. Laplace-based noise on the other hand can preserve sparsity (a consideration as the key space of tokens or strings of token can be quite large), there is an optimized mechanism with weighted sampling, and there are recent improvement on data-dependent privacy analysis across many queries (the situation with hot PATE) Cohen and Lyu (). Our privacy analysis in Section A uses a data-dependent Laplace-based approach.

###### Lemma 3 (Diversity-preservation of Algorithm 2 ) .

###### Proof.

### 6.2 Heterogeneous Ensembles

Figure: Algorithm 3 DistAgg Heterogeneous

For lower values of $\tau$, we propose the meta-scheme described in Algorithm 3: We perform weighted sampling of a token from
$\boldsymbol{c}$ and return it if its count exceeds $2L$. If it is below $2L$ we may return either $j$ or $\bot$. We propose DP implementations in Section B.
We establish that Algorithm 3 is diversity-preserving:

###### Lemma 4 (Diversity-preservation of Algorithm 3 ) .

For $\mu>1$, Algorithm 3 is diversity preserving in the sense of Definition 1 with $\tau=\mu 2L$, $\beta=\frac{1}{2\mu}\ln(\mu)$ and $\gamma=1$.

###### Proof.

Consider the first requirement of Definition 1. Consider a token $j$ with $c_{j,q}\geq\tau$. From Lemma 1 using $p=1/\mu$ we obtain that the token $j$
has frequency at least $c_{j}\geq c_{j,q}/\mu\geq 2L$ with probability at least $0.5\ln(\mu)q$.
The token is sampled with probability $\min\{1,kc_{j}/n\}$ and if so appears also in $\boldsymbol{c}^{*}$ (since $c_{j}\geq 2L$). The expected size (number of entries) of $\boldsymbol{c}^{*}$ is at most $k$ and thus it is returned if sampled with probability at least $1/k$. Overall it is sampled and reported with probability at least $\min\{1/k,c_{j}/n\}$.
In total, the probability is $P_{j}\geq\min\{1/k,c_{j,q}/(\mu n)\}0.5\ln(\mu)q\geq\frac{1}{2k\mu}\ln(\mu)
\frac{c_{j,q}}{n}q$.

The second requirement of Definition 1 is immediate.
The expected frequency of token $j$ is $\sum_{i\in[n]}p^{(i)}_{j}$ and
it is sampled with probability at most $\frac{k}{n}\sum_{i\in[n]}p^{(i)}_{j}$. It can only be the output if sampled.
∎

###### Lemma 4 (Diversity-preservation of Algorithm 3 ) .

###### Proof.

## Conclusion

We proposed and evaluated hot PATE, an extension of the PATE framework that facilitates open ended private learning via prompts. The design is based on a notion of a robust and diversity-preserving aggregation of distributions with methods to implement it in a privacy-preserving way. We envision hot PATE as an API offering with state of the art models.

We expect our design to find further applications beyond the PATE setting. The framework is applicable generally when users contribute sensitive distributions that capture their preferences and the goal is to obtain a public representative sample (bundle of items). Moreover, our notion of a robust aggregate distribution may be useful in applications that require robustness to few outlier users but not necessarily privacy. In a sense, it complements a different aggregate distribution, the multi-objective sampling distribution (Cohen, ), where the goal is to faithfully capture each input distribution with minimum overhead.

## Appendix A Privacy analysis considerations

The effectiveness of Hot PATE depends on the number of queries with yield (token returned) that can be returned for a given privacy budget. In this section
we explore the benefits of data-dependent privacy analysis when the aggregation follows Algorithm 2 (homogeneous ensembles). We use synthetically generated teacher distributions with varying size common component (that can be arbitrarily diverse) and distinct (private) components.

Broadly speaking, with data-dependent analysis, we incur privacy loss on “borderline” queries where the output of the DP aggregation has two or more likely outputs. Queries that return a particular token with high probability or return $\bot$ with high probability incur little privacy loss.

We demonstrate that with Algorithm 2, we can expect that
only a small fraction of frequency histograms generated by coordinated ensembles are “borderline.” (i) For queries with high *yield* (high probability of returning a token over the sampling of the shared randomness), the generated histograms tend to have a dominant token (and thus lower privacy loss). This because coordinated ensembles tend to “break ties” between tokens. (ii) For queries with low yield (high probability of $\bot$ response and low probability of returning a token), the total privacy loss only depends on yield responses. This means that high $\bot$ probability does not cause performance to deteriorate.

This is important because both these regimes are likely in sequential text generation and with coordinated ensembles. We expect many of the tokens to follow the base model distribution and therefore have high agreement and not incur privacy loss. Or alternatively, instructions that require private data have no agreement and return $\bot$. The dependent privacy analysis means that generally we can process many more queries for the privacy budget than if we had just used a DP composition bound.

Figure: Figure 14: Left: Number of $\top$ responses for $\varepsilon_{0}$-DP queries for total $\varepsilon=1$ loss. Right: Cummulative maximum frequency for varying common part $\alpha$.
Refer to caption: extracted/5600004/plots/TCT_boundary_wrappper.png

Concretely we consider NoisyArgMax using Cohen et al. () (^1^11We mention the related (non optimized) sparsity-preserving methods Bun et al. (); Korolova et al. (); Vadhan () and optimized but not sparsity-preserving Ghosh et al. ().)
with the maximum sanitized frequency, with privacy parameters
$(\varepsilon_{0},\delta_{0})$. For privacy analysis across queries
we applied the Target Charging Technique (TCT) of Cohen and Lyu () with the *boundary-wrapper* method. The wrapper modifies slightly the output distribution of the query algorithm (after conditioning on $\rho$!) to include an additional outcome $\top$ (*target*). The wrapper returns $\top$ with this probability (that depends on the response distribution) and otherwise returns a sample from the output distribution of the wrapped algorithm. The probability of $\top$ is at most $1/3$ and decreases with agreement (vanishes when there is response with probability closer to $1$). The technique allows us to analyse the privacy loss by only counting target hits, that is, queries with $\top$ response. Since the probability of $\top$ is at most $1/3$, we get in expectation at least two useful responses per target hit. But in case of agreements, we can get many more.
Figure 14 (left) reports
the number of $\top$ (target) responses we can have with the boundary wrapper method as a function of $\varepsilon_{0}$ with overall privacy budget is $\varepsilon=1$. When $\varepsilon_{0}\leq 0.01$, it is about $(10\varepsilon_{0})^{-2}$.

With hot PATE, we are interested in *yield* responses, those that return a token (not $\bot$, and when we apply the boundary wrapper, also not $\top$). We study how the yield probability behaves for histograms generated by coordinated ensembles.

#### Synthetic Teacher distributions:

We parametrize the set of teacher distributions by $\alpha\in(0,1]$, which is the probability of a common part to all distribution. This component is what we aim to transfer to the student.
The teacher distributions have probability vectors of the form

$$ $\boldsymbol{p}^{(i)}=\alpha\cdot\boldsymbol{s}+(1-\alpha)\cdot\boldsymbol{r}^{ (i)}\ ,$ $$

where $\boldsymbol{s}$ and $\boldsymbol{r}^{(i)}$ are probability vectors.
That is, with probability $\alpha$ there is a sample from the common distribution $\boldsymbol{s}$, and with probability $(1-\alpha)$, there is a sample from an arbitrary distribution that is specific to each teacher.
Note that the common component $\boldsymbol{s}$ can be arbitrarily diverse, that is, $\|\boldsymbol{s}\|_{1}$ is permitted to be arbitrarily small.

When the histogram is generated by a coordinated ensemble, then the distribution of the maximum frequency $c$ of a token is dominated by
sampling $y\sim\mathsf{Exp}[\alpha]$ and then
$c\sim\mathsf{Bin}[e^{-y\cdot(1-\alpha)},n]$. It is visualized in Figure 14 (right) for varying values of $\alpha$.
Note that across all weights $\alpha>0$ of the shared component, no matter how small $\alpha$ is, there is probability
$\approx\alpha$ of being above a high threshold (and returning a token). The probability of $\bot$ (no agreement) in this case can be $\approx 1-\alpha$. Therefore $\alpha$ parametrizes the probability of yield over the sampling of the shared randomness.

Figure: Figure 15: Sweep of $\alpha$, showing probabilities of outcomes: token, $\bot$, $\top$ (target hit).
Refer to caption: extracted/5600004/plots/20k_10K_1em2_1em8.png

Figure 15 shows the distribution of responses as we sweep $\alpha$, broken down by $\top$ (target hit), $\bot$ (abort), and token (yield).
The number of queries we process per target hit, which is the inverse of the probability of $\top$, is $\gtrapprox\varepsilon_{0}n$. It is lowest at $\alpha\approx T/n$ and is very high for small and large $\alpha$, meaning that the privacy cost per query is very small.

The yield (probability of returning a token) per query is $\approx\alpha$.
Note that as $\alpha$ decreases, both yield and target probabilities decrease but their ratio remains the same:
In the regime $\alpha\leq T/n$, the yield per target hit is
$\approx\varepsilon_{0}n/2$. Queries with
$\alpha\gg T/n$ are essentially free in that the yield (token) probability is very high and the $\top$ (target hit) probability is very low.

When using $n=C_{\delta}/\varepsilon_{0}$ ($C_{\delta}\approx 2\log(1/\delta_{0}$) teachers and plugging this in, we obtain that we get
$\gtrapprox 0.005\frac{1}{C_{\delta}}n^{2}$ yields for overall privacy budget $\varepsilon=1$.
This means that we pay only for yield and not for queries.
Note that this holds in the “worst case” across all $\alpha$ values, but the number of yields can be much higher when queries have large $\alpha$ (and “yields” do not incur privacy loss).

## Appendix B DP methods for heterogeneous ensembles

We propose two DP methods to implement Algorithm 3 (Section 6.2) with different trade offs.
In both cases we can apply data-dependent privacy analysis so that queries that do not yield a token (that is, return $\bot$) are essentially “free” in terms of the privacy loss. The parameter $L$ depends on the privacy parameters (and logarithmically on $|V|$).

Importantly however, with the second method we can apply privacy analysis with individual charging, where instead of charging the whole ensemble as a unit we only charge teachers that contributed to a response. With heterogeneous ensembles we expect the diversity to arise both from individual distributions and from differences between teachers and therefore with individual charging allows for much more efficient privacy analysis when different groups of teachers support each prediction.

#### Private Weighted Sampling

This method gains from sparsity (histogram support being much smaller than $|V|$) but the calculation of privacy loss is for the whole ensemble. We can do the analysis in the TCT framework Cohen and Lyu () so that privacy loss only depends on yield queries (those that return a token). We
perform weighted sampling by frequency of each token to obtain the sampled histogram $\boldsymbol{c}^{\prime}$ and then sanitize the frequencies of sampled tokens using the end-to-end sparsity-preserving method of Cohen et al. () to obtain $\boldsymbol{c}^{*}$.
The sanitizing prunes out some tokens from $\boldsymbol{c}^{\prime}$ with probability that depends on the frequency $c_{j}$, privacy parameters, and sampling rate. All tokens in $\boldsymbol{c}^{\prime}$ with frequency above $2L$, where $L$ only depends on the privacy parameters, remain in $\boldsymbol{c}^{*}$.(^2^22We note that the method also produces sanitized (noised) frequency values $c^{*}_{j}$ for tokens in $\boldsymbol{c}^{*}$ such that $|c^{*}_{j}-c_{j}|\leq L$. And hence can also be used for NoisyArgMax)
The final step is to return a token from $\boldsymbol{c}^{*}$ selected uniformly at random or to return $\bot$ if $\boldsymbol{c}^{*}$ is empty.

#### Individual Privacy Charging

This method does not exploit sparsity, but benefits from individual privacy charging Kaplan et al. (); Cohen and Lyu (). It is appropriate when $2L\ll n$. The queries are formulated as counting queries over the set of teachers. The algorithm maintain a per-teacher count of the number of counting queries it “impacted.” A teacher is removed from the ensemble when this limit is reached. Our queries are formed such that at most $O(2L)$ teachers (instead of the whole ensemble) can get “charged” for each query that yields a token.

To express Algorithm 3 via counting queries we do as follows:
We sample a sampling rate $\nu\sim U[1/n,1]$ of teachers and sample a token $v\in V$ uniformly. We sample the teachers so that each one is included with probability $\nu$
and count the number $c^{\prime}_{v}$ of sampled teachers with $y_{i}=v$.
We then do a BetweenThresholds test on $c^{\prime}_{j}$ (using Cohen and Lyu () which improves over Bun et al. ()) to check if $c^{\prime}_{v}\geq 2L$. For “above” or “between” outcomes we report $v$. If it is a “between” outcome we increment the loss counter of all sampled teachers with $y_{i}=v$ (about $2L$ of them).
We note that this process can be implemented efficiently and does not require explicitly performing this “blind” search.

Teachers that reach their charge limit get removed from the ensemble.
The uniform sampling of the sampling rate and token emulates weighted sampling, where the probability that a token gets selected is proportional to its frequency. The sub-sampling of teachers ensures that we only charge the sampled teachers. Teachers are charged only when the query is at the “between” regime so (with high probability) at most $\approx 2L$ teachers are charged. Because we don’t benefit from sparsity, there is overhead factor of
$\log(|V|(n/L))$ in the privacy parameter (to bound the error of this number of queries) but we gain a factor of $n/L$ by not charging the full ensemble for each query in the heterogeneous case where most teachers have different “solutions” to contribute.

## Appendix C Empirical Demonstration on the GPT 3.5 Interface

We report here results using the
OpenAI GPT3.5 text completion interface OpenAI () to the proprietary model. Our experimental design and results were subjected to a limitation of the interface that only provides the top-5 logprobs. The results are consistent with our evaluation in Section 5 and demonstrate the benefits of coordinated ensembles.

Given a text prompt, the interface provides the tokens and probabilities of only the top-5 tokens.
We generated $10^{3}$ queries (prompts)
of the following form (see Example in Figure 16) and collected the top-5 tokens and their probabilities.

> On planet Z, some numbers are edible. <name> from planet Z eats the following numbers for breakfast: <random permutation of $\{63,56,28,17\}\cup\{m\sim U\{11,\ldots,99\}$> Give me an example breakfast number in planet Z. Respond with just the number.

The top 5 tokens returned in all of the $10^{3}$ queries were 2 digit decimal numbers. The response token was more likely to be one of the example numbers in the prompt than a different number.

Figure: Figure 16: Query to GPT3.5
Refer to caption: extracted/5600004/Zplots/planetZquestion96.png

Our queries were constructed to have a shared “general” component that we aim to capture via the private aggregation: The four common numbers that we color-code in plots $17$,$28$,$56$, $63$. Other components such as the name and the fifth number are considered “private.”
A limitation of the interface is that we can not obtain the full distribution over tokens. We thus scaled up each partial
distribution of top-5 to obtain a distribution $\boldsymbol{p}^{(i)}$ for queries $i\in[10^{3}]$.

Figure 17 (top) reports the distribution of the average probabilities $10^{-3}\sum_{i=1}^{10^{3}}\boldsymbol{p}^{(i)}$
of each token with a positive probability. The model displayed some preference for $63$ over the three other special numbers. The bottom plot is a histogram of the frequencies (normalized by $10^{3}$) obtained by independently sampling one token $y_{i}$ from each distribution
$\boldsymbol{p}^{(i)}$. There was little notable change between different sampling: For each token $j$, the frequency is a sum of independent Poisson random variables with parameters $p^{(i)}_{j}$ that we know from standard tail bounds to be concentrated around its expectation.

Figure: Figure 17: Average probabilities (left) and normalized frequency histogram from independent samples (right)
Refer to caption: extracted/5600004/Zplots/FreqAve.png

Figure 18 reports example frequency histograms obtained with coordinated sampling (Algorithm 1) for three samples of the shared randomness $\rho$. Note that a different special token dominates each histogram, and the maximum frequency is much higher than the respective expected value.

Figure: Figure 18: Histograms from coordinated samples for different sampling of shared randomness $\rho$
Refer to caption: extracted/5600004/Zplots/FreqHistcoo1.png

Figure 19 reports aggregate results for $10^{3}$ frequency histograms produced for each of coordinated and independent samples. From each histogram we collected the highest and second highest frequencies of a special number and the highest frequency of a non-special number.
The left plot shows the counts (sorted in decreasing order) of each of these three values.
Note that with independent samples, frequencies remain close to their expectations: The top frequency corresponds to that of $63$. The second highest to one of the other special numbers. Note that with independent sampling no token (special or not) in no trial had frequency $>0.5$. Moreover, the gap between the top and second frequencies was consistent and reflected the gap of the expected frequencies between the two top special tokens.

With coordinated samples, about half of the trials had a dominant token with frequency $>0.5$. The dominant token was always one of the special tokens, but not necessarily the special token with the highest average frequency. Figure 19 (right) shows the probability of each of the special numbers to have frequency above $>0.5$. We can see that all four special numbers are represented with probability roughly proportional to their average probability.

Figure: Figure 19: Counts of top frequencies in decreasing order (left). Distribution of dominant token (right)
Refer to caption: extracted/5600004/Zplots/top_freq_cum.png

We observe two benefits of coordinated sampling. First, tokens appear with high frequency, which is
easier to report privately. Second, when there is dominance, there tends to be a large gap between the highest and second highest frequencies, which is beneficial with data-dependent privacy analysis.

Due to the limitation of the interface that returns only the top 5 probabilities, we constructed our example to have $k=4$ special tokens that should be transferred to the student distribution. Note that the benefits of coordinated sampling scale up with $k$: If we had used $k$ special tokens, the top frequency with independent sampling would decrease proportionally to $k$ whereas the top frequency with coordinated sampling remains high and would not depend on $k$. With larger $k$, the lines for coordinated sampling in Figure 19 (top) would remain the same whereas the lines for independent sampling would shift down proportionally to $k$. This property is an artifact of the theory and is demonstrated in our experiments in Section 5. Additionally, our simulations in Section A hold for distributions that are arbitrarily diverse.

## Peer Reviews

confidence: 2
contribution: 3
initial_rating: 6
presentation: 1
questions: - Can you ground your notion of diversity in a practical example? Why should one adopt your notion of diversity? What utility does it bring? Can you provide concrete empirical results to support the benefit of improved diversity as you define it?
- I had a lot of trouble with your presentation of the suggested method as a privacy-preserving algorithm. Having read the paper, I am not convinced of claims such as Line 337:
  > This high agreement allows rare tokens to pass even with high privacy noise and allow for the aggregate distribution, with fixed privacy requirements, to satisfy Definition 1.  
Can you make a clear case for this?  
- Have I misunderstood part of your work? To be clear, I think as is, this paper is not ready for publication. However, I want to be fair and make sure that I have not misunderstood your work. So I'll be happy to engage with you during the rebuttal process.
soundness: 2
strengths: - Improving diversity of PATE responses is an interesting goal, given how much the privacy of PATE comes from teacher agreement (therefore lack of diversity in teacher votes).
- The idea of coordinated sampling of tokens seems novel. Although its privacy implications are unclear.
summary: The paper introduces HotPATE, a method based on the Private Aggregation of Teacher Ensemble with the distinction that the method forgoes independent teacher data and models. In fact, the teacher coordinate their sampling such that upon aggregation of their votes, rare teacher decisions (for instance, rare tokens in the case of private synthetic next-token generation) can still be produced without requiring a lot of agreement between teachers. The paper claims this process improves the diversity of the resulting vote histograms without privacy cost of not having high agreement  (which is traditionally what ensures low PATE privacy costs for private prediction). A new definition for diversity-preserving aggregeation of distributions is presented. Empirical results show that under that definition, HotPATE improves upon ColdPATE. However, practical implications of the definition and broader contribution is unclear.
weaknesses: As someone who is quite familiar with PATE and its derivatives, I found this paper very hard to read and digest. I think there are a couple of reasons for this:

- **A robust privacy analysis is missing.** The paper introduces a particular histogram aggregation strategy that produces rate token frequency. In a sense, this is not an aggregation that produces a single vote but rather a transformed histogram. Overall, I found the presentation of this rather simple idea overly complicated in Section 3. However, the key issue here is not the contrived procedure and Definition 1, but rather the complete lack of privacy analysis under this new aggregation method. Let me clarify this point: the PATE privacy analysis only holds under the noisy argmax release. In particualr, the analysis is a function of the gap between the top vote and the second top vote of the histogram. If we were to use Def.1 and instead release transformed vote count (for the purposes of diversity), we are strictly releasing more information. In fact, since the rare token frequencies are kept (for diversity purposes), such a scheme will likely have higher privacy cost than releasing a full noised histogram of votes.

- **Writing and exposition is not polished.** The introduction is too long and full of technical detail with frequent forward references. None of the technical terms first appearance receive proper introduction.  I find page 4 almost completely incomprehensible as a result. New terms are frequently used before they are properly defined. For instance, "homogeneous ensembles" is used in Line 186 but partially defined in Line 191. Some terms are really never properly defined at all in the introduction ("diversity", "robustness parameter", etc.)

- **Experimental results are limited.** The results are mostly validating that the algorithm produces more "diverse" tokens. I think this is necessary and good. However, throughout the paper it is unclear what the value of this "diversity" is. I was hoping the experimental results would showcases a concrete benefit from having more diverse tokens. For instance, better generalization (test error) on a down-stream task.

- **Empirical results contain no privacy quantification.** Although the paper seeks to find the trade-off between privacy and diversity, the empirical section contains no quantification of the privacy budget of the algorithm. Coupled with the fact that a proper privacy analysis is missing (see first point above) I have serious doubts regarding the privacy claims of the paper and the empirical section did not do much to alleviate them.

---

confidence: 3
contribution: 3
initial_rating: 6
presentation: 4
questions: 1. In practice, does increasing diversity ever harm utility?

Other Notes:

- Typo on Line 93: "...include component that..."

- Typo on Line 190: "...two use scenarios of applications..."

- Typo on Line 323: "A tokens j that..."
soundness: 3
strengths: - Introduces an extension of PATE that overcomes the diversity-privacy tradeoff
- Motivates the analysis through the notion of diversity preserving aggregation
- Connects proposed method with existing statistics literature: coordinated sampling
- Paper reads well, particularly with comparisons between hot and cold PATE
summary: This paper introduces Hot PATE, an extension of the PATE (Private Aggregation of Teacher Ensembles) framework, to settings where output diversity is important. PATE works by partitioning the data and training a teacher model on each partition. Then, for a given model input, the each teacher model "votes" on a label, and a final label is privately sampled from the teacher histogram. 

The key idea of Hot PATE is to preserve both privacy in the output label and the diversity of teacher distributions. The paper introduces the property of diversity preserving aggregation and introduces ensemble coordination as a technique to satisfy the property. Ensemble coordination strategically introduces correlation between teacher votes to ensure that rare tokens are transferred with high privacy noise, effectively mitigating the privacy penalty associated with high diversity, due to private sampling.

The authors provide an empirical demonstration of this approach in the context of in-context learning and show that Hot PATE yields greater diversity in output tokens.
weaknesses: - The empirical analysis is more along the lines of a proof-of-concept rather than a thorough comparison. The paper would benefit from more systematic experiments between hot and cold PATE.
- No discussion of the limitations of the proposed methods. See question 1.

---

confidence: 3
contribution: 4
initial_rating: 5
presentation: 2
questions: * Besides coverage and diversity, are there other metrics which could be used to demonstrate the effectiveness of hot PATE?
* Line 274: If I’ve understood correctly, “the noise scale must satisfy $\sigma << \arg \max_j c_j$” is a requirement on the utility, and not the privacy? It might be helpful to explain this more thoroughly.
soundness: 3
strengths: * I think this paper has a significant contribution — via a carefully designed aggregation method, PATE can now thrive in a broader and more modern setting. Formalizing the notion of “diversity-preserving” (Definition 1) is also a helpful contribution.
* The PATE framework can now be applied to very fashionable problems such as in-context learning.
summary: Private Aggregation of Teacher Ensembles (PATE) was designed for classification-like tasks where each datapoint has a single ground-truth label. For “diverse" tasks such as sequential text generation, the responses might instead be distributions. But there is a tension between diversity and privacy: diversity in the responses reduces agreement among the teachers, which in turn requires a smaller noise scale and less privacy. This paper proposes “hot PATE” which allows for higher diversity in the responses without increasing the privacy cost.
weaknesses: * The paper is not beginner-friendly and seems to assume a reader who is already very familar with DP, PATE and LLMs. In fairness, this probably is going to be the chief audience of this paper, but at the same time I find it somewhat egregious that differential privacy is never formally defined (even if the definition has to be deferred to the appendix due to space constraints).
* I felt that the privacy guarantees are not rigorously stated, DP implementations are largely left as poorly-described black boxes (e.g., NoisyArgMax in Algorithm 2 is never formally introduced) and none of the algorithms include the privacy parameters as input. I didn't see a formal privacy analysis that can be easily verified, and in terms of reproducibility I feel like the algorithms can’t really be implemented without knowing, for example, how to calibrate the noise scale.

---

confidence: 4
contribution: 2
initial_rating: 5
presentation: 2
questions: As in the weaknesses.
soundness: 3
strengths: 1. The motivation is clear: sequential text generation tasks through in-context learning are inherently diverse ("hot") with multiple valid responses.


2. The idea of aggregating responses from different teachers to maintain both diversity and privacy is interesting.
summary: This paper introduces "hot" PATE, an extension of PATE designed for in-context learning via prompts, addressing tasks that are "diverse" and open-ended. They empirically demonstrate the potential of hot PATE for in-context learning.
weaknesses: 1. My primary concern is the empirical evaluation. The utility of in-context learning is typically measured by accuracy in the literature (e.g., [1,2,3]). However, this paper does not report in-context learning accuracy on specific tasks. It is unclear how much benefit hot PATE can provide for in-context learning. Additionally, the experiment is conducted on only one dataset, which is insufficient, and there is only one baseline ("cold" PATE). It is unclear why comparisons to prior in-context learning work (e.g., [1,2,3]) are not included.


[1] Duan, Haonan, et al. "Flocks of stochastic parrots: Differentially private prompt learning for large language models." Advances in Neural Information Processing Systems 36 (2024).

[2] Tang, Xinyu, et al. "Privacy-Preserving In-Context Learning with Differentially Private Few-Shot Generation." The Twelfth International Conference on Learning Representations.

[3] Wu, Tong, et al. "Privacy-Preserving In-Context Learning for Large Language Models." The Twelfth International Conference on Learning Representations.


2. The paper states that Wu et al. (2023), Lin et al. (2024), and Xie et al. (2024) are independent concurrent work, which is inaccurate. These should be considered prior work, as Wu et al. (2023) and Lin et al. (2024) were published at ICLR 2024, and Xie et al. (2024) at ICML 2024.


3. I suggest extending the literature review of this paper by including the work "Tang, Xinyu, et al. Privacy-Preserving In-Context Learning with Differentially Private Few-Shot Generation. The Twelfth International Conference on Learning Representations.". This work studies differentially private in-context learning and proposes to use the sample and aggregate framework to generate DP synthetic examples for in-context learning inference. It could also serve as an experimental baseline for comparison.




3. Some typos:

(1) I recommend ensuring the correct application of \citet and \citep.


(2) Missing periods in Line 299, Line 396, and Line 427.

Meta-review: The paper proposes a transformation that can be applied before PATE to increase consistency of expert predictions in case they share a low-probability prediction. The authors suggest this allows using private aggregation for new tasks such as aggregating next-word predictions from LLMs.

**Strengths:**
* Interesting idea
* Promising initial experiments

**Weaknesses:**
* Unconventional presentation that many reviewers found inaccessible despite being experts in the area (median score for presentation 2)
* Missing concrete privacy analysis in terms of theorems
* No experimental results for an actual end task

Based on the reviews and my own reading of the paper, I very much agree with the assessment and recommendations for improvements by Reviewer FQD1.

While the idea is interesting and the initial experiments are promising, I find the paper to be too premature for publication at ICLR. I appreciate the authors' claim of generality of their approach, but do not find this an acceptable excuse for not providing concrete privacy-utility tradeoff results and privacy analysis for an actual end task, with comparisons with previous state-of-the-art. Such results would be vital for potential users of the method to understand its value - while you demonstrate improvements in an intermediate metric, there is no guarantee on whether these will actually translate to significant improvements in performance in a relevant end task.

In terms of writing of the paper, I would strongly urge the authors to take the feedback of **all** reviewers seriously. The reviewers are experts in the field and represent potential readers of your paper. If they do not understand the paper, you should not blame the reviewers but think how you could write the paper better to avoid such misunderstandings in the future.

Decision: Reject