# Robust Conformal Prediction with a Single Binary Certificate

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

## Key facts

- Cited by 4 papers in the map (data through 14 Oct 2026).
- Builds on 22 of its 30 references that are in the map.
- First posted on arXiv 7 Mar 2025.

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

- [Semi-Supervised Classification with Graph Convolutional Networks](https://mlsanity.com/paper/1609.02907/) (2016)
- [On Calibration of Modern Neural Networks](https://mlsanity.com/paper/1706.04599/) (2017)
- [Certified Adversarial Robustness via Randomized Smoothing](https://mlsanity.com/paper/1902.02918/) (2019)
- [A Gentle Introduction to Conformal Prediction and Distribution-Free Uncertainty Quantification](https://mlsanity.com/paper/2107.07511/) (2021)
- [Conformal Prediction Under Covariate Shift](https://mlsanity.com/paper/1904.06019/) (2019)
- [Classification with Valid and Adaptive Coverage](https://mlsanity.com/paper/2006.02544/) (2020)
- [Conformal prediction beyond exchangeability](https://mlsanity.com/paper/2202.13415/) (2022)
- [Conformal Risk Control](https://mlsanity.com/paper/2208.02814/) (2022)
- [Least Ambiguous Set-Valued Classifiers with Bounded Error Levels](https://mlsanity.com/paper/1609.00451/) (2016)
- [Randomized Smoothing of All Shapes and Sizes](https://mlsanity.com/paper/2002.08118/) (2020)
- [Learning Optimal Conformal Classifiers](https://mlsanity.com/paper/2110.09192/) (2021)
- [Uncertainty Quantification over Graph with Conformalized Graph Neural Networks](https://mlsanity.com/paper/2305.14535/) (2023)
- [Tight Certificates of Adversarial Robustness for Randomly Smoothed Classifiers](https://mlsanity.com/paper/1906.04948/) (2019)
- [Efficient Robustness Certificates for Discrete Data: Sparsity-Aware Randomized Smoothing for Graphs, Images and More](https://mlsanity.com/paper/2008.12952/) (2020)
- [Improved, Deterministic Smoothing for L_1 Certified Robustness](https://mlsanity.com/paper/2103.10834/) (2021)
- [Certifying Confidence via Randomized Smoothing](https://mlsanity.com/paper/2009.08061/) (2020)
- [Conformal Prediction Sets Improve Human Decision Making](https://mlsanity.com/paper/2401.13744/) (2024)
- [Adversarial Training for Graph Neural Networks: Pitfalls, Solutions, and New Directions](https://mlsanity.com/paper/2306.15427/) (2023)
- [Provably Robust Conformal Prediction with Improved Efficiency](https://mlsanity.com/paper/2404.19651/) (2024)
- [Probabilistically robust conformal prediction](https://mlsanity.com/paper/2307.16360/) (2023)
- [Robust Yet Efficient Conformal Prediction Sets](https://mlsanity.com/paper/2407.09165/) (2024)
- [Conformal Inductive Graph Neural Networks](https://mlsanity.com/paper/2407.09173/) (2024)

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

- [Efficient Robust Conformal Prediction via Lipschitz-Bounded Networks](https://mlsanity.com/paper/2506.05434/) (2025)
- [One Sample is Enough to Make Conformal Prediction Robust](https://mlsanity.com/paper/2506.16553/) (2025)
- [Extending Prediction-Powered Inference through Conformal Prediction](https://mlsanity.com/paper/2510.16166/) (2025)
- [Robust Conformal Intrusion Detection via Traffic-Aware Calibration and Attack-Orbit Invariance](https://mlsanity.com/paper/2609.19241/) (2026)

## Abstract (arXiv)

Conformal prediction (CP) converts any model's output to prediction sets with a guarantee to cover the true label with (adjustable) high probability. Robust CP extends this guarantee to worst-case (adversarial) inputs. Existing baselines achieve robustness by bounding randomly smoothed conformity scores. In practice, they need expensive Monte-Carlo (MC) sampling (e.g. ~104 samples per point) to maintain an acceptable set size. We propose a robust conformal prediction that produces smaller sets even with significantly lower MC samples (e.g. 150 for CIFAR10). Our approach binarizes samples with an adjustable (or automatically adjusted) threshold selected to preserve the coverage guarantee. Remarkably, we prove that robustness can be achieved by computing only one binary certificate, unlike previous methods that certify each calibration (or test) point. Thus, our method is faster and returns smaller robust sets. We also eliminate a previous limitation that requires a bounded score function.