Metric Differential Privacy for Text

49 concepts35 papers1 proposal

When applying traditional Differential Privacy (DP) to databases, the goal is to make the presence or absence of any single individual's record indistinguishable. However, applying this standard directly to natural language introduces a fundamental challenge. Language is discrete, high-dimensional, and deeply structured.

If you apply standard Local Differential Privacy (LDP) to a word, the mathematical guarantee requires that any given input word could be replaced by any other word in the entire vocabulary with a similar probability. In practice, this means a sensitive word like "HIV" might be replaced by "banana," "quantum," or "refrigerator." This completely destroys the grammatical structure and meaning of the text, turning coherent sentences into an unusable "word salad."

To solve this, researchers developed Metric Differential Privacy (mDP) (often operationalized as $d_\chi$-privacy). Instead of treating all words as equally distinct, mDP leverages the geometric properties of word embeddings to scale privacy protection according to semantic distance.

The Core Intuition: Semantic Neighborhoods

The core insight behind metric differential privacy is that we do not need a word to be indistinguishable from every word in the language; we only need it to be indistinguishable from words within its immediate semantic neighborhood. For instance, "doctor" should be plausibly deniable with "physician," "surgeon," or "cardiologist."

Standard LDP:   [doctor]  ---> Equiprobable jump to ---> [banana], [quantum], [physician]
Metric LDP:     [doctor]  ---> High probability    ---> [physician], [surgeon]
                          ---> Low probability     ---> [banana]

By grounding privacy in a metric space—typically a continuous word embedding space where distance correlates with meaning—the mechanism ensures that the utility and underlying logic of the text are preserved. As reviewed by Lijie Hu et al. in Differentially Private Natural Language Models: Recent Advances and Future Directions, embedding perturbation scales noise injection based on these semantic distances, ensuring that private word replacements remain contextually relevant for downstream tasks.

How It Works: Perturbation and Projection

The standard pipeline for metric differential privacy on text, formalized by Oluwaseyi Feyisetan et al. in Privacy- and Utility-Preserving Textual Analysis via Calibrated Multivariate Perturbations, operates in three distinct steps:

  1. Mapping: A discrete token from the text is mapped to a high-dimensional vector space using a pre-trained embedding model (e.g., GloVe or FastText).
  2. Perturbation: Calibrated noise drawn from a continuous distribution (such as a multivariate Laplace or Exponential distribution) is added to the vector. The scale of this noise is determined by the desired privacy budget ($\epsilon$) and the distance metric of the space.
  3. Projection: Because the resulting noisy vector does not land exactly on a real word, a nearest-neighbor search is performed to map the noisy vector back to the closest discrete entry in the vocabulary.

To make these systems practical, Oluwaseyi Feyisetan et al. demonstrated in Calibrating Mechanisms for Privacy Preserving Text Analysis that privacy can be intuitively configured using the "hiding set" (the number of alternative words an input could plausibly have mapped from) and the "retention probability" (the likelihood of a word remaining unchanged), rather than relying solely on abstract $\epsilon$ values.

While Euclidean space is common, it is not the only geometry available. Oluwaseyi Feyisetan et al. also showed in Hyperbolic Embeddings for Preserving Privacy and Utility in Text that moving text perturbations into curved, hyperbolic spaces can better capture the hierarchical relationships of language, yielding up to a 20-fold improvement in privacy guarantees over flat-space methods.

Discrete Selection via the Exponential Mechanism

An alternative to adding noise to continuous vectors and projecting them back is to perform the selection directly in the discrete vocabulary space using the Exponential Mechanism.

Instead of moving vectors, this approach calculates a semantic score for every potential replacement word in the vocabulary based on its distance from the original word. As implemented by Fengran Mo and Sai Chen in A Customized Text Sanitization Mechanism with Differential Privacy, a scoring function assigns selection probabilities to candidate words. By using the exponential mechanism, researchers can bypass the strict triangle inequality requirements of metric-based vector spaces, allowing them to use non-metric similarity measures like cosine similarity or counter-fitted embeddings that are explicitly optimized to group synonyms together.

