FunSearch demonstrates that if we safeguard against LLMs’ hallucinations, the power of these models can be harnessed not only to produce new mathematical discoveries, but also to reveal potentially impactful solutions to important real-world problems.
We envision that for many problems in science and industry — longstanding or new — generating effective and tailored algorithms using LLM-driven approaches will become common practice.
Indeed, this is just the beginning. FunSearch will improve as a natural consequence of the wider progress of LLMs, and we will also be working to broaden its capabilities to address a variety of society’s pressing scientific and engineering challenges.
Large Language Models (LLMs) have demonstrated tremendous capabilities in solving com12 plex tasks, from quantitative reasoning to understanding natural language. However, LLMs 13 sometimes suffer from confabulations (or hallucinations) which can result in them making plau14 sible but incorrect statements (Bang et al., 2023; Borji, 2023). This hinders the use of current 15 large models in scientific discovery. Here we introduce FunSearch (short for searching in the 16 function space), an evolutionary procedure based on pairing a pre-trained LLM with a system17 atic evaluator. We demonstrate the effectiveness of this approach to surpass the best known re18 sults in important problems, pushing the boundary of existing LLM-based approaches (Lehman 19 et al., 2022). Applying FunSearch to a central problem in extremal combinatorics — the cap 20 set problem — we discover new constructions of large cap sets going beyond the best known 21 ones, both in finite dimensional and asymptotic cases. This represents the first discoveries made 22 for established open problems using LLMs. We showcase the generality of FunSearch by apply23 ing it to an algorithmic problem, online bin packing, finding new heuristics that improve upon 24 widely used baselines. In contrast to most computer search approaches, FunSearch searches for 25 programs that describe how to solve a problem, rather than what the solution is. Beyond being 26 an effective and scalable strategy, discovered programs tend to be more interpretable than raw 27 solutions, enabling feedback loops between domain experts and FunSearch, and the deployment 28 of such programs in real-world applications
LLMs, or large language models, have shown great promise in scientific discovery by combining their creativity with the power of evolutionary procedures to push the boundaries of human knowledge.
Here are a few key points to consider:
- Creative Solutions: LLMs are particularly adept at generating creative solutions to complex problems. By providing them with a problem statement and relevant context, LLMs can produce innovative ideas and approaches that might not be easily conceived by humans.
- Guiding Formal Proofs: LLMs can assist in the search for formal proofs for automatic theorem proving. While this area is still in its early stages of development, LLMs have the potential to revolutionize the way mathematical proofs are discovered and verified.
- Genetic Programming: LLMs can be used as a mutation operator in genetic programming, a technique that evolves programs to solve specific problems. This combination of LLMs and genetic programming has led to significant improvements in diverse synthetic problems, neural network architectures, and puzzle-solving.
- New Scientific Discoveries: LLMs have been used to make groundbreaking discoveries in established open problems, such as finding new constructions of large cap sets in extremal combinatorics. These discoveries represent the first scientific results obtained using LLMs and demonstrate their ability to contribute to scientific knowledge.
- Algorithm Improvement: LLMs have been leveraged to develop new algorithms for the online bin packing problem, resulting in heuristics that outperform traditional approaches. This highlights the potential of LLMs to enhance existing algorithms and contribute to practical applications.
It is important to note that while LLMs offer significant potential in scientific discovery, their limitations must also be considered. For instance, LLMs can sometimes suffer from confabulations or incorrect statements due to their training data. Additionally, using LLMs effectively often requires careful prompt engineering and a deep understanding of the problem domain.
Overall, LLMs are emerging as powerful tools for scientific discovery, offering the ability to generate creative solutions, guide formal proofs, enhance genetic programming, make new scientific discoveries, and improve algorithms. As LLMs continue to advance and become more sophisticated, their impact on scientific research is likely to grow even more profound.
