💬 NLP

Beyond Theoretical Bounds: Empirical Privacy Loss Calibration for Text Rewriting Under Local Differential Privacy

This paper introduces TeDA, a hypothesis-testing framework that empirically calibrates privacy loss across text rewriting mechanisms under Local Differential Privacy by measuring text distinguishability in surface and embedding spaces, thereby revealing that nominal $\varepsilon$ bounds often fail to reflect actual privacy levels and providing a more reliable basis for comparing privacy-utility trade-offs.

Original authors: Weijun Li, Arnaud Grivet Sébert, Qiongkai Xu, Annabelle McIver, Mark Dras

Published 2026-03-25

📖 5 min read🧠 Deep dive

CC BY 4.0

Original authors: Weijun Li, Arnaud Grivet Sébert, Qiongkai Xu, Annabelle McIver, Mark Dras

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

The Big Picture: The "Privacy Mask" Problem

Imagine you are at a party, and you want to tell a secret story about your day to a new friend, but you don't want them to know exactly who you are or where you live.

To protect yourself, you decide to wear a Privacy Mask. In the world of computers, this mask is called Local Differential Privacy (LDP). Before you send your text message to the server, your phone scrambles the words just enough to hide the truth, but keeps the story understandable.

For years, computer scientists have used a number called $\epsilon$ (epsilon) to measure how good this mask is.

The Theory: They say, "If we set the mask to $\epsilon = 10$ , it is mathematically guaranteed that no one can guess your secret."
The Problem: It turns out that $\epsilon$ is like a speedometer on a broken car. Two different cars might both say they are going "100 mph," but one is actually driving safely on a highway, while the other is careening off a cliff. In this paper, the authors found that two different text-rewriting tools can claim the same privacy number ( $\epsilon$ ), but one might actually leak your secrets, while the other keeps them safe.

The Solution: TeDA (The "Detective" Test)

The authors, a team from Macquarie University, built a new tool called TeDA (Text Distinguishability Audit). Instead of trusting the broken speedometer ( $\epsilon$ ), TeDA acts like a super-sleuth detective.

Here is how TeDA works, using a game analogy:

1. The Setup: The "Whodunit" Game

Imagine the computer takes your original sentence (e.g., "My password is hunter2") and runs it through a privacy mask. It spits out a scrambled version (e.g., "The password hunter is here to stay").

Now, the Detective (TeDA) is given:

The scrambled message.
A lineup of two possible original sentences:
1. "My password is hunter2" (The Truth)
2. "The sky is blue today" (A Fake)

2. The Test

The Detective tries to guess which of the two was the original.

If the Detective guesses correctly, the mask failed (the privacy is weak).
If the Detective guesses wrong (or is just guessing randomly), the mask succeeded (the privacy is strong).

TeDA plays this game thousands of times with different sentences and different "masks" to see who is actually the best at hiding the truth.

The Two Ways the Detective Looks

The paper introduces two types of detectives to make sure they catch every leak:

The Surface Detective (LLM): This detective reads the words. If the scrambled text still sounds a lot like the original (e.g., same sentence structure, similar words), this detective spots it immediately.
The Deep Detective (Embeddings): Sometimes the words change completely, but the meaning stays the same. This detective looks at the "soul" of the sentence (mathematical vectors). Even if the words are totally different, if the "vibe" or meaning is too close to the original, this detective catches it.

The Shocking Discovery

When the authors tested six different popular privacy tools using TeDA, they found a massive gap between theory and reality:

The "Heavy Hitters" (ADePT, DP-BART): These tools claimed a high privacy number ( $\epsilon = 1000$ ), which sounds scary. But when TeDA tested them, they were actually very safe. The scrambled messages were so garbled that the Detective couldn't guess the original at all.
The "Lightweights" (DP-Paraphrase, DP-Prompt): These tools claimed a lower privacy number ( $\epsilon = 10$ ), which sounds safer. But TeDA found they were leaking secrets. The scrambled messages were still too similar to the originals, and the Detective could guess the truth easily.

