What Can You Do When You Have Zero Rewards During RL?

## Abstract

Abstract Reinforcement learning (RL) with outcome-based rewards has proven effective for improving large language models (LLMs) on complex reasoning tasks. However, its success often depends on the base model occasionally sampling correct solutions. When no correct solutions are sampled, training encounters a zero-reward barrier where learning stalls due to zero gradients. We study this scenario through the graph search task introduced in Bachmann and Nagarajan ( 2024 ) and evaluate recent methods that incorporate desirable components such as dense rewards, diversity incentives, and improved credit assignment. Our experiments show that none of these approaches overcome the zero-reward barrier if the base model never produces a correct answer. In contrast, we find that a simple data-centric intervention of adding easier samples to the training set enables the model to eventually solve the original hard task despite starting from zero reward. Importantly, this succeeds without modifying the RL algorithm itself. Because official implementations of several baselines were unavailable, we developed our own, which allowed us to conduct a detailed analysis of their failure modes. We release these implementations to support further research: https://github.com/rl4reasoning/rl-baselines .

## 1 Introduction

Reinforcement learning (RL) has emerged as a crucial tool in the post-training of large language models (LLMs) for tackling complex reasoning tasks such as mathematical problem solving (Guo et al., 2025), web navigation (Putta et al., 2024), and algorithmic discovery (Fawzi et al., 2022). These advances often rely on sparse rewards, where the model receives only a binary correct-or-incorrect signal at the end of its response. Although such outcome-based rewards can significantly enhance model accuracy, their effectiveness typically relies on starting from a reasonably strong base model (Yue et al., 2025; Gandhi et al., 2025).

When the base model fails to solve a task even after repeated attempts, RL training becomes ineffective since zero rewards yield zero gradients, leaving the model parameters unchanged throughout training, preventing further scaling of RL.

This begs the question:

What can one do if there are zero rewards due to no correct answers
being sampled by the model during RL post-training?

