# Fused3S: Fast Sparse Attention on Tensor Cores

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

## Key facts

- Cited by 2 papers in the map (data through 14 Oct 2026).
- Builds on 26 of its 47 references that are in the map.
- First posted on arXiv 12 May 2025.

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

- [Attention Is All You Need](https://mlsanity.com/paper/1706.03762/) (2017)
- [Graph Attention Networks](https://mlsanity.com/paper/1710.10903/) (2017)
- [Inductive Representation Learning on Large Graphs](https://mlsanity.com/paper/1706.02216/) (2017)
- [FlashAttention: Fast and Memory-Efficient Exact Attention with IO-Awareness](https://mlsanity.com/paper/2205.14135/) (2022)
- [Longformer: The Long-Document Transformer](https://mlsanity.com/paper/2004.05150/) (2020)
- [FlashAttention-2: Faster Attention with Better Parallelism and Work Partitioning](https://mlsanity.com/paper/2307.08691/) (2023)
- [Fast Graph Representation Learning with PyTorch Geometric](https://mlsanity.com/paper/1903.02428/) (2019)
- [Open Graph Benchmark: Datasets for Machine Learning on Graphs](https://mlsanity.com/paper/2005.00687/) (2020)
- [Big Bird: Transformers for Longer Sequences](https://mlsanity.com/paper/2007.14062/) (2020)
- [Generating Long Sequences with Sparse Transformers](https://mlsanity.com/paper/1904.10509/) (2019)
- [Revisiting Semi-Supervised Learning with Graph Embeddings](https://mlsanity.com/paper/1603.08861/) (2016)
- [A Generalization of Transformer Networks to Graphs](https://mlsanity.com/paper/2012.09699/) (2020)
- [GraphSAINT: Graph Sampling Based Inductive Learning Method](https://mlsanity.com/paper/1907.04931/) (2019)
- [Anti-Money Laundering in Bitcoin: Experimenting with Graph Convolutional Networks for Financial Forensics](https://mlsanity.com/paper/1908.02591/) (2019)
- [Sparse GPU Kernels for Deep Learning](https://mlsanity.com/paper/2006.10901/) (2020)
- [Attention-based Graph Neural Network for Semi-supervised Learning](https://mlsanity.com/paper/1803.03735/) (2018)
- [IGB: Addressing The Gaps In Labeling, Features, Heterogeneity, and Size of Public Graph Datasets for Deep Learning Research](https://mlsanity.com/paper/2302.13522/) (2023)
- [FusedMM: A Unified SDDMM-SpMM Kernel for Graph Embedding and Graph Neural Networks](https://mlsanity.com/paper/2011.06391/) (2020)
- [TC-GNN: Bridging Sparse GNN Computation and Dense Tensor Cores on GPUs](https://mlsanity.com/paper/2112.02052/) (2021)
- [Efficient Quantized Sparse Matrix Operations on Tensor Cores](https://mlsanity.com/paper/2209.06979/) (2022)
- [SEA: Sparse Linear Attention with Estimated Attention Mask](https://mlsanity.com/paper/2310.01777/) (2023)
- [High Performance Unstructured SpMM Computation Using Tensor Cores](https://mlsanity.com/paper/2408.11551/) (2024)
- [TorchGT: A Holistic System for Large-scale Graph Transformer Training](https://mlsanity.com/paper/2407.14106/) (2024)
- [Acc-SpMM: Accelerating General-purpose Sparse Matrix-Matrix Multiplication with GPU Tensor Cores](https://mlsanity.com/paper/2501.09251/) (2025)
- [FlashSparse: Minimizing Computation Redundancy for Fast Sparse Matrix Multiplications on Tensor Cores](https://mlsanity.com/paper/2412.11007/) (2024)
- [DF-GNN: Dynamic Fusion Framework for Attention Graph Neural Networks on GPUs](https://mlsanity.com/paper/2411.16127/) (2024)

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

- [On Efficient Scaling of GNNs via IO-Aware Layers Implementations](https://mlsanity.com/paper/2605.31500/) (2026)
- [PageWeaver: KV-Guided Query Unions for Sparse Attention](https://mlsanity.com/paper/2610.11201/) (2026)

## Abstract (arXiv)

Sparse attention is a core building block in many leading neural network models, from graph-structured learning to sparse sequence modeling. It can be decomposed into a sequence of three sparse matrix operations (3S): sampled dense-dense matrix multiplication (SDDMM), softmax normalization, and sparse matrix multiplication (SpMM). Efficiently executing the 3S computational pattern on modern GPUs remains challenging due to (a) the mismatch between unstructured sparsity and tensor cores optimized for dense operations, and (b) the high cost of data movement. Previous works have optimized these sparse operations individually or addressed one of these challenges. This paper introduces Fused3S, the first fused 3S algorithm that jointly maximizes tensor core utilization and minimizes data movement. Across real-world graph datasets, Fused3S achieves 1.6- 16.3× and 1.5-14× speedup over state-of-the-art on H100 and A30 GPUs. Furthermore, integrating Fused3S into Graph Transformer inference accelerates end-to-end performance by 1.05-5.36×, consistently outperforming all 3S baselines across diverse datasets (single and batched graphs) and GPU architectures.