Large Language Model Compression with Global Rank and Sparsity Optimization

This paper proposes a novel two-stage LLM compression method that leverages robust principal component analysis and a probabilistic global allocation strategy to optimize the interaction between low-rank and sparse components while automatically adapting resource distribution across layers, thereby significantly outperforming existing state-of-the-art techniques.

The Gist

Imagine you have a massive, encyclopedic library (a Large Language Model, or LLM) that knows everything from how to write a poem to how to fix a car engine. The problem is, this library is so huge that it takes up an entire warehouse, requires a fleet of trucks to move, and is incredibly slow to search through. You want to shrink it down to fit in a backpack without losing the ability to answer complex questions.

This paper introduces a new method called CAP (Compression with Global Rank and Sparsity Optimization) to solve this problem. Here is how it works, explained through simple analogies.

The Problem: Why Old Methods Fail

Previous attempts to shrink these libraries had two main flaws:

1. The "One-Size-Fits-All" Mistake: Imagine trying to shrink a library by throwing away 50% of the books in every single room. But some rooms (like the "History" section) are full of duplicates, while others (like "Quantum Physics") have unique, vital books. If you cut 50% everywhere, you might throw away the only copy of a crucial book in the Physics room while keeping too many duplicates in the History room.
2. The "Manual Sorting" Bottleneck: Old methods often relied on humans (or rigid rules) to decide which books to keep. They would say, "Keep the top 100 most popular books." But sometimes, a book with only 50 reads is actually more important for understanding a specific topic than a popular one.

The Solution: The Two-Stage "CAP" Strategy

The authors propose a two-step process to intelligently shrink the library.

Stage 1: The "Smart Sort" (RPCA Decomposition)

Imagine the library's books are written in a mix of two styles:

• The "Pattern" Style: Most books follow a standard, predictable structure (like a template for a news article). This is the Low-Rank part.
• The "Outlier" Style: Some books contain weird, specific, or highly unique facts (like a specific recipe for a rare dish or a unique historical anecdote). This is the Sparse part.

What CAP does: Instead of just randomly deleting pages, it uses a mathematical technique called Robust Principal Component Analysis (RPCA). Think of this as a super-smart librarian who instantly separates the "standard templates" from the "unique outliers."

• They put all the standard templates into one pile (Low-Rank).
• They put all the unique, weird facts into a separate, smaller pile (Sparse).

Why this helps: It stops the library from trying to compress the unique facts using the same rules as the standard templates. It creates two distinct "candidate pools" to work with.

Stage 2: The "Global Budget" (Probabilistic Pruning)

Now, the library has a strict budget: "You can only keep 50% of the total pages."

Old methods would look at the "Standard Templates" pile and say, "We need to cut 50% of these," and then look at the "Unique Facts" pile and say, "We need to cut 50% of these too." This is the "one-size-fits-all" mistake again.

CAP's approach is like a smart city planner managing a budget.

• It looks at the entire library at once.
• It asks: "Which specific pages in the 'Standard' pile are actually useless? And which specific pages in the 'Unique' pile are absolutely critical?"
• It uses a probabilistic strategy (like rolling a weighted die) to decide what to keep. If a page is super important, the die is weighted heavily to keep it. If it's redundant, the die is weighted to discard it.
• Crucially, it doesn't just look at one room; it looks at the whole building. If the "History" room is full of duplicates, it cuts heavily there. If the "Physics" room has unique facts, it cuts very little there, even if that means cutting more elsewhere.

The Result: A Backpack-Sized Library

By combining these two steps, CAP achieves something remarkable:

1. It keeps the "skeleton" (Low-Rank): The general structure and common sense of the model remain intact.
2. It keeps the "spark" (Sparse): The specific, weird, and crucial facts that make the model smart are preserved.
3. It fits the budget: It automatically figures out exactly how much to cut from each section to hit the target size without breaking the model.

Why It's Better Than the Rest

• No "Fine-Tuning" Required: Most other methods shrink the library and then have to spend weeks re-teaching the librarian how to find things again (fine-tuning). CAP does it in one go. It's like shrinking the library and having it work perfectly immediately.
• Speed: Because the "Unique Facts" pile becomes extremely empty (very sparse), the computer can skip over them incredibly fast, making the library run faster than before.
• Adaptability: It realizes that the "Physics" section needs more pages than the "History" section, and it adjusts automatically.

In a Nutshell

Think of CAP as a master editor who doesn't just cut random sentences from a book. Instead, they first separate the "boring, repetitive paragraphs" from the "brilliant, unique insights." Then, they use a smart budget to decide exactly which of those insights are so important that they must be saved, even if it means cutting more of the boring stuff. The result is a shorter, faster book that still tells the whole story perfectly.

Technical Summary

1. Problem Statement

Large Language Models (LLMs) face critical deployment challenges due to their massive parameter counts, requiring significant storage, memory, and computational resources. While existing compression techniques like quantization (reducing precision) and pruning (removing weights) are common, they have limitations:

• Quantization often preserves the full structure, limiting compression ratios.
• Unstructured Pruning (e.g., SparseGPT, Wanda) removes individual weights but often requires extensive fine-tuning or distillation to recover performance, especially at high sparsity levels.
• Low-Rank + Sparse Decomposition: A promising approach involves decomposing weight matrices into a low-rank component (capturing global correlations) and a sparse component (capturing outliers/domain-specific knowledge). However, existing methods suffer from:
  1. Heuristic Thresholds: Reliance on manually set singular-value cutoffs, which can discard important medium-sized singular values.
  2. Independent Optimization: The low-rank and sparse parts are often optimized independently or require expensive backpropagation.
  3. Lack of Global Coordination: There is no clear mechanism to dynamically allocate rank vs. sparsity across different layers, despite the fact that redundancy varies significantly between early and deep layers.

