arXiv CSopen access

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

· arxiv_cs

arXiv CS · Papers · License: Open Access

machine learning, deep learning, neural networks

Difficulty-Adaptive Tree-Structured Policy Optimization for Expanding Reasoning Coverage in RLVR Youngjun Yu Sanghwan Jang Hwanjo Yu* Pohang University of Science and Technology (POSTECH) {colin31472, s.jang, hwanjoyu}@postech.ac.kr

Abstract

arXiv:2609.08650v1 [cs.LG] 8 Sep 2026

Reinforcement Learning with Verifiable Rewards (RLVR) has been central to the recent success of Large Reasoning Models. However, while RLVR significantly improves singlesample 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) sentenceentropy-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 paradigm of Large Reasoning Models (LRMs) has achieved remarkable success in eliciting rigorous problem-solving capabilities from foundation models (Jaech et al., 2024; Team et al., 2025). A key mechanism behind this is Reinforcement Learning with Verifiable Rewards (RLVR), exemplified by DeepSeek-R1 (Guo et al., 2025) through its successful application of the Group Relative Policy Optimization (GRPO) (Shao et al., 2024). * Corresponding author. 1

Code: https://github.com/colin31472/DATPO

In parallel, LRM research has increasingly emphasized test-time scaling strategies, including CoT (Wei et al., 2022), majority voting (Wang et al., 2022), best-of-N (Stiennon et al., 2020), and Monte Carlo Tree Search (MCTS) (Ha et al., 2025). Fundamentally, the effectiveness of these methods is limited by the model’s intrinsic reasoning coverage—the breadth of valid reasoning paths the model can explore, typically measured by pass@k. Without sufficient reasoning coverage, even large candidate sets are unlikely to include a correct reasoning path, causing test-time scaling to aggregate or select among recurring errors (Brown et al., 2024; Zhao et al., 2025). However, recent studies (Yue et al., 2025; Dang et al., 2025; Wu et al., 2025) argue that RLVR often fails to unlock new reasoning capabilities beyond the reasoning coverage of the base model. This limitation stems from a lack of explicit exploration strategies that steer the learning or sampling process toward underexplored regions. Without such guidance, the model merely exploits known solutions rather than discovering novel ones. While recent studies introduce exploration strategies to expand reasoning coverage (Walder and Karkhanis, 2025; Yao et al., 2025; Wang et al., 2025), they largely focus on optimization-level interventions, leaving the train-time rollout as a fixed parallel structure. Tree-based frameworks (Hou et al., 2025; Liu et al., 2025a) have begun to move beyond standard parallel sampling. However, these methods primarily utilize tree structures for credit assignment or computational efficiency. Consequently, it remains underexplored which structural choices in train-time rollouts actually expand the model’s reasoning coverage. To bridge this gap, we conduct a systematic empirical analysis of train-time rollouts, revealing three core design principles to maximize reasoning coverage, extending beyond improvements in single-sample accuracy. First, difficulty-adaptive

62 61.4

pass@256 avg@256

64.7

60 Base Model pass@256

57.9

56 21 20.5 20 4

21.0

56.7

59.2

Base Model pass@256

21.2

Base Model avg@256 8 16

Rollout Budget (G)

(a) Models trained on Easy dataset

61.0 60.4

60 61.2

61 59

pass@256 avg@256

21 20.4 20 4

21.2

20.8

Base Model avg@256 8 16

Rollout Budget (G)

(b) Models trained on Medium dataset

59 58 57.9 21

20.4

20 4

Base Model pass@256

20.5

20.6

Base Model avg@256 8 16

Rollout Budget (G)

Figure 1: avg@256 and pass@256 performance across different rollout budgets for models trained on different difficulty subsets.

rollout is an important factor in expanding pass@k, rather than merely an efficiency heuristic. While increasing the rollout budget improves pass@k when training on hard problems, we observe that it can actually degrade pass@k when training on easy problems. Second, tree-based rollout outperforms parallel sampling in discovering correct answers by efficiently utilizing limited computational budgets. Finally, we observe that conventional token-guided forking suffers from localization, where high-entropy tokens cluster in narrow segments and trap exploration. To overcome this, forking decisions must be elevated to a broader semantic level to discover genuinely diverse reasoning paths. Building on these insights, we propose DATPO (Difficulty-Adaptive Sentence-entropyguided Tree-structured Policy Optimization). For train-time exploration, DATPO combines the structural advantages of tree-based search with difficulty-adaptive rollout to expand reasoning coverage. Forking points are selected using sentencelevel entropy signals, broadening the granularity of uncertainty estimation to avoid localization. Furthermore, to maximize coverage-expanding benefits, we augment the advantage function with an annealed sibling-diversity term. This explicitly rewards semantically diverse reasoning branches, encouraging the model to explore a wider range of valid reasoning paths. Extensive experiments on mathematical reasoning benchmarks demonstrate the effectiveness of DATPO, which achieves the highest average pass@k among the compared methods. Furthermore, this expanded reasoning coverage directly translates to superior test-time scaling with majority voting (maj@k).

In summary, our main contributions are as follows: • We reveal key structural principles for expanding reasoning coverage: difficulty-adaptive rollout is a key factor, and tree-structured rollouts inherently outperform parallel sampling, with sentence-entropy forking further amplifying this structural advantage. • We propose DATPO, a novel RLVR framework that integrates these structural insights with a diversity-augmented advantage to maximize coverage-expanding benefits. Experiments on mathematical reasoning benchmarks validate our approach, showing notable improvements in pass@k.

Analyzing the Structural Design of Train-time Rollouts

Despite extensive research on expanding reasoning coverage, the structural design of train-time rollouts remains underexplored. This section investigates optimal rollout structures to maximize not only single-sample accuracy (avg@k) but also broader reasoning coverage (pass@k). Our analysis is driven by three primary research questions: (1) Difficulty-Adaptive Allocation: How should compute budgets be allocated across problems of varying difficulty to expand reasoning coverage?; (2) Topology of Search Space: Which search space structure (tree-based or parallel rollout) more efficiently discovers correct reasoning trajectories?; and (3) Optimal Forking Strategy: Where should forking (branching) occur in tree-based rollouts to effectively promote diverse reasoning paths?

Necessity of Difficulty-Adaptive Rollout

Standard RLVR algorithms, notably GRPO (Shao et al., 2024) and its variants (Yu et al., 2025b; Liu et al., 2025b), typically generate a uniform number of rollouts regardless of problem difficulty. While existing difficulty-adaptive rollout strategies prioritize computational efficiency (Liu et al., 2025a; Liao et al., 2025; Zhang et al., 2025; Zheng et al., 2025a; Li et al., 2025b), we challenge this perspective by demonstrating that adaptive allocation is not merely a resource-saving heuristic but a crucial factor in expanding reasoning coverage. 2.1.1 Empirical Analysis We first partitioned the training dataset into Easy, Medium, and Hard subsets based on the accuracy of the base model. Using GRPO (Shao et al., 2024), we conduct a total of 9 training runs. For each difficulty subset, we vary the rollout budget by adjusting the GRPO group size, G ∈ {4, 8, 16}. The resulting 9 models are evaluated on 3 different benchmarks, reporting both avg@256 and pass@256 metrics (detailed in Appendix B). The aggregated results, as illustrated in Figure 1, reveal two key insights. First, avg@256 shows consistent, yet marginal, improvements with increased rollout budgets (G) across all difficulties. We attribute this to more stable exploitation; larger GRPO group sizes reduce variance in advantage estimation and yield more frequent meaningful learning signals, effectively solidifying the policy distribution around correct solutions. Second, the impact of increasing rollouts on pass@256 shifts from detrimental to beneficial depending on the difficulty of the training dataset. For models trained on the Easy dataset (Figure 1a), larger budgets degrade pass@256. This occurs because the model over-exploits specific, easy templates, overfitting to familiar problems while failing entirely on harder ones. Since pass@256 requires only a single correct path, generating redundant successes for easy problems provides no coverage benefit. Consequently, despite marginal gains in avg@256, pass@256 decreases as the rollout budget increases. Conversely, for models trained on the Hard dataset (Figure 1c), where valid paths are scarce, larger budgets promote broader exploration without overfitting to narrow patterns, consistently improving pass@256. Between these opposing behaviors, models trained on the Medium dataset (Figure 1b) exhibit a nonmonotonic trend, peaking at G = 8 by effectively

Tree (fixed-seg) Tree (random) Parallel

PassRate (%)

2.1

15 10 5

Inference Tokens (×10³)

Figure 2: Comparison of PassRate against inference token consumption between parallel and two treestructured sampling using different forking strategies.

balancing exploration and over-exploitation. These findings suggest that difficulty-adaptive rollout is not merely a heuristic for compute efficiency, but a strategic necessity for balancing the exploitation-exploration trade-off and maximizing the model’s reasoning coverage. Comprehensive theoretical analysis is provided in Appendix A. 2.2

Tree vs. Parallel Rollout

In RLVR, the primary challenge in expanding reasoning coverage is the scarcity of positive learning signals on complex problems. These signals emerge only when the model discovers a correct reasoning path. To address this, we investigate the properties of train-time rollout structures by comparing the conventional parallel rollout with a tree-structured rollout strategy, aiming to determine which topology more efficiently discovers correct trajectories. 2.2.1 Tree Rollout Algorithm We employ a generalized and simplified variant of the two-phase tree rollout strategy originally proposed by Hou et al. (2025). In the first phase, the model generates N independent base rollouts in parallel. Subsequently, in the second phase, we apply a forking point selection algorithm to identify K forking points within each base trajectory. From each selected forking point, we generate B additional branch rollouts, thereby expanding the exploration scope. Detailed algorithmic procedures are provided in Appendix C.1. 2.2.2 Empirical Analysis To analyze cost-efficiency during inference, we compare standard parallel sampling against two tree-structured rollout variants by analyzing PassRate—the probability of obtaining at least one correct solution—as a function of token consumption during generation. These variants include

fixed-seg, which selects the K forking points at equidistant intervals, and random, which selects them uniformly at random (detailed in Appendix C.2). As shown in Figure 2, both tree-structured variants achieve higher token efficiency than parallel sampling. Specifically, their performance curves demonstrate a steeper growth rate, yielding a higher PassRate for the same number of generated tokens. This enhanced efficiency stems from prefix sharing in tree structures, which avoids redundant regeneration of identical early segments and enables the exploration of alternative continuations within the same token budget (Tran et al., 2025; Hou et al., 2025). Furthermore, the choice of forking strategy also affects performance within tree-structured methods. While both fixed-seg and random outperform parallel sampling, fixed-seg consistently achieves a higher PassRate under comparable token budgets. This demonstrates that the effectiveness of treebased exploration depends not only on its structure but also on the placement of branching points.

of the top-k high-entropy sentences are selected as forking points. This strategy naturally evades localization while still targeting the most uncertain regions. We compare this approach with the conventional token-level method (tok-entropy) and three baselines: random, fixed-segment selection (fixed-seg), and Attention-based Tree Branching (ATB) (Liu et al., 2025a), which branches at steps receiving the highest attention weights. Detailed algorithmic procedures are provided in Appendix D.1.

2.3

2.3.2

Forking Point Selection in Tree Search

Section 2.2 shows that the performance of treestructured rollouts varies substantially across different forking strategies. In this section, we investigate which forking strategies most effectively identify correct solutions and promote semantically diverse reasoning paths. 2.3.1

The Localization Phenomenon and Sentence-level Forking

Previous studies primarily select top-k highentropy tokens as forking points (Hou et al., 2025; Zheng et al., 2025b; Cao et al., 2026), as they capture highly uncertain words that act as pivotal branching points (Wang et al., 2025; Cheng et al., 2025). However, we identify a critical limitation in this approach: the localization phenomenon (Figure 8). High-entropy tokens tend to densely cluster within narrow, highly uncertain segments of the reasoning trajectory. Consequently, the search budget is monopolized by repeated resampling within a localized cluster, which limits the structural reach of the search tree. To mitigate localization, we propose a sentencelevel forking strategy (sent-entropy), which expands the granularity of entropy estimation. In this approach, sentence entropy is calculated as the average entropy of its tokens, and the starting points

Method random fixed-seg ATB tok-entropy sent-entropy

PassRate

SibDiv

10.0 13.3 14.7 12.0 17.3

0.0796 0.0853 0.0874 0.1065 0.1049

Table 1: Comparison of forking point selection strategies when applied during inference. Best results are in bold, and second-best results are underlined.

Metrics for Measuring Diversity

While PassRate effectively captures task success, comprehensively evaluating these forking strategies also requires measuring whether the generated paths are semantically diverse. To directly quantify exploration diversity, we introduce an embeddingbased metric, Sibling Diversity (SibDiv). We first partition the reasoning tree into contiguous text blocks bounded by forking points or the end of the trajectory. SibDiv then computes the average pairwise cosine distance (i.e., 1−cosine similarity) between the embeddings of sibling blocks originating from the same forking point. By aggregating these values, this metric effectively evaluates how well the forking points promote semantically diverse reasoning branches. Formal definitions are provided in Appendix D.3. 2.3.3

Empirical Analysis

We evaluated each forking strategy by generating reasoning trees under a fixed inference budget, measuring PassRate and SibDiv (see Appendix D.4 for detailed experimental setups). The results are summarized in Table 1. First, tok-entropy achieves the highest SibDiv because performing additional sampling at the model’s most uncertain points naturally generates diverse immediate sibling blocks. However, due to the local-

ization phenomenon, this high SibDiv is strictly confined to a narrow segment of the reasoning path. The search fails to expand into meaningful structural differences across the entire reasoning tree, resulting in a low PassRate. By simply expanding the granularity of the entropy estimation, sent-entropy shows the highest PassRate while incurring minimal loss in SibDiv. In contrast, baselines such as fixed-seg and ATB inherently avoid localization, yielding higher PassRates than tok-entropy, but exhibit lower SibDiv since they do not utilize uncertainty signals. Ultimately, sent-entropy emerges as the most effective strategy by successfully translating high semantic diversity into a high PassRate.

Methodology

