기술 요약: LLM 추론 및 계획용 신규성 기반 트리 오브 생각 (Tree-of-Thought) 탐색

문제 제기

대규모 언어 모델 (LLM) 은 언어 기반 작업에서 상당한 능력을 입증해 왔으나, 복잡한 추론과 장기 계획에서는 여전히 취약합니다. 단순한 프롬프팅은 종종 실패하며, 트리 오브 생각 (ToT) 과 같은 구조화된 접근 방식은 가지치기되지 않은 분기 탐색으로 인해 실행 시간과 토큰 비용이 기하급수적으로 증가하는 문제가 있습니다. 반면, 반복적 너비 (Iterative Width, IW) 와 같은 너비 기반 플래너와 같은 고전적 계획 알고리즘은 '신규성 (novelty)' 측정을 기반으로 상태를 가지치기하여 효율성을 달성하지만, 이들은 자연어 환경으로 잘 이전되지 않는 경직되고 형식화된 문제 구조 (예: PDDL) 를 요구합니다. 본 연구가 해결하는 핵심 과제는 LLM 의 유연성을 희생하지 않으면서 ToT 에서 효율적인 가지치기를 가능하게 하기 위해 비구조화된 언어 영역 내에서 신규성의 유사 개념을 정의하는 것입니다.

방법론

저자들은 ToT 프레임워크에 신규성 기반 가지치기를 통합하는 계획 알고리즘을 제안합니다. 이 접근 방식은 계획 과정을 네 가지 하위 작업으로 분해합니다:

1. 행동 생성: LLM 이 현재 상태에서 가능한 다음 행동을 제안합니다.
2. 후속 상태 매핑: LLM 이 행동을 결과 상태에 매핑합니다.
3. 계획 검증: 모델이 상태 시퀀스가 목표를 만족하는지 판단합니다.
4. 신규성 추정: LLM 이 신규성 추정기로 작용하는 본 연구의 새로운 기여 부분입니다.

신규성 추정 및 가지치기

이진 특징 부분집합을 기반으로 정수로 신규성을 계산하는 고전적 플래너와 달리, 이 방법은 자연어에 맞춰 신규성을 적응시킵니다. LLM 에게 이전에 방문한 상태 목록과 비교하여 새로운 상태가 신규한지 여부를 결정하는 이진 '예/아니오' 질문을 쿼리합니다. 이는 명시적인 원자 정의나 퓨샷 (few-shot) 예시가 필요 없이 모델의 사전 훈련된 일반 지식과 의미적 이해를 활용하여 고유한 상태를 식별합니다.

탐색 트리는 너비 우선 탐색 (BFS) 또는 깊이 우선 탐색 (DFS) 을 사용하여 탐색할 수 있습니다. 고전적 IW 는 일반적으로 BFS 를 사용하지만, 저자들은 LLM 컨텍스트에서는 BFS 가 기하급수적인 비용 증가로 이어질 수 있다고 지적하며, BFS 와 DFS 간의 트레이드오프를 평가합니다. 이 방법은 도메인 규칙을 설명하는 수동으로 제작된 컨텍스트 프롬프트에만 의존하도록 설계되어, 신규성 추정기 자체에 대한 도메인 특화 프롬프트 엔지니어링을 피합니다.

주요 기여

