aiml

Lesson 7 of 20Module 2

Explain tiled attention and verify its output

Implement tiled attention with online softmax on the CPU. Verify numerical agreement and distinguish storage savings from measured GPU runtime.

Prerequisites

Python, basic causal attention, and the preceding inference lessons.

By the end, you can

  • Explain tiled attention and verify its output.
  • Explain why a new tile maximum requires rescaling both accumulated softmax state and weighted values.
  • Preserve attention output while rescaling state between softmax tiles.
Runtime
Python 3.12+
Dependencies
Standard library only

Lab code, tests and fixtures (ZIP, 90 KB)Quiz check your understanding

Progress is saved in this browser.

When you need this. A document assistant needs longer context, and the attention score matrix grows much faster than its input. Implement an online softmax that processes tiles without retaining the full matrix, then compare its outputs with a direct reference.

What you run. A CPU attention implementation and a logical-access count, compared with a direct numerical reference. The lab runs no FlashAttention GPU benchmark and measures no HBM traffic.

This lesson builds on implement paged cache allocation and copy-on-write.

Keep the softmax state between tiles

Attention weights come from scaled query-key scores followed by softmax. The direct reference retains the scores and probabilities before multiplying by values. The tiled algorithm keeps a running maximum, normalization sum, and output accumulator for each query row.

When a later tile has a larger maximum, rescale both the old normalization sum and the old output accumulator. Otherwise the tiles use incompatible exponential scales. With both rescaled, the tiled result matches the direct calculation up to floating-point rounding. Tiling does not remove the quadratic work of attention.

Query and KV tilesOnline softmaxRunning row statetile scoresupdate stateread stateQuery and KV tilesOnline softmaxRunning row statetile scoresupdate stateread state
The return path represents state used by the next operation; the article distinguishes actual model state from the lab’s inspectable data structures.

tiled_flash_attention() is a readable CPU implementation of the online-softmax mechanism. The tests compare it with standard_attention() under causal masking and with irregular tile sizes. The access calculator counts the repeated K/V reads of its loop order, so it does not assume that each tensor is read from device memory only once.

Follow one query row in the supplied 64-position input with head width 16. The implementation visits keys and values in tiles of 16 positions. Each tile updates that row’s running maximum, normalization sum and weighted output; the direct reference computes the same row with the complete score matrix.

Compare the attention outputs

Download the lab from this page, extract it, and run these commands from its directory. python3 lab.py runs the CPU algorithm on generated inputs and prints a JSON report. It downloads no model and calls no API.

Run the local analysis and checksTerminal · bash
python3 lab.py
python3 -m unittest -v test_lab.py
Read lab.py
lab.pySource · pythonDownload
"""Compare dense and tiled CPU attention with online softmax; device traffic is not measured."""

from __future__ import annotations

import json
import math
import random


def make_qkv(
    seq_len: int,
    head_dim: int,
    seed: int = 42,
) -> tuple[list[list[float]], list[list[float]], list[list[float]]]:
    rng = random.Random(seed)
    q = [[rng.uniform(-0.8, 0.8) for _ in range(head_dim)] for _ in range(seq_len)]
    k = [[rng.uniform(-0.8, 0.8) for _ in range(head_dim)] for _ in range(seq_len)]
    v = [[rng.uniform(-0.8, 0.8) for _ in range(head_dim)] for _ in range(seq_len)]
    return q, k, v


def dot(a: list[float], b: list[float]) -> float:
    return sum(x * y for x, y in zip(a, b))


