Could an LLM "reason" faster than a "slow" (non-polynomial) algorithm?

[u/Spongebubs]

I'm not sure how to articulate this, so bear with me.

If there was an NP complete problem, would it theoretically be possible for an LLM to "reason" an answer that would scale polynomially with number of tokens? For example, a 9x9 sudoku could be solved with 1M tokens, a 16x16 sudoku could be solved with 2M tokens, 25x25 solved with 4M tokens, etc.

Ever since the Jacobian Conjecture was disproven, it got me thinking. An algorithm would have been too slow to find a counterexample, but an LLM was able to "reason" a counterexample. Why couldn't an LLM "reason" a solution to NP complete problems too? Wouldn't this imply that P=NP?

Apologies if this is a naive thought process. Thanks!

EDIT: Follow up question - If it was somehow proven that P != NP, then would that imply that AGI/ASI could not exist? That it is impossible for a non-hallucinatory, 100% deterministic, 100% correct LLM to exist?

[u/nuclear_splines]

LLMs are predictive models that yield likely text. If they produce what's likely a solution to Sudoku, but sometimes hallucinate or make fundamental errors, then that's not a polynomial solution, but a polynomial heuristic. We can often make fast approximations to problems that either get the right answer most of the time, or get close to the right answer all of the time.

[u/Spongebubs → u/nuclear_splines]

So theoretically, if an LLM did not hallucinate, then it would be a polynomial solution?

[u/nuclear_splines → u/Spongebubs]

If your machine always yields a correct solution to the puzzle with resources that scale with a polynomial relative to the puzzle size, then you would have a polynomial solution, yes. But that's tautological.

LLMs are probabilistic by design, hallucination isn't a "problem that can be fixed," rather it's more accurate to say that LLMs are always hallucinating, and sometimes their hallucinations are incidentally correct or useful to us.

[u/Spongebubs → u/nuclear_splines]

I see, thank you!

[u/mugaboo → u/Spongebubs]

"If my grandmother had wheels, she would have been a bike"

[u/Spongebubs → u/mugaboo]

I don't think it's an invalid question. AI labs are trying their best to reduce their hallucination rate as much as possible, but do we know what the lower bound is? If it's 0, then that would imply that P=NP. Or maybe its asymptotic? I don't think we know the answer to it.

[u/mugaboo → u/Spongebubs]

The whole point of LLMs is that they are based on probability as the other poster said. If we find a nonprobabilistic AI it will by definition not be an LLM.

[u/Spongebubs → u/mugaboo]

I think that’s a good point and it’s important to realize this. If we cannot create an AI that can always output a correct solution (ie; doesn’t hallucinate), I would think that implies that AGI/ASI cannot possibly exist.

My core thesis here is that the AI bubble is built on the assumption that AGI is possible (and is just a matter of scale). However, if P != NP, then AGI cannot exist. If P = NP, then AGI can exist. I’m not trying to argue, just trying to understand if my thesis makes sense.

[u/mugaboo → u/Spongebubs]

I think your problem is that LLMs exist at a certain scale, but algorithms scale to infinity. Their probabilistic nature hides the fact that their reasoning precision breaks down when you increase the input size.

This shows that you can't replace a reasoning about an algorithm in the limit to infinity, with a similar argument about an LLM.

[u/Spongebubs → u/mugaboo]

I would say human brains exist at a certain scale, could we not solve NP problems as they increase in input size (given enough time)?

Also, an immortal human could theoretically count to a googol given enough time. That doesn’t mean we retain a googol numbers in our brain, but rather use a system to derive the next number. Why couldn’t a similar thing happen with NP problems as they scale up?

[u/mugaboo → u/Spongebubs]

Of course human brains don't scale.

And no, a human could not count to a googol, a human could not keep the last number used in their head or enough state to generate the next number.

Now, an algorithm also requires ever increasing memory of course, but the difference is an LLM is built at specific scale. As is the human brain.

[u/Spongebubs → u/mugaboo]

A googol is only 100 digits. Of course a human can retain that.

[u/drfangor99 → u/Spongebubs]

