Pyramid Vector Quantization for LLMs

Authors: Tycho F. A. van der Ouderaa, Maximilian L. Croci, Agrin Hilmkil, James Hensman
Primary area: foundation or frontier models, including LLMs
Keywords: quantization large language model llm pyramid vector quantization pvq

Abstract:
Recent works on compression of large language models (LLM) using quantization considered reparameterizing the architecture such that weights are distributed on the sphere. This demonstratively improves the ability to quantize by increasing the mathematical notion of coherence, resulting in fewer weight outliers without affecting the network output. In this work, we aim to further exploit this spherical geometry of the weights when performing quantization by considering \textit{Pyramid Vector Quantization} (PVQ) for large language models. Arranging points evenly on the sphere is notoriously difficult, especially in high dimensions, and in case approximate solutions exists, representing points explicitly in a codebook is typically not feasible due to its additional memory cost. Instead, PVQ uses a fixed integer lattice on the sphere by projecting points onto the 1-sphere, which allows for efficient encoding and decoding without requiring an explicit codebook in memory. To obtain a practical algorithm, we propose to combine PVQ with scale quantization for which we derive theoretically optimal quantizations, under empirically verified assumptions. Further, we extend pyramid vector quantization to utilise Hessian information to minimize quantization error under expected feature activations, instead of only relying on weight magnitudes. Experimentally, we achieve state-of-the-art quantization performance in terms of bits per weight on various large language models.

Decision: reject
Reviewer scores: 8, 6, 1, 5

Reviews and discussion:
<thread>
creation date:
1729076964073

thread_type:
official_review

<thread_object>
creator: reviewer_t3cg

<content>
summary:
In this paper, the authors propose a new post-training quantization algorithm for the quantization of LLMs.
The key idea is to apply a classic pyramid vector quantization (PVQ).
To validate the efficacy of the proposed method, the authors conduct experiments and provide kernels that allow hardware-accelerated encoding and decoding of PVQ.

strengths:
A classic pyramid vector quantization (PVQ) method is well-combined with conventional tricks (e.g., coherence processing, quantization error compensation, Hessian) for the quantization of LLMs.

weaknesses:
1. The authors need to improve the presentation of this paper. It seems that the authors just employed classic encoding and decoding algorithms in the pyramid vector quantization (PVQ) field. Although it is true, the authors need to explain the intuition and meaning of those algorithms. In the current version, the authors just mentioned that they used classic PVQ algorithms, and their pseudocode is provided in the Appendix. Furthermore, the detailed experimental setup is missing. How did the authors construct a calibration dataset? How many data samples are used for the quantization? What is the test dataset? 

2. The authors claimed that one key benefit of PVQ is that decoding is search-free while conventional vector quantization algorithms rely on look-up-table-based search. However, this claim is not justified. Why is this a benefit? Is the PVQ decoding process faster than look-up-table-based decoding? Also, while the authors analyze the time complexity of PVQ encoding/decoding in Table 5, actual processing time has not been measured, and thus the reviewer cannot judge whether the proposed algorithm is efficient.

3. The most crucial concern is that while the authors consider vector quantization, all the compared algorithms (GPTQ and QuaRot) are uniform quantization methods. It is natural that vector quantization methods exhibit better performance, but uniform quantization methods are much more hardware-friendly. The authors need to compare the proposed method with existing **vector quantization** methods [1, 2, 3, 4, 5].

[1] GPTVQ: The Blessing of Dimensionality for LLM Quantization, arXiv 2024

[2] Extreme Compression of Large Language Models via Additive Quantization, ICML 2024

[3] QuIP#: Even Better LLM Quantization with Hadamard Incoherence and Lattice Codebooks, ICML 2024

[4] QTIP: Quantization with Trellises and Incoherence Processing, arXiv 2024

[5] VPTQ: Extreme Low-bit Vector Post-Training Quantization for Large Language Models, arXiv 2024


---‐--‐-------------------------
It might be my final chance to adjust the score. 

While the authors have mentioned that they achieved similar performance with state-of-the-art methods, I cannot see any results regarding this claim.

Please upload the results about apple-to-apple comparison.

