From Attention to IO-Aware Execution: Transformer Computational Structure, Complexity, and Verifiable Analysis

1. First identify the bottleneck being changed

Within a single sample, recurrent sequence models generally need to update their states sequentially along temporal positions. The original Transformer supplements ordering information with positional representations and then allows multiple positions to exchange content through attention. It shortens information paths between distant positions and expands the scope for parallelism across positions during training. Autoregressive decoding, however, still depends on previously generated tokens; parallelizable training does not mean that an entire answer can be generated simultaneously.[1] Attention Is All You Need

2. Q, K, and V are computational roles

Scaled dot-product attention can be written as $$\operatorname{softmax}\!\left(\frac{QK^{\mathsf T}}{\sqrt{d_k}}\right)V$$Q and K form matching scores, softmax normalizes the scores, and the resulting weights are applied to V. The multi-head mechanism performs this operation separately in different projection subspaces and then combines the results. These names describe the vectors' roles in computation; they do not imply that the model possesses “question,” “memory,” or “understanding” modules that correspond directly to human cognition.[1] Attention Is All You Need

3. Performance numbers must retain their experimental context

The original paper reports that Transformer big achieved 28.4 BLEU in its English-to-German WMT 2014 experiment. This number belongs to a particular configuration of data, tokenization, training, decoding, and scoring; it is not evidence of the capabilities of modern general-purpose language models. This article does not compare English-to-French scores across papers: the abstracts, tables, and main text of accessible versions contain differing formulations, and combining them would create a precision in the conclusions that is not warranted.[1] Attention Is All You Need

4. Why long contexts are expensive

Full attention establishes$n\times n$pairs on a sequence of length n. If float32 scores are explicitly stored for a single layer and a single head, the byte count is$n^2\times4$, and doubling the length quadruples this term. Figure 2 in this version uses a different, explicit configuration: FP16 scores for 32 heads, compared separately with a cache spanning 32 layers and 8 KV heads; these two accounting schemes must not be conflated into a single peak device-memory figure. Gradients, projections, activations, and kernel workspaces must be counted separately.[1] Attention Is All You Need[2] FlashAttention: Fast and Memory-Efficient Exact Attenti

5. Two optimizations answer different questions

Longformer changes which positions need to interact, using local windows and selective global attention to process long documents. FlashAttention instead rearranges computation around the memory hierarchy, using tiling and fusion to reduce high-bandwidth device-memory accesses while preserving the exact attention it defines. The former modifies connectivity; the latter optimizes how the same computation is executed. IO optimization must not be described as eliminating all quadratic computation.[3] Longformer: The Long-Document Transformer[2] FlashAttention: Fast and Memory-Efficient Exact Attenti

6. A verifiable analytical example

As an example of accounting for single-layer, single-head float32 scores, lengths of 512, 1024, 2048, and 4096 require 1, 4, 16, and 64 MiB, respectively,$1\,\mathrm{MiB}=2^{20}$bytes. This differs from the configuration in Figure 2 of this version; the numbers come from formulas, not GPU measurements. If the implementation processes blocks without writing the full scores back to high-bandwidth memory, the actual peak will change, so the execution strategy must be checked before interpreting the trend.[1] Attention Is All You Need[2] FlashAttention: Fast and Memory-Efficient Exact Attenti

7. How to compare a “faster” approach

This article recommends separately reporting training sample length, batch size, precision, device, warm-up, throughput, time to first token, and peak device memory, with comparisons made under the same quality target. If one approach truncates the context while another retains the entire input, the speed difference includes a change in the task; if one uses a fused kernel and another a naive implementation, the difference likewise cannot be attributed entirely to architecture. This is a recommendation for experimental design, not a new experimental result from this article.作者分析与复核建议 / Author analysis

An easily overlooked computational boundary

The attention-score $n^2$ term describes only interactions between positions; projections and position-wise feed-forward operations still have their own computational costs. At a fixed sequence length, increasing the hidden dimension changes the relative contributions of these terms; at a fixed dimension, lengthening the sequence makes position pairing more important. Thus, the statement that “attention has quadratic complexity” alone cannot predict the share of runtime spent in each part of the whole model. Model dimensions and inputs should be specified before interpreting actual profiling results.作者分析与复核建议 / Author analysis

8. Sufficient statistics for blockwise softmax

