Packing Ternary Numbers into 8-Bit Bytes for Efficient LLM Weights
How to pack ternary numbers in 8-bit bytes
I explored packing ternary digits, or trits, into 8-bit bytes to optimize storage for BitNet b1.58 weights. By fitting five trits into a byte, I achieved 99% efficiency. This method uses fixed-point multiplication for fast SIMD-friendly unpacking, avoiding slow division operations. The technique is now integrated into llama.cpp for TriLMs and BitNet b1.58, enabling faster processing on AVX2 and ARM NEON hardware.
Would it be nice if instead of extracting the least significant digit with modulo, we could extract the most significant digit with a multiplication?
- JoshTriplett
It's impressive how close to optimal this is.
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.
- lioeters
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)
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.
- JKCalhoun
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.
- Diggsey
How does this packing/unpacking scheme compare to just using a lookup table?
- jjgreen
Possible application: https://thedailywtf.com/articles/What_Is_Truth_0x3f_