기술 요약: 초과 설계 효과 (The Exceedance Design Effect)

1. 문제 정의

머신러닝 시스템은 종종 특정 분위수(quantile)에 설정된 임계값에 의존합니다(예: 90% 커버리지를 보장하는 컨포멀 예측기, 절제 게이트(abstention gates), 또는 안전 필터). 이러한 보장은 교정 세트(calibration set)의 예시들이 독립적이고 동일하게 분포(i.i.d.)한다고 가정합니다. 그러나 LLM 추론, 빔 서치(beam search), 또는 추론 경로(reasoning traces)와 같은 현대적 파이프라인에서는 교정 단위들이 공통된 프롬프트, 문서, 또는 추론 이력을 공유하는 경우가 많으며, 이는 데이터의 클러스터링(clustering)을 생성하여 의존적인 데이터 구조를 만듭니다.

설문 통계학에서는 클러스터링에 따른 평균값의 유효 표본 크기($n_{eff}$) 감소를 설계 효과(design effect, Kish, 1965)를 통해 오랫동안 다루어 왔으나, 본 논문은 표준 보정 방식이 임계값(순서 통계량, order statistics)에는 부적절하다고 주장합니다. 표준 설계 효과는 원시 점수(raw scores)의 상관관계에 기반합니다. 저자는 임계값에 대한 관련 상관관계가 점수 그 자체가 아니라, 초과 지표(exceedance indicators, 점수가 임계값보다 높거나 낮은지 여부) 사이의 상관관계임을 입증합니다. 또한, 이 상관관계는 일정하지 않으며, 임계값이 설정된 특정 수준에 따라 달라집니다.

2. 방법론 및 이론적 프레임워크

핵심 정의

• 초과 지표 (Exceedance Indicator): 임계값 $q_p$ ($p$-분위수)에 대하여, 지표는 $I = \mathbb{1}\{S \le q_p\}$입니다.
• 초과 상관관계 ($\rho_I(p)$): 이러한 이진 지표들의 클러스터 내 상관관계입니다.
• 초과 설계 효과 (DEFF): $1 + (\tilde{m} - 1)\rho_I(p)$로 정의되며, 여기서 $\tilde{m}$은 크기 편향 평균 클러스터 크기입니다.
• 유효 표본 크기 ($n_{eff}$): $n / \text{DEFF}$.

이론적 유도

본 논문은 클러스터링 하에서의 실현된 커버리지($C$)의 분포에 대한 폐쇄형 법칙(closed-form law)을 유도합니다.

1. 설정: 교정 점수들이 크기가 $m$인 $b$개의 클러스터로 들어옵니다 (총 $n=bm$). 클러스터들은 i.i.d.이며, 클러스터 내 점수들은 교환 가능(exchangeable)합니다. 테스트 점수는 교정 클러스터들과 독립적입니다.
2. 경험적 CDF의 분산: 클러스터 수준의 경험적 CDF를 i.i.d. 평균으로 취급하여 분위수의 경험적 CDF의 분산을 도출합니다. 클러스터 내 지표의 합에 대한 분산은 $1 + (m-1)\rho_I(p)$ 항을 도입합니다.
3. Bahadur 표현식: 분위수에 대한 Bahadur 표현식을 사용하여, 저자는 분위수 오차를 커버리지 확률로 매핑할 때 점수 분포의 밀도가 상쇄됨을 보여줍니다. 이는 매우 중요한 단계로, 커버리지의 분산이 원시 점수의 상관관계나 기저 밀도의 형태가 아니라, 오직 지표의 상관관계에만 의존함을 의미합니다.
4. 한계 법칙 (정리 1): $b \to \infty$일 때, 커버리지 $C$는 다음 분산을 갖는 정규 분포(또는 유한 표본의 경우 일치하는 Beta 분포)로 수렴합니다:
   $$\text{Var}(C) \approx \frac{p(1-p)}{n_{eff}} = \frac{p(1-p)}{n / [1 + (m-1)\rho_I(p)]}$$
   이는 설계 효과가 커버리지의 분산에 대해 표본 크기를 감소시키는 역할을 함을 확립합니다.

