On the Expressive Power of a Variant of the Looped Transformer
Yihang Gao Chuanyang Zheng Enze Xie Han Shi Tianyang Hu Yu Li Michael K. Ng Zhenguo Li Zhaoqiang Liu
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
and capability perspectives that standard transformers are capable of
performing some algorithms. To empower transformers with algorithmic
capabilities and motivated by the recently proposed looped transformer (Yang et
al., 2024; Giannou et al., 2023), we design a novel transformer block, dubbed
Algorithm Transformer (abbreviated as AlgoFormer). Compared with the standard
transformer and vanilla looped transformer, the proposed AlgoFormer can achieve
significantly higher expressiveness in algorithm representation when using the
same number of parameters. In particular, inspired by the structure of
human-designed learning algorithms, our transformer block consists of a
pre-transformer that is responsible for task pre-processing, a looped
transformer for iterative optimization algorithms, and a post-transformer for
producing the desired results after post-processing. We provide theoretical
evidence of the expressive power of the AlgoFormer in solving some challenging
problems, mirroring human-designed algorithms. Furthermore, some theoretical
and empirical results are presented to show that the designed transformer has
the potential to be smarter than human-designed algorithms. Experimental
results demonstrate the empirical superiority of the proposed transformer in
that it outperforms the standard transformer and vanilla looped transformer in
some challenging tasks.