def standard_attention(
    q: list[list[float]],
    k: list[list[float]],
    v: list[list[float]],
    causal: bool = True,
    subtract_max: bool = True,
) -> tuple[list[list[float]], dict[str, int]]:
    """Materializes the full N x N score and probability matrices before multiplying by V."""
    n = len(q)
    d = len(q[0])
    scale = 1.0 / math.sqrt(d)

    # 1. Compute S = Q K^T * scale (materialized N x N in HBM)
    scores: list[list[float]] = []
    for i in range(n):
        limit = (i + 1) if causal else n
        row_scores = [dot(q[i], k[j]) * scale for j in range(limit)]
        scores.append(row_scores)

    # 2. Row-wise softmax P = softmax(S) (materialized N x N in HBM)
    probs: list[list[float]] = []
    for row_scores in scores:
        m = max(row_scores) if subtract_max else 0.0
        exps = [math.exp(s - m) for s in row_scores]
        denom = sum(exps)
        probs.append([e / denom for e in exps])

    # 3. Output O = P V
    out: list[list[float]] = []
    for i in range(n):
        row_out = [0.0] * d
        for j, p_ij in enumerate(probs[i]):
            for col in range(d):
                row_out[col] += p_ij * v[j][col]
        out.append(row_out)

    materialized_nxn_elements = sum(len(r) for r in scores) + sum(len(r) for r in probs)
    return out, {"materialized_nxn_elements": materialized_nxn_elements}


def tiled_flash_attention(
    q: list[list[float]],
    k: list[list[float]],
    v: list[list[float]],
    block_q: int = 16,
    block_kv: int = 16,
    causal: bool = True,
    rescale_previous_acc: bool = True,
) -> tuple[list[list[float]], dict[str, int]]:
    """Tiles Q, K, and V in SRAM using online softmax without materializing N x N in HBM."""
    n = len(q)
    d = len(q[0])
    scale = 1.0 / math.sqrt(d)
    out: list[list[float]] = [[0.0] * d for _ in range(n)]
    sram_tile_score_peak = block_q * block_kv
    tiles_visited = 0

    for q_start in range(0, n, block_q):
        q_end = min(q_start + block_q, n)
        q_rows = q_end - q_start
        running_max = [-math.inf] * q_rows
        running_sum = [0.0] * q_rows
        output_acc = [[0.0] * d for _ in range(q_rows)]

        for kv_start in range(0, n, block_kv):
            if causal and kv_start >= q_end:
                break
            kv_end = min(kv_start + block_kv, n)
            tiles_visited += 1

            for local_i in range(q_rows):
                global_i = q_start + local_i
                valid_kv_indices = [
                    j for j in range(kv_start, kv_end) if (not causal or j <= global_i)
                ]
                if not valid_kv_indices:
                    continue

                tile_scores = [dot(q[global_i], k[j]) * scale for j in valid_kv_indices]
                tile_max = max(tile_scores)
                prev_max = running_max[local_i]
                new_max = max(prev_max, tile_max)

                # Rescale factor for previous running_sum and output_acc
                alpha = math.exp(prev_max - new_max) if prev_max > -math.inf else 0.0
                tile_exps = [math.exp(s - new_max) for s in tile_scores]
                tile_sum = sum(tile_exps)

                running_sum[local_i] = running_sum[local_i] * alpha + tile_sum
                acc_scale = alpha if rescale_previous_acc else 1.0
                for col in range(d):
                    acc_val = output_acc[local_i][col] * acc_scale
                    for exp_val, j in zip(tile_exps, valid_kv_indices):
                        acc_val += exp_val * v[j][col]
                    output_acc[local_i][col] = acc_val

                running_max[local_i] = new_max

        for local_i in range(q_rows):
            global_i = q_start + local_i
            inv_sum = 1.0 / running_sum[local_i]
            out[global_i] = [val * inv_sum for val in output_acc[local_i]]

    return out, {
        "materialized_nxn_elements": 0,
        "max_sram_score_tile_elements": sram_tile_score_peak,
        "tiles_visited": tiles_visited,
    }


def max_abs_diff(a: list[list[float]], b: list[list[float]]) -> float:
    return max(abs(x - y) for row_a, row_b in zip(a, b) for x, y in zip(row_a, row_b))


