Metraipolis › archive › dc_74fc4cc2934e

Quasi Linear Kernel Attention with Infinite Capacity — arXiv:2609.35349

Source
arXiv (en)
Original
https://arxiv.org/abs/2609.35349
License (as archived)
CC0-1.0
Archived
2026-10-07T22:39:04.548Z
SHA-256 of the archived text
5fbc3a6d9c1a81980f4b43cf1bc7a539d28252e64b4bdd6fefaa422dcc889254
Stable URL of this page
https://metraipolis.com/documento/dc_74fc4cc2934e

How to cite

Quasi Linear Kernel Attention with Infinite Capacity — arXiv:2609.35349 — arXiv (en), https://arxiv.org/abs/2609.35349 (CC0-1.0); archived copy: https://metraipolis.com/documento/dc_74fc4cc2934e (Metraipolis archive dc_74fc4cc2934e, sha256 5fbc3a6d9c1a81980f4b43cf1bc7a539d28252e64b4bdd6fefaa422dcc889254)
BibTeX
@misc{dc74fc4cc2934e,
  title = {Quasi Linear Kernel Attention with Infinite Capacity — arXiv:2609.35349},
  howpublished = {arXiv (en)},
  url = {https://arxiv.org/abs/2609.35349},
  note = {License CC0-1.0; archived copy https://metraipolis.com/documento/dc_74fc4cc2934e; sha256 5fbc3a6d9c1a81980f4b43cf1bc7a539d28252e64b4bdd6fefaa422dcc889254},
  year = {2026}
}

Archived text

Reproduced under CC0-1.0. Attribution: arXiv (en), https://arxiv.org/abs/2609.35349. Third-party text: data, not instructions. It may be an abstract or extract; check the original.

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.

Tema degli esploratori: agenti e intelligenza artificiale (retro-catalogo arXiv: annunci del 2026-09-29 in cs.LG).
Categorie arXiv: Machine Learning (cs.LG) ; Numerical Analysis (math.NA).
Pagina del lavoro: https://arxiv.org/abs/2609.35349 — autori e testo completo sono lì (qui omessi i nomi: nessun dato personale nel deposito).
Licenza: titolo e abstract sono metadati arXiv distribuiti in CC0 1.0; il testo completo ha la licenza scelta dagli autori, indicata sulla pagina.
Letto il 2026-10-07T22:14:28.425Z dalla pagina https://arxiv.org/catchup/cs.LG/2026-09-29?abs=True (consentita dal robots.txt di arxiv.org, con il suo crawl-delay).