10 ms·

In the words of an author: "What is the performance limit when scaling LLM inference? Sky's the limit. We have mathematically proven that transformers can sol

In the words of an author: "What is the performance limit when scaling LLM inference? Sky's the limit. We have mathematically proven that transformers can solve any problem, provided they are allowed to generate as many intermediate reasoning tokens as needed. Remarkably, constant depth is sufficient. http://arxiv.org/abs/2402.12875 http://arxiv.org/abs/2402.12875 (ICLR 2024)" https://x.com/denny_zhou/status/1835761801453306089 https://x.com/denny_zhou/status/1835761801453306089

candiddevmike 2y ago
> 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
ec109685 2y ago
Is this the infinite monkey Shakespeare trope?
- CamperBob2 2y ago
  Yeah. Monkeys. Monkeys that write useful C and Python code that needs a bit less revision every time there's a model update. Can we just give the "stochastic parrot" and "monkeys with typewriters" schtick a rest? It made for novel commentary three or four years ago, but at this point, these posts themselves read like the work of parrots. They are no longer interesting, insightful, or (for that matter) true.
  - visarga 2y ago
    If you think about it, humans necessarily use abstractions, from the edge detectors in retina to concepts like democracy. But do we really understand? All abstractions leak, and nobody knows the whole stack. For all the poorly grasped abstractions we are using, we are also just parroting. How many times are we doing things because "that is how they are done" never wondering why? Take ML itself, people are saying it's little more than alchemy (stir the pile). Are we just parroting approaches that have worked in practice without real understanding? Is it possible to have centralized understanding, even in principle, or is all understanding distributed among us? My conclusion is that we have a patchwork of partial understanding, stitched together functionally by abstractions. When I go to the doctor, I don't study medicine first, I trust the doctor. Trust takes the place of genuine understanding. So humans, like AI, use distributed and functional understanding, we don't have genuine understanding as meant by philosophers like Searle in the Chinese Room. No single neuron in the brain understands anything, but together they do. Similarly, no single human understands genuinely, but society together manages to function. There is no homunculus, no centralized understander anywhere. We humans are also stochastic parrots of abstractions we don't really grok to the full extent.
    - kaechle 2y ago
      Great points. We're pattern-matching shortcut machines, without a doubt. In most contexts, not even good ones. > When I go to the doctor, I don't study medicine first, I trust the doctor. Trust takes the place of genuine understanding. The ultimate abstraction! Trust is highly irrational by definition. But we do it all day every day, lest we be classified as psychologically unfit for society. Which is to say, mental health is predicated on a not-insignificant amount of rationalizations and self-deceptions. Hallucinations, even.
shawntan 2y ago
Theoretical results exist that try to quantify the number of CoT tokens needed to reach different levels of computational expressibility: https://arxiv.org/pdf/2310.07923 https://arxiv.org/pdf/2310.07923 TL;DR: Getting to Turing completeness can require polynomial CoT tokens, wrt the input problem size. For a field that constantly harps on parallelism and compute efficiency, this requirement seems prohibitive. We really need to get away from constant depth architectures.
- benkuykendall 2y ago
  > Getting to Turing completeness can require polynomial CoT tokens, wrt the input problem size. So, as stated, this is impossible since it violates the Time Hierarchy Theorem. The actual result of the paper is that any poly-time computable function can be computed with poly-many tokens. Which is... not a particularly impressive bound? Any non-trivial fixed neural network can, for instance, compute the NAND of two inputs. And any polynomial computable function can be computed with a polynomial number of NAND gates.
  - shawntan 2y ago
    > The actual result of the paper is that any poly-time computable function can be computed with poly-many tokens. You're right. Re: NAND of two inputs. Isn't this doable even by a single layer (no hidden layers) neural network? Re: Polynomial computable function. I'm assuming this makes no assumption of constant-depth. Because my entire point was that the result of this paper is not actually impressive AND covered by a previous paper. Hopefully that's clearer.
deleted 2y ago
[deleted]
__loam 2y ago
> We have mathematically proven that transformers can solve any problem We should require that you've passed an algorithms and a thermodynamics class before you can post.
- nopinsight 2y ago
  To be clear I think the tweet is a bit exaggerated (and the word ‘performance’ there doesn’t take into account efficiency, for example) but I don’t have the time to read the full paper (just skimmed the abstract and conclusion). I quoted the tweet by an author for people to discuss since it’s still a fairly remarkable result.