If the authors have uploaded results, I would kindly ask AC to consider my score as 6.

If not, my score is fixed to 5.

Also, while I agree some feedbacks of Reviewer 1xev, I honestly think some comments are very tough to address because the major topic is deep learning, not coding theory.

I hope AC to consider my opinions and other reviewers' comments.

questions:
See the Weaknesses.
</content>
</thread_object>

</thread>
<thread>
creation date:
1729616570359

thread_type:
official_review

<thread_object>
creator: reviewer_1xev

<content>
summary:
The paper proposes a quantization method based on using representative points on a sphere to compress LLM weights and activation. The authors claim that it provides a significant improvement over existing art, and it is "codebook free" and "search free".

strengths:
The idea of using spherical code to compress weight and activation may be worth studying. If it can be shown convincingly that this approach indeed outperforms others, then it can make a worthwhile contribution to the area of LLM quantization/compression.

weaknesses:
I found the paper poorly written, lacking clarity, and missing some important baseline comparisons to be convincing.

1. Quantization can be used for different purposes in LLMs. It is done for compressing LLMs (either for storage and transportation across platforms, or for reducing memory usage by reusing weights), but it can also be done for approximate computation. Depending on the targetted usage scenario, the evaluation needs to be designed more carefully. It was never made clear what scenario this work was aiming at. I assume the authors are targeting LLM compression for storage and transportation across platforms since bits were used in the evaluation. This assumption, however, leads to another issue. In data compression, after quantization, an entropy coding step (e.g. Huffman or LZ) is usually taken. The authors seem to have completely ignored this step. It is not clear to me why this is not considered since it is considered common practice.

2. The claim of codebook-free and search-free are dubious. The authors appear to take the naive lookup table implementation as the literal interpretation of "codebook" and "search". However, a structured set of representation points, like the proposed pyramid vectors, is still a codebook. Some codebooks have more structure than others, for example, the simple scalar-quantizer is very structured, but a randomly generated codebook may be the least structured. Representation points obtained by K-mean are not well-structured, but it can also be forced to take certain structures if needed. "Search-free" is also not an accurate term. Even for a completely unstructured codebook, there are approximation methods to simplify the "search" step, for example, using a sum of component-wise differences as an estimate to prune away most candidates. I found using the claim of advantage ambiguous in terms of these two "codebook-free" and "search-free" 

3. The authors did not compare the approach to standard approaches of "lattice quantization", "lattice quantization+entropy coding", and even "scalar quantization" and "scala quantization+entropy coding". Lattice does not require a lookup table, and has efficient enumeration techniques. In Fig. 3, we see that E_8 lattice is already performing better than the proposed approach. However, the authors did not include E_8 and other lattices in all the other comparisons. In fact, A^*_8 may be even better than E_8 in dimension-8. The lattice-based quantization has been known for over 40 years to perform well, and there are very efficient algorithms that avoid "search". See for example: (a) Conway, John, and Neil Sloane. "Fast quantizing and decoding and algorithms for lattice quantizers and codes." IEEE Transactions on Information Theory 28.2 (1982): 227-232. (b) Conway, J., and N. Sloane. "A fast encoding method for lattice codes and quantizers." IEEE Transactions on Information Theory 29.6 (1983): 820-824. I found the lack of comparison with these well-known techniques unacceptable.

4. Another quantization approach is trellis-based quantization, and it is known to also perform well and reduce computation. The authors should consider providing a comparison. 

5. The paper is quite poorly written. A few extreme examples are as follows 1) There is still an unremoved comment in equation (8). 2) Page 4, below (6), it should be "at most" T<D steps. 3) RTN appears in many figures in Section 3, but was not introduced until Section 4. 4) equation (1) is incorrectly/inaccurately written. H is already the Hessian with the expectation over x, then the last expression in (1) should not need to take expectation over x. 

6. I do not believe the claim of "the only method with non-integer shape bits" holds water. The codebook size is not chosen arbitrarily, since it is determined by N(D,K). Therefore, though the number of bits is not necessarily an integer, the number of codewords can still only take discrete values. 

