PaperlayerView exact revision on arXiv

Source-linked AI summary

Replicable Conformal Prediction

Marios Papamichalis, Regina Ruane, Theofanis Papamichalis

arXiv:2608.23638v1stat.MLcs.LG

TL;DR

Independent standard conformal calibrations generally produce different deployed classifiers, complicating artifact verification and enabling favorable-redraw selection. The paper introduces shared-grid replicable calibration, quantifies its sample and set-size costs, and establishes matching lower bounds alongside a no-shared-seed alternative.

  • Problem

    Standard split-conformal calibration produces different classifiers across independent samples, making deployed artifacts difficult to verify and allowing favorable redraws to undercover.

  • Method

    RECAL rounds calibrated thresholds upward on a random grid whose offset comes from one shared seed, while deterministic grids provide a two-classifier guarantee without shared randomness.

  • Results

    Matching lower bounds show the sample and set-size costs are necessary up to constants, while experiments across ImageNet, four hospitals, and four language-model families match the theory.

  • Takeaways & Limitations

    Replicable calibration makes cross-analyst agreement checkable on the deployed artifact and limits the effect of selecting among many recalibrations.

  • Takeaways & Limitations

    Real-image experiments use cross-validated probability outputs rather than one frozen network’s raw logits, clinical sites are small, and training-map and selection replicability remain open.

Abstract

from arXiv · show

Two analysts who calibrate the same predictive model on independent samples will deploy different prediction sets every time, because the calibration threshold inherits the randomness of the data. Wherever deployments must be audited, cached, or approved across sites, this instability is costly: no one can verify that two calibrations produced the same object. We ask two questions: when can independent calibrations yield the identical classifier, and what must that agreement cost? Perfect agreement is impossible, since a procedure that almost always returns one fixed answer cannot remain valid for every distribution, and exact agreement through shared randomness forces the procedure to ignore its data. Sharing a single random seed and rounding the calibrated threshold up to a coarse shared grid resolves the tension: the deployed classifier becomes identical across analysts with any desired probability, coverage guarantees survive, and the price is a quantified increase in set size and calibration data. Matching lower bounds show that no threshold method can pay less, and the method's one tuning constant vanishes asymptotically. Without any shared seed, a fixed grid still confines all analysts to two adjacent classifiers, and no method does better. Replicability also blocks gaming: selecting the most favorable of many recalibrations barely moves a replicable classifier, while the same selection silently undercovers standard conformal prediction. Experiments on real ImageNet outputs, a four-hospital site split, and four language-model families match the theory, including the measured sample-cost frontier.

1 INTRODUCTION

The paper studies whether independent conformal calibrations can produce identical deployed classifiers, motivated by auditability, caching, and cross-site validation. It proves impossibility results, introduces shared-seed grid rounding, and characterizes the resulting agreement, validity, costs, and protection against selective recalibration.

  • Motivation: Conformal prediction deploys a thresholded set-valued classifier with finite-sample coverage, but independent calibrations need not produce the identical artifact.The deployed classifier is treated as a hashed, cached, versioned, and audited object, making identity stronger than similar coverage.
  • Motivation: Continuous-score split conformal calibrations agree with probability zero, while selecting the most favorable of M redraws can systematically undercover.The undercoverage scales on the order of √log M times the coverage standard deviation and can pass a support check.
  • Impossibility: Exact agreement is impossible under nontrivial uniform validity, and shared-seed exact replication otherwise forces the output law to be distribution-independent.The impossibility motivates approximate replicability rather than exact agreement without qualification.
  • RECAL: RECAL rounds each calibrated threshold upward to a coarse random grid generated from one shared seed, preserving coverage while achieving ρ-replicability.Its sample complexity is O(κ2α(1 −α)/(ε2ρ2)) under a local margin condition.
  • Costs and lower bounds: n ≥ 9 16384 α(1 −α)/(ε2ρ2) is necessary for any threshold calibrator, while RECAL attains the corresponding set-size lower bound up to κ2.A consistent pilot removes the prior constant and κ2 asymptotically.
  • Seedless and selective recalibration: Without a shared seed, single-answer replication is impossible below failure probability 1/2, but a deterministic grid confines analysts to two adjacent classifiers.With a pre-registered seed, M redraws produce a distinct classifier with probability at most min{1, (M −1)ρ}, and expected coverage degrades by at most the same amount.

2 RELATED WORK

