Universal Approximation Theorem for a Single-Layer Transformer

• URL: http://arxiv.org/abs/2507.10581v1
• Date: Fri, 11 Jul 2025 11:37:39 GMT
• Title: Universal Approximation Theorem for a Single-Layer Transformer
• Authors: Esmail Gumaan,
• Abstract summary: Deep learning employs multi-layer neural networks trained via the backpropagation algorithm.<n>Transformers have achieved state-of-the-art performance in natural language processing.<n>We prove that a single-layer Transformer, comprising one self-attention layer followed by a position-wise feed-forward network with ReLU activation, can any continuous sequence-to-sequence mapping on a compact domain to arbitrary precision.
• Score: 0.0
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Deep learning employs multi-layer neural networks trained via the backpropagation algorithm. This approach has achieved success across many domains and relies on adaptive gradient methods such as the Adam optimizer. Sequence modeling evolved from recurrent neural networks to attention-based models, culminating in the Transformer architecture. Transformers have achieved state-of-the-art performance in natural language processing (for example, BERT and GPT-3) and have been applied in computer vision and computational biology. However, theoretical understanding of these models remains limited. In this paper, we examine the mathematical foundations of deep learning and Transformers and present a novel theoretical result. We review key concepts from linear algebra, probability, and optimization that underpin deep learning, and we analyze the multi-head self-attention mechanism and the backpropagation algorithm in detail. Our main contribution is a universal approximation theorem for Transformers: we prove that a single-layer Transformer, comprising one self-attention layer followed by a position-wise feed-forward network with ReLU activation, can approximate any continuous sequence-to-sequence mapping on a compact domain to arbitrary precision. We provide a formal statement and a complete proof. Finally, we present case studies that demonstrate the practical implications of this result. Our findings advance the theoretical understanding of Transformer models and help bridge the gap between theory and practice.

Related papers

• Graded Transformers: A Symbolic-Geometric Approach to Structured Learning [0.0]
  We introduce a novel class of sequence models that embed inductive biases through grading transformations on vector spaces.<n>The Graded Transformer holds transformative potential for hierarchical learning and neurosymbolic reasoning.<n>This work advances structured deep learning by fusing geometric and algebraic principles with attention mechanisms.
  arXiv  Detail & Related papers  (2025-07-27T02:34:08Z)
• Interpreting Affine Recurrence Learning in GPT-style Transformers [54.01174470722201]
  In-context learning allows GPT-style transformers to generalize during inference without modifying their weights. This paper focuses specifically on their ability to learn and predict affine recurrences as an ICL task. We analyze the model's internal operations using both empirical and theoretical approaches.
  arXiv  Detail & Related papers  (2024-10-22T21:30:01Z)
• Learning Linear Attention in Polynomial Time [115.68795790532289]
  We provide the first results on learnability of single-layer Transformers with linear attention. We show that linear attention may be viewed as a linear predictor in a suitably defined RKHS. We show how to efficiently identify training datasets for which every empirical riskr is equivalent to the linear Transformer.
  arXiv  Detail & Related papers  (2024-10-14T02:41:01Z)
• Can Looped Transformers Learn to Implement Multi-step Gradient Descent for In-context Learning? [69.4145579827826]
  We show a fast flow on the regression loss despite the gradient non-ity algorithms for our convergence landscape. This is the first theoretical analysis for multi-layer Transformer in this setting.
  arXiv  Detail & Related papers  (2024-10-10T18:29:05Z)
• Learning on Transformers is Provable Low-Rank and Sparse: A One-layer Analysis [63.66763657191476]
  We show that efficient numerical training and inference algorithms as low-rank computation have impressive performance for learning Transformer-based adaption. We analyze how magnitude-based models affect generalization while improving adaption. We conclude that proper magnitude-based has a slight on the testing performance.
  arXiv  Detail & Related papers  (2024-06-24T23:00:58Z)
• Uncovering mesa-optimization algorithms in Transformers [61.06055590704677]
  Some autoregressive models can learn as an input sequence is processed, without undergoing any parameter changes, and without being explicitly trained to do so. We show that standard next-token prediction error minimization gives rise to a subsidiary learning algorithm that adjusts the model as new inputs are revealed. Our findings explain in-context learning as a product of autoregressive loss minimization and inform the design of new optimization-based Transformer layers.
  arXiv  Detail & Related papers  (2023-09-11T22:42:50Z)
• NAR-Former V2: Rethinking Transformer for Universal Neural Network Representation Learning [25.197394237526865]
  We propose a modified Transformer-based universal neural network representation learning model NAR-Former V2. Specifically, we take the network as a graph and design a straightforward tokenizer to encode the network into a sequence. We incorporate the inductive representation learning capability of GNN into Transformer, enabling Transformer to generalize better when encountering unseen architecture.
  arXiv  Detail & Related papers  (2023-06-19T09:11:04Z)
• Transformers as Statisticians: Provable In-Context Learning with In-Context Algorithm Selection [88.23337313766353]
  This work first provides a comprehensive statistical theory for transformers to perform ICL. We show that transformers can implement a broad class of standard machine learning algorithms in context. A emphsingle transformer can adaptively select different base ICL algorithms.
  arXiv  Detail & Related papers  (2023-06-07T17:59:31Z)
• Approximation Rate of the Transformer Architecture for Sequence Modeling [18.166959969957315]
  We consider a class of non-linear relationships and identify a novel notion of complexity measures to establish an explicit Jackson-type approximation rate estimate for the Transformer.<n>This rate reveals the structural properties of the Transformer and suggests the types of sequential relationships it is best suited for approximating.
  arXiv  Detail & Related papers  (2023-05-29T10:56:36Z)
• Predictive Coding beyond Gaussian Distributions [38.51699576854394]
  Predictive coding (PC) is a neuroscience-inspired method that performs inference on hierarchical Gaussian generative models. These methods fail to keep up with modern neural networks, as they are unable to replicate the dynamics of complex layers and activation functions. We show that our method allows us to train transformer networks and achieve a performance comparable with BP on conditional language models.
  arXiv  Detail & Related papers  (2022-11-07T12:02:05Z)

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.