7. The example given in 3.1 is quite ridiculous. In practice, no one would store a quantization table in this manner. Even for an unstructured codebook, only the representative points will be stored, and then the quantization procedure will find one representative point in the codebook through some algorithm, either more direct or searching.

questions:
1. What is the targetted application?
2. Why is the lattice-based approach not compared carefully?
3. Why is the trellis-based approach not compared?
4. Is scalar quantization compared? Is it significantly worse? How about scalar quantization plus entropy coding?
</content>
</thread_object>

</thread>
<thread>
creation date:
1730620082057

thread_type:
official_review

<thread_object>
creator: reviewer_btwr

<content>
summary:
The paper proposes to use a known vector quantization (VQ) method called Pyramid VQ (PVQ) to compress a large language model (LLM) at the bit level. The goal is to maximize the tradeoff between LLM's performance and the number of bits per weight. 

The paper describes the process of applying PVQ to LLMs, provides performance evaluations and comparisons to other VQ methods, and provides a result about the distribution of a normal random vector projection onto a sphere.

strengths:
The topic of quantizing LLM's is timely and important. Quite a few commercial tools offer bit-level compression of LLMs and it appears that theoretical treatment of the topic is lagging.

Analyzing and discussing PVQ in the context of LLMs are solid contributions because the method is used in some applications. The PVQ description and illustrations are clear and engaging. 

Performance comparison to other methods is generally relevant although I have comments below.

weaknesses:
The discussion concerning the advantages of PVQ over other quantization techniques is misleading because the advantage of an implicit codebook generally exists in all practical VQ techniques.  See standard references in the topic like:

[1] Gray, Robert M., and David L. Neuhoff. "Quantization." IEEE Transactions on Information Theory 44, no. 6 (1998): 2325-2383.

Additionally, there is no discussion on the motivation for using VQ compared to scalar quantization in LLMs. Here I'd expect the authors to mention some property of the distribution of attention weights (say) like dependency that makes VQ particularly effective. Other competing methods such as RTN, QuaRot, and QGPT mentioned in the paper are also not fully explained and it is unclear what are the benefits of the proposed method and whether they can be truly attributed to PVQ or the detailed implementation. The coherence processing is perhaps attractive from a practical perspective but it ``hides'' structure in the signal that is ideally exploited by the compressor (not to be confused with `dithering' in scalar quantization that has a different effect). 

