跳到正文
研踪PaperTrail
← 研踪 PaperTrail

arXiv:2502.02270 · v4

Exact Sequence Interpolation with Transformers

首次提交 2025-02-04 20:31
版本更新 2026-11-17 23:18
雷达观测 2026-11-18 16:38
arXiv ↗PDF ↗

摘要

We prove that transformers can exactly interpolate datasets of finite input sequences in Rd\mathbb{R}^d, d≥2d\geq 2, with corresponding output sequences of smaller or equal length. Specifically, given NN sequences of arbitrary but finite lengths in Rd\mathbb{R}^d and output sequences of lengths m1,…,mN∈Nm^1, \dots, m^N \in \mathbb{N}, we construct a transformer with O(∑j=1Nmj)\mathcal{O}(\sum_{j=1}^N m^j) blocks and O(d∑j=1Nmj)\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.

作者备注: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: https://doi.org/10.3030/101073558). Accompanying code available at: https://github.com/DCN-FAU-AvH/exactInterpTF, code DOI: https://doi.org/10.5281/zenodo.21107925

AI 论文解读

基于摘要 · 非全文审阅

此版本尚未生成 AI 解读。解读由后台任务生成并按论文版本保存,登录后共享已有结果。

版本差异

本站首次收录为 v4,暂无更早版本可对照。

观测到的版本

相邻记录可能跳过中间版本;首次发现 v2 及以上也会标为版本更新。

v4 · 2026-11-17 23:18 · 最新观测版本

Exact Sequence Interpolation with Transformers

We prove that transformers can exactly interpolate datasets of finite input sequences in Rd\mathbb{R}^d, d≥2d\geq 2, with corresponding output sequences of smaller or equal length. Specifically, given NN sequences of arbitrary but finite lengths in Rd\mathbb{R}^d and output sequences of lengths m1,…,mN∈Nm^1, \dots, m^N \in \mathbb{N}, we construct a transformer with O(∑j=1Nmj)\mathcal{O}(\sum_{j=1}^N m^j) blocks and O(d∑j=1Nmj)\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.

查看此版本解读 →查看此版本原文 ↗