Expanding Attention: A Taylor-Series Route to Linear-Time Transformers with a Fixed Number of Recurrent States

arXiv:2610.20637v1 公告类型：新

摘要：我们将注意力的指数核展开为包含 $n$ 项的截断泰勒级数，并将每一项分解为张量幂内积，从而将因果历史压缩为恰好 $n$ 个循环状态，每个状态由每个 token 的一次秩一外积更新，且与上下文长度 $N$ 无关。该递推相对于截断核是无损的（float64 下为 $2.2 \times 10^{-16}$），且状态在分块之间可加（$5.7 \times 10^{-14}$），因此预填充可采用并行扫描。实测指数为：softmax 为 $t \propto N^{2.28}$，而状态为 $N^{0.91}$，交叉点在 $N \approx 728$，在 $N = 8192$ 时为 $20.8\times$；每 token 解码延迟恒定为 $7.3\,\mu$s，而 softmax 为 $N^{1.04}$，在 $N = 65536$ 时为 $76.0\times$。精度随 $n$ 呈指数级提升，而成本呈组合式增长，因为第 $m$ 个状态的宽度为 $\binom{d+m-1}{m}$——该上界经 SVD 确认——因此最优解为二阶，即 $n = 3$，误差为 $6.5 \times 10^{-4}$，每个头 $9{,}945$ 个元素。查询与键的归一化是前提条件：缺少该步骤时，参数将超出收敛半径，增加项数不再有帮助。