[Paper Review] A Theoretical Study on Bridging Internal Probability and Self-Consistency for LLM Reasoning

문제

Sampling 기반 test-time scaling에서 SC와 PPL 모두 이론적 한계가 존재하며, 이를 체계적으로 분석한 프레임워크가 부재합니다.

방안

Reasoning error를 Estimation Error + Model Error로 분해하는 이론 프레임워크를 수립하고, LLM 내부 확률을 SC 프레임워크에 Perplexity Consistency한 뒤 저확률 추론 경로를 Reasoning Pruning하는 RPC 방법을 제안합니다.

주요 기여

Sampling 기반 test-time scaling을 confidence estimation 관점에서 분석하는 최초의 이론 프레임워크 제시

SC와 PPL 각각의 한계를 Estimation Error / Model Error 관점에서 정량적으로 규명

두 방법의 장점을 결합한 RPC 제안 — 추정 오차 수렴을 선형에서 지수적으로 가속하면서 모델 오차를 낮게 유지

배경 및 동기

기존 방법의 접근

Consistency 기반 방법 (Ex, Self-Consistency)

동일한 문제에 대해 n개의 reasoning path를 샘플링

Majority vote로 가장 빈번한 답을 선택

Monte Carlo 추정으로 confidence를 계산

Probability 기반 방법 (Ex, Perplexity)

LLM이 생성한 각 reasoning path의 내부 확률 을 직접 활용

확률이 높은 path를 더 신뢰할 만한 것으로 간주

문제점 및 병목

1. Self-Consistency의 느린 수렴

Monte Carlo 추정에 의존하기 때문에 추정 오차가 으로만 감소합니다

샘플 수가 적을 때 성능이 불안정합니다

예: 충분한 성능을 내려면 64~128개의 샘플이 필요한데, 이는 비용이 큽니다

2. Perplexity의 높은 모델 오차

LLM 내부 확률을 직접 사용하지만, 이 확률 자체가 정답 확률과 괴리가 있습니다

특히 확률 값이 매우 낮은 reasoning path에서 수렴 성능이 급격히 degradation합니다

3. 두 방법 모두 개선 여지 존재

SC: 수렴은 느리지만 모델 오차가 낮습니다

PPL: 수렴은 빠르지만 모델 오차가 높습니다

두 장점을 동시에 달성하는 방법이 가능할 것이라는 이론적 근거가 있습니다

근본 원인

두 방법의 한계는 confidence estimation 전략의 근본적 차이에서 비롯됩니다. SC는 순전히 빈도 기반이라 정보를 충분히 활용하지 못하고, PPL은 확률을 직접 쓰지만 관측되지 않은 path에 대한 처리가 부재합니다. 최적의 방법은 빠른 추정 오차 수렴과 낮은 모델 오차를 동시에 달성해야 합니다.

핵심 방법

이론 프레임워크: Reasoning Error 분해

이 논문의 이론적 토대는 reasoning error를 두 개의 독립적 성분으로 분해하는 것입니다.

문제 정의

추론 문제 에서 는 입력 쿼리, 는 정답입니다. LLM은 reasoning path 을 순차적으로 생성하며, 추출 함수 이 최종 답 를 도출합니다.

Confidence: reasoning path 의 생성 확률 , 또는 답 의 확률

실제로는 모든 가능한 path를 열거할 수 없으므로, 개의 샘플 으로 confidence를 추정합니다.

Proposition 1: Error Decomposition (핵심 정리)

임의의 입력 , 정답 , 가능한 답 에 대해, reasoning error 는 다음과 같이 분해됩니다:

각 항의 의미:

Estimation Error: 추정된 confidence 와 실제 확률 사이의 차이. 샘플 수 과 추정 전략에 의존합니다.

Model Error: LLM이 부여한 실제 확률 와 정답 지시함수 사이의 차이. LLM의 추론 능력 자체에 의존하며, 샘플링과 무관합니다.

기존 방법들의 한계를 각각 어떤 오차 성분 때문인지 자세하게 진단할 수 있게 해주기 때문에 분해가 중요합니다.

SC의 이론적 분석

Proposition 2: SC Reasoning Error Decomposition

SC의 confidence 추정:

핵심 관찰:

Estimation Error가 — 즉 선형적으로만 감소합니다

샘플 수를 2배 늘려야 오차가 절반이 되는, 효율이 낮은 구조입니다

다만 Model Error는 SC의 consistency function 특성상 상대적으로 낮습니다

PPL의 이론적 분석

Proposition 3: PPL Reasoning Error Decomposition

PPL의 confidence 추정:

핵심 관찰:

Estimation Error에 항이 포함되어 지수적으로 감소합니다

하지만 이면 이 되어 수렴이 퇴화합니다

