Probabilistic Chain-of-Thought: Sequential Bayesian Inference over Latent Reasoning Correctness

Motivation

• Known: Chain-of-thought prompting은 LLM의 multi-step reasoning을 이끌어내는 데 효과적이며, process reward model(PRM)이나 self-consistency 등 step-level confidence를 활용한 방법들이 존재한다. 하지만 이들 대부분은 각 step의 confidence score를 독립적 신호로 간주하고 product, minimum, position-weighted sum 같은 heuristic으로 결합한다.
• Gap: 자기회귀적 생성 과정에서는 이전 step의 오류가 이후 step에 전파되어 영향을 미치므로, step correctness를 독립적으로 취급하는 것은 실제 생성 과정과 모순되며 miscalibrated aggregate confidence와 비최적 reflection 결정을 초래한다. 기존 연구에는 이러한 sequence-level 오류 전파를 원칙적으로 포착하고 교정할 메커니즘이 없었다.
• Why: 수학적 추론에서 하나의 중간 단계 오류가 전체 도출 과정을 은밀히 무효화할 수 있기 때문에, 신뢰할 수 있는 answer-level confidence 산출과 적절한 reflection 시점 결정은 신경망 기반 수학적 추론 시스템의 신뢰성 확보에 필수적이다.
• Approach: reasoning chain의 latent step-correctness 변수들을 first-order Hidden Markov Model로 모델링하고, Beta emission distribution과 forward-backward algorithm을 이용해 exact marginal posterior πi를 계산함으로써 원칙적인 answer confidence Cfinal과 posterior-driven reflection threshold를 도출한다.

Achievement

Figure 3. Accuracy vs. token budget (relative to no-reflection

1. ECE 대폭 감소: MATH와 GSM8K에서 PCoT는 기존 최선의 heuristic baseline 대비 Expected Calibration Error를 74% 감소시켰다.
2. 정확도 향상: 동일한 2× token budget 조건에서 정확도를 14.7 percentage point 향상시켰다.
3. estimator에 대한 강건성: 세 가지 서로 다른 confidence estimator에 대해서도 일관되게 우수한 성능을 보였다.
4. sequential contamination의 이론적 규명: 하나의 upstream 오류가 모든 downstream step의 posterior를 억제한다는 현상을 formal proposition으로 증명하여, point-wise step scoring이 왜 불충분한지 설명했다.
5. posterior-driven reflection policy 도출: closed-form 최적 reflection threshold τ*_i를 유도하고, 이것이 어떤 raw-score threshold rule보다도 모델 하에서 우월함을 증명했다.

How

Figure 1. Reliability diagrams on the PRM800K test set. Each bar

• reasoning chain S=(s1,...,sn)의 latent binary correctness 변수 Zi를 정의하고, 관측 confidence score ci는 quantile-regression recalibration을 거친 후 Zi=1/0 조건에서 각각 Beta(α1,β1), Beta(α0,β0) emission distribution을 따르도록 설정
• 오류 전파를 포착하기 위해 transition model P(Zi=1|Zi-1=z)를 persistence probability λ와 error-recovery probability ϵ로 파라미터화하고 PRM800K 데이터로부터 파라미터를 추정
• forward-backward algorithm을 통해 O(n) 시간 내에 marginal posterior πi = P(Zi=1|c)를 계산하고, 전체 경로가 정답일 posterior 확률을 Cfinal로 정의
• Proposition 3.4(sequential contamination)를 통해 upstream 오류 관측이 downstream posterior를 단조적으로 억제함을 monotone-likelihood-ratio 조건 하에서 증명
• Proposition 3.5, 3.6을 통해 위치 의존적 최적 reflection threshold τ*_i를 closed-form으로 유도하고 raw-score threshold rule 대비 지배성을 증명
• MATH, GSM8K 데이터셋과 PRM800K annotation을 이용해 ECE, 정확도, token budget 대비 성능을 heuristic baseline과 비교 평가

Originality

• step correctness를 독립 신호가 아닌 first-order Hidden Markov Model의 latent state로 모델링하여 sequential dependence를 명시적으로 포착한 최초의 프레임워크
• confidence score를 관측된 token이 아닌 calibrated emission으로 취급하여 HMM을 LLM reasoning chain 분석에 적용한 새로운 시도
• sequential contamination이라는 현상을 공식적으로 정의하고 monotone-likelihood-ratio 기반 증명으로 이론적 근거를 제시
• posterior 기반 reflection threshold의 optimality를 closed-form proposition으로 증명하여 heuristic threshold rule과의 이론적 우열관계를 명시

Limitation & Further Study

• 첫 번째 order Markov 근사(P(Zi|Z1:i-1,x)≈P(Zi|Zi-1,x))는 tractability를 위한 것으로, 실제로는 더 복잡한 장거리 의존성이 존재할 수 있음
• 최종 answer correctness를 Zn(마지막 step)만으로 결정하는 terminal-state assumption은 지나치게 단순화되어 있으며, 다중 step 또는 majority correctness에 기반한 richer answer model이 필요
• binary correctness(Zi∈{0,1}) 가정은 ordinal 또는 다단계 정확도로 확장 가능하나 본 논문에서는 이를 다루지 않음
• 평가가 MATH, GSM8K 등 수학적 추론 도메인에 국한되어 있어 다른 유형의 reasoning task(상식 추론, 코드 생성 등)에 대한 일반화 가능성은 검증되지 않음
• emission 및 transition parameter 추정이 PRM800K annotation에 의존하므로, annotation 품질과 도메인 특성에 따라 성능이 달라질 수 있음

Evaluation

총평: HMM 기반 exact posterior inference를 통해 step-level confidence의 독립성 가정을 이론적, 실증적으로 반박하고 실질적인 성능 향상을 보인 견고한 연구로, 수학적 추론 신뢰성 평가에 새로운 관점을 제시하지만 terminal-state assumption과 first-order 근사 등 단순화 가정의 확장 여지가 남아 있다.