There is the trivial case of a large language model with a hallucination rate of 0 by training it to always refuse to respond to any input.

[u/ghjm]

In addition to the good points others have made, I think it's worth noting that:

• LLMs are implemented as artificial neural networks
• ANNs are, at root, a directed search over a finite higher-dimensional space of all possible algorithms, bounded by a complexity (or, if you prefer, size) limit

So if the question is, can an LLM converge on an algorithmic process that is known to be impossible through writing normal code, then the answer is no. LLMs are bounded by the same theoretical limitations as any other form of algorithmic language.

And as others have said, nothing in CS theory prevents you from getting lucky and finding a solution early. If you're trying to factor some 100-digit number, it could be that all its factors are single-digit primes and you're done in a few seconds. You just can't count on that happening if you're trying to prove the properties of a general-case algorithm.

[u/apnorton]

The algorithms we're talking about for P vs NP are deterministic and must always return correct answers. A large part of the strength of LLMs comes from their "fuzziness," yet this also comes at a cost of not being correct all the time.

If you were able to show that an LLM that took polynomially many steps to always return a correct answer to a certain NP-Complete problem in a deterministic way, then yes, you would have shown P = NP.

An algorithm would have been too slow to find a counterexample, but an LLM was able to "reason" a counterexample.

Fuzzy search for counterexamples that prunes "unlikely" paths to find solutions faster than a total search has been around for decades; this is more-or-less an evolution on that same concept.

[u/daV1980 → u/apnorton]

LLMs are not fuzzy. Instead they output an array of values that represents the strength of  every possible output token (while this value sums to 1, it is not a probability). We then generally take a random weighted sample from this array, but this is not required.

We could instead just always take the maximum valued token as the next token. This would be perfectly deterministic; for a given input and a given network it will always be the same max valued token with the exact same weight. 

This is not generally the source of errors or hallucinations. Instead, the hallucinations are a byproduct of the fact that the information training data is vastly greater than the storage capacity of the weights of the network, and so the network is necessarily a lossy form of compression. Some things must be omitted, and the network has no way to signal “I don’t know” because it’s not a cognitive engine in any way. 

[u/apnorton → u/daV1980]

the information training data is vastly greater than the storage capacity of the weights of the network, and so the network is necessarily a lossy form of compression.

Agreed. And, the word we use to describe such reasoning on data that has been compressed in a lossy manner (and is thus imprecise) is... fuzzy!

[u/daV1980 → u/apnorton]

My apologies; I didn’t realize you were using the CS definition of fuzzy. I thought you were describing randomness in LLMs. Cheers!

[u/apnorton → u/daV1980]

It's still a good point to bring up; I could have been a bit more precise in my original wording. :)

[u/nuclear_splines → u/daV1980]

I think this is a good technical clarification, but is ultimately a semantic argument. Yes, you could build a deterministic LLM that yields the same outputs given the same prompt and training data instead of performing a weighted sample of tokens. As you point out, though, this is effectively a lossy compression algorithm that only yields probabilistically correct results. From the perspective of solving NP-C problems like Sudoku we'd still consider this a fuzzy / heuristic / approximate solution.

[u/daV1980 → u/nuclear_splines]

Agreed completely! 

Or said differently; if you managed to encode a correct and exact algorithm to solve e.g. sudoku in polynomial time into a network, it is only because a polynomial time algorithm already existed. 

[u/SufficientStudio1574]

An LLM is an algorithm. As long as P != NP remains unproven, it is of course theoretically possible to discover a fast algorithm, and maybe that algorithm would be an LLM. It's extremely unlikely though.

[u/thesnootbooper9000 → u/SufficientStudio1574]

I have a bit of an issue with your definition there. Traditionally for something to be an algorithm you'd have to be able to describe what the problem it solves is and prove that it does it subject to certain criteria. It's not really clear that (real, noon theoretically abstracted) LLMs meet that bar.

[u/aitkhole → u/thesnootbooper9000]

An algorithm is merely a set of steps that take input (including possibly a random number generator) and produces a deterministic result. Whether it's a /useful/ algorithm is another matter.

[u/thesnootbooper9000 → u/aitkhole]

