기술 요약: TsuGO

문제 정의

대규모 언어 모델(LLM) 추론에 대한 기존의 평가는 최종 정답의 정확성에서 과정 수준의 평가로 이동해 왔습니다. 그러나 기존의 과정 수준 방법들은 주로 단일 사고 사슬(Chain-of-Thought, CoT) 궤적의 일관성, 중복성 및 논리적 흐름을 분석하는 데 그칩니다. 이들은 탐색 효율성(Search Efficiency), 즉 모델이 어떻게 추론 경로를 계획하고, 여러 가능성 사이에서 탐색을 조직하며, 경쟁하는 분기들 사이에서 추론 자원(노력)을 어떻게 할당하는지를 포착하는 데는 크게 실패합니다.

대부분의 벤치마크(예: GSM8K, MATH)는 단일 목적을 가진 파생이나 도구 사용과 같은 정적인 능력에 의존하며, 탐색의 조직화는 측정하지 않은 채로 남겨둡니다. 모델이 대안을 탐색하고, 유망한 방향을 식별하며, 백트래킹(backtracking)을 수행해야 하는 복잡하고 적대적인 환경에서, 현재의 평가는 효과적인 탐색 조직화와 유도되지 않은 중복 탐색을 구분할 수 없습니다.

방법론

1. TsuGO 벤치마크

저자들은 **Go 삶과 죽음 문제(tsumego)**를 기반으로 한 과정 수준 벤치마크인 TsuGO를 소개합니다. 이 문제들이 선택된 이유는 다음과 같은 특성을 제공하기 때문입니다:

• 폐쇄적이고 검증 가능한 솔루션 공간: 솔루션은 유한하며 전문가 주석 및 Go 엔진(예: KataGo)을 통해 엄격하게 확인할 수 있습니다.
• 내재된 적대적 구조: 후보 수는 상대방의 가장 강력한 응수에 살아남아야만 유효하므로, 모델은 후보 생성, 변화 읽기(variation reading), 분기 비교, 백트래킹을 수행하도록 강제됩니다.
• 지식과 탐색의 분리: 솔루션 공간을 제한함으로써, TsuGO는 도메인 지식(Go 규칙)과 탐색 과정 자체의 조직화를 분리합니다.

데이터셋 구축:

• 검증된 1,500개의 tsumego 문제(15K에서 7D 난이도 범위)를 선별하였습니다.
• 기호 좌표, 그리드 행렬, 시각적 이미지 및 이들의 조합 등 다섯 가지 양상(modality)으로 정규화되었습니다.
• 다음 두 가지 조건 하에서 평가됩니다:
  • K=4 (제한적): 모델이 제공된 네 개의 후보(하나의 정답과 세 개의 방해 요소) 중 최선의 수를 선택합니다.
  • K=None (개방형): 모델은 후보 힌트 없이 전체 판 위에서 수를 생성, 비교 및 정당화해야 합니다.

2. 과정 탐색 트리 프레임워크

탐색 조직을 평가하기 위해, TsuGO는 자유 형식의 CoT 출력을 구조화된 과정 탐색 트리(Process Search Tree) $T = (V, E, \tau)$로 파싱합니다:

• 노드: 루트(초기 상태), 액션 노드(제안된 수), 평가 노드(최종 판단: 승/패/미결정).
• 추출: LLM 기반 추출기가 원자적 단계(후보 탐색, 변화 읽기, 위치 평가, 백트래킹)를 식별하고 시간적 순서를 보존하면서 트리를 구축합니다.
• 검증: 구조적 검증을 통해 잘 형성된 트리를 보장하며, 중복된 액션을 병합하고 모호한 분기를 처리합니다.

3. 지표

본 벤치마크는 전통적인 **토큰 효율성(TokenE)**과 함께 **탐색 효율성(SearchE)**을 도입합니다:

• SearchE: 세 가지 신호를 집계한 복합 점수입니다:
  • 탐색 낭비 비율 (Search Waste Ratio, SWR): 잘못된 분기에 소비된 자원의 비율.
  • 탐색 첫 발견 (Search First Hit, SFH): 정답 후보 분기가 먼저 탐색되는지 여부.
  • 탐색 정답 순위 (Search Correct Rank, SCR): 탐색 순서에서의 정답 후보 순위.
  • 공식: $SearchE = 100 \cdot (0.5(1-SWR) + 0.3 \cdot SFH + 0.2(1-SCR))$.
