Difficulty adaptive tree search improves reasoning coverage in AI models
Difficulty-Adaptive Tree-Structured Policy Optimization for Expanding Reasoning Coverage in RLVR
Machine LearningArtificial IntelligenceComputation and Language
Summary
Improving how AI models reason and find correct answers often requires exploring many possible solutions during training. The authors found that using a method that adapts the challenge of problems while organizing possible answers in a tree, rather than just trying many samples in parallel, helps the models cover more reasoning possibilities. They also use a technique to choose diverse sentence-level options, which makes the search explore more varied ideas. Their approach, called DATPO, leads to better performance in solving math problems by expanding the kinds of solutions the AI can find.
Reinforcement LearningVerifiable RewardsReasoning CoveragePass@kTree SearchDifficulty AdaptationSentence EntropySemantic DiversityMathematical ReasoningPolicy Optimization
Authors
Youngjun Yu, Sanghwan Jang, Hwanjo Yu
Abstract
Reinforcement Learning with Verifiable Rewards (RLVR) has been central to the recent success of Large Reasoning Models. However, while RLVR significantly improves single-sample accuracy, it often fails to expand the model's intrinsic reasoning coverage (pass@k) due to limited exploration during training. To address this, we optimize the structural design of train-time rollouts to enhance pass@k. Our analysis identifies three key design principles: (1) difficulty-adaptive rollout can play an important role in expanding pass@k, beyond serving as an efficiency heuristic; (2) tree-based rollout outperforms parallel sampling in discovering correct answers; and (3) sentence-entropy-guided forking overcomes the localization phenomenon of token-level branching to maximize semantic diversity. Building on these insights, we propose DATPO (Difficulty-Adaptive Sentence-entropy-guided Tree-structured Policy Optimization). DATPO integrates difficulty-adaptive tree search with a sibling-diversity advantage term, explicitly promoting semantic diversity to expand reasoning coverage during training. Experiments on mathematical reasoning benchmarks demonstrate that DATPO outperforms baselines especially in pass@k, which directly translates to superior test-time scaling performance.