FunSearch (short for searching in the function space) is an artificial intelligence method developed by Google DeepMind for discovering computer programs that solve mathematical and algorithmic problems. It combines a large language model with an automated evaluator and an evolutionary search procedure, generating candidate programs, scoring them, and using high-performing programs to produce new candidates. The system was announced in 2023, with a paper published in the journal Nature, and has been applied to problems in extremal combinatorics and online bin packing.
FunSearch represents a shift in how large language models are used for discovery. Instead of directly generating answers, it frames a problem as a search over computer programs, allowing the model to propose code that is then rigorously tested. This approach leverages the generative capabilities of models like those used in Generative AI while ensuring that outputs are verifiable and often interpretable by researchers.
Method
FunSearch operates by iteratively generating and evaluating candidate programs. The user provides a problem specification, an evaluation function, and an initial program skeleton. At each step, the system samples existing programs from a database, favoring those with higher scores, and constructs a prompt for a pretrained large language model. The model generates a modified program, which is then executed and scored by the evaluator. Valid programs are added back to the database, enabling the search to build on previous successes.
The search uses an island-based evolutionary method to maintain diversity among candidate programs, reducing the risk of converging to local optima. A key advantage, as noted in the original paper, is that FunSearch outputs programs that can be inspected, simplified, and interpreted by researchers, rather than just providing a final numerical answer or a large list of objects.
Algorithmic Formulation
FunSearch can be described as a search over a space of program fragments, typically functions embedded in a fixed skeleton. Let \(\mathcal{F}\) be the space of candidate functions and \(S: \mathcal{F} \to \mathbb{R}\) be an evaluator score obtained by running a fixed solver that calls the candidate function. Given an initial function \(f_0\), FunSearch maintains a database \(D\) of evaluated, valid functions. It repeatedly samples high-scoring functions from \(D\), uses them to construct prompts for a large language model, and asks the model to generate a new candidate function \(f'\). The new function is executed within the problem-specific skeleton and scored. If valid, it is added to \(D\), allowing later prompts to build on stronger candidates.
The idealized objective is to find a candidate function with a high evaluator score, \(f^* \in \arg\max_{f \in \mathcal{F}} S(f)\), though in practice FunSearch returns the best valid function discovered during the search. The original implementation uses an island-based evolutionary process to preserve diversity while favoring higher-scoring programs.
Applications
Cap Set Problem
FunSearch was first demonstrated on the cap set problem, a problem in additive combinatorics concerning the largest possible subset of \(\mathbb{Z}_3^n\) with no three points in a line. In dimension 8, FunSearch found a cap set of size 512, improving on previously known constructions. The paper also reported improved lower bounds for the cap set capacity by discovering constructions related to admissible sets. Google DeepMind described the result as an example of using large language models to generate verifiable new knowledge in mathematics. A Nature news article reported that the system improved on human efforts for a combinatorics problem related to the card game Set.
Online Bin Packing
FunSearch was also applied to the online bin packing problem, where items must be assigned to bins as they arrive. In this setting, FunSearch evolved programmatic heuristics that decide which bin should receive a new item. The original paper reported that the discovered heuristics outperformed the common first-fit and best-fit baselines on simulated data and OR-Library benchmark instances.
Software
Google DeepMind released the FunSearch software in a public GitHub repository, allowing researchers to reproduce the results and apply the method to other problems. The release includes the code for the evolutionary search, the evaluator interface, and examples for the cap set and bin packing problems. This open availability supports further experimentation in the field of Machine learning and Artificial intelligence.
Significance
FunSearch is notable for its integration of large language models with evolutionary computation, a direction that has gained attention in the broader field of Deep learning. By producing interpretable programs, it offers a path toward AI systems that not only solve problems but also provide insights that humans can understand and build upon. The method has been discussed in the context of Google DeepMind's broader efforts to apply AI to scientific discovery, alongside other initiatives in Generative AI.
While FunSearch has shown promise on specific mathematical and algorithmic tasks, its general applicability remains an area of active research. The reliance on a pretrained language model and the need for a well-defined evaluator are constraints that may limit its use in other domains. Nevertheless, the approach has inspired further work on using language models for program synthesis and optimization, contributing to the evolving landscape of AI research.