Difficulty-Adaptive Tree-Structured Policy Optimization for Expanding Reasoning Coverage in RLVR
Youngjun Yu, Sanghwan Jang, Hwanjo Yu
POSTECH
Published September 8, 2026 · on the feed September 10, 2026 · ▲ 10 · arXiv 2609.08650
The 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.
The Brief
1:59A short podcast summary of the paper. Written and voiced by AI.
Transcript
Difficulty-Adaptive Tree-Structured Policy Optimization for Expanding Reasoning Coverage in RLVR. By Youngjun Yu and two others, from the Pohang University of Science and Technology. Published on the eighth of September. Its code repository is public and real: fourteen source files.
Reinforcement learning with verifiable rewards, RLVR, has been central to the recent success of large reasoning models. It reliably improves accuracy on a single sample. What it often fails to do is expand the model's intrinsic reasoning coverage, measured as pass at k: the chance that at least one of several attempts is correct. The authors trace that failure to limited exploration during training.
Their response is to redesign the structure of the rollouts generated during training, with pass at k as the target. Analysis yields three principles. First, adapting rollouts to difficulty can help expand pass at k, and is more than a heuristic for efficiency. Second, rollouts that branch like a tree find correct answers better than parallel sampling does. Third, choosing where to fork by the entropy of whole sentences overcomes a localization problem with branching at the level of single tokens, and so maximizes semantic diversity.
Those three principles become DATPO, short for Difficulty-Adaptive Sentence-entropy-guided Tree-structured Policy Optimization. It combines tree search that adapts to difficulty with an extra advantage term for sibling diversity. That term explicitly rewards branches of the same tree for differing in meaning from one another, which is how the method pushes reasoning coverage outward during training rather than narrowing it.
On mathematical reasoning benchmarks, DATPO outperforms the baselines, and most clearly on pass at k. The authors note that this carries over directly into better performance when compute is scaled at test time.
The paper treats exploration as a question of rollout shape. Which problems get more rollouts, how those rollouts branch, and where the branches split are all design choices, and each was chosen here to widen what the model can reach rather than just sharpen what it already finds.
Paper Quest · 7 chapters · about 40 min
Play this paper
Learn it by doing: make the calls the authors made, guess the result before you see it, and defend it in a viva graded on your own words. Chapter 1 is right here.
Chapter 1 🧩 · The problem
Training made the model sharper, but not broader. That is the wall here.
You are training a model on maths with rewards from an answer checker. Its accuracy on a single try goes up nicely.
The road ahead
- 1 · The problem ~6 min Training with an answer checker makes a model more accurate on one try, but it rarely helps the model find answers it could not find before.
- 2 · What came before ~3 min
- 3 · The key idea ~9 min Reshape the training attempts themselves so the model explores: spend by difficulty, branch attempts as a tree, and reward correct branches that differ.
- 4 · Choose your own research ~3 min
- 5 · Build the method ~8 min Each training step sizes the tree by difficulty, forks it at uncertain sentences, adds a diversity bonus to advantages, then updates the policy.
- 6 · The experiment ~6 min You’ll guess: On mathematical reasoning benchmarks, where did DATPO's advantage over baselines show most clearly?
- 7 · The viva ~5 min Three questions from the examiners, answered in your own words. Win it for the paper’s trophy.
Free, with Google or an email address. Your stars and progress are kept.