Count active blocks and acknowledge the changed operator

Divide queries and keys into blocks of b tokens for the simplest square, evenly divisible case. Each active block allows b² query-key pairs unless an additional element-level mask removes some of them. A sparse row’s softmax denominator sums only its allowed keys. Excluding a block does not merely zero its contribution after computing dense probabilities: the remaining probabilities must be renormalized over the sparse domain. Otherwise the implementation computes a different unnormalized output.

Patterns can combine local, global, or random block connections, as in original sparse-attention work, or reflect a task-specific structure. Their usefulness depends on which information must pass between tokens across layers. A mathematically exact evaluation of the selected sparse pattern is still different from exact dense attention unless excluded weights were truly irrelevant under a defined equivalence condition. The phrase exact kernel must therefore identify the operator for which it is exact.

A lower-triangular arrangement of blocks does not automatically implement token-level causality. The diagonal block still contains future-token entries unless a triangular element mask is applied inside it. Boundary padding also changes how many logical pairs are valid. A kernel may execute a full tile while masking some lanes, so logical allowed-pair counts and executed tensor-core work need not match exactly. Report both when interpreting sparse throughput.

At fixed block size, a bounded number of active key blocks per query block gives a pair count linear in token length. If the number of active blocks per row grows with the number of blocks, the pattern can return toward quadratic complexity. Constants matter too: sparse metadata, gathers, irregular load balance, and small blocks can make fewer arithmetic operations slower than a regular dense tile schedule. Count work first, then measure the actual execution.

Construct a tiny dense reference with exactly the same boolean pattern and compare sparse outputs and gradients to it. Separately compare the chosen sparse model with the original dense model on task quality. These tests answer different questions: one detects kernel errors, the other measures the effect of removing dependencies. A sparse kernel can pass its matching reference perfectly while the sparse architecture performs poorly on a task needing distant interactions.

Test active-block ordering, duplicate metadata entries, empty rows, and partial blocks. Duplicate block entries must not accidentally count the same key twice in the denominator. If a pattern is randomly sampled, preserve its seed or explicit realized mask when reproducing a numerical test. Build the reference from logical token pairs rather than assuming that a library’s compressed metadata format already means what the model designer intended.