Evolutionary & program-synthesis discovery for the Phase-178 autonomous-research stack (TODOS/phase-178 §178.6). Sovereign replication of the AlphaEvolve / FunSearch pattern with a deterministic, machine-checkable problem test bed.
Components#
| Component | Module | Summary |
|---|---|---|
| Island model | island.py |
AlphaEvolve-pattern: N islands, ring migration, per-island elitism, tournament selection + crossover + mutation. Pluggable Mutator/Crossover (LLM ensemble or deterministic edit) and an evaluator "pool" (map_fn). Deterministic given seed. (§178.6.1.1) |
| FunSearch | funsearch.py |
Program search with a clustered program database — clusters keyed by score signature, Boltzmann cluster sampling, shorter-program bias within a cluster — periodic island reset, skeleton-preserving mutation, Pareto (score, simplicity) front. (§178.6.2.1) |
| Problem test bed | problems/ |
Exact verifiers + scorers: matmul multiplication-count (Strassen R=7 / naive R=8 landmarks), sorting-network depth (0/1 principle), cap-set, bin-packing, kissing number, expression-tree symbolic regression. (§178.6.1.2 / §178.6.2.2) |
| Kernel autotuner | kernel_autotune.py |
Evolve tile parameters under a numerical-equivalence gate; real perf_counter timing mode or a deterministic roofline cost-model mode; ships blocked-matmul + RMSNorm reference kernels. (§178.6.1.3, interop with §178.4.1.5) |
| Discovery benchmark | benchmark.py |
Known-optimal-landmark harness with regression alarms and new-SOTA flags, plus the open-math-sweep scaffolding. (§178.6.1.4, §178.6.2.3) |
What is real vs external#
Every fitness here is a deterministically machine-checkable quantity, so a claimed discovery is auditable, not asserted:
- matmul: the trilinear reconstruction must exactly equal the matmul tensor — Strassen's 7 products and the naive 8 both verify; drop a product and it fails.
- sorting networks: validity is the 0/1 principle over all
2^ninputs. - cap-set: no three points sum to zero mod 3 (the verifier caught a bad hand-picked "cap set" in review — greedy is optimal for n≤2 and a valid lower bound beyond).
- kissing / bin-packing / symbolic-regression RMSE: all exact.
The tests prove the search itself works: the island model converges to a convex optimum with monotone (elitist) history, discovers symbolic-regression programs that beat their seeds, and packs bins no worse than first-fit-decreasing; FunSearch homes in on an integer target and keeps a complexity-sorted Pareto front; the autotuner finds the cost-model optimum matching exhaustive grid search.
Reproducing AlphaEvolve's reported match-or-beat on the ~50-problem open-math
canon (and the 4×4→48 matmul result) additionally requires the Gemini/Claude LLM
mutation ensemble and its compute budget — those plug in as the Mutator and as
more registry entries; the harness shape is identical.
Testing#
python3 -m pytest tests/ -q # 32 tests
python3 -m ruff check .