확장

• 불규칙한 가족 (Ragged Families, 명제 2): 클러스터 크기가 $m_j$로 불규칙한 경우, $m$을 크기 편향 평균 $\tilde{m} = \frac{\sum m_j^2}{\sum m_j}$로 대체하면 정리가 성립합니다.
• 정보가 있는 크기 (Informative Sizes, 섹션 2.5): 클러스터 크기가 점수와 상관관계가 있는 경우(예: 어려운 질문이 더 긴 추론 경로를 생성하는 경우), 교정 한계(marginal)가 테스트 한계와 달라져, 설계 효과가 교정하지 못하는 1차 편향(first-order bias)이 발생한다고 경고합니다.
• 평균 드리프트 (Mean Drift, 추측 1): 클러스터링 하에서 평균 커버리지는 정확히 명목 수준 $p$가 아니라, $\rho_I(p)$의 미분에 의존하는 $O(1/b)$ 항만큼 드리프트합니다.

3. 주요 기여

1. 초과 설계 효과: 본 논문은 임계값에 대한 유효 표본 크기가 원시 점수의 상관관계($\rho$)가 아니라 초과 지표의 상관관계($\rho_I$)에 의해 결정됨을 증명합니다.
2. 수준 의존성 (Level-Dependence): $\rho_I(p)$가 임계값 수준 $p$의 함수임을 보여줍니다. 즉, 데이터셋은 단일한 유효 표본 크기를 갖는 것이 아니라, 모든 임계값 수준마다 각각의 값을 가집니다. 많은 경우(예: 가우시안 코퓰라), $\rho_I(p)$는 엄격한 커버리지 수준(예: 99%)에서 완만한 수준(예: 90%)보다 감쇠하므로, 설계 효과는 더 엄격한 커버리지 수준에서 더 작아집니다.
3. 표준 보정의 실패: 원시 점수 상관관계 $\rho$를 사용하여 표준 Kish 설계 효과를 적용하는 것이 왜 잘못되었는지 보여줍니다. 많은 현실적인 시나리오에서 $\rho_I(p) < \rho$이며, 이는 설계 효과를 과대평가(데이터 낭비)하거나, 특정 코퓰라 구조에서는 과소평가(안전하지 않은 배포)하게 만듭니다.
4. 불규칙 클러스터 교정: 불규칙한 클러스터 크기에 대해 크기 편향 평균 $\tilde{m}$을 사용하는 올바른 대치법을 제공하며, 평균 클러스터 크기 $\bar{m}$이 불규칙성에 따른 페널티를 현저히 과소평가함을 보여줍니다.
5. 실증적 검증:
   • 공개된 PRM 데이터셋: 공개된 프로세스 보상 모델(PRM) 교정 세트(25,028개 예시)에서, 저자는 약 1,300의 유효 표본 크기를 측정했습니다. 표준 점수 상관관계는 훨씬 더 작은 페널티를 시사했으나, 지표 상관관계는 약 30.8의 설계 효과를 드러냈습니다(정보가 있는 크기 교정 전).
   • 생성된 스윕 (Generated Sweep): 빔 서치 대 독립 샘플링을 사용하여 "공유 조상(shared ancestry)" 메커니즘을 격리하였으며, 빔 서치가 높은 $\rho_I$를 유발하는 반면 독립 샘플링은 그렇지 않음을 보여주었습니다(동일한 프롬프트에 대해서도 조건화된 경우).

4. 결과 및 측정