Building upon the empirical insights from Section 2, we propose DATPO (Difficulty-Adaptive Sentence-entropy-guided Tree-structured Policy Optimization) to expand a model’s intrinsic reasoning coverage (pass@k). An overview of the proposed framework is illustrated in Figure 3. 3.1

Difficulty-Adaptive Tree Search at Train-time

Building on the tree algorithm proposed in Section 2.2.1, we introduce a difficulty-adaptive tree search to dynamically allocate the search budget. The procedure operates in two phases. First, we generate N independent base rollouts and estimate the empirical difficulty of the prompt through their average verifiable reward V (root) ∈ [0, 1]. Second, we scale the tree expansion proportionally to this difficulty, where a lower V (root) indicates a more challenging problem, thus allocating more search budget. Given maximum budgets for forking points Kmax and branch rollouts Bmax , the adaptive parameters are computed as: K̂ = ⌈Kmax (1 − V (root))⌉

(1)

B̂ = ⌈Bmax (1 − V (root))⌉

(2)

Using the sent-entropy (Section 2.3.1), we identify K̂ forking points within each base trajectory and generate B̂ branches from each point. This mechanism entirely bypasses expansion only when V (root) = 1. For harder problems, it expands the search space up to N (1 + K̂ B̂) leaves. By scaling expansion based on difficulty, this strategy concentrates exploration on unsolved problems to maximize reasoning coverage.

Figure 3: Overview of the proposed DATPO framework.

3.2

Block-level Diversity-augmented Advantage Estimation

To optimize the policy, we partition trajectories into contiguous blocks bounded by forking points or the end of the trajectory. Advantages are computed and assigned at this block level. Since our tree search generates multiple branches from intermediate states, we reliably estimate state values using Monte Carlo (MC) returns (Kazemnejad et al., 2024). For a state s at any forking point, V̂M C (s) is the average verifiable reward of all its descending terminal blocks. For a terminal state sT without further rollouts, V̂M C (sT ) = 0. (b) (b) For a block b spanning from sstart to send , the base advantage is formulated as: (b)

(b)

Âbase (b) = r(b) + V̂M C (send ) − V̂M C (sstart ) (3) where the verifiable reward r(b) ∈ {0, 1} is assigned exclusively to terminal blocks; otherwise, it is 0. All tokens within b share this identical advantage. This block-level advantage assigns precise credit to intermediate steps, effectively facilitating implicit process supervision. To maximize the coverage-expanding benefits, we augment the base advantage with a siblingdiversity term Divsib (b), inspired by the SibDiv metric. Specifically, sibling blocks refer to the child blocks generated from a shared forking point. Divsib (b) is defined as the average cosine distance between the embedding of block b and its sibling blocks, effectively encouraging the model to discover distinct reasoning paths. Crucially, we apply this bonus exclusively to blocks with positive base advantages to avoid incentivizing the exploration of incorrect paths. The augmented advantage is: Â(b) = Âbase (b) + I(Âbase (b) > 0) · α · Divsib (b) (4)

Method

MATH500

AIME26

AIME25

AIME24

AMC23

Average

avg@8 pass@8 avg@64 pass@64 avg@64 pass@64 avg@64 pass@64 avg@64 pass@64 avg@k pass@k Base GRPO Dr.GRPO TreeRL AttnRL DATPO (Ours)

26.3 61.8 61.3 61.7 62.0 63.5

64.7 79.8 78.7 80.7 82.1 81.7

0.4 1.7 3.0 2.4 1.9 2.4

8.9 21.1 23.3 22.2 32.2 33.3

Qwen2.5-3B-Base 0.2 12.2 0.7 24.4 1.4 27.8 1.7 20.0 1.5 25.6 1.6 33.3

1.0 3.6 5.1 4.2 5.2 4.8

22.2 30.0 27.8 24.4 34.4 35.6

10.0 35.9 37.9 38.7 35.7 39.8

78.3 85.8 83.3 83.3 90.8 90.8

7.6 20.7 21.7 21.7 21.3 22.4

37.3 48.2 48.2 46.1 53.0 54.9

Base GRPO Dr.GRPO TreeRL AttnRL DATPO (Ours)

39.9 75.5 75.2 75.3 74.7 76.4

79.4 87.4 86.2 86.2 87.5 87.9

1.7 7.1 7.8 7.9 7.1 6.5

21.1 32.2 25.6 28.9 28.9 33.3

Qwen3-4B-Base 1.1 32.2 10.3 38.9 7.7 35.6 9.4 36.7 8.2 36.7 10.9 42.2

2.8 9.6 9.7 9.4 11.0 14.0

38.9 41.1 40.0 41.1 42.2 46.7

17.2 47.9 46.6 49.4 52.5 48.4

84.2 91.7 90.8 90.8 91.7 91.7

12.5 30.1 29.4 30.3 30.7 31.3

51.2 58.3 55.6 56.7 57.4 60.4

where I(·) is the indicator function, and the coefficient α is linearly annealed during training to gradually decay the exploration incentive, allowing the model to refine its learned reasoning paths. Finally, we optimize the policy directly across the generated tree topology. Given a set of contiguous blocks B generated for a prompt q, the DATPO objective is formulated as: " JDATPO (θ) = Eq∼Q,B∼πθold P

|b| XX

b∈B |b| b∈B t=1

MATH500 Accuracy (%)

Table 2: Evaluation results on mathematical reasoning benchmarks. We report avg@k and pass@k for each dataset.

64 61 58

DATPO (Ours) AttnRL TreeRL

55 0

100

200

300

400

500

Training Step

600

700

Figure 4: Learning curves of MATH500 accuracy over training steps for tree-based methods. (Smoothed)

min ρb,t (θ)Â(b), clip ρb,t (θ), # 1 − ϵ, 1 + ϵ Â(b) , (5) where |b| is the sequence length of block b, and Â(b) is the block-level augmented advantage. Comprehensive algorithmic details and training procedures are provided in Appendix E.

Experiments

4.1

Experimental Setup

Models and Datasets We use Qwen2.5-3B-Base (Yang et al., 2024) and Qwen3-4B-Base (Yang et al., 2025) as base models. For training, we use the MATH dataset (Hendrycks et al., 2021). Evaluation We evaluate the trained models on mathematical reasoning benchmarks, specifically MATH500 (Hendrycks et al., 2021), AIME26, AIME25, AIME24, and AMC23. Using a temperature of 1.0, we report avg@k as the primary

evaluation metric across all benchmarks. Additionally, we report pass@k to assess the reasoning coverage of the trained models. For robustness, the pass@k results are computed by averaging over three independent evaluation runs. Baselines We compare DATPO against the Base model and several advanced RLVR baselines. These include GRPO (Shao et al., 2024) (enhanced with clip-higher and token-level loss (Yu et al., 2025b)) and its variant, Dr.GRPO (Liu et al., 2025b). Furthermore, we evaluate two tree-based methods: TreeRL (Hou et al., 2025), which utilizes top-k high-entropy forking and combined localglobal advantages, and AttnRL (Liu et al., 2025a), which leverages attention-based forking, adaptive sampling, and a one-step off-policy for enhanced efficiency. To ensure a fair comparison, we maintain a comparable total number of generated tokens per problem across all methods while adopting the treeexpansion hyperparameters reported in the original TreeRL and AttnRL papers. Comprehensive details for experiments are provided in Appendix F.

80 75

8 0

PassRate (%)

avg@k maj@k

+7.2

26 24 +5.9

+4.6

+4.5

+6.2

22 20

Level 1 Level 2 Level 3 Level 4 Level 5

Figure 5: Comparison of average leaf count generated at train-time and PassRate across difficulty levels for tree-based methods.

4.2

DATPO AttnRL TreeRL

Accuracy (%)

100

Avg. Leaves

DATPO AttnRL 32 TreeRL

GRPO Dr.GRPO TreeRL AttnRL DATPO

Figure 6: Test-time scaling performance using majority voting (maj@k). The green arrows indicate the performance improvement of maj@k over avg@k.

Main Results

Mathematical Reasoning Performance As reported in Table 2, DATPO achieves the best aggregate avg@k and pass@k across the evaluated benchmarks. Notably, while the improvements in single-sample accuracy (avg@k) are marginal compared to the strongest baseline, AttnRL (e.g., +1.1 and +0.6 on Qwen2.5-3B-Base and Qwen34B-Base, respectively), DATPO achieves substantial gains in pass@k, outperforming AttnRL by +1.9 and +3.0, respectively. This indicates that DATPO’s difficulty-adaptive rollout and siblingdiversity term successfully expand the model’s intrinsic reasoning coverage. Analysis of Training Dynamics We first examine the MATH500 accuracy over training steps (Figure 4). While all three tree-based methods exhibit similar accuracy gains during the initial training steps, TreeRL and AttnRL fail to sustain this upward trend, eventually plateauing or even suffering performance degradation. In contrast, DATPO shows a consistent upward trend throughout the training. This stability can be attributed to the annealed sibling-diversity term, which injects semantic diversity early in training to prevent premature convergence. Furthermore, we analyze the search behavior during training by comparing the average leaf count and PassRate across the difficulty levels of the MATH dataset (Figure 5). Note that these difficulty labels are used strictly for this analysis and were not provided to the model during training. Unlike TreeRL, which maintains a fixed leaf count across all difficulties, DATPO and AttnRL employ difficulty-adaptive rollouts. However, DATPO allocates fewer rollouts to easy problems and significantly more rollouts to hard problems compared to AttnRL. The latter’s adaptive strategy relies heavily

on an attention-based filtering mechanism that simply discards problems with below-average attention scores to maximize computational efficiency. Because this approach acts as a rigid cut-off, it fails to concentrate computational resources on the most challenging problems. Consequently, DATPO’s highly adaptive resource allocation enables it to achieve a higher PassRate on harder problems (Levels 4 and 5) compared to other tree-based methods. 4.3

Test-time Scaling Performance

In this section, we investigate whether the substantial gains in pass@k directly translate into improved test-time scaling performance. To this end, we apply majority voting (maj@k) (Wang et al., 2022)—one of the simplest and most widely adopted test-time scaling strategies—to compare the methods applied to Qwen2.5-3B-Base. We evaluate the effectiveness of these methods across five mathematical reasoning benchmarks, applying k = 8 for MATH500 and k = 64 for the remaining datasets. For robustness, all maj@k results are computed as the average over three independent evaluation runs. As illustrated by the average performance across five benchmarks in Figure 6, DATPO, which achieved the highest pass@k during training, also shows the largest maj@k gain, improving by +7.2 over its avg@k. This demonstrates that expanding a model’s reasoning coverage during training directly enhances test-time scaling performance. 4.4

Ablation Studies

Effect of Forking Strategies Building upon the analysis during inference presented in Section 2.3, we further investigate the impact of different forking strategies during training. We compare DATPO’s default sent-entropy strategy against

Method random fixed-seg ATB tok-entropy sent-entropy

MATH500 avg@8

pass@8

61.5 61.1 62.1 61.3 63.5

81.6 80.6 80.7 80.3 81.7

α 0→0 0.2 → 0 0.4 → 0 0.2 → 0, all 0.2 → 0.2 0.2 → -0.2

MATH500 avg@8

pass@8

62.1 63.5 61.9 61.6 61.5 63.4

81.4 81.7 81.3 81.3 82.0 81.0

Table 3: Ablation study on different forking strategies.

four alternatives: random, fixed-seg, ATB, and tok-entropy, evaluating their performance on the MATH500 benchmark. As reported in Table 3, the sent-entropy yields the highest performance. This confirms our hypothesis: the sent-entropy effectively guides exploration using the model’s uncertainty, while avoiding localization that limits tok-entropy. Effect of Sibling-Diversity To evaluate the effect of the sibling-diversity term, we conduct an ablation study by varying the coefficient α, and evaluate the performance on the MATH500 benchmark, as summarized in Table 4. The results show that the 0.2 → 0 schedule is the most effective, surpassing both the baseline without diversity (0 → 0) and a higher initial coefficient (0.4 → 0). Furthermore, applying the diversity bonus to all blocks (0.2 → 0, all) degrades performance compared to the baseline without diversity, highlighting the need to reward diversity exclusively on valid paths. Annealing is also critical: a constant α (0.2 → 0.2) severely degrades avg@8 despite slight pass@8 gains. Conversely, annealing α to a negative value (0.2 → −0.2) improves avg@8 but noticeably harms pass@8, confirming that penalizing diversity in the later stages of training restricts the model’s reasoning coverage.

Related Work

Reinforcement Learning for LLM Reasoning RLVR has become the standard for post-training of reasoning LLMs. A representative method is Group Relative Policy Optimization (GRPO) (Shao et al., 2024), which replaces the costly critic model of PPO (Schulman et al., 2017) with efficient groupbased advantage estimation. Recent studies build on this framework to enhance stability and resolve optimization issues: DAPO (Yu et al., 2025b) prevents mode collapse through decoupled clipping and dynamic sampling, while Dr.GRPO (Liu et al.,

Table 4: Ablation study on the diversity coefficient α. The right arrow (→) indicates the linear annealing schedule during training. The all applies the diversity term to all blocks, rather than exclusively to those with positive base advantages.

2025b) corrects inherent structural biases in the advantage computation. Exploration Strategies in RLVR RLVR often fails to expand a model’s intrinsic reasoning capacity (pass@k) beyond its base capabilities (Yue et al., 2025; Dang et al., 2025; Wu et al., 2025). To overcome this exploration bottleneck, recent studies introduce explicit mechanisms to diversify search. PKPO (Walder and Karkhanis, 2025) directly optimizes pass@k to solve harder instances, while R1-zero-Div (Yao et al., 2025) and FOR (Yu et al., 2025a) use diversity-aware objectives and divergent reasoning flows to prevent trajectory collapse. Tree-based Search in Reinforcement Learning Proven in RL milestones like AlphaGo (Silver et al., 2016), tree-based search is now adapted to LLMs to enable systematic exploration. TreeRL (Hou et al., 2025) pioneers this with an on-policy framework using entropy-guided branching. To address computational bottlenecks, AttnRL (Liu et al., 2025a) improves efficiency by leveraging difficulty-aware adaptive sampling within a onestep off-policy pipeline. While these methods use trees primarily for credit assignment or computational efficiency, we leverage them to expand the model’s reasoning coverage.

