# PromptGraph: Graph-Guided Prompt Sanitization for Balancing Privacy and Utility in LLM Inference

arXiv: https://arxiv.org/abs/2607.10709 · HTML: https://mlsanity.com/paper/2607.10709/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 21 of its 28 references that are in the map.
- First posted on arXiv 12 Jul 2026.

## Builds on (most cited first, 21 of 21)

- [Training language models to follow instructions with human feedback](https://mlsanity.com/paper/2203.02155/) (2022)
- [The Llama 3 Herd of Models](https://mlsanity.com/paper/2407.21783/) (2024)
- [Chain-of-Thought Prompting Elicits Reasoning in Large Language Models](https://mlsanity.com/paper/2201.11903/) (2022)
- [Qwen3 Technical Report](https://mlsanity.com/paper/2505.09388/) (2025)
- [Lost in the Middle: How Language Models Use Long Contexts](https://mlsanity.com/paper/2307.03172/) (2023)
- [Extracting Training Data from Large Language Models](https://mlsanity.com/paper/2012.07805/) (2020)
- [Calibrate Before Use: Improving Few-Shot Performance of Language Models](https://mlsanity.com/paper/2102.09690/) (2021)
- [What Disease does this Patient Have? A Large-scale Open Domain Question Answering Dataset from Medical Exams](https://mlsanity.com/paper/2009.13081/) (2020)
- [Counterfactual Explanations without Opening the Black Box: Automated Decisions and the GDPR](https://mlsanity.com/paper/1711.00399/) (2017)
- [Graph of Thoughts: Solving Elaborate Problems with Large Language Models](https://mlsanity.com/paper/2308.09687/) (2023)
- [Learning To Retrieve Prompts for In-Context Learning](https://mlsanity.com/paper/2112.08633/) (2021)
- [SAMSum Corpus: A Human-annotated Dialogue Dataset for Abstractive Summarization](https://mlsanity.com/paper/1911.12237/) (2019)
- [Exploiting Unintended Feature Leakage in Collaborative Learning](https://mlsanity.com/paper/1805.04049/) (2018)
- [CodeBLEU: a Method for Automatic Evaluation of Code Synthesis](https://mlsanity.com/paper/2009.10297/) (2020)
- [Privacy- and Utility-Preserving Textual Analysis via Calibrated Multivariate Perturbations](https://mlsanity.com/paper/1910.08902/) (2019)
- [DP-OPT: Make Large Language Model Your Privacy-Preserving Prompt Engineer](https://mlsanity.com/paper/2312.03724/) (2023)
- [A Customized Text Sanitization Mechanism with Differential Privacy](https://mlsanity.com/paper/2207.01193/) (2022)
- [Hide and Seek (HaS): A Lightweight Framework for Prompt Privacy Protection](https://mlsanity.com/paper/2309.03057/) (2023)
- [The Fire Thief Is Also the Keeper: Balancing Usability and Privacy in Prompts](https://mlsanity.com/paper/2406.14318/) (2024)
- [InferDPT: Privacy-Preserving Inference for Closed-box Large Language Model](https://mlsanity.com/paper/2310.12214/) (2023)
- [Unmasking the Reality of PII Masking Models: Performance Gaps and the Call for Accountability](https://mlsanity.com/paper/2504.12308/) (2025)

## Abstract (arXiv)

Large Language Model (LLM) services introduce a fundamental privacy challenge. Sensitive information may be inferred not only from explicit identifiers, such as names or phone numbers, but also from contextual associations among otherwise innocuous spans. Existing sanitizers typically assign privacy or utility signals to individual spans without explicitly modeling pairwise relationships among them. In this paper, we propose PromptGraph, a graph-guided prompt-sanitization approach for privacy-preserving LLM inference. PromptGraph estimates privacy leakage at the span level and utility-relevant contextual dependencies between pairs of spans. It represents each prompt as an attributed graph, in which nodes carry span-level privacy scores and edges encode contextual dependencies needed to preserve utility. The sanitization objective selects a protected span set that maximizes privacy gain while penalizing the loss of contextual dependencies. This formulation explicitly balances privacy and utility when contextual evidence is hidden. Protected spans are sanitized locally, and returned placeholders are restored only after passing local consistency checks. We conduct extensive experiments showing that PromptGraph achieves a more favorable balance between privacy and utility than prompt-privacy baselines.