CITE: Anytime-Valid Statistical Inference in LLM Self-Consistency

Motivation

• Known: 기존 self-consistency 및 적응적 샘플링 기법(majority voting, posterior agreement, entropy 기반 stopping, confidence-aware voting 등)은 계산 비용을 줄이기 위해 data-dependent stopping rule을 사용하지만, 대부분 정지 시점에서의 오류율을 엄밀하게 통제하지 못하거나 답변 카테고리 집합이 사전에 알려져 있다고 가정한다.
• Gap: 응답 레이블 집합이 무한하고 사전에 알려지지 않은 상황에서, 임의의 data-driven stopping rule 하에서도 특정 target 답변을 유일한 mode로 잘못 인증할 확률(false certification)을 지정된 수준 ε 이하로 통제하는 anytime-valid 방법이 부재하였다.
• Why: 응급실 triage 등 고위험 의사결정에서 LLM 출력을 modal-response certificate로 실제 운용하려면 false-certification probability를 정밀하게 통제해야 하며, 이를 만족하지 못하면 과도한 추론 반복으로 계산 비용이 폭증하므로 정밀하고 효율적인 오류 통제가 실용적으로 중요하다.
• Approach: e-process 기반 testing-by-betting 프레임워크를 활용하여 pairwise 비교, target 확률 하한, 미관측 카테고리 확률 상한이라는 세 가지 조건을 동시에 통제하는 intersection-union 방식의 순차 검정 CITE를 제안한다.

Achievement

Figure 2. Mean accuracy vs. sample budget on Qwen3-30B (top) and gpt-oss-20b (bottom), across AIME 2026, FrontierScience

1. Anytime-valid category-agnostic 오류 보장: 답변 카테고리 집합에 대한 사전 지식 없이도 임의의 stopping time에 대해 균일하게 Type-I error를 ε 이하로 통제함을 증명(Theorem 4.1).
2. Category-size-free stopping-time: CITE의 정지 시간 오더가 카테고리 집합 크기에 무관함을 보이고(Theorem 4.3), 이에 상응하는 minimax lower bound를 도출(Theorem 4.4)하여 주요 영역에서 상수배 차이까지 최적임을 입증.
3. Confidence-weighted voting으로의 확장: 가중 관측치 및 gap을 다루도록 CITE를 확장하고 동일한 anytime-valid 오류 통제 및 정지 시간 속도를 유지함을 증명(Section 5).
4. 실증적 성능 검증: 시뮬레이션과 세 가지 LLM 벤치마크 실험을 통해 CITE가 Type-I error를 경험적으로 통제하며, diffuse-tail 상황에서 기존 baseline과 동등하거나 더 나은 인증 성능을 보임을 확인.

How

Figure 1. Overview of the stopping rule by CITE. With the countably infinite set of categories A, CITE tests the hypothe

• 문제를 fixed-target unique-mode testing으로 정식화: H0,r: pr ≤ sup_{a≠r} pa, H1,r: pr > sup_{a≠r} pa
• Ft-measurable stochastic process 세 가지 Et, Lt, Ut를 정의: (i) Et는 target r과 다른 카테고리 a 간 상대적 크기를 e-process(testing-by-betting)로 평가, (ii) Lt는 pr의 하한을 anytime-valid하게 추정, (iii) Ut는 미관측 카테고리 확률의 상한을 제공
• 세 조건 중 하나라도 위반되면 정지하는 stopping rule을 설계하고, {τ < ∞} ⊆ (i)∪(ii)∪(iii) 형태의 union bound를 이용해 전체 Type-I error를 ε로 통제
• union-intersection testing 구조와 e-process의 martingale 성질(Ville's inequality 등)을 결합하여 시간에 대해 균일한(anytime-valid) 오류 보장을 도출
• 카테고리 집합 크기에 무관한 stopping-time rate를 이론적으로 유도하고 매칭되는 minimax lower bound를 증명
• 가중치가 부여된 관측 및 gap이 있는 경우로 프레임워크를 확장하여 confidence-weighted voting에 적용
• Qwen3-30B, gpt-oss-20b 등 LLM을 이용한 self-consistency 실험 및 시뮬레이션으로 방법을 검증

Originality

• 응답 카테고리 집합이 무한하고 사전에 알려지지 않은 상태에서 anytime-valid sequential testing을 다룬 최초의 시도로, 기존 통계학(Good, 1953; Painsky, 2025) 및 LLM test-time compute 연구(Aggarwal et al., 2023; Li et al., 2024 등)와 차별화됨
• 정답의 correctness가 아닌 "response distribution의 유일한 mode로서의 인증"이라는 독자적인 통계적 보장 개념을 제시
• e-process 기반 intersection-union testing을 세 가지 조건(pairwise, target probability, unseen category)으로 분해하여 category-agnostic한 오류 통제를 달성한 구조적 참신성
• 카테고리 집합 크기에 무관한 stopping-time rate와 이에 대응하는 minimax lower bound를 함께 제시하여 이론적 최적성을 뒷받침

Limitation & Further Study

• i.i.d. categorical sampling(Assumption 2.1)을 가정하고 있어, LLM 실제 샘플링 과정에서 발생할 수 있는 프롬프트-종속적 상관관계나 시간에 따른 분포 변화(non-stationarity)는 다루지 않음
• minimax lower bound가 "주요 영역(main regime)"에서만 상수배까지 일치한다고 명시되어 있어, 다른 영역(예: 매우 낮은 ε이나 극단적 diffuse-tail)에서의 최적성은 불분명
• 실험이 제한된 수의 LLM(Qwen3-30B, gpt-oss-20b)과 벤치마크에 국한되어 있어, 더 다양한 모델·태스크·실제 위험 상황(예: ER-REASON과 같은 고위험 응용)에 대한 광범위한 실증이 필요
• weighted voting으로의 확장이 이론적으로만 제시되었고, confidence score의 신뢰성 자체가 훼손된 경우(calibration 문제)에 대한 강건성은 추가 연구가 요구됨

Evaluation

총평: 무한하고 사전 미지의 카테고리 집합 하에서 anytime-valid하게 오류를 통제하는 최초의 LLM self-consistency 인증 프레임워크로, 이론적 엄밀성과 실용적 함의를 모두 갖춘 견고한 워크숍 논문이다.