# PatchDEMUX: A Certifiably Robust Framework for Multi-label Classifiers Against Adversarial Patches

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

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- Builds on 27 of its 39 references that are in the map.
- First posted on arXiv 30 May 2025.

## Builds on (most cited first, 27 of 27)

- [An Image is Worth 16x16 Words: Transformers for Image Recognition at Scale](https://mlsanity.com/paper/2010.11929/) (2020)
- [Microsoft COCO: Common Objects in Context](https://mlsanity.com/paper/1405.0312/) (2014)
- [Towards Deep Learning Models Resistant to Adversarial Attacks](https://mlsanity.com/paper/1706.06083/) (2017)
- [Improved Regularization of Convolutional Neural Networks with Cutout](https://mlsanity.com/paper/1708.04552/) (2017)
- [Certified Adversarial Robustness via Randomized Smoothing](https://mlsanity.com/paper/1902.02918/) (2019)
- [Adversarial Examples Are Not Easily Detected: Bypassing Ten Detection Methods](https://mlsanity.com/paper/1705.07263/) (2017)
- [Adversarial Patch](https://mlsanity.com/paper/1712.09665/) (2017)
- [A Survey of Convolutional Neural Networks: Analysis, Applications, and Prospects](https://mlsanity.com/paper/2004.02806/) (2020)
- [Asymmetric Loss For Multi-Label Classification](https://mlsanity.com/paper/2009.14119/) (2020)
- [Query2Label: A Simple Transformer Way to Multi-Label Classification](https://mlsanity.com/paper/2107.10834/) (2021)
- [(De)Randomized Smoothing for Certifiable Defense against Patch Attacks](https://mlsanity.com/paper/2002.10733/) (2020)
- [Local Gradients Smoothing: Defense against localized adversarial attacks](https://mlsanity.com/paper/1807.01216/) (2018)
- [ML-Decoder: Scalable and Versatile Classification Head](https://mlsanity.com/paper/2111.12933/) (2021)
- [PatchCleanser: Certifiably Robust Defense against Adversarial Patches for Any Image Classifier](https://mlsanity.com/paper/2108.09135/) (2021)
- [Evaluating the Robustness of Semantic Segmentation for Autonomous Driving against Real-World Adversarial Patch Attacks](https://mlsanity.com/paper/2108.06179/) (2021)
- [PatchGuard++: Efficient Provable Attack Detection against Adversarial Patches](https://mlsanity.com/paper/2104.12609/) (2021)
- [Efficient Certified Defenses Against Patch Attacks on Image Classifiers](https://mlsanity.com/paper/2102.04154/) (2021)
- [ObjectSeeker: Certifiably Robust Object Detection against Patch Hiding Attacks via Patch-agnostic Masking](https://mlsanity.com/paper/2202.01811/) (2022)
- [Certified Defences Against Adversarial Patch Attacks on Semantic Segmentation](https://mlsanity.com/paper/2209.05980/) (2022)
- [GAMA: Generative Adversarial Multi-Object Scene Attacks](https://mlsanity.com/paper/2209.09502/) (2022)
- [Action-slot: Visual Action-centric Representations for Multi-label Atomic Activity Recognition in Traffic Scenes](https://mlsanity.com/paper/2311.17948/) (2023)
- [PatchCURE: Improving Certifiable Robustness, Model Utility, and Computation Efficiency of Adversarial Patch Defenses](https://mlsanity.com/paper/2310.13076/) (2023)
- [Domain Knowledge Alleviates Adversarial Attacks in Multi-Label Classifiers](https://mlsanity.com/paper/2006.03833/) (2020)
- [MultiGuard: Provably Robust Multi-label Classification against Adversarial Examples](https://mlsanity.com/paper/2210.01111/) (2022)
- [Open Vocabulary Multi-Label Classification with Dual-Modal Decoder on Aligned Visual-Textual Features](https://mlsanity.com/paper/2208.09562/) (2022)
- [Revisiting Image Classifier Training for Improved Certified Robust Defense against Adversarial Patches](https://mlsanity.com/paper/2306.12610/) (2023)
- [Leveraging Local Patch Differences in Multi-Object Scenes for Generative Adversarial Attacks](https://mlsanity.com/paper/2209.09883/) (2022)

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

- [CertVLA: Certified Defense against Physical Visual Attacks for Vision-Language-Action Models](https://mlsanity.com/paper/2608.20791/) (2026)

## Abstract (arXiv)

Deep learning techniques have enabled vast improvements in computer vision technologies. Nevertheless, these models are vulnerable to adversarial patch attacks which catastrophically impair performance. The physically realizable nature of these attacks calls for certifiable defenses, which feature provable guarantees on robustness. While certifiable defenses have been successfully applied to single-label classification, limited work has been done for multi-label classification. In this work, we present PatchDEMUX, a certifiably robust framework for multi-label classifiers against adversarial patches. Our approach is a generalizable method which can extend any existing certifiable defense for single-label classification; this is done by considering the multi-label classification task as a series of isolated binary classification problems to provably guarantee robustness. Furthermore, in the scenario where an attacker is limited to a single patch we propose an additional certification procedure that can provide tighter robustness bounds. Using the current state-of-the-art (SOTA) single-label certifiable defense PatchCleanser as a backbone, we find that PatchDEMUX can achieve non-trivial robustness on the MS-COCO and PASCAL VOC datasets while maintaining high clean performance