Lune

ICML2022Top-tier venue

What Dense Graph Do You Need for Self-Attention?

Yuxin Wang, Chu-Tak Lee, Qipeng Guo, Zhangyue Yin, Yunhua Zhou, Xuanjing Huang, Xipeng Qiu

Abstract

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(N log N ) complexity with sequence length N . Experiments on tasks requiring various sequence lengths lay validation for our graph function well 1 .

Ask Lune

Know this paper in minutes, not an afternoon.

Lune can read every page of it and the top-tier papers that cite it, and gives you its claims, its evidence and its limits, each one cited to the paper it comes from. No skimming, no AI slop.

3 top-tier papers have cited it since. Know what they found before your reviewers do.

Questions to start from

Lune can draw on

the full paper · the top-tier papers that cite it · related work

Get the answer

Free to start. No credit card required.

Lineage

  • Long Range Arena : A Benchmark for Efficient Transformers cites Big Bird: Transformers for Longer Sequences
  • Efficient Attention via Control Variates cites Long Range Arena : A Benchmark for Efficient Transformers
  • Efficient Attention via Control Variates cites Big Bird: Transformers for Longer Sequences
  • Efficient Attention via Control Variates cites An Image is Worth 16x16 Words: Transformers for Image Recognition at Scale
  • Efficient Attention via Control Variates cites Nyströmformer: A Nyström-based Algorithm for Approximating Self-Attention
  • Nyströmformer: A Nyström-based Algorithm for Approximating Self-Attention cites Long Range Arena : A Benchmark for Efficient Transformers
  • Training-free Diffusion Model Adaptation for Variable-Sized Text-to-Image Synthesis cites Big Bird: Transformers for Longer Sequences
  • Tokens-to-Token ViT: Training Vision Transformers from Scratch on ImageNet cites An Image is Worth 16x16 Words: Transformers for Image Recognition at Scale
Builds onCited byLeft to right by year; the more cited, the higher.

Cited by top-tier papers3

  1. Training-free Diffusion Model Adaptation for Variable-Sized Text-to-Image SynthesisZhiyu Jin, Xuli Shen, Bin Li, Xiangyang XueNeurIPS 2023 · 72 citations
  2. Efficient Attention via Control VariatesLin Zheng, Jianbo Yuan, Chong Wang, Lingpeng KongICLR 2023 · 2 citations
  3. A Capacity-Based Rationale for Multi-Head AttentionMicah AdlerICML 2026 · 2 citations

Builds on7

  1. An Image is Worth 16x16 Words: Transformers for Image Recognition at ScaleAlexey Dosovitskiy, Lucas Beyer, Alexander Kolesnikov, Dirk Weissenborn et al.ICLR 2021 · 21,477 citations
  2. Big Bird: Transformers for Longer SequencesManzil Zaheer, Guru Guruganesh, Kumar Avinava Dubey, Joshua Ainslie et al.NeurIPS 2020 · 3,159 citations
  3. Tokens-to-Token ViT: Training Vision Transformers from Scratch on ImageNetLi Yuan, Yunpeng Chen, Tao Wang, Weihao Yu et al.ICCV 2021 · 2,462 citations
  4. Long Range Arena : A Benchmark for Efficient TransformersYi Tay, Mostafa Dehghani, Samira Abnar, Yikang Shen et al.ICLR 2021 · 881 citations
  5. Nyströmformer: A Nyström-based Algorithm for Approximating Self-AttentionYunyang Xiong, Zhanpeng Zeng, Rudrasis Chakraborty, Mingxing Tan et al.AAAI 2021 · 675 citations

Related papers

  1. O(n) Connections are Expressive Enough: Universal Approximability of Sparse TransformersChulhee Yun, Yin-Wen Chang, Srinadh Bhojanapalli, Ankit Singh Rawat et al.NeurIPS 2020 · 111 citations
  2. NAGphormer: A Tokenized Graph Transformer for Node Classification in Large GraphsJinsong Chen, Kaiyuan Gao, Gaichao Li, Kun HeICLR 2023 · 22 citations
  3. Transformers Generalize DeepSets and Can be Extended to Graphs & HypergraphsJinwoo Kim, Saeyoon Oh, Seunghoon HongNeurIPS 2021 · 48 citations
  4. Even Sparser Graph TransformersHamed Shirzad, Honghao Lin, Balaji Venkatachalam, Ameya Velingker et al.NeurIPS 2024 · 18 citations
  5. SparseFlow: Accelerating Transformers by Sparsifying Information FlowsYeachan Kim, SangKeun LeeACL 2024 · 1 citation
Dusk over the sea between two cliffs drawn in fine vertical lines