# SAC: Accelerating and Structuring Self-Attention via Sparse Adaptive Connection

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

## Key facts

- Cited by 13 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 22 Mar 2020.

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

- [A Survey of Transformers](https://mlsanity.com/paper/2106.04554/) (2021)
- [Hierarchical Graph Transformer with Adaptive Node Sampling](https://mlsanity.com/paper/2210.03930/) (2022)
- [Model Compression and Efficient Inference for Large Language Models: A Survey](https://mlsanity.com/paper/2402.09748/) (2024)
- [Museformer: Transformer with Fine- and Coarse-Grained Attention for Music Generation](https://mlsanity.com/paper/2210.10349/) (2022)
- [Fast Nearest Neighbor Machine Translation](https://mlsanity.com/paper/2105.14528/) (2021)
- [Attention Mechanism in Neural Networks: Where it Comes and Where it Goes](https://mlsanity.com/paper/2204.13154/) (2022)
- [GNN-LM: Language Modeling based on Global Contexts via GNN](https://mlsanity.com/paper/2110.08743/) (2021)
- [Layer-wise Model Pruning based on Mutual Information](https://mlsanity.com/paper/2108.12594/) (2021)
- [CAB: Comprehensive Attention Benchmarking on Long Sequence Modeling](https://mlsanity.com/paper/2210.07661/) (2022)
- [Faster Nearest Neighbor Machine Translation](https://mlsanity.com/paper/2112.08152/) (2021)
- [ChatGPT-Like Large-Scale Foundation Models for Prognostics and Health Management: A Survey and Roadmaps](https://mlsanity.com/paper/2305.06472/) (2023)
- [Sparse Attentive Memory Network for Click-through Rate Prediction with Long Sequences](https://mlsanity.com/paper/2208.04022/) (2022)
- [BLaST: High Performance Inference and Pretraining using BLock Sparse Transformers](https://mlsanity.com/paper/2507.03117/) (2025)

## Abstract (arXiv)

While the self-attention mechanism has been widely used in a wide variety of tasks, it has the unfortunate property of a quadratic cost with respect to the input length, which makes it difficult to deal with long inputs. In this paper, we present a method for accelerating and structuring self-attentions: Sparse Adaptive Connection (SAC). In SAC, we regard the input sequence as a graph and attention operations are performed between linked nodes. In contrast with previous self-attention models with pre-defined structures (edges), the model learns to construct attention edges to improve task-specific performances. In this way, the model is able to select the most salient nodes and reduce the quadratic complexity regardless of the sequence length. Based on SAC, we show that previous variants of self-attention models are its special cases. Through extensive experiments on neural machine translation, language modeling, graph representation learning and image classification, we demonstrate SAC is competitive with state-of-the-art models while significantly reducing memory cost.