>the compute cost still scales O(n²) for n tokens,

That is never the cost, it's a common misconception.

Cost scales linearly per tokens. Unless you are sending one token at a time and avoiding using the same machine or cache.

Just look at api charges, they are charged by token, not by token squared.