3 ms·

That's not a 'bit' ("Binary digIT"). It's closer to a 'trit' ("TeRnary-digIT"). Specifically, ternary digits spanning {-1, 0, 1} (rather than the usual {0, 1, 2

by gojomo 3y ago

That's not a 'bit' ("Binary digIT"). It's closer to a 'trit' ("TeRnary-digIT"). Specifically, ternary digits spanning {-1, 0, 1} (rather than the usual {0, 1, 2} in a base-3 numbering system) are 'balanced ternary'. A great intro to the theoretical reasons ternary might have some promise in computing is this 2001 article from 'American Scientist', "Third Base", which quotes Knuth calling balanced-ternary "perhaps the prettiest numbering system of all" and also discusses an abortive Soviet effort in the direction of ternary computing: http://web.archive.org/web/20011205185830/http://americanscientist.org/Issues/Comsci01/Compsci2001-11.html http://web.archive.org/web/20011205185830/http://americansci... In an aside, the article hints that e-nary digits (base 2.718…) if somehow made practical/meaningful, might actually be better than ternary (or perhaps even optimal?). So maybe this paper's observation that ~"1.58 bits" (ln2(3) binary-digits) is a sweet-spot could be further refined into some method for representing the state of a e-nary-modeled algorithm in ln2(e) binary-digits (~"1.44 bits") per underlying e-it. (As it may be of renewed interest, I've also put this 2001 "American Scientist" base-3 intro as a new HN submission for discussion: https://news.ycombinator.com/item?id=39541756 https://news.ycombinator.com/item?id=39541756)

bee_rider 3y ago
It is obviously pretty common to represent matrices with lots of zeros in a sparse format, like csr or something. I wonder if they could get away with 1-bit representation using a sparse matrix. Of course, it would be a little different from a typical sparse matrix because there’s no problem normally having a zero-value in a structurally non-zero location.
no_identd 3y ago
See also: https://en.wikipedia.org/wiki/Nat_(unit) https://en.wikipedia.org/wiki/Nat_(unit) (make sure to read the footnotes, too) Edit: See also also, on the radix economy of balanced ternary (called "tristate") vs base 3: https://web.archive.org/web/20090312094241/http://abhijit.info/tristate/tristate.html#Base3 https://web.archive.org/web/20090312094241/http://abhijit.in... + a wild Marvin Minsky appears: https://archive.fo/gL2Bv https://archive.fo/gL2Bv That page also brings up the whole "but division" problem with balanced ternary, however, I personally suspect that http://degiorgi.math.hr/aaa_sem/Div_Krishna/887-889.pdf http://degiorgi.math.hr/aaa_sem/Div_Krishna/887-889.pdf ("A Division Algorithm for Signed-Digit Arithmetic" by Chin Tung, from 1968 !) might offer an overlooked path to a solution to that problem And see also also², this quote from TAOCP: "Cauchy pointed out that negative digits make it unneccesary for a person to memorize the multiplication table past 5x5." The—INCREDIBLY ANNOYING TO LOCATE—source for which is "105. Calculs numériques. sur les moyens d'éviter les erreurs dans les calculs numériques." on Pdf page 445/document page 431 here: https://www.e-rara.ch/download/pdf/5702285?name=Tome%2520V%46 https://www.e-rara.ch/download/pdf/5702285?name=Tome%2520V%4... See also also³: https://pdfs.semanticscholar.org/5f77/b1cf105024b41b6824ba91ab1cb6e19b0692.pdf https://pdfs.semanticscholar.org/5f77/b1cf105024b41b6824ba91... (Vince, Andrew - Radix Representation and Rep-Tiling) ( +a vaguely related paper here on quantum mechanics & radix economy, BUT it makes the mistake of using an overly specific formula applicable only to unsigned-digit representations thus drawing the wrong conclusions: https://www.researchgate.net/profile/Vladimir_Garcia-Morales/publication/259578204_Quantum_Mechanics_and_the_Principle_of_Least_Radix_Economy/links/5688127e08ae1e63f1f73000/Quantum-Mechanics-and-the-Principle-of-Least-Radix-Economy.pdf https://www.researchgate.net/profile/Vladimir_Garcia-Morales... )
nighthawk454 3y ago
Base e is the optimal base for number representation, so that’s probably why. Followed by base 3, then base 2. https://en.m.wikipedia.org/wiki/Radix_economy https://en.m.wikipedia.org/wiki/Radix_economy
- o11c 3y ago
  FSVO "optimal". In practice, both physical reality and algorithm design strongly favors base 2.
  - nighthawk454 3y ago
    Yeah, specifically, the definition of optimal provided - radix economy. There are plenty of other considerations one could make in other contexts. Practically, a transcendental base seems... rather impractical. And base 2 is not so much 'more optimal' than base 3 to warrant the electrical complexity probably, for example.
- eru 3y ago
  Negative bases are probably even better, because you can represent negative numbers without worrying about extra sign handling.
dekhn 3y ago
How useful are -0 and 0? You could splurge on two bits per value which gives you { -1, -0, 0, 1 }
- ant6n 3y ago
  3^5=243. so use a byte to represent a vector of 5 ternary values, leaving some possible signaling values.
- schiffern 3y ago
  Rather than (indistinguishable?) 0 and -0, why not add back some magnitude in the positive direction? { -1, 0, 1, 2 } is most obvious, but it's not clear whether it's better or worse than { -1, 0, 1/2, 1 } Maybe theoretically (if not architecturally) it would best to "split the difference" between the two and choose { -1, 0, 1/phi, phi } or perhaps the more implementable { -1, 0, 1, 3 } EDIT: Of course you can also go the other way, with { -1, 1 }
  - dekhn 3y ago
    -0 is not indistinguishable from 0 in floating point math. Most ops return +0 and -0 can behave differently. I don't know of any examples where -0 is important for machine learning, though.
Razengan 3y ago
Why not a tit?
- jdiff 3y ago
  Because bi- is two, tri- is three. Ti- is meaningless, and not good enough of a joke to make up for it.
- esafak 3y ago
  They renamed the biggest ML conference (NIPS) over the same joke, so don't count on it.
  - Razengan 3y ago
    Why? Just because it's spelled identical to a human body part? This kind of shit is one of the most bizarre things about human society (or the prude cultures of it at least), to consider the most natural things so taboo and a "joke" to mention.
    - kaelwd 3y ago
      https://youtu.be/VS11bRa8NnQ?t=122 https://youtu.be/VS11bRa8NnQ?t=122
kleiba 3y ago
Note that they're not claiming that their LLM is 1-bit - they're saying that there is a 1-bit era of LLMs. What they do say is that their approach is a variant of a 1-bit LLM variant, namely a ternary LLM (they explicitly state that in the abstract).

by gojomo 3y ago

bee_rider 3y ago

It is obviously pretty common to represent matrices with lots of zeros in a sparse format, like csr or something. I wonder if they could get away with 1-bit representation using a sparse matrix. Of course, it would be a little different from a typical sparse matrix because there’s no problem normally having a zero-value in a structurally non-zero location.

no_identd 3y ago

See also: https://en.wikipedia.org/wiki/Nat_(unit) https://en.wikipedia.org/wiki/Nat_(unit) (make sure to read the footnotes, too) Edit: See also also, on the radix economy of balanced ternary (called "tristate") vs base 3: https://web.archive.org/web/20090312094241/http://abhijit.info/tristate/tristate.html#Base3 https://web.archive.org/web/20090312094241/http://abhijit.in... + a wild Marvin Minsky appears: https://archive.fo/gL2Bv https://archive.fo/gL2Bv That page also brings up the whole "but division" problem with balanced ternary, however, I personally suspect that http://degiorgi.math.hr/aaa_sem/Div_Krishna/887-889.pdf http://degiorgi.math.hr/aaa_sem/Div_Krishna/887-889.pdf ("A Division Algorithm for Signed-Digit Arithmetic" by Chin Tung, from 1968 !) might offer an overlooked path to a solution to that problem And see also also², this quote from TAOCP: "Cauchy pointed out that negative digits make it unneccesary for a person to memorize the multiplication table past 5x5." The—INCREDIBLY ANNOYING TO LOCATE—source for which is "105. Calculs numériques. sur les moyens d'éviter les erreurs dans les calculs numériques." on Pdf page 445/document page 431 here: https://www.e-rara.ch/download/pdf/5702285?name=Tome%2520V%46 https://www.e-rara.ch/download/pdf/5702285?name=Tome%2520V%4... See also also³: https://pdfs.semanticscholar.org/5f77/b1cf105024b41b6824ba91ab1cb6e19b0692.pdf https://pdfs.semanticscholar.org/5f77/b1cf105024b41b6824ba91... (Vince, Andrew - Radix Representation and Rep-Tiling) ( +a vaguely related paper here on quantum mechanics & radix economy, BUT it makes the mistake of using an overly specific formula applicable only to unsigned-digit representations thus drawing the wrong conclusions: https://www.researchgate.net/profile/Vladimir_Garcia-Morales/publication/259578204_Quantum_Mechanics_and_the_Principle_of_Least_Radix_Economy/links/5688127e08ae1e63f1f73000/Quantum-Mechanics-and-the-Principle-of-Least-Radix-Economy.pdf https://www.researchgate.net/profile/Vladimir_Garcia-Morales... )

nighthawk454 3y ago

Base e is the optimal base for number representation, so that’s probably why. Followed by base 3, then base 2. https://en.m.wikipedia.org/wiki/Radix_economy https://en.m.wikipedia.org/wiki/Radix_economy

o11c 3y ago
FSVO "optimal". In practice, both physical reality and algorithm design strongly favors base 2.
- nighthawk454 3y ago
  Yeah, specifically, the definition of optimal provided - radix economy. There are plenty of other considerations one could make in other contexts. Practically, a transcendental base seems... rather impractical. And base 2 is not so much 'more optimal' than base 3 to warrant the electrical complexity probably, for example.
eru 3y ago
Negative bases are probably even better, because you can represent negative numbers without worrying about extra sign handling.

dekhn 3y ago

How useful are -0 and 0? You could splurge on two bits per value which gives you { -1, -0, 0, 1 }

ant6n 3y ago
3^5=243. so use a byte to represent a vector of 5 ternary values, leaving some possible signaling values.
schiffern 3y ago
Rather than (indistinguishable?) 0 and -0, why not add back some magnitude in the positive direction? { -1, 0, 1, 2 } is most obvious, but it's not clear whether it's better or worse than { -1, 0, 1/2, 1 } Maybe theoretically (if not architecturally) it would best to "split the difference" between the two and choose { -1, 0, 1/phi, phi } or perhaps the more implementable { -1, 0, 1, 3 } EDIT: Of course you can also go the other way, with { -1, 1 }
- dekhn 3y ago
  -0 is not indistinguishable from 0 in floating point math. Most ops return +0 and -0 can behave differently. I don't know of any examples where -0 is important for machine learning, though.

Razengan 3y ago

Why not a tit?

jdiff 3y ago
Because bi- is two, tri- is three. Ti- is meaningless, and not good enough of a joke to make up for it.
esafak 3y ago
They renamed the biggest ML conference (NIPS) over the same joke, so don't count on it.
- Razengan 3y ago
  Why? Just because it's spelled identical to a human body part? This kind of shit is one of the most bizarre things about human society (or the prude cultures of it at least), to consider the most natural things so taboo and a "joke" to mention.
  - kaelwd 3y ago
    https://youtu.be/VS11bRa8NnQ?t=122 https://youtu.be/VS11bRa8NnQ?t=122

kleiba 3y ago

Note that they're not claiming that their LLM is 1-bit - they're saying that there is a 1-bit era of LLMs. What they do say is that their approach is a variant of a 1-bit LLM variant, namely a ternary LLM (they explicitly state that in the abstract).