Comment by TomatoCo

Yes, except no with the KV cache. Because tokens aren't modified by future tokens you can cache the meaning of previous tokens. This makes the total effort linear over the entire context (or constant per forward pass).