Leveraging Semantic Triples for Private Document Generation with Local Differential Privacy Guarantees

Stephen Meisenbacher, Maulik Chevli, Florian Matthes · 2025

Read Leveraging Semantic Triples for Private Document Generation with Local Differential Privacy Guarantees by Stephen Meisenbacher, Maulik Chevli, Florian Matthes (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2508-20736.txt.

Introduction

Stephen Meisenbacher, Maulik Chevli, and Florian Matthes present a way to rewrite private documents with a formal privacy shield, in a 2025 paper. Local differential privacy asks that any one text look much like any other after rewriting, within a set bound. That demand is steep, and past work shows sensible rewriting needs a loose bound, which weakens the shield.

Their method, DP-ST, first breaks a document into semantic triples: small who-does-what facts. Privacy is then spent within a neighborhood of like facts, not the whole text at once. A large language model smooths the result back into flowing prose. Tests showed coherent output even at tight bounds, balancing privacy with use.

Catalog record

CREATORStephen Meisenbacher, Maulik Chevli, Florian Matthes
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE85 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2508-20736

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

Leveraging Semantic Triples for Private Document Generation with Local Differential Privacy Guarantees Stephen Meisenbacher, Maulik Chevli, Florian Matthes Abstract Many works at the intersection of Differential Privacy (DP) in Natural Language Processing aim to protect privacy by transforming texts under DP guarantees. This can be performed in a variety of ways, from word perturbations to full document rewriting, and most often under local DP. Here, an input text must be made indistinguishable from any other potential text, within some bound governed by the privacy parameter ε \varepsilon . Such a guarantee is quite demanding, and recent works show that privatizing texts under local DP can only be done reasonably under very high ε \varepsilon values. Addressing this challenge, we introduce DP-ST , which leverages semantic triples for neighborhood-aware private document generation under local DP guarantees. Through the evaluation of our method, we demonstrate the effectiveness of the divide-and-conquer paradigm, particularly when limiting the DP notion (and privacy guarantees) to that of a privatization neighborhood . When combined with LLM post-processing, our method allows for coherent text generation even at lower ε \varepsilon values, while still balancing privacy and utility. These findings highlight the importance of coherence in achieving balanced privatization outputs at reasonable ε \varepsilon levels. 1 Introduction Figure 1: An overview of the DP-ST pipeline. In the Preparation stage, publicly available texts are decomposed into semantic triples and stored in a vector database with cluster indices. Then, during Privatization , each extracted triple from an input document is replaced with a differentially private triple achieved through the use of the Exponential Mechanism. All private triples are woven together into a reconstructed private document as the output. The field of text privatization encompasses a variety of techniques Sousa and Kern 2023 , ranging from anonymization to differentially private text rewriting methods Hu et al. 2024 . Such methods strive to balance the removal or perturbation of sensitive data and usefulness of the resulting text for the downstream applications, resulting in the so-called privacy-utility tradeoff. Differential Privacy (DP) Dwork 2006 , being a mathematically grounded notion of privacy, provides a useful starting point for balancing the privacy-utility trade-off through the \varepsilon parameter, or the privacy budget . The application of DP in text privatization can be performed at various lexical levels, such as words, sentences, or documents. Earlier works introduced the divide-and-conquer paradigm, e.g., where the word is chosen as the unit of protection, and full texts are privatized by composing word-level DP guarantees Fernandes et al. 2019 ; Feyisetan et al. 2020 ; Carvalho et al. 2023 ; Arnold et al. 2023 . Such composed texts, however, can lack coherence and grammatical structure Mattern et al. 2022 . Later works diverged from this paradigm and introduced methods for providing document-level guarantees, namely through DP noise addition on various text representations Weggenmann et al. 2022 , such as the latent vector in a BART model Igamberdiev and Habernal 2023 . However, these approaches lack the control over which information to privatize, as opposed to word-level approaches. Moreover, they require a higher privacy budget to generate text that has reasonable utility since these works follow the strict local DP definition Igamberdiev and Habernal 2023 . Recent works have leveraged the Exponential Mechanism (EM) McSherry and Talwar 2007 in the generation step of language models, allowing for contextualized privatization and the ability to steer DP privatization with next token prediction probabilities Bo et al. 2021 ; Mattern et al. 2022 ; Utpala et al. 2023 ; Meisenbacher et al. 2024 , thus providing a token -level DP guarantee. However, these do not view the DP privatization task as a bounded privacy budget problem, thereby exacerbating the issue of weak document-level privacy guarantees. Additionally, EM-approaches cannot guarantee grammatical correctness or coherence, due to randomization in the token prediction step. We address these challenges by introducing DP-ST , a text privatization method with slightly relaxed local DP guarantees, which we call neighborhood-aware DP, for enhanced utility. DP-ST leverages a different divide-and-conquer paradigm, by first decomposing input documents into only their core information , represented by semantic subject-verb-object (SVO) triples Schneider et al. 2024 , or simply, semantic triples . Only these triples are privatized under local DP guarantees, aided by a corpus of clustered public semantic triples, whereby the privatization of a triple only considers the public triples within the most semantically similar cluster. Finally, DP-ST takes advantage of the post-processing principle of DP, in that privatized triples are woven together by an LLM to output a reconstructed private document. We find that using DP-ST for local DP text privatization allows for strong privacy protections and utility preservation, while also doing so under low document-level privacy budgets. We show that in comparison to state-of-the-art methods, DP-ST performs considerably better in terms of ensuring coherent outputs and balancing the privacy-utility trade-off. Our experimental results demonstrate the impact of careful DP mechanism design, and we also highlight the importance of reasonable privacy budgets in local DP text privatization, providing a method that begins to reverse the trend of very large or even unbounded privacy budgets. Our work contributes to the field of text privatization and DP text rewriting with the following: 1. We propose DP-ST , which leverages semantic triple decomposition and LLM post-processing for coherent and privacy-preserving text generation under local DP. 2. We demonstrate the effectiveness of DP-ST outputs in utility and privacy experiments, which outperforms SOTA methods in finding positive privacy-utility trade-offs. 3. We open-source the code for triple corpus creation and clustering, as well as the DP-ST method. The repository is found at https://github.com/sjmeis/DPST . 2 Foundations and Related Work DP mechanisms lend plausible deniability to the input of the mechanism by adding calibrated noise to the output. Hence, an observed output cannot be attributed to a specific input with a high probability. Formally, for finite spaces \mathcal{P} and \mathcal{V} with n and m elements respectively, a randomized mechanism \mathcal{M}:\mathcal{P}\to\mathcal{V} is a local \varepsilon -DP mechanism iff \forall x,y\in\mathcal{P} and \forall z\in\mathcal{V} , the following holds: Pr[\mathcal{M}(x)=z]\leq e^{\varepsilon}Pr[\mathcal{M}(y)=z] The translation of DP into NLP (DP NLP) has increased in research interest in recent years, resulting in a great deal of works investigating primarily either model training with DP or DP text privatization Hu et al. 2024 . The integration of DP into NLP, largely dealing with unstructured data, presents several initial challenges as the original notion of DP was designed for structured, tabular data Klymenko et al. 2022 . Beyond this, research in DP NLP carries an extra responsibility of showing that new methods can empirically improve privacy protections, while also abiding by the theoretical constraints of the DP definition. The constraints of DP in the context of NLP have led to many challenging, yet interesting research directions. Mattern et al. 2022 highlight the difficulty in privatizing texts under DP constraints while also maintaining grammatical correctness and semantic coherence, while Igamberdiev and Habernal 2023 echo this notion by demonstrating that such coherence can only be achieved at much higher privacy budgets. Other works point to crucial considerations that must be made in the design and evaluation of DP NLP methods, including ensuring adherence to DP Habernal 2021 , increasing transparency in evaluation Igamberdiev

Read the complete text