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?"
HN discussion
- The technique packs 5 ternary digits (trits) into a single 8-bit byte by converting the base-3 integer to a fixed-point fraction, allowing efficient SIMD extraction via multiplication and bitwise masking rather than slow division.
- While the packing achieves near-optimal density, some commenters argue that ternary arithmetic is inherently awkward due to the lack of an 'opposite' for the middle value, suggesting quaternary systems might be more suitable for AI workloads.
- Practical implementations like BitNet b1.58 utilize these ternary weights in llama.cpp, yet the scarcity of subsequent models suggests there are unaddressed practical factors making the technique less viable than the original paper implied.
- Alternative quantization strategies exist, such as the Sherry technique used in Hy-MT2, which constrains groups of four trits to have exactly one zero, enabling 1.25-bit precision that fits exactly into 5 bits with fast lookup table unpacking.