arXiv:2611.22301v1 cs.AI

MCTS는 무엇을 세어야 하는가? 대규모 언어 모델 추론을 위한 탐험 횟수 학습

MCTS Is Counting the Wrong Thing: Learning Exploration Counts for LLM Reasoning

Xuan Zhang, Zhijian Zhou, Zicheng Hu, Yan Feng, Hongyan Hao, Yuan Qi, Chao Qu

제출 2026-11-18

한국어 초록

몬테카를로 트리 탐색(MCTS)은 강화학습의 주요 성과를 이끌었으나, 대규모 언어 모델(LLM)의 추론에서는 상당한 탐색을 수행해도 개선 폭이 작을 수 있다. 간과해 온 병목은 MCTS가 무엇을 세는지에 있다. 표준 UCT는 텍스트 분기마다 방문 횟수를 독립적으로 기록한다. 따라서 같은 추론 전략을 표현만 달리한 여러 분기가 저마다 탐험 보너스를 받을 수 있다. 이론 분석에서 이처럼 방문 횟수가 분산되면 누적 후회값이 커져 탐험 효율을 떨어뜨릴 수 있음을 보인다. 이를 해결하기 위해 UCT의 탐험 통계량만 바꾸는 학습형 의사 횟수 MCTS(LPC-MCTS)를 도입한다. 정책의 은닉 표현에 붙인 경량 동전 던지기 신경망 헤드로 탐색이 포함한 표현의 범위를 추정한다. 관련 분기가 탐험 근거를 공유할 수 있다. 수학 추론 벤치마크 다섯 개와 탐색 벤치마크 일곱 개에서 LPC-MCTS는 강력한 MCTS 기준선을 일관되게 앞섰다. LPC-MCTS로 학습한 각 정책을 고정한 채 추론 시 표준 MCTS의 방문 횟수를 바꾸자, 수학 벤치마크 다섯 개의 mean@16 정확도가 Qwen2.5-7B에서 평균 3.79%포인트, Qwen3-4B에서 2.71%포인트 높아졌다. 학습과 추론에 모두 LPC-MCTS를 적용하면 표준 MCTS보다 각각 4.96점과 4.37점 높았다. 이론과 실험은 MCTS가 무엇을 세는지 바꾸면 탐험 효율과 추론 성능을 크게 높일 수 있음을 보여 준다.

원문 초록

Monte Carlo tree search (MCTS) has powered landmark successes in reinforcement learning, yet its gains in LLM reasoning can remain modest despite substantial search effort. We identify an overlooked bottleneck: what MCTS counts. Standard UCT assigns independent visit counts to textual branches, allowing different formulations of the same reasoning strategy to repeatedly receive exploration bonuses. Our theoretical analysis shows that this count fragmentation can impair exploration efficiency, as quantified by increased cumulative regret. To address this problem, we introduce Learned Pseudo-Count MCTS (LPC-MCTS), which changes only the exploration statistic in UCT. A lightweight Coin-Flipping Network head on the policy's hidden representations estimates representation coverage, enabling related branches to share exploration evidence. Across 5 mathematical-reasoning and 7 search benchmarks, LPC-MCTS consistently outperforms strong MCTS baselines. Holding each LPC-MCTS-trained policy fixed, replacing standard MCTS counts at inference improves average mean@16 accuracy across 5 mathematical benchmarks by 3.79 percentage points on Qwen2.5-7B and 2.71 points on Qwen3-4B. Applying LPC-MCTS during both training and inference yields gains of 4.96 and 4.37 points over standard MCTS, respectively. Together, our theory and experiments show that changing what MCTS counts can substantially improve its exploration efficiency and reasoning performance.

제출 이력

확인된 버전만 표시합니다. 전체 제출 이력은 arXiv 원문에서 확인하세요.

  1. arXiv:2611.22301v1제출 시각 미확인

함께 살펴볼 논문

공통 태그를 근거로 연결했습니다. 실제 인용 관계나 논문의 우수성을 뜻하지 않습니다.

공통 태그로 연결된 공개 논문이 아직 없습니다.

토론

이 논문과 연결된 포럼 글이 아직 없습니다.