💻 computer science

How Many Different Outputs Can a Transformer Generate?

This paper establishes that a transformer's capacity to generate diverse output sequences is fundamentally limited by its prompt length, proving that the number of accessible sequences grows linearly with the prompt while the proportion of accessible sequences decays exponentially beyond a critical threshold, thereby explaining empirical failures on tasks like copying and cramming.

Original authors: Maxime Meyer, Mario Michelessa, Caroline Chaux, Vincent Y. F. Tan

Published 2026-05-22

📖 5 min read🧠 Deep dive

CC BY 4.0

Original authors: Maxime Meyer, Mario Michelessa, Caroline Chaux, Vincent Y. F. Tan

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

The Big Idea: The "Finite Library" of a Transformer

Imagine a Transformer (the AI model behind chatbots) not as an infinite, magical brain, but as a giant, high-tech library.

The paper asks a simple question: How many different books (sequences of words) can this library actually produce?

The authors discovered a surprising limit: No matter how big the library is, or how much time you give it, it can only write a finite number of unique stories. Most possible stories are fundamentally "inaccessible"—the library simply doesn't have the physical space or the "ink" to write them, even if you try to trick it with different prompts.

The Core Analogy: The Pixelated Map

To understand why this happens, imagine the Transformer's internal thinking process as a giant map (called the "embedding space").

The Map is Pixelated: Because computers use numbers with limited precision (like a digital photo with a fixed number of pixels), this map isn't smooth and continuous. It's made of tiny, discrete "tiles" or "pixels."
The Zones: On this map, different areas correspond to different next words. If the AI's internal "pointer" lands in Zone A, it writes "cat." If it lands in Zone B, it writes "dog."
The Problem of Size: As you ask the AI to write a longer and longer story, the number of possible combinations of words explodes.
- Imagine trying to fit every possible sentence of length 100 into this map.
- Because the map is made of finite tiles, the "zones" for specific long sentences become incredibly tiny—smaller than a single pixel.
- Once a zone is smaller than a pixel, the AI can't distinguish it from its neighbors. It literally cannot "see" the path to write that specific long sentence.

The Three Key Findings

The paper proves three main things about this "Pixelated Map":

1. The "Prompt" is the Key, but it has a Limit
Think of the "prompt" (the text you type) as a key that unlocks a specific door in the library.

The paper shows that the length of the story the AI can write grows linearly with the length of your key (the prompt).
Analogy: If you give the AI a 1-word prompt, it might only be able to write a 10-word story. If you give it a 10-word prompt, it might write a 100-word story. But you can't just keep adding words forever; eventually, the "key" runs out of unique combinations to unlock new, longer paths.

2. The "Cliff" of Failure
There is a specific length threshold.

Below the cliff: The AI works perfectly. It can copy or generate almost any short sequence you ask for.
Above the cliff: The number of stories it can write drops off a cliff. It doesn't get slightly worse; it suddenly becomes impossible to generate most long sequences.
Analogy: Imagine a staircase where the first 50 steps are solid. But step 51 is a trapdoor. Once you pass a certain length, the probability of the AI successfully writing a specific long string of words drops to near zero, exponentially fast.

3. The "Cramming" Experiment
The researchers tested this by trying to "cram" a specific long sequence into the AI's memory using a special, optimized prompt (like a master key).

Result: They found that for short sequences, the AI could be forced to output them. But once the sequence got too long, no amount of "cramming" worked. The AI simply couldn't generate the sequence, no matter how hard they tried to tune the prompt.
This explains why AI models sometimes fail at simple tasks like copying a long string of text perfectly, even if they were trained specifically to do it. It's not a training error; it's a structural limit of the architecture.

Why Does This Happen? (The "Rounding Error" Metaphor)

The paper argues this is due to finite precision.

The Metaphor: Imagine you are drawing a picture with a ruler that only has markings every millimeter. You can draw a straight line easily. But if you try to draw a very complex, long, winding path that requires you to turn at a point that is 0.0001 millimeters away from a mark, your ruler can't do it. You are forced to round to the nearest millimeter.
The Result: Over a long sequence, these tiny rounding errors accumulate. The AI's internal "pointer" drifts off the tiny, precise path required to write a specific long sentence, and it lands in a different zone, producing a different word.

Summary

Transformers are not infinite: They have a hard, mathematical limit on how many unique sequences they can generate.
It's a geometry problem: The limit comes from the shape and size of the "map" inside the AI and the fact that computers can't store infinite precision.
The "Cliff": Performance is great for short tasks but collapses abruptly for long tasks, not gradually.
It's fundamental: This isn't because the model is "dumb" or poorly trained. Even with infinite time and data, the architecture itself cannot generate most long sequences.

The paper concludes that this limitation is a fundamental property of the Transformer design, applying to all sizes of models, from small ones to the massive ones used today.

Technical Summary: How Many Different Outputs Can a Transformer Generate?

Problem Statement

Despite the empirical success of Transformers in natural language processing and computer vision, these models exhibit fundamental failures on simple algorithmic tasks, such as copying or repeating sequences, once the input length exceeds a certain threshold. While prior work has attributed these failures to training data or optimization issues, this paper posits that they stem from intrinsic architectural constraints. Specifically, the authors investigate the accessibility of output sequences: the set of all token sequences a Transformer can generate given any possible prompt (including optimized soft prompts) and arbitrary context length. The core question is: How many distinct sequences can a Transformer actually output, and how does this capacity scale with prompt length and model architecture?

