C lu S an T : Differentially Private and Semantically Coherent Text Sanitization (2025)

Abstract: We introduce CluSanT, a novel text sanitization framework based on Metric Local Differential Privacy (MLDP). Our framework consists of three components: token clustering, cluster embedding, and token sanitization. For the first, CluSanT employs Large Language Models (LLMs) to create—a set of potential substitute tokens which we meaningfully cluster. Then, we develop a parameterized cluster embedding that balances the trade-off between privacy and utility. Lastly, we propose a MLDP algorithm which sanitizes/substitutes sensitive tokens in a text with the help of our embedding. Notably, our MLDP-based framework can be tuned with parameters such that (1) existing state-of-the-art (SOTA) token sanitization algorithms can be described—and improved—via our framework with extremal values of our parameters, and (2) by varying our parameters, we allow for a whole spectrum of privacy-utility tradeoffs between the two SOTA. Our experiments demonstrate CluSanT’s balance between privacy and semantic coherence, highlighting its capability as a valuable framework for privacy-preserving text sanitization.

## introduction the advent of digital technology has led to an exponential increase in the generation and processing of textual data, elevating the importance of privacy within the realm of natural language processing (nlp) @xcite . differential privacy (dp) @xcite , known for its strong mathematical privacy guarantees, presents a viable solution to these challenges. however, applying dp in nlp is fraught with difficulties due to the complex nature of textual data @xcite . existing implementations of dp in nlp typically degrade semantic integrity and readability for humans, posing significant challenges for applications requiring high-quality, coherent text processing. this underscores the need for advanced methods capable of finely balancing privacy with utility @xcite @xcite @xcite . current state-of-the-art (sota) techniques, such as santext @xcite and custext @xcite , illustrate these challenges. san-text, while focused on maximizing privacy, may significantly diminish the utility of sanitized text. conversely, custext can preserve better text utility but can only achieve privacy in a limited manner. santext achieves metric local dp (mldp) text sanitization by probabilistically replacing individual sensitive tokens (e.g., 'paris') with alternative ones (e.g., 'lyon'). replacements are selected with probability proportional to their semantic distance to the original, in a manner similar to the exponential mechanism @xcite in dp literature. while for smaller number of tokens this achieves meaningful replacements, applying this broadly can increase the likelihood of selecting less desirable ones. for instance, while 'lyon' should be one of the top replacements for 'paris,' the combined probability of a large number of low-utility city names can outweigh 'lyon,' leading to poor choices. in response, custext proposed to first cluster tokens based on their similarity. it then performs replacements by selecting only tokens from the relevant cluster, via the exponential mechanism. though improving utility, this approach also limits custext's privacy guarantees to within each cluster. how can we reconcile this conflict between privacy and utility in the sota? we answer this question by introducing clusant, 1 a novel framework for text sanitization consisting of three components: (1) token clustering, (2) cluster embedding, and (3) token sanitization. clusant allows its users to tune their desired privacy/utility tradeoff by controlling the likelihood to choose a sanitized token from a more optimal cluster. independent of the frame-work, we also propose several improvements and evaluation metrics that we experimentally show augment the sota. notably, while clusant's token sanitization algorithm is based on various parameters, it achieves mldp guarantees (thm. 5) for any valid parameters, allowing for flexible plugand-play. we outline our general approach through the following main technical challenges. ## related works the most direct strategy for sanitizing text is directly masking sensitive elements @xcite , which can reduce text utility. instead, differential privacy can replace quasi-identifiers with semantically similar terms. the sota are santext @xcite and cus-text @xcite , which we detail in sec. 3. the most recent work in this line @xcite proposed rantext, an exponential mechanism-based approach for token replacement, with the goal to produce perturbed prompts for llms. however, their stated privacy (theorem 2) is limited to tokens in specific adjacency lists (similar to how custext's privacy is limited to each clustering), rather than standard mldp foot_1 . another work @xcite attempts to choose replacement words within a radius of the original word; however, as radii generally do not partition the set of words, this method appears incompatible with clustering-based algorithms like custext. we moreover were not able to find the code of the algorithm. consequently, we choose not to exper-imentally compare with these works at this time. one improvement we made in our experiments are the datasets used. instead of an ad-hoc method of identifying sensitive words, we use the tab benchmark of @xcite , a corpus of 1,268 english-language court cases from the european court of human rights (echr), with the sensitive data manually-annotated in each document. several works add dp noise to text representations @xcite @xcite or use adversarial training @xcite @xcite to create these representations. these methods produce non-human-readable outputs for ml pipelines, addressing different problems. other works specific to downstream tasks include e.g., training a learning algorithm @xcite . like sota, we produce sanitized text for general use rather than private representations. lastly, @xcite argues that sanitization via replacing individual tokens within a text limits syntax variability, and can lead to e.g., grammar errors. they instead propose paraphrasing via gpt-2. however, we believe our line of works will continue to be useful, since (1) token-based sanitization, such as clusant, do not appear to conflict with, and may even complement paraphrasing, and (2) certain contexts require specific syntax, e.g., legal documents @xcite in our experiments. moreover, one may mitigate certain grammar issues through clustering to separate grammatically dissimilar tokens (e.g., by putting 'britain' and 'british' in different clusters). ## preliminaries following sota, we privatize text by randomising each token (e.g., 'paris', 'united states') deemed 'sensitive', in a way that preserves metric local differential privacy (mldp) @xcite . we call a token sanitization mechanism a (randomised) algorithm which takes as input a token and outputs a token which we call the sanitized token. below, we define ldp. informally, a mechanism m is ldp if from its output (sanitized token) y, one cannot tell if the original input (token) was x or x ′ . pr[m (x ′ )=y] ≤ e ϵ . metric ldp @xcite is a variant/extension of ldp for better utility, by tuning privacy with respect to a distance metric. here, one can more easily distinguish whether y is the output of m (x) or m (x ′ )-if x, x ′ are far apart. specifically, a mechanism m satisfies mldp for a given privacy parameter ϵ ≥ 0 and distance metric d : x ×@xmath0, if the following condition holds for all x, x ′ ∈ x, @xmath1: pr[m (x)=y] pr[m (x ′ )=y] ≤ e ϵ•d(x,x ′ ) . lastly, the exponential mechanism has been applied extensively in previous work on token sanitization (e.g., santext, custext, rantext). informally, it selects a sanitized token with probability proportional to its closeness to the original token (with closeness defined via utility function u). definition 2. @xcite ] let i be a finite set denoting the input space, and o be a finite set denoting the output space. let u(x, y) be a utility function foot_2 defined for any @xmath2, and let ∆@xmath3, ϵ @xmath4. the exponential mechanism, parametrized by i, o, u, ∆u, runs the following: m e (x) (with @xmath5: randomly select @xmath6, where two useful facts from @xcite are as follows. theorem 1. for the exponential mechanism m e , the following hold: if we set parameter ∆@xmath7, y) = -d(x, y) for a metric d, then m e is ϵ-mldp. ## clusant: cluster exponential mechanism with mldp guarantees clusant first clusters tokens based on their similarity. it then sanitizes sensitive tokens by first selecting a cluster, then selecting the replacement token from within that cluster. this approach makes contextually relevant replacements, improving the utility of sanitized text over santext while still maintaining mldp. clusant's privacy guarantees hold for any clustering, allowing for flexible integration of different clustering methods. in this section, we present two of the components in our clusant framework: cluster embedding (sec. 4.1) and token sanitization (sec. 4.2). the method of obtaining a token clustering is independent of this section and will be detailed in our experiments (see sec. 5). through parameterizing our clustering, and cluster embedding with a parameter k, we obtain a spectrum of token sanitization mechanisms that range from santext at one extreme and custext at the other extreme (see sec. 4.1.1). for now, we assume we already have a set of token clusters {c}. ## conclusion we introduced clusant, a novel framework for text sanitization that achieves metric local differential privacy (mldp). clusant comprises token clustering and token sanitization, leveraging large language models to generate substitute tokens, which are then clustered, and sanitized using a mldp algorithm. our mldp framework encompasses a range of privacy-utility tradeoffs via tuneable parameters between state-of-the-art algorithms san-text and custext, allowing users to achieve strong privacy or high utility as required. our framework achieves mldp guarantees regardless of the clustering, allowing for plug-and-play (and future optimization) of this component in our framework. in summary, clusant advances the area of privacypreserving text processing, offering a robust, tuneable solution for handling sensitive text.