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

arXiv:2610.20637v1 Announce Type: new Abstract: We expand the exponential kernel of attention into a truncated Taylor series of n terms and factorize each term into a tensor-power inner product, which collapses the causal history into exactly n recurrent states, each updated by one rank-one outer product per token and independent of context length N. The recursion is lossless with respect to the truncated kernel (2.2 imes 10^{-16} in float64), and the states are additive across chunks (5.7 imes 10^{-14}), so prefill admits a parallel scan. Measured exponents are t propto N^{2.28} for softmax against N^{0.91} for states, with a crossover at N approx 728 and 20.8imes at N = 8192; per-token decoding latency is constant at 7.3,mus against N^{1.04} for softmax, giving 76.0imes at N = 65536. Accuracy improves exponentially in n while cost grows combinatorially, since the m-th state is inom{d+m-1}{m} wide---a bound confirmed by SVD---so the optimum is second order, n = 3, at 6.5 imes 10^{-4} error and 9{,}945 elements per head. Query and key normalization is a prerequisite: without it the argument exceeds the convergence radius and adding terms stops helping.

Source: arXiv cs.LG | 2026-10-16