Summary
arXiv:2502.02270v4 Announce Type: replace-cross Abstract: We prove that transformers can exactly interpolate datasets of finite input sequences in $\mathbb{R}^d$, $d\geq 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-attentio…
Original text(via arXiv stat.ML)
Computer Science > Machine Learning
Title:Exact Sequence Interpolation with Transformers
Abstract:We prove that transformers can exactly interpolate datasets of finite input sequences in $\mathbb{R}^d$, $d\geq 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.
| Comments: | Funded by the European Union's HORIZON-MSCA-2021-DN-01-01, through the ModConFlex project ("Modelling and control of flexible structures interacting with fluids"; Grant Agreement No. 101073558; DOI: this https URL ). Accompanying code available at: this https URL , code DOI: this https URL |
|---|
| Subjects: | Machine Learning (cs.LG) ; Optimization and Control (math.OC); Machine Learning (stat.ML) |
| MSC classes: | 68T07, 68T50 |
| Cite as: | arXiv:2502.02270 [cs.LG] |
| (or arXiv:2502.02270v4 [cs.LG] for this version) |
| https://doi.org/10.48550/arXiv.2502.02270 arXiv-issued DOI via DataCite |
| Related DOI : | https://doi.org/10.1007/s44439-026-00005-y DOI(s) linking to related resources |
Submission history
The text above was extracted automatically from the source page and may miss images, tables or code blocks. The original is authoritative.
Published by arXiv stat.ML
This site only summarises and aggregates; copyright stays with the original author. Headlines and summaries follow the source — where they differ, the original wins.
Read the original ↗