acceptodds
Under review as a conference paper at ICLR 2027

Enabling Certified Robustness for LLMs at Large Perturbation Radii via Corruption-Rate Randomization

Abstract

The widespread deployment of large language models (LLMs) makes jailbreak attacks that induce harmful outputs a critical safety concern. Unlike empirical defenses, randomized smoothing (RS) provides robustness guarantees against all attacks within a specified perturbation budget, but its application to LLMs often certifies only a few token modifications despite extensive sampling. We identify a fundamental bottleneck in widely used RS mechanisms based on fixed-probability masking and deletion: even when every sample receives the target label, the certifiable radius is subject to a ceiling that grows at most logarithmically with the sampling budget, severely limiting certification against large perturbations. To address this bottleneck, our method extends randomization from choosing which tokens to corrupt to choosing the corruption rate itself. By mixing lightly and heavily perturbed inputs while preserving the expected corruption rate, it increases the probability of removing multiple attack-related tokens together. We show that this change can reduce the sampling requirements for certification from exponential to polynomial in the target radius. Experiments on LLM-based harmful-content detection demonstrate substantially larger certified suffix lengths at the same sampling budget, showing that our method extends certified robustness to larger perturbation radii.

Primary area:
alignment, fairness, safety, privacy, and societal considerations
Keywords:
Certified Robustness, Adversarial Robustness, Large Language Model, Deep Learning

Reviews

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

The paper studies the sampling bottleneck of randomized smoothing for certifying LLM safety against token-level jailbreak perturbations. It proposes drawing a shared per-sample corruption rate from a Beta distribution, derives certificates for masking, uniform substitution, and deletion, and proves improved polynomial rather than exponential sampling dependence in relevant regimes. Experiments on harmful-content detection compare against fixed-rate smoothing across several LLM detectors and attack scopes.

Critical strengths

The certificate derivations appear internally consistent. In particular, the masking result follows directly from the shared-rate joint-masking probability cr=EQrc_r=\mathbb{E}{Q^r}, and the comparison between μr\mu^r and a/(a+r)a/(a+r) Q∼Beta(a,1) is correctly established in Theorems 2–3. My concern is instead with the empirical claim that the method retains a favorable benign-utility trade-off, which is not evaluated at the decision level of the certified smoothed detector.

The paper identifies and resolves a concrete statistical limitation of fixed-rate smoothing. Theorems 2 and 3 show, at matched evidence (S,N) and expected corruption rate, that fixed-rate masking has a radius scaling logarithmically in the effective confidence quantity, whereas the Beta-mixture construction produces a linear dependence for b=1b=1. This is a clean and consequential observation, rather than merely another corruption heuristic.

The paper develops certificates beyond the simple masking case. Theorem 1 and Appendix B derive grouped fractional-knapsack certificates for uniform substitution and edit-distance deletion, while Theorem 9 gives a nontrivial O(r)\mathcal{O}(\sqrt{r}) sufficient sampling result for randomized uniform substitution. The experiments then test both suffix-only and full-input settings, and honestly show in Table 4 that randomized deletion can underperform CERT-ED on unrepeated full inputs.

Critical weaknesses

The claimed benign-detection trade-off is not established for the actual smoothed decision rule. The paper fixes an extremely low target-label threshold, τ=4.6×10−5\tau = 4.6\times 10^{-5}, in Section 4.1, so a benign request is declared unsafe by the smoothed detector whenever its estimated unsafe probability exceeds this very small value. Yet Table 7 reports only the percentage of individual corrupted benign samples classified unsafe, not the fraction of benign requests for which the aggregated smoothed probability p(x)p(x) exceeds τ\tau, nor the resulting false-rejection rate. The reported per-sample unsafe rates are themselves large, between 18.81% and 28.35% for masking and substitution, which makes it impossible to infer that the certified detector has acceptable benign behavior at the chosen threshold. This matters because the conclusion claims a “favorable trade-off between robustness and detection performance,” but the presented metric is not the decision metric used in Equation 1 and the certificate. The authors should report request-level smoothed false-positive rates, together with how τ was selected on held-out data, and ideally provide harmful-detection and benign-acceptance results as a threshold trade-off.

Questions for authors

Does diffusion-based purification receive the realized sampled corruption rate Q as an input or conditioning signal, or is it applied identically to samples drawn at all rates? This affects whether the observed gains can be interpreted purely as a change in smoothing geometry, rather than as an interaction between the heavy-tailed corruption distribution and purification behavior.

Reviewer_bTgzOpenReview ↗
Rating
3(+1)
Confidence
2
Informativeness
2
Presentation
3
Soundness
2
Read review
Paper summary

