Overview: The mathematical semantics of causal self-attention, why standard masking breaks when processing token chunks on top of an existing KV cache ($1 < T < T_{ctx}$), the two bugs discovered in nanoGPT (broadcasting crash and SDPA silent corruption), and the unified diagonal-offset formulation that guarantees mathematical correctness.
In decoder-only autoregressive language models (like GPT-2, LLaMA, and Mistral), an attention layer must preserve causality: a token at position $i$ is only permitted to attend to preceding positions $j \le i$. It must never attend to future tokens $j > i$.
In standard un-cached self-attention over sequence length $T$, this is enforced by a square lower-triangular mask of shape $(T, T)$:
Position 0: [ 1, 0, 0, 0 ] ──► Token 0 sees only Token 0
Position 1: [ 1, 1, 0, 0 ] ──► Token 1 sees Tokens 0 and 1
Position 2: [ 1, 1, 1, 0 ] ──► Token 2 sees Tokens 0, 1, and 2
Position 3: [ 1, 1, 1, 1 ] ──► Token 3 sees all tokens
Positions where `mask == 0` are filled with $-\infty$ prior to softmax:
$$\text{Softmax}(\text{Scores} + M)_{i, j} \quad \text{where} \quad M_{i, j} = \begin{cases} 0 & \text{if } j \le i \\ -\infty & \text{if } j > i \end{cases}$$Because $e^{-\infty} = 0$, masked positions receive zero attention weight.
When supporting KV caching and shared-prefix trees, `CausalSelfAttention.forward` encounters three distinct operating modes:
| Scenario | Query Length ($T$) | Total Keys ($T_{ctx}$) | Description | Required Attention Mask |
|---|---|---|---|---|
| 1. Full Prefill | $T = P$ | $T_{ctx} = P$ | Initial prompt forward pass without any prior cache. | Square lower-triangular $(P \times P)$ matrix. |
| 2. Single-Token Decode | $T = 1$ | $T_{ctx} > 1$ | Autoregressive generation step predicting the next token. | Single row $(1 \times T_{ctx})$ with all 1s (unmasked). Token at $T_{ctx}-1$ attends to all past keys. |
| 3. Chunked Prefill | $1 < T < T_{ctx}$ | $T_{ctx} = P + T$ | A multi-token suffix chunk forwarded on top of a cached prefix of length $P$. | Rectangular $(T \times T_{ctx})$ band: query row $i$ attends to columns $0 \dots P+i$. |
When extending nanoGPT for Part C (radix-tree shared-prefix generation), child branches must evaluate a suffix chunk of several tokens on top of a cached prefix. This exercised Scenario 3 ($1 < T < T_{ctx}$) for the first time, exposing two critical bugs:
In the manual attention fallback, the existing code applied the causal mask as:
# Existing nanoGPT code:
att = att.masked_fill(self.bias[:, :, :T, :T] == 0, float('-inf'))
RuntimeError: The size of tensor a (T_ctx) must match the size of tensor b (T) at non-singleton dimension 3
The accelerated FlashAttention path used PyTorch's `F.scaled_dot_product_attention` with the flag:
# Existing nanoGPT code:
is_causal = (T == T_ctx)
y = F.scaled_dot_product_attention(q, k, v, is_causal=is_causal)
To eliminate both bugs permanently, we derived a unified mathematical formula based on the already-cached prefix length $P$:
$$P = T_{ctx} - T$$For any query row $i \in [0, T-1]$ inside the incoming chunk, the token's absolute position in the sequence is $P + i$. Therefore, query row $i$ is allowed to attend to all key columns $j \le P + i$, and must be masked for all columns $j > P + i$.
Suppose cached prefix length $P = 4$, and incoming chunk length $T = 3$ ($T_{ctx} = 7$):
Keys: Col 0 Col 1 Col 2 Col 3 | Col 4 Col 5 Col 6
(---- Cached Prefix ----) | (---- Suffix Chunk ----)
Query Row 0: 1 1 1 1 | 1 0 0 (sees 0..4)
Query Row 1: 1 1 1 1 | 1 1 0 (sees 0..5)
Query Row 2: 1 1 1 1 | 1 1 1 (sees 0..6)
T_ctx = k.size(2)
P = T_ctx - T # Number of previously cached prefix tokens
if self.flash:
if T == T_ctx:
# Full prefill: SDPA internal causal mask works
y = F.scaled_dot_product_attention(q, k, v, is_causal=True, dropout_p=...)
elif T == 1:
# Single-token decode: row at end attends to all keys, no mask needed
y = F.scaled_dot_product_attention(q, k, v, is_causal=False, dropout_p=...)
else:
# Chunked prefill (1 < T < T_ctx): explicit rectangular causal mask
# Query row i (at absolute position P + i) sees keys 0 .. P + i
mask = torch.ones(T, T_ctx, dtype=torch.bool, device=q.device).tril(diagonal=P)
y = F.scaled_dot_product_attention(q, k, v, attn_mask=mask, dropout_p=...)
else:
# Manual attention path
att = (q @ k.transpose(-2, -1)) * (1.0 / math.sqrt(k.size(-1)))
mask = torch.ones(T, T_ctx, dtype=torch.bool, device=q.device).tril(diagonal=P)
att = att.masked_fill(~mask, float('-inf'))
att = F.softmax(att, dim=-1)
y = att @ v
To prove that the chunked-prefill fix produces mathematically identical outputs, we authored a rigorous test suite (`verify_radix_cache.py`). The suite tested a heterogeneous batch of prompts:
We executed greedy generation (`greedy=True`) comparing `generate_radix_shared` against the baseline `generate_independent` across both PyTorch SDPA and manual attention:
$ python verify_radix_cache.py
flash=True: radix-shared == independent -> True
flash=False: radix-shared == independent -> True
All correctness checks passed.
Every single generated token was bit-for-bit identical between independent full-recompute generation and radix-tree prefix-cached chunked prefill, confirming zero numerical regression.