PaperlayerView exact revision on arXiv

Source-linked AI summary

Random Policy Valuation is Enough for LLM Reasoning with Verifiable Rewards

Haoran He, Yuxiao Ye, Qingpeng Cai, Chen Hu, Binxing Jiao, Daxin Jiang, Ling Pan

arXiv:2509.24981v1cs.LGcs.AI

TL;DR

Math RLVR uses a simpler deterministic, tree-structured MDP than the general-purpose settings for which common policy-optimization methods were designed, yet those methods can require heuristics to address instability and diversity collapse. The paper proves that uniform-policy Q-values can identify optimal actions and introduces ROVER, which uses those values to sample reasoning paths. It reports improved pass@1 and pass@256 results on competition-level math tasks and argues that the approach’s scope is bounded by the MDP assumptions.

  • Problem

    Common RLVR policy-optimization methods can suffer training instability and diversity collapse, while math reasoning has deterministic, tree-structured dynamics that raise the question of whether simpler methods suffice.

    Source: §1 · p. 2

  • Method

    The paper proves that greedy actions from a fixed uniform policy’s Q-values are optimal under the stated MDP structure and introduces ROVER, which softmaxes those values to sample actions.

    Source: §1 · p. 2, §3.1 · p. 6, §3.1.1 · p. 7

  • Results

    +8.2 on pass@1 and +16.8 on pass@256 on competition-level AIME24, AIME25, and HMMT25 tasks; ROVER also reports superior performance and diversity compared with state-of-the-art methods.

    Source: §1 · p. 3, §6 · p. 15

  • Takeaways & Limitations

    ROVER offers a simplified approach for RLVR in deterministic tree-structured MDPs with binary terminal rewards.

    Source: §6 · p. 15

    The optimality result assumes a finite-horizon MDP with deterministic transitions, a tree-structured state space, and binary terminal rewards.

    Source: §3.1 · p. 5, §3.1.1 · p. 7

Abstract

from arXiv · show

RL with Verifiable Rewards (RLVR) has emerged as a promising paradigm for improving the reasoning abilities of large language models (LLMs). Current methods rely primarily on policy optimization frameworks like PPO and GRPO, which follow generalized policy iteration that alternates between evaluating the current policy's value and improving the policy based on evaluation. While effective, they often suffer from training instability and diversity collapse, requiring complex heuristic tricks and careful tuning. We observe that standard RLVR in math reasoning can be formalized as a specialized finite-horizon Markov Decision Process with deterministic state transitions, tree-structured dynamics, and binary terminal rewards. Though large in scale, the underlying structure is simpler than general-purpose control settings for which popular RL algorithms (e.g., PPO) were developed, suggesting that several sophisticated techniques in existing methods may be reduced or even omitted. Based on this insight, we prove a surprising result: the optimal action can be recovered from the Q-function of a fixed uniformly random policy, thereby bypassing the generalized policy iteration loop and its associated heuristics. We introduce Random Policy Valuation for Diverse Reasoning (ROVER) to translate this principle into a practical and scalable algorithm for LLM math reasoning, a minimalist yet highly effective RL method that samples actions from a softmax over these uniform-policy Q-values. ROVER preserves diversity throughout training, allowing sustained exploration of multiple valid pathways. Across multiple base models and standard math reasoning benchmarks, ROVER demonstrates superior performance in both \textbf{quality} (\textbf{+8.2} on pass@1, \textbf{+16.8} on pass@256) and \textbf{diversity} (\textbf{+17.6\%}), despite its radical simplification compared to strong, complicated existing methods.

1 Introduction

The paper argues that math RLVR’s deterministic, tree-structured dynamics may not need the complex policy-iteration methods commonly used for RL. It presents a uniform-policy Q-value result and ROVER, which uses those values to balance reasoning quality and diversity.

