Exact sequence interpolation with transformers
Open Access
- 11 May 2026
- journal article
- research article
- Published by Springer Nature in Mathematical Foundations of Machine Learning
- Vol. 2 (1) , 2
Abstract
We prove that transformers can exactly interpolate datasets of finite input sequences in $$\mathbb {R}^d$$ , $$d\ge 2$$ , with corresponding output sequences of smaller or equal length. Specifically, given N sequences of arbitrary but finite lengths in $$\mathbb {R}^d$$ and output sequences of lengths $$m^1, \dots , m^N \in \mathbb {N}$$ , we construct a transformer with $$\mathcal {O}(\sum _{j=1}^N m^j)$$ blocks and $$\smash {\mathcal {O}(d \sum _{j=1}^N m^j)}$$ parameters that exactly interpolates the dataset. Our construction provides complexity estimates that are independent of the input sequence length, by alternating feed-forward and self-attention layers and by capitalizing on the clustering effect inherent to the latter. Our novel constructive method also uses low-rank parameter matrices in the self-attention mechanism, a common feature of practical transformer implementations. These results are first established in the hardmax self-attention setting, where the geometric structure permits an explicit and quantitative analysis, and are then extended to the softmax setting. Finally, we demonstrate the applicability of our exact interpolation construction to learning problems, in particular by providing convergence guarantees to a global minimizer under regularized training strategies. Our analysis contributes to the theoretical understanding of transformer models, offering an explanation for their excellent performance in exact sequence-to-sequence interpolation tasks.
Keywords
All Related Versions
Funding Information
- HORIZON EUROPE Marie Sklodowska-Curie Actions (101073558)
- HORIZON EUROPE Marie Sklodowska-Curie Actions, European Union (101073558)
- Alexander von Humboldt-Stiftung
- European Research Council (CoDeFeL)
- Ministerio de Economía y Competitividad
- Deutsche Forschungsgemeinschaft (Transregio 154 Project)
- Air Force Office of Scientific Research (24IOE027)
This publication has 20 references indexed in Scilit:
- Next-Token Prediction Capacity: General Upper Bounds and a Lower Bound for TransformersIEEE Transactions on Information Theory, 2025
- A mathematical perspective on transformersBulletin of the American Mathematical Society, 2025
- Interplay between depth and width for interpolation in neural ODEsNeural Networks, 2024
- Masked Autoencoders Are Scalable Vision Learners2022
- Error bounds for approximations with deep ReLU networksNeural Networks, 2017
- Approximation theory of the MLP model in neural networksActa Numerica, 1999
- Regularization of Inverse Problems1996
- Multilayer feedforward networks with a nonpolynomial activation function can approximate any functionNeural Networks, 1993
- Approximation capabilities of multilayer feedforward networksNeural Networks, 1991
- Approximation by superpositions of a sigmoidal functionMathematics of Control, Signals, and Systems, 1989