Research map / Large language models / Reasoning and chain of thought

DeepSearch: Overcome the Bottleneck of Reinforcement Learning with Verifiable Rewards via Monte Carlo Tree Search

ICLR 2026 · Large language models › Reasoning and chain of thought · approach: RL with verifiable rewards for reasoning · 0 citations (OpenAlex)

Read the paperCheck your idea against 108,967 papers

AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.

Embeds Monte Carlo Tree Search with global frontier selection, entropy-guided trajectory selection, and adaptive replay-buffer training into RLVR, reaching 62.95% average math accuracy for a 1.5B model with 5.7x fewer GPU hours than extended DAPO training.

Problem

RLVR training for LLM reasoning plateaus after thousands of steps because rollouts are sparse and miss critical reasoning paths, so exploration is limited during training.

Approach

Integrate MCTS directly into the RLVR training loop (not just inference), replacing root-to-leaf UCT traversal with a global frontier priority score (quality, entropy, depth bonuses), selecting the most confident incorrect trajectory when no correct one exists, and caching correct solutions in a replay buffer while iteratively filtering to hard problems; optimized with a Tree-GRPO objective.

Key results

• DeepSearch-1.5B reaches 62.95% average accuracy across six math benchmarks, versus 61.70% for the prior best Nemotron-Research-Reasoning-Qwen-1.5B v2.
• DeepSearch uses about 330 GPU hours for +50 steps, versus 1883.2 GPU hours for 1,875 extended DAPO steps (reported 5.7x fewer), with extended training plateauing at 62.02%.
• Global frontier selection reduces iterations from 209.6 to 187.7 versus vanilla UCT (about 10.4% reduction) and improves trajectory reward from -0.82 to -0.65.

Surprising findings

• Extended DAPO training plateaus around 62% (62.02%) even with 1,875 additional steps, while a short DeepSearch run surpasses it.
• Selecting the most confident (lowest-entropy) incorrect trajectory outperforms random and least-confident selection, contrary to the common uncertainty-seeking intuition.

Limitations

• Evaluated only on 1.5B models and mathematical reasoning benchmarks.
• Per-tree cost is dominated by policy generation (over 99% of time), so the search is computationally heavy per problem despite the claimed efficiency.
• Fixed filtering threshold (25%) and hyperparameters chosen heuristically; the 5.7x efficiency comparison relies on a single extended-training baseline and reported GPU-hour accounting.

Experimental setup

Datasets: DeepMath-103K

Benchmarks: AIME24 AIME25 AMC23 MATH500 Minerva OlympiadBench

Metrics: Pass@1 accuracy (n=32 samples) average accuracy GPU hours search iterations per-tree time

Baselines: Nemotron-Research-Reasoning-Qwen-1.5B v2 Nemotron-Research-Reasoning-Qwen-1.5B v1 DeepScaleR-1.5B STILL-3-1.5B DeepSeek-R1-Distill-Qwen-1.5B Open-RS Qwen2.5-Math-1.5B-Oat-Zero DAPO extended training

Builds on: GRPO DAPO UCT AlphaGo veRL

Closest papers by meaning

• Depth-Breadth Synergy in RLVR: Unlocking LLM Reasoning Gains with Adaptive Exploration (ICML 2026 · similarity 0.91)
• Exploration vs Exploitation: Rethinking RLVR through Clipping, Entropy, and Spurious Reward (ICLR 2026 · similarity 0.91)
• Diversity-Incentivized Exploration for Versatile Reasoning (ICLR 2026 · similarity 0.91)
• RLP: Reinforcement as a Pretraining Objective (ICLR 2026 · similarity 0.91)
• Reasoning with Exploration: An Entropy Perspective (AAAI 2026 · similarity 0.91)
• The Reasoning Boundary Paradox: How Reinforcement Learning Constrains Language Models (NeurIPS 2026 · similarity 0.90)