HERA: High-efficiency Matrix Compression via Element Replacement

Yanshu Wang, Wang Li, Tong Yang

TL;DR

This paper introduces HERA, a novel algorithm for compressing large language models (LLMs) by strategically replacing matrix elements. HERA addresses the significant storage and computational challenges of LLMs by employing a hierarchical approach that segments, compresses, and reorganizes matrices based on parameter distribution, leading to reduced quantization error without sacrificing compression ratios.

What Problem Does This Paper Address?

Large Language Models (LLMs) have become incredibly powerful, driving advancements in various NLP tasks. However, their massive size, often comprising billions of parameters, presents substantial hurdles for deployment, especially on resource-constrained devices like mobile phones and edge computing platforms. This size impacts storage, computation, and memory usage. A critical component exacerbating these issues is the key-value (k-v) cache, essential for speeding up query processing, which demands significant memory.

While vector databases have emerged to efficiently manage LLM-generated vectors, and techniques like compression and quantization aim to reduce model size and computational demands, existing methods often fall short. Traditional approaches that uniformly map parameters to compressed spaces struggle with the uneven distribution of parameters within LLMs, leading to considerable accuracy loss. Therefore, there's a pressing need for innovative compression techniques that can achieve high compression ratios while preserving model performance, especially by accounting for the inherent data distribution.

Methods

HERA introduces a novel algorithm that leverages a heuristic approach for matrix compression. The core idea is to group relevant matrices and compress them using clustering methods, specifically inspired by product quantization and k-means algorithms. HERA's process involves several key steps:

  1. Space Partitioning: The high-dimensional input matrix is divided into multiple low-dimensional subspaces.
  2. Codebook Calculation: For each subspace, k-means clustering is applied to identify cluster centers, forming a codebook for that subspace.
  3. Quantization: Each vector in a subspace is independently quantized by mapping it to its nearest cluster center in the corresponding codebook.
  4. HERA Heuristics (Element Replacement): This is the novel aspect. HERA groups every two adjacent elements in the matrix into pairs. It then compares these pairs and assigns the smaller element to a "small" set and the larger to a "big" set, recording this assignment in a feature map. This process is iteratively applied. The "small" and "big" sets are then independently quantized using a product quantization approach. This heuristic element replacement aims to create a more uniform distribution of data, making subsequent compression more effective.
  5. Dequantization: The process is reversed to reconstruct the original matrix. This involves decoding the quantized values from the codebooks and using the feature map to correctly reconstruct the pairs before expanding them back to the original dimensions.

The algorithm is designed to hierarchically segment, compress, and reorganize the matrix dataset, aiming to reduce quantization error by considering the distribution and magnitude of parameters.

Datasets

The paper states that the datasets used in their experiments were generated with matrices of size N × D. Specifically, they used a "Normal Distribution Dataset" where each element was drawn from a truncated normal distribution with a mean of 0.5 and a standard deviation of 0.16, truncated to the open interval (0, 1). The authors do not mention using any pre-existing LLM datasets for training or evaluation in this work.

Key Insights and Ideas

  • Distribution-Aware Compression is Crucial: The paper strongly emphasizes that uniform compression methods fail to account for the uneven distribution of parameters in LLMs, leading to significant accuracy loss. HERA's success hinges on its ability to adapt to this distribution.
  • Heuristic Element Replacement for Uniformity: The core innovation of HERA lies in its heuristic element replacement strategy. By pairing adjacent elements and separating them into "small" and "big" sets, HERA effectively creates a more uniform distribution, which is more amenable to standard compression techniques like product quantization.
  • Hierarchical Approach Yields Better Results: The combination of hierarchical segmentation, heuristic element replacement, and product quantization allows HERA to achieve better compression with lower error compared to simpler methods.
  • Iterative Refinement Improves Performance: The experimental results show that increasing the number of iterations in HERA leads to better performance, indicating that the iterative refinement of quantization is beneficial.

Key Results

The experimental results demonstrate the effectiveness of HERA:

  • HERA can reduce the quantization error to 12.3% of the original at the same compression ratio.
  • The paper presents extensive experimental results across various numbers of subspaces (8, 16, 32, 128) and iterations (1-4). For instance, with 8 subspaces and 4 iterations, HERA achieved a significant reduction in Mean Squared Error (MSE).
  • When compared to Optimized Product Quantization (OPQ), HERA generally performs better, especially at higher compression ratios, achieving lower MAE, MRE, and MSE.
  • The parameter sensitivity analysis suggests that HERA is less sensitive to parameter choices (like the number of subspaces) compared to other methods, making it more user-friendly.

Limitations and Future Work

  • Dataset Specificity: The experiments were conducted on synthetically generated datasets following a truncated normal distribution. The paper does not explicitly evaluate HERA on real-world LLM weight matrices or benchmark datasets.
  • Focus on Matrix Compression: While the paper discusses LLMs, the core contribution is matrix compression. Its direct application and performance on full LLM models are not detailed.

The authors suggest future work that includes:

  • Applying HERA to other types of applications and broader datasets.
  • Exploring further refinements to the HERA algorithm.
  • Investigating the integration of HERA with other optimization techniques to achieve even greater enhancements in model performance and efficiency.

Summary updated

BibTeX
@misc{wang2024hera,
  author = {Yanshu Wang and Wang Li and Tong Yang},
  title = {{HERA: High-efficiency Matrix Compression via Element Replacement}},
  year = {2024},
  eprint = {2407.03637},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2407.03637},
}
Figure