PaperlayerView exact revision on arXiv

Source-linked AI summary

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

Youngjun Yu, Sanghwan Jang, Hwanjo Yu

arXiv:2609.08650v1cs.LGcs.AIcs.CL

TL;DR

RLVR can improve single-sample accuracy without expanding a model’s intrinsic reasoning coverage, limiting pass@k and test-time scaling. The paper analyzes train-time rollout structure and proposes DATPO, combining difficulty-adaptive tree search, sentence-entropy-guided forking, and sibling-diversity optimization. On mathematical reasoning benchmarks, DATPO achieves the highest average pass@k among compared methods and improves majority-voting test-time scaling.

  • Problem

    RLVR often fails to expand intrinsic reasoning coverage because training lacks explicit exploration toward underexplored reasoning regions.

  • Method

    DATPO combines difficulty-adaptive tree search, sentence-entropy-guided forking, and an annealed sibling-diversity advantage term for semantic exploration.

  • Results

    DATPO achieves the highest average pass@k among compared methods on mathematical reasoning benchmarks and improves majority-voting test-time scaling.

  • Takeaways & Limitations

    Difficulty-adaptive rollout, tree structure, and sentence-level forking provide structural principles for expanding reasoning coverage during RLVR.

  • Takeaways & Limitations

    Validation is restricted to 3B–4B models and mathematical reasoning, leaving scalability to larger models and effectiveness in other rigorous domains unverified.

Abstract

from arXiv · show

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.

1 Introduction

The paper argues that RLVR can improve single-sample accuracy without expanding intrinsic reasoning coverage, and studies train-time rollout structure to address this gap. It identifies difficulty adaptation, tree search, and sentence-level forking as principles underlying DATPO, which improves pass@k and test-time scaling.

  • Motivation: RLVR often fails to unlock reasoning capabilities beyond the base model because training lacks explicit exploration toward underexplored regions.Without guidance, the model exploits known solutions rather than discovering novel reasoning paths.
  • Research gap: Train-time rollout structure remains underexplored as a means of expanding reasoning coverage beyond single-sample accuracy.Prior work largely used fixed parallel rollouts or tree structures for credit assignment and efficiency.
  • Design principles: Difficulty-adaptive rollout can expand pass@k beyond serving as a compute-efficiency heuristic, while tree rollouts outperform parallel sampling in discovering correct answers.The effect of larger rollout budgets depends on problem difficulty, and sentence-entropy forking addresses localization in token-level branching.
  • DATPO: DATPO combines difficulty-adaptive tree search, sentence-level entropy forking, and an annealed sibling-diversity advantage term.The diversity term explicitly rewards semantically diverse reasoning branches.
  • Results: DATPO achieves the highest average pass@k among compared methods on mathematical reasoning benchmarks and improves majority-voting test-time scaling.The paper reports that expanded reasoning coverage directly translates to superior maj@k performance.

2 Analyzing the Structural Design of Train-time Rollouts

The analysis evaluates how difficulty allocation, rollout topology, and forking granularity affect reasoning coverage. It finds that adaptive budgets depend on task difficulty, tree structures use tokens more efficiently than parallel sampling, and sentence-level entropy avoids localized branching.

  • Difficulty-Adaptive Allocation: The study evaluates rollout budgets across Easy, Medium, and Hard subsets using avg@256 and pass@256 to distinguish exploitation from reasoning coverage.Nine GRPO runs vary group size G ∈ {4, 8, 16} across three benchmarks.
  • Difficulty-Adaptive Allocation: Larger rollout budgets marginally improve avg@256 across difficulty levels, but their effect on pass@256 changes with training difficulty.Easy-trained models degrade in pass@256 as budgets increase, whereas Medium-trained models peak at G = 8.
  • Difficulty-Adaptive Allocation: Difficulty-adaptive rollout balances exploration and exploitation, making it a strategic factor in maximizing reasoning coverage rather than merely a compute-saving heuristic.The paper links easy-problem over-exploitation to redundant successes that provide no additional coverage benefit.
  • Tree vs. Parallel Rollout: Tree-structured rollouts achieve higher PassRate than parallel sampling at comparable token budgets.Prefix sharing avoids regenerating identical early segments and enables alternative continuations within the same budget.
  • Tree vs. Parallel Rollout: Forking-point placement affects tree performance: fixed-seg consistently exceeds parallel sampling under comparable token budgets.The result shows that tree topology alone is insufficient; branching locations also matter.
  • The Localization Phenomenon and Sentence-level Forking: Token-entropy forking produces high local sibling diversity but low PassRate because high-entropy tokens cluster in narrow trajectory segments.Sentence-entropy broadens entropy estimation, avoids localization, and achieves the highest PassRate with minimal SibDiv loss.

