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 linear 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.
Figures & tables
Figure 1: Illustration of the chain identification task. The input contains edges forming two disjoint chains Ca=(a1,…,an) and Cb=(b1,…,bn) , and a starting vertex vstart (here ak ). The task is to identify the terminal vertex of the chain containing vstart (here an ).
Real-World Pre-Training
Synthetic Pre-Training
Training Dist.
Test Acc. ( Hard- 15 )
Training Dist.
Test Acc. ( Hard- 20 )
Hard- 15
52.9%
Hard- 20
43.15%
Mixed- 15
96.2%
Mixed- 20
84.77%
Mixed- 10
91.6%
Mixed- 17
78.68%
Table 1: Test accuracy on Hard- n under various post-training distributions, in two real-world post-training experiments on a mathematical reasoning task ( Section 6.1 ). Left: real-world pre-training using Qwen2.5-3B-Instruct and n=15 . Right: synthetic pre-training using a model pre-trained on chain-of-thought traces of simpler instances [ 73 ] and n=20 . Full details in Section I.2 .
Appendix figures & tables6 assets
Supplementary material from the paper’s appendix.
Appendix
Chain size n
Test Acc.
Chain Trav.
4
100%
100%
8
100%
99.3%
12
99.3%
94.2%
Appendix
Table 2: In line with our theory ( Section 5 ), on the chain identification task ( Section 3 ), a Transformer trained with simple examples achieves high accuracy through the efficient chain traversal (reasoning) algorithm, thereby demonstrating an implicit bias towards efficiency ( Section 4 ). In this table, “Test Acc.” and “Chain Trav.” refer to the fraction of test examples that are solved accurately and using the chain traversal algorithm, respectively. For further details on this experiment see Sections I.1.1 and I.1.4 .
Figure 2: In line with our theory ( Section 5 ), on the chain identification task ( Section 3 ), the accuracy of a Transformer on complex test examples is higher when its training data includes simple examples, despite such simple examples inducing a distribution shift. This figure shows the accuracy on complex test examples throughout training, for different training data distributions: ones entailing only complex examples (small k ), and ones entailing a mix of complex and simple examples (large k ). For further details on this experiment see Sections I.1.3 and I.1.4 .
Hyperparameter
Value
RL algorithm
GRPO
KL coefficient β
10−4
Generations per prompt
8
Sampling temperature (training)
0.9
Max completion length (training)
1,024 tokens
Max prompt length (training)
512 tokens
Appendix
Table 3: Hyperparameters used for fine-tuning Qwen2.5-3B-Instruct and Llama-3.2-3B-Instruct on the equations-reasoning task.
Figure 4: Training curves in the real-world pre-training setting. In both panels, the model is evaluated on 15 -Hard while being post-trained either on 15 -Mixed (blue) or 15 -Hard (red).
Training Distribution
Test Acc. ( Hard- 15 )
Hard- 15
50.2%
Mixed- 15
99.3%
Mixed- 10
98.6%
Appendix
Table 4: Same setting as the real-world pre-training experiment in Table 1 , but using Llama-3.2-3B-Instruct as the real-world pre-trained base model. “Test Acc.” is the fraction of 15 -Hard test examples solved correctly.
Real-World Pre-Training
Synthetic Pre-Training
Training Dist. Complexity Levels
Test Acc. ( Hard- 15 )
Training Dist. Complexity Levels
Test Acc. ( Hard- 20 )
{5,10,15}
96.80%
{10,13,17,20}
80.20%
{13,14,15}
52.90%
{17,18,19,20}
48.22%
Appendix
Table 5: Test accuracy on Hard- n under post-training distributions with the same number of distinct complexity levels. Within each setting, the first row includes simple examples and the second contains only harder examples.