Elamur Research⌕
☰
home / papers / 2026 / A Systematic Exploration of Text Decomposition and Budget Distribution in Differentially Private Text Obfuscation

A Systematic Exploration of Text Decomposition and Budget Distribution in Differentially Private Text Obfuscation

Paper · 2026 · Stephen Meisenbacher, Angelo Kleinert and Florian Matthes

Summary

Word-level differentially private (DP) text obfuscation must work on whole documents to be useful. This raises two questions: how to split a document into units, and how to divide a fixed document-level ε among those units. Earlier studies looked at each question separately. This paper is the first to examine them together in a systematic way.

The authors used basic DP composition so that every document receives the same total budget. They then crossed five text decomposition methods with six budget distribution methods, three ε levels and two English user-review datasets, giving 180 configurations. Several chunkers rely on n-gram association scores computed on FineWeb. All texts were perturbed with MADLIB over Word2Vec embeddings trained for the study. Each setup was scored on privacy, utility and their trade-off.

No single combination wins on every criterion. However, an ANOVA shows that both the decomposition choice and the distribution choice significantly affect trade-offs. These design decisions therefore matter in practice, and they can be tuned depending on whether privacy, utility or balance is the priority.

Key points

  • Data preparation: n-grams (n = 1–4) were extracted from the FineWeb SAMPLE-10BT subset (10B tokens) using the regex \b\w+\b. Association measures included PMI and LLR, and PMI-based chunks were kept only if their frequency was ≥ 275 and PMI > 2.
  • Best combinations by goal:
    • POS + Attention gave the best average trade-off (0.236).
    • PMI + YAKE best preserved utility (F1, CS, perplexity), and YAKE was the distribution method in all top-five utility setups.
    • LLR + KeyBERT gave the best privacy.
  • ANOVA results: decomposition (p ≈ 3.3e-04), distribution (p ≈ 2.1e-03), dataset and privacy level all had significant effects. The decomposition × distribution interaction did not (p ≈ 0.88), so the two choices can be optimized separately.
  • Unexpected ε effect: average relative trade-off gains rose as privacy weakened. The authors take this as a sign that utility may dominate trade-off metrics.
  • Limitations and code: the study covers English only, the user-review domain only, and a single mechanism (MADLIB). The code is released at github.com/sjmeis/DP-Decompose-Distribute.

Our summary of the paper, in our own words — not its text. The work belongs to its authors; read it at the links above.

 Institutions

🎓Technical University of MunichMunich · Germany55 works · 48,474 citations

 Fields, topics and concepts

📚 Shelves 2The field of science this work belongs to (OpenAlex fields).Computer Science · 16,667 worksArtificial Intelligence · 16,194 works

Cite

Cite as Stephen Meisenbacher, Angelo Kleinert and Florian Matthes. 2026. A Systematic Exploration of Text Decomposition and Budget Distribution in Differentially Private Text Obfuscation. Proceedings of the Seventh Workshop on Privacy in Natural Language Processing.

The paper itself, not this page. BibTeX from the library's record of the work. DOI 10.18653/v1/2026.privatenlp-main.9

