The researchers started by sketching out the problem they wanted to solve in Python, a popular programming language. But they left out the lines in the program that would specify how to solve it. That is where FunSearch comes in. It gets Codey to fill in the blanks—in effect, to suggest code that will solve the problem.
A second algorithm then checks and scores what Codey comes up with. The best suggestions—even if not yet correct—are saved and given back to Codey, which tries to complete the program again. “Many will be nonsensical, some will be sensible, and a few will be truly inspired,” says Kohli. “You take those truly inspired ones and you say, ‘Okay, take these ones and repeat.’”
After a couple of million suggestions and a few dozen repetitions of the overall process—which took a few days—FunSearch was able to come up with code that produced a correct and previously unknown solution to the cap set problem, which involves finding the largest size of a certain type of set. Imagine plotting dots on graph paper. The cap set problem is like trying to figure out how many dots you can put down without three of them ever forming a straight line.
So, they basically “intelligently” brute forced it? Still cool.
Isn’t that how we learn too? We stop doing the things that don’t work in favor of things that do while repeatedly “brute forcing” ourselves (training/practice).
It’s more like educated guessing, which is a lot faster than brute forcing. They can use code to check the answers so there is ground truth to verify against. A few days of compute time for an answer to a previously unsolved math problem sounds a lot better than brute forcing.
Generate enough data for good guesses and bad guesses and you can train the thing to make better guesses.
it is what we (the people) do as well. we look at the data and try to find a pattern. but the computer can process larger amount of data than people can.that’s it.
no. your claim sounds ridiculous.
Well don’t be a poopy pants!
I didn’t claim anything. I asked. If I’m misguided, then so be it, I’ll learn somthin’.
It’s not brute forcing though. It is similar to genetic programming, it seems, but with more less understood parts.
I mean, I would also call genetic algorithms a form of brute forcing. And just like with genetic algorithms, this approach is going to be severely limited by the range of values that can be updated and the ability to test the outcome.
Why would you not be able to test the outcome fully? And what do you mean by “limited by the range of values that can be updated”?
So they configured the experiment so that only certain lines of code were able to be iterared/updated. Maybe you could ask it to start from scratch, but I imagine that would increase the time for it to converge (if it ever does).
Regarding testing, not all mathematical proofs can be verified by example. Here they were trying to prove that there was an even lower bound for the problem, but not all proofs will work with that structure.
FunSearch (so called because it searches for mathematical functions, not because it’s fun)
I’m probably not the only one who wondered.
Some people might consider that fun :(
I would have called it FunkSearch, to eliminate this misunderstanding.
The Funk, the Whole Funk, and Nothing but the Funk
Gotta have that funk
We have solved the unsolvable problem.
Should probably rename it then.
Lots of problems are unsolvable until they’re solved.
Kind of abusing the word there a bit though eh. Maybe call them something like “really feggin hard problems” instead.
Guarantee this comes out as untrue. Mark me.
They basically found a more effective way to brute force the problem. I don’t doubt that it’s possible. The title calling it unsolvable is nonsense though.
Does it perform better in a significant way to genetic programming?
Can it divide by zero ?
I thought this was interesting bc it’s an instance where a LLM has done something undeniably novel and unique while expanding human understanding. It’s a chink in the armor of the idea that a LLM is a “stochastic parrot” that can only regurgitate and never create.
I’ve been toying with this idea that LLM are showing us that what we thought of as creativity, learning, and problem solving aren’t as rarefied as we thought. We know that AI isn’t conscious, maybe consciousness isn’t as prerequisite to behaviors and cognition as we thought.
I’m not so sure, it feels a lot more like the https://en.wikipedia.org/wiki/Infinite_monkey_theorem, but with a model helping limit the outputs so they are mostly usable. As is stated in the article, it took millions of runs and couple of days to get the results. So its more like brute forcing with a slightly modified genetic algorithm than anything else.
I didn’t see a link to the full article, so maybe something more creative is happening behind the scenes, but it seems unlikely.
