按年被提到
20222024 · 3 次2026
大模型与语言模型›模型表达力与计算理论·arXiv:2209.04881 · cs.LG

On The Computational Complexity of Self-Attention

Feyza Duman Keles, Pruthuvi Mahesakya Wijewardena, Chinmay Hegde · 2022
开始阅读 ↗PDFalphaXiv 讨论
被提及 · 2 人首次 2024-03-05 · 最近 2026-10-26
2不同的人
3活跃月份
4讨论串
98被引(OpenAlex)
arXiv 摘要(候选层不写导读)

Transformer architectures have led to remarkable progress in many state-of-art applications. However, despite their successes, modern transformers rely on the self-attention mechanism, whose time- and space-complexity is quadratic in the length of the input. Several approaches have been proposed to speed up self-attention mechanisms to achieve sub-quadratic running time; however, the large majority of these works are not accompanied by rigorous error guarantees. In this work, we establish lower bounds on the computational complexity of self-attention in a number of scenarios. 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. As a complement to our lower bounds, we show that it is indeed possible to approximate dot-product self-attention using finite Taylor series in linear-time, at the cost of having an exponential dependence on the polynomial order.

候选层:至少 2 个不同的人、在 2 个不同月份提到过,还没到主书架的 3 人 3 个月。没有做立场标注,所以只写“被提及”。

HN 书评

推荐在前,同类按时间 · 每篇最多保留 20 条,统计用全部提及
评论logicchains · 2024-03

“There's fundamentally a trade-off: https://arxiv.org/abs/2209.04881. (Unless the Strong Exponential Time Hypothesis is false, but that's pretty unlikely, like P being equal to NP).”

Based: Simple linear attention language models原评论 ↗
评论logicchains · 2024-03

“>Lately I've been wondering... is this a problem, or a strength? It's a strength; fundamentally it's impossible to achieve the same degree of accuracy with a sub-quadratic attention mechanism: https://arxiv.org/abs/2209.04881 (unless the Strong Exponential Time Hypothesis is false, which is very unlikely, like P=NP).”

Mamba Explained原评论 ↗
评论logicchains · 2024-04

“Transformers are special because theoretically you can't make something "weaker" than a transformer without it losing some accuracy: https://arxiv.org/abs/2209.04881.”

Transformer as a general purpose computer原评论 ↗
评论strommec · 2026-10

“It's surprising that Exponential Time Hypothesis would be false. Quoting a paper from 2022[1]: > 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[...] If OpenAI's proof is correct, does that mean self-attention can be implemented in sub-quadrat…”

The Exponential Time Hypothesis Is False [pdf]原评论 ↗