AdaptDel: Adaptable Deletion Rate Randomized Smoothing for Certified Robustness

AI summary

Overview

Research area: Certified robustness for sequence classification, specifically randomized smoothing for natural language processing models under edit-distance perturbations (adversarial machine learning / trustworthy NLP).

Technical level: Advanced. The paper derives new concentration bounds for input-dependent deletion smoothing, formulates the bound computation as a bounded knapsack problem, and proves a certification theorem. Familiarity with randomized smoothing, edit distance, and confidence bounds is assumed.

Scope: The paper proposes AdaptDel and AdaptDel+, two deletion-based smoothing mechanisms whose deletion rate adapts to input length (and, for AdaptDel+, to empirically calibrated length bins), together with a sound edit-distance certification framework, evaluated on four text classification datasets using a RoBERTa base model.

What This Paper Is About

Existing certified defenses for sequence classification against edit-distance perturbations delete tokens at a single fixed rate for every input, ignoring that sequences of different lengths tolerate deletion differently — the authors cite the observation of Huang et al. that longer text sequences can typically tolerate higher deletion rates without losing accuracy. This fixed, one-size-fits-all rate forces a suboptimal trade-off between robustness (certified radius) and clean accuracy. The paper's goal is to extend randomized smoothing theory to input-dependent (variable) deletion rates and to show that length-aware deletion rates yield substantially larger certified regions at comparable clean accuracy.

Key Contributions

1. A theoretical foundation for variable-rate deletion smoothing. The authors derive lower and upper bounds on the smoothed class probability at a perturbed input, depending only on the smoothed probability at the original input and the length of the longest common subsequence (LCS) between the two sequences, with no assumption about how the deletion rate depends on the input. The bound is computed by solving a bounded knapsack problem.

2. Two adaptive smoothing methods, AdaptDel and AdaptDel+. AdaptDel uses a deletion rate that increases smoothly with input length, ψ(x) = max(p_lb, p(1 − k/|x|)). AdaptDel+ bins inputs by size into n bins and finds an optimal expected post-deletion length per bin via golden-section search, calibrated empirically on the training set.

3. An efficient certification algorithm for the length-dependent case. When the deletion rate depends on the input only through its length, the bounds depend only on |x|, |x̄|, |z★| and the smoothed probability, allowing Algorithm 1 to enumerate neighbouring sequences by counts of deletions, insertions and substitutions and return the largest certified radius (Theorem 3.4, confidence level at least 1 − α).

4. Empirical validation on four NLP tasks. On Yelp, SpamAssassin, IMDB and LUN, AdaptDel and AdaptDel+ 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 relative to state-of-the-art certifications, with clean accuracy drops of 0–2% compared to RanMASK and CERT-ED.

Main Findings

• Adaptive deletion beats fixed-rate deletion at equal accuracy. AdaptDel and AdaptDel+ yield higher certified accuracy than CERT-ED and RanMASK at the same certified accuracy level, with clean accuracy 0–2% lower than those baselines.

• Large gains in certified-region size. The authors report an average improvement of over 50% in mean certified radius and up to 30 orders of magnitude improvement in median cardinality of the certified region relative to state-of-the-art certifications.

• Gains concentrate on longer sequences. AdaptDel is configured so that its deletion rate matches CERT-ED's fixed rate for a test sequence of average length; consequently, results in the first two length quartiles of Yelp are only moderately better than baselines, while the fourth quartile — where length variation is concentrated — shows substantial certified-accuracy gains. The pattern is similar but more pronounced on SpamAssassin.

• AdaptDel+ is strongest across lengths. AdaptDel+ maintains significantly stronger robustness guarantees across all lengths, which the authors attribute to its empirical calibration strategy.

• Datasets with more uniform length variation benefit most. The improvements are especially pronounced for SpamAssassin and LUN, which the paper describes as containing more uniform length variations.

• Fixed-rate deletion is a special case of the framework. Setting ψ(x) = p_del as a constant recovers CERT-ED; the authors state the Lemma 3.3 bound simplifies approximately to the closed-form solution of Huang et al. under this specialization.

Methodology in Plain English

The method builds on randomized smoothing: instead of predicting with a single model on the raw input, the model classifies many randomly perturbed copies of the input and takes a majority vote. The perturbation used here is random token deletion — each token is independently deleted with some probability, producing a random subsequence. Certified robustness then means showing that no edit-distance perturbation within radius r can flip the majority vote.