1 Introduction

  • Current RLVR methods such as PPO and GRPO follow generalized policy iteration, but can suffer unstable learning and entropy collapse, prompting heuristic fixes and case-specific tuning.The cited methods alternate policy evaluation and improvement; examples of heuristics include clipping, KL regularization, and data selection.Source: §1 · p. 2
  • Math reasoning with verifiable rewards forms a finite-horizon MDP with deterministic, tree-structured transitions and binary terminal rewards.The paper asks whether this simpler structure permits an effective RLVR method that maintains both quality and diversity.Source: §1 · p. 2
  • In this setting, greedy action selection from Q-values of a fixed uniformly random policy can recover optimal actions without the GPI cycle.The authors present this as a theoretical result for the specialized math-reasoning setting.Source: §1 · p. 2
  • ROVER samples actions with a softmax over uniform-policy Q-values to explore multiple reasoning pathways while using an LLM-parameterized Q-function instead of a separate value network.The method also uses group reward centering and reward broadcasting to address reward-signal variance and training efficiency.Source: §1 · pp. 2–3
  • +8.2 on pass@1 and +16.8 on pass@256 on competition-level AIME24, AIME25, and HMMT25 tasks; ROVER also finds strategies absent from base models and GRPO-trained models.The authors report these results across diverse tasks and model scales.Source: §1 · p. 3

2 Preliminaries

The preliminaries formulate verifiable-reward LLM generation as an MDP and describe policy-gradient optimization and generalized policy iteration. They contrast those iterative methods with ROVER’s reliance on evaluating a fixed uniform policy.

2 Preliminaries

  • RLVR generation is formulated as an MDP in which states are finite token strings, actions are vocabulary tokens, transitions concatenate tokens deterministically, and completed responses receive binary verifiable rewards.The discount factor is set to 1 in practice, and prompts are sampled from an initial-state distribution.Source: §2 · p. 3
  • PPO-style policy optimization uses an importance-sampling ratio, clipping, KL regularization, and an advantage estimate; GRPO estimates advantages from grouped responses to each prompt.The passage identifies REINFORCE++ and GRPO as examples with different advantage implementations.Source: §2 · p. 3
  • The paper says ROVER seeks exploration and continual-learning desiderata without an explicit KL-divergence regularization term.The comparison is with existing policy optimization methods that use KL penalties to prevent catastrophic forgetting and maintain exploration.Source: §2 · p. 4
  • Generalized policy iteration alternates policy evaluation, which estimates action value, and policy improvement, which shifts preference toward actions scored better by those estimates.The section illustrates GPI in Figure 2.Source: §2 · p. 4, Figure 2 · p. 4
  • ROVER instead evaluates a fixed uniform random policy to derive Q-values, avoiding GPI’s iterative evaluation-improvement process and its non-stationary training target.The cited discussion describes this as simpler for training and implementation.Source: §2 · p. 4

3 ROVER: Random Policy Valuation for Diverse Reasoning

ROVER exploits the deterministic, tree-structured MDPs with binary terminal rewards that characterize math reasoning, replacing iterative policy improvement with valuation of a fixed uniform policy. Softmax action selection extends this approach to preserve diversity, and practical techniques adapt it to large vocabularies and long horizons.

3 ROVER: Random Policy Valuation for Diverse Reasoning

  • ROVER targets RLVR math reasoning's deterministic, tree-structured MDPs with binary terminal rewards, a simpler structure than general-purpose control settings.The tasks can still involve larger spaces and longer horizons than traditional discrete RL tasks.Source: §3 · p. 4, Table 1 · p. 5

3.1 The Random Policy Valuation Framework

  • Under this MDP structure, acting greedily on Q-values from a fixed uniform policy is optimal, and each Q-value represents the probability of a correct continuation.This reduces the problem to policy evaluation without iteratively improving the evaluated policy.Source: §3.1 · pp. 5–6

3.1.1 Beyond Greedy Selection: Balancing Quality and Diversity

  • ROVER samples actions with a softmax over uniform-policy Q-values; at ρ = 1, it covers all four optimal modes with 100% success in the didactic example.Temperature ρ trades off diversity and quality; the performance gap from optimal vanishes as ρ approaches zero.Source: §3.1.1 · pp. 6–7, Figure 5 · p. 7

