# Sparse Attention Acceleration with Synergistic In-Memory Pruning and On-Chip Recomputation

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

## Key facts

- Cited by 12 papers in the map (data through 14 Oct 2026).
- Builds on 51 of its 168 references that are in the map.
- First posted on arXiv 1 Sep 2022.

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

- [Attention Is All You Need](https://mlsanity.com/paper/1706.03762/) (2017)
- [BERT: Pre-training of Deep Bidirectional Transformers for Language Understanding](https://mlsanity.com/paper/1810.04805/) (2018)
- [An Image is Worth 16x16 Words: Transformers for Image Recognition at Scale](https://mlsanity.com/paper/2010.11929/) (2020)
- [PyTorch: An Imperative Style, High-Performance Deep Learning Library](https://mlsanity.com/paper/1912.01703/) (2019)
- [GLUE: A Multi-Task Benchmark and Analysis Platform for Natural Language Understanding](https://mlsanity.com/paper/1804.07461/) (2018)
- [SQuAD: 100,000+ Questions for Machine Comprehension of Text](https://mlsanity.com/paper/1606.05250/) (2016)
- [Longformer: The Long-Document Transformer](https://mlsanity.com/paper/2004.05150/) (2020)
- [ALBERT: A Lite BERT for Self-supervised Learning of Language Representations](https://mlsanity.com/paper/1909.11942/) (2019)
- [Big Bird: Transformers for Longer Sequences](https://mlsanity.com/paper/2007.14062/) (2020)
- [Reformer: The Efficient Transformer](https://mlsanity.com/paper/2001.04451/) (2020)
- [Rethinking Attention with Performers](https://mlsanity.com/paper/2009.14794/) (2020)
- [Generating Long Sequences with Sparse Transformers](https://mlsanity.com/paper/1904.10509/) (2019)
- [Are Sixteen Heads Really Better than One?](https://mlsanity.com/paper/1905.10650/) (2019)
- [Compressive Transformers for Long-Range Sequence Modelling](https://mlsanity.com/paper/1911.05507/) (2019)
- [Long Range Arena: A Benchmark for Efficient Transformers](https://mlsanity.com/paper/2011.04006/) (2020)
- [In-Datacenter Performance Analysis of a Tensor Processing Unit](https://mlsanity.com/paper/1704.04760/) (2017)
- [Efficient Content-Based Sparse Attention with Routing Transformers](https://mlsanity.com/paper/2003.05997/) (2020)
- [Generating Wikipedia by Summarizing Long Sequences](https://mlsanity.com/paper/1801.10198/) (2018)
- [EIE: Efficient Inference Engine on Compressed Deep Neural Network](https://mlsanity.com/paper/1602.01528/) (2016)
- [SpAtten: Efficient Sparse Attention Architecture with Cascade Token and Head Pruning](https://mlsanity.com/paper/2012.09852/) (2020)
- [Structured Pruning of Large Language Models](https://mlsanity.com/paper/1910.04732/) (2019)
- [Chasing Sparsity in Vision Transformers: An End-to-End Exploration](https://mlsanity.com/paper/2106.04533/) (2021)
- [Blockwise Self-Attention for Long Document Understanding](https://mlsanity.com/paper/1911.02972/) (2019)
- [Adaptively Sparse Transformers](https://mlsanity.com/paper/1909.00015/) (2019)
- [Learned Token Pruning for Transformers](https://mlsanity.com/paper/2107.00910/) (2021)
- [SCNN: An Accelerator for Compressed-sparse Convolutional Neural Networks](https://mlsanity.com/paper/1708.04485/) (2017)
- [Bit Fusion: Bit-Level Dynamically Composable Architecture for Accelerating Deep Neural Networks](https://mlsanity.com/paper/1712.01507/) (2017)
- [GOBO: Quantizing Attention-Based NLP Models for Low Latency and Energy Efficient Inference](https://mlsanity.com/paper/2005.03842/) (2020)
- [A3: Accelerating Attention Mechanisms in Neural Networks with Approximation](https://mlsanity.com/paper/2002.10941/) (2020)
- [EdgeBERT: Sentence-Level Energy Optimizations for Latency-Aware Multi-Task NLP Inference](https://mlsanity.com/paper/2011.14203/) (2020)

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

- [Tender: Accelerating Large Language Models via Tensor Decomposition and Runtime Requantization](https://mlsanity.com/paper/2406.12930/) (2024)
- [A Survey: Collaborative Hardware and Software Design in the Era of Large Language Models](https://mlsanity.com/paper/2410.07265/) (2024)
- [PIM Is All You Need: A CXL-Enabled GPU-Free System for Large Language Model Inference](https://mlsanity.com/paper/2502.07578/) (2025)
- [Scaling Down to Scale Up: A Cost-Benefit Analysis of Replacing OpenAI's LLM with Open Source SLMs in Production](https://mlsanity.com/paper/2312.14972/) (2023)
- [PAPI: Exploiting Dynamic Parallelism in Large Language Model Decoding with a Processing-In-Memory-Enabled Computing System](https://mlsanity.com/paper/2502.15470/) (2025)
- [ConSmax: Hardware-Friendly Alternative Softmax with Learnable Parameters](https://mlsanity.com/paper/2402.10930/) (2024)
- [MCBP: A Memory-Compute Efficient LLM Inference Accelerator Leveraging Bit-Slice-enabled Sparsity and Repetitiveness](https://mlsanity.com/paper/2509.10372/) (2025)
- [UniCAIM: A Unified CAM/CIM Architecture with Static-Dynamic KV Cache Pruning for Efficient Long-Context LLM Inference](https://mlsanity.com/paper/2504.07479/) (2025)
- [An Analog and Digital Hybrid Attention Accelerator for Transformers with Charge-based In-memory Computing](https://mlsanity.com/paper/2409.04940/) (2024)
- [Kernel Approximation using Analog In-Memory Computing](https://mlsanity.com/paper/2411.03375/) (2024)
- [DARTH-PUM: A Hybrid Processing-Using-Memory Architecture](https://mlsanity.com/paper/2602.16075/) (2026)
- [D-NOVA: In-Storage Retrieval Accelerator via Dual-Bound 3D NAND-Optimized Similarity Search with Vector Adaptation](https://mlsanity.com/paper/2607.17538/) (2026)

## Abstract (arXiv)

As its core computation, a self-attention mechanism gauges pairwise correlations across the entire input sequence. Despite favorable performance, calculating pairwise correlations is prohibitively costly. While recent work has shown the benefits of runtime pruning of elements with low attention scores, the quadratic complexity of self-attention mechanisms and their on-chip memory capacity demands are overlooked. This work addresses these constraints by architecting an accelerator, called SPRINT, which leverages the inherent parallelism of ReRAM crossbar arrays to compute attention scores in an approximate manner. Our design prunes the low attention scores using a lightweight analog thresholding circuitry within ReRAM, enabling SPRINT to fetch only a small subset of relevant data to on-chip memory. To mitigate potential negative repercussions for model accuracy, SPRINT re-computes the attention scores for the few fetched data in digital. The combined in-memory pruning and on-chip recompute of the relevant attention scores enables SPRINT to transform quadratic complexity to a merely linear one. In addition, we identify and leverage a dynamic spatial locality between the adjacent attention operations even after pruning, which eliminates costly yet redundant data fetches. We evaluate our proposed technique on a wide range of state-of-the-art transformer models. On average, SPRINT yields 7.5x speedup and 19.6x energy reduction when total 16KB on-chip memory is used, while virtually on par with iso-accuracy of the baseline models (on average 0.36% degradation).