PrivBlender: Efficient Differentially Private Prompt Perturbation via Budget Mixing

The rapid development of large language models (LLMs) has heightened privacy risks associated with prompts containing sensitive information. Differentially private prompt perturbation has emerged as a promising approach to addressing these concerns, but existing methods incur substantial online computation overhead because of their reliance on the exponential mechanism. We present PrivBlender, an efficient offline–online framework that supports arbitrary target privacy budgets within a prescribed range, through presampling a small number of candidate outputs at different privacy budgets offline and selecting among them in constant time online. The key theoretical contribution is a novel privacy amplification result for mixtures of data-dependent exponential mechanisms: by appropriately mixing outputs generated at two privacy budgets ${\epsilon }_1$ and ${\epsilon }_2$, PrivBlender can achieve any target privacy budget $\epsilon \in [{\epsilon }_1,{\epsilon }_2]$ and keep the cumulative privacy loss bounded by ${\epsilon }_1+{\epsilon }_2$, regardless of the number of online releases. Experiments across multiple prompt-perturbation methods and downstream tasks show that PrivBlender substantially reduces online computation while matching or improving the utility of existing methods under the same formal privacy guarantee.