For a row of scores, directly computing the sum of exponentials can readily overflow; subtracting the maximum changes only the normalization representation, not the probabilities. When processing a new block, there is no need to retain all previous scores: only the running maximum m, the normalization denominator l, and the weighted sum u before division by the denominator are needed. After bringing the old and new blocks to a common new maximum m′, the previous accumulators are rescaled by exp(m−m′). Numerator and denominator are transformed together, and u/l ultimately gives the output for that row. This derivation explains why reducing transfers to and from device memory need not change attention connectivity; however, the floating-point summation order changes, so numerical equivalence must still be verified within an agreed tolerance.[1] Attention Is All You Need[2] FlashAttention: Fast and Memory-Efficient Exact Attenti

9. Training memory and decoding caches should be modeled separately

Explicit score storage grows with the number of position pairs; the KV cache instead retains keys and values from previous positions at every layer. Assuming L layers, n positions, h_kv KV heads, head dimension d_h, and b bytes per scalar, the cache is approximately 2Lnh_kv d_h b. This expression excludes weights, workspaces, and allocator fragmentation. Reducing the number of KV heads can reduce this term, but does not justify claiming a proportional reduction in training attention operations. Prefill for long prompts, short-step decode, and concurrent requests should each be profiled separately, rather than reporting only a single average token/s.[1] Attention Is All You Need[2] FlashAttention: Fast and Memory-Efficient Exact Attenti

10. Why computational bottlenecks shift with workload

In an idealized roofline model, runtime is bounded below by max(F/compute throughput,B/bandwidth), where F is the operation count and B is the number of bytes actually transferred. Fusion and tiling primarily affect B; reducing connectivity primarily affects F and model expressivity. Actual kernels are also constrained by launch overhead, synchronization, occupancy, and tensor shapes, so this lower bound is not a performance predictor. For example, increasing batch size may amortize weight reads but exhaust KV capacity first; sequence growth may also change the optimal tiling. Device profiling should support a judgment that “the bottleneck has shifted,” rather than inferring speedup factors directly from asymptotic complexity.[2] FlashAttention: Fast and Memory-Efficient Exact Attenti[3] Longformer: The Long-Document Transformer

11. Long-range representation does not automatically imply long-range usability

Positional encoding determines how relative positions enter matching scores; connectivity patterns determine whether information can reach a position; and training data and tasks determine whether the model actually uses the evidence. RoPE's rotational construction can express relative displacement in inner products, but this alone does not guarantee reliability beyond training lengths. At a minimum, verification on long texts should independently vary evidence position, the number of distractors, and the distance between pieces of evidence that must be combined, while checking for shortcuts that rely only on local cues. The length limit, the ability to accept input, and the effective context for completing a task must be reported separately.[4] RoFormer: Enhanced Transformer with Rotary Position Emb[3] Longformer: The Long-Document Transformer

Core formulas and derivations

Method and evidence workflow

Analytical plots and numerical examples

Recalculable worked example

At 8192 tokens, the score matrix for a single layer with 32 heads occupies 4 GiB; the cache for 32 layers and 8 KV heads occupies 1 GiB. They have different lifetimes, so this figure cannot be treated as a peak device-memory measurement or a FlashAttention speed benchmark.

Method comparison

Verification and experimental plan

1. Fix a set of weights, a token sequence, a mask, and a random seed; record precision, device, and kernel version, and disable automatic fallbacks that would change the object of comparison.
2. First compare absolute and relative errors in forward outputs, loss, and gradients, using a small, higher-precision computation as a reference when necessary.
3. Sweep sequence length and batch size separately; warm up at each point, then time with device synchronization, reporting initial compilation overhead separately.
4. Record prefill time to first token and the distribution of per-token decode latency separately; do not obscure differences between stages with an overall average.
5. Measure peak process device memory, allocator-reserved memory, and KV occupancy together; analytical plots provide only an order-of-magnitude reference for individual components.
6. Include tasks with evidence at the beginning, middle, and end; if the faster approach changes connectivity, changes in task quality must also be reported.

Scope and limitations

• Analytical storage estimates exclude gradients, weights, and allocator fragmentation.
• Runtime must be measured on the target device and cannot be read directly from the plotted curves.
• Different connectivity patterns should be compared under the same quality constraints.
• This article did not train a new model or add a new performance benchmark.

Mapping claims to primary sources

1. Attention Is All You NeedVaswani et al. · 2017-06-12v7; sections 3-4; Table 2 (EN-DE only)
2. FlashAttention: Fast and Memory-Efficient Exact Attention with IO-AwarenessDao et al. · 2022-05-27v1; sections 2-3
3. Longformer: The Long-Document TransformerBeltagy et al. · 2020-04-10v2 abstract and architecture description
4. RoFormer: Enhanced Transformer with Rotary Position Embedding, , , , , · 2021-04-20Abstract; 原文方法、理论和实验章节见作者原始论文链接