# Towards Poisoning Robustness Certification for Natural Language Generation

arXiv: https://arxiv.org/abs/2602.09757 · HTML: https://mlsanity.com/paper/2602.09757/

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- Builds on 40 of its 45 references that are in the map.
- First posted on arXiv 10 Feb 2026.

## Builds on (most cited first, 30 of 40)

- [Learning Transferable Visual Models From Natural Language Supervision](https://mlsanity.com/paper/2103.00020/) (2021)
- [Exploring the Limits of Transfer Learning with a Unified Text-to-Text Transformer](https://mlsanity.com/paper/1910.10683/) (2019)
- [LoRA: Low-Rank Adaptation of Large Language Models](https://mlsanity.com/paper/2106.09685/) (2021)
- [Retrieval-Augmented Generation for Knowledge-Intensive NLP Tasks](https://mlsanity.com/paper/2005.11401/) (2020)
- [Direct Preference Optimization: Your Language Model is Secretly a Reward Model](https://mlsanity.com/paper/2305.18290/) (2023)
- [Parameter-Efficient Transfer Learning for NLP](https://mlsanity.com/paper/1902.00751/) (2019)
- [Deep reinforcement learning from human preferences](https://mlsanity.com/paper/1706.03741/) (2017)
- [Training a Helpful and Harmless Assistant with Reinforcement Learning from Human Feedback](https://mlsanity.com/paper/2204.05862/) (2022)
- [Universal and Transferable Adversarial Attacks on Aligned Language Models](https://mlsanity.com/paper/2307.15043/) (2023)
- [Convex optimization](https://mlsanity.com/paper/2106.01946/) (2021)
- [Qwen2 Technical Report](https://mlsanity.com/paper/2407.10671/) (2024)
- [Gemma 2: Improving Open Language Models at a Practical Size](https://mlsanity.com/paper/2408.00118/) (2024)
- [Jailbroken: How Does LLM Safety Training Fail?](https://mlsanity.com/paper/2307.02483/) (2023)
- [Revisiting Unreasonable Effectiveness of Data in Deep Learning Era](https://mlsanity.com/paper/1707.02968/) (2017)
- [Red Teaming Language Models to Reduce Harms: Methods, Scaling Behaviors, and Lessons Learned](https://mlsanity.com/paper/2209.07858/) (2022)
- [OLMo: Accelerating the Science of Language Models](https://mlsanity.com/paper/2402.00838/) (2024)
- [Poisoning Web-Scale Training Datasets is Practical](https://mlsanity.com/paper/2302.10149/) (2023)
- [Model Context Protocol (MCP): Landscape, Security Threats, and Future Research Directions](https://mlsanity.com/paper/2503.23278/) (2025)
- [SecAlign: Defending Against Prompt Injection with Preference Optimization](https://mlsanity.com/paper/2410.05451/) (2024)
- [Witches' Brew: Industrial Scale Data Poisoning via Gradient Matching](https://mlsanity.com/paper/2009.02276/) (2020)
- [Poisoning and Backdooring Contrastive Learning](https://mlsanity.com/paper/2106.09667/) (2021)
- [Certifiably Robust RAG against Retrieval Corruption](https://mlsanity.com/paper/2405.15556/) (2024)
- [Universal Jailbreak Backdoors from Poisoned Human Feedback](https://mlsanity.com/paper/2311.14455/) (2023)
- [Deep Partition Aggregation: Provable Defense against General Poisoning Attacks](https://mlsanity.com/paper/2006.14768/) (2020)
- [Instructions as Backdoors: Backdoor Vulnerabilities of Instruction Tuning for Large Language Models](https://mlsanity.com/paper/2305.14710/) (2023)
- [Attention Tracker: Detecting Prompt Injection Attacks in LLMs](https://mlsanity.com/paper/2411.00348/) (2024)
- [Nightshade: Prompt-Specific Poisoning Attacks on Text-to-Image Generative Models](https://mlsanity.com/paper/2310.13828/) (2023)
- [Instruction Backdoor Attacks Against Customized LLMs](https://mlsanity.com/paper/2402.09179/) (2024)
- [PoisonBench: Assessing Large Language Model Vulnerability to Data Poisoning](https://mlsanity.com/paper/2410.08811/) (2024)
- [Defending Against Prompt Injection With a Few DefensiveTokens](https://mlsanity.com/paper/2507.07974/) (2025)

## Built on by (most cited first, 1 of 1)

- [Inference-Time Consensus for Mitigating Hidden Behaviors from LLM Fine-Tuning](https://mlsanity.com/paper/2607.23394/) (2026)

## Abstract (arXiv)

Understanding the reliability of natural language generation is critical for deploying foundation models in security-sensitive domains. While certified poisoning defenses provide provable robustness bounds for classification tasks, they are fundamentally ill-equipped for autoregressive generation: they cannot handle sequential predictions or the exponentially large output space of language models. To establish a framework for certified natural language generation, we formalize two security properties: stability (robustness to any change in generation) and validity (robustness to targeted, harmful changes in generation). We introduce Targeted Partition Aggregation (TPA), the first algorithm to certify validity/targeted attacks by computing the minimum poisoning budget needed to induce a specific harmful class, token, or phrase. Further, we extend TPA to provide tighter guarantees for multi-turn generations using mixed integer linear programming (MILP). Empirically, we demonstrate TPA's effectiveness across diverse settings including: certifying validity of agent tool-calling when adversaries modify up to 0.5% of the dataset and certifying 8-token stability horizons in preference-based alignment. Though inference-time latency remains an open challenge, our contributions enable certified deployment of language models in security-critical applications.