Numerical evaluations are only against three methods. Because encoding and decoding are not straightforward, I believe that you should also compare runtime information. Indeed, one can easily think about an elaborated lossy weight compression procedure that would certainly outperform all methods but spend considerable time for encoding and decoding (again, see discussion in [1]). There is no comparison to the popular scalar quantization methods (such as the one described in https://huggingface.co/docs/bitsandbytes/en/reference/nn/linear4bit), no comparison to the E8 method that the paper references. There is no explanation of what are the zero-shot tasks. PPL values appear small -- perhaps you mean log(PPL)? 

In Section 3.2 the authors say that E8 is a ``state-of-the-art'' method that exploits ``geometric structure''. Both terms in parentheses need explanation. 

The theoretical result (Theorem 1) appears to be a reformulation of well-known properties of the distribution of projection of Gaussian vectors. I've found via a quick search the reference: 
[2] Frankl, Peter, and Hiroshi Maehara. "Some geometric applications of the beta distribution." Annals of the Institute of Statistical Mathematics 42 (1990): 463-474.
which explains the main point and includes references to earlier works. 

For the amplitude ('gain'), the authors first argue that it makes sense to use a scalar quantizer optimized for the Beta distribution (Theorem 1). However, the quantizer they describe is obtained via quantile transform of a Beta-distributed random variable and is not optimal in general. See the discussion about optimal scalar quantization form [1] and from
[3] Lloyd, Stuart. "Least squares quantization in PCM." IEEE Transactions on Information Theory 28, no. 2 (1982): 129-137.

In Section 2.5, it is said the encoder maps a vector to its **closest point** on the pyramid, but the mapping procedure to follow does not necessarily lead to the closest point in the Eecleadian sense.  

In Section 3.1, the fact that decoding is done by an ``algorithm'' is meaningless unless you can say something about the runtime of this algorithm. 


There are several writing issues: 
Unclear what is "infeasibly large". 
The 0.01 in Step 5 is misplaced.
Eq. (8) has a weird text.
Typo in Theorem 1 (s_h should probably be s_g)
PPF in Eq. (10) is undefined.
I suggest the following notational changes: 'gain' -> 'amplitude', 'shape' -> 'direction', 'SNR' -> 'QSNR' (Read: signal to quantization-noise ratio).

questions:
The background and motivation need improvement. First, I suggest motivating VQ over scalar quantization which is already widely used in LLMs. Next, you can make the case that PVQ is an interesting VQ technique: It can be implemented in high-dimension due to an implicit codebook (like some other VQ techniques) and is also used in some applications. It appears to me that PVQ provides useful encoding under an L1 metric, whereas other methods would be better under, say, the more common L2. Analyzing the performance of PVQ may still be a solid contribution, but the discussion must be more comprehensive.  

Please explain more about the E8 method you provided as "state of the art". Can you compare performance to this method?
Please elaborate more on the other competing methods. Could you also show the performance of 4-bit scalar quantization, say using: https://huggingface.co/docs/bitsandbytes/en/reference/nn/linear4bit

It is well known, hence should be mentioned, that in high dimensions the information in the amplitude ('gain') is negligible compared to the information in the direction ('shape'). For example, see
[4] Kipnis, Alon, and Galen Reeves. "Gaussian approximation of quantization error for estimation from compressed data." IEEE Transactions on Information Theory 67, no. 8 (2021): 5562-5579.

The quantizer you used for the vector's magnitude is not optimized for the Beta distribution in any known sense. The authors either implement the optimal quantization method (under, say, mean squared error) or justify their approach.

Concerning Theorem 1, the authors should discuss how their result relates to or builds upon existing works like [2].
</content>
</thread_object>

</thread>
<thread>
creation date:
1730745691860

thread_type:
official_review

<thread_object>
creator: reviewer_8p83

<content>
summary:
The paper addresses the problem of quantization in llms. They introduce PVQ which is a  codebook-free and search-free vector  quantization scheme .

strengths:
-

weaknesses:
-please provide proper  referencing for  “coherence processing” on page 2. 
 - on page 3, the   \hat{W} is not well introduced. how is it differen from W ? also \hat{W} should be bold since it is a matrix.
- move the legend in fig 2
- introduce all sets and params before their first appearance: S_D,k , P_D,K not introduced in  section 2.4. sets are better be  distinguishable from matrices  , you could use  caligraphic S and P for  sets. 

define “G”  in eq 7.  

- scalars better be represented by small letter. W for number of  words can be mistaken with W for weights. 

-please address the following  typos/grammatical errors:

“we achieves”, “

“compared to
compared methods”

“maximised”

“, making use for quantization costly.”

“The table can be precomputed a table of N”

“quantised” in fig 6

“On top” , “ to also quantize gains also enabling”

- this is not undestandable:  “to which we refer for a more detailed description of this for attention and fullyconnected layers found in most” - L1 ball should be $l_1$ - E8 ,RTN are not properly intriduced. 

-Figure 3 seems to be quantization on a Gaussian source not a neural network. provide mean and variance of the distributon of the Gaussian.

questions:
What is the superiority of your  quantization scheme over the renowned  1.58   llm  quatization scheme?
</content>
</thread_object>

</thread>
<thread>
creation date:
1732795087011

thread_type:
official_comment

<thread_object>
creator: authors

<content>
comment:
Dear ACs and Reviewers,

We appreciate the valuable feedback provided by the reviewers. Most concerns raised were related to minor issues in the description of the method, and reviewers largely recognized our work as an important contribution.

In particular, we thank Reviewer 8P83 for scoring the paper an 8 and Reviewer BTWr for their extensive review and insightful comments.

However, we do not fully understand why Reviewers 'T3cg' and '1xev' assigned scores of 3 to the paper. The sole reason for their rejection appears to be the lack of comparisons with Quip# [1] and QTIP [2], two vector quantization methods that do not account for activation quantization. For weight-only quantization, we were able to provide a comparison during the rebuttal period (see our comments). Although, for reasons outlined in the same comment, this is not a perfect apples-to-apples comparison, it provides sufficient evidence to show that our method achieves comparable performance at 3-4 bits per weight.

We are making every effort to conduct a more precise comparison for inclusion in the paper. However, this has proven more challenging than initially anticipated due to specific issues with Hugging Face versions and the particular choices of models and calibration datasets used in [1, 2]. Despite this, we believe that even without such a comparison, our paper presents strong evidence of outperforming the most relevant state-of-the-art quantization methods.

Furthermore, while our method surpasses most existing methods for weight-only quantization, achieving the best results in this regime is not the sole focus of our work. Our approach, motivated by recent insights into the spherical geometry of LLM weights, provides a significant step forward toward the quantization of both weights and activations, particularly because of the implicit-codebook and being search-free. We are confident that our work represents an important and meaningful contribution to the machine learning community.

Kind regards,

The Authors


[1] Tseng, Albert, et al. "Quip#: Even better LLM quantization with hadamard incoherence and lattice codebooks." arXiv preprint arXiv:2402.04396 (2024).

[2] Tseng, Albert, et al. "QTIP: Quantization with Trellises and Incoherence Processing." arXiv preprint arXiv:2406.11235 (2024).
</content>
</thread_object>

</thread>
<thread>
creation date:
1733221903827

thread_type:
official_comment

<thread_object>
creator: authors

<content>
comment:
Dear ACs and reviewers, 

We sincerely appreciate the valuable feedback provided by the reviewers. Most concerns raised were related to minor issues in the description of the method, and reviewers largely recognized our work as an important contribution to the field.

In light of this, we were surprised by reviewer 1xev’s decision to lower their score to a 1, whilst other other reviewers provided positive evaluations and appeared largely satisfied with our responses. Notably, reviewer BTWr increased their score from a 5 to a 6, and another reviewer 8P83 maintained their score of 8. Reviewer T3cg rated our work with a 3, primarily due to the lack of comparisons with recent vector quantization methods. To address this concern, we provided a comparison with Quip# and QTIP. While the initial comparison was not entirely apples-to-apples, we can share that we have since repeated the experiment using the same Llama 3 model and the RedPajama dataset and obtained similar results. The updated results remain similar at 3–4 bits, though our method did not outperform QTIP, which achieved a superior average downstream performance (0.70 > 0.68 at 4 bits).

It is worth emphasizing that QTIP is a highly state-of-the-art method; however, it is designed exclusively for weight-only quantization, whereas our method supports the quantization of both weights and activations.

In line with the reviewer guidelines, we hope that not achieving state-of-the-art performance compared to recent vector quantization methods in their specialized domain (i.e., weight-only quantization) will not constitute grounds for rejection. Importantly, these vector quantization methods do not address the quantization of weights and activations together—a key capability of our approach. Our proposed PVQ method encodes vectors of weights and/or activations into integers, enabling matrix multiplication (matmul) operations that operate on integers. This facilitates efficient quantization and reduces the memory required to store model weights and activations during forward-pass computation, all while demonstrably maintaining high performance in terms of perplexity and downstream task performance. This feature is highly relevant from a practical perspective and, to the best of our knowledge, has not been demonstrated before.

We would like to thank the reviewers once again for their constructive feedback.

We think that overall our main contributions are:
- Considering quantization of LLM weights using a spherical code, motivated by recent insights into the spherical distribution of LLM weights.
- Adapting PVQ, a well-known compression algorithm, to the context of LLM quantization and extending it with coherence processing, Hessian-based corrections, and our proposed scale quantization.
- Providing both theoretical and empirical evidence on the distribution of grouped normalized rotated weights.
- Undertaking significant engineering efforts to enable efficient parallel implementation of PVQ with CUDA/C++ hardware acceleration, including improvements in the algorithmic complexity of PVQ subroutines and a custom implementation of arbitrary precision integer arithmetic in CUDA.
- Demonstrately providing a highly performant quantization method applicable to both weights and activations.

and believe that considering this format makes an interesting contribution to the field of quantization.
</content>
</thread_object>

</thread>


Metareview:
metareview:
**Summary:**
This paper proposes application of pyramid vector quantization (PVQ) to compression of weights and activations in large language models (LLMs).

**Strengths:**
This paper discusses an important and timely subject of compressing LLMs, and the proposal based on PVQ is interesting.

**Weaknesses:**
- Most reviewers criticized lack of comparison of the proposal with existing vector quantization methods.
- Most reviewers evaluated quality of the presentation of this paper, in its current form, negatively. 

**Reasons:**
Besides the lack of comparison with existing vector quantization methods, I am concerned the most with the quality of the presentation, which would require much more careful proofreading to have the manuscript to get accepted. Below is a relatively long list of points which I think would require revision.

Additional points:
- Page 1, line 22: we achieve(s); (p → P)areto-optimal
- Page 1, lines 23-4: compared to (compared) methods
- Page 1, line 38: has been (been)
- Page 2, lines 4, 45-6; page 3, line 10: pyramid vector quantization → PVQ
- Page 2, line 8: in (a) some chosen
- Page 2, lines 7-9: While the authors argue quantization of weights $W$ and activations $x$, they only introduce $\hat{W}$ and not $\hat{x}$.
- Page 2, line 9: A common conve(rs → nt)ion
- Page 2, line 12: The expectation $\mathbb{E}_{x}[xx^T]$ should never be equal to the empirical mean. One would also need the prefactor $1/N$.
- Page 2, line 14: the (layer-wise output → output error?) at each layer
- Page 2, line 17: "Equation" can be removed.
- Page 2, line 26: higher (number of) dimensions
- Page 2, line 36: "shape" might be better termed as "direction".
- Page 2, lines 38-9: (Kosson et al., 2023) → Kosson et al. (2023)
- Page 2, line 43: that reparameterize(s)
- Page 3, line 2: Chee et al. (2024) → (Chee et al., 2024)
- Page 3, lines 3, 5: The formulas $W=UWV$ and $\hat{W}=V^T\hat{W}U^T$ do not make sense.
- Page 4, line 6: To quantiz(ing → e)
- Page 4, line 14: sum to (1 → $K$)
- Page 4, line 17: $c\in[1,\ldots,N(D,K)-1]$ → $c\in[1,N(D,K)]$
- Page 4, line 25: that allow(s)
- Page 4, line 27: $C_{2,7}=[0,27]$ → $C_{2,7}=[1,28]$; Figure 2 should be corrected accordingly.
- Page 4, lines 27-30: I did not understand the sentence "The table can be precomputed a table ...". It might have been meant "The table of $N(d,k)$ for ... can be precomputed and reused ...".
- Page 5, line 4: (in) Section 3.2.
- Page 6, lines 20-1: "until convergence" should be moved just after "$|w_i|-K$"; One should refer not to Section 2.4 but to Section 2.5.
- Page 6, line 26: The formula for $s$ should be $s=\hat{w}^Tw/\|\hat{w}\|^2$.
- Page 6, line 30; Section 3.4: As Reviewer BTWr questioned, as opposed the proposal by the authors here, it is known that the quantization that is equispaced in the CDF values is not optimal in terms of the mean squared quantization error. See, e.g., Zador, IEEE Trans. Info. Theory, volume 28, pages 139-149, 1982.
- Page 6, equation (8): Please think about most elegant notation here, as is written.
- Page 6, lines 46-7: custom (arithmetic → arbitrary) precision arithmetic
- Page 7, line 7: coefficients → parameters
- Page 7, Theorem 3.1: Why do not the authors write $s_h=\|v_g\|^2/\|w\|^2$? The second parameter of the beta distribution should be $\frac{D(G-1)}{2}$, not $\frac{G(D-1)}{2}$. The statement of this theorem is well known: See, e.g., Ross, *A First Course in Probability*, 10th ed., Pearson, 2020, where Example 3b in Section 6.3.2 states that a sum of iid zero-mean Gaussians is chi-squared and thus gamma, and where Example 7c in Section 6.7 states that $X/(X+Y)$ for independent gammas $X,Y$ is beta.
- Page 7, Figure 5 caption: closely match(es)