From hallucinations to discovery: For the first time a large language model finds new solutions to math problems

Large Language Models (LLMs) like ChatGPT have a lot of things going for them. These powerful AI systems can synthesize and interpret vast amounts of information and are surprisingly human-like with language. At the same time, they’re also notorious for making up facts with confidence. Put simply, they “hallucinate”, as people have come to describe this annoying behavior.

A huge question ever since this technology was released is whether LLMs are capable of discovering new knowledge, rather than repurposing and rehashing existing information. As it turns out, they can.

Researchers at Google’s DeepMind branch have shown a new AI method called FunSearch, which can forge new paths to find solutions to complex problems in mathematics and computer science.

The innovation of FunSearch lies in the pairing of a pre-trained LLM with an automated evaluator. This setup is designed to leverage the LLM’s strength in generating creative solutions in the form of computer code, while the evaluator rigorously checks these solutions for accuracy. The highest-performing solutions are continuously fed back into the cycle, fostering a self-improving loop of problem-solving and innovation.

This partnership enables an iterative refinement process, transforming initial creative outputs into verified, novel knowledge. The focus on discovering “functions” in computer code is what gives FunSearch its distinctive name and operational approach.

This initiative marks the first time LLMs have contributed to solving open problems in the scientific and mathematical community. FunSearch found novel solutions to the cap set problem, a long-standing mathematical challenge.

The Cap Set Problem in mathematics involves finding the largest subset of integers from 0 to 3ⁿ−1 (where each integer is represented in base 3) such that no three integers in the subset sum to another integer in base 3. It’s a challenge in combinatorics, a field concerned with counting, arrangement, and structure. Terence Tao, the highest IQ person in the world and one of the world’s leading mathematicians, once described the cap set problem as one of his favorite open questions in the field.

FunSearch succeeded in discovering new, larger cap sets, contributing valuable insights to the problem and demonstrating the potential of AI in advancing mathematical research. FunSearch’s contribution marks the largest increase in the size of cap sets in the past two decades.

“These results demonstrate that the FunSearch technique can take us beyond established results on hard combinatorial problems, where intuition can be difficult to build. We expect this approach to play a role in new discoveries for similar theoretical problems in combinatorics, and in the future it may open up new possibilities in fields such as communication theory,” wrote the DeepMind researchers in a blog post.

Moreover, FunSearch has proven itself further by enhancing algorithms for the “bin-packing” problem. The bin-packing problem is a classic algorithmic challenge. It involves efficiently packing objects of different sizes into a finite number of bins or containers in a way that minimizes the number of bins used.

Contrary to many computational tools that offer solutions without explanation like a “black box”, FunSearch provides a detailed account of how its conclusions are reached.

“This show-your-working approach is how scientists generally operate, with new discoveries or phenomena explained through the process used to produce them,” add the DeepMind researchers.

The ability of FunSearch to not only generate innovative solutions but also provide the details of the problem-solving process holds immense potential. With the continual advancement of LLM technology, the capabilities of tools like FunSearch are expected to expand, paving the way for groundbreaking discoveries and solutions to some of society’s most pressing scientific and engineering challenges.

The findings were reported in the journal Nature.