Cape: Context-Aware Prompt Perturbation Mechanism with Differential Privacy
Authors: Haoqi Wu
Wei Dai
Wang Li
Qiang Yan
Venue: ICML 2025 poster (2025)
Keywords: differential privacy
private selection
large language model
black-box inference
Primary area: social_aspects->privacy
TL;DR: We propose Cape, a context-aware and bucketized prompt perturbation mechanism based on differential privacy, to enable efficient LLM inference with an improved privacy-utility trade-off.

Abstract: Large Language Models (LLMs) have gained significant popularity due to their remarkable capabilities in text understanding and generation. However, despite their widespread deployment in inference services such as ChatGPT, concerns about the potential leakage of sensitive user data have arisen. Existing solutions primarily rely on privacy-enhancing technologies to mitigate such risks, facing the trade-off among efficiency, privacy, and utility. To narrow this gap, we propose Cape, a context-aware prompt perturbation mechanism based on differential privacy, to enable efficient inference with an improved privacy-utility trade-off. Concretely, we introduce a hybrid utility function that better captures the token similarity. Additionally, we propose a bucketized sampling mechanism to handle large sampling space, which might lead to long-tail phenomenons. Extensive experiments across multiple datasets, along with ablation studies, demonstrate that Cape achieves a better privacy-utility trade-off compared to prior state-of-the-art works.

Cape: Context-A Awrr Prompt Perturbation Mechanism with Differential
Privacy
Haoqi Wu
Wei Dai
Li Wang'
Qiang Yan
Abstract
posing significant risks to user privacy, the prompts can contain sensitive user information or confidential business guidelines (Yu et al., 2024). For example, a user might request ChatGPT to summarize or analyze a confidential business report (Forbes, 2023), potentially resulting in se- vere privacy breaches. This issue further exacerbated by the growing stringency of modern data privacy regulations.
Large Language Models (LLMs) have gained sig- nificant popularity due to their remarkable ca- pabilities in text understanding and generation. However, despite their widespread deployment in inference services such ChatGPT, concerns about the potential leakage of sensitive user data have arisen. Existing solutions primarily rely on privacy-enhancing technologies to mitigate such risks, facing the trade-off among efficiency, pri- vacy, and utility. To narrow this gap, we pro- pose Cape, context-aware prompt perturbation mechanism based on differential privacy, to en- able efficient inference with an improved privacy- utility trade-off. Concretely, we introduce a hy- brid utility function that better captures the to- ken similarity. Additionally, we propose a buck- etized sampling mechanism to handle large sam- pling space, which might lead to long-tail phe- nomenons. Extensive experiments across multiple datasets, along with ablation studies, demonstrate that Cape achieves a better privacy-utility trade- off compared to prior state-of-te the-art art works.
Dara Leokage
Adversary
Client
Original Prompt
Cloud Server
Pronpe
Sensitive Infocmatiion
Response
Deployed Langunge Model
Figure I:
Illustration of existing LLM inference services.
Existing solutions (Ma al., 2023; Dong et al., 2023; Wu al., 2024; Hou al., 2023; Li al., 2024) utilize cryptographic techniques like secure multi-party compu- tation (MPC) (Yao, 1986) and homomorphic encryption (HE) (Gentry, 2009) to offer provable security. However, the huge computation and communication overhead hinders their application in real world scenarios Another line of works utilize the client- hybrid execution paradigm, where client performs some lightweight computations and sends shallow layer embeddings the server. However, prior work (Song & Raghunathan, 2020) has shown that such information can be leveraged to reconstruct the origi- nal text effectively. Subsequent works (Zhou et al., 2023; Du et al., 2023) bridge this gap by adding noise to intermediate embeddings break the linkage between the noisy embed- dings and original tokens. However, major limitation is their reliance white-box inference setup, requiring shal- low layers to be deployed on the client side, which demands extensive model modifications, making it seldom practical.
1. Introduction
Recent advancements in large language models (Vaswani al., 2017) have revolutionized fields such as natural lan- guage processing (Devlin al., 2019; Radford al., 2019), driving their widespread adoption in machine learning (ML) inference services. However, despite their growing popular- ity, data privacy remains critical concern. In MI services like ChatGPT (Brown et al., 2020), the server provides an API that processes client queries and returns generated responses. This paradigm (Figure 1) requires clients to transmit their queries-commontt referred to as prompts in the context of language models- the server in plaintext,
A promising approach is to utilize differential privacy (DP) (Dwork, 2006), widely adopted as the de facto stan- dard for protecting user privacy, to verbatim perturb tokens in the prompts. It is highly efficient and requires mod- ifications to the back-end model. SANTEXT (Yue et al., 2021) and CUSTEXT (Chen et al., 2022) focus on text clas- sification tasks. InferDPT (Tong et al., 2023) takes the first
TikkTok.
Correspondence
to:
Haoqi
Wu
chaaqi.1999 tikktok.com>.
Proceedings of the nnnd International Conference Machine Learning. Vancouver, Canada. PMLR 267, 2025. Copyright 2025 by the author(s).
'Take the SOTA 3-party computing work Ditto (Wu al., 2024) example, the average runtime for generating token with sequence length 128 on Bert-base model requires about 30s.

---

CAPE: Context-Aware Prompt Perturbation Mechanism with Differential Privacy
step towards the open-ended text generation tasks that man- ages to extract more accurate generation from the perturbed response from the server with the aid of a local LLM. To enhance utility, these works replace the original token with a random token from 'truncated' adjacency lists, to reduce the large sampling space in NLP (e.g.. BERT models have a vocabulary of size 30,522). However, this practice achieves higher utility at the sacrifice of privacy, making it vulnerable to k-nearest neighbor attacks (Song& & Raghunathan, 2020). Besides, these works typically measure semantic similar- ity via token-level embedding distances. Such approach overlooks contextual information, often leading to reduced contextual semantic coherence.
that Cape achieves a better privacy-utility trade-off and provides stronger defense against existing privacy attacks. Additionally, ablation studies on the hyper- parameters in utility function and bucketized sampling further validate their effectiveness in our approach.
2. Related Work
Existing works typically employ privacy enhancing tech- nologies to enable private inference, where exist trade-off among efficiency, utility, and privacy. Cryptographic-basee solutions provide provable security and nearly lossless in- ference yet at the sacrifice of efficiency. The state-of-the-an works Ditto (Wu et al., 2024) and CipherGPT (Hou et al., 2023) offers comparable accuracy to plaintext computation. However, they require at least 30s to infer a token on Bert- base model, which is not ready for practical scenarios.
Motivating Example: As shown in Figure 2, 'enjoyable' and 'unenjoyable" appear close in embedding space despite conveying opposite meanings. Incorporating contextual information as constraint can mitigate such ambiguities.
Table 1: Comparison of different methods. v indicates the framework supports a feature, O and O refer to high- medium- and low- low-performance, respectively.
This film enjoyable, leaving lasting impression.
enjovable
enjovable
Method
Black-box Inference Privacy Elliciency Utility
Embedding
Logits
CipherGPT (Hou et al., 2023)
O
Ditio (Wu et al., 2024)
memorable
impressive
TextOhfuscator (Zhou et al., 2023)
enjoyable
enjoyable
DP Forward (Du al., 2023)
/
4
pleasant
pleasant
SANTEXT (Yue et al., 2021)
x
1
4
unenjoyable
delightful
CUSTEXT (Chen et al., 2022)
X
1
Perturbation
InferDPT (Tong et al., 2023)
1
This film pleasant, leaving lasting impression.
Cape
Figure 2: Intuition: Drawback of embedding distance alone.
For DP- solutions, although they yield better efficiency but faces the trade-off between privacy and utility. Some works add DP noise based on token embedding distance over the discrete vocabulary set. SANTEXT (Yue el., 2021) uti- lizes metric-LDP (Alvim et al., 2018) and provides privacy protection over the entire vocabulary. Subsequently, CUS- TEXT (Chen et al., 2022) and InferDPT (Tong et al., 2023) prunes the sampling space to a 'truncated' adjacency list (either static or dynamic), to achieve better utility at the sac- rifice of privacy. Furthermore, SANTEXT and CUSTEXT mainly focus on training data privacy and text classification tasks. Our work introduces a context-aware utility function and optimized sampling mechanism tailored for large sam- pling space that strikes better tradc-off. Other works like TextObfuscator (Zhou et al., 2023) and DP-Forward (Du et al., 2023) adopt a client-server hybrid paradigm to offload some part of the model to the client. Consequently, they can add noise to the continuous intermediate embeddings, which shall incur smaller errors compared sampling over discrete domain. However, they require white-box access to the model and fine-tuning to align the embedding space, which could be hard to put into practice. In comparison, our work can be applied to black-box scenario, requiring minimal modifications to existing paradigm. Recently, there
Therefore, Can we perform efficient, context-awart prompt perturbation with better privacy-utiltyy trade-off?
As an answer to the above question, we develop Cape, a context-aware and bucketized DP mechanism tailored to enhance semantic similarity measurement and optimize the sampling process in large sampling spaces for NLP tasks.
Context-Aware Prompt Perturbation. We introduce hybrid utility function that integrates both contextual information and token embedding distance (e.g., Eu- clidean distance) that achieves improved utility. Such utility function is essential to the subsequent Da-based perturbation (formulated as private selection prob- lems), to ensure rigorous privacy guarantees.
Bucketized Sampling Mechanism. We propose a cus- tomized exponential mechanism to tackle the challenge of large sampling spaces in NLP domain. Specifically, we utilize equal-width bucketing to restrict the sam- pling probability of low-utility items, achieving an improved privacy-uiility trade-off.
Empirical Evaluations. We conduct extensive exper- iments on both text classification and text generation tasks across three datasets. The experiments confirm
2

---

