self-attention-quadratic-complexity
IN premise — entries/2026/06/21/wiki-Generative_pre-trained_transformer.md
Created 2026-06-21T09:50:09+00:00
Standard self-attention has quadratic complexity with respect to input sequence length
Summary
Every token in a sequence has to be compared against every other token, so doubling the input length quadruples the work. This is the core reason very long contexts become so expensive and why there is constant pressure to approximate or restructure attention to avoid that scaling wall.
Dependents
These beliefs depend on this one:
- IN quadratic-attention-drives-efficiency-research — Self-attention's O(n²) complexity is the root constraint driving both context window limitations and a proliferation of efficiency techniques (Flash Attention, sparse/linear variants, Performers).