고전적 휴리스틱 탐색 문제로서의 Tree of Thoughts: 형식적 기초 및 디자인 패턴

대규모 언어 모델 (LLMs)은 놀라운 추론 능력을 보여주었으나, 이들의 표준 생성 과정인 자기회귀적 토큰 예측 (auto-regressive token prediction)은 본질적으로 근시안적이며 연쇄적인 오류 (cascading errors)가 발생하기 쉽습니다. 이를 해결하기 위해, Tree-of-Thoughts (ToT) 프레임워크는 중간 추론 단계에 대한 탐색 공간 (search space)을 생성하여, 탐색 모델이 탐색 (explore), 앞서 보기 (look ahead), 그리고 되돌아가기 (backtrack)를 할 수 있도록 합니다. 그러나 현재의 ToT 연구는 자연어 처리 (Natural Language Processing) 및 자동 계획 (Automated Planning) 커뮤니티 전반에 걸쳐 파편화되어 있으며, 종종 일관되지 않은 용어와 임시방편적인 (ad-hoc) 구현을 사용합니다. 결과적으로, 우리는 고전적 휴리스틱 탐색 (classical heuristic search) 용어에 기반한 통합된 분류 체계 (taxonomy)를 통해 ToT의 지형을 합성합니다. 우리는 LLM 기반 추론을 고전적 탐색 구성 요소인 상태 표현 (state representation, 사고의 입도), 후속 생성 (successor generation, 프롬프팅 연산자), 그리고 휴리스틱 평가 (heuristic evaluation, 진행 상황에 대한 자기 평가)로 매핑합니다. 우리는 우리의 분류 체계 내에서 기존 연구를 분석하고 다음과 같은 신흥 디자인 패턴을 식별합니다: 얕고 결정론적인 작업을 위한 체계적 탐색 (systematic search, Best-First Search) 및 깊은 다단계 추론을 위한 앞서 보기 중심 전략 (lookahead-heavy strategies, DFS, MCTS). 우리는 휴리스틱 탐색과 LLM 추론의 교차점에서 발생하는 미해결 알고리즘 과제들을 식별하며, 휴리스틱 탐색 커뮤니티가 이 신흥 영역에 참여할 것을 촉구하며 결론을 맺습니다.