Conclusion

In this work, we investigate the structural design of train-time rollouts in RLVR to expand the intrinsic reasoning coverage. Our analysis reveals that expanding reasoning coverage can benefit from moving beyond uniform parallel sampling toward difficulty-adaptive resource allocation and the struc-

tural advantages of sentence-entropy-guided tree search. Integrating these principles, we propose DATPO, which explicitly encourages semantic exploration through a sibling-diversity term. Experiments on mathematical benchmarks validate our approach, showing significant improvements in pass@k.

Limitations While DATPO significantly expands reasoning coverage, calculating the sibling-diversity term requires additional forward passes through an external embedding model, which introduces computational overhead. Additionally, while our block-level formulation effectively assigns process-level credit across the tree topology, it relies on small sample sizes. Deriving both the empirical difficulty and Monte Carlo state values from a limited number of rollouts (e.g., N = 4, B = 4) can inject noise into the estimations, occasionally yielding high variance during policy updates. Finally, resource limitations restricted our empirical validation to the 3B-4B parameter regime, leaving DATPO’s scalability to larger models (≥ 7B) unverified. Furthermore, as our evaluation primarily focuses on mathematical reasoning, the framework’s direct effectiveness in other rigorous domains, such as complex logical reasoning or code generation, requires further investigation.

Acknowledgments This work was supported by the Institute of Information & Communications Technology Planning & Evaluation (IITP) grants funded by the Korea government (MSIT) (No. RS-2019-II191906, Artificial Intelligence Graduate School Program (POSTECH); IITP-2026-RS-2026-25616370, AI Star Fellowship Support Program) and by the National Research Foundation of Korea (NRF) grant funded by the Korea government (MSIT) (No. RS2024-00335873).

References Bradley Brown, Jordan Juravsky, Ryan Ehrlich, Ronald Clark, Quoc V Le, Christopher Ré, and Azalia Mirhoseini. 2024. Large language monkeys: Scaling inference compute with repeated sampling. arXiv preprint arXiv:2407.21787. Lang Cao, Hui Ruan, Yongqian Li, Peng Chao, Wu Ning, Haonan Song, Renhong Chen, and Yi-

tong Li. 2026. Treeadv: Tree-structured advantage redistribution for group-based rl. arXiv preprint arXiv:2601.03703. Jianlyu Chen, Shitao Xiao, Peitian Zhang, Kun Luo, Defu Lian, and Zheng Liu. 2024. M3embedding: Multi-linguality, multi-functionality, multi-granularity text embeddings through selfknowledge distillation. In Findings of the Association for Computational Linguistics: ACL 2024, pages 2318–2335, Bangkok, Thailand. Association for Computational Linguistics. Daixuan Cheng, Shaohan Huang, Xuekai Zhu, Bo Dai, Wayne Xin Zhao, Zhenliang Zhang, and Furu Wei. 2025. Reasoning with exploration: An entropy perspective. arXiv preprint arXiv:2506.14758. Xingyu Dang, Christina Baek, J Zico Kolter, and Aditi Raghunathan. 2025. Assessing diversity collapse in reasoning. In Scaling Self-Improving Foundation Models without Human Supervision. Daya Guo, Dejian Yang, Haowei Zhang, Junxiao Song, Peiyi Wang, Qihao Zhu, Runxin Xu, Ruoyu Zhang, Shirong Ma, Xiao Bi, and 1 others. 2025. Deepseek-r1: Incentivizing reasoning capability in llms via reinforcement learning. arXiv preprint arXiv:2501.12948. Rui Ha, Chaozhuo Li, Rui Pu, Litian Zhang, Xi Zhang, and Sen Su. 2025. DSG-MCTS: A dynamic strategyguided Monte Carlo tree search for diversified reasoning in large language models. In Proceedings of the 2025 Conference on Empirical Methods in Natural Language Processing, pages 10530–10544, Suzhou, China. Association for Computational Linguistics. Dan Hendrycks, Collin Burns, Saurav Kadavath, Akul Arora, Steven Basart, Eric Tang, Dawn Song, and Jacob Steinhardt. 2021. Measuring mathematical problem solving with the math dataset. arXiv preprint arXiv:2103.03874. Zhenyu Hou, Ziniu Hu, Yujiang Li, Rui Lu, Jie Tang, and Yuxiao Dong. 2025. Treerl: Llm reinforcement learning with on-policy tree search. arXiv preprint arXiv:2506.11902. Aaron Jaech, Adam Kalai, Adam Lerer, Adam Richardson, Ahmed El-Kishky, Aiden Low, Alec Helyar, Aleksander Madry, Alex Beutel, Alex Carney, and 1 others. 2024. Openai o1 system card. arXiv preprint arXiv:2412.16720. Zishang Jiang, Jinyi Han, Tingyun Li, Xinyi Wang, Sihang Jiang, Jiaqing Liang, Zhaoqian Dai, Shuguang Ma, Fei Yu, and Yanghua Xiao. 2025. Selective expert guidance for effective and diverse exploration in reinforcement learning of llms. arXiv preprint arXiv:2510.04140. Amirhossein Kazemnejad, Milad Aghajohari, Eva Portelance, Alessandro Sordoni, Siva Reddy, Aaron Courville, and Nicolas Le Roux. 2024. Vineppo: Refining credit assignment in rl training of llms. arXiv preprint arXiv:2410.01679.

Yizhi Li, Qingshui Gu, Zhoufutu Wen, Ziniu Li, Tianshun Xing, Shuyue Guo, Tianyu Zheng, Xin Zhou, Xingwei Qu, Wangchunshu Zhou, and 1 others. 2025a. Treepo: Bridging the gap of policy optimization and efficacy and inference efficiency with heuristic tree-based modeling. arXiv preprint arXiv:2508.17445. Ziniu Li, Congliang Chen, Tianyun Yang, Tian Ding, Ruoyu Sun, Ge Zhang, Wenhao Huang, and ZhiQuan Luo. 2025b. Knapsack rl: Unlocking exploration of llms via optimizing budget allocation. arXiv preprint arXiv:2509.25849. Mengqi Liao, Xiangyu Xi, Chen Ruinian, Jia Leng, Yangen Hu, Ke Zeng, Shuai Liu, and Huaiyu Wan. 2025. Enhancing efficiency and exploration in reinforcement learning for LLMs. In Proceedings of the 2025 Conference on Empirical Methods in Natural Language Processing, pages 1451–1463, Suzhou, China. Association for Computational Linguistics. Runze Liu, Jiakang Wang, Yuling Shi, Zhihui Xie, Chenxin An, Kaiyan Zhang, Jian Zhao, Xiaodong Gu, Lei Lin, Wenping Hu, and 1 others. 2025a. Attention as a compass: Efficient exploration for processsupervised rl in reasoning models. arXiv preprint arXiv:2509.26628. Zichen Liu, Changyu Chen, Wenjun Li, Penghui Qi, Tianyu Pang, Chao Du, Wee Sun Lee, and Min Lin. 2025b. Understanding r1-zero-like training: A critical perspective. arXiv preprint arXiv:2503.20783. Nils Reimers and Iryna Gurevych. 2019. SentenceBERT: Sentence embeddings using Siamese BERTnetworks. In Proceedings of the 2019 Conference on Empirical Methods in Natural Language Processing and the 9th International Joint Conference on Natural Language Processing (EMNLP-IJCNLP), pages 3982–3992, Hong Kong, China. Association for Computational Linguistics. David Rein, Betty Li Hou, Asa Cooper Stickland, Jackson Petty, Richard Yuanzhe Pang, Julien Dirani, Julian Michael, and Samuel R Bowman. 2023. Gpqa: A graduate-level google-proof q&a benchmark. arXiv preprint arXiv:2311.12022. Nipun Sadvilkar and Mark Neumann. 2020. PySBD: Pragmatic sentence boundary disambiguation. In Proceedings of Second Workshop for NLP Open Source Software (NLP-OSS), pages 110–114, Online. Association for Computational Linguistics. John Schulman, Filip Wolski, Prafulla Dhariwal, Alec Radford, and Oleg Klimov. 2017. Proximal policy optimization algorithms. arXiv preprint arXiv:1707.06347. Zhihong Shao, Peiyi Wang, Qihao Zhu, Runxin Xu, Junxiao Song, Xiao Bi, Haowei Zhang, Mingchuan Zhang, YK Li, Yang Wu, and 1 others. 2024. Deepseekmath: Pushing the limits of mathematical reasoning in open language models. arXiv preprint arXiv:2402.03300.

David Silver, Aja Huang, Chris J Maddison, Arthur Guez, Laurent Sifre, George Van Den Driessche, Julian Schrittwieser, Ioannis Antonoglou, Veda Panneershelvam, Marc Lanctot, and 1 others. 2016. Mastering the game of go with deep neural networks and tree search. nature, 529(7587):484–489. Nisan Stiennon, Long Ouyang, Jeffrey Wu, Daniel Ziegler, Ryan Lowe, Chelsea Voss, Alec Radford, Dario Amodei, and Paul F Christiano. 2020. Learning to summarize with human feedback. Advances in neural information processing systems, 33:3008– 3021. Kimi Team, Angang Du, Bofei Gao, Bowei Xing, Changjiu Jiang, Cheng Chen, Cheng Li, Chenjun Xiao, Chenzhuang Du, Chonghua Liao, Chuning Tang, Congcong Wang, Dehao Zhang, Enming Yuan, Enzhe Lu, Fengxiang Tang, Flood Sung, Guangda Wei, Guokun Lai, and 77 others. 2025. Kimi k1.5: Scaling reinforcement learning with llms. Preprint, arXiv:2501.12599. Hieu Tran, Zonghai Yao, and Hong Yu. 2025. Exploiting tree structure for credit assignment in rl training of llms. arXiv preprint arXiv:2509.18314. Christian Walder and Deep Karkhanis. 2025. Pass@ k policy optimization: Solving harder reinforcement learning problems. arXiv preprint arXiv:2505.15201. Shenzhi Wang, Le Yu, Chang Gao, Chujie Zheng, Shixuan Liu, Rui Lu, Kai Dang, Xionghui Chen, Jianxin Yang, Zhenru Zhang, and 1 others. 2025. Beyond the 80/20 rule: High-entropy minority tokens drive effective reinforcement learning for llm reasoning. arXiv preprint arXiv:2506.01939. Xuezhi Wang, Jason Wei, Dale Schuurmans, Quoc Le, Ed Chi, Sharan Narang, Aakanksha Chowdhery, and Denny Zhou. 2022. Self-consistency improves chain of thought reasoning in language models. arXiv preprint arXiv:2203.11171. Yubo Wang, Xueguang Ma, Ge Zhang, Yuansheng Ni, Abhranil Chandra, Shiguang Guo, Weiming Ren, Aaran Arulraj, Xuan He, Ziyan Jiang, and 1 others. 2024. Mmlu-pro: A more robust and challenging multi-task language understanding benchmark. Advances in Neural Information Processing Systems, 37:95266–95290. Jason Wei, Xuezhi Wang, Dale Schuurmans, Maarten Bosma, Fei Xia, Ed Chi, Quoc V Le, Denny Zhou, and 1 others. 2022. Chain-of-thought prompting elicits reasoning in large language models. Advances in neural information processing systems, 35:24824– 24837. Fang Wu, Weihao Xuan, Ximing Lu, Mingjie Liu, Yi Dong, Zaid Harchaoui, and Yejin Choi. 2025. The invisible leash: Why rlvr may or may not escape its origin. arXiv preprint arXiv:2507.14843. Shangyu Xing, Siyuan Wang, Chenyuan Yang, Xinyu Dai, and Xiang Ren. 2025. Lookahead tree-based

rollouts for enhanced trajectory-level exploration in reinforcement learning with verifiable rewards. arXiv preprint arXiv:2510.24302. An Yang, Anfeng Li, Baosong Yang, Beichen Zhang, Binyuan Hui, Bo Zheng, Bowen Yu, Chang Gao, Chengen Huang, Chenxu Lv, Chujie Zheng, Dayiheng Liu, Fan Zhou, Fei Huang, Feng Hu, Hao Ge, Haoran Wei, Huan Lin, Jialong Tang, and 41 others. 2025. Qwen3 technical report. arXiv preprint arXiv:2505.09388. An Yang, Baosong Yang, Beichen Zhang, Binyuan Hui, Bo Zheng, Bowen Yu, Chengyuan Li, Dayiheng Liu, Fei Huang, Haoran Wei, Huan Lin, Jian Yang, Jianhong Tu, Jianwei Zhang, Jianxin Yang, Jiaxi Yang, Jingren Zhou, Junyang Lin, Kai Dang, and 22 others. 2024. Qwen2.5 technical report. arXiv preprint arXiv:2412.15115. Jian Yao, Ran Cheng, Xingyu Wu, Jibin Wu, and Kay Chen Tan. 2025. Diversity-aware policy optimization for large language model reasoning. arXiv preprint arXiv:2505.23433. Fangxu Yu, Lai Jiang, Haoqiang Kang, Shibo Hao, and Lianhui Qin. 2025a. Flow of reasoning: Training llms for divergent reasoning with minimal examples. In Forty-second International Conference on Machine Learning. Qiying Yu, Zheng Zhang, Ruofei Zhu, Yufeng Yuan, Xiaochen Zuo, Yu Yue, Weinan Dai, Tiantian Fan, Gaohong Liu, Lingjun Liu, and 1 others. 2025b. Dapo: An open-source llm reinforcement learning system at scale. arXiv preprint arXiv:2503.14476. Yang Yue, Zhiqi Chen, Rui Lu, Andrew Zhao, Zhaokai Wang, Shiji Song, and Gao Huang. 2025. Does reinforcement learning really incentivize reasoning capacity in llms beyond the base model? arXiv preprint arXiv:2504.13837. Xin Zhang, Yanzhao Zhang, Dingkun Long, Wen Xie, Ziqi Dai, Jialong Tang, Huan Lin, Baosong Yang, Pengjun Xie, Fei Huang, Meishan Zhang, Wenjie Li, and Min Zhang. 2024. mGTE: Generalized longcontext text representation and reranking models for multilingual text retrieval. In Proceedings of the 2024 Conference on Empirical Methods in Natural Language Processing: Industry Track, pages 1393–1412, Miami, Florida, US. Association for Computational Linguistics. Yuheng Zhang, Wenlin Yao, Changlong Yu, Yao Liu, Qingyu Yin, Bing Yin, Hyokun Yun, and Lihong Li. 2025. Improving sampling efficiency in rlvr through adaptive rollout and response reuse. arXiv preprint arXiv:2509.25808. Eric Zhao, Pranjal Awasthi, and Sreenivas Gollapudi. 2025. Sample, scrutinize and scale: Effective inference-time search by scaling verification. arXiv preprint arXiv:2502.01839.

