# What Dense Graph Do You Need for Self-Attention?

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

## Key facts

- Cited by 3 papers in the map (data through 14 Oct 2026).
- Builds on 21 of its 32 references that are in the map.
- First posted on arXiv 27 May 2022.

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

- [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 Pile: An 800GB Dataset of Diverse Text for Language Modeling](https://mlsanity.com/paper/2101.00027/) (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)
- [Tokens-to-Token ViT: Training Vision Transformers from Scratch on ImageNet](https://mlsanity.com/paper/2101.11986/) (2021)
- [What Does BERT Look At? An Analysis of BERT's Attention](https://mlsanity.com/paper/1906.04341/) (2019)
- [Long Range Arena: A Benchmark for Efficient Transformers](https://mlsanity.com/paper/2011.04006/) (2020)
- [Nystr"omformer: A Nystr"om-Based Algorithm for Approximating Self-Attention](https://mlsanity.com/paper/2102.03902/) (2021)
- [Axial Attention in Multidimensional Transformers](https://mlsanity.com/paper/1912.12180/) (2019)
- [FNet: Mixing Tokens with Fourier Transforms](https://mlsanity.com/paper/2105.03824/) (2021)
- [LongT5: Efficient Text-To-Text Transformer for Long Sequences](https://mlsanity.com/paper/2112.07916/) (2021)
- [Sparse GPU Kernels for Deep Learning](https://mlsanity.com/paper/2006.10901/) (2020)
- [Utilizing BERT for Aspect-Based Sentiment Analysis via Constructing Auxiliary Sentence](https://mlsanity.com/paper/1903.09588/) (2019)
- [Star-Transformer](https://mlsanity.com/paper/1902.09113/) (2019)
- [How to Train BERT with an Academic Budget](https://mlsanity.com/paper/2104.07705/) (2021)
- [Pixelated Butterfly: Simple and Efficient Sparse training for Neural Network Models](https://mlsanity.com/paper/2112.00029/) (2021)
- [Leveraging BERT for Extractive Text Summarization on Lectures](https://mlsanity.com/paper/1906.04165/) (2019)
- [H-Transformer-1D: Fast One-Dimensional Hierarchical Attention for Sequences](https://mlsanity.com/paper/2107.11906/) (2021)
- [SparseBERT: Rethinking the Importance Analysis in Self-attention](https://mlsanity.com/paper/2102.12871/) (2021)

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

- [Training-free Diffusion Model Adaptation for Variable-Sized Text-to-Image Synthesis](https://mlsanity.com/paper/2306.08645/) (2023)
- [Efficient Attention via Control Variates](https://mlsanity.com/paper/2302.04542/) (2023)
- [Prior-Fitted Networks Scale to Larger Datasets When Treated as Weak Learners](https://mlsanity.com/paper/2503.01256/) (2025)

## Abstract (arXiv)

Transformers have made progress in miscellaneous tasks, but suffer from quadratic computational and memory complexities. Recent works propose sparse Transformers with attention on sparse graphs to reduce complexity and remain strong performance. While effective, the crucial parts of how dense a graph needs to be to perform well are not fully explored. In this paper, we propose Normalized Information Payload (NIP), a graph scoring function measuring information transfer on graph, which provides an analysis tool for trade-offs between performance and complexity. Guided by this theoretical analysis, we present Hypercube Transformer, a sparse Transformer that models token interactions in a hypercube and shows comparable or even better results with vanilla Transformer while yielding O(Nlog N) complexity with sequence length N. Experiments on tasks requiring various sequence lengths lay validation for our graph function well.