6 ms·

> We have mathematically proven that transformers can solve any problem, provided they are allowed to generate as many intermediate reasoning tokens as needed.

> We have mathematically proven that transformers can solve any problem, provided they are allowed to generate as many intermediate reasoning tokens as needed. That seems like a bit of a leap here to make this seem more impressive than it is (IMO). You can say the same thing about humans, provided they are allowed to think across as many years/generations as needed. Wake me up when a LLM figures out stable fusion or room temperature superconductors.

WalterSear 2y ago
> You can say the same thing about humans 1. Holy shit. 2. You can't apply Moore's law to humans.
- Tostino 2y ago
  You can't to chips any more either. Density has continued to increase, but so have prices. The 'law' was tied to the price to density ratio, and it's been almost a decade now since it died.
- gryn 2y ago
  > 2. You can't apply Moore's law to humans. not with that attitude. /s if you take reproduction into account and ignore all the related externalities you can definitely double your count of transistors (humans) every two years.
Horffupolde 2y ago
It is actually impressive. One could argue that writing enabled chain of thought across generations.
krackers 2y ago
I think you're misrepresenting the study. It builds upon previous work that examines the computation power of the transformer architecture from a circuit-complexity perspective. Previous work showed that the class of problems that a "naive" Transformer architecture could compute was within TC0 [1, 2] and as a consequence it was fundamentally impossible for transformers to solve certain classes of mathematical problems. This study actually provides a more realistic bound of AC0 (by analyzing the finite-precision case) which rules out even more problems, including such 'simple' ones as modular parity. We also had previous work that hinted that part of the reason why chain-of-thought works from a theoretical perspective is that it literally allows the model to perform types of computations it could not under the more limited setting (in the same way jumping from FSMs to pushdown automata allows you to solve new types of problems) [3]. [1] https://news.ycombinator.com/item?id=35609652 https://news.ycombinator.com/item?id=35609652 [2] https://blog.computationalcomplexity.org/2023/02/why-cant-little-chatty-do-math.html https://blog.computationalcomplexity.org/2023/02/why-cant-li... [3] https://arxiv.org/abs/2305.15408 https://arxiv.org/abs/2305.15408
- shawntan 2y ago
  Generally, literature on the computational power of the SAME neural architecture can differ on their conclusions based on their premises. Assuming finite precision will give a more restrictive result, and assuming arbitrary precision can give you Turing completeness. From a quick skim this seems like it's making finite precision assumptions? Which doesn't actually tighten previous bounds, it just makes different starting assumptions. Am author of [1].
  - krackers 2y ago
    Ah my bad, great catch! I've updated my comment accordingly.
    - shawntan 2y ago
      You can't really be blamed though, the language in the paper does seem to state what you originally said. Might be a matter of taste but I don't think it's quite accurate. The prior work they referenced actually did account for finite precision cases and why they didn't think it was useful to prove the result with those premises. In this work they simply argued from their own perspective why finite precision made more sense. The whole sub-field is kinda messy and I get quoted differing results all the time. Edit: Also, your original point stands, obviously. Sorry for nitpicking on your post, but I also just thought people should know more about the nuances of this stuff.
