betaFeedback

WorksComputer Science

Computed Permutation Trellis Coding: Near-Optimal Quantization from Two Multiplications and a 64-Byte Table

Abstract

We propose Computed Permutation Trellis Coding (CPTC), a low-bit quantization format for tensors written once and read many times. Formats that round each value on its own, such as INT4 and FP4, waste a large part of their bits against the information-theoretic ideal. Trellis codes recover this loss by encoding values jointly, but prior decoders either need a large lookup table for their best quality or compute values with a hash that restricts what they can decode. CPTC's decoder multiplies its state by two coefficients and adds the top bits of the products to index a 64-byte table. Because that sum is not uniformly distributed, the rarely used ends of a small table can hold values far out in the tails. One decoder serves every bit width from 1 to 6, reproduces the standard integer and floating-point formats exactly, and comes within 0.07 bits of the ideal at 4 bits. It matches a random-permutation trellis code whose table is thousands of times larger, and exceeds every QTIP codebook. 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 codebooks (by up to 27%). The decoder has been built into the AWS Trainium 4 AI accelerator, where it runs at the throughput of the native FP4 and FP8 formats for a negligible fraction of the systolic array's area. Fused encoding kernels quantize an 8B model's linear layers in under two minutes on one GPU and, in cycle-level simulation, on one Trainium 4 chip.

Introduction

When a large language model generates text for a few users at a time, the speed limit is not arithmetic but memory: every token requires streaming all model weights from memory into the compute units, so halving the bits per weight roughly doubles tokens per second. At four bits and below, though, every 0.1 bit of wasted precision shows up in model quality. Weights are the leading example of a tensor that is written once and read many times, and such tensors set the design point of this paper: the write can afford a search, but every read decodes each value at memory bandwidth, so it must cost no more than a few integer operations.

How good can a format with KK bits per value be? For Gaussian data, which LLM weights are made to resemble by standard preprocessing (§ 2), information theory bounds the error of any KK-bit quantizer: at unit variance its mean squared error DD is at least 4−K4^{-K} [9]. We therefore score quantizers in effective bits, Keff=−log⁡4(D)K_{\mathrm{eff}}=-\log_4(D), so the ideal 4-bit quantizer scores 4.00. Effective bits predict model quality: the quantized LLM’s KL divergence from the original falls smoothly as KeffK_{\mathrm{eff}} rises (Figure 1b). A better Gaussian quantizer is a better LLM quantizer, so the rest of the paper compares formats on KeffK_{\mathrm{eff}}. Formats that round each value on its own fall well short: the best possible, the Lloyd–Max quantizer ([23, 27]), scores 3.36, and INT4 and FP4 lower still (Table 1). The missing 0.6 bits can only be recovered by encoding values jointly.

Figure 1. (a) Effective bits (↑) against trellis depth LL at 4 bits: CPTC, RPTC, the QTIP variants at L=16L=16, the best scalar format (Lloyd–Max) and the optimum 4.00 (Table 2). (b) KL to BF16 (↓, seed 0) of Llama 3.1 8B (filled) and 70B (open) against KeffK_{\mathrm{eff}} at 2, 3 and 4 bits, plus the CPTC depth sweep (triangles). Across rates each bit is worth 4× in KL at 70B and 3–8× at 8B (curves; § 5.3).

Table 1: What each codebook costs and delivers, one column per requirement of § 2 plus the encoder’s search: decoder work and storage per lane, whether one circuit serves every bit width, whether the output distribution can be changed by loading a table, how the encoder searches, and how much of the 4 bits is wasted (↓, bits consumed minus KeffK_{\mathrm{eff}} on i.i.d. Gaussians; sources Table 2, Figure 1a, and Appendix § 13.§ 1; n/r: not reported; NF4: Dettmers et al., [13]; NVFP4: Alvarez et al., [1]). †CPTC reaches QTIP’s quality at L−5L-5, with 32× less search. ‡At 4.25 bits with a per-block scale index.

