# Dynamic N:M Fine-grained Structured Sparse Attention Mechanism

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

## Key facts

- Cited by 14 papers in the map (data through 14 Oct 2026).
- Builds on 28 of its 38 references that are in the map.
- First posted on arXiv 28 Feb 2022.

## Builds on (most cited first, 28 of 28)

- [Attention Is All You Need](https://mlsanity.com/paper/1706.03762/) (2017)
- [An Image is Worth 16x16 Words: Transformers for Image Recognition at Scale](https://mlsanity.com/paper/2010.11929/) (2020)
- [Longformer: The Long-Document Transformer](https://mlsanity.com/paper/2004.05150/) (2020)
- [The Lottery Ticket Hypothesis: Finding Sparse, Trainable Neural Networks](https://mlsanity.com/paper/1803.03635/) (2018)
- [Transformers are RNNs: Fast Autoregressive Transformers with Linear Attention](https://mlsanity.com/paper/2006.16236/) (2020)
- [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)
- [Linformer: Self-Attention with Linear Complexity](https://mlsanity.com/paper/2006.04768/) (2020)
- [Efficient Transformers: A Survey](https://mlsanity.com/paper/2009.06732/) (2020)
- [Image Transformer](https://mlsanity.com/paper/1802.05751/) (2018)
- [Long Range Arena: A Benchmark for Efficient Transformers](https://mlsanity.com/paper/2011.04006/) (2020)
- [MobileBERT: a Compact Task-Agnostic BERT for Resource-Limited Devices](https://mlsanity.com/paper/2004.02984/) (2020)
- [Efficient Content-Based Sparse Attention with Routing Transformers](https://mlsanity.com/paper/2003.05997/) (2020)
- [Nystr"omformer: A Nystr"om-Based Algorithm for Approximating Self-Attention](https://mlsanity.com/paper/2102.03902/) (2021)
- [Q8BERT: Quantized 8Bit BERT](https://mlsanity.com/paper/1910.06188/) (2019)
- [Sparse Sinkhorn Attention](https://mlsanity.com/paper/2002.11296/) (2020)
- [SpAtten: Efficient Sparse Attention Architecture with Cascade Token and Head Pruning](https://mlsanity.com/paper/2012.09852/) (2020)
- [Accelerating Sparse Deep Neural Networks](https://mlsanity.com/paper/2104.08378/) (2021)
- [Scaling Neural Machine Translation](https://mlsanity.com/paper/1806.00187/) (2018)
- [Learning N:M Fine-grained Structured Sparse Neural Networks From Scratch](https://mlsanity.com/paper/2102.04010/) (2021)
- [Block Pruning For Faster Transformers](https://mlsanity.com/paper/2109.04838/) (2021)
- [SOFT: Softmax-free Transformer with Linear Complexity](https://mlsanity.com/paper/2110.11945/) (2021)
- [A Unified Lottery Ticket Hypothesis for Graph Neural Networks](https://mlsanity.com/paper/2102.06790/) (2021)
- [Explicit Sparse Transformer: Concentrated Attention Through Explicit Selection](https://mlsanity.com/paper/1912.11637/) (2019)
- [DropAttention: A Regularization Method for Fully-Connected Self-Attention Networks](https://mlsanity.com/paper/1907.11065/) (2019)
- [Systolic Tensor Array: An Efficient Structured-Sparse GEMM Accelerator for Mobile CNN Inference](https://mlsanity.com/paper/2005.08098/) (2020)

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

- [FlightLLM: Efficient Large Language Model Inference with a Complete Mapping Flow on FPGAs](https://mlsanity.com/paper/2401.03868/) (2024)
- [ZipVL: Efficient Large Vision-Language Models with Dynamic Token Sparsification](https://mlsanity.com/paper/2410.08584/) (2024)
- [SLoPe: Double-Pruned Sparse Plus Lazy Low-Rank Adapter Pretraining of LLMs](https://mlsanity.com/paper/2405.16325/) (2024)
- [Generalized Neighborhood Attention: Multi-dimensional Sparse Attention at the Speed of Light](https://mlsanity.com/paper/2504.16922/) (2025)
- [VENOM: A Vectorized N:M Format for Unleashing the Power of Sparse Tensor Cores](https://mlsanity.com/paper/2310.02065/) (2023)
- [Preserving Deep Representations In One-Shot Pruning: A Hessian-Free Second-Order Optimization Framework](https://mlsanity.com/paper/2411.18376/) (2024)
- [Efficient N:M Sparse DNN Training Using Algorithm, Architecture, and Dataflow Co-Design](https://mlsanity.com/paper/2309.13015/) (2023)
- [The Information Pathways Hypothesis: Transformers are Dynamic Self-Ensembles](https://mlsanity.com/paper/2306.01705/) (2023)
- [MEADOW: Memory-efficient Dataflow and Data Packing for Low Power Edge LLMs](https://mlsanity.com/paper/2503.11663/) (2025)
- [Samoyeds: Accelerating MoE Models with Structured Sparsity Leveraging Sparse Tensor Cores](https://mlsanity.com/paper/2503.10725/) (2025)
- [Learning Section Weights for Multi-Label Document Classification](https://mlsanity.com/paper/2311.15402/) (2023)
- [Vectorized FlashAttention with Low-cost Exponential Computation in RISC-V Vector Processors](https://mlsanity.com/paper/2510.06834/) (2025)
- [HieraSparse: Hierarchical Semi-Structured Sparse KV Attention](https://mlsanity.com/paper/2604.16864/) (2026)
- [ELiTeFormer: An Efficient Transformer for FPGAs](https://mlsanity.com/paper/2607.03652/) (2026)

## Abstract (arXiv)

Transformers are becoming the mainstream solutions for various tasks like NLP and Computer vision. Despite their success, the high complexity of the attention mechanism hinders them from being applied to latency-sensitive tasks. Tremendous efforts have been made to alleviate this problem, and many of them successfully reduce the asymptotic complexity to linear. Nevertheless, most of them fail to achieve practical speedup over the original full attention under moderate sequence lengths and are unfriendly to finetuning. In this paper, we present DFSS, an attention mechanism that dynamically prunes the full attention weight matrix to N:M fine-grained structured sparse pattern. We provide both theoretical and empirical evidence that demonstrates DFSS is a good approximation of the full attention mechanism. We propose a dedicated CUDA kernel design that completely eliminates the dynamic pruning overhead and achieves speedups under arbitrary sequence length. We evaluate the 1:2 and 2:4 sparsity under different configurations and achieve 1.27~ 1.89x speedups over the full-attention mechanism. It only takes a couple of finetuning epochs from the pretrained model to achieve on par accuracy with full attention mechanism on tasks from various domains under different sequence lengths from 384 to 4096.