Computational Complexity of Self-Attention Algorithms for Efficient Transformer Architectures
Computers · 10.11.2026 · 15 (11) · 821
DOI: 10.3390/computers15110821 ↗Kurz gefasst
Fachartikel in der Zeitschrift Computers, online erschienen am 10.11.2026. Verfasst von Akinyemi Omololu Akinrotimi und 1 weiteren Autor:innen. Die Arbeit nennt 19 Literaturangaben. Der Volltext ist frei zugänglich (Open Access, CC BY 4.0).
Abstract (Originalsprache)
Self-attention is fundamental to Transformer architectures, but its computational and memory requirements grow quadratically with sequence length. This paper presents a structured narrative review of computationally efficient self-attention algorithms. It establishes the mathematical foundations of standard self-attention and examines dense, sparse/local, low-rank projection, landmark/Nyström, kernel/linear, memory-efficient exact, and hierarchical mechanisms. The review compares these approaches in terms of arithmetic complexity, memory requirements, sequence-length scaling, approximation, connectivity, I/O behaviour, implementation overhead, and hardware dependence. It distinguishes algorithmic complexity reduction from implementation-level optimization and clarifies the conditions under which complexity is linear in sequence length. Analytical crossover conditions show how sequence length, representation dimension, mechanism-specific parameters, and implementation overhead influence practical advantage. The review demonstrates that efficient attention cannot be characterized solely as quadratic versus linear complexity and identifies research gaps in multidimensional complexity modelling, approximation-error trade-offs, I/O complexity, long-range dependency preservation, Pareto efficiency, and hardware-aware analysis.
Zitieren
APA
Akinrotimi, A. O., & Ojo, S. O. (2026). Computational Complexity of Self-Attention Algorithms for Efficient Transformer Architectures. Computers, 15(11), 821. https://doi.org/10.3390/computers15110821
Vancouver
Akinrotimi AO, Ojo SO. Computational Complexity of Self-Attention Algorithms for Efficient Transformer Architectures. Computers. 2026;15(11):821. doi:10.3390/computers15110821
BibTeX
@article{Akinrotimi2026,
author = {Akinrotimi, Akinyemi Omololu and Ojo, Sunday Olusegun},
title = {Computational Complexity of Self-Attention Algorithms for Efficient Transformer Architectures},
journal = {Computers},
year = {2026},
volume = {15},
number = {11},
pages = {821},
doi = {10.3390/computers15110821}
}
EUVIMED