This paper investigates the limitations of fixed-rate randomized smoothing for certifying the robustness of LLM-based harmful-content detectors. The proposed method samples a shared corruption rate from a Beta distribution for each randomized corruption, increasing the probability of jointly removing adversarial modifications while maintaining the same expected corruption rate. The authors derive robustness certificates for token masking, uniform substitution, and deletion, and establish conditional improvements in certification sample complexity from exponential to polynomial dependence on the perturbation radius. Experiments on 50 harmful requests from AdvBench demonstrate substantial improvements in certified radii under the protected-prefix setting, while results for full-input certification are mixed across the four evaluated detectors.

Critical strengths

S1. Clear motivation and interpretable theoretical mechanism

The paper identifies a fundamental limitation of fixed-rate randomized smoothing at large perturbation radii and proposes a simple, theoretically motivated modification. By replacing a fixed corruption rate with a shared random rate, the probability of jointly erasing adversarial modifications changes from μr\mu^r to E[Qr]\mathbb{E}[Q^r], providing an intuitive explanation for the potential certification gains. The closed-form masking bounds further support the theoretical analysis and make the underlying mechanism relatively easy to interpret.

S2. Broad theoretical coverage and informative empirical comparisons

The theoretical framework covers three corruption mechanisms—masking, uniform token substitution, and deletion—extending the applicability of the proposed approach beyond a single perturbation type. The empirical evaluation also provides reasonably controlled comparisons between fixed-rate and randomized-rate methods by matching the underlying detector, expected corruption rate, and sampling budget. Moreover, the inclusion of both protected-prefix and full-input certification settings, together with cases where the proposed method does not outperform the baselines, offers a more informative assessment of its effectiveness and limitations.

Critical weaknesses

W1. Insufficient evaluation of benign utility and practical significance of the certificates

The evaluation does not adequately establish whether the reported robustness certificates preserve meaningful benign utility. Section 2.2 defines the final smoothed detector using the decision threshold p(x)≥τp(x) \geq \tau, with τ=4.6×10−5\tau = 4.6 \times 10^{-5} in Section 4.1. However, Table 7 reports unsafe prediction frequencies for individual corrupted benign samples (20.24%–28.35% for the proposed methods), rather than the request-level false-positive rate of the final thresholded detector. These measurements are not interchangeable and leave the actual benign performance unclear.

This issue is particularly important because Tables 5–6 report full-input substitution certificates whose radii reach the entire editable input length. Under unrestricted token substitution, such a certificate covers all token sequences of the same length, including benign inputs, within the same fixed classification context. This raises concerns about whether the large certified radii reflect meaningful robustness or an overly conservative detector. Reporting request-level false-positive rates and certified-coverage–radius curves at matched benign utility is necessary to establish the practical significance of these results.

W2. Limited generalizability and inconsistent gains across evaluation settings

The empirical improvements are not consistent across detectors and corruption mechanisms, particularly in the more challenging full-input certification setting. As shown in Tables 3–4, randomized masking underperforms its fixed-rate counterpart on Llama-3 and Llama Guard 3, randomized substitution performs worse on Llama-3, and randomized deletion underperforms CERT-ED across all four detectors. Furthermore, most ablation studies and the benign evaluation rely on Llama-2, while the main experiments include only 50 harmful requests, limiting the evidence for generalizability.

The theoretical sample-complexity improvements also rely on favorable observation and threshold conditions, rather than guaranteeing better certification performance for arbitrary detectors. Consequently, although the proposed mechanism is theoretically meaningful, the experiments do not yet establish whether its substantial certification gains generalize to stronger or more recent safety detectors at practically relevant operating points. Additional evaluations, per-request results, and sufficient implementation details would help clarify the scope and reproducibility of the reported improvements.

Questions for authors

See weeknesses

1 comment

Thank you for the detailed response and additional experiments. The new request-level false-positive rates clarify benign utility, and the matched-FPR comparisons establish substantial certification gains in the protected-prefix setting. The gains at low false-positive rates for full-input certification remain uncertain. Overall, the new evidence addresses enough of my original concerns for me to raise my rating to 3 (Weak acceptance).

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

The paper studies certified robustness for LLM-based harmful-content detection using randomized smoothing. Instead of fixing the token corruption rate, it draws one shared Beta-distributed rate per sample while keeping the same mean. For masking, this increases the probability of removing every attacked token and gives polynomial sampling requirements under the stated conditions. The authors also derive certificates for uniform substitution and deletion. Tests on four detectors show large protected-suffix gains, but smaller or reversed gains on unrepeated full inputs.

Critical strengths
  • The masking mechanism is simple and well supported: a shared rate increases joint-removal probability by Jensen's inequality. Its certificate dominates the fixed-rate masking certificate at the same observed counts (Section 3.3).
  • Appendix C gives a sufficient polynomial sampling budget for randomized substitution and a necessary exponential bound for fixed rates under the stated assumptions. This supports the scaling claim more directly than an upper bound alone.
  • Fixed-rate and randomized-rate comparisons share the detector, mean corruption rate, and sample budget (Section 4.1). Table 7 also checks benign false alarms, which matter for a harmful-content detector.
