One-Layer Transformers are Provably Optimal for In-context Reasoning and Distributional Association Learning in Next-Token Prediction Tasks

Quan Nguyen, Thanh Nguyen-Tang · 2025

Read One-Layer Transformers are Provably Optimal for In-context Reasoning and Distributional Association Learning in Next-Token Prediction Tasks by Quan Nguyen, Thanh Nguyen-Tang (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2505-15009.txt.

Introduction

Transformers can learn from examples placed in their input, picking up links between paired items without new training. Quan Nguyen and Thanh Nguyen-Tang study that skill in a 2025 theory paper, under the head title about how transformers learn recall tasks in context. Past theory looked mainly at models trained by a single update step.

The pair show that a class of one-layer models, with three kinds of attention, can hit the best odds a perfect reasoner could reach on a recall task. When such models train by slow descent, their loss falls at a steady rate toward that best level. The work also probes how well the skill spreads to fresh cases. The gaps they fill concern what happens at the end of training, not just after one step.

Catalog record

CREATORQuan Nguyen, Thanh Nguyen-Tang
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE74 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2505-15009

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

One-Layer Transformers are Provably Optimal for In-context Reasoning and Distributional Association Learning in Next-Token Prediction Tasks Quan Nguyen, Thanh Nguyen-Tang Abstract We study the approximation capabilities and on-convergence behaviors of one-layer transformers on the noiseless and noisy in-context reasoning of next-token prediction. Existing theoretical results focus on understanding the in-context reasoning behaviors for either the first gradient step or when the number of samples is infinite. Furthermore, no convergence rates nor generalization abilities were known. Our work addresses these gaps by showing that there exists a class of one-layer transformers that are provably Bayes-optimal with both linear and ReLU attention. When being trained with gradient descent, we show via a finite-sample analysis that the expected loss of these transformers converges at linear rate to the Bayes risk. Moreover, we prove that the trained models generalize to unseen samples as well as exhibit learning behaviors that were empirically observed in previous works. Our theoretical findings are further supported by extensive empirical validations. 1 Introduction Large language models (LLMs) have shown impressive results in complex tasks that require some form of “reasoning” where classical models such as feed-forward networks seem to struggle. These reasoning tasks include, but are not limited to, generating coherent and plausible texts from a given context, language understanding, and mathematical reasoning [ 1 , 2 ] . At the heart of LLMs is the transformer architecture that features the self-attention mechanism [ 3 ] . Transformers can process a long sequence of contexts and enable in-context reasoning via attention mechanisms. Despite such remarkable empirical performance, the theoretical understanding of self-attention in reasoning tasks remains elusive, raising critical risk and safety issues when it comes to the widespread adoption of LLM technology in a socially acceptable manner [ 4 , 5 ] . The literature has shown the usefulness of disentangling the behavior of complex models such as LLMs via controlled-setting tasks that we understand the groundtruth behaviors [ 6 ] . For understanding reasoning in LLMs, one of the benchmark tasks that the literature has been recently embarked on is next-token prediction (NTP), wherein the tasks require a model to understand the context from a sentence to be able to predict the next token correcty. As a running example, consider the task of predicting the next token for the sentence “Anna gives a book to” (the same example used in [ 7 ] ). A global bigram statistics would predict the next token to be “the” as the bigram “to the” naturally occurs in English with high frequency. However, if another person appears in the context, say Bob, then “Bob” is perhaps a better token prediction, even though the bigram “to Bob” is not a frequent bigram in the global context. In transformers, there have been strong (both empirically and theoretically) evidence that attention heads seem to responsible for in-context reasoning such as the in-context bigram “to Bob” [ 8 ] while feedforward layers seem to responsible for storing global statistics or factual knowledge such as the global bigram “to the” [ 9 , 10 , 11 , 12 ] . However, a proper understanding how such capabilities emerge during training is still lacking. For example, it is unclear how distributional associations such as “to the” and in-context reasoning such as “to Bob” are automatically assigned to feed-forward layers and self-attention layers by gradient descent without being explicitly forced to do so during training. Several initial efforts have shed insights into the above question [ 7 , 11 , 12 ] . While they made an important first progress, we are still far from depicting the whole picture of how reasoning emerges in transformers. In particular, the existing theoretical results are limited to the reasoning behavior for just the first gradient steps or an infinite-sample setting, which do not reflect how we actually train transformers in practice. In this paper, we narrow the gap above by providing a more complete picture of training transformers on next-token prediction tasks and how they get assigned with in-context reasoning and distributional association. In particular, we provide a synthetic next-token prediction task that requires a model to differentiate in-context reasoning from distributional association to be able to succeed. We show that one-layer transformers, from either the class of linear or ReLU attentions, suffice to provably approximate the Bayes-optimal predictor of the task. In addition, we show that training these transformers with normalized gradient descents converges at linear rate to the Bayes optimal predictor and exhibit a provable generalization to unseen samples. Furthermore, we show that, after sufficient number of training iterations, feed-forward layer learns to predict the noise token while attention layers learn to predict the true output token, a behavior that has been observed empirically recently. Finally, we corroborate theoretical findings with extensive empirical validations. 1.1 Related Work [ 1 ] demonstrate that trained transformers can perform in-context learning—adapting to new tasks at inference with only a few examples. Building on this, several studies [ 13 , 14 , 15 , 16 ] show that appropriately parameterized transformers can simulate procedures like gradient descent. Furthermore, [ 17 ] prove that transformers can approximate any continuous permutation-equivariant sequence-to-sequence function on compact support. Several works have analyzed transformers’ training dynamics for in-context learning of linear regression. Ahn et al. 2024 show a one-layer linear transformer that performs a preconditioned gradient step, with L layers corresponding to L steps at certain critical points. Mahankali et al. 2023 find that a one-layer linear transformer trained on noisy data mimics a single least-squares gradient step. Zhang et al. 2024 prove convergence to a global minimum under suitable initialization. Huang et al. 2024a study gradient descent in softmax transformers learning linear functions. Cui et al. 2024 show that multi-head attention with large embeddings outperforms single-head variants. Cheng et al. 2023 demonstrate that nonlinear transformers can emulate gradient descent on nonlinear functions. Kim and Suzuki 2024 analyze mean-field and two-timescale limits of linear attention models, and Chen and Li 2024 give computational bounds for training multi-head attention layers. Another line of work investigates the training dynamics for binary classification. [ 26 ] show that self-attention optimization mirrors hard-margin SVMs, revealing the implicit bias of 1-layer transformers trained via gradient descent, and that over-parameterization aids global convergence. [ 27 ] demonstrate that gradient descent on softmax attention converges to a max-margin separator distinguishing locally optimal tokens. Building on this, [ 28 ] provide finite-sample analysis. [ 29 ] offer optimization and generalization guarantees for training single-layer multi-head attention models under the NTK regime. Recent works have also examined transformers’ training dynamics for next-token prediction (NTP). Tian et al. 2023a show that self-attention acts as a discriminative scanner, focusing on predictive tokens and down-weighting common ones. Tian et al. 2023b analyze multilayer dynamics, while Li et al. 2024 find that gradient descent trains attention to learn an automaton via hard retrieval and soft composition. Thrampoulidis 2024 study the implicit bias of gradient descent in linear transformers. Huang et al. 2024b provide finite-time analysis for a one-layer transformer on a synthetic NTP task, showing sublinear max-margin and linear cross-entropy convergence. Their setting assumes one-to-one token mapping, whereas we address a more general case allowing one-to-many mappings and prove generalization results for

Read the complete text