Abstract
LLM과 MCTS (Monte Carlo Tree Search)를 혁신적으로 통합한 MCTSr (MCT Self-Refine) 제안
특히 수학적 추론 능력이 크게 향상됨
[arXiv](2024/06/13 version v2)
Preliminary
UCT (Upper Confidence Boundary of Tree)
Self-refine(Project page 설명, 동영상)
용어 정리:
- P: 다루고 있는 문제 인스턴스
- A: P에 대한 잠재적 답변을 나타내는 노드들의 집합
- M: 각 노드에서 사용 가능한 동작들의 집합
- R: 노드들의 자체 보상을 샘플링하는 함수 (자체 보상이란 LLM에게 스스로 자기 답변을 평가하도록 하는 것을 말함)
- Ra: R로 a의 모든 자체 보상 샘플링 결과를 저장하는 집합
- T: 최대 반복 횟수 도달이나 만족스러운 답변 품질 달성 등의 기준에 따라 검색 과정의 종료를 결정하는 함수
- Q(a): a의 가치를 추정하는 함수. R을 통해 도출됨
- U(a): a의 Q 값에 대한 UCT
- Father(a): 부모 노드를 반환하는 함수
- Children(a): 모든 자식 노드 집합을 반환하는 함수
- N(a): a에 대한 방문 횟수
Methodology
MCTSr의 작업 흐름:
- Initialization: 더미 응답으로 루트 노드 설정
- Selection: Q를 통해 가치 높은 노드 선택
- Self-Refine: Self-Refine framework를 사용하여 새로운 노드로써 향상된 답변 a'를 생성
- Self-Evaluation: 답변에 점수를 매겨 Q 값을 계산
- Backpropagation
- UCT update: 모든 노드의 Q 값을 업데이트 후 다음 반복을 위해 UCT 값 업데이트
요약: 기존의 MCTS + LLM 방법은 a가 답변의 일부였다면, MCTSr에서 기존 노드는 기존 답변, 확장된 노드는 향상된 답변이다.
Self-Evaluation
전통적인 MCTS의 Q(s, a)가 상태 s에서 a의 가치를 평가하는 것과 달리, MCTSr의 Q(a)는 자체 보상을 통해 a만 활용하여 평가한다.
Q(a)는 -100 ~ 100 사이의 보상 점수를 제공해야 하며 보상 경향이 지나치게 부드러워 답변 간의 구분이 명확하지 않은 것을 해결하기 위해 3가지 제약을 설계.
- Prompt Constraint: 보상을 매길 때 엄격한 기준을 준수해야 함
- Full Score Suppression: 완전한 점수를 제공하지 않도록 95 이상의 점수는 감소됨
- Repeated Sampling: 보상 샘플링이 자식 노드에서 수행될 때 부모 노드에서도 수행하여 여러 번 샘플링되도록 함
Backpropagation
Q 값을 상위 노드에 전파.
Update UCT and Selection
"완전 확장"을 정의:
- 자식 노드의 한도가 최대일 때
- 자식 노드의 Q 값이 상위 노드의 것을 초과했을 경우
알파고와 비슷한 방법으로 후보 노드 집합에 대한 UCT 업데이트:
Termination Function
종료 기준:
- Early Stopping: 검색 결과의 개선이 줄어들거나 연속적으로 같은 결과가 나올 경우
- Search Constraints: Rollout 수가 제한에 도달하거나 하나 이상의 노드가 최대 깊이에 도달한 경우
- Advanced Criteria Based on Language Model Logits: LLM logits에서 사전 정의된 측정 항목을 기반으로 검색 종료
Evaluation
LLaMA3-8B 사용
GSM dataset
MATH dataset
Olympiad-level dataset
