MACKO: Sparse Matrix-Vector Multiplication for Low Sparsity

2025/11/17 by V. Macko, Macko, Vladimír, Vladimír Boža +1
Computer Science · #Advanced Neural Network Applications #Artificial Intelligence (cs.AI) #Big Data and Digital Economy #Data Structures and Algorithms (cs.DS) #Distributed #FOS: Computer and information sciences #Machine Learning (cs.LG) #Parallel #Parallel Computing and Optimization Techniques #and Cluster Computing (cs.DC)

paper · pdf · doi:10.48550/arxiv.2511.13061

openalex publication_date 2025/11/17 · openalex created_date 2025/11/19 · openalex updated_date 2026/07/28

Abstract

Sparse Matrix-Vector Multiplication (SpMV) is a fundamental operation in the inference of sparse Large Language Models (LLMs). Because existing SpMV methods perform poorly under the low and unstructured sparsity (30-90%) commonly observed in pruned LLMs, unstructured pruning provided only limited memory reduction and speedup. We propose MACKO-SpMV, a GPU-optimized format and kernel co-designed to reduce storage overhead while preserving compatibility with the GPU's execution model. This enables efficient SpMV for unstructured sparsity without specialized hardware units (e.g., tensor cores) or format-specific precomputation. Empirical results show that at sparsity 50%, MACKO is the first approach with significant 1.5x memory reduction and 1.2-1.5x speedup over dense representation. Speedups over other SpMV baselines: 2.8-13.0x over cuSPARSE, 1.9-2.6x over Sputnik, and 2.2-2.5x over DASP. Applied to Llama2-7B pruned with Wanda to sparsity 50%, it delivers 1.5x memory reduction and 1.5x faster inference at fp16 precision. Thanks to MACKO, unstructured pruning at 50% sparsity is now justified in real-world LLM workloads.

Citations

• The Unseen Frontier: Pushing the Limits of LLM Sparsity with Surrogate-Free ADMM
• Pretraining Large Language Models with NVFP4
• Toward Efficient SpMV in Sparse LLMs via Block Extraction and Compressed Storage
• Phi-4 Technical Report
• Two Sparse Matrices are Better than One: Sparsifying Neural Networks with Double Sparse Factorization
• The Llama 3 Herd of Models
• Qwen2 Technical Report
• FlashAttention-3: Fast and Accurate Attention with Asynchrony and Low-precision
• QTIP: Quantization with Trellises and Incoherence Processing
• QServe: W4A8KV4 Quantization and System Co-design for Efficient LLM Serving
• Benchmarking and Dissecting the Nvidia Hopper GPU Architecture
• OneBit: Towards Extremely Low-bit Large Language Models
• BitDistiller: Unleashing the Potential of Sub-4-Bit LLMs via Self-Distillation
• SliceGPT: Compress Large Language Models by Deleting Rows and Columns
• DistServe: Disaggregating Prefill and Decoding for Goodput-optimized Large Language Model Serving
• Mixtral of Experts
• Fast and Effective Weight Update for Pruned Large Language Models
• Splitwise: Efficient generative LLM inference using phase splitting
• BitNet: Scaling 1-bit Transformers for Large Language Models
• VENOM: A Vectorized N:M Format for Unleashing the Power of Sparse Tensor Cores
• Llama 2: Open Foundation and Fine-Tuned Chat Models
• FlashAttention-2: Faster Attention with Better Parallelism and Work Partitioning
• A Simple and Effective Pruning Approach for Large Language Models
• LLM-QAT: Data-Free Quantization Aware Training for Large Language Models
• QLoRA: Efficient Finetuning of Quantized LLMs
• LLM-Pruner: On the Structural Pruning of Large Language Models
• A Survey of Large Language Models
• FlexGen: High-Throughput Generative Inference of Large Language Models with a Single GPU
• SparseGPT: Massive Language Models Can Be Accurately Pruned in One-Shot
• GPTQ: Accurate Post-Training Quantization for Generative Pre-trained Transformers
• ByteTransformer: A High-Performance Transformer Boosted for Variable-Length Inputs
• LLM.int8(): 8-bit Matrix Multiplication for Transformers at Scale
• DeepSpeed Inference: Enabling Efficient Inference of Transformer Models at Unprecedented Scale
• FlashAttention: Fast and Memory-Efficient Exact Attention with IO-Awareness
• OPT: Open Pre-trained Transformer Language Models
• 8-bit Optimizers via Block-wise Quantization
• Block Pruning For Faster Transformers
• Sparse GPU Kernels for Deep Learning
• Attention Is All You Need
• CSR5: An Efficient Storage Format for Cross-Platform Sparse Matrix-Vector Multiplication

Cited by

• Expand Neurons, Not Parameters
• The Unseen Frontier: Pushing the Limits of LLM Sparsity with Surrogate-Free ADMM
• COSPADI: Compressing LLMs via Calibration-Guided Sparse Dictionary Learning

Related

• Toward Efficient SpMV in Sparse LLMs via Block Extraction and Compressed Storage
• A survey of sparse matrix-vector multiplication performance on large\n matrices
• Optimizing Sparse Matrix-Vector Multiplication on Emerging Many-Core Architectures
• Unified Static-Dynamic Pruning for Efficient LLM Inference
• BLaST: High Performance Inference and Pretraining using BLock Sparse Transformers