# A Tighter Complexity Analysis of SparseGPT

arXiv: https://arxiv.org/abs/2408.12151 · HTML: https://mlsanity.com/paper/2408.12151/

## Key facts

- Cited by 19 papers in the map (data through 14 Oct 2026).
- Builds on 75 of its 103 references that are in the map.
- First posted on arXiv 22 Aug 2024.

## Builds on (most cited first, 30 of 75)

- [Language Models are Few-Shot Learners](https://mlsanity.com/paper/2005.14165/) (2020)
- [Mamba: Linear-Time Sequence Modeling with Selective State Spaces](https://mlsanity.com/paper/2312.00752/) (2023)
- [FlashAttention: Fast and Memory-Efficient Exact Attention with IO-Awareness](https://mlsanity.com/paper/2205.14135/) (2022)
- [OPT: Open Pre-trained Transformer Language Models](https://mlsanity.com/paper/2205.01068/) (2022)
- [FlashAttention-2: Faster Attention with Better Parallelism and Work Partitioning](https://mlsanity.com/paper/2307.08691/) (2023)
- [The Lottery Ticket Hypothesis: Finding Sparse, Trainable Neural Networks](https://mlsanity.com/paper/1803.03635/) (2018)
- [Efficient Streaming Language Models with Attention Sinks](https://mlsanity.com/paper/2309.17453/) (2023)
- [Learning both Weights and Connections for Efficient Neural Networks](https://mlsanity.com/paper/1506.02626/) (2015)
- [Transformers are SSMs: Generalized Models and Efficient Algorithms Through Structured State Space Duality](https://mlsanity.com/paper/2405.21060/) (2024)
- [AWQ: Activation-aware Weight Quantization for LLM Compression and Acceleration](https://mlsanity.com/paper/2306.00978/) (2023)
- [SparseGPT: Massive Language Models Can Be Accurately Pruned in One-Shot](https://mlsanity.com/paper/2301.00774/) (2023)
- [Medusa: Simple LLM Inference Acceleration Framework with Multiple Decoding Heads](https://mlsanity.com/paper/2401.10774/) (2024)
- [H2O: Heavy-Hitter Oracle for Efficient Generative Inference of Large Language Models](https://mlsanity.com/paper/2306.14048/) (2023)
- [SNIP: Single-shot Network Pruning based on Connection Sensitivity](https://mlsanity.com/paper/1810.02340/) (2018)
- [Up or Down? Adaptive Rounding for Post-Training Quantization](https://mlsanity.com/paper/2004.10568/) (2020)
- [What is the State of Neural Network Pruning?](https://mlsanity.com/paper/2003.03033/) (2020)
- [Sparsity in Deep Learning: Pruning and growth for efficient inference and training in neural networks](https://mlsanity.com/paper/2102.00554/) (2021)
- [FlashAttention-3: Fast and Accurate Attention with Asynchrony and Low-precision](https://mlsanity.com/paper/2407.08608/) (2024)
- [Quest: Query-Aware Sparsity for Efficient Long-Context LLM Inference](https://mlsanity.com/paper/2406.10774/) (2024)
- [Pruning neural networks without any data by iteratively conserving synaptic flow](https://mlsanity.com/paper/2006.05467/) (2020)
- [BRECQ: Pushing the Limit of Post-Training Quantization by Block Reconstruction](https://mlsanity.com/paper/2102.05426/) (2021)
- [Model Tells You What to Discard: Adaptive KV Cache Compression for LLMs](https://mlsanity.com/paper/2310.01801/) (2023)
- [Picking Winning Tickets Before Training by Preserving Gradient Flow](https://mlsanity.com/paper/2002.07376/) (2020)
- [Hyena Hierarchy: Towards Larger Convolutional Language Models](https://mlsanity.com/paper/2302.10866/) (2023)
- [Blockwise Parallel Decoding for Deep Autoregressive Models](https://mlsanity.com/paper/1811.03115/) (2018)
- [Optimal Brain Compression: A Framework for Accurate Post-Training Quantization and Pruning](https://mlsanity.com/paper/2208.11580/) (2022)
- [LayerSkip: Enabling Early Exit Inference and Self-Speculative Decoding](https://mlsanity.com/paper/2404.16710/) (2024)
- [Deja Vu: Contextual Sparsity for Efficient LLMs at Inference Time](https://mlsanity.com/paper/2310.17157/) (2023)
- [Compressing Context to Enhance Inference Efficiency of Large Language Models](https://mlsanity.com/paper/2310.06201/) (2023)
- [A Fast Post-Training Pruning Framework for Transformers](https://mlsanity.com/paper/2204.09656/) (2022)

## Built on by (most cited first, 19 of 19)

- [Tensor Product Attention Is All You Need](https://mlsanity.com/paper/2501.06425/) (2025)
- [Circuit Complexity Bounds for RoPE-based Transformer Architecture](https://mlsanity.com/paper/2411.07602/) (2024)
- [Multi-Layer Transformers Gradient Can be Approximated in Almost Linear Time](https://mlsanity.com/paper/2408.13233/) (2024)
- [Bypassing the Exponential Dependency: Looped Transformers Efficiently Learn In-context by Multi-step Gradient Descent](https://mlsanity.com/paper/2410.11268/) (2024)
- [The Computational Limits of State-Space Models and Mamba via the Lens of Circuit Complexity](https://mlsanity.com/paper/2412.06148/) (2024)
- [HSR-Enhanced Sparse Attention Acceleration](https://mlsanity.com/paper/2410.10165/) (2024)
- [High-Order Matching for One-Step Shortcut Diffusion Models](https://mlsanity.com/paper/2502.00688/) (2025)
- [Theoretical Constraints on the Expressive Power of mathsfRoPE-based Tensor Attention Transformers](https://mlsanity.com/paper/2412.18040/) (2024)
- [Video Latent Flow Matching: Optimal Polynomial Projections for Video Interpolation and Extrapolation](https://mlsanity.com/paper/2502.00500/) (2025)
- [Theoretical Guarantees for High Order Trajectory Refinement in Generative Flows](https://mlsanity.com/paper/2503.09069/) (2025)
- [Fast RoPE Attention: Combining the Polynomial Method and Fast Fourier Transform](https://mlsanity.com/paper/2505.11892/) (2025)
- [Only Large Weights (And Not Skip Connections) Can Prevent the Perils of Rank Collapse](https://mlsanity.com/paper/2505.16284/) (2025)
- [Advancing the Understanding of Fixed Point Iterations in Deep Neural Networks: A Detailed Analytical Study](https://mlsanity.com/paper/2410.11279/) (2024)
- [Neural Algorithmic Reasoning for Hypergraphs with Looped Transformers](https://mlsanity.com/paper/2501.10688/) (2025)
- [Scaling Law Phenomena Across Regression Paradigms: Multiple and Kernel Approaches](https://mlsanity.com/paper/2503.01314/) (2025)
- [Differentially Private Kernel Density Estimation](https://mlsanity.com/paper/2409.01688/) (2024)
- [When Can We Solve the Weighted Low Rank Approximation Problem in Truly Subquadratic Time?](https://mlsanity.com/paper/2502.16912/) (2025)
- [Time and Memory Trade-off of KV-Cache Compression in Tensor Transformer Decoding](https://mlsanity.com/paper/2503.11108/) (2025)
- [Theoretical Foundation of Flow-Based Time Series Generation: Provable Approximation, Generalization, and Efficiency](https://mlsanity.com/paper/2503.14076/) (2025)

## Abstract (arXiv)

In this work, we improved the analysis of the running time of SparseGPT [Frantar, Alistarh ICML 2023] from O(d3) to O(dω + d2+a+o(1) + d1+ω(1,1,a)-a) for any a ∈ [0, 1], where ω is the exponent of matrix multiplication. In particular, for the current ω ≈ 2.371 [Alman, Duan, Williams, Xu, Xu, Zhou 2024], our running time boils down to O(d2.53). This running time is due to the analysis of the lazy update behavior in iterative maintenance problems such as [Deng, Song, Weinstein 2022; Brand, Song, Zhou ICML 2024].