def estimate_hbm_bytes(
    seq_len: int,
    num_heads: int = 32,
    head_dim: int = 128,
    bytes_per_elem: int = 2,
    block_q: int = 128,
    block_kv: int = 128,
) -> dict[str, object]:
    """Compare single-layer multi-head attention HBM traffic for standard vs FlashAttention."""
    qkv_o_bytes = 4 * num_heads * seq_len * head_dim * bytes_per_elem
    # Standard attention writes S (N x N), reads S, writes P (N x N), reads P across all heads
    attention_matrix_rw_bytes = 4 * num_heads * (seq_len * seq_len) * bytes_per_elem
    standard_total_bytes = qkv_o_bytes + attention_matrix_rw_bytes

    # Logical tensor accesses for causal outer-Q tiling, assuming no inter-block cache reuse.
    # Hardware HBM traffic requires profiling; this is an access-count model.
    num_q_blocks = math.ceil(seq_len / block_q)
    kv_rows_read = sum(
        min(seq_len, start + block_q) for start in range(0, seq_len, block_q)
    )
    tiled_bytes = (
        2 * num_heads * seq_len * head_dim + 2 * num_heads * kv_rows_read * head_dim
    ) * bytes_per_elem
    return {
        "seq_len": seq_len,
        "num_heads": num_heads,
        "head_dim": head_dim,
        "standard_qkv_o_mb": round(qkv_o_bytes / 1e6, 2),
        "standard_nxn_matrix_hbm_mb": round(attention_matrix_rw_bytes / 1e6, 2),
        "standard_total_hbm_mb": round(standard_total_bytes / 1e6, 2),
        "tiled_logical_access_mb_no_cache_reuse": round(tiled_bytes / 1e6, 2),
        "qkvo_compulsory_bytes_mb": round(qkv_o_bytes / 1e6, 2),
        "num_q_blocks": num_q_blocks,
        "accounting": "logical accesses, not measured HBM traffic; dense baseline and causal tiled loop differ in work",
    }


def build_report() -> dict[str, object]:
    q, k, v = make_qkv(seq_len=64, head_dim=16, seed=42)
    std_out, std_meta = standard_attention(q, k, v, causal=True)
    flash_out, flash_meta = tiled_flash_attention(
        q, k, v, block_q=16, block_kv=16, causal=True
    )
    diff = max_abs_diff(std_out, flash_out)

    hbm_sweep = [
        estimate_hbm_bytes(seq_len=n, num_heads=32, head_dim=128, bytes_per_elem=2)
        for n in (1024, 4096, 16384, 32768)
    ]

    return {
        "equivalence_check": {
            "seq_len": 64,
            "head_dim": 16,
            "block_q": 16,
            "block_kv": 16,
            "max_abs_diff": float(f"{diff:.3e}"),
            "standard_materialized_elements": std_meta["materialized_nxn_elements"],
            "flash_materialized_hbm_elements": flash_meta["materialized_nxn_elements"],
            "flash_sram_tile_elements": flash_meta["max_sram_score_tile_elements"],
            "flash_tiles_visited": flash_meta["tiles_visited"],
            "sample_row0_first4": [round(x, 6) for x in flash_out[0][:4]],
            "sample_last_row_first4": [round(x, 6) for x in flash_out[-1][:4]],
        },
        "hbm_traffic_sweep": hbm_sweep,
    }


def main() -> None:
    print(
        json.dumps(
            {
                "execution_mode": "CPU algorithm with controlled inputs; any latency/capacity coefficients are assumptions",
                **build_report(),
            },
            indent=2,
        )
    )


if __name__ == "__main__":
    main()

The output comparison checks the attention calculation. In this lab, treat a max_abs_diff above rounding error as a bug in the tiled loop; the tests require a difference below 1e-12. The hbm_traffic_sweep entries are calculated separately and do not depend on that comparison. They count logical accesses for a causal 128-position tiling, including repeated K/V reads, next to a dense-baseline estimate. They do not measure GPU memory traffic.

