LUT-GEMM: Quantized Matrix Multiplication based on LUTs for Efficient Inference in Large-Scale Generative Language Models

We highly appreciate your kind efforts in evaluating our work. The manuscript has been carefully revised to address your comments as below.

Weakness 0 & Question

One big issue in writing that prevents one from reimplementing the proposed method is how to construct the binary matrices and scaling factor matrices from the pre-trained weights. The attached code assumes randomized matrices so that part cannot provide any useful information regarding this.

In addition, the authors did not clearly describe how you derive the scaling factors matrices and binary matrices from the pre-trained weights. I think that part is necessary and it will be better if there is any theoretical analysis of the quantization error or variance.

According to this comment, we have included an example implementation in the supplementary material demonstrating the construction of binary matrices and scaling factor matrices from pre-trained weights. Please refer to the examples directory provided in the supplementary material.

In the case of uniform quantization, our process involves initially obtaining scaling factor matrices and integer weight matrices through a uniform quantization method (we utilized the simple RTN method in our example). Subsequently, we proceed to convert the integer weight matrix into binary weight matrices using bitwise operations, as explained in detail in Appendix C of the revised manuscript. Additionally, to form a key for LUT-GEMM, we pack eight consecutive binary weights in a row into a uint8 data type. All these steps are implemented in the example directory.

In the revised manuscript, we’ve clearly highlighted how to construct the binary matrices and scaling factor matrices from the pre-trained weights. Thank you for your feedback to improve the quality of our manuscript significantly.

Weakness 1

Regarding the LUT part, what is the repetition that we can exploit form? The quantitative measurements or ablation studies on this will provide more insights into how many benefits we can get for such LUT-based GEMM instead of vanilla additions. Any theoretical analysis on the upper bound of savings brought from LUT?

As you mentioned, there is an upper bound to the benefits achievable when using LUT-GEMM, and in certain scenarios, it might be less efficient than a typical GEMM approach. When employing LUT-GEMM, the advantage lies in precomputing all additions and subtractions of inputs $x_0$ to $x_7$ through a 256-size table, reducing the original 8 operations to just 1 operation. This translates to a reduction from 8 operations to 1, resulting in a 1/8 computation load. However, this applies to the 1-bit scenario; in the case of 4 bits, there is a 4/8, or 1/2, computational advantage if the memory bandwidth is sufficiently large. Nonetheless, due to limitations in memory bandwidth, the reduction in memory (from 16 bits to 4 bits) theoretically yields a fourfold maximum speed improvement cost-effectively.

However, there are limitations even with LUT-GEMM. In cases where the hidden_dim is exceptionally small, the cost of creating a lookup table might outweigh the computational cost, leading to a relative decrease in speed enhancement. This scenario occurs when hidden_dim is smaller than 512, a situation rarely seen in LLM cases.

We deeply appreciate the invaluable feedback provided by the reviewer.

Weakness 1

The novelty of this paper is ordinary. The main parts, including BCQ quantification and group-wise quantization optimization, both come from existing research. This paper proposes to convert uniform quantization into BCQ format, which is not a complex transformation.

Thanks for your careful comment. In addressing the raised concern regarding the originality of our work, it is crucial to highlight the distinctive contributions of LUT-GEMM, which closely align with recent research trends.

• LUT-GEMM showcases compatibility with cutting-edge model compression techniques. Current investigations into weight-only quantization for Large Language Model (LLM) compression predominantly emphasize uniform quantization [1, 2]. In Appendix C, we clearly demonstrate that LUT-GEMM is not only applicable to non-uniformly quantized models but also to uniformly quantized models, which is neglected in [3] . This showcases the versatility of LUT-GEMM in harnessing the effects of cutting-edge quantization technologies.
• LUT-GEMM introduces group-wise quantization, offering a novel search space for LUT-based kernels. This facilitates the fine-tuning of the trade-off between model size, latency, and accuracy. The flexibility provided by group-wise quantization enables the customization of systems to meet the specific requirements of diverse services.
• In contrast to the focus of prior work [3] on CPU optimization, which demonstrated suboptimal performance on GPUs compared to cuBLAS, LUT-GEMM provides tailored optimization and a comprehensive analysis for the most widely used Large Language Model (LLM) accelerator—GPUs. Our proposed method exhibits superior performance on GPUs compared to cuBLAS, and we offer a thorough analysis regarding optimization on GPUs.

