Research map / Adversarial robustness and security / Certified and empirical robustness
Robust Yet Efficient Conformal Prediction Sets
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Proposes CAS, a CDF-aware bound on randomized-smoothed conformity scores that yields smaller provably robust conformal prediction sets, extended to poisoning (feature and label) and sparse/discrete data.
Problem
Conformal prediction sets lose their coverage guarantee under adversarial test inputs (evasion) and perturbed calibration data (poisoning), and existing robust CP (RSCP) is loose, only handles evasion on continuous data, and lacks finite-sample correction.
Approach
Bound worst-case smoothed conformity scores using the full CDF of randomized smoothed scores rather than only their mean, giving tighter upper/lower bounds and thus smaller robust sets; add MILP-based poisoning-robust thresholds and calibration-time finite-sample correction.
Key results
- On CIFAR-10 with sigma=0.25, CAS yields smaller robust prediction sets than RSCP across radii, with the gap growing with r (up to 2-3x larger on ImageNet and Cora-ML for larger radii).
- Under feature poisoning with k=|D_cal| on CIFAR-10 (r=0.12), CAS certifies about 97.7% empirical coverage, with set size 3.17 (with correction).
- Label poisoning on CIFAR-10 with k=2 keeps robust coverage at 0.901 versus vanilla coverage dropping to 0.859 under perturbation.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| replace the mean-only score bound with a CDF-based bound | CAS versus RSCP · CIFAR-10, ImageNet, and Cora-ML evasion | average prediction set size | Helped |
| use the CDF-based bound instead of the mean-only bound | CAS versus RSCP · CIFAR-10, ImageNet, and Cora-ML evasion | empirical coverage | Mixed |
| compute evasion bounds during calibration rather than for every test example and class | CAS calibration-time evasion certificate · CIFAR-10 | average prediction set size | Helped |
| compute evasion bounds during calibration rather than at test time | CAS · CIFAR-10 evasion, 100 test samples | runtime (seconds): 3.08 -> 0.94 | Helped |
| remove finite-sample correction (ablation) | CAS · CIFAR-10 feature poisoning, r=0.12, k=3 | average set size: 1.84 -> 1.83 | No clear effect |
| remove finite-sample correction (ablation) | CAS · CIFAR-10 feature poisoning, r=0.25, k=|Dcal| | average set size: 7.32 -> 4.48 | Hurt |
| remove finite-sample correction (ablation) | CAS · CIFAR-10 feature poisoning, r=0.25, k=|Dcal| | empirical coverage: 99.6 -> 98.7 | Hurt |
| increase the label-poisoning budget from k=0 to k=2 | CAS · CIFAR-10 label poisoning | set size (clean): 1.41 -> 1.62 | Hurt |
| use the robust label-poisoning threshold rather than vanilla CP | CAS · CIFAR-10 label poisoning, k=1 | coverage (perturbed): 0.872 -> 0.900 | Helped |
| use the robust label-poisoning threshold rather than vanilla CP | CAS · CIFAR-10 label poisoning, k=2 | coverage (perturbed): 0.859 -> 0.901 | Helped |
| use a smaller Gaussian smoothing parameter (ablation) | CAS · CIFAR-10 evasion across certified radii | average prediction set size | Mixed |
Surprising findings
- Standard conformal prediction's coverage can drop under adversarial label noise even for small budgets, while random label noise is known to be benign.
Limitations
- Coverage guarantee is marginal, not conditional, and one-sided for robust coverage.
- Randomized smoothing requires many Monte-Carlo samples, which is computationally expensive.
- Assumes the attacker's goal is to reduce empirical coverage; other attacker goals (e.g., inflating set size) are not covered.
Experimental setup
Datasets: CIFAR-10 ImageNet Cora-ML
Benchmarks: CIFAR-10 ImageNet Cora-ML
Metrics: empirical coverage average set size singleton hit ratio set size-preserving radius
Baselines: RSCP vanilla conformal prediction
Builds on: RSCP randomized smoothing adaptive prediction sets sparse smoothing
Closest papers by meaning
- Robust Conformal Prediction with a Single Binary Certificate (ICLR 2025 · similarity 0.93)
- Verifiably Robust Conformal Prediction (NeurIPS 2024 · similarity 0.92)
- Efficient Robust Conformal Prediction via Lipschitz-Bounded Networks (ICML 2025 · similarity 0.91)
- One Sample is Enough to Make Conformal Prediction Robust (NeurIPS 2025 · similarity 0.91)
- Provably Robust Conformal Prediction with Improved Efficiency (ICLR 2024 · similarity 0.90)
- Provably Reliable Conformal Prediction Sets in the Presence of Data Poisoning (ICLR 2025 · similarity 0.90)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.