Self-attention is described as a weighted average. State what is averaged, how the weights are produced, and derive the time and memory cost in the sequence length n and the head dimension d. Say what that cost means for a 10,000-step tick sequence.

Self-attention is described as a weighted average. State what is averaged, how the weights are produced, and derive the time and memory cost in the sequence length n and the head dimension d. Say what that cost means for a 10,000-step tick sequence.

Approach: Write the query, key and value construction, count the operations in the score matrix and in the weighted sum, and evaluate at the stated sequence length.

Self-attention averages the value vectors with weights softmax(QK^T/sqrt(d)), and both the time and the memory are O(n^2 d), so a 10,000-step sequence needs 10^8 attention weights per head, which is the reason plain transformers are not run directly on tick data. Each position produces a query, a key and a value by linear maps of its own representation. The score matrix QK^T is n by n and costs n^2 d multiply-adds; the softmax over each row costs O(n^2); the weighted sum of values costs another n^2 d. The division by sqrt(d) keeps the score variance at order one, since a dot product of two d-dimensional vectors with unit-variance entries has variance d, and without it the softmax saturates and the gradient vanishes. The n^2 memory is usually the binding constraint because the attention matrix must be kept for the backward pass, and at n = 10,000 with 8 heads in 4-byte floats that is 3.2 GB per layer. Practical routes are to shorten the sequence by bar aggregation, to restrict attention to a local window or a strided pattern, to use a low-rank or kernelised approximation that is linear in n, or to recompute the matrix in blocks so it is never materialised.

Follow-up: For causal attention only the lower triangle is needed. What constant factor does that save, and why does it not change the asymptotic cost?

Key concepts: attention weights, quadratic cost, value vectors, softmax.