XOR-Trellis — Trellis-coded quantization vs VQ codebooks — What does it mean?

The news. On September 30, 2026, researchers at Arm posted XOR-Trellis: Ultra-Low-Complexity Dequantization and Curvature-Aware Hadamard-Free LLM Quantization (arXiv 2610.00432). It makes two changes to trellis-coded weight quantization. First, a decoder built from a few XOR gates and a 4×4 table of FP4 values, cheap enough to replicate at 512 weights per cycle. Second, a path search that weighs each rounding error by how sensitive the model is to it, which lets the method skip the Hadamard rotation that the earlier QTIP method relies on. On Llama-3.1-8B, at about 2.25 bits per weight with no fine-tuning, the rotation-free version reaches a WikiText-2 perplexity of 8.06 with curvature-weighted search alone and 8.00 with an extra reordering step the paper calls energy ordering, against 8.48 for QTIP with rotation. Read the paper →

Directions, not an atlas

Picture telling a friend how to walk a hillside so they stand at a list of target heights, one after another. You could hand them a printed atlas listing every possible route — complete, but absurdly large. Or you could give turn-by-turn directions: at each junction, just say which of four forks to take. The trick that makes short directions powerful is that the four forks on offer depend on the last few turns already taken, so a 2-bit instruction at each step still reaches an enormous variety of routes.

That is the gap between vector quantization and the newer methods. A VQ codebook is the atlas: to quantize a vector of weights jointly, it stores a list of whole reconstruction vectors, and at a fixed number of bits per weight that list grows exponentially as the vector gets longer. Trellis-coded quantization is the directions. Each weight stores a 2-bit branch. The decoder keeps a 16-bit state — 14 bits of recent branch history plus the current branch — and each new branch slides into the history while the oldest bits fall out. The state decides which four values the current branch can choose between.

Because the search runs once, offline, the expensive part — planning the route — is never paid at inference. When the model is quantized, the Viterbi algorithm steps through the state machine keeping only the cheapest partial route into each state, and ends with the code sequence whose decoded values land closest to the targets (the weights after the quantizer's own error-feedback adjustment, called LDLQ). At inference time the reader only follows the directions.

The sign at each junction has to be cheap

Directions only help if reading each sign is quick. During decoding, a large model is often memory-bandwidth-bound: each decoding step streams the weights from memory, so shrinking weights from 16 bits to about 2 cuts the bytes moved. But the saving only shows up if dequantization keeps pace with how fast the chip consumes weights — otherwise the arithmetic of rebuilding each weight becomes the new bottleneck. The paper estimates that QTIP's computed decoder, called 3INST, needs about twelve 32-bit add/subtract operations, an additional 32-bit addition, mask and XOR logic and an FP16 addition per weight: roughly 3–5k small logic-gate equivalents.

XOR-Trellis replaces that arithmetic with a lookup that is almost free. Four masked parity functions each XOR together a fixed subset of the 14 history bits. Two of the resulting bits pick one of four palettes; the other two shuffle which branch maps to which palette entry. The palettes hold FP4 values: [-6, -1.5, 0, 2], [-4, -1, 0.5, 3], [-3, -0.5, 1, 4] and [-2, 0, 1.5, 6]. Every palette offers four distinct values at least 1.5 apart, so no fork is wasted — a palette like [-2, -2, 2, 2] would offer four forks but only two destinations. The whole mapping needs about 14 two-input XOR gates plus the 16-entry table, and the paper reports a 512-weights-per-cycle decoder synthesized in 1,917 µm² of a 3 nm-class (N3P) process.

Cliff edges: weighting errors instead of rotating them

Now suppose some stretches of the hillside run along a cliff edge, where a small misstep costs far more than the same misstep in a meadow. Plain Viterbi search scores every misstep the same way — squared distance from the target — so it happily lands a little off on a cliff edge to stay exact in a meadow. In model terms, the cliffs are high-curvature directions of the Hessian: equal-sized rounding errors can have very different effects on the output.

QTIP's answer is the randomized Hadamard transform, which mixes coordinates so sensitivity is spread more evenly; the authors' hypothesis is that this is why equal scoring works well enough once the weights are rotated. It also tames outlier weights, but a rotation that cannot be folded into the neighbouring layers adds work on every inference. XOR-Trellis keeps the original coordinates and makes the search itself cliff-aware. The LDL factorization the quantizer already computes exposes a diagonal D that says how costly the leftover error in each weight is, and Viterbi now multiplies each step's squared error by that weight's D. If two errors are both 0.1 but one weight's D is eight times the other's, the first now costs eight times as much, so the search spends its limited choices protecting it. The state machine, the stored codes and the decoder are unchanged; only the offline search changes.

Where the bits and the bandwidth go

Hold the budget at 2 bits per weight and ask what a full VQ codebook would need (illustrative arithmetic, not from the paper). For vectors of 8 weights it needs 2^2×8 = 65,536 entries — storable. For vectors of 256 weights it needs 2⁵¹² entries — no memory could hold that. The trellis never builds that table: its 16-bit state also has 65,536 possible values, but the decoder computes each one from about 14 XOR gates instead of storing it. The paper's ~2.25 bits per weight is those 2 bits of path plus one shared scale per group of 32 weights, which adds 0.25 bits per weight (an 8-bit scale ÷ 32). Now the bandwidth, as an illustration that ignores layers kept at higher precision: 8 billion weights in BF16 are 16 GB read per decoded token; at 2.25 bits they are 8 × 10⁹ × 2.25 ÷ 8 ≈ 2.25 GB, about 7× less traffic (illustrative). Those 7× fewer bytes become faster tokens only if the decoder rebuilds weights as fast as the chip consumes them — the whole case for a 14-gate decoder.

What the paper does not show yet

The results are perplexity and zero-shot accuracy at about 2.25 bits per weight, all without fine-tuning; the paper reports gate counts and silicon area for the decoder, not end-to-end tokens per second on a real model. Only the FP4 palettes are evaluated, with FP8 mentioned as preliminary. And the curvature weighting is not a universal upgrade: with the Hadamard rotation still in place, the paper's experiments favor plain Viterbi scoring, which the authors read as the rotation having already evened out the slopes. The D-weighting is a replacement for the rotation, not an addition to it.

Goes deeper in: LLM Internals → Quantization → Modern Methods

Related explainers

• KVarN squeezes the KV cache to 2 bits — Hadamard rotation — the rotation XOR-Trellis removes, applied to the KV cache instead of weights
• Nemotron-H 8B pretrains in FP4 with no Hadamard transform — UE5M3 block scaling — another route to FP4 without rotation, at training time
• Pretrained LLMs resist 4-bit quantization — Counteracting quantization error — why error feedback in post-training quantization works at all