I/O Analysis is All You Need: An I/O Analysis for Long-Sequence Attention

Self-attention over a long sequence is limited less by arithmetic than by moving data between a chip's small fast on-chip memory and its large slow off-chip memory, and while FlashAttention-style tiling reduced that traffic, the tiling was designed by hand rather than derived to be provably minimal; this paper (ICT Chinese Academy of Sciences and Illinois Institute of Technology — Xiaoyang Lu, Xiaoming Chen, Xian-He Sun, and colleagues) does a rigorous I/O analysis of the tall-and-skinny matrix multiplications that dominate long-sequence attention, uses it to derive an I/O-optimal tiling and schedule, and builds AttenIO, an accelerator that adds three-level communication-computation overlap and parallel softmax to reach 1.6 to 8.8 times the speed of prior solutions.

The argument in one glance

Problem

Long-sequence attention is bottlenecked by moving data, not by the math

Self-attention is the core operation of transformer models, and on modern accelerators its speed is decided less by how fast the chip can multiply numbers than by how fast it can move data between its small, fast on-chip memory and its large, slow off-chip memory. The reason is that attention has quadratic memory complexity in the sequence length: to relate every token to every other token, it forms a score matrix whose size grows with the square of how many tokens there are. For a long sequence that matrix is enormous, and shuttling it, along with the keys and values, in and out of off-chip memory saturates the memory system while the arithmetic units wait. So making long-sequence attention fast is fundamentally an input/output problem — minimizing the traffic between memory levels — not a compute problem.
What people did

Tile the attention so intermediates stay on-chip, FlashAttention-style

The influential response was to stop materializing the giant score matrix in off-chip memory at all: process the attention in tiles, computing the softmax incrementally as tiles stream through fast on-chip memory, so the huge intermediate never has to be written out and read back. This tiled, fused dataflow dramatically cut the memory traffic and is the state of the art for exact attention.
Why it fell short

The tiling was designed by intuition, not derived to be optimal

Tiling helps enormously, but the specific tiling and scheduling were arrived at by clever engineering intuition rather than by a rigorous analysis proving they move the least possible data. Without a principled I/O analysis, you cannot know whether a given tiling is optimal or merely good, and you cannot systematically find the best one for a particular memory hierarchy. I/O analysis itself is hard — it requires a deep understanding of both the application dataflow and the memory hierarchy — so a practical methodology to derive, rather than guess, the I/O-optimal schedule for long-sequence attention was missing, leaving performance on the table.
This paper's idea

Analyze the I/O rigorously, derive the optimal schedule, and build hardware around it

This work argues that for long-sequence attention, I/O analysis is all you need: if you understand precisely how data must move, the optimal solution follows. The authors first develop a novel I/O analysis of tall-and-skinny matrix-matrix multiplication — the shape of matrix multiply that dominates long-sequence attention, since the queries, keys, and values are long in the sequence dimension but short in the feature dimension. Guided by that analysis they build AttenIO, an accelerator for exact long-sequence self-attention with three optimizations: an analytically derived I/O-optimal tiling and scheduling that provably minimizes I/O operations, a fine-grained three-level overlapping of communication with computation to hide the I/O stalls that remain, and parallel execution patterns for computing softmax efficiently. AttenIO reaches 1.6 to 8.8 times the speed of state-of-the-art solutions, and makes the broader case that systematic I/O analysis is a principled foundation for high-performance optimization.

Why this problem is worth solving

The bottleneck has moved from arithmetic to memory movement, and attention is where it hurts most.

Modern accelerators can perform arithmetic far faster than they can feed it with data from off-chip memory, so for many workloads the binding constraint is the input/output traffic between the fast on-chip memory (small, close to the compute units) and the slow off-chip memory (large, far away). Self-attention is a stark example. It computes, for a sequence of tokens, how much each token should attend to every other, which requires forming a score matrix whose dimensions are the sequence length by the sequence length — quadratic in the number of tokens. It then normalizes those scores with a softmax and uses them to combine the value vectors. For short sequences this is manageable, but as sequence length grows into the thousands or beyond, the score matrix becomes far too large to hold on-chip, so a naive implementation writes it to off-chip memory and reads it back, and the streaming of keys and values compounds the traffic. The arithmetic, by contrast, is comparatively cheap. So the wall-clock time is set by how much data crosses between memory levels, which is why attention on long sequences is an I/O-bound problem and why reducing that data movement, rather than speeding up the multiplies, is the lever that matters.

