3 ms·
> We prove that the time complexity of self-attention is necessarily quadratic in the input length, unless the Strong Exponential Time Hypothesis (SETH) is fals
by 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.