4 ms·

Low precision: agreed Attention: Isn't it quadratic in context length? I dunno, this feels like the crude first iteration of something that will get inevitably

Low precision: agreed Attention: Isn't it quadratic in context length? I dunno, this feels like the crude first iteration of something that will get inevitably passed by something that scales better.

dpflan 4y ago
Sharing a comment from a similar line of discussion: """ Complexity is quadratic in sequence length. For 512 tokens it is 262K, but for 4000 tokens it becomes 16M and goes OOM on a single GPU. We need about 100K-1M tokens to load whole books at once. Since 2017 there have been hundreds of attempts to bring O(N^2) to O(N), but none of them replaced the vanilla attention yet in large models. They lose on accuracy. Maybe Flash attention has a shot (https://arxiv.org/abs/2205.14135 https://arxiv.org/abs/2205.14135). """ - source: https://news.ycombinator.com/item?id=34171503 https://news.ycombinator.com/item?id=34171503
- whimsicalism 4y ago
  There is literally no way that GPT-4 is using classic O(N^2) attention exclusively. They haven't released the results, but I promise you this is not what they are using exclusively.
  - anthlax 4y ago
    Interesting! How do you know this?
cs702 4y ago
Memory use is already linear in practice, thanks to FlashAttention. It's an open question whether computation can be made sub-quadratic without impacting model performance, although there are ongoing efforts seeking to do exactly that.[a] Keep in mind: Once you go into precision as low as 4 bits (or lower?), all sorts of optimizations can become practical. Off the top of my head, maybe you could cache and reuse common attention sub-matrices (e.g., a 16×16 sub-matrix with 4-bit elements occupies only 16×16×4÷8=128 bytes of space)? My sense is there's so much money at stake here, that whoever does this first will win big even if they end up having to replace or augment it with something better down the road. Hypothetical example: Imagine Intel or AMD coming out with a $1K or $2K card that has "built-in 4-bit attention," enabling you to run transformers of much greater scale on a run-of-the-mill desktop PC. I'd buy that in a heartbeat. [a] Here's a recent post about a new approach from a group at Stanford that looks promising to me, although I don't fully understand all its details yet: https://news.ycombinator.com/item?id=35502187 https://news.ycombinator.com/item?id=35502187
throwawaymaths 4y ago
In theory one could use the nysromformer. Don't know if anyone does in practice
- whimsicalism 4y ago
  They don't
  - throwawaymaths 4y ago
    Do you know why/why not?
    - whimsicalism 4y ago
      They've just gone with a different approach for fast attention. [0] Not sure it was due to any particular merits/lack of the nystroformer. [0]: https://twitter.com/typedfemale/status/1609867110695735296 https://twitter.com/typedfemale/status/1609867110695735296
sebzim4500 4y ago
Probably once context lengths get really long it might be better to use ANN rather than exact attention at inference time. I would imagine this would only pay off with ~100,000 token contexts, and even then it would only work if only a few tokens meaningfully contribute to each attention head.
whimsicalism 4y ago
I agree - unfortunately we have gone so far down the rabbit hole optimizing transformer models. Alternative models like S4 have been able to get transformer level performance with O(N) sequence length scaling.

Low precision: agreed Attention: Isn't it quadratic in context length? I dunno, this feels like the crude first iteration of something that will get inevitably passed by something that scales better.

dpflan 4y ago

Sharing a comment from a similar line of discussion: """ Complexity is quadratic in sequence length. For 512 tokens it is 262K, but for 4000 tokens it becomes 16M and goes OOM on a single GPU. We need about 100K-1M tokens to load whole books at once. Since 2017 there have been hundreds of attempts to bring O(N^2) to O(N), but none of them replaced the vanilla attention yet in large models. They lose on accuracy. Maybe Flash attention has a shot (https://arxiv.org/abs/2205.14135 https://arxiv.org/abs/2205.14135). """ - source: https://news.ycombinator.com/item?id=34171503 https://news.ycombinator.com/item?id=34171503

whimsicalism 4y ago
There is literally no way that GPT-4 is using classic O(N^2) attention exclusively. They haven't released the results, but I promise you this is not what they are using exclusively.
- anthlax 4y ago
  Interesting! How do you know this?

cs702 4y ago

Memory use is already linear in practice, thanks to FlashAttention. It's an open question whether computation can be made sub-quadratic without impacting model performance, although there are ongoing efforts seeking to do exactly that.[a] Keep in mind: Once you go into precision as low as 4 bits (or lower?), all sorts of optimizations can become practical. Off the top of my head, maybe you could cache and reuse common attention sub-matrices (e.g., a 16×16 sub-matrix with 4-bit elements occupies only 16×16×4÷8=128 bytes of space)? My sense is there's so much money at stake here, that whoever does this first will win big even if they end up having to replace or augment it with something better down the road. Hypothetical example: Imagine Intel or AMD coming out with a $1K or $2K card that has "built-in 4-bit attention," enabling you to run transformers of much greater scale on a run-of-the-mill desktop PC. I'd buy that in a heartbeat. [a] Here's a recent post about a new approach from a group at Stanford that looks promising to me, although I don't fully understand all its details yet: https://news.ycombinator.com/item?id=35502187 https://news.ycombinator.com/item?id=35502187

throwawaymaths 4y ago

In theory one could use the nysromformer. Don't know if anyone does in practice

whimsicalism 4y ago
They don't
- throwawaymaths 4y ago
  Do you know why/why not?
  - whimsicalism 4y ago
    They've just gone with a different approach for fast attention. [0] Not sure it was due to any particular merits/lack of the nystroformer. [0]: https://twitter.com/typedfemale/status/1609867110695735296 https://twitter.com/typedfemale/status/1609867110695735296

sebzim4500 4y ago

Probably once context lengths get really long it might be better to use ANN rather than exact attention at inference time. I would imagine this would only pay off with ~100,000 token contexts, and even then it would only work if only a few tokens meaningfully contribute to each attention head.

whimsicalism 4y ago

I agree - unfortunately we have gone so far down the rabbit hole optimizing transformer models. Alternative models like S4 have been able to get transformer level performance with O(N) sequence length scaling.