mlsanityData to 7 Oct 2026

A Tighter Complexity Analysis of SparseGPT

arXiv 2408.12151 ↗First posted 22 Aug 2024cs.DS cs.AI cs.CLcited by 19

Not on the map. Why?

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].

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

Builds on

75 of 103 references.

References · 75

  1. 2020Language Models are Few-Shot Learnerscited by 32,199
  2. 2023Mamba: Linear-Time Sequence Modeling with Selective State Spacescited by 4,616
  3. 2022FlashAttention: Fast and Memory-Efficient Exact Attention with IO-Awarenesscited by 3,611
  4. 2022OPT: Open Pre-trained Transformer Language Modelscited by 3,464
  5. 2023FlashAttention-2: Faster Attention with Better Parallelism and Work Partitioningcited by 2,551
  6. 2018The Lottery Ticket Hypothesis: Finding Sparse, Trainable Neural Networkscited by 2,250
  7. 2023Efficient Streaming Language Models with Attention Sinkscited by 2,115
  8. 2015Learning both Weights and Connections for Efficient Neural Networkscited by 1,998
  9. 2024Transformers are SSMs: Generalized Models and Efficient Algorithms Through Structured State Space Dualitycited by 1,283
  10. 2023AWQ: Activation-aware Weight Quantization for LLM Compression and Accelerationcited by 1,234
  11. 2023SparseGPT: Massive Language Models Can Be Accurately Pruned in One-Shotcited by 1,090
  12. 2024Medusa: Simple LLM Inference Acceleration Framework with Multiple Decoding Headscited by 821
38 more
  1. 2023H2O: Heavy-Hitter Oracle for Efficient Generative Inference of Large Language Modelscited by 805
  2. 2018SNIP: Single-shot Network Pruning based on Connection Sensitivitycited by 802
  3. 2020Up or Down? Adaptive Rounding for Post-Training Quantizationcited by 600
  4. 2020What is the State of Neural Network Pruning?cited by 578
  5. 2021Sparsity in Deep Learning: Pruning and growth for efficient inference and training in neural networkscited by 521
  6. 2024FlashAttention-3: Fast and Accurate Attention with Asynchrony and Low-precisioncited by 507
  7. 2024Quest: Query-Aware Sparsity for Efficient Long-Context LLM Inferencecited by 487
  8. 2020Pruning neural networks without any data by iteratively conserving synaptic flowcited by 475
  9. 2020Picking Winning Tickets Before Training by Preserving Gradient Flowcited by 467
  10. 2023Model Tells You What to Discard: Adaptive KV Cache Compression for LLMscited by 466
  11. 2021BRECQ: Pushing the Limit of Post-Training Quantization by Block Reconstructioncited by 464
  12. 2023Hyena Hierarchy: Towards Larger Convolutional Language Modelscited by 388
  13. 2018Blockwise Parallel Decoding for Deep Autoregressive Modelscited by 318
  14. 2022Optimal Brain Compression: A Framework for Accurate Post-Training Quantization and Pruningcited by 317
  15. 2024LayerSkip: Enabling Early Exit Inference and Self-Speculative Decodingcited by 302
  16. 2023Deja Vu: Contextual Sparsity for Efficient LLMs at Inference Timecited by 247
  17. 2023Compressing Context to Enhance Inference Efficiency of Large Language Modelscited by 185
  18. 2022A Fast Post-Training Pruning Framework for Transformerscited by 161
  19. 2024The Hedgehog & the Porcupine: Expressive Linear Attentions with Softmax Mimicrycited by 119
  20. 2021Accelerated Sparse Neural Training: A Provable and Efficient Method to Find N:M Transposable Maskscited by 103
  21. 2023Fast Attention Requires Bounded Entriescited by 102
  22. 2018Solving Linear Programs in the Current Matrix Multiplication Timecited by 100
  23. 2024TriForce: Lossless Acceleration of Long Sequence Generation with Hierarchical Speculative Decodingcited by 98
  24. 2023HyperAttention: Long-context Attention in Near-Linear Timecited by 85
  25. 2024Get More with LESS: Synthesizing Recurrence with KV Cache Compression for Efficient LLM Inferencecited by 75
  26. 2021Only Train Once: A One-Shot Neural Network Training And Pruning Frameworkcited by 70
  27. 2021Training Multi-Layer Over-Parametrized Neural Network in Subquadratic Timecited by 62
  28. 2020Training (Overparametrized) Neural Networks in Near-Linear Timecited by 58
  29. 2023KDEformer: Accelerating Transformers via Kernel Density Estimationcited by 58
  30. 2020An Improved Cutting Plane Method for Convex Optimization, Convex-Concave Games and its Applicationscited by 57
  31. 2019The Generalization-Stability Tradeoff In Neural Network Pruningcited by 54
  32. 2019Solving Empirical Risk Minimization in the Current Matrix Multiplication Timecited by 53
  33. 2020A Faster Interior Point Method for Semidefinite Programmingcited by 53
  34. 2024Linearizing Large Language Modelscited by 51
  35. 2024QJL: 1-Bit Quantized JL Transform for KV Cache Quantization with Zero Overheadcited by 47
  36. 2019A Deterministic Linear Program Solver in Current Matrix Multiplication Timecited by 42
  37. 2024On Computational Limits of Modern Hopfield Models: A Fine-Grained Complexity Analysiscited by 41
  38. 2024On Statistical Rates and Provably Efficient Criteria of Latent Diffusion Transformers (DiTs)cited by 39

