What Lost, and Why

Most of this book is about what won. This chapter is about what lost, because the failures are more instructive than the successes — they're the clearest evidence for the thesis I started with, that on real hardware the budget that binds is memory bandwidth, not asymptotic FLOP count. A whole research program optimized the wrong quantity, and lost to a technique that left the asymptotics untouched.

The subquadratic attention program#

Attention is $O(N^2)$ in sequence length. Between roughly 2019 and 2022 this looked like the problem to solve, and dozens of papers attacked the exponent:

• Sparse attention (Sparse Transformer, Longformer, BigBird) — each token attends to a fixed pattern (local window + a few global tokens) instead of all tokens, giving $O(N)$ or $O(N \log N)$.Beltagy et al., Longformer, 2020; Zaheer et al., Big Bird, NeurIPS 2020.
• Low-rank / kernel methods (Linformer, Performer) — approximate the attention matrix as low-rank, or replace softmax with a kernel feature map that allows linear-time association.Wang et al., Linformer, 2020; Choromanski et al., Rethinking Attention with Performers, ICLR 2021.
• Hashing (Reformer) — use locality-sensitive hashing so each token attends only to likely-relevant others.
• Dilated attention (LongNet) — expanding receptive fields across layers, claiming linear scaling to a billion tokens.

Each achieved its complexity target. And for training and serving the models people actually deployed, essentially none of them mattered. What happened?

Why they lost#

Three reasons, all of which this book has already armed you to see.

The constant was the problem, not the exponent. From chapter 1, a technique's real cost is FLOPs and bytes moved, weighted by where it lands on the roofline. Standard attention was slow not because it did too many FLOPs but because it wrote the $N \times N$ score matrix to HBM and read it back — it was bandwidth-bound. Flash attention fixed that — kept the matrix in SRAM, exact — and delivered a bigger practical speedup than most of the approximations, at the sequence lengths people trained on. The approximations were solving a complexity problem the hardware didn't actually have yet.

The approximations cost quality, and quality is unforgiving. Sparse and low-rank attention drop or blur real token interactions. At the 2k–8k contexts that dominated, the full $O(N^2)$ was affordable and better, so why accept a worse model to save compute you could afford? The exact method that was also fast dominated the approximate methods that were slightly faster.

Crossover happens later than the asymptotics suggest. An $O(N)$ method with a large constant beats $O(N^2)$ only past some crossover $N$, and for these the crossover sat beyond the context lengths in use. By the time context lengths grew enough to matter, flash attention had moved the $O(N^2)$ constant down far enough to push the crossover further still.

This is, I think, the single most useful strategic lesson in the book: big-O is a statement about the limit, and you do not train at the limit. Constants, memory traffic, and the actual hardware are what determine the winner in the regime you operate in. A technique with a worse complexity class and a better constant beats a better complexity class with a worse constant, right up until the problem gets big enough — and "big enough" is often bigger than you'll ever reach.

The twist: they're coming back#

The honest update, because the story didn't end in 2022. As context lengths push toward millions of tokens for genuine use cases — whole codebases, long documents, extended agent histories — the crossover point is finally being reached, and sparse attention is returning, this time built with flash attention's IO-awareness baked in rather than bolted on:

• DeepSeek NSA (Native Sparse Attention) — trainable hierarchical sparse attention with hardware-aligned kernels, designed for the constants from the start.Yuan et al., Native Sparse Attention: Hardware-Aligned and Natively Trainable Sparse Attention, 2025.
• MoBA (Mixture of Block Attention) — applies MoE-style routing to attention blocks, letting each query attend to a learned-relevant subset.Lu et al., MoBA: Mixture of Block Attention for Long-Context LLMs, 2025.

The lesson isn't that sparse attention was wrong. It's that it was early, and that it was measured against the wrong constant. The ideas were sound; the regime hadn't arrived, and the baseline they had to beat got much faster before it did. Right idea, wrong decade — which is its own kind of lesson about what "lost" even means in this field.

One more casualty worth a mention#

Sequence packing deserves a note, because it's a case of a good idea with a sharp edge. To avoid wasting compute on padding, you concatenate multiple short training sequences into one long one — more real tokens per micro-batch, higher utilization. The trap: if attention isn't masked correctly at the document boundaries, tokens from one document attend to tokens from another, and the model quietly learns from cross-document leakage. The fix is block-diagonal attention masks that reset at each boundary (flash attention supports these via cu_seqlens), and the reason it's worth mentioning is that getting the masking subtly wrong is a bug that improves your loss curve — the model exploits the leaked information — while degrading the actual model. Efficiency bugs that look like wins are the most dangerous kind, and this is the canonical one.

