Search papers, labs, and topics across Lattice.
This paper develops a theoretical understanding of the training dynamics of Reinforcement Learning with Verifiable Rewards (RLVR) for transformers on compositional reasoning tasks, focusing on how it overcomes the long-horizon barrier. It shows that the smoothness of the difficulty spectrum in the training data governs RLVR's effectiveness, with abrupt difficulty discontinuities leading to grokking-type phase transitions and prolonged plateaus. Conversely, a smooth difficulty spectrum enables a relay effect where easier problems facilitate learning harder ones, resulting in continuous improvement.
RLVR's success in long-horizon reasoning hinges on a smooth difficulty spectrum, where mastering easier sub-problems unlocks the ability to tackle harder ones, avoiding frustrating grokking plateaus.
Reinforcement learning with verifiable rewards (RLVR) has been a main driver of recent breakthroughs in large reasoning models. Yet it remains a mystery how rewards based solely on final outcomes can help overcome the long-horizon barrier to extended reasoning. To understand this, we develop a theory of the training dynamics of RL for transformers on compositional reasoning tasks. Our theory characterizes how the effectiveness of RLVR is governed by the smoothness of the difficulty spectrum. When data contains abrupt discontinuities in difficulty, learning undergoes grokking-type phase transitions, producing prolonged plateaus before progress recurs. In contrast, a smooth difficulty spectrum leads to a relay effect: persistent gradient signals on easier problems elevate the model's capabilities to the point where harder ones become tractable, resulting in steady and continuous improvement. Our theory explains how RLVR can improve performance at the edge of competence, and suggests that appropriately designed data mixtures can yield scalable gains. As a technical contribution, our analysis develops and adapts tools from Fourier analysis on finite groups to our setting. We validate the predicted mechanisms empirically via synthetic experiments.
CMU ML