Fundamental bounds on efficiency-confidence trade-off for transductive conformal prediction
Arash Behboodi, Alvaro H. C. Correia, Fabio Valerio Massoli, Christos Louizos
cs.LG, cs.IT, stat.ML
2025-09-05
Qualcomm AI Research proves any non-vanishing TCP confidence needs sets growing as e^{nH(Y|X)}. TSCP hits γ=0.33 on MNIST at n=3, versus 0.93 for Bonferroni split CP.
Standard conformal prediction gives per-item marginal coverage: each input gets its own set that contains the true label with probability at least 1−α. Batch quality control, sample screening, and change approval need a stronger object. One miss can void the whole batch, so the guarantee has to be joint: the full label vector for n test points lands in one prediction set.
Transductive conformal prediction (TCP) is that object. Vovk already suggested Bonferroni: run ordinary conformal at α/n per point and take the Cartesian product. Coverage holds. The set grows fast in n. This Qualcomm AI Research paper asks the harder question: how small can that joint set be, in expectation, while still keeping a stated confidence.
Efficiency is the expected cardinality of the joint set, with growth rate γ{n,m} = (1/n) log E|Γ|. The main inequality ties intrinsic label uncertainty to set size: for any β in (0,1), P(P(Y|X)≤β) ≤ α + β E|Γ|. A spread-out conditional makes the left side large at small β, and the set cannot stay small.
Asymptotically there is a phase transition. Any non-vanishing lim inf of 1−αn forces γ ≥ H(Y|X). If the growth rate sits strictly below the conditional entropy, confidence collapses to zero. The finite-sample form uses Berry–Esseen on the sum of log P(Yi|Xi) and adds a dispersion term σ, the standard deviation of log P(Y|X), plus a third-moment ρ. The working approximation is nγ ≥ n H(Y|X) + √n σ Q^{−1}(α) − (log n)/2 + O(1), with Q the Gaussian tail. The template is finite-blocklength Shannon analysis.
The bound is achievable. With oracle P(Y|X), keep every label vector whose product probability clears a threshold β, and the first two orders match the converse. An approximate Q pays an extra E[D(P(·|X)∥Q(·|X))].
That recipe becomes Transductive Split Conformal Prediction (TSCP): treat model scores f(x)[y] as an approximate conditional, score calibration groups by 1−∏ f(xj)[yj], take a finite-sample-corrected quantile, and keep test label tuples whose product clears the threshold. Naive search is O(|Y|^n); the product structure admits a dynamic-programming prune.
Experiments use MNIST, FashionMNIST, CIFAR-10, and CIFAR-100 with symmetric label noise (keep probability 1−ε=0.98), LeNet-5 or ResNet-20, a calibration pool of about 180 points, and α=0.1. Logs are base 2. The information-theoretic ceiling on γ is log₂ of the number of classes: 3.32 for 10 classes, 6.64 for 100.
On MNIST at n=3, TSCP has γ=0.333 against 0.926 for Bonferroni split CP and 1.068 for APS. At n=9 the numbers are 0.813 vs 2.895 vs 2.919. FashionMNIST at n=3: 0.787 vs SCP 1.404. CIFAR-10 at n=3: 0.995 vs 1.679. CIFAR-100 is tighter: 3.418 vs 4.900 at n=3, and at n=9 TSCP 6.608 vs SCP 6.539, both against the 6.64 ceiling, with TSCP's empirical joint coverage a bit lower (0.88 vs 0.92).
Bonferroni degrades quickly in n: α=0.1 and n=20 means 0.005 per point, and a finite calibration set then swallows most labels. TSCP tracks the theoretical curve for n<10. Past that, grouping a 180-point calibration pool into blocks of n leaves 180/n effective groups, which hurts both coverage and efficiency. Oracle conditionals sit on the bound; perturbing them to KL about 0.12 and 0.26 moves efficiency by the KL term in the theorem.
This is a Shannon-style quota for joint uncertainty quantification. On synthetic data where H(Y|X) and σ are computable, new methods should close the gap to this curve rather than merely beating Bonferroni. Systems that need a whole batch to be error-free should not default to an α/n Cartesian product. TSCP is the engineering reading of the theory: optimal sets are level sets of the (approximate) conditional.
It is a hard lower bound plus a better construction, not a new coverage theory. Coverage still rides on exchangeability.
The finite-sample argument assumes i.i.d. test points; the authors list non-i.i.d. extensions as future work. H(Y|X) and σ are unknown on real data. Estimating them with the same Q used to build the set makes the bounds collapse onto each other. TSCP's effective calibration shrinks with n, and the CIFAR-100 n=9 row is already against the ceiling. All experiments are vision classifiers with synthetic label noise. Enumerating the joint set is still expensive for large |Y| or n; dynamic programming only delays that. The theorems are predictor-agnostic, so they do not depend on the training size m and cannot explain how extra calibration buys smaller sets.