ToT, GoT 정리

2025.02.11 - [인공지능/논문 리뷰 or 진행] - Tree of Thoughts: Deliberate Problem Solving with Large Language Models - 논문 리뷰

Tree of Thoughts: Deliberate Problem Solving with Large Language Models - 논문 리뷰

 

기존 CoT 방식은 다양한 사고 흐름을 동시에 탐색하지 않고, 계획이나 예측, 되돌아가기가 없다.

이러한 한계를 극복하기 위해 ToT가 제안 되었고, Thought Decomposition, Thought Generatot, state Evaluator, Search Algorithm을 통해 진행 

Thought Decomposition - 정해놓은 규칙 기반으로 진행 => 우리 Task엔 별로다...

Thought Generator - 샘플링 (독립적 or 문맥으로 유지하며 생성)

State Evaluator - 각 상태에 점수 or 3개 비교하여 순위 

Search Algorithm - BFS, DFS 둘 중 하나 

 

 

https://github.com/princeton-nlp/tree-of-thought-llm

GitHub - princeton-nlp/tree-of-thought-llm: [NeurIPS 2023] Tree of Thoughts: Deliberate Problem Solving with Large Language Mode

이 방법을 쓰진 않을 것 같아서 대충 정리만 하고 넘어가겠습니다.

def solve(args, task, idx, to_print=True):
    # gpt 호출 시 사용할 기본 파라미터 설정
    global gpt
    gpt = partial(gpt, model=args.backend, temperature=args.temperature)
    
    x = task.get_input(idx)  # 문제 입력 x
    ys = ['']                # 현재까지의 thought 시퀀스들 (초기 상태는 빈 문자열)
    infos = []               # 각 step별 탐색 로그 저장용

    for step in range(task.steps):
        # 🧠 1. Thought Generation (다음 단계 후보 생성)
        if args.method_generate == 'sample':
            # Sample 방식: 각각의 thought 후보를 독립적으로 샘플링
            new_ys = [get_samples(task, x, y, args.n_generate_sample, prompt_sample=args.prompt_sample, stop=task.stops[step]) for y in ys]
        elif args.method_generate == 'propose':
            # Propose 방식: 문맥 기반으로 한 번에 여러 thought 후보 제안
            new_ys = [get_proposals(task, x, y) for y in ys]
        
        new_ys = list(itertools.chain(*new_ys))  # 리스트 평탄화
        ids = list(range(len(new_ys)))           # 후보 인덱스 리스트

        # 📊 2. Thought Evaluation (각 후보의 유망도 평가)
        if args.method_evaluate == 'vote':
            values = get_votes(task, x, new_ys, args.n_evaluate_sample)     # 여러 후보 중 투표 방식으로 선택
        elif args.method_evaluate == 'value':
            values = get_values(task, x, new_ys, args.n_evaluate_sample)    # 각 후보를 독립적으로 점수화

        # ✅ 3. Thought Selection (유망한 후보 선택)
        if args.method_select == 'sample':
            # 확률 기반으로 무작위 선택 (탐색 강화)
            ps = np.array(values) / sum(values)
            select_ids = np.random.choice(ids, size=args.n_select_sample, p=ps).tolist()
        elif args.method_select == 'greedy':
            # 점수가 높은 순으로 상위 n개 선택 (활용 강화)
            select_ids = sorted(ids, key=lambda x: values[x], reverse=True)[:args.n_select_sample]

        select_new_ys = [new_ys[select_id] for select_id in select_ids]  # 선택된 후보 시퀀스들

        # 📄 로깅 및 디버깅 출력
        if to_print: 
            sorted_new_ys, sorted_values = zip(*sorted(zip(new_ys, values), key=lambda x: x[1], reverse=True))
            print(f'-- new_ys --: {sorted_new_ys}\n-- sol values --: {sorted_values}\n-- choices --: {select_new_ys}\n')

        # 현재 step 정보를 기록
        infos.append({'step': step, 'x': x, 'ys': ys, 'new_ys': new_ys, 'values': values, 'select_new_ys': select_new_ys})

        # 다음 step에 사용할 후보들을 업데이트
        ys = select_new_ys

    if to_print: 
        print(ys)

    # 최종 후보 thought 시퀀스들과 각 step의 로그를 반환
    return ys, {'steps': infos}

def get_samples(task, x, y, n_generate_sample, prompt_sample, stop):
    # 프롬프트 선택: standard (IO 스타일) 또는 cot (CoT 스타일)
    if prompt_sample == 'standard':
        prompt = task.standard_prompt_wrap(x, y)
    elif prompt_sample == 'cot':
        prompt = task.cot_prompt_wrap(x, y)
    else:
        raise ValueError(f'prompt_sample {prompt_sample} not recognized')

    # GPT에게 여러 샘플 생성 요청
    samples = gpt(prompt, n=n_generate_sample, stop=stop)

    # 기존 thought y 뒤에 새로운 step을 이어붙임
    return [y + _ for _ in samples]

def get_proposals(task, x, y): 
    # 다음 단계 후보들을 제안하는 prompt 생성
    propose_prompt = task.propose_prompt_wrap(x, y)

    # GPT 호출 후 응답을 줄 단위로 분리
    proposals = gpt(propose_prompt, n=1, stop=None)[0].split('\n')

    # 각 후보를 현재까지의 thought y 뒤에 붙임
    return [y + _ + '\n' for _ in proposals]

def get_values(task, x, ys, n_evaluate_sample, cache_value=True):
    values = []
    local_value_cache = {}

    for y in ys:
        if y in local_value_cache:  # 중복 평가 방지
            value = 0
        else:    
            # 각 후보에 대해 value prompt 생성 → GPT 평가 → 수치화
            value = get_value(task, x, y, n_evaluate_sample, cache_value=cache_value)
            local_value_cache[y] = value
        values.append(value)
    return values
    
def get_votes(task, x, ys, n_evaluate_sample):
    vote_prompt = task.vote_prompt_wrap(x, ys)       # 여러 후보를 비교하는 vote prompt 생성
    vote_outputs = gpt(vote_prompt, n=n_evaluate_sample, stop=None)  # GPT로 투표 실행
    values = task.vote_outputs_unwrap(vote_outputs, len(ys))         # 투표 결과를 수치화
    return values

핵심 구조 

입력 x
 ↓
초기 상태 ys = ['']
 ↓
For each step:
    ├─ generate candidates (sample or propose)
    ├─ evaluate candidates (value or vote)
    ├─ select best (greedy or stochastic)
    └─ update ys ← best candidates
 ↓
최종 ys 출력

 

https://arxiv.org/abs/2308.09687

Graph of Thoughts: Solving Elaborate Problems with Large Language Models

 

2025.02.12 - [인공지능/논문 리뷰 or 진행] - Graph of Thoughts: Solving Elaborate Problems with Large Language Models - 논문 리뷰

Graph of Thoughts: Solving Elaborate Problems with Large Language Models - 논문 리뷰