Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

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

manifold.markets

Post reply on HN
Print view View original

51–60 of 68 posts

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

#51

Post by thumbuddy »

skwirl wrote: post #27
objektif wrote: post #24

Earlier quoted context omitted.

What tasks would you say LLMs are good at that are not related to language?

It's very hard to define what is and is not "related to language" and this is kind of a fundamental question that seemed to get a lot of attention in the 20th century. Maybe these language models can help shine some light on that. According to OpenAI, GPT-4 scores 4 on AP Calculus BC, 5 on AP Statistics, 4 on AP Chemistry, 4 on AP Physics 2. But is mathematical/logical reasoning largely a language task? I don't reall…

You also have to recall that these models were trained on the study materials of all of those tasks. That doesn't cheapen the achievement except to say, it's not "emergent behavior". Probably has half a billion weights dedicated to each of those exams.

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

#52

Post by shawntan »

gwern wrote: post #32
shawntan wrote: post #14

Earlier quoted context omitted.

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…

> 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?

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"

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

#53

Post by thumbuddy »

skwirl wrote: post #25
thumbuddy wrote: post #16

Earlier quoted context omitted.

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

LLMs are good at a lot of things we don't have a good reason to expect them to be good at. It's very hard to come up with "theoretical reasons" it should be good at things, in "theory" they should not be nearly as capable as they are. Even NLP researchers have been shocked at how well this has worked.

If there is no theory, or expected result why should anyone care what it's good at or not? You kinda get what you get and if you don't get what you want you do what?

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

#54

Post by swayvil »

famouswaffles wrote: post #37
eschaton wrote: post #35

Earlier quoted context omitted.

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 reco…

>Where does this idea that ChatGPT and friends are general-purpose come from? Maybe reality? 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.

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.

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

#55

Post by solomatov »

CydeWeys wrote: post #33
solomatov wrote: post #30

Earlier quoted context omitted.

It's not realistically Turing complete. It assumes infinite precision.

Right but a Turing computer assumes infinite storage space which is itself impossible. You cannot have infinite precision without infinite storage, and all real computers that we colloquially say are Turing complete have finite everything.

It's possible to argue that there's no such a thing as infinite precision floats. I.e. all objects have limited "size", and real numbers is just a nice abstraction to simplify discrete world. (https://en.wikipedia.org/wiki/Finitism)

Turing machine is not such thing. At each moment in time, only finitely many cells of the tape are used. (The same applies to natural numbers, there are infinitely many of them, but each one of them has a finite description).

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

#56

Post by solomatov »

famouswaffles wrote: post #28
janalsncm wrote: post #19

Earlier quoted context omitted.

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 prin…

With memory they are. https://arxiv.org/abs/2301.04589

You are mixing up LLMs with Transformers. Transformers with memory are Turing complete, but AFAIK, current state of the art LLMs aren't trained with any kind of memory.

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

#57

Post by solomatov »

janalsncm wrote: post #19
heliophobicdude wrote: post #6

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 col…

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 prin…

> Are large language models even Turing complete?

If you want to see where they have problem ask them to do something about deep hierarchical objects. For example, consider this prompt: "Draw me a complete binary tree with numbers from 1 to 128 using pseudographics"

In my experience, the deeper the structure, the more problematic it is for the current generation of LLMs.

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

#58

Post by dragonwriter »

kaba0 wrote: post #48
dragonwriter wrote: post #21

Earlier quoted context omitted.

> 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 potentia…

> Idealized deterministic computing systems are the only thing that can be Turing complete That’s not true. My computer is for all practical purposes Turing complete - it’s tape is not the RAM, but due to side effecting, being connected to the internet, the whole universe. So while the universe itself is finite, nothing material can be mathematically infinite, Turing completeness fails “lazily”. Unless you hit the li…

> My computer is for all practical purposes Turing complete

“For all practical purposes” is a long way of saying “not”; a large-but-finite tape is not infinite, and the key properties of Turing completeness (both universal computation and the consequent equivalence with all other Turing complete systems) do not hold with “finite but large tapes”, no matter if large is 640 kilobytes or 640 quettabytes. Particularly, differently structured “Turing complete but for finite size” systems of similar actual capacity in bytes are not guaranteed to be able to compute the same subset of all computable results. (Actually Turing machines with the same size tape would be, but “Turing complete but for size” does not imply a consistent ratio between problems of material storage space to equivalent Turing machine tape size.)

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

#59

Post by famouswaffles »

solomatov wrote: post #56
famouswaffles wrote: post #28

Earlier quoted context omitted.

With memory they are. https://arxiv.org/abs/2301.04589

You are mixing up LLMs with Transformers. Transformers with memory are Turing complete, but AFAIK, current state of the art LLMs aren't trained with any kind of memory.

I'm not. The paper specifically deals with language models in particular. Memory is just dynamically inserted context

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

#60

Post by objektif »

skwirl wrote: post #27
objektif wrote: post #24

Earlier quoted context omitted.

What tasks would you say LLMs are good at that are not related to language?

It's very hard to define what is and is not "related to language" and this is kind of a fundamental question that seemed to get a lot of attention in the 20th century. Maybe these language models can help shine some light on that. According to OpenAI, GPT-4 scores 4 on AP Calculus BC, 5 on AP Statistics, 4 on AP Chemistry, 4 on AP Physics 2. But is mathematical/logical reasoning largely a language task? I don't reall…

Exactly what I was trying to imply. Very difficult to classify what is not relevant to language.
Post reply on HN