Achieving Model Robustness through Discrete Adversarial Training

Maor Ivgi, Jonathan Berant

TL;DR

This paper demonstrates that online adversarial training—generating new perturbations at every training step—is far more effective for building robust NLP models than the standard "offline" approach. The authors introduce a new, more efficient discrete attack called BFF (Best-First search over a Factorized graph) and reveal the surprising finding that simple random synonym sampling can outperform complex search-based offline methods while being 10x faster.

What Problem Does This Paper Address?

Deep learning models for language are notoriously brittle. A model might correctly classify "Such an amazing movie!" as positive but fail on "Such an extraordinary film!" even though the meaning is identical. These are called discrete adversarial attacks: small, label-preserving changes to text that trigger prediction errors.

While adversarial training (AT) is a standard defense in computer vision, it’s harder in NLP because language is discrete. Most researchers use "offline augmentation," where they generate a set of adversarial examples once and retrain the model. This paper argues that this is sub-optimal because the model doesn't "adapt" to its own evolving vulnerabilities during training. The authors set out to prove that online augmentation (generating attacks on-the-fly) is the key to true robustness.

Methods

The authors propose two main strategies to improve robustness:

  1. BFF (Best-First Search over a Factorized Graph): Most discrete attacks use "greedy search," which is prone to getting stuck in local optima. BFF improves this in two ways:
  2. Factorization: Instead of looking at every possible synonym for every word at once, it first identifies the most "sensitive" word positions and then tries synonyms for those specific spots. This drastically reduces the computational cost per step.
  3. Best-First Search: It uses a priority queue (min-heap) to explore perturbations. If one path looks like a dead end, it can backtrack and try a different branch, as illustrated in the search paths of Figure 3.
  4. Online Augmentation: Instead of a one-and-done dataset expansion, the authors generate new adversarial examples for every batch during training. This ensures the "adversary" is always targeting the current model's specific weaknesses.
  5. Random Sampling Baselines: They also test a surprisingly simple method: just randomly swapping words with synonyms from a dictionary without any fancy search algorithm.
Figure 3: Example of an attack space, and the paths taken by a greedy algorithm and best-first search. An adversarial example has a probability p < 0.5 for the gold positive label.

Datasets

The researchers evaluated their methods on three diverse benchmarks:

  • SST-2: A standard sentiment analysis dataset with short sentences.
  • IMDB: Sentiment analysis on long-form movie reviews, presenting a much larger "attack space."
  • BoolQ: A challenging reading comprehension dataset (Yes/No questions) that requires global understanding of Wikipedia paragraphs.

Key Insights and Ideas

  • The "Online" Advantage: Online training (ADVON) is significantly more robust than offline training (ADVOFF). As shown in Figure 1, adapting to the model's state during training leads to much higher robust accuracy, even if it is computationally expensive.
  • Randomness is a Strong Baseline: One of the most "aha" moments is that RANDOFF (offline random sampling) often outperforms expensive search-based offline methods like TXFOFF (TextFooler). It’s simpler to implement, 10x faster, and provides a more diverse set of examples that prevents the model from over-fitting to a specific attack strategy.
  • Search Strategy Matters: BFF's ability to backtrack allows it to find adversarial examples that greedy searches miss. This makes it a more rigorous "stress test" for evaluating how robust a model actually is.
  • Attack Space Validity: The authors emphasize that many previous attacks produced "adversarial" examples that were actually unreadable or changed the label (e.g., swapping "compelling" for "unconvincing"). They used a stricter, human-validated filtering process to ensure their attacks were truly label-preserving.
Figure 1: Robust accuracy vs. training slowdown. Note how ADVON (yellow) achieves the highest robustness.

Key Results

  • Massive Robustness Gains: On the IMDB dataset, robust accuracy jumped from 41.2% (Baseline) to 78.9% using BFF with online augmentation (BFFON).
  • Efficiency vs. Power: While online search-based training is the most robust, it is slow (20x to 270x slower than baseline). However, RANDOFF-8 (8 random samples) improved IMDB robustness to 60.9% with only an 8x slowdown, making it a highly practical "middle ground."
  • Higher Success Rates: BFF consistently found more adversarial examples than the previous state-of-the-art, TextFooler, especially when given a larger "budget" of model evaluations (see Figure 4).
Figure 4: Attack success rate vs. budget. BFF (blue) continues to improve as the budget increases, while others plateau.

Limitations and Future Work

  • Training Cost: The primary limitation is the massive computational overhead of online search-based training. While it produces the most robust models, the 200x+ slowdown on some datasets makes it difficult to scale to massive models or datasets.
  • Attack Space Constraints: The authors focused on synonym substitution. Future work could explore more complex discrete attacks, such as paraphrasing or structural changes, and how to integrate them into the online training framework.
  • Generalization: While BFFON is robust against many types of attacks (BFF, TextFooler, Genetic), the authors note that the "arms race" between attacks and defenses is ongoing, and no model is perfectly robust against all possible perturbations.

Summary updated

Abstract

Discrete adversarial attacks are symbolic perturbations to a language input that preserve the output label but lead to a prediction error. While such attacks have been extensively explored for the purpose of evaluating model robustness, their utility for improving robustness has been limited to offline augmentation only. Concretely, given a trained model, attacks are used to generate perturbed (adversarial) examples, and the model is re-trained exactly once. In this work, we address this gap and leverage discrete attacks for online augmentation, where adversarial examples are generated at every training step, adapting to the changing nature of the model. We propose (i) a new discrete attack, based on best-first search, and (ii) random sampling attacks that unlike prior work are not based on expensive search-based procedures. Surprisingly, we find that random sampling leads to impressive gains in robustness, outperforming the commonly-used offline augmentation, while leading to a speedup at training time of ~10x. Furthermore, online augmentation with search-based attacks justifies the higher training cost, significantly improving robustness on three datasets. Last, we show that our new attack substantially improves robustness compared to prior methods.
BibTeX
@inproceedings{ivgi2021achieving,
  author = {Maor Ivgi and Jonathan Berant},
  title = {{Achieving Model Robustness through Discrete Adversarial Training}},
  booktitle = {Conference on Empirical Methods in Natural Language Processing},
  year = {2021},
  url = {https://openreview.net/forum?id=mm9aeWfm3Hx},
}
Figure