Researchers from Deep Mind have developed FunSearch, a method that uses Large Language Models (LLMs) to discover new solutions in mathematics and computer science. The system pairs a pre-trained LLM with an automated evaluator to create new knowledge.
FunSearch has made the first discovery for challenging open problems in science or mathematics using LLMs, finding new solutions for the cap set problem and more effective algorithms for the bin-packing problem. The system also outputs programs that reveal how its solutions are constructed, potentially inspiring further insights in scientists who use FunSearch.
Deep Mind Fun Search
Introduction to FunSearch and Large Language Models
Large Language Models (LLMs) are powerful tools that can read, write, and code to assist in problem-solving. However, they have been known to “hallucinate” or produce factually incorrect information. To overcome this challenge, a method called FunSearch has been introduced. FunSearch pairs a pre-trained LLM, which provides creative solutions in computer code, with an automated evaluator that guards against hallucinations and incorrect ideas. This iterative process allows initial solutions to evolve into new knowledge. FunSearch represents the first time a new discovery has been made for challenging open problems in science or mathematics using LLMs. Published in Nature, the work further highlights the use-cases of LLMs in discovering new theorems and science.
FunSearch’s Discoveries in Mathematical Sciences
FunSearch has made significant discoveries in the field of mathematical sciences. It discovered new solutions for the cap set problem, a longstanding open problem in mathematics. Additionally, FunSearch was used to discover more effective algorithms for the “bin-packing” problem, which has widespread applications such as making data centers more efficient. What sets FunSearch apart is that it outputs programs that reveal how its solutions are constructed, rather than just what the solutions are. This can inspire further insights in the scientists who use FunSearch, driving a cycle of improvement and discovery.
The Process of FunSearch
FunSearch uses an evolutionary method powered by LLMs, which promotes and develops the highest scoring ideas. These ideas are expressed as computer programs, so that they can be run and evaluated automatically. The user writes a description of the problem in the form of code, which includes a procedure to evaluate programs and a seed program used to initialize a pool of programs. The system selects some programs from the current pool, which are fed to an LLM. The LLM creatively builds upon these, and generates new programs, which are automatically evaluated. The best ones are added back to the pool of existing programs, creating a self-improving loop.
Breaking New Ground in Mathematics with FunSearch
FunSearch has been used to address the cap set problem, an open challenge that has puzzled mathematicians for decades. The problem involves finding the largest set of points in a high-dimensional grid, where no three points lie on a line. FunSearch generated solutions that discovered the largest cap sets ever found, representing the largest increase in the size of cap sets in the past 20 years. Moreover, FunSearch outperformed state-of-the-art computational solvers, as this problem scales well beyond their current capabilities.
FunSearch’s Approach to Problem Solving
FunSearch doesn’t just generate solutions to problems. Instead, it generates programs that describe how those solutions were arrived at. This approach is similar to how scientists operate, with new discoveries or phenomena explained through the process used to produce them. FunSearch favors finding solutions represented by highly compact programs, which makes its program outputs easier for researchers to comprehend. This interpretability of FunSearch’s programs can provide actionable insights to researchers.
Applying FunSearch to Real-World Problems
FunSearch was applied to the “bin packing” problem, a practical challenge in computer science that involves packing items of different sizes into the smallest number of bins. FunSearch delivered an automatically tailored program that outperformed established heuristics, using fewer bins to pack the same number of items. FunSearch’s solutions could potentially be slotted into a variety of real-world industrial systems to bring swift benefits.
The Future of FunSearch and LLMs
FunSearch demonstrates that if we safeguard against LLMs’ hallucinations, these models can be harnessed to produce new mathematical discoveries and reveal potentially impactful solutions to important real-world problems. The authors envision that generating effective and tailored algorithms using LLM-driven approaches will become common practice for many problems in science and industry. As LLMs continue to improve, so too will FunSearch, with plans to broaden its capabilities to address a variety of society’s pressing scientific and engineering challenges.
Summary
FunSearch, a method that uses Large Language Models (LLMs) to discover new solutions in mathematics and computer science, has made the first-ever discovery for challenging open problems in these fields. The system, which pairs a pre-trained LLM with an automated evaluator, has found new solutions for the cap set problem, a longstanding mathematical issue, and has also developed more effective algorithms for the ‘bin-packing’ problem, which has wide-ranging applications such as improving data centre efficiency.
- A new method called FunSearch, developed by Alhussein Fawzi, Bernardino Romera Paredes et al, uses Large Language Models (LLMs) to make discoveries in mathematical sciences.
- FunSearch pairs a pre-trained LLM, which provides creative solutions in the form of computer code, with an automated evaluator to guard against incorrect information.
- This method has been used to make the first-ever discovery for challenging open problems in science or mathematics using LLMs.
- FunSearch discovered new solutions for the cap set problem, a longstanding mathematical problem, and also found more effective algorithms for the bin-packing problem, which has practical applications such as improving data centre efficiency.
- The method is unique in that it reveals how its solutions are constructed, rather than just what the solutions are, potentially inspiring further insights in scientists who use FunSearch.
- FunSearch uses Google’s PaLM 2, but is compatible with other LLMs trained on code.
- The method was developed in collaboration with Jordan Ellenberg, a professor of mathematics at the University of Wisconsin–Madison.
Read More: Mathematical discoveries from program search with large language models. Nature (2023)