The Analogy: It's like two people wearing "Safety Vests."

Person A wears a vest labeled "Level 1000 Protection" but it's actually made of heavy steel. You are safe.
Person B wears a vest labeled "Level 10 Protection" but it's actually made of thin paper. You are in danger.
The old way just looked at the label. TeDA checks the material.

Why This Matters

In the real world, companies and researchers need to choose the right privacy tool.

If they trust the old labels ( $\epsilon$ ), they might pick a "paper vest" thinking it's safe, and accidentally leak user data.
Or, they might pick a "steel vest" thinking it's too heavy (bad for utility), when it's actually the perfect balance.

TeDA gives them a calibration scale. It tells them: "Hey, even though these two tools have different labels, they actually offer the same level of real-world privacy."

The Conclusion

The paper argues that we need to stop trusting the theoretical math labels alone. Just like you wouldn't buy a parachute based on the manufacturer's claim without testing it, we shouldn't trust privacy tools without running a detective test.

TeDA is that test. It proves that in the messy, complex world of human language, the only way to know if your secrets are safe is to try to break them yourself.

1. Problem Statement

The widespread adoption of Large Language Models (LLMs) has increased the need to share textual data while preserving privacy. Local Differential Privacy (LDP) addresses this by obfuscating user data locally before release. However, a critical gap exists in evaluating LDP text rewriting mechanisms:

Interpretability of $\epsilon$ : The theoretical privacy budget parameter ( $\epsilon$ ) is difficult to interpret in practice. A nominal $\epsilon$ value does not directly convey the actual amount of information leaked or the probability of an adversary correctly identifying the original input.
Incommensurability: Different mechanisms define privacy at different granularities (e.g., token-level vs. sentence-level). Consequently, identical nominal $\epsilon$ values across different mechanisms can result in vastly different levels of actual privacy leakage.
Lack of Empirical Calibration: Existing empirical auditing frameworks (like Membership Inference Attacks) are primarily designed for centralized DP or tabular data. They struggle with the high-dimensional, discrete, and semantically rich nature of text, where exhaustive enumeration of candidate inputs is intractable.

2. Methodology: TeDA (Text Distinguishability Audit)

The authors propose TeDA, an empirical calibration framework that extends distinguishability-based auditing to natural language. The core idea is to measure the "empirical privacy loss" ( $\epsilon_{emp}$ ) by simulating an adversary attempting to identify the true source text from a privatized output.

Key Components:

Distinguishability-Based Formulation: Instead of relying on theoretical bounds, TeDA treats privacy as a hypothesis testing problem. An adversary is given a privatized text $y$ and a set of candidate original texts $S = \{v_1, ..., v_k\}$ . The goal is to determine which candidate generated $y$ .
Dual-Mode Attacks: To capture different aspects of leakage, TeDA employs two distinct attack strategies:
1. Surface-Level (LLM) Attribution: Uses a Large Language Model (e.g., Qwen3-8B) to judge semantic alignment between the rewritten text and candidates based on wording, phrasing, and syntax.
2. Embedding-Level Attribution: Uses pre-trained embedding models (e.g., all-mpnet-base-v2) to measure vector distance (cosine distance) between the privatized text and candidates. This captures deeper semantic leakage that might persist even if surface forms change.
Candidate Selection Strategy: Recognizing that candidate choice affects leakage estimates, the authors introduce Probabilistic Transition Sampling. This strategy uses a temperature parameter ( $\lambda$ $λ$ ) to control the semantic distance between the true source and distractors:
- $\lambda < 0$ : More-diverse sampling (primary configuration), selecting semantically distant candidates to maximize distinguishability pressure.
- $\lambda > 0$ : More-similar sampling (harder task for the adversary).
- $\lambda \to 0$ : Uniform random sampling.
Efficient Estimator: Standard auditing requires tracking both True Positives (TP) and False Positives (FP), necessitating millions of trials. The authors derive a reduced-form estimator that relies solely on aggregated success events (TPs). By leveraging the symmetry of the hypothesis test, they halve the computational cost (reducing required model queries) while maintaining statistical rigor using the Clopper-Pearson method for confidence intervals.

