AI & ML
Exact Sequence Interpolation with Transformers
arXiv stat.ML0 views
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-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.
Source:https://arxiv.org/abs/2502.02270PreviousClustering in pure-attention hardmax transformers and its role in sentiment analysisNextFunctional Compression as Occam's Razor: Algebraic Complexity from Sensitivity Minimization
Related posts
Monitoring SPF, DKIM and DMARC Drift in CI
0dev.to DevOps
Software Could Turn Edge AI Chips Into Shared Workstations
0dev.to Docker

Tencent reports Q3 revenue up 8% YoY to ~$31.1B, below est., and operating profit down 7% in its first earnings decline in years, as AI capex surges 5x to ~$12B (Bloomberg)
0Techmeme

KPMG uses 100+ AI agents to conduct a parallel audit of a FTSE 250 company in a pilot, saying the AI asked "better questions" and dug deeper than human staff (Financial Times)
0Techmeme

GTA VI review: an unparalleled technical and comedic masterpiece, with elaborate depictions of a heightened reality and an unpredictable environment by design (Jason Schreier/Bloomberg)
0Techmeme

Sony and Rockstar say a new PS5 firmware update is mandatory to play GTA VI ahead of its November 19 launch; the update aims to combat rapid homebrew exploits (Wesley Yin-Poole/IGN)
0Techmeme