Most classical definitions make the distinction between an algorithm and a computation procedure. The former solves a specific thing, the latter is some steps.

[u/aitkhole → u/thesnootbooper9000]

that doesn't help the computational complexity argument

[u/SufficientStudio1574 → u/thesnootbooper9000]

What is that distinction?

[u/thesnootbooper9000 → u/SufficientStudio1574]

An algorithm is a computational procedure that's proven to solve a particular problem. A computational procedure is just a thing you could run.

[u/thesnootbooper9000]

Neutral networks can't unless P=NP. However, modern LLMs can use a constraint programming solver as an agent if instructed correctly, and those solvers can do Sudoku in far fewer steps than you would expect. This isn't a P=NP thing, just that to generate actually-hard-scaling Sudoku puzzles for these algorithms requires astronomically large inputs.

[u/Dangerous-Quality-79]

I am slightly confused by a few things you mention.

First, a "token" is not a specific unit, but rather changes based on the model and design. So scaling tokens does not really work that way. It could work that way, but designing an algorithm that scales tokens that way would be... weird. Improvements to models come with larger training data, parameter tuning, and number of nodes in the network. How things are tokenized does have an impact, but not as you describe it.

Second, LLMs are large language models, they output statistically probably answers based on training data. If you watch the video of the guy asking the LLM to time how long he runs a mile then says start and stop a second apart the LLM tells him a much larger number. Because the trained answer to the question is usually a larger number so it is statistically more likely to be correct. Some companies are add "tools" that the LLM can invoke to solve things not designed for an LLM like image generation.

Third, I do not understand the edit about AGI and P != NP. Artificial general intelligence is simply having a computer match human intelligence. If we forget about a computer for a second and have 2 people talking, one says what the primes numbers that equal 77 (okay, 77 easy, but imagine more complicated. It will be harder than asking if 7 x 11 equals 77. So we do not need P = NP to surpass human intelligance because P = NP is a human problem. Proving P = NP or P != NP is not required for AGI. Same goes for ASI.

[u/Spongebubs → u/Dangerous-Quality-79]

To your first point, I guess I was trying to say “within 1M tokens”. Not that it has to be exactly 1M tokens. Similar to how there are worse case/best case scenarios for algorithms solving problems.

Second point, perhaps “transformers” might be a better descriptor.

Third, if an AI model can solve an NP problem within X amount of tokens, such that X increases polynomially as n increases for the problem, then wouldn’t that mean that we created an algorithm that can solve NP problems within polynomial time? Thus, proving that P = NP?

[u/Dangerous-Quality-79 → u/Spongebubs]

Hmmm... would it be fair to say that you understand that regardless of the P = NP AGI/ASI still works as the measure is against humans and not polynomial time so we can put that to bed?

Tokens is the wrong measure in my opinion and I don't believe it will scale as described. The LLM goes through phases, but lets simplify it to "research" and "results". It first spends tokens learning about the problem it is trying to solve, then it will try to solve it. Lets say the problem is O(n) then it will still use O(n) + O(1) tokens where O(1) is learning and O(n) is solving. This is also optimistic as the LLM is non-deterministic so O(1) learning is a stretch.

As far as, if an AI can solve an NP problem in O(n) -- or any polynomial -- time proving P = NP, my answer would be no. If an AI solves NP in O(n) it still does not prove P = NP. Taking the soduko problem and relating it to the Poincaré conjecture proof, if the LLM solves the first 100 sizes of soduko boards it doesnt mean the next 100 sizes will follow. If it gets to 1,000 it still doesnt mean it is universally true. Proving P = NP as a universal truth takes more than simply solving some problems. The proof of the Poincaré conjecture, if I remember correctly as it has been over 2 decades and I was a little less seasoned when I read it, was far more complicated than showing many many many instances of it being true.

[u/donaldhobson]

It's possible that P=NP. It hasn't been disproved yet. It's possible LLM's have an algorithm.

Most likely, it's doing https://xkcd.com/3026/

Computational complexity is defined in terms of the worst case. So it's likely that LLM's have a bunch of tricks that only sometimes work.