3. Key Contributions

Framework Design: The first empirical calibration framework specifically designed for LDP text rewriting, bridging the gap between tabular LDP auditing and natural language processing.
Novel Attack Vectors: Introduction of complementary distinguishability attacks (LLM-based and Embedding-based) to assess privacy leakage from both human-perceivable and semantic-structural perspectives.
Unified Candidate Strategy: A probabilistic sampling method that allows researchers to simulate adversaries with varying levels of auxiliary information, ensuring robust calibration results.
Efficiency Optimization: A mathematical reduction of the auditing procedure that makes large-scale evaluation of resource-intensive LLM-based rewriting mechanisms feasible.

4. Experimental Results

The authors evaluated TeDA on six representative LDP text rewriting mechanisms (ADePT, DP-BART, DP-Paraphrase, DP-Prompt, DP-MLM, DP-ST) across four datasets (ATIS, SST-2, SNIPS, Trustpilot).

Divergence of Nominal vs. Empirical $\epsilon$ :
- Sentence-Level Mechanisms (ADePT, DP-BART): Despite operating at high nominal $\epsilon$ (up to 2500), these mechanisms showed near-zero empirical privacy loss ( $\epsilon_{emp} \approx 0$ ). The noise injected into sentence embeddings effectively obscured the source.
- Token-Level Mechanisms (DP-Paraphrase, DP-Prompt, DP-MLM): These showed significantly higher $\epsilon_{emp}$ values that rose with nominal $\epsilon$ . Due to the composition theorem, a sentence of $n$ tokens consumes a total budget of $n\epsilon$ , leading to much looser sentence-level guarantees than reported.
- Conclusion: Identical nominal $\epsilon$ values imply drastically different levels of actual privacy protection depending on the mechanism's granularity.
Complementarity of Attacks:
- Some mechanisms (e.g., DP-MLM) preserved surface structure but shifted semantics, making them easier to identify via LLM attacks but harder via embedding attacks.
- Others (e.g., DP-Prompt) altered surface forms significantly but retained semantic overlap, making them harder for LLMs but easier for embedding-based attacks.
Utility-Privacy Trade-offs:
- Mechanisms with low $\epsilon_{emp}$ (ADePT, DP-BART) suffered significant drops in downstream utility (e.g., intent classification F1 scores).
- Mechanisms with higher $\epsilon_{emp}$ (token-level methods) preserved more utility but offered weaker privacy guarantees against attribute inference.
Anomaly Detection: TeDA identified specific behavioral anomalies, such as DP-BART's non-monotonic behavior at very high $\epsilon$ (where outputs diverged into generic content due to signal-to-noise ratio issues) and DP-Paraphrase's insensitivity to $\epsilon$ changes (due to the model's strong prior toward specific sentence starters).

5. Significance

Practical Benchmarking: TeDA provides a "common footing" for comparing LDP mechanisms that use different reporting granularities, moving beyond theoretical bounds to measurable, real-world privacy loss.
Deployment Guidance: It offers a practical tool for practitioners to select mechanisms based on actual privacy-utility trade-offs rather than nominal $\epsilon$ values.
Auditing Insight: The framework can detect implementation flaws or unexpected behaviors in privacy mechanisms (e.g., post-processing effects or model priors dominating the output) that theoretical analysis might miss.
Scalability: By reducing the computational cost of auditing, TeDA enables the evaluation of complex, LLM-based privacy mechanisms at a scale previously considered prohibitively expensive.

In summary, the paper argues that theoretical $\epsilon$ is insufficient for characterizing privacy in text rewriting. TeDA offers a rigorous, empirical, and efficient alternative to calibrate and compare these mechanisms, revealing that "equal" privacy budgets often yield unequal privacy protections.