acceptodds
Under review as a conference paper at ICLR 2027

PrivBlender: Efficient Differentially Private Prompt Perturbation via Budget Mixing

Abstract

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 and , PrivBlender can achieve any target privacy budget and keep the cumulative privacy loss bounded by , 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.

Primary area:
alignment, fairness, safety, privacy, and societal considerations
Keywords:
Differential Privacy, Prompt Perturbation, Exponential Mechanism, Privacy Amplification, Text Sanitization

Reviews

Among:
Shape:
1234this paper, Bottom 27%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 2.00 over 3 reviews, above 27% of the others.
Reviewer_frDJOpenReview ↗
Rating
2
Confidence
3
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

This paper presents PrivBlender, an offline-online framework for prompt perturbation methods, based on the exponential mechanism. It presamples candidate outputs at two privacy budgets offline, then selects between them in constant time online. The main theoretical result gives a mixing probability that satisfies an intermediate target privacy budget for symmetric utility functions. The authors integrate the framework with multiple existing prompt perturbation methods, and evaluate efficiency, downstream utility, and reconstruction attacks on several tasks.

Critical strengths

The mixing result provides a simple way to support a range of target privacy budgets using two presampled candidates, which improves online efficiency.

Critical weaknesses

I am concerned about whether the cache construction preserves privacy when the whole perturbed prompt is released. Scenario 1 of sec 4 states "prepare candidate tokens for each possible token x∈Vx \in \mathcal{V}" using O(∣V∣)O(|\mathcal{V}|) storage. This seems to suggest that repeated occurrences of a word share the same two candidates (though I can't find an explicit description) and if this is the intended construction, the guarantee on the individual token won't extend to the whole output sequence. Think about this example - the prompt (a,a,a) cannot produce three distinct outputs because all positions choose from the same two candidates, but (b,a,a) can do so with positive probability. This violates any finite pure-DP bound for the joint output. Using independent candidate pairs for each position would avoid this example, but the authors need to clarify the actual construction and the corresponding preparation and storage costs in this prompt-unknown scenario.

Questions for authors
  1. Are candidate pairs shared by all occurrences of a vocabulary token, or sampled independently for each position? Can the authors address the example stated in Weakness?
  2. Which deployment scenario does Table 1 measure? What is the exact timed step? Concretely, which preparation steps must be repeated for a new prompt when using CAPE (context-dependent scores), how many releases reuse that preparation? I agree that moving work offline can be useful; the question is which costs are reusable in the intended setting.
1 comment
AuthorsOpenReview ↗

Revision file uploaded

Thank you again for your constructive review. We have uploaded a revised version, with text in blue marking the changes.

A brief summary on the changes made:

  1. We have revised the problem setting in the introduction (page 2-3), Section 4 (page 5) and the conclusion (page 10). Hopefully this clarifies independent perturbation of each token. The performance analysis in Section 4 has also been updated.
  2. Our refined setting is justified with new experiments provided in Appendix F (page 21), where we simulate the scenario that multiple queries with diverse privacy budget requirements are issued.
  3. Changes based on other reviewers' comments: rewriting-based solutions in Section 2, revised performance analyses in Section 4, revised meaning of candidate selection in Section 5.5, eithcs statement.

Our main algorithmic contribuition in Theorem 1 is left unchanged.


We hope these responses address your concerns, and we would be grateful if you would consider raising your score.

Reviewer_dEakOpenReview ↗
Rating
2
Confidence
3
Informativeness
2
Presentation
3
Soundness
3
Read review
Paper summary

This paper proposes PrivBlender, an offline-online framework for differentially private (DP) token-level prompt perturbation. Existing methods (SanText, CusText, RanText, CAPE) use the Exponential Mechanism (EM) to perturb each token in a prompt, which takes O(|V|) time per token for a vocabulary V. PrivBlender pre-samples candidate tokens offline at privacy budgets e1 and e2, and selects one online via a Bernoulli coin flip in O(1) time to satisfy any target budget e in [e1, e2]. Using the symmetry of the utility function (Lemma 1), the authors prove a tighter privacy amplification bound for mixing two EM outputs (Theorem 1) than standard subsampling amplification, with cumulative privacy loss bounded by e1 + e2.

Critical strengths
  • Interesting theoretical observation for EM on large candidate sets: Lemma 1 and Theorem 1 show that because symmetric EM outputs have bounded probabilities around 1/|V|, mixing two EM outputs cancels out the |V| factor and gives a much higher selection probability p(e) than generic subsampling amplification.

  • Strong empirical utility in the right privacy regime: When the target e is in the upper half of [e1, e2] (that is, e > (e1 + e2) / 2), PrivBlender matches or outperforms running the base mechanisms directly at the same nominal e.

  • Good experimental coverage: The paper evaluates multiple existing token-perturbation methods across classification and text generation, and includes empirical privacy evaluations (KNN and MTI attacks) alongside nominal e-DP comparisons.

Critical weaknesses
  • The offline-online split is poorly motivated and unclearly implemented:
    • For prefix-conditioned methods (CAPE), logits depend on the user's prompt prefix, so this computation must happen online when the prompt arrives rather than offline.
    • For non-contextual methods (SanText, CusText), it is unclear if Table 1 precomputes once for the vocabulary V or per prompt; reusing a single O(|V|) lookup table across prompts would map repeated occurrences of a word to the same cached token.
    • Since generating (y1, y2) already spends e1 + e2 privacy budget, one could simply privatize the prompt once and reuse that single output via post-processing rather than resampling.
  • All main experiments (Sections 5.1-5.4) and the optimal point in Figure 14 use e1 = 0 (uniform sampling). When e1 = 0, PrivBlender is equivalent to running 1 EM at e2 followed by Randomized Response on its output, which does not require two offline EM runs.
  • PrivBlender only works well in a narrow regime of (e, e1, e2) and underperforms the baselines when e < (e1 + e2) / 2. The fixes in Section 5.5 either require an expensive offline KNN grid search (Figure 14) or store multiple offline candidates (Figure 5), which increases the composed privacy loss to the sum of all offline budgets.
  • The baselines use different neighboring definitions and privacy guarantees (full vocabulary for SanText, size-K clusters for CusText, and an unplotted e' overhead for CAPE), which is not clearly explained, and Figure 4 shows PrivBlender has the same empirical privacy-utility trade-off as the base methods.
  • Token-level budgets of e in [10, 60] (which compose across all tokens in a prompt) are too large to provide meaningful formal privacy guarantees in practice.
Questions for authors
  1. In Table 1, do you precompute once for the vocabulary V or per prompt for SanText and CusText? If precomputed once in O(|V|) space, how does reusing the same pre-sampled pair across repeated words affect privacy? Also, why not simply release a single privatized prompt via post-processing?
  2. Since all main experiments use e1 = 0, how does PrivBlender differ from running 1 EM at e2 followed by Randomized Response on its output, and why does Table 1 pay 2x the online cost in the offline stage when e1 = 0 is uniform sampling?
  3. Since CAPE requires the user's prompt prefix to compute contextual logits, how can its offline step be performed ahead of time in standard LLM inference?
  4. Do you have task-agnostic guidelines for choosing e1 and e2 without running an offline grid search on the dataset (Figure 14), and doesn't storing multiple offline candidates (Figure 5) increase the total composed privacy loss to the sum of all offline budgets?
1 comment
AuthorsOpenReview ↗

Revision file uploaded

Thank you again for your constructive review. We have uploaded a revised version, with text in blue marking the changes.

A brief summary on the changes made:

  1. We have revised the problem setting in the introduction (page 2-3), Section 4 (page 5) and the conclusion (page 10). Hopefully this
    • provides better motivation for the offline-online split
    • explains why the warehouse knows the user prompt
    • clarifies independent perturbation of each token
    • explains why direct reuse can be suboptimal
  2. Our refined setting is justified with new experiments provided in Appendix F (page 21), where we simulate the scenario that multiple queries with diverse privacy budget requirements are issued. This is also an example where ε1≠0\varepsilon_1\neq 0.
  3. The discussion of candidate selection in Section 5.5 (page 9-10) has been revised, including a change to the subheading.
  4. Changes based on other reviewers' comments: rewriting-based solutions in Section 2, revised performance analyses in Section 4, eithcs statement

Our main algorithmic contribuition in Theorem 1 is left unchanged.


We hope these responses address your concerns, and we would be grateful if you would consider raising your score.

Reviewer_bXwDOpenReview ↗
Rating
2
Confidence
4
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

The paper proposes PrivBlender, a speed-up for token-level DP prompt perturbation (SanText, CusText, CAPE). For each token, it perturbs twice offline with the exponential mechanism, once at a low budget ε1 and once at a high budget ε2. Online, it simply mixes the two. Experiments on SST-2, QNLI and Wikitext show similar or better utility than the base methods at the same nominal ε, plus KNN and MTI attack evaluations.

Critical strengths

The idea is simple and helpful, and it gives clear improvements, mainly in online efficiency, for all the token-level DP methods it is applied to (SanText, CusText, CAPE).

Critical weaknesses

My main concern is the contribution. The core idea is to sample twice under two privacy budgets and mix the outputs, which gives an efficiency gain over existing methods.

However, these existing methods all perturb prompts at the token level, and this whole class of work is now outdated.

Prompt-level privacy is no longer achieved by noising individual tokens. Instead, a local LLM rewrites the prompt: it decodes under DP, constrained to the privacy level the user wants, and the rewritten prompt is what gets sent.

Rewriting is known to give empirical privacy benefits, and adding DP to the decoding gives theoretical guarantees as well. This is now a well-established line of work that improves over token-level perturbation.

Examples include DP-Prompt (Utpala et al., 2023, arXiv:2310.16111), DP-Fusion (Thareja et al., 2025, arXiv:2507.04531), where "token-level" refers to protecting labeled sensitive tokens during LLM inference rather than vocabulary-level token swapping, and InvisibleInk (Vinod et al., 2025, arXiv:2507.02974).

InvisibleInk in particular also treats LLM sampling as an exponential mechanism and directly targets its computational cost, so the efficiency problem this paper addresses is already being tackled in the LLM-rewriting setting.

None of these works is cited or compared against.

The paper should either show that PrivBlender extends to LLM-based DP rewriting or justify why token-level perturbation remains relevant. Otherwise the contribution is limited to a setting the field has moved past.

Questions for authors
  1. Can the authors clearly explain why token-level text perturbation is still relevant, given that LLM-based DP rewriting is now the established approach to prompt-level privacy? The baselines (SanText, CusText, CAPE) and the datasets (SST-2, QNLI, Wikitext) are dated and contain no explicitly private content. Newer benchmarks and datasets with annotated private tokens, such as the Text Anonymization Benchmark (TAB) built on ECHR court cases, would be a more appropriate test.

  2. Why perturb every token in the prompt rather than only the private ones? In practice, privacy and compliance requirements mostly concern PII. Perturbing only the labeled sensitive tokens would likely preserve much more utility at the same guarantee.

  3. Can the authors elaborate on the contribution? PrivBlender appears to be a post hoc addition that speeds up existing DP prompt perturbation methods, rather than a prompt perturbation method in its own right. What does it offer beyond efficiency for these specific mechanisms?

  4. How does PrivBlender compare against LLM-based DP rewriting methods such as DP-Prompt, DP-Fusion and InvisibleInk, in privacy, utility and computational cost? If Theorem 1 does not extend to LLM decoding, where outputs depend on context and the utility is not symmetric, can the authors state this explicitly?

1 comment
AuthorsOpenReview ↗

Revision file uploaded

Thank you again for your constructive review. We have uploaded a revised version, with text in blue marking the changes.

A brief summary on the changes made:

  1. We have revised the problem setting in the introduction (page 2-3), Section 4 (page 5) and the conclusion (page 10). Hopefully this provides better motivation for prompt perturbation under multiple analyses, and better explains our contribution.
  2. Our refined setting is justified with new experiments provided in Appendix F (page 21), where we simulate the scenario that multiple queries with diverse privacy budget requirements are issued. Note that for rewritting-based methods, the limitations of "Fresh Noise" and "Endpoint Reuse" still exist.
  3. We have mentioned rewriting-based solutions in Section 2 (page 4) as a separate line of research, and discussed about its combination with our framework as an open problem in the conclusion.
  4. The ethics statement has been updated.
  5. Changes based on other reviewers' comments: revised performance analyses in Section 4, revised meaning of candidate selection in Section 5.5.

Our main algorithmic contribuition in Theorem 1 is left unchanged.


We hope these responses address your concerns, and we would be grateful if you would consider raising your score.

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Loading the map…

Discussion (0)

Sign in to comment.