3.2 Practical Implementation

  • ROVER adapts valuation to large vocabularies and long horizons using the LLM's parameters, a fixed-baseline relative Q-function, and mean-centered rewards broadcast across generated tokens.Sampling n responses per prompt reduces estimation variance and enriches the value-landscape approximation.Source: §3.2 · pp. 8–9

4 Experiments

ROVER is evaluated on countdown and math reasoning tasks, with results covering solution quality, diversity, learned reasoning behavior, and ablations. Across the reported math benchmarks, it improves pass@1 and pass@k, while the countdown experiments examine training dynamics and solution diversity.

4.1 Countdown Tasks

  • On countdown tasks, ROVER surpasses all baselines after 400 training steps and ultimately reaches the highest ceiling performance.Its entropy remains higher than the baselines, and it finds more diverse solutions; Figure 7 reports 17 distinct correct solution equations for ROVER versus 3 for GRPO.Source: §4.1 · pp. 9–10, Figure 7 · p. 9
  • A temperature ρ of 1 achieves robust performance; higher values slow convergence, while lower values encourage premature exploitation and entropy collapse.At ρ = 0.001, near-deterministic sampling is associated with severe training instability.Source: §4.1 · p. 10, Figure 8 · p. 10

4.2 Reasoning on Math Tasks

  • For math-task evaluation, the study uses Qwen3-8B-Base, Qwen3-4B-Base, and DeepSeek-R1-Distill-Qwen-1.5B, with DeepSeek results reported in the appendix.Training uses DeepScaler; evaluations include AIME24, AIME25, HMMT25, OlympiadBench, AMC23, MATH500, and the out-of-distribution GPQA-diamond benchmark.Source: §4 · p. 9, §4.2 · p. 10

4.2.1 Performance Analysis

  • +8.2 pass@1 over the strongest baseline on AIME24, AIME25, and HMMT25 is reported for Qwen3-8B-Base.The reported pass@1 improvements are +7.3 averaged across all benchmarks and +8.2 averaged on the AIME24, AIME25, and HMMT25 subset.Source: §4.2.1 · pp. 10–11
  • +16.8 over the best baseline on pass@256 averaged on AIME24, AIME25, and HMMT25; ROVER also continues gaining as k increases.The passage reports that ROVER surpasses all baselines and the base model as k increases, while baselines saturate or underperform the base model at large k.Source: §4.2.1 · pp. 11–12, Figure 9 · p. 11

4.2.2 Diversity Analysis

  • +17.6% relative diversity improvement over the average of all baselines is reported, alongside +6.8% over GRPO.Diversity is measured by the number of distinct strategies among up to 32 correct AIME24 responses, judged for strategic equivalence.Source: §4.2.2 · p. 12, Figure 10 · p. 12

4.2.3 Behavioral Analysis

  • ROVER outputs more reasoning-related forking tokens, especially tokens associated with rethinking and self-correction, and discovers two strategies beyond those found by the base and GRPO models.The strategy comparison uses 32 samples per model, clustered by strategic equivalence using an LLM judge.Source: §4.2.3 · pp. 13–14, Figure 13 · p. 13, Figure 12 · p. 13

4.2.4 Ablation Studies

  • In the Bellman-target ablation, removing Q′ causes entropy and response length to collapse, while β = 5.0 diminishes the reward signal and degrades performance.Performance remains stable for β from 0.2 to 1.0, and the default is β = 1.0.Source: §4.2.4 · p. 14, Figure 14 · p. 14

5 Related Work

Prior RLVR methods commonly build on policy-gradient objectives and add heuristics to address instability and diversity. The paper contrasts this approach with random-policy valuation and emphasizes semantic measures of reasoning diversity.

RLVR

  • RLVR work includes actor-only methods such as GRPO, RLOO, ReMax, and REINFORCE++, while leading approaches still rely on PPO-style objectives and often use case-specific heuristics [Schulman et al., 2017] [Shao et al., 2024] [Li et al., 2024] [Hu et al., 2025a].The cited heuristics include advantage normalization, clipping, KL regularization, entropy loss, reward shaping, and data augmentation.Source: §5 · p. 14

