Related papers: On the Expressive Power of Transformers

On the Expressive Power of Transformers

URL: http://arxiv.org/abs/2608.12671v1
Date: Thu, 13 Aug 2026 00:12:15 GMT
Title: On the Expressive Power of Transformers
Abstract summary: Circuit complexity has emerged as the "correct" branch of computational complexity to analyze the expressive power of transformers.<n>Here, we present an overview of selected results that delineate the expressive power of transformers using concepts and methods from circuit complexity.
Score: 0.8594140167290097
License: http://creativecommons.org/licenses/by/4.0/
Abstract: 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 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.

Related papers

Fixed Universal Transformers [50.35639171254542]
We introduce emphuniversal transformers: fixed transformers that can simulate any transformer in a given class via a suitable input embedding.<n>We provide explicit sparse constructions achieving universality when the embedding dimension is sufficiently large.<n>Our results suggest that much of a transformer's expressive power may reside in its input representation rather than its learned weights.
arXiv Detail & Related papers (2026-05-29T15:22:06Z)
Revisiting Padded Transformer Expressivity: Which Architectural Choices Matter and Which Don't [78.36679389968772]
We find that padded $textL$ constantprecision transformers are surprisingly robust to expressivity.<n>$logd-looped constant-precision transformers reach $textFO-uniform TCd$, and growing-precision ones reach $textFO-uniform TCd$.
arXiv Detail & Related papers (2026-05-28T19:58:43Z)
Approximation of Permutation Invariant Polynomials by Transformers: Efficient Construction in Column-Size [6.9060054915724]
Transformers are a type of neural network that have demonstrated remarkable performance across various domains.<n>In this study, we investigate the ability of transformers to approximate column-symmetrics.
arXiv Detail & Related papers (2025-02-17T05:56:11Z)
A Comparative Study on Code Generation with Transformers [0.0]
This paper introduces the concept of a "A Comparative Study on Code Generation with Transformers"<n>A model based on Transformer architecture, and NLP methodologies to automatically generate C++ source code for different varieties of problems.
arXiv Detail & Related papers (2024-12-07T21:18:23Z)
Transformers are Efficient Compilers, Provably [11.459397066286822]
Transformer-based large language models (LLMs) have demonstrated surprisingly robust performance across a wide range of language-related tasks.<n>In this paper, we take the first steps towards a formal investigation of using transformers as compilers from an expressive power perspective.<n>We introduce a representative programming language, Mini-Husky, which encapsulates key features of modern C-like languages.
arXiv Detail & Related papers (2024-10-07T20:31:13Z)
AlgoFormer: An Efficient Transformer Framework with Algorithmic Structures [80.28359222380733]
We design a novel transformer framework, dubbed AlgoFormer, to empower transformers with algorithmic capabilities.<n>In particular, inspired by the structure of human-designed learning algorithms, our transformer framework consists of a pre-transformer that is responsible for task preprocessing.<n>Some theoretical and empirical results are presented to show that the designed transformer has the potential to perform algorithm representation and learning.
arXiv Detail & Related papers (2024-02-21T07:07:54Z)
Looped Transformers are Better at Learning Learning Algorithms [16.98720552888865]
We propose the utilization of looped transformer architecture and its associated training methodology. Experimental results suggest that the looped transformer achieves performance comparable to the standard transformer.
arXiv Detail & Related papers (2023-11-21T08:32:38Z)
On the Power of Saturated Transformers: A View from Circuit Complexity [87.20342701232869]
We show that saturated transformers transcend the limitations of hard-attention transformers. The jump from hard to saturated attention can be understood as increasing the transformer's effective circuit depth by a factor of $O(log n)$.
arXiv Detail & Related papers (2021-06-30T17:09:47Z)
Thinking Like Transformers [64.96770952820691]
We propose a computational model for the transformer-encoder in the form of a programming language. We show how RASP can be used to program solutions to tasks that could conceivably be learned by a Transformer. We provide RASP programs for histograms, sorting, and Dyck-languages.
arXiv Detail & Related papers (2021-06-13T13:04:46Z)
Scalable Transformers for Neural Machine Translation [86.4530299266897]
Transformer has been widely adopted in Neural Machine Translation (NMT) because of its large capacity and parallel training of sequence generation. We propose a novel scalable Transformers, which naturally contains sub-Transformers of different scales and have shared parameters. A three-stage training scheme is proposed to tackle the difficulty of training the scalable Transformers.
arXiv Detail & Related papers (2021-06-04T04:04:10Z)

This list is automatically generated from the titles and abstracts of the papers in this site.