# Provably Robust Conformal Prediction with Improved Efficiency

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

## Key facts

- Cited by 27 papers in the map (data through 14 Oct 2026).
- Builds on 14 of its 26 references that are in the map.
- First posted on arXiv 30 Apr 2024.

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

- [Deep Residual Learning for Image Recognition](https://mlsanity.com/paper/1512.03385/) (2015)
- [Certified Adversarial Robustness via Randomized Smoothing](https://mlsanity.com/paper/1902.02918/) (2019)
- [Classification with Valid and Adaptive Coverage](https://mlsanity.com/paper/2006.02544/) (2020)
- [Uncertainty Sets for Image Classifiers using Conformal Prediction](https://mlsanity.com/paper/2009.14193/) (2020)
- [Provably Robust Deep Learning via Adversarially Trained Smoothed Classifiers](https://mlsanity.com/paper/1906.04584/) (2019)
- [Least Ambiguous Set-Valued Classifiers with Bounded Error Levels](https://mlsanity.com/paper/1609.00451/) (2016)
- [Fast Differentiable Sorting and Ranking](https://mlsanity.com/paper/2002.08871/) (2020)
- [MACER: Attack-free and Scalable Robust Training via Maximizing Certified Radius](https://mlsanity.com/paper/2001.02378/) (2020)
- [Differentiable Ranks and Sorting using Optimal Transport](https://mlsanity.com/paper/1905.11885/) (2019)
- [Learning Optimal Conformal Classifiers](https://mlsanity.com/paper/2110.09192/) (2021)
- [Practical Adversarial Multivalid Conformal Prediction](https://mlsanity.com/paper/2206.01067/) (2022)
- [Training Uncertainty-Aware Classifiers with Conformalized Deep Learning](https://mlsanity.com/paper/2205.05878/) (2022)
- [Exchangeability, Conformal Prediction, and Rank Tests](https://mlsanity.com/paper/2005.06095/) (2020)
- [Probabilistically robust conformal prediction](https://mlsanity.com/paper/2307.16360/) (2023)

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

- [Robust Yet Efficient Conformal Prediction Sets](https://mlsanity.com/paper/2407.09165/) (2024)
- [Wasserstein-regularized Conformal Prediction under General Distribution Shift](https://mlsanity.com/paper/2501.13430/) (2025)
- [Backward Conformal Prediction](https://mlsanity.com/paper/2505.13732/) (2025)
- [Conformal Prediction under Levy-Prokhorov Distribution Shifts: Robustness to Local and Global Perturbations](https://mlsanity.com/paper/2502.14105/) (2025)
- [Conformal Risk Minimization with Variance Reduction](https://mlsanity.com/paper/2411.01696/) (2024)
- [Verifiably Robust Conformal Prediction](https://mlsanity.com/paper/2405.18942/) (2024)
- [Game-Theoretic Defenses for Robust Conformal Prediction Against Adversarial Attacks in Medical Imaging](https://mlsanity.com/paper/2411.04376/) (2024)
- [Direct Prediction Set Minimization via Bilevel Conformal Classifier Training](https://mlsanity.com/paper/2506.06599/) (2025)
- [Enhancing Adversarial Robustness with Conformal Prediction: A Framework for Guaranteed Model Reliability](https://mlsanity.com/paper/2506.07804/) (2025)
- [Uncertainty-Aware Reward Modeling for Stable RLHF](https://mlsanity.com/paper/2606.19818/) (2026)
- [Provably Reliable Conformal Prediction Sets in the Presence of Data Poisoning](https://mlsanity.com/paper/2410.09878/) (2024)
- [Robust Conformal Prediction with a Single Binary Certificate](https://mlsanity.com/paper/2503.05239/) (2025)
- [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)
- [Generalization and Informativeness of Weighted Conformal Risk Control Under Covariate Shift](https://mlsanity.com/paper/2501.11413/) (2025)
- [Quantifying Uncertainty in Natural Language Explanations of Large Language Models for Question Answering](https://mlsanity.com/paper/2509.15403/) (2025)
- [ConformalShift: Targeted Event Reordering Against Adaptive ECG Monitoring](https://mlsanity.com/paper/2608.03628/) (2026)
- [Quadratic Advantage with Quantum Randomized Smoothing Applied to Time-Series Analysis](https://mlsanity.com/paper/2407.18021/) (2024)
- [CertDW: Towards Certified Dataset Ownership Verification via Conformal Calibration](https://mlsanity.com/paper/2506.13160/) (2025)
- [Smoothing-Based Conformal Prediction for Balancing Efficiency and Interpretability](https://mlsanity.com/paper/2509.22529/) (2025)
- [CoFineLLM: Conformal Finetuning of LLMs for Language-Instructed Robot Planning](https://mlsanity.com/paper/2511.06575/) (2025)
- [Cost-Sensitive Conformal Training with Provably Controllable Learning Bounds](https://mlsanity.com/paper/2511.17861/) (2025)
- [Ensuring Calibration Robustness in Split Conformal Prediction Under Adversarial Attacks](https://mlsanity.com/paper/2511.18562/) (2025)
- [Vision-Language Model Confidence Is Not a Property of the Answer](https://mlsanity.com/paper/2608.06571/) (2026)
- [Conformal Risk Minimization for Semi-Supervised Domain Adaptation via Optimal Transport](https://mlsanity.com/paper/2608.23153/) (2026)
- [Robust Conformal Intrusion Detection via Traffic-Aware Calibration and Attack-Orbit Invariance](https://mlsanity.com/paper/2609.19241/) (2026)
- [NNV3: Expanding Neural Network Verification to New Architectures and Domains](https://mlsanity.com/paper/2609.30050/) (2026)

## Abstract (arXiv)

Conformal prediction is a powerful tool to generate uncertainty sets with guaranteed coverage using any predictive model, under the assumption that the training and test data are i.i.d.. Recently, it has been shown that adversarial examples are able to manipulate conformal methods to construct prediction sets with invalid coverage rates, as the i.i.d. assumption is violated. To address this issue, a recent work, Randomized Smoothed Conformal Prediction (RSCP), was first proposed to certify the robustness of conformal prediction methods to adversarial noise. However, RSCP has two major limitations: (i) its robustness guarantee is flawed when used in practice and (ii) it tends to produce large uncertainty sets. To address these limitations, we first propose a novel framework called RSCP+ to provide provable robustness guarantee in evaluation, which fixes the issues in the original RSCP method. Next, we propose two novel methods, Post-Training Transformation (PTT) and Robust Conformal Training (RCT), to effectively reduce prediction set size with little computation overhead. Experimental results in CIFAR10, CIFAR100, and ImageNet suggest the baseline method only yields trivial predictions including full label set, while our methods could boost the efficiency by up to 4.36×, 5.46×, and 16.9× respectively and provide practical robustness guarantee. Our codes are available at https://github.com/Trustworthy-ML-Lab/Provably-Robust-Conformal-Prediction.