# SpAtten: Efficient Sparse Attention Architecture with Cascade Token and Head Pruning

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

## Key facts

- Cited by 234 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 17 Dec 2020.

## Built on by (most cited first, 30 of 234)

- [Efficient Streaming Language Models with Attention Sinks](https://mlsanity.com/paper/2309.17453/) (2023)
- [SmoothQuant: Accurate and Efficient Post-Training Quantization for Large Language Models](https://mlsanity.com/paper/2211.10438/) (2022)
- [AWQ: Activation-aware Weight Quantization for LLM Compression and Acceleration](https://mlsanity.com/paper/2306.00978/) (2023)
- [H2O: Heavy-Hitter Oracle for Efficient Generative Inference of Large Language Models](https://mlsanity.com/paper/2306.14048/) (2023)
- [MInference 1.0: Accelerating Pre-filling for Long-Context LLMs via Dynamic Sparse Attention](https://mlsanity.com/paper/2407.02490/) (2024)
- [SpecInfer: Accelerating Generative Large Language Model Serving with Tree-based Speculative Inference and Verification](https://mlsanity.com/paper/2305.09781/) (2023)
- [Gated Attention for Large Language Models: Non-linearity, Sparsity, and Attention-Sink-Free](https://mlsanity.com/paper/2505.06708/) (2025)
- [QServe: W4A8KV4 Quantization and System Co-design for Efficient LLM Serving](https://mlsanity.com/paper/2405.04532/) (2024)
- [A Survey on Efficient Inference for Large Language Models](https://mlsanity.com/paper/2404.14294/) (2024)
- [LLM in a flash: Efficient Large Language Model Inference with Limited Memory](https://mlsanity.com/paper/2312.11514/) (2023)
- [SPViT: Enabling Faster Vision Transformers via Soft Token Pruning](https://mlsanity.com/paper/2112.13890/) (2021)
- [A Fast Post-Training Pruning Framework for Transformers](https://mlsanity.com/paper/2204.09656/) (2022)
- [REST: Retrieval-Based Speculative Decoding](https://mlsanity.com/paper/2311.08252/) (2023)
- [Learned Token Pruning for Transformers](https://mlsanity.com/paper/2107.00910/) (2021)
- [Keyformer: KV Cache Reduction through Key Tokens Selection for Efficient Generative Inference](https://mlsanity.com/paper/2403.09054/) (2024)
- [SeerAttention: Learning Intrinsic Sparse Attention in Your LLMs](https://mlsanity.com/paper/2410.13276/) (2024)
- [Dynamic Memory Compression: Retrofitting LLMs for Accelerated Inference](https://mlsanity.com/paper/2403.09636/) (2024)
- [QuantumNAS: Noise-Adaptive Search for Robust Quantum Circuits](https://mlsanity.com/paper/2107.10845/) (2021)
- [S3: Increasing GPU Utilization during Generative Inference for Higher Throughput](https://mlsanity.com/paper/2306.06000/) (2023)
- [Full Stack Optimization of Transformer Inference: a Survey](https://mlsanity.com/paper/2302.14017/) (2023)
- [Compression of Generative Pre-trained Language Models via Quantization](https://mlsanity.com/paper/2203.10705/) (2022)
- [Efficient Methods for Natural Language Processing: A Survey](https://mlsanity.com/paper/2209.00099/) (2022)
- [FlightLLM: Efficient Large Language Model Inference with a Complete Mapping Flow on FPGAs](https://mlsanity.com/paper/2401.03868/) (2024)
- [Model Compression and Efficient Inference for Large Language Models: A Survey](https://mlsanity.com/paper/2402.09748/) (2024)
- [Zero-TPrune: Zero-Shot Token Pruning through Leveraging of the Attention Graph in Pre-Trained Transformers](https://mlsanity.com/paper/2305.17328/) (2023)
- [Fast On-device LLM Inference with NPUs](https://mlsanity.com/paper/2407.05858/) (2024)
- [MoE-Pruner: Pruning Mixture-of-Experts Large Language Model using the Hints from Its Router](https://mlsanity.com/paper/2410.12013/) (2024)
- [Keyword Transformer: A Self-Attention Model for Keyword Spotting](https://mlsanity.com/paper/2104.00769/) (2021)
- [SparseViT: Revisiting Activation Sparsity for Efficient High-Resolution Vision Transformer](https://mlsanity.com/paper/2303.17605/) (2023)
- [ANT: Exploiting Adaptive Numerical Data Type for Low-bit Deep Neural Network Quantization](https://mlsanity.com/paper/2208.14286/) (2022)

## Abstract (arXiv)

The attention mechanism is becoming increasingly popular in Natural Language Processing (NLP) applications, showing superior performance than convolutional and recurrent architectures. However, attention becomes the compution bottleneck because of its quadratic computational complexity to input length, complicated data movement and low arithmetic intensity. Moreover, existing NN accelerators mainly focus on optimizing convolutional or recurrent models, and cannot efficiently support attention. In this paper, we present SpAtten, an efficient algorithm-architecture co-design that leverages token sparsity, head sparsity, and quantization opportunities to reduce the attention computation and memory access. Inspired by the high redundancy of human languages, we propose the novel cascade token pruning to prune away unimportant tokens in the sentence. We also propose cascade head pruning to remove unessential heads. Cascade pruning is fundamentally different from weight pruning since there is no trainable weight in the attention mechanism, and the pruned tokens and heads are selected on the fly. To efficiently support them on hardware, we design a novel top-k engine to rank token and head importance scores with high throughput. Furthermore, we propose progressive quantization that first fetches MSBs only and performs the computation; if the confidence is low, it fetches LSBs and recomputes the attention outputs, trading computation for memory reduction. Extensive experiments on 30 benchmarks show that, on average, SpAtten reduces DRAM access by 10.0x with no accuracy loss, and achieves 1.6x, 3.0x, 162x, 347x speedup, and 1,4x, 3.2x, 1193x, 4059x energy savings over A3 accelerator, MNNFast accelerator, TITAN Xp GPU, Xeon CPU, respectively.