Haizhong Zheng, Yang Zhou, Brian R Bartoldson, Bhavya Kailkhura, Fan Lai, Jiawei Zhao, and Beidi Chen. 2025a. Act only when it pays: Efficient reinforcement learning for llm reasoning via selective rollouts. arXiv preprint arXiv:2506.02177. Tianyu Zheng, Tianshun Xing, Qingshui Gu, Taoran Liang, Xingwei Qu, Xin Zhou, Yizhi Li, Zhoufutu Wen, Chenghua Lin, Wenhao Huang, and 1 others. 2025b. First return, entropy-eliciting explore. arXiv preprint arXiv:2507.07017.

Theoretical Analysis of Difficulty-Adaptive Rollout

We provide a theoretical analysis of the empirical findings in Section 2.1. In particular, we explain why increasing the rollout budget G consistently improves the expected avg@k, while the behavior of pass@k can vary across difficulty subsets. Notation.

For a prompt x and a policy πθ , let px (θ) :=

[r(y) = 1]

y∼πθ (·|x)

denote the single-sample correctness probability under a binary verifiable reward r(y) ∈ {0, 1}. In empirical evaluations, metrics are computed over a finite set of k independent samples Y = i.i.d. (y (1) , . . . , y (k) ) ∼ πθ (· | x). We define the empirical estimators as: k X

\ x (θ) := 1 r y (j) , avg@k k j=1   k X \ x (θ) := I pass@k r y (j) ≥ 1 . j=1

However, to rigorously analyze the optimization dynamics, we focus on their expected values with respect to the policy. Throughout this analysis, we omit the hat notation and define avg@kx (θ) and pass@kx (θ) strictly as these theoretical expectations: h i \ x (θ) avg@kx (θ) := EY∼πθ avg@k = px (θ) and h i \ x (θ) pass@kx (θ) := EY∼πθ pass@k k = 1 − 1 − px (θ) . By formulating these metrics as expectations, the theoretical avg@k rigorously simplifies to the single-sample success probability px (θ). For the analysis below, given the current policy parameters θ, let + θG := θ + ηĝG (x)

denote one GRPO update with rollout group size G, learning rate η, and stochastic gradient estimator ĝG (x). We consider only the reward-advantage component of the GRPO update, excluding auxiliary regularization terms.

Theorem A.1 (One-step expected avg@k improvement with rollout budget). Fix a prompt x and a policy πθ . Let p := px (θ) ∈ (0, 1), and let SG ∼ Binomial(G, p) denote the number of correct responses in a rollout group size G ≥ 2. Assume px (·) is twice continuously differentiable with a bounded Hessian, and the gradient estimator satisfies E[∥ĝG (x)∥2 ] < ∞. Further assume: A1. The update vanishes if all group rewards are identical: ĝG (x) = 0 almost surely if SG ∈ {0, G}. A2. The expected update direction on mixedreward batches is a positive constant cx > 0 independent of G: E[⟨∇θ px (θ), ĝG (x)⟩ | 1 ≤ SG ≤ G − 1] = cx . Then, for sufficiently small η, the expected correctness probability satisfies: + E[px (θG )] = px (θ) + ηcx ΨG (p) + OG (η 2 ),

where ΨG (p) := 1 − pG − (1 − p)G . Consequently, for any finite set of rollout budgets G, there exists η0 > 0 such that for all η ∈ (0, η0 ) and any G1 , G2 ∈ G with G2 > G1 : + + E[px (θG )] > E[px (θG )]. 2 1

Furthermore, the first-order gain coefficient ΨG (p) is strictly increasing in G with diminishing returns. Proof. By definition, theoretical expected avg@k simplifies to the single-sample correctness probability px (θ). Let EG := {1 ≤ SG ≤ G − 1} be the event of a mixed-reward batch, which occurs with probability Pr(EG ) = 1−(1−p)G −pG = ΨG (p). By A1, the update is zero outside EG . Applying A2, the expected directional derivative is: E[⟨∇θ px (θ), ĝG (x)⟩] = Pr(EG )E[⟨∇θ px (θ), ĝG (x)⟩ | EG ] = cx ΨG (p). Since px (·) has a bounded Hessian on the update region, Taylor’s theorem gives + px (θG ) = px (θ) + η ⟨∇θ px (θ), ĝG (x)⟩ + RG (η),

where, for some Hessian bound L < ∞, |RG (η)| ≤ L2 η 2 ∥ĝG (x)∥2 . Taking expectations

and using E[∥ĝG (x)∥2 ] < ∞ gives E[RG (η)] = OG (η 2 ), completing the first claim. To establish monotonicity, we evaluate the marginal increase in ΨG (p) for p ∈ (0, 1): G

ΨG+1 (p) − ΨG (p) = p(1 − p) + (1 − p)p > 0, confirming ΨG (p) strictly increases with G. For any G2 > G1 , the first-order difference ηcx (ΨG2 (p)−ΨG1 (p)) is strictly positive and dominates the OG1 ,G2 (η 2 ) remainder term for η strictly less than some threshold η0 (G1 , G2 ) > 0. Taking the minimum η0 across all pairs in the finite set G establishes the strict ordering simultaneously. Finally, the second difference of ΨG (p) is −p2 (1 − p)G − (1 − p)2 pG < 0, confirming diminishing returns. Remark on Assumption 2. A2 serves as an idealized first-order approximation to isolate the core mechanism: larger groups increase the mixed-reward probability ΨG (p), thereby providing nonzero relative reward signals more frequently. In practice, GRPO normalizes advantages relative to p the group (e.g., the positive advantage scales as (G − s)/s), meaning the exact expected magnitude cx technically depends on G. However, this assumption keeps the mechanism analytically transparent and highlights a plausible first-order driver of the empirical monotonicity observed during training. Remark on advantage-estimation variance. Our analysis isolates the signal-availability mechanism, demonstrating that a larger G yields more frequent informative updates. We do not explicitly model the variance reduction in advantage estimation to avoid complex distributional assumptions. Therefore, this theorem formalizes one core driver of the avg@k improvement, acknowledging that other statistical benefits also contribute. Extension to Dataset-Level Notation. While Theorem A.1 characterizes the optimization dynamics of a single prompt, explaining the difficultydependent behavior requires dataset-level formalization. Let px,d (G) denote the single-sample correctness probability on a test prompt x ∈ D for a policy trained on difficulty subset d using rollout budget G. We define the expected average correctness (µd (G)) and pass@k over the dataset D as: µd (G) := Ex∼D [px,d (G)], h k i (d) pass@kD (G) := Ex∼D 1 − 1 − px,d (G) .

Theorem A.2 (Variance Penalty Decomposition of pass@k). Fix k ≥ 2. Let fk (p) := 1 − (1 − p)k and define the Jensen gap (d) Jk,d (G) := fk µd (G) − pass@kD (G). Then the following hold: 1. Jk,d (G) ≥ 0, with equality if and only if px,d (G) is constant almost surely over x ∼ D. 2. For any two rollout budgets G2 > G1 , (d)

(d)

pass@kD (G2 ) − pass@kD (G1 ) = fk µd (G2 ) − fk µd (G1 ) | {z } gain from higher avg@kD

−

Jk,d (G2 ) − Jk,d (G1 ) | {z }

loss from test-set prompt heterogeneity

Moreover, if σd2 (G) := Varx∼D [px,d (G)], then Jk,d (G) =

k−2 2 k(k − 1) 1 − µd (G) σd (G) 2 + O Ex∼D |px,d (G) − µd (G)|3 .

Hence, to second order, the penalty term is controlled by the cross-prompt dispersion of onesample success probabilities on the test set. Proof. For k ≥ 2 and p ∈ (0, 1), fk′ (p) = k(1 − p)k−1 > 0, fk′′ (p) = −k(k − 1)(1 − p)k−2 < 0, so fk is strictly increasing and strictly concave on (0, 1). By definition, the expected mean is µd (G) = Ex∼D [px,d (G)], and the expected pass rate is (d)

pass@kD (G) = Ex∼D [fk (px,d (G))]. Applying Jensen’s inequality to the concave function fk , (d)

pass@kD (G) = Ex∼D [fk (px,d (G))] ≤ fk (Ex∼D [px,d (G)]) = fk µd (G) . Thus Jk,d (G) ≥ 0. Since fk is strictly concave, equality holds if and only if px,d (G) is constant almost surely.

Now rewrite (d) pass@kD (G) = fk µd (G) − Jk,d (G). Subtracting the identities for G2 and G1 yields (d)

(d)

pass@kD (G2 ) − pass@kD (G1 ) = fk µd (G2 ) − fk µd (G1 ) − Jk,d (G2 ) − Jk,d (G1 ) ,

specific training dynamics. Consequently, while these exact behavioral patterns may not identically manifest in every setup, bridging this theoretical mechanism with our specific findings allows us to formally characterize the three observed regimes as follows: Easy:

∆G Jk,Easy (G) > ∆G fk,Easy (G)

=⇒

pass@kD

(Easy)

(G + 1) < pass@kD

(G),

Hard: ∆G Jk,Hard (G) < ∆G fk,Hard (G) which gives the exact decomposition. (Hard) (Hard) =⇒ pass@kD (G + 1) > pass@kD (G), For the second-order approximation, apply Taylor’s theorem around µd (G): Medium: ∆G Jk,Medium (G) crosses ∆G fk,Medium (G) fk (px,d (G)) = fk µd (G) (Medium) =⇒ pass@kD (G) is non-monotonic. + fk′ µd (G) px,d (G) − µd (G) 2 1 + fk′′ µd (G) px,d (G) − µd (G) where ∆G Jk,d (G) = Jk,d (G + 1) − Jk,d (G) and 2 ∆ G fk,d (G) = fk (µd (G + 1)) − fk (µd (G)). + O(|px,d (G) − µd (G)|3 ). Analytically, the second-order approximation reveals that the penalty term Jk,d (G) is directly Taking the expectation over x ∼ D, the linear term 2 vanishes because Ex∼D [px,d (G) − µd (G)] = 0. proportional to the cross-prompt variance σd (G). This theoretically explains the paradoxical degraHence dation in pass@kD observed when training on the Ex∼D [fk (px,d (G))] = fk µd (G) Easy dataset. When the rollout budget G is large, 2 1 ′′ the policy over-exploits specific, easily solvable + fk µd (G) σd (G) templates rather than learning generalizable rea2 soning skills. Evaluated on a general test set, this + O Ex∼D |px,d (G) causes severe polarization: the success probability 3 px,d (G) converges to 1 for familiar easy prompts − µd (G)| . but remains near 0 for unseen or harder problems. Rearranging gives Consequently, the surge in the variance penalty (∆G Jk,Easy (G)) outweighs the marginal gains in 1 mean performance (∆G fk,Easy (G)), resulting in a Jk,d (G) = − fk′′ µd (G) σd2 (G) 2 decrease in the overall pass@kD . + O Ex∼D |px,d (G) − µd (G)|3 , Conversely, on the Hard dataset, valid reasoning paths are scarce. An increased rollout budget proand substituting fk′′ (µ) = −k(k − 1)(1 − µ)k−2 motes broader exploration, enabling the model to completes the proof. internalize more generalizable reasoning patterns. This uniformly improves the test-set mean µd (G) Connection to Empirical Regimes. Rather than across prompts, maintaining low cross-prompt varipositing a universal law applicable to all training enance and keeping the associated penalty minimal. vironments, Theorem A.2 provides a rigorous analytical lens to interpret the specific empirical obser- B Experimental Details of Section 2.1 vations reported in Section 2.1. Specifically, while the theorem formally establishes the mathematical We train Qwen2.5-3B-Instruct (Yang et al., 2024) mechanism—that the dynamics of pass@kD are on the MATH (Hendrycks et al., 2021) dataset, entirely governed by a trade-off between the mean which we partition into Easy, Medium, and Hard improvement gain (∆fk ) and the cross-prompt vari- subsets based on the base model’s empirical accuance penalty (∆Jk,d )—the actual increase of this racy. Specifically, for each problem, we sample variance (σd2 (G)) is an empirical characteristic dic- 12 independent solutions from the base model and tated by the intrinsic difficulty of the dataset and categorize problems according to the number of

Training Configuration Easy / G = 4 Easy / G = 8 Easy / G = 16 Medium / G = 4 Medium / G = 8 Medium / G = 16 Hard / G = 4 Hard / G = 8 Hard / G = 16

Wall Clock (Hours) 5.0 9.2 16.4 5.4 9.4 16.6 5.5 9.9 17.5

Table 5: Wall Clock Time for each difficulty subset and rollout budget.

correct samples. Problems for which all 12 samples are either entirely correct or entirely incorrect are excluded, as they provide no informative signal for distinguishing difficulty. Among the remaining problems, those with 1–4 correct samples are categorized as Hard, 5–8 as Medium, and 9–11 as Easy. This results in 2,217 Easy, 1,433 Medium, and 1,712 Hard problems. To ensure a balanced training distribution, we subsample each subset to 1,400 problems. The model was trained for 5 epochs on each difficulty-specific dataset. Using GRPO (Shao et al., 2024), we conduct a total of 9 training runs, applying rollout budgets of G ∈ {4, 8, 16} for each difficulty subset. Our implementation is based on a modified version of the GRPO-Zero repository2 , which adopts a tokenlevel policy gradient without KL regularization or clipping. We use a binary verifiable reward, assigning 1 to correct final answers and 0 otherwise. During training, all samples are generated with temperature 1.0 and a maximum generation length of 1024 tokens. We fix all optimization hyperparameters, including a batch size of 256, while adjusting the number of problems per batch (64, 32, 16) to realize group sizes of 4, 8, and 16, respectively. All experiments are conducted on a single A100 GPU. The wall-clock times for each training configuration are reported in Table 5. We evaluate the resulting 9 models on three benchmarks: MATH500, AIME25, and AIME24. For each problem, we generate 256 reasoning paths in parallel. We compute pass@k for k ∈ {1, 2, 4, 8, 16, 32, 64, 128, 256}, and report results for each model trained under different difficulty 2