@inproceedings{meisenbacher2026systematic,
  title = {{A Systematic Exploration of Text Decomposition and Budget Distribution in Differentially Private Text Obfuscation}},
  author = {Stephen Meisenbacher, Angelo Kleinert and Florian Matthes},
  booktitle = {Proceedings of the Seventh Workshop on Privacy in Natural Language Processing},
  year = {2026},
  doi = {10.18653/v1/2026.privatenlp-main.9},
  url = {https://doi.org/10.18653/v1/2026.privatenlp-main.9}
}

References

48 references, 12 of them with a card of ours. ↗ leads to the work, «find» searches for one we have no id for yet.

  1. Stefan Arnold, Dilara Yesilbas, and Sven Weinzierl. 2023a. Driving context into text-to-text privatization. In Proceedings of the 3rd Workshop on Trustworthy Natural Language Processing (TrustNLP 2023), pages 15–25, Toronto, Canada. Association for Computational Linguistics. in natural language proc… find
  2. Stefan Arnold, Dilara Yesilbas, and Sven Weinzierl. 2023b. Guiding text-to-text privatization by syntax. In Proceedings of the 3rd Workshop on Trustworthy Natural Language Processing (TrustNLP 2023), pages 151–162, Toronto, Canada. Association for Computational Linguistics. find
  3. Jacob Devlin, Ming-Wei Chang, Kenton Lee, and Kristina Toutanova. 2019. BERT: Pre-training of deep bidirectional transformers for language understanding. In Proceedings of the 2019 Conference of the North American Chapter of the Association for Computational Linguistics: Human Language Technologies,…
  4. Doug Beeferman, Adam Berger, and John Lafferty. 1999. Statistical models for text segmentation. Machine learning, 34(1):177–210. find
  5. Ted Dunning. 1993. Accurate methods for the statistics of surprise and coincidence. Computational Linguistics, 19(1):61–74.
  6. Vishal Bhalla and Klara Klimcikova. 2019. Evaluation of automatic collocation extraction methods for language learning. In Proceedings of the Fourteenth Workshop on Innovative Use of NLP for Building Educational Applications, pages 264–274, Florence, Italy. Association for Computational Linguistics. find
  7. Cynthia Dwork. 2006. Differential privacy. In International colloquium on automata, languages, and programming, pages 1–12. Springer. find
  8. Steven Bird, Ewan Klein, and Edward Loper. 2009. Natural language processing with Python: analyzing text with the natural language toolkit. O’Reilly Media, Inc. find
  9. Ricardo Campos, Vítor Mangaravite, Arian Pasquali, Alípio Jorge, Célia Nunes, and Adam Jatowt. 2020. Yake! keyword extraction from single documents using multiple local features. Information Sciences, 509:257–289. find
  10. Ricardo Silva Carvalho, Theodore Vasiloudis, Oluwaseyi Feyisetan, and Ke Wang. 2023. TEM: high utility metric differential privacy on text. In Proceedings of the 2023 SIAM International Conference on Data Mining (SDM), pages 883–890. SIAM. find
  11. Konstantinos Chatzikokolakis, Miguel E Andrés, Nicolás Emilio Bordenabe, and Catuscia Palamidessi. 2013. Broadening the scope of differential privacy using metrics. In Privacy Enhancing Technologies: 13th International Symposium, PETS 2013, Bloomington, IN, USA, July 10-12, 2013. Proceedings 13, pag… find
  12. Kenneth Ward Church and Patrick Hanks. 1990. Word association norms, mutual information, and lexicography. Computational Linguistics, 16(1):22–29.
  13. Mathieu Constant, Gülşen Eryiǧit, Johanna Monti, Lonneke van der Plas, Carlos Ramisch, Michael Rosner, and Amalia Todirascu. 2017. Survey: Multiword expression processing: A Survey. Computational Linguistics, 43(4):837–892.
  14. Francesco Luigi De Faveri, Guglielmo Faggioli, and Nicola Ferro. 2025. Dp-comet: A differential privacy contextual obfuscation mechanism for texts Natasha Fernandes, Mark Dras, and Annabelle McIver. 2019. Generalised differential privacy for text document processing. In Principles of Security and Tr… find
  15. Oluwaseyi Feyisetan, Borja Balle, Thomas Drake, and Tom Diethe. 2020. Privacy- and utility-preserving textual analysis via calibrated multivariate perturbations. In Proceedings of the 13th International Conference on Web Search and Data Mining, WSDM ’20, page 178–186, New York, NY, USA. Association… find
  16. R. A. Fisher. 1992. Statistical Methods for Research Workers, pages 66–70. Springer New York, New York, NY. find
  17. Maarten Grootendorst. 2020. Keybert: Minimal keyword extraction with bert. find
  18. Lulu Gu, Yue Pan, and Pengyuan Liu. 2021. A comparative study of collocation extraction methods from the perspectives of vocabulary and grammar: A case study in the field of journalism. In Proceedings of the 35th Pacific Asia Conference on Language, Information and Computation, pages 201–210, Shangh… find
  19. Pengcheng He, Xiaodong Liu, Jianfeng Gao, and Weizhu Chen. 2021. Deberta: Decoding-enhanced bert with disentangled attention. Preprint, arXiv:2006.03654.
  20. Dirk Hovy, Anders Johannsen, and Anders Søgaard. 2015. User review sites as a resource for large-scale sociolinguistic studies. In Proceedings of the 24th International Conference on World Wide Web, WWW ’15, page 452–461, Republic and Canton of Geneva, CHE. International World Wide Web Conferences S… find
  21. Lijie Hu, Ivan Habernal, Lei Shen, and Di Wang. 2024. Differentially private natural language models: Recent advances and future directions. In Findings of the Association for Computational Linguistics: EACL 2024, pages 478–499, St. Julian’s, Malta. Association for Computational Linguistics. find
  22. Timour Igamberdiev, Thomas Arnold, and Ivan Habernal. 2022. DP-rewrite: Towards reproducibility and transparency in differentially private text rewriting. In Proceedings of the 29th International Conference on Computational Linguistics, pages 2927–2933, Gyeongju, Republic of Korea. International Com… find
  23. Shiva Prasad Kasiviswanathan, Homin K. Lee, Kobbi Nissim, Sofya Raskhodnikova, and Adam Smith. 2008. What can we learn privately? In 2008 49th Annual IEEE Symposium on Foundations of Computer Science, pages 531–540. find
  24. Kunho Kim, Sivakanth Gopi, Janardhan Kulkarni, and Sergey Yekhanin. 2021. Differentially private n-gram extraction. In Advances in Neural Information Processing Systems, volume 34, pages 5102–5111. Curran Associates, Inc. find
  25. Oleksandra Klymenko, Stephen Meisenbacher, and Florian Matthes. 2022. Differential privacy in natural language processing: The story so far. In Proceedings of the Fourth Workshop on Privacy in Natural Language Processing, pages 1–11, Seattle, United States. Association for Computational Linguistics. find
  26. Zehan Li, Xin Zhang, Yanzhao Zhang, Dingkun Long, Pengjun Xie, and Meishan Zhang. 2023. Towards general text embeddings with multi-stage contrastive learning. Preprint, arXiv:2308.03281.
  27. Darshini Mahendran, Changqing Luo, and Bridget T. Mcinnes. 2021. Review: Privacy-preservation in the context of natural language processing. IEEE Access, 9:147600–147612. find
  28. Justus Mattern, Benjamin Weggenmann, and Florian Kerschbaum. 2022. The limits of word level differential privacy. In Findings of the Association for Computational Linguistics: NAACL 2022, pages 867–881, Seattle, United States. Association for Computational Linguistics. find
  29. Casey Meehan, Khalil Mrini, and Kamalika Chaudhuri. 2022. Sentence-level privacy for document embeddings. In Proceedings of the 60th Annual Meeting of the Association for Computational Linguistics (Volume 1: Long Papers), pages 3367–3380, Dublin, Ireland. Association for Computational Linguistics. find
  30. Stephen Meisenbacher, Maulik Chevli, and Florian Matthes. 2024. A collocation-based method for addressing challenges in word-level metric differential privacy. In Proceedings of the Fifth Workshop on Privacy in Natural Language Processing, pages 39–51, Bangkok, Thailand. Association for Computationa… find
  31. Stephen Meisenbacher, Chaeeun Joy Lee, and Florian Matthes. 2025. Spend your budget wisely: Towards an intelligent distribution of the privacy budget in differentially private text rewriting. In Proceedings of the Fifteenth ACM Conference on Data and Application Security and Privacy, CODASPY ’25, pa… find
  32. Tomas Mikolov, Kai Chen, Greg Corrado, and Jeffrey Dean. 2013. Efficient estimation of word representations in vector space. Preprint, arXiv:1301.3781.
  33. George A. Miller. 1995. Wordnet: a lexical database for english. Commun. ACM, 38(11):39–41.
  34. Irina Pak and Phoey Lee Teh. 2017. Text segmentation techniques: a critical review. Innovative Computing, Optimization and Its Applications: Modelling and Simulations, pages 167–181. find
  35. Xudong Pan, Mi Zhang, Shouling Ji, and Min Yang. 2020. Privacy risks of general-purpose language models. In 2020 IEEE Symposium on Security and Privacy (SP), pages 1314–1331. find
  36. Pavel Pecina and Pavel Schlesinger. 2006. Combining association measures for collocation extraction. In Proceedings of the COLING/ACL 2006 Main Conference Poster Sessions, pages 651–658, Sydney, Australia. Association for Computational Linguistics. find
  37. Guilherme Penedo, Hynek Kydlíček, Loubna Ben Allal, Anton Lozhkov, Margaret Mitchell, Colin Raffel, Leandro Von Werra, and Thomas Wolf. 2024. The fineweb datasets: decanting the web for the finest text data at scale. In Proceedings of the 38th International Conference on Neural Information Processi…
  38. Alec Radford, Jeff Wu, Rewon Child, David Luan, Dario Amodei, and Ilya Sutskever. 2019. Language models are unsupervised multitask learners. OpenAI. find
  39. Nils Reimers and Iryna Gurevych. 2019. Sentence-BERT: Sentence embeddings using Siamese BERT-networks. In Proceedings of the 2019 Conference on Empirical Methods in Natural Language Processing and the 9th International Joint Conference on Natural Language Processing (EMNLP-IJCNLP), pages 3982–3992,…
  40. Ivan A Sag, Timothy Baldwin, Francis Bond, Ann Copestake, and Dan Flickinger. 2002. Multiword expressions: A pain in the neck for nlp. In International conference on intelligent text processing and computational linguistics, pages 1–15. Springer.
  41. Samuel Sousa and Roman Kern. 2023. How to keep text private? a systematic review of deep learning methods for privacy-preserving natural language processing. Artificial Intelligence Review, 56(2):1427– 1492. find
  42. Mukund Sundararajan, Ankur Taly, and Qiqi Yan. 2017. Axiomatic attribution for deep networks. In Proceedings of the 34th International Conference on Machine Learning, volume 70 of Proceedings of Machine Learning Research, pages 3319–3328. PMLR. find
  43. Training Parameters. The training parameters used for WORD 2 VEC models are given in Table 3. For the privacy and utility experiments which involved the fine-tuning of a DEBERTA - V 3- BASE , the training parameters are reported in Table 4. find
  44. Erik F. Tjong Kim Sang and Sabine Buchholz. 2000. Introduction to the CoNLL-2000 shared task chunking. In Fourth Conference on Computational Natural Language Learning and the Second Learning Language in Logic Workshop.
  45. John W. Tukey. 1953. Section of mathematics and engineering: Some selected quick and easy methods of statistical analysis. Transactions of the New York Academy of Sciences, 16(2 Series II):88–97. find
  46. Benjamin Weggenmann, Valentin Rublack, Michael Andrejczuk, Justus Mattern, and Florian Kerschbaum. 2022. Dp-vae: Human-readable text anonymization for online reviews with differentially private variational autoencoders. In Proceedings of the ACM Web Conference 2022, WWW ’22, page 721–731, New York,… find
  47. Xiang Yue, Minxin Du, Tianhao Wang, Yaliang Li, Huan Sun, and Sherman S. M. Chow. 2021. Differential privacy for text analytics via natural text sanitization. In Findings of the Association for Computational Linguistics: ACL-IJCNLP 2021, pages 3853–3866, Online. Association for Computational Linguis… find
  48. Random Seeding. For any procedure requiring randomization, we used a random seed of 42. For training tasks where we ran three training runs (and reported the average score), we used the seeds of 42, 43, and 44, sequentially. Vector Size Architecture Training Workers Window Size Minimum Count Trainin… find

Updated

↑ back to top

This page in Markdown → https://md.research.elamur.ai/free/en/papers/meisenbacher-2026-systematic-exploration-text-decomposition-budget/