DeepSearch: 검증 가능한 보상을 가진 강화학습의 병목 현상을 극복하기 위한 트리 기반 검색

이 논문은 DeepSearch라는 새로운 프레임워크를 제안하며, 이는 언어 모델의 추론 능력을 향상시키기 위해 검증 가능한 보상을 이용한 강화학습 (RLVR) 훈련 과정에 몬테카를로 트리 검색 (MCTS) 을 직접 통합한 방법론입니다. 기존 연구들이 추론 (Inference) 단계에서만 검색을 활용하는 반면, DeepSearch 는 훈련 단계 자체에 구조화된 탐색을 내재화하여 RLVR 의 성능 정체 (Plateau) 문제를 해결합니다.

다음은 논문의 핵심 내용을 요약한 기술적 분석입니다.

1. 문제 정의 (Problem Statement)

• RLVR 의 한계: 최근 언어 모델 (LLM) 의 복잡한 추론 능력 향상을 위해 검증 가능한 보상 (예: 수학 문제의 정답 여부) 을 이용한 강화학습 (RLVR) 이 필수적이 되었습니다. 그러나 기존 RLVR 접근법은 훈련 중 희소 탐색 (Sparse Exploration) 패턴에 의존합니다. 모델이 제한된 롤아웃 (Rollout) 만을 수행하여 중요한 추론 경로를 놓치거나, 해답 공간을 체계적으로 커버하지 못합니다.
• 성능 정체: 기존 연구들은 훈련 단계를 늘리는 것 (Brute-force scaling) 으로 성능을 향상시키려 했지만, 수천 단계의 최적화 이후 성능이 정체되는 현상이 관찰되었습니다. 이는 단순히 계산 자원을 늘리는 것만으로는 RLVR 의 잠재력을 완전히 끌어낼 수 없음을 시사합니다.
• 훈련과 추론의 분리: 기존 방법론들은 구조화된 검색 (Tree Search) 을 추론 단계에만 국한시켰으며, 훈련 과정에는 통합하지 않아 모델이 체계적인 탐색 과정을 학습할 기회를 박탈했습니다.

2. 방법론 (Methodology: DeepSearch)

DeepSearch 는 MCTS 를 훈련 루프에 직접 통합하여 훈련 중 탐색 (Training-time Exploration) 을 가능하게 합니다. 주요 구성 요소는 다음과 같습니다.

2.1. 엔트로피 기반 확장 (Expansion with Entropy-Based Guidance)

• 현재 상태 (관측치) 에 기반하여 정책 모델이 다음 추론 단계의 후보들을 생성합니다.
• 최신한 오류 선택 전략: 정답이 없는 경우, 무작위 오류가 아닌 가장 확신 있는 오류 (Most Confident Incorrect) 를 선택합니다. 이는 경로 전체의 평균 엔트로피가 가장 낮은 (모델이 가장 확신하지만 틀린) 추론 경로를 식별하여, 모델이 가장 많이 실수하는 부분을 집중적으로 학습하도록 유도합니다.

2.2. 휴리스틱 점수 백업 (Heuristic Score Backup)

• 선택된 경로 (정답 또는 가장 확신 있는 오답) 에 대해 노드별 Q-value 를 업데이트합니다.
• 비대칭 업데이트 규칙: 정답 경로에 속한 노드는 Q-value 가 음수가 되지 않도록 제약하며, 오답 경로의 노드는 적절한 페널티를 부여합니다. 이는 잘못된 추론 경로를 학습하되, 한 번 정답 경로로 확인된 노드가 실수로 인해 부정적인 평가를 받지 않도록 보장합니다.
• 깊이 감쇠 함수: 터미널 노드에서 가까운 노드일수록 더 높은 가중치를 부여하여 최종 결과에 대한 책임을 명확히 합니다.

2.3. 하이브리드 선택 전략 (Hybrid Selection Strategy)

기존 MCTS 의 UCT(Upper Confidence Bounds for Trees) 알고리즘은 국소적 (Local) 탐색에 치우칠 수 있어, DeepSearch 는 이를 보완한 글로벌 프런티어 선택 (Global Frontier Selection) 을 도입했습니다.

