aiqbench analysis
This research demonstrates that Transformers can spontaneously develop Chain-of-Thought reasoning through outcome-based reinforcement learning, provided the training distribution includes sufficient mass on simpler examples. Theoretically, policy gradient dynamics drive the model to converge on structured, interpretable algorithms for tasks requiring iterative steps, a finding validated across both synthetic and real-world mathematical reasoning benchmarks. For practitioners, this highlights that sparse rewards alone are insufficient; the data distribution must explicitly support the emergence of generalizable reasoning strategies to avoid infeasible learning dynamics.
Outcome-Based RL Provably Leads Transformers to Reason, but Only With the Right Data
arXiv:2601.15158v4 Announce Type: replace Abstract: Transformers trained via Reinforcement Learning (RL) with outcome-based supervision can spontaneously develop the ability to generate intermediate reasoning steps (Chain-of-Thought). Yet the mechanism by which sparse rewards drive policy gradient to discover such systematic reasoning remains poorly understood. We address this by analyzing the policy gradient dynamics of single-layer Transformers on a synthetic graph traversal task that cannot be solved without Chain-of-Thought but admits a simple iterative solution. We prove that despite training solely on final-answer correctness, policy gradient drives the Transformer to converge to a structured, interpretable algorithm that iteratively traverses the graph vertex-by-vertex. We characterize the distributional properties required for this emergence, identifying the critical role of "simple examples": instances requiring fewer reasoning steps. When the training distribution places sufficient mass on these simpler examples, the Transformer learns a generalizable traversal strategy that extrapolates to longer chains; when this mass vanishes, policy gradient learning becomes infeasible. We corroborate our theoretical results through experiments on synthetic data and with real-world language models on mathematical reasoning tasks, validating that our theoretical findings carry over to practical settings.
Abstract:Transformers trained via Reinforcement Learning (RL) with outcome-based supervision can spontaneously develop the ability to generate intermediate reasoning steps (Chain-of-Thought). Yet the mechanism by which sparse rewards drive policy gradient to discover such systematic reasoning remains poorly understood. We address this by analyzing the policy gradient dynamics of single-layer Transformers on a synthetic graph traversal task that cannot be solved without Chain-of-Thought but admits a simple iterative solution. We prove that despite training solely on final-answer correctness, policy gradient drives the Transformer to converge to a structured, interpretable algorithm that iteratively traverses the graph vertex-by-vertex. We characterize the distributional properties required for this emergence, identifying the critical role of "simple examples": instances requiring fewer reasoning steps. When the training distribution places sufficient mass on these simpler examples, the Transformer learns a generalizable traversal strategy that extrapolates to longer chains; when this mass vanishes, policy gradient learning becomes infeasible. We corroborate our theoretical results through experiments on synthetic data and with real-world language models on mathematical reasoning tasks, validating that our theoretical findings carry over to practical settings.
Machine Learning (cs.LG); Artificial Intelligence (cs.AI)
arXiv:2601.15158 [cs.LG]
(or arXiv:2601.15158v4 [cs.LG] for this version)
Full text under the publisher's open licence · 191 words
Related coverage
The Entangled Dimensions of Decision Theory
LessWrong · Jul 30, 2026
Lattice-Based Cryptography Explained
Quantum Zeitgeist · Aug 15, 2026
When are safe Pareto improvements individually rational?
LessWrong · Oct 13, 2026
An unexamined cause of the OpenAI Hugging Face hacking incident: its binary performance metric
LessWrong · Sep 23, 2026