Research map / Architectures and efficiency / Attention and transformers

A unified framework for establishing the universal approximation of transformer-type architectures

NeurIPS 2025 · Architectures and efficiency › Attention and transformers · approach: Transformer expressivity and learnability · 1 citations (OpenAlex)

Read the paperCheck your idea against 108,967 papers

AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.

Gives a unified, non-constructive sufficient condition (token distinguishability plus nonlinear affine-invariant feedforward layers) for universal approximation of transformer-type architectures under permutation-group equivariance, and simplifies verification via analyticity for kernel, sparse, Linformer, and new attention variants.

Problem

Whether transformer-type architectures with various attention mechanisms (kernel-based, sparse, low-rank) have the universal approximation property, without relying on architecture-specific constructions, including under permutation-group symmetry.

Approach

Identifies token distinguishability (token-mixing layers producing distinct contextual tokens for samples in different G-orbits) as the key requirement for UAP; under an analyticity assumption on attention parameters, this reduces to checking just two samples, yielding a non-constructive, verifiable criterion covering many attention types.

Key results

• Proves S_n-UAP for transformers with kernel-based attention (exp kernel, RBF kernel, Performer kernel) satisfying an analyticity and limit-distinguishability condition, with one token-mixing layer sufficient for UAP.
• Shows sparse-attention transformers with sparsity patterns connected within m layers achieve G-UAP with G the intersection of automorphism groups, with m attention layers sufficient for UAP.
• Establishes UAP for Linformer (without symmetry restriction) and SkyFormer (S_n-UAP), and gives D_n- and C_n-equivariant attention designs with token distinguishability.

Surprising findings

• Random sparse patterns have trivial automorphism group with probability approaching 1 for large n, so connectivity alone suffices for UAP without symmetry restriction.

Limitations

• Normalization layers are not considered in the analysis.
• Architectures lacking analyticity (some variants) are not covered for the number-of-layers result.
• Non-constructive criteria give no quantitative approximation rates or insight into component contributions.

Experimental setup

Baselines: Yun et al. constructive transformer UAP Performer UAP Linformer UAP sparse transformer constructive UAP

Builds on: ResNet universal approximation via control theory Transformer Performer Linformer sliding window attention

Closest papers by meaning

• Fixed Universal Transformers (NeurIPS 2026 · similarity 0.88)
• Are Transformers with One Layer Self-Attention Using Low-Rank Weight Matrices Universal Approximators? (ICLR 2024 · similarity 0.88)
• Understanding the Expressive Power and Mechanisms of Transformer for Sequence Modeling (NeurIPS 2024 · similarity 0.88)
• InfoFlow: A Framework for Multi-Layer Transformer Analysis (NeurIPS 2026 · similarity 0.88)
• Subcritical Signal Propagation at Initialization in Normalization-Free Transformers (NeurIPS 2026 · similarity 0.87)
• Separations in the Representational Capabilities of Transformers and Recurrent Architectures (NeurIPS 2024 · similarity 0.87)