When I read the paper, Reformer: The Efficient Transformer, I cannot get the same complexity of the memory-efficient method in Table 1 (p. 5), which summarizes time/memory complexity of scaled dot-product, memory efficient, and LSH attention.

The memory complexity of the memory-efficient method is as follow:

$$\max \left(b n_{h} l d_{k}, b n_{h} l^{2}\right)$$

$b$: batch size $l$: sequence length $n_h$: the number of attention head $d_k$: the dimension of query or key

To the best of my knowledge, the memory-efficient method will do a loop for each query, therefore, the whole attention matrix will not show up.

So, shouldn't the memory complexity be $\max(b n_h l d_k, b n_h l)=(b n_h l d_k)$ instead of $\max(b n_h l d_k,b n_h l^2)$?

New contributor
tsu is a new contributor to this site. Take care in asking for clarification, commenting, and answering. Check out our Code of Conduct.

Your Answer

tsu is a new contributor. Be nice, and check out our Code of Conduct.

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.