Mathematical Discoveries from Program Search with Large Language Models (FunSearch)

14 Dec 2023 · Paper

---

1. Motivation

LLMs generate plausible but often incorrect ideas (confabulation), which blocks their use for problems where correctness is everything. Meanwhile, many hard combinatorial problems admit a fast, machine-checkable scoring function but no tractable exact solver. FunSearch’s bet: if a frozen LLM is confined to mutating a short, human-specified decision function and every output must survive a deterministic evaluator, the LLM’s creativity becomes a search operator for programs that generate verifiable solutions - producing artifacts that are interpretable, concise, and deployable rather than raw solutions.¹

---

2. Methodology

2.1 Search Structure

FunSearch is an island-based evolutionary method - “islands model, also known as a multiple population and multiple-deme model” - over a population of correct programs. Several subpopulations evolve independently to preserve diversity and escape local optima.¹ The system is distributed and asynchronous, with three worker types: a programs database, samplers (which build prompts and call the LLM), and evaluators (which execute and score programs).¹

Sampler:    k programs <- database.sample(island i)
            prompt = best-shot(k programs)          # §2.3
            child  = LLM.complete(prompt)
Evaluator:  scores = evaluate(execute(child))       # invalid -> discard
Database:   island i.register(child, scores)
Periodic:   discard worst half of islands;
            reseed them by cloning best individuals
            from surviving islands                  # migration

2.2 State Representation

The state is a user-written program skeleton containing boilerplate and known problem structure; only the function governing the critical logic is evolved. In the paper’s applications this is a priority function consumed by a fixed greedy solve procedure: “we evolve a priority function used to make decisions at every step.”¹ Evolved artifacts are short Python functions; the paper stresses that outputting programs-that-generate-solutions, rather than the solutions themselves, yields interpretability and scale-invariance.¹ A main function wires solve to evaluate, sometimes aggregating scores over multiple inputs (e.g., different bin-packing instances) by mean.¹

2.3 Generation Mechanism

The generator is a frozen pretrained LLM with no fine-tuning: Codey (PaLM-2 family, fine-tuned on code, accessed via API) for the main results; StarCoder is evaluated in the supplement as an open-source alternative.¹ New candidates come from best-shot prompting: sample $k$ programs from one island, sort them by score, rename them with version suffixes (priority_v0, priority_v1, …), concatenate them into a single prompt, and append the header of the function to be generated (priority_vk).¹ In practice $k=2$: “two functions lead to better results compared to just one, with diminishing returns beyond that.”¹ A fast-inference model is deliberately preferred over slower, higher-quality ones, because total throughput matters: results use on the order of $10^6$ samples each.¹ Prompts may optionally include docstrings, primitive functions, and imports.¹

2.4 Evaluation & Grounding

A user-provided evaluate function scores every candidate. Programs that fail to execute within time/memory limits or produce invalid outputs “are discarded” before entering the database - the evaluator “guards against confabulations and incorrect ideas.”¹ Because cap sets and admissible sets are finite verifiable objects, the evaluator doubles as a proof checker: accepted improvements (e.g., a size-512 cap set in dimension 8) are correct by construction.¹ AlphaEvolve’s later characterization puts the FunSearch evaluation regime at ≤20 minutes on a single CPU per candidate.²

2.5 Memory / Information Flow

The programs database is the only memory: it “keeps a population of correct programs” and serves samples for prompts. There is no textual or episodic memory - context injected into generation consists solely of sampled prior programs. Cross-island information flow happens exclusively through the periodic reset described below.¹

2.6 Selection & Propagation

Sampling first picks an island, then a program within it, “favouring higher-scoring and shorter programs” - an implicit parsimony pressure.¹ Migration is implemented as a reset: “we let information flow between the islands by periodically discarding the programs in the worst half of the islands (corresponding to the ones whose best individuals have the lowest scores). We replace the programs in those islands with a new population, initialized by cloning one of the best individuals from the surviving islands.”¹ Exact island counts and reset periods are specified in the paper’s Methods/supplement (not extracted here). This reset rule is the direct ancestor of the island-protection and migration rules in OpenEvolve and ShinkaEvolve.³⁴

2.7 Anti-Slop / Anti-Hallucination Mechanisms

