3 ms·
> Same with attention in feed forward networks requiring exponential time with a reduction in expressability. Huh? Can you say more about that? What takes expo
by drdeca 3y ago
> Same with attention in feed forward networks requiring exponential time with a reduction in expressability.
Huh? Can you say more about that? What takes exponential time with transformers?
- nyrikki 3y ago> We prove that the time complexity of self-attention is necessarily quadratic in the input length, unless the Strong Exponential Time Hypothesis (SETH) is false. This argument holds even if the attention computation is performed only approximately, and for a variety of attention mechanisms. https://proceedings.mlr.press/v201/duman-keles23a/duman-keles23a.pdf https://proceedings.mlr.press/v201/duman-keles23a/duman-kele...
- drdeca 3y agoThanks! But, quadratic time complexity (which I had heard that attention requires, which doesn't surprise me) is not exponential time. I acknowledge that they related this to the assumption of the SETH (which surprises me a little). But, this doesn't mean that transformers take exponential time. I don't think I understood what you meant by the "with a reduction in expressability" part of the statement, so maybe that is the reason behind me not following.