I/O Complexity Analysis of Transformer Architectures

Transformer architectures have achieved epochal results across a high number of applications but their runtime performance has become increasingly influenced by the cost of moving data across the memory hierarchy. This thesis studies the I/O complexity of Transformers on a two-level memory model aiming to understand how different algorithms and execution schedules can affect communication costs. The analysis begins with attention where we analyze known communication bounds and I/O-aware implementations such as FlashAttention to then extend to the other main components of the Transformer block. For feed-forward networks, we derive a fused execution schedule that reduces intermediate data movement and we specify its communication cost. The main contribution of the thesis is a model-specific I/O analysis of a complete Transformer block: by combining results for individual components with a decomposition argument, we obtain a specific lower bound and compare it with derived upper bounds, also identifying regimes in which the bounds match. We also study sequences of Transformer blocks, compare materialized and activation-resident execution strategies and quantify the potential benefit of preserving intermediate activations across layers, but we deliberately avoid claims of general optimality.