[1] Lin, Ji, et al. "AWQ: Activation-aware Weight Quantization for LLM Compression and Acceleration." arXiv preprint arXiv:2306.00978 (2023).
[2] Frantar, Elias, et al. "OPTQ: Accurate quantization for generative pre-trained transformers." The Eleventh International Conference on Learning Representations. 2022.
[3] Jeon, Yongkweon, et al. "Biqgemm: matrix multiplication with lookup table for binary-coding-based quantized dnns." SC20: International Conference for High Performance Computing, Networking, Storage and Analysis. IEEE, 2020.

Weakness 2

The author mentioned that the optimization here currently only focuses on the inference of a single batch, which may limit its use.

In Section 6, we acknowledge that LUT-GEMM exhibits diminishing performance gains with increasing batch size. This phenomenon arises due to the effective utilization of a potent built-in GEMM accelerator Tensor core, which becomes operational when the batch size exceeds 4. Consequently, the design choice of LUT-GEMM, employing CUDA core for single batch operations, is intentionally tailored for scenarios assumed to process single requests at a time in personal computers, prioritizing privacy considerations.

Weakness 3

The LUT-Based method requires a significant amount of memory capacity in exchange for efficiency. In Table 2, the 4-bit quantified LUT-GEMM storage footprint exceeds the 16 bit model of the cuBLAS baseline. In fact, storage resources are also the main focus of quantization in large language models, not just performance. This paper seems to focus mainly on computational efficiency, but lacks a comparison between memory resource usage.

We appreciate your feedback, and we acknowledge that there were some confusing descriptions in the original manuscript regarding memory utilization in Table 2. To clarify, the presented memory utilization in Table 2 represents the percentage of time over the past sample period during which global (device) memory was being read or written [4]. In essence, the memory utilization metric is closely linked to memory movement rather than the amount of memory used in a GPU.

In reality, the memory footprint of LUT-GEMM is significantly smaller than that of cuBLAS. This substantial reduction in memory usage allows us to successfully execute a 175B model on a single GPU, as demonstrated in Table 4. In contrast, attempting to run the 16-bit model of the cuBLAS baseline results in an out-of-memory (OOM) occurrence. We have taken your feedback into consideration and, in the revised manuscript, have made efforts to clearly present the definition of memory utilization in Table 2 to avoid any confusion.

[4] https://nvidia.custhelp.com/app/answers/detail/a_id/3751/~/useful-nvidia-smi-queries

We express our sincere gratitude for the invaluable feedback offered by the reviewer.

Weakness 1

As said above, the originality question is the key. Please provide detailed narrative on the differentiation. Including prior kernels in evaluations would be even stronger.

Thanks for your careful comment. In addressing the raised concern regarding the originality of our work, it is crucial to highlight the distinctive contributions of LUT-GEMM, which closely align with recent research trends.

• LUT-GEMM showcases compatibility with cutting-edge model compression techniques. Current investigations into weight-only quantization for Large Language Model (LLM) compression predominantly emphasize uniform quantization [1, 2]. In Appendix C, we clearly demonstrate that LUT-GEMM is not only applicable to non-uniformly quantized models but also to uniformly quantized models, which is neglected in [3]. This showcases the versatility of LUT-GEMM in harnessing the effects of cutting-edge quantization technologies.
• LUT-GEMM introduces group-wise quantization, offering a novel search space for LUT-based kernels. This facilitates the fine-tuning of the trade-off between model size, latency, and accuracy. The flexibility provided by group-wise quantization enables the customization of systems to meet the specific requirements of diverse services.
• In contrast to the focus of prior work [3] on CPU optimization, which demonstrated suboptimal performance on GPUs compared to cuBLAS, LUT-GEMM provides tailored optimization and a comprehensive analysis for the most widely used Large Language Model (LLM) accelerator—GPUs. Our proposed method exhibits superior performance on GPUs compared to cuBLAS, and we offer a thorough analysis regarding optimization on GPUs.

[1] Lin, Ji, et al. "AWQ: Activation-aware Weight Quantization for LLM Compression and Acceleration." arXiv preprint arXiv:2306.00978 (2023).
[2] Frantar, Elias, et al. "OPTQ: Accurate quantization for generative pre-trained transformers." The Eleventh International Conference on Learning Representations. 2022.
[3] Jeon, Yongkweon, et al. "Biqgemm: matrix multiplication with lookup table for binary-coding-based quantized dnns." SC20: International Conference for High Performance Computing, Networking, Storage and Analysis. IEEE, 2020.

Weakness 2

The last row of Table 2 suggests 4X speed up with 4-bit quantization at kernel level. However this does not seems to translate to the 4-bit end2end latency in Tables 3 and 4, not anywhere close to 4X. Can you explain why?