Reducing the traffic is known to help, but knowing how much is possible requires analysis, not intuition.

I/O analysis is the study of how much data a computation must move between levels of a memory hierarchy, and what schedule of operations minimizes that movement given a fixed amount of fast memory. In principle it can give a lower bound — the least data any correct implementation could move — and a matching schedule that achieves it, turning optimization from trial and error into derivation. In practice it is difficult, because it demands a precise model of the application’s dataflow (which values are produced, consumed, and reused, and when) together with the memory hierarchy (the sizes and speeds of each level), and reconciling the two into a provably minimal schedule is intricate. The payoff, though, is large: an I/O-optimal schedule tells you not just a faster way but the best way to move the data, and it exposes exactly where remaining stalls come from so they can be hidden. For a workload as important and as I/O-bound as long-sequence attention, having a rigorous I/O analysis rather than a hand-tuned tiling means you can be confident the data movement is minimized and design the hardware to match, which is precisely the gap this work sets out to fill by analyzing the tall-and-skinny matrix multiplications at attention’s core.

What people did before, and where it broke

Naive exact attention. Compute the full score matrix, write it to off-chip memory, read it back for the softmax and the value combination. Where it broke. The quadratic score matrix and its round trips to off-chip memory saturate the memory system, so on long sequences the accelerator spends its time moving data rather than computing.
FlashAttention-style tiled, fused attention. Process attention in tiles and compute the softmax incrementally on-chip so the giant score matrix is never materialized off-chip. Where it broke. It greatly reduces traffic and is the state of the art, but its tiling and scheduling come from engineering intuition, not from an analysis proving the movement is minimal, so it may not be optimal and cannot be systematically retargeted.
General-purpose GPU execution of attention. Run the tiled attention on a GPU with its fixed memory hierarchy and scheduler. Where it broke. Without hardware and a schedule co-designed to the I/O-optimal dataflow, remaining I/O stalls and softmax inefficiencies are not fully hidden, leaving throughput below what the data movement alone would allow.
I/O analysis for generic matrix multiply. Apply classical I/O lower bounds for square matrix multiplication. Where it broke. Long-sequence attention is dominated by tall-and-skinny multiplications — long in the sequence dimension, short in the feature dimension — whose data-movement behavior differs from the square case, so an analysis tailored to that shape was needed.
The gap. No one had done a rigorous I/O analysis of the tall-and-skinny matrix multiplications that dominate long-sequence attention, derived from it an I/O-optimal tiling and schedule, and built an accelerator that both realizes that schedule and hides its residual stalls with communication-computation overlap and efficient softmax.

How AttenIO works

From an I/O analysis of tall-and-skinny matmul to an I/O-optimal attention accelerator

↓ →
new
↓ →
new
↓ →
new
↓ →
new
↓ →
new

The idea

Derive the optimal data movement instead of guessing it. The manifesto in the title is that, for an I/O-bound workload like long-sequence attention, I/O analysis is all you need — if you understand precisely how data must move through the memory hierarchy, the optimal implementation follows from the analysis rather than from trial and error. The prior state of the art reduced attention’s traffic with a cleverly tiled, fused dataflow, but its tiling was a good engineering choice, not a proven-minimal one, so there was no guarantee it moved the least possible data and no principled way to retarget it. AttenIO replaces that intuition with derivation: it analyzes the data-movement lower bound of the computation and constructs a tiling and schedule that meet it, so the movement is minimized by construction. Turning a scheduling and tiling decision into something derived from a rigorous data-movement analysis, rather than hand-tuned, is the same principled stance the dynamic-tiling work for sparse data covered elsewhere on this site takes, letting an analysis of how the data actually moves dictate how the computation is blocked instead of picking a tiling by feel. AttenIO’s contribution is to carry that principle all the way to a provably I/O-optimal schedule for attention.

