Abstract
The Transformer architecture is widely applied in sequence modeling applications, yet the theoretical understanding of its working principles remains limited. In this work, we investigate the approximation rate for single-layer Transformers with one head. 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. This rate reveals the structural properties of the Transformer and suggests the types of sequential relationships it is best suited for approximating. In particular, the results on approximation rates enable us to concretely analyze the differences between the Transformer and classical sequence modeling methods, such as recurrent neural networks.
Introduction
While Transformers have become the de facto standard for sequence modeling in natural language processing and computer vision, their theoretical "black box" nature persists. Universal Approximation Theorems guarantee that a sufficiently large Transformer can learn any continuous function, but they fail to specify the approximation rate—how quickly the error diminishes as model capacity (e.g., number of heads or neurons) increases. This paper, presented at NeurIPS 2024, addresses this gap by establishing the first "Jackson-type" approximation rates for Transformers.
Theoretical Framework and Complexity Measures
The researchers treat the Transformer as a mathematical operator, breaking its analysis into three primary components:
- Representation Theorem: They demonstrate that general sequence-to-sequence relationships can be decomposed into pairwise interactions (Attention) and pointwise transformations (Feed-Forward Networks).
- Complexity Measures: To quantify the difficulty of a task, the authors utilize Proper Orthogonal Decomposition (POD). This functional analogue of Singular Value Decomposition (SVD) determines if token interactions are "low-rank." If a few dominant patterns can describe how tokens influence one another, the task's complexity is low.
- Jackson-type Approximation Rate: The derived formula shows that approximation error decreases as the "budget"—the number of attention heads $m_h$ and the size of feed-forward layers $m_{FF}$—is increased.
Empirical Validation
The theoretical findings were validated using synthetic data and real-world benchmarks like CIFAR-10 (via Vision Transformers) and WMT2014 English-German translation.
As illustrated in the figure above, the estimated singular values (a) exhibit a sharp decay, confirming that many practical sequence tasks possess a low-rank structure. Furthermore, the training error (c) follows a power-law decay of approximately $O(1/m_h^{0.27})$, aligning closely with the mathematical rates predicted by the Jackson-type estimates.
Key Insights: Transformers vs. RNNs
The analysis highlights a critical distinction between Transformers and Recurrent Neural Networks (RNNs):
- Permutation Invariance: Transformers are mathematically indifferent to sequence order (even with position encodings, the complexity measure remains stable under shuffling). In experiments, shuffling CIFAR-10 patches only reduced Transformer accuracy from 0.98 to 0.96, whereas RNN error increased by several orders of magnitude.
- Temporal Mixing Weakness: The paper identifies "Temporal Mixing"—the blending of information across many time steps—as a significant challenge for Transformers. Such tasks cause the interaction rank to explode, making them harder for Transformers to approximate than RNNs, which handle sequential "blurring" or averaging more naturally.
Conclusion and Future Directions
This research provides a rigorous foundation for understanding why Transformers excel at low-rank token interactions and permutation-flexible tasks. However, the identified weakness in temporal mixing suggests that for tasks involving heavy signal processing, RNN-like structures or specialized preprocessing may still be superior. Future work aims to extend these proofs to deep, multi-layer Transformers and explore architectural modifications to mitigate the temporal mixing bottleneck.
Summary updated