# Learnable Low-Rank Polynomial Sketch for Effective Linear Attention

arXiv: https://arxiv.org/abs/2610.14219 · HTML: https://mlsanity.com/paper/2610.14219/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 27 of its 33 references that are in the map.
- First posted on arXiv 9 Oct 2026.

## Builds on (most cited first, 27 of 27)

- [Think you have Solved Question Answering? Try ARC, the AI2 Reasoning Challenge](https://mlsanity.com/paper/1803.05457/) (2018)
- [Mamba: Linear-Time Sequence Modeling with Selective State Spaces](https://mlsanity.com/paper/2312.00752/) (2023)
- [SQuAD: 100,000+ Questions for Machine Comprehension of Text](https://mlsanity.com/paper/1606.05250/) (2016)
- [HellaSwag: Can a Machine Really Finish Your Sentence?](https://mlsanity.com/paper/1905.07830/) (2019)
- [PIQA: Reasoning about Physical Commonsense in Natural Language](https://mlsanity.com/paper/1911.11641/) (2019)
- [The Pile: An 800GB Dataset of Diverse Text for Language Modeling](https://mlsanity.com/paper/2101.00027/) (2020)
- [Transformers are RNNs: Fast Autoregressive Transformers with Linear Attention](https://mlsanity.com/paper/2006.16236/) (2020)
- [Rethinking Attention with Performers](https://mlsanity.com/paper/2009.14794/) (2020)
- [The LAMBADA dataset: Word prediction requiring a broad discourse context](https://mlsanity.com/paper/1606.06031/) (2016)
- [RWKV: Reinventing RNNs for the Transformer Era](https://mlsanity.com/paper/2305.13048/) (2023)
- [Long Range Arena: A Benchmark for Efficient Transformers](https://mlsanity.com/paper/2011.04006/) (2020)
- [Gated Delta Networks: Improving Mamba2 with Delta Rule](https://mlsanity.com/paper/2412.06464/) (2024)
- [Linear Transformers Are Secretly Fast Weight Programmers](https://mlsanity.com/paper/2102.11174/) (2021)
- [Nystr"omformer: A Nystr"om-Based Algorithm for Approximating Self-Attention](https://mlsanity.com/paper/2102.03902/) (2021)
- [Sketching as a Tool for Numerical Linear Algebra](https://mlsanity.com/paper/1411.4357/) (2014)
- [cosFormer: Rethinking Softmax in Attention](https://mlsanity.com/paper/2202.08791/) (2022)
- [Simple linear attention language models balance the recall-throughput tradeoff](https://mlsanity.com/paper/2402.18668/) (2024)
- [Kimi Linear: An Expressive, Efficient Attention Architecture](https://mlsanity.com/paper/2510.26692/) (2025)
- [FLatten Transformer: Vision Transformer using Focused Linear Attention](https://mlsanity.com/paper/2308.00442/) (2023)
- [On The Computational Complexity of Self-Attention](https://mlsanity.com/paper/2209.04881/) (2022)
- [Language Models Enable Simple Systems for Generating Structured Views of Heterogeneous Data Lakes](https://mlsanity.com/paper/2304.09433/) (2023)
- [Skyformer: Remodel Self-Attention with Gaussian Kernel and Nystr"om Method](https://mlsanity.com/paper/2111.00035/) (2021)
- [PolySketchFormer: Fast Transformers via Sketching Polynomial Kernels](https://mlsanity.com/paper/2310.01655/) (2023)
- [Never Train from Scratch: Fair Comparison of Long-Sequence Models Requires Data-Driven Priors](https://mlsanity.com/paper/2310.02980/) (2023)
- [PolaFormer: Polarity-aware Linear Attention for Vision Transformers](https://mlsanity.com/paper/2501.15061/) (2025)
- [Automatic Unsupervised Tensor Mining with Quality Assessment](https://mlsanity.com/paper/1503.03355/) (2015)
- [EUGens: Efficient, Unified, and General Dense Layers](https://mlsanity.com/paper/2601.22563/) (2026)

## Abstract (arXiv)

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 Learnable Low-Rank Polynomial Sketch (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.