FunSearch (so called because it searches for mathematical functions, not because itâs fun) continues a streak of discoveries in fundamental math and computer science that DeepMind has made using AI. First AlphaTensor found a way to speed up a calculation at the heart of many different kinds of code, beating a 50-year record. Then AlphaDev found ways to make key algorithms used trillions of times a day run faster.
Yet those tools did not use large language models. Built on top of DeepMindâs game-playing AI AlphaZero, both solved math problems by treating them as if they were puzzles in Go or chess. The trouble is that they are stuck in their lanes, says Bernardino Romera-Paredes, a researcher at the company who worked on both AlphaTensor and FunSearch: âAlphaTensor is great at matrix multiplication, but basically nothing else.â
FunSearch takes a different tack. It combines a large language model called Codey, a version of Googleâs PaLM 2 that is fine-tuned on computer code, with other systems that reject incorrect or nonsensical answers and plug good ones back in.
âTo be very honest with you, we have hypotheses, but we donât know exactly why this works,â says Alhussein Fawzi, a research scientist at Google DeepMind. âIn the beginning of the project, we didnât know whether this would work at all.â
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.
Itâs super niche, but important. Mathematicians do not even agree on how to solve it, let alone what the solution is. (It is also connected to matrix multiplication, the computation that AlphaTensor found a way to speed up.) Terence Tao at the University of California, Los Angeles, who has won many of the top awards in mathematics, including the Fields Medal, called the cap set problem âperhaps my favorite open questionâ in a 2007 blog post.