2 ms·

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 line

• ex-aws-dude 25d ago
  I see and is there only 1 layer of relations? Or does it accumulate the relations like A relates to B, so also add in B's relations
  • TomatoCo 23d ago
    Well, I'm under the impression that the relations are recursive but you skip computing them recursively by caching B's relations. However if you look at your sibling comments you'll see that I may not have the right grasp on the matter.
• libraryofbabel 25d ago
  > 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.
  • TomatoCo 23d ago
    I was under the impression that each new token attends to one previous token per attention head, and that the slowdown observed was more because those attended to tokens are more spread out in memory and get less memory-architecture-style cache hits.