# Exact Sequence Interpolation with Transformers

arXiv: https://arxiv.org/abs/2502.02270 · HTML: https://mlsanity.com/paper/2502.02270/

## Key facts

- Cited by 2 papers in the map (data through 14 Oct 2026).
- Builds on 31 of its 46 references that are in the map.
- First posted on arXiv 4 Feb 2025.

## Builds on (most cited first, 30 of 31)

- [Attention Is All You Need](https://mlsanity.com/paper/1706.03762/) (2017)
- [BERT: Pre-training of Deep Bidirectional Transformers for Language Understanding](https://mlsanity.com/paper/1810.04805/) (2018)
- [Adam: A Method for Stochastic Optimization](https://mlsanity.com/paper/1412.6980/) (2014)
- [An Image is Worth 16x16 Words: Transformers for Image Recognition at Scale](https://mlsanity.com/paper/2010.11929/) (2020)
- [GPT-4 Technical Report](https://mlsanity.com/paper/2303.08774/) (2023)
- [Masked Autoencoders Are Scalable Vision Learners](https://mlsanity.com/paper/2111.06377/) (2021)
- [Training Compute-Optimal Large Language Models](https://mlsanity.com/paper/2203.15556/) (2022)
- [BEiT: BERT Pre-Training of Image Transformers](https://mlsanity.com/paper/2106.08254/) (2021)
- [Train Short, Test Long: Attention with Linear Biases Enables Input Length Extrapolation](https://mlsanity.com/paper/2108.12409/) (2021)
- [Are Sixteen Heads Really Better than One?](https://mlsanity.com/paper/1905.10650/) (2019)
- [Error bounds for approximations with deep ReLU networks](https://mlsanity.com/paper/1610.01145/) (2016)
- [Are Transformers universal approximators of sequence-to-sequence functions?](https://mlsanity.com/paper/1912.10077/) (2019)
- [A mathematical perspective on Transformers](https://mlsanity.com/paper/2312.10794/) (2023)
- [The emergence of clusters in self-attention dynamics](https://mlsanity.com/paper/2305.05465/) (2023)
- [Small ReLU networks are powerful memorizers: a tight analysis of memorization capacity](https://mlsanity.com/paper/1810.07770/) (2018)
- [Deep Learning via Dynamical Systems: An Approximation Perspective](https://mlsanity.com/paper/1912.10382/) (2019)
- [Neural ODE control for classification, approximation and transport](https://mlsanity.com/paper/2104.05278/) (2021)
- [Are Transformers with One Layer Self-Attention Using Low-Rank Weight Matrices Universal Approximators?](https://mlsanity.com/paper/2307.14023/) (2023)
- [Transformers are Universal In-context Learners](https://mlsanity.com/paper/2408.01367/) (2024)
- [On the Optimal Memorization Power of ReLU Neural Networks](https://mlsanity.com/paper/2110.03187/) (2021)
- [Memorization Capacity of Multi-Head Attention in Transformers](https://mlsanity.com/paper/2306.02010/) (2023)
- [Provable Memorization via Deep Neural Networks using Sub-linear Parameters](https://mlsanity.com/paper/2010.13363/) (2020)
- [Clustering in Causal Attention Masking](https://mlsanity.com/paper/2411.04990/) (2024)
- [Sumformer: Universal Approximation for Efficient Transformers](https://mlsanity.com/paper/2307.02301/) (2023)
- [Measure-to-measure interpolation using Transformers](https://mlsanity.com/paper/2411.04551/) (2024)
- [Clustering in pure-attention hardmax transformers and its role in sentiment analysis](https://mlsanity.com/paper/2407.01602/) (2024)
- [Next-token prediction capacity: general upper bounds and a lower bound for transformers](https://mlsanity.com/paper/2405.13718/) (2024)
- [Interplay between depth and width for interpolation in neural ODEs](https://mlsanity.com/paper/2401.09902/) (2024)
- [Generic controllability of equivariant systems and applications to particle systems and neural networks](https://mlsanity.com/paper/2404.08289/) (2024)
- [Cluster-based classification with neural ODEs via control](https://mlsanity.com/paper/2312.13807/) (2023)

## Built on by (most cited first, 2 of 2)

- [Reachability and asymptotics of Gaussian Transformer dynamics](https://mlsanity.com/paper/2606.07600/) (2026)
- [Universal interpolation for deep residual self-attention networks](https://mlsanity.com/paper/2610.01981/) (2026)

## Abstract (arXiv)

We prove that transformers can exactly interpolate datasets of finite input sequences in ℝd, d≥ 2, with corresponding output sequences of smaller or equal length. Specifically, given N sequences of arbitrary but finite lengths in ℝd and output sequences of lengths m1, dots, mN ∈ mathbbN, we construct a transformer with O(sumj=1N mj) blocks and smashO(d sumj=1N mj) 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.