FlashDecoding: Split-K GQA Decode Attention

HardML Coding

Problem statement

Implement a single decode step of FlashDecoding with grouped-query attention (GQA).

At decode time the query is one token while the key/value cache has length $S$. FlashDecoding splits that cache along the sequence axis, computes attention on each split, and merges the split results so the output equals full attention.

Inputs

  • q: array of shape (batch, n_q_heads, head_dim): query for the new token
  • k, v: arrays of shape (batch, seq, n_kv_heads, head_dim): the KV cache
  • n_splits: positive int, number of contiguous splits of the sequence axis

n_q_heads is divisible by n_kv_heads. Each KV head is shared by n_q_heads / n_kv_heads query heads (GQA; MHA is the special case n_kv_heads == n_q_heads).

Contract

  • Attention scores are scaled by $1/\sqrt{\mathrm{head\_dim}}$.
  • Partition seq with the same lengths as numpy.array_split(range(seq), n_splits) (leading splits get the remainder).
  • Empty splits (when n_splits > seq) contribute nothing.
  • The returned array has shape (batch, n_q_heads, head_dim) and must match full GQA scaled-dot-product attention

$$\mathrm{softmax}\!\left(q\,k^\top / \sqrt{d}\right) v$$

with KV heads repeated to the query-head axis.

Use 64-bit floats internally.

Example

Input:

q = [[[1.0, 0.0], [0.0, 1.0]]]           # (1, 2, 2): two query heads
k = [[[[1.0, 0.0]], [[0.0, 1.0]]]]        # (1, 2, 1, 2): one KV head
v = [[[[1.0, 2.0]], [[3.0, 4.0]]]]        # (1, 2, 1, 2)
flash_decoding(q, k, v, n_splits=2)

Output:

[[[1.6605 2.6605]
  [2.3395 3.3395]]]   (rounded to 4 decimals)

Reasoning: One KV head is shared by both query heads (group size 2). Head 0 scores are $[1, 0] / \sqrt{2} = [0.7071, 0]$, softmax weights $[0.6698, 0.3302]$, output $0.6698 \cdot [1, 2] + 0.3302 \cdot [3, 4] = [1.6605, 2.6605]$. Head 1 has the mirrored scores. Splitting the two-token cache into two splits of one token each and merging them gives exactly the same result.

Show hint

If each split only knows its own scores, what extra statistics must it report so a later step can recover the exact global softmax?

Relevant roles: LLM Engineer, Deep Learning Engineer, ML Engineer and Research Scientist.

Related free problems