Efficient Certified Robustness Assessment for Transformer Models via Verifier-Aware Perturbation-Position Scheduling

Certified robustness provides guarantees that a model’s prediction is stable within a specified perturbation region, but certified-radius assessment for Transformer text classifiers is computationally expensive because sentence-level certificates require repeated radius searches over multiple perturbation positions. Existing approaches primarily improve the precision or runtime of individual verifier calls, whereas repeated position-level search is an additional source of computational cost. We address this bottleneck with verifier-aware perturbation-position scheduling: selected positions undergo full radius search to obtain a candidate sentence-level radius, skipped positions are validated at that radius, and only failed validations receive fallback search. Thus, scheduling reduces repeated search effort but preserves verifier coverage of all eligible perturbation tasks. Experiments include an expanded 100-example SST-2 evaluation and a 30-example Yelp evaluation, together with one-token and two-token embedding-space perturbations, early-exit verifier cascades, and scheduling ablations, to assess certificate preservation and verification efficiency across different settings. On the expanded SST-2 all-position evaluation, the scheduler reproduces the exhaustive sentence-level radius on all examples, while substantially reduces the number of full radius searches. Additional sensitivity experiments show similar scheduling behavior under the evaluated depth and longer-sequence settings. The presented results suggest that perturbation-position scheduling provides a verifier-compatible way to reduce repeated work in certified robustness assessment. Next research steps should expand the evaluation by addressing large pretrained language models, alternative verification backends, and broader discrete text perturbation settings.