EUVIMEDEUVIMED entdecken
Open Access · CC BY 4.0

Computational Complexity of Self-Attention Algorithms for Efficient Transformer Architectures

Akinyemi Omololu Akinrotimi, Sunday Olusegun Ojo

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).

AbstractBibliografische AngabenZitierenVerwandte Studien

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}
}
Kostenlos starten →