🤖 machine learning

PATCH: Learnable Tile-level Hybrid Sparsity for LLMs

PATCH is a hybrid sparsity framework that partitions LLM weight matrices into tiles with learnable dense or 2:4 sparse mappings to enable continuous sparsity ratios between 0% and 50%, thereby achieving superior accuracy and practical GPU speedups compared to existing unstructured or rigid semi-structured pruning methods.

Original authors: Younes Hourri, Mohammad Mozaffari, Maryam Mehri Dehnavi

Published 2026-04-30

📖 3 min read☕ Coffee break read

CC BY 4.0

Original authors: Younes Hourri, Mohammad Mozaffari, Maryam Mehri Dehnavi

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

Imagine a Large Language Model (LLM) as a massive, hyper-organized library containing billions of books (parameters). To run this library quickly on a standard computer, you must remove some books. However, you face a tricky dilemma:

The "messy" approach (Unstructured Sparsity): You randomly throw away books from everywhere on the shelves. This preserves the library's knowledge very accurately because you can be highly selective, but it creates a chaotic mess. A librarian (the computer's GPU) trying to find books must hop around everywhere, making the process slow and inefficient.
The "strict" approach (2:4 Sparsity): You decide to follow a strict rule: "In every group of four books, you must remove exactly two." This makes the librarian's work simple and fast because the pattern is predictable. However, this rule is too rigid. Sometimes the two books you must remove are actually the most important ones, causing the library to lose its intelligence and accuracy.

Here comes PATCH into play: The "intelligent tile" librarian

The work introduces a new method called PATCH (Pruning with a Learnable Tile-level Configuration for Hybrid Sparsity). Instead of choosing between the "messy" and the "strict" approaches, PATCH acts like an intelligent librarian who divides the library into tiles (small, manageable shelf sections).

Here is how it works, using a simple analogy:

The tile system: Imagine the library is divided into square tiles, like a mosaic.
The decision: For each tile, the PATCH system learns to make a choice:
- Option A (Dense): Keep this tile completely filled with books. This is intended for the "critical" areas of the library where accuracy is most important.
- Option B (2:4 Sparsity): Apply the strict rule "remove two out of four" to this tile. This is intended for areas where the library has extra, redundant books that can safely be removed to save space and increase speed.
The learning process: The system does not guess. It "trains" itself to figure out exactly which tiles should be full and which should be sparse. It learns to keep the important parts dense and the redundant parts sparse while simultaneously following hardware-friendly rules.

Why is this a big deal?

The best of both worlds: PATCH bridges the gap. It keeps the library accurate (like the messy approach) but organizes it so computers can read it quickly (like the strict approach).
Flexible speed: You can tell PATCH: "I want the library to be 25% smaller" or "50% smaller." It adjusts the number of "full tiles" versus "sparse tiles" to perfectly achieve that goal, instead of getting stuck at a fixed 50% reduction.
Real-world results: The authors tested this on models ranging from small to very large (up to 13 billion parameters).
- Speed: On a standard consumer graphics card (an A6000 GPU), PATCH made the models run 1.18 to 1.38 times faster than the original, unpruned models.
- Intelligence: Unlike other methods that make the model "dumber" when they speed it up, PATCH actually made the models more accurate (by 0.37% to 2.96%) compared to the current state-of-the-art strict method (MaskLLM).

Summary

Think of PATCH as a way to clean up a massive warehouse. Instead of randomly throwing things away (which slows down the forklifts) or following a dumb rule that throws away important items, PATCH intelligently assigns certain zones to be kept full and other zones to be cleared according to a pattern that forklifts love. The result is a warehouse that is faster to navigate yet still contains all essential knowledge.

1. Problem Statement

Large Language Models (LLMs) offer superior performance but suffer from prohibitive memory and compute costs during deployment. Model pruning is a primary solution, yet existing approaches face a fundamental trade-off:

Unstructured Sparsity: Allows non-zero elements at arbitrary positions, preserving high accuracy but creating irregular memory access patterns that prevent efficient GPU acceleration (e.g., Tensor Cores).
Semi-structured Sparsity (e.g., 2:4): Enforces a rigid pattern (two non-zero values per four elements) that is hardware-friendly and accelerates inference. However, the fixed 50% sparsity ratio and uniform application across all layers often lead to significant accuracy degradation, especially when using One-Shot pruning methods.

Current methods struggle to bridge the gap between the flexibility of unstructured pruning and the hardware efficiency of semi-structured pruning, particularly regarding the inability to continuously adjust sparsity ratios or distribute sparsity non-uniformly across layers.

2. Methodology: PATCH

The authors propose PATCH (Pruning with a Learnable Tile-level Configuration for Hybrid Sparsity), a framework that enables a continuous sparsity ratio between 0% and 50% while maintaining hardware compatibility.

Core Mechanism

PATCH divides weight matrices into Tiles (e.g., $b_1 \times b_2$ ). For each tile, the model learns to decide whether to remain dense (0% sparsity) or become 2:4-sparse (50% sparsity).

