acceptodds
Under review as a conference paper at ICLR 2027

Beyond Local Perturbation: Privacy Amplification for Black-Box LLM Inference

Abstract

For black-box private LLM inference, differentially private prompt privatization provides formal privacy guarantees without modifying the remote LLM, but stronger privacy typically requires heavier perturbation and degrades downstream utility. We introduce a privacy amplification framework that leverages cross-user anonymity and expands the anonymity set through controllable pseudo-prompt expansion, enabling weaker local perturbation under the same end-to-end privacy budget. To account for the resulting amplification, we develop a mechanism-aware accountant that exploits the sequential structure of prompt privatizers through likelihood-ratio moments, avoiding explicit enumeration of the exponentially large sequence output space. The accountant supports both autoregressive and token-replacement privatizers and remains tractable for sequence lengths where distribution-based mechanism-aware accounting becomes costly. Experiments on MMLU and MedicalQA show relative F1 improvements of \(8.2%\)–\(10.2%\) over the original privatization mechanisms and substantially tighter privacy amplification than generic shuffle accounting.

Primary area:
generative models
Keywords:
Large language model, privacy-preserving inference, differential privacy

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_1GVPOpenReview ↗
Rating
2
Confidence
3
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

This paper proposes a privacy amplification framework for black-box LLM inference. The framework shuffles locally privatized prompts with independently generated pseudo prompts, allowing weaker local perturbation under an end-to-end privacy budget. The accountant bounds sequence-level moments using per-step quantities and propagates them through shuffling. Authors conducted experiments on MMLU and MedicalQA and evaluated utility and complexity.

Critical strengths

Combining per-step moment bounds with shuffle accounting addresses a computational bottleneck, making mechanism-aware privacy accounting computationally tractable.

Critical weaknesses
  • Evidence is limited for the accountant's tightness or method's utility on longer sequences. Fig. 4 reports tightness only at T=5 and runtime up to T=7, while the application setup allows much more tokens. Sec 5.4 uses worst-case per-step bounds; Sec 6.3 notes that the moment bounds and overlap coefficient can introduce looseness. Experiments in sec. 7.2 show promising utility results, but authors did not report the length or discuss how varying the length would affect the privacy bounds or the utility, which is important for the practical application setting.
  • I found it hard to judge the additional contribution of the accountant on top of the prior work Girgis et al. [1], which already derive the common-component reduction and express shuffled likelihood-ratio moments through local ratios.

References

[1] Girgis, A. M., Data, D., Diggavi, S., Suresh, A. T., and Kairouz, P. On the Renyi Differential Privacy of the Shuffle Model. ACM CCS, 2021.

Questions for authors
  1. Can the authors report privacy bounds and accounting time as sequence length increases, along with the local parameters, overlap values, and actual group sizes used for accounting?
  2. Which steps go beyond the analysis in Girgis et al.? What improvement in privacy bounds or computation come from those steps?
Reviewer_tgWyOpenReview ↗
Rating
2
Confidence
3
Informativeness
2
Presentation
3
Soundness
3
Read review
Paper summary

This paper proposes a privacy amplification framework for black-box LLM inference. Users locally perturb their prompts using existing differential privacy (DP) mechanisms and send them to a non-colluding shuffler, which mixes in synthetic "pseudo-prompts" and permutes the batch before forwarding it to the LLM provider. To compute the amplified privacy guarantee without enumerating the exponentially large space of all possible token sequences, the authors introduce a polynomial-time moment accountant that tracks per-token likelihood-ratio moments across the sequence. Experiments on MMLU and MedicalQA across two LLMs (GPT-5-mini, Gemini-3.1-flash) and three local mechanisms (DP-Prompt, DP-Fusion, CusText) show consistent utility improvements.

Critical strengths
  • Novel Direction: Using a shuffler to amplify privacy for black-box LLM prompts is a natural and well-motivated idea, as pure local DP on text typically requires very high epsilon budgets to preserve utility.
  • Solid Empirical Evaluation: The authors evaluate 2 datasets, 2 LLMs, and 3 privatization methods (with and without amplification), reporting confidence intervals and empirical attack metrics.
  • Efficient Privacy Accountant: The moment-based accountant scales polynomially with sequence length T and batch size n, offering tighter bounds than generic shuffle accountants without exponential sequence enumeration.
  • Pseudo-Prompt Augmentation: Injecting synthetic prompts at the shuffler to enlarge the anonymity set is an interesting way to trade compute for privacy, though its novelty relative to prior dummy-padding work in shuffle DP should be clarified.
