# Approaching I/O-optimality for Approximate Attention

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

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 20 of its 26 references that are in the map.
- First posted on arXiv 22 May 2026.

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

- [Attention Is All You Need](https://mlsanity.com/paper/1706.03762/) (2017)
- [FlashAttention: Fast and Memory-Efficient Exact Attention with IO-Awareness](https://mlsanity.com/paper/2205.14135/) (2022)
- [FlashAttention-2: Faster Attention with Better Parallelism and Work Partitioning](https://mlsanity.com/paper/2307.08691/) (2023)
- [Transformers are RNNs: Fast Autoregressive Transformers with Linear Attention](https://mlsanity.com/paper/2006.16236/) (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)
- [FlashAttention-3: Fast and Accurate Attention with Asynchrony and Low-precision](https://mlsanity.com/paper/2407.08608/) (2024)
- [Nystr"omformer: A Nystr"om-Based Algorithm for Approximating Self-Attention](https://mlsanity.com/paper/2102.03902/) (2021)
- [Fast Attention Requires Bounded Entries](https://mlsanity.com/paper/2302.13214/) (2023)
- [HyperAttention: Long-context Attention in Near-Linear Time](https://mlsanity.com/paper/2310.05869/) (2023)
- [SMYRF: Efficient Attention using Asymmetric Clustering](https://mlsanity.com/paper/2010.05315/) (2020)
- [More Asymmetry Yields Faster Matrix Multiplication](https://mlsanity.com/paper/2404.16349/) (2024)
- [Red-blue pebbling revisited: near optimal parallel matrix-matrix multiplication](https://mlsanity.com/paper/1908.09606/) (2019)
- [Optimal-Degree Polynomial Approximations for Exponentials and Gaussian Kernel Density Estimation](https://mlsanity.com/paper/2205.06249/) (2022)
- [Smoothing the gap between NP and ER](https://mlsanity.com/paper/1912.02278/) (2019)
- [Fine-Grained I/O Complexity via Reductions: New lower bounds, faster algorithms, and a time hierarchy](https://mlsanity.com/paper/1711.07960/) (2017)
- [Red-Blue Pebbling with Multiple Processors: Time, Communication and Memory Trade-offs](https://mlsanity.com/paper/2409.03898/) (2024)
- [I/O complexity and pebble games with partial computations](https://mlsanity.com/paper/2410.22237/) (2024)
- [The Impact of Partial Computations on the Red-Blue Pebble Game](https://mlsanity.com/paper/2506.10854/) (2025)

## Abstract (arXiv)

We revisit the I/O complexity of attention in large language models. Given query-key-value matrices Q,K,V∈ℝn× d, and a machine with fast memory size M, the goal is to compute the "attention matrix" A=softmax(Q K top/√d) V with the minimal number of data transfers between fast and slow memory. Existing methods in the literature, most notably FlashAttention and its variants, incur an I/O cost that depends quadratically on n, while a trivial lower bound only requires Omega(nd) I/O's to read the inputs and write the output. In this work, we present a technique for computing attention where the I/O cost only depends almost-linearly on n in most parameter regimes. This is achieved by developing I/O-efficient algorithms inspired by the recent approximate attention framework of Alman and Song. We also prove corresponding lower bounds in each parameter regime to show that our algorithms are indeed close to I/O-optimal.