• 분산 vs 평균: 클러스터링의 주요 영향은 평균(1차 효과)이 아니라 실현된 커버리지의 분산(2차 효과)에 있습니다. 한 번 배포된 시스템은, 평균적으로는 명목 수준을 유지하더라도, 개별 실행 시에는 커버리지가 목표치보다 훨씬 낮을 수 있습니다.
• 오차의 규모: PRM 데이터셋에서 실현된 커버리지 분포는 i.i.d. 예측보다 $4.46\times$ 더 넓었습니다. 커버리지가 0.5 퍼센트 포인트 부족할 확률은 i.i.d.의 경우 1,000건당 0.4건이었으나, 클러스터링된 경우 1,000건당 284.5건으로 증가했습니다.
• 표준 vs 올바른 방식: 원시 점수 상관관계를 사용하여 설계 효과를 추정하는 것은 올바른 지표 기반 법칙보다 최대 $5.7\times$ 더 큰 오류를 범했습니다. 일부 사례(예: SQuAD 2.0)에서는 원시 점수 상관관계가 거의 0에 가까워 교정이 필요 없는 것처럼 보였으나, 지표 상관관계는 양수였으며 상당한 교정이 필요했습니다.
• 꼬리 행동 (Tail Behavior): 꼬리 독립 코퓰라(Gaussian 등)의 경우, 임계값이 꼬리 쪽으로 이동함에 따라 설계 효과가 감소합니다. 꼬리 의존 코퓰라(Student-t 또는 원자 혼합 모델 등)의 경우, 설계 효과는 꼬리 의형 계수(tail dependence coefficient)에 의해 결정되는 하한선에 도달합니다.

5. 의의 및 주장

본 논문은 설문 조사 샘플링 이론과 컨포멀 예측 사이의 간극을 메운다고 주장합니다. 설계 효과, 지표 상관관계, 크기 편향 평균(모두 설문 조사 샘플링, 계량 경제학, 코퓰라 이론에 존재함)과 같은 구성 요소들은 별도로 존재해 왔으나, 본 논문은 이를 클러스터링된 데이터로부터 추정된 임계값을 위한 구체적인 법칙으로 최초로 결합하였습니다.

완곡한 주장:

• 본 논문은 정보가 있는 클러스터 크기(크기와 점수가 상관관계가 있는 경우) 문제를 해결한다고 주장하지 않습니다. 대신 이를 진단하고, 가중 컨포멀 예측(weighted conformal prediction)과 같은 다른 교정이 필요함을 명시합니다.
• 평균 드리프트(추측 1)는 완전히 증명된 정리라기보다, 측정된 잔차(remainder)를 동반한 잘 검증된 추측으로 제시됩니다. 다만 분산 법칙(정리 1)은 증명되었습니다.
• 본 논문은 모든 클러스터링이 나쁘다고 주장하는 것이 아니라, 클러스터링된 세트가 얼마나 많은 "정보"를 보유하고 있는지 정확히 정량화하는 도구를 제공하여, 실무자가 그 트레이드오프를 결정할 수 있게 합니다.

실무적 시사점:

• 실무자는 원시 점수 상관관계에 의존하기보다, 동일 클러스터 쌍으로부터 $\rho_I(p)$를 직접 추정해야 합니다.
• 유효 표본 크기는 단일한 글로벌 숫자가 아니라, 커버리지 수준별로 보고되어야 합니다.
• "깊이를 사는 것"(프롬프트당 더 많은 샘로)은 "너비를 사는 것"(더 많은 프롬프트)에 비해 수익 체감(diminishing returns)이 발생합니다. 왜냐하면 $n_{eff}$는 클러스터 수 $b$에 의해 제한되기 때문입니다.
• 단일 배포의 신뢰성을 해석하기 위해서는 클러스터 수 $b$와 유효 표본 크기 $n_{eff}$를 모두 보고하는 것이 필수적입니다.

결론적으로, 클러스터링의 "피해"는 평균 커버리지 지표에서는 보이지 않지만, 개별 배포에서는 온전히 체감됩니다. 또한 평균을 위한 표준 도구들(Kodik의 공식 등)은 순위 기반 보증(rank-based guarantees)을 제공하는 컨포멀 예측에는 불충분합니다.