How google-deepmind/funsearch works
This repository is organized around two layers:
1. A generic FunSearch implementation in implementation/
2. Problem-specific notebooks and result artifacts in the other directories
The overall architecture is a research codebase for discovering mathematical constructions by program search, rather than a production application.
Main subsystems
• implementation/
- This is the core search engine.
- It contains the evolutionary loop, candidate-program storage, code editing/manipulation utilities, evaluation logic, and sampling logic.
- It is explicitly single-threaded in this repo and is meant to be adapted to an external language model, sandbox, and distributed execution environment that are not included here.
• Problem-specific experiment directories
- cap_set/
- admissible_set/
- bin_packing/
- cyclic_graphs/
- corner_free_set/
These directories contain notebooks and/or precomputed outputs for specific combinatorial optimization or construction problems.
How the system is structured
The repository splits cleanly into three kinds of components:
1. Search infrastructure
- Located under implementation/
- Responsible for proposing candidate programs, running them, scoring them, and keeping the best ones.
2. Problem definitions and experiment notebooks
- Located in the problem directories
- Each notebook sets up a specific mathematical task, invokes or demonstrates the FunSearch pipeline, and often reproduces results from the paper.
3. Discovered artifacts
- Plain-text .txt files containing sets or constructions found by the search
- These are stored alongside the relevant problem directory for convenience and reproducibility
Core data flow
The main flow in the generic FunSearch pipeline is:
1. A problem-specific notebook or driver defines the target specification
- For example, a cap set, admissible set, cyclic graph independent set, or bin-packing heuristic problem.
- The repository includes one example specification file in implementation/specification_nonsymmetric_admissible_set.txt.
2. The search engine samples existing candidate programs
- programs_database.py stores the current population of candidate programs and their scores.
- sampler.py chooses which programs or fragments to present for variation.
3. Code is transformed into prompts or mutation targets
- code_manipulation.py handles extraction and rewriting of code fragments.
- This is part of the interface between stored programs and whatever language model is used externally to generate new variants.
4. New candidate programs are evaluated
- evaluator.py scores the generated candidate against the task-specific objective.
- The repo does not include the execution sandbox used for untrusted code, so the evaluator is only one part of the full runtime setup.
5. The best candidates are fed back into the database
- Successful programs are retained, scored, and become the next generation’s parents.
6. The loop repeats
- funsearch.py orchestrates this search cycle in a single-threaded form.
Important architectural boundaries
• Generic engine vs. problem-specific content
- The code in implementation/ is intended to be reusable across tasks.
- The notebooks and data files in the problem directories are specific to each combinatorial domain.
• Included vs. external infrastructure
- Included: program storage, code manipulation, evaluation logic, single-threaded search orchestration, tests.
- Not included: the language model, the sandbox for running generated code safely, and the distributed system used in the original large-scale experiments.
• Source code vs. discovered outputs
- The repository keeps both the search machinery and the resulting constructions.
- The .txt files in the problem directories are outputs of the search, not inputs to the generic engine.
Repo-specific contents by directory
• cap_set/
- Notebook plus a precomputed cap set result file n8_size512.txt
- Represents discovered cap sets and a runnable example notebook
• admissible_set/
- Notebook plus several discovered admissible set files and pre-admissible set files
- The size...txt filenames encode the size of the discovered construction
• bin_packing/
- Notebook for online 1D bin packing heuristics
- This directory is more evaluation-focused and appears to emphasize reproducing the reported heuristic behavior
• cyclic_graphs/
- Notebook plus a discovered independent set result file
- The output is framed as an independent set problem in strong products of cyclic graphs
• corner_free_set/
- Contains only numerical result files
- These are the discovered index sets satisfying the corner-free constraints described in the paper’s supplementary material
• implementation/
- The reusable FunSearch machinery
- Also includes tests for the major modules:
- code_manipulation_test.py
- evaluator_test.py
- funsearch_test.py
- programs_database_test.py
Relevant technologies and runtime characteristics
• Python-based implementation
• Jupyter notebooks are the primary user-facing entry point for the experiments
• Colab is the intended easy execution environment, according to the README
• The architecture is research-oriented and notebook-driven, not packaged as a service or CLI application
• Tests are included for the engine components, indicating the core logic is designed to be verifiable independently of the notebooks
How to think about the architecture diagram
A useful diagram would show:
• At the top or left: problem notebooks and problem-specific specifications/data
• In the center: the FunSearch engine in implementation/
- funsearch.py as the orchestration layer
- programs_database.py as the persistent candidate store
- sampler.py as selection logic
- code_manipulation.py as the code-to-prompt / mutation bridge
- evaluator.py as the scoring boundary
• On the outside: an external language model and a sandbox, both absent from this repo but required by the full system
• At the bottom or right: discovered constructions saved as text files in the problem directories
In short, this repository is a split between a reusable program-search engine and a set of domain-specific mathematical experiments and results.
Main entry points: funsearch.py FunSearch loop · code_manipulation.py Code tools · sampler.py Sampler · evaluator.py Evaluator
Components 17
FunSearch core
Reusable program-search machinery under implementation/
- FunSearch loop · Single-threaded search cycle coordinating sampling, variation, evaluation, and retention
implementation/funsearch.py - Program DB · Stores the population of candidate programs and their scores
implementation/programs_database.py - Sampler · Chooses programs or fragments for variation
implementation/sampler.py - Code tools · Extracts and rewrites code fragments into promptable mutation targets
implementation/code_manipulation.py - Evaluator · Scores generated candidates against the task objective
implementation/evaluator.py - Spec file · Example problem specification used by the engine
implementation/specification_nonsymmetric_admissible_set.txt - Engine tests · Tests covering the major search-engine modules
Problem experiments
Notebook-driven problem setups and discovered artifacts
- Cap set notebook · Notebook for the cap set construction search
cap_set/cap_set.ipynb - Cap result · Precomputed cap set construction output
cap_set/n8_size512.txt - Admissible notebook · Notebook for admissible-set experiments
admissible_set/admissible_set.ipynb - Admissible results · Discovered admissible-set and pre-admissible-set outputs
- Bin packing notebook · Notebook for online 1D bin packing heuristics
bin_packing/bin_packing.ipynb - Cyclic graphs notebook · Notebook for cyclic-graph independent-set experiments
cyclic_graphs/cyclic_graphs.ipynb - Cyclic result · Precomputed independent-set output for a cyclic-graph instance
cyclic_graphs/nodes11_n4_size754.txt - Corner-free results · Corner-free set outputs stored as result files
External dependencies
Runtime pieces required by the full system but not included here
- Language model · Absent from this repo; supplies candidate code mutations
- Sandbox · Absent from this repo; safely runs untrusted generated code
Connections 18
- Cap set notebook → FunSearch loop: drives · Defines a cap-set task and invokes the generic search loop
- Admissible notebook → FunSearch loop: drives · Defines admissible-set variants and runs the search engine
- Bin packing notebook → FunSearch loop: drives · Sets up the bin-packing heuristic experiment
- Cyclic graphs notebook → FunSearch loop: drives · Sets up the cyclic-graph construction search
- FunSearch loop → Sampler: selects · Orchestrates which candidate programs are sampled for variation
- FunSearch loop → Code tools: mutates · Routes stored code through fragment extraction and rewriting
- FunSearch loop → Evaluator: scores · Sends generated candidates for task-specific scoring
- FunSearch loop → Program DB: updates · Retains successful programs and their scores for the next generation
- Sampler → Program DB: reads · Uses stored candidate population as the sampling pool
- Code tools → Language model: prompts · Builds prompt or mutation targets for the external generator
- Language model → Code tools: returns variants · Produces candidate code fragments consumed by the search loop
- Evaluator → Sandbox: executes in · Requires an external execution boundary for untrusted candidate code
- Spec file → FunSearch loop: defines task · Supplies the target specification used by the engine
- FunSearch loop → Engine tests: validated by · Core modules are covered by dedicated tests
- Cap result → Cap set notebook: reproduces · Notebook demonstrates or reproduces the stored cap-set output
- Admissible results → Admissible notebook: reproduces · Notebook demonstrates the admissible-set outputs
- Cyclic result → Cyclic graphs notebook: reproduces · Notebook demonstrates the cyclic-graph output
- Corner-free results → FunSearch loop: artifact of · Result files are outputs of the shared search machinery