NeFut Logo NeFut
Admin Login

[CS.AI] On the Expressive Power of Transformers

Published at: 2026-08-14 22:00 Last updated: 2026-08-16 07:03
#LLM #Artificial Intelligence #Circuit Complexity

Transformers form the critical component of essentially all large language models (LLMs) in use today. Because of their ubiquity and computational capability, there is a rapidly growing body of work that aims to precisely calibrate the expressive power of transformers as language recognizers by comparing them against standard models of computation studied for decades by the theoretical computer science community. In this endeavor, circuit complexity has by and large emerged as the "correct" branch of computational complexity to analyze the expressive power of transformers; the reason is that parameterizing transformers by the various resources they use, such as attention and precision, leads to direct comparisons with different classes of circuits parameterized by resources such as type of gates, size, and depth. Here, we present an overview of selected results that delineate the expressive power of transformers using concepts and methods from circuit complexity. Blogger's Review: The study of transformers' expressive power is a hot topic in the field of artificial intelligence, and through circuit complexity analysis, we can better understand the computational capabilities of transformers and their applications in language models.

Original Source: https://arxiv.org/abs/2608.12671

[h] Back to Home