# Learning and Transferring Sparse Contextual Bigrams with Linear Transformers

arXiv: https://arxiv.org/abs/2410.23438 · HTML: https://mlsanity.com/paper/2410.23438/

## Key facts

- Cited by 9 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 30 Oct 2024.

## Built on by (most cited first, 9 of 9)

- [Training Dynamics of In-Context Learning in Linear Attention](https://mlsanity.com/paper/2501.16265/) (2025)
- [On the Convergence of Gradient Descent on Learning Transformers with Residual Connections](https://mlsanity.com/paper/2506.05249/) (2025)
- [Disentangling Feature Structure: A Mathematically Provable Two-Stage Training Dynamics in Transformers](https://mlsanity.com/paper/2502.20681/) (2025)
- [Facts in Stats: Impacts of Pretraining Diversity on Language Model Generalization](https://mlsanity.com/paper/2510.16096/) (2025)
- [How Can Mamba Learn In Context with Outliers and Generalize Provably?](https://mlsanity.com/paper/2510.00399/) (2025)
- [Transformers Provably Learn to Internalize Chain-of-Thought](https://mlsanity.com/paper/2605.28600/) (2026)
- [Data Distribution as a Lever for Guiding Optimizers Toward Superior Generalization in LLMs](https://mlsanity.com/paper/2602.00576/) (2026)
- [The Power of Power Law: Asymmetry Enables Compositional Reasoning](https://mlsanity.com/paper/2604.22951/) (2026)
- [What Pretraining and Midtraining Make Learnable from Rewards?](https://mlsanity.com/paper/2609.38446/) (2026)

## Abstract (arXiv)

Transformers have excelled in natural language modeling and one reason behind this success is their exceptional ability to combine contextual informal and global knowledge. However, the theoretical basis remains unclear. In this paper, first we introduce the Sparse Contextual Bigram (SCB), a natural extension of the classical bigram model, where the next token's generation depends on a sparse set of earlier positions determined by the last token. We then analyze the training dynamics and sample complexity of learning SCB using a one-layer linear transformer with a gradient-based algorithm. We show that when trained from scratch, the training process can be split into an initial sample-intensive stage where the correlation is boosted from zero to a nontrivial value, followed by a more sample-efficient stage of further improvement. Additionally, we prove that, provided a nontrivial correlation between the downstream and pretraining tasks, finetuning from a pretrained model allows us to bypass the initial sample-intensive stage. We also empirically demonstrate that our algorithm can outperform SGD in this setting and discuss its relationship with the usual softmax-based transformers.