Analyze the shape that actually dominates: the tall-and-skinny multiply. A rigorous I/O analysis only helps if it models the real computation, and long-sequence attention is not a generic square matrix multiply. Its query, key, and value matrices are tall and skinny — very long in the sequence dimension, because there are many tokens, but short in the feature dimension, because each token’s representation is comparatively small — and the multiplications that form and apply the score matrix inherit that shape. The data-movement behavior of a tall-and-skinny multiply differs from the square case that classical I/O bounds usually target, so AttenIO develops a novel I/O analysis specifically for it, and finds that this captures the dominant data movement of the entire attention. By analyzing the operation whose traffic actually governs the workload, the derived schedule optimizes what matters rather than a proxy. Grounding a dataflow optimization in a careful account of the specific computation’s structure and locality, rather than a generic template, is the same locality-first discipline the work on compiling to locality-aware dataflow covered elsewhere on this site is built on, where getting the data-movement model right for the actual computation is the prerequisite for a good mapping. AttenIO shows that for attention, the right model to analyze is the tall-and-skinny multiply.

Minimize the traffic, then hide what is left, and keep softmax off the critical path. An I/O-optimal schedule minimizes data movement, but it cannot make the unavoidable movement free, so AttenIO pairs the derived tiling with two mechanisms that address the residue. First, it overlaps communication with computation at a fine, three-level granularity, so that the remaining transfers between memory levels happen concurrently with useful arithmetic and their latency is hidden behind computation rather than stalling it. Second, it gives the softmax — which in exact attention must be computed carefully while data streams and can easily become a serial bottleneck between the two matrix multiplications — parallel execution patterns so it keeps pace. Together these ensure the accelerator actually runs near the rate the minimized I/O allows, rather than being throttled by exposed transfers or a slow normalization. Overlapping communication with computation so that data movement is masked behind work instead of blocking it is the same scheduling idea the communication-computation-overlap work covered elsewhere on this site is built around, arranging transfers to run in the shadow of computation. AttenIO applies it in concert with a schedule specifically derived to make that overlap as effective as possible.

Following a long-sequence attention through AttenIO

Computing exact attention over a long sequence with minimized, hidden I/O

An illustrative trace, based on the paper's abstract and standard attention background, of how AttenIO would process long-sequence attention. Internal details beyond the abstract were not available for this draft.

Step 1 of 5

A long sequence of tall-and-skinny Q, K, V matrices arrives

The query, key, and value matrices for a long sequence are long in the sequence dimension and short in the feature dimension. Forming the score matrix (queries against keys) and applying it to the values are tall-and-skinny multiplications whose data movement between memory levels dominates the runtime.

The full score matrix is quadratic in sequence length, too large to hold on-chip, which is why its traffic must be minimized rather than materialized.

Why it works

A derived schedule beats a hand-tuned one at its own game. Prior tiling was chosen by intuition and might not be minimal → but analyzing the I/O lower bound and constructing a schedule to meet it minimizes movement by construction → so AttenIO does not leave data-movement savings unclaimed.
Modeling the tall-and-skinny shape optimizes the real bottleneck. Classical square-matrix I/O bounds do not match attention’s shape → but a novel analysis of tall-and-skinny multiplication captures its dominant data movement → so the derived schedule optimizes the traffic that actually governs the workload.
Overlap hides the movement that cannot be removed. Even an optimal schedule must move some data on the critical path → but three-level communication-computation overlap runs those transfers concurrently with arithmetic → so the residual I/O is masked and the accelerator runs near its I/O-limited rate.
Parallel softmax keeps the normalization from bottlenecking. Exact streaming softmax can serialize between the two matmuls → but parallel execution patterns compute it efficiently alongside them → so softmax does not become the new limiter once the matmul I/O is minimized.
Co-designing hardware to the analysis realizes the theory. An optimal schedule on mismatched hardware would stall → but building the accelerator around the derived dataflow → so the analytically minimal I/O translates into an actual 1.6 to 8.8 times speedup.

What it costs (trade-offs and scope)

