Hierarchical Sparse Plus Low Rank Compression of LLM

AI summary

Overview

• Research area: Model compression for large language models, sitting at the intersection of numerical linear algebra (hierarchical matrix formats, sparse-plus-low-rank decomposition) and efficient deep-learning inference.
• Technical level: Advanced. The paper assumes familiarity with SVD, randomized sketching, matrix reordering (Reverse Cuthill–Mckee), and hierarchical matrix formats such as HSS and HODLR.
• Scope: The paper proposes and evaluates a two-stage "sparse plus hierarchical low-rank" compression scheme (sHSS, and its RCM-reordered variant sHSS‑RCM) applied to the attention projection layers of LLaMA‑7B, measuring perplexity on WikiText-103-v1.

What This Paper Is About

Deploying large language models is expensive because of their memory and compute footprint, and existing compression options each have drawbacks: quantization lowers precision, and plain low-rank or SVD-based compression struggles when weight matrices contain a few very large outlier entries. This paper asks whether combining a sparse "outlier" matrix with a recursively structured hierarchical low-rank factorization of the remaining residual can preserve accuracy better than sparse-plus-SVD baselines while still saving memory. The authors also test whether reordering the weight matrix with Reverse Cuthill–Mckee (RCM) before compression improves results, and they report an FP16 CUDA implementation that runs on a single H100.

Key Contributions

1. Sparse + hierarchical low-rank compression (sHSS). A multilevel, hierarchically separable factorization that first carves the top‑p% high-magnitude weights into a sparse mask and then applies depth-halved low-rank approximations to the off-diagonal blocks of the residual matrix.
2. An RCM-enhanced variant (sHSS‑RCM). Reordering weight matrices with Reverse Cuthill–Mckee so that large entries cluster toward the diagonal and toward the block-diagonal hierarchy, which the paper reports can shrink off-diagonal ranks further.
3. A unified comparison. Sparse + HSS, sparse + exact SVD, and sparse + randomized SVD are placed under one "sparse plus (hierarchical) low rank" formulation and compared on LLaMA‑7B weights, isolating the effects of sparsity, matrix reordering, and low-rank compression on perplexity.
4. A hardware-friendly implementation. An end-to-end half-precision (16-bit) CUDA implementation compresses 1.6B parameters of linear layers of LLaMA‑7B on a single H100, achieving up to 1.7× storage reduction, with the matrix–vector multiply reduced to one sparse multiplication plus a sequence of thin-matrix multiplications.

Main Findings

• Targeted scope is sufficient. Compressing only the self-attention projections (q_proj, k_proj, v_proj) — about 1.6B parameters out of a roughly 7B-parameter LLaMA‑7B base (described elsewhere in the paper as approximately 6.7 billion parameters) — yields large memory savings while retaining comparable state-of-the-art perplexity on WikiText test samples.
• Headline perplexity number. With a 30% sparsity budget and an outer rank of 512, sHSS‑RCM achieves a perplexity of 1.64, which the paper reports as outperforming dense baselines and classical sparse-plus-SVD variants while also achieving significant memory savings.
• Hierarchical beats SVD-based methods at aggressive compression. When more than 50% of the target parameters are compressed (down to between 0.8B and 1.0B parameters), sHSS and sHSS‑RCM do better than sparse randomized SVD (sR‑SVD) and marginally better than sparse exact SVD (sSVD).
• Hierarchical methods also win at moderate compression. At approximately 10% compression of the target parameters, hierarchical methods again show lower perplexity than SVD-based methods; the paper reports on average better perplexity than the base model despite the 10% parameter compression.
• Higher sparsity helps the low-rank step. For a fixed rank, removing a larger percentage of a layer's weights before low-rank factorization makes the low-rank approximation more accurate, leading to better perplexity — the paper's ablation uses sp10, sp20, and sp30 (10%, 20%, and 30% sparsity).
• RCM gives a modest gain. When RCM is applied after 10% of matrix entries are removed, it gives better perplexity than without it; for the other two sparsity levels tested, the difference was not pronounced. In the storage-versus-perplexity comparison, sHSS‑RCM sits slightly below sHSS at comparable storage.
• Ablation settings. The reported ablation study uses rank 512 and depth 4 for the hierarchical methods sHSS and sHSS‑RCM, with an SVD tolerance fixed at 1e‑6 throughout the experiments.
• Precision choice. All experiments use 16-bit floating point (fp16). The authors considered 8-bit quantization but avoided it after early tests showed degraded generation quality and inconsistent decoding behaviour.

Methodology in Plain English

The authors take a weight matrix from a model layer and split it into two parts. First, they lift out the entries with the largest magnitudes — the statistical outliers — into a separate sparse matrix. Second, they take what remains and compress it with a hierarchical low-rank scheme: the matrix is broken into blocks, the off-diagonal blocks are approximated by low-rank factors, and the diagonal blocks are split again and again in a recursive binary tree (a three-level version is described in detail), with the rank budget halved at each level because the blocks themselves halve in size. The insight borrowed from scientific computing is that off-diagonal blocks in structured matrices tend to be numerically low-rank, so they can be stored cheaply.

