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 ε .
Differential Privacy (DP) for text matured from disjointed word-level substitutions to contiguous sentence-level rewriting by leveraging the generative capacity of language models. While this form of text privatization is best suited for balancing formal privacy guarantees with grammatical coherence, its impact on the register identity of text remains largely unexplored. By conducting a multidimensional stylistic profiling of differentially-private rewriting, we demonstrate that the cost of privacy extends far beyond lexical variation. Specifically, we find that rewriting under privacy constraints induces a systematic functional mutation of the text's communicative signature. This shift is characterized by the severe attrition of interactive markers, contextual references, and complex subordination. By comparing autoregressive paraphrasing against bidirectional substitution across a spectrum of privacy budgets, we observe that both architectures force convergence toward a non-involved and non-persuasive register. This register-blind sanitization effectively preserves semantic content but structurally homogenizes the nuanced stylistic markers that define human-authored discourse.
Despite the strengths of modern anonymization and de-identification techniques, the risk of re-identification remains significant due to the indirect identifiers remaining in texts. To address this problem, recent works have applied text rewriting under Differential Privacy (DP) to prevent data linkage by perturbing texts via noise addition. Such methods privatize all tokens in a text indiscriminately, diminishing text quality and usability in critical domains such as in clinical settings. Focusing on indirect personal identifiers (IPIs), we introduce a utility-preserving DP text rewriting method that only privatizes spans containing IPIs. We show that our method effectively reduces re-identification risks in clinical texts while being producing more coherent and usable output texts, leading to higher privacy-utility trade-offs. In this, we demonstrate the effectiveness of hybrid text privatization, which leverages the promise of DP in an efficient, usable manner.
Ibrahim Baroud, Stephen Meisenbacher, Sebastian Möller +2
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
The goal of differentially private text obfuscation is to obfuscate, or "perturb", input texts with Differential Privacy (DP) guarantees, such that the private output texts are quantifiably indistinguishable from the originals. While perturbation at the word level is intuitive, meaningful text privatization happens on complete documents. Recent research has laid the groundwork for reasoning about privacy budget distribution, namely, how an overall ε budget can be sensibly distributed among the component pieces of a text. We perform a systematic evaluation of multiple text decomposition and budget distribution techniques in the context of DP text obfuscation, testing how different methods for chunking texts can be combined with techniques for allocating ε to these chunks. Our experiments reveal that such design choices are very important, as even with comparable privacy budgets, significantly different results can occur based on which methods are chosen. In this, we provide credible evidence of the feasibility of maximizing empirical trade-offs by optimizing DP obfuscation procedures.
Stephen Meisenbacher, Angelo Kleinert, Florian Matthes
Technical University of Munich School of Computation, Information and Technology Department of Computer Science Garching, Germany