AdaptDel: Adaptable Deletion Rate Randomized Smoothing for Certified Robustness
Authors: Zhuoqun Huang
Neil G Marchant
Olga Ohrimenko
Benjamin I. P. Rubinstein
Venue: NeurIPS 2025 poster ()
Keywords: Randomized Smoothing
Certified Robustness
Adversarial Training
Primary area: social_and_economic_aspects_of_machine_learning
TL;DR: We propose AdaptDel, a randomized smoothing technique with adaptable deletion rates, achieving higher certified accuracy for sequence classification under edit distance perturbations, outperforming previous methods on diverse NLP tasks.

Abstract: We consider the problem of certified robustness for sequence classification against edit distance perturbations. Naturally occurring inputs of varying lengths (e.g., sentences in natural language processing tasks) present a challenge to current methods that employ fixed-rate deletion mechanisms and lead to suboptimal performance. To this end, we introduce AdaptDel methods with adaptable deletion rates that dynamically adjust based on input properties. We extend the theoretical framework of randomized smoothing to variable-rate deletion, ensuring sound certification with respect to edit distance. We achieve strong empirical results in natural language tasks, observing up to 30 orders of magnitude improvement to median cardinality of the certified region, over state-of-the-art certifications.

AdaptDel: Adaptable Deletion Rate Randomized Smoothing for Certified Robustness
Zhuoqun Huang University of Melbourne zhuoqun@unimell..o edw.elllbeedddd................. au
Neil G. Marchant University of Melbourne mmarchant@unimell edu. au
Olga Ohrimenko University of Melbourne oohrimenko@uniimell edu au
Benjamin P. Rubinstein University of Melbourne brubinstein@unimelle edu, au
Abstract
We consider the problem of certified robustness for sequence classification against edit distance perturbations. Naturally occurring inputs of varying lengths (e.g., tences in natural language processing tasks) present a challenge to current methods that employ fixed-rate deletion mechanisms and lead to suboptimal performance. To this end, we introduce AdaptDel methods with adaptable deletion rates that dy- namically adjust based on input properties. We extend the theoretical framework of randomized smoothing to variable-rate deletion, ensuring sound certification with respect edit distance. We achieve strong empirical results in natural language tasks, observing up to 30 orders of magnitude improvement to median cardinality of the certified region, over wate-of-the-as certifications.
Introduction
Recent advancements in machine learning have led significant improvements across many domains, however the fragility of models to benign noise [ and adversarial perturbations (2) continues to undermine model reliability. While empirical defenses have shown promising results in enhancing model robustness 3 they often lack guarantees when facing adaptive adversaries capable of exploiting the model's defense strategies. Consequently, certified defenses have emerged promising alternative, providing robustness guarantees against arbitrary attacks within a defined threat model 9.3 Among certified defenses, randomized smoothing (14 15] has gained widespread recognition for its scalability to large models and strong robustness guarantees.
Sequence prediction tasks, fundamental to natural language processing, bioinformatics, and time series analysis, present unique challenges for certified robustness. Established threat models, such as bounded l, perturbations, Moreover, the prevailing additive moise-based smoothing mechanisms are ill-defined for discrete data. To address these challenges, smoothing mechanisms have been proposed that additively perturb and permute sequences in embedding space [16] or delete sequence elements [17]. The deletion- based mechanism provides certificates under bounded edit distance perturbations, whereas the perturbation/ permutation-bast mechanisms provide certificates in embedding space and typically fail to cover edit distance perturbations of any magnitude [T8] Appendix FJ. This focus variable-length inputs is a key differentiator from many certified defenses in computer vision, where fixed-size inputs are the norm and cength-depender adaptation less critical.
fundamentally incompatible with variable-length, discrete sequences.
While deletion-based mechanisms have shown promise, one area where existing mechanisms fall short is their use of fixed deletion rate for all inputs. This one-size-fits-al approach disregards
39th Conference on Neural Information Processing Systems (NcurIPS 2025).

---

potential variations in sequence length, complexity, or domain-speciie characteristics. For instance, Huang al. [18] observed that longer text sequences can typically tolerate higher deletion rates without compromising predictive accuracy. This insight suggests a fixed deletion rate may lead to suboptimal trade-off's between robustness and performance, partieularly for inputs that could benefit from more nuanced treatment.
The potential of input-dependent smoothing for discrete sequences remains largely unexplored. Prior work has considered Gaussian smoothing with input-dependent noise for Ep certification of real- valued inputs. Other work has taken an ad hoc approach, where where[Cohen al. certificate for uniform Gaussian noise is corrected iteratively at test time [19] 20). However, this results in a model where each output depends on the chain of previous outputs, which complicates interpretability. may lead to error propagation and increases computational complexity and memory requirements. A more rigorous approach was taken by Súkeník et Gaussian noise.
[21] who derived a certificate for input-dependent
In this paper, we extend input-dependent smoothing to discrete sequences, where new analysis is required to obtain sound edit distance certificates. We begin by introducing a general framework for deletion smoothing with input-dependent deletion rates, which provides bounds on the smoothed model's 's confidence scores under perturbations. Building on these bounds, we propose two methods that support efficient edit distance certification: AdaptDel, which uses a rate, and AdaptDel+, which further optimizes the deletion rate using input binning and empirical calibration. Our contributions are summarized as follows:
deletion
We develop theoretical foundation for variable deletion rates, enabling robust smoothing mechanisms that adapt to input length.
We propose AdaptDel and AdaptDel+, two novel adaptive smoothing techniques, which enable computationally efficient certified robustness while maintaining high accuracies.
We evaluate our methods on four natural language processing tasks with varying input sizes, demonstrating that AdaptDel and AdaptDel+ achieve stronger robustness on all datasets at the same certified accuracy, with little to no degradation in clean accuracy: for example, we observe up 30 orders of magnitude improvement to median cardinality of the certified region.
2 Preliminaries
Task d' = S2" denote the set of finite-length sequences with tokens drawn from vocabulary Ω. For sequence E X, let the length be denoted by |x), and let the k-thh token be denoted by Ig- We consider a sequence classification task, where a model f predicts the class y E y of input sequence
Though our methods apply to generic sequence classification, we focus on text for concreteness, where text is mapped to sequence using tokenizer. For instance, in topic classification, the input text might be a news article and the possible classes are topics like "politics" and "sports" [22].
Edit Distance While it is common consider by-based threat models for the image domain, textual data is subject to more structured perturbations, such as edit-based perturbations [23] Given two sequences x. Ø E X, and subset of edit operations C {del, ins, sub}. we define the edit distance di + σ)) as the minimum number of edits required to transform æ into á. We note that edit distance is not symmetric if o contains del without ins vice versa, which explains our use of to emphasize directionality. Although dist, is not necessarily a distance metric, this is not a problem for our analysis our our results hold regardless.
Edit Distance Robustness Given a classifier f. we consider the problem of certifying its robustness under bounded edit distance perturbations. Specifically, we are interested in certifying that the classifier's prediction is invariant to any input perturbation of magnitude r in edit distance,
Vī E B,(2; f(x) = f()).
(1)
where B, o) = (a X' dist. x .²) S r) denotes the edit distance ball of radius r centered on

---

As is typical for randomized smoothing, we will develop mechanisms that produce randomized radius given imput sequence æ. such that with high probability a, this radius is valid certificate at æ. We achieve this certification against general edit distance using a smoothing mechanism based exclusively on deletions, which we introduce and justify in Section
3 Adaptable Deletion Certification
We now present our framework for deletion- randomized smoothing with a deletion rate that adapts depending on the input. Our framework generalizes fixed-rate randomized deletion ([7), achieving edit distance certificates with superior robustness-accuaacy trade-off's over wider range of inputs. To begin, we review randomized smoothing in Section 3.1 and describe our variable-rate deletion mechanism in Section 3.2, Next, in Section 3.3 we obtain bounds the smoothed classifier's scores under input perturbations, where we make no assumptions about the deletion rate's 's dependence complex, obtain bounds that can evaluated algorithmically by solving a bounded knapsack problem. Finally, in Section 3.4 specialize framework length-dependent deletion rates, which allows efficiently compute an edit distance certificate.
on the input. Although the adaptive setting makes the analysis significantly
3.1 Randomized Smoothing
While various techniques have been developed for certified robustness, randomized smoothing [4] a leading approach owing to its scalability to large models and the size the robust radii it can achieve. Given base classifier fo X - V. and smoothing mechanism ø X - D(X) that maps the input to a distribution perturbed inputs, randomized smoothing defines a smoothed classifier X y such that
[(x) == arg max (a Jb,
yEY
where Py (æ; fbr ω) is the smoothed class probability Py (x;; fu, Φ) effectiveness of randomized smoothing heavily relies on the choice of smoothing mechanism. An ideal mechanism will achieve large robustness certificates in the desired threat model while minimizing the performance degradation.
Pr Prz) [f) v]. The
3.2 Variable-Rate Deletion
We now present a smoothing mechanism that randomly deletes sequence tokens, where the rate of deletion varies as function of the input sequence. Our mechanism generalizes the fixed-rate deletion mechanism proposed by Huang et al. [17]
We begin by defining notation to express the mechanism symbolically. Let = (el..... , ( be vector of deletion indicator variables for input text containing [z] tokens, where e, if the i-th token is to be retained and e, = 0 it is to be deleted. We slightly abuse notation and let |E| := Σ, e denote the number of tokens retained. The space of possible deletion indicators for input text is denoted as E(x) {0, 1 |=|, Our variable-rate deletion mechanism is parametrized by deletion probability function th: X + [o, 1]. that maps an input æ to a deletion probability shared across tokens. The probability mass function for e at input takes the form g(E|x) II, (xx))
(()))
ie., each deletion indicator is drawn i.i.d. from a Bernoulli distribution with probability (xx)). We write apply(æ; to denote the resultant sequence after deleting the tokens referenced in from input text æ. The end result of this process a random subsequence of æ, which we denote by @ (z)) emphasizing the dependence on v/.
Using this notation, we can express the smoothed class probability as a sum over the space of deletion indicator variables:
Py (2; Jin db)) = Σ (E, with sn, = = (ssplly(a.e))==
<Ef(x)
where we define 1 as the indicator function that returns if the predicate A is true and 0 otherwise. We conceal the dependence on de and write Py fu) where evident.
Remark (On Smoothing vs. Certified Edits). Our smoothing mechanism uses only deletions, while our edit distance certificate (derived in the following sections) provides robustness against broader

---

set of edits, including insertions and substitutions. This distinction is valid because the primary role of smoothing mechanism is to ensure that nearby sequences under the certificate's 's distance measure produce statistically similar distributions of perturbed outputs. Since an edit distance ball contains sequences of varying lengths, the smoothing mechanism must be able to change the input's dimensionality. Deletion is a simple and effective operator for this purpose; by randomly removing tokens, maps different source sequences to a common, lower-dimensional subsequence. While mechanism incorporating insertions substitutions could also be designed, deletion alone is sufficient to create the statistical overlap necessary for certification.
3.3 Analysis for Variable-Rate Deletion
We now turn our attention to deriving a certificate for randomized smoothing with variable-rate deletion, where we make no assumption about the functional form of the deletion rate y/. Our key results are lower and upper bounds on the smoothed class probability Py Py(#:; ft) at a neighboring input æ. that depend solely on the smoothed class probability the original input æ and the size of the longest common subsequence between and æ. These bounds can be used to perform brute force certification, or to derive more certificates under simplifying assumptions on the functional form of the deletion rate d (discussed in the next section).
The first step in our analysis is to identify correspondence between deletions for neighboring inputs. Let
[=((c,))) E E(x) x E(x)
be a partial order on the space of deletion indicators E(z). We can then write [ e' if e' can be obtained from e by deleting additional tokens.
This allows to define set of deletions building on e:
Eιv, E) {e' E E(x) E
which represents all possible deletions that extend the base deletion e under the space of deletion indicators E. We further define the subset of deletions that result in subsequences of a specifie length:
E (xx e*) {e E E(x,
I |E
k}.
which represents the set of all equivalent edits achieving the same length & by summing the deletion indicators.
The following result adapted from 17 Lemma 4] identifies a relationship between terms in Equation for a pair inputs æ, x based on their longest common subsequence.
Lemma 2 (7).. Let x* be a longest common subsequence (26) of and æ, and let E* {(w) and Ex E ((x) be any deletions such that apply (ë, E*) apply (xx E*) = =z" Then there exists a bijection m: E(x,E') > E(x,c") such that apply(æ, E) apply(æ, E) for any é è" and m().. Furthermore, we have
3
8 8f (c,
p(v, 5)11 cl (E,
where define vb (xx), & = (x)) and p( 3)
v(1اا v11-0) for conciseness.
We can decompose the sum over edits in Equation 2 into two parts: sum over edits in the set E E(x, e*) building e* and a sum over the remaining edits not in this set. After invoking Lemma 2 we obtain the following relation between the smoothed class probability at æ and x:
3
(x; fb)
Σ eEE(22E))
p(u. (1 (e,x)
Σ
(E,
(3)
(ES(B))
From here, we obtain a lower bound on the right-hand side of (3) by dropping the sum over {())
E E(τ, E*) and deriving a lower bound on the sum over E(ær, 6") that is the solution to bounded knapsack problem. Later, we use this pairwise lower bound obtain an edit distance certificate by considering the worst case ã within a bounded edit distance from

---

Lemma 3. Let L, I X be pair of inputs with a longest common subsequence (LCS) x" and let
j Py (x Define
h, 1/ 1p
H
max ME (.(1="), 110 h,
16 < 10
as a threshold on the number of tokens retained when editing x. where B& (n, p) = (c) (1 p is the Binomial pmf for trials with success probability 1 p. Then there exists a lower bound 1b( x, E, v) S Py [b; f6) such that:
(1
[]
1)+1==1
1b(14, 20, 2b
B.(1=",, 1)
15/ 10/01
[(1+++1)
c(s,, x |2 1b H
+ BH (1))),15)
(=:))-)
B (|21 12"1,,1)
where
(1-1)(H*-
c(u, |z|,|2=1| 1, H") p 2//=
()((,,,,)),
i=I(I+++1)
1 1 seB a binary indicator and [.) = Li is gridded flooring gloornn operation.
Proof sketch. We consider the case where sb 2 sh, as the opposite case follows similar logic. Dropping the last term in Equation we obtain the bound:
Py Py; fb)
Σ
(z,
cEE(n,ct)
Since all factors are non-negative, we focus on lower bounding the sum over (xx, c²), which we denote by (æ; fu). We lower bound (æ; fb) by replacing the base model fú by worst-case plausible model
o
fb)
min
Σ
p(u, (1tll))
(EE(2).))
where the set plausible models satisfying the constraint in Lemma 5
F
Σ eEE(2,e*)
sy(e, x:) 2 1 +b |="| W
The minimization problem can now be viewed as bounded knapsack problem is treated as an item of size = je). with weight wi() and value v(i). So for size i at most (?) items are available. We choose multiplicities h(i) S (M) to minimize ( subject to En wi))(ii) > W. Since the unit-value ratio uui)/w(ii p( J increases in the greedy solution orders by filling up to a critical H where the cumulative weight would meet W, then takes as many items of size H1* as possible without meeting the weight requirement. This yields a valid, though not necessarily tight, lower bound.
27 where each
By similar argument, also obtain upper bound (æ f6) in Lemma (deferred to Appendix due to space constraints) that is the solution to a maximization problem viewed as a bounded knapsack problem (28). The upper bound is not needed when computing certificate in the
style of Cohen et al. [4]. However, it is needed to compute certificates in the style of Lecuyer et al.
[13 or for certification of top-k predictions (29]
We note that the bounds in Lemmas [ndd
used to compute an edit distance certificate by exhaustive search for arbitrary deletion functions (see Appendix with constant factor improve- ment over querying the smoothed classifier directly. By making further assumptions on the deletion function, are able compute certificates more efficiently, demonstrated in the next section.
5

---

3.4 Certification for Length-Dependent Deletion
We now turn our attention the class of deletion functions (z)) that depend on the input only via the length xz]. To emphasize this restricted form of dependence on we write (xx w [ in this section. For eb of this form, the lower and upper bounds on Py (æ. fi) in Lemmas 3 and depend only on Py Py(ar, ft.,, the sequence lengths |ae] and |æ), and the length of the I.CS | We can Therefore enumerate over all neighboring sequences E within edit distance r of x by enumerating over the
number of edits ne of each type in E o, such that the total number of edits Videl Viins + auub does
not exceed r. The set containing the possible number of edits of each type at radius is defined as follows:
C(o,r)
- (ndch Rinss Nlub) E NNU. {N]
=
Ridel + Minn Medel 7del S r r'deelo Rins I r'linsEo Asub I r slusbbo }
We can now establish Algorithm Tand Theorem 4 that certify the top prediction of a smoothed clas- sifier with length-dependent deletion function &b
Algorithm 1 CERTIFY
Require:
base classifier ft. input sequence æ, predicted class yı, mangth-dependentt dele- tion probability v/, allowed edit operations o, significance level a
using these insights. It follows the standard Monte Carlo estimation approach from prior work [44 [5]. Lines and @and@eestine estimate lower confidence bound for the predicted class y1 and an upper confidence bound for the runner up class y/2 following the ap- proach of Lecuyer et al. [15] with designated a confidence bound. We use Py( fbr dg. a) with superscript lb or ub to denote the Clopper-Pean Pearson lower and upper confidence bound for the smoothed
Ensure: maximum radius that can be certified 1: t < ph (æ;; fo: óg.
2: 17 + maX (xr(;;; Jb. &w. ax)
3: for 0 to oo do
4:
for all (Adel Mins: Nsub) ) E C(o, r) do
5:
@ x
+ nins ridel
class probability py- This involves a Bonferroni correction (dividing a by 2) since a one-sided con- fidence bound is estimated for two-classes using the same sample drawn from (x)). We circumvent
6:
Z lb (t.p
x. N. 1))
7:
auh ub (ith 12,,2, a. 2.4)
8:
if t S jub then
the problem of needing to divide the confidence level by the number of classes by estimating the top and runner-up using an independent set of samples and output radius of ( if there is disagreement between the two batches of samples. The for loop in Line then attempts to verify a certificate at increasing radii, by checking all neighboring inputs parameterized by the number of edits of each type (Line 4. If a violation is found-whee probability exceeding the probability for y/1 within the a confidence bound-the previous best radius is returned. The proof of Theorem is deferred to Appendix A
9:
return
the classifier's 's prediction changes due to the runner-up
Theorem 4. Given smoothed classifier f as described in Algorithm with a length-dependent deletion function vb
Vā E (,; f(x) f())
with confidence level least 1 a.
We now consider various options for specifying length-dependent deletion function tb.
Fixed-Rate Deletion The most basic option fixed-rate deletion mechanism.
(xx) == Pdel.
for some constant Pdel E [0, 1]. For this specialization, we show in Appendix A that the Lemma simplifies approximately to the closed form analytical solutions obtained by Huang et al. [I8]. Although this mechanism was shown to be effective for malware detection and some natural language tasks, it is less suited when there is variation in sequence/text lengths. In particular, one can optimize the mechanism by setting Pael for best average length input performance, but this may be suboptimal for inputs that deviate from the average length.
Length Dependent Deletion We propose mechanism, AdaptDel, where the deletion rate smoothly increases as a function of the input sequence length. Specifically, we define
k
))
(xx)) = max (ib. P
(5)
x

---

where PDs E [0. 1] is minimum deletion rate, p E [pis. 1] is the asymptotic deletion rate (as |x| - 00), and k O is a parameter that scales the deletion rate based on the input length. In subsequent experiments, we set Phs Pdel. P 1 and A: = [(1 pb) E[[ar]]] so that the deletion rate in Equation [ matches the deletion rate in Equation + for a test sequence of average length. This allows for a fair comparison between fixed-rate deletion and AdaptDel. We note that clipping of the deletion rate below Pbb is done to avoid a certified radius of zero for short inputs. While this may sacrifice some accuracy, it enables non-vacuous certificates for shorter sequences. One intuition is that longer input sequences are inherently more tolerant to noise, allowing for a more significant deletion rate to be applied without severely impacting model performance.
Optimized Length Dependent Deletion We also consider an enhanced optimization based cer- tification approach, dubbed AdaptDel+, where we bin the inputs by sizes into n bins and find an optimal expected length after deletion for each bin using golden section based search (Algorithm 5)
In particular, let (ar) denote the index of the bin input x: belongs to, then we have (>(x)) == 1 k
[
where kyt=) is the empirically optimized expected length for bin g(x).. We provide more details and
intuition for Algorithm in the Appendix C
4 Experiments
To evaluate the effectiveness of AdaptDel and AdaptDel+, we conduct experiments on diverse set of natural language processing tasks. These include five-class sentiment analysis on the Yelp dataset [22] spam detection using the SpamAssassin dataset 33 31 sentiment analysis on the IMDB dataset (32,, and unreliable news detection using the LUN dataset [1]. The varying input sizes of these datasets allow for a comprehensive assessment of AdaptDel's overall effécttiveness. We also analyze performance by dividing inputs into quartiles based on their length. Detailed specifications of these datasets are provided Table [ in Appendix [D] The appendices provide further certified results (Appendix E), details on computational efficiency (Appendix F) and supplementary analysis of empirical robustness against common text attacks (Appendix G
Model and Parameter Setup We use a pre-trained RoBERTa model 34 as a non- non-smoothed baseline (NoSmooth) and base model for randomized smoothing. We compare our adaptive deletion rate policies AdaptDel and AdaptDel+ with fixed deletion rate baseline, that corresponds to CERT-ED [8. All of these methods support certification of edit distance. We note that CERT-ED has one parameter Pael, AdaptDel has two parameters pm and k. The parameters for AdaptDel+ are determined via an empirical calibration procedure on the training set (see Appendix ( We additionally include RanMASK [3] bascline that supports more limited Hamming distance certificate. uses a masking mechanism, where the fraction of masked tokens Pmask is fixed. For all smoothed models, we apply the same base RoBERTa model, training procedure, and parameter settings where possible. During inference, we use 1000 samples for prediction and 4000 samples for certification to ensure stable and reliable results. We refer the reader to Appendix for further details, including how AdaptDel+ is calibrated.
Performance Measures We report clean accuracy, the accuracy without any robustness guarantee, as a measure of model performance. To evaluate robustness, we use the certified radius (CR), which quantifies the largest perturbation radius under which a prediction is provably robust. A larger CR indicates greater robustness. Following Huang et al. [18], we also report log-cardinality of the certified region (log(CC)), the base- 10 logarithm of the number of perturbations enclosed by the CR under the given threat model. For Hamming distance (RanMASK), this is an exact count, whereas for edit distance (CERT-ED, AdaptDel, AdaptDel+), it serves lower bound, underestimating by at most one order of magnitude. For incorrectly classified inputs, we assign CR- = CC = O. Finally, we define certified accuracy the proportion of inputs that are both correctly classified and possess log-cardinalities exceeding a given threshold c.
4.1 Robustness- Trade-off
Figure I presents the certified accuracy as function of the log-cardinality of the certified region for all datasets. Each curve depicts how the fraction of test instances that remain correct and certifiably robust changes as the size of the certificate grows (in log-scale). Combined with results in
7

---

60
100
100
100
Creffed Crefodaacuetty accuntty
50-
Mocklzeferoulnn airengo CORT Plrumi
Noce Loeeoorrooon
CITY ES
Hoce mn M
10
70
60
61
Conttee
30
20
23
20
50
150
100
150
200
1ce cardin lnfiCC)
Log candiaal (ng)CC)
(a) Yelp
(b) IMDB
(c) SpamAssassin
(d) LUN
Figure 1: Certified accuracy plotted against lower bound on the log-cardinality of the certified region. Each point (c, a) on a curve indicates that a fraction a of the test inputs were correctly classified with certified cagddinida of at least While AdaptDel consistently outperforms the baselines, A achieves the highest certified accuracy for larger certified regions.
Table 4 in Appendix E.2 both AdaptDel and AdaptDel+ maintain competitive clean accuracy (0-2% drop compared to RanMASKand CERT-ED), while significantly enhancing robustness guarantees compared to RanMASK and CERT-ED. In particular, they improve the mean certified radius by an average of over 50%, and the median cardinality of the certified region by up to 30 orders of magnitude. This substantial expansion highlights the effectiveness of adaptive deletion in certifying robustness against significantly broader space of perturbations, making it particularly valuable in adversarial settings where sequence manipulations are common.
We observe that methods based on Adapt and A generally yield higher certified accu- racy than CERT-ED and RanMASK for larger cardinalities, reflecting the same trend of increased robustness reported in our mean CR and median CC metrics. These improvements are especially pronounced for SpamAssassin and LUN datasets which contain more uniform length variations (see quantile of lengths in Figure 2 and Figure 4). Our results show improved performance for longer sequences that deviate from the average length.
4.2 Robustness Scaling with Input Size
Figure Sigure[stae shows how certified accuracy scales with respect to both input size (grouped by quartile) and the log-cardinality of the certified region. Each panel/facet on the left of the figure corresponds to a quartile, where the range of input sizes can be read from the quantile function on the right. For the Yelp dataset (left), results within the first two quarters are slightly mixed with AdaptDel and AdaptDel+ showing moderate advantage over RanMASK and CERT-ED, This is expected, as AdaptDel is configured to match the fixed deletion rate of CERT-ED for short sequences, with its advantages becoming more pronounced as sequence length increases. However, for the fourth quarter where the length variations is concentrated, both AdaptDel and AdaptDel+ achieve substantial gains in certified accuracy, indicating that as input size grows, our smoothing techniques can certify robustness against a broader range of adversarial edits. Meanwhile, for the Asassin dataset (right), a similar pattern emerges, but the benefits are more pronounced. Additionally, we observe that AdaptDel+ maintains significantly stronger robustness guarantees across all lengths, showing the effectiveness of our calibration strategy in enhancing certified accuracy for varying input sizes.
Overall, our approach not only preserves clean accuracy but significantly enhances certified robustness, particularly for longer sequences. Compared to state-of-te -tate-of-the-art methods, we achieve an average improvement in mean certified radius of over 50% and increase the median certified region cardinality by up to 30 orders of magnitude. This demonstrates superior scalability and highlights the practical value of tailoring the smoothing rate to input length, property that can be critical in adversarial settings where length variations are common.
5 Related Work
In addition to the works mentioned in the introduction, now describe approaches closest to ours.
8

---

Meda Steegh
Pook wetaaasttaeeee shrrel
Adpol
drragh 137-43
Cantoo
Cantloc (%))
0.75
0.75
Medil per dtreggh
Moder Letta nution singht
Cantees
1,00
1.02
20
40
60
80
10019
378
50
100
130
200
433
Log cardinaityy lepoCC)
Input Size
Log carcinaliyy (ege
Size
(a) Yelp dataset
(b) SpamAssassin dataset
Figure 2: Certified accuracy function of the log-cardinality of the certified region, grouped by quartile input size. The subfigure on the right displays the quantile by input size, with the dashed lines indicating the quartiles corresponding to the certified accuracy plots on the left. Each set of axes (top to bottom) corresponds to split the test set on the enngth-based quartiles (smallest to largest). For example, the second plot from top to bottom shows the certified accuracies of examples within Q1 to Q2. The results demonstrate that the methods scale effectively across varying input sizes, with higher certified accuracy achieved for larger input sizes and higher carddinany regions.
Certification for Edit Perturbations There a growing body of work aimed at extending certifi- cation handle edit-based threat models structured input spaces. In the natural language domain, randomized smoothing has been applied to certify robustness against synonym and word substitution attacks [11 35). However, their certificates do not cover insertions or deletions of words. To address this gap, recent work has studied broader threat models that go beyond substitutions. Zhang al. [66 provide certificates against permutations and fz-bounded perturbations of sequence ele- ments in embedding space. Rocamora et al. [6)] provide edit distance certificates for convolutional classifiers with bounded Lipschitz constants. While their approach does not require smoothing, limited to convolutional architectures and yields empirical accuracy and robustness guarantees that are significantly smaller than those of the randomized smoothing approach considered this paper.
Beyond sequences, edit distance certification has also been explored for sets and graphs. Liu et al. 37 apply subsampling- based randomized smoothing certify point cloud classifiers against bounded number of point insertions, deletions, and substitutions. Schuchardt et al. (38) propose general framework for group equivariant tasks that provides edit distance certificates for graph classifiers 39
Input-Dependent Smoothing Most applications of randomized smoothing consider additive noise mechanisms, where the noise level is independent of the input. While this simplifies the robustness analysis, it is suboptimal and has been shown result in disparities in class-wise accuracy [40]. Several works have attempted to address this, particularly for input-dependent Gaussian noise. Wang al. (5) divide the input space into several "robust regions". each with a constant calibrated noise- level, and use the fixed-noise certificate of Cohen et al. [4] within each region. However, their approach assumes all test samples are available for calibration and it comes with higher train/test costs. Eiras et al. [19 and Alfarra et al. (20] also use the fixed-noise certificate as a starting point, before issuing a new certificate they apply correction that depends on all previously issued certificates. By contrast, Sákeník et al. [21 obtain tight certificate for input-dependent Gaussian noise by generalizing the proof technique of Cohen al. 114. They find that the variability of noise scale is limited in practice due to the curse of dimensionality. Lyu et al. [4] propose general

---

framework for input-dependent smoothing mechanisms that can potentially consist of multiple steps. However, in order obtain certificate, the mechanism must satisfy functional differential privacy.
While our approach shares some similarities with the above prior work, it differs fundamentally in two ways. First, the edit distance certificates consider include inputs with variable dimensions (sequence lengths), which is not the case for f, certificates where all inputs have the same dimensions. This makes deriving sound certificate for dimension-des -depeddde noise more challenging our case. We note that Gaussian smoothing with a dimension-dependen noise scale is covered by the standard fixed-noise certificate of Cohen et [4]. Cohen al. observed that higher dimensional images can tolerate large noise scales while retaining visual information we enable such noise scaling for variable- length sequences while ensuring sound certification. Second, our certificate and mechanism are qualitatively very different- our deletion mechanism cannot be expressed as additive noise, and edit distance arguably more challenging analyze than lp distance given is defined as the solution to discrete optimization problem.
Conclusion
In this work we propose variable rate deletion for sequence classification classfication--ettedinnn randomized smoothing certification to adapt to inputs of varying length. We develop theoretical framework for variable rate deletion, which allows the deletion probability to adapt dynamically based on input propose AdaptDel and AdaptDel+, mechanisms designed
properties. Building this foundation, to enhance robustness certification while maintaining competitive performance. The former uses length-dependent deletion rate, whereas the latter further optimizes the deletion rate using input binning and empirical calibration.
Our results demonstrate that AdaptDel and AdaptDel+ consistently outperform existing state-of-the the art methods, such as CERT-ED and RanMASK, across diverse NLP tasks with varying input lengths. Our methods achieve superior trade-off, offering significant gains in certified robustness while maintaining competitive clean accuracy. This highlights their effectiveness in real-world scenarios (e.g. LLMs) where input sequences can vary significantly in length. Our contributions pave the way for more adaptable and robust approaches to certifying sequence classifiers.
Limitations
Our work focuses the problem of certified robustness for sequence classification against edit distance perturbations. While edit distance offers more appropriate threat model than bp-bounded attacks, this choice still a syntactic surrogate for attacks that preserve semantic similarity. And while our contributions permit length-dependent deletion rates, it is conceivable that more general input-dependent deletion rates could yield improved certified robustness.
Acknowledgments and Disclosure of Funding
We acknowledge partial funding from the Australian Research Council DP220102269. This research was supported by The University of Melbourne's 's Research Computing Services and the Petascale Campus Initiative.
References
[1] Yonatan Belinkov and Yonatan Bisk. Synthetic and natural noise both break neural machine translation. In International Conference Learning Representations, 2018.
[2] Ian Goodfellow, Jonathon Shlens, and Christian Szegedy. Explaining and Harnessing Adversar- ial Examples. In International Conference on Learning Representations, 2015.
[3] Shuhuai Ren, Yihe Deng, Kun He, and Wanxiang Che. Generating natural language adversarial examples through probability weighted word saliency. In Proceedings of the 57th Annual Meeting of the Association for Computational Linguistics, 2019.
10

---

[4] Yuan Zang, Fanchao Qi, Chenghao Yang, Zhiyuan Liu, Meng Zhang, Qun Liu, and Maosong Sun. Word-level textual adversarial attacking as combinatorial optimization. In Proceedings of the 58th Annual Meeting of the Association for Computational Linguistics, 2020.
[5] Xiaosen Wang, Yichen Yang, Yihe Deng, and Kun He. Adversarial training with fast gradient projection method against synonym substitution based text attacks. Proceedings of the AAAI Conference on Artificial Intelligence, 35, 2021.
[6] Chen Zhu, Yu Cheng, Zhe Gan, Siqi Sun, Tom Goldstein, and Jingjing Liu. FreeLB: Enhanced adversarial training for natural language understanding. In International Conference on Learning Representations, 2020.
[7] Maor Ivgi and Jonathan Berant. Achieving model robustness through discrete adversarial training. In Proceedings of the 2021 Conference on Empirical Methods Natural Language Processing, 2021.
[8] Linyang Li, Ruotian Ma, Qipeng Guo, Xiangyang Xue, and Xipeng Qiu. BERT-ATTACK: Adversarial attack against BERT using BERT. In Proceedings of the 2020 Conference on Empirical Methods in Natural Language Processing (EMNLP), 2020.
[9] Po-Sen Huang, Robert Stanforth, Johannes Welbl, Chris Dyer, Dani Yogatama, Sven Gowal, Krishnamurthy Dvijotham, and Pushmeet Kohli. Achieving verified robustness to symbol substitutions via interval bound propagation. In Proceedings of the 2019 Conference on Empirical Methods in Natural Language Processing and the 9th International Joint Conference on Natural Language Processing (EMNLP-IJCNL)), 2019.
[10] Robin Jia, Aditi Raghunathan, Kerem Göksel, and Percy Liang. Certified robustness to adver- sarial word substitutions. In Proceedings of the 2019 Conference on Empirical Methods in Natural Language Processing and the 9th International Joint Conference on Natural Language Processing (EMNLP-IJCNLP), 2019.
[11] Mao Ye, Chengyue Gong, and Qiang Liu. SAFER: A structure-free approach for certified robustness to adversarial word substitutions. In Proceedings of the 58th Annual Meeting of the Association for Computational Linguistics, 2020.
[12] Wenjie Wang, Pengfei Tang, Jian Lou, and Li Xiong. Certified robustness to word substitution attack with differential privacy. In Proceedingy of the 2021 Conference of the North American Chapter of the Association for Computational Linguistics: Human Language Technologies, 2021.
[13] Jiehang Zeng, Jianhan Xu, Xiaoqing Zheng, and Xuanjing Huang. Certified robustness text adversarial attacks by randomized [MASK]. Computational Linguistics, 49, 2023.
[14] Jeremy Cohen, Elan Rosenfeld, and Zico Kolter. Certified Adversarial Robustness via Random- ized Smoothing. In International Conference on Machine Learning, volume 97, 2019.
[15] Mathias Lecuyer, Vaggelis Atlidakis, Roxana Geambasu, Daniel Hsu, and Suman Jana. Certified robustness adversarial examples with differential privacy. In 2019 IEEE Symposium on Security and Privacy (SP), 2019.
[16] X. Zhang, H. Hong, Y. Hong, P. Huang, B. Wang, Z. Ba, and K. Ren. Text-CRS: A generalized certified robustness framework against textual adversarial attacks. In 2024 IEEE Symposium Security and Privacy (SP), 2024.
[17] Zhuoqun Huang, Neil G. Marchant, Keane Lucas, Lujo Bauer, Olga Ohrimenko, and Benjamin I. P. Rubinstein. RS-Del: Edit distance robustness certificates for sequence classifiers via randomized deletion. Advances in Neural Information Processing Systems, volume 36, 2023.
[18] Zhuoqun Huang, Neil G. Marchant, Olga Ohrimenko, and Benjamin I. P. Rubinstein. CERT- ED: Certifiably robust text classification for edit distance. Findings of the Association for Computational Linguistics: EMNLP 2024, 2024.

---

[19] Francisco Eiras, Motasem Alfarra, Philip TOm, M. Pawan Kumar, Puneet K. Dokania, Bernard Ghanem, and Adel Bibi. ANCER: Anisotropic certification via sample-wiss wise volume maximiza- tion. Transactions on Machine Learning Research, 2022.
[20] Motasem Alfarra, Adel Bibi, Philip H. S. Torr, and Bernard Ghanem. Data dependent random- ized smoothing. In Proceedings of the Thirty-Fighth Conference Uncertainty in Artificial Intelligence, volume 180, 2022.
[21] Peter Súkeník, Aleksei Kuvshinov, and Stephan Günnemann. Intriguing properties of input- dependent randomized smoothing. In Proceedings of the 39th International Conference on Machine Learning, volume 162, 2022.
[22] Xiang Zhang, Junbo Zhao, and Yann LeCun. Character-level convolutional networks for text classification. In Advances in Neural Information Processing Systems, volume 28, 2015.
[23] Gao, Jack Lanchantin, Mary Lou Soffa, and Yanjun Qi. Black-box generation of adversarial text sequences to evade deep learning classifiers. In 2018 IEEE Security and Privacy Workshops (SPW), 2018.
[24] Siddhant Garg and Goutham Ramakrishnan. BAE: BERT-based adversarial examples for text classification. In Proceedings of the 2020 Conference on Empirical Methods in Natural Language Processing (EMNLP), 2020.
[25] Dianqi Li, Yizhe Zhang, Hao Peng, Liqun Chen, Chris Brockett, Ming-Ting Sun, and Bill Dolan. Contextualized perturbation for textual adversarial attack. In Proceedings of the 2021 Conference of the North American Chapter of the Association for Computational Linguistics: Human Language Technologies, 2021.
[26] Robert A. Wagner and Michael J. Fischer. The string-to-string correction problem. Journal of the ACM, 21, 1974.
[27] Csirik, B. G. Frenk, M. Labbé, and S. Zhang. Heuristics for the 0-1 min-knapsaack problem. Acta Cybern., 10, 1991.
[28] George B. Dantzig. Discrete-variable extremum problems. Operations Research, 5, 1957.
[29] Jinyuan Jia, Xiaoyu Cao, Binghui Wang, and Neil Zhenqiang Gong. Certified robustness for top-k predictions against adversarial perturbations via randomized smoothing. In International Conference Learning Representations, 2020.
[30] Justin Mason. SpamAssassin public mail corpus. http://sppaassaassnn apache org/ publiccorpus/ 2006. dataset 6047 email messages categorized into spam non- spam for testing spam filtering systems. Includes multiple revisions and updates, with detailed metadata in the README filc.
[31] Yangyi Chen, Hongcheng Gao, Ganqu Cui, Fanchao Qi, Longtao Huang, Zhiyuan Liu, and Maosong Sun. Why should adversarial perturbations be imperceptible? Rethink the research paradigm adversarial NLP. In Proceedings of the 2022 Conference on Empirical Methods in Natural Language Processing, Abu Dhabi, United Arab Emirates, 2022.
[32] Andrew L. Maas, Raymond E. Daly, Peter T. Pham, Dan Huang, Andrew Y. Ng, and Christopher Potts. Learning word vectors for sentiment analysis. In Proceedings of the 49th Annual Meeting of the Association for Computational Linguistics: Human Language Technologies, 2011.
[33] Hannah Rashkin, Eunsol Choi, Jin Yea Jang, Svitlana Volkova, and Yejin Choi. Truth of varying shades: Analyzing language in fake news and political fact-checking. In Proceedings of the 2017 Conference on Empirical Methods in Natural Language Processing, 2017.
[34] Liu Zhuang, Lin Wayne, Shi Ya, and Zhao Jun. A robustly optimized BERT pre-training approach with post-training. In Proceedings of the 20th Chinese National Conference on Computational Linguistics, 2021.
12

---

[35] Jiabao Ji, Bairu Hou, Zhen Zhang, Guanhua Zhang, Wenqi Fan, Qing Li, Yang Zhang, Gaowen Liu, Sijia Liu, and Shiyu Chang, Advancing the robustness of large language models through self-denoised smoothing. In Proceedings of the 2024 Conference of the North American Chapter of the Association for Computational Linguisties: Human Language Technologies (Volume Short Papers), 2024.
[36] Elias Abad Rocamora, Grigorios Chrysos. and Volkan Cevher. Certified robustness in NLP under bounded levenshtein distance. In JCML 2024 Next Generation of Al Safety Workshop, 2024.
[37] Hongbin Liu, Jinyuan Jia, and Neil Zhenqiang Gong. PointGuard: Provably robust 3D point cloud classification. In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition (CVPR), CVPR, pages 6186-6195, 2021.
[38] Jan Schuchardt, Yan Scholten, and Stephan Günnemann. (Provable) adversarial robustness for group equivariant tasks: Graphs, point clouds. molecules, and more. In Advances in Neural Information Processing Systems, NeurIPS, 2023.
[39] Aleksandar Bojchevski, Johannes Gasteiger, and Stephan Günnemann. Efficient robustness certificates for discrete data: Sparsity-awart randomized smoothing for graphs, images and more. In International Conference on Machine Learning, ICML, 2020.
[40] Jeet Mohapatra, Ching- Yun Ko, Lily Weng, Pin-Yu Yu Chen, Sijia Liu, and Luca Daniel. Hidden cost of randomized smoothing. In International Conference Artificial Intelligence and Statistics, pages 4033-4041. PMLR, 2021.
[41] Saiyue Lyu, Shadab Shaikh, Frederick Shpilevskiy, Evan Shelhamer, and Mathias Lécuyer. Adaptive randomized smoothing: Certified adversarial robustness for multi-step defences. In The eighth Annual Conference on Neural Information Processing Systems, 2024. URL https://openreviier www.iiew.eeeeeeeeeeeeeeeeeeeeeee MeerumiiddMMiAtOOO.i
[42] Guang-He Lee, Yang Yuan, Shiyu Chang, and Tommi Jaakkola. Tight certificates of adversarial robustness for randomly smoothed classifiers. In Advances in Neural Information Processing Systems, volume 32, 2019.
[43] John Morris, Eli Lifland, Jin Yong Yoo, Jake Grigsby, Di Jin, and Yanjun Qi. Textattack: framework for adversarial attacks, data augmentation, and adversarial training in nip. In Proceedings of the 2020 Conference on Empirical Methods in Natural Language Processing: System Demonstrations, pages 119-126, 2020.
[44] Di Jin, Zhijing Jin, Joey Tianyi Zhou, and Peter Szolovits. Is BERT Really Robust? A Strong Baseline for Natural Language Attack on Text Classification and Entailment. Proceedings of the AAAI Conference on Artificial Intelligence, 34, 2020.
13

---

A Proofs and Additional Results
This appendix provides proofs for the results in Sections 3.3 and 3.4 For the proof of Lemma 2
refer the reader Lemma 4 of Huang et al. [17] We also provide an additional result (Lemma showing that our certificate for variable rate deletion recovers the certificate of Huang et al. for fixed rate deletion, with only a negligible difference.
Before proving Lemma 3 we obtain bounds on the sums that appear in the decomposition of the smoothed class probability Py (æ; ft) presented in Equation
Lemma 5.
E
(1)(E S (01=)-1=*1
(6)
(E(()))((
Σ eEf(x,e*)
(e, py fo) + w101-1111
(7)
Proof. First, observe that
Σ
Σ
856 ())
<E(())((((.e))
eEE(x,Ee)
< 1
Σ
g(E/x))
<EE(x,e*)
wi - |x*1
a(c' - c/2:)
cEE(1,cc)
<
|=*|
Then it is straightforward to decompose the smoothed class probability
Py(a;; fu)
Σ
(e,(xx))+ +
Σ
(5,(E,))
cEE(an.c)
cEE(a))(((,c**
and obtain the lower bound
Σ <EE(m.e*)
8 (E, = Po(
Σ
8 (e,
(EE()))(((m.t))
2 py( - -0110111=1
Our proof strategy for Lemma restated below, is inspired by the analysis of Lee et al. for continuous-space smoothing. However, several key adaptations necessary for the discrete, variable-length setting. First, their analysis relies on partitioning the space of perturbed inputs and ordering the parts by increasing likelihood. This is not possible in our tractable due to the fact that multiple paths can lead to the same perturbed input. Second, discrete space requires careful treatment of rounding ensure validity of the bound.
this likelihood is
Lemma 3. Let x. X be a pair of inputs with a longest common subsequence (LCS) x* and let (=; ft). Define
min B.(l=* 1111 max "
h
1 2 J. 1 < v.
H
h,
as a threshold on the number of tokens retained when editing a, where By (n. p) (+) - p
is the Binomial pmf for trials with success probability 1 p. Then there exists a lower bound
14

---

1b(1, x. 2, S (T: fo) such that:
1b(μ, 2, 2) = + -
(1-1)( -1)41==)
B,(12*1, 1)) (=((++)))
c(ss, [c]| 1,, H²))
(1:1) )
+ BH 10.-(12%1,,)
B (12² 12)))1))
where
[2,, (2, = 1 + +/ (1-1)(11 -1+t1=1))++"1
Σ
1,(1='),1b,
+=((+++1)
1 = 1 2eb is a binary indicator and
L.]v = v is gridded flooring operation.
Proof. We will prove the where vb > v. the proof for the opposite case follows similar logic. By dropping the second sum in Equation
we obtain the following lower bound:
Py fu)
Σ
plu, +) <) 8% (c.
eE0(x.e")
(w:f6)
Since (i
(il non-negative constant, we focus on lower bounding the summation term ( fb) and reinstate the constant later.
F ( (a( f) n be the set of base classifiers that are consistent with the observed value of the smoothed class probability μ = Py (æ; fb). We seek a lower bound on (ū, fb) that does not depend on the functional form of the base classifier, so consider the worst case in the set F:
o a fx)
min JEF
Σ eEE(z,ee)
p(u, b) sT(E,
(
We can rewrite the sum over E(x, E²) as a double sum over the number of retained elements i, followed by sum over edits the set (x e*) = {E E(x, |e| i). Hence we have
RHS of
min JEF
p b)
8f(c,2))
cEE,(a,e))
1="|
min
1 (1 R)
|
1 ((apply(m.c)) (EE,(
JEF
0=0
where the second equality follows from the definitions of s5(c, and p()), b) in Lemma and the i..dd Bernoulli specification of g<</z))
Let [r]] {0..... .......* n denote the of non-negative integers up to n. We rewrite the minimization problem in Equation as minimization problem over the set of functions H from [N] to [M] where N |2*| and M = UEIN (?). Specifically, we have
min NEW
(i)h(i)
2=
s.t.
h(i)
Σ
1 ((spll((z.)) and FEF,
(10)
(x,,6
where we have defined v(1) & 5ー (1 Jy.. Next, continue lower bound the solution to the above problem by relaxing the constraints. First, we replace F by superset (invoking Lemma 3):
((i
Σ
(apply((r.))=== 2 W
1=
cEE,(a,,e))
15

---

where we have defined w(i) == (1 - 15) N and W = 1 2/ -N The new constraint on
(replacing Equation I0p is then
h(1)
Σ (=,,(
Happly((ee))=
and m(i)(()) w and FEX-D.
Second, relax the constraint further, by allowing h(t) be any integer in the set [(:)]-
The resulting relaxed minimization problem is bounded knapsack problem:
min
(i)((()
(11)
NEW
Σ w())(()) 2 w and h(1) - (
s.t.
(12)
Noting that the value per unit weight v(i)/w(1)) = p(b, 3) is increasing in for s/ 2 v we propose the following greedy "solution", which slightly violates the constraint:
< H
W ------- 1-0 (Ww())) w(H+)
(1)
i= H
otherwise,
where H' win w7)w) H.
We now show that h" yields valid lower bound on Equation 11
First, observe that
w (1) < W,
(13)
which means the constraint in Equation 12 is not necessarily satisfied by h². Now suppose there
exists a solution h' to Equation 11 that yields tighter lower bound than h". Define A(i) =
w(i)(h((i) (i) (i)) and observe that A(i) when i < H" and (i) S 0 when H* By
combining Equation 13 (for h²) and Equation 12 (for h)), we have Σ (i) S 0. Together, these results imply
p(b. ()(() Sp(s, H'
Σ A(i 1=0
The first inequality holds because we are increasing the magnitude of positive terms (i H²) and decreasing the magnitude of negative terms (i H*), noting that p(1, 3² is increasing in i. This then implies (by expanding the definition of (i))::
N
Σ (())((1)
Σ ())
Σ P(
Σ (1))(1))
which is contradiction, thereby confirming that ht yields a valid lower bound. Substituting ht in the objective yields the following lower bound:
N
a (E; fb)
(1)
|e*|
H
Σ
B,(l=%),
+ 10 10|0--1=1|
|==1
H
By
2
xb)
+ Bg (1=5),())
f=
Bh (1 +))
(1=
16

---

Finally, we multiple both sides of the above inequality by (a fv).
obtain the desired lower bound on
We use the same proof strategy to obtain an upper bound on the smoothed probability below, The upper bound can be used derive a robustness certificate for in the style of Lecuyer et al. [T5]
Lemma 6. Let a, x X be a pair of inputs with longest common subsequence (LCS) and Py (2; ft). Define
min i B(0* H, max n: 1,0)2
+ S v + > 1/.
H*
H,
as a threshold on the number of tokens retained when editing æ. where B (n, = (*) pm> is the Binomial pmf n trials with with success probability 1 p. Then there exists an upper bound ub( x. iz, 1b) 2 Pv (z;; ft) such that:
ub(H, 2. 21) 1500
-1=
Σ
Bi([=*).
| |2-1
(=0(H++1)
(((,,12*), 1b, H²))
BH- (12%),0)
1 13111-1=11
Bи- (12*1,0))
(1:11)
where
du, v, (1-9) -1)+gll=""
Σ
B,((z*),
H=
9 1828 is binary indicator and [. [ G. is gridded ceiling operation.
Proof. We will prove the case where vp S J.. By combining Equations and we obtain the following upper bound:
(0; fb) S T
Σ
p(v; 15) (e, + (1- (55aa -1=1))
eES(2,ee)
a(axfh))
We focus upper bounding the summation term (w;; fo) and reinstate the constant factor term in parentheses later.
3 and
Let F {f Py (x; /) = μ} be the set base classifiers that are consistent with the observed value of the smoothed class probability (y ft). We seek an upper bound on a (@t fb) that does not depend on the functional form the base classifier, so we consider the worst case in the set F:
(
fb) max JEF
Σ
p(4,)5) s(((,x))
(14)
cEE(xxe*)
Rewriting the sum E(x, E*)
as double over the number of retained elements and edits in Ex e*) (see proof of Lemma we find:
RHS
14
max JEF
p
Σ
s7(e,x) x))
(x,e))))))
|=*|
Hi
1 (1 F)
H(pply(z.c))==
(15)
FEF
1=0
cEE,(m,c*)
17

---

Let in] = .f.....,7. } denote the set of non-neen non-negative integers up to n. We can rewrite the maximization problem Equation 15 as maximization problem over the of functions H. from [N] to [M] where | and U.e[N] (*). Specifically, we have
max (i)((i)
NEW
s.t. h(t)
(apply((.c))== and fe (EE,(m,c*)
Σ
(16)
where we have defined v(1) the above problem by relaxing the constraints. First, we replace F by superset:
& i 15). Next, continue lower bound the solution to
Σ w(i)
1 (applyy(m.)))- S
where we have defined wi) == (1 4) of N The new constraint on à (replacing Equation 16 then
h(1)= = Σ H(applyla..)) and Σ w())(() and fe x
(EE,(w.)")
Second, we relax the constraint further, by allowing h(t) to be any integer the set ((,)].
The resulting relaxed maximization problem is a bounded knapsack problem:
max
(i))(()
(17)
NER
1=0
Σ w(i)h(i) S n and M(1) < (
(18)
Noting that the value per unit weight vii)/((i) p(ا. 3) is decreasing in for ab S 3 we propose the following greedy "solution", which slightly violates the constraint:
<< H
( (0))
h1(1)=
i= H
0.
otherwise,
where H* = min H. El (7)))))
H.
We now show that h" yields a valid upper bound on Equation 17 First, observe that
wii) 4.
(19)
which means the constraint in Equation 18 is not necessarily satisfied by ht., Now suppose there
exists a solution h to Equation 17 that yields a tighter upper bound than h²". Define A = w<))(h" (i) hi))) and observe that (11) > when i < H' and ( O when H* By
combining Equation 19 (for h²) and Equation 18 (for 1/), we have
A Z Together, these
results imply
Σ p( (() 2p(1, H' Σ A(i)
1=0
The first inequality holds because we are decreasing the magnitude of positive terms (i < H²) and increasing the magnitude of negative terms (i >> H*), noting that p(t,, 35)5 is decreasing in This then implies (by expanding the definition of (())::
N
N
N
Σ (())(()) = Σ p(u. 1)) "i)h"""" (1) 2 Σ p( / (1))((1) Σ (1))
0
18

---

which is contradiction, thereby confirming that ht yields a valid upper bound. Substituting h* in the objective yields the following upper bound:
a fb)
(i)
|=*
H
1 Σ 11
By (| 1,44
Σ
Ba(1=*bb0) + Bn (1=1,122.10 15)
Bи-
(1:11)
Finally, multiple both sides of the above inequality by Py(a; fo).
T gill
obtain the desired upper bound
Theorem 4. Given a smoothed classifter f as described Algorithm with a length-dependent deletion function v.
Vā E (x; f(x) f())
with confidence level least 1
Proof. By the definition of the smoothed classifier f. the prediction is determined by the probability
distribution induced by (v(=)) Let the and tub be the Clopper-Peatee Pearson lower and upper confidence bounds, respectively, for the probabilities of the top class and the runner-up class By Algo- rithm these are estimated such that, with confidence least a,
Pys (z) for (w))) 2 t and
uh 12
Pyz Pyz for (m))
For any perturbation (x; o), Algorithm and Lemma ensures that
22
22
By transitivity, it follows that
Pys (æ;; fur Av(w)) > Puz (2z for ow(w))
with probability at least 1 a. Hence, the predicted class remains y1 for all perturbations within (x o), completing the proof.
Lemma 7. By setting the deletion probability fixed constant, i.e., vb(x) == for all Lemma recovers Theorem 5 of Huang et al. (17) with only a negligible difference.
Specifically, let ac ic E X be a pair of inputs with longest common subsequence (LCS) z" and μ (2, Under this assumption, the probability Py( f6) satisfies the lower bound
Pa( (6) 2 Pael ||
(n 11-1+
(oc] Pde
-1=1 -
H |='1-
-dee)
Pdel
Here, H represents the minimal number of retained tokens required to satisfy
Σ B,(lz*) (.ee)) 2 4 Pdel
|||1
where B& (n = (1) - p)k - is the Binomial pmf for n trials with with success probability 1 p.
The difference from Theorem 5 of Huang et al. 177 is solely due to the term (1 |||+ ="I-H" which is typically less than 10-7, negligible compared to the other terms.
Pdel)* H² ) Pael
19

---

Proof. As vb = 2 pdel.
أ (1 (1-D((1-1)+44))
(
Py b fb)
Σ
1,((=*1,1)
|//00/112 i=((--11)
+ 160011111
Σ -1-))
By (5
-1-((1-)))
+ BH (12*1,05)
13 (12*1.
H -1
[8 - [c0
Σ B:(1z*1,Pde))
Pdel
1=-1 Σ -1 B,(12* Pdel)
+ BH (1=* (Pee)
1
Pdel
BH- (12* (Pdo))
(1=-)-
-1
Pdel
[8 - (o0
Σ
Be(12*1 l.Pee)
1 - + Pdel
|=1-12*
= (1
H
|2*1 H
BH (12*) Pdel)
(.eel)
BH (|2*) Pdel)
ja Pdel
loe
1o Pdel
1="|
(1 Pdel) H" |0|1||o|+|="1--1
11
Pdel
The first equality holds because I evaluates to 0. The last inequality holds because [a] 2 1, which applies to the gridded flooring operation.
This result closely matches Theorem of Huang et al. 17), differing only by the term (1
Pael) H" |2|-| x"I-H" which is typically less than 10-7, negligible compared the other terms.
Pael
B Certification for Arbitrary Deletion Probability Functions
In Lemmas and we obtained bounds on the smoothed class probabilities at neighboring input æ some query input æ. These bounds can used directly for edit distance certification, by exhaustively enumerating over all neighboring inputs E that are within edit distance r from æ. Algorithm details how this can be done. We note that this algorithm provides significant advantage over naively certifying the smoothed model. A naive approach would require running a full Monte Carlo estimation for every neighbor æ whereas our algorithm performs the costly estimation only once for the original input The certification check for each neighbor then relies the analytical bounds, which are computationally inexpensive.
Algorithm 2 CERTIFY GENERAL
Require: fb: base classifier, input sequence, y1 predicted class, th: length-dependent deletion probability function, o: allowed edit operations, at significance level
Ensure: r: maximum radius that can be certified
1: tl < Ph (x: fur P a:)
2: tub < maxx pyb(<;; fb. ds. a))
3: for to 00 do
4:
for all Ø E B, B do
5:
7th с- [b x 1))
6:
aub + ub ti x. H. v.)
2g
7:
7 < 1 then
8:
return
9:
end if
10: end for
11:
end for
20

---

C AdaptDel+ Details and Intuition
In this section, we provide details and intuition behind the optimization process for AdaptDel+. The core idea is to calibrate the deletion mechanism by finding optimal expected lengths for each input bin, ensuring that certified robustness is maximized while maintaining minimum certified accuracy threshold.
Create Equal Width Bins Algorithm 3 is used to create bins based on the lengths of the input sequences, ensuring that each bin contains least minimum number of samples. The algorithm first computes the lengths of all sequences in the dataset and trims extreme outliers based on specified percentage. then iteratively reduces the target number of bins, recalculating new set of equally spaced boundaries in each step. until all bins contain at least the minimum number of samples. The result a set of bin boundaries that divides the dataset into equal-width intervals, tailored the data distribution while avoiding sparsity issues. We use these crude bin boundaries with some manual calibration. We report the exact bin boundaries used Appendix
Algorithm 3 CHEAVEEDYAAAMCEEEUUWWWWTTTTE
Require: Dataset D. Threshold C, Outlier percentage a (default: 1%)
Ensure: Bin boundaries B
1: Compute input lengths for all samples in
2: Trim lengths outside and 100 percentiles
3: Initialize k f estimated number of bins, Bx + equally spaced boundaries
4: while True do
5: Assign data to bins defined by B&
6: if all bins have at least C' samples then
7: Break
8:
end if
9:
k k+
Update B equally spaced boundaries for &s bins
11:
i < then
Raise error: Cannot satisfy threshold end if
13:
end while
15:
Return B₁
Optimizing Certified Radius Algorithm 4 describes the process of determining the maximum certified radius (r) that meets specific certified accuracy threshold (T). This achieved by iteratively calculating the certified accuracy for each radius using the dataset and checking whether it satisfies the threshold. The objective is to return the largest and the corresponding certified accuracy (CertAcce,) for that level of robustness. However, due the discrete nature of the objective, the optimization surface is non-smooth, making direct optimization challenging. To address this, we also calculate the certified accuracy, which provides smoother metric helpful for hyperparameter tuning.
Algorithm 4 MAXCERTRADIUS
Require: fo: Base model, k: Expected lengths after deletion, D: Dataset, Certified accuracy threshold, o: allowed edit operations
Ensure: Maximum certified radius Certified accuracy CertAcc,
1: Define deletion function (xx)) == &
2: (x) CERTIFY v.
3: for mar-- = 0 xo do
4: CertAcc, + E (a.jeD
r 1 (on
[]
5: if Cert.Ac,, < 7 then CertAcc,-1
6: return
7: end if
8: end for
21

---

Finding Optimal Expected Lengths The AdaptDel+ mechanism employs Algorithm to optimize the expected lengths for each imput bin. The input data is divided into bins based on sequence lengths. and for each bin, we identify the expected length after deletion that maximizes the certified radius and aceuracy while adhering to the minimum accuracy threshold. The relationship between the expected length and the optimization objectives is approximately unimodal, allowing the use of efficient search methods.
We adopt golden section search to minimize the number of queries required for optimization. This choice is particularly advantageous computing certified radii and accuracies involves expensive stochastic sampling from randomized smoothed models. Golden section search strikes a balance be- tween accuracy and computational efficiency, making it well-suited for this problem. The asymptotic complexity of this calibration process is linear in both the number of bins, and the sample size per bin, m. This results from the main loop iterating through each of the bins, while the optimization search performed within each bin has a cost that is linear in the m samples being evaluated.
Algorithm OPTTMIZEEXPPCTTEDEENO
Require: fs: base model, ID: training dataset, fgo- .1..... In ): bin intervals, т: certified accuracy threshold, tol: search tolerance, m: sample size per bin, allowed edit operations
Ensure: Optimized expected lengths K
1: Initialize K [0, (0.....0) 0]
2: for i {1,
- 1} do
3: Sample m data points from the interval
+ - {x |<| E (8..9i+1)
4: low - 9 high 0.3 gi
5: while high 1 low > tol do
6:
mi + low + (3 - /2 (high - low)
7:
m2 f high (3 /5 (high low)
8:
71, T1,CAi MAXCERTRADIUS fú. m1, D, T,
9:
T2, CA2 + MAXCERTRADIUS (f. m2, D,
(f: > 12) or (r1 = 12 and CA₁ > CA2) then
11:
high < m2
else
13:
low m
14:
end if
15:
end while
16: K e (high + low)/2
17:
end for
18: return Optimized expected lengths K
Stochastic Challenges Despite its efficiency, the optimization process can be sensitive to the stochastic nature of randomized smoothing models and potential biases in binned data. This occasion- ally results optimized expected lengths (k) that are not strictly increasing with bin lengths, which can slightly affect the smoothness of the calibration. To mitigate this, additional regularization or smoothing steps may be considered during the optimization process.
The resulting optimized expected lengths (K) are then used to parameterize the deletion function (xx), as defined in Section 3
K (((z))
((x) =
x
where g(x) is the index of the bin corresponding the input æ. This adaptive approach ensures robust performance across varying input lengths and scenarios.
D Evaluation Setup
We describe the detailed evaluation setup in this section.
22

---

Number of Instances
Dataset
Avg. Words
Train
Valid
Test"
Yelp
134.1
585 000
63 000
10000
SpamAssassin
228.2
2152
239
2.378
IMDB
231.2
22,500
2500
25000
LUN
269.9
13416
1 1490
6454
Table 1: Summary of datasets. "Avg. Words" denotes the average number of words per instance in the dataset.
"The full test set is used for evaluation for all datasets except for Yelp, where we sample 000 instances from the available 50 000 instances.
D.1 Dataset Specification
We collect all data from HuggingFace Datasets and the AdvBench repository 31
D.2 Parameter Settings
Parameter
Values
Model
AnteeeeelllssSsqqeeeeealalaaiaia ("roberta-
Base model
Tokenizer
Python command
wransformers.get wet.tggeeete__eeeeeeeeeeeeeeeeee wwieear_shheuleeerrre hetphhhuuleewihh___eee_eeeeeeeee warru
Scheduler
Warmup epochs
10
Python class
torch. torch.optim. AdamM
Learning rate
2.0E-5
Optimizer
Weight decay
1.0E-6 clip_grad_ hupp_grad_norrs norm___om____ (model. dondel..praae parametera (), 1.0)
Gradient clipping
Batch size
32
Max. epoch
200
Training
Early stopping
No improvement in validation loss after 25 epochs
Table 2: Parameter settings for RoBERTa, the optimizer and training procedure. Parameter settings consistent across all models (NoSmooth, CERT-ED, RanMASK, AdaptDel, AdaptDel+) except where specified.
For all randomized smoothing mechanisms, perturbations are applied at the word level. Specifically, an imput text first split into sequence of words using white-space tokenization. The smoothing mechanism then deletes words from this sequence. The resulting sequence of words is joined back into a string, which is then passed the base RoBERTa model's tokenizer for processing into subword tokens. We fine-tune the base RoBERTa model on these perturbed inputs using the respective training split for each dataset. The default parameter configurations for our experiments are provided in T2 We avoid individually calibrating the optimizer or training schedule for each model, as the default settings demonstrate robust performance across all datasets. To approximate the smoothed models (RanMASK, CERT-ED, AdaptDel, AdaptDel+), we rely on Monte Carlo sampling with 1000 perturbed inputs for prediction and 4000 for certification, using significance level 0.05.
D.3 AdaptDel+ Setup
To train and calibrate AdaptDel+, use the parameter settings provided in Table Since the optimized expected lengths are not available during training. we use random deletion probability ranging from 70% 99%. Empirically, this strategy proved effective in producing stable smoothed classifier. The certified accuracy threshold (7) is set to 40% for the Yelp dataset and 75% for the
23

---

Dataset
Parameter
Values
10. 28, 82, 135, 189, 243, 296, 350, 404, 457, 511, 565, 619, 672, 780, 887,887,888 oo]
Bin boundaries B
Yelp
Threshold
0.40
Sample size per bin
200
[0, 72, 133, 194, 256, 318, 379, 440, 502, 564, 625, 686, 748, 810, 871, 932, oc]
boundaries B
IMDB
Threshold
0.75
Sample size per bin
200
Bin boundaries B [0, 23,, oo]
SpamAssassin
Threshold
0.75
Sample size per bin
50
Bin boundaries B [0,85, 150,216, 282, 347,
LUN
Threshold
0.75
Sample size per bin
200
Table 3: Parameters used in optimizing AdaptDel+.
IMDB, SpamAssassin, and LUN datasets. Bins are created using the entire training set (excluding validation samples). and manual deletion boundaries made if the number of bins is excessive. For optimizing the expected lengths, we use Monte Carlo sampling with prediction size of 32 and certification size of 256. The specific number of samples per bin used for optimization is outlined in Table Finally, we do not retrain the base model after determining the optimal deletion rates.
E Additional Experimental Results
We provide additional experimental results and details in this section. We first present the values of (x(x) and ky(=) for AdaptDel and AdaptDel+ in Appendix E.1 We then provide additional certified accuracy results, the quantile certified accuracy results for the IMDB and LUN datasets, and certified
accuracy as function of the certified radius for all datasets in Appendix E.2 We also include an
ablation study on the Pdel values for AdaptDel and AdaptDel+ in Appendix with discussion on the computation complexity and cost of our methods in Appendix
E.3 Finally, we conclude
F.1 Parameters for AdaptDel and AdaptDel+
We present the values of (b())) and kig(z)) for AdaptDel and AdaptDel+ in Figure 3 Unlike Adapt- Del, AdaptDel+ does not enforce a strictly monotonically increasing (b(x). Instead, AdaptDel+ dynamically adjusts (bxx) according the characteristies of the dataset. Future work could further investigate richer classes of (zx), potentially including regularization methods. Our framework is specifically designed to allow such flexibility.
E.2 Other Certified Accuracy Results
As illustrated in Table 4 both AdaptDel and AdaptDel+ maintain competitive clean accuracy while significantly enhancing robustness guarantees compared to RanMASK and CERT-ED, particular, they improved the mean certified radius by average of over 50%. and the median cardinality of the certified region by up to 30 orders of magnitude. This substantial expansion highlights the effectiveness of adaptive deletion in certifying robustness against significantly broader space of perturbations, making particularly valuable in adversarial settings where sequence manipulations common.
report standard deviation (normalised as standard error) in Table 4 but note that it does not directly imply statistical significance due to input length being key variable. Instead, report

---

mvssaasan
Yelp
SpamAtsaassnn
0.33
250
520
750
1000
1.0
700
330
400
200
600
000
800
1003
103
200
310
IMDB
LUN
IMD8
LUN
250
530
750
1000
1.00
200
200
600
100
200
(a) AdaptDel deletion rates (2x) vs input length
(b) AdaptDel+ deletion rates (xx) vs input length
Yelp
SpamAssassin
6-
13
10
Iraut lengh
Ingur larghh
(c) AdaptDel+ retention rates ky(w) vs input length
Figure 3: Plots of the deletion rate (xxx) for AdaptDel and AdaptDel+ and the retention length lig(e)) for AdaptDel+. The top left plot shows the deletion rates ((x) for AdaptDel as a function of input length. The top right plot shows the deletion rates (xx)) for AdaptDel+ The bottom left plot shows the retention rates kg(=)) for AdaptDel+ as a function of input length. The plots demonstrate that AdaptDel and AdaptDel+ adaptively adjust their deletion rates based on the input length.
function of input length.
25

---

Dataset
Model
Clean Acc.
Mean CR
Wass. Dist.
Agg, log(CC)
NoSmooth
69.25
RanMASK, 90%
57.15
0.61 = 0.013
0.31
0.00
Yelp
CERT-ED, 90%
58.57
0.75 = 0.013
0.26
7.16
AdaptDel, 90%
56,98
0.99 i 0.023
0.28
6.89
AdaptDel+
56.22
0.77 1 0.016
0.24
6.78
NoSmooth
93.48
RanMASK, 90%
86.87
2.33 0.012
0.43
14.02
SpamAssassin
CERT-ED, 90%
88.26
2.35
0.012
0.42
14.49
AdaptDel, 90%
87.99
2.86
1 0.018
0.20
14.77
AdaptDel+
88.06
2.77 + 0.016
0.24
14.01
NoSmooth
98.02
RanMASK, 90%
97.65
5.09 + 0.031
0.58
37.49
Yelp
CERT-ED, 90%
97.81
5.03 + 0.031
0.57
38.66
AdaptDel, 90%
97.73
6.25 0.053
0.30
38.79
AdaptDel+
96.93
12.35 + 0.152
0.14
72.74
NoSmooth RanMASK, 90%
99.16
97.91
4,83 + 0.022
0.31
34.51
LUN
CERT-ED, 90%
98.20
4.94 + 0.019
0.34
37.68
AdaptDel, 90%
97.88
5.65 0.028
0.30
38,90
AdaptDel+
95.09
10.69
0.24
66.90
Table 4: Comparison of robustness certificates across models and datasets. All metrics computed on the full test set. "Mean CR" refers to the mean certified radius, reported with standard error. A larger standard error indicates greater variability in certified radii across examples. We report the Wasserstein distance ("Wass. Dist.") between the standardized distributions of certified radius and input length measure of how well each method adapts to variations in input length (smaller is better). The right-most column reports the median log-cardinality of the certified region. For the Yelp dataset, the first quartile (Q1) of Iog(CC) is reported instead, since the median certified region cardinality is zero. Despite slight degradation in clean accuracy. both AdaptDel and AdaptDel+ significantly outperform RanMASK and CERT-ED in terms of both median and mean robustness.
the Wasserstein distance to capture how well each method adapts to variations in input length. Our adaptive methods achieve a lower Wasserstein distance, indicating a stronger alignment between the distribution of certified radii and the distribution of input lengths. This successful adaptation is also reflected higher variability (SE) of the certified radius, as the method appropriately assigns different radii to inputs of different lengths.
Figure extends our analysis the IMDB and LUN datasets, reinforeing the trends observed Fig- ure 2 In both datasets, certified accuracy improves with input size and log-cardinality, with adaptive deletron methods (AdaptDel, AdaptDel+) outperforming RanMASK and CERT-ED, Cespeill, for longer sequences. For IMDB, since more than 50% of the length variation is concentrated in the last quartile, we observe significant improvement in robustness in this region. contrast, performance in the other three quartiles is more mixed, aligning with our previous observations on the Yelp dataset Figure For the LUN dataset, interestingly, AdaptDel+ underperforms in the first quartile, which may be due to the instability of the AdaptDel+ optimization procedure, as discussed in Appendix C This suggests potential areas for improvement in AdaptDel+. However, its performance improves gradually with increasing input length, similar to the trend observed in SpamAssassin, where both AdaptDel and AdaptDel+ achieve significantly stronger robustness for longer sequences. These results further confirm the scalability of our approach across varying text distributions and input sizes.
Certified accuracy cannot be summarized by single number without losing critical information about robustness under varying radii. To address this, we provide Figure [] which plots certified accuracy as a function of the certification radius, as per convention. Note that this comparison disadvantages AdaptDel, AdaptDel+, and CERT-ED, as RanMASK operates under the more constrained Hamming distance threat model. Despite this, our methods consistently outperform others, following a similar pattern to the certified accuracy log-cardinality plot. This further supports use of log-
26

---

J888855885
0.30
0.0
Alaahin
Maik potatilia vieeen
Pick Uedertellesieee Sleedss
Cuand
0.28
Made detareala sne
Aluabie
0.75
0.75
Maie parta satia 611
Plcck Euttatie
L500000
Conter
1.50
60 Ugg Candinul by. 0g1C
100/0
562
52
75
100
125
150
175
415
Log card Fullyy. lgg
Impu.
(a) IMDB dataset
(b) LUN dataset
Figure 4: Certified accuracy as a function of the log- log-cardinality of the certified region, grouped by quartile of imput size. The subfigure the right displays the quantile by input size, with the dashed lines indicating the quartiles corresponding to the certified accuracy plots on the left. Each set of axes (top bottom) corresponds to split of the test set the length-based quartiles (smallest to largest). For example, the second plot from top to bottom shows the certified accuracies of examples with in Q1 Q2. The results demonstrate that the methods scale effectively higher certified accuracy achieved for larger input sizes and higher log-cardinality regions.
varying input sizes, with
cardinality certified accuracy balanced summary metric that does not unfairly favor any specific method.
E.3 Ablation Study Deletion Rate Lower Bound for AdaptDel
As shown in Table increasing the lower bound pn (and reducing the retention count = [(1 Pib) [B(xx)>)) in AdaptDel consistently improves the certified robustness across all datasets, albeit at a modest cost to clean accuracy. For instance, on the IMDB dataset, raising Pbb from 50% to 95% enhances the mean certified radius from 0.34 to 4.26, with corresponding increase in the aggregated log-cardinality from 0.00 to 20.87. Similar trends are observed on the SpamAssassin and LUN datasets, where higher Plb values lead to significant gains in both the certified region size. This demonstrates that enforcing more aggressive deletion rates amplifies the certifiability of AdaptDel, especially on longer-input datasets. Furthermore, the Wasserstein distance between certified radius and input length steadily decreases with higher Pbb. suggesting that the deletion strengthens. These results underscore the critical role of tuning deletion rates in balancing clean accuracy and robustness guarantees, enabling AdaptDel to scale effectively with input complexity.
certified radius and
certified radius becomes more haput-length-wward
F Analysis of Computational Efficiency
In this appendix, we document the computational requirements for training and certifying the models used in our study. We begin by benchmarking certification time for each method on the SpamAssassin dataset. Next, we report the compute costs of our remaining experiments (both training and certification) as presented in the main paper. Overall, we demonstrate that AdaptDel and AdaptDel+ match or exceed the efficiency of CERT-ED and RanMASK both training and certification.
27

---

60
100
Model,pertutation strength
90
Model perturbation strength
Certified accuracy (96)
50
RanMASK, Prus
CERT-ED, 90%
Certified accuracy (%)
80
CERT-ED, Fiu 90%
RanMASK Pres.
40
AdapDel - 90%
70
AdapDel.pt, 90%
AdapDal+
Adapfiel
20
30
10
20
10
0
5
10
15
20
5
10
15
Radius,
Radius,
(a) Yelp dataset
IMDB dataset
100
100
90
pootl.peturrattion strength
90
Model perturiation strength
CERT-ED, 90%
Certified accuracy (%%
CERT-ED, 90%
RanMASK, Press 90%
RanM/SKK 90%
Certified accuracy
AdapDellpp 90%
70
AdapDelips 90%
60
AdapDall
60
AdapDwit
50
50
40
40
30
30
20
20
10
10
0
30
10
20
Radius, r
Radius, r
(c) SpamAssassin dataset
(d) LUN dataset
Figure 5: Certified accuracy for all methods as a function of the certified radius. While AdaptDel consistently outperforms RanMASK and CERT-ED across all radii, AdaptDel+ achieves the highest certified accuracy for larger certified regions. Note that, CERT-ED, AdaptDel, and AdaptDel+ certifies Leveshtein distance perturbations, while RanMASK only certifies Hamming distance perturbations. Thus, the actual robustness of RanMASK at the same radii is lower than that of CERT-ED, AdaptDel and AdaptDel+.
All experiments in this paper are conducted using private cluster with Intel(R) Xeon(R) Gold 6326 CPU 2.90GHz and NVIDIA A100 GPUs. Unless otherwise specified, we use single GPU for all experiments.
F.1 Standardized Cost Comparison for Certification
The certification process consists of two key stages: Monte Carlo estimation and the certification logic. In the first stage, we estimate the smoothed classifier's output probabilities for the input ar by making Npred = 1000 and Necrt 4000 forward calls to the base model, shown in Lines 2 Algorithm ! This stage dominates the overall runtime. In the second stage, the certification logic (Lines 3-9) uses these estimated probabilities find the largest certified radius. A loose bound on the asymptotic complexity of this second step is O(r²) for certified radius r. This follows since Algorithm I (Lines 3-9) performs a lincar search for the radius (Line 3. contributing factor of
(r)). Within this loop, it iterates through all edit combinations C(o, r) in Line 4 of which there are
O The inner bound caleulations (Lines 6 and are approximately linear in the number of edits, (r)).
Despite this asymptotic complexity, standardized empirical tests show AdaptDel runs 20% and 372% faster than CERT-ED and RanMASK, respectively (Figure(o). Notably, we evaluate runtime efficiency using the SpamAssassin -chaset-chosen specifically as the most challenging scenario due to its
28

---

Dataset
k
Clean Acc.
Mean CR
Wass. Dist.
Median log(CC)
50%
65
67.89
0.16 + 0.066
0.44
0.00
60%
52
66,84
0.32 + 0.07
0.34
0,00
70%
63.33
0,41 + 0.099
0.31
6.32
Yelp
80%
63.13
0.61 + 0.013
0.27
6,60
90%
13
56.98
0.99 + 0.023
0.28
6,89
95%
48.40
1.41 + 0.037
0.32
6.92
50%
115
94.64
0.34 1 0.005
0.29
0.00
60%
92
93.15
0.86 1 0.005
0.39
6.83
70%
91.29
1.01 + 0.007
0.29
6.83
IMDB
80%
90.59
1.61 0.010
0.25
12.51
90%
23
87.99
2.86 + 0.018
0.20
14.77
95%
11
85.25
4,26 + 0.028
0.16
20.87
50%
115
98.15
0.53 + 0.013
0.45
0.00
60%
92
98.19
1,25 + 0.011
0.45
7.02
70%
69
97.98
1.61 + 0.019
0.34
7.02
Spam A ssassin
80%
97.98
3.20 0.024
0.36
20.22
90%
97.73
6,25 + 0.053
0.30
38.79
95%
11
97.69
11.58 + 0.111
0.24
69.84
50%
135
99.32
0.53 1 0.066
0.34
7.18
60%
108
99.36
1.25 1 0.006
0.67
7.18
70%
99.10
1.55 + 0.009
0.42
7.30
LUN
80%
98.74
2.96
0.36
20.51
90%
97.88
5.65 + 0.028
0.30
38,90
95%
13
96.19
9.64 + 0.061
0.21
65.74
Table 5: Ablation study on the deletion probability lower bound phb for AdaptDel, with = [(1 Pl,) [=[ }J. All metrics computed on the full test set. "Mean CR" refers to the mean certified radius, reported with standard error. A larger standard error indicates greater variability certified radii across examples. We report the Wasserstein distance ("Wass. Dist.") between the standardized distributions of certified radius and input length, as a measure of how well each method adapts variations in input length (smaller is better). The right-most column contains the median log- cardinality (log(CC)) of the certified region. For the Yelp dataset, the first quartile (Q1) of log (CC) reported instead, since the median certified region cardinality is zero.
RanMASK
CERTED
AcaptDel
2530
2500
2500
Ferwor Sire 31.0000
Fevirr (ee0 2.7800
Prweettes 2.331
1502
1500
1500
1932
1200
1200
0.0
25
3.0
7.3
12.5
12.3
15.0
0.0
23
532
7.5
20.2
12.5
13.0
5.0
2.5
5.0
75
10.0
12.3
13.2
Time Coal 1sl
Tims Cool 30
Time Oost
(a) RanMASK
(b) CERT-ED
(c) AdaptDel
Figure From left to right are the histogram of computation cost for forward operation and computing certified radius for RanMASK, CERT-ED and AdaptDel, respectively. For this experiment, we set the batch size to 256 and the number of samples for certification to be 4096. As a result, a total of 16 batches required compute the certified radius. The histogram shows the distribution of the computation cost for each method. The total cost of AdaptDel is lower compared to all other methods despite the increased complexity in compute time. This is because the adaptive deletion rate provides shorter smoothed input size for longer inputs, significantly reducing the cost of the forward computation.
29

---

Table 6: Training time statistics for each dataset and model. The number of epochs varies due to early stopping.
Dataset/Number samples
Model
Statistic
Yelp/585 000
SpamAssassin/2 152
IMDB/22 500
LUN/13 416
epochs
30
40
30
.5
NoSmooth
sec/epoch
66269
258
epochs
60
50
65
RanMASK, 90%
sec/epoch
2.5
341
epochs
60
60
CERT-ED, 90%
sec/epoch
2 334
13
128
55
epochs
155
70
AdaptDel. 90%
sec/epoch
989
50
41
epochs
90
65
140
75
AdaptDel+
sec/epoch
3 146
14
73
83
Dataset/Number of samples
Model
000
IMDB/25 (00
SpamAssassin/223378 378
LUN/6
RanMASK, 90%
9313
131
13 899
641
CERT-ED, 90%
2 233
3311
3319
4889
AdaptDel, 90%
129
896
4.900
3 174
AdaptDel+
269
1812
857
2
Table 7: Certification time in milliseconds per sample on the test for each dataset, including overheads. We use 1000 Monte Carlo samples for prediction and 4000 samples for estimating certified radii.
longer certified radii and shorter sequence lengths. Since the efficiency gains of AdaptDel most pronounced on longer inputs where can apply a higher deletion rate, benchmarking on a dataset with shorter sequences provides more conservative estimate of its performance advantage. The observed efficiency improvement is primarily due to reduced forward-pass times resulting from adaptive deletion rates. In practice, computing the certified radius itself accounts for less than 5% of the total runtime.
F.2
Train
Table 0 shows the number of epochs used train each model/dataset (with early stopping) and the training time per epoch. While AdaptDel is the fastest in training, AdaptDel+ takes similar time to train compared CERT-ED, which is 2-3 times faster than the non-smoothed baseline, and 2-5 times faster to train than RanMASK. The total computation used across all datasets for certification is estimated to be 300 hours A100 GPU time.
In addition to the training times reported in Table the AdaptDel+ method requires a one-time, offline calibration step to determine the optimal expected lengths for each bin, detailed in Appendix C This process is performed after the base model is trained and does not add to the online certification time. On a single NVIDIA A100 GPU, the total calibration times were: Yelp (9.5 hrs), IMDB (12 hrs), SpamAssassin (8 hrs), and LUN (12 hrs).
F.3
Certification
Table 7 shows the average certification time per test instance, including overheads. Our approaches are upto and 10 times faster than CERT-ED and RanMASK. The total computation used across all datasets for certification is estimated to be 240 hours A100 GPU time.
30

---

G Empirical Robustness Against Text Attacks
While the primary focus of our work is on certified robustness, also evaluate the empirical robustness of our methods against several common text-based adversarial attacks. This analysis provides a more practical perspective on model resilience against existing attack heuristics.
Experimental Setup Our experimental setup largely follows the methodology of Huang et al. 18 We evaluate all models randomly selected subsample of 200 instances from each dataset's test set. For the smoothing-bes estimation with 100 samples to approximate the smoothed classifier's 's prediction. This smaller sample size than used for certification, a necessary compromise to make the computational cost of attacking these models feasible. To ensure all attacks terminate within reasonable timeframe, enforce query budget of 3000 calls to the target model and time budget of 2 hours per instance.
defenses (AdaptDel, CERT-ED, and RanMASK), we use a Monte Carlo
Attack Outcomes
Each attack on a given instance can result in of four outcomes:
Success:
The attack successfully finds an adversarial example that changes the model's correct prediction to incorrect one.
Failure:
The attack terminates without finding an adversarial example. This occurs if the attack exhausts its search space or reaches the predefined query limit of 3000 model evaluations.
Skipped: The original input misclassified by the model, so no attack initiated.
Timeout: The attack exceeds the time limit 7200 seconds before terminating.
Metries and Baselines We measure performance using robus! accuracy, defined as the fraction of non-skipped instances for which the attack outcome was either 'Failure' 'Timeout', This metric captures the percentage of initially correct predictions that remain correct after the attack.
We evaluate AdaptDel against several baselines: the smoothing- baaeod methods CERT-ED [8 and RanMASK 13), and the adversarial training method FreeLB 6 These models are tested against five representative attacks using the TextAttack framework
43 which cover diverse range of
perturbation strategies:
2 search for adversarial examples by applying a combination of word insertions, deletions, and substitutions.
General Edit Distance Attacks: Clare 25 and BAE-I
Word Substitution Attacks: BERT-Autack [8] and TextFooler 44 craft attacks by replacing
important words with semantically similar substitutes.
Character-level Attack: DeepWord (23] perturbs the input by applying small character-
level edits (e.g., swaps, deletions) to words.
Results and Discussion The robust accuracy of each model against five widely-used attacks is summarized in Table 8 We observe that AdaptDel achieves a robust accuracy that is broadly comparable to the CERT-ED bascline across most attacks, with differences often falling within the margin of statistical error for the given sample size.
This result is consistent with the primary contribution of our work. The main advantage of AdaptDel is its ability to provide stronger certified robustness guarantees, particularly for longer sequences, by adapting the deletion rate. This adaptation optimized for the worst-case analysis required for certification, which does not necessarily translate to a direct advantage against the specific heuristics employed by these empirical attacks. Therefore, while AdaptDel demonstrates strong empirical resilience par with existing methods, its key benefit remains in the domain of provable security, where it significantly expands the size of the certified region.
H Impact Statement
Where adversarial examples present an important threat to the integrity of learned models, randomized smoothing reflects a well-doeumented defense, while certifications offer reliable measurement of robustness. Together, this research offers potential societal benefit from more resilient AI systems, and
31

---

IMDB
Rebuet Accuracy
Model
ReelB
0.4
AdeciDal
CERTIED
BAS-I
DeepWordRug
BERT-Anack
Attack
SpamAssassin
Rooust Accuraby
Model
0.0
FieeLB
RanMASK
AdapiDel
CERFEDD
0.0
BAE-1
CLARE
DeepWosdHug
TextFooler
BERT-AIack
Attack
Robust Acturaty
0.8
Model
0.0
RanMASK
AdapiDel
0.2
CERFED
BAE-1
CLARE
DeapWordRug
TextFooker
BERT-Alack
Attack
Figure Robust accuracy of AdaptDel compared baseline defenses against five common adversar- ial text attacks. Error bars indicate 95% bootstrap confidence intervals. Across the three datasets, DdaptDel demonstrates empirical robustness that is statistically comparable the CERT-ED baseline. All smoothing-basse methods are highly robust on the LUN and SpamA datasets, while the adversarial training method Freel.B shows vulnerability specific sond-substitution attacks.
Attack
Model
BAE-I
BERT-Attack
CLARE
DeepWordBug
TextFooler
Dataset: IMDB
AdaptDel
0.860 / 0.660
0,865 / 0.575
0.890 / 0.665
0.885 0.540
0.860 / 00.455
CERT-ED
0.885 0.690
0.860 0.580
0,880 / 0.675
0,880 0.540
0.880/ / 0.530
FreeLB
0.940 0.730
0.940 0.060
0,940 0.735
0,940 / 0.485
0.940 0.100
RanMASK
0.875 0.680
0.885 0.535
0.880 0.680
0.880 / 0.495
0.880 0.430
Dataset: LUN
AdaptDel
0.980/0.96.
0.980 0.930
0.980 0.955
0.985 0.920
0.985 0.955
CERT-ED
0.995 0995/0.955 0.955
0.995 0.960
0,995 0.955
0.990 0.960
1.000 0,960
FreeLB
0,995 / 0.990
0,995
0.870
0,995 0.975
0,995 / 0.900
0,995 / 0,900
RanMASK
0.980 0.915
0.980 / 0.900
0.975 / 0.915
0.970 0.910
0.970 0.920
Dataset: SpamAssassin
AdaptDel
0.975 0.945
0,970 0,940
0.970 / 0.935
0,970 / 0.945
0.960 / 0.940
CERT-ED
0.965 0.950
0.965 / 0.945
0.965 / 0.950
0.970 / 0.945
0.970 / 0.950
FreeLB
0.970 0.960
0.970/0.575
0.970 / 0.960
0.970 / 0.795
0.970 / 0.510
RanMASK
0.965 0.945
0.965 / 0.935
0.955 0.945
0.965 0.930
0.965 0.930
Table 8: Empirical robustness results of different models against various attacks on three datasets.
Each cell shows the accuracy before and after the attack (e.g., 0.860 0.660 means 86,0% accuracy before the attack and 66.0% accuracy after the attack).
32

---

better transparency of limitations of robustness. Our work furthers the study of more realistic threat models than 2 e,-bounded perturbations found in vision, with edit distance and sequence classifiers more suitable to NI.. With longer sequences offering greater margin for smoothing by deletion without sacrificing accuracy, we are able better balance utility and certification.
33

---

NeurIPS Paper Checklist
Claims
Question: Do the main claims made in the abstract and introduction accurately reflect the
paper's contributions and scope?
Answer: [Yes]
Justification: We accurately describe the main claims made the abstract and introduction, which reflect the paper's contributions and scope. The paper presents novel approach to randomized smoothing for sequence classifiers, demonstrating its effectiveness in achieving certified robustness.
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made the paper.
The abstract and/or introduction should clearly state the claims made, including the contributions made the paper and important assumptions and limitations. A No or NA answer to this question will not be perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results can be expected to generalize to other settings.
It is fine to include aspirational goals as motivation as long as it is clear that these goals are not attained by the paper.
2. Limitations
Question:
Does the paper discuss the limitations of the work performed by the authors?
Answer: [Yes]
Justification: We discuss the limitations of our work, including assumptions made and their potential impact on the results a dedicated "L "Limitations" section at the end the paper's body.
Guidelines:
The answer NA means that the paper has no limitation while the answer No means that the paper has limitations, but those are not discussed in the paper.
The authors are encouraged to create a separate "Limitations" section their paper.
The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (e.g., independence assumptions, noiseless settings, model well-specification, asymptotic approximations only holding locally). The authors should reflect on how these assumptions might be violated in practice and what the implications would be.
The authors should reflect on the scope of the claims made, e.g. if the approach was only tested on few datasets or with few runs. In general, empirical results often depend on implicit assumptions, which should be articulated.
The authors should reflect on the factors that influence the performance of the approach. For example, facial recognition algorithm may perform poorly when image resolution low or images are taken in low lighting. Or speech-to-tex- system might not be used reliably provide closed captions for online lectures because it fails handle technical jargon.
The authors should discuss the computational efficiency of the proposed algorithms and how they scale with dataset size.
If applicable, the authors should discuss possible limitations of their approach to address problems of privacy and faimess.
While the authors might fear that complete honesty about limitations might be used by reviewers as grounds for rejection, worse outcome might be that reviewers discover limitations that aren't acknowledged
the paper. The authors should use their best judgment and recognize that individual actions in favor of transparency play an impor- tant role in developing norms that preserve the integrity of the community. Reviewers will be specifically instructed to not penalize honesty concerning limitations.
34

---

3. Theory assumptions and proofs
Question: For each theoretical result, does the paper provide the full set of assumptions and a complete (and correct) proof?
Answer: [Yes]
Justification: We provide a complete set of assumptions and proofs for each theoretical result in the paper. We put details of these proofs in Appendix
Guidelines:
The answer NA means that the paper does not include theoretical results. All the theorems, formulas, and proofs in the paper should be numbered and cross- referenced.
All assumptions should be clearly stated or referenced in the statement of any theorems.
The proofs can either appear in the main paper or the supplemental material, but if they appear in the supplemental material, the authors are encouraged to provide a short proof sketch to provide intuition.
Inversely, any informal proof provided in the core of the paper should complemented by formal proofs provided in appendix or supplemental material.
Theorems and Lemmas that the proof relies upon should be properly referenced.
4. Experimental result reproducibility
Question: Does the paper fully disclose all information needed to reproduce the main ex- perimental results of the paper to the extent that it affects the main claims and/or conclusions of the paper (regardless whether the code and data are provided or not)?
Answer: [Yes]
We provide all the necessary information to reproduce the main experimental results Appendix D including details about the datasets, models, and evaluation metrics. Additionally, we provide the code and data used in the experiments.
Justification:
Guidelines:
The answer NA means that the paper does not include experiments.
If the paper includes experiments, a No answer to this question will not perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not.
If the contribution is dataset and/or model, the authors should describe the steps taken make their results reproducible or verifiable.
Depending on the contribution, reproducibility can be accomplished in various ways. For example, if the contribution is novel architecture, describing the architecture fully might suffice, or if the contribution a specific model and empirical evaluation, it may be necessary either make it possible for others replicate the model with the same dataset, or provide access to the model. In general. releasing code and data is often one good way accomplish this, but reproducibility can also be provided via detailed instructions for how to replicate the results, access to a hosted model (e.g., in the case of large language model), releasing of a model checkpoint, or other means that appropriate to the research performed.
While NeurIPS does not require releasing code, the conference does require all submis- sions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) the contribution is primarily a new algorithm, the paper should make clear how reproduce that algorithm. (b) If the contribution is primarily the architecture clearly and fully.
model architecture, the paper should describe
(c) the contribution a new model (e.g., a large language model), then there should either be way to access this model for reproducing the results or way to reproduce the model (e.g., with an open-source dataset instructions for how to construct the dataset).
35

---

(d)
We recognize that reproducibility may be tricky in some cases, in which case authors are welcome describe the particular way they provide for reproducibility. In the case of closed-source models, it may be that access to the model is limited in some way (e.g., to registered users), but it should be possible for other researchers to have some path to reproducing or verifying the results.
5. Open access to data and code
Question: Does the paper provide open access to the data and code, with sufficient instruc- tions to faithfully reproduce the main experimental results, as described in supplemental material?
Answer: [Yes]
Justification: Our experiments based on publicly available datasets, and we provide the code and data as supplementary material. The instructions for reproducing the results are included in the README file.
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurlPS code and data submission guidelines (https://nips.cm cc/
for more details.
While we encourage the release of code and data, we understand that this might not be possible, "No" is an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (c.g., for new open-source benchmark).
The instructions should contain the exact command and environment needed to run to reproduce the results. See the NeurlPS code and data submission guidelines (https
httpa/////uidee/deSSuuuiisissss sonoooooic for more details. 7/ //iips.cc/ppll wttpcccppppppppeeeeeeeeeeeeeeeee
The authors should provide instructions on data access and preparation, including how access the raw data, preprocessed data, intermediate data, and generated data,
The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. If only subset of experiments reproducible, they should state which ones are omitted from the script and why.
At submission time, to preserve anonymity, the authors should release anonymized versions (if applicable).
Providing as much information as possible in supplemental material (appended to the paper) recommended, but including URLs to data and code permitted.
6. Experimental setting/details
Does the paper specify all the training and test details (e.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?
Question:
Answer: [Yes]
Justification: We specify all training and test details in Section 4 and Appendix D including data splits, hyperparameters, and optimizer types in the appendix and also in the provided configuration files.
Guidelines:
The answer NA means that the paper does not include experiments.
The experimental setting should be presented in the core of the paper to a level of detail that is necessary to appreciate the results and make sense of them.
The full details can be provided either with the code, in appendix, or as supplemental material.
7. Experiment statistical significance
Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Question:
Answer: [No]
36

---

While we provide standard error for the certified radius, we do not provide error bars for the results as randomized smoothing expensive and we only run each experiment once.
Justification:
Guidelines:
The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results are accompanied by error bars, confi- dence intervals, or statistical significance tests, at least for the experiments that support the main claims of the paper.
The factors of variability that the error bars are capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, overall run with given experimental conditions).
The method for calculating the error bars should be explained (closed form formula, call to a library function, bootstrap, etc.)
The assumptions made should be given (e.g.. Normally distributed errors).
It should be clear whether the error bar is the standard deviation or the standard error of the mean.
is OK to report 1-sigma error bars, but one should state it. The authors should preferably report a 2-sigma error bar than state that they have 96% CI, if the hypothesis of Normality of errors is not verified.
For asymmetric distributions, the authors should be careful not to show in tables or figures symmetric error bars that would yield results that are out range (c.g. negative error rates).
If error bars are reported in tables or plots, The authors should explain the text how they were calculated and reference the corresponding figures or tables in the text.
8. Experiments compute resources
For each experiment, does the paper provide sufficient information on the com- puter resources (type of compute workers, memory, time execution) needed to reproduce the experiments?
Question:
Answer: [Yes]
Justification: We provide details of the compute resources needed to reproduce the periments, including the type of compute workers, memory, and time execution in Appendix
Guidelines:
The answer NA means that the paper does not include experiments.
The paper should indicate the type of compute workers CPU or GPU, internal cluster, or cloud provider, including relevant memory and storage.
The paper should provide the amount of compute required for each of the individual experimental runs as well as estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported in the paper (c.g., preliminary or failed experiments that didn't 't make into the paper).
9. Code of ethics
Question: Does the research conducted in the paper conform, in every respect, with the NeurIPS Code of Ethics btttps://neurppee httpp//pbl./.thicccccuaeaaeaeeee
Answer: [Yes]
Justification: Our research conforms with the NeurlPS Code of Ethics, and we have taken all necessary precautions to ensure that our work is ethical and responsible.
Guidelines:
The answer NA means that the authors have reviewed the NeurIPS Code of Ethics.
If the authors answer No, they should explain the special circumstances that require deviation from the Code of Ethics.
37

---

The authors should make sure to preserve anonymity (e.g., if there is special consid- eration due to laws or regulations their jurisdiction).
10. Broader impacts
Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer: [Yes]
Justification:
We discuss potential societal impacts in Appendix H
Guidelines:
The answer NA means that there no societal impact of the work performed.
If the authors answer NA or No, they should explain why their work has no societal impact why the paper does not address societal impact.
Examples of negative socictal impacts include potential malicious unintended uses (e.g., disinformation, generating fake profiles, surveillance), fairness considerations (e.g., deploymeetm of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations.
The conference expects that many papers will be foundational research and not tied to particular applications, let alone deployments. However, if there is a direct path to any negative applications, the authors should point it out. For example, it is legitimate point out that an improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point out that a generic algorithm for optimizing neural networks could enable people to train models that generate Deepfakes faster.
The authors should consider possible harms that could arise when the technology is being used as intended and functioning correctly, harms that could arise when the technology is being used as intended but gives incorrect results, and harms following from (intentional or unintentional) misuse of the technology.
If there are negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition attacks, mechanisms for monitoring misuse, mechanisms to monitor how a system learns from feedback over time, improving the efficiency and accessibility of MI.).
11. Safeguards
Question:
Does the paper describe safeguards that have been put in place for responsible release of data models that have high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?
Answer: [NA]
Justification: This applicable work as we do release any data models that have high risk for misuse.
Guidelines:
The answer NA means that the paper poses no such risks.
Released models that have high risk for misuse or dual-us should be released with necessary safeguards to allow for controlled use of the model, for example by requiring that users adhere to usage guidelines or restrictions to access the model or implementing safety filters.
Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images.
We recognize that providing effective safeguards is challenging, and many papers do not require this, but encourage authors to take this into account and make best faith effort.
12. Licenses for existing assets
Question: Are the creators original owners of assets (e.g., code, data, models), used in the paper, properly credited and are the license and terms of use explicitly mentioned and properly respected?
Answer: [Yes]
38

---

Justification:
We credit the creators/owners of the datasets and baselines used in the paper We also provide proper attribution in our code.
(see Section
Guidelines:
The answer NA means that the paper does use existing assets.
The authors should cite the original paper that produced the code package or dataset.
The authors should state which version of the asset used and, possible, include URL.
The name of the license (e.g., CC-BY 4.0) should be included for each asset.
For scraped data from a particular source (e.g.. website). the copyright and terms of service of that source should be provided.
assets are released, the license, copyright information, and terms use in package should be provided. For popular datasets, paperssii thoode com/ com/datasets has curated licenses for some datasets. Their licensing guide can help determine the license of dataset.
For existing datasets that are re- e-packaged, both the original license and the license of the derived asset (if it has changed) should be provided.
If this information is not available online, the authors are encouraged to reach out to the asset's 's creators.
13. New assets
Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?
Answer: [Yes]
Justification: We provide code with instructions for reproducing our results in the supple- mentary material.
Guidelines:
The answer NA means that the paper does release new assets.
Researchers should communicate the details the dataset/code/model as part of their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent was obtained from people whose asset used.
At submission time, remember to anonymize your assets (if applicable). You can either create anonymized URL or include anonymized zip file.
14. Crowdsourcing and research with human subjects
Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given to participants and screenshots, if applicable, as well details about compensation (if any)?
Answer: [NA]
Justification: Not applicable our research does not involve crowdsourcing or human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsoureing nor research with human subjects.
Including this information in the supplemental material is fine, but if the main contribu- tion of the paper involves human subjects, then as much detail as possible should be included in the main paper.
According to the NeurIPS Code of Ethics, workers involved data collection, curation, or other labor should be paid at least the minimum wage in the country of the data collector.
Institutional review board (IRB) approvals or equivalent for research with human subjects
39

---

Question: Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or equivalent approval/review based on the requirements of your country or institution) were obtained?
Answer: [NA]
Justification: Not applicable research does not involve human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with
human subjects.
Depending on the country in which research is conducted, IRB approval (or equivalent)
may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper.
We recognize that the procedures for this may vary significantly between institutions and locations, and expect authors to adhere to the NeurIPS Code of Ethics and the guidelines for their institution.
For initial submissions, do not include any information that would break anonymity (if applicable), such as the institution conducting the review.
16. Declaration of LLM usage
Question: Does the paper describe the usage of LLMs if it is important, original, or non-standard component of the core methods this research? Note that the LLM is used only for writing, editing, or formatting purposes and does not impact the core methodology, scientific rigorousness, or originality of the research, declaration is not required.
Answer: [Yes]
Justification: We used LLMs while implementing scaffolding codes and when making minor adjustments to code. We reviewed any LLM-generated code and made necessary adjustments to ensure correctness. However, the core methods of this research do not involve LLMs as any important, original, or non-standard components.
Guidelines:
The answer NA means that the core method development in this research does not involve LLMs as any important, original, or non stanstandard components.
Please refer to LLM httppp///beerpppcccccc/oooeerrre for what should or should not be described.
40


Reviews:
[{"review_id": "KW7vuEboqt", "reviewer": "Reviewer_Sr1y", "summary": "This paper proposes AdaptDel and AdaptDel+, two randomized smoothing methods for certified robustness against edit distance perturbations in sequence classification tasks. Unlike prior work that uses a fixed deletion rate (e.g., CERT-ED), AdaptDel dynamically adjusts the deletion probability based on input length, and AdaptDel+ further calibrates this adaptively via binning and empirical optimization. The authors provide a theoretical framework to support edit-distance certification with input-dependent deletion rates and demonstrate empirical improvements over existing baselines on several NLP datasets.", "questions": "- How computationally intensive is the AdaptDel+ calibration process, especially in scenarios with many bins or limited training data?\n- Could the proposed approach be extended to certify robustness under general edit operations, including insertions and substitutions?\n- Given the difficulty of interpreting the derived bounds, can the authors provide more intuition or visualization for how the adaptive deletion affects robustness?", "limitations": "yes", "rating": 4, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 2, "significance": 3, "originality": 2, "strengths_and_weaknesses": "The paper extends deletion-based randomized smoothing by introducing input-dependent deletion rates, enabling more flexible certification against edit-distance perturbations. The proposed methods, AdaptDel and AdaptDel+, are supported by new theoretical bounds and demonstrate improved certified robustness compared to prior baselines, such as CERT-ED and RanMASK, across several NLP tasks. The knapsack-based formulation and calibration strategy in AdaptDel+ are technically sound and contribute to improvements in robustness, especially for longer sequences.\n\nHowever, the method is a relatively straightforward extension of CERT-ED and remains limited to perturbations that only involve deletion. The theoretical analysis, while correct, is dense and challenging to interpret, lacking an intuitive explanation. AdaptDel+ introduces additional complexity through its calibration process, yet the paper provides limited discussion on its computational cost or reproducibility. Overall, the novelty and clarity are limited, and the scope is narrow.", "was_revised": true, "final_justification": "- Rebuttal clarified theoretical design and empirical behavior of adaptive deletion.\n- The explanation of how input-dependent smoothing improves certified robustness added important context.\n- Deletion-only smoothing remains a core limitation affecting generality.\n- I raise my score to 4, reflecting a more complete understanding of the method's contribution.", "rebuttal": "We thank the reviewer for their thoughtful feedback and constructive criticism. We appreciate the recognition of our work's technical merits and the improvements in certified robustness demonstrated by our methods. \n\n> Overall, the novelty and clarity are limited, and the scope is narrow. \n\nWe appreciate the reviewer's perspective. However, we respectfully disagree with this assessment. Our work introduces a novel approach to input-dependent randomized smoothing for discrete sequences, which has not been explored in previous literature. We extend the theoretical framework for randomized smoothing to variable-rate deletion, ensuring sound certification with respect to edit distance. This contribution is both novel and significant in the field of certified robustness. \n\nRegarding clarity, we would appreciate specific feedback on which aspects of the paper were unclear, so we can improve the presentation in the final version. As for the scope, our work addresses a fundamental challenge in NLP robustness, applicable to a wide range of sequence classification tasks. We believe this scope is sufficiently broad and impactful. \n\n> AdaptDel+ introduces additional complexity through its calibration process, yet the paper provides limited discussion on its computational cost or reproducibility. \n\n> How computationally intensive is the AdaptDel+ calibration process, especially in scenarios with many bins or limited training data? \n\nWe thank the reviewer for highlighting this aspect.  \n\nRegarding computational cost: We acknowledge that our submission did not include information about the computational cost of the AdaptDel+ calibration process. Here are the calibration times for each dataset: \n \n\n| Dataset | Calibration time (HH:MM) | \n|:---|---:| \n| Yelp | 09:34 | \n| SpamAssassin | 08:02 | \n| IMDB | 12:10 | \n| LUN | 12:06 | \n\n \n\nWe note that the calibration process (Algorithm 5) has an asymptotic running time that is linear in the number of bins $n$ and sample size per bin $m$. It is done offline (following training) and does not contribute to online certification time. We will include these details in the final version of the paper. \n\nConcerning reproducibility: The process is fully detailed in pseudocode in Appendix C, including Algorithm 5. We report the parameter settings used in Appendix D.3 and provide code in the supplementary material. If there are specific aspects of reproducibility that the reviewer finds lacking, we would appreciate more detailed feedback to address these concerns. \n\n> the method is a relatively straightforward extension of CERT-ED and remains limited to perturbations that only involve deletion. \n\n> Could the proposed approach be extended to certify robustness under general edit operations, including insertions and substitutions? \n\nWe appreciate the opportunity to clarify a potential misunderstanding. Our method is not limited to certifying deletion-only perturbations. Instead, it provides robustness guarantees against the generalized edit distance, where the set of edit operations $\\mathsf{o}$ can be any subset of insertions, substitutions, and deletions. This is stated in Section 2, though we removed a more explicit paragraph to fit within the page limit – we will reinstate this in the final version. \n\nBy contrast, our smoothing mechanism does employ deletion operations only. This decoupling of the smoothing mechanism from the certified threat model is a key feature of our approach, though it's not a new concept [LJG21, LF21]. The critical requirement is that the smoothing distribution produces statistically similar outputs for inputs that are close in edit distance, which we achieve using deletion-based smoothing.  \n\nIn our experiments, we focus on certification of (Levenshtein) edit distance, which is supported by our method and CERT-ED (line 243). RanMASK only supports Hamming distance certification (line 246).  \n\n> Given the difficulty of interpreting the derived bounds, can the authors provide more intuition or visualization for how the adaptive deletion affects robustness? \n\nThe key intuition behind our approach is that while higher deletion rates generally improve robustness, they also tend to reduce clean accuracy. However, prior work has observed that longer sequences can tolerate more aggressive deletion without as significant a drop in accuracy. Lemma 3.2 can be used to bound the stability of a smoothed classifier with input-dependent deletion rates. While the bound is complex to express mathematically, it is computationally tractable. This is not uncommon in the certification literature, where bounds often cannot be expressed analytically but must be computed numerically [LYC+19, SKG22]. \n\nOur experiments demonstrate how adaptive deletion impacts robustness. In essence, we can achieve a similar robustness/accuracy trade-off for short sequences while improving performance for longer sequences. This is most clearly illustrated in Fig 2, where we plot certified accuracy grouped by quartile of input size. \n\n**References** \n\n- Liu, H., J. Jia, and N. Z. Gong. \"PointGuard: Provably robust 3D point cloud classification.\" In: CVPR 2021. \n\n- Levine, A. and S. Feizi. \"Improved, deterministic smoothing for L1 certified robustness.\" In: ICML 2021. \n\n- Súkenı́k, P., A. Kuvshinov, and S. Günnemann. \"Intriguing Properties of Input-Dependent Randomized Smoothing.\" In: ICML 2022. \n\n- Lee, G. H., Y. Yuan, S. Chang, and T. Jaakkola. \"Tight certificates of adversarial robustness for randomly smoothed classifiers.\" In: NeurIPS 2019."}, {"review_id": "Utap0mh0e2", "reviewer": "Reviewer_RXHq", "summary": "This paper extend deletion-based randomized smoothing from a fixed token deletion rate to a length adaptive rate. The authors derived a new probabilistic bound for adaptive deletion and proposed two variants AdaptDel (analytical length dependent) and AdaptDel+ (data driven bin calibration). The paper studies an interesting problem about how to model discrete certified robustness problem and make the method adaptive.", "questions": "See above.", "limitations": "Yes.", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 3, "originality": 3, "strengths_and_weaknesses": "- **Motivation**. Different from most prior work in image space, this work studies discrete text data for certified robustness. It is interesting and  well motivated by the real world needs. I feel this is meaningful to the robustness community. Can you provide some explanations with maybe a toy example of why typical continuous RS does not work?\n\n- **Theory**. The theory part is sound with bounds for arbitrary $\\psi(x)$. \n\n(1) The operations o contains three elements del, ins, sub, but section directly jump to del only, can you briefly explain why the other two operations are dropped? \n\n(2) For line 143, how can you make apply($\\bar{x},\\bar{\\epsilon}$)=apply($\\bar{x},\\epsilon^\\star$)? Is there a typo? Do you mean apply($\\bar{x},\\bar{\\epsilon}$)=apply($x,\\epsilon^\\star$)? \n\n(3) Can you explain how you define $\\rho$ intuitively? Also it is not trivial to see the equivalence of lemma 3.1 from lemma4 from [1], can you elaborate a bit?\n\n(4) If I understand correctly, the bound is derived from greedy algorithm of knapsack problem relaxation. Can you explain your bound tightness? It might be helpful to discuss it a bit for future better schedule $\\psi$.\n\n(5) Notation-wise (minor), $m$ is used to define bijection in lemma 3.1 and also define the num of trails in lemma 3.2. \n\n- **Experiments**. The paper performed experiments on 4 diverse datasets and compared with two baselines CERT-ED and RanMASK. The computational cost is also included. \n\n(1) In the LUN setup, AdapDel is not better than CERT-ED at small radius. And when radius is small, the improvement is also marginal in IMDB and SpamAssassin. Can you explain why?\n\n(2) How does AdaptDel behave for extremely short inputs where deletion can harm semantics much?\n\n[1] Huang et al. 2024, RS-Del: Edit Distance Robustness Certificates for Sequence Classifiers via Randomized Deletion", "was_revised": true, "final_justification": "- The authors claimed that the smoothing mechanism uses only deletion and will be more careful in the final version.\n- The authors explained the key difference from lemma 4 in [1].\n- The authors agreed the bound is not tight due to the constraint relaxations. However, I feel more discussion of schedule $\\psi$ is lacking.\n- The authors also explained the experimental results and will include details in the final version.\nOverall, I feel the authors solved most of my concerns and I will recommend a score of 5.", "rebuttal": "Thank you for your thoughtful review and insightful questions. We appreciate your recognition of our work's motivation and theoretical soundness. \n\n> The operations o contains three elements del, ins, sub, but section directly jump to del only, can you briefly explain why the other two operations are dropped? \n\nThank you for highlighting this point. We originally included a more explicit explanation of this distinction, but it was cut due to space constraints. To clarify: the edit operations in Section 2 define the edit distance we _certify_, which in our experiments includes all three operations (Levenshtein distance). Our smoothing mechanism, however, uses only deletion. This decoupling of certification and smoothing operations is a key feature of our approach, allowing us to certify robustness against a broader set of edit operations while using a simpler smoothing mechanism. We will reinstate a more explicit discussion of this in the final version to prevent any misunderstanding. \n\n> For line 143, how can you make $\\mathrm{apply}(\\bar{x}, \\bar{\\epsilon}) = \\mathrm{apply} (\\bar{x}, \\epsilon^\\star)$? Is there a typo? Do you mean $\\mathrm{apply}(\\bar{x}, \\bar{\\epsilon}) = \\mathrm{apply} (x, \\epsilon^\\star)$? \n\nThank you for catching this typo. The correct equation should be $\\mathrm{apply}(\\bar{\\mathbf{x}}, \\bar{\\epsilon})  = \\mathrm{apply} (\\mathbf{x}, \\epsilon)$. \n\n> Can you explain how you define $\\rho$ intuitively? Also it is not trivial to see the equivalence of lemma 3.1 from lemma4 from [1], can you elaborate a bit? \n\nWe define $\\rho(\\psi, \\bar{\\psi})$ purely to make the math more concise. It's a product of ratios of deletion and retention probabilities (line 145), simplifying to 1 when the deletion probability is constant ($\\psi = \\bar{\\psi}$). \n\nRegarding Lemma 3.1, the key differences from Lemma 4 in [1] are: \n\n- We represent deletion edits as Boolean vectors aligned with $\\mathbf{x}$, whereas [1] uses _sets of indices_ into $\\mathbf{x}$ that are _retained_ (i.e., not deleted). \n\n- We use $\\mathcal{E}(\\mathbf{x}, \\mathbf{\\epsilon}^\\star)$ to denote the edits building on $\\mathbf{\\epsilon}^\\star$ (by flipping zeros to ones), whereas [1] uses $2^{\\epsilon^\\star}$ to denote the edits building on $\\epsilon^\\star$ (by removing indices from the set). \n\n- This representation difference explains why the direction of the inequality flips: we consider $\\bar{\\mathbf{\\epsilon}} \\sqsupseteq \\bar{\\mathbf{\\epsilon}}^\\star$, whereas [1] considers $\\bar{\\epsilon} \\subseteq \\bar{\\epsilon}^\\star$. \n\n- The equality relating $s(\\bar{\\mathbf{\\epsilon}}, \\bar{\\mathbf{x}})$ and $s(\\mathbf{\\epsilon}, \\mathbf{x})$ follows from (2), where an input-dependent deletion probability is used in place of the constant deletion probability from [1].  \n\n> If I understand correctly, the bound is derived from greedy algorithm of knapsack problem relaxation. Can you explain your bound tightness? It might be helpful to discuss it a bit for future better schedule $\\psi$. \n\nYou're correct that we use a knapsack problem relaxation. The bound is sound but not tight due to constraint relaxations in the proof of Lemma 3.2 (following eq. 10).  Regarding the design of $\\psi$, we believe it should be tailored based on the specific dataset and base model characteristics. For instance, some datasets may not tolerate as much noise, necessitating a more conservative $\\psi$. \n\n> Notation-wise (minor), $m$ is used to define bijection in lemma 3.1 and also define the num of trails in lemma 3.2. \n\nThanks for spotting this. We’ll use a different symbol in Lemma 3.2 to avoid confusion. \n\n> In the LUN setup, AdapDel is not better than CERT-ED at small radius. And when radius is small, the improvement is also marginal in IMDB and SpamAssassin. Can you explain why? \n\nThis behavior is expected. AdaptDel is configured to match CERT-ED's deletion rate (90%) for short sequences (Fig 3a), which primarily determines the certified radius. We expect (and observe) larger certified radii for longer sequences where AdaptDel's deletion rate increases. We will incorporate this explanation in the final version of the paper. \n\n > How does AdaptDel behave for extremely short inputs where deletion can harm semantics much? \n\nFor short inputs, AdaptDel uses the same deletion rate as CERT-ED, resulting in comparable semantic impact. Our input-dependent approach is motivated by the hypothesis that longer sequences can often tolerate higher deletion rates without significant semantic loss. Our experiments on multiple datasets support this hypothesis, demonstrating the effectiveness of our approach. This empirical validation, alongside our theoretical contributions in deriving certificates for input-dependent deletion, is a core contribution of our work. \n\nAdditionally, AdaptDel's increasing deletion rate with sequence length leads to more uniform post-deletion sequences. This characteristic could benefit the model across all sequence lengths by promoting more stable training and potentially easier learning of robust features, as the model encounters more consistent input lengths."}, {"review_id": "WZBBeqgW1Y", "reviewer": "Reviewer_jfSu", "summary": "This paper focuses on a new method for certifying robustness against edit distance perturbations in sequence classification tasks using randomized smoothing. The intuition is that state-of-the-art (SOTA) solutions use a fixed-rate deletion mechanism, which has been shown to be suboptimal for real-world data where sequence lengths can vary significantly. Instead, they should use input-dependent noise when certifying robustness, as highlighted in previous work for other tasks. Thus, the paper proposes AdaptDel, a method that employs an adaptable deletion rate that dynamically adjusts based on the input length of the sequence. The paper introduces also another variant called AdaptDel+, which further optimizes this rate through input binning and empirical calibration. The experimental evaluation is comprehensive: it  includes four natural language processing datasets and shows that the proposed methods achieve up to a 30 orders of magnitude improvement in the median cardinality of the certified region and up to 50% longer certified radius. The improvements are particularly evident for longer sequences and on datasets with more uniform length variations. Finally, the paper also provides a detailed analysis of the robustness scaling with input size.", "questions": "How do the probabilistic guarantees of the smoothed classifier hold empirically against text attacks? (you can use the methodology used in [B]).\n\n[B] Huang et. al., CERT-ED: Certifiably Robust Text Classification for Edit Distance, in ACL 2024.", "limitations": "yes, the authors have appropriately discussed the limitations of their work throughout the text and in an apposite section in the paper.", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 3, "originality": 3, "strengths_and_weaknesses": "Thank you to the authors for submitting this interesting paper. I find the research direction about improving randomized smoothing and the performance of the smoothed classifiers particularly interesting, especially when methods are based on in prior evidence. I believe the authors have done an excellent job in summarizing their findings in the main body of the paper, while the appendix contains interesting results and proofs that complete the work. Below, I discuss the strengths and weaknesses of this work, and I hope the authors can address my question.\n\n## Strengths\n\nThe intuition of the paper is sound: as highlighted in [A], using input-dependent noise in randomized smoothing may address better the robustness-accuracy tradeoff the smoothed classifiers. The authors extend this intuition to sequence tasks, showing that the same intuition applies.\nThe proposed method is both interesting and useful. It is based on the formal result that allows the algorithm to compute lower and upper bounds on the smoothed class probability for a neighboring input (within the edit distance threat model). They depend only on the smoothed class probability at the original input and the size of the longest common subsequence between the two inputs. This result is then formally proven (in the Appendix) and enables computing a certificate of robustness by exploiting a reduction of the problem of computing lower and upper bounds on the probability to a knapsack problem. Subsequently, the paper introduces a length-based deletion function used in the smoothing procedure that is essential for making the work novel and relevant, since it simulates how the probability of deleting a token varies with sequence length, even though more complex deletion functions could be defined as acknowledged by the authors.\n\nThe experimental evaluation is ok and considers datasets considered in previous work detailing baselines considered in this paper. Compared to previous methods, AdaptDEL achieves a significantly higher certified radius and mean cardinality of the certified region. Moreover, the additional experimental results in the Appendix clearly show the superior performance of AdaptDEL across all datasets and its greater computational efficiency compared to baselines.\nFinally, the related work section is curated and details well the differences between the proposal and close related work.\n\n## Weaknesses\n\nRelated work describing the considered baselines, such as [B], also provides evidence of the empirical robustness of the smoothed classifier. Although this is not fundamental to show, since you have already provided results about the certified radius, it would be useful to show that the probabilistic guarantee also holds empirically by considering some text attacks, as in [B].\n\n[A] Súkeník et. al., Intriguing properties of input-dependent randomized smoothing, in ICML 2022.\n\n[B] Huang et. al., CERT-ED: Certifiably Robust Text Classification for Edit Distance, in ACL 2024.", "was_revised": true, "final_justification": "I fully support the acceptance of this paper, since it is good or excellent in all its parts. The intuition of the paper is sound and novel, since using input-dependent noise to certify robustness with randomized smoothing may address better the robustness-accuracy tradeoff the smoothed classifiers. The authors have extended this intuition to sequence tasks, showing that the same intuition applies.\nThe proposed method to certify robustness is both interesting and useful and all the theoretical results are formally proven. Also the experimental evaluation is good and considers datasets considered in previous work detailing baselines considered in this paper. Compared to previous methods, the proposed method achieves a significantly higher certified radius and mean cardinality of the certified region. Moreover, the additional experimental results in the Appendix clearly show the greater computational efficiency of the proposed method compared to baselines.\n\nThe authors have also responded to the concern raised in my review, even though they did not provide new experimental results. However, the raised concern does not undermine the quality of the work; addressing it would have only strengthened the evidence supporting the proposed method, which is already well supported by the existing results.", "rebuttal": "Thank you for the positive evaluation of our work. We're pleased you found our research direction interesting and our findings well-summarized. We appreciate your recognition of the sound intuition behind our approach and the comprehensive experimental evaluation. \n\nRegarding your question about empirical robustness against text attacks: \n\nWe are familiar with the methodology used in [B] for testing empirical robustness. While we acknowledge the value of such empirical validation, our focus in this work is on provable robustness guarantees through certification. The certified radii we provide ensure that, with high probability, no attack within that radius can change the classifier's prediction. This means that: \n\n- Any attack operating within the certified region would be provably ineffective with high probability. \n\n- For potential attacks outside the certified region, a practical deployment of our method could employ abstention for inputs where robustness cannot be guaranteed. \n\nGiven these strong theoretical guarantees, we believe our current results demonstrate the effectiveness of our approach. This focus on certification without empirical attack testing is the norm for work on certified robustness, although we appreciate the value of empirical research in adversarial ML more broadly."}, {"review_id": "LFz5Jy41MS", "reviewer": "Reviewer_QS5h", "summary": "The addressed topic of this work is certified robustness for deletion-based smoothing mechanism in sequence classification against edit distance perturbations. Particularly, this work extends the fixed deletion rate in previous works to an adaptive deletion rate for discrete sequences. Theoretical guarantees are established and practical algorithms are developed.", "questions": "This work overall is good, and I would like to propose several issues for a discussion.\n\n1.Existing certified defenses give rigorous theoretical guarantees but suffer from limited applicability. For example, while Gaussian noise perturbations are commonly adopted for certified robustness in image classification, such guaranteed robustness is actually insufficient against those adversarial examples. That is, the certified radius under Gaussian noises is typically much smaller than perturbation generated by basic attacks like FGSM. Regarding your deletion-based mechanism, the reviewer is curious whether your algorithm and others can be somehow effective against those more realistic discrete-input attacks (if any). Any discussions or experiments would be appreciated.\n\n2.Missing explanations about the robustness-accuracy trade-off  \nAs elaborated in Sec.4.1, there exists a robustness-accuracy trade-off for the proposed AdapDel and AdapDel+. In Table 4 of Appendix E.2, the clean accuracy of AdapDel and AdapDel+ is generally smaller than the compared methods. The authors are suggested to give a discussion on the reasons behind. Is it due to the intrinsic mechanism of AdapDel/AdapDel+, or the hyper-parameter settings? Could more sophisticated hyper-parameter tuning boost clean accuracy? Achieving competitive or even better clean accuracy is desirable and also further strengthens this work.", "limitations": "Yes.", "rating": 5, "confidence": 2, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 3, "originality": 3, "strengths_and_weaknesses": "Strengths  \n1.Certifications for deletion-based smoothing mechanism on discrete sequences are built.  \n2.There are extensive experiments, including certified robustness, hyper-parameters analysis and computational complexity.\n\nWeakness  \n1.It would be appreciated that discussions or experiments on practical settings, e.g., adversarial examples on discrete inputs, are supplemented.  \n2.Missing explanations about the robustness-accuracy trade-off.  \n\nRefer detailed weaknesses in my questions below.", "was_revised": true, "final_justification": "As I wrote in the initial review, this work is overall good and I just proposed two concerns for a discussion. In the disucssion phase, although the first concern cannot be completely addressed through experiments due to the time limit, I still acknowledge the quality of this work and increase my final rating from 4 to 5.", "rebuttal": "We appreciate the reviewer's thoughtful comments and questions. We'll address each point in turn: \n\n> 1. Practical settings and adversarial examples \n\nWe acknowledge that certified radii, including those in our work, may not always encompass all practical attacks. However, our approach significantly expands the certified region compared to previous methods, particularly for longer sequences. This improvement is crucial as it narrows the gap between theoretical guarantees and practical attack scenarios. \n\nIt's important to note that the edit distance threat model, while not perfect, represents a significant advancement over previous work that only accommodates substitutions (Hamming distance). This allows us to certify robustness against a broader range of perturbations, including insertions and deletions, which are particularly relevant for text data [GR20, LZP+21]. \n\nWe also emphasize that certification isn't solely about defending against adversarial attacks. It's equally important for ensuring model stability under benign noise, which is common in real-world applications. Our method provides strong guarantees for this broader notion of robustness. \n\n> Missing explanation for robustness-accuracy trade-off  \n\nWe appreciate the opportunity to clarify this point. Looking at Table 4, we'd argue that the clean accuracy of AdaptDel and AdaptDel+ is generally on par with CERT-ED, with only slight drops (less than 1-2 percentage points) which may not be statistically significant.  \n\nThe slight variations in clean accuracy could be attributed to several factors: \n\n- Convergence of training/calibration under variable-rate deletion \n\n- The base model's ability to handle variable-rate deletion \n\n-  More aggressive deletion for medium to long sequences potentially affecting their accuracy \n\nWe believe these small trade-offs in clean accuracy are well justified by the significant improvements in certified robustness, particularly for longer sequences. That said, we agree that further improving clean accuracy is desirable. This could potentially be achieved by manually adjusting the deletion rate curve for AdaptDel, or adjusting the certified accuracy threshold $\\tau$ for AdaptDel+. \n\n \n\n**References** \n\n- Garg, S., and G. Ramakrishnan. “BAE: BERT-based adversarial examples for text classification.” In: EMNLP 2020. \n\n- Li, D., Y. Zhang, H. Peng, L. Chen, C. Brockett, M. Sun, and B. Dolan. “Contextualized perturbation for textual adversarial attack.” In: NACL 2021."}]

Author rebuttal:

Meta-review: I thank all authors and reviewers for their work and the helpful discussion.

**Strengths:**

- Multiple reviewers emphasized the utility of making progress on robustness against text-based attacks, moving beyond the image domain.
- In particular, the progress towards certified robustness is appreciated.
- During discussion, it could be clarified that all edits (deletions, insertions, and replacements) are protected against, even though the smoothing itself is performed via deletions only
- The edit distance is (the reviewers agreed after discussion) a relevant threat model in the text domain

**Weaknesses:**

- Multiple reviewers were concerned that empiric experiments against text attacks are missing, validating that the proposed novel smoothing method provides empiric advantages, not only advantages in terms of bounds. In other words, it may be that all bounds are just overly pessimistic and the practical robustness far exceeds the certificate. However, the reviewers agreed during reviewer-AC discussions that these kinds of experiments are not strictly required for this paper to be accepted; and the authors committed to providing the experiments for the camera-ready.
- Multiple reviewers were confused about the fact that only deletions were used and how relevant the threat model is but these concerns could be clarified.

Overall, all weaknesses of the paper could be addressed during discussion and the strengths remain substantial. As such, I wholeheartedly recommend acceptance.
Decision: Accept (poster)