FunSearch: Leveraging Large Language Models for Mathematical Discoveries

By Alhussein Fawzi and Bernardino Romera Paredes

In a groundbreaking development, researchers at DeepMind have introduced FunSearch, a novel method that harnesses the power of Large Language Models (LLMs) to make new discoveries in mathematical sciences. This approach marks the first time LLMs have been used to solve open problems in mathematics and computer science, offering significant implications for scientific research.

Technical Overview

FunSearch operates by leveraging an LLM's ability to generate creative solutions in the form of computer code, paired with an automated evaluator that ensures these solutions are correct. The process involves several key steps:

• Problem Definition: The user provides a problem description in the form of code, which includes:

  • A procedure to evaluate candidate programs.
  • An initial seed program to start the search.

• Solution Generation: The LLM generates multiple candidate solutions (functions) based on the provided problem description.

• Evaluation and Selection: The evaluator runs these functions and scores them based on their performance. Only the highest-scoring solutions are retained.

• Evolutionary Iteration: The process iterates, with the LLM refining its ideas based on feedback from the evaluator. Over time, this back-and-forth interaction leads to increasingly sophisticated and effective solutions.

Key Achievements

Cap Set Problem

One of FunSearch's notable achievements is solving an open problem in combinatorial mathematics known as the cap set problem. This problem involves finding the largest subset of a finite vector space over the field with three elements (GF(3)) that contains no three points on a line. Despite its simplicity, it has eluded mathematicians for decades.

• Initial Solutions: FunSearch generated initial candidate solutions.
• Refinement and Validation: Through iterative refinement, FunSearch discovered new, previously unknown solutions to the cap set problem.

Bin-Packing Problem

FunSearch also demonstrated practical applications by improving algorithms for the bin-packing problem. This problem is crucial in various industries, including data center management, where it helps optimize resource allocation.

• Algorithm Discovery: FunSearch identified more efficient bin-packing algorithms.
• Performance Gains: These new algorithms showed significant improvements over existing methods, potentially leading to more efficient and cost-effective solutions in real-world scenarios.

Why It Matters

The ability of LLMs to generate verifiably correct and novel solutions has profound implications for scientific research:

• Enhanced Creativity: FunSearch leverages the creative capabilities of LLMs while ensuring accuracy through automated evaluation.
• Transparent Solutions: Unlike traditional black-box AI models, FunSearch outputs programs that reveal how solutions are constructed. This transparency can inspire further insights and improvements.
• Iterative Improvement: The evolutionary approach allows for continuous refinement, driving a virtuous cycle of discovery and innovation.

Future Directions

The potential applications of FunSearch extend beyond mathematics and computer science. Researchers at DeepMind have already shown how the method can be used to enhance human performance in combinatorial competitive programming (as detailed in an arXiv report published in December 2024).

Conclusion

FunSearch represents a significant step forward in using AI for scientific discovery. By combining the creative power of LLMs with rigorous evaluation, it opens new avenues for solving complex problems and advancing our understanding of mathematical sciences.