# Concise One-Layer Transformers Can Do Function Evaluation (Sometimes)

arXiv: https://arxiv.org/abs/2503.22076 · HTML: https://mlsanity.com/paper/2503.22076/

## Key facts

- Cited by 3 papers in the map (data through 14 Oct 2026).
- Builds on 9 of its 10 references that are in the map.
- First posted on arXiv 28 Mar 2025.

## Builds on (most cited first, 9 of 9)

- [Are Transformers universal approximators of sequence-to-sequence functions?](https://mlsanity.com/paper/1912.10077/) (2019)
- [Representational Strengths and Limitations of Transformers](https://mlsanity.com/paper/2306.02896/) (2023)
- [What Formal Languages Can Transformers Express? A Survey](https://mlsanity.com/paper/2311.00208/) (2023)
- [On Limitations of the Transformer Architecture](https://mlsanity.com/paper/2402.08164/) (2024)
- [Are Transformers with One Layer Self-Attention Using Low-Rank Weight Matrices Universal Approximators?](https://mlsanity.com/paper/2307.14023/) (2023)
- [Theoretical limitations of multi-layer Transformer](https://mlsanity.com/paper/2412.02975/) (2024)
- [One-layer transformers fail to solve the induction heads task](https://mlsanity.com/paper/2408.14332/) (2024)
- [Simulating Hard Attention Using Soft Attention](https://mlsanity.com/paper/2412.09925/) (2024)
- [Strassen Attention, Split VC Dimension and Compositionality in Transformers](https://mlsanity.com/paper/2501.19215/) (2025)

## Built on by (most cited first, 3 of 3)

- [Indexing: the Beginning and the End](https://mlsanity.com/paper/2607.22361/) (2026)
- [Every Bit Counts: A Theoretical Study of Precision-Expressivity Tradeoffs in Quantized Transformers](https://mlsanity.com/paper/2602.02707/) (2026)
- [Exact-Solution Volume and Length Generalization in Transformers](https://mlsanity.com/paper/2610.07676/) (2026)

## Abstract (arXiv)

While transformers have proven enormously successful in a range of tasks, their fundamental properties as models of computation are not well understood. This paper contributes to the study of the expressive capacity of transformers, focusing on their ability to perform the fundamental computational task of evaluating an arbitrary function from [n] to [n] at a given argument. We prove that concise 1-layer transformers (i.e., with a polylog bound on the product of the number of heads, the embedding dimension, and precision) are capable of doing this task under some representations of the input, but not when the function's inputs and values are only encoded in different input positions. Concise 2-layer transformers can perform the task even with the more difficult input representation. Experimentally, we find a rough alignment between what we have proven can be computed by concise transformers and what can be practically learned.