aiqbench analysis
The paper targets the quadratic cost of softmax attention in Transformers by approximating polynomial kernels for linear attention, and it claims a learned low-rank sketch reduces approximation error relative to prior methods. The provable error bound and benchmark gains are the claims to verify, since the abstract gives no quantitative results. For practitioners, the key question is whether the accuracy gains hold at real long-context scales and with acceptable speed and memory overhead.
Learnable Low-Rank Polynomial Sketch for Effective Linear Attention
arXiv:2610.14219v1 Announce Type: cross 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 \textbf{L}earnable \textbf{Lo}w-Rank \textbf{P}olynomial \textbf{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.
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 \textbf{L}earnable \textbf{Lo}w-Rank \textbf{P}olynomial \textbf{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.
Machine Learning (cs.LG); Artificial Intelligence (cs.AI); Computation and Language (cs.CL)
arXiv:2610.14219 [cs.LG]
(or arXiv:2610.14219v1 [cs.LG] for this version)
https://doi.org/10.48550/arXiv.2610.14219 Focus to learn more arXiv-issued DOI via DataCite (pending registration)
arXivLabs is a framework that allows collaborators to develop and share new arXiv features directly on our website.
Both individuals and organizations that work with arXivLabs have embraced and accepted our values of openness, community, excellence, and user data privacy. arXiv is committed to these values and only works with partners that adhere to them.
Have an idea for a project that will add value for arXiv's community? Learn more about arXivLabs.
Full text under the publisher's open licence · 274 words
Related coverage
Generalization and infinite width
LessWrong · Aug 1, 2026
Game Design Creativity evals
LessWrong · Oct 12, 2026
PIRAMID: Progress and Plans
LessWrong · Jul 27, 2026
Provable Transformer Context Compression for In-Context Reinforcement Learning
arXiv · Oct 15, 2026