[Origin]
[Summary]
ToT 프롬프트 방식 평가
[Contents]
[Abstract]
ToT라는 방법 소개
현재 언어 모델의 left-to-right 방식을 해결할 수 있는 방식 제시
left-to-right 방식의 문제란?: exploration, strategic lookahead, where initial decisions play
a pivotal role을 사용하는 곳에서 한계점을 가진다.
[introduction]
현재의 언어 모델
original autoregressive mechanism에 기반한 모델(token level decision one-by-one, left-to-right)은 성공적인 결과를 이루어 내었다.
이 메커니즘만이 언어모델을 해결할 수 있을까? → 새로운 메커니즘을 제안해 보자.
인간 인지를 바탕으로한 새로운 메커니즘: Dual Mode
인간은 인지를 위해서 dual mode를 사용한다.
- System1: fast, automatic, unconscious mode
- System2: slow, deliberate, conscious mode
현재의 토큰 수준의 간단한 모델은 system1로 해석할 수 있으며, system2로 언어 모델이 더 신중할 수 있도록 보완할 수 있다.
ToT
언어 모델 문제를 해결하기 위한 새로운 프레임 워크
이 프레임 워크를 통해서 밑의 세 가지 문제(deductive, mathematical, commonsense, lexical reasoning abilities, and a way to incorporate systematic planning or search를 요구하는)를 시험해볼 것이다.
[Background]
기존의 언어 모델
사전에 학습된 모델: p_theta
theta: 파라미터
x,y,z: 언어 시퀀스 (x[i] 등.. 은 토큰)
⇒ “문장 하나에 대한 확률을 만든다”라고 생각하면 될 듯
Input-Output prompting: 입력을 출력으로 바꾸는 방법
입력이 일어났을 때의 출력의 조건부 확률로 표현할 수 있다.
Chain-of-thought (CoT) Prompting ⇒ 그림(1) 참고
x와 y가 non-trivial 문제일 때 사용하는 방법이다. (ex. x가 수학 문제이고, y가 그 문제에 대한 정답일 때)
이 때는 x와 y사이를 연결 짓기 위해서 z 시퀀스(z는 ex. 수학 방정식)를 도입한다.
참고 자료
Self-consistency with CoT (CoT-SC): CoT의 앙상블 메서드(CoT에 다양한 결과 추가) ⇒ 그림(1) 참고
다양한 z 시퀀스를 도입한다. (= 한 문제에 대한 다양한 풀이 법을 도입한다)
[Tree of Thoughts: Deliberate Problem Solving with LM]
인간 문제 풀이에 대한 연구는 사람들이 combinatorial problem space를 탐색한다는 걸 제안한다.
tree의 node는 partitial solution을 의미한다. branch는 operator를 의미한다. 문제 해결 과정은 어느 가지를 선택할 지를 의미한다.
→ 또한 이것은 기존의 LM에서의 두 가지 한계점을 지적한다.
1) 기존 LM은 다른 가능성을 확인하지 않는다.
2) lookahead, backtracking 등의 도움이 되는 옵션을 수행하지 않는다.
ToT(CoT의 업그레이드 버전)는 이러한 기존 LM의 결점을 해결할 수 있다.
LM이 여러 경로를 탐색할 수 있도록 돕는 패러다임이다. → CoT-SC와 같이..
→ 그러나 CoT는 단순히 투표 많이 받는 경로를 고르는 것이라면, ToT는 노드를 탐색하면서 결과를 얻는다.
Partial sol을 위한 state s = [x,z1···i]를 찾는 검색 알고리즘 프레임이다.
핵심은 다음 네 가지이다.
1) 중간 단계, 생각 단계 (z)를 어떻게 분해할 것인가
2) Potential thought를 어떻게 설정할 것인가
3) state를 어떻게 평가할 것인가
4) 검색 알고리즘은 어떤 걸 사용할 것인가
[Thought decomposition]
ToT는 명시적으로 생각들을 sampling 한다.
→ 문제의 특성을 고려하여 중간 단계 생각을 sampling 한다.
→ CoT와의 차이 그림(1)보고 이해하기 → ToT는 생각을 분해한다.
→ 생각들은 수식이 될 수도 있고, 단어일 수도 있고, ….
그림
[Thought generator]
생각을 생성하기 위한 두 가지 전략
- Sample(Cot prompt): CoT를 활용해서 i.i.d한 생각을 생성 → Creative Writing
- Propose(Propose prompt): 순차적으로 생각을 생성 → Game of 24, Cross words
[State evaluator]
현재 상태가 얼마나 정답에 가까운지에 대한 평가
- Value: 각 상태를 독립적으로 평가
- Vote: 투표
[Search algorithm]
Tree에서의 탐색 알고리즘
- BFS
- DFS
ToT의 장점
(1): Generality: I/O, CoT, CoT-SC는 모두 ToT의 특수한 형태로 볼 수 있다(i.e. trees of limited depth and breadth).
(2): Modularity: decomposition, generation, evaluation, search procedure을 모듈로써 볼 수 있다.
(3): Adaptability: 다양한 문제 특징을 수용할 수 있다.
(4): Convenience: 추가적인 학습이 필요하지 않다.
[Experience]
GPT-4에서 CoT, IO로 해결하기 어려운 세 가지 문제를 제시
[Game-24]: Propose Prompt
수학적 추론 문제
주어진 4개의 숫자를 이용해서 주어진 1개의 목표 숫자를 만드는 것
Task Setup
100개 문제에 대한 정답률로 Prompt 방식 평가
Baseline
- I/O: 입력-출력 쌍
- CoT: 입력-세 개의 중간 방정식(생각)-출력
- CoT-SC: 100개의 CoT를 바탕으로한 CoT-SC를 만들어서 성능 개선
ToT Setup
(a)
- 각 노드에는 계산 결과 + 남은 수 ex. 4+9 = 13, 10,13,13 → 13이 두 개인 이유는 우리가 13을 계산 결과로 얻었기 때문에 추가로 또 쓸 수 있기 때문이다.
- 5개의 후보를 유지 (anti-chain에서 5개 고른다는 의미인 것 같다)
(b)
- sure/likely/impossible로 나눈다.
- 3번씩 sampling
Result
Error Analysis
- left to right decoding 문제
[Creative Writing]: CoT Prompt
창의적 글쓰기 문제
4개의 입력 문장에 대해서 4개의 입력 문장으로 끝나는 네 개의 단락 구성하기
Task Setup
- 100개의 무작위 질문 입력
- 출력에 대해 zero-shot prompting을 활용하거나 인간을 통해 점수를 매긴다.
Baseline
IO/CoT가 어떻게 하는지.. → zero-shot으로 학습 (unseen data로 학습) (질문: CoT 자체가 few-shot prompting 아닌가?) → 아 .. 중간 계획은 ‘미리’ 알려주고, 그 이후에는 zero shot 하는듯
ToT Setup
이런식으로 setup된다.
Result
ToT model이 더 일관성을 보였다.
Error Analysis
[Mini crosswords]: Propose Prompt
위의 두 예시 보다 ToT가 깊은 예시
Task Setup
GooBix 바탕으로 셋 업
Baseline
5개 input
ToT Setup
DFS로 탐색
Result
Error Analysis
[Discussion]
[Limitations and future directions]
GPT가 이미 좋은 성능을 나타내는 분야에는 필요없다.
sampling 방법과 다르게 GPT API를 사용해야 한다.
[Conclusion]
LM의 한계점을 해결하는 법을 제시