1. LLM 을 위한 신규성 적응: 이 논문은 언어 도메인을 위한 측정 가능한 신규성 개념을 제안하며, LLM 의 내재화된 의미 지식을 활용하여 엄격한 특징 매칭 대신 상태의 고유성에 기반하여 탐색 가지를 가지치기합니다.
2. 도메인 중립적 프레임워크: 도메인 규칙에 대한 컨텍스트 프롬프트 변경만으로 다양한 도메인 (계획 및 추론) 에서 유연한 실험을 가능하게 하는 일반적 구현이 개발되었으며, 이는 최소한의 수동 노력으로 이루어집니다.
3. 하위 작업 평가: 저자들은 Plan-Bench 에서 영감을 받은 전용 평가 프레임워크를 도입하여 네 가지 하위 작업 (행동 생성, 상태 매핑, 검증, 신규성 추정) 을 고전적 플래너가 생성한 정답 (ground truths) 에 대해 독립적으로 테스트합니다.
4. 프롬프팅에 대한 실증적 분석: 이 연구는 프롬프트 설계에 대한 LLM 계획의 민감성을 강조하며, 특히 'pick-up'과 'unstack'을 구분하는 것과 같은 반복되는 실패 지점을 식별하고, 표적 프롬프트 확장이 성능을 어떻게 크게 향상시킬 수 있는지 보여줍니다.

실험 결과

이 접근 방식은 Blocksworld 및 Logistics 계획 도메인과 MATH 벤치마크 (5 단계 난이도) 에서 평가되었습니다.

• 하위 작업 성능: Qwen3 14B 모델을 사용할 때, 'Thinking Mode'(추론 토큰) 와 자연어 프롬프팅이 일반적으로 가장 좋은 결과를 낳았습니다. 모델은 표준 시나리오에서 성공적으로 신규성 가지치기를 수행했으나, 엄격한 너비 기반 추론이 필요한 비중복 상태를 포함하는 더 어려운 변형에서는 어려움을 겪었습니다.
• 토큰 효율성: 잘 구성된 설정 (특히 'Thinking Mode'와 'Direct' 행동/상태 매핑 사용) 에서 신규성 가지치기 ToT 는 유사한 성공률을 유지하면서 표준 ToT 대비 토큰 비용을 최대 20 배까지 절감했습니다. 예를 들어, Blocksworld 에서 DFS 와 Thinking Mode 를 사용할 때, 기본 ToT 는 평균 33 만 토큰을 사용했으나, 신규성 가지치기 버전은 평균 1 만 8 천 토큰을 사용했습니다.
• 일반화 능력: 이 방법은 신규성 추정 프롬프트를 재조정하지 않고도 Logistics 도메인과 MATH 벤치마크로 효과적으로 이전되었으나, MATH 와 같은 다른 추론 도메인에서의 최적 토큰 효율성은 도메인 특화 프롬프트 조정이 필요한 것으로 나타났습니다.
• 한계: poorly configured 설정에서는 성능이 크게 저하되어 해결률이 거의 0 에 수렴했고, 신규성 쿼리의 오버헤드로 인해 토큰 비용이 100% 이상 증가했습니다. 이 방법은 근본적인 ToT 구성의 기본 성능에 크게 의존합니다.

중요성 및 주장

이 논문은 신규성 기반 가지치기가 탐색 공간과 토큰 소비를 극적으로 줄여 복잡한 계획 작업에 ToT 추론의 효율성을 성공적으로 향상시킬 수 있다고 주장합니다. 저자들은 이 방법이 솔루션 품질에 대한 형식적 보장이나 정확한 신규성 계산이 부재하여 고전적 너비 기반 계획과 다르지만, LLM 의 적응력을 활용하는 실용적이고 유연한 대안을 제공한다고 강조합니다.

그러나 저자들은 이 접근법의 견고성에 대해 겸손한 입장을 취합니다. 재귀적 LLM 프롬프팅의 불안정성이 근본적인 과제로 남아 있어 구성이 번거롭고 예측 불가능하다고 지적합니다. 복잡한 시나리오에서 가지치기 행동은 진정한 '신규성' 추론보다는 중복 감지에 크게 의해 주도되는 것으로 관찰됩니다. 따라서 이 연구는 더 효율적인 LLM 계획으로 나아가는 한 걸음으로 제시되며, 목표 직렬화, 대체 신규성 추정기, 또는 상태 이해를 향상시키기 위한 더 큰 기본 모델 사용과 같은 향후 방향을 제안합니다.