The paper connects conformal calibration to prior work on replicability and conformal prediction. Its distinction is to provide set-level identity with finite-sample validity, explicit constants, lower bounds, and extensions across calibration settings.

  • Replicability: Prior replicability work studies agreement across independent samples, including costs, list relaxations, and links to privacy and stability.The paper applies this framework to conformal prediction and distribution-free uncertainty quantification.
  • Replicability: Relative to replicable quantile methods, this work adds conformal set semantics, finite-sample guarantees, two-sided coverage bands, unequal-sample analysts, and explicit Beta-law-based constants.It also contributes coverage-metric lower bounds, obliviousness and list theory, while using the prior construction as a distribution-free fallback.
  • Conformal prediction: RECAL applies unchanged to conformal risk control and conformal-language-model stopping because these methods calibrate one scalar.The paper also instruments APS/RAPS scores and evaluation within the conformal prediction setting.

3 PRELIMINARIES: CALIBRATION AND REPLICATION METRICS

The preliminaries define split-conformal calibration, shared-seed replicability, and a spectrum of agreement metrics. They establish that standard continuous-score calibration does not replicate, motivating shared-grid thresholding.

  • Calibration: Split conformal calibrates an order-statistic threshold eτn and deploys Cτ(x) = {y : s(x, y) ≤τ}, achieving coverage at least 1 −α.The construction assumes a fixed measurable score with continuous calibration-score law.
  • Replication: A calibrator is ρ-replicable when two independent datasets using the same shared random string return identical outputs with probability at least 1−ρ.List replicability instead requires both outputs to lie in a common distribution-dependent list of bounded size.
  • Shared-grid calibration: RECAL uses one shared uniform offset to round each empirical threshold upward to a shared grid, while the seedless variant sets the offset to zero.The seedless rule places analysts in a common two-element list of adjacent classifiers.
  • Replication metrics: The replication spectrum records identity, pointwise agreement, churn mass, and list membership, which are not totally ordered.Identity implies extreme pointwise agreement and churn values, but maximizing identity can worsen conditional churn.
  • Standard conformal instability: For continuous scores, two independent standard split-conformal calibrations have threshold and map equality probability zero.Their realized coverage nevertheless fluctuates according to the associated Beta law.

4 EXACT REPLICATION IS IMPOSSIBLE AND FORCES OBLIVIOUSNESS

The paper proves that exact replication conflicts with nontrivial uniform validity. With shared randomness, exact replication forces data-oblivious output; without it, strong single-answer replication is also incompatible with uniform validity.

  • Setup: Uniform ε-validity requires coverage within [1 −α −ε, 1 −α + ε] for every distribution in the stated class.The two-sided requirement rules out the trivial procedure that always returns the full label set.
  • Impossibility: If ε+δ < min(α, 1−α), no (1, δ)-list-replicable procedure can be uniformly ε-valid.Because every seedless ρ-replicable procedure is (1, ρ)-list replicable, the same obstruction applies when ε + ρ is below the threshold.
  • Obliviousness: With a shared seed, exact replication makes the output equal to a fixed seed-dependent value almost surely under every distribution.The output law is therefore independent of the data-generating distribution, making validity vacuous except at the data-oblivious endpoint.
  • Obliviousness: Determinism does not evade the impossibility because sample randomness remains, and exact validity with atomless outputs is possible only without informative replication.The result establishes shared randomness as necessary for the paper’s useful replication relaxation.

5 RECAL: REPLICABLE CALIBRATION WITH A SHARED SEED

RECAL rounds calibrated thresholds upward on a shared random grid, making independent classifiers agree with controlled probability while preserving coverage. Its finite-sample guarantees quantify the calibration-size, set-size, and selective-recalibration costs.

  • RECAL construction: Rounding upward can only enlarge prediction sets, so RECAL preserves the classical marginal coverage guarantee.Its analysis controls threshold disagreement and rounding inflation through a local margin condition.
  • Finite-sample guarantees: Theorem 2 bounds threshold disagreement by B_n f_min β + 4e^(-n f_min^2/2)/n and supplies simultaneous conditional coverage bands.On agreement, the two classifiers coincide at every test input when they use the same score.
  • Finite-sample guarantees: Choosing β = ε/(2f_max) and n ≥ max{32κ^2α(1−α)/(ε^2ρ^2), 8log(2/δ)/ε^2, n_0} yields ρ-replicability and inflation at most ε.The guarantee holds with probability 1−δ over calibration data for every realized shared offset.
  • Selective recalibration: With a fixed pre-registered offset, M selective recalibrations produce a distinct classifier with probability at most min{1,(M−1)ρ}, while standard conformal selection loses approximately a_Mσ_n coverage.Support-only audits have zero power against this selection, whereas replicability restores selection robustness.
  • Pilot calibration: A shared pilot estimates local density and selects the grid width, while a valid prior bound ˆκ ≥ κ is the remaining uncertified input.The pilot construction achieves unconditional disagreement probability at most ρ + δ_p and preserves marginal coverage for every pilot and offset realization.
  • Asymptotics: The plug-in pilot removes κ from the asymptotic premium and makes the prior constant ˆκ asymptotically unnecessary.The resulting width meets the lower-bound frontier within an absolute factor.

