FlashBoB: I/O-Efficient Exact Backward-over-Backward for Softmax Attention

Anthony Givans, Michael Crawshaw, Mingrui LiuarXiv 2026 · arXiv

TL;DR

FlashBoB brings the memory discipline of FlashAttention to the "double backward" pass (backward-over-backward), enabling exact second-order optimization and meta-learning on long sequences. By uncovering a hierarchical affine structure in the softmax double backward, it eliminates the need to store massive $N \times N$ intermediate matrices, scaling context lengths up to 262K tokens on a single GPU while delivering up to a $6.3\times$ speedup over prior non-materializing baselines.

What Problem Does This Paper Address?

Transformers are the backbone of modern deep learning, but their core mechanism—softmax attention—suffers from quadratic memory and compute scaling with respect to sequence length ($N$). FlashAttention elegantly solved this for standard training by tiling computations and recomputing intermediate statistics on-chip (SRAM) instead of writing massive $N \times N$ matrices to off-chip high-bandwidth memory (HBM).

However, a growing class of advanced machine learning techniques requires differentiating through the backward pass itself. This operation, called backward-over-backward (BoB) or the double backward, is essential for second-order optimizers (like Sophia), meta-learning (MAML), test-time training, and gradient-based memory systems.

Standard automatic differentiation frameworks (like PyTorch) materialize huge intermediate quadratic-sized tensors during this double backward pass, leading to Out-Of-Memory (OOM) errors at modest sequence lengths (e.g., $N=8,192$). Existing custom kernels either still materialize too much data or rely on heavily synchronized hardware atomic updates that stall GPU threads.

Methods

The authors introduce FLASHBOB, an exact, I/O-efficient two-pass algorithm for softmax attention BoB.

The key mathematical breakthrough is identifying a hierarchical affine structure in the softmax double backward equations. Specifically, they show that all outputs can be determined via affine transformations driven by just two row-wise scalar vectors ($\alpha$ and $E$).

This algebraic insight allows them to collapse what would naturally be a four-pass schedule into a highly efficient two-pass tiled schedule:

  • Pass 1 (Row-Major): Processes data row by row, computes intermediate tile statistics, accumulates the row-wise scalars ($\alpha, E$), and writes out row-side outputs ($\tilde{d}(Q), \tilde{d}(dO)$).
  • Pass 2 (Column-Major): Reads the saved row scalars and streams through column blocks to finalize column-side outputs ($\tilde{d}(K), \tilde{d}(V)$) without any atomic conflicts.

By doing this, FLASHBOB keeps all $N \times N$ intermediate matrices strictly within fast on-chip SRAM, matching the theoretical I/O lower bound for forward attention.

Figure 1: FLASHBOB overview. The legend at top encodes memory tier (HBM, SRAM) and tile role; saturated text marks variables held fixed in registers, lighter text marks variables streamed through. Pass 1 holds a row block and streams column blocks to finalize the row-side outputs and write (α, E) to HBM. Across the kernel boundary, Pass 2 holds a column block, streams row blocks, reads (α, E), and writes the remaining outputs. Only two length-N vectors cross the boundary, and no N×N tensor is ever materialized in HBM.

Datasets

The authors evaluated their method using the FineWeb-derived training data (specifically the VisionTheta/fineweb-1B dataset stream, a 1-billion-token subset of the FineWeb corpus). This was used to demonstrate full-scale GPT-2 Small pre-training performance using second-order optimization.

Key Insights and Ideas

  • The Affine Fusion "Aha" Moment: The naive dependency graph of the double backward pass suggests a strict sequential dependency: $\alpha_i \rightarrow \tilde{d}(P)_{ij} \rightarrow E_i \rightarrow \tilde{d}(S)_{ij}$. This would normally force multiple separate passes over the data. Recognizing that $\alpha_i$ and $E_i$ enter later equations affinely allows the algorithm to accumulate $\alpha$-free components first and apply corrections later, fusing multiple sweeps into one.
  • Eliminating Atomics: Prior non-materializing attempts like FlashBack parallelized over rows but suffered from heavy thread contention due to synchronized global atomic updates when writing column-owned outputs. FLASHBOB completely sidesteps this by switching to a column-major traversal in its second pass, ensuring each output block is written exactly once.
  • Proving Optimality: The paper proves a tight HBM traffic upper bound of $\Theta(N^2 d^2 / M)$ and shows it matches the theoretical lower bound for forward attention, proving that FLASHBOB is asymptotically optimal under the score-recomputation model.

