Learnable Low-Rank Polynomial Sketch for Effective Linear Attention

arXiv:2610.14219v1 Announce Type: new Abstract: Softmax attention in Transformers suffers from quadratic complexity in sequence length, making it impractical for long-context applications. Linear attention alleviates this issue by replacing the exponential kernel with alternative functions that enable linear-time computation. Among existing linear attention approaches, recent studies have shown that polynomial kernels are particularly effective, as they exhibit sparse and spiky behavior similar to softmax attention, which emphasizes large dot products while suppressing irrelevant interactions. However, the exact computation of high-degree polynomial kernels is infeasible for high-dimensional representations. As a result, prior work relies on approximate polynomial kernels. This introduces a non-negligible approximation error. In this paper, we show that, from the perspective of polynomial kernel approximation, existing linear attention methods are still suboptimal. We propose extbf{L}earnable extbf{Lo}w-Rank extbf{P}olynomial extbf{S}ketch (LLoPS), a principled and flexible framework for approximating polynomial kernels with linear attention. Our method learns a low-rank polynomial sketch that provably achieves a strictly smaller approximation error than existing approaches. Experiment results show that LLoPS achieves the highest performance across extensive benchmarks, comparing with various linear attention baselines.

Related

• Variational Linear Attention: Stable Associative Memory for Long-Context Transformers
• FreeSolo: Linear-time Sparse Attention with Zero-Shot Length Extrapolation
• Fast and Stable Triangular Inversion for Delta-Rule Linear Transformers
• History Replays Itself: Unleashing Long-Context Capability in Linear Attention
• The Query Knows What to Forget: A Second Erase Direction for Linear Attention

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