Standard transformer attention mechanisms face a fundamental scalability bottleneck in long-context scenarios. The quadratic complexity with respect to sequence length, denoted as $O(N^2 \cdot d)$ where $N$ represents the sequence length and $d$ the feature dimension, imposes significant computational and memory overhead. This challenge becomes particularly pronounced when processing context windows exceeding tens of thousands of tokens, where the attention score matrix computation itself dominates the inference latency budget. Various approximation techniques have been proposed, ranging from linear attention formulations to low-rank decomposition methods. Among these approaches, the symmetry-aware Taylor approximation stands out for its mathematical elegance and practical efficiency gains.
Leveraging Symmetry in Attention Matrices
The core observation that enables symmetry-aware approximation lies in the structural properties of causal attention matrices. In autoregressive language models, the attention pattern exhibits a distinctive triangular constraint: each token can only attend to preceding positions. This constraint implies that attention weights depend solely on the relative distance between query and key positions, not on their absolute indices. Mathematically, this manifests as a Toeplitz structure in the attention matrix, where entries are constant along diagonals. When computing attention scores, this symmetry allows for significant parameter reduction, as the same kernel function can be reused for all position pairs separated by identical offsets.
Consider the standard softmax attention formulation where attention weights are computed as $\text{softmax}\left(\frac{Q K^T}{\sqrt{d}}\right)$. In the causal setting, the effective attention matrix maintains a banded structure with bandwidth equal to the current sequence position. By exploiting this symmetry, we can avoid redundant computations that would otherwise treat each position pair as unique. The symmetry is not merely a computational convenience but reflects the underlying inductive bias of autoregressive models, which prioritize relative positional relationships over absolute encoding in many downstream tasks.
Taylor Series Expansion for Exponential Kernels
The exponential function embedded in softmax, specifically $\exp(q \cdot k)$, poses the primary computational challenge. Direct evaluation of this kernel for all query-key pairs requires $O(N^2)$ operations. Taylor series expansion provides a systematic approximation by replacing the exponential with a truncated polynomial of degree $K$: $\exp(x) \approx \sum_{k=0}^{K} \frac{x^k}{k!}$. This polynomial approximation transforms the kernel computation into a series of element-wise multiplications and summations, which can be efficiently vectorized and potentially precomputed for recurrent evaluation.
The approximation error introduced by truncation depends on both the magnitude of the input $x = q \cdot k / \sqrt{d}$ and the chosen polynomial degree. For typical query and key vectors in modern transformer architectures, the dot products are often centered around zero with bounded variance, making low-order approximations surprisingly effective. Empirically, a third-order or fifth-order Taylor polynomial captures over 95% of the softmax mass in most practical scenarios, with errors becoming negligible for positions with low attention weight allocation. The truncation order $K$ thus serves as a tunable hyperparameter balancing approximation fidelity against computational savings.
Achieving O(1) Per-Token Complexity
The combination of symmetry exploitation and Taylor approximation enables a constant-time-per-token computation pattern. Rather than maintaining and updating the full attention matrix, the algorithm maintains a compact state vector representing the accumulated polynomial features. When a new token arrives, its contribution to the attention output is computed by evaluating the Taylor polynomial using the precomputed state and the incoming query vector. This evaluation requires only $O(K \cdot d)$ operations, independent of the current sequence length $N$.
The key engineering insight is the recursive nature of the state update. For a Taylor expansion of degree $K$, we maintain $K+1$ state vectors, each corresponding to a power of the accumulated key features. Upon processing a new key vector $k_t$, the state updates as $s^{(m)}{t} = s^{(m)}{t-1} + (k_t)^{\odot m}$ for $m = 0 \dots K$, where $\odot m$ denotes element-wise power. The query processing then computes the attention output as a dot product between the query vector and each state component, weighted by the Taylor coefficients. This formulation completely eliminates the need for explicit attention matrix materialization.
Practical Implementation Parameters and Trade-offs
Implementing symmetry-aware Taylor approximation requires careful consideration of several engineering parameters. The polynomial degree $K$ typically ranges from 3 to 5 in deployed systems, with higher values offering better accuracy at the cost of proportional computation increase. For most language model inference workloads, $K=3$ provides an excellent accuracy-efficiency trade-off, reducing attention computation latency by a factor of 5-10x compared to standard softmax attention while maintaining perplexity degradation below 0.5%.
Memory footprint optimization involves strategically batching the state vector updates. Since the state components are independent, they can be updated concurrently on modern GPU architectures. Numerical stability considerations suggest applying a scaling factor $\sqrt{d}$ within the Taylor polynomial evaluation to prevent overflow in higher-order terms. Additionally, maintaining a running estimate of the maximum attention score enables dynamic coefficient normalization, compensating for approximation drift over extremely long contexts.
The approach does carry inherent limitations worth acknowledging. Non-causal attention patterns, such as those used in encoder-only models or bidirectional reasoning tasks, do not exhibit the same symmetry properties and thus cannot benefit directly from this technique. Similarly, tasks relying heavily on precise absolute positional information may experience accuracy degradation under the symmetry assumption.
Conclusion and Future Directions
Symmetry-aware Taylor approximation represents a principled approach to reducing transformer inference costs in long-context scenarios. By mathematically exploiting the structural properties of causal attention and systematically approximating the exponential kernel, this technique achieves constant per-token computational complexity while preserving model quality. Future research directions include adaptive polynomial degree selection based on per-position confidence estimates and hybrid approaches that selectively apply exact attention for critical token positions.
资料来源：本文算法原理基于线性注意力（Katharopoulos et al., 2020）与核方法近似注意力（Choromanski et al., 2020）的研究范式，具体参数建议参考泰勒展开在指数函数数值逼近中的标准误差界分析。