Research map / Learning theory and algorithms / Prediction and decision losses
Robust Conformal Prediction with a Single Binary Certificate
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 BinCP, a robust conformal prediction method that binarizes randomized-smoothing scores with a threshold and needs only one binary certificate, enabling small robust sets with ~150 Monte-Carlo samples.
Problem
Robust conformal prediction under adversarial test perturbations currently requires expensive Monte-Carlo sampling (~10^4 samples) and per-point certificates, and assumes bounded conformity scores, yielding large prediction sets.
Approach
Binarize smoothed scores via a threshold tau so that the smooth score becomes a smoothed binary classifier probability; robustness then needs only one binary certificate c^down[p_alpha, B] computed once, and Clopper-Pearson intervals are tighter for binary variables. Works for unbounded scores.
Key results
- BinCP achieves small robust prediction sets on CIFAR-10 with about 150 MC samples, versus about 2000 or more needed by CAS.
- Only one binary certificate is computed, versus at least one per calibration or test point for CAS, reducing runtime.
- De-randomized DSSN certificate gives exact l1 robustness with no sample correction needed.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use BinCP instead of CAS | Robust conformal prediction · CIFAR-10, ImageNet, and Cora-ML | average set size | Helped |
| Use BinCP with Gaussian smoothing instead of CAS | Robust conformal prediction · ImageNet, sample-corrected | average set size | Helped |
| Use BinCP rather than CAS with sparse smoothing | Robust conformal prediction · Cora-ML | average set size | Helped |
| Use de-randomized DSSN smoothing instead of Gaussian smoothing (ablation) | BinCP · CIFAR-10, ℓ1 robustness | average set size | Helped |
| Increase the Monte Carlo sampling budget (ablation) | BinCP · Cora-ML | average set size | No clear effect |
| Increase the Monte Carlo sampling budget (ablation) | CAS · Cora-ML | average set size | Helped |
| Use sample correction (ablation) | CAS · ImageNet | average set size | Hurt |
| Use sample correction (ablation) | BinCP · ImageNet | average set size | Hurt |
| Increase Gaussian smoothing strength (ablation) | BinCP and CAS · CIFAR-10 | average set size | Mixed |
| Use TPS rather than APS as the score function (ablation) | BinCP · CIFAR-10 | average set size | Helped |
| Use smooth prediction instead of non-smooth prediction (ablation) | Vanilla conformal prediction · CIFAR-10 under adversarial attack | empirical coverage | Helped |
| Use BinCP rather than CAS with asymptotically valid coverage | Robust conformal prediction · ImageNet | average set size | No clear effect |
Surprising findings
- Smoothed scores yield inherent robustness under attack even without any certificate, while non-smooth vanilla CP drops to near 0 coverage at tiny radii.
- Sample correction has almost no effect on BinCP with sparse smoothing, whereas CAS benefits considerably from more samples.
Limitations
- Still requires many forward passes per input (around 150 on CIFAR-10).
- Robustness in input space is not linked to robustness under distribution shift.
- Realistic inductive GNN threat model is not addressed.
Experimental setup
Datasets: CIFAR-10 ImageNet Cora-ML
Benchmarks: CIFAR-10 ImageNet Cora-ML
Metrics: average set size empirical coverage runtime
Baselines: CAS RSCP+ RSCP
Builds on: conformal prediction randomized smoothing CAS (CDF-aware sets) RSCP DSSN de-randomized smoothing
Closest papers by meaning
- One Sample is Enough to Make Conformal Prediction Robust (NeurIPS 2025 · similarity 0.94)
- Robust Yet Efficient Conformal Prediction Sets (ICML 2024 · similarity 0.93)
- Provably Robust Conformal Prediction with Improved Efficiency (ICLR 2024 · similarity 0.92)
- Verifiably Robust Conformal Prediction (NeurIPS 2024 · similarity 0.92)
- Efficient Robust Conformal Prediction via Lipschitz-Bounded Networks (ICML 2025 · similarity 0.90)
- Exploring the Noise Robustness of Online Conformal Prediction (NeurIPS 2025 · similarity 0.88)
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.