This is a draft built from the paper’s abstract. The full paper was behind a publisher access wall for this draft (no arXiv version, no open-access or author copy located, and no web-archive snapshot), so this account is assembled from the paper’s detailed abstract and standard attention background. The exact I/O analysis and its lower-bound derivation, the precise tiling and schedule, the three-level overlap mechanism, the parallel softmax patterns, the accelerator microarchitecture, and the baselines and datasets are not reproduced here and should be read from the paper.
The reported figures are the abstract’s own, and a range. The 1.6-to-8.8-times speedup is the abstract’s reported result over state-of-the-art solutions; the specific baselines, sequence lengths, and hardware behind that range are not detailed in this draft, and a range that wide suggests the gain depends strongly on the configuration.
It targets exact long-sequence attention specifically. The analysis and accelerator are built for exact self-attention where sequences are long and the matrices are tall-and-skinny; workloads with short sequences, different matrix shapes, or approximate (sparse) attention may not see the same benefit, and the approach does not by itself reduce attention’s quadratic work, only the data movement of computing it exactly.
An I/O-optimal schedule assumes a modeled memory hierarchy. Deriving the optimal tiling depends on an accurate model of the on-chip and off-chip memory sizes and speeds; on a hierarchy that differs from the modeled one, the derived schedule may need to be re-derived, and its optimality is relative to the model’s assumptions.
It is a hardware-accelerator design. Realizing AttenIO’s benefit means the co-designed accelerator, not just a software change on an existing GPU, so the results reflect a specialized design; how much of the benefit transfers to commodity hardware following the same analysis is a question the abstract does not settle.

The evaluation

Computing exact long-sequence self-attention

Property	Naive exact attention	Tiled fused (FlashAttention-style)	AttenIO
Materializes the score matrix off-chip
How the tiling is chosen
Hides residual I/O stalls
Softmax execution
Reported outcome (per abstract)

A qualitative comparison based on the paper's abstract; the paper's main body, including its exact I/O analysis, derived tiling and schedule, overlap and softmax mechanisms, accelerator design, and specific baselines, was not available for this draft. The 1.6-to-8.8-times figure is the abstract's reported speedup over state-of-the-art solutions.Underlined values explain themselves when clicked.

Where this stops working

What to keep in mind

This is an honest draft assembled from the paper’s detailed abstract and standard self-attention background; the full text was not accessible (no arXiv preprint, no open-access or author copy found, and the ACM Digital Library version returned a bot-verification challenge), so the internal design is not reproduced. What is solid and comes directly from the abstract: long-sequence exact self-attention is dominated by I/O between on-chip and off-chip memory due to its quadratic memory complexity; I/O analysis is powerful but hard, requiring understanding of dataflow and memory hierarchy; the authors develop a novel I/O analysis of tall-and-skinny matrix-matrix multiplication that captures attention’s dominant data movement; and AttenIO applies it with three optimizations — an analytically derived I/O-optimal tiling and scheduling, fine-grained three-level communication-computation overlapping, and parallel softmax execution patterns — reaching 1.6 to 8.8 times speedup over state-of-the-art solutions. The explanation of self-attention, tall-and-skinny matrices, and tiled attention is standard background and the natural reading of the abstract, not a claim about AttenIO’s specific internals. Read the exact analysis, the derived schedule, the overlap and softmax mechanisms, the accelerator design, and the evaluation in the paper itself; treat this page as a faithful account at the level of the abstract, not of the implementation.

Background

Why data movement, not arithmetic, sets the pace

It helps to see this work as part of a decades-long shift in what limits computer performance. For a long time, making programs faster meant doing arithmetic faster, but the speed of arithmetic has outrun the speed of memory so thoroughly that for most large computations the real cost is now moving the data, not computing on it — the so-called memory wall. On modern accelerators the gap between how fast a chip can multiply and how fast it can fetch operands from off-chip memory is enormous, so a workload that touches a lot of data spends its time waiting on transfers while the arithmetic units idle. Self-attention on long sequences is a textbook case, because its quadratic intermediate is far too big to keep close to the compute. This is why so much recent systems work is really about choreographing data movement: deciding what to keep in fast memory, when to move it, and how to overlap those moves with work. AttenIO’s stance — that for such a workload the I/O analysis is the whole game and the rest follows — is a sharp statement of that shift, insisting that you optimize the movement first and derive everything else from it. This treatment of data movement through the memory hierarchy as the first-class thing to minimize is the same premise the locality-aware dataflow-compilation work covered elsewhere on this site is built on, organizing computation around where data lives and how it flows rather than around the arithmetic. AttenIO carries the premise to its logical end for attention: analyze the I/O, and optimality follows.

