QTIP: Quantization with Trellises and Incoherence Processing

In general, reducing the size of the uncompressed codebook reduces the cost of lookup. QuIP# is forced to use a battery of bit manipulation operations (amortized to 3 per weight) to compress its 65536-entry V=8 codebook down to a 256*32-bit LUT. Due to the trellis-based quantization algorithm, QTIP HYB requires a much smaller uncompressed codebook (1024 entries at V=2) to achieve better accuracy. We decompress this from a 512 * 32-bit LUT in only 0.5 integer ALU instructions per weight, versus QuIP# which requires 3. QTIP HYB has an additional cost of ~1.5 integer ALU ops to unpack the trellis and calculate the codebook index, which comes out to a total of 2 ALU ops per loaded weight. At 2 bits, this is 8 ALU ops per loaded byte. On the flip side, QTIP at V=2 requires 4x more codebook lookups than QuIP# at V=8. The effect of these differences on inference speed depends on the details of the specific target microarchitecture.

Essentially,

• QTIP reduces the necessary uncompressed codebook size, which reduces the necessary runtime resources (smaller LUT hardware or fewer ALU ops: 0.5 ALU ops for HYB vs 3 for QuIP# E8P).
• QTIP HYB requires 1.5 ALU ops per weight to unpack and map trellis entries to codebook indices.
• QTIP HYB requires more lookups per weight than QuIP#. This is fine on modern GPUs, which have fast banked shared memory. On other architectures, performance will depend on the SIMD shuffle or L1 cache throughput. However, QTIP can be done without any lookups at all (e.g. 3INST and 1MAD) while QuIP# cannot.
• The decompress overhead is essentially constant for all bit widths for QTIP. VQ costs more as bit width increases.
• QTIP 3INST and 1MAD require a fixed number of ALU instructions to decode, and do not use a LUT, reducing cache considerations.

where “ALU ops” here refers to INT32 ALU ops.

Openreview is not letting me make a comment to the rebuttal, so you are going to see this before the rebuttal. Please read the rebuttal first before reading this.

QTIP’s significance (W1)

Tables 3 and 4 show QTIP’s strengths. Table 3 indicates that QTIP w/out fine-tuning consistently beats VQ-based approaches w/ fine-tuning, showing that there is significant value in better quantizers. QTIP also succeeds where fine-tuning “fails.” Fine-tuning does not reliably improve QuIP# at 4 bits, but QTIP consistently outperforms QuIP# there. This is even more impressive since 4 bit QuIP# is almost lossless. Table 4 shows that even after fine-tuning, QTIP still consistently improves over QuIP#. At all bitrates, QTIP can reduce QuIP#’s perplexity gap by >25%, an impressive feat.

Inference speed analysis (W2)

Decoding QuIP#’s E8P takes roughly 3 instructions per weight. This is similar to QTIP’s codes. However, E8P reads 8 weights at once while QTIP reads fewer (2 for HYB, none for 3INST/1MAD). The achievable decoding speed for both methods is dependent on hardware properties (see comments for more details). However, QTIP’s strength lies in its flexibility. The general QTIP framework just requires efficiently generating a pseudorandom Gaussian. The paper gives 3 very different code constructions as examples, two of which don’t even require lookups. In contrast, E8P is very rigid and specially constructed. QuIP# wouldn’t work on devices with little cache, and still scales exponentially w.r.t. dimension and bitrate. For example, even a 3 bit codebook using E8P’s construction wouldn’t fit in cache on modern GPUs. QuIP# uses residual quantization to scale, but RQ is suboptimal vs. a single quantizer.

Other hardware (e.g. ARM) (W3)

Different hardware has different properties and instructions, but we believe that QTIP can be fast on a broad class of accelerators due to its flexibility. QTIP only requires generating a pseudorandom Gaussian efficiently, and can work on devices with no cache as well as devices with lookup hardware. The paper mainly targets Nvidia GPUs due to their popularity. That said, we answer this question from two perspectives:

Can look-up instructions replace TCQ? Generally no, if you want the same quantized model quality. The look-up instructions in most architectures are limited. For example, ARMv8 NEON’s vqtbl4q_u8 intrinsic looks up 16 idxs in a 64-entry codebook. QuIP#’s E8P has 256 8D entries. We know that QTIP outperforms QuIP#, and vqtbl4q_u8 can’t even handle QuIP#. Reducing codebook size would reduce quality, so only using look-up instructions aren’t enough for QTIP’s quality.

Can look-up instructions work with TCQ? Yes, this is essentially the HYB code. In the ARM example, we can use a 6 bit 1D codebook with HYB (Q=6, V=1). Quantizing Llama 2 7B to 2 bits with this setup and w/out fine-tuning gives 6.89 Wikitext2 perplexity – essentially the same as 3INST. We could implement this by packing the 6 bit codebook into registers and using vqtbl4q_u8.

Editorial Notes

[5] To the best of our knowledge, AQLM and QuIP# are the highest quality LLM PTQ methods currently available. Both perform vector quantization. [24-32] K is the bitrate; we will fix this.

L24-32, exponential space and time (Q1)

We’re not sure what you mean here. VQ with an unstructured codebook takes $O(2^{kd}d)$ space and time since closest vector search is NP-hard (https://cseweb.ucsd.edu/~daniele/papers/CVPP.pdf). “Exponential” refers to how the space and time complexity of VQ scale with dim and bitrate, not whether it is possible to perform VQ fast. In practice, people do use structured codebooks to reduce cost by a constant factor. This is what QuIP# uses to do 8D VQ for roughly the cost of 4D VQ (256X reduction). However, this doesn’t solve exponential scaling – it just makes VQ cheaper.

L116, discussion on structured search (Q2)

Searching over an unstructured k bit T dim codebook requires $O(2^{kT})$ time. You’re right that adding structure can make this tractable. For example, product quantization (PQ) with a group size of g makes the codebook the outer product of a g-dim codebook, reducing the runtime to $O(T2^{kg}/g)$. However, this is no longer simply VQ. TCQ is another way to add structure by making the codebook entries fixed-length walks on a trellis. The tradeoff to adding structure is increased distortion. The rate-distortion limit lower-bounds the distortion for an unstructured k bit quantizer. Table 1 shows that TCQ gets much closer to this limit than vector/scalar PQ, making it a better way to add structure.

Table 1 (Q3)

Table 1 computes distortion w/out considering speed. Inf-dim VQ would achieve the rate-distortion limit. 8D VQ with E8P is the limit of what we can do for fast inference on current GPUs, so the fact that QTIP can reduce the rate-distortion gap by >2/3 while using fewer resources makes it a much better quantizer.

Figure 2 (Q4)

In the bitshift trellis, the last L-kV bits of a state are the first L-kV bits of the next state, so we only need to store the kV bit “delta” for each entry in the input sequence. 0010110 represents node indices 00, 01, 10, 01, 11, and 10. Your coding scheme stores which edge to take, but would require knowing the graph structure to decode. The bitshift trellis bakes the structure into the numbering scheme, enabling fast decoding. Regarding transitioning to the next value, this is why we want a large trellis (large L) and randomized codebook, since that increases the probability we can transition to arbitrary values. Naive TCQ has exponential space complexity in L, so we need QTIP’s compute-based codes that dissociate L from space to get high quantization quality on today’s hardware.

Why does TCQ work? (Q5)

Mao and Gray’s RPTC paper (https://ieeexplore.ieee.org/document/5895067/) has theory on TCQ. In short, TCQ satisfies the four necessary conditions of an optimal quantizer. Intuitively, TCQ performs better because it is stateful, letting you “switch” between which size $2^{KV}$ part of the larger size $2^L$ space you are searching in at every step.

Some more questions and comments:

Thanks for your explanation on the Trellis decoding - I believe it would also be wise to add this explanation to the paper, as as a layman in the information theoretical source coding field, I did not get it at first.

I am still unclear on what the Lookup-free computed codes actually do. As I understand it, you can take any word, run it through your 1MAD or 3INST algorithm, and out comes the number you decode right? Do they still have anything to do with the trellis coding that you mentioned? Given a weight tensor, how do you actually find which words encode this value the best?

On the discussion of the runtime and it’s exponential time - I believe I understand what you are saying, but I also think it’s a bit unfair. Your introduction essentially reads: There’s these VQ methods, and they are exponential in the dimensionality, our method achieves better scaling in dimensionality, so it’s better…our problem sizes are fixed, we’re compressing a fixed-size network. These compression methods are never used in a method where the exponential scaling in dimensions actually matters. The authors of the other papers find an optimal trade-off in dimensions/num_clusters->codebook size and performance. This is not like a travelling salesman problem where your O() notation actually matters if you want to scale up your problem to larger sizes. The dimensionality is a choice, and the scaling being exponential is not the actual fact that matters. Rather your question is: At the same codebook sizes/decoding time, what is the best packing I can achieve. You claim ‘VQ requires exponential […] which limits its practicality', which I think is too strong. These methods are very practical because they are applied on lower dimensions, and the codebook size is explicitly limited. Given that this argument is so important for your paper, I would take some care :)

For some of the comments I made, I was also secretely asking that they would be addressed in a new revision of the paper, any thoughts on that? ;)

Editorial Note: Even if AQLM and QUIP# are the highest quality LLM PTQ methods currently known to you, it does not mean the field has converged. I don’t believe any model efficiency committee with prominent researchers created a consensus of what is best, and concluded that there is nothing better out there. If anything, it's highly dependent on what's available on the hardware as well.

I guess a final question for me to understand ...

To clarify, these computed codes are not random, they just do a good job of decorrelating the state ID from the computed value. Like your example FP8 casting code, our codes are deterministic in their outputs. The reason why we want a code that appears random is because under the bitshift trellis, random codes are asymptotically optimal as L increases (see the RPTC paper for more details https://ee.stanford.edu/~gray/trellis.pdf). Table 1 in the RPTC paper shows that an optimal code with a small L has higher distortion than a random code with a large L. This means that we should always increase L as much as possible, and our compute-based codes let us do that without impacting decoding speed.

One thing that worries me is that for a low number of bits, your 'approximately Gaussian' doesn't really hold very strongly, and there will be quite some bias in the number format you choose.

In trellis coding, the codebook assigns values to the states (2^L), so the number of representable codebook values is independent of the bitrate K. These codes are approximately Gaussian for large enough L ($\gtrapprox$ 10), and our experiments use L=16. Figure 3 shows the set of representable neighboring values in a bitshift trellis for various codebooks when L = 16. Indeed, 1MAD and 3INST give very similar coverage as a random Gaussian. Figure 3 also shows why we want a “randomized” codebook. Since neighboring states in the bitshift trellis share L-KV bits, a poorly designed computed code will have strong correlations that result in unrepresentable neighboring values. The leftmost plot in Figure 3 shows such a code, where large portions of the state space are unrepresentable with the bitshift trellis. A code that does direct casting to FP8 (what you suggested above) would have extreme correlations since the mantissa bits of a state become the exponent and sign bits of the next state. Openreview isn’t letting me send an image of the correlation plot, but you can generate a plot with the Python script below to verify for yourself. Section 3.1 in the paper also has more details on random codes.

import torch
import matplotlib.pyplot as plt

L = 8
# bitrate, adjust accordingly. V =1 for plotting purposes.
K = 4

states = torch.arange(1 << (L+K), dtype=torch.int32)

left = (states >> K).to(torch.uint8)
right = (states & ((1 << L) - 1)).to(torch.uint8)

lval = left.view(torch.float8_e5m2).float()
rval = right.view(torch.float8_e5m2).float()

plt.scatter(lval, rval)
plt.show()

On the exponential scaling ...

The focus of the paper is indeed to show that QTIP achieves a better quality/speed tradeoff over existing quantization methods. Our empirical results show that QTIP outperforms VQ-based methods such as QuIP# and AQLM while offering the same fast inference as QuIP#. The section about VQ’s exponential scaling was to explain why we can’t increase the VQ dimension to improve quality while preserving fast inference. We know from information theory that the distortion of a vector quantizer is lower bounded by a strictly decreasing function of the dimension (http://vkostina.caltech.edu/pdfs/2012KostinaVerdu-lossycomp.pdf). This means that for optimal codebooks and a fixed bitrate, the only way to improve VQ’s quality is by increasing the dimension. TCQ lets us achieve lower distortion than the best “fast inference” VQ, which translates into higher quality quantized LLMs. QTIP’s contribution is enabling fast decoding with TCQ so we can quantize LLMs with it while supporting fast inference.

It would be great if you could be a little bit more explicit ...

Most of our responses are based off of information already in the paper. We will make this information more clear in an updated manuscript. We will also add new information from the rebuttal/discussion period, such as those on hardware requirements for QTIP's kernels.

Thank you for your review, we will be sure to clarify how trellis coding works in an updated manuscript. We uploaded a response to F569's latest questions, which you may find useful.

QTIP's contribution (W1)

The focus of QTIP is on what to quantize with (e.g. VQ, TCQ), and not how to quantize (e.g. GPTQ, fine-tuning). Choosing a good quantizer is hard since LLM weight matrices have outliers and small-batch LLM inference is memory bound, necessitating fast decoding. While the field of signal processing has known for a while that TCQ achieves lower distortion than VQ, there is little to no existing work on designing trellis quantizers for fast parallel decoding. This is the “missing piece of the puzzle” needed to make TCQ work for LLM compression, which QTIP addresses.

Our experiments used QuIP#’s BlockLDLQ framework for two main reasons. First, QuIP# is a state-of-the-art vector quantization framework that supports fast inference, making it a good baseline to show the benefits of TCQ. Second, LDLQ variants are optimal among adaptive rounding methods that use linear feedback from the Hessian. By using BlockLDLQ, we can be reasonably certain that the empirical improvements are from TCQ and not spurious interactions between the quantizer and a subpar rounding algorithm. Finally, we note that QTIP could be used as a drop-in replacement for VQ in other rounding algorithms. QTIP’s orthogonality to the actual rounding method further broadens QTIP’s practicality.

Incoherence Processing (W2)

Both QuIP and QuIP# detail how incoherence processing affects the Hessian and how we can use incoherence to bound the proxy error tr(WHW.T). We refer the reviewer to QuIP and QuIP# to see how incoherence processing can benefit quantization, even when using Hessian information.

QTIP uses the random Hadamard transform (RHT) to perform incoherence processing. The RHT is fully invertible up to numerical error, meaning that the Hessian matrices do not lose information from incoherence processing bar catastrophic imprecision. We ran the quantization algorithm in fp64 and did not observe differences vs. fp32, so numerical error is not a dominating factor in the quantization step.

Cost of Fine-Tuning (W3)

QTIP’s focus is on the quantizer itself and not fine-tuning. Whether the end user chooses to fine-tune or not is a “deployment choice,” and in either case QTIP offers improvements over SOTA vector quantization methods. Table 3 shows that even without any fine-tuning, QTIP usually outperforms SOTA vector quantization based methods that use fine-tuning, meaning that fine-tuning isn't strictly necessary to make QTIP SOTA. Table 4 shows that QTIP still gives significant improvements after fine-tuning. In fact, QTIP holds up where fine-tuning “fails.” QTIP almost halves the 4 bit perplexity gap vs. QuIP#, while fine-tuning has little effect at 4 bits. Finally, since QTIP is orthogonal to fine-tuning, we expect that new fine-tuning algorithms will compose with QTIP to produce even better quantized models.

Implementation Details (W4)

Most of these details, including datasets, are available in the Appendix. We will add additional information in an updated manuscript and the code will be made available at a later date.

Quantization Error (Q1)

Table 1 shows the distortion for an i.i.d. Gaussian sample. If we re-run Table 1 with actual weight matrices and incoherence processing, then we get very similar results since incoherence processing produces approximately i.i.d. Gaussian weights.

However, LLM quantization algorithms usually minimize the expected activation error (proxy error, Eq 1) instead of MSE (Table 1). Using a calibration set of 25 million tokens from RedPajama, scalar quantization achieves a relative error of 0.073, VQ (QuIP# E8P) 0.060, and TCQ (QTIP 3INST) 0.045, when quantizing the 10_down layer of Llama 2 70B to 2 bits without fine-tuning. Like in Table 1, QTIP reduces the proxy error over SQ and VQ.

HYB Uniqueness (Q2)

In our experiments, we use a different codebook per linear layer. Since this codebook is very small (1K entries) relative to the matrix size (>>1M entries), it adds < 0.01 bits per weight. If a per-layer codebook is not possible, a shared codebook should also work fine. 1MAD and 3INST use the same codebook per layer and also achieve SOTA performance. This is due to incoherence processing producing approximately i.i.d Gaussian weights, so the codebooks are all essentially Gaussian.

LLM Quantization Fine-Tuning vs. LoRA-Style Methods (Q3)

To clarify, QTIP’s focus is on the quantizer, not the rounding or fine-tuning algorithm. Table 4 used QuIP#’s tune-as-you-go fine-tuning method. This method, and other similar ones like AQLM’s fine-tuning algorithm, tune the quantized model to recover the original model. In contrast, LoRA and LQ-LoRA are aimed at fine-tuning to new downstream tasks. These are two fundamentally different problems, so it is difficult to compare methods across problem areas. It may be possible to adapt methods to solve both problems, but that is beyond the scope of this work.

A fair comparison would detail the expected activation error ...

The rebuttal does have this information for the 10_down layer of Llama 2 70B (see the paragraph after the table). QTIP achieves a lower proxy error than QuIP (scalar quantization) and QuIP# (vector quantization). We are not familiar with the AQLM codebase so we did not attempt to measure its proxy error. Due to time, we won't be able to get proxy error measurements for all the layers before the end of the discussion period. However, below are proxy errors for layers 39 and 79 of Llama 2 70B for scalar quantization, vector quantization (QuIP#), and trellis quantization (QTIP) when quantized to 2 bits. As expected, QTIP achieves the lowest proxy error in all cases.

Note: there was a bug in the scalar quantization proxy error code in the first version of this response. We have updated the table with the correct results. The SQ proxy error in the original rebuttal was not affected by this bug.

Regarding LQ-LoRA, our understanding is that LQ-LoRA focuses on obtaining a better quantized + low rank initialization for the final goal of downstream fine-tuning to new tasks. Post training quantization methods like QuIP#, AQLM, and QTIP focus on finding a quantized model that is as close to the original model as possible, which is a fundamentally different problem. LQ-LoRA mainly presents results on downstream fine-tuning, where they can get lower perplexity on C4 than even the original unquantized model. This is impressive, but should also make it obvious that LQ-LoRA is solving a different problem than PTQ.

I believe some layers would suffer more from the incoherence processing step; see for e.g. early layers in Fig.1 in [1]

We're not sure what you mean by "suffer more" from incoherence processing. Incoherence processing is a fully invertible transformation up to numerical error. This means that incoherence processing does not result in information loss unless there is catastrophic numerical imprecision. As mentioned in the rebuttal, we did not observe differences from running our experiments in FP32 vs. FP64, so numerical imprecision is not an issue here. If you are questioning the efficacy of incoherence processing in the quantization process, we recommend taking a look at QuIP and QuIP#. Both papers have theory showing that the proxy error can be bounded by the incoherence $\mu$ of the weight matrix when using LDLQ variants. The bound gets tighter as $\mu$ gets smaller, which is what incoherence processing does.

Updated Inference Speeds on More Devices and More Bitrates

Below are throughput numbers for decoding 1024 tokens on the RTX 3090, RTX A6000 Ampere, and RTX 6000 Ada, averaged over 8 runs. The kernels were not re-tuned for each device, so they could be made faster. These numbers were run using an updated inference speed script from the QuIP# codebase that is more accurate than the numbers in the paper. In all cases where the FP16 model fits on the device, QTIP is faster than FP16.

Ablations and fast inference (W1 and W2)

The main components of QTIP that enable fast inference are the bitshift trellis and compute-based codes. To understand why these are necessary, let us look at the L, K, and V parameters in trellis coding. L is the trellis size, K is the bitrate, and V is how many weights we quantize per step. Larger trellises improve quality, and increasing V can increase decoding throughput by amortizing ops. However, a larger V enforces more structure on the search space and may decrease quality. When L = KV, TCQ becomes K bit V dim VQ, bridging the two.

The bitshift trellis lets us avoid storing the trellis, which requires $2^{L+KV}L$ bits ($2^L$ nodes each with $2^{KV}$ edges). The bitshift trellis also enables parallel decoding, which is important since modern accelerators are highly parallel. The compute-based codes dissociate L from the amount of cache needed. While a pure-lookup codebook would take $16 \* 2^L V$ bits of cache, scaling exponentially with L, the compute-based codes use a constant amount or none at all. Note that this means we could have used L > 16 in the paper to achieve higher quality at the cost of encoding time, since L does not affect decoding speed.

Table A shows an ablation on L for quantizing Llama 2 7B with K=2, V=1, the bitshift trellis, a pure-lookup codebook, and no fine-tuning. L=8 is the largest L achievable if we had to store the trellis and codebook in the same amount of cache as the HYB code (2KiB). L=10 is the largest L achievable if we only had to store the codebook. As expected, increasing L improves quality. Table A also shows very little difference between an equal-sized LUT codebook and QTIP’s codes, meaning that QTIP isn't sacrificing quality for speed. However, an equal-sized LUT would need >10X more cache than the latest GPUs have, making the bitshift trellis and compute-based codes necessary to achieve both quality and speed.

Table B shows an ablation on V with L=12 and 16, K=2, and the same settings as Table A. Increasing V generally decreases quality, but this can be recovered with a larger L. It is hard to measure V's impact on decoding speed since this is highly implementation and hardware dependent, so V is more of a user-chosen hyperparameter.

Table A

Table B

Notation (W3)

We will update the camera ready to improve readability.

Performance Gains (W4)

The easiest way to see QTIP’s improvements are at 4 bits and in larger models, where fine-tuning has less impact (Table 3). Tables 3 and 4 show that at 4 bits, all 3 of the QTIP formulations significantly reduce the quantization error over QuIP# and AQLM, which is impressive given how well these methods do at 4 bits. Table 3 also shows that for most model sizes and bitrates, QTIP without fine tuning matches or exceeds QuIP# with fine tuning, showing the importance of using a good quantizer. Finally, these quality gains are essentially “free” over QuIP#, since QTIP offers the same fast inference speeds.

Fine-tuning QTIP (Q1)

Yes, the HYB code has a small codebook that can be fine-tuned. Table 4 uses fine-tuning with the small codebook included in the set of tunable parameters. Tuning the codebook helps slightly, but a better fine-tuning algorithm could probably do better.

Bit Accounting (Q2)

QTIP has two sources of overhead beyond the quantized weights: sign vectors used for the random Hadamard transform (RHT), and the codebook in the HYB code (3INST and 1MAD do not have codebooks). For a nxm matrix, the sign vectors take up (n+m) bits. For the HYB code, the codebook takes up 2^Q x V x 16 bits (see Section 3.1.2 for more details). We used Q=9, but you can go down to Q~6 without noticeable degradation. At Q=9, the codebook uses 2KiB. Amortized over n*m entries, the codebook and sign vectors take up <0.01 additional bits. We will add these details to the appendix.

tK vs Kt (Q3)

tK and Kt = t times K

L125 (Q4)

125 should say $2^L \times 2^{kV}$

Highlighting (Q5)

We will re-highlight the numbers to be more consistent.

AQLM inference speed (Q6)

The QuIP# authors recently released a more accurate generation timing script. We have re-timed all the methods on an RTX 6000 Ada. The numbers below are the average throughput for decoding 1024 tokens over 8 trials; we will update the paper with this.

L70 (O1)

“These methods” refers to those listed on L66-68. We will clarify this.

LCG citation (O2)

We will update the paper with this.

AQLM fine-tuning (O3)

Thank you for pointing this out, we will update the paper with these numbers. We note that this does not change our analysis, which is that QTIP achieves better performance than both QuIP# and AQLM with the same general fine-tuning scheme, while preserving QuIP#'s fast inference.