QuantityRecorded value
Maximum numerical difference1.388e-16
Reference retained score/probability elements4160
Tiled retained full-matrix elements0
Tiles visited10
Inspect the complete local result
Recorded local resultRecorded output · jsonDownload
{
  "execution_mode": "CPU algorithm with controlled inputs; any latency/capacity coefficients are assumptions",
  "equivalence_check": {
    "seq_len": 64,
    "head_dim": 16,
    "block_q": 16,
    "block_kv": 16,
    "max_abs_diff": 1.388e-16,
    "standard_materialized_elements": 4160,
    "flash_materialized_hbm_elements": 0,
    "flash_sram_tile_elements": 256,
    "flash_tiles_visited": 10,
    "sample_row0_first4": [
      -0.267257,
      0.731232,
      -0.775466,
      0.699456
    ],
    "sample_last_row_first4": [
      0.017991,
      -0.007947,
      0.059253,
      0.070964
    ]
  },
  "hbm_traffic_sweep": [
    {
      "seq_len": 1024,
      "num_heads": 32,
      "head_dim": 128,
      "standard_qkv_o_mb": 33.55,
      "standard_nxn_matrix_hbm_mb": 268.44,
      "standard_total_hbm_mb": 301.99,
      "tiled_logical_access_mb_no_cache_reuse": 92.27,
      "qkvo_compulsory_bytes_mb": 33.55,
      "num_q_blocks": 8,
      "accounting": "logical accesses, not measured HBM traffic; dense baseline and causal tiled loop differ in work"
    },
    {
      "seq_len": 4096,
      "num_heads": 32,
      "head_dim": 128,
      "standard_qkv_o_mb": 134.22,
      "standard_nxn_matrix_hbm_mb": 4294.97,
      "standard_total_hbm_mb": 4429.19,
      "tiled_logical_access_mb_no_cache_reuse": 1174.41,
      "qkvo_compulsory_bytes_mb": 134.22,
      "num_q_blocks": 32,
      "accounting": "logical accesses, not measured HBM traffic; dense baseline and causal tiled loop differ in work"
    },
    {
      "seq_len": 16384,
      "num_heads": 32,
      "head_dim": 128,
      "standard_qkv_o_mb": 536.87,
      "standard_nxn_matrix_hbm_mb": 68719.48,
      "standard_total_hbm_mb": 69256.35,
      "tiled_logical_access_mb_no_cache_reuse": 17582.52,
      "qkvo_compulsory_bytes_mb": 536.87,
      "num_q_blocks": 128,
      "accounting": "logical accesses, not measured HBM traffic; dense baseline and causal tiled loop differ in work"
    },
    {
      "seq_len": 32768,
      "num_heads": 32,
      "head_dim": 128,
      "standard_qkv_o_mb": 1073.74,
      "standard_nxn_matrix_hbm_mb": 274877.91,
      "standard_total_hbm_mb": 275951.65,
      "tiled_logical_access_mb_no_cache_reuse": 69524.78,
      "qkvo_compulsory_bytes_mb": 1073.74,
      "num_q_blocks": 256,
      "accounting": "logical accesses, not measured HBM traffic; dense baseline and causal tiled loop differ in work"
    }
  ]
}
Saved output report for explain tiled attention and verify its output; execution mode and values come from the linked raw result.

The image is a report generated from the saved CPU run, not a new run. Open the full-resolution report or read the raw result.

Separate storage savings from runtime

Tiling reduces intermediate storage. On a supported GPU kernel it can also improve data movement, but the result depends on tile size, register pressure, cache reuse, precision and backend support. A compulsory-byte lower bound is not actual HBM traffic. Measure the selected runtime backend before claiming a FlashAttention speedup.

Exponential overflow. Large scores can overflow a naive exponential: math.exp raises OverflowError. Subtracting the row maximum keeps the reference calculation finite, and the running maximum keeps the tiled calculation finite.

Accumulator rescaling. When a later tile raises the running maximum, an unscaled old output accumulator gives the wrong attention output. The test makes the last key large so that the maximum rises on a later tile, and the comparison with the reference catches the error.

Read the executable checks
Executable checksSource · pythonDownload
"""Unit and failure-boundary tests for standard vs tiled FlashAttention."""

from __future__ import annotations

import unittest

from lab import (
    estimate_hbm_bytes,
    make_qkv,
    max_abs_diff,
    standard_attention,
    tiled_flash_attention,
)


