Packing Ternary Numbers in 8-bit Bytes for SIMD Unpacking

Packing 5 Trits in 8 Bits with 99% Efficiency

Ternary numbers have three possible values per digit (trit). The theoretical minimum storage is log(3)/log(2) ≈ 1.585 bits per trit. For practical SIMD-friendly packing, a block size that aligns well with bytes is needed. The sweet spot: 5 trits fit into 8 bits at 1.6 bits per trit, achieving 99.06% efficiency.

The Packing Scheme

The idea is straightforward: treat the 5 trits as digits of a base-3 number and store that number in a byte. For example, trits [2,1,0,2,1] become 23^4 + 13^3 + 03^2 + 23^1 + 1 = 162 + 27 + 0 + 6 + 1 = 196. This packs into a single byte.

Fast Multiplication Unpacking

Extracting trits via repeated division and modulo is slow and not SIMD-friendly. Instead, the author uses fixed-point multiplication to extract the most significant trit directly.

The trick: Multiply the packed byte by 3, then shift right by 8 bits to get the top 2 bits of the 10-bit result. Those 2 bits encode the most significant trit. Repeat with the remainder.

For example, to extract the first trit from byte b:

uint8_t trit = (b * 3) >> 8;  // yields 0, 1, or 2
b = (b * 3) & 0xFF;           // remove extracted trit

This works because multiplying by 3 scales the value so the top bits represent the trit. The remainder is the lower 8 bits after multiplication.

Packing (with Division)

Packing requires division, but that's acceptable since packing happens less often than unpacking (e.g., once when loading LLM weights). The packing formula:

uint8_t pack_5_trits(uint8_t t0, uint8_t t1, uint8_t t2, uint8_t t3, uint8_t t4) {
    return (((((t4 * 3 + t3) * 3 + t2) * 3 + t1) * 3 + t0) + 242) / 243;
}

The +242 and /243 perform a ceiling division to correct off-by-one errors from truncation during unpacking.

Verification

The author provides a C program that tests all 3^5 = 243 combinations:

#include 
#include 

int main() {
    for (uint8_t t0 = 0; t0 < 3; t0++)
    for (uint8_t t1 = 0; t1 < 3; t1++)
    for (uint8_t t2 = 0; t2 < 3; t2++)
    for (uint8_t t3 = 0; t3 < 3; t3++)
    for (uint8_t t4 = 0; t4 < 3; t4++) {
        uint8_t packed = (((((t4 * 3 + t3) * 3 + t2) * 3 + t1) * 3 + t0) + 242) / 243;
        // unpack
        uint8_t b = packed;
        uint8_t u0 = (b * 3) >> 8; b = (b * 3) & 0xFF;
        uint8_t u1 = (b * 3) >> 8; b = (b * 3) & 0xFF;
        uint8_t u2 = (b * 3) >> 8; b = (b * 3) & 0xFF;
        uint8_t u3 = (b * 3) >> 8; b = (b * 3) & 0xFF;
        uint8_t u4 = (b * 3) >> 8;
        if (u0 != t0 || u1 != t1 || u2 != t2 || u3 != t3 || u4 != t4) {
            printf("FAIL\n");
            return 1;
        }
    }
    printf("PASS\n");
    return 0;
}

Compile and run: gcc -o test test.c && ./test — outputs "PASS".

Real-World Use: llama.cpp

This technique is already merged into llama.cpp via PR #8151 for ternary types used in BitNet b1.58 and TriLM models. SIMD implementations for AVX2 and ARM NEON accelerate unpacking.

Why This Matters

Ternary weights reduce memory and computation in LLMs. Efficient packing/unpacking directly impacts inference speed. The multiplication-based unpacking is easily vectorized, making it ideal for modern CPUs and GPUs.

Next Steps

If you're working with ternary neural networks, adopt this packing scheme. Check the llama.cpp PR for reference implementations. Consider extending to larger block sizes (e.g., 7 trits in 11 bits) if your hardware supports wider SIMD.