https://github.com/policy-gradient/GRPO-Zero

Algorithm 1 Tree Rollout Input: Policy πθ , Prompt x, Base rollouts N , Forking points K, Branch rollouts B, Selection method. Output: Trajectory set T Initialize R ← ∅, T ← ∅ Phase 1: Base Rollouts for i = 1 to N do Sample base trajectory τ (i) ∼ πθ (· | x) R ← R ∪ {τ (i) } T ← T ∪ {τ (i) } end for Phase 2: Branch Rollouts for each τ ∈ R do Select K forking points F ⊂ {1, . . . , |τ |} via Algorithm 2 for each f ∈ F do Extract trajectory prefix xf ← [x; τ1:f ] for j = 1 to B do ′(j) Sample continuation τf ∼ πθ (· | xf ) (j)

τ̃f

′(j)

← [τ1:f ; τf ] (j)

T ← T ∪ {τ̃f } end for end for end for

subsets and rollout budgets (Figure 7). In addition, we aggregate results across the three benchmarks and report the averaged avg@256 and pass@256, as shown in Figure 1.

Details on Tree-Structured Rollout (Section 2.2)

C.1

Tree Algorithm Details

Algorithm 1 provides the detailed procedure of the two-phase tree rollout strategy. C.2

Experimental Details of Section 2.2.2

To evaluate cost-efficiency during inference, we measure the PassRate—the probability of discovering at least one correct solution—against token consumption on the AIME25 benchmark using Qwen2.5-3B-Instruct. We compare standard parallel sampling with two tree-structured variants: fixed-seg (equidistant branching) and random (uniform random branching). Detailed procedures for these forking strategies are provided in Appendix D.1.

easy_4 easy_8 easy_16

pass@k (%)

25 20 15 10

10 2

k (log scale)

128

256

5 1

k (log scale)

128

256

medium_4 medium_8 medium_16

10 4

k (log scale)

128

256

k (log scale)

128

256

k (log scale)

128

256

(g) Hard / MATH500

128

256

k (log scale)

128

256

128

256

hard_4 hard_8 hard_16

pass@k (%)

hard_4 hard_8 hard_16

30 20

10 2

(f) Medium / AIME24

k (log scale)

medium_4 medium_8 medium_16

(e) Medium / AIME25

hard_4 hard_8 hard_16

pass@k (%)

(b) Easy / AIME25

(d) Medium / MATH500 95 90 85 80 75 70 65 60 55

easy_4 easy_8 easy_16

(a) Easy / MATH500 95 90 85 80 75 70 65 60 55

easy_4 easy_8 easy_16

pass@k (%)

95 90 85 80 75 70 65 60 55

10 1

k (log scale)

(h) Hard / AIME25

128

256

k (log scale)

(i) Hard / AIME24

Figure 7: pass@k performance on evaluation benchmarks for models trained on different difficulty subsets. Labels such as easy_8 denote models trained on the Easy subset with group size G = 8.

Formal Definition of PassRate For parallel sampling, the model generates M independent trajectories, Tparallel = {τ (1) , . . . , τ (M ) }. The PassRate is defined as: ! M X PassRateparallel = I r(τ (i) ) ≥ 1 i=1

where r(·) ∈ {0, 1} is the verifiable binary reward. Token consumption scales linearly with M . For tree-structured rollouts, generating N base rollouts, K forking points per base, and B branches per forking point yields a set of leaf trajectories Ttree . The total number of terminal paths is N (1 + KB). The PassRate is evaluated over these leaves: ! X PassRatetree = I r(τ ) ≥ 1 τ ∈Ttree

Unlike parallel sampling, tree rollouts consume tokens sub-linearly relative to the number of terminal paths, as context prefixes up to each forking point are computed only once and shared across branches.

Configurations To analyze PassRate against token consumption (Figure 2), we varied the computational budget for both methods. For parallel sampling, we evaluated independent rollout counts of M ∈ {4, 8, 16, 32}. For tree rollouts, we fixed the branching parameters at K = 2 and B = 2, and scaled the base rollouts N ∈ {2, 4, 8}. These configuration tuples (N, K, B) yield 10, 20, and 40 terminal paths, respectively, enabling a direct comparison of exploration efficiency relative to token expenditure. Detailed forking point selection algorithms are provided in Appendix D.1.

Details on Forking Point Selection Strategies (Section 2.3)

D.1

Forking Point Selection Algorithms

We detail the five forking point selection algorithms in Algorithm 2, which is utilized in Phase 2 Branch Rollouts. Let a trajectory be denoted as a sequence of tokens τ = (y1 , y2 , . . . , y|τ | ). For entropy-based methods, let Ht denote the token-level entropy

Algorithm 2 Forking Points Selection Algorithms

Metric

random

sent-entropy

tok-entropy

Input: Trajectory τ , Number of forking points |τ | K, Selection method, Token entropies {Ht }t=1 , Parsed sentences S = {S1 , . . . , SM }, SenS }M , Parsed steps Z = tence entropies {Hm m=1 {Z1 , . . . , ZL }, Step-level FCI scores {yl }L l=1 . Output: Forking points F ⊂ {1, . . . , |τ |}, where |F| = K if method is random then Sample F ⊂ {1, . . . , |τ |} uniformly at random else if method then o nj is fixed-seg k |τ | F ← k · K+1 k = 1, . . . , K else if method is ATB then C ← {l ∈ {1, . . . , L} | yl ≥ Quantile(y1 , . . . , yL , 0.8)} L∗ ← the K smallest indices (earliest steps) from C F ← {νl | l ∈ L∗ } else if method is tok-entropy then F ← arg top−K Ht

NND ↓ MPD ↓ WCR@5 ↑ WCR@10 ↑

0.157 0.337 8.9 16.4

0.130 0.296 12.9 25.3

0.106 0.251 23.6 35.3

t∈{1,...,|τ |}

else if method is sent-entropy then S M∗ ← arg top−K Hm m∈{1,...,M }

F ← {µm | m ∈ M∗ } end if return F at step t, which is computed using the language model’s probability distribution over the vocabulary V : X Ht = − P (v | y<t ) log P (v | y<t ) v∈V

For the sentence-level method, we parse the trajectory into M sentences, S = {S1 , S2 , . . . , SM }, by aligning character-level sentence boundaries detected via PySBD (Sadvilkar and Neumann, 2020) with the tokenizer’s offset mapping. Each sentence Sm represents a contiguous span of token indices, and µm denotes the start token index of Sm . The S is defined as the average tosentence entropy Hm ken entropy within that sentence to mitigate length bias: 1 X S Hm = Ht |Sm | t∈Sm

Attention-based Tree Branching (ATB) operates on the premise that attention scores serve as meaningful metrics to identify important reasoning behaviors. To leverage this insight, the trajectory is

Table 6: Quantitative comparison of forking-point localization across different selection strategies. Arrows indicate stronger localization.

first segmented into L discrete steps (e.g., delimited by line breaks), denoted as Z = {Z1 , . . . , ZL }, where νl represents the start token index of step Zl . ATB then computes a Forward Context Influence (FCI) score yl for each step, quantifying its influence on subsequent tokens by aggregating attention weights. When selecting forking points, ATB first isolates a candidate set consisting of the top 20% of steps with the highest FCI scores. From this set, it selects the K earliest steps as the final forking points. Lastly, the operator arg top−K denotes the extraction of the subset of indices that correspond to the K highest values of a given metric. D.2

Quantitative and Qualitative Analysis of Forking-Point Localization

As illustrated in Figure 8, high-entropy tokens tend to densely cluster within narrow, highly uncertain segments of the reasoning trajectory. Consequently, the search budget is monopolized by repeated resampling at a single localized point, which severely limits the structural reach of the search tree. To quantitatively characterize the localization phenomenon, we measure the distribution of selected forking points using three metrics: Nearest Neighbor Distance (NND), the average distance to the closest forking point; Mean Pairwise Distance (MPD), the average pairwise distance among all selected points; and Window-based Clustering Ratio (WCR@P ), the percentage of forking-point pairs whose distance falls within P % of the trajectory length. Lower NND and MPD and higher WCR indicate stronger localization. As shown in Table 6, tok-entropy exhibits the strongest localization, with the lowest NND (0.106) and MPD (0.251) and the highest WCR@5 (23.6%) and WCR@10 (35.3%). In comparison, sent-entropy increases NND and MPD to 0.130 and 0.296, respectively, while reducing WCR@5 and WCR@10 to 12.9% and 25.3%, quantitatively demonstrating that sentence-level entropy mitigates

the localization of forking points. To further observe how the selected tokens differ across forking strategies, we conducted a case study comparing tok-entropy, sent-entropy, and ATB. Figure 9 visualizes the forking points (K = 4) selected by each method along a single, fixed reasoning path. The tok-entropy method suffers from localization, trapping the selected points within a narrow segment. In contrast, sent-entropy still targets the model’s uncertain regions but distributes the forking points much more evenly, operating at a broader semantic level. Meanwhile, ATB selects steps receiving the highest attention weights; while this can be meaningful for dividing logical reasoning steps, it operates independently of the model’s uncertainty. As shown in Figure 9, ATB often selects highly deterministic points to branch from. Performing additional sampling at these points yields low SibDiv and, consequently, a limited PassRate, as reflected in Table 1. Based on these observations, sent-entropy proves to be the most effective forking strategy by successfully leveraging uncertainty signals while resolving the localization issue. D.3

Formal Definitions of SibDiv

Because recent studies emphasize semantic diversity for effective exploration (Jiang et al., 2025; Yao et al., 2025), it is critical to rigorously quantify the divergence of the explored reasoning paths discussed in Section 2.3.2. To this end, we model the generated reasoning tree as a collection of text segments, referred to as blocks. Formally, a block is defined as a contiguous sequence of reasoning spanning from the root to the first forking point, between two consecutive forking points, or from a final forking point to a leaf. Let F denote the set of all forking points and B denote the set of all blocks within a single generated reasoning tree. We extract a dense semantic representation eb for each block b ∈ B utilizing the gte-large-en-v1.5 model (Zhang et al., 2024). Sibling Diversity (SibDiv) is formulated as the complement of the average pairwise cosine similarity among sibling blocks: 1 X SibDiv = 1− |F|

f ∈F

bi ,bj ∈B(f ), i<j cos(ebi , ebj ) |B(f )| 2

(6) where B(f ) ⊂ B represents the specific subset of child blocks branching directly from a given

Method random fixed-seg ATB tok-entropy tok-entropy w/ 5% dist. tok-entropy w/ 10% dist. sent-entropy

PassRate

SibDiv

10.0 13.3 14.7 12.0 14.0 15.3 17.3

0.0796 0.0853 0.0874 0.1065 0.1041 0.1007 0.1049

Table 7: Comparison of forking-point selection strategies, including distance-forced token-entropy baselines.

forking point f , and cos(·, ·) denotes the cosine similarity function. A higher SibDiv score indicates that the model successfully generates semantically distinct continuations from its forking points. By aggregating this localized diversity, SibDiv effectively captures the degree of semantic exploration and reasoning diversity across the entire tree. D.4

Experimental Details of Section 2.3.3

We evaluated each forking strategy by generating reasoning trees under a fixed inference budget, measuring SibDiv and PassRate. Specifically, we conducted inference on the AIME26 benchmark using the Qwen2.5-3B-Instruct model. To isolate the effect of the forking point selection strategy from the inherent randomness of language model generation, we generated and fixed a single base rollout for each problem. We then applied each selection method to identify K = 4 distinct forking points along this fixed base trajectory. From each identified forking point, we generated B = 4 additional branch rollouts. This procedure ensures a strictly controlled environment, yielding exactly 17 terminal leaves (1 base + 16 new branches) per problem across all methods. Finally, we calculated the PassRate and SibDiv across these 17 leaves and averaged the metrics over the entire dataset. To ensure the robustness of our findings, we repeated this entire experimental procedure five independent times and report the final averaged results in Table 1. D.5

Analyzing the Benefits of Sentence-Level Entropy

While sent-entropy substantially improves PassRate over tok-entropy, it remains unclear whether this gain arises simply from mitigating localization or from identifying more semantically meaningful decision points. To disentangle these effects, we introduce distance-forced tok-entropy

solve

the

problem

with

no of

[space x1]

Step

palindrome \

ots

### The 4

-zero

(

i 6

equal

[space x1]

[space x1] to

Case

3 Case

consider

[space x1] not

written a

pal

ind

rom

For

ots

written

need

over

consider

{

even

number

line +

base

the

digits

solve

cannot

number

Pal

since

written

}

[space x1]

))

Case

The

palindrome

need 1

[space x1]

their

sum

)

and

Pal

digits

with

2 digits

1length

(

)

[space x1]

must

indrome

form

[space x1]

the

palindrome

-zero

and

their

sum

must

over

simpl

[space x1]

with

{

ifying

)

[space x1]

line

non

[space x1] \

))

}

aba

digits

}

Thus

[space x1]

-zero

digits

[space x1]

the

a (

[space x1]

= \(

[space x1]

)

gives

[space x1]

)

(

valid

[space x1]

)

gives

[space x1]

)

(

valid

[space x1]

)

gives

[space x1]

)

(

valid

[space x1]

)

gives

[space x1]

)

(

valid

[space x1]

)

gives

[space x1]

)

(

valid

[space x1]

)

gives

[space x1]

)