6 LOWER BOUNDS: SAMPLES AND SET SIZE

The paper proves that shared-seed replicability requires calibration samples and set-size inflation, while these costs are unavoidable for threshold methods. The lower bounds identify the relevant α(1−α) dependence and score-mass geometry.

  • Sample lower bound: n ≥ 9(1−8δ)^2α(1−α)/(ε^2ρ^2) is necessary for uniformly valid ρ-replicable threshold calibration.The lower bound is proved on a hard atomless family satisfying the local margin condition with κ = 1.
  • Sample lower bound: A two-point density family reduces threshold accuracy to a replicable coin problem, producing the α(1−α) factor without logarithmic loss.The construction uses the count N ~ Bin(n,m) near bias 1−α.
  • Scope of lower bounds: For a fixed distribution, the oracle threshold is 0-replicable, exactly valid, and has zero inflation, so the lower bound is necessarily worst-case.RECAL attains the worst-case frontier up to κ^2.
  • Set-size lower bound: Any threshold mismatch crosses a full grid cell, forcing churn at least equal to that cell’s label mass and converting unavoidable inflation into set-size cost.The same geometry explains both always-paid set enlargement and churn on rare mismatches.

7 THE SEEDLESS SETTING: AN OPTIMAL TWO-ELEMENT LIST

Without a shared seed, exact single-answer replication is unavailable below failure probability 1/2. A deterministic grid instead confines analysts to two adjacent thresholds, and this list size is optimal within the margin class.

  • Two-element list: Deterministic-grid RECAL places every analyst, with probability at least 1−δ, in a sample-independent two-element list at rate n ≥ ⌈32κ^2log(2/δ)/ε^2⌉.The list consists of adjacent thresholds separated by β = ε/(2f_max).
  • Optimality: For δ < 1/2, no procedure can provide a deterministic singleton output and the two-sided accuracy band for every distribution in the class.Thus list size two is optimal within the specified margin class.
  • Interpretation: One replicable answer requires a shared seed and 1/ρ^2 cost, whereas two answers require neither.The two adjacent thresholds provide a checkable property for regulators unable to coordinate randomness.
  • Full conformal limitation: For full conformal prediction with a 1-nearest-neighbor score, nonendpoint cutoffs have zero agreement probability even with shared randomness.Agreement occurs only at endpoint cutoffs, so rounding does not rescue the usual full-conformal rule.

8 EXPERIMENTS

Experiments evaluate RECAL across image, language-model, and small-site settings, finding that baseline calibrations rarely replicate while RECAL meets its targets with predictable size and sample costs.

  • Real ImageNet calibrations agree on 65% of points, or 87% after derandomization, but have identity 0.00.
  • Four real language-model families show only 24–55% pointwise agreement, with disagreements of 5–20 tokens per context.
  • RECAL achieves identity .95 at ρ=.1 and 1.00 at ρ=.01 on the synthetic image track, while real language-model non-replication remains at or below the .10 target.
  • At n=25,000, RECAL increases set size by 19% on the synthetic track and 17% on real ImageNet at ρ=.1.
  • At n=800, the ρ=.1 target costs +238% set size, whereas ρ=.2 costs +4%, demonstrating the small-sample trade-off.
  • Measured mismatch decays approximately as n^-1/2, with fitted exponents from −.43 to −.50 and crossing slope 2.09.

9 DISCUSSION, LIMITATIONS, AND FUTURE WORK

