Towards Poisoning Robustness Certification for Natural Language Generation
Not on the map. Why?
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.
Key facts. Cited by 1 paper in the map (data through 7 Oct 2026). Builds on 40 of its 45 references that are in the map. First posted on arXiv 10 Feb 2026.
Builds on
40 of 45 references.
References · 40
- 2021Learning Transferable Visual Models From Natural Language Supervisioncited by 33,456
- 2019Exploring the Limits of Transfer Learning with a Unified Text-to-Text Transformercited by 14,491
- 2021LoRA: Low-Rank Adaptation of Large Language Modelscited by 14,084
- 2020Retrieval-Augmented Generation for Knowledge-Intensive NLP Taskscited by 9,160
- 2023Direct Preference Optimization: Your Language Model is Secretly a Reward Modelcited by 7,916
- 2019Parameter-Efficient Transfer Learning for NLPcited by 4,195
- 2017Deep reinforcement learning from human preferencescited by 3,846
- 2022Training a Helpful and Harmless Assistant with Reinforcement Learning from Human Feedbackcited by 3,634
- 2023Universal and Transferable Adversarial Attacks on Aligned Language Modelscited by 2,914
- 2021Convex optimizationcited by 2,479
- 2024Qwen2 Technical Reportcited by 2,076
- 2024Gemma 2: Improving Open Language Models at a Practical Sizecited by 1,928
28 more
- 2023Jailbroken: How Does LLM Safety Training Fail?cited by 1,565
- 2017Revisiting Unreasonable Effectiveness of Data in Deep Learning Eracited by 916
- 2022Red Teaming Language Models to Reduce Harms: Methods, Scaling Behaviors, and Lessons Learnedcited by 702
- 2024OLMo: Accelerating the Science of Language Modelscited by 599
- 2023Poisoning Web-Scale Training Datasets is Practicalcited by 276
- 2025Model Context Protocol (MCP): Landscape, Security Threats, and Future Research Directionscited by 257
- 2024SecAlign: Defending Against Prompt Injection with Preference Optimizationcited by 179
- 2020Witches' Brew: Industrial Scale Data Poisoning via Gradient Matchingcited by 156
- 2021Poisoning and Backdooring Contrastive Learningcited by 149
- 2024Certifiably Robust RAG against Retrieval Corruptioncited by 144
- 2023Universal Jailbreak Backdoors from Poisoned Human Feedbackcited by 120
- 2020Deep Partition Aggregation: Provable Defense against General Poisoning Attackscited by 112
- 2023Instructions as Backdoors: Backdoor Vulnerabilities of Instruction Tuning for Large Language Modelscited by 100
- 2024Attention Tracker: Detecting Prompt Injection Attacks in LLMscited by 82
- 2023Nightshade: Prompt-Specific Poisoning Attacks on Text-to-Image Generative Modelscited by 72
- 2024Instruction Backdoor Attacks Against Customized LLMscited by 50
- 2024PoisonBench: Assessing Large Language Model Vulnerability to Data Poisoningcited by 31
- 2025Defending Against Prompt Injection With a Few DefensiveTokenscited by 26
- 2024Here's a Free Lunch: Sanitizing Backdoored Models with Model Mergecited by 21
- 2024Certified Robustness to Data Poisoning in Gradient-Based Trainingcited by 17
- 2022On Collective Robustness of Bagging Against Data Poisoningcited by 16
- 2023Run-Off Election: Improved Provable Defense against Data Poisoning Attackscited by 16
- 2024Defending Against Weight-Poisoning Backdoor Attacks for Parameter-Efficient Fine-Tuningcited by 16
- 2023TextGuard: Provable Defense against Backdoor Attacks on Text Classificationcited by 14
- 2025Abstract Gradient Training: A Unified Certification Framework for Data Poisoning, Unlearning, and Differential Privacycited by 6
- 2024FCert: Certifiably Robust Few-Shot Classification in the Era of Foundation Modelscited by 3
- 2025Keeping up with dynamic attackers: Certifying robustness to adaptive online data poisoningcited by 3
- 2025Certifying Language Model Robustness with Fuzzed Randomized Smoothing: An Efficient Defense Against Backdoor Attackscited by 2
Built on by
Citing papers per year: 2026: 1.
1 paper.
Similar, not cited
Close in wording, no citation either way
- 2026Inference-Time Vulnerability Beyond Shallow Safety: Alignment Along Generation Trajectories
- 2025TRIDENT: Enhancing Large Language Model Safety with Tri-Dimensional Diversified Red-Teaming Data Synthesis
- 2025EVALOOOP: A Self-Consistency-Centered Framework for Assessing Large Language Model Robustness in Programming
- 2025Vulnerability Mitigation for Safety-Aligned Language Models via Debiasing
- 2026Trustworthy RAG: An Evaluation Agent for Detecting Misinformation and Knowledge Poisoning in Generative AI Systems
- 2026Can Safety Emerge from Weak Supervision? A Systematic Analysis of Small Language Models
- 2025SafeTuneBed: A Toolkit for Benchmarking LLM Safety Alignment in Fine-Tuning
- 2024The Dark Side of Human Feedback: Poisoning Large Language Models via User Inputs