FunSearch

{{Short description|Artificial intelligence method for mathematical discovery}} {{Use mdy dates|date=May 2026}}

{{Infobox software | name = FunSearch | developer = Google DeepMind | released = {{Start date and age|2023|12|14}} | programming language = Python | genre = Artificial intelligence<br>program synthesis<br>evolutionary computation<br>mathematical optimization | license = Apache License 2.0 (software)<br>CC BY 4.0 (other materials) | repo = {{URL|https://github.com/google-deepmind/funsearch}} | website = {{URL|https://deepmind.google/discover/blog/funsearch-making-new-discoveries-in-mathematical-sciences-using-large-language-models/}} }}

'''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.<ref name="romera-paredes-2024">{{cite journal |last1=Romera-Paredes |first1=Bernardino |last2=Barekatain |first2=Mohammadamin |last3=Novikov |first3=Alexander |last4=Balog |first4=Matej |last5=Kumar |first5=M. Pawan |last6=Dupont |first6=Emilien |last7=Ruiz |first7=Francisco J. R. |last8=Ellenberg |first8=Jordan S. |last9=Wang |first9=Pengming |last10=Fawzi |first10=Omar |last11=Kohli |first11=Pushmeet |last12=Fawzi |first12=Alhussein |display-authors=etal |title=Mathematical discoveries from program search with large language models |journal=Nature |volume=625 |pages=468–475 |date=2024 |doi=10.1038/s41586-023-06924-6 |url=https://www.nature.com/articles/s41586-023-06924-6 |access-date=May 4, 2026}}</ref>

Google DeepMind announced FunSearch in 2023, and the associated paper was published in ''Nature''.<ref name="deepmind-funsearch">{{cite web |title=FunSearch: Making new discoveries in mathematical sciences using Large Language Models |website=Google DeepMind |date=December 14, 2023 |url=https://deepmind.google/discover/blog/funsearch-making-new-discoveries-in-mathematical-sciences-using-large-language-models/ |access-date=May 4, 2026}}</ref> The system was applied to the cap set problem in extremal combinatorics and to the online bin packing problem, where it found new mathematical constructions and new packing heuristics.<ref name="mouret-2024">{{cite journal |last=Mouret |first=Jean-Baptiste |title=Large language models help computer programs to evolve |journal=Nature |volume=625 |pages=452–453 |date=January 17, 2024 |doi=10.1038/d41586-023-03998-0}}</ref><ref name="ellenberg-2025">{{cite arXiv |last1=Ellenberg |first1=Jordan S. |last2=Fraser-Taliente |first2=Cristofero S. |last3=Harvey |first3=Thomas R. |last4=Srivastava |first4=Karan |last5=Sutherland |first5=Andrew V. |title=Generative Modeling for Mathematical Discovery |date=March 17, 2025 |eprint=2503.11061 |class=cs.LG}}</ref>

== Method == FunSearch frames a problem as a search over computer programs rather than as a direct search over individual solutions. The user provides a problem specification, an evaluation function, and an initial program or program skeleton. At each iteration, FunSearch samples existing programs from a database, favors higher-scoring programs, builds a prompt for a pretrained large language model, and asks the model to generate modified programs. The generated programs are then executed and scored by the evaluator.<ref name="romera-paredes-2024" />

The search process uses an island-based evolutionary method intended to maintain a diverse set of candidate programs and reduce the risk of becoming trapped in local optima. According to the original paper, one advantage of the approach is that FunSearch outputs programs that can sometimes be inspected, simplified, and interpreted by researchers, instead of only producing a final numerical answer or a large list of objects.<ref name="romera-paredes-2024" />

== Algorithmic formulation == FunSearch can be described as a search over a space of program fragments, usually functions embedded in a fixed program skeleton. Let <math>\mathcal{F}</math> be a space of candidate functions and let <math>S: \mathcal{F} \to \mathbb{R}</math> be an evaluator score obtained by running a fixed solver that calls the candidate function. Given an initial function <math>f_0</math>, FunSearch maintains a database <math>D</math> of evaluated, valid functions. It repeatedly samples high-scoring functions from <math>D</math>, uses them to construct prompts for a large language model, and asks the model to generate a new candidate function <math>f'</math>. The new function is executed inside the problem-specific program skeleton and scored by the evaluator. If the generated function is valid, it is added back into <math>D</math>, allowing later prompts to build on stronger previous candidates.<ref name="romera-paredes-2024" />

In simplified form, the search loop can be written as:

<math display="block"> D \leftarrow \{(f_0, S(f_0))\} </math>

<math display="block"> f' \sim \operatorname{LLM}(\operatorname{prompt}(f_1,\ldots,f_k)), \quad (f_i, S(f_i)) \in D </math>

<math display="block"> \text{if } f' \text{ is valid, then } D \leftarrow D \cup \{(f', S(f'))\}. </math>

The idealized objective is to find a candidate function with a high evaluator score,

<math display="block"> f^* \in \operatorname*{arg\,max}_{f \in \mathcal{F}} S(f), </math>

although in practice FunSearch returns the best valid function discovered during the search. The original implementation uses an island-based evolutionary process to preserve diversity among candidate functions while favoring higher-scoring programs.<ref name="romera-paredes-2024" /><ref name="ellenberg-2025" />

== Applications ==

=== Cap set problem === FunSearch was first demonstrated on the cap set problem, a problem in additive combinatorics concerning the largest possible subset of <math>\mathbb{Z}_3^n</math> 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 using FunSearch to discover constructions related to admissible sets.<ref name="romera-paredes-2024" />

Google DeepMind described the result as an example of using large language models to generate verifiable new knowledge in mathematics.<ref name="deepmind-funsearch" /> A ''Nature'' news article reported that the system improved on human efforts for a combinatorics problem related to the card game Set.<ref name="castelvecchi-2023">{{cite journal |last=Castelvecchi |first=Davide |title=DeepMind AI outdoes human mathematicians on unsolved problem |journal=Nature |date=December 14, 2023 |doi=10.1038/d41586-023-04043-w}}</ref>

=== Online bin packing === FunSearch was also applied to the online bin packing problem, where items must be assigned to bins as they arrive.<ref name="romera-paredes-2024" /> 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.<ref name="romera-paredes-2024" />

== Software == Google DeepMind released the FunSearch software in a public GitHub repository accompanying the FunSearch paper. The repository includes examples and data for cap sets, admissible sets, online bin packing, independent sets in strong products of cycle graphs, corner-free sets, and related experiments. It also includes a single-threaded implementation of the FunSearch pipeline, although the repository notes that it does not include the language models, execution sandbox, or distributed infrastructure used in the original experiments. The repository states that its software is licensed under the Apache License 2.0, while other materials are licensed under the Creative Commons Attribution 4.0 International License.<ref name="github-funsearch">{{cite web |title=google-deepmind/funsearch |website=GitHub |publisher=Google DeepMind |url=https://github.com/google-deepmind/funsearch |access-date=May 4, 2026}}</ref>

== Reception == In a ''Nature'' News & Views article, Jean-Baptiste Mouret described FunSearch as connecting genetic programming with large language models, writing that the work showed how language models could help computer programs evolve. The article characterized the system as a proof of concept for AI-assisted mathematical discovery.<ref name="mouret-2024" />

== References == {{reflist}}

== External links == * {{Official website|https://deepmind.google/discover/blog/funsearch-making-new-discoveries-in-mathematical-sciences-using-large-language-models/}} * {{GitHub|google-deepmind/funsearch}}

Category:Google DeepMind Category:Applications of artificial intelligence Category:Evolutionary algorithms Category:Large language models Category:Mathematical optimization Category:Software using the Apache license