Online Softmax Attention as Coupled Accumulators

MediumML Coding

Problem statement

Flash attention computes softmax(q K^T / sqrt(d)) V for one query without materializing the scores. It streams the keys and maintains three accumulators: the running maximum m, the running normalizer l, and the unnormalized output o. Implement the per-key update rule and the full computation in the form a fused kernel would execute.

attend_step(m, l, o, s, v)

  • Given the current accumulators, a new score s (a float) and its value row v (a NumPy vector): m_new = max(m, s), alpha = exp(m - m_new), p = exp(s - m_new), l_new = l * alpha + p, o_new = o * alpha + p * v. Return (m_new, l_new, o_new). All updates read the old values.

flash_attention(Q, K, V)

  • For each query row: start with m = -inf, l = 0, o = zeros(d); for every key j compute s = q . K[j] / sqrt(d) and apply attend_step; the output row is o / l. Return the (N, d) float32 result.

reference_attention(Q, K, V)

  • The standard two-pass form with the materialized score matrix.

score_matrix_bytes(N, elem_bytes=4)

  • Bytes the materialized N x N score matrix would occupy.

Notes

  • With m = -inf initially, alpha = exp(-inf - s) = 0 on the first key, which zeroes the empty accumulators harmlessly.
  • Use float64 inside the loop and cast at the end to keep the comparison with the reference tight.

Example

Input:

m, l, o = attend_step(-math.inf, 0.0, np.zeros(2), 1.0, np.array([1.0, 2.0]))
print(m, l, o.tolist())

Output:

1.0 1.0 [1.0, 2.0]

Reasoning: the first key sets the maximum, its unnormalized probability weight is 1, and the output accumulator becomes its value row.

Show hint

What single factor converts terms that were accumulated against an old maximum into terms against a new, larger maximum?

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

Related free problems