Incremental Learning of Sparse Attention Patterns in Transformers

This paper studies simple transformers trained on a high-order Markov chain, where the model must incorporate information from multiple past positions, each with different statistical importance. We show that transformers learn the task incrementally, with each stage corresponding to learning how to copy information from a subset of positions via a sparse attention pattern. Notably, the learning dynamics transition from a competitive phase, where all heads focus on the statistically most important positions, to a cooperative phase, where different heads specialize in different patterns. We model these dynamics with simplified differential equations and prove stage-wise convergence of the resulting system. Functionally, these stages correspond to a sequence of increasingly expressive misspecified models, with the full model class reached only at the end. Overall, we give a theoretical account of how structured attention patterns and head specialization emerge in stages without an explicit curriculum, with implications for generalization in sequential tasks.

This paper studies how transformers learn to use information from earlier positions in a sequence. The main finding is that learning happens in stages. At first, all attention heads focus on the most important past positions, so the heads compete to learn the same pattern. Later, the heads begin to specialize: different heads focus on different past positions, allowing the model to combine multiple pieces of information. The paper shows this behavior in a controlled Markov-chain task and explains it with a simplified mathematical model. The theory suggests that structured attention patterns and head specialization can emerge naturally from training, even without an explicit curriculum telling the model what to learn first.