QET: Enhancing Quantized LLM Parameters and KV cache Compression through Element Substitution and Residual Clustering

Yanshu Wang, Li Wang, Tong Yang, Yang, Tong

Abstract

The matrix quantization entails representing matrix elements in a more space-efficient form to reduce storage usage, with dequantization restoring the original matrix for use. We formulate the Quantization Error Minimization (QEM) problem as minimizing the distance between a matrix before and after quantization, under the condition that the quantized matrix occupies the same memory space. Matrix quantization is crucial in various applications, including Large Language Models (LLMs) weight quantization, vector databases, KV cache quantization, graph compression, and image compression. Recent advancements in LLMs, such as GPT-4 and BERT, have highlighted the importance of matrix compression due to the large size of parameters and KV cache, which are stored as matrices. We propose Quantum Entanglement Trees (QET) to address the QEM problem by leveraging the local orderliness of matrix elements, involving iterative element swapping to form a locally ordered matrix. This matrix is then grouped and quantized by columns. To enhance QET, we introduce two optimizations: further quantizing residuals to reduce MSE, and using masking and batch processing to accelerate the algorithm. Experimental results demonstrate that QET can effectively reduce MSE to 5.05%, 13.33%, and 11.89% of the current best method on the LLM dataset, K cache, and V cache, respectively.

Introduction

As Large Language Models (LLMs) continue to scale, their memory footprint presents a significant bottleneck for deployment on consumer-grade hardware. For instance, a model like GPT-3 requires massive storage for its 175 billion parameters. Furthermore, during inference, the "KV cache"—which stores previous context to accelerate token generation—can consume over 30% of total GPU memory.

To mitigate these requirements, researchers employ quantization, a process that represents high-precision numerical data (e.g., 32-bit floats) using fewer bits (e.g., 4-bit integers). The fundamental challenge is the Quantization Error Minimization (QEM) problem: how to compress data while minimizing the loss of information. Traditional methods often treat matrix elements as independent entities, ignoring spatial relationships and leading to substantial accuracy degradation at high compression ratios.

The QET Methodology

The core innovation of this work is the Quantum Entanglement Trees (QET) algorithm, which introduces a "rearrange-then-quantize" paradigm. The authors observed that the specific order of elements within a matrix significantly influences its compressibility.

Element Substitution and Recursive Partitioning

The QET algorithm operates by iteratively comparing adjacent pairs of elements. It partitions elements into two sub-matrices: a "Small Part" ($S$) and a "Large Part" ($L$). Every swap performed to achieve this ordering is recorded in an "Indicator Map," which serves as a roadmap for dequantization.

The QET workflow: element substitution into small/large parts, indicator map generation, and final clustering.

This process is repeated recursively across multiple layers. Similar to the expanding receptive field in a Convolutional Neural Network, this multi-layered approach allows elements that were originally distant in the matrix to eventually be compared and ordered. The result is a "locally ordered" matrix where values are more predictable and clustered.

Subspace Grouping and Clustering

Once the matrix has been rearranged to exhibit local orderliness, it is divided into subspaces. Because the elements are now sorted, standard clustering algorithms like Product Quantization (PQ) can identify much more accurate "centroids" to represent the data. By splitting the matrix into $m$ blocks with $c$ centroids, the system can express $c^m$ possible values while only storing $c \times m$ centroids, providing an exponential increase in expressive power.

Optimizations

To further refine the accuracy and speed of the algorithm, two key optimizations were introduced:

  1. Residual Quantization Optimization (RQO): After the initial quantization pass, the algorithm calculates the difference (residual) between the original and dequantized matrix. This residual matrix, which typically has a smaller data range, is then quantized itself.
  2. Codebook Quantization Optimization (CQO): To maximize space savings, the "dictionary" of centroids (the codebook) is also compressed.
Residual Quantization Optimization (RQO) process for refining quantization accuracy.

Experimental Setup and Datasets

The efficacy of QET was evaluated across several demanding benchmarks:

  • LLM Weights: Matrices extracted from LLaMA2 (11008 × 4096).
  • KV Cache: Key and Value matrices from the KV Quant dataset (4096 × 4096).
  • Synthetic Data: Matrices following a truncated normal distribution to test theoretical performance limits.
  • General Purpose: The Gist and Wiki datasets to demonstrate broader applicability beyond LLMs.

Key Insights

  • The Power of Order: The paper demonstrates that reordering elements can drastically reduce the number of unique vectors needed for perfect representation. A simple $2 \times 2$ matrix example shows that swapping elements can reduce the required basis vectors from two to one.
  • Theoretical Gains: For normally distributed data, the authors mathematically prove that QET's rearrangement strategy reduces Mean Squared Error (MSE) to approximately 68.2% of standard Product Quantization (PQ) even before additional optimizations.

Results and Performance

QET significantly outperforms established baselines, including PQ, Optimized Product Quantization (OPQ), and Round-To-Nearest (RTN):

  • Accuracy Improvements: On LLM weight datasets, QET achieved a staggering reduction in MSE, reaching only 5.05% of the error produced by the previous state-of-the-art method.
  • KV Cache Efficiency: For K and V caches, the error was reduced to 13.33% and 11.89% of the baseline, respectively.
  • Computational Trade-offs: While the full iterative QET algorithm is more computationally intensive than simple rounding, the authors developed a "Vanilla" version. This version utilizes batch processing and masking to maintain high speed while still significantly outperforming traditional methods in accuracy.

Conclusion and Future Directions

QET represents a significant step forward in matrix compression for large-scale models. By leveraging element substitution to create order before quantization, it achieves unprecedented accuracy at high compression ratios.

However, challenges remain. The computational overhead of iterative swapping and indicator map management is higher than traditional methods. Future work will focus on adapting these techniques for dynamic, live LLM deployments and developing specialized hardware acceleration to perform swapping operations efficiently.

Summary updated

Abstract

The matrix quantization entails representing matrix elements in a more space-efficient form to reduce storage usage, with dequantization restoring the original matrix for use. We formulate the Quantization Error Minimization (QEM) problem as minimizing the distance between a matrix before and after quantization, under the condition that the quantized matrix occupies the same memory space. Matrix quantization is crucial in various applications, including Large Language Models (LLMs) weight quantization, vector databases, KV cache quantization, graph compression, and image compression. Recent advancements in LLMs, such as GPT-4 and BERT, have highlighted the importance of matrix compression due to the large size of parameters and KV cache, which are stored as matrices. We propose Quantum Entanglement Trees (QET) to address the QEM problem by leveraging the local orderliness of matrix elements, involving iterative element swapping to form a locally ordered matrix. This matrix is then grouped and quantized by columns. To enhance QET, we introduce two optimizations: further quantizing residuals to reduce MSE, and using masking and batch processing to accelerate the algorithm. Experimental results demonstrate that QET can effectively reduce MSE to 5.05%, 13.33%, and 11.89% of the current best method on the LLM dataset, K cache, and V cache, respectively. Our contributions include the abstraction of the QEM problem, the design of the QET algorithm, and the proposal of two optimizations to improve accuracy and speed.
BibTeX
@misc{wang2024qet,
  author = {Yanshu Wang and Li Wang and Tong Yang and Yang, Tong},
  title = {{QET: Enhancing Quantized LLM Parameters and KV cache Compression through Element Substitution and Residual Clustering}},
  year = {2024},
  eprint = {2407.03637},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2407.03637},
}
Figure