# google-deepmind/funsearch architecture

> Architecture diagram of the GitHub repository google-deepmind/funsearch, generated by GitDiagram from its file tree, README and a sample of source files (last updated 2026-03-30). It is an AI-made overview: check details against the source.

- Interactive diagram: https://gitdiagram.com/google-deepmind/funsearch
- Repository: https://github.com/google-deepmind/funsearch

## Overview

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: [`implementation/funsearch.py`](https://github.com/google-deepmind/funsearch/blob/HEAD/implementation/funsearch.py) (FunSearch loop), [`implementation/code_manipulation.py`](https://github.com/google-deepmind/funsearch/blob/HEAD/implementation/code_manipulation.py) (Code tools), [`implementation/sampler.py`](https://github.com/google-deepmind/funsearch/blob/HEAD/implementation/sampler.py) (Sampler), [`implementation/evaluator.py`](https://github.com/google-deepmind/funsearch/blob/HEAD/implementation/evaluator.py) (Evaluator)

## Diagram (Mermaid)

```mermaid
flowchart TD

subgraph "FunSearch core"
  funsearch_loop["FunSearch loop<br/>orchestrator<br/>[funsearch.py]"]
  program_db[("Program DB<br/>candidate store")]
  sampler(("Sampler<br/>selection<br/>[sampler.py]"))
  code_manipulation["Code tools<br/>rewrite bridge"]
  evaluator["Evaluator<br/>scoring boundary<br/>[evaluator.py]"]
  specification["Spec file<br/>task spec"]
  engine_tests["Engine tests<br/>verification"]
end

subgraph "Problem experiments"
  cap_notebook["Cap set notebook<br/>experiment notebook<br/>[cap_set.ipynb]"]
  cap_result["Cap result<br/>discovered artifact<br/>[n8_size512.txt]"]
  admissible_notebook["Admissible notebook<br/>experiment notebook"]
  admissible_results["Admissible results<br/>discovered artifact"]
  binpacking_notebook["Bin packing notebook<br/>experiment notebook<br/>[bin_packing.ipynb]"]
  cyclic_notebook["Cyclic graphs notebook<br/>experiment notebook"]
  cyclic_result["Cyclic result<br/>discovered artifact"]
  cornerfree_results["Corner-free results<br/>discovered artifact"]
end

subgraph "External dependencies"
  language_model(("Language model<br/>external generator"))
  sandbox["Sandbox<br/>external executor"]
end

cap_notebook -->|"drives"| funsearch_loop
admissible_notebook -->|"drives"| funsearch_loop
binpacking_notebook -->|"drives"| funsearch_loop
cyclic_notebook -->|"drives"| funsearch_loop
funsearch_loop -->|"selects"| sampler
funsearch_loop -->|"mutates"| code_manipulation
funsearch_loop -->|"scores"| evaluator
funsearch_loop -->|"updates"| program_db
sampler -->|"reads"| program_db
code_manipulation -->|"prompts"| language_model
language_model -->|"returns variants"| code_manipulation
evaluator -->|"executes in"| sandbox
specification -->|"defines task"| funsearch_loop
funsearch_loop -.->|"validated by"| engine_tests
cap_result -.->|"reproduces"| cap_notebook
admissible_results -.->|"reproduces"| admissible_notebook
cyclic_result -.->|"reproduces"| cyclic_notebook
cornerfree_results -.->|"artifact of"| funsearch_loop

click funsearch_loop "https://github.com/google-deepmind/funsearch/blob/main/implementation/funsearch.py"
click program_db "https://github.com/google-deepmind/funsearch/blob/main/implementation/programs_database.py"
click sampler "https://github.com/google-deepmind/funsearch/blob/main/implementation/sampler.py"
click code_manipulation "https://github.com/google-deepmind/funsearch/blob/main/implementation/code_manipulation.py"
click evaluator "https://github.com/google-deepmind/funsearch/blob/main/implementation/evaluator.py"
click specification "https://github.com/google-deepmind/funsearch/blob/main/implementation/specification_nonsymmetric_admissible_set.txt"
click cap_notebook "https://github.com/google-deepmind/funsearch/blob/main/cap_set/cap_set.ipynb"
click cap_result "https://github.com/google-deepmind/funsearch/blob/main/cap_set/n8_size512.txt"
click admissible_notebook "https://github.com/google-deepmind/funsearch/blob/main/admissible_set/admissible_set.ipynb"
click binpacking_notebook "https://github.com/google-deepmind/funsearch/blob/main/bin_packing/bin_packing.ipynb"
click cyclic_notebook "https://github.com/google-deepmind/funsearch/blob/main/cyclic_graphs/cyclic_graphs.ipynb"
click cyclic_result "https://github.com/google-deepmind/funsearch/blob/main/cyclic_graphs/nodes11_n4_size754.txt"

classDef toneNeutral fill:#f8fafc,stroke:#334155,stroke-width:1.5px,color:#0f172a
classDef toneBlue fill:#dbeafe,stroke:#2563eb,stroke-width:1.5px,color:#172554
classDef toneAmber fill:#fef3c7,stroke:#d97706,stroke-width:1.5px,color:#78350f
classDef toneMint fill:#dcfce7,stroke:#16a34a,stroke-width:1.5px,color:#14532d
classDef toneRose fill:#ffe4e6,stroke:#e11d48,stroke-width:1.5px,color:#881337
classDef toneIndigo fill:#e0e7ff,stroke:#4f46e5,stroke-width:1.5px,color:#312e81
classDef toneTeal fill:#ccfbf1,stroke:#0f766e,stroke-width:1.5px,color:#134e4a
class funsearch_loop,program_db,sampler,code_manipulation,evaluator,specification,engine_tests toneBlue
class cap_notebook,cap_result,admissible_notebook,admissible_results,binpacking_notebook,cyclic_notebook,cyclic_result,cornerfree_results toneAmber
class language_model,sandbox toneMint
```

## Components

### FunSearch core

Reusable program-search machinery under implementation/

- [FunSearch loop](https://github.com/google-deepmind/funsearch/blob/HEAD/implementation/funsearch.py): orchestrator · Single-threaded search cycle coordinating sampling, variation, evaluation, and retention · `implementation/funsearch.py`
- [Program DB](https://github.com/google-deepmind/funsearch/blob/HEAD/implementation/programs_database.py): candidate store · Stores the population of candidate programs and their scores · `implementation/programs_database.py`
- [Sampler](https://github.com/google-deepmind/funsearch/blob/HEAD/implementation/sampler.py): selection · Chooses programs or fragments for variation · `implementation/sampler.py`
- [Code tools](https://github.com/google-deepmind/funsearch/blob/HEAD/implementation/code_manipulation.py): rewrite bridge · Extracts and rewrites code fragments into promptable mutation targets · `implementation/code_manipulation.py`
- [Evaluator](https://github.com/google-deepmind/funsearch/blob/HEAD/implementation/evaluator.py): scoring boundary · Scores generated candidates against the task objective · `implementation/evaluator.py`
- [Spec file](https://github.com/google-deepmind/funsearch/blob/HEAD/implementation/specification_nonsymmetric_admissible_set.txt): task spec · Example problem specification used by the engine · `implementation/specification_nonsymmetric_admissible_set.txt`
- **Engine tests**: verification · Tests covering the major search-engine modules

### Problem experiments

Notebook-driven problem setups and discovered artifacts

- [Cap set notebook](https://github.com/google-deepmind/funsearch/blob/HEAD/cap_set/cap_set.ipynb): experiment notebook · Notebook for the cap set construction search · `cap_set/cap_set.ipynb`
- [Cap result](https://github.com/google-deepmind/funsearch/blob/HEAD/cap_set/n8_size512.txt): discovered artifact · Precomputed cap set construction output · `cap_set/n8_size512.txt`
- [Admissible notebook](https://github.com/google-deepmind/funsearch/blob/HEAD/admissible_set/admissible_set.ipynb): experiment notebook · Notebook for admissible-set experiments · `admissible_set/admissible_set.ipynb`
- **Admissible results**: discovered artifact · Discovered admissible-set and pre-admissible-set outputs
- [Bin packing notebook](https://github.com/google-deepmind/funsearch/blob/HEAD/bin_packing/bin_packing.ipynb): experiment notebook · Notebook for online 1D bin packing heuristics · `bin_packing/bin_packing.ipynb`
- [Cyclic graphs notebook](https://github.com/google-deepmind/funsearch/blob/HEAD/cyclic_graphs/cyclic_graphs.ipynb): experiment notebook · Notebook for cyclic-graph independent-set experiments · `cyclic_graphs/cyclic_graphs.ipynb`
- [Cyclic result](https://github.com/google-deepmind/funsearch/blob/HEAD/cyclic_graphs/nodes11_n4_size754.txt): discovered artifact · Precomputed independent-set output for a cyclic-graph instance · `cyclic_graphs/nodes11_n4_size754.txt`
- **Corner-free results**: discovered artifact · Corner-free set outputs stored as result files

### External dependencies

Runtime pieces required by the full system but not included here

- **Language model**: external generator · Absent from this repo; supplies candidate code mutations
- **Sandbox**: external executor · Absent from this repo; safely runs untrusted generated code

## Connections

- 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
