[version_five]

> Easy-rated Sudoku puzzle means a puzzle classified as easy by any reputable Sudoku site or puzzle generator. This market plans to use the LA Times(Sudoku - Free daily Sudoku games from the Los Angeles Times (latimes.com)) for judging, but I maintain the option to use a different Sudoku generator.

Is there any theoretical reason why an attention based llm could or couldn't generate an answer to an NP hard problem? As I understand, attention is N^2, but it's not obvious if that's relevant to the complexity of problems that can be solved. It's obviously not relevant to answers that are regurgitated, which may be all answers?

It would be better if "easy" had a mathematical definition.

[MichaelBurge]

A single forward pass shouldn't be able to, but remember the format allows it to be iterated. So it should be Turing Complete, if the error rate is low enough and enough iterations are allowed.

[shawntan]

I recommend reading the theoretical work on the computational capabilities of Transformers: https://twitter.com/lambdaviking/status/1630581475425828864 References to other work can probably be found in that article.

Shameless plug to my own blogpost about this: https://blog.wtf.sg/posts/2023-02-03-the-new-xor-problem/

TL;DR: The theoretical class of problems that Transformers can solve (without Chain-of-Thought style responses) is fairly limited. Generally, universal approximation proofs rely on infinite precision assumptions, which are not practical in reality. Empirical results also show very limited capabilities when tested on certain formal languages.

In the Sudoku case, the problem-length is limited, so one could conceptually make a large enough model that could memorise all solutions to all possible combinations of permissible sudoku boards, which could then just access and read out the solutions.

[gwern]

> The theoretical class of problems that Transformers can solve (without Chain-of-Thought style responses) is fairly limited.

Which is irrelevant because how would a Transformer emit a complete Sudoku solution in a single forward-pass/token in the first place?

[shawntan]

I suppose you mean in order to give the answer to a Sudoku puzzle, you'd need a string of tokens anyway: [(x,y) grid coordinates], [digit].

I think if we're getting specific to this particular Sudoku example, the CoT would probably involve a trace of the entire filling-in and backtracking steps that a solver would do.

My guess is that the straightforward output of the exact solution, even though it requires several tokens, wouldn't be enough to do the constraint resolution in Sudoku, you'd need the intermediate CoT "thinking out loud"

[gwern]

> I think if we're getting specific to this particular Sudoku example, the CoT would probably involve a trace of the entire filling-in and backtracking steps that a solver would do.

Yes, and maybe the occasional generation of the complete boardstate to date, because you don't want to leave the boardstate implicit and require it to be reconstructed within each forward pass - that's 'using up serial computations' that a Transformer can't afford. But if you periodically serialize the best-answer-to-date, you are more likely to be able to bite off a chewable chunk.

> My guess is that the straightforward output of the exact solution, even though it requires several tokens, wouldn't be enough to do the constraint resolution in Sudoku

A Transformer is not much different from an unrolled RNN without weight-sharing, so for any specific sudoku size, there should be some depth which does allow the worst-case amount of backtracking or other solution to the problem. (One way to show this would be to use the RASP programming language to program such a solver.) It's just it'd probably be bigger/deeper than you have available now.

[shawntan]

Right, I see your point. Since Sudoku is fixed-size, you can always construct a Transformer with the worse-case depth. That makes sense.

I was assuming given a trained Transformer, you wouldn't know how many effective "steps of computation" it contained, and so would probably have to resort to CoT.

[AdieuToLogic]

> Is there any theoretical reason why an attention based llm could or couldn't generate an answer to an NP hard problem?

Putting aside for the moment that a Large Language Model (LLM) is a predictive statistical model based on and producing from what consisted its training set, answering whether or not any algorithm can solve an NP hard problem first requires a clarification; is a brute force exhaustive search allowed?

If it is, I am unsure if an arbitrary LLM could find a solution due to the dependence on training. If not, I am confident in saying an LLM could not solve arbitrary NP hard problems in P time as that has yet to be proven possible AFAIK.

[epylar]

LLM's aren't statistical in the sense of memorizing percentages of words that come after other words. They are modeling a very high dimensional function using a neural net. I suppose they're statistical in the sense of learning how to mimic what they've seen, but this includes some very surprising emergent abilities as well.

[AdieuToLogic]

> LLM's aren't statistical in the sense of memorizing percentages of words that come after other words.

Agreed, in that LLM's are an improvement beyond Bayesian models[0].

> I suppose they're statistical in the sense of learning how to mimic what they've seen, but this includes some very surprising emergent abilities as well.

Your point of "mimic what they've seen" is what I mean by being predictive statistical models. And yes, there very well can be surprising, even emergent, output given depending on the training data set.

But to refocus back onto the original question the article presents, which is could an LLM somehow produce solutions to a problem category which has no solution with mathematical underpinning, is a bit fantastical IMHO.

0 - https://en.wikipedia.org/wiki/Bayesian_statistics