16 ms·

Will a prompt that enables GPT-4 to solve easy Sudoku puzzles be found?

37 points by kilobit 3y ago

brucethemoose2 3y ago
A relevant PR: https://github.com/ggerganov/llama.cpp/pull/1773 https://github.com/ggerganov/llama.cpp/pull/1773
version_five 3y ago
> 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 3y ago
  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.
- AdieuToLogic 3y ago
  > 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 3y ago
    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 3y ago
      > 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 https://en.wikipedia.org/wiki/Bayesian_statistics
- shawntan 3y ago
  I recommend reading the theoretical work on the computational capabilities of Transformers: https://twitter.com/lambdaviking/status/1630581475425828864 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/ 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 3y ago
    > 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 3y ago
      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 3y ago
        > 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.
charcircuit 3y ago
Only allowing 50 generations makes this very hard.
heliophobicdude 3y ago
The title is funny to me. We should consider a new computation complexity class for LLMs. Let's call the ones that can be solved with a prompt, Promptable. For the problems that we cannot reliably solve with a single prompt yet, let's call them non-deterministic promptable, or NP. Question is, for most of these hard problems, is there a prompt that can solve them? Better yet, is there a prompt good enough that we collapse all of the hardest problems in NP with a single prompt? Will we ever know if NP can be reduced to P???
- AdieuToLogic 3y ago
  > Will we ever know if NP can be reduced to P??? My opinion is that it cannot, due to the unbounded nature of NP problems[0]. Regarding sudoku specifically, the question is a bit more nuanced (as described here[1]). As for the NP nature of sudoko in its general form, a short but very informative description can be found here[2]. HTH 0 - https://en.wikipedia.org/wiki/NP_(complexity) https://en.wikipedia.org/wiki/NP_(complexity) 1 - https://stackoverflow.com/questions/50703174/is-sudoku-np-complete/50703232#50703232 https://stackoverflow.com/questions/50703174/is-sudoku-np-co... 2 - http://www.cs.ox.ac.uk/people/paul.goldberg/FCS/sudoku.html http://www.cs.ox.ac.uk/people/paul.goldberg/FCS/sudoku.html
- janalsncm 3y ago
  Are large language models even Turing complete? Or more specifically, is there something we can say about LLMs as a class with respect to this question? For any architecture like Vaswani’s GPT or a bigger iteration of it, eventually you run out of attention heads and layers. If the answer is categorically no, then any sufficiently sophisticated code is not “promotable”. However, I don’t think there’s anything in principle which prevents LLMs from being Turing complete.
  - dragonwriter 3y ago
    > Are large language models even Turing complete? Idealized deterministic computing systems are the only thing that can be Turing complete, actual systems cannot be (because Turing completeness requires infinite space), LLMs are actual systems, and also are not limited-space approximation of idealized deterministic systems (they are, I suppose, deterministic if you know all the relevant parameters, including potentially some that are hardware-dependent, but they generally are a deterministic approximation of a nondeterministic system.) You can, of course, prompt an LLM to predict the output of a deterministic system and to do direct computation, but, absent an interface to external tools that actually do the computation, the results for that are notoriously unreliable.
earthboundkid 3y ago
An LLM is a tool. It is a very versatile tool. It can be used in many situations. It does not therefore follow that it should be used in all situations. Even if you wanted to use an AI to solve sudoku, there is no particular reason to begin with a model trained for language modeling instead of a model better suited to the task.
- thumbuddy 3y ago
  I don't get it there are so many ways to solve sudokus why does anyone care about this anyways?
  - jyap 3y ago
    It’s just a well known problem case that has a straightforward answer that is easily verifiable. Eg. Can a model play tic-tac-toe or solve chess puzzles
    - thumbuddy 3y ago
      I feel like it's kind of a weird question because if you change the random seed enough times maybe one of them could be good at chess puzzles but suck at being a chat bot, or be good at sudokus but be a horrible pair programmer. I don't know what value a lot of these questions bring once a model hits a trillion parameters of which none or very very few are understood.
  - coldtea 3y ago
    Well, it's not really about finding a way to solve sudokus. Nobody involved in this cares for that as a goal in itself. It's about the mystery of why an LLM can't do it well. It's about the challenge of finding a way (prompt) to get it to. It's about what this reveals about the inner workings and limitations of an LLM.
    - thumbuddy 3y ago
      So maybe I think about things a little differently, but is there a theoretical reason why we should expect a large language model to be good at sudokus? I remember not long ago they often struggled with adding two numbers
