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

2019/12/20 by Chulhee Yun, Yun, Chulhee, Srinadh Bhojanapalli +7 · 1 voice · 41 citations
Computer Science · #Fuzzy Logic and Control Systems #Natural Language Processing Techniques #Neural Networks and Applications #Software Engineering Research #Speech Recognition and Synthesis #Topic Modeling #cs.LG #stat.ML

paper · pdf · doi:10.48550/arxiv.1912.10077

openalex publication_date 2019/12/20 · openalex created_date 2019/12/26 · openalex updated_date 2026/07/28

Abstract

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 simpler alternatives to self-attention layers and empirically evaluate them.

Citations

• The Fast Johnson–Lindenstrauss Transform and Approximate Nearest Neighbors
• On the Turing Completeness of Modern Neural Network Architectures
• XLNet: Generalized Autoregressive Pretraining for Language Understanding

Cited by

• MoLGE: Mixture of Language Group Experts for Efficient Scaling of Massively Multilingual Speech Recognition
• On the Universality of Transformer Architectures; How Much Attention Is Enough?
• Lyapunov-based Adaptive Transformer (LyAT) for Control of Stochastic Nonlinear Systems
• AttenGW: A Lightweight Attention-Based Multi-Detector Gravitational-Wave Detection Pipeline
• Sliced ReLU attention: Quasi-linear contextual expressivity via sorting
• Algorithmic Thinking Theory
• Rectifying LLM Thought from Lens of Optimization
• DoPE: Denoising Rotary Position Embedding
• A General Method for Proving Networks Universal Approximation Property
• Vocabulary In-Context Learning in Transformers: Benefits of Positional Encoding
• Scaling Laws and In-Context Learning: A Unified Theoretical Framework
• Take Goodhart Seriously: Principled Limit on General-Purpose AI Optimization
• Key and Value Weights Are Probably All You Need: On the Necessity of the Query, Key, Value weight Triplet in Decoder-Only Transformers
• Hierarchical Graph Networks for Accurate Weather Forecasting via Lightweight Training
• An integrated neural wavefunction solver for spinful Fermi systems
• Unraveling Syntax: Language Modeling and the Substructure of Grammars
• Unlocking Symbol-Level Precoding Efficiency Through Tensor Equivariant Neural Network
• Design Principles for Sequence Models via Coefficient Dynamics
• The Effect of Attention Head Count on Transformer Approximation
• Prompt reinforcing for long-term planning of large language models
• Allocation of Parameters in Transformers
• FieldFormer: Locality-Aware Transformers for Spatio-Temporal Modeling on Sparse Sensor Networks
• Transformers through the lens of support-preserving maps between measures
• GoalRank: Group-Relative Optimization for a Large Ranking Model
• Bridging Kolmogorov Complexity and Deep Learning: Asymptotically Optimal Description Length Objectives for Transformers
• Latent Twins
• Causality-Induced Positional Encoding for Transformer-Based Representation Learning of Non-Sequential Features
• Localmax dynamics for attention in transformers and its asymptotic behavior
• Dynamic Relational Priming Improves Transformer in Multivariate Time Series
• Fast attention mechanisms: a tale of parallelism
• Beyond Memorization: Extending Reasoning Depth with Recurrence, Memory and Test-Time Compute Scaling
• Optimal Dynamic Regret by Transformers for Non-Stationary Reinforcement Learning
• The LLM as a Network Operator: A Vision for Generative AI in the 6G Radio Access Network
• Integral Transformer: Denoising Attention, Not Too Much Not Too Little
• CLIPSym: Delving into Symmetry Detection with CLIP
• Too Easily Fooled? Prompt Injection Breaks LLMs on Frustratingly Simple Multiple-Choice Questions
• Deep Neural Networks with General Activations: Super-Convergence in Sobolev Norms
• Transformers in Pseudo-Random Number Generation: A Dual Perspective on Theory and Practice
• Context-aware Rotary Position Embedding
• Graded Transformers
• Compositional Generalization in Semantic Parsing: Pre-training vs. Specialized Architectures

Discussions

• J'aime beaucoup ce papier aussi: arxiv.org/abs/1912.10077 Ça n'apprend pas grand chose sur comment un obtient un LLM, mais c'est interessant de voir que les deux composante (Attention + MLP) sont néce [bsky, 4 points, 0 comments]

Related

• Universal Approximation Theorem for a Single-Layer Transformer
• Sumformer: Universal Approximation for Efficient Transformers
• Prompting a Pretrained Transformer Can Be a Universal Approximator
• Are Transformers with One Layer Self-Attention Using Low-Rank Weight Matrices Universal Approximators?
• Approximation and Estimation Ability of Transformers for Sequence-to-Sequence Functions with Infinite Dimensional Input