mlsanityData to 14 Oct 2026

How Many Different Outputs Can a Transformer Generate?

arXiv 2605.22223 ↗First posted 21 May 2026cs.LGcited by 0

Not on the map. Why?

Abstract (arXiv)

We study how we can leverage only a handful of characteristics of a transformer's architecture to closely predict the number of different sequences it can output, both qualitatively and quantitatively. We provide an upper bound depending on the length of the prompt, which we show empirically to be tight up to a factor less than 10, across architectures and model sizes. Our analysis also provides a theoretical explanation for previously observed empirical failures of transformers on simple sequence tasks, such as copying and cramming. Formally, we prove that (i) the maximal length of accessible sequences (those that the transformer can output for some prompt) grows linearly with the prompt length, (ii) beyond a critical threshold, the proportion of accessible sequences decays exponentially with sequence length, and (iii) the linear coefficient relating prompt length to accessible sequence length admits a theoretical upper bound. Notably, these results hold even with unbounded context and computation time.

Key facts. No citing papers in the map yet (data through 14 Oct 2026). Builds on 40 of its 50 references that are in the map. First posted on arXiv 21 May 2026.

Builds on

40 of 50 references.

References · 40

  1. 2017Attention Is All You Needcited by 60,361
  2. 2020An Image is Worth 16x16 Words: Transformers for Image Recognition at Scalecited by 30,186
  3. 2019PyTorch: An Imperative Style, High-Performance Deep Learning Librarycited by 20,305
  4. 2023Mamba: Linear-Time Sequence Modeling with Selective State Spacescited by 4,718
  5. 2023Pythia: A Suite for Analyzing Large Language Models Across Training and Scalingcited by 1,786
  6. 2019Similarity of Neural Network Representations Revisitedcited by 1,755
  7. 2020Point Transformercited by 1,470
  8. 2016Understanding intermediate layers using linear classifier probescited by 1,353
  9. 2021Scaling Vision Transformerscited by 999
  10. 2019How Contextual are Contextualized Word Representations? Comparing the Geometry of BERT, ELMo, and GPT-2 Embeddingscited by 784
  11. 2019Compressive Transformers for Long-Range Sequence Modellingcited by 726
  12. 2023Eliciting Latent Predictions from Transformers with the Tuned Lenscited by 623
28 more
  1. 2019Are Transformers universal approximators of sequence-to-sequence functions?cited by 406
  2. 2024Titans: Learning to Memorize at Test Timecited by 328
  3. 2023Looped Transformers as Programmable Computerscited by 237
  4. 2024Repeat After Me: Transformers are Better than State Space Models at Copyingcited by 216
  5. 2017All-but-the-Top: Simple and Effective Postprocessing for Word Representationscited by 212
  6. 2020The Lipschitz Constant of Self-Attentioncited by 174
  7. 2021Inductive Biases and Variable Creation in Self-Attention Mechanismscited by 144
  8. 2023The emergence of clusters in self-attention dynamicscited by 140
  9. 2021Sinkformers: Transformers with Doubly Stochastic Attentioncited by 138
  10. 2023What Formal Languages Can Transformers Express? A Surveycited by 124
  11. 2021Statistically Meaningful Approximation: a Case Study on Approximating Turing Machines with Transformerscited by 102
  12. 2024Transformers need glasses! Information over-squashing in language taskscited by 91
  13. 2020O(n) Connections are Expressive Enough: Universal Approximability of Sparse Transformerscited by 83
  14. 2022Your Transformer May Not be as Powerful as You Expectcited by 55
  15. 2021IsoScore: Measuring the Uniformity of Embedding Space Utilizationcited by 53
  16. 2023Are Transformers with One Layer Self-Attention Using Low-Rank Weight Matrices Universal Approximators?cited by 47
  17. 2024A Formal Framework for Understanding Length Generalization in Transformerscited by 45
  18. 2023How Smooth Is Attention?cited by 44
  19. 2024Transformers are Universal In-context Learnerscited by 43
  20. 2023On the Expressivity Role of LayerNorm in Transformers' Attentioncited by 33
  21. 2021Universal Approximation Under Constraints is Possible with Transformerscited by 32
  22. 2023Universality and Limitations of Prompt Tuningcited by 30
  23. 2023Approximation Rate of the Transformer Architecture for Sequence Modelingcited by 28
  24. 2025Cramming 1568 Tokens into a Single Vector and Back Again: Exploring the Limits of Embedding Space Capacitycited by 28
  25. 2024Transformers in Uniform TC0cited by 25
  26. 2024Fundamental Limits of Prompt Tuning Transformers: Universality, Capacity and Efficiencycited by 22
  27. 2025Mamba Modulation: On the Length Generalization of Mambacited by 16
  28. 2025Memory Limitations of Prompt Tuning in Transformerscited by 4

Built on by

Not cited yet.