If you remember only three things

1. Exact self-attention over long sequences is bottlenecked by input/output — moving data between fast on-chip and slow off-chip memory — because its quadratic memory complexity makes the score matrix and the key/value streaming overwhelm the memory system while the arithmetic units wait. FlashAttention-style tiling cut this traffic by never materializing the score matrix off-chip, but its tiling and scheduling were chosen by engineering intuition rather than derived to move the provably least data, and rigorous I/O analysis (which would give the optimum) is hard because it needs a precise model of both dataflow and memory hierarchy.
2. This work argues I/O analysis is all you need: it develops a novel I/O analysis of tall-and-skinny matrix-matrix multiplication — the shape that dominates long-sequence attention, since the query, key, and value matrices are long in the sequence dimension but short in the feature dimension — and uses it to build AttenIO, an accelerator for exact long-sequence attention with three optimizations: an analytically derived I/O-optimal tiling and schedule that minimizes I/O operations, fine-grained three-level communication-computation overlap to hide residual I/O stalls, and parallel execution patterns for efficient softmax.
3. AttenIO reaches 1.6 to 8.8 times the speed of state-of-the-art solutions and makes the broader case that systematic I/O analysis is a principled foundation for high-performance optimization. This explainer is a draft written from the abstract without the paper body, so the exact I/O analysis and lower bound, the derived tiling and schedule, the overlap and softmax mechanisms, the accelerator microarchitecture, and the baselines should be confirmed against the paper; the approach targets exact long-sequence attention specifically and is a co-designed hardware accelerator.

Check yourself

Check your understanding

1. Why is computing self-attention over long sequences an input/output problem rather than a compute problem?
2. What is the limitation of FlashAttention-style tiling that this paper addresses?
3. Why does the paper analyze "tall-and-skinny" matrix multiplication specifically?
4. What should a reader keep in mind about this explainer, and what did the paper report?

Sources

The paper is “I/O Analysis is All You Need: An I/O Analysis for Long-Sequence Attention” by Xiaoyang Lu and Xian-He Sun (Illinois Institute of Technology) and Boyu Long, Xiaoming Chen, and Yinhe Han (Institute of Computing Technology, Chinese Academy of Sciences), published at ASPLOS 2026, DOI 10.1145/3779212.3790174.

This explainer is a draft. The paper’s main text was not accessible at the time of writing (there is no arXiv preprint, no open-access or author copy was located, and the ACM Digital Library PDF returned a bot-verification challenge), so it is written from the paper’s detailed abstract together with standard background on self-attention and I/O-aware computing. The abstract supplies the problem framing (optimizing I/O between on-chip and off-chip memory is increasingly critical on GPUs and accelerators; I/O analysis is complex, requiring deep understanding of application dataflow and memory hierarchy; self-attention’s quadratic memory complexity poses significant challenges to memory systems), the key contribution (a novel I/O analysis for tall-and-skinny matrix-matrix multiplication that captures the dominant data movement of long-sequence self-attention), the system (AttenIO, an I/O-driven accelerator for exact long-sequence self-attention), the three optimizations (an analytically derived I/O-optimal tiling and scheduling to minimize I/O operations, fine-grained three-level communication-computation overlapping to hide I/O stalls, and parallel execution patterns for efficient softmax), and the reported result (a 1.6 to 8.8 times speedup over state-of-the-art solutions, with the broader argument that I/O analysis is a principled foundation for high-performance I/O optimizations). The explanation of self-attention, tall-and-skinny matrices, and tiled fused attention is standard background and the natural reading of the abstract, not a claim about AttenIO’s specific internal design. The paper’s exact I/O analysis and lower-bound derivation, the precise tiling and schedule, the three-level overlap mechanism, the parallel softmax patterns, the accelerator microarchitecture, and the baselines and datasets are not reproduced here and should be read from the paper; no numbers beyond the abstract’s have been introduced.