# @nous/evo-search

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^n` inputs.
- 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

```bash
python3 -m pytest tests/ -q     # 32 tests
python3 -m ruff check .
```