# Run-Off Election: Improved Provable Defense against Data Poisoning Attacks

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

## Key facts

- Cited by 17 papers in the map (data through 14 Oct 2026).
- Placed in Backdoor and data poisoning attacks, one of 12 directions in LLM safety and security.
- Builds on 33 of its 48 references that are in the map.
- First posted on arXiv 5 Feb 2023.

## Placed in

- LLM safety and security / [Backdoor and data poisoning attacks](https://mlsanity.com/safety/backdoor-and-data-poisoning-attacks/)

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

- [Deep Residual Learning for Image Recognition](https://mlsanity.com/paper/1512.03385/) (2015)
- [Unsupervised Representation Learning by Predicting Image Rotations](https://mlsanity.com/paper/1803.07728/) (2018)
- [Certified Adversarial Robustness via Randomized Smoothing](https://mlsanity.com/paper/1902.02918/) (2019)
- [Targeted Backdoor Attacks on Deep Learning Systems Using Data Poisoning](https://mlsanity.com/paper/1712.05526/) (2017)
- [Network In Network](https://mlsanity.com/paper/1312.4400/) (2013)
- [Poison Frogs! Targeted Clean-Label Poisoning Attacks on Neural Networks](https://mlsanity.com/paper/1804.00792/) (2018)
- [On Evaluating Adversarial Robustness](https://mlsanity.com/paper/1902.06705/) (2019)
- [Robust Estimators in High Dimensions without the Computational Intractability](https://mlsanity.com/paper/1604.06443/) (2016)
- [Semidefinite relaxations for certifying robustness to adversarial examples](https://mlsanity.com/paper/1811.01057/) (2018)
- [Randomized Smoothing of All Shapes and Sizes](https://mlsanity.com/paper/2002.08118/) (2020)
- [Agnostic Estimation of Mean and Covariance](https://mlsanity.com/paper/1604.06968/) (2016)
- [Sever: A Robust Meta-Algorithm for Stochastic Optimization](https://mlsanity.com/paper/1803.02815/) (2018)
- [RAB: Provable Robustness Against Backdoor Attacks](https://mlsanity.com/paper/2003.08904/) (2020)
- [Deep Partition Aggregation: Provable Defense against General Poisoning Attacks](https://mlsanity.com/paper/2006.14768/) (2020)
- [Certified Robustness to Label-Flipping Attacks via Randomized Smoothing](https://mlsanity.com/paper/2002.03018/) (2020)
- [Certified Defenses for Adversarial Patches](https://mlsanity.com/paper/2003.06693/) (2020)
- [Intrinsic Certified Robustness of Bagging against Data Poisoning Attacks](https://mlsanity.com/paper/2008.04495/) (2020)
- [Strong Data Augmentation Sanitizes Poisoning and Backdoor Attacks Without an Accuracy Tradeoff](https://mlsanity.com/paper/2011.09527/) (2020)
- [Label Sanitization against Label Flipping Poisoning Attacks](https://mlsanity.com/paper/1803.00992/) (2018)
- [Curse of Dimensionality on Randomized Smoothing for Certifiable Robustness](https://mlsanity.com/paper/2002.03239/) (2020)
- [Improved Certified Defenses against Data Poisoning with (Deterministic) Finite Aggregation](https://mlsanity.com/paper/2202.02628/) (2022)
- [Second-Order Provable Defenses against Adversarial Attacks](https://mlsanity.com/paper/2006.00731/) (2020)
- [Data Augmentation for Meta-Learning](https://mlsanity.com/paper/2010.07092/) (2020)
- [Random Smoothing Might be Unable to Certify ℓ_∞ Robustness for High-Dimensional Images](https://mlsanity.com/paper/2002.03517/) (2020)
- [MaxUp: A Simple Way to Improve Generalization of Neural Network Training](https://mlsanity.com/paper/2002.09024/) (2020)
- [Robustly-reliable learners under poisoning attacks](https://mlsanity.com/paper/2203.04160/) (2022)
- [On Collective Robustness of Bagging Against Data Poisoning](https://mlsanity.com/paper/2205.13176/) (2022)
- [Robust learning under clean-label attack](https://mlsanity.com/paper/2103.00671/) (2021)
- [On Optimal Learning Under Targeted Data Poisoning](https://mlsanity.com/paper/2210.02713/) (2022)
- [Learning and Certification under Instance-targeted Poisoning](https://mlsanity.com/paper/2105.08709/) (2021)

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

- [Certifiably Robust RAG against Retrieval Corruption](https://mlsanity.com/paper/2405.15556/) (2024)
- [Certified Robustness to Data Poisoning in Gradient-Based Training](https://mlsanity.com/paper/2406.05670/) (2024)
- [Temporal Robustness against Data Poisoning](https://mlsanity.com/paper/2302.03684/) (2023)
- [Provable Robustness of (Graph) Neural Networks Against Data Poisoning and Backdoor Attacks](https://mlsanity.com/paper/2407.10867/) (2024)
- [Provably Reliable Conformal Prediction Sets in the Presence of Data Poisoning](https://mlsanity.com/paper/2410.09878/) (2024)
- [Cert-SSBD: Certified Backdoor Defense with Sample-Specific Smoothing Noises](https://mlsanity.com/paper/2504.21730/) (2025)
- [Exact Certification of Data-Poisoning Attacks Using Mixed-Integer Programming](https://mlsanity.com/paper/2602.16944/) (2026)
- [FCert: Certifiably Robust Few-Shot Classification in the Era of Foundation Models](https://mlsanity.com/paper/2404.08631/) (2024)
- [UTrace: Poisoning Forensics for Private Collaborative Learning](https://mlsanity.com/paper/2409.15126/) (2024)
- [On Practical Aspects of Aggregation Defenses against Data Poisoning Attacks](https://mlsanity.com/paper/2306.16415/) (2023)
- [Certified Robustness to Clean-Label Poisoning Using Diffusion Denoising](https://mlsanity.com/paper/2403.11981/) (2024)
- [Prompting the Unseen: Detecting Hidden Backdoors in Black-Box Models](https://mlsanity.com/paper/2411.09540/) (2024)
- [Trust Under Siege: Label Spoofing Attacks against Machine Learning for Android Malware Detection](https://mlsanity.com/paper/2503.11841/) (2025)
- [Towards Poisoning Robustness Certification for Natural Language Generation](https://mlsanity.com/paper/2602.09757/) (2026)
- [Robustness Certificates for Neural Networks Against Data Poisoning and Evasion Attacks](https://mlsanity.com/paper/2512.20865/) (2025)
- [Exact Certification of Neural Networks and Partition Aggregation Ensembles against Label Poisoning](https://mlsanity.com/paper/2604.11416/) (2026)
- [Soft Specialists: α-R'enyi Ensembles for Uncertainty-Aware LLM Post-Training](https://mlsanity.com/paper/2605.27747/) (2026)

## Abstract (arXiv)

In data poisoning attacks, an adversary tries to change a model's prediction by adding, modifying, or removing samples in the training data. Recently, ensemble-based approaches for obtaining provable defenses against data poisoning have been proposed where predictions are done by taking a majority vote across multiple base models. In this work, we show that merely considering the majority vote in ensemble defenses is wasteful as it does not effectively utilize available information in the logits layers of the base models. Instead, we propose Run-Off Election (ROE), a novel aggregation method based on a two-round election across the base models: In the first round, models vote for their preferred class and then a second, Run-Off election is held between the top two classes in the first round. Based on this approach, we propose DPA+ROE and FA+ROE defense methods based on Deep Partition Aggregation (DPA) and Finite Aggregation (FA) approaches from prior work. We evaluate our methods on MNIST, CIFAR-10, and GTSRB and obtain improvements in certified accuracy by up to 3%-4%. Also, by applying ROE on a boosted version of DPA, we gain improvements around 12%-27% comparing to the current state-of-the-art, establishing a new state-of-the-art in (pointwise) certified robustness against data poisoning. In many cases, our approach outperforms the state-of-the-art, even when using 32 times less computational power.