Zero-Shot Privacy-Aware Text Rewriting via Iterative Tree Search (2025)

Abstract: The increasing adoption of large language models (LLMs) in cloud-based services has raised significant privacy concerns, as user inputs may inadvertently expose sensitive information. Existing text anonymization and de-identification techniques, such as rule-based redaction and scrubbing, often struggle to balance privacy preservation with text naturalness and utility. In this work, we propose a zero-shot, tree-search-based iterative sentence rewriting algorithm that systematically obfuscates or deletes private information while preserving coherence, relevance, and naturalness. Our method incrementally rewrites privacy-sensitive segments through a structured search guided by a reward model, enabling dynamic exploration of the rewriting space. Experiments on privacy-sensitive datasets show that our approach significantly outperforms existing baselines, achieving a superior balance between privacy protection and utility preservation.

## introduction the rapid integration of large language models (llms) into cloud-based applications has amplified privacy concerns, as user-generated texts often inadvertently disclose sensitive personal information. in domains ranging from healthcare @xcite to legal proceedings @xcite and social media interactions @xcite , the submission of unfiltered inputs to llm apis risks exposing details like medical histories, identities, or locations, which may be logged, analyzed, or misused by service providers. traditional anonymization techniques, such as rulebased redaction or scrubbing, frequently compromise textual naturalness and utility, producing outputs that are awkward or semantically diminished. while finetuning llms on privacy-sanitized datasets @xcite mitigates some risks, 1 corresponding author. advancements in llm-driven text anonymization have begun to address these challenges by leveraging generative capabilities to balance privacy preservation with utility and naturalness @xcite @xcite . these techniques surpass the limitations of text-based differential privacy (dp) methods @xcite , which introduce noise to obscure identities but often result in degraded readability and task performance. instead, they utilize accessible opensource models, such as t5 @xcite and llama2-7b @xcite , to perform targeted paraphrasing that reworks sensitive elements while maintaining the original intent. despite these progresses, existing approaches remain constrained in three critical ways. first, they predominantly operate on predefined personally identifiable information (pii) categories or statically detected spans, offering limited adaptability to dynamic or user-specified privacy profiles-such as custom sensitivities to financial details in professional narratives or ideological nuances in public discourse @xcite . second, achieving robust results with open-source llms typically requires finetuning on specialized datasets, which are often unavailable or costly to curate for underrepresented domains. third, by applying uniform strategies across all private elements, these methods overlook varying levels of information sensitivity-treating a casual mention of a hobby equivalently to protected health data-which leads to either excessive modifications that erode util-ity or inadequate protections that allow inference attacks, thus hindering precise calibration of the privacy-utility-naturalness trade-off. we address these gaps with napare, a zeroshot, iterative tree-search algorithm for naturalness and privacy-aware text rewriting, deployable on medium-sized local llms to ensure fully offline operation. formally, given a privacy specification p-encompassing pii lists, textual directives, or user profiles-and an input utterance u, napare generates an output y that eradicates or conceals references to p, upholds non-sensitive content for effective cloud-based task execution, and mimics natural language with minimal semantic alterations. the pipeline of napare integrates precision and exploration in two phases. initially, privacy segment alignment decomposes u to pinpoint sensitive portions, calculating scores align t @xmath0, t j ) for each segment t j via embedding similarities or cosine metrics, isolating a sequence of targets t (1) p , . . . , t (m) p for focused intervention. subsequently, a monte carlo tree search (mcts)inspired framework @xcite ) models rewriting as a decision tree: root nodes reflect partial states of u, with branches extending through actions-deletion for high-sensitivity spans or obscuration via generalization. node selection employs upper confidence bound for trees (uct) to weigh promising paths, while a controllable onestep llm rewriter, prompted with privacy strategies, yields candidate sets y cand gated by a thresholded utility function ls(y, p seg ) ≤ γ. a reward model r(y, p) synthesizes nli-derived privacy entailment scores @xcite with domainspecific utility measures, enabling backpropagation to refine explorations iteratively. as outlined in algorithm 1, the process advances sequentially: each segment's optimal rewrite, once thresholdcompliant or budget-exhausted, proceeds to the next iteration, culminating in a cohesive y f inal . this structured, reward-guided search distinguishes napare by dynamically navigating the rewriting space, supporting flexible privacy handling without finetuning. it ensures the searching to generate high quality rewrite even with less capable model compared to commercial llm like gpt-4o our contributions include: ## privacy-aware text rewriting task formulation given the privacy information described p from the user, the objective of our method is to leverage the generation ability of locally deployed llm to rewrite the input utterance u in order to either remove or obscure any private information presented in p. the p is generalized privacy specification of a user. it can be a set of pii removed, text-formatted privacy requirements or profiles. the generated sentence y should satisfy the following requirements: (1) y does not reveal any private information identified in p. ## security analysis despite advances in privacy-aware text rewriting, a critical vulnerability persists: adversaries aware of the rewriting algorithm may attempt to reconstruct original sensitive information from sanitized outputs. motivated by this risk, which could undermine napare's zero-shot, local deployment for protecting user data in cloud interactions, we evaluate robustness against theoretically optimal reconstruction attacks inspired by text sanitization vulnerabilities @xcite . using mediumsized llms like llama2-7b for rewriting, we adopt frameworks for context-free and contextual bayesian attacks, deriving attack success rate (asr) bounds at the token level. for the context-free optimal reconstruction, the adversary recovers tokens via: where x is the sensitive token set, y i is the rewritten token, and probabilities reflect prior distributions and rewriting mechanisms. contextual variants incorporate adjacent tokens c i . we focus on differing tokens between input u and output y, applying token-to-token alignment for length variations. ## related work privacy in large language models recent research highlights growing concerns over privacy risks in large-scale language models, where both explicit and implicit private information can be inferred from text generation @xcite . attack methods such as membership inference @xcite and reconstruction attacks @xcite reveal that models can memorize and leak sensitive details from training data. prior studies have explored differential privacy mechanisms @xcite , adversarial training @xcite , and explicit text anonymization @xcite to mitigate these risks given various context, but these methods often degrade text utility or limited in the certain form of privacy requirements. privacy-preserving text rewriting privacyaware text rewriting approaches typically rely on rule-based scrubbing @xcite , finetuned anonymization models @xcite , or zero-shot prompting techniques @xcite . rule-based approaches are precise but lim-ited in flexibility, while fine-tuned models require extensive human supervision. recent work has leveraged prompt engineering for privacy preservation without retraining models, demonstrating effectiveness in document rewriting @xcite . @xcite considers llm as an adversary to give feedback to the rewrite model to minimize the re-identification risk. our study goes another direction to rewrite via tree-based rewrite with an explicit rewrite strategy. tree search and reward-guided generation tree search techniques have been increasingly explored in llm-controlled text generation, allowing structured decision-making over multiple reasoning and generation paths. tree of thoughts (tot) enables llms to explore multiple reasoning paths systematically, improving complex tasksolving by iterating over various candidate solutions @xcite . similarly, self-play with tree search refinement (spar) enhances model instruction by refining generated outputs through structured search and iterative decision-making @xcite . our method builds upon these principles by tree search and iterative refinement for privacy-preserving rewriting, ensuring progressive modifications that balance privacy, naturalness, and semantic preservation. ## conclusion this paper introduces napare, a zero-shot treesearch based iterative privacy-aware rewriting method that adopts a mcts-inspired search strategy. through our extensive experiments, we show that our approach significantly outperforms baselines in terms of improved preservation of privacy, utility and naturalness. the mcts-inspired search strategy is also superior to alternative methods. one possible direction is to further adapt and optimize napare as a versatile and generalized user privacy rewrite solution, particularly for on-device llms, to better accommodate evolving data release scenarios and granular user preferences.