transformer-quadratic-cost-context-window

IN premise — entries/2026/06/21/wiki-Transformer_deep_learning_architecture-chunk-1.md

Created 2026-06-21T09:50:11+00:00

Transformer attention computation scales quadratically O(n²) with context window size, unlike RNNs which scale linearly O(n) but cannot parallelize.

Summary

The core transformer architecture trades memory and compute for speed: it can process an entire sequence at once on modern hardware, but the cost of comparing every token to every other token grows dramatically as the sequence gets longer. This is the main reason doubling a context window costs roughly four times more compute, and it drives the ongoing research into cheaper attention mechanisms and longer-context models.

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