- bonoboTP 2y ago
  This is an accepted ICLR paper by authors from Stanford, Toyota and Google. That's not a guarantee for anything, of course, but they likely know basic algorithms and the second law. You can certainly argue against their claims, but you need to put in the legwork.
  - __loam 2y ago
    I don't think I should need to argue with the absurd claim that these can solve any problem.
tooltower 2y ago
Constant depth circuits can solve everything? I feel like I missed some important part of circuit complexity. Or this is BS.
- whimsicalism 2y ago
  CoT means you're adding loops
- shawntan 2y ago
  Using CoT implicitly increases the depth of the circuit. But yes, poorly worded.
m3kw9 2y ago
Sort of like quantum superposition state? So here is an idea, using quantum to produce all possible inferences and use some not yet invented algorithms to collapse to the final result
deleted 2y ago
[deleted]
riku_iki 2y ago
> Remarkably, constant depth is sufficient. I think article also says log(n) embedding size (width?) is required, where n is size of input.
ljsprague 2y ago
Skynet's the limit.
tsimionescu 2y ago
One question, if anyone knows the details: does this prove that there exists a single LLM that can approximate any function to arbitrary precision given enough CoT, or does it prove that for every function, there exists a Transformer that fits those criteria? That is, does this prove that a single LLM can solve any problem, or that for any problem, we can find an LLM that solves it?
- jstanley 2y ago
  Doesn't the latter imply the former? If it's possible to find an LLM for any given problem, then find an LLM for the problem "find an LLM for the problem and then evaluate it" and then evaluate it, and then you have an LLM that can solve any problem. It's the "Universal Turing Machine" for LLMs. I wonder what's the LLM equivalent of the halting problem?
  - progval 2y ago
    > It's the "Universal Turing Machine" for LLMs. A closer analogy is the Hutter Search (http://hutter1.net/ai/pfastprg.pdf http://hutter1.net/ai/pfastprg.pdf), as it is also an algorithm that can solve any problem. And it is probably too inefficient to use in practice, like the Hutter Search.
  - deleted 2y ago
    [deleted]
  - detourdog 2y ago
    In the late ‘80s they were called expert systems. Most demonstrations were regarding troubleshooting large systems, industrial processes, and education.
DarkNova6 2y ago
The more interesting is whether the ability of reason and solve problems scales linearly or logarithmically.
deleted 2y ago
[deleted]

candiddevmike 2y ago

> 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

ec109685 2y ago

Is this the infinite monkey Shakespeare trope?

CamperBob2 2y ago
Yeah. Monkeys. Monkeys that write useful C and Python code that needs a bit less revision every time there's a model update. Can we just give the "stochastic parrot" and "monkeys with typewriters" schtick a rest? It made for novel commentary three or four years ago, but at this point, these posts themselves read like the work of parrots. They are no longer interesting, insightful, or (for that matter) true.
- visarga 2y ago
  If you think about it, humans necessarily use abstractions, from the edge detectors in retina to concepts like democracy. But do we really understand? All abstractions leak, and nobody knows the whole stack. For all the poorly grasped abstractions we are using, we are also just parroting. How many times are we doing things because "that is how they are done" never wondering why? Take ML itself, people are saying it's little more than alchemy (stir the pile). Are we just parroting approaches that have worked in practice without real understanding? Is it possible to have centralized understanding, even in principle, or is all understanding distributed among us? My conclusion is that we have a patchwork of partial understanding, stitched together functionally by abstractions. When I go to the doctor, I don't study medicine first, I trust the doctor. Trust takes the place of genuine understanding. So humans, like AI, use distributed and functional understanding, we don't have genuine understanding as meant by philosophers like Searle in the Chinese Room. No single neuron in the brain understands anything, but together they do. Similarly, no single human understands genuinely, but society together manages to function. There is no homunculus, no centralized understander anywhere. We humans are also stochastic parrots of abstractions we don't really grok to the full extent.
  - kaechle 2y ago
    Great points. We're pattern-matching shortcut machines, without a doubt. In most contexts, not even good ones. > When I go to the doctor, I don't study medicine first, I trust the doctor. Trust takes the place of genuine understanding. The ultimate abstraction! Trust is highly irrational by definition. But we do it all day every day, lest we be classified as psychologically unfit for society. Which is to say, mental health is predicated on a not-insignificant amount of rationalizations and self-deceptions. Hallucinations, even.

