# Diffuser: Efficient Transformers with Multi-hop Attention Diffusion for Long Sequences

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

## Key facts

- Cited by 12 papers in the map (data through 14 Oct 2026).
- Builds on 40 of its 54 references that are in the map.
- First posted on arXiv 21 Oct 2022.

## Builds on (most cited first, 30 of 40)

- [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)
- [RoBERTa: A Robustly Optimized BERT Pretraining Approach](https://mlsanity.com/paper/1907.11692/) (2019)
- [Longformer: The Long-Document Transformer](https://mlsanity.com/paper/2004.05150/) (2020)
- [TriviaQA: A Large Scale Distantly Supervised Challenge Dataset for Reading Comprehension](https://mlsanity.com/paper/1705.03551/) (2017)
- [REALM: Retrieval-Augmented Language Model Pre-Training](https://mlsanity.com/paper/2002.08909/) (2020)
- [Transformers are RNNs: Fast Autoregressive Transformers with Linear Attention](https://mlsanity.com/paper/2006.16236/) (2020)
- [Transformer-XL: Attentive Language Models Beyond a Fixed-Length Context](https://mlsanity.com/paper/1901.02860/) (2019)
- [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)
- [Aligning Books and Movies: Towards Story-like Visual Explanations by Watching Movies and Reading Books](https://mlsanity.com/paper/1506.06724/) (2015)
- [Predict then Propagate: Graph Neural Networks meet Personalized PageRank](https://mlsanity.com/paper/1810.05997/) (2018)
- [Conditional Image Generation with PixelCNN Decoders](https://mlsanity.com/paper/1606.05328/) (2016)
- [Long Range Arena: A Benchmark for Efficient Transformers](https://mlsanity.com/paper/2011.04006/) (2020)
- [A Generalization of Transformer Networks to Graphs](https://mlsanity.com/paper/2012.09699/) (2020)
- [Ups and Downs: Modeling the Visual Evolution of Fashion Trends with One-Class Collaborative Filtering](https://mlsanity.com/paper/1602.01585/) (2016)
- [PixelCNN++: Improving the PixelCNN with Discretized Logistic Mixture Likelihood and Other Modifications](https://mlsanity.com/paper/1701.05517/) (2017)
- [Diffusion Improves Graph Learning](https://mlsanity.com/paper/1911.05485/) (2019)
- [Are Transformers universal approximators of sequence-to-sequence functions?](https://mlsanity.com/paper/1912.10077/) (2019)
- [Efficient Attention: Attention with Linear Complexities](https://mlsanity.com/paper/1812.01243/) (2018)
- [Axial Attention in Multidimensional Transformers](https://mlsanity.com/paper/1912.12180/) (2019)
- [Random Feature Attention](https://mlsanity.com/paper/2103.02143/) (2021)
- [Diffusion-Convolutional Neural Networks](https://mlsanity.com/paper/1511.02136/) (2015)
- [Sparse Sinkhorn Attention](https://mlsanity.com/paper/2002.11296/) (2020)
- [Synthesizer: Rethinking Self-Attention in Transformer Models](https://mlsanity.com/paper/2005.00743/) (2020)
- [Constructing Datasets for Multi-hop Reading Comprehension Across Documents](https://mlsanity.com/paper/1710.06481/) (2017)
- [GraphFormers: GNN-nested Transformers for Representation Learning on Textual Graph](https://mlsanity.com/paper/2105.02605/) (2021)

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

- [A Survey on Efficient Inference for Large Language Models](https://mlsanity.com/paper/2404.14294/) (2024)
- [FlightLLM: Efficient Large Language Model Inference with a Complete Mapping Flow on FPGAs](https://mlsanity.com/paper/2401.03868/) (2024)
- [Mixture of Attention Spans: Optimizing LLM Inference Efficiency with Heterogeneous Sliding-Window Lengths](https://mlsanity.com/paper/2406.14909/) (2024)
- [KG-Rank: Enhancing Large Language Models for Medical QA with Knowledge Graphs and Ranking Techniques](https://mlsanity.com/paper/2403.05881/) (2024)
- [Rough Transformers: Lightweight and Continuous Time Series Modelling through Signature Patching](https://mlsanity.com/paper/2405.20799/) (2024)
- [Large Language Models on Wikipedia-Style Survey Generation: an Evaluation in NLP Concepts](https://mlsanity.com/paper/2308.10410/) (2023)
- [A Directional Diffusion Graph Transformer for Recommendation](https://mlsanity.com/paper/2404.03326/) (2024)
- [Rough Transformers for Continuous and Efficient Time-Series Modelling](https://mlsanity.com/paper/2403.10288/) (2024)
- [AdaCluster: Adaptive Query-Key Clustering for Sparse Attention in Video Generation](https://mlsanity.com/paper/2604.18348/) (2026)
- [HiPool: Modeling Long Documents Using Graph Neural Networks](https://mlsanity.com/paper/2305.03319/) (2023)
- [Long Sequence Modeling with Attention Tensorization: From Sequence to Tensor Learning](https://mlsanity.com/paper/2410.20926/) (2024)
- [Unveiling the Secret of AdaLN-Zero in Diffusion Transformer](https://mlsanity.com/paper/2608.09438/) (2026)

## Abstract (arXiv)

Efficient Transformers have been developed for long sequence modeling, due to their subquadratic memory and time complexity. Sparse Transformer is a popular approach to improving the efficiency of Transformers by restricting self-attention to locations specified by the predefined sparse patterns. However, leveraging sparsity may sacrifice expressiveness compared to full-attention, when important token correlations are multiple hops away. To combine advantages of both the efficiency of sparse transformer and the expressiveness of full-attention Transformer, we propose textitDiffuser, a new state-of-the-art efficient Transformer. Diffuser incorporates all token interactions within one attention layer while maintaining low computation and memory costs. The key idea is to expand the receptive field of sparse attention using Attention Diffusion, which computes multi-hop token correlations based on all paths between corresponding disconnected tokens, besides attention among neighboring tokens. Theoretically, we show the expressiveness of Diffuser as a universal sequence approximator for sequence-to-sequence modeling, and investigate its ability to approximate full-attention by analyzing the graph expander property from the spectral perspective. Experimentally, we investigate the effectiveness of Diffuser with extensive evaluations, including language modeling, image modeling, and Long Range Arena (LRA). Evaluation results show that Diffuser achieves improvements by an average of 0.94% on text classification tasks and 2.30% on LRA, with 1.67× memory savings compared to state-of-the-art benchmarks, which demonstrates superior performance of Diffuser in both expressiveness and efficiency aspects.