50 most cited of 75 All 75 (JSON)

Built on by

Cited by year

Citing papers per year: 2024: 8; 2025: 11.

19 papers.

Sort:

By area:

  1. 2025Tensor Product Attention Is All You Needcited by 27
  2. 2024Circuit Complexity Bounds for RoPE-based Transformer Architecturecited by 26
  3. 2024Multi-Layer Transformers Gradient Can be Approximated in Almost Linear Timecited by 22
  4. 2024Bypassing the Exponential Dependency: Looped Transformers Efficiently Learn In-context by Multi-step Gradient Descentcited by 21
  5. 2024The Computational Limits of State-Space Models and Mamba via the Lens of Circuit Complexitycited by 21
  6. 2024HSR-Enhanced Sparse Attention Accelerationcited by 19
  7. 2025High-Order Matching for One-Step Shortcut Diffusion Modelscited by 15
  8. 2024Theoretical Constraints on the Expressive Power of mathsfRoPE-based Tensor Attention Transformerscited by 12
  9. 2025Video Latent Flow Matching: Optimal Polynomial Projections for Video Interpolation and Extrapolationcited by 11
  10. 2025Theoretical Guarantees for High Order Trajectory Refinement in Generative Flowscited by 9
  11. 2025Fast RoPE Attention: Combining the Polynomial Method and Fast Fourier Transformcited by 9
  12. 2025Only Large Weights (And Not Skip Connections) Can Prevent the Perils of Rank Collapsecited by 7
7 more
  1. 2024Advancing the Understanding of Fixed Point Iterations in Deep Neural Networks: A Detailed Analytical Studycited by 4
  2. 2025Scaling Law Phenomena Across Regression Paradigms: Multiple and Kernel Approachescited by 4
  3. 2025Neural Algorithmic Reasoning for Hypergraphs with Looped Transformerscited by 3
  4. 2025When Can We Solve the Weighted Low Rank Approximation Problem in Truly Subquadratic Time?cited by 3
  5. 2024Differentially Private Kernel Density Estimationcited by 2
  6. 2025Time and Memory Trade-off of KV-Cache Compression in Tensor Transformer Decodingcited by 2
  7. 2025Theoretical Foundation of Flow-Based Time Series Generation: Provable Approximation, Generalization, and Efficiencycited by 2