How does attention complexity scale with sequence length?

Self-attention has O(n²) time and memory complexity with sequence length.

Each token attends to every other token, producing quadratic scaling in both compute and memory. This is why long-context models require optimizations like sparse attention or linear attention.