How do Transformers perform In-Context Autoregressive Learning?

• URL: http://arxiv.org/abs/2402.05787v2
• Date: Wed, 5 Jun 2024 13:44:00 GMT
• Title: How do Transformers perform In-Context Autoregressive Learning?
• Authors: Michael E. Sander, Raja Giryes, Taiji Suzuki, Mathieu Blondel, Gabriel Peyré,
• Abstract summary: We train a Transformer model on a simple next token prediction task. We show how a trained Transformer predicts the next token by first learning $W$ in-context, then applying a prediction mapping.
• Score: 76.18489638049545
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Transformers have achieved state-of-the-art performance in language modeling tasks. However, the reasons behind their tremendous success are still unclear. In this paper, towards a better understanding, we train a Transformer model on a simple next token prediction task, where sequences are generated as a first-order autoregressive process $s_{t+1} = W s_t$. We show how a trained Transformer predicts the next token by first learning $W$ in-context, then applying a prediction mapping. We call the resulting procedure in-context autoregressive learning. More precisely, focusing on commuting orthogonal matrices $W$, we first show that a trained one-layer linear Transformer implements one step of gradient descent for the minimization of an inner objective function, when considering augmented tokens. When the tokens are not augmented, we characterize the global minima of a one-layer diagonal linear multi-head Transformer. Importantly, we exhibit orthogonality between heads and show that positional encoding captures trigonometric relations in the data. On the experimental side, we consider the general case of non-commuting orthogonal matrices and generalize our theoretical findings.

Related papers

• On the Role of Depth and Looping for In-Context Learning with Task Diversity [69.4145579827826]
  We study in-context learning for linear regression with diverse tasks. We show that multilayer Transformers are not robust to even distributional shifts as small as $O(e-L)$ in Wasserstein distance.
  arXiv  Detail & Related papers  (2024-10-29T03:27:56Z)
• Graph Transformers Dream of Electric Flow [72.06286909236827]
  We show that the linear Transformer, when applied to graph data, can implement algorithms that solve canonical problems. We present explicit weight configurations for implementing each such graph algorithm, and we bound the errors of the constructed Transformers by the errors of the underlying algorithms.
  arXiv  Detail & Related papers  (2024-10-22T05:11:45Z)
• Towards Understanding the Universality of Transformers for Next-Token Prediction [20.300660057193017]
  Causal Transformers are trained to predict the next token for a given context. We take a step towards understanding this phenomenon by studying the approximation ability of Transformers for next-token prediction.
  arXiv  Detail & Related papers  (2024-10-03T21:42:21Z)
• Can Transformers Learn $n$-gram Language Models? [77.35809823602307]
  We study transformers' ability to learn random $n$-gram LMs of two kinds. We find that classic estimation techniques for $n$-gram LMs such as add-$lambda$ smoothing outperform transformers.
  arXiv  Detail & Related papers  (2024-10-03T21:21:02Z)
• Unveiling Induction Heads: Provable Training Dynamics and Feature Learning in Transformers [54.20763128054692]
  We study how a two-attention-layer transformer is trained to perform ICL on $n$-gram Markov chain data. We prove that the gradient flow with respect to a cross-entropy ICL loss converges to a limiting model.
  arXiv  Detail & Related papers  (2024-09-09T18:10:26Z)
• On Mesa-Optimization in Autoregressively Trained Transformers: Emergence and Capability [34.43255978863601]
  Several suggest that transformers learn a mesa-optimizer during autorere training. We show that a stronger assumption related to the moments of data is the sufficient necessary condition that the learned mesa-optimizer can perform.
  arXiv  Detail & Related papers  (2024-05-27T05:41:06Z)
• How Well Can Transformers Emulate In-context Newton's Method? [46.08521978754298]
  We study whether Transformers can perform higher order optimization methods, beyond the case of linear regression. We demonstrate the ability of even linear attention-only Transformers in implementing a single step of Newton's iteration for matrix inversion with merely two layers.
  arXiv  Detail & Related papers  (2024-03-05T18:20:10Z)
• Transformers learn to implement preconditioned gradient descent for in-context learning [41.74394657009037]
  Several recent works demonstrate that transformers can implement algorithms like gradient descent. We ask: Can transformers learn to implement such algorithms by training over random problem instances? For a transformer with $L$ attention layers, we prove certain critical points of the training objective implement $L$ iterations of preconditioned gradient descent.
  arXiv  Detail & Related papers  (2023-06-01T02:35:57Z)
• Transformers learn in-context by gradient descent [58.24152335931036]
  Training Transformers on auto-regressive objectives is closely related to gradient-based meta-learning formulations. We show how trained Transformers become mesa-optimizers i.e. learn models by gradient descent in their forward pass.
  arXiv  Detail & Related papers  (2022-12-15T09:21:21Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.