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

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. 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.