5 ms·

> * In existing LLMs, we can replace all parameter floating-point values representing real numbers with ternary values representing (-1, 0, 1). Why is this so

> * In existing LLMs, we can replace all parameter floating-point values representing real numbers with ternary values representing (-1, 0, 1). Why is this so shocking? Quantization has been widely explored, driving that to its extreme (and blowing up parameter count to make up for it) just seems like a natural extension of that. Easier said than done, of course, and very impressive that they pulled it off. > In matrix multiplications (e.g., weights by vectors), we can replace elementwise products in each dot product (a₁b₁ + a₂b₂ ...) with elementwise additions (a₁+b₁ + a₂+b₂ ...), in which signs depend on each value I feel like this follows naturally from having only ternary values, multiplication doesn't really bring much to the table here. It's a bit surprising that it's performing so well on existing hardware, usually multiplication hardware sees more optimization, especially for GPGPU hardware.

cs702 3y ago
> Why is this so shocking? Quantization has been widely explored, driving that to its extreme (and blowing up parameter count to make up for it) just seems like a natural extension of that. I find it shocking that we don't even need lower floating-point precision. We don't need precision at all. We only need three symbols to represent every value. > I feel like this follows naturally from having only ternary values, multiplication doesn't really bring much to the table here. It's a bit surprising that it's performing so well on existing hardware, usually multiplication hardware sees more optimization, especially for GPGPU hardware. I find it shocking. Consider that associative addition over ternary digits, or trits, represented by three symbols (a,b,c) has only three possible input pairs, (a,b), (a,c), or (b,c) (within each pair, order doesn't matter), and only three possible outputs, a, b, or c. Matrix multiplications could be executed via crazy-cheap tritwise operations in hardware. Maybe ternary hardware[a] will become a thing in AI? --- [a] https://en.wikipedia.org/wiki/Ternary_computer https://en.wikipedia.org/wiki/Ternary_computer
- jerf 3y ago
  An integer is just a concatenation of bits. Floating point appears more complicated but from an information theory perspective it is also just a concatenation of bits. If, for the sake of argument, one replaced a 64-bit int with 64 individual bits, that's really the same amount of information and a structure could hypothetically then either choose to recreate the original 64-bit int, or use the 64-bits more efficiently by choosing from the much larger set of possibilities of ways to use such resources. Trits are helpful for neural nets, though, since they really love signs and they need a 0. So from the perspective that it's all just bits in the end the only thing that is interesting is how useful it is to arrange those bits into trits for this particular algorithm, and that the algorithm seems to be able to use things more effectively that way than with raw bits. This may seem an absolutely bizarre zigzag, but I am reminded of Busy Beavers, because of the way they take very the very small primitives of a Turing Machine, break it down to the smallest pieces, then combine them in ways that almost immediately cease to be humanly comprehensible. Completely different selection mechanism for what appears, but it turns out Turing Machine states can do a lot "more" than you might think simply by looking at human-designed TMs. We humans have very stereotypical design methodologies and they have their advantages, but sometimes just letting algorithms rip can result in much better things than we could ever hope to design with the same resources.
  - cs702 3y ago
    > So from the perspective that it's all just bits in the end the only thing that is interesting is how useful it is to arrange those bits into trits for this particular algorithm, and that the algorithm seems to be able to use things more effectively that way than with raw bits. Thank you. I find many other things interesting here, including the potential implications for hardware, but otherwise, yes, I agree with you, that is interesting.
  - SkyBelow 3y ago
    This sort of breakdown also reminds me of the explanation of why busy beavers grow faster than anything humans can ever define. Anything a human can define is a finite number of steps that can be represented by some turing machine of size M. A turning machine of size N > M can then use M as a subset of it, growing faster than than the turing machine of size M. Either it is the busy beaver for size N, or it grows slower than the busy beaver for size N. Either way, the busy beaver for size N grows faster than whatever the human defined that was captured by the turning machine of size M. This explanation was what helped me understand why busy beavers is faster growing than any operator that can be formally defined (obviously you can define an operator that references busy beaver itself, but busy beaver can be considered to not be formally defined, and thus any operator defined used it isn't formally defined either). The bit about floating point numbers just being a collection of bits interpreted in a certain way helps make sense why a bigger model doesn't need floating points at all.
  - eru 3y ago
    > We humans have very stereotypical design methodologies and they have their advantages, but sometimes just letting algorithms rip can result in much better things than we could ever hope to design with the same resources. Yes. Though here the interesting point is not so much that these structures exist, but that 'stupid' back-propagation is smart enough to find them. You can't find busy beavers like that.
- jxy 3y ago
  The matrices (weights) are ternary. The vectors are not.
  - cs702 3y ago
    The activations are in (-1, 1), so they're also representable by (-1, 0, 1).
    - rfoo 3y ago
      This is wrong. The paper described that their activation is in int8 during inference. That being said, before-LLM-era deep learning already had low bit quantization down to 1w2f [0] working back in 2016 [1]. So it's certainly possible it would work for LLM too. [0] 1-bit weights, 2-bit activations; though practically people deployed 2w4f instead. [1] https://arxiv.org/abs/1606.06160 https://arxiv.org/abs/1606.06160
- deleted 3y ago
  [deleted]
- p1esk 3y ago
  If you find three symbols per weight shocking, this paper should completely blow your mind: https://arxiv.org/abs/1803.03764 https://arxiv.org/abs/1803.03764 I admit it did shock me when it came out.
- cs702 3y ago
  EDIT: Embarrassingly, on the last paragraph I got the number of possible input pairs wrong: > only three possible input pairs, (a,b), (a,c), or (b,c) (within each pair, order doesn't matter) The correct number, ignoring order, is six pairs, because we have to include (a,a), (b,b), and (c,c).
satellite2 3y ago
Because it's no longer a linear optimization or curve fitting problem. It becomes a voting or combinatorial problem. Which at least in my mind are two completely different areas of research.
- HPsquared 3y ago
  With enough parameters, it probably starts looking continuous again. Like how in physics everything is quantised at the smallest scale but if you put enough atoms together it all smooths out and behaves "classically".
  - amelius 3y ago
    Yes, but we can simulate classical physics using mathematical shortcuts. Simulating every little atom would take a lot more work.
ncruces 3y ago
Well I guess it's the “blowing up parameter count to make up for it” that confuses me, but maybe it's just ignorance. Like what would be the expected factor of this blow up to make up the difference between ternary and whatever 16 bits encoding they were using? I mean intuitively I'd expect to need ~10× the symbols to encode the same information? Are they using an order of magnitude more parameters, or is that not how it works?
- int_19h 3y ago
  With existing common quantization techniques, a 70b model quantized to 3-bit still drastically outperforms an unquantized 35b model.
  - p1esk 3y ago
    Are you sure? I was under impression that 3b quantization still results in a significant degradation. Which quantization method are you talking about?
    - int_19h 3y ago
      It does result in a significant degradation relative to unquantized model of the same size, but even with simple llama.cpp K-quantization, it's still worth it all the way down to 2-bit. The chart in this llama.cpp PR speaks for itself: https://github.com/ggerganov/llama.cpp/pull/1684#issue-1739619305 https://github.com/ggerganov/llama.cpp/pull/1684#issue-17396...
      - p1esk 3y ago
        Oh wow, you’re right. Though it seems that they are using very small weight group sizes: either 16 or 32 (fp16 scaling factor per group). In this paper it seems there’s no weights grouping, so it’s a bit apples to oranges.
gemeral 3y ago
> and blowing up parameter count to make up for it based on (an admittedly rapid and indulgent reading of the paper), it seems like they're not increasing the parameter size. Do you mind pointing out where the blowup is occurring?
- magnustesshu 3y ago
  They're saying that likely, models of comparable size will perform worse (the paper claims as good) But since they are (optimized up to 8 or 10x if packing terns beyond 2 bits, in practice it seems 3-5x considering larger other structures needed in memory) more memory efficient, the largest models can be that much larger.
SuchAnonMuchWow 3y ago
> I feel like this follows naturally from having only ternary values, multiplication doesn't really bring much to the table here. It's a bit surprising that it's performing so well on existing hardware, usually multiplication hardware sees more optimization, especially for GPGPU hardware. No, unless I'm mistaken it's a huge impact: it means the matrix product is separable: basically, it's a O(n²) algorithm, and not O(n3): add together all the c_j = sum(a_i_j), d_i = sum(b_i_j), and the final results are all the combinations of cj+di. And even then, half that is unnecessary because the d_i can all be pre-computed when before inference since they are weights. But I skimmed over the paper, and didn't found the part where it was explained how they replace the product by additions: from what I understand, they remplace multiplications by bi by selecting +ai, 0, or -ai. So the final matrix multiplication can be implemented by only additions, but only because the weights are 1,0,-1 they avoid multiplications altogether. This is really different from what the GP said (remplacing a0*b0+... by a0+b0+...).

cs702 3y ago

> Why is this so shocking? Quantization has been widely explored, driving that to its extreme (and blowing up parameter count to make up for it) just seems like a natural extension of that. I find it shocking that we don't even need lower floating-point precision. We don't need precision at all. We only need three symbols to represent every value. > I feel like this follows naturally from having only ternary values, multiplication doesn't really bring much to the table here. It's a bit surprising that it's performing so well on existing hardware, usually multiplication hardware sees more optimization, especially for GPGPU hardware. I find it shocking. Consider that associative addition over ternary digits, or trits, represented by three symbols (a,b,c) has only three possible input pairs, (a,b), (a,c), or (b,c) (within each pair, order doesn't matter), and only three possible outputs, a, b, or c. Matrix multiplications could be executed via crazy-cheap tritwise operations in hardware. Maybe ternary hardware[a] will become a thing in AI? --- [a] https://en.wikipedia.org/wiki/Ternary_computer https://en.wikipedia.org/wiki/Ternary_computer

jerf 3y ago
An integer is just a concatenation of bits. Floating point appears more complicated but from an information theory perspective it is also just a concatenation of bits. If, for the sake of argument, one replaced a 64-bit int with 64 individual bits, that's really the same amount of information and a structure could hypothetically then either choose to recreate the original 64-bit int, or use the 64-bits more efficiently by choosing from the much larger set of possibilities of ways to use such resources. Trits are helpful for neural nets, though, since they really love signs and they need a 0. So from the perspective that it's all just bits in the end the only thing that is interesting is how useful it is to arrange those bits into trits for this particular algorithm, and that the algorithm seems to be able to use things more effectively that way than with raw bits. This may seem an absolutely bizarre zigzag, but I am reminded of Busy Beavers, because of the way they take very the very small primitives of a Turing Machine, break it down to the smallest pieces, then combine them in ways that almost immediately cease to be humanly comprehensible. Completely different selection mechanism for what appears, but it turns out Turing Machine states can do a lot "more" than you might think simply by looking at human-designed TMs. We humans have very stereotypical design methodologies and they have their advantages, but sometimes just letting algorithms rip can result in much better things than we could ever hope to design with the same resources.
- cs702 3y ago
  > So from the perspective that it's all just bits in the end the only thing that is interesting is how useful it is to arrange those bits into trits for this particular algorithm, and that the algorithm seems to be able to use things more effectively that way than with raw bits. Thank you. I find many other things interesting here, including the potential implications for hardware, but otherwise, yes, I agree with you, that is interesting.
- SkyBelow 3y ago
  This sort of breakdown also reminds me of the explanation of why busy beavers grow faster than anything humans can ever define. Anything a human can define is a finite number of steps that can be represented by some turing machine of size M. A turning machine of size N > M can then use M as a subset of it, growing faster than than the turing machine of size M. Either it is the busy beaver for size N, or it grows slower than the busy beaver for size N. Either way, the busy beaver for size N grows faster than whatever the human defined that was captured by the turning machine of size M. This explanation was what helped me understand why busy beavers is faster growing than any operator that can be formally defined (obviously you can define an operator that references busy beaver itself, but busy beaver can be considered to not be formally defined, and thus any operator defined used it isn't formally defined either). The bit about floating point numbers just being a collection of bits interpreted in a certain way helps make sense why a bigger model doesn't need floating points at all.
- eru 3y ago
  > We humans have very stereotypical design methodologies and they have their advantages, but sometimes just letting algorithms rip can result in much better things than we could ever hope to design with the same resources. Yes. Though here the interesting point is not so much that these structures exist, but that 'stupid' back-propagation is smart enough to find them. You can't find busy beavers like that.
jxy 3y ago
The matrices (weights) are ternary. The vectors are not.
- cs702 3y ago
  The activations are in (-1, 1), so they're also representable by (-1, 0, 1).
  - rfoo 3y ago
    This is wrong. The paper described that their activation is in int8 during inference. That being said, before-LLM-era deep learning already had low bit quantization down to 1w2f [0] working back in 2016 [1]. So it's certainly possible it would work for LLM too. [0] 1-bit weights, 2-bit activations; though practically people deployed 2w4f instead. [1] https://arxiv.org/abs/1606.06160 https://arxiv.org/abs/1606.06160
deleted 3y ago
[deleted]
p1esk 3y ago
If you find three symbols per weight shocking, this paper should completely blow your mind: https://arxiv.org/abs/1803.03764 https://arxiv.org/abs/1803.03764 I admit it did shock me when it came out.
cs702 3y ago
EDIT: Embarrassingly, on the last paragraph I got the number of possible input pairs wrong: > only three possible input pairs, (a,b), (a,c), or (b,c) (within each pair, order doesn't matter) The correct number, ignoring order, is six pairs, because we have to include (a,a), (b,b), and (c,c).

satellite2 3y ago

Because it's no longer a linear optimization or curve fitting problem. It becomes a voting or combinatorial problem. Which at least in my mind are two completely different areas of research.

HPsquared 3y ago
With enough parameters, it probably starts looking continuous again. Like how in physics everything is quantised at the smallest scale but if you put enough atoms together it all smooths out and behaves "classically".
- amelius 3y ago
  Yes, but we can simulate classical physics using mathematical shortcuts. Simulating every little atom would take a lot more work.

ncruces 3y ago

Well I guess it's the “blowing up parameter count to make up for it” that confuses me, but maybe it's just ignorance. Like what would be the expected factor of this blow up to make up the difference between ternary and whatever 16 bits encoding they were using? I mean intuitively I'd expect to need ~10× the symbols to encode the same information? Are they using an order of magnitude more parameters, or is that not how it works?

int_19h 3y ago
With existing common quantization techniques, a 70b model quantized to 3-bit still drastically outperforms an unquantized 35b model.
- p1esk 3y ago
  Are you sure? I was under impression that 3b quantization still results in a significant degradation. Which quantization method are you talking about?
  - int_19h 3y ago
    It does result in a significant degradation relative to unquantized model of the same size, but even with simple llama.cpp K-quantization, it's still worth it all the way down to 2-bit. The chart in this llama.cpp PR speaks for itself: https://github.com/ggerganov/llama.cpp/pull/1684#issue-1739619305 https://github.com/ggerganov/llama.cpp/pull/1684#issue-17396...
    - p1esk 3y ago
      Oh wow, you’re right. Though it seems that they are using very small weight group sizes: either 16 or 32 (fp16 scaling factor per group). In this paper it seems there’s no weights grouping, so it’s a bit apples to oranges.

gemeral 3y ago

> and blowing up parameter count to make up for it based on (an admittedly rapid and indulgent reading of the paper), it seems like they're not increasing the parameter size. Do you mind pointing out where the blowup is occurring?

magnustesshu 3y ago
They're saying that likely, models of comparable size will perform worse (the paper claims as good) But since they are (optimized up to 8 or 10x if packing terns beyond 2 bits, in practice it seems 3-5x considering larger other structures needed in memory) more memory efficient, the largest models can be that much larger.

SuchAnonMuchWow 3y ago

> I feel like this follows naturally from having only ternary values, multiplication doesn't really bring much to the table here. It's a bit surprising that it's performing so well on existing hardware, usually multiplication hardware sees more optimization, especially for GPGPU hardware. No, unless I'm mistaken it's a huge impact: it means the matrix product is separable: basically, it's a O(n²) algorithm, and not O(n3): add together all the c_j = sum(a_i_j), d_i = sum(b_i_j), and the final results are all the combinations of cj+di. And even then, half that is unnecessary because the d_i can all be pre-computed when before inference since they are weights. But I skimmed over the paper, and didn't found the part where it was explained how they replace the product by additions: from what I understand, they remplace multiplications by bi by selecting +ai, 0, or -ai. So the final matrix multiplication can be implemented by only additions, but only because the weights are 1,0,-1 they avoid multiplications altogether. This is really different from what the GP said (remplacing a0*b0+... by a0+b0+...).