The growing use of large language models has increased interest in sharing textual data in a privacy-preserving manner. One prominent line of work addresses this challenge through text rewriting under Local Differential Privacy (LDP), where input texts are locally obfuscated before release with formal privacy guarantees. These guarantees are typically expressed by a parameter ε that upper bounds the worst-case privacy loss. However, nominal ε values are often difficult to interpret and compare across mechanisms. In this work, we investigate how to empirically calibrate across text rewriting mechanisms under LDP. We propose TeDA, which formulates calibration via a hypothesis-testing framework that instantiates text distinguishability audits in both surface and embedding spaces, enabling empirical assessment of indistinguishability from privatized texts. Applying this calibration to several representative mechanisms, we demonstrate that similar nominal ε bounds can imply very different levels of distinguishability. Empirical calibration thus provides a more comparable footing for evaluating privacy-utility trade-offs, as well as a practical tool for mechanism comparison and analysis in real-world LDP text rewriting deployments.
Figures & tables
Figure 1: Text Distinguishability Audit for empirical privacy assessment of text rewriting mechanisms. (1) A mechanism M produces privatized text at a given privacy budget εtheoretical ; (2) an adversary A attempts to identify the true source vi from a candidate set S ; (3) A correct attribution indicates empirical distinguishability, while an incorrect attribution indicates indistinguishability.
Method
Rewriting
Ref: I’ve only used it once and it helped! PLEASE DO NOT SHARE MY NAME OR E-MAIL ADDRESS!
ε=1000
ADePT
sues run barcelona because now provided 80 if drive believe flood smart situation sold sign
DP-BART
Click here to view the latest edition of SHARE THIS STORY Helen
DP-Paraphrase
I Democratic People helm the White House. foggy skies violence. I dysphagia. I classroom.
DP-Prompt
I’ve only used it once and it helped! Please do not share my name or E-mail address!
Table 1: Example text rewritings at the same theoretical ε by ADePT ( Krishna et al., 2021 ) , DP-BART ( Igamberdiev and Habernal, 2023 ) , DP-Paraphrase ( Mattern et al., 2022 ) , DP-Prompt ( Utpala et al., 2023 ) , DP-MLM ( Meisenbacher et al., 2024 ) and DP-ST ( Meisenbacher et al., 2025 ) .
Figure 2: Empirical calibration results under the LLM distinguishability attack across datasets. The x-axis shows nominal ε and the y-axis shows estimated empirical privacy loss εemp . The dashed horizontal line marks the finite-sample ceiling ( ≈7.54 , k=2 , T=104 ).
Figure 3: Empirical calibration results under the external ( top ) and internal ( bottom ) embedding distinguishability attacks across datasets. Axes and ceiling as in Figure 2 .
Figure 4: Downstream utility and privacy attribute protection across LDP text rewriting methods, evaluated at ε∈{250,1000,2500} with error bars over 3 random seeds. (a) SNIPS intent classification and (b) Trustpilot sentiment report utility F1 (higher is better). (c) Trustpilot gender attribute inference F1 measures resistance to private attribute inference (lower is better).
Text
Case 1: LLM correct, embedding wrong (DP-MLM)
Rewritten
moving from india to salt washing
True input
flights from indianapolis to seattle washington
Distractor
what is bna
Case 2: LLM wrong, embedding correct (DP-Prompt)
Rewritten
the following restrictions are not included in the text
Table 2: Complementary behavior of LLM and embedding attacks on ATIS.
Figure 5: Empirical calibration results under T=104 and 106 Monte Carlo trials with DP-MLM on ATIS, showing consistent trends across ε values.
Figure 6: Results under three candidate selection strategies on the ATIS dataset: (a) more-diverse sampling ( λ =-10,000), (b) uniform random sampling ( λ =0), and (c) more-similar sampling ( λ =10,000). While the empirical privacy loss varies depending on the auxiliary information available to the adversary, the relative ranking and trends across different LDP mechanisms remain consistent.
Appendix figures & tables5 assets
Supplementary material from the paper’s appendix.
Appendix
Method
Rewriting
Ref: I had previously used and bought from Boilerjuice, so it had on record somewhere a USER name and EMAIL ADDRESS for me
ε=1000
ADePT
zoo retired results now package counts comeback such because
DP-BART
Quote from Boiler Room "I just can’t believe it
DP-Paraphrase
I Stapped on Bo resurgence. I tribeed on Boilerju pioneered. I————-
DP-Prompt
I had previously used and bought from Boilerjuice , so it had on record somewhere a USER name and EMAIL ADDRESS for me
Appendix
Table 3: Example outputs of six LDP text rewriting mechanisms under the same theoretical ε on Trustpilot reviews ( Hovy et al., 2015 ) .
Seed
Output
Ref: After many tries, I got it to work. I hope it’s fixed for next time!
ε=2500 (high variance, divergent outputs)
42
A while back, I got a call from my friend, Nathan.
1234
The following is a rush transcript. Copy may not be in its final form.
101
Atheist "It’s time to get started. I
ε=1000 (low variance, semantically consistent)
Appendix
Table 4: DP-BART output variability across random seeds at different ε values. At ε=2500 , outputs exhibit high variance and diverge into generic or unrelated content ( e.g., media templates, religious terms), while at ε=1000 , outputs remain semantically consistent across seeds.
Figure 10: Signal-to-noise ratio (SNR) analysis of DP-BART across different ε values. (a) The clipping operation forces all post-clip sentence embeddings to have approximately constant L2 norm ( ≈ 5.7), while noise magnitude decreases as ε increases. (b) The resulting SNR varies significantly: high SNR at ε=2500 (4.07), balanced SNR at ε=1000 (1.60), and low SNR at ε=250 (0.41), corresponding to different output quality regimes.
Method
Output
Original: listen to westbam alumb allergic on google music
The peoplecats are on the internet. The people are on the
ε=2500
The people are rainbow colored. The people are on the internet
Appendix
Table 5: Comparison of three token-level LDP text rewriting methods on a SNIPS sentence ( Coucke et al., 2018 ) , illustrating differences in tokenization and semantic fidelity.
Figure 11: Token probabilities at the first generated position reveal that the GPT-2 paraphraser used by the DP-Paraphrase (as reproduced by Meisenbacher et al. (2024) ), fine-tuned on SNLI ( Bowman et al., 2015 ) entailment pairs, has an overwhelming prior toward SNLI-style sentence starters ( e.g., ‘ The’ at 71.6% for ε=2500 ), while the original token ‘ listen’ has negligible probability ( ≤2.3×10−3 ) at various ε values. Increasing ε further concentrates the distribution on these prior-favored tokens, making the generated output insensitive to the adjustment of ε .
Quality & Usability Lab, Technical University of Berlin, Berlin, Germany · German Research Center for Artificial Intelligence (DFKI), Berlin, Germany · Technical University of Munich, School of CIT, Garching, Germany +1