Diversity metrics and diversity-aware RLVR

  • The paper favors semantic-level diversity measures because syntactic variation can fail to distinguish strategies in complex reasoning tasks [Zhang et al., 2025c].The discussed measures include cosine distance, number of distinct strategies, and utility.Source: §5 · p. 15
  • Unlike cited diversity-aware methods that reweight rewards using sequence probability, submodular mutual information, or semantic classification, ROVER aims to preserve generation diversity without explicit regularization or heuristics [He et al., 2025a] [Chen et al., 2025b] [Li et al., 2025a].The related-work discussion characterizes ROVER as grounded in random-policy valuation.Source: §5 · p. 15

6 Conclusion

The conclusion presents ROVER as a simplified RLVR approach based on uniformly random policy Q-values and states the structural setting behind its theoretical result. The accompanying proof explains why greedy actions from those Q-values lead to an optimal policy in that setting.

6 Conclusion

  • ROVER is presented as achieving high-quality, diverse reasoning policies while eliminating complex evaluation-improvement loops, with superior performance and diversity to state-of-the-art methods.The conclusion limits experiments to math reasoning with models up to 8B parameters and notes that tool calls or intermediate feedback may violate the assumed MDP structure.Source: §6 · p. 15
  • The conclusion treats extending ROVER beyond its current setting, including applications with tool calls or intermediate feedback, as future work because those settings may not satisfy its assumptions.Source: §6 · p. 15

A.1 Proof of Theorem 3.1

  • For a finite-horizon MDP with deterministic tree structure and binary terminal rewards, the greedy policy with respect to the uniform-policy Q-function is optimal.The proof argues that positive Q-values identify actions whose subtrees contain a correct terminal state, so greedy choices remain on a path to a correct solution.Source: §A.1 · p. 22

A.2 Proof of Theorem 3.2

The proof bounds the value of a softmax policy built from uniform-policy Q-values. It analyzes incorrect trajectories by grouping them according to their last key state and notes that the bound approaches the optimal value as temperature approaches zero.

A.2 Proof of Theorem 3.2

  • Theorem 2 gives a lower bound on the value of the softmax policy πs, whose actions are selected from uniform-policy Q-values at temperature ρ.The passage defines key states as states with both optimal and suboptimal actions and defines Prπs(s|s0) as the probability of reaching s from s0 under πs.Source: §A.2 · p. 22
  • The proof groups incorrect trajectories by their last key state, using the tree structure to partition the set of incorrect trajectories.It then relates the probability of failure to the chance that πs chooses a zero-Q-value action at that last key state.Source: §A.2 · pp. 22–23
  • As ρ approaches zero, the bound’s right-hand side converges to R, the optimal value.Source: §A.2 · pp. 22–23

B Gradient Analysis

This section compares ROVER’s gradient objective with policy-gradient methods and identifies conditions under which their objectives can be approximately equal. It also reports supplemental pass@k results across values of β.

B Gradient Analysis

  • ROVER’s gradient and GRPO’s gradient share the core term ∇θ log πθ(a|s).The comparison assumes the policy πθ depends on θ.Source: B Gradient Analysis · pp. 23–24
  • The objectives can be approximately equal if ROVER’s Q′ term is removed and GRPO’s advantage is normalized without the standard-deviation term.Source: B Gradient Analysis · p. 24
  • A supplemental figure reports pass@k performance across β values for Qwen3-4B-Base after 300 training steps.Source: Figure 15 · p. 25

C The Countdown Task

The section presents Countdown as a math-reasoning task in which a model must use given numbers and basic arithmetic operations to reach a target. It describes the task as an accessible test bed despite its challenge for small models.

The Countdown Task

  • Countdown evaluates arithmetic reasoning by asking an LLM to find an equation that reaches a target using given numbers and basic operations.Source: C The Countdown Task · p. 25
  • For the supplied number set {19, 36, 55, 7}, the target 65 is reached exactly by 55 + 36 − 7 − 19, providing a valid arithmetic solution for this instance.Source: C The Countdown Task · p. 25
  • The task’s reasoning path is simple, but it remains challenging for small LLMs, making it an accessible math-reasoning test bed.Source: C The Countdown Task · p. 25
  • Training and testing use TinyZero’s 327,680-problem training set and 1,024 unseen test problems, with binary reward for equation correctness.Source: C The Countdown Task · p. 25

