Are Transformers universal approximators of sequence-to-sequence functions?

By Chulhee Yun, Srinadh Bhojanapalli, Ankit Singh Rawat, Sashank J. Reddi, Sanjiv Kumar. 2019

533 citations recorded by the source corpus.

Despite the widespread adoption of Transformer models for NLP tasks, the expressive power of these models is not well-understood. In this paper, we establish that Transformer models are universal approximators of continuous permutation equivariant sequence-to-sequence functions with compact support, which is quite surprising given the amount of shared parameters in these models. Furthermore, using positional encodings, we circumvent the restriction of permutation equivariance, and show that Transformer models can universally approximate arbitrary continuous sequence-to-sequence functions on a compact domain. Interestingly, our proof techniques clearly highlight the different roles of the self-attention and the feed-forward layers in Transformers. In particular, we prove that fixed width self-attention layers can compute contextual mappings of the input sequences, playing a key role in the universal approximation property of Transformers. Based on this insight from our analysis, we consider other architectures that can compute contextual mappings and empirically evaluate them.

Subfields: Artificial Intelligence, Information Systems, Scaling & Learning Theory

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

In Information Systems

In Scaling & Learning Theory

Citations in the corpus

RoFormer: Enhanced Transformer with Rotary Position Embedding (2021, background): “It is noteworthy that the self-attention architecture of the current PLMs has shown to be position-agnostic Yun et al. [2020].”
Big Bird: Transformers for Longer Sequences (2020, methodology): “The key difference between our proposed attention mechanism to that of Vaswani et al. [92], Yun et al. [105] is that we add a special token at the beginning of each sequence and assign it a special vector.”
On The Computational Complexity of Self-Attention (2022, background): “Transformers have already been shown to exhibit the universal approximation property [23], but lose expressivity unless the self-attention mechanism is accompanied with skip connections [24].”
Qatten: A General Framework for Cooperative Multiagent Reinforcement Learning (2020, methodology): “The Universal Approximation Theorem for Transformer proved in (Yun et al., 2020) math-ematically justiﬁes our choice, where attention mechanism is shown to be responsible for Transformer’s approximation ability.”
MATE: Multi-view Attention for Table Transformer Efficiency (2021, methodology): “Yun et al. (2020a) showed that Transformers are universal approximators for any continuous sequence-to-sequence function, given sufficient layers.”
Limits to Depth Efficiencies of Self-Attention (2020, background): “Theoretical results on Transformers include a proof that they are universal approximators of sequence to sequence functions [Yun et al., 2019], an examination of their robustness [Shi et al., 2020], a comparison between a single self-attention layer and a single convolutional layer [Cordonnier et…”
What Can Transformers Learn In-Context? A Case Study of Simple Function Classes (2022, background): “There is a long line of work investigating the capabilities [69, 15, 77, 51, 76, 7, 78], limitations [25, 6], applications [37, 17, 49], and internal workings [19, 65, 71, 18, 48] of Transformer models.”
Crossformer: Transformer Utilizing Cross-Dimension Dependency for Multivariate Time Series Forecasting (2023, background): “Although Yun et al. (2020) theoretically proves that Transformers with trainable positional embedding are universal approximators of sequence-to-sequence functions, the ordering information still needs to be enhanced in practice.”
Looped Transformers as Programmable Computers (2023, background): “Our work follows a similar problem setting as previous studies (e.g. (Yun et al., 2019; Garg et al., 2022; Aky ¨ urek et al., 2022; von Oswald et al., 2022)) in which the input sequence consists of d - dimensional embedding vectors rather than tokens.”
Towards Revealing the Mystery behind Chain of Thought: a Theoretical Perspective (2023, background): “Recently, such results have been well extended to Transformer models [60].”
Transformers in Time Series: A Survey (2022, background): “Moreover, there is a thorough theoretical study [Yun et al. , 2020] showing that the Trans-former models are universal approximators of sequence-to-sequence functions.”
$O(n)$ Connections are Expressive Enough: Universal Approximability of Sparse Transformers (2020, methodology): “As discussed earlier, dense Transformers satisfy Assumptions 1 and 2, which means that Theorem 1 subsumes the existing result [33] for dense Transformers.”
Learning to Encode Position for Transformer with Continuous Dynamical Model (2020, unknown): “[7] prove that the design of self-attentive architecture leads to a family of permutation equivalence functions.”
Choose a Transformer: Fourier or Galerkin (2021, background): “…approximator such as a deep neural network to approximate functions/operators, following the discussion in Section D.2, the “consistency” of an approximation class embodies itself as the Universal Approximation Theorem (UAT, e.g., see [42, 18], and [58, 67, 77, 99] for modern expositions).”
Axial Residual Networks for CycleGAN-based Voice Conversion (2021, background): “In fact, replacing the self-attention layer of the Transformer block with dynamic lightweight convolution has been proposed in [26], showing improvements when applied to early layers.”
What learning algorithm is in-context learning? Investigations with linear models (2022, background): “There are various existing universality results for transformers (Yun et al., 2020; Wei et al., 2021), and for neural networks more generally (Hornik et al.”
Quasi Linear Kernel Attention with Infinite Capacity (2026, unknown): “Alternative notions of expressivity for attention mechanisms were considered in Yun et al. (2020); Furuya et al. (2025).”