FunSearch: Making New Discoveries in Mathematical Sciences Using Large Language Models

Forum topic · ✨步子哥 · 2026-01-08

Summary

FunSearch, developed by Google DeepMind, is a method that pairs a pre-trained large language model (LLM) with an automated evaluator to search for new solutions in mathematics and computer science. The LLM proposes candidate solutions as computer programs, while the evaluator verifies their correctness and scores their performance; the best programs are fed back to the LLM in an evolutionary loop. Key design elements include best-shot prompting, skeleton programs, island-based evolution, and fully automated evaluation. FunSearch produced the largest cap set constructions in over 20 years for the cap set problem in extremal combinatorics, and autonomously discovered a bin packing heuristic that outperformed established algorithms on standard benchmarks. Unlike black-box AI outputs, the discovered solutions are human-readable programs that experts can verify, study, and refine. FunSearch laid the groundwork for DeepMind's AlphaEvolve (2025), which scales the approach using Gemini 2.0 models to optimize entire codebases, including data center scheduling and matrix multiplication algorithms. The work demonstrates a blueprint for verifiable, LLM-driven scientific discovery.

Introduction

Large Language Models (LLMs) have shown remarkable capabilities in coding, writing, and question answering, but their tendency to "hallucinate" — producing plausible but incorrect information — has limited their use in scientific discovery. Researchers at Google DeepMind introduced FunSearch ("Function Search"), a novel method that harnesses the creative power of LLMs while guarding against hallucinations by rigorously verifying every proposal. FunSearch has, for the first time, enabled an LLM-based system to make genuine discoveries on open, challenging problems in the mathematical sciences.

The FunSearch Method: Evolutionary Search in Function Space

FunSearch exploits the fact that many problems in mathematics and computer science are "easy to evaluate" but "hard to solve." It formulates such problems as a search for functions — for example, a function that outputs candidate solutions to a puzzle. A pre-trained LLM proposes programs, and an automated evaluator tests each one, scoring correctness and quality. The best-performing programs are iteratively fed back to the LLM, evolving an initial set of ideas into progressively better solutions.

Key design choices include:

Best-Shot Prompting: Rather than random sampling, the LLM receives the best solutions found so far as context, encouraging it to improve on the most promising ideas. The system maintains a database of high-scoring programs used as prompt examples.
Skeleton Programs: FunSearch often starts from a simple "skeleton" providing the basic structure, with the LLM evolving only the critical function governing problem-solving logic (e.g., a heuristic in a greedy algorithm). This keeps the search tractable and interpretable.
Island-Based Evolution: The search is split into multiple sub-populations ("islands") evolving in parallel and periodically sharing their best solutions, maintaining diversity and avoiding local optima.
Automated Evaluation: The evaluator executes each generated function on test cases and scores it automatically, enabling rapid iteration over thousands of candidates without human intervention.

This creates a self-reinforcing discovery loop. Importantly, the discovered programs are interpretable pieces of code that humans can read, understand, and build upon — a major advantage over black-box AI solutions.

Discovering New Mathematical Insights

FunSearch was applied to two long-standing open problems and surpassed the best-known results in both:

Cap Set Problem (Mathematics)

The cap set problem asks for the largest subset of points in a high-dimensional grid over $\mathbb{F}_3^n$ such that no three points lie on a line. Brute-force enumeration is infeasible as dimension grows. FunSearch discovered constructions yielding the largest cap sets ever found — the largest improvement in over 20 years — outperforming both previous human constructions and state-of-the-art computer search methods, especially at larger scales. This was the first genuine AI-driven discovery on a well-known open problem in pure mathematics (a problem once called his favorite open question by Fields Medalist Terence Tao).

Online Bin Packing (Computer Science)

In the online bin packing problem, items of different sizes arrive one by one and must be placed immediately into bins, minimizing the total number of bins — a problem with practical applications like data center resource allocation. FunSearch autonomously evolved a new heuristic that outperformed established algorithms, packing the same items into significantly fewer bins than the best previously known heuristics on standard benchmarks, despite not being specifically trained on bin packing.

Broader Impact and Future Directions

FunSearch addresses the fundamental challenge of getting creative ideas from an AI while ensuring their correctness. Any problem that can be formulated as a function search with a measurable outcome is a candidate for the approach — from cryptography and optimization to physical simulations. Because outputs are human-readable programs, domain experts can verify, learn from, and refine the results, creating a collaborative human-AI discovery loop.

The success of FunSearch paved the way for DeepMind's AlphaEvolve (2025), which builds on the same evolutionary approach at larger scale, using Gemini 2.0 LLMs to evolve entire codebases. AlphaEvolve has improved Google data center job scheduling (saving substantial computing resources) and discovered faster matrix multiplication algorithms.

Conclusion

FunSearch demonstrates that LLMs, when combined with rigorous automated evaluation in an evolutionary framework, can make genuine scientific discoveries — breaking a decades-old combinatorics record and finding better real-world algorithms. It offers a blueprint for AI systems that propose, verify, and iteratively improve solutions, amplifying rather than replacing human ingenuity, and marks a significant step toward AI-driven discovery as a normal part of the scientific process.