On the Expressive Power of Transformers

Phokion Kolaitis, Rik Sengupta

Multi-layer transformers form the critical component of essentially all large language models (LLMs) in use today. Because of their ubiquity and computational capability, there is…