How Many Different Outputs Can a Transformer Generate?
Maxime Meyer, Mario Michelessa, Caroline Chaux, Vincent Y. F. Tan · 2026
Read How Many Different Outputs Can a Transformer Generate? by Maxime Meyer, Mario Michelessa, Caroline Chaux, Vincent Y. F. Tan (2026) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2605-22223.txt.
Introduction
Maxime Meyer and co-authors ask how many different outputs a transformer can generate, predicting the count from a handful of design characteristics. They give an upper bound depending on prompt length, empirically tight within a factor under 10 across architectures and sizes. Maximal output sequence length grows linearly with prompt length, while beyond a critical threshold the output proportion decays exponentially. The linear coefficient itself admits a theoretical upper bound. The analysis also explains observed transformer failures on copying and cramming, even with unbounded context and compute.
Catalog record
| CREATOR | Maxime Meyer, Mario Michelessa, Caroline Chaux, Vincent Y. F. Tan |
|---|---|
| YEAR | 2026 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 84085 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2605.22223
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
How Many Different Outputs Can a Transformer Generate? Maxime Meyer, Mario Michelessa, Caroline Chaux, Vincent Y. F. Tan 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. † † affiliationnotice: Equal contribution 1 Introduction Transformers ( 42 ) have become the dominant architecture in modern deep learning, achieving state-of-the-art results across domains such as natural language processing ( 47 ) and computer vision ( 9 ; 52 ; 51 ) . Despite their success, these models fail on surprisingly simple tasks—such as copying or repeating sequences ( 22 ) —once the input exceeds a certain length. These failures persist even for large models specifically trained on those tasks, suggesting that they may reflect intrinsic architectural constraints. This paper characterizes such constraints by identifying structural limitations that hold for all transformers, independently of model size, training data, or available computation: • We show that every transformer can output only a finite set of output sequences. That is, most sequences are fundamentally inaccessible: no choice of prompt, context length, or inference strategy can cause the model to generate them. This impossibility result provides a principled explanation for well-documented failures of transformers on simple algorithmic tasks, such as exact copying. • Moreover, we show that for a fixed prompt length, the proportion of accessible sequences of length n decays exponentially fast with n beyond a model-dependent threshold. This phenomenon explains a puzzling empirical behavior observed in practice, where transformers perform nearly perfectly up to a critical length and then fail abruptly rather than gradually. • Finally, we derive an explicit formula to predict those thresholds as functions of the transformer architecture being used. Remarkably, this theoretical result closely matches empirical performance observed across a wide range of transformer architectures and model sizes. To establish these results, we analyze how the finite precision and the geometry of the internal representations of a transformer constrain the set of sequences it can represent or generate. We formalize this constraint through the notion of accessible sequences , defined as outputs that can arise from some input prompt (Section 3 ). The main theoretical analysis, which yields the results stated above, is conducted in Section 4 . We also devise experiments that validate our theoretical predictions in Section 5 1 1 1 Code is available at github.com/mario-michelessa/transformers_accessibility . Remark 1.1 (Broader Applicability of Our Results) . Our bounds extend beyond transformers and apply to any architecture with bounded internal representations and finite precision. This may include state-space models such as Mamba ( 18 ) . However, the possibility of diverging hidden states ( 29 ) makes the analysis more challenging, and we leave this direction for future work. 1.1 Related Works Approximation Theory of Transformers. The representational power of transformers has been extensively explored through the lens of approximation theory. In contrast, we study how finite numerical precision constrains this expressivity—showing that, as rounding errors accumulate, even simple functions such as the identity map become difficult to approximate in practice. 49 established the first universal approximation property for continuous functions, later extended to sparse attention transformers ( 50 ) and sparse target functions ( 10 ) . Subsequent works refined these results for one-layer architectures ( 24 ; 23 ) and examined approximation under compact output constraints ( 27 ) . Architectural factors such as relative positional encodings ( 30 ) have also been analyzed. A complementary line of work investigates approximation properties under prompt tuning ( 45 ; 20 ) . Among those, 32 uses a proof strategy similar to ours, leveraging a packing number-type argument. Empirical Analyses of Sequence Accessibility. Empirical studies have also examined the ability of transformers to reproduce or memorize sequences. 2 showed that transformers struggle to reliably copy long sequences, but their analysis focuses on highly synthetic settings—sequences differing by only a few tokens or alternating between two symbols ( e.g. 0 and 1). In contrast, our work studies the capacity of transformers to generate, and therefore copy, arbitrary sequences. In this line of work, 22 showed that even transformers trained on the specific task of copying struggle to reliably execute this task as the sequence length increases. The work most closely related to ours is 28 , who introduced the “cramming” procedure as an exact test of accessibility. For any target sequence [\mathbf{x}_{1},\ldots,\mathbf{x}_{n}] , a set of trainable memory vectors [\mathbf{mem}]=[\mathbf{y}_{1},\ldots,\mathbf{y}_{m}] is optimized so that the model generates [\mathbf{x}_{1},\ldots,\mathbf{x}_{n}] when conditioned on [\mathbf{mem}] . This approach effectively searches over all possible prompts—including highly unnatural ones—to determine whether a sequence is accessible. Cramming thus provides an operational definition of accessibility: a sequence is accessible if and only if a corresponding encoding [\mathbf{mem}] exists. Our work provides the first rigorous theoretical explanation for the empirical findings in 28 , and extends the experimental analysis beyond the original setting. We describe this further in Section 5 . Mean-Field Transformers. To analyze prompts of arbitrary length, it is useful to interpret a transformer as a mapping between probability measures rather than finite-length sequences, following the mean-field formulation introduced by 39 and defined in Section 2.2 . This perspective has been further developed in several directions. 7 employed it to study the Lipschitz continuity of transformers, while 13 extended the approximation theory of transformers to the space of probability distributions. More recently, 32 leveraged the mean-field framework to characterize the memory limitations of transformers. Our analysis builds upon this formulation to derive accessibility bounds that hold independent of the prompt. Representations of the Embedding Space. Prior work has visualized and probed LLM embedding spaces in three main ways. First, transformer representations have been shown to be highly anisotropic, with a large fraction of the variance concentrated along a small number of directions ( 33 ; 12 ) . Second, probing methods have shown that certain syntactic and semantic properties are linearly recoverable from transformer hidden representations ( 1 ; 19 ; 26 ) . Third, decoding intermediate activations by projecting them through the decoder matrix to logits reveals layerwise sharpening of next-token beliefs ( 35 ; 4 ) . Inspired by this decoding view, we use the same decoder matrix to find hyperplanes that partition the embedding space into next-token argmax cells in Section 3 . Expressive Power of Transformers. Complementary to the line of work on approximation theory, the expressivity of transformers can also be studied in terms of the formal