CodebookDecoder (ops, storage)All KKRetargetableEncode/valueWaste at 4 bits
INT4 / FP4cast, 0×, per width×round0.86 / 0.85
NF4 / Lloyd–Maxlookup, 32 B×, per width× / ✓round0.67 / 0.64
MXFP4 / NVFP4 (4.25/4.5 b)cast + scale, 0×, per width×round1.09 / 1.11
E8P (QuIP#)signs + 2 KiB LUT×, per rate×E8 structured search0.56
Nested E8 (NestQuant)E8 closest point, 0✓×E8 closest point, O(T)O(T)0.36‡
Learned VQMiB LUT×, per rate✓beam search, 2TK2^T Kn/r
TKn/r
LC trellis1 mul + 8–128 KiB LUT✓✓Viterbi, 2L2^L0.06
RPTC128 KiB LUT✓✓Viterbi, 2L2^L0.10
QTIP HYBhash + 2 KiB LUT×, K≤4K \le4✓Viterbi, 2L2^L0.39
QTIP 1MAD / 3INST1–3 int ops, 0✓×, fixed lawViterbi, 2L2^L0.14 / 0.15
CPTC (ours)2 mul + add + 64 B LUT✓, K∈[1,6]K \in[1, 6]✓, exact scalarViterbi, 2L2^L (2L−52^L-5)†0.07

Table 1.

Trellis codes ([25, 37]) do that while keeping decoding simple: each value is decoded from the last LL bits of the code stream, the state, by a fixed map (LL is the trellis depth). A map built into hardware must be cheap, serve every bit width, adapt to new distributions and deliver high quality (§ 2), and prior maps each give one of these up. Random Permutation Trellis Coding (RPTC; [25]) stores a table with 2L2^L entries. Linear congruential (LC) codes ([15]) compute a table index with one multiplication but need kilobytes of table for their best quality. QTIP ([37]) replaces the table with a hash, which fixes the distribution of the decoded values, or keeps a small table that limits which values it can decode.

We show that two multiplications shrink the table to 64 bytes. Our decoder multiplies the state by two coefficients, adds the top bits of the two products, and uses the sum to index the table. The sum is approximately triangular rather than uniform, like the sum of two dice: it lands near the middle of the table often and at its ends rarely. The rarely used end entries can therefore hold values far out in the tails of a bell-shaped distribution, further than a uniformly used table of the same size reaches (§ 4.1). At 4 bits CPTC reaches 3.93 effective bits, matching RPTC with a table 8,192× larger (Figure 1a).

One decoder serves every bit width from 1 to 6 at the same cost. Encoding searches over 2L2^L states per value. Our fused kernels run it at tens of millions to billions of values per second on a GPU and, in cycle-level simulation, on Trainium 4 itself (§ 6.3). This opens the door to other tensors that are written once and read many times: key-value (KV) caches, and the weights in quantization-aware training, which many accelerators read for multiple minibatches between updates. Our main contributions are:

  • Decoder. Two 16-bit multiplications and a 64-byte table come within 0.07 bits of the ideal up to 4 bits, at a cost that is the same for every bit width from 1 to 6 (§ 3 and Table 2).

CodebookStorageK=1K=1K=2K=2K=3K=3K=4K=4K=5K=5K=6K=6
QTIP HYB2 KiB0.9321.9122.8403.6113.9363.936
QTIP 3INST—0.9361.9312.9023.8524.7485.469
QTIP 1MAD—0.9331.9312.9073.8644.7655.514
RPTC128 KiB0.9561.9352.9163.8964.8725.840
LC8–128 KiB0.9601.9502.9453.9384.9305.922
CPTC64 B0.9501.9482.9433.9344.9135.802
CPTCQ7_{Q7}128 B0.9501.9472.9433.9344.9195.869
CPTCQ7-FP16_{Q7\text{-FP16}}256 B0.9491.9472.9433.9354.9265.904

Table 2. Effective bits (↑\uparrow) of every trellis codebook at each bit width, all run at L=16L=16 under one protocol (rows described in the text), with the table each decoder must store (CPTC in 8-bit E2M5 unless marked FP16, others FP16; “—”: nothing stored). Bold: within 0.003 of the underlined column best.

  • Theory. Every scalar format of up to 6 bits is a special case of this decoder (§ 3.4). A bound on what any fixed table can reach, however deep the trellis, shows how much quality the table itself costs (Theorem 1). We also quantify what a smaller table or narrower table entries would cost (§ 5.1).

  • Quality. CPTC leads every QTIP codebook at every bit width, and up to 4 bits it is within 0.01 bits of LC codes that store kilobytes of table (Table 2). Loading a different 64-byte table retargets it to other distributions (§ 5.1 and § 5.2). On Llama 3.1 8B and 70B, quantized without fine-tuning in the YAQA pipeline ([38]), it has the lowest KL divergence at every bit width against QTIP’s table-based and best hash-based codebooks (§ 5.3).

  • Systems. The decoder is built into AWS Trainium 4 ([3]), where it runs at the throughput of the native FP4 and FP8 formats for a negligible fraction of the systolic array’s area (§ 6.1). A fused GPU encoder runs 2,400× faster than QTIP’s released encoder at equal quality: 32× comes from the method, which reaches that quality with a trellis five bits shallower, and the remaining 75× from the fused kernel, which is engineering. A Trainium 4 encoder, in cycle-level

simulation, quantizes tensors on the chip itself. Either one encodes an 8B model’s linear layers in under two minutes (§ 6.3).

Background

LLM weight quantization and the standard-normal reduction. When few tokens are processed at once, an LLM layer’s speed is set by how fast its weights stream from memory, so weights are compressed once and decompressed on the fly in the weight-load path. Incoherence processing [11] with the Random Hadamard Transform (RHT; [36]) reduces this to a clean statistical problem. With HnH_n the orthonormal Hadamard matrix, built by doubling for nn a power of two, and random sign vectors sUs_U, sVs_V, the RHT of an m×nm \times n weight matrix WW is

W~=UWV⊤,U=Hmdiag⁡(sU),V=Hndiag⁡(sV),H1=(1),H2n=12(HnHnHn−Hn).\widetilde{W}=UWV^\top,\quad U=H_m\operatorname{diag}(s_U),\quad V=H_n\operatorname{diag}(s_V),\quad H_1=(1),\quad H_{2n}=\frac{1}{\sqrt{2}}\begin{pmatrix}H_n&H_n\\H_n&-H_n\end{pmatrix}.

UU and VV are orthogonal, so the layer computes Wx=U⊤W~VxWx=U^\top\widetilde{W}Vx with fast transforms on its input and output, and every entry of W~\widetilde{W} is a signed sum of all entries of WW, so after rescaling the entries closely approximate i.i.d. standard-normal draws. We adopt this preprocessing unchanged, so CPTC’s quality is directly comparable to prior work built on it, and what remains is quantizing i.i.d. Gaussian samples as accurately as possible.

Effective bits. Let XX be the unit-variance source (the target distribution after the preprocessing above), X^\widehat{X} its reconstruction, D=E[(X−X^)2]D=\mathbb{E}[(X-\widehat{X})^2] the distortion (MSE), and RX(D)R_X(D) the rate-distortion function of XX under squared error (Berger, [9]): the minimum rate, in bits per value, at which any coder reaches distortion DD. We define effective bits as the Shannon lower bound on RXR_X at the measured distortion, the left end of the classical sandwich

Keff≔−log⁡4DN(X)≤RX(D)≤−log⁡4DN(X+Z),N(X)=e2h(X)2πe,(1)K_{\mathrm{eff}}\coloneqq-\log_4\frac{D}{N(X)}\le R_X(D)\le-\log_4\frac{D}{N(X+Z)},\qquad N(X)=\frac{e^{2h(X)}}{2\pi e}, \tag*{(1)}

where NN is entropy power, hh is differential entropy in nats, and Z∼N(0,D)Z\sim\mathcal{N}(0,D) is independent test-channel noise. A quantizer spending KK bits per value has Keff≤RX(D)≤KK_{\mathrm{eff}}\le R_X(D)\le K, so the deficit K−KeffK-K_{\mathrm{eff}} never understates the wasted rate, and one effective bit is a 4×4\times factor in distortion. For the Gaussian, our default target, the bound is exact (N(X)=1N(X)=1); for the other targets Appendix § 13.§ 2 verifies that the sandwich is thin at K≥3K\ge3.

From scalar to joint quantization. The scalar ceiling of § 1 (Lloyd–Max at 3.36 effective bits, with INT4 and FP4 below it) binds every method that rounds values one at a time. GPTQ ([17]), AWQ ([21]), and SqueezeLLM ([20]) improve the assignment of values to scalar codepoints and inherit the scalar ceiling; CPTC replaces the format itself, standing where INT4 or FP4 stand, so these methods compose with it. Joint quantization escapes the ceiling ([12]): QuIP# ([36]) uses the E8E_8 lattice, NestQuant ([34]) nests it self-similarly, LLVQ ([39]) extends to the 24-dimensional Leech lattice, and learned-codebook vector quantization (VQ; AQLM, Egiazarian et al., 2024; VPTQ, [22]) trains megabyte-scale codebooks. CPTC instead encodes values jointly as a walk through a 2L2^L-state trellis at a per-value decode cost of two multiplies and a lookup.

Trellis-coded quantization. Trellis-coded quantization ([26]) quantizes jointly while spending exactly KK bits per value: each value’s reconstruction depends on its neighbors’ code bits too. The decoder keeps an LL-bit state qq, simply the most recent LL bits of the code stream, and maps it to a value through a fixed function ϕ\phi. In the bitshift subfamily relevant here, reading the next value’s KK bits just shifts them into the state register, which is why decoding stays hardware-trivial. Although only KK bits are stored per value, consecutive values share L−KL-K state bits, so the decoder effectively selects from a 2L2^L-entry codebook, the source of the quality beyond scalar formats. The price is a Viterbi encoding search over all 2L2^L states (§ 3.2).

Prior bitshift trellis codes. The map ϕ\phi from state to value is where prior designs differ. Linear congruential (LC) trellis codes (Anderson & Eriksson, [5]; Eriksson et al., [15]), the earliest computed codebooks, take branch labels from congruential maps of the state and read values at the labels’ quantiles from a stored table. RPTC (Mao et al., [25]) shuffles the 2L2^L states with a stored random permutation PP and assigns state qq the value at quantile (P[q]+12)/2L(P[q] + \frac{1}{2})/2^L of the target’s optimal reproduction law; this provably meets the marginal condition of asymptotically optimal codes and empirically approaches the Shannon bound as LL grows, but the shuffle is 2L2^L entries. QTIP (Tseng et al., [37]) computes ϕ\phi with a hash: its 1MAD and 3INST variants need no table but can only emit the approximately Gaussian law the hash produces, and its HYB variant regains the choice of distribution through a stored kk-means codebook.

Requirements for a hardware codebook. Weight formats are decoded in a datapath fixed at tape-out and replicated per lane beside the multiply-accumulate units, so every lane pays for whatever the decoder holds, which sets four requirements. It must be cheap: a few integer operations and register-resident state per value; a kilobyte-scale table per lane, or one shared with a read port per lane, has no place in the weight-load path. It must be general across bit widths: one circuit serving every rate, ideally reproducing the scalar formats it replaces. It must be flexible in its output distribution: the target law will change over the chip’s lifetime, so retargeting must mean loading state, not respinning silicon. Recent accelerators already expose such state for scalar formats: AWS Trainium 3 converts MXFP4 (Rouhani et al., [33]) operands to MXFP8 through an arbitrary programmer-defined mapping of the 16 codes (Amazon Web Services, [2]), and on NVIDIA Rubin GPUs the tensor-core MMA can read one operand as 3-bit indices into a lookup table of 8 E4M3 values per 8-column slice (NVIDIA, [29]). Both tables are scalar codebooks, so they stay below the scalar ceiling. And it must deliver high quality, or the block is not worth its area. Encoding is not exempt: how often a tensor is rewritten sets how much search it can afford, so the encoder’s search cost counts too. A TT-dimensional VQ searches 2TK2^T K codewords unless it is a lattice with a fast closest-point algorithm; trellis codes pay a Viterbi search over 2L2^L states, which CPTC’s small-LL quality and fused encoders (§ 6.3) make cheap enough to open the door to online use. Table 1 scores existing codebooks on these axes: each prior design gives up at least one, and § 3 shows a computed permutation meets all four.

AWS Trainium. Each NeuronCore of an AWS Trainium chip pairs four compute engines with software-managed on-chip SRAM (Amazon Web Services, [2, 4]). Its main data store, the SBUF, is a two-dimensional memory of 128 partitions: a tensor’s leading axis, the partition dimension, maps onto the partitions, and its remaining axes, the free dimension, run contiguously within each partition. The engines process the partitions in parallel, one lane per partition, so work in different partitions is independent, while moving data across partitions takes an explicit operation. The Tensor Engine is a systolic array of 128×C128 \times C processing elements, one row per partition and CC columns (C=128C = 128 through NeuronCore-v4): it loads a stationary operand from SBUF into the array (the weight load), streams a moving operand past it while Algorithm 1 CPTC decode (per value), with multiplier width Lmax⁡=16L_{\max}=16. Lines 6–10 are an optional storage optimization: for mirror-symmetric codebooks only the lower half T↓\mathcal{T}_{\downarrow} (2Q2^Q entries) is stored and the upper half is served by a mirrored lookup (§ 3.3).

Require: Lmax⁡L_{\max}-bit state qq; coefficients a0,a1∈{0,…,2Lmax⁡−1}a_0,a_1 \in\{0,\ldots,2^{L_{\max}}-1\}; codebook table T\mathcal{T}, or its lower half T↓\mathcal{T}_{\downarrow} under symmetric storage; optional shift ss (default s=0s=0).

  1. Q←log⁡2(∣T∣+1)−1Q \leftarrow\log_2(|\mathcal{T}|+1)-1 ▷ tap width; ∣T∣=2Q+1−1|\mathcal{T}|=2^{Q+1}-1, s∈{0,…,Q−1}s \in\{0,\ldots,Q-1\}

  2. x0←(a0⋅q) mod 2Lmax⁡,x1←(a1⋅q) mod 2Lmax⁡x_0 \leftarrow(a_0 \cdot q) \bmod2^{L_{\max}},\qquad x_1 \leftarrow(a_1 \cdot q) \bmod2^{L_{\max}}

  3. x0←x0≫(Lmax⁡−Q+s),x1←x1≫(Lmax⁡−Q+s)x_0 \leftarrow x_0 \gg(L_{\max}-Q+s),\qquad x_1 \leftarrow x_1 \gg(L_{\max}-Q+s) ▷ x0,x1∈[0,2Q−s−1]x_0,x_1 \in[0,2^{Q-s}-1]

  4. i←x0+x1i \leftarrow x_0+x_1 ▷ i∈[0,2Q−s+1−2]i \in[0,2^{Q-s+1}-2]

  5. return T[i]\mathcal{T}[i] ▷ if the full table is stored; else lines 6–10

  6. if i<2Qi<2^Q then ▷ symmetric-storage lookup (optional)

  7. return T↓[i]\mathcal{T}_{\downarrow}[i]

  8. else

  9. return −T↓[2Q+1−2−i]-\mathcal{T}_{\downarrow}[2^{Q+1}-2-i]

  10. end if

contracting over the partition dimension, and accumulates the results. The Vector Engine runs operations in which each output depends on many inputs, such as reductions; the Scalar Engine runs element-wise ones; the GpSimd Engine’s programmable vector processors run general-purpose code; and DMA engines move data between SBUF and high-bandwidth memory (HBM). § 6 uses this vocabulary for Trainium 4.

Computed Permutation Trellis Coding

CPTC replaces RPTC’s stored random permutation with a computed one: the LL-bit state is multiplied by two fixed coefficients, the top bits of the two products are added, and the sum indexes a 64-byte table of output values. This section gives the decoder (§ 3.1), the encoder (§ 3.2), how the table is filled (§ 3.3), which existing formats the decoder reproduces (§ 3.4), why two multiplications suit bell-shaped targets (§ 4.1), and what any fixed table can reach (§ 4.2).

Decode primitive

The decoder is parameterized by two coefficients a0,a1a_0,a_1 of Lmax⁡L_{\max} bits (we use Lmax⁡=16L_{\max}=16 throughout); a table T\mathcal{T} of 2Q+1−12^{Q+1}-1 entries, where the tap width Q≤Lmax⁡Q\le L_{\max} is the number of top bits kept from each product; and an optional shift s∈{0,…,Q−1}s \in\{0,\ldots,Q-1\} (default 0). The shift lets a decoder built with tap width QQ emulate any smaller tap width Q′=Q−sQ'=Q-s (Proposition 2). Algorithm 1 and Figure 2 show how one value is decoded from the Lmax⁡L_{\max}-bit state qq, of which only the low LL bits carry information (§ 3.2). Every step is an integer operation.

Figure 2. The CPTC decoder for one value (Q=6Q=6, Algorithm 1): the state shifts right to take the next KK stream bits, the top six bits of its two products are added, and the sum indexes the 64-byte table through the mirror fold.

We fix Lmax⁡=16L_{\max}=16 because returns diminish there: encoding cost grows as 2L2^L while the last doubling buys only 0.008 bits (Figure 1a), and 16-bit operands fit SIMD lanes and hardware datapaths. When the table is mirror-symmetric (T[i]=−T[2Q+1−2−i]\mathcal{T}[i]=-\mathcal{T}[2^{Q+1}-2-i]), only its lower half of 2Q2^Q entries is stored, and lines 6–10 of Algorithm 1 read it with one comparison and a conditional sign flip. We use Q=6Q=6 unless stated otherwise, a 127-entry table stored in 64 bytes. This is the size built into AWS Trainium 4’s decode path (§ 6.1) and the smallest that keeps the trellis gain for every K∈[1,6]K \in[1,6] (§ 3.3).

Trellis state and Viterbi encoder

A block of TT values is stored as TKTK code bits. The decoder slides an Lmax⁡L_{\max}-bit window over them in steps of KK and passes each window to Algorithm 1 (Appendix § 11.§ 1 shows the bit layout). Two properties make reading the raw window exact. First, the window needs no masking to LL bits: the coefficients end in Lmax⁡−LL_{\max}-L zeros, so the stream bits above the low LL drop out of the products modulo 2Lmax⁡2^{L_{\max}}. Second, the block is tail-biting: its first Lmax⁡−KL_{\max}-K bits are treated as if appended to its end, which closes the trellis into a cycle, so every value has a full state and no bits are spent on start-up. Values are decoded from the first to the last, so in practice a state register replaces the window: each step shifts it right by KK and takes the next KK stream bits at the top (Figure 2).

The encoder is the standard Viterbi search for the lowest-MSE path through the 2L2^L-state trellis, in O(T⋅2L)O(T \cdot2^L) time and O(T⋅2L−K)O(T \cdot2^{L-K}) backtrace memory. Tail-biting ([37, 24]) costs a second Viterbi pass per block. A tensor that is written once pays this cost once, and a later update re-encodes only the blocks it touches. Our fused encoders keep the cost modest: under two minutes for the linear weights of an 8B model at L=16L=16 on one GPU or, in cycle-level simulation, one Trainium 4 chip (§ 6.3).

Symmetric lookup table and output types

The index i=x0+x1i=x_0+x_1 ranges over [0,2Q+1−2][0,2^{Q+1}-2], that is [0,126][0,126] at Q=6Q=6. For a target distribution symmetric about zero, CPTC stores only the lower half of the table and reads the upper half through the mirrored lookup of Algorithm 1. The fold is exact because the coefficient search keeps only pairs whose index histogram is mirror-symmetric (Appendix § 11.§ 2). Symmetry saves storage but is not required: with a0=0a_0=0 the mirror branch is never taken and the table can hold any distribution. The table size follows from the largest rate: to beat a scalar format at rate KK the table needs at least 2K2^K stored entries, which for K≤6K \le6 gives Q=6Q=6.

Entries are stored one per byte as E2M5 (§ 6.1); a platform without E2M5 can store INT8 instead, at no cost up to K=4K=4 and 0.03 bits at K=6K=6 (0.13 on the Laplacian; Appendix § 13.§ 2).

The table starts from the target distribution and the index distribution of the chosen pair (a0,a1)(a_0,a_1). Let FF be the target’s CDF, let h[i]h[i] count the states whose index is ii, and let G(i)=2−L∑i′≤ih[i′]G(i)=2^{-L}\sum_{i' \le i}h[i'] be the index CDF, with G(−1)=0G(-1)=0. Cell ii owns the probability interval [G(i−1),G(i)][G(i-1),G(i)], and its starting entry is the conditional mean of the target over that interval:

T[i]=EX∼F[X∣F(X)∈[G(i−1),G(i)]].(2)\mathcal{T}[i] = \mathbb{E}_{X\sim F}\left[X \mid F(X) \in[G(i-1),G(i)]\right]. \tag*{(2)}

The target enters only through the table, so retargeting changes only the 2Q2^Q stored values, and one coefficient pair serves every target. (The reported results use one pair per rate, which at L=16L=16 gains at most 0.008 bits over a single unified pair.)

Table generation. Equation (2) assumes each entry represents a quantile interval, but the Viterbi encoder does not assign values that way, least of all at small depth, where it has few paths to choose from and the best table approaches the scalar Lloyd–Max codebook. We therefore generate the table with Lloyd’s iteration on the trellis ([35]), as Eriksson et al. [15] do for LC codes. Starting from Equation (2) rescaled by a depth-dependent factor, we encode synthetic samples of the target with the current table, replace each entry by the mean of the samples assigned to it, repeat, and fit the result to the table’s data type (Appendix § 11.§ 2). This computation can be done offline, once per distribution, rate and trellis depth. At L=KL=K it recovers Lloyd–Max up to the rounding of the data type, and every deeper trellis scores above it.

Multiplicative coefficients and scalar formats

The coefficients also set the trellis depth: L=16−ctz⁡(a0∣a1)L=16-\operatorname{ctz}(a_0 \mid a_1), where ctz counts trailing zeros. For L≤QL \le Q one coefficient is enough: a0=0a_0=0, a1a_1 an odd multiple of 216−L2^{16-L} (Table 6) and s=Q−Ls=Q-L. The choice a1=216−La_1=2^{16-L} is the scalar embedding of Proposition 1. For L>QL>Q, two nonzero coefficients give the near-triangular index distribution that the table exploits. Best coefficients. We search (a0,a1)(a_0,a_1) for each depth LL and rate KK on Gaussian samples, exhaustively at small LL and by sampling above (Appendix § 11.§ 2 lists the pairs and the protocol). At K=4K=4 quality rises with every step in LL and reaches 3.93 effective bits at L=16L=16.

LLK=1K=1K=2K=2K=3K=3K=4K=4K=5K=5K=6K=6Unified
10000, 8000
20000, C000
30000, A000
40000, 5000
50000, 2800
60000, A400
77A00, 7A003A00, 3A00A200, A2006200, C4002E00, 5C000200, 04006200, C400
88700, 87007A00, BD006100, 61001B00, 36007700, DC000400, 81009700, AE00
98580, 85804280, 4280E180, E1806100, B0806500, 9280CC80, D9009900, AC80
108940, 894041C0, 41C08A80, 954039C0, 4E001A40, A4001380, 99C0A880, C440
117920, 792041E0, 41E07480, AD205D00, B3A06040, A8201400, C0A09BE0, A7C0
125F60, 6BB077D0, C7A07DA0, E2D081D0, EE806810, A0207020, 94104550, 82A0
1361C8, 6F203490, 8C488320, DCC851C0, DE38D820, F0083008, 7C1043F8, 83F0
146BBC, 71787708, C88474B0, AB2C6D20, 82A407F0, CFFC5008, E4047E48, C824
156B6E, 73DC792E, C75C1D48, 825211CA, 5E509808, A0025A84, 9DC2483E, 677C
169097, 97AE7AE6, C8B37474, AB1D6A78, 85CF1C04, 3C010AEE, D3379282, A981

Table 6.

CPTC generalizes scalar quantization.

Every scalar format is a special case of the decoder:

Proposition 1 (Scalar embedding). For K∈{1,…,Q}K \in\{1,\ldots,Q\} and any 2K2^K-entry codebook C={cq}\mathcal{C}=\{c_q\} with cqc_q representable in the table data type, the CPTC decoder with a0=0a_0=0, a1=216−Ka_1=2^{16-K}, s=Q−Ks=Q-K, and T[q]=cq\mathcal{T}[q]=c_q produces w^=cq\widehat{w}=c_q for every qq.

The proof is direct from Algorithm 1: a0=0a_0=0 zeros x0x_0, and the shift leaves x1=qx_1=q. Here L=KL=K and the trellis is degenerate. As a corollary, every INTKK, FPKK, Lloyd–Max or other KK-bit scalar format with K≤QK\le Q is a CPTC instance with L=KL=K. (Irrational codepoints need a table type matching the implementation’s output precision, e.g. FP16.)

Adopting the decoder therefore never costs quality: L=KL=K recovers the scalar format exactly. A deeper trellis was better in every configuration we tested: every depth and rate on the Gaussian, and every target of Table 3 at L=16L=16.

β\betaK=1K=1K=2K=2K=3K=3K=4K=4K=5K=5K=6K=6
∞\infty0.84 (0.75)1.91 (1.75)2.94 (2.75)3.95 (3.75)4.95 (4.75)5.89 (5.75)
2.00.95 (0.73)1.95 (1.54)2.94 (2.43)3.93 (3.36)4.91 (4.32)5.80 (5.30)
1.50.94 (0.63)1.94 (1.42)2.93 (2.29)3.92 (3.21)4.89 (4.17)5.74 (5.15)
1.00.93 (0.40)1.91 (1.15)2.90 (1.99)3.88 (2.91)4.79 (3.86)5.48 (4.84)

Table 3. Effective bits (↑\uparrow) of CPTC on targets from uniform (β=∞\beta=\infty) to Laplacian (β=1\beta=1), with the best scalar quantizer for each cell in parentheses; only the 64 table bytes change between rows (L=16L=16, T=256T=256, 3 seeds; entropy-power normalized, so KK is an upper bound in every column; the β=2\beta=2 row repeats Table 2).

Likewise, for L≤QL\le Q RPTC’s 2L2^L-entry codebook fits in CPTC’s table verbatim (Proposition 1 with K←LK\leftarrow L). For L>QL>Q CPTC computes a structured permutation in place of RPTC’s random one, trading 2L2^L entries for two multiplications.

An implementation also emulates smaller configurations (Appendix § 11.§ 3). Say a table data type D\mathcal{D} dominates D′\mathcal{D}' if some scale c>0c>0 makes every value of D′\mathcal{D}', multiplied by cc, a value of D\mathcal{D}.

Proposition 2 (Dominance). A decoder with parameters (Lmax⁡,Q,D)(L_{\max},Q,\mathcal{D}) bit-exactly emulates any decoder with Lmax⁡′≤Lmax⁡L'_{\max}\le L_{\max}, Q′≤QQ'\le Q, and D′\mathcal{D}' dominated by D\mathcal{D}: replace each coefficient aja_j by aj⋅2Lmax⁡−Lmax⁡′a_j\cdot2^{L_{\max}-L'_{\max}}, set the shift s=Q−Q′+s′s=Q-Q'+s' (s′s' the emulated decoder’s shift), and load the table rescaled by cc (outputs then agree up to the factor cc, and exactly when c=1c=1).

The triangular index distribution as a companding law

With only 2Q+1−12^{Q+1}-1 distinct codepoints, the table limits quality at any depth (Theorem 1), so it matters where the codepoints land. The starting table of Equation (2) places them according to how often each index is hit. The index distribution thus acts as a companding law (Bennett, [8]): for target density pp and index law gg, the codepoint density is λ(x)∝p(x)/g(x)\lambda(x) \propto p(x)/g(x). Table generation then moves the values, but the index map still fixes how many states share each entry.

The obvious choice is a uniform index law, with equal probability mass per codepoint, and it is what a single multiplication produces. Its tails are short: with M=127M=127 equal-mass Gaussian codepoints the largest sits at only 2.66σ2.66\sigma, and as a scalar codebook 83% of its error comes from its two end cells. The scalar-optimal placement, λ⋆∝p1/3\lambda^\star\propto p^{1/3} (Panter & Dite, [31]), instead spreads codepoints wider than the data, by 3×\sqrt{3}\times for a Gaussian. The second multiplication moves the table in that direction. The sum of the two products’ top bits is approximately triangular, and its rarely hit edge cells stretch the codebook to a profile about 2×\sqrt{2}\times wider than the data, with the outermost quantile codepoint at 3.67σ3.67\sigma (Figure 3). That lies between the source width and the scalar-optimal 3\sqrt{3}, and as a scalar codebook it stays within 7–17% of the Lloyd–Max optimum at every table size (Appendix § 12.§ 1). The table has to match the index law: filled as if the index were uniform, it costs 0.69 effective bits at L=16L=16, K=4K=4 (3.93 → 3.25, Table 14).

Figure 3. Where the two index laws put their codepoints (M=127M=127, standard normal). Top: equal-mass placement from a uniform index law, red marking the clipped tail. Middle: the triangular law’s quantile placement (the conditional-mean table of Equation (2) puts its outermost entry at 3.74σ3.74\sigma). Bottom: the two index laws over the 127 table cells.

β\betaLloyd–MaxUniform fillRPTCLC, 64 BCPTC (E2M5)CPTC (FP16)
∞\infty (uniform)3.753.533.933.953.953.95
2.0 (normal)3.363.253.903.903.933.93
1.53.213.113.873.863.923.92
1.0 (Laplacian)2.912.783.833.773.883.88

Table 14. Effective bits (↑) at K=4K=4, L=16L=16 on generalized-Gaussian targets, entropy-power normalized so 4.00 is an upper bound in every row (T=256T=256, 3 seeds, std below 0.01). “Uniform fill” is the CPTC table of Equation (2) filled as if the index were uniform, with no table generation; “LC, 64 B” is the one-multiply code of Table 15; RPTC uses the quantiles of each target’s optimal reproduction law (Mao et al. [25]), with no Lloyd step.

Theoretical limits and extensions

Alphabet ceiling. Every decoded value comes from a fixed table, so no encoder and no trellis depth can beat the rate-distortion function restricted to that table (Finamore & Pearlman, [16]):

Theorem 1 (Alphabet ceiling). Let X1,…,XnX_1,\ldots,X_n be i.i.d. with a density and finite variance and let a code of rate KK bits per value (any block length, any encoder) reproduce each XiX_i by some X^i∈C\hat{X}_i \in C, where C⊂RC \subset\mathbb{R} is a fixed finite set (more generally C⊂RVC \subset\mathbb{R}^V for codes that emit VV-tuples, at rate VKVK per tuple, with distortion per value). Then

1n∑i=1nE(Xi−X^i)2≥DC(K):=min⁡{E(X−X^)2:X^∈C, I(X;X^)≤K},\frac{1}{n}\sum_{i=1}^{n}\mathbb{E}(X_i-\hat{X}_i)^2 \ge D_C(K) := \min\{\mathbb{E}(X-\hat{X})^2 : \hat{X}\in C,\ I(X;\hat{X})\le K\},

the alphabet-constrained rate-distortion function. In particular

Keff≤KC(K):=−12log⁡2(DC(K)/N(X))K_{\mathrm{eff}} \le K_C(K) := -\frac{1}{2}\log_2\left(D_C(K)/N(X)\right)

for every trellis depth LL and block size TT, and DC(K)≥N(X) 4−KD_C(K) \ge N(X)\,4^{-K}, with N(X)≤σ2N(X)\le\sigma^2 the entropy power of Equation (1) (equality for the Gaussian).

The ceiling is proved in Appendix § 12.§ 2 and can be computed with the Blahut–Arimoto algorithm. It bounds how much of a codebook’s gap to the Shannon limit is forced by its table. CPTC’s 127-entry E2M5 table caps it at 3.998 effective bits at K=4K=4, so the table’s values account for at most 0.002 bits of its 0.07-bit gap. OTIP HYB’s 512-pair table (1,024 pairs with its sign flip) caps HYB at 3.687 at K=4K=4 and at 3.936 for every K≥5K\ge5, which is the plateau in Table 2 (ceilings in Table 9).

Alphabet∣C∣|C|K=1K=1K=2K=2K=3K=3K=4K=4K=5K=5K=6K=6
Shannon limit∞\infty1.0002.0003.0004.0005.0006.000
Lloyd–Max optimal 127-point table1271.0002.0003.0003.9994.9935.930
CPTC generated table, E2M5 (deployed)≤127\le1271.0002.0003.0003.9984.9875.871
CPTC measured, L=16L=160.9501.9482.9433.9344.9135.802
Equal-mass table, midpoints1271.0001.9952.9553.7864.3164.521
Equal-mass table, midpoints641.0001.9872.8983.5773.8943.966
QTIP HYB pair table1,024 pairs1.0001.9942.9443.6873.9363.936
HYB measured, L=16L=160.9321.9122.8403.6113.9363.936

Table 9. The most effective bits (↑) any code of rate KK can reach with a given reproduction alphabet, at any trellis depth (Theorem 1, standard normal). Measured L=16L=16 rows repeat Table 2; the CPTC row uses the generated L=16L=16 table of each KK. HYB’s alphabet is 512 kk-means pairs with a sign flip on the first component (1,024 pairs at rate 2K2K per pair).

Two further threads are developed in the appendices. Achievable rate (Appendix § 12.§ 3): with one multiplication and a full table (a0=0a_0=0, Q=LQ=L) the decoder is RPTC with the algebraic permutation Pa(q)=aq mod 2LP_a(q)=aq\mathbin{\bmod}2^L in place of a random one. For every odd multiplier aa it provably satisfies the necessary marginal-optimality condition of Mao et al. [25]; the joint conditions, and any such statement for the two-multiply decoder, remain open. In-stream metadata (Appendix § 11.§ 5): parity constraints let the encoder commit auxiliary bits (block scale, zero point, flags) into the codeword itself. Each auxiliary bit committed to a group of gg values costs about 1/g1/g effective bits per value.

Experiments

We evaluate CPTC on (i) i.i.d. source quantization (§ 5.1); (ii) the bimodal matmul-aware density of Ang et al. [6], reached by changing only the table (§ 5.2); and (iii) LLM weight-only quantization

(§ 5.3). Unless noted, CPTC uses L=16L=16, the coefficients of Table 6, T=256T=256 (i.i.d.) or T=128T=128 (matmul), tail-biting encoding, and the generated tables of § 3.3.

I.i.d. source quantization

We generate 2222^{22} i.i.d. samples per target and seed (three seeds unless noted) and report effective bits (Equation (1)). The spread across seeds is about 0.0005 bits: over ten seeds CPTC at K=4K=4 scores 3.9334±0.00053.9334 \pm0.0005 (Appendix § 13.§ 1).

Standard normal at K=4K=4 (Figure 1a). CPTC at L=16L=16 reaches Keff=3.93K_{\mathrm{eff}}=3.93. That matches RPTC run two state bits deeper (3.92 at L=18L=18, Table 11) and exceeds QTIP’s best 4-bit variant (3.86), a score CPTC already matches at L=11L=11. Scalar and block-scaled formats score 0.5–0.8 effective bits lower (Table 1).

LL89101112131415161718
QTIP 1MAD————————3.86——
RPTC3.453.553.643.723.783.823.853.883.903.913.92
LC, 64 B3.363.703.813.863.873.883.893.893.90——
CPTC3.773.813.843.863.893.903.923.933.93——

Table 11. Effective bits (↑) at each trellis depth LL for K=4K=4 (T=256T=256, 2222^{22} samples): RPTC, the 64-byte LC code and CPTC, with QTIP’s 1MAD at L=16L=16 (Table 2). Scalar formats stop at 3.36 (Lloyd–Max; symmetric INT4 3.14, FP4 3.15) and the limit is 4.00.

Codebook quality across bit widths (Table 2). We reran every prior trellis codebook at L=16L=16 under one protocol. The QTIP rows run the authors’ released code and tables; HYB emits value pairs from a 512-pair kk-means table. RPTC is the random permutation of the target’s optimal-reproduction-law quantiles [25]. LC is the stronger of two searched one-multiply forms per column, with its codebook scaled and Lloyd-optimized as its authors prescribe (Appendix § 13.§ 1). The CPTCQ7_{Q7} rows double the table (E2M5 and FP16).

CPTC leads every QTIP variant at every KK, by a margin that grows from 0.014 bits at K=1K=1 to 0.29 at K=6K=6; HYB’s fixed alphabet caps it past K=4K=4 (Theorem 1). With 128–2,048× the storage, LC leads every column: by 0.002–0.004 bits over CPTC for K∈[2,4]K \in[2, 4], 0.010 at K=1K=1 and 0.017/0.12 at K=5/6K=5/6, which CPTCQ7_{Q7} in FP16 narrows to 0.004/0.018.

Beyond the Gaussian (Table 3). The unit-variance generalized Gaussian pβ(x)∝exp⁡(−∣x/α∣β)p_{\beta}(x) \propto\exp(-|x/\alpha|^{\beta}) interpolates from the uniform (β→∞\beta\to\infty) through the normal (β=2\beta=2) to the Laplacian (β=1\beta=1) [28, 7]. For each β\beta only the 64 table bytes change, and KeffK_{\mathrm{eff}} is entropy-power normalized (Equation (1)).

The trellis advantage over the Lloyd–Max scalar optimum of each (β,K)(\beta,K) holds everywhere and grows with tail weight, from 0.20 bits at β=∞\beta=\infty to 0.97 at β=1\beta=1 (K=4K=4). At β=1\beta=1 CPTC nears scalar quality with a full bit less rate (2.90 at K=3K=3 against scalar’s 2.91 at K=4K=4). CPTC exceeds RPTC’s quantile codebooks across the family, by 0.02–0.05 bits at K=4K=4. A table filled as if the index were uniform trails CPTC by more as the tails grow, from 0.42 bits at β=∞\beta=\infty to 1.10 at β=1\beta=1 (Table 14). CPTC meets every target with the same coefficients. On the Gaussian (β=2\beta=2) the gap to the bound is 0.05–0.07 bits for K≤4K \le4 and grows to 0.20 at K=6K=6 as the 127-codepoint ceiling binds.

Why not a smaller decoder. Each part of CPTC’s decode cost (the per-value map, the table size and its data type) has a measured or provable price. One multiplication with a table of the same size trails by 0.01/0.04/0.09/0.14 bits at K=3K=3–6, by more on heavy-tailed targets, and by about twice that at K=3K=3–5 with 32-byte tables (Appendices § 13.§ 1 and § 13.§ 2). A table with Q=K−1Q=K-1, or an INT(KK) table, has only 2K−12^{K}-1 codepoints, one short of a rate-KK scalar quantizer, so no trellis depth can match scalar quality (Proposition 4). This makes Q=6Q=6 the smallest table that can beat scalar at K=6K=6. Two doublings above that floor (Q=K+1Q=K+1 in INT(K+2K+2)) cost at most 0.03 bits against the Q=6Q=6 FP16 reference at every KK (Table 18, Appendix § 13.§ 3).

Table 18: The smallest matched codebook, Q=K+1Q=K+1 stored in INT(K+2K+2), and its effective bits (↑\uparrow; protocol of Table 2): “Scale” is the no-clipping rule of Appendix § 13.§ 3 applied to each row’s own starting table, “Table bits” the stored half (2K+12^{K+1} entries of K+2K+2 bits), and the last two columns the same-size and the Q=6Q=6 codebooks in FP16.

KKQQCodepointsTypeScaleTable bitsKeffK_{\mathrm{eff}}, INT(K+2K+2)same QQ, FP16Q=6Q=6, FP16
127INT31.75120.950.950.95
2315INT42.75321.931.941.95
3431INT55802.922.942.94
4563INT691923.913.933.93
56127INT7164484.904.924.92
67255INT8301,0245.875.905.87

Table 18.

A bimodal target: matmul-aware tables

This experiment shows that CPTC’s table absorbs an arbitrary symmetric target density with no change to the decode path, coefficients or encoder: only the 64 table bytes differ. The target is the optimal scalar point density λ⋆\lambda^\star of Ang et al. [6] for a matrix product whose operand pairs have correlation ρ\rho. The density turns bimodal past a phase transition at ∣ρ∣=1/3|\rho|=1/\sqrt{3}. We build the table by moving each entry of the generated Gaussian table to the same quantile of λ⋆\lambda^\star (Appendix § 13.§ 5). Their work and ours are orthogonal: they improve the codebook for a given rate-KK scalar quantizer, and we improve the coder for a given codebook. This is the table-design flexibility that RPTC pays 2L2^L entries for and QTIP’s hash-based variants give up. It is a demonstration only: a deployment would estimate ρ\rho once per layer or attention head and look up a precomputed table, which we do not evaluate here.

We adopt the synthetic correlated-Gaussian setting of Ang et al. [6] as-is, with both operands quantized, unlike the weight-only rest of the paper. AA and BB are drawn so each output entry’s multiplicative pairs are i.i.d. bivariate standard normal with correlation ρ\rho, and we report the relative Frobenius error of A^B^\hat{A}\hat{B} over 10 trials for A∈Rm×kA\in\mathbb{R}^{m\times k}, B∈Rk×nB\in\mathbb{R}^{k\times n} at m=n=128m=n=128, k=256k=256.

Figure 4 shows that CPTC-MMAWARE (CPTC with the λ⋆\lambda^\star table) has the lowest error at every ρ\rho tested, tied with Gaussian-table CPTC at ρ=0\rho=0. Its edge over the best standard scalar format (NF4; Dettmers et al. [13]) widens from 1.5×1.5\times at ρ=0\rho=0 to 2.2×2.2\times at ρ=0.9\rho=0.9. There it is also 1.8×1.8\times better than Gaussian-table CPTC and 1.2×1.2\times better than the scalar MatMul-Opt of Ang et al. [6]. Trellis coding alone cannot capture the matmul-tail importance that λ⋆\lambda^\star encodes.

Figure 4. Matmul error against operand correlation: relative Frobenius error at 4 bits per value on synthetic correlated Gaussians. The vertical line is the predicted phase transition ∣ρ∣=1/3|\rho| = 1/\sqrt{3}; error bars are the standard error of the mean (SEM) over 10 trials (where not visible, smaller than the markers).

Baselines, scale calibration and the per-ρ\rho numbers are in Appendix § 13.§ 5 (Table 19).

Method0.00.30.50.60.70.80.9
INT40.1620.0440.0380.0310.0320.0270.025
FP40.1590.0430.0340.0330.0310.0300.028
NF40.1390.0360.0290.0260.0260.0230.022
MatMul-Opt ([6])0.1390.0330.0220.0190.0170.0140.012
CPTC-Gauss0.0930.0240.0190.0170.0180.0180.018
CPTC-MMaware0.0930.0220.0160.0140.0130.0110.010

Table 19. Relative Frobenius error (↓\downarrow) of the quantized product against the exact one at K=4K=4 (m=n=128m=n=128, k=256k=256, mean of 10 trials, SEM ≤0.0021\leq0.0021). Bold: best per column.

LLM weight-only quantization

We quantize Llama 3.1 Instruct models in the YAQA pipeline of Tseng et al. [38] without fine-tuning, swapping only the codebook (Table 4; protocol and controls in Appendix § 13.§ 6). CPTCQ5_{Q5} is the 63-codepoint table of the GPU kernel (§ 6.2).

KKCodebookDKL↓D_{\mathrm{KL}} \downarrow W2Perplexity ↓\downarrow W2Perplexity ↓\downarrow C4Acc ↑\uparrow 0-shotDKL↓D_{\mathrm{KL}} \downarrow W2Perplexity ↓\downarrow W2Perplexity ↓\downarrow C4Acc ↑\uparrow 0-shot
8B-Instruct70B-Instruct
16BF1606.5028.02271.403.5246.46077.1
4QTIP HYB0.01316.6088.11771.20.0298†3.685†6.516†76.8
QTIP 1MAD0.01006.5798.09271.50.02383.6476.50076.8
CPTCQ5Q_50.00966.5708.08871.30.02253.6316.50076.9
CPTC0.00956.5668.08671.30.02273.6426.49976.9
3QTIP HYB0.04506.8528.34470.80.0967†4.035†6.649†76.3
QTIP 1MAD0.04056.8248.31470.30.08763.9656.62876.4
CPTCQ5Q_50.03966.8288.29470.60.08563.9686.62176.6
CPTC0.03876.7978.29770.50.08453.9466.62176.6
2QTIP HYB0.24248.4029.79866.70.3281†5.259†7.316†74.3
QTIP 1MAD0.22718.2549.69667.30.32215.2257.28674.3
CPTCQ5Q_50.22128.2289.65367.10.31455.1917.26574.7
CPTC0.22028.2389.63467.40.31765.2107.26974.5

Table 4. Llama 3.1 Instruct quantized in YAQA’s pipeline ([38]) with only the codebook swapped, no fine-tuning: KL to the BF16 model (↓), perplexities (↓) and mean zero-shot accuracy (↑; ARC-c/e, BoolQ, HellaSwag, PIQA; within noise, unbolded). QTIP rows are our runs of its HYB and 1MAD codebooks; the HYB rows match the published HYB numbers within 0.007 KL. KL and perplexities average three RHT seeds (KL spread 0.3–4.1%); †one seed; Acc from seed 0. W2: Wikitext-2. Bold: best per rate and model.

KL tracks the codebook’s i.i.d. effective bits (Figure 1b). log⁡2DKL\log_2 D_{\mathrm{KL}} is a smooth function of KeffK_{\mathrm{eff}} (quadratic fits, r2≥0.997r^2\geq0.997): each effective bit is worth 4×4\times in KL at 70B, is an MSE, and 8×8\times to 3K at 8B from 2 to 4 bits. Within every rate the KL order of the three codebooks is their KeffK_{\mathrm{eff}} order, and KL falls with depth along an 8B sweep (Appendix § 13.§ 6). The i.i.d. gains therefore carry to the model.

CPTC has the lowest KL divergence to the unquantized model at every rate and scale against QTIP’s HYB and 1MAD codebooks. Against HYB, YAQA’s default codebook, the margin grows with rate (9% at K=2K=2, 14% at K=3K=3, 27% at K=4K=4 at 8B) as its 512-pair table saturates (Theorem 1). Against the table-free 1MAD it is 3–5% at 8B and 1–5% at 70B (full-table arm), the ordering of Table 2. The Q=5Q=5 arm costs at most 0.001 KL at either scale and leads at 70B for K∈{2,4}K\in\{2,4\}, so the GPU kernel’s smaller table is no compromise.

Zero-shot accuracy separates rates, not formats: it is within about a point of BF16 at K≥3K \ge3, and the formats drop together at K=2K=2. A preliminary run on Qwen3.8-27B ((Qwen Team, 2026)), a hybrid gated-DeltaNet model, shows the same ordering (Table 22).

KKCodebookDKLD_{\mathrm{KL}} ↓ W2Perplexity ↓ W2†Perplexity ↓ C4Acc ↑ 0-shot
16BF1607.6856.80074.1
5CPTC0.02957.5636.80573.9
4HYB0.07197.2636.81773.7
4CPTC0.05637.4476.81774.0
3HYB0.11757.2706.87974.1
3CPTC0.10607.4756.87073.8
2HYB0.30636.8027.22273.1
2CPTC0.26307.0887.19273.4

Table 22.

Systems

Decoding on AWS Trainium 4

CPTC is implemented on AWS Trainium 4 ([3]), an AI accelerator (§ 2), where the decode primitive sits inside the weight-load path that feeds the systolic array. The hardware additions on top of the existing FP4 dataflow are minimal: a state register per lane, the two coefficient products in the shift-accumulate form of Equation (3), one 6-bit adder (the sum of the two products’ top 6 bits, a 7-bit table index), a 64-byte table held in registers, and the sign flip of the mirrored lookup. Output formatting is shared with the floating-point modes already present. Sized for throughput parity with the native FP4 dataflow at K≤4K \le4 and with FP8 at K≤6K \le6, the decoder occupies a negligible fraction of the systolic array’s area. The design as a whole, CPTC decode path included, has closed timing and is ready for production, so these results describe a deployable datapath rather than a synthesis estimate. The decoder RTL is formally verified against a golden reference of Algorithm 1, and the two multiplications and the index sum fit within one array clock cycle.

Integration. The packed bitstream sits in SBUF like any other stationary operand, and two instructions cooperate to decode it. A table-load instruction copies the 64-byte table from SBUF into the decoder’s table registers and sets (a0,a1,T,s)(a_0, a_1, T, s) in configuration registers from its immediate fields, once per tensor and quadrant of the systolic array. The weight-load instruction then takes a CPTC data type, one per bit width KK, as its input type and decodes with whatever the last table load programmed, so one table load serves any number of weight loads. Its hot path reads 32-bit words of packed code into a state register per lane. Each lane decodes 8 values per cycle via Algorithm 1: at the native FP4 rate a lane is one partition, and at the FP8 rate an even/odd pair of partitions works as one lane, 4 values per partition (the FP4 rate and FP8 rate below). The register-held table is read by all lanes’ lookup muxes in parallel, and the decoded values enter the systolic array’s multiply-accumulate pipeline in the same cycle an FP4 or FP8 value would.

Shift-accumulate products. Consecutive windows overlap, so the window of value tt follows from that of value t+1t+1: qt=((qt+1≪K)∣ct) mod 216q_t = ((q_{t+1} \ll K) \mathbin{|} c_t) \bmod2^{16}, with ctc_t value tt’s KK-bit code. The bits shifted out at the top contribute only multiples of 2162^{16} to a product, so each coefficient’s product xj,t=(aj⋅qt) mod 216x_{j,t} = (a_j \cdot q_t) \bmod2^{16} (j∈{0,1})(j \in\{0,1\}) obeys the same recurrence:

xj,t=((xj,t+1≪K)+aj⋅ct) mod 216.(3)x_{j,t} = ((x_{j,t+1} \ll K) + a_j \cdot c_t) \bmod2^{16}. \tag*{(3)}

A lane decodes its 8 values per cycle as one batch and evaluates this recurrence in parallel inside it, which replaces each 16×1616 \times16 multiplier with a KK-bit shift and one addition of aj⋅cta_j \cdot c_t, a 16×Kmax⁡16 \times K_{\max} product (Kmax⁡=6K_{\max}=6) whose partial-product array is about 3/83/8 the size of the full one.

Data layout (Figure 5). Each tail-biting block of TT values is stored as a [T/8,8][T/8, 8] array whose second axis lies along the systolic array’s contraction dimension (which runs over the 8 values of a word and then across partitions), with the block’s TKTK bits packed into whole 32-bit words. A block never straddles a tile, the part of the array one load instruction fills, so each block stays inside one decode lane (a partition at FP4 rate, an even/odd pair at FP8 rate). The recurrence above therefore stays inside one lane, and the lanes run in parallel. At FP4 rate a block occupies one SBUF partition; at FP8 rate its words alternate across the pair, so a block must span an even number of words. Whole-word packing therefore sets the minimum block size: TKTK a multiple of 32 bits at FP4 rate and of 64 bits at FP8 rate, i.e. TT a multiple of 32/gcd⁡(32,K)32/\gcd(32,K) and of 64/gcd⁡(64,K)64/\gcd(64,K) respectively. The minimum is 8 to 64 values depending on KK, and the T∈{128,256}T \in\{128,256\} used throughout this paper satisfy the constraint for every KK. The layout is compatible with Trainium 4’s microscaling support.

Figure 5. How one CPTC block (K=4K=4, T=32T=32) is laid out in SBUF. Top: the logical [T/8,8][T/8, 8] tile; each row is one 32-bit word of eight 4-bit codes. Middle: at FP4 rate the block fills one SBUF partition. Bottom: at FP8 rate the words alternate over an even/odd partition pair, so the block must span an even number of words. Both rates read 32 bits of packed code per cycle.

Table data type. Every decoded value is a table entry or its negative, so the table’s data type is the decoder’s output format. On Trainium 4 every table entry must be an E2M5E2M5 value. E2M5E2M5 is an 8-bit float with a sign bit, 2 exponent bits (bias 1) and 5 mantissa bits, with subnormals, no infinities and the all-ones magnitude reserved for NaN. Its 253 distinct values span [−7.75,7.75][-7.75, 7.75] in steps of 1/321/32 for magnitudes below 2, 1/161/16 in [2,4)[2,4) and 1/81/8 in [4,7.75][4,7.75].

Throughput. The CPTC path sustains the chip’s native per-cycle weight-load rate: parity with FP4 for K≤4K \le4 and with FP8 for K≤6K \le6. A memory-bound decode step therefore runs at the same tokens per second as the native FP4 path while delivering the quality of Table 4, and lower rates stream proportionally fewer bytes.

Decoding on CPUs and GPUs

Without a native decode unit, the primitive maps to two integer multiplies, two shifts, an add and a small indexed load on x86, Arm and GPUs. Table 5 times the linear layers of a Llama 3.1 8B forward pass at batch 1 against an INT4 kernel that shares each pipeline. The two-multiply and CPU kernels use the 63-codepoint Q=5Q=5 table stored in full, which needs no mirror fold (on GPUs in FP16, the CPTCQ5_{Q5} rows of Table 4; on CPUs in INT8). On stock NVIDIA GPUs, a fused kernel decodes the stream straight into the tensor-core operand registers (Appendix § 14.§ 1). On the bandwidth-bound L40S it runs at 0.98× the speed of the INT4 baseline (3.6× cuBLAS FP16). On the bandwidth-rich H100 it is ALU-bound: 0.62× INT4 for the L=16L=16 two-multiply decoder, and 0.79× for a Hopper-only L=10L=10 state-table variant at 3.84 effective bits. This makes the case for a native decode instruction. On CPUs, CPTC at K=4K=4 streams the forward pass as fast as an INT4 kernel (0.98× on AMD Zen 4, 0.97× on AWS Graviton5; Appendix § 14.§ 2).

PlatformCPTC decoderFP16INT4CPTCCPTC speed vs. INT4
NVIDIA L40Stwo multiplies, L=16L=1619.085.125.240.98×
NVIDIA H100two multiplies, L=16L=165.512.113.400.62×
NVIDIA H100state table, L=10L=105.512.112.670.79×
AMD Zen 4, 64 coresAVX-51251.913.313.60.98×
AWS Graviton5, 96 coresNEON36.08.68.90.97×

Table 5. Time per token for the linear layers of Llama 3.1 8B at batch 1 (ms, ↓): CPTC at K=4K=4 against an INT4 kernel that shares its pipeline, with FP16 for reference. GPUs fuse the decode into the tensor-core GEMM; CPUs decode into the INT8 dot product on all cores of one node. Times cover decode and matmul only.

Encoding on GPUs and Trainium 4

GPU. Our GPU kernel fuses the tail-biting Viterbi search of § 3.2 into one persistent Triton launch. On one L40S its throughput runs from 60 million values/s at L=16L=16, K=4K=4 (T=128T=128) to 3.3 billion at L=10L=10, at MSE within 0.02% of a torch.compile reference on identical inputs. At L=16L=16 it encodes the 7.0 billion values of Llama 3.1 8B’s linear layers in under two minutes. Against QTIP’s shipped encoder, equal-quality encoding runs 2,400× faster on the same GPU (Appendix § 14.§ 3). Of this, 32× is method-level: equal quality at L=11L=11 means 32× less search, since work is ∝2L\propto2^L. The remaining 75× comes from the fused kernel, engineering that a fused encoder for QTIP’s codebooks would also gain. Encoding this fast opens the door to online uses such as KV caches at small LL (3.84 effective bits at L=10L=10).

Trainium 4. The encoder also runs on Trainium 4 itself, so tensors can be quantized where they are consumed. The kernel runs the same two-pass tail-biting search as the GPU kernel, with one block per SBUF partition and the trellis states along the free dimension. The Vector Engine runs the forward passes, and the GpSimd Engine walks the survivors back while other blocks run their forward passes, writing the bitstream directly in the weight-load layout of Figure 5. In a cycle-level simulation of the pre-silicon design at T=256T=256 and K=4K=4, one chip encodes 69 million values/s at L=16L=16 and 4.6 billion at L=10L=10 (a reference point, not a comparison with the GPU), so it too encodes those 7.0 billion values in under two minutes. For K∈[2,6]K \in[2,6] the rate stays within 0.90–1.04× of the K=4K=4 rate (Table 27).

L\KL\backslash K123456
814,62015,51816,46416,58616,328—
97,8148,3338,7748,9248,8468,624
103,8954,1634,4764,5584,5834,546
111,9212,0632,1942,2842,3212,321
129891,0581,0631,1391,1591,170
13498529546564575584
14252263274281283290
15120129138140141141
1642†6367697070

Table 27. Trainium 4 Viterbi encoder throughput per chip (↑, millions of values per second) at every trellis depth and bit width in a cycle-level simulation (T=256T=256, best launch per cell). “—”: not supported, as the backtrace needs L−K≥3L-K \ge3; † rows split across partitions, the only layout that fits.

Limitations and future work

Limitations. The LLM experiments cover only Llama 3.1 8B and 70B, a model family that has since been superseded, and one preliminary run on Qwen3.8-27B (Appendix § 13.§ 6). The Trainium 4 encoder is measured in cycle-level simulation, not on silicon. Without a native decode unit, decode is ALU-bound where bandwidth is plentiful: the H100 runs the L=16L=16 decoder at 0.62× an INT4 baseline (0.79× with an L=10L=10 state-table variant, Table 5), and on Arm the NEON decoder runs K=2K=2 and 3 at only 1.0× and 0.91× the INT4 speed although their streams are shorter (Appendix § 14.§ 2). The primitive is a short, fixed sequence: two 16-bit multiplies, two shifts, an add and a 64-byte table lookup. A single fused decode instruction, like the dot-product and table-lookup instructions CPUs and GPUs added for low-bit formats, would remove that bottleneck, as the Trainium 4 datapath does natively.

Future work. Fast encoding at small LL opens the door to online quantization, such as KV caches and the weights in quantization-aware training. We leave these to future work, along with activation quantization, rotation-free quantization with retargeted tables, and evaluation on architectures such as mixture-of-experts and multimodal models.

Conclusions

CPTC replaces the stored trellis codebook with a computed one: two 16-bit multiplications and a 64-byte symmetric table, where the triangular index law of the two products spreads the codepoints into the tails. One decoder serves every K∈[1,6]K \in[1,6] and the standard scalar formats, meeting all four requirements of § 2. At K=4K=4 it reaches 3.93 effective bits, matching RPTC run two state bits deeper, within 0.005 bits of linear congruential codes that store 8 KiB, and exceeding QTIP. In YAQA’s pipeline it has the lowest KL against QTIP’s HYB and 1MAD codebooks on Llama 3.1 8B and 70B without fine-tuning. A timing-closed implementation in the weight-load path of the AWS Trainium 4 AI accelerator, at FP4 (K≤4K \le4) and FP8 (K≤6K \le6) throughput parity for a negligible fraction of the systolic array’s area, shows the format is realizable in hardware. On x86 and Arm CPUs the decoder runs at INT4 pace at K=4K=4 with a 63-entry table. The format suits any write-once, read-many tensor; weights are the case evaluated here, and its Viterbi encoder also runs on Trainium 4 itself in cycle-level simulation.

Acknowledgements

We thank Albert Tseng for many valuable discussions on trellis-coded quantization. We thank Yida Wang and Jun Wu for encouraging us to pursue this work. We thank Wojciech Romaszkan and Ron Diamant for their help and support in integrating CPTC into AWS Trainium 4, and other colleagues at Annapurna Labs for helping ship it into production.

Appendix

The appendix has four parts, in the order the main text uses them. Appendix § 11 gives the details of the decoder and encoder of § 3: the tail-biting stream layout (Appendix § 11.§ 1), the coefficient tables, search protocol and table generation (Appendix § 11.§ 2), the scalar-format emulation proofs (Appendix § 11.§ 3), and in-stream metadata (Appendix § 11.§ 5). Appendix § 12 is the theory behind § 4.1 and § 4.2: the index-law ablation (Appendix § 12.§ 1), the alphabet-ceiling theorem (Appendix § 12.§ 2), and the achievable-rate reduction (Appendix § 12.§ 3). Appendix § 13 extends the experiments of § 5: the i.i.d. results (Appendices § 13.§ 1 to § 13.§ 3), the matmul-aware methods (Appendix § 13.§ 5) and the LLM details (Appendix § 13.§ 6). Appendix § 14 covers the systems side of § 6: the GPU and CPU decode kernels (Appendices § 14.§ 1 and § 14.§ 2) and the fused Viterbi encoder (Appendix § 14.§ 3); the accelerator is described in § 6.1.

Decoder and encoder details

Tail-biting construction

This appendix gives the stream layout and the block decode procedure behind § 3.2: Figure 6 shows the layout and Algorithm 2 the procedure.

Bit layout and CPTC block decode algorithm

Figure 6. How a block is decoded from the packed bitstream. Top: bit layout for K=4K=4, T=8T=8, Lmax⁡=16L_{\max}=16: value vtv_t’s code occupies bits tKtK to tK+K−1tK+K-1 (bit 0 rightmost), window tt reads the 16 bits starting at bit tKtK, and the last three windows (orange) wrap into the dashed tail-biting copy of the first 12 bits. Bottom: the procedure (Algorithm 2).

Construction. Tail-biting trellis codes were introduced by Ma & Wolf [24] in convolutional coding and adapted to bitshift trellis quantization by Tseng et al. [37]; we use the QTIP construction unchanged. The block’s first Lmax⁡−KL_{\max}-K bits are logically appended to its end (line 1 of Algorithm 2; at depth L<Lmax⁡L < L_{\max} only the first L−KL-K of them affect any decoded value), so the LL-bit windows read at positions 0,K,…,(T−1)K0, K, \ldots, (T-1)K close into a cycle: the start and end states agree by construction and no bits are spent on start-up. The encoder runs Viterbi twice per block (once on the block rotated by T/2T/2, whose path fixes the state at the wrap seam, and once on the block itself with its start state pinned to that state), per Tseng et al. [37].

Table 6 gives recommended (a0,a1)(a_0,a_1) pairs, searched over pairs in [0,2L)2[0,2^L)^2 whose OR is odd, on 2192^{19}–2202^{20} Philox-generated N(0,1)\mathcal{N}(0,1) samples (a selection seed disjoint from every evaluation seed) at the paper’s table-size parameter Q=6Q=6: per depth, a per-KK searched pair for every K∈[1,6]K \in[1,6] and a single unified pair selected on all rates jointly (minimum mean deficit K−KeffK-K_{\mathrm{eff}} over the six rates). The K=4K=4 column is the default pair, from a search exhaustive through L=10L=10 and sampled above (which the plateau below justifies); the other columns re-score up to 2162^{16} mirror-symmetric candidates per depth on all six rates. The pair of each (L,K)(L,K) is then chosen among the best few candidates with generated E2M5 tables under the standard protocol, and every change is confirmed on 2302^{30} samples. Coefficients are in the 16-bit form of Algorithm 1 (16 − LL trailing zeros). For L≤6L \le6, a0=0a_0=0 suffices, since all 2L2^L states map directly into the table; for L≥7L \ge7 the coefficients are nonzero, and, when distinct, produce the near-triangular index law of § 4.1. All searches at L≥7L \ge7 require a perfectly mirror-symmetric index histogram (h[i]=h[126−i]h[i]=h[126-i]), which makes the fold of § 3.3 exact. At low rates and small depths the per-KK winners are equal pairs (a0=a1a_0=a_1, which index the 64 even cells uniformly): there center resolution matters more than tail protection. At K=4K=4 quality is monotone in LL and saturates at Keff=3.93K_{\mathrm{eff}}=3.93 (L=16L=16, K=4K=4); the unified pair is within 0.017 bits of the per-KK best at every rate for L≥12L \ge12.

Table generation. The tables of § 3.3 are generated per target and (L,K)(L,K) at T=256T=256 from 2222^{22} synthetic samples of the target per round: 30 Lloyd rounds (a tail-biting Viterbi encode), then each entry becomes the mean of the samples assigned to its cell, with mirrored cells pooled for L≥6L \ge6 and 20 damped ones, keeping the round that scores best on a held-out set. Generation starts from Equation (2) rescaled by (1+2/n)(1−4−K)\sqrt{(1+2/n)(1-4^{-K})} with n=L−K+1n=L-K+1, a heuristic starting width from the point-density law of fixed-rate high-resolution quantization in nn dimensions (Gersho [18]) with a rate correction (for the generalized Gaussians of Appendix § 13.§ 2, (1+2/n)1/β(1+2/n)^{1/\beta}); for L≤6L \le6, where every state has its own entry, it is run from the Equation (2) table of every odd multiplier a1a_1, each of which orders the states differently, prescreened

Algorithm 2 CPTC block decode from the packed bitstream (tail-biting).

Require: code bits b[0…TK−1]b[0 \ldots TK-1] of one block (KK bits per value, TT values); parameters of Algorithm 1.

  1. b′←b∥b[0…Lmax⁡−K−1]b' \leftarrow b \mathbin{\|} b[0 \ldots L_{\max}-K-1] ▷ tail-biting: wrap the first Lmax⁡−KL_{\max}-K bits

  2. for t=0,1,…,T−1t=0,1,\ldots,T-1 do

  3. q←∑k=0Lmax⁡−1b′[tK+k]⋅2kq \leftarrow\sum_{k=0}^{L_{\max}-1} b'[tK+k]\cdot2^k ▷ little-endian window; no masking to LL needed

  4. w^t←Decode⁡(q)\hat{w}_t \leftarrow\operatorname{Decode}(q) ▷ Algorithm 1

  5. end for

  6. return w^0,…,w^T−1\hat{w}_0,\ldots,\hat{w}_{T-1}

Table 6: The coefficient pairs to use, in hex, for each trellis depth LL: the searched pair for each bit width KK and one unified pair for all rates, searched at Q=6Q=6. The K=4K=4 column is the default pair; for L≤6L\leq6 one pair serves every KK.

with 1212 rounds on 2202^{20} samples with the best three kept. The result is fitted to its data type by 1616 further rounds with every entry snapped to the grid. A final pass then moves single entries to a neighboring grid value while the measured error falls. Reported numbers use seeds disjoint from generation.

Bad pairs and the plateau. Exhaustive Viterbi evaluation at K=4K=4, with Equation (2) tables, of every unordered pair with odd OR (histogram symmetry not imposed) at L=8L=8 (24,640 pairs) and L=10L=10 (393,472), plus a 40,000-pair sample at L=12L=12, shows that failure is governed by the sum Σ=a0+a1 mod 2L\Sigma= a_0 + a_1 \bmod2^L, with ∣Σ∣=min⁡(Σ,2L−Σ)|\Sigma| = \min(\Sigma, 2^L-\Sigma): no pair with ∣Σ∣<2L−5|\Sigma| < 2^{L-5} or 2-adic valuation ν2(Σ)>2\nu_2(\Sigma) > 2 (≈14% of the space) is within 0.05 bits of the optimum at L=8L=8 or 1010. Outside this set the landscape is a broadening plateau: the fraction of pairs within 0.05 bits of the optimum grows from 15% (L=8L=8) to 30% (L=10L=10) to 63% (L=12L=12), and the max-to-median gap shrinks 0.11 → 0.07 → 0.04 bits, so the search only has to avoid the bad set and pick from a large near-optimal one.

All-KK selection. At L=16L=16 the unified pair scores (0.948, 1.945, 2.938, 3.931, 4.906, 5.795) for K=1,…,6K = 1,\ldots,6 (generated E2M5 tables), within 0.008 bits of the per-KK pair at every rate, so joint selection is essentially free at the design point. The stakes are larger at small depths: at L=10L=10 the unified pair gives up 0.02 bits to the default pair at K=4K=4 and gains 0.08–0.09 over it at K∈{3,5,6}K \in\{3,5,6\}, the relevant trade for online small-LL uses (§ 6.3). The paper’s quality tables load the per-KK column for each rate; the unified column serves deployments that fix one pair for all rates.

Coefficients for Q=7Q = 7. Where the 127-codepoint alphabet ceiling binds (K≥5K \ge5), one table doubling recovers about a third of the K=6K=6 deficit in either data type (about half if the entries are also widened to FP16) while keeping the symmetric fold. Re-searching pairs whose 255-cell Q=7Q=7 histogram is full and mirror-symmetric yields, with FP16 tables, 4.926 at K=5K=5 (pair (0xBEC5, 0xC514)) and 5.904 at K=6K=6 (pair (0x06CE, 0x13E7)), with K≤4K \le4 unchanged; in E2M5 at the scale of Appendix § 13.§ 3 the same pairs score 4.919/5.869, the CPTCQ7_{Q7} row of Table 2. A single unified Q=7Q=7 pair (0x518D, 0x781A) is within 0.005 bits of the per-KK winners at every rate. By Proposition 2, Q=7Q=7 hardware serves every Q≤7Q \le7 configuration.

Scalar format emulation

This appendix gives the constructions behind the scalar-format reductions of § 3.4, and proves the dominance rule (Proposition 2).

Integer formats via CPTC. Setting a0=0x0000a_0 = \texttt{0x0000}, a1=216−Ka_1 = 2^{16-K}, s=6−Ks = 6-K, and T[q]=(q−2K−1)/8\mathcal{T}[q] = (q - 2^{K-1})/8 for q∈[0,2K−1]q \in[0,2^K-1] (a signed KK-bit integer ramp at scale 18\frac{1}{8}, every entry an E2M5 value for K≤6K \le6) reduces Algorithm 1 to a direct integer lookup. Since L=16−ctz⁡(a1)=KL = 16 - \operatorname{ctz}(a_1) = K, the trellis is degenerate. All 2K2^K indices fall in the lower half of the table; the symmetric upper half is unused.

FP4 via CPTC at K=4K=4. Setting K=4K=4, a0=0x0000a_0 = \texttt{0x0000}, a1=0x1000a_1 = \texttt{0x1000}, s=2s = 2, and populating the first 1616 entries of T\mathcal{T} with the FP4 codepoints, each of which is an E2M5 value, reduces the decoder to an FP4 lookup.

Dominance-rule mechanics (proof of Proposition 2). The bit-exact emulation works direction by direction. Table direction: the shift ss lets a QQ-sized implementation emulate one built with a smaller table parameter Q′=Q−sQ' = Q-s: for s≥1s \ge1 every index in Algorithm 1 falls below 2Q2^Q, so the mirror branch of Algorithm 1 (lines 6–10) is inactive and the emulated codebook, signs stored explicitly, occupies the first 2Q−s+1−12^{Q-s+1}-1 entries of T\mathcal{T} (the FP4 embedding above uses this). Width direction: replacing aja_j (mod 2Lmax⁡′2^{L'_{\max}}) by aj⋅2Lmax⁡−Lmax⁡′a_j \cdot2^{L_{\max}-L'_{\max}} shifts every product’s bits up in lockstep, and the top-bits extraction of Algorithm 1 line 3 removes the difference; this is checked against the golden reference decoder (Appendix § 14.§ 3). Data-type direction: the dominated table loads after the common rescaling cc that a per-table scale absorbs, e.g. FP4’s codepoints are E2M5 values (§ 6.1).

Encoding auxiliary information into the CPTC bitstream

This appendix develops the in-stream metadata thread of § 4.2. CPTC’s encoder is free to choose, among all bit sequences that decode to a low-MSE reproduction of the input, one whose bits also satisfy a chosen linear constraint. This lets the encoder commit auxiliary metadata (a per-block scale, a zero point, an exponent, a flag) into the CPTC codeword itself, with no separate storage and no change in the encoder’s complexity.

Construction. Commit auxiliary bit bjb_j at the boundary of group jj of gg values by constraining the parity (XOR) of that group’s gKgK emitted code bits to equal bjb_j. The constraint is enforced inside Viterbi without enlarging the state space: track the cumulative parity as one extra bit alongside each state’s accumulated cost, and at every group boundary set the cost of any state whose recorded parity disagrees with the target bit to +∞+\infty. Subsequent steps propagate only consistent paths, so the encoder stays O(T⋅2L)O(T \cdot2^L), the same complexity as auxiliary-free CPTC. This is a heuristic rather than the exact constrained optimum, which would double the state space with the parity bit: when two paths of different parity merge into one state, only the survivor’s parity is kept. The measured cost below includes whatever optimality this forfeits.

Rate cost. Each auxiliary bit fixes one linear constraint on the gKgK code bits committed to it, removing one degree of freedom from the encoder’s search space: 1/g1/g effective bits per value per auxiliary bit. The canonical use is the per-block exponent of an MX-style format (Rouhani et al., [33]): at L=16L=16, K=4K=4, an 8-bit scale per G=64G=64 values (g=8g=8) costs 1/8=0.1251/8 = 0.125 effective bits per value in theory and 0.132 measured, leaving CPTC at K=4K=4 with an in-stream scale at 3.80 effective bits, still well above the 3.36 of the Lloyd–Max scalar. The same construction carries per-block zero points (asymmetric quantization), per-block format flags, or any other small-bit-budget metadata.

Theory

Index-law ablation: uniform vs. triangular composition

This appendix quantifies the statement of § 4.1 that the table has to match the index law: filled as if the index were uniform, a small table loses its trellis gain. Figure 3 shows the two placements and the two laws side by side.

Relation to 1MAD and LC. QTIP’s 1MAD also sums equidistributed quantities (hashed bytes) to obtain a bell-shaped law, but it uses the sum as the value: the decoded number is the sum itself, so the reproduction distribution is whatever the central-limit sum gives and cannot be retargeted. CPTC uses the sum as an index into a table composed with that sum’s law (Equation (2)), which is a companding rule: the law determines where codepoints are dense and the table determines what they are. That separation is what lets a 64-byte table follow a Gaussian, a generalized Gaussian or a bimodal matmul-aware target (§ 5.1 and § 5.2). LC has the same separation of labels from reproducers, but one congruential map gives a near-uniform index law (Proposition 3, Appendix § 12.§ 3).

Codebook level. Table 7 reports exact scalar nearest-codepoint MSE on N(0,1)\mathcal{N}(0,1) for MM-point codebooks vi=F−1((G(i−1)+G(i))/2)v_i = F^{-1}((G(i-1) + G(i))/2), the midpoint quantile of each cell of the index law’s CDF GG, under three index laws: uniform (equal probability mass), symmetric triangular, and the Lloyd–Max optimum (Lloyd, [23]; Max, [27]) as the reference. Triangular tracks Lloyd–Max within 7–17% at every size, while uniform degrades from 2.2× (at M=15M=15) to 29× (at M=511M=511) worse than triangular. The mechanism is overload: the uniform law’s largest codepoint sits at the (M−0.5)/M(M-0.5)/M quantile (2.66 at M=127M=127), and the two unbounded tail cells contribute 83% of its MSE; the triangular law reaches 3.67 (tail share 16%) and Lloyd–Max 4.18 (tail share 2%). Because overload decays only as about 1/(Mln⁡M)1/(M \ln M) while granular error decays as M−2M^{-2} (Panter & Dite, [31]; Bennett, [8]), the uniform law also loses the rate: doubling MM buys only ~2.3× instead of ~4×. Matching the 127-entry triangular codebook with a uniform-composed one takes M>511M > 511: the composition is worth more than 4× in table size.

MMUniformTriangularLloyd–MaxUnifTri\frac{\mathrm{Unif}}{\mathrm{Tri}}TriLM\frac{\mathrm{Tri}}{\mathrm{LM}}
152.52e-21.14e-21.07e-22.21.07
311.00e-22.90e-32.66e-33.51.09
634.17e-37.37e-46.65e-45.71.11
1271.79e-31.88e-41.66e-49.61.13
2557.85e-44.77e-54.15e-516.51.15
5113.50e-41.21e-51.04e-528.91.17

Table 7. Exact MSE (↓) of MM-point Gaussian codebooks built from a uniform vs. a triangular index law, against the Lloyd–Max optimum.

Beyond the Gaussian. The same comparison at M=127M=127 (all sources unit variance): uniform-over-triangular MSE ratio is 9.6× for N(0,1)\mathcal{N}(0,1), 15.6× for Laplacian, and 7.4× for Student-t5t_5. The ratio exceeds 7× for all three targets. The composition benefit is a property of mean-concentrated targets generally, not of the Gaussian.

End-to-end trellis ablation. Table 8 repeats the comparison inside the full CPTC pipeline (L=16L=16, K=4K=4, T=128T=128, the paper’s (a0,a1)(a_0,a_1), Viterbi encoding of 2222^{22} i.i.d. N(0,1)\mathcal{N}(0,1) samples), varying only how the table is populated. Two conclusions. First, filling the table as if the index were uniform costs 0.69 effective bits (3.92 → 3.23) at T=128T=128 with quantile-midpoint tables (the same at T=256T=256 with conditional-mean entries, Table 14) and lands below the Lloyd–Max scalar (3.36). Second, replacing the triangular composition with the scalar Lloyd–Max table of the same size changes nothing (3.917 vs. 3.919): the triangular composition already places each entry inside its cell, and at L=16L=16 the partition itself is also near-optimal. The composition assumes uniformly random states, while the encoder visits them non-uniformly; the two index distributions differ by only 0.002 in total variation at L=16L=16, K=4K=4. This compares visit frequencies only; which samples an entry receives is a separate matter, addressed by table generation (§ 3.3).

Effective entriesTable lawKeffK_{\mathrm{eff}}
127 (s=0s=0)Uniform composition3.233
127 (s=0s=0)Scalar Lloyd–Max table3.917
127 (s=0s=0)Triangular composition3.919
63 (s=1s=1)Uniform composition3.197
63 (s=1s=1)Triangular composition3.903
31 (s=2s=2)Uniform composition3.048
31 (s=2s=2)Triangular composition3.821

Table 8. Effective bits (↑) of the full CPTC pipeline when only the law that fills the table changes (L=16L=16, K=4K=4, T=128T=128, 2222^{22} samples; quantile-midpoint tables, before table generation).

Alphabet ceilings: what the table can and cannot cost

CPTC’s decoder emits values from a fixed table, 127 entries at Q=6Q=6. Proposition 4 bounds what such a table can achieve when it has at most 2K2^K values. Theorem 1 in § 4.2 gives the general form of that bound, a restatement of the classical alphabet-constrained rate-distortion function [16, 9], which Eriksson et al. [15] also use as the reference for LC codes. This appendix proves it, computes it for the CPTC and HYB alphabets of Table 2, and uses it to bound how much of CPTC’s gap to the Shannon limit the set of table values forces.

Proof of Theorem 1. Let BB be the nKnK-bit codeword, so I(Xn;X^n)≤I(Xn;B)≤H(B)≤nKI(X^n;\hat{X}^n) \le I(X^n;B) \le H(B) \le nK. Since the XiX_i are independent and X^n\hat{X}^n is a function of BB, I(Xn;X^n)≥∑iI(Xi;X^i)I(X^n;\hat{X}^n) \ge\sum_i I(X_i;\hat{X}_i) (independence and the chain rule; [9]). Each X^i\hat{X}_i lies in CC, so I(Xi;X^i)≥RC(Di)I(X_i;\hat{X}_i) \ge R_C(D_i) with Di=E(Xi−X^i)2D_i=\mathbb{E}(X_i-\hat{X}_i)^2 and RCR_C the rate-distortion function with reproduction alphabet CC, which is convex and nonincreasing because the alphabet constraint is per letter and preserved under time sharing. Hence nK≥∑iRC(Di)≥nRC(Dˉ)nK \ge\sum_i R_C(D_i) \ge nR_C(\bar{D}), i.e. Dˉ≥DC(K)\bar{D} \ge D_C(K). Dropping the alphabet constraint gives the Shannon bound.

In the classical random-coding setting the ceiling is approached: for a memoryless source and a bounded distortion measure there exist time-varying trellis codes whose distortion approaches the rate-distortion function exponentially in the constraint length (Viterbi & Omura, [40]). RPTC and CPTC are time-invariant, and squared error on a Gaussian is unbounded, so for them KC(K)K_C(K) is a bound, not a proven asymptote. It is also computable: DC(K)D_C(K) is a convex program over the output law on CC, and the Blahut–Arimoto iteration (Blahut, [10]) converges to it. We discretize N(0,1)\mathcal{N}(0,1) on 17,001 points of [−8.5,8.5][-8.5,8.5] (step 0.001, far below every codepoint spacing) and bisect the log-slope to a bracket of 10−410^{-4}. As a check, the 16-point Lloyd–Max alphabet at K=4K=4 gives KC=3.3589K_C=3.3589, the scalar Lloyd–Max value to four decimals, as it must (with ∣C∣=2K|C|=2^K the optimal assignment is deterministic). For HYB the alphabet is a set of value pairs, so the same computation runs in two dimensions at rate 2K2K per pair on a 401×401401 \times401 grid over [−6,6]2[-6,6]^2, with the pair table normalized to unit variance as in Table 2.

What the table costs. Every measured value in Table 9 lies at or below its ceiling (HYB attains it for K≥5K \ge5), as the theorem requires, and the ceilings split CPTC’s gap to Shannon into a part its table values force (K−KCK-K_C) and a remainder (KCK_C–measured). At K≤4K \le4 at most 0.002 bits of the 0.05–0.07-bit gap of Table 2 is forced by the set of table values; the remainder depends on depth and on the map from states to entries. At K=5K=5 the table values force 0.013 of the 0.087-bit gap, at K=6K=6 0.129 of 0.198, the rigorous form of the alphabet ceiling that § 5.1 and Appendix § 11.§ 2 observe. The Lloyd–Max 127-point row is a reference alphabet: the deployed table is within 0.001 bits of it through K=4K=4 and 0.06 below at K=6K=6. For HYB the ceiling saturates at 3.936 from K=5K=5 on (the rate constraint stops binding once it exceeds the alphabet’s nearest-neighbor entropy of 9.92 bits per pair), and the measured plateau is 3.936: HYB’s fixed 512-pair table is provably what caps it past K=4K=4, and no trellis depth can lift it.

One multiplication, scale, and depth. The equal-mass rows quantify the tail argument of § 4.1. With the equal-mass composition at its natural scale the extreme codepoint sits at the quantile 1−1/(2M)1-1/(2M), and the overload error alone bounds Keff≤12log⁡2(ln⁡M)+o(1)K_{\mathrm{eff}} \le\frac{1}{2}\log_2(\ln M)+o(1) regardless of KK or LL (the exact overload integral gives 4.16 at M=64M=64 and 4.74 at M=127M=127; the closed form alone 4.03 and 4.63), while the two-multiply law places the extreme cell at mass 2−2Q2^{-2Q}, an overload of 2.7×10−52.7 \times10^{-5} at Q=6Q=6, below the Shannon distortion for every K≤7K \le7. This bound is a property of the composition, not of the multiplication count: stretching the 127-point uniform-law table by a factor κ\kappa raises its ceiling at K=4K=4 from 3.82 at κ=1\kappa=1 (conditional-mean entries; 3.79 with quantile midpoints, Table 9) to 3.92 (κ=1.1\kappa=1.1) and 3.98 (κ=1.3\kappa=1.3). What remains for a one-multiply table is a finite-depth cost (Table 10): with a tuned stretch it recovers from 3.78 to 3.88 at K=4K=4 and from 4.37 to 4.80 at K=5K=5, while the two-multiply table is nearly scale-insensitive (+0.005 and +0.016 at its best stretch, close to the rescaling table generation starts from) and still leads by 0.06 and 0.12 bits at matched table size (128 vs. 127 cells; the generated 64-byte tables are 0.04 and 0.09 apart, Appendix § 13.§ 1), and by 0.11 and 0.25 against a 64-cell one-multiply table. One multiplication can protect the tails, but only with a stretch worth 0.1–0.4 bits at 128 cells, and then trails at matched table size; for the triangular law the stretch is a 0.01-bit refinement.

TableKKκ=1.0\kappa=1.01.051.11.21.31.4
One multiply, 64 cells43.6123.6973.7553.8173.8253.802
One multiply, 128 cells43.7773.8323.8623.8783.8583.820
Two multiplies (CPTC), 127 cells43.9303.9353.9323.9083.8713.826
One multiply, 64 cells53.9864.1544.2924.5024.6224.672
One multiply, 128 cells54.3744.5264.6294.7604.7964.790
Two multiplies (CPTC), 127 cells54.9024.9164.9184.9014.8664.822

Table 10. Effective bits (↑\uparrow) at L=16L=16 when the table is stretched by a factor κ\kappa: one-multiply tables with conditional-mean entries (best of 16 random odd multipliers, chosen at κ=1\kappa=1 on held-out data) against the two-multiply table of Equation (2) in FP16, before table generation (T=256T=256, 3 seeds).

Achievable rate and the limit LL to infinity

The classical achievability results are Viterbi & Omura [40] (time-varying trellises with random branch labels achieve the rate-distortion function of an i.i.d. source under a bounded distortion measure) and Gray [19] (a non-constructive existence proof for time-invariant trellis codes). Mao et al. [25] complement these with necessary conditions on every asymptotically optimal stationary code (the marginal reproduction distribution converges to a Shannon-optimal one; finite-order joints factor; the reproduction whitens; the code bits approach fair coins) and prove that RPTC satisfies the marginal condition. Their proof uses one property of the random permutation, bijectivity, so it transfers deterministically to the one-multiply, full-table case of CPTC, for every odd multiplier:

Proposition 3 (Reduction and marginal optimality). With a0=0a_0=0, a1=a⋅216−La_1=a\cdot2^{16-L} for odd aa, Q=LQ=L, s=0s=0, and TT holding the target’s 2L2^L quantile values (RPTC’s rule; Equation (2) gives the cell means instead, with the same limit), CPTC is RPTC with the specific permutation Pa(q)=aq mod 2LP_a(q)=aq\bmod2^L in place of a random one: PaP_a is a bijection for every odd aa, and the decoder computes ϕ(q)=T[Pa(q)]\phi(q)=T[P_a(q)]. Consequently, for any target with CDF FF and finite variance, the decoded-state marginal under uniform states is the exact 2L2^L-point quantile discretization of FF, independent of aa, and converges weakly (and in Wasserstein-2) to the target as L→∞L\to\infty, so under uniformly distributed states this case satisfies the necessary marginal condition of Mao et al. [25] for every odd multiplier.

The condition is necessary, not sufficient, and does not discriminate among coefficients: the identity permutation (a=1a=1) satisfies it and yields a poor code. It concerns the optimal reproduction distribution, N(0,σ2−D)\mathcal{N}(0,\sigma^2-D) for Gaussian MSE, not the source; since Proposition 3 holds for any loaded FF, the table can be composed to the test channel, which at our rates is numerically indistinguishable from the source (σ2−D≈0.996\sigma^2-D\approx0.996 at K=4K=4). The same reduction places one-multiply CPTC inside the linear congruential trellis family of Eriksson et al. [15]: PaP_a carries the bitshift dynamics to an affine recursion, Pa((q≪K)∣u)=(Pa(q)≪K)+au mod 2LP_a((q\ll K)\mid u)=(P_a(q)\ll K)+au\bmod2^L, so the permuted state follows their generating LC recursion and the destination-state labels realize their affine congruential label rule. In neither family is a decode-time recursion implied; for CPTC the incremental update (Equation (3)) is an optional optimization.

What neither family has is an achievability theorem. The joint conditions are open even for RPTC: Mao et al. [25] anticipate “a source coding theorem using random coding ideas”, and none has appeared; for CPTC with two coefficients and a small table both the marginal and the joint conditions are open. All CPTC results are at finite L≤16L\leq16, where the per-LL comparison with RPTC (Table 11) is direct evidence and no such theorem is needed.

Extended results

Extended i.i.d. source-quantization results

This appendix collects the i.i.d. results that § 5.1 summarizes: the trellis-depth sweep behind Figure 1a (Table 11), the block-size sweep, the block-scaled scalar formats, the RPTC search-budget control, the LC baseline construction with the headline-margin precision, and the lattice VQ baselines of Table 1. Each baseline follows its own paper: RPTC takes the quantiles of N(0,1−4−K)\mathcal{N}(0,1-4^{-K}) under a random permutation, in 16 bits and with no Lloyd step; QTIP runs the authors’ code and tables, with codebook and data matched in scale as in its pipeline; LC is described below. The CPTC and LC tables are Lloyd-iterated.

Block size TT. Larger TT gives the Viterbi encoder more freedom to find a good cyclic walk; smaller TT adds tail-biting boundaries. Empirically (Table 12) quality saturates near T=128T=128 on the standard normal at K=4K=4, L=16L=16.

Block size TT163264128256
KeffK_{\mathrm{eff}}3.243.713.873.923.93

Table 12. How effective bits (↑) depend on the block length TT (K=4K=4, L=16L=16, standard protocol).

Block-scaled scalar formats. The 4-bit formats that hardware executes natively attach one 8-bit scale to each group of GG values: MXFP4 (Rouhani et al., [33]) an E8M0 (power-of-two) scale with G=32G=32, 4.25 bits per value, and NVFP4 (Alvarez et al., [1]) an E4M3 scale with G=16G=16, 4.5 bits. Table 13 scores both on the standard normal under the protocol of § 5.1 (2222^{22} samples, round-to-nearest, the accelerator’s bit-exact microscaling library, each format’s own per-group max-abs scale rule: the shared E8M0 exponent of the group maximum for MX, an E4M3 scale for NVFP4), together with the INT4 element type and the 6-bit variants. A power-of-two scale buys nothing on the whitened i.i.d. source (MXFP4 is within 0.01 bits of per-tensor FP4); an E4M3 scale acts as a mild compander, worth 0.1–0.4 bits, but costs 0.25–0.5 bits of rate. CPTC carries a block scale without leaving its KK bits per value: the in-stream 8-bit scale per 64 of Appendix § 11.§ 5 keeps 3.80 effective bits at exactly 4 bits, 0.4 above NVFP4 at 4.5. Block scaling earns its keep on unrotated weights with outliers, which the RHT removes, so these are statements about the i.i.d. regime only.

Is CPTC’s edge just search budget? The trellis-depth sweep of Table 11 (plotted as Figure 1a) shows CPTC ahead of our RPTC reimplementation at every LL. CPTC’s coefficients are the best of a search (exhaustive through L=10L=10, sampled above), while each RPTC number is a random draw, so we gave RPTC a search too: the best of 100 random permutations on a held-out 2202^{20}-sample normal set, evaluated on the standard 2222^{22}-sample set. Selection gains far less than the gap to CPTC: best-of-100 RPTC reaches 3.49 at L=8L=8 (vs. 3.45 single-draw, 3.77 CPTC), 3.78 at L=12L=12 (vs. 3.78, 3.89), and 3.90 at L=16L=16 (vs. 3.90, 3.93). Random-permutation distortion concentrates tightly (worst-of-100 to best-of-100 spans 0.08 bits at L=8L=8 and under 0.02 from L=12L=12), so selecting among random permutations does not close the gap to CPTC. Extending the reimplementation to L∈{17,18}L \in\{17,18\} gives the RPTC L=17/18L=17/18 entries of Table 11 (3.91 and

ElementScaleGGbits/valueKeffK_{\mathrm{eff}}Format
FP4 E2M1E8M0324.253.16MXFP4
FP4 E2M1E8M0164.503.18
FP4 E2M1E4M3324.253.30
FP4 E2M1E4M3164.503.39NVFP4
INT4E8M0324.252.86
INT4E4M3164.503.53
FP6 E2M3E8M0326.255.15MXFP6
FP6 E2M3E4M3166.505.33
FP4 E2M1per-tensor—4.003.15
NF4per-tensor—4.003.33
Lloyd–Maxper-tensor—4.003.36scalar optimum
CPTC K=4K=4in-stream 8-bit644.003.80Appendix § 11.§ 5
CPTC K=4K=4per-tensor—4.003.93
CPTC K=6K=6per-tensor—6.005.80

caption: Block-scaled scalar formats on a standard normal: element type, scale type and group size GG, total bits per value including the scale, and effective bits (↑\uparrow; standard protocol, round-to-nearest, bit-exact microscaling library). Reference rows: per-tensor scalar formats, and CPTC from Table 2 and Appendix § 11.§ 5.

:::

3.92), so CPTC at L=16L=16 (3.93) matches RPTC two state bits deeper. CPTC’s edge at equal depth has no theorem yet.

The LC baseline and headline-margin precision. The LC row of Table 2 reports, per rate, the stronger of two searched one-multiply constructions, both run under the standard protocol with our tail-biting encoder. (i) Axiom SR/LC, the construction of Eriksson et al. [15]: MS=216−KM_S = 2^{16-K} shift-register states, per-branch labels li(u)=(g⋅i+a(u)) mod MLl_i^{(u)} = (g \cdot i + a^{(u)}) \bmod M_L with ML=MSM_L = M_S, one shared odd generator and maximally separated offsets a(u)=α+uML/2Ka^{(u)} = \alpha+ uM_L/2^K (their Theorems 1–2, extended to K≥3K \ge3), best of 150 random (g,α)(g,\alpha) on a held-out seed. Its reproduction values follow their paper: the source quantiles at the labels times a scale factor chosen on held-out data (their Eq. 17), then optimized by the generalized Lloyd algorithm on the trellis (their Section IV-A), the procedure § 3.3 uses for CPTC. It supplies the LC row at K≤4K \le4 (0.960/1.950/2.945/3.938). (ii) Full-codebook computed permutation (Proposition 3: a0=0a_0 = 0, Pa(q)=aq mod 216P_a(q) = aq \bmod2^{16}, 2162^{16}-entry codebook built the same way, best of 200 odd multipliers per rate), a strengthening beyond their paper; it supplies K=5K=5 (4.930) and K=6K=6 (5.922, against the axiom form’s 5.892). On the winning forms the scale factor is worth up to 0.014 bits and the Lloyd step up to 0.005 (0.03 dB, in line with the <0.04 dB their paper reports for Gaussians). At CPTC’s storage and data type (the labels reduced to 128 cells by their top bits and a mirror-symmetric E2M5 table, 64 bytes) the axiom construction, searched at that size (best of 600 random (g,α)(g,\alpha)), with the same two steps reaches 0.957/1.948/2.932/3.898/4.820/5.661 at K=1,…,6K=1,\ldots,6: ahead of CPTC at K=1K=1, level at K=2K=2 and behind by 0.011/0.036/0.093/0.141 at K=3K=3–6. With both tables halved (64 labels against CPTC’s 63-entry Q=5Q=5 table, 32 bytes each) it reaches 0.957/1.944/2.914/3.848/4.705 at K=1,…,5K=1,\ldots,5 against CPTC’s 0.948/1.948/2.942/3.928/4.868: the gap at K=3K=3–5 roughly doubles, to 0.027/0.080/0.163 (at K=6K=6 neither 63 nor 64 values can beat the 64-level scalar quantizer, Proposition 4). Across depth at K=4K=4 it is the LC row of Table 11; below L=11L=11 it has fewer than 128 labels, one per state, and its L=16L=16 cell is the K=4K=4 value above. Their Definition 3 read literally, with labels taken modulo 128, depends on only K+7K+7 state bits and scores lower (3.861 at K=4K=4).

For the headline margins we also report 10-seed precision: CPTC L=16L=16, K=4K=4 scores 3.9334 ±\pm 0.0005 and RPTC L=18L=18, K=4K=4 scores 3.9228 ±\pm 0.0004. A random permutation beats CPTC’s Q=6Q=6 table in two cells of Table 2: K=1K=1 (0.956 against CPTC’s 0.9497 ±\pm 0.0004), where its reproduction law N(0,1−4−K)\mathcal{N}(0,1-4^{-K}) is narrowest, and K=6K=6 (5.840 vs. 5.802).

Lattice VQ baselines (Table 1). The E8P and nested-E8 entries are our runs of the authors’ released code on the protocol of Table 2 (2222^{22} samples, three seeds). QuIP#′′^{\prime\prime}’s E8P is its 2-bit codebook (256 absolute-value entries with sign flips and a ±14\pm\frac{1}{4} shift, 2162^{16} points in 8 dimensions); its 4-bit codebook quantizes the residual with a second, rescaled E8P stage, and its 3-bit codebook with a 1-bit E8 stage. We sweep the input and residual scales around the released values: K=2K=2 gives 1.727 at the released scale (0.0913 MSE, against the 0.089 Tseng et al. [37] report for the same codebook), K=3K=3 gives 2.541, and K=4K=4 gives 3.444 (3.351 at the released scales). NestQuant’s nested Gosset code maps each 8-vector to the E8 closest point, reduces modulo mm (m=16m=16 at 4 bits) and decodes with a second closest-point search; its encoder picks one of kk scales per block, a side channel of log⁡2k/8\log_2 k/8 bits per value, under the shared pseudorandom dither of the released code. With a single scale (exactly 4 bits, scale swept, overload rate 10−410^{-4}) it reaches 3.03 effective bits, below the Lloyd–Max scalar ceiling, because one scale’s Voronoi shaping region must enclose the Gaussian tails; with k=2k=2 and k=4k=4 scales chosen by exhaustive subset search it reaches 3.60 at 4.125 bits and 3.89 at 4.25 bits, deficits of 0.53 and 0.36 bits against its own rate. At 2 bits (m=4m=4) the same runs give 1.09, 1.54 (2.125 bits) and 1.77 (2.25 bits), against 1.727 for E8P and 1.948 for CPTC at exactly 2 bits. The Leech-lattice codebook of van der Ouderaa et al. [39] has no released implementation; its paper reports 0.078 MSE at 2 bits (1.84 effective bits) and no 4-bit figure.

Generalized-Gaussian targets: normalization and extended results

This appendix supports the beyond-the-Gaussian experiment of § 5.1 (Table 3): the entropy-power normalization and its verified tightness, the K=4K=4 method comparison of Table 14, the 64-byte LC comparison (Table 15) and INT8 tables (Table 16). For each β\beta the generation of § 3.3 starts from Equation (2) (empirical index intervals, per-cell conditional mean under pβp_\beta in closed form through incomplete gamma functions) and its result is fitted to E2M5 at a per-β\beta scale chosen on one held-out seed, which keeps it within 0.01 bits of the FP16 one at K=4K=4 for every β\beta, with the same (a0,a1)(a_0,a_1) and encoder throughout.

β\betaK=1K=1K=2K=2K=3K=3K=4K=4K=5K=5K=6K=6
∞\infty0.845 (−0.007)1.910 (−0.001)2.939 (−0.002)3.953 (−0.004)4.956 (−0.006)5.934 (−0.043)
2.00.956 (−0.009)1.947 (0.000)2.931 (0.011)3.896 (0.037)4.816 (0.096)5.660 (0.140)
1.50.945 (−0.004)1.932 (0.005)2.908 (0.022)3.858 (0.060)4.749 (0.137)5.548 (0.194)
1.00.916 (0.010)1.894 (0.019)2.854 (0.049)3.767 (0.112)4.590 (0.203)5.313 (0.164)

Table 15. Effective bits (↑\uparrow) of the one-multiply LC code with a 64-byte E2M5 table on generalized-Gaussian targets, with CPTC’s lead over it in parentheses (negative: LC ahead). L=16L=16, T=256T=256, 3 seeds.

β\betaK=1K=1K=2K=2K=3K=3K=4K=4K=5K=5K=6K=6
∞\infty0.838 (0.000)1.909 (0.000)2.937 (0.000)3.948 (0.001)4.949 (0.001)5.857 (0.034)
2.00.947 (0.000)1.947 (0.000)2.942 (0.000)3.933 (0.000)4.910 (0.001)5.767 (0.032)
1.50.941 (0.000)1.937 (0.000)2.930 (0.000)3.918 (0.000)4.882 (0.004)5.736 (0.006)
1.00.926 (−0.001)1.913 (0.000)2.903 (0.000)3.876 (0.003)4.782 (0.011)5.346 (0.131)

Table 16. Effective bits (↑\uparrow) of CPTC with an INT8 table on generalized-Gaussian targets, with its deficit against the E2M5 table in parentheses. L=16L=16, T=256T=256, 3 seeds.

Normalization and its tightness. For the unit-variance generalized Gaussian the differential entropy has the closed form h(X)=β−1+ln⁡(2αΓ(1/β)/β)h(X)=\beta^{-1}+\ln(2\alpha\Gamma(1/\beta)/\beta) with α=(Γ(1/β)/Γ(3/β))1/2\alpha=(\Gamma(1/\beta)/\Gamma(3/\beta))^{1/2} (Nadarajah [28]), which is what Equation (1)’s N(X)N(X) uses. As β→∞\beta\to\infty it gives the uniform’s N(X)=12/(2πe)≈0.703N(X)=12/(2\pi e)\approx0.703, the classical quarter-bit advantage of the uniform source over the Gaussian at equal variance. For β≠2\beta\ne2 the Shannon ceiling is not exactly achievable at finite rate, but nearly so at K≥3K\ge3: bisecting Equation (1)’s upper end for the distortion it certifies achievable (with N(X+ZD)N(X+Z_D) by FFT convolution) places the true limit at K=4K=4 above 3.995 effective bits across β∈[1,2]\beta\in[1,2] (above 2.98 at K=3K=3) and above 3.95 for the uniform, whose discontinuous density slows the bound’s convergence. For β∈[1,2]\beta\in[1,2] the gaps in Table 14 are therefore genuine coding and table loss, not slack in the ceiling.

One multiplication at equal storage. Table 15 repeats the 64-byte LC comparison of Appendix § 13.§ 1 on these targets. For each target and rate the LC code is built as its paper prescribes: a generator and offset searched on the target (best of 600), the source quantiles at the labels times a scale factor chosen on held-out data, the Lloyd step on the trellis, and a mirror-symmetric E2M5 table at the best of four storage scales. CPTC keeps one coefficient pair per rate for every target. On the uniform target the one-multiply code is level or ahead at every rate; on the other three CPTC’s lead grows with tail weight at every rate from 2 to 5 and, except on the Laplacian at K=6K=6, with the rate. The β=2\beta=2 row is a run independent of Appendix § 13.§ 1 and agrees with it within 0.005 bits; CPTC’s values are those of the run behind Table 3.

INT8 tables. Table 16 repeats the sweep of Table 3 with INT8 tables, fitted like the E2M5 ones at a per-β\beta scale chosen on one held-out seed. INT8 matches E2M5 within 0.003 bits up to K=4K=4 on every target. At K=6K=6 it costs 0.03 bits on the uniform and the Gaussian and 0.13 on the Laplacian, where E2M5’s finer steps near zero help.

Table size and data type

This appendix supports the table-data-type knob of § 5.1 (Table 18) and proves the alphabet floor used there. The 8-bit table entries are themselves quantized codepoints, so the table data type sets a second floor on quality: rounding the table entries to the nearest representable value perturbs each by up to half an output unit in the last place. Table 17 sweeps table data types at L=16L=16 across KK under the identical encoder and protocol (T=256T=256, 2222^{22} samples, 3 seeds; seed std <10−3<10^{-3} bits): signed integers INT3–INT8, the mini-floats FP4 (E2M1, 15 values), FP6 (E2M3, 63 values) and E4M3 (253 values), the deployed type E2M5 (253 values), and the codepoints kept in BF16 or FP16 as references. Each type gets a single storage scale for all KK, chosen deterministically from the maximum entry of the K=4K=4 starting table of Equation (2): the largest 3-mantissa-bit float such that after rounding no codepoint of that table saturates. The generated table of each rate is then fitted to the type at that scale (Appendix § 11.§ 2). For E2M5 the rule gives a scale of 2: the outermost entry of the starting table sits at 3.74σ\sigma (the conditional mean of the triangle’s edge cell; its quantile midpoint in § 4.1 is 3.67σ\sigma), and 3.74 ×\times 2 stays inside the type’s span of 7.75, which the next scale would exceed. For INT6 it gives 8, and its table scores 3.926 at K=4K=4 against E2M5’s 3.934.

Table 17: Effective bits (↑\uparrow) by table data type at L=16L=16 (T=256T=256, 2222^{22} samples, 3 seeds). Each unit-variance codepoint vv is stored as round⁡(cv)\operatorname{round}(cv) in the type’s grid, with the fixed scale cc of the Scale column, and decoded as the stored value/cc. FP4 is E2M1 (15 values), FP6 is E2M3 (63); E4M3 and E2M5 have 253 values each (all-ones reserved for NaN). The last two columns use the type’s grid as a plain scalar quantizer, at the same scale and at the MSE-optimal scale with clipping; the 16-bit rows are native round-to-nearest.

Table typeScaleCPTC (L=16L=16), K=1K=1K=2K=2K=3K=3K=4K=4K=5K=5K=6K=6Scalar (type alone), at ccopt. cc
INT30.8750.951.601.601.601.601.601.602.21
INT420.961.942.772.792.792.792.793.14
FP41.750.951.942.843.123.123.123.123.15
INT540.951.952.943.763.793.793.794.04
INT680.951.952.943.934.754.784.794.93
FP620.951.952.943.924.805.125.125.12
E4M31200.951.952.943.934.815.195.225.24
INT7160.951.952.943.934.905.695.775.83
INT8320.951.952.943.934.915.776.736.73
E2M520.951.952.943.934.915.806.997.08
BF1610.951.952.943.934.925.869.239.23
FP1610.951.952.943.934.925.8712.2312.23

Table 17.

Three observations. First, the rule of thumb is b≈K+2b \approx K+2 integer bits: INT4 saturates beyond K=2K=2, INT5 beyond K=3K=3, INT6 beyond K=4K=4. Second, level placement sets the plateau height: with the same 15 levels FP4 plateaus at 3.12 against INT4’s 2.79, FP6 is ahead of INT6 by 0.05 at K=5K=5 and 0.34 at K=6K=6, and E2M5, whose 253 values keep all 127 codepoints distinct for K≥3K \ge3, stays within 0.07 bits of FP16 everywhere, while E4M3’s coarse mantissa caps it at 5.19 at K=6K=6. Third, wherever a type saturates, the CPTC rows flatten at the type’s own scalar quality (the “at cc column): the coder degenerates to the format it stores. The design guidance: E2M5 is the right default for the full K∈[1,6]K \in[1,6] range; a platform without it can default to INT8, which matches E2M5 up to K=5K=5 and costs 0.03 bits at K=6K=6 (other targets in Table 16); INT6 or FP6 are valid cost reductions for K≤4K \le4, where they give up at most 0.01 bits. (This table’s E2M5 row uses the deterministic no-clipping scale; Table 3 uses a per-β\beta calibrated scale for β≠2\beta\ne2, and its β=2\beta=2 row repeats Table 2.)

A minimal codebook. The sweep above holds the table-size parameter at Q=6Q=6 and varies only the storage type; the two knobs can be driven down together. Setting Q=K+1Q=K+1 gives a codebook of 2K+2−12^{K+2}-1 codepoints, and INT(K+2K+2) storage offers exactly 2K+2−12^{K+2}-1 symmetric levels, one per codepoint, so both the entry count and the entry width are at their matched minimum. Two bits further down on either knob is a provable floor, formalizing the table-sizing argument of § 3.3:

Proposition 4 (Alphabet floor). If the decoded-state codebook takes at most MM distinct values, then for every trellis depth LL, block size TT, and encoder, the per-sample MSE is at least that of the MM-point Lloyd–Max scalar quantizer.

The proof is two lines: every decoded value lies in the codebook, so each sample’s squared error is at least its squared distance to the nearest codepoint, and the MM-point Lloyd–Max codebook minimizes the expectation of exactly that quantity. At Q=K−1Q=K-1 the codebook has 2K−12^{K}-1 distinct codepoints, and a symmetric INT(KK) table has 2K−12^{K}-1 representable levels whatever QQ is, in either case one value short of the 2K2^{K} a rate-KK scalar quantizer uses, so by the proposition the decoder is strictly worse than the scalar optimum no matter how deep the trellis. Any trellis gain therefore requires Q≥KQ \ge K and strictly more than KK storage bits, and the matched configuration sits two doublings above each floor; Table 18 shows those two bits buy back essentially everything. By Proposition 2, every row with K≤5K \le5 runs bit-exactly on the fixed (Lmax⁡=16L_{\max}=16, Q=6Q=6) datapath via the shift s=5−Ks=5-K; the K=6K=6 row has Q=7Q=7 and needs the wider table of CPTCQ7_{Q7}.

Matmul-aware experiment: methods and per-ρ\rho results

This appendix gives the table design, baselines, scale calibration and per-ρ\rho numbers behind § 5.2.

Table design. The table contents encode the reproduction distribution, not the decode path. Ang et al. [6] show that for a multiplicative pair with operand correlation ρ\rho, the asymptotically optimal scalar quantizer has point density

λ⋆(u)∝exp⁡(−u2/6)⋅((1−ρ2)+ρ2u2)1/3,u=x/σ,(4)\lambda^\star(u) \propto\exp(-u^2/6) \cdot\left((1-\rho^2)+\rho^2u^2\right)^{1/3}, \qquad u=x/\sigma, \tag*{(4)}

exhibiting a unimodal-to-bimodal phase transition at ∣ρ∣=1/3|\rho|=1/\sqrt{3}. We move each entry of the generated Gaussian table T\mathcal{T} of § 3.3 to the same quantile of the normalized λ⋆\lambda^\star,

T⋆[i]=(F⋆)−1(Φ(T[i]/σT)),(5)\mathcal{T}^\star[i] = (F^\star)^{-1}\left(\Phi(\mathcal{T}[i]/\sigma_{\mathcal{T}})\right), \tag*{(5)}

where F⋆F^\star is the CDF of the normalized λ⋆\lambda^\star, Φ\Phi the standard normal CDF and σT\sigma_{\mathcal{T}} the standard deviation of the decoded values.

Methods. Scalar baselines INT4, FP4, and NF4 use max⁡∣c∣=1\max|c|=1 codebooks with a 20-point grid-searched per-matrix scale. MatMul-Opt ([6]) uses a 16-level scalar codebook at λ⋆\lambda^\star-quantile midpoints. CPTC-Gauss is CPTC with the Gaussian-target table; CPTC-MMaware uses λ⋆\lambda^\star at the data-generating ρ\rho (Equation (5)). For matmul-aware methods the codebook is in uu-space (variance ≈3\approx3 at ρ=0\rho=0, ≈4.6\approx4.6 at ρ=0.9\rho=0.9); the shared scale calibration is described below.

Per-ρ\rho results. Table 19 gives the numbers plotted in Figure 4. At ρ=0\rho=0, where λ⋆\lambda^\star degenerates to a Gaussian wider than the source, CPTC-MMaware ties CPTC-Gauss after shared-scale calibration; the matmul-aware codebook pays off from ρ=0.3\rho=0.3 onward, and CPTC-Gauss plateaus around 0.017–0.019 for ∣ρ∣≥0.5|\rho|\geq0.5.

Calibration objective. Per-entry MSE is the wrong calibration objective for the matmul-aware codebook, which deliberately spreads codepoints into the source tails; it selects too tight a scale. By the symmetry of the data-generating model the optimal scales satisfy cA⋆=cB⋆c_A^\star=c_B^\star, so we calibrate one shared scale per ρ\rho by minimizing matmul Frobenius error over five held-out matrix pairs on a 19-point grid over [0.4,1.3]⋅σ^[0.4,1.3]\cdot\hat{\sigma}.

Comparison with Ang et al. [6]. Ang et al. [6] present a similar plot (their Figure 2). Our MatMul-Opt curve reproduces their result at K=4K=4: it tracks NF4 at ρ=0\rho=0 and pulls ahead as ∣ρ∣|\rho| grows, with 1.86×1.86\times lower error than NF4 by ρ=0.9\rho=0.9; for CPTC-MMaware the trellis gain persists on top (1.5×1.5\times at ρ=0\rho=0, 1.2×1.2\times at ρ=0.9\rho=0.9).

LLM weight-only quantization details

Every LLM result in this section uses the YAQA Sketch-B pipeline of Tseng et al. [38] without fine-tuning: all quantized rows share its RHT preprocessing, two-sided Kronecker-factored Hessians, per-block scales, and the pipeline’s published loading factor (scale_override 0.9, from the authors’ released recipe), with only the trellis codebook swapped, so the comparison isolates the format from the rounding algorithm. The Llama

Table 20: KL to BF16 (↓\downarrow) on Wikitext-2 for each RHT seed behind the means of Table 4: seed 0 is the original run, seeds 1 and 2 change only the RHT sign vectors; range is (max − min)/mean. At every rate and scale both CPTC arms are below 1MAD on each seed; HYB was rerun at 8B only.

Instruct results

Instruct results use the authors’ released Hessians; the Qwen3.8-27B results at the end of this section use Hessians we collected ourselves, since none are published for that model. All of them use the authors’ evaluation protocol (GPTQ Wikitext-2 and C4 splits, sequence length 8,192). DKLD_{\mathrm{KL}} is the divergence to the unquantized model’s next-token distribution, the metric YAQA optimizes and the most sensitive of the three.

Harness and protocol validation. Our reproduction of the YAQA pipeline matches its authors’ published numbers wherever the same artifacts can be evaluated, at both scales. Our 8B BF16 baselines match theirs to displayed precision (6.502/8.022 vs. 6.50/8.02 at 8B), and running the QTIP quantizer ourselves under their recipe (seed 0 of the QTIP HYB rows of Table 4) reproduces the corresponding row of YAQA’s Table 1 to all displayed digits at K=4K=4 (0.0130, 6.608/8.118 vs. 0.013, 6.61/8.12), with K=3/2K=3/2 regenerations at 0.0452/0.2403 vs. their 0.044/0.241 and the 70B regenerations at 0.0298/0.0967/0.3281 vs. their 0.030/0.094/0.335 at K=4/3/2K=4/3/2. Two controls localize everything to the codebook: re-collecting the full 65,536-sequence Sketch-B Hessians from scratch reproduces our results to three decimals, and six independent draws of HYB’s kk-means table span 0.006 effective bits. The loading factor matters: at unit scale the QTIP quantizer degrades to 0.0172 at K=4K=4, so we adopt the authors’ released 0.9; it was tuned by them for HYB, and CPTC is nearly insensitive to it (0.00967 at unit loading vs. 0.00955 at 0.9, see 0, Table 21), so the shared setting does not favor CPTC. The factor was not varied for 1MAD. Every KL and perplexity cell of Table 4 but 70B HYB is the mean of three runs that differ only in the Random Hadamard Transform’s sign vectors: the pipeline is deterministic given the Hessians and this seed (re-collecting the Hessians moved results by under 0.001 KL), so we exposed the per-layer RHT seed and reran seeds 1 and 2 (seed 0 is the original run; Table 20). The spread across seeds is 0.3–4.1% of the value, comparable across codebooks, and both CPTC arms have a lower KL than 1MAD on every individual seed at every rate and scale (the closest call is CPTCQ5_{\mathrm{Q5}} at 70B K=3K=3, seed 1: 0.0871 vs. 0.0872), so the ordering of Table 4 does not rest on a seed. HYB has three seeds at 8B and one at 70B because its runs, on QTIP’s own encoder, take about six times longer.

ModelCodebookKKseed 0seed 1seed 2meanrange
8BQTIP HYB40.013010.012940.013240.013062.3%
8BQTIP 1MAD40.010190.009780.010040.010004.1%
8BCPTCQ5_{\mathrm{Q5}}40.009750.009580.009510.009612.5%
8BCPTC40.009550.009470.009500.009510.8%
8BQTIP HYB30.045200.045090.044860.045050.8%
8BQTIP 1MAD30.040470.040920.040100.040502.0%
8BCPTCQ5_{\mathrm{Q5}}30.039530.039960.039200.039561.9%
8BCPTC30.038220.039120.038630.038662.3%
8BQTIP HYB20.240260.244870.242090.242411.9%
8BQTIP 1MAD20.232040.225680.223480.227073.8%
8BCPTCQ5_{\mathrm{Q5}}20.220730.220440.222520.221230.9%
8BCPTC20.218200.220430.221910.220181.7%
70BQTIP 1MAD40.023520.024040.023870.023812.2%
70BCPTCQ5_{\mathrm{Q5}}40.022640.022550.022240.022481.8%
70BCPTC40.022650.022720.022650.022670.3%
70BQTIP 1MAD30.088180.087190.087440.087601.1%
70BCPTCQ5_{\mathrm{Q5}}30.084490.087060.085180.085583.0%
70BCPTC30.083810.084960.084810.084531.4%
70BQTIP 1MAD20.324680.321010.320530.322071.3%
70BCPTCQ5_{\mathrm{Q5}}20.312410.313740.317270.314471.5%
70BCPTC20.319360.318840.314530.317581.5%

Table 20.

RoundingCPTCHYBCPTC advantage
RTN0.033630.05334−37%
YAQA-B0.009670.01720−44%
YAQA gain3.5×3.1×…

Table 21.

A full 8B quantization run takes about six minutes on one 8-GPU node (fused Viterbi encoder; a banded reformulation of the rounding solver with identical results), which is what makes recipe-uniform grids and these controls affordable. We did not run LC or RPTC in the LLM pipeline; Table 2 remains the locus of that comparison.

Results (Table 4). Beyond the margins of § 5.3: against the published HYB numbers CPTC’s DKLD_{\mathrm{KL}} margin at 8B is 8.6/12.1/26.9% at K=2/3/4K=2/3/4, and against 1MAD it is 3/5/5% at 8B and 1/4/5% at 70B (full-table arm; 3/2/4% and 2/2/6% for CPTCQ5_{\mathrm{Q5}}). At K=5K=5 (single runs, seed 0) quantization is nearly free and the ordering holds: at 8B CPTC 0.0031 (perplexity 6.516 vs. 6.502), CPTCQ5_{\mathrm{Q5}} 0.0032, 1MAD 0.0032 and HYB 0.0075, whose table saturates at 3.94 effective bits at 5 bits (Theorem 1); at 70B CPTC 0.0068, CPTCQ5_{\mathrm{Q5}} 0.0069 and 1MAD 0.0070. The Q=5Q=5 arm, whose 63 FP16 codepoints make the GPU kernel’s table gather bank-conflict-free (Appendix § 14.§ 1), costs at most 0.001 DKLD_{\mathrm{KL}} at 8B (0.0001 at K=4K=4), costs 0.001 at 70B K=3K=3, and beats the full table at 70B K∈{2,4}K \in\{2,4\} (0.3145 vs. 0.3176, 0.0225 vs. 0.0227). Zero-shot accuracy over ARC-{c,e}, BoolQ, HellaSwag, PIQA sits within 1.1 points of BF16 (71.38 at 8B, 77.09 at 70B) for every codebook at K≥3K \ge3 and drops together at K=2K=2 (4.0–4.7 points at 8B, 2.4–2.8 at 70B), so it separates rates but not formats and we do not rank by it. Absolute zero-shot numbers do not transfer across harness versions (our harness scores the identical BF16 model 1.56 points higher on average than their published row), so every zero-shot number we report is self-measured.

Codebook or rounding? (Table 21). Replacing YAQA’s adaptive rounding with round-to-nearest (RTN; both codebooks at unit loading) isolates the two effects. CPTC’s advantage survives without adaptive rounding (37% lower DKLD_{\mathrm{KL}} than HYB under RTN, 44% under YAQA at the same loading), so it is a property of the codebook, not an interaction with the rounding algorithm; conversely YAQA rounding is worth 3.1–3.5× for either codebook.

Table 21: The codebook effect with and without adaptive rounding: KL to BF16 (↓) at K=4K=4 on 8B, same pipeline at unit loading, single runs, with YAQA’s adaptive rounding and with plain round-to-nearest. The codebook advantage survives removing adaptive rounding. Unit loading is HYB’s unfavorable setting (0.0130 at its released 0.9, seed 0).

KL tracks effective bits (Figure 1b). I.i.d. effective bits under the protocol of Table 2 predict the quantized model’s quality. For CPTC, QTIP 1MAD and QTIP HYB at K∈{2,3,4}K \in\{2,3,4\}, nine cells per model (the CPTCQ5_{\mathrm{Q5}} arm lies within 0.007 KL of CPTC on seed 0 and is omitted for legibility), a quadratic least-squares fit of log⁡2DKL\log_2 D_{\mathrm{KL}} against KeffK_{\mathrm{eff}} has r2=0.999r^2=0.999 at 8B and 0.997 at 70B. Because the codebook points cluster near the three rates, each point is weighted by the inverse count of its 0.1-bit KeffK_{\mathrm{eff}} bin, so the fit is uniform over the covered range rather than a curve through three clusters, and the 8B fit also includes the depth-sweep points below, 44 distinct cells in all. A slope of −2 is what a KL proportional to weight MSE predicts, since one effective bit is a 4× factor in distortion (Equation (1)); across rates 70B follows it (fitted slope −2.0 at 2 bits to −1.9 at 4), while at 8B the slope runs from −3.0 at 2 bits through −2.3 at 3 to −1.7 at 4: the KL gain per effective bit shrinks with rate. Within a single rate the three codebooks give slopes of −1.1/−2.0/−1.3 at 70B and −3.8/−2.4/−1.4 at 8B for K=2/3/4K=2/3/4, from three points each. Rank order among them is exact at both scales: in every same-rate pair the codebook with more effective bits has the lower KL (9/9 pairs each). The relation does not order the two CPTC arms: CPTCQ5_{\mathrm{Q5}} has the lower KL at 70B for K∈{2,4}K \in\{2,4\} (Table 4). Nor do the LLM data resolve gaps whose KL effect is within the seed range (0.3–4.1%): the LC margins of Table 2 for K∈[2,4]K \in[2,4] and INT6’s cost (at most 0.01 bits) move KL by about 1%. KeffK_{\mathrm{eff}} values are the L=16L=16 Gaussian measurements; KL values are the seed-0 runs of Table 4.

Trellis-depth sweep. Varying LL at fixed KK moves a single codebook along the same law. We quantized Llama 3.1 8B with CPTC at every LL from KK to 16 for K∈{2,3,4}K \in\{2,3,4\} (per-(L,K)(L,K) coefficients, RHT seed 0, same recipe), and measured each configuration’s i.i.d. effective bits under the protocol of Table 2. Within each rate, KL falls with depth up to seed noise: at K=4K=4 it falls from 0.047 (L=4L=4, 2.80 effective bits) to 0.00955 (L=16L=16, 3.93); at K=3K=3 from 0.169 (L=3L=3, 2.16) to 0.038; at K=2K=2 from 0.78 (L=2L=2, 1.48) to 0.218. The L=KL=K cells use the conditional-mean fill of Equation (2) rather than a Lloyd–Max table, which is why K=4K=4, L=4L=4 sits below INT4; the exact scalar reproduction of § 3.4 needs the scalar codebook loaded. Figure 1b plots the 38 cells with Keff≥1.75K_{\mathrm{eff}} \ge1.75 (all but L≤5L \le5 at K=2K=2): log⁡2DKL\log_{2} D_{\mathrm{KL}} against KeffK_{\mathrm{eff}} has Spearman ρ=−0.999\rho= -0.999 and a uniformly weighted slope of −2.4-2.4 (r2=0.99r^{2}=0.99); per rate the slope over LL is −2.0-2.0 at K=4K=4, −2.7-2.7 at K=3K=3 and −3.9-3.9 at K=2K=2, the steepening described above. The depth points land on the codebook comparison of the previous paragraph without any change of fit, which is the transfer claim in its strongest form: what Table 2 measures on Gaussian samples is what the model sees.

A preliminary result on a different architecture: Qwen3.8-27B (Table 22). Everything above is dense-attention Llama. Qwen3.8-27B interleaves 48 gated-DeltaNet linear-attention layers with 16 gated-attention layers in a 3:1 pattern and carries a vision tower, so it tests whether the codebook advantage is architecture-specific. No Sketch-B Hessians are published for it, so we collected the full 65,536-sequence set ourselves (about 6.5 days on one 8-GPU node, text only with the vision tower detached). We quantize 400 linears (six per DeltaNet layer, seven per attention layer); the small decay-gate projections, the short convolutions and all norms stay in BF16, and the 17,408-wide MLP dimension, which admits no power-of-two Hadamard, uses an order-68 Paley construction. This is a single run on our own Hessians, and we report it as preliminary. CPTC lowers DKLD_{\mathrm{KL}} at every rate (0.0563/0.1060/0.2630 vs. 0.0719/0.1175/0.3063 at K=4/3/2K=4/3/2) and C4 perplexity at K=3K=3 and K=2K=2, tying at K=4K=4 (6.8171 vs. 6.8165); at K=5K=5 (CPTC only; HYB’s 512-pair table caps at 3.94 effective bits there, Table 2) C4 perplexity is within 0.005 of BF16 and DKLD_{\mathrm{KL}} halves again to 0.0295. As on Llama, zero-shot accuracy does not separate the formats: every quantized model sits within a point of BF16 (74.1), and even K=2K=2 costs only 0.7–1.0 points for both codebooks.

Why we do not rank this model by Wikitext-2 perplexity. On this split every quantized model scores below BF16, contradicting DKLD_{\mathrm{KL}} and C4. Raw Wikipedia text is far from this model’s post-training data, and the BF16 model is overconfident on it: softening its logits by a temperature τ\tau takes its Wikitext-2 perplexity from 7.685 at τ=1\tau=1 to a minimum of 7.440 at τ=1.15\tau=1.15, which reproduces CPTC’s K=4K=4 score of 7.447 with no quantization, while the best temperature for C4 (τ=1.05\tau=1.05) lowers its perplexity by only 0.016. Four of the quantized scores are lower still, so temperature does not account for all of the effect. The same harness shows no inversion on Llama (Table 4), so we report the column for completeness and rank by DKLD_{\mathrm{KL}}, which is also the argument of Tseng et al. [38] for the metric.

Table 22: Qwen3.8-27B (hybrid gated-DeltaNet/attention) in YAQA’s pipeline with our own 65,536-sequence Hessians, no fine-tuning, single run: KL and perplexity (↓), Acc (↑, mean 0-shot accuracy as in Table 4). CPTC has the lower KL at every rate and the lower or equal C4 perplexity. †Wikitext-2 perplexity is not informative on this model (softening the BF16 model’s logits by a temperature alone lowers it to CPTC’s K=4K=4 score, see text), so that column is unbolded. W2: Wikitext-2.

Systems details

Fused decode + tensor-core GEMM on stock GPUs

This appendix details the decode-side kernel of § 6.2. It is a separate claim from the accelerator result of § 6.1: that one is a post-layout datapath; this one is what a GPU with no CPTC support can do today with general-purpose integer instructions. The two share only the decode primitive of Algorithm 1.

Structure. The kernel targets weights times low-batch activations (≤8\le8 columns), the regime weight-only quantization is for. Each warp decodes a 16×6416 \times64 tile of the weight matrix (16 output rows by 64 positions along the contraction); each lane reads a 128-bit window of the code stream and decodes 32 values, and the decoded values land directly in the mma.sync.m16n8k16 operand registers. This costs nothing at run time because the map from stream position to fragment slot is a fixed permutation, applied to the weights once, before quantization, so no lane shuffles or shared-memory transposes are needed to reach tensor-core layout. Only one word per lane crosses a lane boundary (the window straddling the next lane’s data), supplied by a single shfl. The Q=5Q=5 table’s 63 FP16 entries occupy 32 four-byte words, one per shared-memory bank, so the per-lane table gather is conflict-free without replication. Accumulation is FP32 throughout, including the cross-warp reduction and any CTA-level split-KK atomics; only the final store narrows.

The INT4 baseline. Speedup over cuBLAS FP16 conflates two effects: moving 4×4\times fewer weight bytes, and paying to decode them. To separate these we run an INT4 baseline that is the same kernel with the same layout, staging, MMA and epilogue, whose decode is a shift and a mask instead of Algorithm 1. It is verified to be the L=4L=4 CPTC decoder with an identity table, so it is bit-exact-comparable, and it is an upper bound on any 4-bit weight-only kernel using this data path. The gap between CPTC and this baseline is the cost of the trellis and nothing else.

Results (Table 23). The rows are two decode schemes over one GEMM pipeline. Two multiplies is the full L=16L=16 decoder of Algorithm 1 with the Q=5Q=5 table. State table indexes a 2L2^L-entry table by the L=10L=10 state itself; it is the small-LL design point of § 6.3 (3.84 effective bits at K=4K=4), not the L=16L=16 quantizer of Table 2. Table 23 isolates decode cost per weight, the only thing the schemes differ in. Decode time does not depend on the table contents. Two GPUs give opposite answers. On the L40S the two-multiply form and the baseline both sit at 0.99–1.00× a measured pure-streaming ceiling at the saturated size: the memory system binds and the decode hides inside it, the two-multiply form at 0.995× the baseline’s speed (0.98× across the Llama shapes). On the H100, with about 4× the bandwidth, the decode ALU becomes the limiter and the same form falls to 0.48× at the saturated size (0.62× across the Llama shapes); the state-table scheme, which spends Hopper’s larger shared memory instead of arithmetic (a 4 KiB state table of 2102^{10} 32-bit words, replicated 32-fold into 128 KiB so the warp-wide gather is bank-conflict-free), reduces decode to a shift, a mask-or and one load and reaches 0.73× (0.79× across the Llama shapes). That table exceeds Ada’s 99 KiB per-CTA cap, hence no L40S state-table row in Table 23. All measurements are cold-L2 (the code stream is rotated over enough copies to exceed L2), CUDA-event timed, autotuned over CTA width, warps per tile, split-K and pipeline depth, and checked against an FP32 reference matmul on the decoded weights (maximum absolute error about 10−510^{-5}).

GPUDecodestack (ms)vs. cuBLASsaturated (μ\mus)×\times ceil
L40S (Ada)cuBLAS FP1619.08—2,5950.959
two multiplies5.243.64×\times6260.993
INT4 baseline5.123.73×\times6230.998
QTIP HYB kernel†^{\dagger}5.83.3×\times——
two multiplies, unfused‡^{\ddagger}5.35 / 5.843.57×\times——
H100 (Hopper)cuBLAS FP165.51—6571.011
two multiplies3.401.62×\times3300.504
state table2.672.06×\times2190.759
INT4 baseline2.112.61×\times1591.048
QTIP HYB kernel†^{\dagger}3.21.7×\times——
two multiplies, unfused‡^{\ddagger}3.54 / 4.311.56×\times——
state table, unfused‡^{\ddagger}2.85 / 3.651.93×\times——

Table 23. Decode fused into the tensor-core GEMM at batch 1 (K=4K=4, T=256T=256, the Q=5Q=5 table except in the state-table rows; FP16 in/out, FP32 accumulation). “stack” (↓): time per token for the 32-layer Llama 3.1 8B linear stack; “vs. cuBLAS” (↑): its speedup over cuBLAS FP16; “saturated” (↓): a 229,376×\times4,096 matrix large enough that cuBLAS itself is bandwidth-bound; “×\times ceil” (↑): throughput relative to the measured pure-streaming read ceiling at that size (above 1 is possible because a GEMM’s small activation operand comes from L2). The INT4 baseline shares the whole pipeline without any trellis decode, so its gap to the CPTC rows is the decode cost. The state-table scheme needs 128 KiB of shared memory per CTA and does not run on Ada. †^{\dagger}QTIP’s released HYB kernel at K=4K=4 on the seven unfused per-projection shapes, timed as its own harness does, kernel time only. ‡^{\ddagger}CPTC on those same shapes, kernel-only / with the output-zeroing launch; speedup from the kernel-only time. Speedups of the †^{\dagger} and ‡^{\ddagger} rows are against the fused-stack cuBLAS time.

What binds each scheme. Profiling attributes the two regimes to different pipes. The arithmetic schemes are ALU-issue-bound on Hopper (78–83% of peak ALU; variants spanning 4.5–5.5 ALU operations per value all measured within a factor of 1.005 of each other), and the state-table scheme saturates the shared-memory path at 85.5% of peak LITEX with one load per decoded value; an oracle that halves its lookups for free bounds the available speedup at 1.26×. Neither limit can be removed without changing the decode method (fewer lookups per value for the state table, less ALU work for the arithmetic schemes), which is the concrete sense in which § 6.1’s decode unit is the remaining lever on bandwidth-rich parts.

Against QTIP’s released kernels. QTIP ships CUDA decode kernels for its HYB codebook at K∈{2,3,4}K \in\{2,3,4\}, fixed to Llama’s per-projection shapes at batch 1. We built them unmodified, timed them the way their own test harness does (inside a CUDA graph with per-launch events, cold-L2), and ran our kernel on the same seven shapes. At K=4K=4 their kernel takes 5.8 ms per token for the 32-layer Llama 3.1 8B stack on the L40S and 3.2 ms on the H100; our two-multiply form takes 5.35 and 3.54 ms kernel-only (5.84 and 4.31 ms including the output-zeroing launch its split-KK atomics currently require), and the Hopper state-table scheme 2.85 ms (3.65 ms with that launch). The fused-stack rows of Table 23 run fewer, larger shapes, hence their 5.24 and 3.40 ms. On the bandwidth-bound L40S both are near the memory wall (HYB 5.8 ms against CPTC’s 5.35 ms kernel-only); on the H100, kernel-only, the portable form runs at 0.90×\times HYB’s speed and the state table at 1.12×\times (0.74×\times and 0.88×\times with the zeroing launch). HYB’s is the cheaper GPU decode: one 32-bit shared load per two values with no arithmetic, which is possible only because its output alphabet is a 512-pair table (1,024 pairs with the sign flip), the restriction behind its quality gap in Table 2 and Table 4. CPTC keeps the full alphabet and pays with the multiplier, which the accelerator of § 6.1 provides natively.

CPU decode kernels

The decode primitive also vectorizes on general-purpose CPUs. We implemented it in C++17 for AVX-512 (with the VBMI byte permutes), for AVX2 and for AArch64 NEON, with a portable scalar fallback, and verified every path bit-exact against the reference decoder for K∈[1,6]K \in[1,6], for the E2M5 and the INT8 table types and for both table configurations (Q=6Q=6 with the mirror fold, and the Q=5Q=5, 63-entry table stored in full), on x86 (Zen 3, Zen 4) and on Arm (Graviton5, with Arm Neoverse V3 cores). The AVX-512 kernel decodes 64 values per step in about 15 instructions (a byte permute and a multishift to cut out the 16-bit windows, two 16-bit lane multiplies and shifts per 32 windows, and one table permute); the Q=5Q=5 form needs no compare, subtract or sign flip for the fold, and the table permute costs the same for the 31-, 63- and folded 127-codepoint tables, so a smaller table would not speed the CPU up. Table 24 gives single-core throughput; the kernel is issue-bound (removing one multiply in a timing-only experiment gains only 1.15×\times). The NEON kernel spends 16 instructions per 16 values on 128-bit vectors; on the Neoverse V3 its multiplies, dot product and table lookup share two of the four vector pipes, which caps it at about 8.7 billion values/s per core in the GEMM path (7.6 measured at K=3K=3; the standalone rates of Table 24 also pay a natural-order permute and a store per value) and puts K=2K=2 and K=3K=3 out of reach of the memory roof on that machine.

KernelCPUFP16 out Q=6Q=6 foldFP16 out Q=5Q=5INT8 out Q=6Q=6 foldINT8 out Q=5Q=5
AVX-512Zen 415.024.420.125.3
AVX2Zen 42.83.14.14.7
AVX2Zen 32.42.73.74.1
NEONGraviton53.95.05.16.8
INT4 unpack (FP16 out), AVX-512 / AVX2Zen 447 / 29
INT4 unpack (FP16 out), NEONGraviton523

Table 24. Single-core decode throughput on CPUs (↑\uparrow, billions of values per second) from an L2-resident stream of 2172^{17} values at K=4K=4, T=256T=256, best of 100–200 runs (other KK at 0.97–1.04×\times these rates on x86 and 0.87–1.00×\times on NEON; the AVX-512 row writes its output in the GEMM’s tile order). FP16 output uses the E2M5 table, INT8 output an INT8 table. Zen 4: AMD EPYC 9R14 (AVX-512); Zen 3: AMD EPYC 7R13 (AVX2); Graviton5: AWS Graviton5, Arm Neoverse V3 cores (NEON). The last rows unpack INT4 nibbles through a 16-entry table, the cheapest 4-bit decode.

End to end. Table 25 times the weight stream of a Llama 3.1 8B forward pass (the seven linear layers of each of 8 transformer layers, scaled to the model’s 32; weights streamed from DRAM, activations resident) on the 64-core Zen 4 server in one parallel region, against FP16 weights, INT8 weights with VNNI dot products, and the INT4 nibble unpack feeding the same VNNI path. CPTC decodes to INT8 codes and uses the same VNNI dot product (Q=5Q=5 table in INT8). The machine sustains about 270 GB/s, which FP16, INT8 and INT4 all reach: they are bandwidth-bound. The comparison of interest is at equal bits: CPTC at K=4K=4 reaches the same bandwidth as INT4 and takes the same time at batch 1, so the trellis decode is hidden under the memory stream. At K=3K=3 and K=2K=2 the stream is 0.75×\times and 0.50×\times as long and the time falls to 0.83×\times and 0.60×\times the K=4K=4 time, against 0.75×\times and 0.50×\times for a purely bandwidth-bound format: the decode is partly exposed at K=3K=3 (233 of the 270 GB/s roof) and more so at K=2K=2 (217 GB/s). The INT4 baseline is a pure nibble lookup without scale handling, the strongest form of it; run-to-run spread is about 5%. The lower block repeats the measurement on one 96-core NUMA node of a Graviton5 (Neoverse V3, NEON with SDOT dot products), whose node roof is about 405 GB/s. At K=4K=4 the picture is the same: CPTC reaches 0.97×\times the INT4 bandwidth and takes the same time at batch 1 (8.9 vs. 8.6 ms). At K=3K=3 and K=2K=2 the 128-bit NEON decoder, capped at about 8.7 billion values/s per core, cannot feed the shorter streams at the roof (11.3 and 16.9 billion values/s per core would be needed), so those rates are decode-bound at 275 and 208 GB/s: K=2K=2 finishes in the INT4 time and K=3K=3 runs at 0.91×\times its speed, rather than faster. With the mirror-folded Q=6Q=6 table, the accelerator’s format, the K=4K=4 stack takes 14.1 ms on Zen 4 and 11.1 ms on Graviton5, 0.94×\times and 0.78×\times the INT4 speed.

WeightsbitsmsGB/s
Zen 4, 64 cores (AVX-512, VNNI)
FP161651.9269
INT8, VNNI825.8271
INT4 unpack, VNNI413.3262
CPTC K=6K=6619.9263
CPTC K=4K=4413.6257
CPTC K=3K=3311.3233
CPTC K=2K=228.1217
Graviton5, one 96-core node (NEON, SDOT)
FP161636.0388
INT8, SDOT817.5399
INT4 unpack, SDOT48.6405
CPTC K=6K=6613.8379
CPTC K=4K=448.9391
CPTC K=3K=339.5275
CPTC K=2K=228.4208

Table 25. Time to stream the weights of a 32-layer Llama 3.1 8B forward pass (ms, ↓\downarrow) at batch 1 and the bandwidth reached, on a 64-core Zen 4 server (top) and one 96-core Graviton5 NUMA node (bottom). CPTC decodes an INT8 table (Q=5Q=5) into the INT8 dot product (VNNI on x86, SDOT on Arm); INT4 unpacks nibbles into the same dot product. Best of 7 passes over 8 transformer layers, scaled to 32.

Viterbi encoder: reference implementation and fused kernels

Listing 1 is the single-iteration Viterbi update in PyTorch notation; the full TT-step encoder applies this sequentially over the block’s values, and tail-biting wraps that in an outer pass that fixes the starting state. The rest of this subsection describes the fused GPU kernel that accelerates this reference by 33–134×\times (Table 26) and its Trainium 4 counterpart. The decoder-side counterpart, a per-value golden reference decoder, is the oracle against which the dominance rule of Proposition 2 and the hardware kernels are validated bit-exactly.

L\KL\backslash K123456
102,960 (114×)3,539 (60×)3,381 (35×)3,253 (33×)3,526 (37×)3,666 (37×)
111,642 (127×)1,864 (62×)2,002 (46×)1,935 (43×)1,985 (44×)2,080 (46×)
12864 (133×)992 (66×)1,020 (45×)1,100 (49×)1,149 (50×)1,098 (47×)
13436 (134×)505 (67×)528 (45×)562 (49×)579 (48×)570 (48×)
14218 (134×)244 (65×)255 (44×)276 (48×)277 (47×)263 (44×)
1584 (103×)105 (56×)116 (38×)127 (44×)133 (45×)131 (43×)
1632 (79×)48 (51×)53 (35×)60 (41×)63 (43×)61 (41×)

Table 26. Fused Viterbi encoder throughput (↑, millions of values per second) on one L40S at every trellis depth and bit width (T=128T=128, 2222^{22} values, median of 5; reference: median of 3), with the speedup over the torch.compile reference of Listing 1 in parentheses. Work grows as 2L2^L; the KK dependence comes from backpointer traffic and occupancy.

Listing 1: Viterbi iteration for CPTC encoding.

# a:                         running cost per (L-K)-bit prefix, shape (2**(L-K),)
# decoded_states: codebook, shape (2**L,); W_t: next value; K: bits/value
# The reference walks the block in reverse, so each new code lands in the
# low K bits of its window in the packed stream of Alg. 2.
def viterbi_iteration(a, decoded_states, W_t, K):
    # squared error of every full state s = (prefix << K) / u
    current_cost = (decoded_states - W_t).square()
    # state s extends prefix s >> K, whose running cost a holds
total = a.unsqueeze(-1).expand(-1, 2**K).reshape(-1) + current_cost
# next prefix = low L-K bits of s; minimize over the high K bits;
# a_new and b_t have shape (2**(L-K),)
a_new, b_t = total.reshape(2**K, -1).min(dim=0)
return a_new, b_t

What the kernel computes. For each block the encoder solves the tail-biting minimum-distortion path problem of § 3.2: over all state sequences that follow the bitshift transition and close into a cycle, it minimizes ∑t(wt−ϕ(qt))2\sum_t(w_t-\phi(q_t))^2 with ϕ\phi the decode map of Algorithm 1, and emits the per-value codes ctc_t. Launched as framework-level tensor operations (Listing 1 under torch.compile) the recursion is latency-bound: each of the TT trellis steps and TT backtrace steps is a separate kernel launch. We fuse the whole pipeline (forward pass, arg min, half backtrace to the tail-biting midpoint state, second forward pass, full backtrace) into one persistent Triton launch that keeps the running costs in registers across all TT steps. Four optimizations matter: the per-step minimum packs the FP16 path cost and the predecessor index into one 32-bit word, so one unsigned minimum returns both; for K≤4K \le4 the KK-bit predecessor indices pack ⌊8/K⌋\lfloor8/K\rfloor per byte; the first T/2T/2 steps of the first forward pass skip the backpointer store, which the half backtrace never reads; and at small 2L−K2^{L-K} the kernel packs several independent blocks per program.

Table 26 reports the full (L,K)(L,K) throughput matrix on an NVIDIA L40S at T=128T=128: 33–134×\times faster than the torch.compile reference at matching MSE. The kernel accumulates path costs in FP16 where the reference uses FP32, which flips 2–4% of codes on near-tie paths (measured at K=4K=4 and at L=16L=16) and moves the MSE by at most 0.02% (L∈[10,16]L \in[10,16], K∈[1,6]K \in[1,6], both encoding the same FP16 input). At the main design point (L=16L=16, K=4K=4) it sustains ∼\sim60 million values/s, putting 7.0 billion values, the size of Llama 3.1 8B’s linear layers, under two GPU-minutes; smaller trellises encode proportionally faster (1.1 billion values/s at L=12L=12). The kernel is compute-limited: an Nsight Compute profile at L=10L=10, K=4K=4 shows 73% SM throughput against under 1% DRAM utilization, with the integer ALU pipe the busiest at 70%.

Against QTIP’s shipped encoder. QTIP’s released repository encodes with a batched PyTorch Viterbi (bitshift_codebook.quantize, commit e90c668), the same framework-level form as our reference. We timed it unmodified on the same L40S at its shipped settings (L=16L=16, T=256T=256, i.e. its 16 ×\times 16 tiles), 2222^{22} standard-normal values, median of 5 runs: 0.76 million values/s for 1MAD, 0.77 for 3INST and 1.5 for HYB, whose V=2V=2 pairs halve the trellis steps. Our fused encoder at T=256T=256 runs 59 million values/s at L=16L=16, 1,819 at L=11L=11 and 3,110 at L=10L=10. By Table 11, CPTC at L=11L=11 scores 3.865 effective bits against 1MAD’s 3.864 at L=16L=16 (CPTC L=16L=16: 3.934). Encoding at equal quality is therefore about 2,400× faster than QTIP’s shipped encoder: 32× less work from running L=11L=11 instead of L=16L=16, which is method-level, and the remaining 75× from the fused kernel (78× when both encoders run at L=16L=16), which a fused Viterbi for QTIP’s codebooks would recover.

On Trainium 4. Table 27 is the counterpart of Table 26 for the Trainium 4 encoder of § 6.3: the per-chip throughput of the best launch at every (L,K)(L,K) in a cycle-level simulation of the pre-silicon design. These simulated per-chip rates (T=256T=256) are a reference point, not a comparison with the measured per-GPU rates of Table 26 (T=128T=128).

References

  1. [1]Eduardo Alvarez, Omri Almog, Eric Chung, Simon Layton, Dusan Stosic, Ronny Krashinsky, and Kyle Aubrey. Introducing NVPF4 for efficient and accurate low-precision inference. https://developer.nvidia.com/blog/introducing-nvpf4-for-efficient-and-accurate-low-precision-inference/, June 2025. NVIDIA Technical Blog.
  2. [2]Amazon Web Services. NeuronCore-v4 architecture. AWS Neuron documentation, https://awsdocs-neuron.readthedocs-hosted.com/en/latest/about-neuron/arch/neuron-hardware/neuron-core-v4.html, 2025a. Trainium 3.
  3. [3]Amazon Web Services. Trainium3 UltraServers now available: Enabling customers to train and deploy AI models faster at lower cost. https://www.aboutamazon.com/news/aws/trainium-3-ultraserver-faster-ai-training-lower-cost, December 2025b. Announcement of Trainium 4.
  4. [4]Amazon Web Services. Trainium/Inferentia2 architecture guide for NKI. AWS Neuron documentation, https://awsdocs-neuron.readthedocs-hosted.com/en/latest/nki/guides/architecture/trainium_inferentia2_arch.html, 2026.
  5. [5]John B. Anderson and Tomas Eriksson. Trellis source codes based on linear congruential recursions. IEEE Communications Letters, 9(3):198–200, 2005.DOI
  6. [6]Calvin Ang, Sungyoon Kim, and Mert Pilanci. Optimal scalar quantization for matrix multiplication: Closed-form density and phase transition. arXiv preprint arXiv:2603.19559, 2026.arxiv.org/abs/2603.19559
  7. [7]Ron Banner, Yury Nahshan, and Daniel Soudry. Post training 4-bit quantization of convolutional networks for rapid-deployment. In Advances in Neural Information Processing Systems (NeurIPS), 2019. arXiv:1810.05723.arxiv.org/abs/1810.05723
  8. [8]W. R. Bennett. Spectra of quantized signals. Bell System Technical Journal, 27(3):446–472, 1948. doi: 10.1002/j.1538-7305.1948.tb01340.x.DOI
  9. [9]Toby Berger. Rate Distortion Theory: A Mathematical Basis for Data Compression. Prentice-Hall, 1971.
  10. [10]Richard E. Blahut. Computation of channel capacity and rate-distortion functions. IEEE Transactions on Information Theory, 18(4):460–473, 1972.DOI
  11. [11]Jerry Chee, Yaohui Cai, Volodymyr Kuleshov, and Christopher De Sa. QuIP: 2-bit quantization of large language models with guarantees. In Advances in Neural Information Processing Systems (NeurIPS), 2023.arxiv.org/abs/2307.13304
  12. [12]John H. Conway and Neil J. A. Sloane. Sphere Packings, Lattices and Groups. Springer, third edition, 1999.
  13. [13]Tim Dettmers, Artidoro Pagnoni, Ari Holtzman, and Luke Zettlemoyer. QLoRA: Efficient finetuning of quantized LLMs. In Advances in Neural Information Processing Systems (NeurIPS), 2023.arxiv.org/abs/2305.14314
  14. [15]Tomas Eriksson, John B. Anderson, and Norbert Goertz. Linear congruential trellis source codes: Design and analysis. IEEE Transactions on Communications, 55(9):1693–1701, 2007.DOI
  15. [16]Weiler A. Finamore and William A. Pearlman. Optimal encoding of discrete-time continuous-amplitude memoryless sources with finite output alphabets. IEEE Transactions on Information Theory, 26(2):144–155, 1980.DOI
  16. [17]Elias Frantar, Saleh Ashkboos, Torsten Hoefler, and Dan Alistarh. GPTQ: Accurate post-training quantization for generative pre-trained transformers. In International Conference on Learning Representations (ICLR), 2023.arxiv.org/abs/2210.17323
  17. [18]Allen Gersho. Asymptotically optimal block quantization. IEEE Transactions on Information Theory, 25 (4):373–380, 1979.DOI
  18. [19]Robert M. Gray. Time-invariant trellis encoding of ergodic discrete-time sources with a fidelity criterion. IEEE Transactions on Information Theory, 23(1):71–83, 1977.
  19. [20]Sehoon Kim, Coleman Hooper, Amir Gholami, Zhen Dong, Xiuyu Li, Sheng Shen, Michael W. Mahoney, and Kurt Keutzer. SqueezeLLM: Dense-and-sparse quantization. In International Conference on Machine Learning (ICML), 2024. arXiv:2306.07629.arxiv.org/abs/2306.07629
  20. [21]Ji Lin, Jiaming Tang, Haotian Tang, Shang Yang, Wei-Ming Chen, Wei-Chen Wang, Guangxuan Xiao, Xingyu Dang, Chuang Gan, and Song Han. AWQ: Activation-aware weight quantization for on-device LLM compression and acceleration. In Proceedings of Machine Learning and Systems (MLSys), 2024.DOI
  21. [22]Yifei Liu, Jicheng Wen, Yang Wang, Shengyu Ye, Li Lyna Zhang, Ting Cao, Cheng Li, and Mao Yang. VPTQ: Extreme low-bit vector post-training quantization for large language models. In Conference on Empirical Methods in Natural Language Processing (EMNLP), 2024. arXiv:2409.17066.arxiv.org/abs/2409.17066
  22. [23]Stuart P. Lloyd. Least squares quantization in PCM. IEEE Transactions on Information Theory, 28(2):129–137, 1982. Written at Bell Laboratories in 1957.DOI
  23. [24]Howard H. Ma and Jack K. Wolf. On tail biting convolutional codes. IEEE Transactions on Communications, 34(2):104–111, 1986. doi: 10.1109/TCOM.1986.1096498.DOI
  24. [25]Mark Z. Mao, Robert M. Gray, and Tamás Linder. Rate-constrained simulation and source coding i.i.d. sources. IEEE Transactions on Information Theory, 57(7):4516–4529, 2011. doi: 10.1109/TIT.2011.2145930.DOI
  25. [26]Michael W. Marcellin and Thomas R. Fischer. Trellis coded quantization of memoryless and Gauss–Markov sources. IEEE Transactions on Communications, 38(1):82–93, 1990.DOI
  26. [27]Joel Max. Quantizing for minimum distortion. IRE Transactions on Information Theory, 6(1):7–12, 1960.DOI
  27. [28]Saralees Nadarajah. A generalized normal distribution. Journal of Applied Statistics, 32(7):685–694, 2005. doi: 10.1080/02664760500079464.DOI
  28. [29]NVIDIA. CUDA Toolkit 13.4 release notes. https://docs.nvidia.com/cuda/archive/13.4.1/cuda-toolkit-release-notes/index.html, 2026a.
  29. [31]P. F. Panter and W. Dite. Quantization distortion in pulse-count modulation with nonuniform spacing of levels. Proceedings of the IRE, 39(1):44–48, 1951. doi: 10.1109/JRPROC.1951.230419.DOI
  30. [33]Bita Darvish Rouhani, Ritchie Zhao, Ankit More, Mathew Hall, Alireza Khodamohammadi, Summer Deng, Dhruv Choudhary, Marius Cornea, Eric Dellinger, Kristof Denolf, Dusan Stosic, Vennugil Elango, Maximilian Goloub, Alexander Heinecke, Phil James-Roxby, Dharmesh Jani, Gaurav Kolhe, Martin Langhammer, Ada Li, Levi Melnick, Maral Mesmakhosroshahi, Andres Rodriguez, Michael Schulte, Rasoul Shafipour, Lei Shao, Michael Siu, Pradeep Dubey, Paulius Mickevicius, Maxim Naumov, Colin Verrilli, Ralph Wittig, Doug Burger, and Eric Chung. Microscaling data formats for deep learning. arXiv preprint arXiv:2310.10537, 2023.arxiv.org/abs/2310.10537
  31. [34]Semyon Savkin, Eitan Porat, Or Ordentlich, and Yury Polyanskiy. NestQuant: Nested lattice quantization for matrix products and LLMs. In International Conference on Machine Learning (ICML), 2025. arXiv:2502.09720.arxiv.org/abs/2502.09720
  32. [35]Lawrence C. Stewart, Robert M. Gray, and Yoseph Linde. The design of trellis waveform coders. IEEE Transactions on Communications, 30(4):702–710, 1982.DOI
  33. [36]Albert Tseng, Jerry Chee, Qingyao Sun, Volodymyr Kuleshov, and Christopher De Sa. QuIP#: Even better LLM quantization with Hadamard incoherence and lattice codebooks. In International Conference on Machine Learning (ICML), 2024a. arXiv:2402.04396.arxiv.org/abs/2402.04396
  34. [37]Albert Tseng, Qingyao Sun, David Hou, and Christopher De Sa. QTIP: Quantization with trellises and incoherence processing. In Advances in Neural Information Processing Systems (NeurIPS), 2024b. arXiv:2406.11235.arxiv.org/abs/2406.11235
  35. [38]Albert Tseng, Zhaofeng Sun, and Christopher De Sa. Model-preserving adaptive rounding. In International Conference on Machine Learning (ICML), 2026. arXiv:2505.22988.arxiv.org/abs/2505.22988
  36. [39]Tycho F. A. van der Ouderaa, Mart van Baalen, Paul Whatmough, and Markus Nagel. Leech lattice vector quantization for efficient LLM compression. arXiv preprint arXiv:2603.11021, 2026.arxiv.org/abs/2603.11021
  37. [40]Andrew J. Viterbi and James K. Omura. Trellis encoding of memoryless discrete-time sources with a fidelity criterion. IEEE Transactions on Information Theory, 20(3):325–332, 1974.

Paper details

vlnc:W_53zwejf8
Version
v1 · latest
Published
Fresh — added to the Hub within the last 30 days
Added
License
CC BY 4.0
Usage

views · 0

downloads · 0

A view counts once per browser per day, a download each time the PDF is requested.

  • Computer Science

Not recorded for this paper

View statement
Looking for related papers…
Contents