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 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 -bit quantizer: at unit variance its mean squared error is at least [9]. We therefore score quantizers in effective bits, , 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 rises (Figure 1b). A better Gaussian quantizer is a better LLM quantizer, so the rest of the paper compares formats on . 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 at 4 bits: CPTC, RPTC, the QTIP variants at , 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 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 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 , with 32× less search. ‡At 4.25 bits with a per-block scale index.
| Codebook | Decoder (ops, storage) | All | Retargetable | Encode/value | Waste at 4 bits |
| INT4 / FP4 | cast, 0 | ×, per width | × | round | 0.86 / 0.85 |
| NF4 / Lloyd–Max | lookup, 32 B | ×, per width | × / ✓ | round | 0.67 / 0.64 |
| MXFP4 / NVFP4 (4.25/4.5 b) | cast + scale, 0 | ×, per width | × | round | 1.09 / 1.11 |
| E8P (QuIP#) | signs + 2 KiB LUT | ×, per rate | × | E8 structured search | 0.56 |
| Nested E8 (NestQuant) | E8 closest point, 0 | ✓ | × | E8 closest point, | 0.36‡ |
| Learned VQ | MiB LUT | ×, per rate | ✓ | beam search, | n/r |
| TK | n/r | ||||
| LC trellis | 1 mul + 8–128 KiB LUT | ✓ | ✓ | Viterbi, | 0.06 |
| RPTC | 128 KiB LUT | ✓ | ✓ | Viterbi, | 0.10 |
| QTIP HYB | hash + 2 KiB LUT | ×, | ✓ | Viterbi, | 0.39 |
| QTIP 1MAD / 3INST | 1–3 int ops, 0 | ✓ | ×, fixed law | Viterbi, | 0.14 / 0.15 |
| CPTC (ours) | 2 mul + add + 64 B LUT | ✓, | ✓, exact scalar | Viterbi, ()† | 0.07 |
Table 1.
Trellis codes ([25, 37]) do that while keeping decoding simple: each value is decoded from the last bits of the code stream, the state, by a fixed map ( 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 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 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).
| Codebook | Storage | ||||||
| QTIP HYB | 2 KiB | 0.932 | 1.912 | 2.840 | 3.611 | 3.936 | 3.936 |
| QTIP 3INST | — | 0.936 | 1.931 | 2.902 | 3.852 | 4.748 | 5.469 |
| QTIP 1MAD | — | 0.933 | 1.931 | 2.907 | 3.864 | 4.765 | 5.514 |
| RPTC | 128 KiB | 0.956 | 1.935 | 2.916 | 3.896 | 4.872 | 5.840 |
| LC | 8–128 KiB | 0.960 | 1.950 | 2.945 | 3.938 | 4.930 | 5.922 |
| CPTC | 64 B | 0.950 | 1.948 | 2.943 | 3.934 | 4.913 | 5.802 |
| CPTC | 128 B | 0.950 | 1.947 | 2.943 | 3.934 | 4.919 | 5.869 |
| CPTC | 256 B | 0.949 | 1.947 | 2.943 | 3.935 | 4.926 | 5.904 |
Table 2. Effective bits () of every trellis codebook at each bit width, all run at 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 the orthonormal Hadamard matrix, built by doubling for a power of two, and random sign vectors , , the RHT of an weight matrix is
and are orthogonal, so the layer computes with fast transforms on its input and output, and every entry of is a signed sum of all entries of , 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 be the unit-variance source (the target distribution after the preprocessing above), its reconstruction, the distortion (MSE), and the rate-distortion function of under squared error (Berger, [9]): the minimum rate, in bits per value, at which any coder reaches distortion . We define effective bits as the Shannon lower bound on at the measured distortion, the left end of the classical sandwich
where is entropy power, is differential entropy in nats, and is independent test-channel noise. A quantizer spending bits per value has , so the deficit never understates the wasted rate, and one effective bit is a factor in distortion. For the Gaussian, our default target, the bound is exact (); for the other targets Appendix § 13.§ 2 verifies that the sandwich is thin at .
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 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 -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 bits per value: each value’s reconstruction depends on its neighbors’ code bits too. The decoder keeps an -bit state , simply the most recent bits of the code stream, and maps it to a value through a fixed function . In the bitshift subfamily relevant here, reading the next value’s bits just shifts them into the state register, which is why decoding stays hardware-trivial. Although only bits are stored per value, consecutive values share state bits, so the decoder effectively selects from a -entry codebook, the source of the quality beyond scalar formats. The price is a Viterbi encoding search over all states (§ 3.2).
Prior bitshift trellis codes. The map 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 states with a stored random permutation and assigns state the value at quantile of the target’s optimal reproduction law; this provably meets the marginal condition of asymptotically optimal codes and empirically approaches the Shannon bound as grows, but the shuffle is entries. QTIP (Tseng et al., [37]) computes 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 -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 -dimensional VQ searches codewords unless it is a lattice with a fast closest-point algorithm; trellis codes pay a Viterbi search over states, which CPTC’s small- 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 processing elements, one row per partition and columns ( 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 . Lines 6–10 are an optional storage optimization: for mirror-symmetric codebooks only the lower half ( entries) is stored and the upper half is served by a mirrored lookup (§ 3.3).
Require: -bit state ; coefficients ; codebook table , or its lower half under symmetric storage; optional shift (default ).
▷ tap width; ,
▷
▷
return ▷ if the full table is stored; else lines 6–10
if then ▷ symmetric-storage lookup (optional)
return
else
return
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 -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 of bits (we use throughout); a table of entries, where the tap width is the number of top bits kept from each product; and an optional shift (default 0). The shift lets a decoder built with tap width emulate any smaller tap width (Proposition 2). Algorithm 1 and Figure 2 show how one value is decoded from the -bit state , of which only the low bits carry information (§ 3.2). Every step is an integer operation.
Figure 2. The CPTC decoder for one value (, Algorithm 1): the state shifts right to take the next 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 because returns diminish there: encoding cost grows as 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 (), only its lower half of entries is stored, and lines 6–10 of Algorithm 1 read it with one comparison and a conditional sign flip. We use 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 (§ 3.3).
Trellis state and Viterbi encoder
A block of values is stored as code bits. The decoder slides an -bit window over them in steps of 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 bits: the coefficients end in zeros, so the stream bits above the low drop out of the products modulo . Second, the block is tail-biting: its first 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 and takes the next stream bits at the top (Figure 2).
The encoder is the standard Viterbi search for the lowest-MSE path through the -state trellis, in time and 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 on one GPU or, in cycle-level simulation, one Trainium 4 chip (§ 6.3).
Symmetric lookup table and output types
The index ranges over , that is at . 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 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 the table needs at least stored entries, which for gives .
Entries are stored one per byte as E2M5 (§ 6.1); a platform without E2M5 can store INT8 instead, at no cost up to and 0.03 bits at (0.13 on the Laplacian; Appendix § 13.§ 2).
The table starts from the target distribution and the index distribution of the chosen pair . Let be the target’s CDF, let count the states whose index is , and let be the index CDF, with . Cell owns the probability interval , and its starting entry is the conditional mean of the target over that interval:
The target enters only through the table, so retargeting changes only the stored values, and one coefficient pair serves every target. (The reported results use one pair per rate, which at 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 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: , where ctz counts trailing zeros. For one coefficient is enough: , an odd multiple of (Table 6) and . The choice is the scalar embedding of Proposition 1. For , two nonzero coefficients give the near-triangular index distribution that the table exploits. Best coefficients. We search for each depth and rate on Gaussian samples, exhaustively at small and by sampling above (Appendix § 11.§ 2 lists the pairs and the protocol). At quality rises with every step in and reaches 3.93 effective bits at .
| Unified | |||||||
| 1 | 0000, 8000 | ||||||
| 2 | 0000, C000 | ||||||
| 3 | 0000, A000 | ||||||
| 4 | 0000, 5000 | ||||||
| 5 | 0000, 2800 | ||||||
| 6 | 0000, A400 | ||||||
| 7 | 7A00, 7A00 | 3A00, 3A00 | A200, A200 | 6200, C400 | 2E00, 5C00 | 0200, 0400 | 6200, C400 |
| 8 | 8700, 8700 | 7A00, BD00 | 6100, 6100 | 1B00, 3600 | 7700, DC00 | 0400, 8100 | 9700, AE00 |
| 9 | 8580, 8580 | 4280, 4280 | E180, E180 | 6100, B080 | 6500, 9280 | CC80, D900 | 9900, AC80 |
| 10 | 8940, 8940 | 41C0, 41C0 | 8A80, 9540 | 39C0, 4E00 | 1A40, A400 | 1380, 99C0 | A880, C440 |
| 11 | 7920, 7920 | 41E0, 41E0 | 7480, AD20 | 5D00, B3A0 | 6040, A820 | 1400, C0A0 | 9BE0, A7C0 |
| 12 | 5F60, 6BB0 | 77D0, C7A0 | 7DA0, E2D0 | 81D0, EE80 | 6810, A020 | 7020, 9410 | 4550, 82A0 |
| 13 | 61C8, 6F20 | 3490, 8C48 | 8320, DCC8 | 51C0, DE38 | D820, F008 | 3008, 7C10 | 43F8, 83F0 |
| 14 | 6BBC, 7178 | 7708, C884 | 74B0, AB2C | 6D20, 82A4 | 07F0, CFFC | 5008, E404 | 7E48, C824 |
| 15 | 6B6E, 73DC | 792E, C75C | 1D48, 8252 | 11CA, 5E50 | 9808, A002 | 5A84, 9DC2 | 483E, 677C |
| 16 | 9097, 97AE | 7AE6, C8B3 | 7474, AB1D | 6A78, 85CF | 1C04, 3C01 | 0AEE, D337 | 9282, A981 |
Table 6.
CPTC generalizes scalar quantization.
Every scalar format is a special case of the decoder:
Proposition 1 (Scalar embedding). For and any -entry codebook with representable in the table data type, the CPTC decoder with , , , and produces for every .
The proof is direct from Algorithm 1: zeros , and the shift leaves . Here and the trellis is degenerate. As a corollary, every INT, FP, Lloyd–Max or other -bit scalar format with is a CPTC instance with . (Irrational codepoints need a table type matching the implementation’s output precision, e.g. FP16.)
Adopting the decoder therefore never costs quality: 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 .
| 0.84 (0.75) | 1.91 (1.75) | 2.94 (2.75) | 3.95 (3.75) | 4.95 (4.75) | 5.89 (5.75) | |
| 2.0 | 0.95 (0.73) | 1.95 (1.54) | 2.94 (2.43) | 3.93 (3.36) | 4.91 (4.32) | 5.80 (5.30) |
| 1.5 | 0.94 (0.63) | 1.94 (1.42) | 2.93 (2.29) | 3.92 (3.21) | 4.89 (4.17) | 5.74 (5.15) |
| 1.0 | 0.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 () of CPTC on targets from uniform () to Laplacian (), with the best scalar quantizer for each cell in parentheses; only the 64 table bytes change between rows (, , 3 seeds; entropy-power normalized, so is an upper bound in every column; the row repeats Table 2).
Likewise, for RPTC’s -entry codebook fits in CPTC’s table verbatim (Proposition 1 with ). For CPTC computes a structured permutation in place of RPTC’s random one, trading entries for two multiplications.
An implementation also emulates smaller configurations (Appendix § 11.§ 3). Say a table data type dominates if some scale makes every value of , multiplied by , a value of .
Proposition 2 (Dominance). A decoder with parameters bit-exactly emulates any decoder with , , and dominated by : replace each coefficient by , set the shift ( the emulated decoder’s shift), and load the table rescaled by (outputs then agree up to the factor , and exactly when ).
The triangular index distribution as a companding law
With only 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 and index law , the codepoint density is . 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 equal-mass Gaussian codepoints the largest sits at only , and as a scalar codebook 83% of its error comes from its two end cells. The scalar-optimal placement, (Panter & Dite, [31]), instead spreads codepoints wider than the data, by 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 wider than the data, with the outermost quantile codepoint at (Figure 3). That lies between the source width and the scalar-optimal , 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 , (3.93 → 3.25, Table 14).
Figure 3. Where the two index laws put their codepoints (, 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 ). Bottom: the two index laws over the 127 table cells.
| Lloyd–Max | Uniform fill | RPTC | LC, 64 B | CPTC (E2M5) | CPTC (FP16) | |
| (uniform) | 3.75 | 3.53 | 3.93 | 3.95 | 3.95 | 3.95 |
| 2.0 (normal) | 3.36 | 3.25 | 3.90 | 3.90 | 3.93 | 3.93 |
| 1.5 | 3.21 | 3.11 | 3.87 | 3.86 | 3.92 | 3.92 |
| 1.0 (Laplacian) | 2.91 | 2.78 | 3.83 | 3.77 | 3.88 | 3.88 |
Table 14. Effective bits (↑) at , on generalized-Gaussian targets, entropy-power normalized so 4.00 is an upper bound in every row (, 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 be i.i.d. with a density and finite variance and let a code of rate bits per value (any block length, any encoder) reproduce each by some , where is a fixed finite set (more generally for codes that emit -tuples, at rate per tuple, with distortion per value). Then
the alphabet-constrained rate-distortion function. In particular
for every trellis depth and block size , and , with 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 , 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 and at 3.936 for every , which is the plateau in Table 2 (ceilings in Table 9).
| Alphabet | |||||||
| Shannon limit | 1.000 | 2.000 | 3.000 | 4.000 | 5.000 | 6.000 | |
| Lloyd–Max optimal 127-point table | 127 | 1.000 | 2.000 | 3.000 | 3.999 | 4.993 | 5.930 |
| CPTC generated table, E2M5 (deployed) | 1.000 | 2.000 | 3.000 | 3.998 | 4.987 | 5.871 | |
| CPTC measured, | 0.950 | 1.948 | 2.943 | 3.934 | 4.913 | 5.802 | |
| Equal-mass table, midpoints | 127 | 1.000 | 1.995 | 2.955 | 3.786 | 4.316 | 4.521 |
| Equal-mass table, midpoints | 64 | 1.000 | 1.987 | 2.898 | 3.577 | 3.894 | 3.966 |
| QTIP HYB pair table | 1,024 pairs | 1.000 | 1.994 | 2.944 | 3.687 | 3.936 | 3.936 |
| HYB measured, | 0.932 | 1.912 | 2.840 | 3.611 | 3.936 | 3.936 |
Table 9. The most effective bits (↑) any code of rate can reach with a given reproduction alphabet, at any trellis depth (Theorem 1, standard normal). Measured rows repeat Table 2; the CPTC row uses the generated table of each . HYB’s alphabet is 512 -means pairs with a sign flip on the first component (1,024 pairs at rate per pair).
Two further threads are developed in the appendices. Achievable rate (Appendix § 12.§ 3): with one multiplication and a full table (, ) the decoder is RPTC with the algebraic permutation in place of a random one. For every odd multiplier 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 values costs about 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 , the coefficients of Table 6, (i.i.d.) or (matmul), tail-biting encoding, and the generated tables of § 3.3.
I.i.d. source quantization
We generate 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 scores (Appendix § 13.§ 1).
Standard normal at (Figure 1a). CPTC at reaches . That matches RPTC run two state bits deeper (3.92 at , Table 11) and exceeds QTIP’s best 4-bit variant (3.86), a score CPTC already matches at . Scalar and block-scaled formats score 0.5–0.8 effective bits lower (Table 1).
| 8 | 9 | 10 | 11 | 12 | 13 | 14 | 15 | 16 | 17 | 18 | |
| QTIP 1MAD | — | — | — | — | — | — | — | — | 3.86 | — | — |
| RPTC | 3.45 | 3.55 | 3.64 | 3.72 | 3.78 | 3.82 | 3.85 | 3.88 | 3.90 | 3.91 | 3.92 |
| LC, 64 B | 3.36 | 3.70 | 3.81 | 3.86 | 3.87 | 3.88 | 3.89 | 3.89 | 3.90 | — | — |
| CPTC | 3.77 | 3.81 | 3.84 | 3.86 | 3.89 | 3.90 | 3.92 | 3.93 | 3.93 | — | — |
Table 11. Effective bits (↑) at each trellis depth for (, samples): RPTC, the 64-byte LC code and CPTC, with QTIP’s 1MAD at (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 under one protocol. The QTIP rows run the authors’ released code and tables; HYB emits value pairs from a 512-pair -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 CPTC rows double the table (E2M5 and FP16).
CPTC leads every QTIP variant at every , by a margin that grows from 0.014 bits at to 0.29 at ; HYB’s fixed alphabet caps it past (Theorem 1). With 128–2,048× the storage, LC leads every column: by 0.002–0.004 bits over CPTC for , 0.010 at and 0.017/0.12 at , which CPTC in FP16 narrows to 0.004/0.018.
Beyond the Gaussian (Table 3). The unit-variance generalized Gaussian interpolates from the uniform () through the normal () to the Laplacian () [28, 7]. For each only the 64 table bytes change, and is entropy-power normalized (Equation (1)).
The trellis advantage over the Lloyd–Max scalar optimum of each holds everywhere and grows with tail weight, from 0.20 bits at to 0.97 at (). At CPTC nears scalar quality with a full bit less rate (2.90 at against scalar’s 2.91 at ). CPTC exceeds RPTC’s quantile codebooks across the family, by 0.02–0.05 bits at . A table filled as if the index were uniform trails CPTC by more as the tails grow, from 0.42 bits at to 1.10 at (Table 14). CPTC meets every target with the same coefficients. On the Gaussian () the gap to the bound is 0.05–0.07 bits for and grows to 0.20 at 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 –6, by more on heavy-tailed targets, and by about twice that at –5 with 32-byte tables (Appendices § 13.§ 1 and § 13.§ 2). A table with , or an INT() table, has only codepoints, one short of a rate- scalar quantizer, so no trellis depth can match scalar quality (Proposition 4). This makes the smallest table that can beat scalar at . Two doublings above that floor ( in INT()) cost at most 0.03 bits against the FP16 reference at every (Table 18, Appendix § 13.§ 3).
Table 18: The smallest matched codebook, stored in INT(), and its effective bits (; 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 ( entries of bits), and the last two columns the same-size and the codebooks in FP16.
| Codepoints | Type | Scale | Table bits | , INT() | same , FP16 | , FP16 | ||
| 1 | 2 | 7 | INT3 | 1.75 | 12 | 0.95 | 0.95 | 0.95 |
| 2 | 3 | 15 | INT4 | 2.75 | 32 | 1.93 | 1.94 | 1.95 |
| 3 | 4 | 31 | INT5 | 5 | 80 | 2.92 | 2.94 | 2.94 |
| 4 | 5 | 63 | INT6 | 9 | 192 | 3.91 | 3.93 | 3.93 |
| 5 | 6 | 127 | INT7 | 16 | 448 | 4.90 | 4.92 | 4.92 |
| 6 | 7 | 255 | INT8 | 30 | 1,024 | 5.87 | 5.90 | 5.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 of Ang et al. [6] for a matrix product whose operand pairs have correlation . The density turns bimodal past a phase transition at . We build the table by moving each entry of the generated Gaussian table to the same quantile of (Appendix § 13.§ 5). Their work and ours are orthogonal: they improve the codebook for a given rate- scalar quantizer, and we improve the coder for a given codebook. This is the table-design flexibility that RPTC pays entries for and QTIP’s hash-based variants give up. It is a demonstration only: a deployment would estimate 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. and are drawn so each output entry’s multiplicative pairs are i.i.d. bivariate standard normal with correlation , and we report the relative Frobenius error of over 10 trials for , at , .
Figure 4 shows that CPTC-MMAWARE (CPTC with the table) has the lowest error at every tested, tied with Gaussian-table CPTC at . Its edge over the best standard scalar format (NF4; Dettmers et al. [13]) widens from at to at . There it is also better than Gaussian-table CPTC and better than the scalar MatMul-Opt of Ang et al. [6]. Trellis coding alone cannot capture the matmul-tail importance that 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 ; 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- numbers are in Appendix § 13.§ 5 (Table 19).
| Method | 0.0 | 0.3 | 0.5 | 0.6 | 0.7 | 0.8 | 0.9 |
| INT4 | 0.162 | 0.044 | 0.038 | 0.031 | 0.032 | 0.027 | 0.025 |
| FP4 | 0.159 | 0.043 | 0.034 | 0.033 | 0.031 | 0.030 | 0.028 |
| NF4 | 0.139 | 0.036 | 0.029 | 0.026 | 0.026 | 0.023 | 0.022 |
| MatMul-Opt ([6]) | 0.139 | 0.033 | 0.022 | 0.019 | 0.017 | 0.014 | 0.012 |
| CPTC-Gauss | 0.093 | 0.024 | 0.019 | 0.017 | 0.018 | 0.018 | 0.018 |
| CPTC-MMaware | 0.093 | 0.022 | 0.016 | 0.014 | 0.013 | 0.011 | 0.010 |
Table 19. Relative Frobenius error () of the quantized product against the exact one at (, , mean of 10 trials, SEM ). 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). CPTC is the 63-codepoint table of the GPU kernel (§ 6.2).
| Codebook | W2 | Perplexity W2 | Perplexity C4 | Acc 0-shot | W2 | Perplexity W2 | Perplexity C4 | Acc 0-shot | |
| 8B-Instruct | 70B-Instruct | ||||||||
| 16 | BF16 | 0 | 6.502 | 8.022 | 71.4 | 0 | 3.524 | 6.460 | 77.1 |
| 4 | QTIP HYB | 0.0131 | 6.608 | 8.117 | 71.2 | 0.0298† | 3.685† | 6.516† | 76.8 |
| QTIP 1MAD | 0.0100 | 6.579 | 8.092 | 71.5 | 0.0238 | 3.647 | 6.500 | 76.8 | |
| CPTC | 0.0096 | 6.570 | 8.088 | 71.3 | 0.0225 | 3.631 | 6.500 | 76.9 | |
| CPTC | 0.0095 | 6.566 | 8.086 | 71.3 | 0.0227 | 3.642 | 6.499 | 76.9 | |
| 3 | QTIP HYB | 0.0450 | 6.852 | 8.344 | 70.8 | 0.0967† | 4.035† | 6.649† | 76.3 |
| QTIP 1MAD | 0.0405 | 6.824 | 8.314 | 70.3 | 0.0876 | 3.965 | 6.628 | 76.4 | |
| CPTC | 0.0396 | 6.828 | 8.294 | 70.6 | 0.0856 | 3.968 | 6.621 | 76.6 | |
| CPTC | 0.0387 | 6.797 | 8.297 | 70.5 | 0.0845 | 3.946 | 6.621 | 76.6 | |
| 2 | QTIP HYB | 0.2424 | 8.402 | 9.798 | 66.7 | 0.3281† | 5.259† | 7.316† | 74.3 |
| QTIP 1MAD | 0.2271 | 8.254 | 9.696 | 67.3 | 0.3221 | 5.225 | 7.286 | 74.3 | |
| CPTC | 0.2212 | 8.228 | 9.653 | 67.1 | 0.3145 | 5.191 | 7.265 | 74.7 | |
| CPTC | 0.2202 | 8.238 | 9.634 | 67.4 | 0.3176 | 5.210 | 7.269 | 74.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). is a smooth function of (quadratic fits, ): each effective bit is worth in KL at 70B, is an MSE, and to 3K at 8B from 2 to 4 bits. Within every rate the KL order of the three codebooks is their 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 , 14% at , 27% at 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 arm costs at most 0.001 KL at either scale and leads at 70B for , 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 , and the formats drop together at . A preliminary run on Qwen3.8-27B ((Qwen Team, 2026)), a hybrid gated-DeltaNet model, shows the same ordering (Table 22).
| Codebook | ↓ W2 | Perplexity ↓ W2† | Perplexity ↓ C4 | Acc ↑ 0-shot | |
| 16 | BF16 | 0 | 7.685 | 6.800 | 74.1 |
| 5 | CPTC | 0.0295 | 7.563 | 6.805 | 73.9 |
| 4 | HYB | 0.0719 | 7.263 | 6.817 | 73.7 |
| 4 | CPTC | 0.0563 | 7.447 | 6.817 | 74.0 |
| 3 | HYB | 0.1175 | 7.270 | 6.879 | 74.1 |
| 3 | CPTC | 0.1060 | 7.475 | 6.870 | 73.8 |
| 2 | HYB | 0.3063 | 6.802 | 7.222 | 73.1 |
| 2 | CPTC | 0.2630 | 7.088 | 7.192 | 73.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 and with FP8 at , 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 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 , 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 follows from that of value : , with value ’s -bit code. The bits shifted out at the top contribute only multiples of to a product, so each coefficient’s product obeys the same recurrence:
A lane decodes its 8 values per cycle as one batch and evaluates this recurrence in parallel inside it, which replaces each multiplier with a -bit shift and one addition of , a product () whose partial-product array is about the size of the full one.
Data layout (Figure 5). Each tail-biting block of values is stored as a 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 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: a multiple of 32 bits at FP4 rate and of 64 bits at FP8 rate, i.e. a multiple of and of respectively. The minimum is 8 to 64 values depending on , and the used throughout this paper satisfy the constraint for every . The layout is compatible with Trainium 4’s microscaling support.
Figure 5. How one CPTC block (, ) is laid out in SBUF. Top: the logical 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 value. 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 in steps of for magnitudes below 2, in and in .
Throughput. The CPTC path sustains the chip’s native per-cycle weight-load rate: parity with FP4 for and with FP8 for . 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 table stored in full, which needs no mirror fold (on GPUs in FP16, the CPTC 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 two-multiply decoder, and 0.79× for a Hopper-only state-table variant at 3.84 effective bits. This makes the case for a native decode instruction. On CPUs, CPTC at streams the forward pass as fast as an INT4 kernel (0.98× on AMD Zen 4, 0.97× on AWS Graviton5; Appendix § 14.§ 2).
| Platform | CPTC decoder | FP16 | INT4 | CPTC | CPTC speed vs. INT4 |
| NVIDIA L40S | two multiplies, | 19.08 | 5.12 | 5.24 | 0.98× |
| NVIDIA H100 | two multiplies, | 5.51 | 2.11 | 3.40 | 0.62× |
| NVIDIA H100 | state table, | 5.51 | 2.11 | 2.67 | 0.79× |
| AMD Zen 4, 64 cores | AVX-512 | 51.9 | 13.3 | 13.6 | 0.98× |
| AWS Graviton5, 96 cores | NEON | 36.0 | 8.6 | 8.9 | 0.97× |
Table 5. Time per token for the linear layers of Llama 3.1 8B at batch 1 (ms, ↓): CPTC at 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 , () to 3.3 billion at , at MSE within 0.02% of a torch.compile reference on identical inputs. At 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 means 32× less search, since work is . 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 (3.84 effective bits at ).
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 and , one chip encodes 69 million values/s at and 4.6 billion at (a reference point, not a comparison with the GPU), so it too encodes those 7.0 billion values in under two minutes. For the rate stays within 0.90–1.04× of the rate (Table 27).
| 1 | 2 | 3 | 4 | 5 | 6 | |
| 8 | 14,620 | 15,518 | 16,464 | 16,586 | 16,328 | — |
| 9 | 7,814 | 8,333 | 8,774 | 8,924 | 8,846 | 8,624 |
| 10 | 3,895 | 4,163 | 4,476 | 4,558 | 4,583 | 4,546 |
| 11 | 1,921 | 2,063 | 2,194 | 2,284 | 2,321 | 2,321 |
| 12 | 989 | 1,058 | 1,063 | 1,139 | 1,159 | 1,170 |
| 13 | 498 | 529 | 546 | 564 | 575 | 584 |
| 14 | 252 | 263 | 274 | 281 | 283 | 290 |
| 15 | 120 | 129 | 138 | 140 | 141 | 141 |
| 16 | 42† | 63 | 67 | 69 | 70 | 70 |
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 (, best launch per cell). “—”: not supported, as the backtrace needs ; † 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 decoder at 0.62× an INT4 baseline (0.79× with an state-table variant, Table 5), and on Arm the NEON decoder runs 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 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 and the standard scalar formats, meeting all four requirements of § 2. At 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 () and FP8 () 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 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.

Figure 6. How a block is decoded from the packed bitstream. Top: bit layout for , , : value ’s code occupies bits to (bit 0 rightmost), window reads the 16 bits starting at bit , 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 bits are logically appended to its end (line 1 of Algorithm 2; at depth only the first of them affect any decoded value), so the -bit windows read at positions 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 , 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].
Recommended coefficients and table generation
Table 6 gives recommended pairs, searched over pairs in whose OR is odd, on – Philox-generated samples (a selection seed disjoint from every evaluation seed) at the paper’s table-size parameter : per depth, a per- searched pair for every and a single unified pair selected on all rates jointly (minimum mean deficit over the six rates). The column is the default pair, from a search exhaustive through and sampled above (which the plateau below justifies); the other columns re-score up to mirror-symmetric candidates per depth on all six rates. The pair of each is then chosen among the best few candidates with generated E2M5 tables under the standard protocol, and every change is confirmed on samples. Coefficients are in the 16-bit form of Algorithm 1 (16 − trailing zeros). For , suffices, since all states map directly into the table; for the coefficients are nonzero, and, when distinct, produce the near-triangular index law of § 4.1. All searches at require a perfectly mirror-symmetric index histogram (), which makes the fold of § 3.3 exact. At low rates and small depths the per- winners are equal pairs (, which index the 64 even cells uniformly): there center resolution matters more than tail protection. At quality is monotone in and saturates at (, ); the unified pair is within 0.017 bits of the per- best at every rate for .
Table generation. The tables of § 3.3 are generated per target and at from 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 and 20 damped ones, keeping the round that scores best on a held-out set. Generation starts from Equation (2) rescaled by with , a heuristic starting width from the point-density law of fixed-rate high-resolution quantization in dimensions (Gersho [18]) with a rate correction (for the generalized Gaussians of Appendix § 13.§ 2, ); for , where every state has its own entry, it is run from the Equation (2) table of every odd multiplier , each of which orders the states differently, prescreened
Algorithm 2 CPTC block decode from the packed bitstream (tail-biting).
Require: code bits of one block ( bits per value, values); parameters of Algorithm 1.
▷ tail-biting: wrap the first bits
for do
▷ little-endian window; no masking to needed
▷ Algorithm 1
end for
return
Table 6: The coefficient pairs to use, in hex, for each trellis depth : the searched pair for each bit width and one unified pair for all rates, searched at . The column is the default pair; for one pair serves every .
with rounds on samples with the best three kept. The result is fitted to its data type by 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 , with Equation (2) tables, of every unordered pair with odd OR (histogram symmetry not imposed) at (24,640 pairs) and (393,472), plus a 40,000-pair sample at , shows that failure is governed by the sum , with : no pair with or 2-adic valuation (≈14% of the space) is within 0.05 bits of the optimum at or . Outside this set the landscape is a broadening plateau: the fraction of pairs within 0.05 bits of the optimum grows from 15% () to 30% () to 63% (), 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- selection. At the unified pair scores (0.948, 1.945, 2.938, 3.931, 4.906, 5.795) for (generated E2M5 tables), within 0.008 bits of the per- pair at every rate, so joint selection is essentially free at the design point. The stakes are larger at small depths: at the unified pair gives up 0.02 bits to the default pair at and gains 0.08–0.09 over it at , the relevant trade for online small- uses (§ 6.3). The paper’s quality tables load the per- column for each rate; the unified column serves deployments that fix one pair for all rates.
Coefficients for . Where the 127-codepoint alphabet ceiling binds (), one table doubling recovers about a third of the 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 histogram is full and mirror-symmetric yields, with FP16 tables, 4.926 at (pair (0xBEC5, 0xC514)) and 5.904 at (pair (0x06CE, 0x13E7)), with unchanged; in E2M5 at the scale of Appendix § 13.§ 3 the same pairs score 4.919/5.869, the CPTC row of Table 2. A single unified pair (0x518D, 0x781A) is within 0.005 bits of the per- winners at every rate. By Proposition 2, hardware serves every 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 , , , and for (a signed -bit integer ramp at scale , every entry an E2M5 value for ) reduces Algorithm 1 to a direct integer lookup. Since , the trellis is degenerate. All indices fall in the lower half of the table; the symmetric upper half is unused.
FP4 via CPTC at . Setting , , , , and populating the first entries of 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 lets a -sized implementation emulate one built with a smaller table parameter : for every index in Algorithm 1 falls below , so the mirror branch of Algorithm 1 (lines 6–10) is inactive and the emulated codebook, signs stored explicitly, occupies the first entries of (the FP4 embedding above uses this). Width direction: replacing (mod ) by 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 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 at the boundary of group of values by constraining the parity (XOR) of that group’s emitted code bits to equal . 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 . Subsequent steps propagate only consistent paths, so the encoder stays , 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 code bits committed to it, removing one degree of freedom from the encoder’s search space: 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 , , an 8-bit scale per values () costs effective bits per value in theory and 0.132 measured, leaving CPTC at 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 for -point codebooks , the midpoint quantile of each cell of the index law’s CDF , 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 ) to 29× (at ) worse than triangular. The mechanism is overload: the uniform law’s largest codepoint sits at the quantile (2.66 at ), 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 while granular error decays as (Panter & Dite, [31]; Bennett, [8]), the uniform law also loses the rate: doubling buys only ~2.3× instead of ~4×. Matching the 127-entry triangular codebook with a uniform-composed one takes : the composition is worth more than 4× in table size.
| Uniform | Triangular | Lloyd–Max | |||
| 15 | 2.52e-2 | 1.14e-2 | 1.07e-2 | 2.2 | 1.07 |
| 31 | 1.00e-2 | 2.90e-3 | 2.66e-3 | 3.5 | 1.09 |
| 63 | 4.17e-3 | 7.37e-4 | 6.65e-4 | 5.7 | 1.11 |
| 127 | 1.79e-3 | 1.88e-4 | 1.66e-4 | 9.6 | 1.13 |
| 255 | 7.85e-4 | 4.77e-5 | 4.15e-5 | 16.5 | 1.15 |
| 511 | 3.50e-4 | 1.21e-5 | 1.04e-5 | 28.9 | 1.17 |
Table 7. Exact MSE (↓) of -point Gaussian codebooks built from a uniform vs. a triangular index law, against the Lloyd–Max optimum.
Beyond the Gaussian. The same comparison at (all sources unit variance): uniform-over-triangular MSE ratio is 9.6× for , 15.6× for Laplacian, and 7.4× for Student-. 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 (, , , the paper’s , Viterbi encoding of i.i.d. 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 with quantile-midpoint tables (the same at 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 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 , . This compares visit frequencies only; which samples an entry receives is a separate matter, addressed by table generation (§ 3.3).
| Effective entries | Table law | |
| 127 () | Uniform composition | 3.233 |
| 127 () | Scalar Lloyd–Max table | 3.917 |
| 127 () | Triangular composition | 3.919 |
| 63 () | Uniform composition | 3.197 |
| 63 () | Triangular composition | 3.903 |
| 31 () | Uniform composition | 3.048 |
| 31 () | Triangular composition | 3.821 |
Table 8. Effective bits (↑) of the full CPTC pipeline when only the law that fills the table changes (, , , 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 . Proposition 4 bounds what such a table can achieve when it has at most 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 be the -bit codeword, so . Since the are independent and is a function of , (independence and the chain rule; [9]). Each lies in , so with and the rate-distortion function with reproduction alphabet , which is convex and nonincreasing because the alphabet constraint is per letter and preserved under time sharing. Hence , i.e. . 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 is a bound, not a proven asymptote. It is also computable: is a convex program over the output law on , and the Blahut–Arimoto iteration (Blahut, [10]) converges to it. We discretize on 17,001 points of (step 0.001, far below every codepoint spacing) and bisect the log-slope to a bracket of . As a check, the 16-point Lloyd–Max alphabet at gives , the scalar Lloyd–Max value to four decimals, as it must (with 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 per pair on a grid over , 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 ), as the theorem requires, and the ceilings split CPTC’s gap to Shannon into a part its table values force () and a remainder (–measured). At 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 the table values force 0.013 of the 0.087-bit gap, at 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 and 0.06 below at . For HYB the ceiling saturates at 3.936 from 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 , 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 , and the overload error alone bounds regardless of or (the exact overload integral gives 4.16 at and 4.74 at ; the closed form alone 4.03 and 4.63), while the two-multiply law places the extreme cell at mass , an overload of at , below the Shannon distortion for every . This bound is a property of the composition, not of the multiplication count: stretching the 127-point uniform-law table by a factor raises its ceiling at from 3.82 at (conditional-mean entries; 3.79 with quantile midpoints, Table 9) to 3.92 () and 3.98 (). 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 and from 4.37 to 4.80 at , 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.
| Table | 1.05 | 1.1 | 1.2 | 1.3 | 1.4 | ||
| One multiply, 64 cells | 4 | 3.612 | 3.697 | 3.755 | 3.817 | 3.825 | 3.802 |
| One multiply, 128 cells | 4 | 3.777 | 3.832 | 3.862 | 3.878 | 3.858 | 3.820 |
| Two multiplies (CPTC), 127 cells | 4 | 3.930 | 3.935 | 3.932 | 3.908 | 3.871 | 3.826 |
| One multiply, 64 cells | 5 | 3.986 | 4.154 | 4.292 | 4.502 | 4.622 | 4.672 |
| One multiply, 128 cells | 5 | 4.374 | 4.526 | 4.629 | 4.760 | 4.796 | 4.790 |
| Two multiplies (CPTC), 127 cells | 5 | 4.902 | 4.916 | 4.918 | 4.901 | 4.866 | 4.822 |
Table 10. Effective bits () at when the table is stretched by a factor : one-multiply tables with conditional-mean entries (best of 16 random odd multipliers, chosen at on held-out data) against the two-multiply table of Equation (2) in FP16, before table generation (, 3 seeds).
Achievable rate and the limit 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 , for odd , , , and holding the target’s quantile values (RPTC’s rule; Equation (2) gives the cell means instead, with the same limit), CPTC is RPTC with the specific permutation in place of a random one: is a bijection for every odd , and the decoder computes . Consequently, for any target with CDF and finite variance, the decoded-state marginal under uniform states is the exact -point quantile discretization of , independent of , and converges weakly (and in Wasserstein-2) to the target as , 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 () satisfies it and yields a poor code. It concerns the optimal reproduction distribution, for Gaussian MSE, not the source; since Proposition 3 holds for any loaded , the table can be composed to the test channel, which at our rates is numerically indistinguishable from the source ( at ). The same reduction places one-multiply CPTC inside the linear congruential trellis family of Eriksson et al. [15]: carries the bitshift dynamics to an affine recursion, , 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 , where the per- 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 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 . Larger gives the Viterbi encoder more freedom to find a good cyclic walk; smaller adds tail-biting boundaries. Empirically (Table 12) quality saturates near on the standard normal at , .
| Block size | 16 | 32 | 64 | 128 | 256 |
| 3.24 | 3.71 | 3.87 | 3.92 | 3.93 |
Table 12. How effective bits (↑) depend on the block length (, , standard protocol).
Block-scaled scalar formats. The 4-bit formats that hardware executes natively attach one 8-bit scale to each group of values: MXFP4 (Rouhani et al., [33]) an E8M0 (power-of-two) scale with , 4.25 bits per value, and NVFP4 (Alvarez et al., [1]) an E4M3 scale with , 4.5 bits. Table 13 scores both on the standard normal under the protocol of § 5.1 ( 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 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 . CPTC’s coefficients are the best of a search (exhaustive through , 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 -sample normal set, evaluated on the standard -sample set. Selection gains far less than the gap to CPTC: best-of-100 RPTC reaches 3.49 at (vs. 3.45 single-draw, 3.77 CPTC), 3.78 at (vs. 3.78, 3.89), and 3.90 at (vs. 3.90, 3.93). Random-permutation distortion concentrates tightly (worst-of-100 to best-of-100 spans 0.08 bits at and under 0.02 from ), so selecting among random permutations does not close the gap to CPTC. Extending the reimplementation to gives the RPTC entries of Table 11 (3.91 and
| Element | Scale | bits/value | Format | ||
| FP4 E2M1 | E8M0 | 32 | 4.25 | 3.16 | MXFP4 |
| FP4 E2M1 | E8M0 | 16 | 4.50 | 3.18 | |
| FP4 E2M1 | E4M3 | 32 | 4.25 | 3.30 | |
| FP4 E2M1 | E4M3 | 16 | 4.50 | 3.39 | NVFP4 |
| INT4 | E8M0 | 32 | 4.25 | 2.86 | |
| INT4 | E4M3 | 16 | 4.50 | 3.53 | |
| FP6 E2M3 | E8M0 | 32 | 6.25 | 5.15 | MXFP6 |
| FP6 E2M3 | E4M3 | 16 | 6.50 | 5.33 | |
| FP4 E2M1 | per-tensor | — | 4.00 | 3.15 | |
| NF4 | per-tensor | — | 4.00 | 3.33 | |
| Lloyd–Max | per-tensor | — | 4.00 | 3.36 | scalar optimum |
| CPTC | in-stream 8-bit | 64 | 4.00 | 3.80 | Appendix § 11.§ 5 |
| CPTC | per-tensor | — | 4.00 | 3.93 | |
| CPTC | per-tensor | — | 6.00 | 5.80 |
caption: Block-scaled scalar formats on a standard normal: element type, scale type and group size , total bits per value including the scale, and effective bits (; 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 (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]: shift-register states, per-branch labels with , one shared odd generator and maximally separated offsets (their Theorems 1–2, extended to ), best of 150 random 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 (0.960/1.950/2.945/3.938). (ii) Full-codebook computed permutation (Proposition 3: , , -entry codebook built the same way, best of 200 odd multipliers per rate), a strengthening beyond their paper; it supplies (4.930) and (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 ), with the same two steps reaches 0.957/1.948/2.932/3.898/4.820/5.661 at : ahead of CPTC at , level at and behind by 0.011/0.036/0.093/0.141 at –6. With both tables halved (64 labels against CPTC’s 63-entry table, 32 bytes each) it reaches 0.957/1.944/2.914/3.848/4.705 at against CPTC’s 0.948/1.948/2.942/3.928/4.868: the gap at –5 roughly doubles, to 0.027/0.080/0.163 (at neither 63 nor 64 values can beat the 64-level scalar quantizer, Proposition 4). Across depth at it is the LC row of Table 11; below it has fewer than 128 labels, one per state, and its cell is the value above. Their Definition 3 read literally, with labels taken modulo 128, depends on only state bits and scores lower (3.861 at ).
For the headline margins we also report 10-seed precision: CPTC , scores 3.9334 0.0005 and RPTC , scores 3.9228 0.0004. A random permutation beats CPTC’s table in two cells of Table 2: (0.956 against CPTC’s 0.9497 0.0004), where its reproduction law is narrowest, and (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 ( samples, three seeds). QuIP#’s E8P is its 2-bit codebook (256 absolute-value entries with sign flips and a shift, 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: gives 1.727 at the released scale (0.0913 MSE, against the 0.089 Tseng et al. [37] report for the same codebook), gives 2.541, and 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 ( at 4 bits) and decodes with a second closest-point search; its encoder picks one of scales per block, a side channel of bits per value, under the shared pseudorandom dither of the released code. With a single scale (exactly 4 bits, scale swept, overload rate ) 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 and 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 () 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 method comparison of Table 14, the 64-byte LC comparison (Table 15) and INT8 tables (Table 16). For each the generation of § 3.3 starts from Equation (2) (empirical index intervals, per-cell conditional mean under in closed form through incomplete gamma functions) and its result is fitted to E2M5 at a per- scale chosen on one held-out seed, which keeps it within 0.01 bits of the FP16 one at for every , with the same and encoder throughout.
| 0.845 (−0.007) | 1.910 (−0.001) | 2.939 (−0.002) | 3.953 (−0.004) | 4.956 (−0.006) | 5.934 (−0.043) | |
| 2.0 | 0.956 (−0.009) | 1.947 (0.000) | 2.931 (0.011) | 3.896 (0.037) | 4.816 (0.096) | 5.660 (0.140) |
| 1.5 | 0.945 (−0.004) | 1.932 (0.005) | 2.908 (0.022) | 3.858 (0.060) | 4.749 (0.137) | 5.548 (0.194) |
| 1.0 | 0.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 () 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). , , 3 seeds.
| 0.838 (0.000) | 1.909 (0.000) | 2.937 (0.000) | 3.948 (0.001) | 4.949 (0.001) | 5.857 (0.034) | |
| 2.0 | 0.947 (0.000) | 1.947 (0.000) | 2.942 (0.000) | 3.933 (0.000) | 4.910 (0.001) | 5.767 (0.032) |
| 1.5 | 0.941 (0.000) | 1.937 (0.000) | 2.930 (0.000) | 3.918 (0.000) | 4.882 (0.004) | 5.736 (0.006) |
| 1.0 | 0.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 () of CPTC with an INT8 table on generalized-Gaussian targets, with its deficit against the E2M5 table in parentheses. , , 3 seeds.
Normalization and its tightness. For the unit-variance generalized Gaussian the differential entropy has the closed form with (Nadarajah [28]), which is what Equation (1)’s uses. As it gives the uniform’s , the classical quarter-bit advantage of the uniform source over the Gaussian at equal variance. For the Shannon ceiling is not exactly achievable at finite rate, but nearly so at : bisecting Equation (1)’s upper end for the distortion it certifies achievable (with by FFT convolution) places the true limit at above 3.995 effective bits across (above 2.98 at ) and above 3.95 for the uniform, whose discontinuous density slows the bound’s convergence. For 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 , with the rate. The 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- scale chosen on one held-out seed. INT8 matches E2M5 within 0.003 bits up to on every target. At 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 across under the identical encoder and protocol (, samples, 3 seeds; seed std 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 , chosen deterministically from the maximum entry of the 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 (the conditional mean of the triangle’s edge cell; its quantile midpoint in § 4.1 is 3.67), and 3.74 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 against E2M5’s 3.934.
Table 17: Effective bits () by table data type at (, samples, 3 seeds). Each unit-variance codepoint is stored as in the type’s grid, with the fixed scale of the Scale column, and decoded as the stored value/. 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 type | Scale | CPTC (), | Scalar (type alone), at | opt. | |||||
| INT3 | 0.875 | 0.95 | 1.60 | 1.60 | 1.60 | 1.60 | 1.60 | 1.60 | 2.21 |
| INT4 | 2 | 0.96 | 1.94 | 2.77 | 2.79 | 2.79 | 2.79 | 2.79 | 3.14 |
| FP4 | 1.75 | 0.95 | 1.94 | 2.84 | 3.12 | 3.12 | 3.12 | 3.12 | 3.15 |
| INT5 | 4 | 0.95 | 1.95 | 2.94 | 3.76 | 3.79 | 3.79 | 3.79 | 4.04 |
| INT6 | 8 | 0.95 | 1.95 | 2.94 | 3.93 | 4.75 | 4.78 | 4.79 | 4.93 |
| FP6 | 2 | 0.95 | 1.95 | 2.94 | 3.92 | 4.80 | 5.12 | 5.12 | 5.12 |
| E4M3 | 120 | 0.95 | 1.95 | 2.94 | 3.93 | 4.81 | 5.19 | 5.22 | 5.24 |
| INT7 | 16 | 0.95 | 1.95 | 2.94 | 3.93 | 4.90 | 5.69 | 5.77 | 5.83 |
| INT8 | 32 | 0.95 | 1.95 | 2.94 | 3.93 | 4.91 | 5.77 | 6.73 | 6.73 |
| E2M5 | 2 | 0.95 | 1.95 | 2.94 | 3.93 | 4.91 | 5.80 | 6.99 | 7.08 |
| BF16 | 1 | 0.95 | 1.95 | 2.94 | 3.93 | 4.92 | 5.86 | 9.23 | 9.23 |
| FP16 | 1 | 0.95 | 1.95 | 2.94 | 3.93 | 4.92 | 5.87 | 12.23 | 12.23 |
Table 17.
Three observations. First, the rule of thumb is integer bits: INT4 saturates beyond , INT5 beyond , INT6 beyond . 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 and 0.34 at , and E2M5, whose 253 values keep all 127 codepoints distinct for , stays within 0.07 bits of FP16 everywhere, while E4M3’s coarse mantissa caps it at 5.19 at . Third, wherever a type saturates, the CPTC rows flatten at the type’s own scalar quality (the “at column): the coder degenerates to the format it stores. The design guidance: E2M5 is the right default for the full range; a platform without it can default to INT8, which matches E2M5 up to and costs 0.03 bits at (other targets in Table 16); INT6 or FP6 are valid cost reductions for , 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- calibrated scale for , and its row repeats Table 2.)
A minimal codebook. The sweep above holds the table-size parameter at and varies only the storage type; the two knobs can be driven down together. Setting gives a codebook of codepoints, and INT() storage offers exactly 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 distinct values, then for every trellis depth , block size , and encoder, the per-sample MSE is at least that of the -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 -point Lloyd–Max codebook minimizes the expectation of exactly that quantity. At the codebook has distinct codepoints, and a symmetric INT() table has representable levels whatever is, in either case one value short of the a rate- 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 and strictly more than 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 runs bit-exactly on the fixed (, ) datapath via the shift ; the row has and needs the wider table of CPTC.
Matmul-aware experiment: methods and per- results
This appendix gives the table design, baselines, scale calibration and per- 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 , the asymptotically optimal scalar quantizer has point density
exhibiting a unimodal-to-bimodal phase transition at . We move each entry of the generated Gaussian table of § 3.3 to the same quantile of the normalized ,
where is the CDF of the normalized , the standard normal CDF and the standard deviation of the decoded values.
Methods. Scalar baselines INT4, FP4, and NF4 use codebooks with a 20-point grid-searched per-matrix scale. MatMul-Opt ([6]) uses a 16-level scalar codebook at -quantile midpoints. CPTC-Gauss is CPTC with the Gaussian-target table; CPTC-MMaware uses at the data-generating (Equation (5)). For matmul-aware methods the codebook is in -space (variance at , at ); the shared scale calibration is described below.
Per- results. Table 19 gives the numbers plotted in Figure 4. At , where degenerates to a Gaussian wider than the source, CPTC-MMaware ties CPTC-Gauss after shared-scale calibration; the matmul-aware codebook pays off from onward, and CPTC-Gauss plateaus around 0.017–0.019 for .
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 , so we calibrate one shared scale per by minimizing matmul Frobenius error over five held-out matrix pairs on a 19-point grid over .
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 : it tracks NF4 at and pulls ahead as grows, with lower error than NF4 by ; for CPTC-MMaware the trellis gain persists on top ( at , at ).
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 () 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). 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 (0.0130, 6.608/8.118 vs. 0.013, 6.61/8.12), with 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 . 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 -means table span 0.006 effective bits. The loading factor matters: at unit scale the QTIP quantizer degrades to 0.0172 at , 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 CPTC at 70B , 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.
| Model | Codebook | seed 0 | seed 1 | seed 2 | mean | range | |
| 8B | QTIP HYB | 4 | 0.01301 | 0.01294 | 0.01324 | 0.01306 | 2.3% |
| 8B | QTIP 1MAD | 4 | 0.01019 | 0.00978 | 0.01004 | 0.01000 | 4.1% |
| 8B | CPTC | 4 | 0.00975 | 0.00958 | 0.00951 | 0.00961 | 2.5% |
| 8B | CPTC | 4 | 0.00955 | 0.00947 | 0.00950 | 0.00951 | 0.8% |
| 8B | QTIP HYB | 3 | 0.04520 | 0.04509 | 0.04486 | 0.04505 | 0.8% |
| 8B | QTIP 1MAD | 3 | 0.04047 | 0.04092 | 0.04010 | 0.04050 | 2.0% |
| 8B | CPTC | 3 | 0.03953 | 0.03996 | 0.03920 | 0.03956 | 1.9% |
| 8B | CPTC | 3 | 0.03822 | 0.03912 | 0.03863 | 0.03866 | 2.3% |
| 8B | QTIP HYB | 2 | 0.24026 | 0.24487 | 0.24209 | 0.24241 | 1.9% |
| 8B | QTIP 1MAD | 2 | 0.23204 | 0.22568 | 0.22348 | 0.22707 | 3.8% |
| 8B | CPTC | 2 | 0.22073 | 0.22044 | 0.22252 | 0.22123 | 0.9% |
| 8B | CPTC | 2 | 0.21820 | 0.22043 | 0.22191 | 0.22018 | 1.7% |
| 70B | QTIP 1MAD | 4 | 0.02352 | 0.02404 | 0.02387 | 0.02381 | 2.2% |
| 70B | CPTC | 4 | 0.02264 | 0.02255 | 0.02224 | 0.02248 | 1.8% |
| 70B | CPTC | 4 | 0.02265 | 0.02272 | 0.02265 | 0.02267 | 0.3% |
| 70B | QTIP 1MAD | 3 | 0.08818 | 0.08719 | 0.08744 | 0.08760 | 1.1% |
| 70B | CPTC | 3 | 0.08449 | 0.08706 | 0.08518 | 0.08558 | 3.0% |
| 70B | CPTC | 3 | 0.08381 | 0.08496 | 0.08481 | 0.08453 | 1.4% |
| 70B | QTIP 1MAD | 2 | 0.32468 | 0.32101 | 0.32053 | 0.32207 | 1.3% |
| 70B | CPTC | 2 | 0.31241 | 0.31374 | 0.31727 | 0.31447 | 1.5% |
| 70B | CPTC | 2 | 0.31936 | 0.31884 | 0.31453 | 0.31758 | 1.5% |
Table 20.
| Rounding | CPTC | HYB | CPTC advantage |
| RTN | 0.03363 | 0.05334 | −37% |
| YAQA-B | 0.00967 | 0.01720 | −44% |
| YAQA gain | 3.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 margin at 8B is 8.6/12.1/26.9% at , 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 CPTC). At (single runs, seed 0) quantization is nearly free and the ordering holds: at 8B CPTC 0.0031 (perplexity 6.516 vs. 6.502), CPTC 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, CPTC 0.0069 and 1MAD 0.0070. The arm, whose 63 FP16 codepoints make the GPU kernel’s table gather bank-conflict-free (Appendix § 14.§ 1), costs at most 0.001 at 8B (0.0001 at ), costs 0.001 at 70B , and beats the full table at 70B (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 and drops together at (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 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 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 , nine cells per model (the CPTC arm lies within 0.007 KL of CPTC on seed 0 and is omitted for legibility), a quadratic least-squares fit of against has 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 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 , 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: CPTC has the lower KL at 70B for (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 and INT6’s cost (at most 0.01 bits) move KL by about 1%. values are the Gaussian measurements; KL values are the seed-0 runs of Table 4.
Trellis-depth sweep. Varying at fixed moves a single codebook along the same law. We quantized Llama 3.1 8B with CPTC at every from to 16 for (per- 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 it falls from 0.047 (, 2.80 effective bits) to 0.00955 (, 3.93); at from 0.169 (, 2.16) to 0.038; at from 0.78 (, 1.48) to 0.218. The cells use the conditional-mean fill of Equation (2) rather than a Lloyd–Max table, which is why , sits below INT4; the exact scalar reproduction of § 3.4 needs the scalar codebook loaded. Figure 1b plots the 38 cells with (all but at ): against has Spearman and a uniformly weighted slope of (); per rate the slope over is at , at and at , 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 at every rate (0.0563/0.1060/0.2630 vs. 0.0719/0.1175/0.3063 at ) and C4 perplexity at and , tying at (6.8171 vs. 6.8165); at (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 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 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 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 takes its Wikitext-2 perplexity from 7.685 at to a minimum of 7.440 at , which reproduces CPTC’s score of 7.447 with no quantization, while the best temperature for C4 () 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 , 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 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 ( columns), the regime weight-only quantization is for. Each warp decodes a 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 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- atomics; only the final store narrows.
The INT4 baseline. Speedup over cuBLAS FP16 conflates two effects: moving 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 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 decoder of Algorithm 1 with the table. State table indexes a -entry table by the state itself; it is the small- design point of § 6.3 (3.84 effective bits at ), not the 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 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 ).
| GPU | Decode | stack (ms) | vs. cuBLAS | saturated (s) | ceil |
| L40S (Ada) | cuBLAS FP16 | 19.08 | — | 2,595 | 0.959 |
| two multiplies | 5.24 | 3.64 | 626 | 0.993 | |
| INT4 baseline | 5.12 | 3.73 | 623 | 0.998 | |
| QTIP HYB kernel | 5.8 | 3.3 | — | — | |
| two multiplies, unfused | 5.35 / 5.84 | 3.57 | — | — | |
| H100 (Hopper) | cuBLAS FP16 | 5.51 | — | 657 | 1.011 |
| two multiplies | 3.40 | 1.62 | 330 | 0.504 | |
| state table | 2.67 | 2.06 | 219 | 0.759 | |
| INT4 baseline | 2.11 | 2.61 | 159 | 1.048 | |
| QTIP HYB kernel | 3.2 | 1.7 | — | — | |
| two multiplies, unfused | 3.54 / 4.31 | 1.56 | — | — | |
| state table, unfused | 2.85 / 3.65 | 1.93 | — | — |
Table 23. Decode fused into the tensor-core GEMM at batch 1 (, , the 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,3764,096 matrix large enough that cuBLAS itself is bandwidth-bound; “ 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. QTIP’s released HYB kernel at on the seven unfused per-projection shapes, timed as its own harness does, kernel time only. CPTC on those same shapes, kernel-only / with the output-zeroing launch; speedup from the kernel-only time. Speedups of the and 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 , 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 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- 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 HYB’s speed and the state table at 1.12 (0.74 and 0.88 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 , for the E2M5 and the INT8 table types and for both table configurations ( with the mirror fold, and the , 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 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). 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 ; the standalone rates of Table 24 also pay a natural-order permute and a store per value) and puts and out of reach of the memory roof on that machine.
| Kernel | CPU | FP16 out fold | FP16 out | INT8 out fold | INT8 out |
| AVX-512 | Zen 4 | 15.0 | 24.4 | 20.1 | 25.3 |
| AVX2 | Zen 4 | 2.8 | 3.1 | 4.1 | 4.7 |
| AVX2 | Zen 3 | 2.4 | 2.7 | 3.7 | 4.1 |
| NEON | Graviton5 | 3.9 | 5.0 | 5.1 | 6.8 |
| INT4 unpack (FP16 out), AVX-512 / AVX2 | Zen 4 | 47 / 29 | |||
| INT4 unpack (FP16 out), NEON | Graviton5 | 23 |
Table 24. Single-core decode throughput on CPUs (, billions of values per second) from an L2-resident stream of values at , , best of 100–200 runs (other at 0.97–1.04 these rates on x86 and 0.87–1.00 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 ( 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 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 and the stream is 0.75 and 0.50 as long and the time falls to 0.83 and 0.60 the time, against 0.75 and 0.50 for a purely bandwidth-bound format: the decode is partly exposed at (233 of the 270 GB/s roof) and more so at (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 the picture is the same: CPTC reaches 0.97 the INT4 bandwidth and takes the same time at batch 1 (8.9 vs. 8.6 ms). At and 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: finishes in the INT4 time and runs at 0.91 its speed, rather than faster. With the mirror-folded table, the accelerator’s format, the stack takes 14.1 ms on Zen 4 and 11.1 ms on Graviton5, 0.94 and 0.78 the INT4 speed.
| Weights | bits | ms | GB/s |
| Zen 4, 64 cores (AVX-512, VNNI) | |||
| FP16 | 16 | 51.9 | 269 |
| INT8, VNNI | 8 | 25.8 | 271 |
| INT4 unpack, VNNI | 4 | 13.3 | 262 |
| CPTC | 6 | 19.9 | 263 |
| CPTC | 4 | 13.6 | 257 |
| CPTC | 3 | 11.3 | 233 |
| CPTC | 2 | 8.1 | 217 |
| Graviton5, one 96-core node (NEON, SDOT) | |||
| FP16 | 16 | 36.0 | 388 |
| INT8, SDOT | 8 | 17.5 | 399 |
| INT4 unpack, SDOT | 4 | 8.6 | 405 |
| CPTC | 6 | 13.8 | 379 |
| CPTC | 4 | 8.9 | 391 |
| CPTC | 3 | 9.5 | 275 |
| CPTC | 2 | 8.4 | 208 |
Table 25. Time to stream the weights of a 32-layer Llama 3.1 8B forward pass (ms, ) 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 () 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 -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 (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.
| 1 | 2 | 3 | 4 | 5 | 6 | |
| 10 | 2,960 (114×) | 3,539 (60×) | 3,381 (35×) | 3,253 (33×) | 3,526 (37×) | 3,666 (37×) |
| 11 | 1,642 (127×) | 1,864 (62×) | 2,002 (46×) | 1,935 (43×) | 1,985 (44×) | 2,080 (46×) |
| 12 | 864 (133×) | 992 (66×) | 1,020 (45×) | 1,100 (49×) | 1,149 (50×) | 1,098 (47×) |
| 13 | 436 (134×) | 505 (67×) | 528 (45×) | 562 (49×) | 579 (48×) | 570 (48×) |
| 14 | 218 (134×) | 244 (65×) | 255 (44×) | 276 (48×) | 277 (47×) | 263 (44×) |
| 15 | 84 (103×) | 105 (56×) | 116 (38×) | 127 (44×) | 133 (45×) | 131 (43×) |
| 16 | 32 (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 (, values, median of 5; reference: median of 3), with the speedup over the torch.compile reference of Listing 1 in parentheses. Work grows as ; the 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 with the decode map of Algorithm 1, and emits the per-value codes . Launched as framework-level tensor operations (Listing 1 under torch.compile) the recursion is latency-bound: each of the trellis steps and 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 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 the -bit predecessor indices pack per byte; the first steps of the first forward pass skip the backpointer store, which the half backtrace never reads; and at small the kernel packs several independent blocks per program.
Table 26 reports the full throughput matrix on an NVIDIA L40S at : 33–134 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 and at ) and moves the MSE by at most 0.02% (, , both encoding the same FP16 input). At the main design point (, ) it sustains 60 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 ). The kernel is compute-limited: an Nsight Compute profile at , 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 (, , i.e. its 16 16 tiles), standard-normal values, median of 5 runs: 0.76 million values/s for 1MAD, 0.77 for 3INST and 1.5 for HYB, whose pairs halve the trellis steps. Our fused encoder at runs 59 million values/s at , 1,819 at and 3,110 at . By Table 11, CPTC at scores 3.865 effective bits against 1MAD’s 3.864 at (CPTC : 3.934). Encoding at equal quality is therefore about 2,400× faster than QTIP’s shipped encoder: 32× less work from running instead of , which is method-level, and the remaining 75× from the fused kernel (78× when both encoders run at ), 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 in a cycle-level simulation of the pre-silicon design. These simulated per-chip rates () are a reference point, not a comparison with the measured per-GPU rates of Table 26 ().
References
- [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]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]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]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]John B. Anderson and Tomas Eriksson. Trellis source codes based on linear congruential recursions. IEEE Communications Letters, 9(3):198–200, 2005.DOI
- [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
- [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]Toby Berger. Rate Distortion Theory: A Mathematical Basis for Data Compression. Prentice-Hall, 1971.
- [10]Richard E. Blahut. Computation of channel capacity and rate-distortion functions. IEEE Transactions on Information Theory, 18(4):460–473, 1972.DOI
- [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]John H. Conway and Neil J. A. Sloane. Sphere Packings, Lattices and Groups. Springer, third edition, 1999.
- [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
- [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
- [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
- [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
- [18]Allen Gersho. Asymptotically optimal block quantization. IEEE Transactions on Information Theory, 25 (4):373–380, 1979.DOI
- [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.
- [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
- [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
- [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
- [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
- [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
- [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
- [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
- [27]Joel Max. Quantizing for minimum distortion. IRE Transactions on Information Theory, 6(1):7–12, 1960.DOI
- [28]Saralees Nadarajah. A generalized normal distribution. Journal of Applied Statistics, 32(7):685–694, 2005. doi: 10.1080/02664760500079464.DOI
- [29]NVIDIA. CUDA Toolkit 13.4 release notes. https://docs.nvidia.com/cuda/archive/13.4.1/cuda-toolkit-release-notes/index.html, 2026a.
- [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
- [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
- [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
- [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
- [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
- [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
- [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
- [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
- [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.