3 Methodology

DATPO uses difficulty-adaptive tree search to allocate more exploration to harder problems, then optimizes block-level advantages with semantic sibling diversity.

  • Difficulty-Adaptive Tree Search at Train-time: DATPO estimates prompt difficulty from average verifiable reward across independent base rollouts and scales tree expansion accordingly.Lower root reward indicates a harder problem and receives more search budget.
  • Difficulty-Adaptive Tree Search at Train-time: Sentence entropy identifies forking points within each base trajectory, generating branches that expand the search space for difficult problems.For harder problems, expansion can reach N(1 + K̂ B̂) leaves.
  • Block-level Diversity-augmented Advantage Estimation: The method partitions trajectories into contiguous blocks and assigns advantages at block level, giving all tokens within a block the same credit signal.Terminal verifiable rewards are assigned to terminal blocks, supporting implicit process supervision.
  • Block-level Diversity-augmented Advantage Estimation: DATPO augments base advantages with sibling diversity, measured as average cosine distance from sibling-block embeddings, and applies it to positive-advantage blocks.The diversity coefficient is annealed during training to reduce the exploration incentive over time.
  • Block-level Diversity-augmented Advantage Estimation: The policy objective is optimized directly over the generated tree topology using contiguous blocks and their sequence lengths.The framework overview presents this tree-structured training procedure.

4 Experiments

Experiments evaluate DATPO on mathematical reasoning benchmarks and find its strongest gains in reasoning coverage, training stability, hard-problem resource allocation, and majority-voting scaling.

  • Main Results: DATPO achieves the best aggregate avg@k and pass@k across the evaluated mathematical reasoning benchmarks.Compared with AttnRL, pass@k gains are +1.9 for Qwen2.5-3B-Base and +3.0 for Qwen3-4B-Base, while avg@k gains are smaller.
  • Main Results: DATPO’s difficulty-adaptive rollout and sibling-diversity term expand the model’s intrinsic reasoning coverage.The reported improvement is specifically reflected in pass@k rather than only single-sample accuracy.
  • Training Dynamics: DATPO maintains a consistent upward MATH500 accuracy trend during training, unlike tree-based baselines that plateau or degrade.The annealed sibling-diversity term is attributed to preventing premature convergence by injecting semantic diversity early.
  • Training Dynamics: DATPO allocates fewer rollouts to easy problems and more to hard problems than AttnRL, achieving higher PassRate on Levels 4 and 5.AttnRL’s attention-based filtering uses a rigid cutoff that does not concentrate resources on the hardest problems.
  • Test-time Scaling: DATPO improves average maj@k by +7.2 over avg@k across five benchmarks, the largest gain among compared methods.The evaluation uses majority voting with k = 8 for MATH500 and k = 64 for the remaining datasets.
  • Ablation Studies: Sentence-entropy forking achieves the highest MATH500 performance among the compared forking strategies, avoiding token-entropy localization.The ablation compares random, fixed-seg, ATB, and tok-entropy alternatives.
  • Ablation Studies: The 0.2 → 0 diversity schedule is most effective, while applying diversity to all blocks or penalizing it later harms coverage-related performance.A constant schedule severely degrades avg@8, whereas annealing to a negative value harms pass@8.

5 Related Work

Related work spans RLVR optimization, explicit exploration objectives, and tree-based search, while DATPO targets the underexplored structural design of train-time rollouts.

  • Reinforcement Learning for LLM Reasoning: GRPO replaces PPO’s critic with group-based advantage estimation, and later variants address stability and structural optimization issues.The related work positions GRPO as a representative RLVR method.
  • Exploration Strategies in RLVR: Recent RLVR exploration methods diversify search through pass@k optimization, diversity-aware objectives, and divergent reasoning strategies.These approaches address the limitation that RLVR may not expand reasoning capacity beyond the base model.
  • Tree-based Search: Tree-based LLM methods use systematic exploration, with TreeRL emphasizing entropy-guided branching and AttnRL emphasizing difficulty-aware adaptive sampling.Prior tree methods primarily use trees for credit assignment or computational efficiency.

6 Conclusion

