Title: Outcome-Based RL Provably Leads Transformers to Reason, but Only With the Right Data

Abstract: While Reinforcement Learning (RL) with outcome-based supervision has been shown to enable Transformers to spontaneously generate intermediate reasoning steps (Chain-of-Thought), the precise mechanism by which sparse rewards guide policy gradients to uncover such systematic reasoning remains unclear. To resolve this, we examine the policy gradient dynamics of single-layer Transformers applied to a synthetic graph traversal task. This task is unsolvable without Chain-of-Thought but allows for a straightforward iterative solution. We demonstrate that training exclusively on final-answer accuracy causes the policy gradient to drive the Transformer toward a structured, interpretable algorithm that traverses the graph vertex by vertex. Our analysis identifies specific distributional properties necessary for this emergence, highlighting the pivotal importance of "simple examples"—instances that demand fewer reasoning steps. If the training distribution assigns adequate probability mass to these simpler cases, the Transformer acquires a generalizable traversal strategy capable of extrapolating to longer chains. Conversely, if this mass disappears, policy gradient learning fails. We support these theoretical insights with experiments on synthetic datasets and with real-world language models on mathematical reasoning tasks, confirming that our findings are applicable to practical scenarios.

Source: arXiv Generated at: 2026-06-04 00:00:00 UTC