Critical weaknesses
  • Realism and Overlap of Pseudo-Prompts:
    • It is unclear how distributional overlap (gamma) between pseudo-prompts and real prompts behaves as sequence length T grows, or why an attacker cannot simply filter out out-of-distribution pseudo-prompts when gamma becomes very small.
    • For DP-Prompt, the authors sample pseudo-prompts directly from the target benchmark (MMLU/MedicalQA), which is unrealistic since a real shuffler only sees encrypted prompts. For DP-Fusion, the main text omits how pseudo-prompts are generated (leaving the T5-base span-infilling procedure to Appendix C.1.3).
  • Pseudo-prompts should be most helpful when there are very few real prompts (n_r), but the utility experiments only test n_r = 5000 (and n_r = 1000 in Figure 7), where shuffling real prompts alone already captures most of the gains (Figures 5 and 7).
  • Small Context Groups n(c) in Practice (DP-Fusion & CusText): These methods only shuffle prompts that share the exact same unperturbed public template c. In real-world queries, it is unlikely that many concurrent users share identical templates. Even with n_r = 5000 benchmark prompts, Table 2 shows group sizes have a median of only 7 to 8 and a minimum of 1.
  • Calibrating Local Noise Under Unknown Group Size n(c): Clients must perturb their prompts locally before sending them to the shuffler, yet Appendix C.1.4 states that local privacy parameters are calibrated using the realized group size n(c). It is unclear how a client knows n(c) in advance, or why pseudo-prompts are allocated proportionally to n_r(c) (Eq. 3) instead of padding small groups up to a guaranteed minimum size.
Questions for authors
  1. Since the overlap gamma decays exponentially with sequence length T (Appendix C.1.2), what are the exact values of gamma and n(c) used in Figure 3(c)-(d) for local epsilon in [15, 50], and how does Algorithm 3 avoid collapsing to the unshuffled bound when (n - 1) * gamma is much smaller than 1?
  2. How does the method perform if pseudo-prompts are drawn from a generic distribution rather than the target benchmark (DP-Prompt), and can an attacker filter out T5-base infills (DP-Fusion) when they differ from real sensitive spans?
  3. How do clients calibrate their local noise parameter before knowing how many other users n_r(c) will share their template c in the batch? Why use proportional allocation (Eq. 3) instead of padding small groups to a fixed minimum size?
  4. What is the utility gain of pseudo-prompts when the number of real requests n_r is small (e.g., 10 to 100) rather than 5000?
Reviewer_sMwsOpenReview ↗
Rating
2
Confidence
4
Informativeness
3
Presentation
3
Soundness
2
Read review
Paper summary

This paper proposes a privacy amplification framework for DP prompt privatization in black-box LLM inference. Users privatize their prompts locally, and a trusted shuffler mixes the privatized prompts from many users with data-independent pseudo prompts, then permutes the batch before sending it to the provider. Because reports can no longer be linked to users, each user can apply weaker local perturbation under the same end-to-end privacy budget. To quantify this, the authors propose a mechanism-aware shuffle accountant. It bounds the per-step likelihood-ratio moments of the local privatizer and propagates them through shuffling, without enumerating the exponentially large output space. The framework is applied to DP-Prompt, DP-Fusion and CusText.

Critical strengths

The paper is well written and easy to follow.

The idea is nice and new. Amplifying DP prompt privatization through cross-user shuffling, with a formal accounting of the gain, is a fresh direction for black-box private inference.

The framework is post hoc. It sits on top of the local privatizer, so it can easily be combined with other DP prompt privatization methods, as shown with DP-Prompt, DP-Fusion and CusText.

I believe this work is very useful for other work in this direction. Other methods can benefit from the idea directly and gain additional privacy from indistinguishability among other prompts, on top of their own local guarantees. Because the framework runs on the side of whoever holds the prompts, it can be deployed without any change to the remote LLM. It therefore adds privacy at little cost and can easily be integrated into existing and future prompt privatization methods.