The new twist is that the deletion probability is a function of the input rather than a constant. To certify under this setting, the authors compare the smoothed class probability at an input x with that at a neighbour x̄. Using a bijection between deletion patterns (Lemma 3.2), based on a longest common subsequence of x and x̄, they can match up the perturbations that produce identical subsequences and relate their probabilities by simple ratios. Bounding the sum of those matched terms becomes a bounded knapsack problem: different numbers of retained tokens act as item sizes, and the greedy solution fills sizes in order up to a threshold H★.

Because this bound depends only on the smoothed probability, the sequence lengths and the LCS length, the authors restrict the deletion rate to depend on input length alone. Then certification reduces to enumerating possible combinations of deletion, insertion and substitution counts within a radius r, and checking whether the worst-case confidence bound for the top class still beats the best bound for the runner-up. Confidence bounds are Clopper-Pearson bounds estimated with 1000 samples for prediction and 4000 samples for certification, with a Bonferroni correction (α divided by two) and separate sample batches for the top and runner-up classes to avoid dividing α by the number of classes.

AdaptDel's parameters are set to p_lb = p_del, p = 1 and k = floor((1 − p_lb) E{|x|}), so it matches the fixed-rate baseline on average-length test sequences. AdaptDel+ instead bins inputs by size and searches (via golden-section search) for the expected post-deletion length that works best per bin, calibrated on the training data. The base classifier throughout is a pre-trained RoBERTa model, and RanMASK is included as a baseline that certifies only the more limited Hamming distance.

Why This Matters

Research impact. Randomized smoothing for sequences has largely used a single global noise/deletion level. This paper shows that input-dependent rates can be handled rigorously — with a sound certificate rather than an ad hoc test-time correction — and that the payoff in certified-region size is large. It extends prior work on input-dependent Gaussian noise smoothing from real-valued inputs to discrete sequences, where the analysis is more involved because the certificate must hold under edit distance and the smoothing mechanism must be able to change the dimensionality of the input.

Real-world applications.

• Spam filtering, where spammers routinely insert or delete characters and tokens; the SpamAssassin evaluation directly targets this setting.
• Unreliable news and misinformation detection (the LUN dataset), where adversarial text edits attempt to evade a classifier.
• Sentiment analysis on user-generated reviews (Yelp five-class and IMDB), where inputs vary enormously in length and short reviews are easy to over-delete.
• Malware detection, which the paper cites as a domain where fixed-rate deletion smoothing has already proven effective and where input length varies widely.

Industry relevance. Any production text-classification pipeline that must withstand deliberate evasions — content moderation, abuse detection, safety filters — faces the same trade-off between accuracy on normal traffic and guarantees under adversarial editing. Certified robustness provides an auditable guarantee rather than an empirical claim, and adaptive deletion rates deliver that guarantee while costing little clean accuracy (0–2% reported).

Future Directions

• Certifying beyond the top-1 prediction. The authors note that their upper bound (Lemma A.2) is not needed for Cohen-style top-1 certification, but is required for Lecuyer-style certificates or for certification of top-k predictions — leaving top-k certification with adaptive deletion rates as an open path.

• Deletion rates that depend on more than length. The paper states that the full variable-rate analysis makes no assumption about the functional form of ψ, but efficient certification is only derived for the length-dependent case. Rates depending on sequence complexity, domain characteristics, or other input properties, computed via exhaustive search, remain to be explored.

• Other smoothing operators. The authors note that a mechanism incorporating insertions or substitutions could also be designed, and that deletion alone is sufficient to create the statistical overlap needed for certification — leaving room to study such hybrid mechanisms.

• Efficiency of certification. The paper defers details of computational efficiency to Appendix F, and certification here requires enumerating edit-count combinations and drawing 4000 samples per input; scaling this to much larger corpora or longer documents is a natural engineering question.

• Extension beyond text. The introduction frames sequence prediction as fundamental to bioinformatics and time-series analysis as well as NLP, so applying adaptive deletion smoothing to those domains is an unresolved question. The paper's conclusion is not included in the available content, so additional directions the authors may state there are not reported here.

Target Audience

Researchers and practitioners working on certified robustness, adversarial NLP, and trustworthy text classification — particularly those already familiar with randomized smoothing who want to understand how input-dependent noise can be made certifiable for discrete sequences. It is also relevant to security-minded engineers deploying spam, fraud, moderation or malware-detection classifiers that must resist edit-based evasion, and to theoreticians interested in knapsack-style bounding of smoothed probabilities. The mathematical density of Section 3 means non-specialists will find the empirical results (Figures 1 and 2 and the appendix tables) more immediately accessible.

Authors’ 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.