Full Conformal Prediction under Stochastic Non-Conformity Measure

Motivation

• Known: 전통적인 full conformal prediction 이론은 non-conformity score function t가 deterministic이고 첫 N개 인자에 대해 permutation invariant일 때 exchangeable data 하에서 conformal p-value가 valid하다는 것이 알려져 있으며, 이는 ridge regression과 같은 deterministic 학습 알고리즘에 적용된다.
• Gap: 현대 머신러닝(SGD, random initialization, random forest, LLM 추론 등)을 이용한 non-conformity measure는 stochastic하므로 deterministic permutation invariance 조건이 지나치게 제한적이며, 이에 대한 대안으로 여러 논문(Barber et al., 2023; Bian & Barber, 2023; Lee et al., 2023; Bai & Jin, 2024)이 "permutation invariance in distribution"이라는 완화된 조건을 충분조건으로 제시했으나, 저자는 이 조건이 실제로는 불충분함을 보인다.
• Why: full conformal prediction의 타당성을 보장하는 정확한 조건을 아는 것은, SGD, random initialization, random forest, LLM API 호출 등 stochasticity가 불가피한 현대 머신러닝 파이프라인에서 conformal prediction의 coverage guarantee가 실제로 성립하는지를 판단하는 데 필수적이며, 기존에 널리 인용되던 조건이 틀렸다는 것은 관련 이론 및 응용 연구들에 중요한 정정을 요구한다.
• Approach: 저자는 stochastic non-conformity score function T를 알고리즘 무작위성 공간 (Ω, F, Palg)을 도입해 형식화하고, 기존에 알려진 "permutation invariance in distribution" 조건이 반례를 통해 불충분함을 보인 뒤, 이를 대체하는 "Conditional Independence & Permutation Invariance in Distribution"이라는 새로운 충분조건을 제안 및 증명한다.

Achievement

Figure 1. DT stands for deterministic permutation invariance,

1. 오류 지적: Barber et al. (2023), Bian & Barber (2023), Lee et al. (2023), Bai & Jin (2024) 등 4편의 논문에서 언급된 "permutation invariance in distribution" 충분조건이 실제로는 full conformal prediction의 타당성을 보장하지 못함을 간단한 반례(iid Uniform 데이터, N=2, 두 개의 독립적인 표준 Brownian 관련 무작위성 이용)로 증명하였다.
2. 정확한 충분조건 제시: 기존 조건보다 강하지만 여전히 deterministic almost sure invariance(Lee et al., 2025의 조건)보다는 약한, "Conditional Independence & Permutation Invariance in Distribution"이라는 새로운 충분조건을 도입하여 SGD 등 다양한 stochastic 학습 설정을 포괄할 수 있음을 보였다.
3. 문헌 정리: full conformal prediction의 stochastic non-conformity 조건에 관한 기존 5편 논문의 주장을 체계적으로 검토하고 각 주장의 정확성 여부(불충분/충분하지만 협소함)를 분류하였다.

How

Figure 1. DT stands for deterministic permutation invariance,

• Algorithm 1(deterministic non-conformity score를 이용한 conformal p-value 계산)과 Algorithm 2(stochastic T를 이용한 계산)를 formal하게 정의하여 비교
• 알고리즘 무작위성을 나타내는 (Ω, F, Palg)를 데이터 생성 공간과 독립적으로 설정하고, T = [Ti]_{i=1}^{N+1}를 각 좌표별로 다른 randomness를 가질 수 있도록 일반화
• 기존 4편 논문에서 주장된 "equality in distribution under permutation" 조건을 형식적으로 두 요소(같은 인덱스 내 permutation에 대한 분포 동일성, 서로 다른 인덱스 간 분포 동일성)로 분해
• iid Uniform([0,1]^2) 데이터와 N=2인 간단한 설정에서, 두 개의 독립적인 표준 Brownian motion(혹은 관련 확률과정)을 이용한 반례를 구성하여 기존 조건이 만족되지만 conformal p-value가 valid하지 않음을 보임 (Figure 1에서 deterministic permutation invariance(DT)와의 비교 제시)
• Lee et al. (2025)의 almost sure equality 조건이 충분하지만 SGD와 같은 일반적 stochastic 학습에는 적용 불가능할 정도로 협소함을 지적
• Conditional Independence & Permutation Invariance in Distribution 조건을 새롭게 정의하고 이것이 타당성의 충분조건임을 증명 (본문 발췌에는 증명의 전체 세부사항은 포함되지 않음)

Originality

• 기존에 여러 논문에서 각주로 간략히 언급되며 별다른 검증 없이 통용되던 "permutation invariance in distribution" 조건이 실제로는 틀렸음을 최초로 명시적으로 지적하고 반례를 제시함
• stochastic non-conformity measure 하에서 full conformal prediction의 타당성을 다루는 산발적 논의들을 체계적으로 정리하고 비교분석한 최초의 시도로 보임
• deterministic almost sure invariance와 (틀린) distributional invariance 사이의 간극을 메우는 새로운 조건(Conditional Independence & Permutation Invariance in Distribution)을 제시

Limitation & Further Study

• 본문 발췌에는 새로 제안된 "Conditional Independence & Permutation Invariance in Distribution" 조건의 정확한 수학적 정의와 완전한 증명이 포함되어 있지 않아, 조건의 실제 적용 범위와 엄밀성을 완전히 평가하기 어려움
• 반례가 다소 인위적인 (iid Uniform, N=2, Brownian motion 기반) 설정에 국한되어 있어, 실제 SGD나 random forest와 같은 구체적 머신러닝 알고리즘에 새 조건이 어떻게 검증되는지에 대한 구체적 사례 제시가 필요함
• 새 조건이 필요충분조건(necessary and sufficient)인지, 아니면 여전히 충분조건에 불과한지에 대한 논의가 불명확하며, 후속 연구로 조건의 최적성(tightness) 검증과 LLM 기반 full conformal prediction(예: fine-tuning을 포함한 설정)으로의 확장이 필요함

Evaluation

총평: 기존에 여러 저명 논문에서 별다른 검증 없이 통용되던 조건의 오류를 명확한 반례로 지적한 점은 이론적으로 중요한 기여이나, 발췌된 본문만으로는 새로 제안된 충분조건의 완전한 증명과 실용적 적용 사례가 부족해 워크숍 규모의 짧은 논문으로서의 한계가 있다.