  Natural language processing (NLP) made an impressive jump with the
introduction of Transformers. ChatGPT is one of the most famous examples,
changing the perception of the possibilities of AI even outside the research
community. However, besides the impressive performance, the quadratic time and
space complexity of Transformers with respect to sequence length pose
significant limitations for handling long sequences. While efficient
Transformer architectures like Linformer and Performer with linear complexity
have emerged as promising solutions, their theoretical understanding remains
limited. In this paper, we introduce Sumformer, a novel and simple architecture
capable of universally approximating equivariant sequence-to-sequence
functions. We use Sumformer to give the first universal approximation results
for Linformer and Performer. Moreover, we derive a new proof for Transformers,
showing that just one attention layer is sufficient for universal
approximation.