Hybrid Mask Generation: The final mask is a weighted combination of a "dense" option and a "2:4-sparse" option.
Learnable Distributions:
1. Tile Selection: A learnable logit distribution determines the probability that a tile is dense or sparse. This is sampled using Gumbel-Softmax to enable differentiable optimization.
2. Pattern Selection: Within tiles marked as sparse, a separate learnable distribution selects the specific 2:4 pattern (from 6 possible permutations).
Optimization Objective: The training objective combines:
- Standard modeling loss (e.g., Next Token Prediction).
- Sparsity Regularization: A term that penalizes deviations from a target global sparsity ratio ( $\rho$ ), enabling precise control in the 0–50% range.
- Weight Regularization: Promotes larger weight magnitudes to support gradient propagation.

Variants

PATCHJoint: Jointly optimizes both the tile-level selection (dense vs. sparse) and the fine-grained 2:4 patterns within sparse tiles. Used for smaller models (<1 billion parameters).
PATCHTile: A memory-efficient variant where the 2:4 patterns are frozen (initialized from a high-quality One-Shot method like MaskLLM), and only the tile-level decisions for dense/sparse are optimized. This enables scaling to larger models (up to 13 billion) with limited GPU memory.

Inference & Deployment

STOICC Integration: Since standard GPU libraries (cuBLAS, cuSPARSELt) do not support mixed dense/sparse tiles, PATCH utilizes STOICC, a Triton-based compiler. STOICC autotunes kernel configurations (tile sizes, e.g., $128 \times 128$ ) to handle hybrid execution efficiently.
Hardware Compatibility: By ensuring sparse tiles strictly follow the 2:4 pattern, PATCH leverages NVIDIA/AMD Tensor Cores for acceleration, while dense tiles use standard dense kernels.

3. Main Contributions

Hybrid Sparsity Framework: Introduces the first method enabling a continuous sparsity ratio (0%–50%) by dynamically mixing dense and 2:4 sparse tiles within the same weight matrix.
Learnable Non-Uniform Allocation: Unlike fixed 2:4 methods, PATCH learns to allocate sparsity adaptively. It preserves density in sensitive layers (e.g., early/late Transformer blocks, Attention mechanisms) and applies sparsity to redundant layers (e.g., middle blocks, MLP Up/Gate/Down matrices).
End-to-End Differentiable Training: Uses Gumbel-Softmax to jointly optimize mask selection and weight pruning, avoiding the accuracy loss associated with One-Shot pruning.
Practical Deployment: Demonstrates the first successful integration of hybrid tile-level sparsity with a compiler (STOICC) to achieve real speedups on consumer GPUs.

4. Experimental Results

The authors evaluated PATCH on models with 0.5 to 13 billion parameters (Qwen-2.5, LLaMA-2/3, Gemma-3) using 8 Zero-Shot downstream tasks and WikiText2 perplexity.

Accuracy:
- PATCH consistently outperforms State-of-the-Art 2:4 pruning methods (MaskLLM, SparseGPT, Wanda, ProxSparse).
- On LLaMA-2 7B, PATCH achieves an average accuracy of 51.58% at 25% sparsity, compared to 48.62% for MaskLLM (50% sparsity) and 45.92% for ProxSparse.
- PATCH significantly narrows the gap to dense models; at 25% sparsity, it is within approximately 2 percentage points of dense accuracy.
- Perplexity: PATCH achieves lower perplexity than all baselines. For LLaMA-2 7B at 25% sparsity, PPL is 5.86 versus 6.78 for MaskLLM.
Speedup & Efficiency:
- On an NVIDIA A6000 GPU (LLaMA-2 7B), PATCH achieves end-to-end speedups of 1.18× to 1.38× over dense baselines.
- Memory requirements are reduced to 0.59×–0.76× of the dense model.
- PATCH outperforms unstructured pruning (which offers no speedup) and rigid 2:4 pruning (which often degrades accuracy too severely to justify the speed).
Ablation Studies:
- Global vs. Layer-wise: Global sparsity targets (allowing variable sparsity per layer) significantly outperform uniform layer-wise targets.
- Tile Size: Performance is robust across tile sizes, with $4 \times 4$ offering the finest control. However, hardware efficiency requires larger execution tiles ( $128 \times 128$ ).
- Initialization: The method is robust to initialization priors; the global sparsity target enables dynamic redistribution during training.

5. Significance

PATCH represents a significant step forward in efficient LLM inference by resolving the "accuracy vs. acceleration" dilemma.

Bridging the Gap: It successfully combines the hardware acceleration benefits of semi-structured sparsity with the flexibility of unstructured allocation.
Practicality: It goes beyond theoretical pruning to demonstrate actual speedups on real hardware using existing compiler infrastructure (STOICC).
Scalability: The memory-efficient variant (PATCHTile) proves that hybrid sparsity can be applied to large models (13B+) without massive compute budgets for training masks.
Future Direction: The framework is pattern-agnostic and can theoretically be extended to other N:M patterns (e.g., 4:8) as new hardware supports them, making it a versatile solution for future LLM compression.

In summary, PATCH offers a flexible, learnable, and hardware-efficient pruning strategy that enables practitioners to tune the trade-off between model quality and inference speed with unprecedented granularity.