I don't know much about LLMs but does that mean you have N^2 computation with the context size since every token needs to track how it relates to every other token?
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).
This is incorrect. The compute required per forward pass to generate each additional token during decode will scales as O(N), even with a KV cache (without a KV cache, it would scale as O(N^2)). Over generating N tokens, it's O(N^2) with the cache (and O(N^3) without).
It's O(N) for a forward pass because that new token still has to "attend to" to each previous token. That requires N dot products: between the cached key vectors and the new query vector for the new position. You also have N reads from memory (K and V) which is probably gonna be your actual bottleneck. (Decode is memory-bound.)
This is why you should avoid long contexts, if you can, even with a warm cache. You will get charged more, in "cache read" tokens.