Where this leaves you#

Every technique in this book is one move: spend the budget you have to buy back the budget that binds. Memory, compute, bandwidth — pick which you're out of, pay in one of the others, and know the exchange rate. That's the whole discipline, and it's why I wanted to write the derivations out rather than leave them as a list of names. The names are easy. The exchange rates are the job.

Thanks for reading to the end.

Credits#

This book began as an expansion of Gauri Gupta's LLM Optimization Notes: Memory, Compute & Inference Techniques (archived), a compact and genuinely useful index of this material. Her outline is the skeleton this book put flesh on; the derivations, arithmetic, and errors are mine. If you found this useful, her original is the right place to see the whole map at a glance.

References#

Organized by chapter. Everything here was written from these primary sources rather than from secondary summaries.

Roofline & fundamentals

• Williams, Waterman & Patterson. Roofline: An Insightful Visual Performance Model for Multicore Architectures. CACM, 2009.
• Kaplan et al. Scaling Laws for Neural Language Models. 2020.

Memory & checkpointing

• Micikevicius et al. Mixed Precision Training. ICLR, 2018.
• Chen et al. Training Deep Nets with Sublinear Memory Cost. 2016.
• Korthikanti et al. Reducing Activation Recomputation in Large Transformer Models. MLSys, 2023.
• Dettmers et al. 8-bit Optimizers via Block-wise Quantization. ICLR, 2022.

Attention & the KV cache

• Milakov & Gimelshein. Online normalizer calculation for softmax. 2018.
• Rabe & Staats. Self-attention Does Not Need $O(n^2)$ Memory. 2021.
• Dao et al. FlashAttention: Fast and Memory-Efficient Exact Attention with IO-Awareness. NeurIPS, 2022.
• Dao. FlashAttention-2. 2023.
• Shah et al. FlashAttention-3. NeurIPS, 2024.
• Shazeer. Fast Transformer Decoding: One Write-Head is All You Need. 2019.
• Ainslie et al. GQA: Training Generalized Multi-Query Transformer Models. EMNLP, 2023.
• DeepSeek-AI. DeepSeek-V2 and DeepSeek-V3 Technical Report. 2024.
• Kwon et al. Efficient Memory Management for LLM Serving with PagedAttention. SOSP, 2023.
• Zheng et al. SGLang: Efficient Execution of Structured Language Model Programs. NeurIPS, 2024.

Quantization

• Dettmers et al. LLM.int8(). NeurIPS, 2022.
• Xiao et al. SmoothQuant. ICML, 2023.
• Frantar et al. GPTQ. ICLR, 2023.
• Lin et al. AWQ. MLSys, 2024.
• Dettmers et al. QLoRA. NeurIPS, 2023.

Parallelism

• Rajbhandari et al. ZeRO: Memory Optimizations Toward Training Trillion Parameter Models. SC, 2020.
• Shoeybi et al. Megatron-LM. 2019.
• Huang et al. GPipe. NeurIPS, 2019.
• Narayanan et al. PipeDream. SOSP, 2019.
• Qi et al. Zero Bubble Pipeline Parallelism. ICLR, 2024.
• Liu et al. Ring Attention with Blockwise Transformers. 2023.
• Shazeer et al. Outrageously Large Neural Networks (Sparsely-Gated MoE). 2017.
• Fedus et al. Switch Transformers. 2021.
• Grattafiori et al. The Llama 3 Herd of Models. 2024.

Serving & speculative decoding

• Yu et al. Orca: A Distributed Serving System for Transformer-Based Generative Models. OSDI, 2022.
• Agrawal et al. Sarathi-Serve. OSDI, 2024.
• Zhong et al. DistServe. OSDI, 2024.
• Leviathan et al. Fast Inference from Transformers via Speculative Decoding. ICML, 2023.
• Chen et al. Accelerating LLM Decoding with Speculative Sampling. 2023.
• Cai et al. Medusa. 2024.

The efficient-attention postmortem

• Beltagy et al. Longformer. 2020.
• Zaheer et al. Big Bird. NeurIPS, 2020.
• Wang et al. Linformer. 2020.
• Choromanski et al. Rethinking Attention with Performers. ICLR, 2021.
• Yuan et al. Native Sparse Attention. 2025.
• Lu et al. MoBA: Mixture of Block Attention. 2025.