# Fundamental bounds on efficiency-confidence trade-off for transductive conformal prediction

arXiv: https://arxiv.org/abs/2509.04631 · HTML: https://mlsanity.com/paper/2509.04631/

## Key facts

- Cited by 2 papers in the map (data through 14 Oct 2026).
- Builds on 20 of its 47 references that are in the map.
- First posted on arXiv 4 Sep 2025.

## Builds on (most cited first, 20 of 20)

- [A Gentle Introduction to Conformal Prediction and Distribution-Free Uncertainty Quantification](https://mlsanity.com/paper/2107.07511/) (2021)
- [Distribution-Free Predictive Inference For Regression](https://mlsanity.com/paper/1604.04173/) (2016)
- [Conformal Prediction Under Covariate Shift](https://mlsanity.com/paper/1904.06019/) (2019)
- [Classification with Valid and Adaptive Coverage](https://mlsanity.com/paper/2006.02544/) (2020)
- [Least Ambiguous Set-Valued Classifiers with Bounded Error Levels](https://mlsanity.com/paper/1609.00451/) (2016)
- [Conformal Inference of Counterfactuals and Individual Treatment Effects](https://mlsanity.com/paper/2006.06138/) (2020)
- [Testing for Outliers with Conformal p-values](https://mlsanity.com/paper/2104.08279/) (2021)
- [Learning by Transduction](https://mlsanity.com/paper/1301.7375/) (2013)
- [Localized Conformal Prediction: A Generalized Inference Framework for Conformal Prediction](https://mlsanity.com/paper/2106.08460/) (2021)
- [Theoretical Foundations of Conformal Prediction](https://mlsanity.com/paper/2411.11824/) (2024)
- [A Conformal Prediction Approach to Explore Functional Data](https://mlsanity.com/paper/1302.6452/) (2013)
- [Universal Inference](https://mlsanity.com/paper/1912.11436/) (2019)
- [Criteria of efficiency for conformal prediction](https://mlsanity.com/paper/1603.04416/) (2016)
- [E-Values Expand the Scope of Conformal Prediction](https://mlsanity.com/paper/2503.13050/) (2025)
- [Transductive conformal inference with adaptive scores](https://mlsanity.com/paper/2310.18108/) (2023)
- [An Information Theoretic Perspective on Conformal Prediction](https://mlsanity.com/paper/2405.02140/) (2024)
- [Universal distribution of the empirical coverage in split conformal prediction](https://mlsanity.com/paper/2303.02770/) (2023)
- [Instance-Log-Optimality of Portfolio-Based E-Processes and their Sequential Hypothesis Tests](https://mlsanity.com/paper/2504.02818/) (2025)
- [Second-Order Asymptotically Optimal Statistical Classification](https://mlsanity.com/paper/1806.00739/) (2018)
- [Optimal E-Values for Exponential Families: the Simple Case](https://mlsanity.com/paper/2404.19465/) (2024)

## Built on by (most cited first, 2 of 2)

- [Singleton-Optimized Conformal Prediction](https://mlsanity.com/paper/2509.24095/) (2025)
- [Supervised Learning as Lossy Compression: Characterizing Generalization and Sample Complexity via Finite Blocklength Analysis](https://mlsanity.com/paper/2602.04107/) (2026)

## Abstract (arXiv)

Transductive conformal prediction addresses the simultaneous prediction for multiple data points. Given a desired confidence level, the objective is to construct a prediction set that includes the true outcomes with the prescribed confidence. We demonstrate a fundamental trade-off between confidence and efficiency in transductive methods, where efficiency is measured by the size of the prediction sets. Specifically, we derive a strict finite-sample bound showing that any non-trivial confidence level leads to exponential growth in prediction set size for data with inherent uncertainty. The exponent scales linearly with the number of samples and is proportional to the conditional entropy of the data. Additionally, the bound includes a second-order term, dispersion, defined as the variance of the log conditional probability distribution. We show that the transductive methods based on the approximate conditional distribution can approach this bound. Inspired by this setup, we introduce a practical transductive prediction algorithm that surpasses Bonferroni methods.