4 ms·

I'm not saying if the paper is correct or not (since I can't tell), but I don't think your argument really holds. Consider applying it to multiplication: Funda

I'm not saying if the paper is correct or not (since I can't tell), but I don't think your argument really holds. Consider applying it to multiplication: Fundamentally, multiplication need to look at every pair of integer from the two input numbers. It must be O(n^2); N digits looking at N other digits is quadratic. Any sub-quadratic multiplication must hence necessarily lose some information.

actionfromafar 8mo ago
Doesn't that have to do with how many bits you allow in the actual calculation in physical reality?
- hellohello2 8mo ago
  Well, for multiplication complexity is defined in terms of on the number of digits/bits digits directly. For attention, complexity is defined on terms of the number of input vectors which are all at fixed precision. I don't understand what happens to the method proposed in the paper at higher precision (since I don't understand the paper), but in reality in doesn't matter since there is no value in anything over float16 for machine learning.
logicchains 8mo ago
Multiplication has some properties like being cumulative. If we assume the sequence has any specific properties then we no longer have a general sequence model.
- direwolf20 8mo ago
  I think you meant commutative. Attention also has some specific properties. And sometimes results are just unexpected. Did you know that anything a Turing machine can do in t tome steps, a different Turing machine can do in O(sqrt(t log t)) memory cells? https://news.ycombinator.com/item?id=44055347 https://news.ycombinator.com/item?id=44055347
deleted 8mo ago
[deleted]
nine_k 8mo ago
Integer multiplication x * y can be trivially done in O(k): k = log₂(min(x, y)). This is because we can do addition in constant time, adding all bits in parallel. By combining many more adding units, we can do (fixed-size) multiplication in constant time, too: https://en.wikipedia.org/wiki/Dadda_multiplier https://en.wikipedia.org/wiki/Dadda_multiplier
sifar 8mo ago
Multiplication can be sub-quadratic using Karatsuba's algorithm.
- nullc 8mo ago
  That is the poster's point!

actionfromafar 8mo ago

Doesn't that have to do with how many bits you allow in the actual calculation in physical reality?

hellohello2 8mo ago
Well, for multiplication complexity is defined in terms of on the number of digits/bits digits directly. For attention, complexity is defined on terms of the number of input vectors which are all at fixed precision. I don't understand what happens to the method proposed in the paper at higher precision (since I don't understand the paper), but in reality in doesn't matter since there is no value in anything over float16 for machine learning.

logicchains 8mo ago

Multiplication has some properties like being cumulative. If we assume the sequence has any specific properties then we no longer have a general sequence model.

direwolf20 8mo ago
I think you meant commutative. Attention also has some specific properties. And sometimes results are just unexpected. Did you know that anything a Turing machine can do in t tome steps, a different Turing machine can do in O(sqrt(t log t)) memory cells? https://news.ycombinator.com/item?id=44055347 https://news.ycombinator.com/item?id=44055347

deleted 8mo ago

[deleted]

nine_k 8mo ago

Integer multiplication x * y can be trivially done in O(k): k = log₂(min(x, y)). This is because we can do addition in constant time, adding all bits in parallel. By combining many more adding units, we can do (fixed-size) multiplication in constant time, too: https://en.wikipedia.org/wiki/Dadda_multiplier https://en.wikipedia.org/wiki/Dadda_multiplier

sifar 8mo ago

Multiplication can be sub-quadratic using Karatsuba's algorithm.

nullc 8mo ago
That is the poster's point!