# Scalable and Precise Patch Robustness Certification for Deep Learning Models with Top-k Predictions

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

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 23 of its 37 references that are in the map.
- First posted on arXiv 31 Jul 2025.

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

- [An Image is Worth 16x16 Words: Transformers for Image Recognition at Scale](https://mlsanity.com/paper/2010.11929/) (2020)
- [Intriguing properties of neural networks](https://mlsanity.com/paper/1312.6199/) (2013)
- [Adversarial Patch](https://mlsanity.com/paper/1712.09665/) (2017)
- [Certified Defenses for Adversarial Patches](https://mlsanity.com/paper/2003.06693/) (2020)
- [(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)
- [PatchCleanser: Certifiably Robust Defense against Adversarial Patches for Any Image Classifier](https://mlsanity.com/paper/2108.09135/) (2021)
- [Certified Robustness for Top-k Predictions against Adversarial Perturbations via Randomized Smoothing](https://mlsanity.com/paper/1912.09899/) (2019)
- [Smooth Loss Functions for Deep Top-k Classification](https://mlsanity.com/paper/1802.07595/) (2018)
- [Certified Patch Robustness via Smoothed Vision Transformers](https://mlsanity.com/paper/2110.07719/) (2021)
- [Towards Practical Certifiable Patch Defense with Vision Transformer](https://mlsanity.com/paper/2203.08519/) (2022)
- [Minority Reports Defense: Defending Against Adversarial Patches](https://mlsanity.com/paper/2004.13799/) (2020)
- [Investigating Top-k White-Box and Transferable Black-box Attack](https://mlsanity.com/paper/2204.00089/) (2022)
- [Efficient Certified Defenses Against Patch Attacks on Image Classifiers](https://mlsanity.com/paper/2102.04154/) (2021)
- [Differentiable Top-k Classification Learning](https://mlsanity.com/paper/2206.07290/) (2022)
- [Almost Tight L0-norm Certified Robustness of Top-k Predictions against Adversarial Perturbations](https://mlsanity.com/paper/2011.07633/) (2020)
- [PatchCensor: Patch Robustness Certification for Transformers via Exhaustive Testing](https://mlsanity.com/paper/2111.10481/) (2021)
- [PatchCURE: Improving Certifiable Robustness, Model Utility, and Computation Efficiency of Adversarial Patch Defenses](https://mlsanity.com/paper/2310.13076/) (2023)
- [Geometry-Inspired Top-k Adversarial Perturbations](https://mlsanity.com/paper/2006.15669/) (2020)
- [Revisiting Image Classifier Training for Improved Certified Robust Defense against Adversarial Patches](https://mlsanity.com/paper/2306.12610/) (2023)
- [FinGAT: Financial Graph Attention Networks for Recommending Top-K Profitable Stocks](https://mlsanity.com/paper/2106.10159/) (2021)
- [CrossCert: A Cross-Checking Detection Approach to Patch Robustness Certification for Deep Learning Models](https://mlsanity.com/paper/2405.07668/) (2024)
- [A Majority Invariant Approach to Patch Robustness Certification for Deep Learning Models](https://mlsanity.com/paper/2308.00452/) (2023)

## Abstract (arXiv)

Patch robustness certification is an emerging verification approach for defending against adversarial patch attacks with provable guarantees for deep learning systems. Certified recovery techniques guarantee the prediction of the sole true label of a certified sample. However, existing techniques, if applicable to top-k predictions, commonly conduct pairwise comparisons on those votes between labels, failing to certify the sole true label within the top k prediction labels precisely due to the inflation on the number of votes controlled by the attacker (i.e., attack budget); yet enumerating all combinations of vote allocation suffers from the combinatorial explosion problem. We propose CostCert, a novel, scalable, and precise voting-based certified recovery defender. CostCert verifies the true label of a sample within the top k predictions without pairwise comparisons and combinatorial explosion through a novel design: whether the attack budget on the sample is infeasible to cover the smallest total additional votes on top of the votes uncontrollable by the attacker to exclude the true labels from the top k prediction labels. Experiments show that CostCert significantly outperforms the current state-of-the-art defender PatchGuard, such as retaining up to 57.3% in certified accuracy when the patch size is 96, whereas PatchGuard has already dropped to zero.