Methodology

The authors approach the problem by analyzing the geometric constraints imposed by finite numerical precision and the bounded nature of internal representations within the Transformer architecture.

Mean-Field Formulation: To handle arbitrary prompt lengths, the authors interpret Transformers as mappings between probability measures (mean-field extension) rather than finite sequences. This leverages the permutation equivariance of attention layers.
Embedding Space Partitioning: The embedding space is partitioned into regions ( $E_t$ ) corresponding to the most likely next token (or sequence of tokens) based on the decoder's output projection.
Packing Number Analysis: The authors utilize the concept of packing numbers (the maximum number of disjoint balls of a given radius that can fit in a space) to quantify the number of distinct inputs a Transformer can distinguish.
- Finite Precision Assumption: They assume the Transformer has finite precision $\epsilon$ , meaning it cannot distinguish between inputs closer than $\epsilon$ (modeled as axis-aligned cubes or balls).
- Bounded Support: They assume the embedding support is contained within a bounded region (e.g., a ball of radius $r$ ).
Theoretical Derivation: By bounding the packing number of the input space relative to the volume of the embedding support, they derive upper bounds on the number of accessible sequences.
Empirical Validation: The theoretical predictions are tested using the "Cramming" task (Kuratov et al., 2025), where a frozen Transformer is conditioned on optimized soft prompts to generate specific target sequences. They also evaluate copying tasks to observe length-dependent generalization failures.

Key Contributions

1. Finite Accessibility of Sequences

The paper proves that a Transformer can output only a finite set of distinct sequences, regardless of the prompt length or inference strategy.

Theorem 4.5: For a Transformer with precision $\epsilon$ , embedding radius $r$ , and prompt length $m$ , the number of distinct accessible sequences is upper-bounded by $(1 + 2r/\epsilon)^{dm}$ .
Implication: Most sequences are fundamentally inaccessible; no choice of prompt can cause the model to generate them.

2. Linear Scaling and Exponential Decay

The authors establish a precise relationship between prompt length and the maximum length of accessible sequences:

Linear Growth: The maximal length $n$ of accessible sequences grows linearly with the prompt length $m$ ( $n \propto m$ ).
Exponential Decay: Beyond a critical threshold $N$ , the proportion of accessible sequences of length $n$ decays exponentially with $n$ .
Theoretical Threshold: They derive an explicit formula for this threshold: $n^* \approx C \cdot m$ , where $C$ depends on the embedding dimension $d$ , vocabulary size $|V|$ , precision $\epsilon$ , and support radius $r$ .

3. Explanation of Empirical Failures

The analysis provides a theoretical explanation for the "abrupt failure" observed in practice (e.g., perfect copying up to length $L$ , then total failure). The paper argues this is not a gradual degradation but a consequence of the exponential decay of accessible sequences beyond the critical threshold.

4. Refined Bounds via Geometry

The authors refine their theoretical upper bounds by relaxing the assumption of a uniform ball-shaped embedding support. They propose:

Anisotropic Supports: Modeling the support as cones or ellipsoids to better capture the actual distribution of embeddings.
Non-Uniform Cell Volumes: Accounting for the fact that common tokens occupy larger regions in the embedding space than rare tokens.
These refinements reduce the gap between theoretical upper bounds and empirical observations (from a factor of ~10 down to ~5–6).

Results

Theoretical Predictions

Corollary 4.6: For a fixed prompt budget $m$ , accessibility remains high up to a length $n^*(m)$ and then drops exponentially. The slope of this linear relationship is bounded by $C \leq \frac{d \ln(1 + 2r/\epsilon)}{\ln(|V|)}$ .
Corollary 4.10: Even with unbounded context and computation, there exists a threshold $N$ beyond which almost all sequences are inaccessible.

Empirical Validation

Cramming Task: Experiments on models (Pythia, Qwen-2.5, Llama-3.2, Gemma-3) show that the length $n_{50}$ (where accessibility drops to 50%) scales linearly with the number of trainable memory vectors $m$ ( $R^2 > 0.99$ ).
Slope Comparison: The empirically observed slopes are consistently lower than the theoretical upper bounds, with the ratio between theory and experiment ranging from 4.5 to 20.4 depending on the model and geometric assumptions used.
Copying Task: Models trained to copy sequences up to length 50 fail abruptly when tested on longer sequences, confirming the existence of a sharp accessibility threshold independent of prompt length.
Cell Volume Distribution: Analysis reveals that decoder cell volumes are highly skewed; a small set of frequent tokens (e.g., whitespace, punctuation) occupies a disproportionate fraction of the embedding space, which tightens the accessibility bounds compared to uniform assumptions.

Significance and Claims

The paper claims to provide the first rigorous theoretical explanation for the intrinsic limitations of Transformers on sequence generation tasks. Its significance lies in:

Architectural Limits: Demonstrating that the inability to copy long sequences is a fundamental property of the architecture's finite precision and bounded representations, not merely a training artifact.
Predictive Power: Offering a formula to predict the performance limits of a Transformer based solely on its embedding space geometry (dimension, vocabulary size, precision, and support shape), without needing to inspect the full parameter set.
Generalizability: The results extend beyond Transformers to any architecture with bounded internal representations and finite precision (e.g., State-Space Models like Mamba, though diverging hidden states present challenges).

The authors conclude that the embedding space, despite representing only a fraction of the model's parameters, carries meaningful information about the model's fundamental capabilities and limitations.