To study this question, we consider the simple task of searching for a path from a source node to a target node in a star graph from Bachmann and Nagarajan (2024) (see Fig.[1](https://arxiv.org/html/2510.03971v1#S1.F1)). As we will discuss later, this task enables a controlled and systematic study of how different RL post-training methods perform under zero outcome rewards
(see Sec.[2](https://arxiv.org/html/2510.03971v1#S2)).

While one could address the issue of zero rewards by performing supervised fine-tuning (SFT) on human-written or model-generated traces and then apply RL (Gandhi et al., 2025), we deliberately rule out this option for the sake of this study.
This lets us isolate and evaluate methods specifically intended for scenarios with zero outcome rewards during RL training.

The above assumption leaves us with several interesting approaches to tackle the problem of zero rewards. For instance, one could apply reward shaping (Setlur et al., 2025a; Qu et al., 2025) to obtain dense rewards that provide a learning signal based on the quality of intermediate steps, even when outcome rewards are zero.
One could also explore approaches that improve credit assignment for intermediate steps in reasoning (Kazemnejad et al., 2024). Alternatively, the model could be incentivized to sample diverse responses during RL fine-tuning (Chow et al., 2025), in the hope that at least one response receives a non-zero reward, thereby kick-starting RL training.

Figure: Figure 1: (Left) Illustration of the Degree-3-Path-3 task, where the center node ($4$) has degree $3$ and each outgoing path has length $3$. The graph is represented as an adjacency list, and given a source node ($4$) and a destination node ($7$), the task is to output a path from source to destination (e.g., $4,2,7$). See Appendix [C](https://arxiv.org/html/2510.03971v1#A3) for the prompt used. (Right) Success rates of different baselines: Dr.GRPO, VinePPO, Progress Rewards, and Best-of-N aware finetuning, compared with our data-mixing approach, which augments the training dataset with an equal proportion of samples from the easier Deg-5-Path-5 dataset. The baselines fail to break the zero-reward barrier, yielding zero success on the test set, whereas mixing in easier samples if effective with outcome rewards.
Refer to caption: figures/Star-Graph.png

However, to our surprise, we find that all of these methods fail (Figure [1](https://arxiv.org/html/2510.03971v1#S1.F1)) on the simple graph search task(^1^11In scenarios where the base model cannot sample a correct answer), despite being specifically designed for cases with zero outcome rewards (see Sec. [3](https://arxiv.org/html/2510.03971v1#S3)). We investigate these methods and discuss possible explanations for their failure (Sec. [4.1](https://arxiv.org/html/2510.03971v1#S4.SS1) and App. [A](https://arxiv.org/html/2510.03971v1#A1)). Notably, no official code was available for several of these baselines, so we implemented our own versions, which we release for the community to build upon.

In contrast, we show that a simple data-centric intervention unlocks RL training. By adding easier(^2^22Samples where the base model can generate a correct answer and receive a non-zero reward) instances to the training dataset, the model gradually learns to solve the harder task using outcome rewards only, even when it was initially unable to do so. Crucially, this is achieved without modifying the RL algorithm at all.

This strategy can be seen as a form of implicit curriculum (Stojanovski et al., 2025; Setlur et al., 2025b). In the discussion, we explain how this intervention can aid skill learning (Eysenbach, 2025), and how correlated actions learned from easier samples (see Sec. [5.3](https://arxiv.org/html/2510.03971v1#S5.SS3)) can transfer to harder tasks that the base model could not previously solve.

Our contributions are three fold: (i): We benchmark recently proposed RL algorithms that aim to (a) improve diversity in samples (Chow et al., 2025), (b) perform credit assignment (Kazemnejad et al., 2024), or (c) apply reward shaping (Setlur et al., 2025a), and observe that none of these approaches are effective under zero outcome rewards on a graph search task. (ii): We demonstrate a simple data-centric approach is able to unlock RL training, where mixing samples of easier difficulty helps the model learn to solve the original hard task, even when the model initially could not do so. (iii): In the process of benchmarking different approaches, we implement baselines for which no official code was available, and provide a detailed analysis of why these methods are ineffective in zero outcome rewards scenario.

## 2 Experimental Setup

In this section, we describe the task and outline the baselines we compare against.

Q: What is the task?

A: We study the graph search problem introduced in Bachmann and Nagarajan (2024). As shown in Fig. [1](https://arxiv.org/html/2510.03971v1#S1.F1), the input is an adjacency list representing a star graph, along with a source and destination node. The task is to output the path from the source to the destination, where the source is always the center of the star and the destination is one of its leaf nodes. To benchmark models in the zero-reward setting, we use the Degree-10-Path-10 graph, where the center node has degree $10$ and each branch has length $10$. As illustrated in Fig. [1](https://arxiv.org/html/2510.03971v1#S1.F1), existing methods fail on this task.

Q: Why bother about a graph search problem?

A: Although the task may seem simple, it has several properties that make it well-suited for our study: (i) Controlled difficulty: The task supports automatic dataset generation at varying difficulty levels, allowing a systematic study of how training on easier instances transfers to harder ones. (ii) Challenging for transformers: Prior work shows that transformers struggle to directly output the correct path, but if they perform intermediate reasoning in a chain of thought, they can effectively search through the graph in-context. (iii) Low reliance on world knowledge: Solving these tasks does not require external knowledge. This is a critical feature, as it allows us to isolate the core technical challenge, the zero-reward barrier, without the confounding factors of external information such as knowledge of theorems or lemmas which are often useful for mathematical reasoning problems. This also enables rigorous comparisons of methods with modest compute using relatively small models (e.g., $1.5$B parameter scale).

Q: What baselines do we evaluate?

A: We evaluate three recent methods that tackle different challenges in reinforcement learning for reasoning tasks. VinePPO (Kazemnejad et al., 2024) improves step-level credit assignment by measuring the change in value between states before and after each reasoning step using Monte Carlo rollouts. Although this slows individual training iterations, it reduces gradient variance and stabilizes learning. Along similar lines, Rewarding Progress (Setlur et al., 2025a) combines outcome rewards with step-level advantages estimated under a different policy, encouraging exploration and making it particularly effective on hard problems. Best-of-N-aware (BoN) finetuning (Chow et al., 2025) takes a complementary approach by modifying the training objective to better match inference-time goals: instead of requiring all $N$ generations to be correct, it encourages producing at least one correct output among $N$ attempts. This promotes diversity in the model’s outputs and increases the likelihood of obtaining a non-zero reward to initiate RL training. Together, these methods represent state-of-the-art strategies for addressing sparse rewards. For details on the objective and implementation refer Appendix [A](https://arxiv.org/html/2510.03971v1#A1).

Q: What is the training setup?

All experiments were conducted on $4$ NVIDIA H100 GPUs using Qwen2.5-1.5B-Instruct as the base model. Each experiment was limited to a maximum of 24 hours or 1,000 RL iterations, whichever occurred first. While we used a single model across all experiments, we expect our findings to generalize to other models. The primary difference would be which tasks are challenging: for Qwen2.5-1.5B-Instruct, the Degree-10-Path-10 dataset is difficult, whereas other models might find it easier or harder. Nevertheless, increasing task complexity would likely lead to failures even for larger models.

## 3 Baselines fail under zero outcome rewards

Surprisingly, all the baseline methods we tried—namely, naive RL (Dr. GRPO) Shao et al. (2024), VinePPO Kazemnejad et al. (2024), Rewarding Progress Setlur et al. (2025a), and Best-of-N-aware finetuning Chow et al. (2025)—failed on the simple star graph search task, specifically on the Degree-10-Path-10 instance (see Fig. [1](https://arxiv.org/html/2510.03971v1#S1.F1)).

While naive RL is expected to fail under zero-outcome rewards, it is notable that the other baseline methods also fail to solve the task, despite being designed to operate under such conditions.

A keen reader may already have several questions about this result. Before proceeding further, we first address these potential questions.

Q: Is this task even solvable?

We will see in Section [5](https://arxiv.org/html/2510.03971v1#S5) that the Degree-10-Path-10 task is indeed solvable. Furthermore, Fig. [2](https://arxiv.org/html/2510.03971v1#S3.F2) shows that all baselines can solve the easier Degree-3-Path-3 task, in which the center node has a degree of 3 and each outgoing path consists of 3 nodes.

Q: Are you sure this isn’t a hyper-parameter issue in the baselines?

To rule out any implementation issues, we focused on several important aspects of each method. For VinePPO, we increased the number of rollouts used to estimate the value of intermediate states, giving the model additional chances to reach the correct answer. To meet the requirements of desirable provers outlined in Setlur et al. (2025a), we experimented with more powerful provers that can occasionally solve the Degree-10-Path-10 task. For Best-of-N aware finetuning, we followed the recommended practices described in Chow et al. (2025), testing two different schedules for the KL coefficient and increasing clipping for the sample-dependent weights.

Unfortunately, none of our interventions succeeded. A discussion of these experiments is provided in Section [4.1](https://arxiv.org/html/2510.03971v1#S4.SS1). In Sec. [5](https://arxiv.org/html/2510.03971v1#S5) we discuss a simple data-mixing strategy that helps the unlock RL training.

Figure: Figure 2: Success rates of different RL algorithms (Dr.GRPO, VinePPO, Progress Rewards, and Best-of-N aware finetuning) on a held-out test set of Degree-3-Path-3 graphs. These models were trained on Degree-3-Path-3 graphs. All algorithms are able to solve the task when the model starts with a reasonable success rate. Furthermore, VinePPO converges in fewer iterations compared to Dr.GRPO, consistent with findings reported in the literature.
Refer to caption: x2.png

## 4 Failure Analysis of Baselines

All four baselines, including Dr.GRPO, Progress Rewards, VinePPO, and Best-of-N aware finetuning, receive no rewards during training, and thus have zero success rates at test time (see Fig. [1](https://arxiv.org/html/2510.03971v1#S1.F1)). For the VinePPO and Progress Rewards baselines, we use Monte Carlo rollouts to estimate the value of intermediate states and compute step-level advantages (refer Appendix [A](https://arxiv.org/html/2510.03971v1#A1)), which makes each RL iteration roughly five times slower. Nevertheless, we continued training these two methods for approximately five times longer than Dr.GRPO and Best-of-N aware finetuningto rule out the possibility that they might start solving the task at later stages. Despite this extended training, we observe that these methods remain unable to solve the task.

As we discuss in Section [4.1](https://arxiv.org/html/2510.03971v1#S4.SS1), a key reason for the failure of some baselines on the Degree-10-Path-10 task is the base model’s inability to occasionally sample correct trajectories. To rule out any implementation issues, we also experimented with a variant of the task where the center node has a degree of three and each outgoing path has three nodes. In this setting, the base model has an initial success rate of $\sim 20\%$, analogous to the conditions explored in prior work where the base model starts with a reasonable success rate. As shown in Fig. [2](https://arxiv.org/html/2510.03971v1#S3.F2), we observe that (i) all algorithms are able to solve the task when the base model begins with a reasonable success rate, and (ii) although each iteration of VinePPO is more expensive, it converges in fewer iterations compared to Dr.GRPO, consistent with findings reported in the literature.

### 4.1 Case-by-case analysis

Here we discuss some of the reasons why the baselines are ineffective on harder variants of the task.

Dense rewards are not really dense in VinePPO and Progress Rewards: Methods like VinePPO and Progress Rewards go beyond Dr.GRPO by computing step-level advantages. However, non-zero step-level advantages are obtained only when there is a change in the value of the state before and after taking the step. This means that for VinePPO to produce a non-zero advantage for a step ($\hat{A}^{\pi_{\theta}}_{y_{c_{i}}}\neq 0$ in equation [4](https://arxiv.org/html/2510.03971v1#A1.E4) ), some of the rollouts under the current policy must succeed. Similarly, for the Progress Rewards, some of the rollouts under the prover policy must succeed ($\hat{A}^{\mu}_{y_{c_{i}}}\neq 0$ in equation [6](https://arxiv.org/html/2510.03971v1#A1.E6)). In our setting, we observe that throughout training, neither the current policy nor the policy generates a successful rollout. Thus step-level advantages offer no learning signal.

Instantiating a helpful prover to get a meaningful Progress Rewards is hard:
The Progress Rewards (Setlur et al., 2025a) work notes that a prover that is too strong or too weak is ineffective: a strong prover cannot distinguish between good and bad steps, while a weak prover fails from most intermediate states, resulting in zero step-level advantages and no learning. Consequently, they identify two desirable properties for provers: (i) the prover should neither be too strong nor too weak, and (ii) it should be reasonably aligned with the policy being optimized.

To satisfy these requirements for the Degree-10-Path-10 graph, we experiment with two provers. The first, $\pi_{\text{5x5}}$, is model trained using Dr.GRPO on the Degree-5-Path-5 task and achieves around $65\%$ accuracy on Degree-10-Path-10, partially satisfying the first property. The second, $\pi_{\text{5x5 mixed with 10x10}}$, is trained using Dr.GRPO on an equal mixture of Degree-5-Path-5 and Degree-10-Path-10 graphs and reaches around $85\%$ accuracy on Degree-10-Path-10.

As shown in Fig. [3](https://arxiv.org/html/2510.03971v1#S4.F3), both provers have a reasonable success rate on the Degree-10-Path-10 task from the start, giving non-zero step-level advantages early in training. The $\pi_{\text{5x5}}$ prover provides non-zero step-level advantages about $50\%$ of the time, while the $\pi_{\text{5x5 mixed with 10x10}}$ prover does so about $60\%$ of the time. However, as seen in Fig. [3](https://arxiv.org/html/2510.03971v1#S4.F3), this signal does not lead to better task performance. In both cases, the model responses often become degenerate, repeating characters or words to fill the context window. We believe this happens because the prover policy is not well aligned with the policy being optimized.

Figure: Figure 3: Effect of Progress Rewards using different prover policies. (Left): Fraction of non-zero step advantages ($\hat{A}^{\mu}_{y_{c_{i}}}\neq 0$ in Equation [6](https://arxiv.org/html/2510.03971v1#A1.E6)) for two provers: $\mu=\texttt{Best-of-4}(\pi_{5\text{x}5})$ and $\mu=\texttt{Best-of-4}(\pi_{5\text{x}5\text{-mixed-with-}10\text{x}10})$, where the models were trained on Deg-5-Path-5 alone or mixed with Deg-10-Path-10, respectively. Both models provide non-zero step advantages for Progress Rewards due to their reasonable success rates on the harder task. (Right): Success rate on a held-out test set of Degree-10-Path-10 examples. Despite using the same two provers, both models fail on the Degree-10-Path-10 task. We believe this is because the prover policy is not well aligned with the policy being optimized.
Refer to caption: x3.png

Unstable training in Best-of-N aware finetuning:
We followed the practices suggested in Chow et al. (2025), including (a) using a KL schedule and (b) clipping the sample-dependent weights multiplied by the log probability (Eq. 9 in Chow et al. (2025)). Notably, the KL schedule in Chow et al. (2025) is quite aggressive, starting with a coefficient of $1$ and decaying to $0.001$, whereas the current standard is to keep it constant at $0.001$ (Kazemnejad et al., 2024). They also clip the failure probability ($p_{\text{fail}}$; see Section [A.5](https://arxiv.org/html/2510.03971v1#A1.SS5)). Despite these strategies, we observed large sample-dependent weights ($g_{N}^{+}$ and $g_{N}^{-}$ in Eq. [8](https://arxiv.org/html/2510.03971v1#A1.E8)), which we countered by directly clipping them to stabilize training. Unfortunately, none of these interventions enabled the model to solve the Degree-10-Path-10 dataset.

To investigate further, we applied the method to the Degree-5-Path-5 dataset which Dr.GRPO can effectively solve (see Fig. [7](https://arxiv.org/html/2510.03971v1#A4.F7)). We believe a major reason is the presence of very high negative gradients. When the failure probability ($p_{\text{fail}}$) is close to 1, the sample-dependent weights become large, and multiplying them by negative log probabilities produces high magnitude negative gradients. This drives the model responses toward degeneracy where it repeats the same set of characters. Figure [4](https://arxiv.org/html/2510.03971v1#S4.F4) shows this effect: with a lower KL penalty ($0.001$), the model’s response lengths increase rapidly, and inspection of the outputs confirms degeneracy, while success rates remain zero. Using a strong-to-weak KL penalty ($0.1~\text{to}~0.001$) stabilizes training but does not help solve the hard task.

We think this problem of high negative gradients could be resolved when one uses a capable base model to begin with (low failure probability means lower magnitude sample dependent weights for the negative samples), which is what Chow et al. (2025) work with (also see Fig. [2](https://arxiv.org/html/2510.03971v1#S3.F2) where Best-of-N aware finetuning is able to solve the Degree-3-Path-3, possibly due to relatively lower failure rates initially, compared to Degree-5-Path-5).

We believe that the issue of high negative gradients can be mitigated by starting with a capable base model. Such a model has a lower failure probability ($p_{\text{fail}}$ in Eq. [8](https://arxiv.org/html/2510.03971v1#A1.E8)), which keeps the sample-dependent weights $g_{N}^{+}$ and $g_{N}^{-}$ (in Eq. [8](https://arxiv.org/html/2510.03971v1#A1.E8)) within a reasonable range, thus ensuring stable training. As shown in Fig. [2](https://arxiv.org/html/2510.03971v1#S3.F2), Best-of-N aware finetuning is able to solve the Degree-3-Path-3 task, likely due to its relatively lower initial failure rates compared to Degree-5-Path-5.

Figure: Figure 4: Using a lower KL coefficient, i.e., the standard value of 0.001 in Best-of-N aware finetuning, results in unstable training due to large-magnitude negative gradients, causing model responses to degenerate into repeating the same character. In contrast, using a KL schedule as recommended in Chow et al. (2025) (decaying from a strong KL penalty of $0.1$ to $0.001$) remains stable but fails to learn, as success rates stay at zero (see figure on the right).
Refer to caption: x5.png

## 5 Adding easy samples works

As shown in Fig. [1](https://arxiv.org/html/2510.03971v1#S1.F1), mixing a simpler variant of the task, specifically samples from the Degree-5-Path-5 dataset, into the original Degree-10-Path-10 dataset significantly improves performance, allowing the model to solve the task where all baselines had previously failed.

This raises an important question: are all “easy” samples equally effective? In this section, we explore (i) the impact of mixing samples of varying difficulty levels and (ii) how one can, in some cases, bypass the challenge of selecting samples with the appropriate difficulty for a given task.

### 5.1 Not all easy samples work

Here we consider mixing two other types of easy datasets in equal proportion with the original Degree-10-Path-10 task. The first easy graph is a Degree-2-Path-5 graph, where the center node has a degree of $2$, and each of the outgoing paths has $5$ nodes. The second easy graph is a Degree-5-Path-2 graph, where the center node has a degree of $5$, and each of the outgoing paths has only $2$ nodes.

As shown in Fig. [5](https://arxiv.org/html/2510.03971v1#S5.F5) (left), in both cases the training rewards saturate around $0.5$. From Fig.[5](https://arxiv.org/html/2510.03971v1#S5.F5) (right), it is evident that neither of the easier datasets helps in solving the original Degree-10-Path-10 task. Examining the chain-of-thought traces reveals that: (i) when the Degree-2-Path-5 task is mixed with the original task, the model often explores only two branches before committing to a final answer. While this strategy works for the easier dataset (where the center node has degree $2$), it fails on the Degree-10-Path-10 task, which requires exploring multiple branches. (ii) In the case of the Degree-5-Path-2 mixture, instances are solved using a simple adjacency-list lookup, and the model shows no evidence of backtracking on harder graphs. In both settings, the model learns to solve only the easier dataset in the mixture, which explains why the training rewards plateau near $0.5$.

Figure: Figure 5: (Left): Rewards that Qwen2.5/Qwen-1.5B-Instruct model obtains while training Dr.GRPO on a dataset containing an equal mixture of (i): Degree-5-Path-2 mixed with Degree-10-Path-10, and (ii): Degree-2-Path-5 mixed with Degree-10-Path-10. The training rewards saturate to around $0.5$ in both cases, and in both cases the model learns to solve the easier examples in the mixture. (Right): Success rate on a held-out test set of Degree-10-Path-10 examples. Both mixtures do not help the model solve the harder Degree-10-Path-10 task.
Refer to caption: x7.png

### 5.2 Mixing all samples you have is effective

From Fig. [5](https://arxiv.org/html/2510.03971v1#S5.F5), it is clear that not all easy samples are equally effective, and it is not obvious in advance what a model will learn from a given dataset. To be useful, samples must have the right difficulty, meaning they should be solvable by the model while also encouraging behaviors that transfer to the target task. As we saw earlier, adding Degree-5-Path-5 examples improves performance (Fig. [1](https://arxiv.org/html/2510.03971v1#S1.F1)), whereas adding much easier examples such as Degree-5-Path-2 or Degree-2-Path-5 does not (Fig. [5](https://arxiv.org/html/2510.03971v1#S5.F5)). For the graph search task, one can probably reason why Degree-5-Path-2 or Degree-2-Path-5 is very easy and why Degree-5-Path-5 represents the right difficulty. However, for general tasks, it is often difficult to define the right difficulty a priori. This requirement of selecting the right difficulty makes the approach cumbersome.

However, we find that if one mixes all samples they have of varying difficulty in the training dataset and then train using naive RL (Dr.GRPO), the model is able to solve the hard task.
To be specific, if one constructs a dataset that combines Degree-2-Path-5, Degree-5-Path-2, Degree-5-Path-5, and Degree-10-Path-10 examples in equal proportion, and train using Dr.GRPO, model learns to solve the Degree-10-Path-10 task (see Fig. [6](https://arxiv.org/html/2510.03971v1#S5.F6)). Importantly, the RL algorithm itself remains unchanged, only the data changes .

Thus, if the base model cannot solve the task initially, adding samples of varying difficulty can help it succeed. Moreover, even when the base model can already solve the task, easy-to-hard curricula that is implicit in the dataset can accelerate convergence (Stojanovski et al., 2025).

### 5.3 Why does this work?

We believe there may be an interesting connection to skill learning here (Eysenbach, 2025). Easier samples allow the model to acquire certain skills (or correlated actions) from outcome rewards alone. These learned skills can then transfer to more difficult tasks that the base model could not originally solve. Another way to view this is that correlated actions (or skills) simplify the search problem during RL: the model now searches in the space of skills rather than in the raw space of tokens (which is much larger). In other words, including examples of the appropriate difficulty in the training mixture helps reduce the effective action space when doing RL, making it easier for the model to sample a successful rollout. For example, one useful skill for this task is traversing down a branch to a leaf node without hallucinating and then backtracking. Another is systematically exploring all branches one by one. That said, these are anthropomorphized descriptions; ultimately, what counts as a “skill” is determined by the RL optimization process.

Figure: Figure 6: (Left): Rewards obtained while training on an equal-proportion mixture of Deg-2-Path-5, Deg-5-Path-2, Deg-5-Path-5, and Deg-10-Path-10 using Dr.GRPO. During training, the model learns to solve all elements in the mixture, with rewards reaching $1.0$. (Right): Success rate on a held-out test set of Degree-10-Path-10 examples. The model trained on the mixture dataset begins solving the harder task.
Refer to caption: x9.png

## 6 Related work

Curriculum learning and data difficulty control: Recent work highlights the importance of curricula in developing reasoning abilities for large language models. Reasoning Gym (Stojanovski et al., 2025) introduces parameterized reasoning tasks of varying difficulty and shows that easy-to-hard training accelerates convergence. Building on this idea, E3 (Explore–Exploit–Extrapolate) (Setlur et al., 2025b) jointly varies task difficulty and token budgets to gradually expand in-context reasoning. WISDOM (Qiu et al., 2025) takes a similar approach by generating chain-of-thought data of increasing difficulty to expose models to progressively harder math problems, while SEC (Chen et al., 2025b) adapts problem selection using a multi-armed bandit based on the model’s learning progress. Together, these studies demonstrate that carefully controlling what data a model sees and when it sees it is a powerful mechanism for scaling reasoning in LLMs. However, they still assume that the base model begins with some initial level of capability.
Concurrent to us, Sun et al. (2025) employed a similar strategy to help base model escape the zero reward barrier.

Self-play and self-generated supervision:
Several methods leverage self-play or model-generated data to provide supervision in low-reward scenarios. Cheng et al. (2024) show that an adversarial two-player game played by copies of an LLM can improve its reasoning through RL on game outcomes. Wang et al. (2025) introduce a Critic-Discernment Game (CDG), in which a prover model is alternately challenged by helpful and misleading critics, training it to maintain correct answers despite adversarial feedback. More recently, methods such as Self-Questioning LMs (Chen et al., 2025a) allow models to generate their own subtasks and verifiers, creating a self-curriculum without relying on external datasets. These approaches highlight the use of self-play loops and self-generated supervision to bootstrap training when explicit reward signals are sparse or absent.

Reward shaping and credit assignment in sparse RL:
A complementary line of work addresses the sparse reward problem by shaping rewards or refining credit assignment. Classic methods such as Hindsight Experience Replay (Andrychowicz et al., 2017) demonstrate that relabeling failed trajectories as successes for alternate goals allows learning from episodes that would otherwise provide no signal. Building on this idea, recent approaches in LLM reasoning focus on step-level credit assignment, enabling models to extract useful learning signals even from failed trajectories. For example, VinePPO (Kazemnejad et al., 2024) uses Monte Carlo rollouts to compute step-level advantages, yielding stable improvements over vanilla PPO (Schulman et al., 2017), while Rewarding Progress (Setlur et al., 2025a) trains $Q$-functions to score intermediate reasoning steps based on their progress towards the final answer, substantially improving sample efficiency. OREAL (Lyu et al., 2025) takes an orthogonal approach by combining best-of-N outcome supervision (Chow et al., 2025) with token-level reward models to propagate credit to critical steps in long reasoning traces. These studies demonstrate that reward shaping and refined credit assignment can mitigate sparse feedback, yet they still assume the presence of some non-zero signal. By contrast, our work focuses on the zero-reward setting, where such techniques fail unless easier instances are provided to bootstrap learning (see Fig. [1](https://arxiv.org/html/2510.03971v1#S1.F1)).

## 7 Limitations and Future Work

Our analysis focuses on the graph search problem, and it remains an open question to what extent these findings generalize to more complex reasoning domains such as mathematical problem solving or code generation. While we employed a uniform mixture of task difficulties (see Fig. [6](https://arxiv.org/html/2510.03971v1#S5.F6)), exploring optimal weightings or curricula for easy versus hard tasks could further improve convergence. In addition, our approach relies on a non-zero success rate on simple problems to bootstrap learning. Addressing this cold-start challenge through self-play data generation or more robust pretraining is a promising direction for future work.

## 8 Conclusions

Our results highlight the critical role of data-centric strategies in RL for reasoning. Algorithmic improvements such as dense rewards, refined credit assignment, and diversity incentives fail when the base model has zero success rates on the task. In contrast, introducing easy instances consistently enables learning by providing a foothold from which the model can bootstrap toward more challenging tasks. We recommend that future evaluations include settings where base models initially fail, as success from these cold-start regimes offers a more robust measure of genuine progress in exploration and reasoning.

## 9 Acknowledgments

We thank Andrei Nicolicioiu, Anthony Chen, Neelabh Madan, Saksham Rastogi (pogs), Morgane M Moss, Daman Arora, Atharv Sonwane, Madhur Panwar, Aastha Jain and Omar Salemohamed for their valuable feedback on this paper. We also express our gratitude to Mila and NYU’s infrastructure team for providing the computing resources that made this project possible.

## References

- Andrychowicz et al. [2017]
Marcin Andrychowicz, Filip Wolski, Alex Ray, Jonas Schneider, Rachel Fong, Peter Welinder, Bob McGrew, Josh Tobin, OpenAI Pieter Abbeel, and Wojciech Zaremba.
Hindsight experience replay.
*Advances in neural information processing systems*, 30, 2017.
- Bachmann and Nagarajan [2024]
Gregor Bachmann and Vaishnavh Nagarajan.
The pitfalls of next-token prediction.
In Ruslan Salakhutdinov, Zico Kolter, Katherine Heller, Adrian Weller, Nuria Oliver, Jonathan Scarlett, and Felix Berkenkamp, editors, *Proceedings of the 41st International Conference on Machine Learning*, volume 235 of *Proceedings of Machine Learning Research*, pages 2296–2318. PMLR, 21–27 Jul 2024.
URL [https://proceedings.mlr.press/v235/bachmann24a.html](https://proceedings.mlr.press/v235/bachmann24a.html).
- Chen et al. [2025a]
Lili Chen, Mihir Prabhudesai, Katerina Fragkiadaki, Hao Liu, and Deepak Pathak.
Self-questioning language models.
*arXiv preprint arXiv:2508.03682*, 2025a.
- Chen et al. [2025b]
Xiaoyin Chen, Jiarui Lu, Minsu Kim, Dinghuai Zhang, Jian Tang, Alexandre Piché, Nicolas Gontier, Yoshua Bengio, and Ehsan Kamalloo.
Self-evolving curriculum for llm reasoning, 2025b.
URL [https://arxiv.org/abs/2505.14970](https://arxiv.org/abs/2505.14970).
- Cheng et al. [2024]
Pengyu Cheng, Yong Dai, Tianhao Hu, Han Xu, Zhisong Zhang, Lei Han, Nan Du, and Xiaolong Li.
Self-playing adversarial language game enhances llm reasoning.
In A. Globerson, L. Mackey, D. Belgrave, A. Fan, U. Paquet, J. Tomczak, and C. Zhang, editors, *Advances in Neural Information Processing Systems*, volume 37, pages 126515–126543. Curran Associates, Inc., 2024.
URL [https://proceedings.neurips.cc/paper_files/paper/2024/file/e4be7e9867ef163563f4a5e90cec478f-Paper-Conference.pdf](https://proceedings.neurips.cc/paper_files/paper/2024/file/e4be7e9867ef163563f4a5e90cec478f-Paper-Conference.pdf).
- Chow et al. [2025]
Yinlam Chow, Guy Tennenholtz, Izzeddin Gur, Vincent Zhuang, Bo Dai, Aviral Kumar, Rishabh Agarwal, Sridhar Thiagarajan, Craig Boutilier, and Aleksandra Faust.
Inference-aware fine-tuning for best-of-n sampling in large language models.
In *The Thirteenth International Conference on Learning Representations, ICLR 2025, Singapore, April 24-28, 2025*. OpenReview.net, 2025.
URL [https://openreview.net/forum?id=77gQUdQhE7](https://openreview.net/forum?id=77gQUdQhE7).
- Eysenbach [2025]
Benjamin Eysenbach.
Self-supervised reinforcement learning.
*Tutorial, https://ben-eysenbach.github.io/self-supervised-rl/*, 2025.
- Fawzi et al. [2022]
Alhussein Fawzi, Matej Balog, Aja Huang, Thomas Hubert, Bernardino Romera-Paredes, Mohammadamin Barekatain, Alexander Novikov, Francisco J R. Ruiz, Julian Schrittwieser, Grzegorz Swirszcz, et al.
Discovering faster matrix multiplication algorithms with reinforcement learning.
*Nature*, 610(7930):47–53, 2022.
- Gandhi et al. [2025]
Kanishk Gandhi, Ayush Chakravarthy, Anikait Singh, Nathan Lile, and Noah D. Goodman.
Cognitive behaviors that enable self-improving reasoners, or, four habits of highly effective stars, 2025.
URL [https://arxiv.org/abs/2503.01307](https://arxiv.org/abs/2503.01307).
- Guo et al. [2025]
Daya Guo, Dejian Yang, Haowei Zhang, Junxiao Song, Ruoyu Zhang, Runxin Xu, Qihao Zhu, Shirong Ma, Peiyi Wang, Xiao Bi, et al.
Deepseek-r1: Incentivizing reasoning capability in llms via reinforcement learning.
*arXiv preprint arXiv:2501.12948*, 2025.
- Kazemnejad et al. [2024]
Amirhossein Kazemnejad, Milad Aghajohari, Eva Portelance, Alessandro Sordoni, Siva Reddy, Aaron Courville, and Nicolas Le Roux.
Vineppo: Unlocking rl potential for llm reasoning through refined credit assignment, 2024.
URL [https://arxiv.org/abs/2410.01679](https://arxiv.org/abs/2410.01679).
- Liu et al. [2025]
Zichen Liu, Changyu Chen, Wenjun Li, Penghui Qi, Tianyu Pang, Chao Du, Wee Sun Lee, and Min Lin.
Understanding r1-zero-like training: A critical perspective.
In *Conference on Language Modeling (COLM)*, 2025.
- Lyu et al. [2025]
Chengqi Lyu, Songyang Gao, Yuzhe Gu, Wenwei Zhang, Jianfei Gao, Kuikun Liu, Ziyi Wang, Shuaibin Li, Qian Zhao, Haian Huang, et al.
Exploring the limit of outcome reward for learning mathematical reasoning.
*arXiv preprint arXiv:2502.06781*, 2025.
- Putta et al. [2024]
Pranav Putta, Edmund Mills, Naman Garg, Sumeet Motwani, Chelsea Finn, Divyansh Garg, and Rafael Rafailov.
Agent q: Advanced reasoning and learning for autonomous ai agents.
*arXiv preprint arXiv:2408.07199*, 2024.
- Qiu et al. [2025]
Chenhao Qiu, Qianglong Chen, Jintang Li, Caiyu Wang, Runsen Hua, Minghui Li, Shengshan Hu, and Yechao Zhang.
WISDOM: Progressive curriculum synthesis makes LLMs better mathematical reasoner, 2025.
URL [https://openreview.net/forum?id=hFFAg5Dmw9](https://openreview.net/forum?id=hFFAg5Dmw9).
- Qu et al. [2025]
Yuxiao Qu, Matthew YR Yang, Amrith Setlur, Lewis Tunstall, Edward Emanuel Beeching, Ruslan Salakhutdinov, and Aviral Kumar.
Optimizing test-time compute via meta reinforcement fine-tuning.
*arXiv preprint arXiv:2503.07572*, 2025.
- Schulman et al. [2017]
John Schulman, Filip Wolski, Prafulla Dhariwal, Alec Radford, and Oleg Klimov.
Proximal policy optimization algorithms.
*arXiv preprint arXiv:1707.06347*, 2017.
- Setlur et al. [2025a]
Amrith Setlur, Chirag Nagpal, Adam Fisch, Xinyang Geng, Jacob Eisenstein, Rishabh Agarwal, Alekh Agarwal, Jonathan Berant, and Aviral Kumar.
Rewarding progress: Scaling automated process verifiers for LLM reasoning.
In *The Thirteenth International Conference on Learning Representations, ICLR 2025, Singapore, April 24-28, 2025*. OpenReview.net, 2025a.
URL [https://openreview.net/forum?id=A6Y7AqlzLW](https://openreview.net/forum?id=A6Y7AqlzLW).
- Setlur et al. [2025b]
Amrith Setlur, Matthew YR Yang, Charlie Snell, Jeremy Greer, Ian Wu, Virginia Smith, Max Simchowitz, and Aviral Kumar.
e3: Learning to explore enables extrapolation of test-time compute for llms.
*arXiv preprint arXiv:2506.09026*, 2025b.
- Shao et al. [2024]
Zhihong Shao, Peiyi Wang, Qihao Zhu, Runxin Xu, Junxiao Song, Xiao Bi, Haowei Zhang, Mingchuan Zhang, YK Li, Yang Wu, et al.
Deepseekmath: Pushing the limits of mathematical reasoning in open language models.
*arXiv preprint arXiv:2402.03300*, 2024.
- Stojanovski et al. [2025]
Zafir Stojanovski, Oliver Stanley, Joe Sharratt, Richard Jones, Abdulhakeem Adefioye, Jean Kaddour, and Andreas Köpf.
Reasoning gym: Reasoning environments for reinforcement learning with verifiable rewards, 2025.
URL [https://arxiv.org/abs/2505.24760](https://arxiv.org/abs/2505.24760).
- Sun et al. [2025]
Yiyou Sun, Yuhan Cao, Pohao Huang, Haoyue Bai, Hannaneh Hajishirzi, Nouha Dziri, and Dawn Song.
Delta-code: How does rl unlock and transfer new programming algorithms in llms?, 2025.
URL [https://arxiv.org/abs/2509.21016](https://arxiv.org/abs/2509.21016).
- Wang et al. [2025]
Pinzheng Wang, Juntao Li, Zecheng Tang, Haijia Gui, and Min zhang.
Improving rationality in the reasoning process of language models through self-playing game.
In *Forty-second International Conference on Machine Learning*, 2025.
URL [https://openreview.net/forum?id=PPsiS5nSlv](https://openreview.net/forum?id=PPsiS5nSlv).
- Williams [1992]
Ronald J. Williams.
Simple statistical gradient-following algorithms for connectionist reinforcement learning.
*Mach. Learn.*, 8(3–4):229–256, May 1992.
ISSN 0885-6125.
doi: 10.1007/BF00992696.
URL [https://doi.org/10.1007/BF00992696](https://doi.org/10.1007/BF00992696).
- Yue et al. [2025]
Yang Yue, Zhiqi Chen, Rui Lu, Andrew Zhao, Zhaokai Wang, Shiji Song, and Gao Huang.
Does reinforcement learning really incentivize reasoning capacity in llms beyond the base model?
*arXiv preprint arXiv:2504.13837*, 2025.

## Appendix A Baseline Implementation Details

In this section, we provide background on reinforcement learning (RL) for large language models (LLMs) and describe the objective that different baselines optimize.

### A.1 RL for LLMs

Let $\pi_{\theta}(a\mid s)$ denote a policy parameterized by $\theta$, which defines the probability of taking action $a$ in state $s$. A trajectory of length $T$ is denoted by $\tau=(s_{0},a_{0},s_{1},a_{1},\dots,s_{T},a_{T})$, and the total reward of a trajectory is $R(\tau)$. In the context of language models, the initial state $s_{0}$ corresponds to the input question, actions correspond to generated tokens, and subsequent states represent the question along with the partial sequence of answer tokens.

RL training using Reinforce [Williams, 1992] optimizes the following objective:

$$ $\displaystyle\theta^{*}=\text{argmax}_{\theta}~\mathbb{E}_{x\sim\mathcal{D}}~\mathbb{E}_{y\sim\pi_{\theta}(.\mid x)}R(x,y)$ (1) $$

Here, $x$ is a question sampled from the distribution of questions $\mathcal{D}$, $y$ is a response sampled from the LLM $\pi_{\theta}(.\mid x)$, and $R(x,y)$ is the reward for generating response $y$ to question $x$. In our graph search setting, we prompt the LLM to output its final answer inside \boxed{}, so the reward function simply extracts the string in \boxed{} and compares it to the true path.

### A.2 Dr. GRPO [Liu et al., 2025 ]

The objective in Equation [1](https://arxiv.org/html/2510.03971v1#A1.E1) typically exhibits high variance. To reduce this variance, recent methods such as GRPO [Shao et al., 2024] Dr. GRPO [Liu et al., 2025] subtract a baseline from the reward, which is computed by generating multiple rollouts for a given question and taking the average reward. In our setting, we perform on-policy training; thus, the importance ratio and advantage clipping terms in the objective from equation 3 in [Liu et al., 2025] vanish, resulting in the following final objective:

$$ $\displaystyle\nabla_{\theta}\mathcal{J}(\theta)=\mathbb{E}_{x\sim\mathcal{D},\{y_{i}\}_{i=1}^{G}\sim\pi_{\theta}(.\mid x)}\frac{1}{G}\sum_{i=1}^{G}\sum_{t=1}^{|y_{i}|}\hat{A}_{i,t}\nabla_{\theta}\log\pi_{\theta}(y_{i,t}\mid y_{i,<t})-\beta~\mathbb{D}_{\text{KL}}(\pi_{\theta}||\pi_{\text{ref}})$ (2) $$

where $\hat{A}_{i,t}$ is computed as $R(x,y_{i})-\frac{1}{G}\sum_{j=1}^{j=G}R(x,y_{j})$. We set $G=5$ for all our experiments.

Intuitively, the objective increases the likelihood of tokens that lead to positive outcomes and decreases the likelihood of tokens that do not. Note that this loss formulation weights all steps in the reasoning chain equally, i.e., $\hat{A}_{i,t}$ is independent of $t$.

### A.3 VinePPO [Kazemnejad et al., 2024 ]

Methods like GRPO and Dr. GRPO weigh all tokens in a reasoning chain equally. However, this may not be optimal, as not all steps in a reasoning chain contribute equally to solving a problem. For example, identifying lemmas to use in proving a theorem may be more important than generating tokens that are included merely for grammatical correctness. VinePPO addresses this problem by performing credit assignment to weigh more important steps higher and less important steps lower. It does so by computing step level advantages instead of trajectory level advantages.

Given a question $x\sim\mathcal{D}$, and a reasoning chain $y\sim\pi_{\theta}(.\mid x)$, VinePPO divides the reasoning chain $y$ into steps or chunks $y_{c_{1}},y_{c_{2}}\ldots y_{c_{n}}$, and finally the gradient of the objective is computed as

$$ $\displaystyle\nabla_{\theta}\mathcal{J}(\theta)=\sum_{i=1}^{n}\hat{A}^{\pi_{\theta}}_{y_{c_{i}}}\sum_{t=s_{c_{i}}}^{e_{c_{i}}}\,\nabla_{\theta}\log\pi_{\theta}\!\big(y_{t}\mid y_{<t},x\big)$ (3) $$

where $\hat{A}^{\pi_{\theta}}_{y_{c_{i}}}$ denotes the advantage of step $y_{c_{i}}$, with $s_{c_{i}}$ and $e_{c_{i}}$ representing the start and end indices of the $i^{\text{th}}$ chunk, respectively. The advantage at each step is estimated using Monte Carlo rollouts from the state before and after that step. In other words, given a trajectory $y=y_{c_{1}}\oplus y_{c_{2}}\oplus\ldots\oplus y_{c_{n}}$ where $\oplus$ denotes the concatenation operation $\hat{A}^{\pi_{\theta}}_{y_{c_{i}}}$ is computed as follows:

$$ $\displaystyle\hat{A}^{\pi_{\theta}}_{y_{c_{i}}}=V^{\pi_{\theta}}(\oplus_{j=1}^{j=i}y_{j})-V^{\pi_{\theta}}(\oplus_{j=1}^{j=i-1}y_{j})$ (4) $$

where $V^{\pi_{\theta}}(s)$ is computed by taking the average reward recieved from $K$ Monte Carlo rollouts. In our experiments we set $K=3$. Note that we omit the KL penalty term from Equation [3](https://arxiv.org/html/2510.03971v1#A1.E3) for the sake of simplicity. For VinePPO, we use the code released by the authors [here](https://github.com/McGill-NLP/nano-aha-moment/).

### A.4 Progress Rewards [Setlur et al., 2025a ]

Like the VinePPO objective in Equation [3](https://arxiv.org/html/2510.03971v1#A1.E3), progress rewards also aim to compute step-level advantages. However, their objective differs from VinePPO in two key ways: (i) they estimate the advantages in Equation [4](https://arxiv.org/html/2510.03971v1#A1.E4) under a policy different from the one being optimized, which they refer to as the prover policy, and (ii) combine the step-level advantages with the trajectory-level reward to form the final objective:

$$ $\displaystyle\nabla_{\theta}\mathcal{J}(\theta)=\sum_{i=1}^{n}(R(y)+\alpha\cdot\hat{A}^{\mu}_{y_{c_{i}}})\sum_{t=s_{c_{i}}}^{e_{c_{i}}}\,\nabla_{\theta}\log\pi_{\theta}\!\big(y_{t}\mid y_{<t},x\big)$ (5) $$

where $\mu$ is $\texttt{Best-of-4}(\pi_{\text{ref}})$. Similar to equation [4](https://arxiv.org/html/2510.03971v1#A1.E4) they compute step advantages under the prover policy $\mu$ as:

$$ $\displaystyle\hat{A}^{\mu}_{y_{c_{i}}}=V^{\mu}(\oplus_{j=1}^{j=i}y_{j})-V^{\mu}(\oplus_{j=1}^{j=i-1}y_{j})$ (6) $$

In their work, a neural network is trained to approximate $V^{\pi_{\text{ref}}}(s)$ by collecting a dataset of reasoning trajectories sampled from $\pi_{\text{ref}}$. For simplicity, we instead rely on rollouts to compute $V^{\pi_{\text{ref}}}(s)$. With this, we optimize the following objective:

$$ $\displaystyle\nabla_{\theta}\mathcal{J}(\theta)=\sum_{i=1}^{n}(\hat{A}(y)+\alpha\cdot\hat{A}^{\mu}({y_{c_{i}}}))\sum_{t=s_{c_{i}}}^{e_{c_{i}}}\nabla_{\theta}\log\pi_{\theta}\big(y_{t}\mid y_{<t},x\big)$ (7) $$

Notice the change from Equation [5](https://arxiv.org/html/2510.03971v1#A1.E5), where we replace $R(y)$ with $\hat{A}(y)$. We make this substitution because we operate in a group-style setting with access to multiple rollouts for a question. Using $\hat{A}(y)$ instead of $R(y)$ yields a lower-variance estimate of the gradient. $\hat{A}(y)$ is computed as $(R(y)-\text{average reward over $G$ rollouts})$.

### A.5 Best-of-N Finetuning [Chow et al., 2025 ]

Chow et al. [2025] introduce inference-aware fine-tuning that explicitly optimizes for BoN performance. The hope is optimizing for BoN performance could result in the model sampling diverse responses.
A key result is Lemma 3, which provides a BoN-aware policy gradient estimator under binary rewards.
By introducing asymmetric weighting functions that depend on the probability of failure, the method upweights correct predictions on hard inputs while redistributing mass away from unreliable outputs.

Assuming the reward $R(x,y)\in\{0,1\}$. Then the gradient of the BoN-aware RL objective (Equation 6) with respect to the model parameters $\theta$ is

$$ $\mathbb{E}_{x\sim D}\!\left[\mathbb{E}_{y\sim\pi_{\mathrm{bon},R=1}}\!\left[\nabla_{\theta}\log\pi_{\theta}(y\mid x)\right]\,g^{+}_{N}\!\bigl(P_{\mathrm{fail}}(x)\bigr)-\mathbb{E}_{y\sim\pi_{\mathrm{bon},R=0}}\!\left[\nabla_{\theta}\log\pi_{\theta}(y\mid x)\right]\,g^{-}_{N}\!\bigl(P_{\mathrm{fail}}(x)\bigr)\right],$ (8) $$

where the sample-dependent weights are

$$ $g^{+}_{N}(p)=\frac{N\,p^{\,N-1}}{1-p^{N}},\qquad g^{-}_{N}(p)=\frac{N\,(1-p^{\,N-1})}{1-p^{N}}.$ $$

## Appendix B Hyperparameters

Table [1](https://arxiv.org/html/2510.03971v1#A2.T1) lists the hyperparameters that are common across all methods. Since we do on-policy training parameters such as the clipping ratio ($\epsilon$) and ppo-epochs are not applicable.

**Table 1: Common hyper-parameters used in our experiments.**
| Hyperparameter | Value |
| --- | --- |
| Learning Rate | $1\times 10^{-6}$ |
| Effective Batch Size | $32$ |
| Number of rollouts per data point | $5$ |
| Max Prompt Length | $1024$ |
| Max Response Length | $4096$ |
| KL Coefficient ($\beta$) | $1\times 10^{-3}$ |
| Temperature | 0.6 |
| Top p | 0.999 |
| Micro Batch Size | 4 |
| Discount Factor ($\gamma$) | 1 |
| Base Model | Qwen2.5/Qwen-1.5B-Instruct |

### B.1 VinePPO

We estimate the value of an intermediate state, $V^{\pi_{\theta}}(s)$, using three rollouts from the current policy.

### B.2 Rewarding Progress

We estimate the value of an intermediate state, $V^{\pi_{\text{ref}}}(s)$, using three rollouts from the reference policy. The parameter $\alpha$ in Equation [7](https://arxiv.org/html/2510.03971v1#A1.E7) is set to 5, following the recommendation in Setlur et al. [2025a].

### B.3 Best-of-N Aware Finetuning

For $N$ used in Best-of-N, we use $N=8$. We clip the sample dependent weights to $[-3,3]$. We decay the KL coefficient from 0.1 to 0.001.

## Appendix C Prompts

For our experiments, we prompt the Qwen2.5/Qwen-1.5B-Instruct model in the following manner

During training, the string inside \boxed{} is extracted and compared against the ground truth path to assign the reward.

## Appendix D Additional Results

Easier versions of the task are solvable: To rule out any implementation issues and verify that the graph search task is not inherently unsolvable, we experiment with simpler variants of the task, such as the Degree-3-Path-3 and Degree-5-Path-5 graphs. As shown in Figs. [7(a)](https://arxiv.org/html/2510.03971v1#A4.F7.sf1) and [7(b)](https://arxiv.org/html/2510.03971v1#A4.F7.sf2), RL training using outcome rewards is effective on these simpler variants, but remains ineffective on the harder Degree-10-Path-10 dataset.

Figure: (a) Rewards obtained during training Dr.GRPO on the graph search task with varying levels of difficulty.
Refer to caption: x11.png

## Peer Reviews

confidence: 3
contribution: 1
initial_rating: 2
presentation: 2
questions: 1. How many "easy" examples are required to bootstrap learning? Can we use just a small amount and sample them with a higher frequency to kickstart learning?

2. Can the need for "easy" examples be avoided by providing some teacher-based exploration? E.g. use the answer/output from a stronger model/human when early in training.
soundness: 2
strengths: * The identified problem is an important (if well-known) one. This failure mode of RL is especially important in the context of LLM training and the increasing application of them towards difficult tasks. While I think this paper would benefit from improved and more thorough analysis, it doesn't change the fact that the problem itself is important to the community.

* The discussion on why existing methods fail in the sparse reward setting are helpful (Sec. 4). While some of these failure modes are somewhat obvious, the exploration of the prover for Progress Rewards and degeneracy in Best-of-N provide some nice insights.

* Clean implementations of methods are always greatly appreciated for the sake of reproducibility, and the community would benefit from the ones put forward here.
summary: This paper explores the "zero reward barrier" in reinforcement learning with LLMs. This occurs when the model is incapable of generating outputs that yield non-zero rewards, thus has no meaningful gradient for updating the policy. The paper proposes a simple curriculum-style solution: inject easier problems to the training set. This is studied in the context of a graph search problem, and performance is compared to baseline approaches.
weaknesses: * At risk of being overly reductive, this just seems like a curriculum. The idea that a lack of meaningful rewards complicates learning (which is especially common in sparse reward settings) has long been known in reinforcement learning. There are many common approaches to help mitigate this: curriculum, intelligent exploration, transfer learning, reward shaping, prioritized/hindsight experience (if off policy) etc. While some of these are indeed mentioned in the paper itself, it doesn't change the fact that this isn't by any means a novel finding in the context of RL. This is particularly apparent in Sec. 5.3, as this reasoning is exactly the purpose behind developing a training curriculum (as well as other replay-based techniques).

* The above issue isn't necessarily a fatal flaw in the paper if there is a suitably rigorous analysis with interesting findings. And while I do appreciate the analysis of existing technqiues in Sec. 4, ultimately it is applied only to a graph search problem and a single LLM (Qwen 2.5 1.5B). While I agree that this is a useful problem, it does mean that the curriculum that is being implicitly introduced is only studied in the context of one problem and one model.

* I like the discussion on what is the "right" difficulty of curriculum, e.g. what samples should be chosen (5.1/5.2). This has always been a challenging problem in curriculum design in RL and I think it is very useful to explore in the context of LLM training. However, there is no satisfying answer to this problem in the paper other than simply adding samples of all difficulties, which makes it difficult to apply more broadly to other tasks.

---

confidence: 4
contribution: 2
initial_rating: 2
presentation: 2
questions: 1. Why did the authors only single task?
2. Curious to know what authors think when the model size is larger and if the claims still hold. 
3. Why did the authors only consider single model in this paper to validate the claims?
soundness: 2
strengths: All baselines flatline at zero success on Deg-10-P10, and the paper convincingly rules out trivial explanations by showing Deg-3-P3 is solvable.It offers a simple fix: include easier instances (Deg-5-P5) or mix difficulties, which reliably unlocks learning under outcome rewards. They explain why step-credit still gives no signal when success=0 and why BoN is unstable without strong KL/clipping.
summary: Paper studies the “zero-reward barrier” in RL post-training for LLMs: when a base model never samples a correct answer, outcome-based RL stalls. Using a controllable graph search task (Degree-10-Path-10), the authors evaluate Dr.GRPO, VinePPO, Rewarding Progress, and BoN-aware finetuning and report persistent zero success.

Core result: a data-centric fix—mixing in easier instances (not too easy) enables learning on the hard task without changing the RL algorithm; equal-mixing all difficulties also works.
weaknesses: 1. The paper focuses on a single controllable toy task. While that’s fine for isolating dynamics, I’d expect the core insight (“mix difficulties to break zero-reward stalls”) to be validated on more realistic benchmarks. There are no results on real-world-style tasks, so external validity is unclear.
2. Running everything on one small, single family/model caps the claim. The zero-reward barrier and the benefit of mixing difficulties likely depend on base competence and instruction-tuning/tokenizer quirks; a larger Qwen or a different family (e.g., Llama/Mistral) might start with non-zero success on the hard split, changing both learning curves and the size of the effect.

---

confidence: 5
contribution: 2
initial_rating: 2
presentation: 2
questions: What happens if the number of rollouts or compute budget is scaled up by one or two orders of magnitude? Does performance improve at all?

Could the authors test smaller or simpler tasks (e.g., lower degree/path length) to see when learning actually starts?

Can they design a dynamic curriculum that adjusts difficulty automatically instead of fixing ratios?

How do classical RL baselines and other coldstart RL algorithms perform on the same environment? Without comparison, it is unclear whether the task itself is solvable.
soundness: 1
strengths: The paper tackles an ambitious question about combining LLMs and RL, which is of high interest to the community.

The authors show enthusiasm in connecting classical RL problems to language-based reasoning, and the overall motivation is understandable.
summary: The paper explores whether large language models can perform reinforcement learning (RL) style reasoning in a synthetic sparse-reward environment.
The authors design a graph-search task (“Degree-10-Path-10”) and train the LLM through policy-gradient updates using only a few sampled completions per input.
They claim that the failure of training indicates the fundamental infeasibility of applying RL to LLMs for complex reasoning and their curriculum training can solve it.
weaknesses: 1) Insufficient exploration and unrealistic sampling setup.

The experiments rely on only a few rollouts per data point (five completions), under a completely sparse 0/1 reward.
This setup guarantees that almost no successful trajectories are ever observed, so gradients vanish and training fails by design.
The paper then interprets this trivial failure as a general limitation of LLMs, which is misleading.
RL methods typically require thousands to millions of rollouts for such problems; the present configuration is not a valid test of feasibility.

2) Compute–task imbalance.

The graph-search problem (Degree-10-Path-10) explodes combinatorially in difficulty, but the compute and sample budgets remain fixed and minimal.
The failure is thus compute-bound rather than method-bound.
No scaling study is provided to show where learning begins to succeed or how the outcome changes with more computation.
The conclusion that “RL cannot work for LLMs” is not supported without such evidence.

3) Superficial notion of curriculum learning.

The “curriculum” is a manually mixed dataset of easy and hard samples at a fixed ratio.
It is static, non-adaptive, and not connected to the model’s learning progress.
This is better described as data filtering, not curriculum learning.
In modern RL, curricula are dynamic and algorithmic—tasks or rewards evolve based on the agent’s competence.
The paper misses this key distinction and offers no analysis of why or when their fixed mixture helps.
Moreover, the current setup risks overfitting to “easy” samples and does not test generalization to unseen or multi-solution cases.
The authors also have no idea about the works of the meta-learning and curriculum learning community from RL.
I would expect more holistic solutions rather than simply picking samples. 
When the algorithm try more reasoning tasks, do you also manually give easier samples?  

4) Missing comparisons and baselines.

No results from standard RL algorithms are shown for the same environment.
Without knowing that a baseline agent can solve the task, the “failure” of the LLM provides little information.
The paper also lacks ablations on rollout number, reward shaping, or task scaling.

5) Overstated conclusions.

The authors generalize their negative results to claim that RL on LLMs is infeasible, but the evidence only shows that the current configuration is under-explored and under-resourced.
The conclusions are therefore not justified by the experiments.

6) Clarity and structure issues.

The writing is fragmented, with vague definitions, missing implementation details, and inconsistent terminology (e.g., “rollout,” “curriculum,” “episode”).
The overall presentation makes it difficult to follow the core argument.

---

confidence: 3
contribution: 3
initial_rating: 4
presentation: 2
questions: n/a
soundness: 3
strengths: The strengths of the work are as follows.
- First, the zero-reward barrier is a fundamental challenge limiting RL scalability for LLMs.
- Second, the authors implement and rigorously test multiple recent methods specifically designed for sparse rewards. 
- Third, there is a thorough failure mode analysis on dense rewards.
- Finally, the work is reproducible and the authors provide complete code.
summary: This work investigates the zero-reward barrier in reinforcement learning for large language models. These are scenarios where the base model cannot generate any correct solutions during training, causing learning to stall. Using a graph search task from Bachmann and Nagarajan (2024), the authors evaluate recent RL methods designed for sparse rewards: VinePPO (credit assignment), Rewarding Progress (reward shaping), and Best-of-N aware finetuning (diversity incentives). The authors implement baselines (providing code) and provide detailed failure analyses. They release their implementations to support further research.

The strengths of the work are as follows. First, the zero-reward barrier is a fundamental challenge limiting RL scalability for LLMs. Second, the authors implement and rigorously test multiple recent methods specifically designed for sparse rewards. Third, there is a thorough failure mode analysis on dense rewards. Finally, the work is reproducible and the authors provide complete code.

The weaknesses of the work are as follows. First, there is a limited task diversity since the work only focuses on graph search tasks. It would be great to see some analysis on if this transfers to math, coding, etc. Second, there is only experiments on a 1.5B model. It would be great to see larger models, to see if the trend holds. Finally, some improvements to presentation (e.g. graph readability) could be made in the paper, spacing.
weaknesses: The weaknesses of the work are as follows.
- First, there is a limited task diversity since the work only focuses on graph search tasks. It would be great to see some analysis on if this transfers to math, coding, etc.
- Second, there is only experiments on a 1.5B model. It would be great to see larger models, to see if the trend holds.
- Finally, some improvements to presentation (e.g. graph readability) could be made in the paper, spacing.