Tiled attention uses linear retained memory and quadratic arithmetic

The forward procedure retains $Q,K,V,Y$ and $(m_i,{\mathrm{\ell }}_i{)}_{i=1}^n$. Their scalar counts are $nd+nd+nv+nv+2n=O(n(d+v))$ because $d,v\ge 1$. At any query and key block it stores at most $b$ scores and the current and block weighted-value vectors of length $v$, plus a constant number of scalars. This is $O(b+v)$ extra live storage, and it discards the block workspace before moving to the next block.

The forward loops examine at most $n^2$ query-key pairs. For each pair, the score dot product uses $O(d)$ operations; its normalized exponential and weighted-value contribution use $O(1+v)$ operations. Block maxima, membership queries, and scalar loop overhead cost $O(n^2)$ in total. There are at most $n\lceil n\mathrm{/}b\rceil \le n^2$ block visits, each summary copy or merge costs $O(v)$, and final row divisions cost $O(nv)$. Thus forward arithmetic is $O(n^2(d+v))$. Only one block's scores and weighted-value summaries are live, so no $n\times n$ score or probability array is allocated.

The reverse procedure's retained arrays are $Q,K,V,Y,G,dQ,dK,dV$ and the $2n$ row statistics. Their scalar counts are all $O(n(d+v))$. For one row and one key it recomputes one score and one probability, forms scalar inner products, and updates entries in the already allocated gradient arrays; it needs only a constant number of additional scalars, which is within $O(b+v)$. It does not store the recomputed probabilities across pairs.

Each query-key pair in the reverse pass costs $O(d+v)$ operations: one score, one inner product with $V_j$, and vector updates with lengths $d$ and $v$. There are at most $n^2$ pairs, and the finite loop overhead is at most $O(n^2)$, so reverse arithmetic is $O(n^2(d+v))$. Since scores and probabilities are recomputed one at a time, this pass also creates no $n\times n$ array. The separate exactness claim is supplied by [F3].