Hacker News

points by strommec 3 days ago | 0 comments

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-quadratic time? I.e. we could eventually have all the most advanced LLMs running on cheap hardware? To put it more playfully, is ETH being false actually bearish for Nvidia?

[1]: https://arxiv.org/abs/2209.04881

[–] rokob 3 days ago

No, SETH implies quadratic time does not mean !SETH implies !quadratic time.

[–] dnautics 3 days ago

but you're telling me.... there's a chance

[–] Xirdus 3 days ago

This but unironically.

[–] programjames 3 days ago

put a number on your probabilities. there's a chance you have an aneurysm in the next few minutes and fail to see my comment. if so, oh well, i tried.

[–] _ink_ 2 days ago

If AI really scales indefinitely is an increase in efficiency even bearish for Nvidia? Wouldn't they still build more and more compute as fast as they can, because these things get smarter and better with more compute?

[–] caughtinthought 3 days ago

SETH is a much stronger claim than ETH

[–] jibalt 3 days ago

Not relevant, because !ETH => !SETH

What is relevant is that the logic goes the other way: SETH implies quadratic, !SETH implies nothing.

[–] varyherb 3 days ago

Right, so a refutation of ETH would also refute SETH.

[–] margalabargala 3 days ago

Yes, it's one strong stronger.

[–] refulgentis 3 days ago

It's playful!

But it's also not even wrong, in the Pauli sense.

That makes me wonder if "I see your CS proof, how does this affect LLMs / nvidia stonk price???" being immediately self-described as "playful" ensures criticism looks cranky.

[–] Joker_vD 3 days ago

"I see your particle physics paper (on sustainability of neutron-induced chain fission reaction in uranium), how does this affect the world politics???"

Turns out, it affected the global politics tremendously.