D Results of Math Tasks on DeepSeek-1.5B

On DeepSeek-R1-Distill-Qwen-1.5B, ROVER is evaluated on math competition tasks using pass@1 and pass@64. It outperforms DeepScaler on both measures in a same-dataset comparison, while the ProRLv2 comparison differs in data and training compute.

D Results of Math Tasks on DeepSeek-1.5B

E.1 Training and Evaluation Details

The section gives training and evaluation settings, a token-probability case study, and additional pass@k and maj@k results. ROVER has consistently superior pass@k on Qwen3-4B-Base across k values, while other RL baselines decline at higher k.

E.1 Training and Evaluation Details

  • Training fixes 600 steps for ROVER and baselines with 128 × 8 samples per step; evaluation uses 256 runs on smaller benchmarks and 10 on larger ones.Source: §E.1 · p. 26
  • The baselines include PPO, GRPO, DAPO, and REINFORCE++; implementations follow official veRL recipes.Source: §E.1 · pp. 26–27

E.2 Case Studies

  • On a representative AIME24 prompt, ROVER assigns higher probabilities to contrast- or shift-indicating tokens, particularly “wait,” which facilitates exploration of alternative reasoning paths.Source: §E.2 · p. 27, Figure 16 · p. 28

E.3 Additional Experiment Results

  • ROVER shows consistently superior pass@k on Qwen3-4B-Base across k values, while other RL baselines drop as k increases.Source: §E.3 · p. 27, Figure 17 · p. 28
  • Supplementary maj@k results cover AIME25 for Qwen3-8B-Base, averaging 1,000 repeated random samplings of k responses.Source: §E.3 · p. 28, Figure 18 · p. 28

E.3.1 Ablation of temperature ρ

The temperature ablation shows that higher temperature increases stochasticity and maintains entropy, while lower temperature trades diversity and pass@k for better pass@1. The appendix also compares training entropy, defines additional diversity measures, and presents prompt and decoding-temperature analyses.

E.3.1 Ablation of temperature ρ

  • A smaller training temperature (ρ = 0.01) yields a greedy, deterministic policy that improves pass@1 but compromises diversity, including reduced pass@k; the default is ρ = 1.A larger temperature (ρ = 4) produces more stochastic behavior and constant entropy, which affects performance.Source: §E.3.1 · pp. 28–29, Figure 19 · p. 29

E.3.2 Training dynamics

  • ROVER maintains relatively higher entropy during training, which can increase stably later, while baseline entropy inevitably falls to a low level.The curves compare Qwen3-8B-Base and Qwen3-4B-Base.Source: Figure 20 · p. 29

E.4 Measuring the diversity of LLM responses

  • The appendix supplements its distinct-strategy count with utility, which combines diversity and quality under a user-patience model, and cosine distance, the average pairwise response-embedding distance.Higher cosine distances indicate greater semantic diversity; utility rewards novel responses while geometrically discounting additional generations.Source: §E.4 · pp. 29–30

E.5 Prompts

  • The appendix reports quality-diversity trade-offs at decoding temperatures t ∈ [0.3, 0.9, 1.2] and provides the RL training, evaluation, and judge prompt templates.The base model uses the same prompt template during evaluation as the trained model; the judge prompt refines Li et al. (2025a) for more nuanced strategy classification.Source: §E.4 · p. 30, §E.5 · p. 30, Figure 24 · p. 31

E.4 Measuring the diversity of LLM responses

  • ROVER exhibits greater diversity than baselines across all decoding temperatures on the three diversity metrics.Its diversity advantage is most pronounced at relatively low decoding temperature, such as t = 0.3; baseline diversity improves as temperature rises but remains lower.Source: §E.4 · p. 30, Figure 23 · p. 31

Related papers

Loading 2509.24981v1…