Model Error가 SC보다 일반적으로 크며, path-level 확률과 정답 여부의 괴리가 원인입니다

전체 아키텍처: RPC 방법


입력 문제 x
  → LLM Sampling: n개의 reasoning path 생성
  → Reasoning Pruning (RP): 저확률 path 제거
  → Perplexity Consistency (PC): 남은 path로 confidence 추정
  → 최종 답 선택

모듈 1: Perplexity Consistency (PC)

LLM 내부 확률을 SC 프레임워크에 통합하여, PPL의 빠른 수렴과 SC의 낮은 모델 오차를 동시에 달성합니다.

핵심 공식

고유한 reasoning path 집합 에 대해, 임의의 답 의 추정 확률,

SC와의 차이점을 명확히 하면,

SC: 답이 인 path의 개수를 세서 으로 나눕니다 (빈도 기반)

PC: 답이 인 path의 확률을 합산합니다 (확률 가중)

Theorem 4: PC Reasoning Error Decomposition

(답이 인 고유 path 수), 로 정의하면:

PC의 이점:

Estimation Error 수렴율: 으로 지수적 수렴 — PPL과 동급

Model Error: SC와 동일한 형태 — SC와 동급

즉, PC는 PPL의 빠른 수렴과 SC의 낮은 모델 오차를 모두 달성합니다.

수렴 퇴화 문제 존재.

모듈 2: Reasoning Pruning (RP)

저확률 reasoning path를 사전에 제거하여 PC의 수렴 퇴화 문제를 방지합니다.

기본 아이디어

확률 가 매우 낮은 답 는 정답일 가능성이 희박합니다. 이런 path의 존재가 PC의 수렴 속도를 끌어내리므로, threshold 이하의 누적 확률을 가진 답을 제거합니다:

Theorem 7: Pruning의 효과 보장

최적 threshold (정답의 실제 확률)로 설정하면, RP는 다음 확률 이상으로 최적의 오차 감소를 달성합니다:

여기서 는 답이 인 샘플 수입니다.

이는 model error 자체도 효과적으로 감소시킵니다. 잘못된 답에 할당된 확률을 제거하기 때문입니다.

자동 Threshold 결정: Weibull Mixture Model

argus_poster_weibull.pdf

48.9 KiB

세 방법의 이론적 비교 요약

측면	Self-Consistency (SC)	Perplexity (PPL)	RPC (PC + RP)
Estimation Error 수렴	선형	지수적	지수적
Model Error	낮음	높음	낮음 (SC 수준)
저확률 path 대응	자연 처리	수렴 퇴화	RP로 제거
Confidence 해석	빈도 기반 (직관적)	확률 기반 (편향 가능)	확률 가중 빈도 (균형적)
필요 샘플 수	많음 (64-128)	적음	SC 대비 50% 이하

실험 분석

1. 효율성 (RQ1): 샘플링 비용 50% 이상 절감

MathOdyssey에서는 71.4%의 샘플링 절감이 이루어졌습니다. 이는 이론에서 예측한 PC의 지수적 수렴 속도가 실제로 작동함을 보여줍니다.

2. 성능 (RQ2): 동일 샘플 수에서 최고 정확도

RPC는 기존 방법 대비 평균 1.29% 향상을 달성했으며, 모든 데이터셋에서 최고 성능을 기록했습니다.

3. 신뢰성 (RQ3): ECE(Expected Calibration Error) 감소

방법	MATH ECE	MathOdyssey ECE	OlympiadBench ECE	AIME ECE	평균 ECE
PPL	48.99	67.70	86.90	88.98	73.14
VERB	47.46	69.92	84.68	86.29	72.09
SC	6.71	12.23	20.20	14.35	13.37
RPC	6.41	9.87	18.86	14.32	12.37

RPC의 confidence 추정이 실제 정답률과 더 잘 calibration 되어 있습니다.

4. 코드 생성 태스크에서도 유효

Deepseek-Coder 33B 모델로 코드 생성 벤치마크에서도 RPC가 최고 성능을 달성하여, 수학 추론에 국한되지 않는 범용성을 확인했습니다.

한계

Bernoulli 가정 의존: 이론 분석이 LLM 샘플링이 Bernoulli 분포를 따른다는 가정에 기반합니다. 실제 LLM 생성은 더 복잡한 분포를 보일 수 있습니다.

Weibull Mixture 피팅 불안정: 샘플 수가 매우 적을 때(n < 16) mixture model 피팅이 불안정해질 가능성이 있으며, Truncated Mean으로 완화하지만 근본적 해결은 아닙니다.

긴 reasoning chain에서의 확률 추정: path가 매우 길어지면 내부 확률 의 값이 극도로 작아져, 수치적 안정성 문제가 발생할 수 있습니다.