The discussion frames replicable calibration as artifact-level agreement with explicit validity, measurability, and representation assumptions, while identifying open scope boundaries for deployment and theory.

  • Replicable calibration makes cross-analyst agreement checkable on the deployed artifact, yielding one classifier or a certified pair with matched costs and a selection bound.
  • Future work includes frozen production-scale deployment, finite-n removal of κ̂ and κ2, and training-map or selection replicability beyond cutoff stabilization.
  • The formal arguments use standard Borel output spaces, measurable deployed maps, and absolutely continuous covariates to establish the impossibility and size bounds.
  • The formal setup treats outputs as encoded elements of V and requires all randomness affecting the deployed map to be included before output.
  • Uniform two-sided ε-validity constrains marginal coverage for every distribution in Pac to [1−α−ε, 1−α+ε].
  • The singleton-list impossibility follows when ε+δ<min{α,1−α}, while the proof also establishes a common output across distributions under shared-seed replication.

A.2 PROOF OF THEOREM 1(B)

The proof shows that exact shared-seed replication forces a data-oblivious output law, after which uniform validity imposes pointwise coverage constraints on the deployed maps.

  • Exact replication under a dominating law yields a measurable representation v⋆(r) independent of the calibration data for every P∈Pac.
  • Uniform two-sided validity transfers to pointwise bounds ℓε≤p(x,y)≤uε for almost every covariate and every label.
  • Summing the pointwise bounds over the K labels produces the asserted two-sided prediction-set size bound.
  • A deterministic order-statistic procedure can be uniformly two-sided 0-valid yet have an atomless output law, so no singleton list has positive success probability.
  • A data-oblivious shared-seed procedure using everywhere-full and everywhere-empty maps is exactly replicable and valid, but uninformative.

B PROOFS FOR SECTIONS 3 AND 5

The appendix formalizes conformal threshold behavior, RECAL’s shared-offset guarantees, selection robustness, and robustness to score or population mismatch, while recording finite-sample caveats.

  • The split-conformal coverage variable follows Beta(kn,n+1−kn), and expected coverage of the smallest threshold is exactly kn/(n+1)≥1−α.
  • RECAL with a shared offset satisfies threshold mismatch probability at most ρ, so deployed classifiers are ρ-replicable while retaining marginal coverage at least 1−α.
  • With probability at least 1−cM, every measurable selection among M redraws deploys the same classifier, and coverage loss is bounded by cM=min{1,(M−1)ρ}.
  • The asymptotic √2 log M expression is not an exact finite-M formula, and the stated lower-order claim is not uniform when margin parameters vary.
  • Equal numerical thresholds need not yield equal maps when analysts use different scores, although the disagreement probability is bounded by min{1,2fmaxηs}.
  • Under bounded score and population mismatch, equal thresholds imply map disagreement at most min{1,δ+2fmaxηs} on the stated event.

C PROOF OF THEOREM 3

The proof embeds a binomial hard family into threshold calibration and uses seed-conditional acceptance probabilities to derive replication lower bounds. It also identifies the scope of the argument and the grid-based construction used for the matching upper bound.

  • Scope: The lower-bound argument applies to exact replication of a scalar threshold index, not automatically to equality of arbitrary classifier maps or sample-dependent nested families.Equal indices imply equal set maps, but converse equality can occur without equal indices; unrestricted score-space subsets are also outside this reduction.
  • Proof mechanism: The proof directly bounds the derivative of the seed-conditional acceptance probability and integrates the replicability constraint without a logarithmic loss.No external replicable-coin theorem is required.
  • Hard family: The hard family varies a density parameter m while preserving atomlessness, continuity, and controlled local density around the target quantile.The construction uses M=[p−2ε,p+2ε], with p=1−α, and establishes common margin and density parameters.
  • Binomial reduction: A binomial reduction makes the calibration sample depend on m through N∼Bin(n,m), while the conditional sample law given N is m-independent.This enables analysis through the acceptance probability h_r(m) for each shared seed r.
  • Replicability bound: For a fixed seed, disagreement between independent Bernoulli decisions has probability 2h_r(m)(1−h_r(m)), which lower-bounds threshold disagreement.The proof integrates this pointwise relation across the hard family using variance and derivative bounds.
  • RECAL construction: RECAL rounds the calibrated threshold upward on a shared random grid, preserving validity while constraining outputs to shared grid values and enabling replicability.The construction’s grid-cell localization supports the corresponding classifier agreement and set-size analysis.

D.1 PROOF OF THEOREM 4

