Abstract
Deep neural networks in Natural Language Processing (NLP) are vulnerable to adversarial word substitutions that can flip model predictions with minimal semantic changes. We present TextVerifier, a framework that provides certifiable robustness guarantees by "sandwiching" the maximal safe radius between tightening lower and upper bounds. TextVerifier employs an anytime estimation strategy and leverages GPU acceleration to efficiently determine the minimum number of word substitutions required to fool a classifier. Experimental results across multiple datasets and architectures demonstrate that TextVerifier provides tighter bounds and certified safety zones more effectively than existing adversarial attack methods.
Introduction
The fragility of deep neural networks in NLP is well-documented; minor perturbations, such as synonym substitutions, can significantly degrade performance. Identifying the maximum safe radius—the minimum Hamming distance ($L_0$ norm) of word changes required to alter a model's output—is critical for assessing robustness. However, this calculation is NP-hard due to the discrete search space of language and the non-convexity of decision boundaries. Existing verification tools often suffer from high computational costs or produce bounds too loose for practical application.
Methods
TextVerifier addresses these challenges through a multi-stage pipeline optimized for parallel execution on GPUs. The process begins with search space optimization, identifying "qualified" words and generating synonym sets using counter-fitting embeddings to maintain semantic integrity.
The framework utilizes a "Sandwich" approach to bound the safe radius:
- Lower Bound ($l_p$): Establishes a radius within which no adversarial examples exist. If the model is not fooled by any combination of $p$ word changes, the lower bound is $p$.
- Upper Bound ($u_p$): Identifies the smallest discovered adversarial example, serving as a competitive attack mechanism.
As an anytime algorithm, TextVerifier continuously refines these bounds, narrowing the uncertainty interval $[l_t, u_t]$ as computation proceeds. This allows for practical use in time-constrained environments where a "best-so-far" certificate is valuable. A novel parallelization strategy allows the system to process sets of candidate texts simultaneously on GPUs, significantly boosting efficiency compared to sequential search methods.
Results
Evaluation was conducted on four standard benchmarks (MR, AG, IMDB, Yelp) using BERT, CNN, and LSTM architectures.
As shown in the results, TextVerifier consistently achieves tighter upper bounds than state-of-the-art attacks like TextFooler, PWWS, and BERT-Attack. For example, on the MR dataset using a BERT model, TextVerifier reduced the mean upper bound to 1.57, significantly lower than BERT-Attack's 2.23. Furthermore, the system successfully proved lower bounds (safe zones) where no adversarial perturbations are possible, a feat standard adversarial attacks cannot achieve. The parallelization strategy ensures competitive runtimes, making it feasible to verify large batches of text on standard hardware.
Conclusion
TextVerifier offers a robust and efficient solution for verifying NLP classifiers. By providing certifiable bounds through an anytime framework, it bridges the gap between theoretical verification and practical application. While sentence length and synonym library size impact performance, the framework's ability to provide tightening bounds makes it suitable for safety-critical systems. Future research will explore extending these guarantees to character-level perturbations and sentence-level paraphrasing to further enhance model reliability.
Summary updated