class FlashAttentionTest(unittest.TestCase):
    def test_tiled_flash_attention_matches_standard_attention_across_tile_sizes(
        self,
    ) -> None:
        q, k, v = make_qkv(seq_len=64, head_dim=16, seed=7)
        std_out, _ = standard_attention(q, k, v, causal=True)
        for bq, bkv in ((8, 8), (16, 16), (13, 19), (32, 8)):
            flash_out, meta = tiled_flash_attention(
                q, k, v, block_q=bq, block_kv=bkv, causal=True
            )
            self.assertLess(max_abs_diff(std_out, flash_out), 1e-12)
            self.assertEqual(meta["materialized_nxn_elements"], 0)

    def test_access_count_includes_repeated_kv_reads(self) -> None:
        small = estimate_hbm_bytes(seq_len=4096)
        large = estimate_hbm_bytes(seq_len=32768)
        self.assertGreater(
            small["tiled_logical_access_mb_no_cache_reuse"],
            small["qkvo_compulsory_bytes_mb"],
        )
        self.assertGreater(
            large["tiled_logical_access_mb_no_cache_reuse"]
            / small["tiled_logical_access_mb_no_cache_reuse"],
            8,
        )
        self.assertNotIn("hbm_traffic_reduction_x", large)

    def test_naive_softmax_overflows_without_max_shift(self) -> None:
        """Large attention logits overflow exp() when subtract_max=False, whereas online max shift stays finite."""
        q = [[500.0, 500.0], [500.0, 500.0]]
        k = [[1.0, 1.0], [2.0, 2.0]]
        v = [[1.0, 0.0], [0.0, 1.0]]
        with self.assertRaises(OverflowError):
            standard_attention(q, k, v, causal=False, subtract_max=False)
        safe_std, _ = standard_attention(q, k, v, causal=False, subtract_max=True)
        safe_flash, _ = tiled_flash_attention(
            q, k, v, block_q=1, block_kv=1, causal=False
        )
        self.assertLess(max_abs_diff(safe_std, safe_flash), 1e-12)

    def test_forgetting_output_rescaling_across_tiles_corrupts_attention(self) -> None:
        """Omitting the exp(prev_max - new_max) rescaling on output_acc produces wrong attention outputs."""
        q, k, v = make_qkv(seq_len=32, head_dim=8, seed=99)
        # Emphasize a late key so running_max increases on a subsequent KV tile
        k[-1] = [4.0] * 8
        std_out, _ = standard_attention(q, k, v, causal=True)
        correct_flash, _ = tiled_flash_attention(
            q, k, v, block_q=8, block_kv=8, causal=True, rescale_previous_acc=True
        )
        buggy_flash, _ = tiled_flash_attention(
            q, k, v, block_q=8, block_kv=8, causal=True, rescale_previous_acc=False
        )
        self.assertLess(max_abs_diff(std_out, correct_flash), 1e-12)
        self.assertGreater(max_abs_diff(std_out, buggy_flash), 0.1)


if __name__ == "__main__":
    unittest.main()

Try a change and explain the result

Compare several tile sizes, including sizes that do not divide the sequence. Explain why the numerical result should agree even when the visitation order changes. Use the rescaling test to locate the first wrong assumption in an incorrect accumulator.

A later attention tile raises the running score maximum. What must be rescaled?

Choose one answer, then check your reasoning.

Read the explanation

The running state must use the same exponential scale as the new tile.

Select a supported attention backend

Use this lab to learn and test the mechanism, not to serve requests: it is pure Python on the CPU. In the serving runtime, prefer a supported attention backend. Confirm mask semantics and numerical tolerance for the exact dtype. Do not call a generic scaled-dot-product-attention call FlashAttention until you confirm which backend it selected.

References

Sources checked October 24, 2026. Runtime-specific commands and results apply to the recorded versions; linked rolling documentation can change. The application scenarios are teaching examples, not claims about an author’s production incident.

Written by Arjun Prabhulal.

Module 2

Budget weights, cache and attention memory