The work moves RLVR train-time rollouts beyond uniform parallel sampling by combining difficulty-adaptive allocation with sentence-entropy-guided tree search. DATPO adds explicit semantic exploration through sibling diversity and improves pass@k on mathematical benchmarks.

  • DATPO moves beyond uniform parallel sampling through difficulty-adaptive resource allocation and sentence-entropy-guided tree search.
  • DATPO explicitly encourages semantic exploration through a sibling-diversity term.
  • Experiments on mathematical benchmarks show significant improvements in pass@k.

Limitations

The method has computational and estimation limitations, and its empirical validation is constrained to small rollout samples and mathematical reasoning settings.

  • Computing sibling diversity requires additional forward passes through an external embedding model, introducing computational overhead.
  • Limited rollout samples can make empirical difficulty and Monte Carlo state-value estimates noisy, occasionally producing high-variance policy updates.The paper gives N = 4 and B = 4 as an example of small rollout sizes.
  • Validation is restricted to 3B-4B models, leaving scalability to models ≥7B unverified.
  • The evaluation primarily targets mathematical reasoning, so effectiveness in complex logical reasoning and code generation requires further investigation.

A Theoretical Analysis of Difficulty-Adaptive Rollout

The analysis explains why larger rollout groups improve expected avg@k while pass@k can vary by difficulty, through a trade-off between mean gains and cross-prompt variance. It formalizes increasing but diminishing returns for avg@k and characterizes different difficulty regimes.

  • Difficulty-dependent pass@k: Increasing G can reduce pass@k on Easy problems but improve it on Hard problems because cross-prompt variance responds differently to additional rollouts.The analysis attributes Easy degradation to template over-exploitation and Hard improvement to broader exploration of scarce valid reasoning paths.
  • Pass@k decomposition: Expected avg@k is theoretically equivalent to single-sample correctness probability, whereas pass@k depends additionally on prompt-level heterogeneity.The pass@k decomposition separates gains from higher avg@k from losses caused by test-set prompt heterogeneity.
  • Expected avg@k dynamics: For sufficiently small learning rates, expected avg@k increases strictly with G but with diminishing returns.The result holds simultaneously over any finite set of rollout budgets.
  • Expected avg@k dynamics: Larger rollout budgets consistently improve expected avg@k because mixed-reward groups provide informative relative-reward signals more frequently.The analysis models a GRPO update using rollout group size G and isolates the reward-advantage component.
  • Scope and assumptions: The theoretical conclusions are scoped by idealized assumptions, including a G-independent mixed-reward update magnitude and omission of advantage-estimation variance.The paper presents these assumptions as a first-order lens rather than a universal law for all training environments.
  • Pass@k decomposition: The pass@k penalty is nonnegative and vanishes exactly when single-sample correctness is constant across prompts.This follows from the strict concavity of f_k(p) = 1 − (1 − p)^k.

B Experimental Details of Section 2.1

The experiments train nine GRPO models on difficulty-partitioned MATH subsets under three rollout budgets, then evaluate them with large-scale parallel sampling. The setup uses balanced subsets and binary verifiable rewards.

  • Dataset construction: The MATH dataset is divided into Easy, Medium, and Hard subsets using base-model accuracy from 12 sampled solutions per problem.Problems with 1–4, 5–8, and 9–11 correct samples are labeled Hard, Medium, and Easy, respectively; all-correct and all-incorrect problems are excluded.
  • Training setup: The study trains nine models using GRPO with rollout budgets G ∈ {4, 8, 16} for each difficulty subset.Each subset is balanced to 1,400 problems before training.
  • Evaluation: Each trained model is evaluated on MATH500, AIME25, and AIME24 using 256 reasoning paths per problem.Pass@k is reported for k ∈ {1, 2, 4, 8, 16, 32, 64, 128, 256}.
  • Rollout procedure: The rollout procedure uses base trajectories followed by selected forking points and branch rollouts to construct a trajectory set.The method is described as a two-phase tree rollout strategy.

C.2 Experimental Details of Section 2.2.2

The Section 2.2.2 experiments compare parallel and tree-structured rollouts under matched computational configurations, then examine how forking-point strategies affect localization. Sentence-level entropy broadens branching beyond token-level concentration.

  • Rollout comparison: Tree rollouts share computed prefixes, consuming tokens sub-linearly relative to their number of terminal paths.With N base rollouts, K forking points, and B branches, the tree produces N(1 + KB) terminal paths.
  • Rollout comparison: The cost-efficiency comparison evaluates parallel rollout counts M ∈ {4, 8, 16, 32} against tree configurations producing 10, 20, and 40 terminal paths.Tree experiments use K = 2, B = 2, and N ∈ {2, 4, 8}.
  • Forking strategies: Forking strategies include random, fixed-segment, attention-based, token-entropy, and sentence-entropy selection.The algorithms select branching locations from token, sentence, segment, or attention-derived uncertainty structures.
  • Forking strategies: Sentence-level entropy averages token entropy within each parsed sentence, providing a broader uncertainty signal for selecting forking points.Sentences are aligned with tokenizer offsets and represented as contiguous token spans.