• 국소 선택 (Local Selection): 동일한 부모 노드를 가진 형제 노드 간 비교에는 전통적인 UCT 를 사용합니다.
• 글로벌 프런티어 선택: 전체 검색 트리에 걸쳐 다음 확장을 수행할 가장 유망한 노드를 선택합니다.
  • 품질 잠재력 (Quality Potential): 부모 노드의 높은 가치 반영.
  • 불확실성 보너스 (Uncertainty Bonus): 정책의 엔트로피를 기반으로 탐색 영역 조정.
  • 깊이 보너스 (Depth Bonus): 더 깊은 탐색을 장려.
  • 이 전략은 국소 최적해에 갇히는 것을 방지하고 계산 자원을 전역적으로 효율적으로 분배합니다.

2.4. 적응형 훈련 전략 및 재생 버퍼 (Adaptive Training with Replay Buffer)

• 점진적 필터링: 모델이 쉽게 해결하는 문제는 훈련 세트에서 제외하고, 여전히 실패율이 높은 '어려운 문제 (Hard Subset)'만 선별하여 MCTS 계산 자원을 집중합니다.
• 캐싱된 솔루션 재사용: MCTS 를 통해 정답을 찾은 문제는 재생 버퍼에 저장합니다. 이후 훈련에서는 이 캐싱된 정답 경로를 직접 활용하고, 새로운 MCTS 탐색은 해결되지 않은 문제에만 적용합니다. 이는 불필요한 계산을 줄이고 효율성을 극대화합니다.
• Tree-GRPO 목적 함수: 트리 구조의 추론 흔적 (Trace) 에서 노드 수준의 이점 (Advantage) 을 계산하여 정책 최적화를 수행합니다.

3. 주요 기여 (Key Contributions)

1. 훈련 중 MCTS 통합: 추론 단계가 아닌 훈련 단계 자체에 체계적인 탐색을 도입하여 RLVR 의 근본적인 병목 현상 (불충분한 탐색) 을 해결했습니다.
2. 글로벌 프런티어 선택 전략: 전체 트리를 고려한 유망 노드 선정 및 엔트로피 기반의 '가장 확신 있는 오류' 선택을 통해 효율적인 학습 신호를 제공합니다.
3. 적응형 재생 버퍼: 캐싱된 솔루션을 활용하여 계산 비용을 줄이면서도 모델이 해결한 문제를 잊지 않도록 (Catastrophic Forgetting 방지) 하는 효율적인 훈련 파이프라인을 제안했습니다.

4. 실험 결과 (Results)

• 벤치마크 성능: 수학 추론 벤치마크 (AIME 2024/2025, AMC2023, MATH500 등) 에서 **1.5B 파라미터 모델 기준 평균 정확도 62.95%**를 기록하여 기존 최상위 모델 (Nemotron-Research-Reasoning-Qwen-1.5B v2, 61.70%) 을 능가하는 새로운 State-of-the-Art(SOTA) 를 달성했습니다.
• 계산 효율성: 기존 확장 훈련 (Extended Training) 방식에 비해 5.7 배 적은 GPU 시간으로 더 높은 성능을 달성했습니다.
  • 기존 방식: 1,883 GPU 시간으로 62.02% 정확도 (성능 정체).
  • DeepSearch: 330 GPU 시간으로 62.95% 정확도 달성.
• 성능 곡선: DeepSearch 는 훈련 초기부터 더 빠른 수렴을 보이며, 단순한 훈련 시간 연장이 아닌 알고리즘적 혁신을 통한 효율적인 학습이 가능함을 입증했습니다.

5. 의의 및 결론 (Significance & Conclusion)

DeepSearch 는 언어 모델의 추론 능력 확장을 위해 모델 파라미터나 훈련 단계 수를 무작정 늘리는 (Scaling Depth) 방식에서 벗어나, 알고리즘적 혁신을 통한 훈련의 폭 (Scaling Breadth) 을 확장하는 새로운 패러다임을 제시합니다.

• 전략적 탐색의 중요성: 단순히 더 많은 계산 자원을 투입하는 것보다, 훈련 과정에서 체계적이고 전략적인 탐색 (Systematic Exploration) 을 수행하는 것이 성능 향상에 훨씬 효과적입니다.
• 학습 과정의 재설계: 추론 단계에서 기대되는 정교한 추론 패턴을 훈련 과정 자체에 반영함으로써, RLVR 방법론의 한계를 극복하고 더 강력하고 효율적인 추론 모델을 구축할 수 있음을 보여줍니다.

이 연구는 수학 추론을 넘어 다양한 복잡한 의사결정 문제에서 MCTS 기반의 훈련 프레임워크가 가지는 잠재력을 입증하며, 향후 RLVR 연구의 중요한 방향성을 제시합니다.