On the Expressive Power of a Variant of the Looped Transformer

• DOI: 10.48550/arxiv.2402.13572
• Publication Date: 2024-02-21
• Authors: Yihang Gao; Chuanyang Zheng; Enze Xie; Han Shi; Tianyang Hu; Li Yu; Michael Ng; Zhenguo Li; Zhaoqiang Liu
• Keywords: Expressive power

Besides natural language processing, transformers exhibit extraordinary performance in solving broader applications, including scientific computing and computer vision. Previous works try to explain this from the expressive power capability perspectives that standard are capable of performing some algorithms. To empower with algorithmic capabilities motivated by recently proposed looped transformer (Yang et al., 2024; Giannou 2023), we design a novel block, dubbed Algorithm Transformer (abbreviated as AlgoFormer). Compared vanilla transformer, AlgoFormer can achieve significantly higher expressiveness algorithm representation when using same number parameters. In particular, inspired structure human-designed learning algorithms, our block consists pre-transformer is responsible for task pre-processing, iterative optimization post-transformer producing desired results after post-processing. We provide theoretical evidence challenging problems, mirroring Furthermore, empirical presented show designed has potential be smarter than Experimental demonstrate superiority it outperforms tasks.