Nature News: AI beats human mathematicians to solve classic mathematical problems for the first time

Artificial intelligence (AI) big models beat human mathematicians.

In a paper published today in Nature, a research team at Google DeepMind introduced a method for searching for new solutions in mathematics and computer science, FunSearch , which works by pairing pre-trained large language models (LLMs) with automatic "evaluators" to prevent hallucinations and wrong ideas. By iterating back and forth between these two components, the initial solution evolves into new knowledge.

The study is the first to leverage LLMs for challenging open problems in science or mathematics. FunSearch found new solutions to the capped set problem, a long-standing open problem in mathematics. And, to demonstrate the practical usefulness of FunSearch, the researchers used it to discover more efficient algorithms for solving the "bin packing" problem, which has ubiquitous applications, such as improving the efficiency of data centers.

Scientific progress has always relied on the ability to share new understanding. What makes FunSearch a particularly powerful scientific tool is that the program it outputs reveals how its solution was built, not just what the solution is. The authors of the paper said, "Hopefully this will inspire further insights from scientists using FunSearch, driving a virtuous cycle of improvement and discovery."

“The solutions generated by FunSearch are much richer in concept than just lists of numbers,” said Jordan Ellenberg, co-author and professor of mathematics at the University of Wisconsin-Madison. “When I studied them, I learned something.”

Finding the maximum upper bound set, solving the "bin packing" problem

FunSearch uses an evolutionary approach powered by LLMs to promote and develop the highest scoring ideas. These ideas are expressed as computer programs so that they can be run and evaluated automatically.

First, the user writes a description of the problem in the form of code, which includes the process of evaluating programs and the seed program used to initialize the program pool.

FunSearch is an iterative process. In each iteration, the system selects some programs from the current pool of programs and feeds them back to the LLMs. Subsequently, the LLMs build on this creatively and generate new programs that are automatically evaluated. The best programs are added back to the existing pool of programs, creating a self-improvement cycle.

FunSearch uses Google's PaLM 2, but it is compatible with other code-trained LLMs.

Figure | FunSearch process

The research focused on the upper bound set problem , an open challenge that has puzzled mathematicians in multiple research fields for decades, and which the renowned mathematician Terence Tao once described as his favorite open problem.

The problem involves finding the largest set of points (called an upper bound set) in a high-dimensional grid in which no three points lie on a line. The problem is important because it serves as a model for other problems in extremal combinatorics, which studies how large or small sets of numbers, graphs, or other objects can be. Brute-force computational approaches to the problem don't work; the number of possibilities that need to be considered quickly becomes greater than the number of atoms in the universe.

Figure | Interactive chart showing the evolution from a seed program (top) to a new high-scoring function (bottom). Each circle is a program and its size is proportional to the score assigned to it.

However, FunSearch has found the largest set of upper bounds ever discovered in some settings in a procedural form, the largest increase in the size of upper bounds in the past 20 years , and it has also outperformed state-of-the-art computational solvers.

In addition, the researchers explored the flexibility of FunSearch by applying it to real-world challenges in computer science. The "bin packing" problem looks at how to pack items of different sizes into the least number of bins, which is at the heart of many real-world problems.

It’s just the beginning

Discovering new mathematical knowledge and algorithms in different fields is a notoriously difficult task that is largely beyond the capabilities of state-of-the-art AI systems. To solve such challenging problems using FunSearch, the research introduces several key components .

It’s worth noting that FunSearch isn’t a black box that simply generates solutions to problems. Instead, it generates programs that describe how those solutions were arrived at, and this method of showing work is how scientists typically operate .

FunSearch tends to find solutions represented by highly compact programs, solutions with low Kolmogorov complexity . Short programs can describe very large objects, allowing FunSearch to scale to large problems such as finding a needle in a haystack. In addition, this feature of FunSearch also makes its program output easier for researchers to understand.

More importantly, this interpretability of FunSearch programs can provide researchers with actionable insights. For example, when using FunSearch, some of its high-scoring outputs have interesting symmetries in their code.

Figure | Inspecting the code generated by FunSearch yields further actionable insights (left); the original “acceptable” set built using the (shorter) program on the left (right).

The results on the upper bound set problem show that the FunSearch technique can go beyond established results on difficult combinatorial problems, where it is difficult to build intuition. The researchers expect this approach to be instrumental in new discoveries on similar theoretical problems in combinatorics and to open up new possibilities in areas such as communication theory.

Alternatively, hard combinatorial problems such as online bin packing can be solved using other AI methods, such as neural networks and reinforcement learning. FunSearch’s approach has also proven to be effective, but it can also require a lot of resources to deploy. On the other hand, the code output by the method can be easily checked and deployed, which means that its solution has the potential to be embedded in a variety of real-world industrial systems to bring rapid benefits.

FunSearch demonstrates that if one can guard against the illusions of LLMs, the power of these models can be harnessed not only to generate new mathematical discoveries, but also to reveal potentially effective solutions to important real-world problems.

The research team anticipates that it will become common practice to use LLMs-driven approaches to generate efficient and customized algorithms for many problems in science and industry, both long-standing and new.

In fact, this is just the beginning. The researchers said: "We will also work to expand its capabilities to address a variety of society's pressing scientific and engineering challenges."

Reference Links:

https://deepmind.google/discover/blog/funsearch-making-new-discoveries-in-mathematical-sciences-using-large-language-models/

https://www.nature.com/articles/s41586-023-06924-6