akrolsmir 3y ago
Austin from Manifold here - cool to see this trending! I thought the structure of this prediction market was especially cool, as it forms a collaborative, crowdsourced puzzle challenge to generate the perfect prompt. (I've personally bet yes, but not sure if that prediction is holding up...)
andythemoron 3y ago
Seeing this thread makes me want to bust out some Prolog.
SomewhatLikely 3y ago
I haven't seen prediction contacts that can be resolved at 50% before. It seems like that throws off the interpretation of the probability.
swayvil 3y ago
Can we use this technology to find a recognizable pattern in any complex blob of data? Is that how this works? How about, "Given 100000 readings from a person's body/brain, determine whether they are lying". Can we do that?
- eschaton 3y ago
  I don’t understand how so many people on Hacker News engage in this line of questioning. If by “this technology” you mean “large neural networks” the answer is yes, and we’ve been doing so for several decades now. That’s very specifically what they’re good at. If you mean “LLMs like ChatGPT” specifically, then no, they’re extremely large neural networks trained on very specific data sets. To perform a different recognition task, you train with different data sets. Where does this idea that ChatGPT and friends are general-purpose come from?
  - famouswaffles 3y ago
    >Where does this idea that ChatGPT and friends are general-purpose come from? Maybe reality? https://general-pattern-machines.github.io/ https://general-pattern-machines.github.io/ Large Language Models are as general purpose as they come especially for Machine Learning. They generalize to any kind of pattern, linguistic or not.
    - swayvil 3y ago
      Ya. They've used NN for recognizing faces, airplanes, trolls, songs... all kinds of stuff. Gleaning useful order from vast dizzying complexity is the name of the game. Or so is my rudimentary understanding.
- famouswaffles 3y ago
  >Can we use this technology to find a recognizable pattern in any complex blob of data? Is that how this works? Possibly in general. https://general-pattern-machines.github.io/ https://general-pattern-machines.github.io/ As for your example, I don't think so.
supersat 3y ago
Unlikely, for reasons explained in this video: https://youtu.be/bEovhfxJsM4?t=2339 https://youtu.be/bEovhfxJsM4?t=2339 However, it apparently can write a program using the Z3 SAT solver to find a solution.
- throwawaylinux 3y ago
  > However, it apparently can write a program using the Z3 SAT solver to find a solution. Not that it's unimpressive in general that a LLM can write a program from a prompt like that, but for this particular juxtaposition it doesn't seem like it's especially interesting or impressive that it can write such a program. A SAT program is basically just re-stating the the rules in a particular form. It doesn't even have to be able to apply those rules. The solver does the hard work.
  - kaba0 3y ago
    Also, if it has enough training data to know how to write such a SAT solver problem, it has surely seen sudoku exercises as part of that data set..
supersat 3y ago
Unlikely, for reasons explained in this video: https://youtu.be/bEovhfxJsM4?t=2339 https://youtu.be/bEovhfxJsM4?t=2339 However, apparently it can write a program using the Z3 SAT solver to find a solution.
- zacmps 3y ago
  It seems like it might be possible to get around this by letting the model emit moves like ` discard last 5` which would also let it keep a history of it's previous branches.
marmakoide 3y ago
Will a prompt that enables a prompt that enables GPT-4 to solve easy Sudoku puzzles be found ? I don't know how much meta-prompting have been explored. Maybe it's where The Singularity is at ?
dave333 3y ago
For most sudoku puzzles solving each cell is a logic puzzle that can be expressed in words just as current solvers have it in code. It can try to solve each vacant cell in turn using each of its rules until it finds a solution for that cell. And then it can be told to keep trying to solve another cell until it finishes the puzzle. Brute force with a core of logic.

37 points by kilobit 3y ago

A relevant PR: https://github.com/ggerganov/llama.cpp/pull/1773 https://github.com/ggerganov/llama.cpp/pull/1773

> 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 3y ago
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.
AdieuToLogic 3y ago
> 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 3y ago
  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 3y ago
    > 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 https://en.wikipedia.org/wiki/Bayesian_statistics
shawntan 3y ago
I recommend reading the theoretical work on the computational capabilities of Transformers: https://twitter.com/lambdaviking/status/1630581475425828864 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/ 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 3y ago
  > 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 3y ago
    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 3y ago
      > 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.

charcircuit 3y ago

Only allowing 50 generations makes this very hard.

heliophobicdude 3y ago

The title is funny to me. We should consider a new computation complexity class for LLMs. Let's call the ones that can be solved with a prompt, Promptable. For the problems that we cannot reliably solve with a single prompt yet, let's call them non-deterministic promptable, or NP. Question is, for most of these hard problems, is there a prompt that can solve them? Better yet, is there a prompt good enough that we collapse all of the hardest problems in NP with a single prompt? Will we ever know if NP can be reduced to P???

AdieuToLogic 3y ago
> Will we ever know if NP can be reduced to P??? My opinion is that it cannot, due to the unbounded nature of NP problems[0]. Regarding sudoku specifically, the question is a bit more nuanced (as described here[1]). As for the NP nature of sudoko in its general form, a short but very informative description can be found here[2]. HTH 0 - https://en.wikipedia.org/wiki/NP_(complexity) https://en.wikipedia.org/wiki/NP_(complexity) 1 - https://stackoverflow.com/questions/50703174/is-sudoku-np-complete/50703232#50703232 https://stackoverflow.com/questions/50703174/is-sudoku-np-co... 2 - http://www.cs.ox.ac.uk/people/paul.goldberg/FCS/sudoku.html http://www.cs.ox.ac.uk/people/paul.goldberg/FCS/sudoku.html
janalsncm 3y ago
Are large language models even Turing complete? Or more specifically, is there something we can say about LLMs as a class with respect to this question? For any architecture like Vaswani’s GPT or a bigger iteration of it, eventually you run out of attention heads and layers. If the answer is categorically no, then any sufficiently sophisticated code is not “promotable”. However, I don’t think there’s anything in principle which prevents LLMs from being Turing complete.
- dragonwriter 3y ago
  > Are large language models even Turing complete? Idealized deterministic computing systems are the only thing that can be Turing complete, actual systems cannot be (because Turing completeness requires infinite space), LLMs are actual systems, and also are not limited-space approximation of idealized deterministic systems (they are, I suppose, deterministic if you know all the relevant parameters, including potentially some that are hardware-dependent, but they generally are a deterministic approximation of a nondeterministic system.) You can, of course, prompt an LLM to predict the output of a deterministic system and to do direct computation, but, absent an interface to external tools that actually do the computation, the results for that are notoriously unreliable.

earthboundkid 3y ago

An LLM is a tool. It is a very versatile tool. It can be used in many situations. It does not therefore follow that it should be used in all situations. Even if you wanted to use an AI to solve sudoku, there is no particular reason to begin with a model trained for language modeling instead of a model better suited to the task.

thumbuddy 3y ago
I don't get it there are so many ways to solve sudokus why does anyone care about this anyways?
- jyap 3y ago
  It’s just a well known problem case that has a straightforward answer that is easily verifiable. Eg. Can a model play tic-tac-toe or solve chess puzzles
  - thumbuddy 3y ago
    I feel like it's kind of a weird question because if you change the random seed enough times maybe one of them could be good at chess puzzles but suck at being a chat bot, or be good at sudokus but be a horrible pair programmer. I don't know what value a lot of these questions bring once a model hits a trillion parameters of which none or very very few are understood.
- coldtea 3y ago
  Well, it's not really about finding a way to solve sudokus. Nobody involved in this cares for that as a goal in itself. It's about the mystery of why an LLM can't do it well. It's about the challenge of finding a way (prompt) to get it to. It's about what this reveals about the inner workings and limitations of an LLM.
  - thumbuddy 3y ago
    So maybe I think about things a little differently, but is there a theoretical reason why we should expect a large language model to be good at sudokus? I remember not long ago they often struggled with adding two numbers

akrolsmir 3y ago

Austin from Manifold here - cool to see this trending! I thought the structure of this prediction market was especially cool, as it forms a collaborative, crowdsourced puzzle challenge to generate the perfect prompt. (I've personally bet yes, but not sure if that prediction is holding up...)

andythemoron 3y ago

Seeing this thread makes me want to bust out some Prolog.

SomewhatLikely 3y ago

I haven't seen prediction contacts that can be resolved at 50% before. It seems like that throws off the interpretation of the probability.

swayvil 3y ago

Can we use this technology to find a recognizable pattern in any complex blob of data? Is that how this works? How about, "Given 100000 readings from a person's body/brain, determine whether they are lying". Can we do that?

eschaton 3y ago
I don’t understand how so many people on Hacker News engage in this line of questioning. If by “this technology” you mean “large neural networks” the answer is yes, and we’ve been doing so for several decades now. That’s very specifically what they’re good at. If you mean “LLMs like ChatGPT” specifically, then no, they’re extremely large neural networks trained on very specific data sets. To perform a different recognition task, you train with different data sets. Where does this idea that ChatGPT and friends are general-purpose come from?
- famouswaffles 3y ago
  >Where does this idea that ChatGPT and friends are general-purpose come from? Maybe reality? https://general-pattern-machines.github.io/ https://general-pattern-machines.github.io/ Large Language Models are as general purpose as they come especially for Machine Learning. They generalize to any kind of pattern, linguistic or not.
  - swayvil 3y ago
    Ya. They've used NN for recognizing faces, airplanes, trolls, songs... all kinds of stuff. Gleaning useful order from vast dizzying complexity is the name of the game. Or so is my rudimentary understanding.
famouswaffles 3y ago
>Can we use this technology to find a recognizable pattern in any complex blob of data? Is that how this works? Possibly in general. https://general-pattern-machines.github.io/ https://general-pattern-machines.github.io/ As for your example, I don't think so.

supersat 3y ago

Unlikely, for reasons explained in this video: https://youtu.be/bEovhfxJsM4?t=2339 https://youtu.be/bEovhfxJsM4?t=2339 However, it apparently can write a program using the Z3 SAT solver to find a solution.

throwawaylinux 3y ago
> However, it apparently can write a program using the Z3 SAT solver to find a solution. Not that it's unimpressive in general that a LLM can write a program from a prompt like that, but for this particular juxtaposition it doesn't seem like it's especially interesting or impressive that it can write such a program. A SAT program is basically just re-stating the the rules in a particular form. It doesn't even have to be able to apply those rules. The solver does the hard work.
- kaba0 3y ago
  Also, if it has enough training data to know how to write such a SAT solver problem, it has surely seen sudoku exercises as part of that data set..

supersat 3y ago

Unlikely, for reasons explained in this video: https://youtu.be/bEovhfxJsM4?t=2339 https://youtu.be/bEovhfxJsM4?t=2339 However, apparently it can write a program using the Z3 SAT solver to find a solution.

zacmps 3y ago
It seems like it might be possible to get around this by letting the model emit moves like ` discard last 5` which would also let it keep a history of it's previous branches.

marmakoide 3y ago

Will a prompt that enables a prompt that enables GPT-4 to solve easy Sudoku puzzles be found ? I don't know how much meta-prompting have been explored. Maybe it's where The Singularity is at ?

dave333 3y ago

For most sudoku puzzles solving each cell is a logic puzzle that can be expressed in words just as current solvers have it in code. It can try to solve each vacant cell in turn using each of its rules until it finds a solution for that cell. And then it can be told to keep trying to solve another cell until it finishes the puzzle. Brute force with a core of logic.