The proof establishes seedless list replicability by controlling the empirical quantile on a common deterministic grid. It proves that two adjacent thresholds suffice and that singleton threshold lists cannot generally achieve the same guarantee.

  • Accuracy control: A DKW event controls the empirical quantile around q, yielding a high-probability accuracy band for the rounded threshold.The proof combines the quantile deviation bound with local density control and the grid spacing β.
  • Validity: Upward rounding preserves marginal coverage because the rounded threshold is no smaller than the split-conformal order statistic.Exchangeability and continuity yield coverage kn/(n+1)≥1−α.
  • Optimality: A translated-uniform subfamily rules out an unconditional singleton threshold list under translations when δ<1/2.Nearby translations force the output atom to remain constant, but extreme translations make any fixed threshold violate the accuracy band.
  • Scope: The optimality claim concerns numerical thresholds and transfers to classifier maps only when the threshold-to-classifier map is injective on the admissible domain.A dense attainable score range is sufficient for this injectivity.
  • Distribution-free fallback: Without a margin assumption, a shared-seed binary-search fallback remains distribution-free on a known finite score grid, at a larger sample complexity.The fallback uses a known grid of R score values and retains approximate two-sided calibration guarantees.

F CONSTANTS: DERIVATIONS FOR REMARK 2

The constant calculations compare expectation-level, high-probability, and black-box analyses of calibrated rounding. They quantify both the benefit of the margin assumption and the gap between certified and empirical sample costs.

  • Exact-Beta analysis: n≈7.2×10^5 is required by the exact-Beta analysis at (α,ε,ρ,δ)=(0.1,0.02,0.1,0.05), with replicability dominating coverage.The two terms are approximately 7.2×10^5 and 7.4×10^4, respectively.
  • Coverage behavior: Figure 2 contrasts standard calibration’s exact Beta coverage law with RECAL’s concentration on a few shared grid atoms, all at least 1−α.This concentration supports both replication and the selection bound.
  • Replicability behavior: Figure 3 shows RECAL’s achieved non-replication tracking the target from below, while κ̂∈{1.5,2} restores compliance when κ̂=1 excursions occur.The image track uses n=25,000, and the digits track uses n=800.
  • DKW analysis: The high-probability DKW/union analysis is approximately 49 times more expensive than the exact-Beta analysis.The ratio is ln(8/ρ)/(α(1−α)), reflecting a variance-versus-tail gap.
  • Binary-search fallback: The black-box replicable binary-search bound is approximately 2.6×10^8 samples, about 350 times the exact-Beta row while requiring no margin assumption.The comparison quantifies the cost of removing Assumption 1.
  • Empirical frontier: The empirical frontier is n*≈3.6×10^4, making the certified exact-Beta constant approximately five times conservative on the testbed.At the same parameters, the certified calculation gives 1.8×10^5.

G EXPERIMENTAL DETAILS

Experiments measure replication, calibration cost, model-scale effects, selection robustness, and real-data behavior across image, digit, and language-model settings. Results broadly match the theory, while finite-pool ties create small baseline identity rates.

  • Sample-complexity frontier: Mismatch decay slopes are −.49, −.50, −.43, and −.49, while n∗ versus 1/(ερ) has slope 2.09 with 95% CI [1.99, 2.28].The measurements match the predicted n−1/2 decay and the theoretical (ερ)^−2 scaling.
  • Environment and protocols: Experiments use deterministic regeneration, cached logits, fixed seeds, and standardized score and calibration interfaces across image, digit, and language-model tracks.The real-model tables regenerate from cached logits in 6–10 CPU-minutes per model; the full suite was rerun end-to-end once.
  • Model-scale sweep: Across a 20× Pythia model-scale range, standard-set size falls from 559 to 108 tokens but agreement rises only from .16 to .40, whereas RECAL identity is .85–.94 at ρ=.1.The RECAL size cost varies non-monotonically within 46–84%, consistent with tail geometry.
  • Real-data results: On real ImageNet at n=25,000, RECAL reaches identity .87 at ρ=.1 with coverage .910 and size 5.05, a +17% size cost.At ρ=.01, identity rises to .99 while size reaches 13.2; seedless two-list mass is 1.000.
  • Experimental limitation: Finite-pool ties produce baseline identity rates up to .02 on image, .02–.05 on digits, and .00–.04 on real language models, artifacts that vanish for continuous populations.These ties slightly help all methods equally.
Loading 2608.23638v1…