shawntan 2y ago

Theoretical results exist that try to quantify the number of CoT tokens needed to reach different levels of computational expressibility: https://arxiv.org/pdf/2310.07923 https://arxiv.org/pdf/2310.07923 TL;DR: Getting to Turing completeness can require polynomial CoT tokens, wrt the input problem size. For a field that constantly harps on parallelism and compute efficiency, this requirement seems prohibitive. We really need to get away from constant depth architectures.

benkuykendall 2y ago
> Getting to Turing completeness can require polynomial CoT tokens, wrt the input problem size. So, as stated, this is impossible since it violates the Time Hierarchy Theorem. The actual result of the paper is that any poly-time computable function can be computed with poly-many tokens. Which is... not a particularly impressive bound? Any non-trivial fixed neural network can, for instance, compute the NAND of two inputs. And any polynomial computable function can be computed with a polynomial number of NAND gates.
- shawntan 2y ago
  > The actual result of the paper is that any poly-time computable function can be computed with poly-many tokens. You're right. Re: NAND of two inputs. Isn't this doable even by a single layer (no hidden layers) neural network? Re: Polynomial computable function. I'm assuming this makes no assumption of constant-depth. Because my entire point was that the result of this paper is not actually impressive AND covered by a previous paper. Hopefully that's clearer.

deleted 2y ago

[deleted]

__loam 2y ago

> We have mathematically proven that transformers can solve any problem We should require that you've passed an algorithms and a thermodynamics class before you can post.

nopinsight 2y ago
To be clear I think the tweet is a bit exaggerated (and the word ‘performance’ there doesn’t take into account efficiency, for example) but I don’t have the time to read the full paper (just skimmed the abstract and conclusion). I quoted the tweet by an author for people to discuss since it’s still a fairly remarkable result.
bonoboTP 2y ago
This is an accepted ICLR paper by authors from Stanford, Toyota and Google. That's not a guarantee for anything, of course, but they likely know basic algorithms and the second law. You can certainly argue against their claims, but you need to put in the legwork.
- __loam 2y ago
  I don't think I should need to argue with the absurd claim that these can solve any problem.

tooltower 2y ago

Constant depth circuits can solve everything? I feel like I missed some important part of circuit complexity. Or this is BS.

whimsicalism 2y ago
CoT means you're adding loops
shawntan 2y ago
Using CoT implicitly increases the depth of the circuit. But yes, poorly worded.

m3kw9 2y ago

Sort of like quantum superposition state? So here is an idea, using quantum to produce all possible inferences and use some not yet invented algorithms to collapse to the final result

deleted 2y ago

[deleted]

riku_iki 2y ago

> Remarkably, constant depth is sufficient. I think article also says log(n) embedding size (width?) is required, where n is size of input.

ljsprague 2y ago

Skynet's the limit.

tsimionescu 2y ago

One question, if anyone knows the details: does this prove that there exists a single LLM that can approximate any function to arbitrary precision given enough CoT, or does it prove that for every function, there exists a Transformer that fits those criteria? That is, does this prove that a single LLM can solve any problem, or that for any problem, we can find an LLM that solves it?

jstanley 2y ago
Doesn't the latter imply the former? If it's possible to find an LLM for any given problem, then find an LLM for the problem "find an LLM for the problem and then evaluate it" and then evaluate it, and then you have an LLM that can solve any problem. It's the "Universal Turing Machine" for LLMs. I wonder what's the LLM equivalent of the halting problem?
- progval 2y ago
  > It's the "Universal Turing Machine" for LLMs. A closer analogy is the Hutter Search (http://hutter1.net/ai/pfastprg.pdf http://hutter1.net/ai/pfastprg.pdf), as it is also an algorithm that can solve any problem. And it is probably too inefficient to use in practice, like the Hutter Search.
- deleted 2y ago
  [deleted]
- detourdog 2y ago
  In the late ‘80s they were called expert systems. Most demonstrations were regarding troubleshooting large systems, industrial processes, and education.

DarkNova6 2y ago

The more interesting is whether the ability of reason and solve problems scales linearly or logarithmically.

deleted 2y ago

[deleted]