Key Results

  • Massive Scaling: On a single NVIDIA A100 (80GB) GPU, FLASHBOB successfully scaled to a sequence length of $N = 262,144$. In comparison, standard PyTorch OOMs at $N = 8,192$, and custom HVP baselines fail at $N = 16,384$ (see Figure 4).
  • Raw Speedups: FLASHBOB is up to $10\times$ faster than PyTorch materialization, $3.8\times$ faster than GradMem-derived kernels, and up to $6.3\times$ faster than FlashBack.
Table 1: Attention-layer BoB on NVIDIA A100 80GB. Shape: GPT-2 Small attention, batch 4, 12 heads, head dimension 64, causal mask, BF16 inputs with FP32 reductions. OOM denotes out of memory; best wall-clock time is bold.
  • Full-Model & Training Impact: When integrated into end-to-end second-order training steps for GPT-2 models on NVIDIA B200 GPUs, FLASHBOB consistently outperformed all baselines and avoided OOMs at larger context lengths (see Figure 5).
Table 2: End-to-end second-order GPT-2 step on NVIDIA B200. Batch 4, BF16 inputs with FP32 reductions. OOM denotes exceeding the measured memory budget. At small N, attention is only part of the total step; the gap widens when attention dominates runtime and memory.
  • On a 1B-token GPT-2 Small training run with the Sophia-H optimizer, FLASHBOB reduced Hessian estimation time by $2.45\times$, cut total training wall time by $2.2\times$, and reduced peak GPU memory usage by $2.2\times$ while perfectly preserving the loss trajectory.

Limitations and Future Work

  • Implementation Level: FLASHBOB is currently implemented in generic Triton. It does not yet exploit lower-level hardware specializations like warp specialization (found in FlashAttention-3) or the asymmetric scaling features of FlashAttention-4 on Blackwell architectures.
  • Head Dimension Constraints: The current implementation is highly optimized for standard head dimensions ($d \le 128$). Scaling to larger head dimensions like $d = 256$ introduces severe register and shared-memory pressure, which will require re-deriving asynchronous load schedules and warp layouts in future work.

Summary updated

Abstract

Transformer models built on the attention mechanism have become a central building block in modern deep learning, yet softmax attention remains a major bottleneck for long-context workloads. While FlashAttention makes the forward and first backward passes I/O-efficient, it does not support backward-over-backward (BoB), which enables exact differentiation through the backward pass for applications such as second-order optimization, test-time training, gradient-based memory, and meta-learning. Existing BoB implementations either materialize large intermediate tensors or exhaust GPU memory at long sequence lengths. We present FlashBoB, an exact, I/O-efficient algorithm for BoB in softmax attention that keeps computation within on-chip tiles and avoids all $N \times N$ intermediate tensors, where $N$ is the sequence length. The key insight is a hierarchical affine structure in the softmax double backward: two row-wise scalars determine all outputs through affine transformations. This yields a two-pass schedule with bounded on-chip static random-access memory (SRAM) usage and minimal off-chip high-bandwidth memory (HBM) traffic. FlashBoB achieves $Θ(N^2 d^2/M)$ HBM traffic ($d$ is the head dimension and $M$ is the memory size) and, within the standard FlashAttention-style score-recomputation model, matches the inherited large-cache lower bound for exact forward attention. Empirically, it scales exact attention BoB to $N=262\text{K}$ on a single A100 80GB GPU, where prior PyTorch exact baselines fail by $N=16\text{K}$, and is up to $6.3\times$ faster than FlashBack. These results make exact second-order attention practical at long-context sequence lengths where prior implementations cannot run efficiently.
BibTeX
@misc{givans2026flashbob,
  author = {Anthony Givans and Michael Crawshaw and Mingrui Liu},
  title = {{FlashBoB: I/O-Efficient Exact Backward-over-Backward for Softmax Attention}},
  year = {2026},
  eprint = {2609.24089},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2609.24089},
}
Figure