We sincerely appreciate your valuable feedback on our manuscript. Upon careful reevaluation, we've identified an error in the reported experimental results regarding the speedup achieved by our proposed method. In our manuscript, we originally stated a speedup of 4.32x in matrix multiplication, but upon revisiting our findings, we acknowledge that the actual speedup achieved was 3.23x. Now, the result is aligned with our end-to-end latency evaluation represented in Table 4. We deeply regret this oversight and recognize the importance of accurately representing our experimental outcomes. To rectify this mistake, we revise the manuscript to reflect the correct speedup, ensuring the accuracy and integrity of our reported findings. Once again, we extend our gratitude for your meticulous review, which has enabled us to address this error and enhance the precision of our work.

Furthermore, to demonstrate the effect of speed up in matrix multiplication to end-to-end performance, we have conducted latency evaluations on the OPT-30B model. Note that, for a fair comparison with FP16 cuBLAS, we utilized the OPT-30B model, which is executable on a single GPU without quantization. As illustrated in the table below, the end-to-end speedup closely correlates with the speedup achieved in matrix multiplication.

Weakness 3

A critical property of the proposal is that the benefit gets larger as the matrix dimension increases. Right now the results only show end2end latency for OPT 66B and 175B. Could you add a plot of latency as a function of OPT model sizes, all the way from the smallest to 175B?

The authors highly appreciate this careful suggestion. During the revision, we have added a figure in the revised manuscript to show end-to-end latency as a function of OPT model sizes (Figure 8).

I have read the rebuttal and thanks for the correction and additional data and explanation. My rating is unchanged.

We are grateful for the valuable feedback provided by the reviewer. In this response, we thoroughly address each of your comments and suggestions.

Weakness 1

The achievement of deploying huge models on a singular GPU is undermined by the lack of reported accuracy metrics at this scale.

We apologize for the unclear descriptions. In Table 5 of our manuscript, we aimed to present the latency and accuracy metrics for the quantized OPT-175B model, specifically compressed for deployment on a single GPU. It's worth noting that the PPL, where lower values indicate better performance, exhibits an increase as the quantization bit $q$ increases and the group size g decreases. In the revised manuscript, we have included a comprehensive accuracy evaluation at $q=3$ with newly added Table 9.

Weakness 2

The paper lacks a direct accuracy and latency comparison among different models, although the OPT model family is a good choice.

To take this comment into account, we have expanded our evaluations to include latency assessments across the LLaMA model family (Table 7 in the revised manuscript).

* PPL from AWQ reference [1]
[1] Lin, Ji, et al. "AWQ: Activation-aware Weight Quantization for LLM Compression and Acceleration." arXiv preprint arXiv:2306.00978 (2023).

Weakness 3

The paper does seem to have some limited technical novelty since it adapts and extends prior method in minor to moderate ways, but the analysis and implementation seem to make up for it.

Thanks for your careful comment. In addressing the raised concern regarding the originality of our work, it is crucial to highlight the distinctive contributions of LUT-GEMM, which closely align with recent research trends.

• LUT-GEMM showcases compatibility with cutting-edge model compression techniques. Current investigations into weight-only quantization for Large Language Model (LLM) compression predominantly emphasize uniform quantization [1, 2]. In Appendix C, we clearly demonstrate that LUT-GEMM is not only applicable to non-uniformly quantized models but also to uniformly quantized models, which is neglected in [3]. This showcases the versatility of LUT-GEMM in harnessing the effects of cutting-edge quantization technologies.
• LUT-GEMM introduces group-wise quantization, offering a novel search space for LUT-based kernels. This facilitates the fine-tuning of the trade-off between model size, latency, and accuracy. The flexibility provided by group-wise quantization enables the customization of systems to meet the specific requirements of diverse services.
• In contrast to the focus of prior work [3] on CPU optimization, which demonstrated suboptimal performance on GPUs compared to cuBLAS, LUT-GEMM provides tailored optimization and a comprehensive analysis for the most widely used Large Language Model (LLM) accelerator—GPUs. Our proposed method exhibits superior performance on GPUs compared to cuBLAS, and we offer a thorough analysis regarding optimization on GPUs.

[1] Lin, Ji, et al. "AWQ: Activation-aware Weight Quantization for LLM Compression and Acceleration." arXiv preprint arXiv:2306.00978 (2023).
[2] Frantar, Elias, et al. "OPTQ: Accurate quantization for generative pre-trained transformers." The Eleventh International Conference on Learning Representations. 2022.
[3] Jeon, Yongkweon, et al. "Biqgemm: matrix multiplication with lookup table for binary-coding-based quantized dnns." SC20: International Conference for High Performance Computing, Networking, Storage and Analysis. IEEE, 2020.