Similarly, Minxin Du et al. demonstrated in Differential Privacy for Text Analytics via Natural Text Sanitization that sampling replacements directly from a precomputed probability matrix avoids the high computational overhead of high-dimensional continuous noise generation, making local text sanitization highly efficient.

Taming the Long Tails: Neighborhoods and Truncation

Despite the elegance of scaling noise by distance, continuous noise distributions inherently possess "long tails." Under strict privacy budgets (low $\epsilon$), the added noise can be large enough to occasionally kick a word completely out of its semantic neighborhood, reintroducing the "word salad" problem.

To combat this, two primary optimization strategies have emerged:

1. Neighborhood Restriction

Instead of considering the entire vocabulary as potential replacements, the mechanism's output space is restricted to a small, pre-defined neighborhood of semantically similar candidates. Fengran Mo and Sai Chen proved that narrowing the search space to a word's closest neighbors significantly reduces the absolute noise introduced during data sanitization, dramatically improving downstream utility while preserving formal privacy boundaries.

2. Noise Truncation

Rather than restricting the vocabulary beforehand, the noise distribution itself can be modified. Di Wang et al. introduced a "High-Dimensional Truncated Laplacian" (TrLaplace) mechanism in Private Language Models via Truncated Laplacian Mechanism. By mathematically bounding the noise distribution in the embedding space, they eliminate the extreme outliers that cause semantic incoherence, ensuring that a privatized word maintains its broad logical category (e.g., replacing a specific time with another time, rather than an unrelated noun).

Standard Laplace Noise:    [------- Long Tail Outliers Possible -------]
Truncated Laplace Noise:   [--- Bounded Semantic Neighborhood Only ---]

Scaling Up: From Words to LLM Inference

As the field has transitioned from simple text classification to Large Language Models (LLMs), metric differential privacy has scaled from individual tokens to broader contexts.

Sentence-Level Privacy

Word-by-word perturbation can sometimes fail to mask high-level conceptual themes or stylistic fingerprints. To address this, Casey Meehan et al. proposed Sentence-level Privacy for Document Embeddings. By ensuring that no single sentence uniquely identifies a document's overall embedding, this approach effectively masks macro-level sensitive themes that word-level perturbations might leak.

Client-Side LLM Sanitization

In modern cloud-based AI architectures, users routinely send sensitive prompts to remote LLMs. Metric differential privacy serves as an ideal framework for local, client-side sanitization.

For instance, the DYNTEXT framework by Juhua Zhang et al. (DYNTEXT: Semantic-Aware Dynamic Text Sanitization for Privacy-Preserving LLM Inference) dynamically adjusts the size of the candidate replacement list based on a word's semantic density, ensuring optimal privacy-utility trade-offs before a prompt leaves the user's device.

Similarly, Honglan Yu et al. developed a framework (Towards Confidential and Efficient LLM Inference with Dual Privacy Protection) that identifies sensitive tokens on a client-side trusted environment, adds Laplace noise to the similarity scores of potential replacements, and sends the sanitized tokens to remote GPUs. Because the core meaning remains intact, the remote cloud model can still generate highly accurate, contextually coherent responses without ever seeing the user's exact private text.

Key Foundational Work

SynTF: Synthetic and Differentially Private Term Frequency Vectors for Privacy-Preserving Text Mining (2018) — contributed 1 concept elements to this direction.
Frequent grams based embedding for privacy preserving record linkage (2012) — contributed 1 concept elements to this direction.
History & citationVersion 1 · 2026-10-04

Current · Permanent link

View frozen version 1

Cite this direction

Latest version (a living page):

@misc{lacuna_metric_differential_privacy_13238f87,
  title = {metric differential privacy},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/metric-differential-privacy/rdr_13238f8715e147e3b100b1502e24a54a},
  note = {Latest version of a living research direction; cite a version for a fixed text. Accessed 2026-11-19},
}

This exact version (version 1, frozen text):

@misc{lacuna_metric_differential_privacy_13238f87_v1,
  title = {metric differential privacy},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/metric-differential-privacy/rdr_13238f8715e147e3b100b1502e24a54a/v/1},
  note = {Version 1, frozen 2026-10-04. Accessed 2026-11-19},
}
About

These directions overlap with this one through shared papers.

See something wrong? Report a mistake