Computed Permutation Trellis Coding: Near-Optimal Quantization Designed for Native Hardware Acceleration

We propose Computed Permutation Trellis Coding (CPTC), a low-bit weight format whose decoder multiplies the trellis state by two $16$-bit coefficients and uses the top bits of the products to index a $64$-byte table. Formats that round each value independently, such as INT4, FP4, and NF4, waste $0.6$ or more of their $4$ bits against the information-theoretic ideal; trellis codes recover this loss by encoding values jointly, but prior decoders either store a large table (Random Permutation Trellis Coding, RPTC) or replace it with a hash (QTIP) that fixes the distribution of the decoded values. CPTC computes the table index instead: the index distribution the two multiplications induce is a near-optimal rule for placing codepoints in a small table. One decoder with $16$-bit multipliers, a $64$-byte table and a coefficient pair loaded per configuration serves every bit width $K\in [1,6]$, reproduces the standard integer and floating-point formats exactly, and loses at most $0.07$ bits against the information-theoretic ideal for all $K\le 4$, matching RPTC run two state bits deeper from an $8,192\times$ smaller table and exceeding QTIP's best variant ($3.93$ vs. $3.86$ effective bits at $K=4$). In LLM weight quantization without fine-tuning, CPTC has the lowest KL divergence to the unquantized model at every tested bit width on LLaMA 3.1 8B and 70B Instruct against QTIP's HYB (by up to $27\%$) and 1MAD (by up to $5\%$) codebooks, and at $3$–$4$ bits surpasses even YAQA's fine-tuned $70$B releases. A fused persistent GPU Viterbi kernel encodes an 8B-parameter model in about two GPU-minutes, and the decoder has been built into the weight-load path of a commercial systolic-array accelerator, where, post-layout, it runs at native FP4/FP8 throughput for about $3\%$ of the systolic array's area.