Introduction
Most adversarial research in Natural Language Processing (NLP) has focused on classification tasks, such as sentiment analysis. In these scenarios, small perturbations to a sentence typically do not alter the ground-truth label. However, structured prediction tasks—such as Part-of-Speech (POS) tagging and dependency parsing—are significantly more sensitive to minor changes.
Researchers have identified a "sensitivity gap": while 80% of small perturbations in classification tasks maintain the original label, only 20% do so in structured prediction. This makes generating "imperceptible" adversarial attacks exceptionally difficult, as word substitutions often inadvertently change the correct grammatical structure, rendering the attack invalid. To address this, the SHARP (SearcH-based adversarial Attack for stRuctured Prediction) framework treats the attack as a search-based optimization problem.
The SHARP Framework
SHARP formulates the black-box attack by seeking a perturbed sentence $x$ that maximizes a multi-objective function $F(x)$, balancing three critical pillars:
- Attacking Effectiveness: Since the ground truth for a modified sentence is unknown, SHARP utilizes two external "reference models." An attack is deemed successful if it causes the victim model to disagree with these reference models.
- Fluency: Using perplexity scores from a pretrained language model (e.g., RoBERTa), SHARP ensures the adversarial sentence remains natural-sounding.
- Meaning Preservation: BERTScore is employed to verify that the adversarial sentence conveys the same core semantic meaning as the original source.
Hybrid Search (HS)
To navigate the vast "sentence space," SHARP introduces a Hybrid Search strategy. Traditional beam search often gets trapped in local optima, while Metropolis-Hastings sampling is exploratory but inefficient. SHARP combines these approaches, starting with high exploration to identify promising regions and gradually transitioning to beam search for fine-tuning the final perturbation.
Key Insights: The Reference Model Strategy
A major challenge in attacking structured prediction is the lack of ground truth for synthetic sentences. SHARP solves this by using the agreement between two independent, high-performing reference models as a proxy for truth. The researchers found that using diverse reference models—measured by a metric called Opposite Intersection over Union (OIoU)—leads to more potent attacks because they are less likely to share the same inherent biases or errors.
Experimental Results
The framework was evaluated using the Penn Treebank (PTB) 3.0 dataset against two victim models: a Deep Biaffine parser for dependency parsing and a Bi-LSTM-CNN-CRF model for POS tagging.
SHARP significantly outperformed previous state-of-the-art methods:
- Attack Success Rate (ASR): In dependency parsing, SHARP achieved a token-level ASR of 32.4%, a massive increase over the 5.6% achieved by prior methods. At the sentence level, it successfully fooled the model in 100% of test cases where reference models agreed.
- Human Evaluation: Judges rated SHARP-generated sentences as more fluent and better at preserving meaning than those produced by baseline methods.
- Robustness: The study demonstrated that adversarial training—incorporating SHARP-generated examples into the training set—improved the victim model's accuracy and resilience against future attacks.
Conclusion and Future Work
While SHARP is computationally more intensive than simple substitution methods due to its iterative search and multiple model inferences, it represents a significant leap in attacking complex NLP structures. Future research may expand beyond word-level replacements to include phrase-level reordering and paraphrasing, further testing the boundaries of structured prediction robustness.
Summary updated