2. Methodology: CAP (Two-Stage Framework)

The authors propose CAP, a novel two-stage, training-free compression framework that utilizes Robust Principal Component Analysis (RPCA) and Policy Gradient optimization to achieve global resource allocation.

Stage 1: Principled Decomposition via RPCA

Instead of directly pruning weights, the method first decomposes each weight matrix $W$ into a low-rank matrix $L$ and a sparse matrix $S$ using RPCA.

• Objective: Solve the convex optimization problem:
  $$\min_{L,S} \|L\|_* + \lambda \|S\|_1 \quad \text{subject to} \quad W = L + S$$
  Where $\|L\|_*$ is the nuclear norm (promoting low rank) and $\|S\|_1$ is the L1 norm (promoting sparsity).
• Mechanism: The authors use the Alternating Direction Method of Multipliers (ADMM) to solve this.
• Purpose: This step reduces the massive search space of individual weights into two structured subspaces: a low-dimensional subspace (global patterns) and a sparse subspace (local anomalies/outliers). Crucially, this stage is not for achieving a target compression ratio but for creating a high-quality candidate pool.

Stage 2: Learnable Probabilistic Pruning (Global Resource Allocation)

Once decomposed, the method performs a global, budget-aware selection to meet a specific parameter budget $K$.

• Probabilistic Modeling: Retention decisions for singular values in $L$ and non-zero entries in $S$ are modeled as Bernoulli random variables with learnable probabilities ($s_{\sigma_i}$ and $s_{S_{ij}}$).
• Optimization via Policy Gradient:
  • The retention probabilities are treated as policy parameters.
  • The method minimizes the expected reconstruction loss on a small calibration set using REINFORCE-style policy gradients.
  • A moving average baseline is used to reduce variance.
  • Key Advantage: This avoids backpropagation through the original LLM parameters and eliminates the need for manual thresholds. It learns which components are most "useful" relative to their cost.
• Final Selection: After optimization, the probabilities are used to rank all potential parameters globally. The top-$K$ parameters are selected deterministically to strictly adhere to the budget.
• Efficiency: The final low-rank component is factorized into smaller matrices ($U'$ and $V'$) to reduce inference latency.

3. Key Contributions

1. Novel Two-Stage Framework: CAP uniquely combines RPCA for structural decomposition with Policy Gradient for global resource allocation, separating the "what to keep" (decomposition) from "how much to keep" (allocation).
2. Training-Free & Threshold-Free: The method eliminates the need for manual singular-value thresholds or expensive fine-tuning/backpropagation on the original model weights. It adapts automatically to the redundancy characteristics of different layers.
3. Global Coordination: Unlike layer-wise allocation methods, CAP jointly optimizes rank and sparsity across the entire model, dynamically balancing the trade-off between low-rank and sparse components based on learned utility.
4. Theoretical Foundation: The approach leverages the convexity of RPCA for a principled separation of global and local features, followed by a stochastic optimization for discrete budget constraints.

4. Experimental Results

The authors evaluated CAP on a wide range of models (LLaMA-1/2/3, Phi-3, Qwen2.5, OPT, BERT) across various compression ratios (30% to 50% sparsity).

• Performance vs. Unstructured Pruning: CAP consistently outperforms state-of-the-art unstructured pruning methods (SparseGPT, Wanda, DSNoT, OATS) and layer-wise allocation methods (OWL, AlphaPruning).
  • Example: On LLaMA-3 8B at 50% sparsity, CAP achieved 74.05% zero-shot accuracy compared to 73.25% for the best baseline (AlphaPruning) and 72.85% for the dense model's uncompressed performance drop.
• Performance vs. Joint Compression: CAP surpasses joint compression methods like SLiM (which combines low-rank, sparsity, and quantization) and L2QER.
  • Example: On LLaMA-3.1-8B-Instruct, CAP improved Chain-of-Thought reasoning (GSM8K) by +11.2% over Wanda at 50% sparsity.
• Efficiency:
  • Throughput: CAP achieves higher inference throughput (176.5 tok/s) compared to Wanda (163.4 tok/s) on A100 GPUs. This is attributed to the sparse component $S$ achieving extremely high sparsity (>85%), which is more efficient for Sparse Matrix Multiplication (SpMM) than the uniform 50% sparsity of standard pruning.
  • Memory: CAP maintains a lower peak memory footprint (14.90 GB vs. 15.18 GB for Wanda).
• Robustness: The method shows strong robustness across different calibration datasets (C4, WikiText, GitHub Code) and maintains performance even under high compression (25% retention).

5. Significance

This paper addresses a critical bottleneck in LLM deployment: how to compress models aggressively without losing the "knowledge neurons" required for reasoning and factual accuracy.

• Paradigm Shift: It moves away from heuristic, layer-by-layer pruning or simple magnitude-based removal toward a global, data-driven optimization of the model's structural representation.
• Practical Impact: By being training-free and avoiding backpropagation, CAP is highly scalable and suitable for compressing massive models (e.g., 70B+ parameters) where fine-tuning is computationally prohibitive.
• Hardware Synergy: The resulting structure (Low-Rank + Highly Sparse) is specifically optimized for modern hardware accelerators, offering real-world inference speedups alongside parameter reduction.

In conclusion, CAP demonstrates that a principled decomposition followed by probabilistic global allocation is a superior strategy for LLM compression, outperforming existing SOTA methods in both accuracy and inference efficiency.