How Many Different Outputs Can a Transformer Generate?

• URL: http://arxiv.org/abs/2605.22223v1
• Date: Thu, 21 May 2026 09:26:37 GMT
• Title: How Many Different Outputs Can a Transformer Generate?
• Abstract summary: 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.<n>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.
• Score: 45.158621811869466
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: 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.

Related papers

• Quantitative Bounds for Length Generalization in Transformers [58.175107357008876]
  We study the problem of length generalization (LG) in transformers.<n>LG occurs when the internal behavior of the transformer on longer sequences can be "simulated" by its behavior on shorter sequences.
  arXiv  Detail & Related papers  (2025-10-30T21:31:36Z)
• Memory Limitations of Prompt Tuning in Transformers [45.158621811869466]
  We show that the amount of information memorized by a transformer cannot scale faster than linearly with the prompt length.<n>We also present the first formal proof of a phenomenon empirically observed in large language models: performance degradation.<n>This finding offers a fundamental understanding of the intrinsic limitations of transformer architectures.
  arXiv  Detail & Related papers  (2025-08-30T09:08:00Z)
• What One Cannot, Two Can: Two-Layer Transformers Provably Represent Induction Heads on Any-Order Markov Chains [64.31313691823088]
  In-context learning (ICL) is a capability of transformers, through which trained models learn to adapt to new tasks by leveraging information from the input context.<n>We show that a two-layer transformer with one head per layer can indeed represent any conditional k-gram.
  arXiv  Detail & Related papers  (2025-08-10T07:03:01Z)
• Sequence Complementor: Complementing Transformers For Time Series Forecasting with Learnable Sequences [5.244482076690776]
  We find that expressive capability of sequence representation is a key factor influencing Transformer performance in time forecasting.<n>We propose a novel attention mechanism with Sequence Complementors and prove feasible from an information theory perspective.
  arXiv  Detail & Related papers  (2025-01-06T03:08:39Z)
• Adversarial Testing as a Tool for Interpretability: Length-based Overfitting of Elementary Functions in Transformers [0.0]
  We study elementary edit functions using a defined set of error indicators to interpret the behaviour of the sequence-to-sequence Transformer. We show that generalization to shorter sequences is often possible, but confirm that longer sequences are highly problematic.
  arXiv  Detail & Related papers  (2024-10-17T17:39:46Z)
• LongNet: Scaling Transformers to 1,000,000,000 Tokens [146.4077038371075]
  LongNet is a Transformer variant that can scale sequence length to more than 1 billion tokens. Our work opens up new possibilities for modeling very long sequences, e.g., treating a whole corpus or even the entire Internet as a sequence.
  arXiv  Detail & Related papers  (2023-07-05T17:59:38Z)
• Universality and Limitations of Prompt Tuning [65.8354898840308]
  We take one of the first steps to understand the role of soft-prompt tuning for transformer-based architectures. We analyze prompt tuning from the lens of universality and limitations with finite-depth pretrained transformers for continuous-valued functions. Our result guarantees the existence of a strong transformer with a prompt to approximate any sequence-to-sequence function in the set of Lipschitz functions.
  arXiv  Detail & Related papers  (2023-05-30T06:47:07Z)
• DBA: Efficient Transformer with Dynamic Bilinear Low-Rank Attention [53.02648818164273]
  We present an efficient yet effective attention mechanism, namely the Dynamic Bilinear Low-Rank Attention (DBA) DBA compresses the sequence length by input-sensitive dynamic projection matrices and achieves linear time and space complexity. Experiments over tasks with diverse sequence length conditions show that DBA achieves state-of-the-art performance.
  arXiv  Detail & Related papers  (2022-11-24T03:06:36Z)

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

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.