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

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 × 10-16 in float64), and the states are additive across chunks (5.7 × 10-14), so prefill admits a parallel scan. Measured exponents are t propto N2.28 for softmax against N0.91 for states, with a crossover at N ≈ 728 and 20.8× at N = 8192; per-token decoding latency is constant at 7.3,μs against N1.04 for softmax, giving 76.0× at N = 65536. Accuracy improves exponentially in n while cost grows combinatorially, since the m-th state is binomd+m-1m wide---a bound confirmed by SVD---so the optimum is second order, n = 3, at 6.5 × 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.