• TokenE: 관찰 가능한 토큰 비용에 의해 정규화된 정확도 ($A / (A + ITT/1000)$).
• 진단: 궤적 지표(최대 깊이, 팬아웃, 노드 수) 및 규모 지표(총 토큰 수)를 포함합니다.

주요 결과

다양한 최첨단 LLM(Kimi-K2.5, Qwen3-VL, DeepSeek-R1, GLM-4.6V, Gemini 모델 포함) 및 비-LLM 베이스라인(MCTS/UCT 및 KataGo)을 대상으로 실험을 수행했습니다.

1. LLM은 유도된 탐색에 뒤처짐: 가장 강력한 LLM조차 안정적인 tsumego 해결에는 미치지 못합니다. 일부 설정에서는 유도되지 않은 MCTS보다 성능이 뛰어나지만, 신경망 유도 방식인 KataGo보다는 현저히 약합니다.
2. 탐색 조직화가 병목 구간임:
   • K=4 vs. K=None: 제한적 탐색(K=4)에서 개방형 탐색(K=None)으로 넘어갈 때 성능이 크게 저하됩니다. 강력한 모델은 정답 후보를 더 빨리 찾아내고 생산적인 분기에 노력을 지속함으로써 성공하지만, 많은 모델은 신경 유도 알고리즘보다는 유도되지 않은 탐색 알고리즘에 가깝게 행동합니다.
   • 토큰 효율성 $\neq$ 탐색 효율성: 더 긴 CoT나 더 높은 토کن 효율성이 반드시 더 나은 탐색을 의미하지는 않습니다. 일부 모델은 긴 토큰 효율적 궤적을 생성하지만, 구조적으로 확산되어 있으며 정답 분기에 자원을 할당하는 데 실패합니다.
3. SearchE가 정확도와 더 잘 상관됨: SearchE는 TokenE보다 작업 성공과 더 일관되게 정렬됩니다. TokenE는 낮은 토큰 비용이 효과적인 탐색을 보장하지 않기 때문에 분산되는 반면, SearchE는 자원이 솔루션을 향해 어떻게 할당되는지를 직접 측정합니다.
4. 실패 모드: 분석 결과, 실패는 도메인 지식의 부족보다는 탐색 자원 할당 문제에서 기인하는 경우가 많았습니다. 모델들은 자주 다음과 같은 현상을 보입니다:
   • 올바른 로컬 분기로 진입하는 데 실패함.
   • 약한 로컬 라인을 결정적인 것으로 받아들임.
   • 다단계 라인 진행 중 좌표/상태 유지에서 이탈함.
   • 유망한 강수(forcing branches)를 조기에 종료하거나 포기함.

의의 및 주장

본 논문은 탐색 효율성과 추론 자원 할당이 현재 LLM 추론 평가에서 누락된 차원이라고 주장합니다.

• 결과 정확도를 넘어: TsuGO는 최종 답변이나 단일 궤적의 일관성만을 평가하는 것이 복잡하고 적대적인 문제를 해결하는 모델을 이해하는 데 불충분함을 보여줍니다.
• 진단적 가치: 자유 형식의 궤적을 과정 탐색 트리로 변환함으로써, TsuGO는 추론 노력이 어디에 소비되는지에 대한 진단적 피드백을 제공하며, 후보 생성, 분기 비교, 백트래킹에서의 병목 현상을 식별합니다.
• 미래 방향: 결과는 향end LLM 추론의 개선이 단순히 최종 답변이나 유창한 근거를 넘어, 탐색 조직화(예: 분기 우선순위 지정, 상대 응수 검증, 상태 유지)를 명시적으로 감독하는 훈련 프레임워크를 필요로 함을 시사합니다.

저자들은 TsuGO가 아직 포화 상태가 아니라고 결론짓습니다. 최첨단 모델들조차 전문화된 탐색 알고리즘에 비해 상당한 탐색 조직화 격차를 보이고 있으며, 이는 자율적 추론을 위한 미래 연구의 중요한 영역임을 강조합니다.