Efficiently Packing Ternary Numbers into 8-bit Bytes

Recently, I was distracted nerd-sniped into finding a way to pack the ternary weights used in BitNet b1.58. The objective was to get as close as possible to the theoretical information density limit of: $\frac{\log(3)}{\log(2)} \approx 1.58496 \text{ bits per digit}$

In this context, I will refer to a "ternary digit" as a trit (analogous to how a "binary digit" is a "bit").

Determining the Optimal Block Size

To ensure that unpacking remains fast and compatible with parallel processing (SIMD), we cannot use infinitely large blocks. We need a block size that balances information density with hardware convenience.

The goal is to find a power of 3 ($3^n$) that sits just below a power of 2 ($2^m$).

Block Size Comparison Table:

As shown, 5 trits fit remarkably well into a single 8-bit byte, resulting in 1.6 bits per trit.

---

The Packing Strategy

The fundamental approach is to treat a sequence of trits as a single number in base-3.

def pack_number(digits: list[int], base: int) -> int:
    number = 0
    for digit in digits:
        assert digit < base
        number = number * base
        number = number + digit
    return number

The SIMD Unpacking Challenge

While you can extract digits using repeated division and modulo operations, these are efficient $\text{slow}$ and often unsupported for integers in SIMD programming.

The Solution: Instead of using modulo to find the least significant digit, we can use multiplication to extract the most significant digit.

Tada! By scaling the number, we can extract digits from the top bits of a 10-bit result when multiplying the 8-bit byte by 3.

This shifts the computational burden to the packing phase. Since LLM weights are packed once but unpacked millions of times during inference, this is an ideal trade-off.

---

Implementation

Packing Trits into Bytes

The following Python function takes values in $\{-1, 0, 1\}$ and packs them.

• Clamp input to $\{-1, 0, 1\}$
• Shift range to $\{0, 1, 2\}$
• Convert to base-3
• Scale to 8-bit range

def pack_trits(digits: list[int]) -> bytearray:
    assert len(digits) % 5 == 0 # Padding not handled here
    n_bytes = len(digits) // 5
    packed = bytearray()
    
    for i in range(n_bytes):
        b = 0
        for j in range(5):
            digit = digits[5 * i + j]
            digit = max(-1, min(digit, 1)) # Clamp
            digit += 1 # Map -1,0,1 -> 0,1,2
            b *= 3
            b += digit
        
        # Ceiling division to prevent truncation errors during unpacking
        b = ((b * 256) + (243 - 1)) // 243
        packed.append(b)
        
    return packed

Unpacking without Modulo

To retrieve the trits efficiently:

def unpack_trits(packed: bytes) -> list[int]:
    trits: list[int] = []
    for byte in packed:
        b = byte
        for i in range(5):
            b = b * 3
            trit = b >> 8 # Extract most significant digit
            trits.append(trit - 1) # Map 0,1,2 -> -1,0,1
            b = b & 0xFF # Keep only the remainder
    return trits

---

Verification and Real-World Use

To ensure this process is entirely lossless, I verified it with a C program that tests every possible 8-bit value (0-242).

#include <stdint.h>
#include <stdio.h>
#include <string.h>

int main(void) {
    char s1[6] = { 0 };
    char s2[6] = { 0 };
    for (uint8_t i = 0; i < 243; ++i) {
        uint8_t n = i;
        // Base-3 representation via modulo (Least Significant Digit first)
        for (int j = 5; j-- >= 0;) {
            s1[j] = (n % 3) + '0';
            n /= 3;
        }
        // Fixed-point scaling
        uint8_t q = (((uint16_t)i) * 256 + (243 - 1)) / 243;
        // Extraction via multiplication (Most Significant Digit first)
        for (int j = 0; j < 5; ++j) {
            uint16_t m = q * 3;
            s2[j] = (m >> 8) + '0';
            q = m & 0xFF;
        }
        printf("%s, %s: %s \n", s1, s2, strcmp(s1, s2) == 0 ? 
               "\033[1;32mPASS\033[0m" : "\033[1;31mFAIL\033[0m");
    }
    return 0;
}

Execution:

$ gcc ternary-packing.c -o ternary-packing
$ ./ternary-packing
# Result: PASS for all 243 values.

This specific technique has been integrated into llama.cpp for TriLMs and BitNet b1.58, featuring optimized SIMD implementations for both ARM NEON and AVX2. You can find the implementation in this pull request.