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 8 hours ago | parent | next [-]

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

▲

dnautics 8 hours ago | parent [-]

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

	▲	Xirdus 8 hours ago \| parent \| next [-]
		This but unironically.
	▲	programjames 8 hours ago \| parent \| prev [-]
		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.

▲

caughtinthought 8 hours ago | parent | prev | next [-]

SETH is a much stronger claim than ETH

	▲	jibalt 6 hours ago \| parent \| next [-]
		Not relevant, because !ETH => !SETH What is relevant is that the logic goes the other way: SETH implies quadratic, !SETH implies nothing.
	▲	varyherb 5 hours ago \| parent \| prev \| next [-]
		Right, so a refutation of ETH would also refute SETH.
	▲	margalabargala 6 hours ago \| parent \| prev [-]
		Yes, it's one strong stronger.

▲

refulgentis 6 hours ago | parent | prev [-]

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 2 hours ago \| parent [-]
		"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.