Replicable Conformal Prediction

Technical Summary: Replicable Conformal Prediction

Problem Statement
Standard split conformal prediction produces set-valued classifiers with finite-sample coverage guarantees. However, when two independent analysts calibrate a conformal predictor on separate held-out samples, they almost surely deploy different classifiers. This occurs because the calibrated threshold is an order statistic of continuously distributed scores; thus, the probability of two independent calibrations yielding the identical threshold (and consequently the identical classifier) is zero.

This lack of replicability creates significant issues for deployment artifacts that require hashing, caching, versioning, or auditing. Furthermore, the instability is exploitable: an adversary can redraw their calibration set multiple times and select the most favorable draw, leading to systematic undercoverage that remains undetectable by standard support checks. While "one-point stability" notions exist, they do not guarantee that the deployed classifier itself is identical across runs.

Methodology: RECAL
The paper proposes RECAL (Replicable Calibration), a procedure that ensures two independent analysts deploy the identical classifier with high probability ($1-\rho$) while preserving marginal coverage guarantees.

1. Shared Seed and Rounding: RECAL utilizes a shared random seed to generate a random offset $u$ for a fixed grid width $\beta$. Analysts compute the standard conformal threshold $\hat{\tau}$ and round it upward to the nearest grid point defined by $u + \beta\mathbb{Z}$.

   • The upward rounding ensures that the marginal coverage guarantee ($\ge 1-\alpha$) is preserved unconditionally, as the prediction sets only grow.
   • The shared grid ensures that if the unrounded thresholds $\hat{\tau}$ and $\hat{\tau}'$ fall within the same grid cell (or straddle a boundary in a specific way), the rounded thresholds $\tau$ and $\tau'$ will be identical.

2. Theoretical Framework:

   • Impossibility of Exact Replication: The paper proves that exact replication (probability 1 of identical output) is impossible for any procedure that remains uniformly valid for every distribution. Furthermore, with a shared seed, exact replicability forces the output to be data-oblivious (ignoring the data), rendering the classifier uninformative.
   • Local Margin Assumption: The analysis relies on a local margin condition (Assumption 1), assuming the score distribution has a density bounded away from zero and infinity in a neighborhood of the target quantile. This allows for explicit constants in sample complexity bounds.
   • Seedless Variant: Without a shared seed, the paper shows that exact singleton replication is impossible below a failure probability of $1/2$. However, a deterministic grid can confine all analysts to a common list of two adjacent classifiers with high probability, which is optimal for seedless settings.

3. Robustness to Selection: The paper analyzes "selective recalibration," where an adversary selects the best of $M$ calibration draws. It proves that if a procedure is $\rho$-replicable, the probability that an adversary can find a distinct classifier among $M$ draws is bounded by $\min\{1, (M-1)\rho\}$. This prevents the systematic undercoverage seen in standard split conformal prediction under selection.

Key Contributions

1. Impossibility Theory: The authors establish that exact replication is incompatible with non-trivial validity and that shared randomness is necessary for meaningful replicability. They characterize the frontier for seedless replication as a two-element list of adjacent classifiers.
2. RECAL Algorithm: A concrete, replicable split-conformal calibrator with preserved validity. The paper provides explicit finite-sample constants for the required calibration size $n$ to achieve a target replicability $\rho$ and coverage error $\epsilon$: $n = O(\kappa^2 \alpha(1-\alpha) / (\epsilon^2 \rho^2))$, where $\kappa$ bounds the local score-density ratio.
3. Lower Bounds: The paper derives lower bounds with explicit constants, showing that the sample complexity and the inflation in set size (coverage) are unavoidable for any threshold calibrator. The set-size cost is shown to be $\Omega(\sqrt{\alpha(1-\alpha)/n}/\rho)$.
4. Plug-in Procedure: A pilot procedure is introduced to estimate the density constant $\kappa$ from data, removing the need for a pre-specified $\hat{\kappa}$ asymptotically.
5. Empirical Validation: Experiments on ImageNet (synthetic and real), a small-data digits task, and four large language model families (GPT-2, Pythia, Qwen, Llama) demonstrate that RECAL achieves the predicted replicability targets. The experiments confirm that standard conformal prediction has near-zero identity, while RECAL achieves high identity (e.g., 0.95–1.00) with a quantifiable cost in prediction set size.

Results

• Replicability: RECAL successfully achieves the target non-replication rate $\rho$. For example, at $\rho=0.1$, the method achieved identity rates of 0.95 on synthetic image data and 0.89–0.96 on real language models.
• Coverage: Marginal coverage is preserved ($\ge 1-\alpha$). The realized coverage concentrates on grid atoms, preventing the Beta-distributed fluctuations of standard conformal prediction.
• Set Size Cost: The method incurs a cost in the size of the prediction sets. On real language models, the set size increased by 55–59% at $\rho=0.1$. The paper notes that for models with heavy-tailed vocabularies (e.g., Qwen), this cost can be significantly higher due to the geometry of the score distribution, though this is a property of the score space, not a failure of the method.
• Selection Attack: In a stress test where an adversary selected the lowest-coverage draw from 20 recalibrations, standard split conformal undercovered significantly (0.892 vs. nominal 0.900). RECAL, however, maintained coverage above the nominal level because all candidates were upward-rounded, valid thresholds.

Significance and Claims
The paper claims to provide the first framework for replicability in conformal prediction, addressing a critical gap where standard methods fail to produce identical artifacts across independent runs. The significance lies in:

• Auditability and Caching: Enabling the deployment of verifiable, cached, and versioned conformal predictors, which is essential for regulatory audits and production systems.
• Selection Robustness: Providing a theoretical and practical defense against "selection attacks" where parties cherry-pick calibration sets to manipulate coverage.
• Trade-off Characterization: Explicitly quantifying the cost of replicability in terms of sample size and prediction set size, showing that these costs are unavoidable and providing the optimal rates.

The authors remain modest about limitations, noting that the real-image experiments used cross-validated probabilities rather than raw logits from a single frozen network, and that the clinical site-split track was limited by small sample sizes ($n \le 303$). They also acknowledge that while the asymptotic removal of the density constant $\kappa$ is possible, finite-sample uniform removal remains an open problem.