Authors: Albert Alcalde, Giovanni Fantuzzi, Enrique Zuazua
Modern machine learning systems often process a large amount of input data to produce a short output. A document may contain thousands of words, yet a system may sort it into a single category. In a sentence with several missing words, we may ask for only those words. This is not limited to language. In computer vision, for example, an image can be split into hundreds of patches while the model is asked for one category.
Transformers, the architecture behind large language models (LLMs), are particularly effective on problems of this kind. Their success is well known, but some of the mathematical reasons for it are still being worked out. In recent work [1], we studied a basic version of this question: given a finite collection of input sequences and the output sequence assigned to each of them, can a transformer reproduce all of these pairs exactly?
This is what is known as an interpolation problem. Instead of trying to describe everything a trained language model does, we isolate one capability of the architecture, namely its memorization ability. This approach also makes it possible to ask a quantitative question: once we have the ability to interpolate, how large must the transformer be?
The length that matters
Suppose the data contain N input sequences. The j-th input may be long, while its target output contains only m_j elements, called tokens. In our paper, we construct a transformer that matches every pair exactly. Crucially, the number of trainable parameters grows with the embedding dimension and with the total number of output tokens \sum_{j=1}^N m_j, but not with the input lengths themselves.
This distinction is important, yet it does not say that long sequences are cheap to process: standard self-attention still has a computational cost that grows quadratically with sequence length. Instead, the result concerns model size for this memorization problem. In the construction, a long input does not force a proportionally larger set of trainable parameters when the desired output is short.
This is the regime of many familiar tasks, including classification, summarization, and masked prediction. The theorem includes these examples as special cases. They give the right intuition: the model has to read a large object and retain only the small amount of information needed in the output.
The geometry of self-attention
The proof views each token as a point in a high-dimensional space. Feed-forward layers move tokens individually, whereas self-attention couples their motion. With suitable parameters, tokens can form clusters, collapse to selected points, or remain separated. This lets the construction replace a long input with a controlled number of representatives, as illustrated in Figure 1.
The full construction has four stages, alternating self-attention and feed-forward layers:
1. Separation: tokens belonging to different training sequences are separated whenever they overlap.
2. Leader selection: the transformer selects exactly as many leaders in each sequence as the output requires.
3. Collapse: self-attention collapses the remaining tokens onto those leaders.
4. Interpolation: feed-forward layers move the surviving representatives to the prescribed output tokens.
Figure 1. Depending on the geometric configuration, the action of self-attention can make tokens converge to a few clusters, collapse to one point, or remain separated.
The argument is easiest to see first with hardmax attention, an idealized rule that selects the strongest interaction exactly. The construction is then adapted to the more practical softmax case, which requires an additional step that uses ReLU feed-forward layers to remove the residual error and recover exact interpolation.
Figure 2. Illustration of the constructive sequence interpolation proof of [1].
Why attention helps
Without self-attention, a feed-forward network processes every token independently and cannot generally distinguish sequences that share tokens but have different outputs. Flattening a sequence for a residual network avoids this limitation, but makes the relevant dimension grow with input length. Transformers instead preserve token structure while using nonlocal interactions to separate and compress the sequence, so their parameter estimate can scale with the typically much shorter output length.
A consequence for training
The existence of an exact interpolant also gives a simple consequence for regularized training of these architectures. For a Tikhonov-regularized objective [2], a global minimizer cannot have an objective value larger than the regularization penalty evaluated at an exact interpolating solution. As the regularization strength tends to zero, this gives a linear upper bound on the optimal loss.
Numerical experiments in the paper illustrate this scaling. Specifically, they show how an approximation result can impose a quantitative benchmark on optimization once an exact solution is known to exist. This can be useful in practice, since the loss is often the only quantity that can be monitored during training.
Figure 3. A synthetic training experiment compares the regularized loss with the theoretical bound and shows the predicted near-linear scaling with the regularization parameter $\varepsilon$.
What remains open
Our theoretical construction gives a concrete picture of why transformers are well suited to longinput, short-output tasks, but it does not describe the behavior of a particular trained model. Open questions include whether exact interpolation can be achieved with less depth, how parameter magnitudes depend on token separation, and how multi-head or causal attention changes the construction. These questions become increasingly relevant as the context length of LLMs continues to grow.
References
[1] A. Alcalde, G. Fantuzzi, and E. Zuazua, “Exact sequence interpolation with transformers,” Mathematical Foundations of Machine Learning 2:2 (2026), DOI: 10.1007/s44439-026-00005-y.[2] H. W. Engl, M. Hanke, and A. Neubauer, Regularization of Inverse Problems, Mathematics and Its Applications, vol. 375, Springer, Dordrecht (1996).