(

not

Thus

there

####

Case

[space x1]

Pal

over 1

{

need

4 point

\( =

[space x1]

[space x1] 1

)

[space x1]

[space x1] 2

\( =

[space x1]

}

ifying b

invalid

[space x1]

Thus

[space x1]

\( =

[space x1]

since

[space x1]

)

[space x1]

gives

begin

[space x1] \

{

[space x1]

cdot

[space x1]

equation 2

is +

[space x1]

)

(

)

valid

b \

(

6 \ )

)

cdot 2

[space x1]

valid

[space x1]

cdot 2

[space x1]

)

(

)

(

valid

array

}{

cccc

}

end

{

array

]

grid

moves \(

valid

[space x1]

b \

)

gives

[space x1]

)

(

valid

[space x1]

)

gives

[space x1]

)

(

valid

[space x1]

)

gives

[space x1]

)

(

valid

[space x1]

\( =

[space x1]

)

gives

Rightarrow

[space x1]

cdot 2

[space x1]

1 =

[space x1]

b \

Rightarrow

[space x1]

)

gives

[space x1]

)

(

valid

[space x1]

). [space x1]

)

gives

[space x1]

)

(

valid

[space x1]

)

gives

[space x1]

)

(

valid

[space x1]

there

palindrome

[ boxed ]

squares

(

)

and

number

row

[space x1]

moves

the

bug

moves

{

(

[space x1]

)

(

valid

equival

ently

[space x1]

find

the

number

[space x1]

right

(

comb

inator

ial

problem

where

need

sequence

given

the

}

[space x1]

sequences

solve

this

two

)

problem

[space x1]

invalid

)

[space x1]

valid

(

pal \

the

ind

9 ,

since

rom

)

the

equation

Now

}{

[

such

bin

we 0

bin

{

need

}

{

times

}{

calculate

}{

[space x1]

\ \

}{ \

} times

times

[space x1]

valid

[space x1]

must

[space x1]

, )

ind

rom

digits pal

The }{

The

}{

note

}

} The

}{

and rom

\( es

)

from

[space x1]

)

from

[space x1]

[

sqrt

]

Thus

[space x1]

, ind

[space x1]

find

{

the

[

sqrt

{

frac

[space x1]

times

[space x1]

bin

frac

omial

{

}

{

determine any

}

frac

the

coins

probability

when

outcome

[space x1]

}{

rolling

[space x1]

{

of \

each

{

for

}{

\ \

}{

First

}{

times

{

[space x1]

}{

find

the

probability

that

any

coins

This

boxed

]

that

Alice

standard

fair

and

six

Bob

each

-sided

die

receive is

belong

pattern

Let

Alice

denote

and

the

can

Bob

[space x1]

times

the

square

times

[space x1]

any

coins

the

sequence

[space x1]

(

Alice

[space x1]

(

Bob

[space x1]

(

Carol

Alice

the

and

Bob

that P

Alice

third

each

receive

calculating

coin

and

The

first

roll

Alice

coin

The

second

roll

Bob

coin

The

third

roll

Carol

coin

first

three

coin

)

frac

left

(\ 2 ]

least

find

but

Alice

coins is

{

}{

{

}{

right

overall

probability

2 structure

remains

Carol

given

{

]

}

bin

compute

{

times

}

times

frac

{

[space x1]

0 \

times

[space x1]

times

[space x1]

times

[space x1]

root

}

final

answer

[space x1]

{

}

<|im_end|>

Selected Top-4 High Entropy Tokens top-4 floor 1.327

solve

the .

problem

Given

have

that n

\( )

need S

understand

)

elements

has and

the

structure )

disjoint

elements

shifting

the

for

elements

coin

)

coin

)

frac

elements

)

from

the

constant

set

each

cousin

integer

1 and

4 The

cousins

)

and

its

can

formed

)

3 this

must

{

frac

all

constant

must

the

same

Let

denote

the

elements

)

{

ots

)

for

)

ots

{

}

belongs

Bob

the

least

two

coins

that

the

then

continuing

each

probability

before

Carol

receive

and

least

two

)

where

cousins

)

must

}

the

For

form

{

\( _

S 1

\ +

) k

and ,

ots

some

integer

Since

coins

this

before

Carol

first

coins

Carol

)

and a

\( )

\ for

)

must

any

be \

disjoint

ots

This

implies

that

must

}

)

therefore

number

such )

that

can

any

integer

k except

The

number

possible

values

corresponds

for

(

probability

(

probability (

probability

frac

{

frac

{

and

{

}{

}{ 1

}{

)).

))

sequence ,

two

restart Bob

coins

and

need

Carol

) 1

cousin

the

that

)

has

exactly

[space x1]

Given

[space x1]

unique

\( of

cousins

[space x1]

[space x1] of

Since

[space x1]

)

cousins

have

each

repeat

coins

[space x1]

the

The

process

until

probability

[

]

impl

ies

right

)

times

left

)

\ (\

left

frac

{

}{

right

)

times

frac

{

\ 1

Thus }

, \

the ).

least

number

elements

the

set

)

can

have

boxed

{

<|im_end|>

receiving

the

same

coins

}

The

note

that

probability

the

first

left

ots

the of

three

sequence

can

start

with

Alice

then

repeating

right

and

4 various

starting

rolls

ways

Bob

3 receiving

this

pattern

and

frac

}{

{

}{

right

infinite

This

and

common

ratio

given

}{

frac

series

geometric r

series

with

frac

{

the

}{

frac

{

first

}{

term

The

frac

{

left

frac

}{

sum

infinite

)

frac

{

}{

frac

{

}{

geometric

[

}

]

Thus

frac

}}

{ \

the

probability

any

coins

The

probability

[space x1]

[

boxed

]

can

that frac

[space x1]

{

}

{

r {

= }{

Alice 1

written 6

} 1

\ 2

and

frac

{

}{

}}

{

}}

frac

{

}{

}}

Bob

each

receive

least

two

}{

frac

{

}{

)

[space x1]

Therefore

where 1

coins

before

m +

Carol

receives

[space x1]

1 6

and

<|im_end|>

Non-selected entropy

Selected Top-4 High Entropy Tokens

Non-selected entropy

Selected Top-4 High Entropy Tokens

dark red + black box low 0.000

[

the

frac

the

and

}

the

coins

rolls

occurring

two

sequence

frac 7

1To

specific

{

\ these have

[

}{

[space x1]

outcomes

left

arrange

This

[space x1]

approached

and

probability

receives

Consider

rolled

this

dark red + black box

need

ways moves

[space x1]

Non-selected entropy

rolling

frac

receives

Given

coefficient

[space x1]

}

low 0.000

receives

rolling

frac

probability 6

)

moves

\( We

}

need

Carol

probabilities

probability

the

probability 6

[space x1]

also

\( choose

( d

cousins

First

[space x1]

from to

]

to 1

)

ifying

[space x1]

simpl =

[space x1]

such

[space x1]

cases 5

Thus 3

pal

all

[space x1] number

). 1

valid

from

from total

[space x1]

and

[space x1]

<|im_end|>

before

get need

}

[space x1] [space x1]

)

cba

= +

rom

a c

Selected Top-4 High Entropy Tokens

coins

repeatedly

to we

dark red + black box

least

) and

[space x1]

top-4 floor 1.497

exactly

[space x1]

digits

+ 2

ind

abc

[space x1] 1

pal

[space x1]

Therefore 2

valid

line

[space x1]

)

with over

= 0

{

are

gives

Non-selected entropy low 0.000

needs

[space x1]

\ \

the

)

\ d b

izing ,

+ 2

[space x1]

there

Conclusion

digits

indrome \(

Pal form +

mar

[space x1]

Sum

digits

###

]

[space x1]

[space x1] -

number

times

the +

[space x1]

Thus

c a

[space x1] \

has

+ 2

are

[space x1]

The

moves

these

and

times

total

[

[space x1]

The

[space x1]

right

[space x1]

the \

[space x1]

Rightarrow

Case

make

}

has

{

The

[space x1]

and where

[space x1]

####

point

, ,

Rightarrow

Thus

from

follows

[space x1]

b \

[space x1]

gives

gives [space x1]

[space x1]

gives

[space x1]

take or

[space x1]

can

right

grid

[space x1]

bug

move

the

Rightarrow

the

only

2 denote

[space x1]

paths

can

, ,

valid bug

1 Let

[space x1]

vertex

[space x1]

of The

the

\( in

gives

Rightarrow

left

[space x1]

3 represents

number

grid to

[space x1]

the

We {

)

gives

Rightarrow

[space x1] 1

\ \

)

+ \(

b -

[space x1]

on right

N 3

[space x1]

[space x1] 1

[space x1] [space x1] 3

[space x1]

gives

Rightarrow

count

) from

[space x1] [space x1] 1

The -

digits

simpl

rom

abc

[space x1]

ind

[space x1]

line 3

pal

with

valid

[space x1]

)

indrome

form

a 1

the +

}

has

[space x1] 3

need B

[space x1]

palindrome

[space x1]

= =

The

a a