CAPE: Context-Aware Prompt Perturbation Mechanism with Differential Privacy
also some works that offer less privacy protection but po- tentially better utility for minimizing disclosure risks (Dou et al., 2024; Staab et al., 2024). These works use LLMs to detect and anonymize sensitive attributes in an innovative way, which we perceive as complementary to our approach for improving utility.
where u(z; M/) denotes the utility function that measures the utility score for selecting yi, and A denotes the sensitivity, which is computed as A. max [u(z, y) - =uxx,, v)).
3.4. Threat Model
In our scenario, the client C sends the prompt x to cloud server S and receives generation results in return: r + M(x). Here, x t2..,.... [n), where t, E V denotes the tokens in the vocabulary. The prompt x may contain sensitive tokens such as emails and genders, and directly uploading such information to S compromises the privacy of clients. Table 2 lists the main used notations in this work.
3. Preliminaries
3.1. Transformer-basedd Inference
Transformer models generally consist of three parts: 1) the Embedding module that maps discrete tokens to continu- ous word embeddings; 2) a stack of Transformer Block; 3) the last Head module that maps the hidden embeddings to task-specific logit. The logits y/: = _Mxx,CCtaa [Ctr)(Ctr) are used to deduce the sampling probabilities for next token 24, where C't denotes the preceding text (and following text).
Table 2: Notations used in this paper.
Symbol
Description
the server that provides inference service the client that inputs prompt
C
M
the language model
V
the vocabulary
3.2. Differential Privacy
word token V
the original prompt a fa.... fu.] and perturbed prompt
Differential privacy (DP) defines the worst-case privacy guarantee. The maximum output probability difference between any two neighbor inputs is bounded by es, where denotes the privacy budget. In this paper, we focus local DP (Kasiviswanathan et al., 2008), which operates on individual data points x and allows clients to locally perturb their data before sending it to the server using the DP mechanism R. Therefore, an adversary cannot effectively infer the original input x based on the outputs.
6, A
privacy budget and sensirivity, respectively utility function
-(
R
the private selection mechanism
deudlt, !
Buelidean distance between tokens i and t' the logits for candidate token i, given context Iz
In
((t,,)
the distance between
token f; and candidate token f, the number of buckets
No
AL
impurtance factors of contextual logits and token distance
Goal. Our goal is to perturb the original prompt using DP as = R(x), ensuring that not only the perturbed e pro- vides rigorous privacy guarantee (i.e., an adversary can not effectively infer original prompt) but also maintains ac- ceptable utility (i.e., task-specific performance is retained).
Definition 3.1 (E-Local Differential Privacy (Ka- siviswanathan et al., 2008)). Given privacy budget 0, randomized algorithm R : X + )' satisfies e-LDP if, for each possible output E Y, and all adjacent 01, 22 E X, the following holds:
Adversary. We consider the LLM inference service provider S as the potential adversary. We do not consider man-in-the-mideee attacks and assume the communication channel secure. S is assumed to be semi-honest, meaning the adversary follows the execution flow for inference but may attempt to extract sensitive information by collecting and analyzing the messages received from the client. S has access to the perturbed prompt å. and the DP mechanism R is publicly known. Moreover, S possesses unlimited com- putational power, allowing it to launch attacks, such as the mask token inference attack (Yue et al., 2021).
(1)( = y]
P[R(x2) = wl Se
In the NLP domain, we tokenize the prompt into tokens, and the sampling spaces X' and y are defined as the token vocabulary V. Conceptually, under e-LDP, any adjacent tokens 21 and 22 can be randomized to the same output token y with indistinguishable probability.
3.3. Private Selection
The task of private selection is to design a randomized algo- rithm R that returns some y: that approximately maximizes the utility u(z, y1) while satisfying differential privacy.
4. Design
4.1. Context-aware Prompt Perturbation
Definition 3.2 (e- (e-Exponential Mechanism (EM) (McSherry & Talwar, 2007)). Given a privacy budget e > 0, ran- domized Exponential mechanism RÆM: : X + y/ satisfies c-LDP if, for each possible output y: E V, and input x E X:: Plys|zr] x 2A
Cape acts as a safeguard layer, allowing the client to locally perturb the prompts and hide sensitive data from the server.
As illustrated in Figure 3 (in green background). the overall procedure is as follows: Given an input prompt containing a sequence of sensitive tokens x {1i, 12, m. (n), and a
u((r v:)
3

---

CAPE: Context-Aware Prompt Perturbation Mechanism with Differential Privacy
Cleent
Perrured Rergens
tween 4 and 4,- Additionally, we introduce importance factors Az. and Ap for logit and distance, respectively. The- oretically, increasing λr enhances contextual coherence, while emphasizing Ap improves semantic similarity.
Pronge (Seudtir Infernation
Sumpling Fanction
Pertarhed Phonge
Cloud Server
Depkyyaal Largaage Maddl
0 Device Medel
finhudring
Penzhaaion
A
To satisfy the monotonicity, since a larger logit indicates higher contextual relevance (i.e., positive correlation) while larger distance indicates lower semantic similarity (i.e.. negative correlation), we use the form u x L exp(-D) to obtain the utility. By default, we use Euclidean distance over the embedding space to measure the token distance D. The contribution of token distance can be formulated as:
Lega
Adversary
hore Gender
① Myyrri lilkey Fanction
timul
Dati Loukage
Lang
Lpe Comeettotore stinr
Figure 3: High-level workflow of Cape.
differential private mechanism R (i.e., Cape), we verbatim replace the original token i; to randomized output token i 4, E V. All these randomized tokens l, constitute the perturbed prompt ě = { = R(t,)), where i E [1, Then, the perturbed prompt è is sent to S for subsequent text generation. Cape consists of two major components:
Draw -duue (i,,t,,,115 [V
(4)
D D Dminn
D Dnorm Dmaz Dmnn
(5)
D= exp( exxpl-nnorm -Dnorm)
(6)
By hybrid, we consider both token distance D and contextual logits L when computing the utility scores for candidate sampling tokens. Prior works (Yue et al., 2021; Chen et al., 2022) merely focus on the token distance alone. We resort to a client-side small device model to capture the contextual information and use Euclidean distance as the default measurement for token distance.
Hybrid Utility Function:
Regarding the boundedness, since Dnorm E [0, 1]. we have D S 1. However, the logit L, which distributes over real value space E, is dependent on the model and input. To limit the contribution of logit to the utility score, we can clip the logit to a given bound B as follows:
(7) To determine suitable bound B, we analyze the logit dis- tribution using few calibration samples. The bound is then selected based on the maximum value. We provide a histogram of both logits and distance in Appendix B.7.
I = clip( (Trpw B)
We adopt Exponen- tial mechanism, the de facto standard in private selec- tion problems, to sample replacement tokens. Notably, the large sampling space in NLP (e.g., the vocabulary in Bert-base models is 30,522) could lead to long-tail phenomenon. To tackle this problem, we propose bucketized variant to refine the sampling probability distribution, especially when the budget is small.
Bucketized Sampling Function:
4.1.2. SAMPLING ALGORITHM
With the utility function defined, we proceed the sampling algorithm, with Exponential mechanism (EM) as the basis.
Long-Tib Tail Phenomenon. We first note that there exists long-tail phenomenon when the sampling space is extremely large (i.e., a large vocabulary V in NLP). In standard EM, the sampling probability for t, can be simply formulated as:
4.1.1. UTILITY FUNCTION
In private selection, the utility function is essential to the sampling performance, which should satisfy two features: 1) Monotonicity: Candidates with higher utility scores are more likely be sampled, which guarantees the utility of the mechanism; 2) Boundedness: The output space of the utility function should be bounded to keep the sensitivity A controllable, ensuring rigorous privacy protection.
expl 22 u(4e,
P(R(4) 4+)
(8)
1 exp u(;,
When V is relatively large, many low-utility candidate to- kens have individually negligible probabilities, but collec- tively their sum is significant. According to the cumulative sampling probability distribution in Figure 4a and 4b, the majority of probabilities are significantly lower than 0.0001, yet they account for a substantial portion of the CDF.
We hereby design a hybrid utility function for the i-th token 4 in prompt as:
u(4i, (.)) = L. D(1,, ((1,,,))> AA
(3)
where t, denote the original and candidate tokens, L, Ma(1, (Czz) denotes the logits for I, given context Clr and a client-side model Me. Ctr can be both preceding and fol- lowing information (e.g.. {t,,...,tt t4-1, ..., fn) } in Bert) or preceding information alone (c.g., {t1, t2, ..., 1 in GPT). D(t,, (r) denotes the token embedding distance be-
Theoretically. let P. and pt denote the smallest and largest probabilities, respectively, with their maximum difference bounded by e (i.e., pt S Ps e²). N denotes the vocabulary size. The probability sum of the top-k tokens (IC) relative to
4

---

CAPE: Context-Aware Prompt Perturbation Mechanism with Differential Privacy
CDF of Sampling Prbobblity
CDP of Candidate Probability
CDF of Docket Probubliing
Comubitiv Probsblit
Cumnlative Prolabiity
Cummutaivv: Pullbblity
10
2 10
0.2
830
675
1.
413
20
Probsbiility
200-
Index
19.00
3-400
Bucket Indox
(a) Sampling CDF.
(b) Candidate Probability.
(c) Bucket Probability.
Figure 4: Cumulative distribution function of sampling probabilities for 'book' in "This is good book.' upon GPT2.
the remaining ones can be expressed as:
candidate to unique bucket of width (Umaz Umin)) (ominn/AN 1/Ns- Notably, if a bucket contains no candidates, it is skipped-a scenario that may occur when N₂ is large. For each bucket, we use the average utility score its candidates as its repre- sentative score. Then, as shown in Algorithm 2, we use EM to sample a bucket, followed by uniform sampling from the chosen bucket obtain the replacement token. The bucketized probability is given by:
Pi = Σ
S k-
kt.
Pt. P2 = Σ Ep. -k)
(9)
KEK.
igk
P1 $
kP
e
ee
1 (N k)
2
(10)
P2 (N -
k) .ps
N
If we set C = 6, k = 10 and N = 50000, we have B 403-10
P 50000 0.08. That is, a great portion of low-utility candidates takes over 90% percent of probability mass. In practice, the empirical cumulative probability for k 10 is less than 1%, i..., P2 2 99%. This observation contradicts the intuitive expectation that candidate tokens closely re- sembling the original token would have higher probabilities.
exp( 22 mean(b:))
P[R(() = [,]
if b, (11)
[b:]
where A = max,, max b B1, b, D' denote utilities of dif- brdd' ferent buckets. As shown in Figure 4c, Cape effectively mitigates the long-tail phenomenon, where low-utility can- didates now constitute a smaller cumulative probability. The proof to Theorem 4. is provided Appendix C.
Algorithm Equal width Bucketing: Bucket
Input: Utility score vector यž the number of buckets No Output: A set of buckets B with different tokens.
Initialize B +-+0 0 W. Sort(w)
Theorem 4.1. The bucketized Exponential Mechanism sat- isfies ('''') d'd-dffferential privacy, where é' = >1(nmmx [bel
w2b Bucketize(ū,,NN)
(.
for i +- 1 to No do
4.2. Define Non-sensitive Tokens
b; + (tylubb = i}
ūb,s < a(bbi}
To further enhance the utility, we utilize pre-defined set of context-independent non-sensitive tokens. This set primar- ily consists of 179 NLTK stopwords (c.g., 'the', 'a') and 32 punctuations (e.g.. ',, !"), which, while lacking significant context-sensitee information, are essential for text coher- ence and readability. We retain these non-sensitive tokens while perturbing those sensitive ones in the prompt.
if (T)) 0 then
B B (maan(,,))))...
return B
Bucketing Strategy, straightforward solution is use larger c, which, however, results in low level of formal privacy. To address this, we propose to bucketize the sam- pling space to refine the sampling probability distribution. Specifically, we adopt equal-width bucketing, which parti- tions the sampling space into uniformly sized N, buckets based on the numerical utility ranges. The key idea to bound the probability sum of all candidates in the same bucket (i.e., within a certain utility interval), proportional to exp( 2/ mean(b.)) (b,)), where b; denotes the token set that maps to the i-th bucket, Uh.s denotes the score vectors for these tokens and mean(b,) = I bu.k/(bsl- As shown in Algorithm 1, we sort the utility scores and assign each
5. Experiments
Datasets & Metries. We consider two types of text tasks: 1) text classification; and 2) open-ended text generation. For the former, we follow prior works (Yue et al., 2021; Chen et al., 2022) use two GLUE datasets with privacy implications. 1) SST-2: This contains sentiment annota- tions for movie reviews, which is used to perform sentiment classification (positive or negative); 2) QNLI: This is a dataset containing sentence pairs for binary classification (entailment/not entailment). We use accuracy as the metrie.
5

---

CAPE: Context-Aware Prompt Perturbation Mechanism with Differential Privacy
Algorithm 2 Cape Mechanism: R
in Python and re-run all the experiments.
Input: Prompt x: = {11, t2,..., ), device model M, em- bedding table ε, importance factors ÄL, Ap. bucket number N₁, and budget 6 >
Experimental setup. All the experiments are carried out on one Debian 11 machine equipped with one Intel Xeon Platinum 8260 CPU (6 cores and 2.40GHz), 16GB of RAM and 4 Nvidia Tesla-V100-SXMDD-22GG GPUs.
Output: Perturbed prompt & +- R(x)
Initialize 2 4-0 0
for i x-11 1 to do
5.1. Privacy-Utility Trade-off'
T(t+) = Utility(M Cr,
(i((4), + Bucket(ū(()), (6)
To begin, we focus on the empirical privacy- utility trade-off of different perturbation mechanisms in both text classifi- cation and open-ended text generation tasks. We will study the effects of formal privacy in the following Section 5.2.
x Sample bucket using EM
b, < (M)) ((4)..)
/* Randomly choose a token from b, */
4 ~ (ni
In terms of efficiency, after setup phase that computes the token embedding distance, the perturbation of Cape only consumes about 0.1 ~ 0.15 second for each input in average considering a small batch size of 2. The detailed efficiency evaluation is provided in Appendix B.5.
8 4 a|,
return .
For the latter, we follow (Tong et al., 2023) to use Wikitext- 103-v1, large-scale dataset derived from Wikipedia articles for language modeling tasks. We use coherence, and align- ment as the evaluation metrics (detailed in Section 5.1.2).
5.1.1. TEXT CLASSIFICATION
For text classification tasks, we leverage a pre-trained Owen2-1.5B-Instruus model (Li al., 2023) for zero-shot learning on the validation set of SST-2 and QNLI datasets. The instructions (i.e., system prompts) used to obtain classi- fication results are provided in Appendix D. Notably, this inference-only paradigm presents a greater challenge in ef- fectively preserving semantics, as the absence of re-training limits its ability to capture and refine noisy semantics.
For privacy evaluation, we consider the following two at- tacks. We calculate the attack success rate asr on sensitive tokens and the privacy score as 1 asr.
KNN Attack (Song& & Raghunathan, 2020). The adversary computes the embedding distance between the perturbed token and all other tokens in the vocabulary, and then selects the Top-k tokens with the smallest distances, where we set = 10. The Top-10 accuracy is defined as the proportion of cases where the original token appears within 10.
Figure 5 illustrates the privacy-utility trade-off under KNN and MTI attacks with [1, 20). respectively. The closer the line is to the upper right corner, the better the trade-off. The detailed utility and privacy numbers are deferred to Appendix B. and B.4. The results across different settings confirm that Cape achieves better trade-off than baselines. Cape achieves comparable task utility to CUSTEXT and superior to that of SANTEXT and InferDPT owing the hybrid utility function and bucketing optimization. Specif- ically. CUSTEXT achieves higher utility even when is small (a stringent formal privacy) owing to its usage of fixed and small adjacency lists. However, such practice leads to worse defense against attacks. Besides, Cape (BERT) yields better utility than Cape (GPT2) since Bert models captures both preceding and following contextual informa- tion, thus ensuring better coherence and semantic similarity.
Masked Token Inference (MTI) Attack (Yue et al., 2021). The adversary employs a BERT model, which captures both preceding and following contextual information, to predict the masked token. We replicate this attack by sequentially re- placing the perturbed token i with the special token [MASK]. The Rouge-L L Fl score is used to evaluate the similarity be- tween predicted and original prompt.
Baselines. We compare Cape with SANTEXT (Yue al., 2021) and CUSTEXT (Chen et al., 2022) on their default setting (based on GloVe embedding). We also adopt Infer- DPT (Tong et al., 2023) as the baseline (based on text- Sabeedding-dda-O00 (OpenAI, 2023)), which is the first work that supports open-ended text generation. For Cape, we utilize either the BERT (Devlin et al.. 2019) model or the GPT-2 (Radford al., 2019) model to capture contex- tual information, along with their respective embeddings to compute token distances. By default, we set Å 0.5, Ap = 1.0 and N₂- = 50. We run inference on the origi- nal data as non-private baseline. The detailed vocabulary configuration is provided in Appendix A. To ensure a fair comparison, we faithfully implement all these mechanisms
There is one special case in Figure 5d that Cape (BERT) performs slightly worse than Cape (GPT2) and the base- lines when e is small under MTI attacks. This is mainly due to the fact that BERT used MTI attack fail to recognize the sub-word tokens in GPT-based Cape (GPT2) and Infer- DPT, and word-level tokens in Vlo SANTEXT and CUSTEXT. This also explains the high privacy scores (over 70%) even when = 20. Such vocabulary mismatch actu- ally hinders the attack performance. Therefore, we mainly
6

---

CAPE: Context-Aware Prompt Perturbation Mechanism with Differential Privacy
373
02.5
UNIPY 1... 33 8
550
300
425
100
20
10
Privacy
Privacy
Friway
Frivayy
(a) KNN attack on SST-2
(b) KNN attack on QNLI
(a) KNN attack Coherence. (b) KNN attack vs. Alignment.
Non-private SANTEXTT --. CUSTEXT CAPE (BERT) - InferDP
65-
Random
... SANTEXT- -... CUSTEXT+ CAPE (GPT3)
Figure 6: Privacy-utility trade-offs in terms of KNN attack by varying E [1, 20] on Wikitext-1033 103--v dataset. Privacy is measured by privacy scores under empirical attacks.
45
30
Prtracy
Privacy
(c) MTI attack SST-2
(d) MTI attack QNLI
which causes OOM error when calculating sampling proba- bilities. As shown in Figure 6, Cape significantly outper- forms InferDPT and achieves similar utility to CUSTEXT when is large. Whereas, CUSTEXT fails to provide rea- sonable empirical privacy. Even with 1, it achieves a privacy score of only around 40%. The results exhibit the superior performance of Cape. The detailed utility numbers are deferred to Appendix B.2.
Non-private ...- SANTEXT -U-CUUTTXT CAPE (BERT) InferDPT
Random
SANTEXT+ ---- CUSTEXT CAPE (GPTZ)
Figure 5: Privacy-utility trade-offs in terms of privacy at-
tacks vs. accuracy rates by varying E [1, 20]. Privacy is measured by privacy scores under empirical attacks.
evaluate KNN attacks in the following experiments.
5.1.2. OPEN-ENDED TEXT GENERATION TASKS
5.2. Influence of Privacy Budget
Compared text classification tasks, text generation is more sensitive to the perturbation. When some key information in the text is disturbed, the generated text may have poor coherence and alignment to the original prompt. We thereby follow InferDPT (Tong et al., 2023) to use a lightweight local model (Qwen2-14 1 -.BB-nnstruc), denoted as extraction model Me. to refine the perturbed response generated by the server. When receiving the noisy generation ý from S, C uses the extraction model de-noise the response as y + M,,, v). Additionally, we denote the expected re- sponse (i.e., non-private) as y. In the following experiments, we vary the perturbation mechanisms, while utilizing the same extraction model (default temperature of 0.5). The instructions used to generate noisy response and extract response are provided in Appendix We use coherence and alignment to measure the text generation utility. Both metrics are computed using cosine similarity that goes as:
In this section, evaluate each method in terms of formal privacy, with of varying e on each method. We do not attempt to align the privacy levels across these methods, as they provide dis- tinct forms of actual formal privacy, which could introduce ambiguities. For instance, the <-metric-LDDP-hase SAN- TEXT effectively adheres e'DP, where e' e dmmar with dmax 14.86 (as derived from Glo Ve embeddings, shown in Table 4). In InferDPT, the random adjacency list is generated using Laplace noise with a default bud- get of approximately 9, resulting in an actual privacy bud- get of ~ E ++S 9. Similarly, our method operates under è' = c In (nmaxx 1b. (b)] c 8. An exception is CUSTEXT, which employs a static adjacency list of default size 20, making it hard to quantify the actual privacy budget.
20]. Notably, we examine the effect
1.2.1. UTILITY EVALUATION
Emb(s:) Emb(s2)
CS(11, 82)
(12)
We compute the Rouge-I, F1 score between the original and perturbed prompts on SST-2 dataset, which serves as an indicator sentence-level semantic similarity. We also provide some perturbation examples in Appendix E.
[mmb(s)]] (2))
where the sentence embedding (r) computed using the method in SimCSE (Gao et al., 2021). Coherence mea- sures the cosine similarity between original prompt and the extracted response y' as CS(x,, 1/), and Alignment mea- sures the similarity between the extracted response y' and expected response as CSS 3').
The results are presented in Table 3. In general, the scores of all methods increase with the privacy budget Among them, SANTEXT+ and CUSTEXT+ achieve high scores even when e is small. This is because in SANTEXT+, a proportion of tokens (top w% most frequent tokens, even not stopwords) are treated as non-sensitive. While in CUS-
Notably, we fail to evaluate SANTEXT because it requires a vocabulary size of approximately 221, 2,,62 over Wikitext,
7

---

CAPE: Context-Aware Prompt Perturbation Mechanism with Differential Privacy
Table 3: Sentence-level similarity of various methods.
1002
1000
750
750
Mechanism
Rouge-L. (
5/ 300
5/ 500
c=1
c=2
2
c=
3
6
c=
c=
< 20
280
250
SANTEXT
13.43
71.31
99.36
99.45
99.45
99.45
10
10
SANTEXT+
52.56
57.77
72.98
76.37
77.46
77.66
77.56
(a) SANTEXT
(b) SANTEXT+
CUSTEXT
14.50
17.87
22.74
47.27
81.44
95.54
99.48
40
CUSTEXT+
50.66
52,90
55.47
69.41
88.46
97.18
99.71
30
InferDUr
13.00
14.09
14,92
16.48
23.20
38.68
68.11
6520
38.38
39.20
40.86
46.85
60.22
76.49
92.03
Cape
GPT2
37.60
38.19
40.08
44.55
56.46
73.46
90.65
(c) CUSTEXT
(d) CUSTEXT+
1000
TEXT, each word has pre-defined token adjacency list, which results in a high probability that word will either remain unchanged or be perturbed to synonym', yielding higher similarity. This also accounts for their weak privacy defense against attacks. Regarding SANTEXT, InferDPT and Cape, Cape achieves the best performance. Specifi- cally, when we align the actual 6 ~ 14, corresponding to SANTEXT (c ~ 1), InferDPT and Cape (c ~ 6), the score of Cape is significantly larger than the other two methods.
750
600
750
A 500
5 500
300)
250
150
250
14
20
10
14
(e) InferDPT
(f) Cape (BERT)
(g) Cape (GPT2)
Figure 7: Mapping set size S, with
[1, 20) on SST-2.
following context. This distinction also explains why Cape (BERT) surpasses Cape (GPT-2) in the above experiments.
5.2.2. PRIVACY EVALUATION
5.3. Ablation Studies
We evaluate the empirical privacy using effective map- ping set size S,. This is calculated by counting the num- ber of distinct tokens mapped from t after perturbation as S. = {L'l(' = R())}. Intuitively, the mapping set should encompass the entire vocabulary. A larger S, implies greater entropy in the mapping distribution, thereby indi- cating higher empirical privacy. We also provide two other metrics: retention ratio N₂ and defense against attacks in Appendix B.3~BB4 44 due to page limitation.
We additionally evaluate Cape under various parameter configurations on SST-2 dataset. From now on, we adopt the Bert- based Cape for its superiority. We here vary utility importance factor and bucket number to perform an exten- sive comparison. Additionally, we evaluate the feasibility of using model distillation on client-side device model in Appendix B.6. We choose KNN attack as the privacy metric and evaluate the classification accuracy on SST-2 dataset.
To evaluate S₁, we run perturbation methods 1,000 times to each token in the vocabulary on SST-2 dataset with E [L, 20). The results are illustrated in Figure 7, For the metric- LDP-based SANTEXT, S, decreases rapidly as increases, dropping to approximately 100 when
1. VARYING IMPORTANCE FACTOR
To evaluate the effect of incorporating contextual logits, we run experiments on varying logit importance factor AL E [0.2, 0.5, 1.0, 1.2, 1.5], with fixed distance importance factor Xn as 1.0 in the hybrid utility function.
3. In contrast, CUSTEXT maintains S; at around 20 in most cases, even when E = 1. This consistency stems from CUSTEXT's design, which restricts the sampling space for each token to a fixed size (20 by default). However, this approach also implies that under a KNN attack with Top-20 accuracy, CUSTEXT's privacy score would be nearly zero
Uninee 2
For InferDPT and Cape, both methods exhibit a propor- tional decrease in S, as increases due to their use of EM over the entire vocabulary. Owing to our bucketing strategy, Cape exhibits lower entropy than InferDPT. Notably, in Cape, the BERT variant outperforms the GPT-2 variant by producing a smaller and smoother S, distribution. This can be attributed to BERT's s use of a denser embedding space. Moreover, BERT is better at capturing both preceding and
26
23 Privacy
20
23
30
100
Privacy
(a) A E [0, 1.5]
(b) No. E [20,200]
Figure 8: Ablation results under various parameter configu- rations with e [1.
As shown in Figure 8a, a utility function that relies solely on token embedding distance (i.e., A = 0.0) demonstrates the poorest performance. highlighting the importance of incorporating contextual logits for designing effective utility
The proportion of synonyms exceeds 40% even when 2, as shown in Table III of the paper (Tong et al., 2023).
8

---

CAPE: Context-Aware Prompt Perturbation Mechanism with Differential Privacy
functions. However, assigning excessive weight logits (e.g., dy 1.5) results in diminished performance. This occurs because a token that better fits the context may not always be semantically similar to the original token.
References
Alvim, M. S., Chatzikokolakis, K., Palamidessi, C., and Pazii, A. Invited paper: Local differential privacy on metric spaces: Optimizing the trade-off with utility, 31 IEEE Computer Security Foundations Sympo- sium, CSF 2018, Oxford, United Kingdom, July 9-12, 2018, pp. 262-267. IEEE Computer Society, 2018. doi: 10.1 2018. 000026. URL https:://oi.orr: (021099/CFF22118.00
5.3.2. VARYING BUCKET NUMBER
We use bucketing to handle the dilemma of large sampling space. To test the effect of bucket number No, we conduct experiments on varying No {20,50 50, 100, 150, 2003.
The experiment results are illustrated in Figure 8b. Notably, No 50 achieves the best performance, while the two ex- tremes, N₂ E {20, 200), yield the worst results. As N, increases, resulting in a larger sampling space, the empirical privacy level improves. For instance, when e = 1.0, the pri- vacy score for N₂- = 200 is approximately 10% higher than that for N₂ 50. However, this comes at the cost of utility, which declines rapidly. This is because larger N, makes it more likely to select bucket with low utility, causing sigmificant utility degradation. Balancing the privacy-utility trade-off, N₂-- = 50 emerges as an optimal choice.
Brown, T. B., Mann, B., Ryder, N., Subbiah, M., Kaplan, J., Dhariwal, P., Neelakantan, A., Shyam, P., Sastry, G., Askell, A., Agarwal, S., Herbert- Voss, A., Krueger, G., Henighan, T., Child, R., Ramesh, A., Ziegler, D. M., Wu, J., Winter, C.,, Hesse, C., Chen, M., Sigler, E., Litwin, M., Gray, S., Chess, B., Clark, J., Berner, C., McCandlish, S., Radford, A., Sutskever, I., and Amodei, D. Language models are few-shot learners, 2020.
Chen, H., Mo, F., Chen, C., Cui, J., and Nie, J. A cus- tomised text privatisation mechanism with differential privacy. CoRR, abs/2207.00 193, 2022. doi: 10.48550/ ARXIV.2207.0113
6. Conclusion
URL https://doi.org
In this paper, we propose context-aware prompt perturba- tion mechanism to strike a better balance in privacy-utility trade-off in LLM inference services. By perturbing user prompts using differential privacy, we provide quantifiable privacy protection, with moderate utility degradation. In the future, we plan to explore more fine-grained privacy mechanisms tailored different groups of tokens, such as application-specifie semantic categories or user-specific personalization scenarios.
Devlin, J., Chang, M., Lee, K., and Toutanova, K. BERT: pre-training of deep bidirectional transformers for lan- guage understanding. In Burstein, J., Doran, C., and Solorio, T. (eds.), Proceedings of the 2019 Confer- ence of the North American Chapter of the Association for Computational Linguistics: Human Language Tech- nologies, NAACL-HLT 2019, Minneapolis, MN, USA, June 2-7, 2019, Volume (Long and Short Papers), pp. 4171-4186. Association for Computational Linguis- tics, 2019. doi: 10. 10.18655/11/19914423, URL https: / wtt.:..ogg/...16533//3333
Impact Statement
This paper presents work whose goal is to advance the field of Machine Learning. Our work aims to address critical pri- vacy concerns surrounding user prompts in widely adopted L.LM-based inference services. To safeguard sensitive user information during inference, we leverage differential pri- vacy, which provides quantifiable privacy protection con- trolled by a privacy budget. However, we also acknowledge the inevitable utility degradation caused by the introduction of random noise to perturb the original prompts. A key contribution of this work lies in the development of novel hybrid utility function that integrates contextual information with token embedding distances, alongside a bucketized sampling algorithm designed specifically for the NIP do- main's 's large sampling space. These advancements have the potential to make private LLM inference more practical and scalable for real- world applications.
Dong, Y., Lu, W., Zheng, Y., Wu, H., Zhao D., Tan, J., Huang, Z,, Hong, C., Wei, T. and Chen, W. PUMA: secure inference of llama-7b in five minutes. CoRR, abs/2307.12533, 2023, doi: 2tt.org/10.6550/xxx....333
URL https://
Dou, Y., Krsek, I., Naous, T., Kabra, A., Das, S., Rit- ter, A., and Xu, W. Reducing privacy risks in online self-disclosures with language models. In Ku, L., Mar- tins, A., and Srikumar, V. (eds.), Proceedings of the 62nd Annual Meeting of the Association for Computa- tional Linguistics (Volume 1: Long Pupers), ACI. 2024, Bangkok, Thailand, August 11-16, 2024, pp. 13732- 13754. Association for Computational Linguistics, 2024. doi: 10...666S1122244.---LO..... URL https: / //bbb.org//0001655/v11///2.2.2
9

---

CAPE: Context-Aware Prompt Perturbation Mechanism with Differential Privacy
Du, M., Yue, X., Chow, S. S. M., Wang, T., Huang. C., and Sun, H. Dp-forward: Fine-tuning and infer- ence on language models with differential privacy in forward pass. In Meng, W., Jensen, C. D., Cremers, C., and Kirda, E. (eds.), Proceedings of the 2023 ACM SIGSAC Conference on Computer and Communications Security, CCS 2023, Copenhagen, Denmark, Novem- ber 26-30, 2023, pp. 2665-2679. ACM, 2023. doi: 10.1 00.1145/357611553611653 URL https: htttps://doi.rgg//////// 10.1145/3576915.3661
2024, 2024. URL http://pppersmmipscc//
paper super__fileesppaer//22/4//2
25445bbeeebbbcf57dccee0001133333 Abstract-CCnffrenceente
Ma, J., Zheng, Y., Feng, J., Zhao, D., Wu, H., Fang, W. Tan, J., Yu, C., Zhang, B., and Wang, L. Secretflow- spu: A performant and user-friendly framework for Drivac--rresevve machine learning. In Lawall, J. and Williams, D. (eds.), Proceedings of the 2023 USENIX An- nual Technical Conference, USENIX ATC 2023, Boston, MA, USA, July 10-12, 2023, pp. 17-33. USENIX As- sociation, 2023, URL htwps: http:///wwwww.sww...oo conference/atcoo http:///eeea.eeeeeeeeeeteaaaaaae wttp:/patteennnnnooom/e
Dwork, C. Differential Privacy, pp. 1-12. Jan 2006. doi: 10. 10.1700117 URL attp://dx.do..org/
10.1007/117870065
Forbes.
Samsung bans chatgpt among employees
McSherry, F. and Talwar, K. Mechanism design via dif- ferential privacy. 48th Annual IEEE Symposium on Foundations of Computer Science (FOCS 2007), October 20-23, 2007, Providence, RI, USA, Proceed- ings, pp. 94-103, IEEE Computer Society, 2007. doi: 10.1 10.1109/FOCSS 2007.41. URL https://doi.org: 10.109/FOcC.200..41
after sensitive code leak, 2023. URL https:
sensitive- code leak.
Gao, T. Yao, X., and Chen, SimCSE: Simple contrastive learning of sentence embeddings. In Empirical Methods in Natural Language Processing (EMNLP), 2021.
OpenAL. New and improved embedding model., 2023. URL https: http:/::///eeaa.om../ hamm//llg//eew/
Gentry, C. fully homomorphic encryption scheme. PhD thesis, Stanford University, USA, 2009. Utthttps::// searchworks.staheee sesrchiorkssstanffordedtteseesse
-nd
Radford, A., Wu, J., Child, R., Luan, D., Amodei, D., and Sutskever, Language models are unsupervised multitask learners. 2019.
Hou, X., Liu, J., Li, Li, Y., Lu, W., Hong, C., and Ren, K. Ciphergpt: Secure two-party GPT inference. IACR Cryptol, ePrint Arch.. pp. 1147, 2023. URL https: //eprint.iacr.ort wtt.eerrrrrg/22///1111 2023/1147
Sanh, V., Debut, L., Chaumond, J., and Wolf, Distilbert, distilled version of BERT: smaller, faster, cheaper and lighter. CoRR, abs/1910.01 108, 2019. URL http:// http:///aab99110010000
Kasiviswanathan, S. P., Lee, H. K., Nissim, K., Raskhod- nikova, S., and Smith, A. D. What can we learn pri- vately? In 49th Annual IEEE Symposium on Founda- tions of Computer Science, FOCS 2008, October 25-28, 2008, Philadelphia, PA, USA, pp. 531-540, IEEE Com- puter Society, 2008. doi: 10. 10.1109/FOCS.2008.. https: http://dooooggg/ 0.100.1199900 00211100FFOCCC 2ww.1000/FOC..2008.22
Song, C. and Raghunathan, A. Information leakage in em- bedding models. In Ligatti, J., Ou, X., Katz, J., and Vigna, G. (eds.), CCS '20: 2020 ACM SIGSAC Confer- ence Computer and Communications Security, Virtual Event, USA, November 93, 2020, pp. 377-390. ACM, 2020. doi: 10. 10.1145/3372297.441722 3417270. URL https: (ee.2oogg/..11455333229333.3
URL
Li, Z., Zhang, X., Zhang, Y., Long, D., Xie, P., and Zhang, M. Towards general text embeddings with multi-stage contrastive learning. arXiv preprint 0tt.223388.3288. 2023.
Staab, R.. Vero. M. Balunovie, M., and Vechev, M. T. Large language models are advanced anonymiz- ers. CoRR, abs/2402.13846, 2024. doi: 10.48550/
Li, Z., Yang, K., Tan, J., Lu, W., Wu, H., Wang, X., Yu, Y., Zhao, D., Zheng, Y., Guo, M.. and Leng, Nimbus: Secure and efficient two-party inference for transformers. In Globersons, A., Mackey, L., Belgrave, D., Fan, A., Paquet, U., Tomezak, J. M., and Zhang, C. (eds.), Advances in Neural Information Processing Systems 38: Annual Conference on Neu- ral Information Processing Systems 2024, NeurIPS 2024, Vancouver, BC, Canada, December 10 15,
ARXIV 24XIV URL https://doi.org/ 10.48550/rxx1.2402.11
Tong, M., Chen, K., Qi. Y., Zhang, J., Zhang, W., and Yu, N. Privinfer: Privacy-preserving inference for black-box large language model. CoRR, abs/2310.12214. 2023. doi: 10.48550ARKXIV2330012222 URL https: doi.org/10.48550/arkk
10

---

CAPE: Context-Aware Prompt Perturbation Mechanism with Differential Privacy
Vaswani, A., Shazeer, N., Parmar, N., Uszkoreit, J., Jones, L.,, Gomez, A. N., Kaiser, L.., and Polosukhin, I. Attention is all you need. In Guyon, I., von Luxburg, U.. Bengio, S., Wallach, H. M., Fergus, R., Vishwanathan, S. V. N., and Garnett, R. (eds.), Advances in Neural Information Processing Systems 30: Annual Conference on Neural Information Processing Systems 2017, December 4-9, 2017, Long Beach, CA. USA, pp. 5998 6008, 2017. URL https::/prrceedingaat paper/2017/hash// Fo0033cc45 Abstract.html.
Wu, H., Fang. W., Zheng, Y., Ma, J., Tan, J., and Wang. L. Ditto: Quantizaton--awaee secure inference of trans- formers upon MPC. In Forty-firsi International Confer- ence on Machine Learning. ICML 2024, Vienna, Austria, July 21-27, 2024. OpenReview.net, 2024. URL ht htsps:
Yao, A. C. How to generate and exchange secrets (ex- tended abstract). In 27th Annual Symposium on Foum- dations of Computer Science, Toronto, Canada, 27-29 October 1986, pp. 162-167. IEEE Computer Society, 1986. doi: 10.1109/SFCSS.988655 URL https: // //t...ogg....119//F5..... 1tt.:211000//S.1188...
Yu, D., Kairouz, P., Oh, S., and Xu, Z. Privacy-preserving instructions for aligning large language models. In Forty- first International Conference on Machine Learning, ICML 2024, Vienna, Austria, July 21-27, 2024. OpenRe- view.net, 2024. URL https: http//penrvev..eoe /
Yue, X., Du, M., Wang. T., Li, Y., Sun, H., and Chow, S. S. M. Differential privacy for text analyties via natu- ral text sanitization. In Zong, C., Xia, F., Li, W., and Navigli, R. (eds.), Findings of the Association for Com- putational Linguisties: ACL/IJCNLP 2021, Online Event, August 1-6, 2021, volume ACL/IJCNLP 2021 of Findings of ACI, pp- 3853-3866 Association for Computational Linguistics, 2021. doi: 10. 100118653/11220111FNNDD ACL.337. URL https: http::///...orrg/....555/// 2021. nd igs
Zhou, x., Lu, Y., Ma, R. Gui, T., Wang, Y., Ding, Y., Zhang, Y., Zhang, Q., and Huang, X. Textob- fuscator: Making pre-trained language model pri- vacy protector via obfuscating word representations. In Rogers, A., Boyd-Graber: J. L., and Okazaki, N. (eds.), Findings of the Asxociation for Computational Linguistics: ACL 2023, Toronto, Canada, July 9-14, 2023, pp. 5459-5473. Association for Computational Linguistics, 2023. doi: 10. 10.11665/V//20033F/DDDN ACL.337. URL /ttptppps//oo..cc////0/855// 2023. 3023.findings-ac1.333

---

CAPE: Context-Aware Prompt Perturbation Mechanism with Differential Privacy
A. Vocabulary Configuration
The vocabulary configuration for the baselines and Cape are provided in Table 4, Notably, SANTEXT leverages a subset of GloVe, specifically tailored to the dataset's 's vocabulary, excluding tokens that do not appear in the dataset. CUSTEXT similarly trims the Vlo vocabulary to align with predefined vocabulary subset 3. InferDPT also prunes the cl100k_bast to initial I 11,000 English tokens as the vocabulary. Specifically, the embeddings in CUSTEXT are normalized, resulting in smaller Euclidean distances.
Table 4: Vocabulary configurations. V Vaampte denotes the actual sampling space. K and K denote the size of (random)
adjacency list in CUSTEXT and InferDPT, respectively.
Ve (d 300)
Bert (d 768)
GPT
Methods
(d c {768, 1536))
V
dmaz
[V Veompiel
dmax
Vsamptel
[
dmnx
Vsamplel
14,283 (SST-2)
SANTEXT
2,196,017
14.86
87,751 (QNLI)
221,642 (Wikitext-10344
CUSTEXT
76,855
1.66
K
InferDPT
100,256 (1 (11,000)
1.44
K
Cape
30,522
2.89
30,522
50,257
7.58
50,257
B. Detailed Experiment Results
B.1. Utility for text classification tasks
Table presents the utility of different methods, measured by inference accuracy of text classification on SST-2 and QNLI datasets. Notably, as mentioned Section 5.2, we directly use the definition of privacy budget in their papers without alignment our work in case of ambiguities. We here focus on the influence of
Table 5: Utility comparison of various perturbation mechanisms at similar privacy levels on SST-2 and QNLI datasets.
Methods
SST-2
QNLI
[=1 1 <=2
3
==
=
10
<=
14
<=
20
c=1
c=2
c=
3
c
<=
10
14
20
Random
51.72
SANTEXT
52.29
52.52
76.15
91.06
92.09
91.17
90.14
50.98
50.91
66.68
76.90
76.55
76.55
76.66
SANTEXT+
64.22
67.20
77.52
79.47
81.63
82.17
83.27
58.72
60.44
66.26
68.74
69.52
71.13
71.59
CUSTEXT
62.50
63,53
65.60
72.01
82,21
91.51
92.20
61.71
61.61
63.23
67.07
73.81
76.11
76.57
CUSTEXT+
71.56
72.13
73.05
82.56
86.19
91.74
92.43
65.22
66.48
67.38
69.69
76.00
76.66
77.01
InferDPT
54.19
55.52
56.54
58.38
56.42
60.44
79.70
52.27
53.33
$4.19
56.13
$7.67
62,80
72.18
Bert
58.14
60.01
62.33
64.93
76.56
83.24
91.33
52,10
51.77
52.17
53.74
59.76
67.93
75.84
Cape
GPT2
59.63
60.89
61.27
63.99
77.81
80.67
90.25
51.66
51.86
52.59
52.66
59.45
67.09
73.62
Non-private
92.54
76.88
B.2. Utility for open-ended text generation tasks
The detailed utility numbers for open-ended text generation tasks are illustrated in Table 6. We measure the utility of the noisy generation from two aspects: coherence to the original prompt, and alignment to the expected generation.
B.3. Privacy: Retention Ratio
Retention ratio N₂ is calculated by counting the frequency of retention of token after the perturbation. This is a straightforward metric for evaluating privacy protection. A higher N, indicates that more tokens remain unperturbed, reflecting lower level of privacy protection. As the privacy budget increases, all methods exhibit higher N,. Among
Liimieed vocabulary: innstraiint//ccaauuul
12

---

CAPE: Context-Aware Prompt Perturbation Mechanism with Differential Privacy
Table 6: Coherence & Similarity on Open-ended Text Generation.
Coherence
Alignment
Methods
1
<=2
6=
6
10
14
t=
20
<=
6=2
<=3
6
== 10
< 14
<= 20
CUSTEXT
53.78
54.23
55.11
56.83
59.36
58.85
58.93
57.73
58.04
58.69
61.21
63.83
64.38
64.03
62.26
InferDPT
41.00
36.04
46.72
49.04
54.35
60.33
Bert
42.82
44.07
44.74
47.00
51.22
55.40
58.02
47.86
49.07
49.79
51.27
55.95
59.50
62.31
Copa
GPT
43.20
42.01
42.91
45.61
51.07
54.81
$7.80
47.69
47.12
47.67
50.85
55.37
59.32
62.62
Non-private
59.78
65.05
these methods, Cape consistently achieves the lowest Nt. SANTEXT demonstrates much faster increase in N₂ due its usage of metric-LDP. Additionally, since SANTEXT+ classifies portion of the most frequent tokens non-sensitive, and InferDPT operates with truncated vocabulary of size 11,000, both methods exhibit high N₂ even when 1. CUSTEXT also produces higher N, due to its limited sampling space for each token. Under fixed the Ne of CUSTEXT is nearly double that of Cape.
100
SANEEATIGENN
SANTEXT
CURTEXT- (006A6
CAPE (IEH))
CAPE (GPTZ)
ROVBFT
40
20
1.0
3.0
6.0
10.0
14.0
20.0
E
Figure 9: Retention ratio N₂ by varying the privacy parameter E [1, on the SST-2 dataset.
B.4. Privacy: Defense scores against privacy attacks
We conduct some existing attacks to empirically demonstrate the privacy protection comparison with varying privacy budgets. As introduced in Section 5, we calculate the attack success rate asr on sensitive tokens and the privacy score as 1 0.8.
100
165
Provay
Privecy
13
2.
2.5
20.8
12.3
15.0
12.5
200
25
3.0
160
125
13.0
17.
238
22
2.0
72
1600
12.2
13.0
175
23.
22
30
75
180
122
13.0
208
(a) KNN attacks on SST-2.
(b) MTI attacks on SST-2.
(c) KNN attacks on QNLI.
(d) MTI attacks on QNLI.
Non-private
SANTEXT CUSTEXT CAPE (BERT)
InferDPT
Random
SANTEXT+ - CUSTEXT+ CAPE (GPT2)
Figure 10: Privacy evaluation by varying the privacy parameter e E [1,20].
B.5. Efficiency Evaluation
We evaluate the efficiency of various methods by measuring their runtime cost and memory consumption. A batch size of 2 is used, representing two simultaneous client-side queries. This is reasonable given the lack of high concurrency
13

---

CAPE: Context-Aware Prompt Perturbation Mechanism with Differential Privacy
requirements on the client. Each experiment is repeated five times calculate the average runtime. The total runtime is divided into two phases: 1) Setup phase, which pre-computes token embedding distances, constructs adjacency lists and calculates sampling probabilities; 2) Perturbation phase, which performs the perturbation
input user prompt.
As shown in Table 7, Cape ensures prompt privacy with minimal time overhead. While Cape consumes more resources due to the use of a local model, its average runtime per input prompt remains under 0.2 seconds. SANTEXT and CUSTEXT exhibit the lowest runtime costs, as they precompute adjacency lists and sampling probabilities for each token. However, this comes the expense of higher setup phase runtimes, particularly for CUSTEXT, where adjacency list construction significantly increases overhead. The GPU memory consumption of Cape is approximately 1.5 GB. In Appendix B.6, we further explore the potential of model distillation to reduce this memory requirement.
Table 7: Efficiency evaluation by measuring the average runtime cost in each stage.
Runtime
Memory
Methods
Setup
Perturbation
Perturbation
SANTEXT
325.14s
0.003s
0.81G
CUSTEXT
2929.75s
0.002s
0.16G
InferDPT
28.66is
0.05s
1.03G
Bert
37.91s
0.15s
1.37G
Cape
GPT2
98.25s
0.10s
1.12G
B.6. Ablation:
Distilled Local Model
In Cape, a client-side device model is used to obtain the contextual information to enhance the utility. The parameter size for the Bert-base and GPT2-base models evaluated above is about 400 MB. We note that for those resource-limited devices, we need to further decrease the resource consumption. Model distillation (Sanh et al., 2019) provides a promising direction to lower the model size. To verify its feasibility in Cape, evaluated the performance on the widely-used distilbert model* 4, of which the size is reduced by about 40%.
CATE QUERTY (DSMIBERT)
CAPES (DURT)
90
90
CAPE (DiMIBERT)
Nanoprivate
Nuxigrivtte
85
85
80
80
Utility
Utility
75
75
70
65
65
60
55
55
20
60
80
100
20
40
60
80
Privacy
Privacy
(a) KNN attack with T accuracy.
(b) KNN attack with Top- 10 accuracy
Figure 11: Privacy-utility trade-offss in terms of success rates of KNN attacks vs. accuracy rates by varying the privacy
parameter [1, 20] on the SST-2 dataset.
We evaluate the classification accuracy and KNN attack accuracy on the SST-2 dataset using both the bert-base and distilbert models. As illustrated in Figure 11, distilbert generally achieves performance comparable to the original bert model. Specifically, its classification accuracy at most 1% lower than that of bert under the same empirical privacy level. Detailed results in Table 8 indicate that the distilled model exhibits slightly lower accuracy and stronger privacy defense on
hhttps://hugginngfaccc. sti wbert/ddrr /wf.tdditttti wewrtbeebbbb seatt--baeeuncccsee
14

---

CAPE: Context-Aware Prompt Perturbation Mechanism with Differential Privacy
fixed formal priavey level (i.e., e). This can be attributed the reduced expressiveness of distilbert embeddings compared the original model.
Table 8: Privacy-utility trade-offss in terms of success rates of KNN attacks accuracy rates w/wo model distillation.
Accuracy
Privucy (Top-10) 1
Methods
<
<-
6
c-
10
c-
14
<-
20
<-1
<-
c-
c-
10
c-
20
83.24
9.07
Cape
DistilBert
55.28
59.63
61,86
63.50
76.17
82.13
90.24
93.69
92.50
89.96
80.72
68.57
42.21
10.27
Non-private
B.7. Histogram logits and token embedding distance
We here run some statistics on the example prompt: 'This a good book.' using GPT-2 model. We compute the logits for book with "This is good [MASK]] the context. We compute the Euclidean distance between book and other tokens in the vocabulary V. The histogram of the logits and distance illustrated in Figure 12.
Histogram of Logit Score Distribution (L*)
Histogram Distance Score Distribution (exp(-D))
5000
4000
8000
20
Frequency
Frequency
6000
5.0
1.0
2000
4000
2000
0.5
0.9
1.0
Value
Value
(a) Logit L
(b) Distance exp(-D) AD)
Figure 12: Histogram of different distance metrics for 'This is good book.'. Ae 0.5, Ap 1.0.
C. Proofs of Theorems
Proof of Theorem 4.1. Consider the original token & V, another token L' V {1) and possible output token y E V. We use Bt) bū [N6]) denote the i-th bucket that token t belongs N, is the bucket number. Additionally, use (t,(t,) to denote the bucket utility for (t) and [B()) to denote the cardinality of bucket B(t).
According to the sampling probabilities in Equation 11, we have:
P(R(()= y]
P(R(t') = y) exp( 2Z (t.tt)))
exp
2X
Ub (b.(())))
1 exp( 24 uo(t,
[B())
V
cxp(1 24 un(t',u)))
[B(())
exp 1/ up (1, (()))
Σ
3 exp
( us 11))
[By())
exp 11 ub(( (l', .))
Σ
1
M
exp
ZA Wa (1,);))
[Bx)
15

---

CAPE: Context-Aware Prompt Perturbation Mechanism with Differential Privacy
Let max [4]
exp(e'), we have
| (v)l [By)
S exp(e'). Consequently, we have:
1g
P( = y]
P(R(L)) y)
exp ub (1, 11)
j=m exp( us(t', exp(e')
Vl
27
exp 2A us((t'
Σ/= exp
(t, 8Ú))
24
cxppl c (u(t, 8)
=(tt,)))))
Σ
j= expl
u(t' U1))
22
exp(c)
Σ exp 22 ut, Uj))
5==1 expl 2A utt, m())
|V]
<exp( ()
exp(e)
2
プ |
exp 23 ((,
<exp( ? 9) expl,) 2 exp((c)
=xxp(++e')
The proof shown that our sampling mechanism satisfies (e + e'D-DP.
D. System Prompts
We provide the system prompts used in the text classification and open-ended text generation tasks in Table 9,
Table 9: The detailed prompts text classification and open-ended text generation tasks.
Text Classification on SST-2:
You helpful assistant. Classify if the sentence is positive or negative sentiment. Just gives the answer in positive, negative.
"Content": (input)
Text Classification on QNLI:
You are helpful assistant trained to determine whether given context sentence contains the information needed to answer the given question. If the context answers the question, respond "Yes". Otherwise, respond "No". "Question": {question)
"Context": (sentence)
Text Generation on Wikitext-1088 103-vl: Your task is to extend Prefix Text.
"Prefix Text": (prompt)
Provide only your Continuation.
"Continuation"
Extraction noisy response on Wikitext- 103-vI:
Your task is to extend the "Prefix Text".
Use "Perturbed Generation" as your primary writing material for your extension. Extract coherent and consistent text from the "Perturbed Generation" and integrate them into your continuation. Ensure seamless alignment with the context established by the "Prefix Text".
Provide only your "Extended Text".
Preffx Text": (prompt)
Perturbed Generation":
Extenddd Text":
E. Perturbation Example
We provide some perturbation examples Table 10. Given input prompts 'it a charming and often affecting journey and 'it 's slow very, very slow vary the perturbation methods and privacy budgets.
Toy Example. Consider the example prompt: 'it 's slow very very slow The step-by- steppp perturbation process is as follows.
16

---

CAPE: Context-Aware Prompt Perturbation Mechanism with Differential Privacy
1. Initialize empty token T @b.
2. Tokenize the text prompt using tokenizer and obtain a list of tokens denoted as L.
3. For each token in the list, calculate its utility score. Take "slow" in 'it slow very, very slow as example.
(a) Compute the contextual logits for the MASKED token as I, = M('i 's [MASKED] verr very slow :).
(b) Compute the embedding distance between 'slow' and other tokens in the vocabulary as = deuc("slow' ssoow" V).
(c) Obtain the final utility score = I DAP,
(d) Bucketize all the tokens in the vocabulary into N₂ buckets according to the utility score
(e) Sample bucket using standard Exponential mechanism.
(f) Uniformly sample token from the bucket sampled the previous step.
g Concatenate the newly sampled token to T as T < TV.
4. Finally, we get the perturbed prompt T.
17

---

CAPE: Context-Aware Prompt Perturbation Mechanism with Differential Privacy
Table 10: Perturbation examples of varying privacy budgets for different methods.
Original Prompt:
Mechanism
Rouge-L. (FII
charming and often affecting journey it 's slow very very slow
photo describes several brilliant nowhere practically partly sorts nictzsche clearly do chewing holstered female reid see addictive emphasized
SANTEXT
nevertheless serviceable 2/3 reaction pretend especially daft jouracy. sucked addition laziness increasingly catastrophic defies unwatchable injuries
13.43
fan recognized a charming its oftn affecting journey.
yes 's slow very, intensity stacks.
charming often affecting journey..
99.36
slow very very slow
it 's charming and often committed joumey..
bible slow Iaconic very. very slow solely
SANTEXT+
discussed combined charming banquet often majority encountered precedent slow very , very slow.
57.77
indeed 's leaving charming bothered often operates journey f. slow very, very slow
wanted puzzlod cachanting and often affecting journey yes honestly unfortunately attract however possibilities very slow
76.37
this rather charming all may impair alone
kind 's try something this went
CUSTEXT
's rather charming others tend impair alone.
kind 's something. this went
17.87
's be charming also often impair future
kind 's try sort this went
ratber charming also remain impair happiness. every 's slow very,
47.27
lovely and exist consequence experiences.
it runs very, very slow
CUSTEXT=
it lovely and we consqquence experiences.
very, very slow
$2.90
lovely and allering experiences.
it runs - very, very slow
it's fairytale often affecting lifestyle. (t'space-vor very slow
69.41
Saw axis Translate Sie Incorrect invasion sizes. security instance exter - precision. Converter versus.
InferDPT
plash
Char prior affecting Joy.
noglect- extraerdinary. intimate
16.48
Kit so Adventure charming according affecting analysis. 'it s1- verity. functional wrest.
inferior Bike rub alike affecting jourey...
14
leaming slow very levant instead.
38.68
it's royals andnard popularized progressing. dormitory it's läbre very slower.
Cape
it's axon and quietlyately journey. will very, very civilized. of
46.85
it's charming and greatly intimidation her.
it's slower vory, very busy.
it's charming and highly painful journey. slow very, very slow.
14
76.49
it's aivably and typically EStreamm screened, Christensen it d''DragouMaggzinn after very, very K.Kof
Cape
it's really and her angry sumrr. poor dowaed very, veryadium.
44.55
it's telling and often affecting ride. it's very, very PM, where
14 it's and often affecting journey. slow office very. very put. This
71.46
18


Reviews:
[{"review_id": "GpHaFa3v4t", "reviewer": "Reviewer_Mrs5", "summary": "The paper proposes a new approach to perturb the tokens in user prompts to preserve local differential privacy in an efficient and utility-friendly way. For this, the authors utilize a secondary model, called device model, to generate logits for each token and use exponential mechanism (weighted by these logits) to randomize the token. The experimental results suggest better privacy-utility tradeoffs compared prior work in this area.", "questions": "", "limitations": "", "rating": 4, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer Mrs5 for the positive feedback on \"proposed approach would be useful to improve privacy preserving inference on LLMs\", which is quite encouraging for us. We hereby answer the specific questions below and provide detailed explanations.\n\n> Q1: Clarity of low efficiency of cryptographic solutions.\n\nWe measure efficiency by the average inference runtime cost. \nFor cryptographic solutions, take the SOTA 3-party computing work Ditto [1] as an example, the average runtime for generating **one** token with a sequence length of $128$ on Bert-base model requires about **30 seconds**, which is far more expensive than our method. As shown in Appendix B.5, DP-based methods typically incur **less than 1 second** overhead for perturbation after an initial setup. We will supplement a brief description on the concrete runtime numbers in the Introduction section for better clarity.\n\n[1]: Ditto: Quantization-aware secure inference of transformers upon MPC. https://arxiv.org/pdf/2405.05525\n\n> Q2: Effect of vocabulary or tokenizer mismatch.\n\nWe first clarify that by \"black-box,\" we mean that no knowledge of or modification to the server model is required in our work. We will add this description in Section 4.1 for better clarity.\n\nWe list the vocabulary configuration in Appendix A. Notably, the device models (i.e., Bert and GPT-2) actually use different vocabularies compared to the server model (i.e., Qwen2-1.5B-Instruct, with a vocabulary size of 151,936).\nAs shown in Table 3, while Bert (with a vocabulary size of 30,522) exhibits a larger vocabulary mismatch compared to GPT-2 (with a vocabulary size of 50,257), it still achieves higher sentence similarity.\n\nThe possible reason could be that the perturbation using device model produces semantically-close natural language tokens. Consequently, although the tokenization granularity differs, the composition of sub-tokens still yield similar embeddings in the black-box model. For example, if device model perturbs 'unhappy' to 'un pleasant', although separated by space, its semantics can still be recognized by the black-box model. \nHowever, we believe that partial knowledge of the server model, such as its vocabulary, could further enhance semantic similarity, making it an interesting topic for future work.\n\n> Q3: What does the privacy axis in Figure 5 refer to? How was it measured and what unit is this?\n\nApologies for the misunderstanding. \"privacy\" here refers to privacy score, which is defined at the beginning of Section 5 (at the bottom of Page 5). We will unify the notation and modify the axis label to \"Privacy Score\" for better clarity.\nWe first calculate the attack success rate ($asr$) using KNN Attack and Masked Token Inference Attack. The privacy score is then defined as $1 - asr$.\n\n> Q4: Clarity of Algorithm 1 could be improved.\n\nThanks for your suggestion. We will provide more detailed description in the final version. \nIn Algorithm 1, $b_i$ denotes the token set that maps to the $i$-th bucket. Correspondingly, $\\vec{u}_{b,i} = \\vec{u}\\\\{b_i\\\\}$ denotes the score vectors for these tokens. Then, we can calculate the mean score for this bucket. \n\n> Q5: Typos\n\nThanks for your careful reading. We have corrected the typos in Related Work and Preliminaries. We will review the entire paper and check for any additional typos in the final version.\n\n> Q6: Toy example of the overall mechanism\n\nThanks for your recommendation. We will supplement a section in the Appendix to give a step-by-step example to ease understanding.", "claims_and_evidence": "- In the introduction and related work sections, the paper talks about \"efficiency\", claiming that their work is more efficient that cryptographic solutions. But it is not clear what kind of efficiency this refers to or why their approach is more efficient at least at a high level. I suggest adding a brief discussion on why cryptographic solutions are less efficient. \n\n- The paper proposes the new approach as a black-box technique. But it would be better to clarify that it needs another model, called device model, to generate the logits. It's also not clear from the experiments how the results would be affected when there is a vocabulary or tokenizer mismatch between the black box model and the device model.", "methods_and_evaluation_criteria": "- What does the privacy axis in Figure 5 refer to? How was it measured and what unit is this?", "theoretical_claims": "- In the definition of exponential mechanism, the sensitivity is given as $max_{x, y, y'}\\| u(x, y) - u(x, y')  \\|$ but it should be $max_{x, x', y}\\| u(x, y) - u(x', y)  \\|$.", "experimental_designs_or_analyses": "The experimental setup seem reasonable. It would be nice to try a few more pairs of pre-trained models and device models to understand the impact of vocabulary and tokenizer mismatches better.", "relation_to_broader_scientific_literature": "The proposed approach would be useful to improve privacy preserving inference on LLMs.", "essential_references_not_discussed": "I can't think of a key missing reference.", "other_strengths_and_weaknesses": "- Clarity of Algorithm 1 could be improved. For instance, the operation on line 6, $\\vec{u} \\{ b_i \\} $, was not defined. \n\nMinor: \n- \"where exists a trade-off\" in Related Work", "other_comments_or_suggestions": "An example on how the mechanism would work step by step on a toy setup would improve the clarity significantly.", "questions_for_authors": "Please see above.", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "hd74V7ChRe", "reviewer": "Reviewer_pKo2", "summary": "The paper introduces Cape, a DP mechanism designed to protect user privacy when interacting with LLM inference services. The authors identify an issue in current LLM services: users need to submit their prompts in plaintext for inference, exposing sensitive information. The paper proposes a context-aware approach that perturbs user prompts before sending them to the server while maintaining reasonable utility, including: a hybrid utility function that combines both token embedding distance and contextual information to better measure semantic similarity, and a bucketized sampling mechanism to handle the large vocabulary space in NLP tasks. The authors evaluate Cape on both text classification and text generation tasks, demonstrating improved privacy-utility trade-offs compared to prior methods like SANTEXT, CUSTEXT, and InferDPT.", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer pKo2 for the positive feedback on \"achieves a better privacy-utility trade-off than existing approaches\". We hereby answer the specific questions below.\n\n> A more comprehensive evaluation for semantic privacy leakage and utility.\n\nThanks for your suggestions. For privacy evaluation, we follow prior works and try our best to measure the empirical privacy comprehensively, including attack success rates, effective mapping set size and retention ratio. In this work, we primarily focus on single-token-level privacy leakage, such as name, age, etc. We clarify that more coarse-grained, semantic-level leakage like intent recognition (involving multiple token compositions), is out of our current scope. However, it is an interesting topic that could be explored in future work.\n\nFor utility evaluation, we use commonly-used metrics like accuracy and alignment for a fair comparison, which yields better interpretability. We believe it would be interesting to use LLM-as-a-judge in more complext tasks like multi-candidate ranking.\n\n> Additional literature references\n\nThese two works use LLMs to detect and anonymize sensitive attributes in an innovative way, which we perceive as complementary to our approach for improving utility. We will reference these papers and discuss their potential incorporation in Related Work.\n\n> Privacy concern on extraction model\n\nWe clarify that there is no potential privacy leakage on using extraction model. In our setting, the extraction model is deployed locally on the client-side. Therefore, the adversary only has access to the perturbed prompt $\\hat{x}$ and noisy generation $\\hat{y}$ and cannot launch attacks on the extraction model without additional knowledge.\n\n> Clarification on perturbed text generation pipeline\n\nWe follow InferDPT [1] to perform perturbation-then-extraction text generation pipeline, with Qwen2-1.5B-Instruct serving as both the server model and extraction model. We clarify that the choice of the models is actually orthogonal to our work. As illustrated in Figure 6, with models fixed and varying perturbation mechanisms, our method yields better trade-off than baselines. \n\nBesides, the effectiveness of this privacy-preserving pipeline is evidenced by Table VII in InferDPT paper [1]. The perturbation-then-extraction scheme (with Vicuna-7b-4bit model as the extraction model) yields better coherence scores against generation with Vicuna-7b-4bit alone.\n\n> Scenario where the server possesses privileged information.\n\nThans for your suggestion. The scenario you mentioned resembles RAG-based applications, where server possesses an external knowledge database, which helps generate better responses. We will include this scenario in Introduction to better highlight the necessity of invoking privacy-preserving ML services.\n\n> Practical scalability and usability\n\nWe first clarify that the two sample texts in Appendix are taken from the validation split of SST-2 dataset, providing a real-world example. Our method is also applicable to long-text scenarios, as demonstrated by the text generation experiments on Wikitext-103-v1 dataset. As shown in Figure 6, similar trade-offs are observed in long-text generation, not just in short-text classification. \n\nBelow, due to words limitation, we present a sample text from the Wikitext-103-v1 dataset. Some tokens (**marked in bold**), such as numerical values for length and weight, and words like \"homarus\" -> \"hortus\", \"large\" -> \"small\", \"weighting\" -> \"measuring\" are perturbed. However, the overall semantics and grammatical structure are well preserved. More fine-grained sensitive data taxnomy level perturbation shall greatly improve real-world usability, which is complementary to our work.\n\n- $\\epsilon=14$: **hortus** gammarus is a **small** crustacean, with **aak** length up to **95** centimetres ( **30** in ) and **measuring** up to 5 – 6 kilograms ( 11 - **15** lb ), although the lobsters caught in lobster pots are usually 23 – **35** cm ( 9 – 15 in ) long and weigh 0 @.@ 7 – 2 @.@ 2 kg ( 1 @.@ 5 – 4 @.@ 9 lb ) .\n\nIn terms of usability, we acknowledge the inevitable trade-off between privacy and utility in DP-based methods—privacy comes at a cost. However, our approach manages to achieve a better balance than previous work. In real-world applications, we believe that an application-specific or user-specific taxonomy of sensitive data can guide the development of more refined privacy mechanisms. For instance, we could use separate sampling spaces for location, name, etc. to constrain sampling space while preserving semantics. Additionally, perturbation-aware fine-tuning in SANTEXT[2] could further enhance utility. Although the perturbed prompts may not be human-readable, they can be effectively understood by the fine-tuned model (e.g., extraction model).\n\n\n[1]: InferDPT: Privacy-preserving Inference for Black-box Large Language Models.\n\n[2]: Differential Privacy for Text Analytics via Natural Text Sanitization.", "claims_and_evidence": "The authors claim that Cape achieves a better privacy-utility trade-off than existing approaches, which is supported in the experiments section through the adversarial attacks. \nThe empirical results demonstrate that Cape provides stronger defense against privacy attacks (KNN and MTI attacks) while maintaining competitive utility compared to baselines. The ablation studies validate design choices like the hybrid utility function and bucketing strategy.", "methods_and_evaluation_criteria": "The authors evaluated both utility metrics (accuracy for classification, coherence and alignment for generation) and privacy metrics (attack success rates, effective mapping set size, retention ratio). The authors use multiple datasets (SST-2, QNLI, Wikitext-103) to validate their approach across different task types.\n\nWhile the paper uses KNN Attack and MTI Attack as evaluation metrics for privacy leakage, these methods may not capture all potential forms of information leakage in the perturbation process. For example, there's a possibility of semantic leakage that goes beyond token-level. The composition of multiple perturbed words in context could still reveal meaningful patterns that might enable adversaries to infer sensitive information, even when individual tokens appear adequately protected. A more comprehensive evaluation framework that considers semantic composition effects and contextual meaning reconstruction would improve the privacy analysis. \n\nFurthermore, it might be interesting to use additional utility metrics, such as LLM as a judge, or comparing the difference between perturbed response and the ground truth response.", "theoretical_claims": "I did not check the correctness of Theorem 4.1 whose proof is in the appendix. At a glance, the proof looks sound to me.", "experimental_designs_or_analyses": "I reviewed the experiments and have questions regarding section 5.1.2, which I mention in the questions for authors section.", "relation_to_broader_scientific_literature": "The paper contributes to privacy-preserving LLM inference techniques. The authors reviewed cryptographic solutions, client-server hybrid execution approaches, and previous DP-based techniques (SANTEXT, CUSTEXT, InferDPT).", "essential_references_not_discussed": "There are some additional literature that offers less privacy protection but potentially better utility for minimizing disclosure risks:\n\nDou, Yao, Isadora Krsek, Tarek Naous, Anubha Kabra, Sauvik Das, Alan Ritter, and Wei Xu. “Reducing Privacy Risks in Online Self-Disclosures with Language Models.” arXiv, June 23, 2024. http://arxiv.org/abs/2311.09538.\n\nStaab, Robin, Mark Vero, Mislav Balunović, and Martin Vechev. “Large Language Models Are Advanced Anonymizers.” arXiv, February 21, 2024. http://arxiv.org/abs/2402.13846.", "other_strengths_and_weaknesses": "Strengths\n\nThe paper addresses an important area of privacy protection for LLM. The authors improve DP token perturbation algorithms through two novel improvements: the hybrid utility function and bucketized sampling mechanism.\n\nWeaknesses\n\nWhile the author bridged some part of the gap, the output text remains difficult to interpret and use in practice.", "other_comments_or_suggestions": "If you have any important questions for the authors, please carefully formulate them here. Please reserve your questions for cases where the response would likely change your evaluation of the paper, clarify a point in the paper that you found confusing, or address a critical limitation you identified. Please number your questions so authors can easily refer to them in the response, and explain how possible responses would change your evaluation of the paper.\n\nOn line 335 that the authors mention: 'When receiving the noisy generation yˆ from S, C uses the extraction model to de-noise the response as y′ ← Me(x, yˆ).' Does this step introduce potential privacy leakage? Since the extraction model has knowledge of prompt structures such as syntax or grammar, could this denoising step help adversaries recover the original prompt? It would be valuable to know if the authors performed privacy analyses (such as KNN attacks) against the extracted text, not just the perturbed prompts.\n\n\nIt seems like the text from the appendix, though after extraction, is still unusable given the short length and the often ungrammatical nature. Could you please comment on the scalability of your method in the actual deployment of a sanitization framework?", "questions_for_authors": "On line 335, the authors state: \"'When receiving the noisy generation yˆ from S, C uses the extraction model to de-noise the response as y′ ← Me(x, yˆ).\" Could you clarify the type of server model in this setup?\n\nThe extraction model, a 1.5B model, appears to be strong enough to handle continuation tasks on the Wikitext103-v1 dataset. Have you conducted control experiments measuring the performance of text generation using unperturbed prompts directly with the extraction model? This would help distinguish whether the reported performance stems primarily from the extraction model's capabilities rather than the privacy-preserving pipeline.\n\nHave you considered designing experiments where the task completion explicitly requires the server's involvement, such as scenarios where the server possesses privileged information unavailable to the client? This would better demonstrate the necessity and effectiveness of your privacy-preserving approach in real-world applications.\n\nThe text samples in the appendix exhibit limited length and grammatical issues that raise concerns about practical usability. Could you address the scalability of your method in real-world deployment scenarios? Specifically, what additional techniques might improve the quality of sanitized outputs while maintaining privacy guarantees?", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "tHMCqyoEMF", "reviewer": "Reviewer_jdXq", "summary": "This paper introduces Cape, a DP prompt perturbation mechanism aimed at enhancing the privacy-utility trade-off in LLM-based inference services through context-aware utility function and bucketized sampling function. The proposal is motivative and provides promising solutions to the long-tail dilemma in private selection over large NLP vocabulary. This paper provides comprehensive experimental validation showcasing Cape’s effectiveness.", "questions": "", "limitations": "", "rating": 4, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer jdXq for the positive feedback on \"The proposal is motivative and provides promising solutions\". We hereby answer the specific questions below and provide detailed explanations.\n\n> Paper polishment\n\nThanks for your suggestion. We acknowledge that on-device generation and acceleration are receiving increasing attention. In this regard, we conduct experiments of device model distillation, which are deferred to Appendix B.6 due to page limit. In the final version, we will supplement a detailed discussion on accelerating on-device computation using other SOTA techniques like quantization, sparsity, etc. \n\nRegarding Table 3, as explained at the beginning of Section 5.2, prior work uses distinct formal privacy definitions, making alignment challenging. Furthermore, we believe that empirical privacy, as indicated by privacy attacks, better reflects actual privacy protection.\n\n> Extensibility to other DP mechanisms\n\nThanks for your suggestion. The permute-and-flip mechanism can be regarded as a variant of private selection algorithm, which we consider orthogonal to our work. \nWe believe the permute-and-flip mechanism could be incorporated into Algorithm 2 as a replacement for the Exponential mechanism, and we can explore this as part of future work.\n\n> Typos\n\nThanks for your careful reading. We have corrected the typos in the mean calculation. We will review the entire paper and check for any additional typos in the final version.", "claims_and_evidence": "Technically solid\nmoderate-to-high impact paper", "methods_and_evaluation_criteria": "with no major concerns with respect to evaluation, resources, reproducibility, ethical considerations.", "theoretical_claims": "with no major concerns with respect to theoretical claims.", "experimental_designs_or_analyses": "with no major concerns with respect to soundness/validity of any experimental designs or analyses.", "relation_to_broader_scientific_literature": "[1]: Permute-and-Flip: A new mechanism for differentially private selection", "essential_references_not_discussed": "[1]: Permute-and-Flip: A new mechanism for differentially private selection", "other_strengths_and_weaknesses": "Strengths: 1. The direction of enhancing prompt privacy in LLM inference services is promising.\n2. The idea is neat and straightforward.\n3. The writing is good and easy-to-understand. \n4. Extensive experiments, along with ablation studies showcase the effectiveness of proposed approach. \n5. The utility improvements are promising against prior works in both text classification and text generation tasks.\nWeakness: \nThe proposed solution causes inevitable utility loss to enhance prompt privacy with high efficiency. However, this paper indeed achieves a better privacy-utility trade-off against prior works.", "other_comments_or_suggestions": "1. It would be better if the authors could align the theoretical privacy budgets of different works in Table 3 for better understanding.\n2. I recommend the authors to move the ablation of model distillation into main body. Besides, quantization could be discussed to further improve the efficiency and memory consumption.", "questions_for_authors": "1. See weakness above. I think on-device model acceleration is promising, especially for privacy concerns.\n2. Is the proposed mechanism applicable to other DP mechanisms? E.g., more recent private selection mechanisms like permute-and-flip mechanism[1]?\n3. The calculation of mean(b_i) uses b_{i, k}, does it refer to u_{i, k}?\n\n[1]: Permute-and-Flip: A new mechanism for differentially private selection", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Meta-review: This paper proposed an algorithm to achieve (local) differential privacy at inference time by using an exponential mechanism weighted by a reference model to randomize the tokens in the user prompt. The proposed algorithm is simple and effective and achieves good privacy-utility trade off. The problem of protecting user privacy in LLM inference is important and the reviewers found this paper well writting, easy to follow and the results convincing with extensive experiment results.
Decision: Accept (poster)