Full Conformal Prediction under Stochastic Non-Conformity Measure
Thanawat Sornwanee · 2026
Read Full Conformal Prediction under Stochastic Non-Conformity Measure by Thanawat Sornwanee (2026) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2606-28730.txt.
Introduction
Thanawat Sornwanee, writing alone, repairs the footing of conformal prediction, the method that wraps any model in honest confidence sets. Full conformal prediction retrains the model on every candidate answer, and modern practice makes its non-conformity measure random, since training itself involves chance. A folklore loosening claimed the guarantee survives if the measure is merely permutation invariant in distribution.
Sornwanee shows that the commonly used condition is in fact not enough, a crack in a widely used guarantee. In its place he provides a correct sufficient condition, which he names conditional independence together with permutation invariance in distribution. The new condition still covers several chance-driven settings that arise in machine learning practice, so the repair does not exile the methods people actually use. It tells them exactly which extra shape their randomness must respect.
Catalog record
| CREATOR | Thanawat Sornwanee |
|---|---|
| YEAR | 2026 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 35 KB |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2606.28730
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
Full Conformal Prediction under Stochastic Non-Conformity Measure Thanawat Sornwanee Abstract The theory of full conformal prediction uses deterministic non-conformity measure, but modern usage of full conformal prediction often relies on machine learning training, making stochasticity inevitable. A simple sufficient condition of almost sure permutation invariance of the non-conformity measure can be too restrictive, so many have suggested the relaxation to permutation in distribution as a condition for full conformal prediction validity. We, however, show that this commonly known condition is actually insufficient. We then provide a correct sufficient condition: Conditional Independence & Permutation Invariance in Distribution , which encompasses several stochastic settings that may be used in machine learning. 1 Full conformal prediction Given the dataset of \displaystyle\left(\left[z_{i}=(x_{i},y_{i})\right]_{i=1}^{N},x_{N+1}\right), where x_{i} is the input and y_{i} is the output, we are interested in constructing a confidence bound on the unobserved output y_{N+1} . A standard conformal prediction relies on the routine of retrieving conformal p-value from the rank of the non-conformity score. Afterwards, the conformal prediction returns a confidence set \displaystyle\left\{\hat{y}\in\mathcal{Y}:\text{conformal p-value}\left(\left[z_{i}\right]_{i=1}^{N},\left(x_{N+1},\hat{y}\right)\right)\geq\alpha\right\}. In full conformal prediction setting, we are given a non-conformity score function t:\mathcal{Z}^{N+1}\to\mathcal{S} , where \mathcal{S} is a totally preordered set endowed with a binary relation 1 1 1 which is reflexive, transitive, and complete. \succcurlyeq , and is normally chosen to be \left(\mathbb{R},\geq\right) . ( 19 ; 18 ) We the compute the score in leave-one-out manner, and then compute the conformal p-value from the rank of the score as outlined in the algorithm 1 . Algorithm 1 Conformal p-Value via Deterministic t 0: Full Data z\in\mathcal{Z}^{N+1} 1: for i=1 to N+1 do 2: Compute Non-Conformity Score s_{i}=t\left(z_{1},\dots,z_{i-1},z_{i+1},\dots,z_{N+1},z_{i}\right) 3: end for 4: Compute Conformal p-Value P=\frac{1}{N+1}\left[1+\sum_{i=1}^{N}\mathbf{1}_{S_{N+1}\succcurlyeq S_{i}}\right] 5: return P The result is that, if Z=\left[Z_{i}=(X_{i},Y_{i})\right]_{i=1}^{N+1} is exchangeable, and the non-conformity score function t is permutation invariant in the first N arguments, then the conformal p-value of the actual data Z is a valid p-value 2 2 2 See appendix A for a formal definition. . This implies that the actual output Y_{N+1} is in the confidence set with respect to \left(\left[Z_{i}\right]_{i=1}^{N},X_{N+1}\right) with probability \geq 1-\alpha , where the randomness is from the stochasticity of Z itself. In most cases, the function t uses the first N data entries, which is \{z_{j}\}_{j\neq i} , symmetrically to train a regression model 3 3 3 If the training returns more estimators, such as variance estimator or quantile estimator, one can modify the score to incorporate them. ( 12 ; 15 ) \hat{f}_{-i}:\mathcal{X}\to\mathcal{Y} , and use the loss \left\|y_{i}-\hat{f}_{-i}(x)\right\| to be the non-conformity score S_{i} . Note that the trained model \hat{f}_{-i} does not have to be good or satisfy any conditions apart from that it training process must be deterministic and permutation invariant in the data input \{z_{j}\}_{j\neq i} . For example, a ridge regression or machine learning with fixed initialization and stochastic descent will satisfy this. Permutation invariance seems to be natural to most modern machine learning algorithm, but deterministic training requirement is often violated. Modern applications of full conformal prediction often rely on a training of a machine learning model, which may involve stochasticity via stochastic gradient descent as well as random initialization. ( 8 ; 17 ) Some may also employ different stochastic training model such as random forests. ( 11 ; 6 ) Apart from the stochasticity in the training, we will see that the stochasticity in the inference time is also not uncommon. The emergence usage of modern LLM (large language model) as well as other generative model can have stochasticity in the inference such as from the API call itself. 4 4 4 Currently, the usage of LLM as well as other pretrained models in conformal prediction is more limited to a split conformal setting. ( 14 ; 13 ; 16 ; 5 ) However, one can imagine the use of full conformal prediction by doing a fine-tuning steps, or other post-training alignment methods, with the input data. Though this has not been extensively studied ( 1 ) suggest adding a small white noise to each score can also be used for tie-breaking. This suggests that a better understanding of full conformal prediction under a stochastic non-conformity measure is crucial. 2 Stochasticity Before discussing the prior works, we will provide some formulation of full conformal prediction under stochastic measure/score. This is when we replace the routine of computing conformal p-value from using a deterministic function t:\mathcal{Z}^{N+1}\to\mathcal{S} to stochastic function(s) T . Note that we will assume that every function mentioned has to be measurable throughout. Since we may evaluate different non-conformity score with different randomness 5 5 5 For example, \omega may dictate 3 independently drawn random seed \epsilon_{1} , \epsilon_{2} , and \epsilon_{3} . The training process to get score 1 may only utilize the seed \epsilon_{1} , while that of the score 2 only uses \epsilon_{2} . Therefore, mathematically, we need to put the indicator for T . , we then need to provide flexibility for the stochastic function of each coordinate to be different. Formally, we have the algorithmic random space \left(\Omega,\mathcal{F},\mathbb{P}_{\text{alg}}\right) , which will throughout be assumed to be independent from that generating data, and a vector of stochastic functions T=\left[T_{i}\right]_{i=1}^{N+1} where T_{i}:\mathcal{Z}^{N+1}\times\Omega\to\mathcal{S} for each i\in\{1,2,\dots,N+1\} . The routine of computing non-conformity score becomes the algorithm 2 . Note that, for a given z , the p-value P still inherits randomness from the algorithm. Algorithm 2 Conformal p-Value via Stochastic T 0: Full Data z\in\mathcal{Z}^{N+1} , Algorithmic Random Space \left(\Omega,\mathcal{F},\mathbb{P}_{\text{alg}}\right) 1: Realize \omega\sim\mathbb{P}_{\text{alg}} 2: for i=1 to N+1 do 3: Compute Stochastic Non-Conformity Score S_{i}=T_{i}\left(z_{1},\dots,z_{i-1},z_{i+1},\dots,z_{N+1},z_{i};\omega\right) 4: end for 5: Compute Stochastic Conformal p-Value P=\frac{1}{N+1}\left[1+\sum_{i=1}^{N}\mathbf{1}_{S_{N+1}\succcurlyeq S_{i}}\right] 6: return P The question of interest is then What is a sufficient condition on the random functions T=\left[T_{i}\right]_{i=1}^{N+1} for the validity of the conformal prediction? This is when the actual observation Y_{N+1} is included in the confidence set with probability \geq 1-\alpha , where now the randomness comes from both the data Z itself and the algorithm. This is equivalent to asking for a sufficient condition for the conformal p-value in the algorithm 2 to be a valid p-value whenever the random input Z is an exchangeable random vector. Formally, for any exchangeable Z , we require, for all \alpha\geq 0 , \displaystyle\mathbb{P}\left(\text{conformal p-value}\left(Z;\omega\right)\leq\alpha\right)\leq\alpha. 2.1 Prior Works As discussed, the stochasticity in full conformal prediction is not uncommon, but the theoretical study is lacking. To the author’s knowledge, only 5 papers explicitly mention about condition for stochastic conformal score. The mentions are brief: 3 of them are in footnotes. 4 claims are also incorrect. Incorrect Claims The paper “Conformal Prediction Beyond Exchangeability" ( 3 ) has claimed that in a case where the stochastic T is such that \displaystyle T_{i}(z_{1},z_{2},\dots,z_{i-1},z_{i+1},z_{i+2},\dots,z_{N+1},z_{i};\omega) \displaystyle=\left(\mathcal{A}(z_{1},z_{2},\dots,z_{i-1},z_{i+1},z_{i+2},\dots,z_{N+1};\omega)\right)\left(z_{i}\right) for some random algorithm \mathcal{A} mapping z_{-i}\in\mathcal{Z}^{N} to a function \hat{\mu}:\mathcal{X}\to\mathcal{Y} , which is assumed to be \mathbb{R} , then we only require \displaystyle\mathcal{A}\left(z;\cdot\right)\overset{\text{d}}{=}\mathcal{A}\left(\left[z_{\sigma(i)}\right]_{i=1}^{N};\cdot\right) for all z\in\mathcal{Z}^{N+1} and for all permutation \sigma\in S_{N} . 6 6 6 The footnote 2 of ( 3 ) states that “If \mathcal{A} is a randomized algorithm, then this equality is only required to hold in a distributional sense,” where the original equality refers to \mathcal{A}\left(z\right)=\mathcal{A}\left(\left[z_{\sigma(i)}\right]_{i=1}^{N}\right) , which is a commonly used sufficient condition in deterministic full conformal