we \(

ally

\( \(

digit

[space x1]

equation

are

point diagon

digit

non

valid

to move

[

indrome

the

[space x1]

has

problem

)

[space x1]

and

####

this \

each

[space x1]

Analysis

the

possible

to .

es be \(

[space x1]

rom can

where

integer

up given

ind

Constraints

non ,

Pal digits \

positive

add

constraints

of of }}

digits

the

Step

, a

2 be

and

number +

[space x1]

need

#### 4This

{

must

Structure odd

number

whose

: an

ots

line

[space x1]

must

over

the

and

rom

Step

finding

digits

ind

with _k

digits ,

###

pal

zero

structure

###

top-4 floor 1.572

dark red + black box low 0.000

top-4 floor 1.560

Figure 8: Visualization of token-entropy localization. Dark red boxed tokens indicate the selected top-4 high-entropy forking points. These points densely cluster within a narrow segment, monopolizing the search budget and limiting structural diversity.

To solve the problem of finding the number of positive integer palindromes written in base $1 0$ with no zero digits and whose digits add up to $13$, we need to consider the structure of

To solve this problem, we need to count the number of valid paths the bug can take from point A

palindromes and the constraints given.

A palindrome with an odd number of digits can be written as }} , where

overline{a_1a_2 ldots a_k a_{k+1

a_1 = a_{k+1}, a_2 = a_{k}, ldots, a_k = a_1 . For an even number of digits, it i

s written as

to point

on the grid. The bug can only move right or up, and it cannot move diagonall

y or from right to left. Let's denote the grid as follows, where each point represents a vert

### Step 1: Structure of Palindromes

ex:

overline{a_1a_2 ldots a_k} .

### Step 2: Constraints The digits must be non-zero (i.e.,

1, 2, 3, 4, 5, 6, 7, 8, 9 ) and their sum must equal

begin{array}{cccccccccc} & & & & & & & & & A

### Step 3: Case Analysis

& & & & & & & & B

We need to consider the number of digits (length) of the palindrome.

end{array}

#### Case 1: Palindrome with 1 digit This is not possible since the digits must be non-zero and their sum must be

13 .

#### Case 2: Palindrome with 3 digits The palindrome has the form ing to

overline{aba} . Thus, the equation is

2a + b = 13 . We need

and

a + b + a = 13 , simplify

to be non-zero digits (i.e.,

a, b in {1, 2, 3, 4,

5, 6, 7, 8, 9} ). gives

b = 1

(valid).

a = 5

gives

b = 3

(valid).

a = 4

gives

b = 5

(valid).

a = 3

gives

b = 7

(valid).

a = 2

gives

b = 9

(valid).

a = 1

gives

b = 11

(invalid since 11 is not a valid digit).

B . The total number of moves is 20, and we need to c

hoose 10 of these moves to be right (or equivalently, 10 moves to be up). This is a combinato

a = 6

Thus, there are

The grid has 10 squares in a row, so the bug needs to make exactly 10 moves to the right (R) and 10 moves up (U) to get from

rial problem where we need to find the number of ways to arrange 10 R's and 10 U's in a seque nce of 20 moves.

valid palindromes:

The number of such sequences is given by the binomial coefficient:

616, 535, 454, 373, 292 .

#### Case 3: Palindrome with 5 digits The palindrome has the form

overline{abcba} . Thus, the equation is

a + b + c + b + a = 13

, simplifying to

2a + 2b + c = 13 . We need

2 * 4 + 2b + c = 13 Rightarrow 8 + 2b + c = 13 Rightarrow 2b + c = 5 :

a = 4

gives

b = 1

gives

c = 3

(valid):

41414 .

b = 2

gives

c = 1

(valid):

42244 .

a = 3

gives

b = 1

gives

c = 5

(valid):

31313 .

b = 2

gives

c = 3

(valid):

32233 .

a = 2

gives

b = 1

gives

b = 2

gives

b = 3

gives

N = binom{20}{10} = (20!)/(10!10!)

Now, we need to calculate

2 * 3 + 2b + c = 13 Rightarrow 6 + 2b + c = 13 Rightarrow 2b + c = 7 :

a, b, c in {1, 2, 3, 4, 5, 6, 7, 8, 9} .

2 * 2 + 2b + c = 13 Rightarrow 4 + 2b + c = 13 Rightarrow 2b + c = 9 : c = 7

(valid):

21212 .

c = 5

(valid):

22522 .

c = 3

(valid):

23323 .

sqrt{N} . First, we compute

binom{20}{10} :

binom{20}{10} = (20!)/(10!10!) = (20 \times 19 \times 18 \times 17 \times 16 \times 15 \times 14 \times 13 \times 12 \times 11)/(10 \times 9 \times 8 \times 7 \times 6 \times 5 \times 4 \ times 3 \times 2 \times 1) = 184756

a = 1

gives

2 * 1 + 2b + c = 13 Rightarrow 2 + 2b + c = 13 Rightarrow 2b + c = 11 :

b = 1

gives

c = 9

(valid):

11911 .

b = 2

gives

c = 7

(valid):

12712 .

b = 3

gives

c = 5

(valid):

13513 .

b = 4

gives

c = 3

(valid):

14314 .

Thus, there are

Next, we find the square root of 184756:

valid palindromes.

#### Case 4: Palindrome with 7 digits The palindrome has the form

overline{abcdeedcba} . Thus, the equation is

+ d + c + b + a = 13 , simplifying to

2a + 2b + 2c + 2d + e = 13 , or

a + b + c + d + e

2(a + b + c + d) + e

sqrt{184756} = 430

= 13 . -

a + b + c + d = 6

and

e = 1

(valid):

a = 1, b = 1, c = 2, d = 2 :

1122111 .

a = 1, b = 1, c = 1, d = 3 :

1133111 .

a = 1, b = 1, c = 1, d = 2, e = 0

Thus, there are

Thus, the final answer is:

(invalid since

must be 1).

valid palindromes.

430

### Conclusion Summarizing the valid palindromes from all cases: 2

from 3 digits,

from 7 digits. Therefore, the total number of such palindromes is

from 5 digits, and

5 + 9 + 2 = 16 .

Forking Point Selection Methods Token Entropy

Sentence Entropy

Forking Point Selection Methods ATB

Token Entropy

Sentence Entropy

ATB

To solve this problem, we need to determine the probability that Alice and Bob each receive a

To solve the problem, we need to understand the structure of the set

t least two coins before Carol receives any coins when a standard fair six-sided die is rolle

en that

d repeatedly.

from

has

elements, each cousin of

and its cousins. Giv

elements and be disjoint

by a constant integer, an

where

a_1 < a_2 < *s < a_n . Fo

d this constant must be the same for all elements in

First, note the probabilities for each outcome:

must also have

S . The cousins can be formed by shifting the elements of S .

- The probability of rolling a 1 or 2 (Alice's coin) is (2)/(6) = (1)/(3). - The probability of rolling a 3 or 4 (Bob's coin) is (2)/(6) = (1)/(3).

Let's denote the elements of

- The probability of rolling a 5 or 6 (Carol's coin) is (2)/(6) = (1)/(3).

and

some integer We need to find the probability that Alice and Bob each receive at least two coins before Car

for any

to be cousins, k . Since

T and

i . This implies that

{a_1, a_2, ldots, a_n}

must be of the form

{a_1 + k, a_2 + k, ldots, a_n + k}

must be disjoint,

must be such that

can be any integer except

for

a_n + k neq a_i

a_1, a_2, ldots, a_{n-1} .

ol receives any coins. This can be approached by calculating the probability that the first t wo coins belong to Alice and Bob, and the third coin belongs to Carol, and then continuing th is pattern.

The number of possible values for

nique cousin, the number of cousins of

Let's denote the probability that Alice and Bob each receive at least two coins before Carol

is therefore

n - 1 . Since each

n - 1 . Given that

Thus, the least number of elements the set

can have is

corresponds to a u

has exactly 4040 cousin

s, we have:

receives any coins as P.

n - 1 = 4040 implies n = 4041. Consider the sequence of outcomes: 1. The first roll is Alice's coin (probability (1)/(3)). 2. The second roll is Bob's coin (probability (1)/(3)). 3. The third roll is Carol's coin (probability (1)/(3)).

4041 .

Given these first three rolls, the sequence restarts, and we need to repeat the process until we have at least two Alice coins, two Bob coins, and no Carol coins. The probability of this specific sequence occurring is: ((1)/(3)) x ((1)/(3)) x ((1)/(3)) = ((1)/(3))^3 = (1)/(27)

To find the overall probability P, we note that the sequence can start in various ways, but t he structure remains the same. The probability of starting with Alice and Bob receiving coins and Carol receiving no coins in the first three rolls, and then repeating this pattern, is gi ven by: P = (1)/(27) + ((1)/(27))^2 + ((1)/(27))^3 + *s

This is an infinite geometric series with the first term a = (1)/(27) and common ratio r = (1 )/(27). The sum S of an infinite geometric series is given by: S = (a)/(1 - r) = frac{(1)/(27)}{1 - (1)/(27)} = frac{(1)/(27)}{(26)/(27)} = (1)/(26)

Thus, the probability that Alice and Bob each receive at least two coins before Carol receive s any coins is (1)/(26). The probability can be written as (m)/(n) where m = 1 and n = 26. Therefore, m + n = 1 + 26 = 27.

Forking Point Selection Methods Token Entropy

Sentence Entropy

Forking Point Selection Methods ATB

Token Entropy

Sentence Entropy

ATB

Figure 9: Case studies comparing forking point selections across tok-entropy, sent-entropy, and ATB. Colored boxes indicate the tokens selected by each method, with overlapping boxes denoting agreement between methods. Notably, while tok-entropy suffers from localization, sent-entropy distributes points more evenly across broader semantic levels, whereas ATB often targets deterministic points regardless of uncertainty.

baselines that preserve the original token-level entropy signal while explicitly preventing nearby forking points. Starting from candidates ranked by token entropy, we greedily select forking points and skip any candidate whose distance from an already selected point is within a predefined fraction of the total trajectory length. We consider minimum-distance thresholds of 5% and 10%. As shown in Table 7, explicitly enforcing a minimum distance between token-level forking points improves PassRate from 12.0 for standard tok-entropy to 14.0 and 15.3 with the 5% and 10% constraints, respectively. This confirms that localization itself is a limiting factor for token-level entropy-based branching. However, both distanceforced variants still underperform sent-entropy, which achieves a PassRate of 17.3. Since these variants mitigate localization while retaining the same token-level entropy signal, the remaining gap suggests that the benefit of sent-entropy cannot be attributed solely to distributing forking points more broadly. Rather, sentence-level entropy provides a more effective signal for identifying semantically meaningful decision points for branching.

sibling blocks branching from P (b). The siblingdiversity term for a specific block b is computed as its average semantic distance to its siblings: P Divsib (b) = 1 −

b′ ∈Bsib (b)\{b} cos(eb , eb′ )

|Bsib (b)| − 1

, (8)

where eb is the embedding of block b. We define Divsib (b) = 0 when b has no valid sibling block. While the evaluation metric SibDiv (defined in Appendix D.3) aggregates pairwise similarities across all forking points to report a single treelevel scalar, the reward term Divsib (b) is evaluated at the individual block level to provide the advantage augmentation. E.2

DATPO Objective Function

DATPO employs a token-level policy gradient objective mapped across the tree topology. Given a set of generated blocks B for a prompt q, the objective is defined as: " JDATPO (θ) = Eq∼Q,B∼πθold P

|b| XX

b∈B |b| b∈B t=1

Algorithmic and Formal Details of DATPO

This section provides the formal definitions of the advantage components and the complete training procedure for Difficulty-Adaptive Sentenceentropy Guided Tree-Structured Policy Optimization (DATPO), expanding upon the methodology outlined in Section 3.

min ρb,t (θ)Â(b), clip ρb,t (θ), # 1 − ϵ, 1 + ϵ Â(b) , (9) where |b| is the sequence length of block b, ρb,t (θ) = πθπθ (y(yt |xt |x<t<t) ) is the importance ratio, and old

E.1

Formal Definitions of Value Estimation and Sibling Diversity term

Monte Carlo State Value (V̂M C ) For a state s corresponding to a specific forking point, let T (s) denote the set of all terminal blocks descending from s. The Monte Carlo state value is formally defined as the expected verifiable reward over these terminal paths: V̂M C (s) =

X 1 r(τ ). |T (s)|

Â(b) is the block-level augmented advantage. E.3

Complete DATPO Algorithm

Algorithm 3 details the end-to-end training procedure. By extending the two-phase rollout strategy into the training framework, the process is structured into four distinct phases: base rollouts, adaptive branch rollouts, block-level advantage estimation, and policy update.

(7)

τ ∈T (s)

For a terminal state send , the set of descending paths is empty, strictly enforcing V̂M C (send ) = 0. Block-Level Sibling Diversity (Divsib (b)) Let P (b) denote the forking point from which block b originates, and let Bsib (b) denote the set of all

E.4

Comparison with Other Tree-based Methods

To contextualize DATPO within the landscape of recent tree-based RLVR methodologies, we highlight two fundamental distinctions between our approach and existing frameworks such as TreeRL (Hou et al., 2025) and AttnRL (Liu et al., 2025a).

Algorithm 3 DATPO Input: Initial policy πθ , Prompts dataset Q, Maximum number of forking points Kmax , Maximum number of branch rollouts per forking point Bmax , Base rollouts N , Diversity coefficient α. Output: Optimized policy πθ∗ Sample prompt q ∼ Q Phase 1: Base Rollouts Generate N independent base trajectories R = {τ (1) , . . . , τ (N ) } via πθ (·P| q) (i) Compute V (root) = N1 N i=1 r(τ ) Compute adaptive budgets: K̂ = ⌈Kmax (1 − V (root))⌉, B̂ = ⌈Bmax (1 − V (root))⌉ Phase 2: Adaptive Branch Rollouts Initialize tree path set T ← R if K̂ > 0 and B̂ > 0 then for each τ ∈ R do Select K̂ forking points F using sent-entropy forking strategy (Algorithm 2) for each f ∈ F do Extract trajectory prefix xf ← [q; τ1:f ] Generate B̂ branch continuations from prefix xf Add generated branches to T end for end for end if Phase 3: Block-level Advantage Estimation Partition T into a set of contiguous blocks B for each block b ∈ B do (b) (b) Compute V̂M C (sstart ) and V̂M C (send ) (b) (b) Âbase (b) = r(b) + V̂M C (send ) − V̂M C (sstart ) Compute Divsib (b) using block embeddings (Equation 8) Â(b) = Âbase (b) + I(Âbase (b) > 0) · α · Divsib (b) end for Phase 4: Policy Update Update θ by maximizing JDATPO (θ) (Equation 9) using advantages {Â(b)}b∈B Anneal α according to schedule return Optimized policy πθ∗

Structural Robustness in Optimization Both TreeRL and AttnRL generate tree-structured rollouts but ultimately flatten these trees into a set of N (1 + K × B) independent sequences to perform sequence-level policy updates (Hou et al., 2025). A critical flaw in this unfolding process is that com-

mon trajectory prefixes are duplicated across multiple sequences, causing the policy to redundantly update on the same early tokens. To mitigate the resulting overfitting, these methods rely on a heuristic penalty, artificially downweighting the advantage of non-leaf steps by dividingp it by the square root of the descending leaf count ( |L(sn )|) (Hou et al., 2025; Liu et al., 2025a). In contrast, DATPO is structurally immune to this redundancy. By strictly partitioning the generated tree into non-overlapping contiguous blocks, every token within the tree belongs to exactly one block. Because DATPO performs explicit blocklevel updates directly over the tree topology, it naturally prevents duplicate gradient updates on shared prefixes, providing a highly robust credit assignment mechanism without the need for ad-hoc advantage penalization. Motivation for Difficulty-Adaptive Exploration While AttnRL (Liu et al., 2025a) similarly incorporates a difficulty-adaptive exploration mechanism, its approach is fundamentally driven by computational efficiency. Specifically, AttnRL reduces the sampling budget for easy problems to prevent inefficient exploration and filter out responses with zero advantages. Conversely, DATPO’s difficulty-adaptive rollout originates from a completely different motivation: maximizing intrinsic reasoning coverage (pass@k). As demonstrated in Section 2.1, adaptive budget allocation is not merely a resource-saving heuristic, but a key algorithmic factor for successfully expanding a model’s pass@k without inducing mode collapse. Built entirely around this objective, DATPO further maximizes coverage through the structural superiority of trees (Section 2.2) and optimal semantic forking (Section 2.3). Thus, while DATPO and AttnRL share superficial similarities in their adaptive nature, they are built upon fundamentally distinct motivations and optimization goals.

Details on Main Experiments (Section 4)

F.1

Experimental Setups

500 problems used as the MATH500 and use the remaining 12,000 problems as the training set. Evaluation We evaluate the trained models on mathematical reasoning benchmarks, specifically MATH500 (Hendrycks et al., 2021), AIME26, AIME25, AIME24, and AMC23. We report avg@k as the primary evaluation metric across all benchmarks. All evaluations were performed with a temperature of 1.0 and a maximum generation length of 2048. To assess the reasoning coverage and test-time scaling performance of the trained models, we additionally report pass@k and maj@k (majority voting), respectively. We use k = 8 for MATH500, and k = 64 for the remaining benchmarks. For robustness, both pass@k and maj@k results are computed by averaging over three independent evaluation runs for each dataset. The final maj@k in Figure 6 is then reported as the average of these results across all mathematical reasoning benchmarks. Baselines We compare DATPO with several baselines: (1) Base, the base model without any additional training; (2) GRPO (Shao et al., 2024), standard GRPO enhanced with the token-level loss and clip-higher strategy from DAPO (Yu et al., 2025b). Following prior work (Liao et al., 2025) showing that dynamic sampling can be detrimental for relatively weak reasoning models, we intentionally adopt only this specific subset of DAPO components; (3) Dr.GRPO (Liu et al., 2025b), a refined variant of GRPO that corrects structural biases in advantage estimation; (4) TreeRL (Hou et al., 2025), a tree-based RL method that selects forking points from high-entropy tokens and estimates process-level advantages by combining local and global advantages; and (5) AttnRL (Liu et al., 2025a), another tree-based RL method built upon TreeRL with a focus on improving efficiency by selecting forking points based on attention scores and adopting adaptive sampling and one-step off-policy. For TreeRL and AttnRL, we adopt the same treeexpansion hyperparameters as reported in original papers. To ensure a fair comparison, we control the total number of generated tokens per problem to be comparable across all methods (detailed in Appendix F.3). F.2

Implementation Details

Sampling and Algorithmic Hyperparameters Across all methods, we set the sampling temperature to 1.0 and the maximum generation length to

Method GRPO Dr.GRPO TreeRL AttnRL DATPO (Ours)

Avg. Generated Tokens 8,755.7 8,608.3 11,029.9 8,807.3 8,952.4

Table 8: Average number of generated tokens per question during training across different methods.

1024 tokens. For GRPO and Dr.GRPO, we sample 16 responses per problem. For the tree-based baselines, we strictly follow the hyperparameters reported in their respective original papers. Specifically, for TreeRL, we set the tree expansion parameters to (N, K, B) = (6, 2, 2). For AttnRL, we use maximum budgets of (N, Kmax , Bmax ) = (6, 2, 2), select the top 20% of FCI steps as forking candidates, and apply ∆ = 4 and λ = 0.9 for adaptive batching. For our proposed DATPO, we set the adaptive tree parameters to (N, Kmax , Bmax ) = (4, 3, 4). We intentionally employ a larger maximum branch count (Bmax = 4) compared to the baselines, as calculating the sibling diversity term (Divsib ) across merely two branches (B = 2) diminishes its significance. To accommodate this wider branching while keeping the total number of generated tokens per problem comparable to the baseline methods, we adjusted the base and forking budgets accordingly. The diversity coefficient α is initialized to 0.2 and linearly annealed to 0 over the course of training. To compute the semantic diversity representations, we utilize the gte-large-en-v1.5 embedding model (Zhang et al., 2024). Furthermore, to prevent OutOf-Memory (OOM) errors caused by the expansion of adaptive methods (AttnRL and DATPO), we apply rollout chunking during the branch rollout phase. We generate branch rollouts in chunk sizes of 384 for Qwen2.5-3B-Base and 64 for Qwen34B-Base. Training Hyperparameters We formulate the task with a binary verifiable reward, assigning a reward of 1 if the final answer is correct and 0 otherwise. Models are optimized using the AdamW optimizer with β = (0.9, 0.999) and a constant learning rate of 5 × 10−6 . We omit the KL divergence penalty and the clipping ratio is set to 0.2. For the GRPO baseline enhanced with the clip-higher strategy, we set the upper clip ratio to

Method

Wall Clock (Hours) Parallel Rollout

GRPO Dr.GRPO

26.3 27.1

Tree-based Rollout TreeRL AttnRL DATPO w/o diversity DATPO DATPO w/ one-step off-policy

56.2 55.5 56.0 60.3 60.0

Component

Time (s)

Total runtime (%)

Policy Diversity embedding Update Others

150.44 13.65 102.17 33.76

50.14 4.55 34.05 11.25

Total

300.02

100.00

Table 10: Per-step runtime breakdown of DATPO across different computational components.

Original MMLU-Pro

Table 9: Wall-clock comparison across different methods.

11.2%

3.2% 3.4%

Sampled MMLU-Pro (500) 11.2%

4.2%

3.2% 3.4%

4.2%

6.0%

10.8%

10.8% 6.6%

0.28 and the lower to 0.2. During training, we update the policy using 16 prompts per step, maintaining a global mini-batch size of 64 and a microbatch size of 2 for gradient accumulation across all methods. The total effective batch size varies by method: GRPO and Dr.GRPO utilize a fixed batch size of 256; TreeRL employs a batch size of 480 (comprising 96 base rollouts and 384 branch rollouts); whereas the batch sizes for AttnRL and DATPO dynamically adjust per step due to their adaptive nature. Notably, because DATPO performs block-level policy updates, its mini-batch and micro-batch sizes are defined with respect to the number of contiguous blocks rather than full sequences. All experiments were executed on a computing cluster equipped with 8 NVIDIA A100 GPUs, where each individual training run was conducted on a single A100 GPU. Our codebase is developed based on the GRPO-Zero framework3 . F.3 Computational Cost and Wall-Clock Time To ensure a fair comparison, we control the total number of generated tokens per problem to be comparable across all methods. The actual average number of generated tokens per question during training for each method is detailed in Table 8. However, despite this token-level equivalence, treebased methods generally incur a higher wall-clock time compared to standard parallel rollouts, as reported in Table 9. This discrepancy arises from the inherent sequential dependency in tree generation: branch rollouts cannot commence until the base rollouts are fully generated and forking points are explicitly selected, creating a computational bottleneck. Furthermore, our proposed DATPO requires additional overhead to compute block-level embeddings for the diversity term, slightly increasing its wall-clock time relative to other tree-based base3

https://github.com/policy-gradient/GRPO-Zero

8.0%

chemistry law

6.6%

9.4%

6.8%

9.1%

math physics

6.6%

9.4%

9.2%

7.0%

8.0%

7.7%

engineering other

6.8%

Categories economics health

psychology business

7.0% 7.6%

biology philosophy

computer science history

Figure 10: Comparison of category-wise distributions between the original MMLU-Pro dataset and our sampled subset (500 instances). Stratified sampling ensures the original proportions are preserved.

lines. We note that adopting the one-step off-policy approach proposed in AttnRL (Liu et al., 2025a) can marginally mitigate this latency. Table 10 provides a detailed breakdown of the per-step runtime of DATPO by computational component. F.4

Generalization to Out-Of-Domain Tasks

To investigate whether the models trained on mathematical reasoning datasets can lead to improvements in reasoning performance across other domains, we additionally conduct out-of-domain evaluations using GPQA-Diamond (Rein et al., 2023) and MMLU-Pro (Wang et al., 2024). For MMLUPro, we applied stratified sampling to evaluate on a subset of 500 instances, preserving the original proportional distribution across categories such as math, physics, chemistry, engineering, law, and economics. A comparison of the category-wise distributions between the original and sampled datasets is provided in Figure 10. We evaluate the models trained with each method using two base models, Qwen2.5-3B-Base and Qwen3-4B-Base, and report the avg@8 metric for both benchmarks. Table 11 presents the results of the out-ofdomain evaluation. Overall, DATPO demonstrates consistent performance across both the GPQA-Diamond and MMLU-Pro datasets. Specifically, compared to the strongest baselines, DATPO achieves a +2.4 percentage point improvement on

Method

GPQA-Diamond

MMLU-Pro

Qwen2.5-3B-Base Base 21.1 GRPO 25.3 Dr.GRPO 26.1 TreeRL 25.3 AttnRL 25.9 DATPO (Ours) 28.5

18.4 32.6 31.2 33.1 33.2 33.1

Qwen3-4B-Base 24.2 35.9 38.2 36.7 38.4 39.6

34.8 55.9 57.3 55.6 56.6 57.7

Base GRPO Dr.GRPO TreeRL AttnRL DATPO (Ours)

F.5

Further Ablation Studies

Effect of Difficulty-Adaptive Rollout While Section 4.2 indirectly demonstrates the benefits of our approach against non-adaptive baselines (e.g., TreeRL), we conduct this ablation to explicitly isolate the impact of the difficulty-adaptive mechanism by evaluating a static, non-adaptive variant of DATPO. Applying our default tree-expansion parameters of (N, Kmax , Bmax ) = (4, 3, 4) to a static rollout would significantly increase the overall training budget. Therefore, to maintain a token consumption comparable to our adaptive framework, we restrict the tree-expansion parameters of this non-adaptive variant to a narrower configuration of (N, K, B) = (6, 2, 2). As reported in Table 12, the full DATPO framework outperforms the non-adaptive variant in both avg@k and pass@k. The lower pass@k of the non-adaptive model aligns with our empirical analysis in Section 2.1: uniformly expanding the rollout budget across all problems, regardless of their difficulty, can lead to a decrease in pass@k. Furthermore, the absence of difficulty adaptation also degrades avg@k. We attribute this to a compound-

DATPO w/o difficulty-adaptive

DATPO

MATH500 AIME26 AIME25 AIME24 AMC23

62.9 / 81.0 2.6 / 21.1 1.7 / 25.6 5.4 / 31.1 37.0 / 90.0

63.5 / 81.7 2.4 / 33.3 1.6 / 33.3 4.8 / 35.6 39.8 / 90.8

Average

21.9 / 49.8

22.4 / 54.9

Table 12: Ablation study on difficulty-adaptive rollout. Results are reported as avg@8 / pass@8 for MATH500 and avg@64 / pass@64 for all other benchmarks. 40

Table 11: Out-of-domain evaluation results. We report avg@8 accuracy for each dataset.

α=0 α : 0.2 → 0 (DATPO)

pass@k (%)

GPQA-Diamond and a marginal -0.1 point difference on MMLU-Pro using the Qwen2.5-3BBase model. When applied to the Qwen3-4BBase model, it yields consistent improvements of +1.2 and +0.4 percentage points on the respective benchmarks. These results demonstrate that the enhancements in reasoning capacity observed on in-domain mathematical benchmarks successfully generalize to improved reasoning performance on out-of-domain tasks.

Benchmark

30 25 20 15

100

200

300

400

500

600

700

Training Step

Figure 11: pass@64 on AIME26 across training checkpoints under different diversity-coefficient schedules.

ing effect during training: the restricted reasoning coverage artificially limits the variety of valid reasoning paths discovered, which consequently undermines the effectiveness of the annealed siblingdiversity term that relies on a rich, diverse set of trajectories to properly optimize the policy. Training Dynamics of the Diversity-Augmented Advantage. Table 4 reports the effect of the diversity coefficient only at the final checkpoint. To examine how the diversity-augmented advantage affects reasoning coverage throughout training, we additionally evaluate pass@64 on AIME26 at 100step intervals. We compare training without the diversity term (α = 0) against DATPO with the default linearly annealed schedule (α : 0.2 → 0). Each result is averaged over three independent evaluation runs and reported as the mean ± standard deviation. As shown in Figure 11, without the diversity term, pass@64 peaks at 30.0% at step 200 and decreases to 25.6% by step 700. In contrast, DATPO exhibits an overall upward trend after the initial training stage and reaches 33.3% at step 700. These results suggest that the diversity-augmented advantage mitigates the early saturation of reasoning cov-

Embedding

Size

all-mpnet-base-v2 bge-m3 gte-base-en-v1.5 gte-large-en-v1.5

110M 560M 137M 434M

MATH500 avg@8

pass@8

62.9 61.6 63.4 63.5

81.9 81.7 81.9 81.7

Table 13: Ablation study on different embedding models.

Method

Avg. Tokens

MATH500 avg@8

pass@8

TreeRL (4,3,4)

17,766.0

62.5

81.3

AttnRL (4,3,4)

12,478.7

62.1

80.0

DATPO

8,952.4

63.5

81.7

Table 14: Performance of baselines under wider tree topology. Avg. Tokens denotes the average number of generated tokens per question during training. The values in parentheses specify the tree expansion hyperparameters (N, K, B).

erage and promotes its continued expansion during training. Effect of Embedding Models As noted in Appendix F.2, DATPO defaults to using gte-large-en-v1.5 to compute the block-level sibling-diversity term (Divsib ). To assess the sensitivity of our framework to the choice of the embedding model, we conduct an additional ablation study comparing it against three alternative models of varying scales: all-mpnet-base-v2 (Reimers and Gurevych, 2019), bge-m3 (Chen et al., 2024), and gte-base-en-v1.5 (Zhang et al., 2024). As reported in Table 13, while the 434Mparameter gte-large-en-v1.5 model achieves the highest avg@8 accuracy (63.5%), smaller architectures such as all-mpnet-base-v2 (110M) and gte-base-en-v1.5 (137M) also yield highly competitive performance, even marginally outperforming the default configuration in pass@8 (81.9%). These results demonstrate that DATPO is robust to the scale and specific choice of the underlying embedding model. Consequently, the effectiveness of our diversity-augmented advantage appears to stem primarily from capturing stable, relative semantic distance signals among sibling blocks, rather than relying strictly on the absolute capacity or size of the embedding model itself.

F.6

Performance of Baselines under Wider Tree Topology

As detailed in Appendix F.2, the tree-based baseline methods (TreeRL and AttnRL) were evaluated using the default tree expansion hyperparameters reported in their original papers, specifically (N, K, B) = (6, 2, 2) for TreeRL and (N, Kmax , Bmax ) = (6, 2, 2) for AttnRL. In contrast, our proposed DATPO utilized a wider branching configuration of (N, Kmax , Bmax ) = (4, 3, 4) to ensure a sufficient number of branch rollouts for computing the sibling-diversity term. Although we rigorously constrained the total number of generated tokens to be comparable across all methods in our main experiments (Appendix F.3), one might argue that DATPO’s performance gains simply stem from this wider tree topology (B = 4) rather than its algorithmic design. To isolate the impact of our algorithmic design, we conduct an additional experiment where both TreeRL and AttnRL are trained using the identical wider configuration of (4, 3, 4) (or (4, 3, 4) maximum limits for AttnRL). As reported in Table 14, forcing the baselines into this wider topology does not improve their overall performance. We observe three key findings: First, our proposed DATPO achieves the highest performance in both avg@8 and pass@8 while generating the fewest average tokens per problem during training. Second, compared to their original (6, 2, 2) configurations (as reported in Table 2), both TreeRL and AttnRL experience performance degradation in some metrics when scaled to the (4, 3, 4) topology. Taken together, these results confirm that the superiority of our framework is driven by the algorithmic improvements of the difficultyadaptive rollout and diversity-guided exploration, rather than merely relying on wider tree expansion hyperparameters.

Further Related Works

G.1

Tree-based Search in Reinforcement Learning

Tree-based search, famously successful in reinforcement learning milestones like AlphaGo (Silver et al., 2016), is now being adapted to the generative landscape of LLMs to unlock more systematic exploration. TreeRL (Hou et al., 2025) pioneers this with an on-policy framework using entropyguided branching. To address computational bottlenecks, AttnRL (Liu et al., 2025a) improves effi-

ciency by leveraging difficulty-aware adaptive sampling within a one-step off-policy pipeline. Recent research optimizes structural efficiency: TEMPO (Tran et al., 2025) leverages prefix-tree structure for branch-aware credit assignment, while TreePO (Li et al., 2025a) maximizes KV-cache reuse. To prevent paths from collapsing into homogeneous reasoning, LATR (Xing et al., 2025) explicitly maximizes trajectory-level diversity by dynamically branching and pruning semantically redundant paths via lookahead simulation. Furthermore, TreeAdv (Cao et al., 2026) refines credit assignment by combining an entropy-based branching method with a tree-structured advantage redistribution. While these methods primarily utilize tree structures for credit assignment or computational efficiency, our work leverages tree structures with the primary goal of expanding the model’s reasoning coverage.

Use of AI assistants

AI assistants were utilized for code implementation and for refining the linguistic presentation of the manuscript. All AI-generated outputs were carefully reviewed, modified, and validated by the authors.

Record · ID 668064 · SHA-256 46637f2314fd5d6f
Retrieved via Conceptio — every document is proof-bundled with source, license, and retrieval metadata.