Topic 02: Causal Masking & Chunked Prefill Bug Fixes

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.


1. The Foundation of Causal Masking

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.


2. The Three Attention Scenarios in Modern LLMs

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$.

3. The Two Insidious Bugs in Standard Code

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:

Bug 1: The Non-Flash Path Broadcasting Crash

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'))

Bug 2: PyTorch SDPA Silent Mask Corruption

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)

4. The Unified Mathematical Solution

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$.

Visualizing the Rectangular Chunked-Prefill Mask

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)

The Clean PyTorch Implementation in `model.py`

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

5. Correctness Verification (`verify_radix_cache.py`)

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.


6. Interview Takeaway & Soundbite

🎯 Interview Answer — "What was the most subtle bug you encountered during this project?"
“The most insidious bug occurred in PyTorch SDPA during chunked prefill. When prefilling a suffix chunk on top of an existing KV cache, the condition `is_causal = (T == T_ctx)` evaluated to `False`. Unlike manual attention—which threw a broadcasting shape error—SDPA silently executed unmasked attention, allowing earlier suffix tokens to attend to future suffix tokens. I resolved this by unifying the mask with a diagonal offset $P = T_{ctx} - T$, ensuring query row $i$ attends strictly to columns $0 \dots P+i$ across all three operating modes.”