Five layered controls: (i) the deterministic evaluator gates every candidate; (ii) invalid or non-terminating programs are discarded outright; (iii) the fixed greedy skeleton confines the LLM to the critical logic, reducing the chance “of mistakes that would render the entire program incorrect”; (iv) untrusted generated code executes in a sandboxed distributed system (DeepMind’s launchpad); (v) outputs are verifiable mathematical objects checked by the evaluator.¹ Note that the released repository explicitly excludes the LLM, sandbox, and distributed infrastructure.⁵

---

3. Results

• Cap sets: in dimension $n=8$, a cap set of size 512 - larger than the best previously known construction (which combined lower-dimensional cap sets); manual simplification of the discovered program yielded a construction resembling the optimal Hill 112-cap in $\mathbb{Z}_3^6$.¹
• Cap-set capacity via admissible sets: a full-size $I(12,7)$ admissible set improved the lower bound on cap-set capacity from 2.2180 (SAT-solver-based prior SOTA) to 2.2184; interpreting the discovered program (symmetric admissible sets) pushed the bound to 2.2202.¹
• Online 1-D bin packing (excess bins vs. offline optimum): FunSearch beats first fit and best fit on all seven benchmarks, e.g., 0.68% vs. 4.20%/3.90% on Weibull-10k and 0.03% vs. 4.00%/3.79% on Weibull-100k. Discovered strategy: use least-capacity bins only when the fit is very tight, avoiding unusable small gaps.¹
• Robustness: “every single run of FunSearch” succeeded on the cap-set (admissible-set) and bin-packing problems; results are “not too sensitive to the exact choice of LLM.”¹ Scale: ~$10^6$ samples per result.¹

---

4. Limitations & Assumptions

FunSearch needs machine-gradeable tasks with a fast evaluate and tolerates million-scale sample budgets; AlphaEvolve’s comparison notes no observed benefit from larger LLMs.² Only the marked function inside a human-designed skeleton evolves, and the skeleton “may constrain the space of programs.”¹ The production system (LLM, sandbox, distributed infrastructure) is not released.⁵

---

5. Critical Analysis

• Distinctive strength: the first demonstration that evaluator-grounded LLM program evolution produces publishable mathematics - and the artifacts are short, human-interpretable programs whose manual analysis yielded further improvements (2.2184 → 2.2202).¹
• Structural weakness / trade-off: the fixed skeleton and single-function scope cap what can be expressed; million-sample throughput requirements and best-shot prompting with $k{=}2$ are throughput-hungry and context-poor compared with successors.
• Connections: FunSearch is the direct ancestor of AlphaEvolve (#4) - AlphaEvolve’s Table 1 is explicitly a FunSearch→AlphaEvolve capability delta (whole files vs. single function, thousands vs. millions of samples, strong-LLM benefit vs. none), with shared authors (Novikov, Balog, Kumar, Dupont, Ruiz, Kohli, Fawzi).² Its islands + best-shot design is inherited by OpenEvolve (#7) and by ShinkaEvolve (#8), whose island-migration protection rule cites Romera-Paredes et al.; GigaEvo (#8) replicated its bin-packing SOTA as a validation task.³⁴ The same evolve-a-function-in-a-skeleton pattern underlies LLM-SR (#24)‘s equation-program search.

---

6. References

Footnotes

1. FunSearch full-text PDF mirror (HAL) - https://hal.science/hal-04682926v1/file/s41586-023-06924-6.pdf ↩ ↩² ↩³ ↩⁴ ↩⁵ ↩⁶ ↩⁷ ↩⁸ ↩⁹ ↩¹⁰ ↩¹¹ ↩¹² ↩¹³ ↩¹⁴ ↩¹⁵ ↩¹⁶ ↩¹⁷ ↩¹⁸ ↩¹⁹ ↩²⁰ ↩²¹ ↩²² ↩²³ ↩²⁴

2. Novikov et al., “AlphaEvolve,” arXiv:2506.13131 (Table 1 characterization of FunSearch) - https://arxiv.org/abs/2506.13131 ↩ ↩² ↩³

3. OpenEvolve repository - https://github.com/algorithmicsuperintelligence/openevolve ↩ ↩²

4. Lange, Imajuku & Cetin, “ShinkaEvolve,” arXiv:2509.19349 - https://arxiv.org/abs/2509.19349 ; Khrulkov et al., “GigaEvo,” arXiv:2511.17592 - https://arxiv.org/abs/2511.17592 ↩ ↩²

5. Romera-Paredes et al., Nature 625:468–475, DOI 10.1038/s41586-023-06924-6 - https://www.nature.com/articles/s41586-023-06924-6 ; official code: https://github.com/google-deepmind/funsearch ↩ ↩²