D.2 Quantitative and Qualitative Analysis of Forking-Point Localization

The analysis shows that token-entropy forking localizes exploration, whereas sentence-entropy distributes forks more broadly and identifies more semantically meaningful decision points. Distance constraints reduce localization but do not match sentence-entropy’s branching quality.

  • Localization phenomenon: Token-entropy forking clusters high-entropy points in narrow trajectory segments, monopolizing the search budget and limiting structural diversity.The localization restricts the structural reach of the search tree.
  • Quantitative analysis: Lower NND and MPD, together with higher WCR, indicate stronger localization of selected forking points.These metrics quantify nearest-neighbor spacing, pairwise spacing, and within-window clustering.
  • Quantitative analysis: Tok-entropy has NND 0.106, MPD 0.251, WCR@5 23.6%, and WCR@10 35.3%, while sent-entropy reaches 0.130, 0.296, 12.9%, and 25.3%, respectively.The changes quantitatively demonstrate reduced localization under sentence-level entropy.
  • Qualitative analysis: Across case studies, sent-entropy distributes forks across broader semantic levels, unlike localized tok-entropy and uncertainty-insensitive ATB selections.The comparison uses K = 4 forking points on a fixed reasoning path.
  • Semantic diversity: SibDiv measures semantic exploration by aggregating the distinctness of sibling continuations across the reasoning tree.It is defined from sibling-block semantic representations and summarized as a tree-level diversity score.
  • Distance-forced baselines: Distance-forced tok-entropy raises PassRate from 12.0 to 14.0 and 15.3 at 5% and 10% thresholds, but sent-entropy reaches 17.3.The remaining gap indicates that sentence-level entropy provides a more effective signal for semantically meaningful branching points, beyond spacing alone.

F.4 Generalization to Out-Of-Domain Tasks

DATPO’s mathematical-reasoning improvements are evaluated beyond the training domain on GPQA-Diamond and MMLU-Pro. Results are generally favorable, though performance varies by model and benchmark.

  • Evaluation setup: DATPO is evaluated out of domain on GPQA-Diamond and a stratified 500-instance subset of MMLU-Pro.The MMLU-Pro subset preserves the original proportions across subject categories.
  • Results: For Qwen2.5-3B-Base, DATPO improves GPQA-Diamond by 2.4 percentage points and differs by -0.1 point on MMLU-Pro versus the strongest baselines.The reported metric is avg@8 accuracy.
  • Results: For Qwen3-4B-Base, DATPO improves GPQA-Diamond by 1.2 points and MMLU-Pro by 0.4 points, supporting cross-domain transfer of the observed reasoning gains.The results are reported relative to the strongest baselines.

F.5 Further Ablation Studies

Further ablations show that difficulty adaptation, diversity augmentation, embedding choice, and algorithmic design each affect DATPO’s results. They also identify computational and configuration trade-offs relevant to interpreting the comparisons.

  • Difficulty-adaptive rollout: The full DATPO framework outperforms its static non-adaptive variant in both avg@k and pass@k.The ablation supports difficulty-adaptive rollout as a contributor beyond fixed budget allocation.
  • Diversity-augmented advantage: Without the diversity term, pass@64 peaks at 30.0% at step 200 and falls to 25.6% at step 700, whereas DATPO reaches 33.3% at step 700.The diversity-augmented advantage is associated with continued expansion of reasoning coverage during training.
  • Embedding models: Smaller embedding models remain competitive: all-mpnet-base-v2 and gte-base-en-v1.5 marginally exceed the default in pass@8 at 81.9%, while gte-large reaches 63.5% avg@8.The results indicate robustness to embedding-model scale and choice.
  • Wider-topology control: DATPO’s wider tree configuration was tested against TreeRL and AttnRL under identical wider limits to separate topology from algorithmic effects.The comparison addresses whether DATPO’s gains arise merely from using B = 4.
  • Wider-topology control: Under the matched wider topology, DATPO achieves the highest avg@8 and pass@8 while generating the fewest average training tokens per problem.The authors attribute the advantage to difficulty-adaptive rollout and diversity-guided exploration rather than wider expansion alone.
Loading 2609.08650v1…