Quasi Linear Kernel Attention with Infinite Capacity
Abstract
The evaluation cost of transformers with softmax attention scales quadratically with sequence length. Kernel attention addresses this by replacing softmax with a more general kernel function. In this paper, we aim to identify kernels that retain the expressivity of attention while enabling quasi linear computation. To quantify expressivity, we introduce a capacity for each kernel, measuring the maximum sequence length for which the attention matrix can approximate the identity. A higher capacity thus indicates greater expressivity. We show that expressive kernels like softmax, Gauss, and Laplace have infinite capacity. In contrast, common quasi linear kernels, such as those derived from finite dimensional feature maps, exhibit finite capacity. As a solution, we propose additive kernels constructed from univariate spline and polynomial exponential kernels. We prove that these maintain infinite capacity while allowing quasi linear computation via sorting. Finally, we implement additive sorting kernels efficiently and benchmark them against modern softmax backends, demonstrating advantages for long sequences.
Related
- Infinite-Dimensional Spherical Kernel ridge Regression
- Boundary Kernel Rigidity and Infinite-Dimensional Complex Hyperbolic Representations
- Kernel--wreath constructions and infinite families of finite simple skew braces
- Flow-based Spectral Kernel Learning for Nonstationary Attention
- Kernel-based Interpolatory Methods for Context Compression of Attention Mechanisms
BibTeX
@misc{rux2026quasi,
title = {{Quasi Linear Kernel Attention with Infinite Capacity}},
author = {Nicolaj Rux and Johannes Hertrich and Sebastian Neumayer},
howpublished = {arXiv},
year = {2026},
month = sep,
doi = {10.48550/arxiv.2609.35349},
eprint = {2609.35349},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2609.35349},
}
RIS
TY - UNPB
TI - Quasi Linear Kernel Attention with Infinite Capacity
AU - Nicolaj Rux
AU - Johannes Hertrich
AU - Sebastian Neumayer
PY - 2026
DA - 2026/09/28
PB - arXiv
DO - 10.48550/arxiv.2609.35349
UR - https://arxiv.org/abs/2609.35349
AB - The evaluation cost of transformers with softmax attention scales quadratically with sequence length. Kernel attention addresses this by replacing softmax with a more general kernel function. In this paper, we aim to identify kernels that retain the expressivity of attention while enabling quasi linear computation. To quantify expressivity, we introduce a capacity for each kernel, measuring the maximum sequence length for which the attention matrix can approximate the identity. A higher capacity thus indicates greater expressivity. We show that expressive kernels like softmax, Gauss, and Laplace have infinite capacity. In contrast, common quasi linear kernels, such as those derived from finite dimensional feature maps, exhibit finite capacity. As a solution, we propose additive kernels constructed from univariate spline and polynomial exponential kernels. We prove that these maintain infinite capacity while allowing quasi linear computation via sorting. Finally, we implement additive sorting kernels efficiently and benchmark them against modern softmax backends, demonstrating advantages for long sequences.
ER -