Critical weaknesses
  • Large gains are concentrated in the protected-suffix setting. On unrepeated full inputs, masking sometimes loses and CERT-ED wins deletion on every detector (Tables 3–4), so the practical benefit is conditional, as the authors acknowledge.
  • Table 2 shows strong sensitivity to suffix length, with masking radius falling to 6.48 at 400 tokens and rising to 37.20 at 800. The proposed PAD-interference explanation is not tested, leaving this behavior unexplained.
  • The polynomial sampling claim is not checked with a sample-budget sweep. Appendix C states its conditions and eventual ceiling at a fixed positive threshold, but the experiments keep the budget fixed.
Questions for authors
  • How much of the deletion gap against CERT-ED comes from the loose bound after occurrence labels are discarded (Appendix B.6)? Could a tighter bound improve the full-input results?
  • Could you test different mask symbols and report per-request radii for Table 2? This would help distinguish PAD interference from other detector-scoring effects.
  • How stable are the suffix gains on larger and more varied jailbreak sets? Will the release include detector prompts, corruption settings, and certificate-computation code?
Reviewer_ThMuOpenReview ↗
Rating
3
Confidence
2
Informativeness
3
Presentation
3
Soundness
2
Read review
Paper summary

This paper proposes a certified defense for LLMs against token-level attacks by extending randomized smoothing from token-level selection to the corruption rate itself via a tailored Beta distribution, which successfully breaks the logarithmic radius ceiling of fixed-rate mechanisms and provably reduces the sample requirement for large perturbation certification from exponential to polynomial.

Critical strengths
  1. This paper identifies the fundamental sampling bottleneck of fixed-rate randomized smoothing that restricts certification to only a few tokens, for which it introduces an elegant corruption-rate randomization scheme using a Beta distribution that preserves the expected corruption rate while transforming the joint-removal probability from exponential to polynomial.

  2. The theoretical framework comprehensively covers multiple discrete perturbation kernels including masking, uniform substitution, and deletion without altering the downstream base detector, which yields substantially larger certified radii under matched sampling budgets in suffix-constrained settings.

Critical weaknesses
  1. The impressive certified radii reported in Table 1 largely hinge on the highly constrained suffix-only setting, where the core prompt prefix is fully protected and preserves the necessary harmful intent for detection. And once evaluated on realistic full-input attacks where edits can hit any token without protection (Table 3 and Table 4), the performance gains almost vanish, with randomized deletion even falling behind the baseline. This drop suggests that the theoretical polynomial advantage relies on a fragile assumption that classification confidence p‾\underline{p} remains intact, a condition easily shattered when heavy corruption from the Beta distribution destroys intent, defining tokens in open text. Can you clarify whether rate randomization offers any verifiable practical advantage over fixed-rate baselines in unconstrained, prefix-free attack scenarios?

  2. I think the extreme radius variations in Table 2 reveal a severe vulnerability when moving to longer editable suffixes without text purification, where certified radii collapse unpredictably from over a hundred tokens down to nearly zero. This non-monotonic instability reflects the dilemma from the detector's perspective is introducing heavily corrupted inputs from the Beta distribution injects long sequences of pad tokens or noisy replacements that confuse the underlying LLM classifier, drastically depressing its prediction confidence p‾\underline{p} on long inputs. So, how sensitive is the downstream detector to these heavily corrupted inputs, and how to ensure certification stability when scaling to longer contexts?

Questions for authors
  1. Can you clarify whether rate randomization offers any verifiable practical advantage over fixed-rate baselines in unconstrained, prefix-free attack scenarios?

  2. How sensitive is the downstream detector to these heavily corrupted inputs, and how to ensure certification stability when scaling to longer contexts?

Comments on the paper

1 comment
AuthorsOpenReview ↗

Summary of Revisions to the Manuscript

Dear Reviewers,

Thank you for your time and thoughtful feedback on our submission.

In response to your comments, we have revised the manuscript to incorporate additional experimental results and present certified robustness alongside benign utility (especially with FPRs of each randomized smoothing methods), together with the figures and tables requested by the reviewers. These revisions are primarily concentrated in Section 4 (Experiments) and Appendices D.3–E, which include additional implementation details and supplementary experimental results. We have also further clarified the presentation in Appendices D.1 and D.2.

We provide this overview to help you locate the revisions when assessing the updated manuscript. The specific changes addressing each reviewer's comments are detailed in our corresponding responses.

Once again, we sincerely appreciate the time and care you have devoted to the review process. Thank you!

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

Related papers

Loading the map…

Discussion (0)

Sign in to comment.