Before compressing, they optionally permute rows and columns using Reverse Cuthill–Mckee ordering, which is a classical bandwidth-reduction technique. The idea is to push the big entries closer to the diagonal so the off-diagonal parts are easier to compress. The permutation matrices are saved at each recursion level, and at inference time the input vector is permuted, pushed through the recursive structure of sparse and thin matrix multiplications, and then inverse-permuted on the output, with the top-level sparse contribution added back at the end.

Evaluation uses LLaMA‑7B base with compression restricted to q_proj, k_proj, and v_proj. The authors explain they limited compression to these layers because compressing all linear layers indiscriminately caused instability in perplexity, and because these projection matrices are square, which suits symmetric reordering like RCM. Perplexity is measured on the WikiText-103-v1 test set (over 1.8 million training examples and 4,358 test examples drawn from Wikipedia articles classified as "Good" or "Featured"). All experiments ran on a single NVIDIA H100 GPU, with PyTorch used for SVD and tensor operations.

Why This Matters

Impact on research. The paper argues that hierarchical structure in LLM weight matrices is under-exploited relative to quantization and pruning, and that sparse-plus-low-rank ideas from numerical linear algebra can be fruitfully transplanted into LLM compression. It also provides a controlled comparison between hierarchical and SVD-based sparse-plus-low-rank methods, and isolates the effect of a classical graph-based reordering step. The authors position the work as complementary to quantization and knowledge distillation rather than competing with them.

Real-world applications:

• Serving large language models on commodity or on-premises hardware where GPU memory is the binding constraint.
• Latency-sensitive applications such as chatbots, where a smaller memory footprint translates into faster loading and lower energy use.
• On-device or edge deployment, including privacy-motivated local inference on phones and low-powered devices.
• Fine-tuning and continued training of compressed models, since the scheme is designed to be trainable end-to-end with standard optimizers.

Industry relevance. The experiments stay within a single H100 and use fp16 with batched CUDA kernels, and the paper claims the compressed models retain full FP16 inference speed, with compression completed within minutes. That makes the approach relevant to practitioners who need predictable, hardware-friendly memory reductions rather than research-only compression pipelines. The released PyTorch code is linked at https://github.com/misterpawan/hi-solo-llm.

Future Directions

• Extending beyond the attention projections. The paper explicitly leaves compression across a broader range of layers (including MLP layers) to future work, noting the difficulty of applying symmetric reordering to non-square matrices because of asymmetric padding and the need for pseudo-permutation matrices.
• Combining with quantization. The authors propose combining sHSS with 4-bit weight quantization, which they did not test here (8-bit was considered but set aside).
• Dynamic rank adaptation during fine-tuning. Varying the rank budget adaptively rather than fixing the outer rank is named as a promising avenue for pushing compression past the 7-billion-parameter frontier.
• Alternative sparse reordering schemes and activations. The paper suggests exploring other reordering techniques popular in scientific computing — Nested Dissection, AMD, and COLAMD — and extending the technique to transformer activations to enable end-to-end memory reduction during training.
• Open question on RCM. The authors state that more experiments on larger LLMs are needed before concluding whether RCM reordering provides significant benefits.

Target Audience

This paper is best suited to machine-learning systems researchers and engineers working on efficient LLM inference, model compression, or low-rank and sparse matrix methods, as well as numerical linear algebra researchers interested in applications of hierarchical matrix formats. Readers will get the most from it with prior familiarity with SVD, randomized numerical linear algebra, and block-structured matrix factorizations. Practitioners seeking a drop-in compression recipe should note that the study is limited to LLaMA‑7B attention projections, FP16 precision, and a single evaluation dataset, and that several results (such as exact storage comparisons at matched compression levels) are described as not directly comparable across methods.

Authors’ abstract

Modern large language models (LLMs) place extraordinary pressure on memory and compute budgets, making principled compression indispensable for both deployment and continued training. We present Hierarchical Sparse Plus Low-Rank (HSS) compression, a two-stage scheme that (i) removes the largest-magnitude weights into a sparse matrix S and (ii) applies a recursive Hierarchically Sparse Separable (HSS) low-rank factorisation to the dense residual matrix. A recursive rank-reducing strategy and a reverse Cuthill-Mckee (RCM) permutation are introduced to align high weights towards the diagonal with the block-diagonal hierarchy, maximising off-diagonal compressibility (because they are touched only once). HSS is hardware-friendly: its matrix-vector multiply reduces to one sparse and a sequence of thin-matrix multiplications and can be trained end-to-end with standard optimisers. Experiments on LLaMA-7B show that targeting only the self-attention projections (1.6 B parameters of Q, K, and V matrices out of a total 7B parameters) suffices to yield large memory savings while retaining comparable state-of-the-art perplexity scores on test samples of the WikiText dataset. For example, with a 30\% sparsity budget and an outer rank of 512, sHSS-RCM achieves a perplexity of 1.64, outperforming dense baselines and classical sparse-plus-SVD variants, while also achieving significant memory savings.