You can beat the efficiency of 5 trits in 8 bits (1.6) with as few as 17 trits in 27 bits (~1.588), but once you account for rounding up to a whole number of bytes for practical reasons, then beating the efficiency requires going to at least 111 trits in 176 bits (~1.586), or perhaps more practically for fast unpacking, 161 trits in 256 bits (~1.59).
At that level, even if you have, say, 27B trits, the more efficient encodings would save something like 38-45MB (theoretical limit ~48MB), likely at the cost of some slowdown.
> a diagram that shows that dividing 0x7F (127) by 243 and then multiplying by 256 results in 0x86 (134)
> Tada!
How... how does that help with anything?
> Now digits can be easily extracted from the top two bits of the resulting 10-bit number when multiplying this 8-bit byte by 3.
What? Why? How? This is supposed to be the most insightful part of the post, and it's literally just "Behold!" from that one proof of Pythagorean theorem. Could someone please elaborate it for a non-genius like me?
I think the key insight here is that 243 is 100000 in base3. So dividing by 243 essentially converts any 5 digit base 3 number to [0,1) interval. Multiplying by 256 converts it to [0,256) interval which conveniently fits into a byte.
I was actually mucking with ChatGPT about possible "post-binary" architectures.
I ended up feeling that ternary is just icky, because the "middle value" doesn't have an "opposite"
Maybe we should do what quaternions did to complex numbers and just jump from 2 to 4: Quaternary CPUs
I couldn't understand half of the words it spat out but it turns out that using pairs of "quits" as the atomic computation unit to represent complex numbers and/or 2x2 matrices could be ideal for AI etc.
Amusing that the link to an article on ternary numbers was posted by Mr Triplett. (:
The article is well-written and illustrated. The technique described is used in llama.cpp for running language models like BitNet b1.58 whose weights are stored as ternary types.
> ..in which every single parameter (or weight) of the LLM is ternary {-1, 0, 1}
> significantly more cost-effective in terms of latency, memory, throughput, and energy consumption
The original paper on this technique was published in Feb 2024. (Also linked from the article)
However, since then there have only been a few other models using ternary weights. I get the impression that there are factors not considered in the paper which make it less practical than it seemed.
Despite my ignorance on what would be involved, I like to fantasize that companies like Apple (who own their own chip design and hardware) can put these ternary pack/unpack operations in hardware with a single instruction for each (and also instructions for performing the various matrix convolutions using ternary numbers) so that we can get on-device LLMs.
I suppose with the recent quantized Bonsai models we're already seeing on-device LLMs for phones and the like… But I (again, forgive my ignorance) assume that there is an order of magnitude or more in performance sitting out there if we get custom hardware instructions.
There is a possibility space there. Some transistors are "naturally" ternary (which we use today for things like binary error correction). Also the Soviet Union went down the rabbit hole of ternary computers and programming languages, which is fascinating history to explore.
The interesting questions are if enough LLMs use ternary enough and for long enough into the future to make investments in ternary hardware worth it. Ternary hardware is probably less general purpose than the modern GPU design that is being used for LLMs today and the crossover of "general purpose floating point matrix math engine" for graphics as well as LLMs a useful one, particularly because we know the graphics revenue models pretty well (and gamers are pretty upset at GPU pricing right now because of LLM demand).
One way to beat this in terms of coding efficiency would be to use something like rANS (explanation [1], code [2]).
You would have a more complicated decoder with rANS though, even if you removed the frequency table lookup (because always 1/3) and you'd only produce one output at a time instead of 5 doing this with a lookup table.
It might be possible to use a combination of both techniques with e.g. a 16 bit accumulator, multiplying by 243 to get the value to lookup into bits 23-16 and then bias and shift the incoming 8 bits into the accumulator.
I wonder if NNs could be trained well enough with 1 bit weights (i.e. 0 and 1) with some layers doing addition, while others substraction (i.e. weight sign would be "hardcoded" into the network architecture). Or with zero-less weights (e.g. -1, -0.5, 0.5, 1).
20 comments
[ 5.1 ms ] story [ 47.5 ms ] threadYou can beat the efficiency of 5 trits in 8 bits (1.6) with as few as 17 trits in 27 bits (~1.588), but once you account for rounding up to a whole number of bytes for practical reasons, then beating the efficiency requires going to at least 111 trits in 176 bits (~1.586), or perhaps more practically for fast unpacking, 161 trits in 256 bits (~1.59).
At that level, even if you have, say, 27B trits, the more efficient encodings would save something like 38-45MB (theoretical limit ~48MB), likely at the cost of some slowdown.
The single trit packing is a commonly optimized DBNULL structure for booleans.
Bits/trit approaches the 1.5 asymptote, because that is the fundamental packing limit.
The trick is to use it when you have a trit to start with, like when you have a set which is a tiny bit over a power of two.
There are places where you end up with odd numbers in set sizes, for example when storing a poker hand.
Read Cactus Kev's trick[1] which I think needs a 27 bit section & optimizing it was where I first ran into trit packing.
[1] - http://suffe.cool/poker/evaluator.html
How... how does that help with anything?
> Now digits can be easily extracted from the top two bits of the resulting 10-bit number when multiplying this 8-bit byte by 3.
What? Why? How? This is supposed to be the most insightful part of the post, and it's literally just "Behold!" from that one proof of Pythagorean theorem. Could someone please elaborate it for a non-genius like me?
I ended up feeling that ternary is just icky, because the "middle value" doesn't have an "opposite"
Maybe we should do what quaternions did to complex numbers and just jump from 2 to 4: Quaternary CPUs
I couldn't understand half of the words it spat out but it turns out that using pairs of "quits" as the atomic computation unit to represent complex numbers and/or 2x2 matrices could be ideal for AI etc.
The article is well-written and illustrated. The technique described is used in llama.cpp for running language models like BitNet b1.58 whose weights are stored as ternary types.
> ..in which every single parameter (or weight) of the LLM is ternary {-1, 0, 1}
> significantly more cost-effective in terms of latency, memory, throughput, and energy consumption
The original paper on this technique was published in Feb 2024. (Also linked from the article)
The Era of 1-bit LLMs: All Large Language Models are in 1.58 Bits - https://arxiv.org/abs/2402.17764
However, since then there have only been a few other models using ternary weights. I get the impression that there are factors not considered in the paper which make it less practical than it seemed.
And missed it by one letter. <jk>
I suppose with the recent quantized Bonsai models we're already seeing on-device LLMs for phones and the like… But I (again, forgive my ignorance) assume that there is an order of magnitude or more in performance sitting out there if we get custom hardware instructions.
The interesting questions are if enough LLMs use ternary enough and for long enough into the future to make investments in ternary hardware worth it. Ternary hardware is probably less general purpose than the modern GPU design that is being used for LLMs today and the crossover of "general purpose floating point matrix math engine" for graphics as well as LLMs a useful one, particularly because we know the graphics revenue models pretty well (and gamers are pretty upset at GPU pricing right now because of LLM demand).
You would have a more complicated decoder with rANS though, even if you removed the frequency table lookup (because always 1/3) and you'd only produce one output at a time instead of 5 doing this with a lookup table.
It might be possible to use a combination of both techniques with e.g. a 16 bit accumulator, multiplying by 243 to get the value to lookup into bits 23-16 and then bias and shift the incoming 8 bits into the accumulator.
[1] https://fgiesen.wordpress.com/2014/02/18/rans-with-static-pr...
[2] https://github.com/rygorous/ryg_rans