The accounting is also a useful contribution. The authors explicitly instantiate the accountant for existing methods (DP-Prompt, DP-Fusion and CusText), which shows that it works well in practice and is not only a theoretical construct. The accountant is carefully designed and properly derived. It avoids enumerating the exponentially large output space, which makes it tractable where existing mechanism-aware accountants are not.

Critical weaknesses
  1. The paper misses closely related prior work. SharedRequest (arXiv 2606.05004) already mixes original prompts with noisy variants at the batch level under a multi-party anonymity protocol, and ConfusionPrompt (arXiv 2401.00870) already hides genuine prompts among pseudo prompts. Neither is cited or compared against. Both are important baselines, and the novelty should be scoped to the shuffle accounting.

  2. It is unclear where the amplification comes from. For a pure-DP privatizer γ = e^{−ε₀}, and the shuffle only helps when γn ≫ 1. At ε ≥ 15 with n ≈ 10⁴ (Figure 3), or with context groups of about 8 requests (Table 2), γn is far below 1, so the shuffled bound reduces to the local one. The gains likely come from the moment accounting of the local mechanism itself. The authors should report the accountant without shuffling (n = 1), and state γ, γn(c) and the local ε for each result.

  3. A wrong privatized prompt leads to a wrong answer. Perturbation can drop an answer option or replace a clinical term, and the LLM then answers a different question. The paper reports only F1, with no measure of prompt fidelity (semantic similarity, LLM judge), no analysis of how often answers flip compared with the non-private answer, and no mitigation on the user side.

A simple LLM-based assessment of how shuffling, through weaker local perturbation, affects the answers would also be very useful.

  1. CusText is not prompt-level DP. Tokens from different replacement sets have disjoint supports (γ = 0), and fixing the replacement set per position within a group (C.1.2) makes each sensitive token's cluster public. This contradicts the adjacency stated in C.1.1.

  2. Only the spans GPT-5-mini marks as sensitive are protected, and anything it misses is sent in plaintext. The recall of this annotation should be evaluated.

  3. In multi-round use, later turns that include earlier responses reveal the user's previous shuffled position. The composition in D.1 does not cover this.

  4. DP-Fusion chooses λ dynamically at each generation step, tuning it to balance privacy and utility under its per-step Rényi bound. To get a usable overlap coefficient, the paper caps this λ with an extra constraint governed by a fixed parameter κ (C.1.2). The method evaluated is therefore no longer DP-Fusion as proposed. The cap can force much smaller λ, and so lower utility, at exactly the steps where DP-Fusion would otherwise adapt. This can substantially affect the reported results for both Original and Amplified. It is also unclear whether the Original baseline uses the capped or the uncapped mechanism. The authors should either adapt the accountant to DP-Fusion’s actual dynamic λ, for example by deriving γ and the per-step moments from its per-step Rényi guarantee, or run DP-Fusion so that its λ selection is preserved. They should also report how often the cap binds and how much it changes utility.

As the paper builds on DP-Fusion, it is very important to explain these changes in detail.

Questions for authors
  1. How does the method compare to SharedRequest (arXiv 2606.05004) and ConfusionPrompt (arXiv 2401.00870) in utility, privacy and cost?

  2. What do the bounds look like without shuffling (n = 1), and what are γ, γn and the local ε for each reported result?

  3. How faithful are the privatized prompts to the originals, and how often do the answers change compared with the non-private answers?

  4. Can a simple LLM-based assessment show how shuffling affects the answers?

  5. Does CusText satisfy prompt-level DP when protected tokens come from different replacement sets, and what does the fixed per-position replacement set reveal?

  6. How accurate is the GPT-5-mini annotation of sensitive spans, and what happens to the guarantee when spans are missed?

  7. Does the multi-round guarantee still hold when later turns include earlier responses?

  8. How exactly was DP-Fusion modified? Can the accountant use DP-Fusion's dynamic λ directly, how often does the cap bind, and does the Original baseline use the capped version?

  9. How is variable output length handled in Theorem 6.1, and does Algorithm 3 really run in O(nA²)?

If the authors address these points, I am happy to raise my score.

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

Related papers

Loading the map…

Discussion (0)

Sign in to comment.