On The Computational Complexity of Self-Attention

2022/09/11 by Feyza Duman Keles, Keles, Feyza Duman, Pruthuvi Mahesakya Wijewardena +3 · 25 citations
Computer Science · Engineering · #Advanced Memory and Neural Computing #Computational Complexity (cs.CC) #FOS: Computer and information sciences #Machine Learning (cs.LG) #Neural Networks and Reservoir Computing #Semiconductor materials and devices

paper · pdf · doi:10.48550/arxiv.2209.04881

openalex publication_date 2022/09/11 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

Transformer architectures have led to remarkable progress in many state-of-art applications. However, despite their successes, modern transformers rely on the self-attention mechanism, whose time- and space-complexity is quadratic in the length of the input. Several approaches have been proposed to speed up self-attention mechanisms to achieve sub-quadratic running time; however, the large majority of these works are not accompanied by rigorous error guarantees. In this work, we establish lower bounds on the computational complexity of self-attention in a number of scenarios. We prove that the time complexity of self-attention is necessarily quadratic in the input length, unless the Strong Exponential Time Hypothesis (SETH) is false. This argument holds even if the attention computation is performed only approximately, and for a variety of attention mechanisms. As a complement to our lower bounds, we show that it is indeed possible to approximate dot-product self-attention using finite Taylor series in linear-time, at the cost of having an exponential dependence on the polynomial order.

Cited by

• Deep learning for pedestrians: backpropagation in Transformers
• SSCATeR: Sparse Scatter-Based Convolution Algorithm with Temporal Data Recycling for Real-Time 3D Object Detection in LiDAR Point Clouds
• Everything is Context: Agentic File System Abstraction for Context Engineering
• Cache What Lasts: Token Retention for Memory-Bounded KV Cache in LLMs
• CAMformer: Associative Memory is All You Need
• Scaling Self-Supervised and Cross-Modal Pretraining for Volumetric CT Transformers
• Small Language Models for Phishing Website Detection: Cost, Performance, and Privacy Trade-Offs
• Mamba4Net: Distilled Hybrid Mamba Large Language Models For Networking
• Predicting Task Performance with Context-aware Scaling Laws
• Breadcrumbs Reasoning: Memory-Efficient Reasoning with Compression Beacons
• Schema for In-Context Learning
• PISA: A Pragmatic Psych-Inspired Unified Memory System for Enhanced AI Agency
• CacheClip: Accelerating RAG with Effective KV Cache Reuse
• RegexPSPACE: A Benchmark for Evaluating LLM Reasoning on PSPACE-complete Regex Problems
• Extending ResourceLink: Patterns for Large Dataset Processing in MCP Applications
• Untangling Component Imbalance in Hybrid Linear Attention Conversion Methods
• Elucidating the Design Space of FP4 training
• AQUA: Attention via QUery mAgnitudes for Memory and Compute Efficient Inference in LLMs
• Adaptive Token Merging for Efficient Transformer Semantic Communication at the Edge
• Adaptive Pareto-Optimal Token Merging for Edge Transformer Models in Semantic Communication
• Fast attention mechanisms: a tale of parallelism
• The Token Tax: Systematic Bias in Multilingual Tokenization
• TrimTokenator: Towards Adaptive Visual Token Pruning for Large Multimodal Models
• Improved Algorithms for Kernel Matrix-Vector Multiplication Under Sparsity Assumptions
• Semantic Segmentation of iPS Cells: Case Study on Model Complexity in Biomedical Imaging

Related

• FAST: Factorizable Attention for Speeding up Transformers
• Conv-Linformer: Boosting Linformer's Performance with Convolution in Small-Scale Settings
• kNN Attention Demystified: A Theoretical Exploration for Scalable Transformers
• Stable, Fast and Accurate: Kernelized Attention with Relative Positional Encoding
• Fast Monte-Carlo Approximation of the Attention Mechanism