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