# Difficulty-Adaptive Tree-Structured Policy Optimization for Expanding Reasoning Coverage in RLVR

arXiv: https://arxiv.org/abs/2609.08650 · HTML: https://mlsanity.com/paper/2609.08650/

## Key facts

- Cited by 2 papers in the map (data through 14 Oct 2026).
- Placed in Reinforcement learning for reasoning, one of 17 directions in LLM reasoning.
- Builds on 26 of its 34 references that are in the map.
- First posted on arXiv 8 Sep 2026.

## Placed in

- LLM reasoning / [Reinforcement learning for reasoning](https://mlsanity.com/lr/reinforcement-learning-for-reasoning/)

## Builds on (most cited first, 26 of 26)

- [Proximal Policy Optimization Algorithms](https://mlsanity.com/paper/1707.06347/) (2017)
- [Sentence-BERT: Sentence Embeddings using Siamese BERT-Networks](https://mlsanity.com/paper/1908.10084/) (2019)
- [Measuring Mathematical Problem Solving With the MATH Dataset](https://mlsanity.com/paper/2103.03874/) (2021)
- [GPQA: A Graduate-Level Google-Proof Q&A Benchmark](https://mlsanity.com/paper/2311.12022/) (2023)
- [Learning to summarize from human feedback](https://mlsanity.com/paper/2009.01325/) (2020)
- [MMLU-Pro: A More Robust and Challenging Multi-Task Language Understanding Benchmark](https://mlsanity.com/paper/2406.01574/) (2024)
- [Understanding R1-Zero-Like Training: A Critical Perspective](https://mlsanity.com/paper/2503.20783/) (2025)
- [M3-Embedding: Multi-Linguality, Multi-Functionality, Multi-Granularity Text Embeddings Through Self-Knowledge Distillation](https://mlsanity.com/paper/2402.03216/) (2024)
- [Large Language Monkeys: Scaling Inference Compute with Repeated Sampling](https://mlsanity.com/paper/2407.21787/) (2024)
- [Does Reinforcement Learning Really Incentivize Reasoning Capacity in LLMs Beyond the Base Model?](https://mlsanity.com/paper/2504.13837/) (2025)
- [Reasoning with Exploration: An Entropy Perspective](https://mlsanity.com/paper/2506.14758/) (2025)
- [mGTE: Generalized Long-Context Text Representation and Reranking Models for Multilingual Text Retrieval](https://mlsanity.com/paper/2407.19669/) (2024)
- [Act Only When It Pays: Efficient Reinforcement Learning for LLM Reasoning via Selective Rollouts](https://mlsanity.com/paper/2506.02177/) (2025)
- [The Invisible Leash: Why RLVR May or May Not Escape Its Origin](https://mlsanity.com/paper/2507.14843/) (2025)
- [TreeRL: LLM Reinforcement Learning with On-Policy Tree Search](https://mlsanity.com/paper/2506.11902/) (2025)
- [TreePO: Bridging the Gap of Policy Optimization and Efficacy and Inference Efficiency with Heuristic Tree-based Modeling](https://mlsanity.com/paper/2508.17445/) (2025)
- [Sample, Scrutinize and Scale: Effective Inference-Time Search by Scaling Verification](https://mlsanity.com/paper/2502.01839/) (2025)
- [PySBD: Pragmatic Sentence Boundary Disambiguation](https://mlsanity.com/paper/2010.09657/) (2020)
- [Flow of Reasoning: Training LLMs for Divergent Reasoning with Minimal Examples](https://mlsanity.com/paper/2406.05673/) (2024)
- [Improving Sampling Efficiency in RLVR through Adaptive Rollout and Response Reuse](https://mlsanity.com/paper/2509.25808/) (2025)
- [Exploiting Tree Structure for Credit Assignment in RL Training of LLMs](https://mlsanity.com/paper/2509.18314/) (2025)
- [Enhancing Efficiency and Exploration in Reinforcement Learning for LLMs](https://mlsanity.com/paper/2505.18573/) (2025)
- [Attention as a Compass: Efficient Exploration for Process-Supervised RL in Reasoning Models](https://mlsanity.com/paper/2509.26628/) (2025)
- [Lookahead Tree-Based Rollouts for Enhanced Trajectory-Level Exploration in Reinforcement Learning with Verifiable Rewards](https://mlsanity.com/paper/2510.24302/) (2025)
- [Selective Expert Guidance for Effective and Diverse Exploration in Reinforcement Learning of LLMs](https://mlsanity.com/paper/2510.04140/) (2025)
- [TreeAdv: Tree-Structured Advantage Redistribution for Group-Based RL](https://mlsanity.com/paper/2601.03703/) (2026)

## Built on by (most cited first, 2 of 2)

- [SERA: Scale-Equalized Rollout Allocation for Maximum Likelihood Reinforcement Learning](https://mlsanity.com/paper/2609.36552/) (2026)
- [Branching On-Policy Distillation](https://mlsanity.com/paper/2610.13481/) (2026)

## Abstract (arXiv)

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.