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 gradient descent to discover such systematic reasoning remains poorly understood. We address this by analyzing the gradient flow dynamics of single-layer Transformers on a synthetic graph traversal task that cannot be solved without Chain-of-Thought (CoT) but admits a simple iterative solution. We prove that despite training solely on final-answer correctness, gradient flow drives the model 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 instances, the model learns a generalizable traversal strategy that extrapolates to longer chains; when this mass vanishes, gradient-based 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 (translated)
通过强化学习（RL）并基于结果进行监督训练的Transformers可以自发地发展生成中间推理步骤的能力（Chain-of-Thought）。然而，稀疏奖励如何驱动梯度下降以发现这种系统性推理机制仍然不清楚。我们通过分析单层Transformer在合成图遍历任务中的梯度流动动态来解决这个问题，该任务无法仅凭直觉解决但允许简单的迭代解决方案。 我们证明了尽管训练中只关注最终答案的准确性，梯度流动仍能驱动模型收敛到一种结构化且可解释的算法上，这种算法能够逐节点地遍历图。我们还描述了这一现象出现所需的分布特性，并确定“简单示例”的关键作用：那些需要较少推理步骤的例子。当训练数据集中足够多的是这些简单的例子时，模型会学习出一种泛化的遍历策略并能推广到更长的链路上；而如果这种简单的实例在数据集中的比例下降，基于梯度的学习就变得不可行。 我们通过合成数据上的实验以及对现实世界语言模型在数学推理任务上的研究来验证我们的理论结果，并且证实了这些发现能够应用于实际场景中。
URL
https://arxiv.org/abs/2601.15158