aurareturn 2y ago
> You can say the same thing about humans, provided they are allowed to think across as many years/generations as needed. Isn’t this a good thing since compute can be scaled so that the LLM can do generations of human thinking in a much shorter amount of time? Say humans can solve quantum gravity in 100 years of thinking by 10,000 really smart people. If one AGI is equal to 1 really smart person. Scale enough compute for 1 million AGI and we can solve quantum gravity in a year. The major assumption here is that transformers can indeed solve every problem humans can.
- wizzwizz4 2y ago
  > Isn’t this a good thing since compute and be scaled so that the LLM can do generations of human thinking in a much shorter amount of time? But it can't. There isn't enough planet. > The major assumption here is that transformers can indeed solve every problem humans can. No, the major assumptions are (a) that ChatGPT can, and (b) that we can reduce the resource requirements by many orders of magnitude. The former assumption is highly-dubious, and the latter is plainly false. Transformers are capable of representing any algorithm, if they're allowed to be large enough and run large enough. That doesn't give them any special algorithm-finding ability, and finding the correct algorithms is the hard part of the problem!
  - aurareturn 2y ago
    > But it can't. There isn't enough planet. How much resource are you assuming an AGI would consume?
    - wizzwizz4 2y ago
      Are we talking about "an AGI", or are we talking about overfitting large transformer models with human-written corpora and scaling up the result? "An AGI"? I have no idea what that algorithm might look like. I do know that we can cover the majority of cases with not too much effort, so it all depends on the characteristics of that long tail. ChatGPT-like transformer models? We know what that looks like, despite the AI companies creatively misrepresenting the resource use (ref: https://www.bnnbloomberg.ca/business/technology/2024/08/21/how-tech-companies-are-obscuring-ais-real-carbon-footprint/ https://www.bnnbloomberg.ca/business/technology/2024/08/21/h...). Look at https://arxiv.org/pdf/2404.06405 https://arxiv.org/pdf/2404.06405: > Combining Wu’s method with the classic synthetic methods of deductive databases and angle, ratio, and distance chasing solves 21 out of 30 methods by just using a CPU-only laptop with a time limit of 5 minutes per problem. AlphaGeometry had an entire supercomputer cluster, and dozens of hours. GOFAI approaches have a laptop and five minutes. Scale that inconceivable inefficiency up to AGI, and the total power output of the sun may not be enough.
whimsicalism 2y ago
it's a TCS result. seems like many commenting don't know about computability
Veedrac 2y ago
> Wake me up when a LLM figures out stable fusion or room temperature superconductors. Man, the goalposts these days.
- WalterSear 2y ago
  Shh!! It's working! It's working!
- FeepingCreature 2y ago
  "I love [goalposts]. I love the whooshing noise they make as they go by." --Douglas Adams, slightly adjusted

WalterSear 2y ago

> You can say the same thing about humans 1. Holy shit. 2. You can't apply Moore's law to humans.

Tostino 2y ago
You can't to chips any more either. Density has continued to increase, but so have prices. The 'law' was tied to the price to density ratio, and it's been almost a decade now since it died.
gryn 2y ago
> 2. You can't apply Moore's law to humans. not with that attitude. /s if you take reproduction into account and ignore all the related externalities you can definitely double your count of transistors (humans) every two years.

Horffupolde 2y ago

It is actually impressive. One could argue that writing enabled chain of thought across generations.

krackers 2y ago

I think you're misrepresenting the study. It builds upon previous work that examines the computation power of the transformer architecture from a circuit-complexity perspective. Previous work showed that the class of problems that a "naive" Transformer architecture could compute was within TC0 [1, 2] and as a consequence it was fundamentally impossible for transformers to solve certain classes of mathematical problems. This study actually provides a more realistic bound of AC0 (by analyzing the finite-precision case) which rules out even more problems, including such 'simple' ones as modular parity. We also had previous work that hinted that part of the reason why chain-of-thought works from a theoretical perspective is that it literally allows the model to perform types of computations it could not under the more limited setting (in the same way jumping from FSMs to pushdown automata allows you to solve new types of problems) [3]. [1] https://news.ycombinator.com/item?id=35609652 https://news.ycombinator.com/item?id=35609652 [2] https://blog.computationalcomplexity.org/2023/02/why-cant-little-chatty-do-math.html https://blog.computationalcomplexity.org/2023/02/why-cant-li... [3] https://arxiv.org/abs/2305.15408 https://arxiv.org/abs/2305.15408

shawntan 2y ago
Generally, literature on the computational power of the SAME neural architecture can differ on their conclusions based on their premises. Assuming finite precision will give a more restrictive result, and assuming arbitrary precision can give you Turing completeness. From a quick skim this seems like it's making finite precision assumptions? Which doesn't actually tighten previous bounds, it just makes different starting assumptions. Am author of [1].
- krackers 2y ago
  Ah my bad, great catch! I've updated my comment accordingly.
  - shawntan 2y ago
    You can't really be blamed though, the language in the paper does seem to state what you originally said. Might be a matter of taste but I don't think it's quite accurate. The prior work they referenced actually did account for finite precision cases and why they didn't think it was useful to prove the result with those premises. In this work they simply argued from their own perspective why finite precision made more sense. The whole sub-field is kinda messy and I get quoted differing results all the time. Edit: Also, your original point stands, obviously. Sorry for nitpicking on your post, but I also just thought people should know more about the nuances of this stuff.

aurareturn 2y ago

> You can say the same thing about humans, provided they are allowed to think across as many years/generations as needed. Isn’t this a good thing since compute can be scaled so that the LLM can do generations of human thinking in a much shorter amount of time? Say humans can solve quantum gravity in 100 years of thinking by 10,000 really smart people. If one AGI is equal to 1 really smart person. Scale enough compute for 1 million AGI and we can solve quantum gravity in a year. The major assumption here is that transformers can indeed solve every problem humans can.

wizzwizz4 2y ago
> Isn’t this a good thing since compute and be scaled so that the LLM can do generations of human thinking in a much shorter amount of time? But it can't. There isn't enough planet. > The major assumption here is that transformers can indeed solve every problem humans can. No, the major assumptions are (a) that ChatGPT can, and (b) that we can reduce the resource requirements by many orders of magnitude. The former assumption is highly-dubious, and the latter is plainly false. Transformers are capable of representing any algorithm, if they're allowed to be large enough and run large enough. That doesn't give them any special algorithm-finding ability, and finding the correct algorithms is the hard part of the problem!
- aurareturn 2y ago
  > But it can't. There isn't enough planet. How much resource are you assuming an AGI would consume?
  - wizzwizz4 2y ago
    Are we talking about "an AGI", or are we talking about overfitting large transformer models with human-written corpora and scaling up the result? "An AGI"? I have no idea what that algorithm might look like. I do know that we can cover the majority of cases with not too much effort, so it all depends on the characteristics of that long tail. ChatGPT-like transformer models? We know what that looks like, despite the AI companies creatively misrepresenting the resource use (ref: https://www.bnnbloomberg.ca/business/technology/2024/08/21/how-tech-companies-are-obscuring-ais-real-carbon-footprint/ https://www.bnnbloomberg.ca/business/technology/2024/08/21/h...). Look at https://arxiv.org/pdf/2404.06405 https://arxiv.org/pdf/2404.06405: > Combining Wu’s method with the classic synthetic methods of deductive databases and angle, ratio, and distance chasing solves 21 out of 30 methods by just using a CPU-only laptop with a time limit of 5 minutes per problem. AlphaGeometry had an entire supercomputer cluster, and dozens of hours. GOFAI approaches have a laptop and five minutes. Scale that inconceivable inefficiency up to AGI, and the total power output of the sun may not be enough.

whimsicalism 2y ago

it's a TCS result. seems like many commenting don't know about computability

Veedrac 2y ago

> Wake me up when a LLM figures out stable fusion or room temperature superconductors. Man, the goalposts these days.

WalterSear 2y ago
Shh!! It's working! It's working!
FeepingCreature 2y ago
"I love [goalposts]. I love the whooshing noise they make as they go by." --Douglas Adams, slightly adjusted