mirror of
https://github.com/allaunthefox/Research-Stack.git
synced 2026-07-31 03:05:21 +00:00
183766b2a8
Complete model of the co-evolution loop: 1. DAG finds basin → checkpoint 2. FAMM stores checkpoint (delay-line memory with frustration) 3. FSDU computes scar (residual manifold geometry) 4. Scar transforms coordinates (Fisher eigenstructure rotation) 5. DNA re-encodes in new coordinates (alphabet evolves) 6. Sort accelerates search (lexicographic = energy order) 7. Results feedback as new scars (loop closes) All four systems (DAG, FAMM, FSDU, DNA) are coupled. None can be understood in isolation. Refs: FAMM.lean (delay-line memory), FSDU_theory.md (scar update), ChentsovFinite.lean (metric uniqueness), dna_gpu.py (sort acceleration)
300 lines
12 KiB
Markdown
300 lines
12 KiB
Markdown
# CO-EVOLUTION: FAMM + Resumable DAG + DNA Sort
|
||
|
||
## The Full Loop
|
||
|
||
```
|
||
┌─────────────────────────────────────────────────────────────────────────────┐
|
||
│ CO-EVOLUTION ENGINE (FAMM-DAG-DNA) │
|
||
│ │
|
||
│ ┌─────────┐ ┌─────────┐ ┌─────────┐ ┌─────────┐ ┌─────────┐ │
|
||
│ │ DAG │───>│ FAMM │───>│ FSDU │───>│ DNA │───>│ SORT │ │
|
||
│ │ explores│ │ stores │ │ scars │ │ re-enc │ │ accel │ │
|
||
│ │ basin │ │ checkpt │ │ manifold│ │ coords │ │ search │ │
|
||
│ └────┬────┘ └────┬────┘ └────┬────┘ └────┬────┘ └────┬────┘ │
|
||
│ ↑ │ │ │ │ │
|
||
│ └──────────────┴──────────────┴──────────────┴──────────────┘ │
|
||
│ FEEDBACK │
|
||
│ │
|
||
│ Each iteration: │
|
||
│ 1. DAG evaluates chunk S_k → partial results R_k │
|
||
│ 2. FAMM stores (R_k, g^{(k)}, T_k) as delay-line cell │
|
||
│ 3. FSDU computes scar: what did traversal change on manifold? │
|
||
│ 4. Scar defines coordinate transform T_{k+1} │
|
||
│ 5. DNA re-encodes solutions in T_{k+1} coordinates │
|
||
│ 6. Sort accelerates: lexicographic order = energy order in NEW coords │
|
||
│ 7. Results feed back: new scar → new FAMM cell → new DAG checkpoint │
|
||
│ │
|
||
│ The manifold evolves. The alphabet evolves. The search evolves. │
|
||
│ All three co-evolve. │
|
||
└─────────────────────────────────────────────────────────────────────────────┘
|
||
```
|
||
|
||
## What FAMM Actually Is
|
||
|
||
From `2-Search-Space/FAMM/FAMM.lean`:
|
||
|
||
**FAMM = Frustrated Access Memory Module**
|
||
|
||
Not a standard memory. A **delay-line memory** where access time IS the storage mechanism.
|
||
|
||
```lean
|
||
structure FAMMCell where
|
||
data : Q16_16 -- stored value
|
||
delay : Q16_16 -- access delay (time to read)
|
||
delayMass : Q16_16 -- causal constraint mass
|
||
delayWeight : Q16_16 -- constraint strength
|
||
```
|
||
|
||
The "frustration" is the competing delay constraints. When multiple FAMM cells want the same delay line at the same time, they can't all have it. The system is **frustrated** — like a spin glass where not all spins can align.
|
||
|
||
This is not a bug. It's the **computational mechanism**:
|
||
|
||
- High delayMass = important constraint (hard to satisfy)
|
||
- High delayWeight = strong influence (affects many other cells)
|
||
- Frustration = information about the manifold's curvature
|
||
|
||
## FSDU = FAMM Scar Differential Update
|
||
|
||
From `2-Search-Space/FAMM/docs/FSDU_theory.md`:
|
||
|
||
**Every traversal leaves a scar.**
|
||
|
||
The scar is residual geometry that rewrites the graph metric:
|
||
|
||
```
|
||
scar_k = (∂E/∂θ evaluated at p̂_k, eigenvectors of g^{(k)})
|
||
```
|
||
|
||
This scar is not just a record of what was searched. It's **active geometry**:
|
||
|
||
- It defines new coordinates for the next search
|
||
- It weights the priority field (A* vs Dijkstra vs Greedy)
|
||
- It makes the manifold fractal (scars at every scale)
|
||
|
||
## The Co-Evolution Mechanism
|
||
|
||
### Step 1: DAG Explores Chunk
|
||
|
||
```
|
||
S_k = subset of {0,1}^n to evaluate
|
||
R_k = {E(x) : x ∈ S_k} -- energies
|
||
p̂_k = empirical distribution from R_k -- Gibbs-like
|
||
g^{(k)} = Fisher information matrix -- from Chentsov (proven unique)
|
||
eig_k = eigenvectors(g^{(k)}) -- principal directions
|
||
T_k = coordinate_transform(eig_k) -- rotation matrix
|
||
```
|
||
|
||
### Step 2: FAMM Stores Checkpoint
|
||
|
||
```
|
||
cell_k = FAMMCell {
|
||
data = pack(R_k, best_E, best_x) -- compressed results
|
||
delay = f(eig_k[0]) -- largest eigenvalue → delay
|
||
delayMass = Tr(g^{(k)}) -- trace = total curvature
|
||
delayWeight = |S_k| / 2^n -- coverage fraction
|
||
}
|
||
|
||
bank.store(cell_k) -- writes to delay line
|
||
```
|
||
|
||
The **delay encodes the eigenvalue** — directions with high curvature (sharp basins) have longer delays because they're more "important" (takes longer to fully explore). The **delayMass encodes the trace** — total manifold curvature discovered. The **delayWeight encodes coverage** — how much of the space we've seen.
|
||
|
||
### Step 3: FSDU Computes Scar
|
||
|
||
```
|
||
scar_k = FSDU.compute(bank, cell_k)
|
||
|
||
-- What changed on the manifold?
|
||
scar_k.gradient = ∇_θ E(p̂_k) -- where is energy decreasing?
|
||
scar_k.curvature = eig_k[0] -- sharpest basin direction
|
||
scar_k.frustration = delayMass × (1 - coverage) -- unsatisfied constraints
|
||
scar_k.memory = bank.accumulated_scars -- all previous scars combined
|
||
```
|
||
|
||
The **frustration** is key: it's high when we've found a sharp basin (high curvature) but haven't explored it fully (low coverage). This tells the system: "there's something important here, go deeper."
|
||
|
||
### Step 4: Scar Transforms Coordinates
|
||
|
||
```
|
||
T_{k+1} = scar_k.define_transform()
|
||
|
||
-- New coordinates align with:
|
||
-- 1. Gradient direction (where energy decreases fastest)
|
||
-- 2. Curvature eigenvector (sharpest basin)
|
||
-- 3. Frustration vector (unexplored important regions)
|
||
|
||
-- This is a generalized rotation on the Fisher manifold:
|
||
-- T_{k+1} = exp(η · scar_k.generator) -- Lie group element
|
||
-- where η = learning rate, generator = scar structure
|
||
```
|
||
|
||
### Step 5: DNA Re-Encodes
|
||
|
||
```
|
||
-- OLD: DNA(x) = int_to_dna(energy_rank(x)) in original coordinates
|
||
-- NEW: DNA'(x) = int_to_dna(energy_rank'(x)) in T_{k+1} coordinates
|
||
|
||
-- The alphabet ORDERING changes:
|
||
-- If T_{k+1} rotates basis, the "first" base is now the "gradient direction"
|
||
-- Lexicographic sort explores gradient-first in the new system
|
||
|
||
-- DNA bases A,B,C,G,P,S,T,Z map to directions on the manifold
|
||
-- After transform T_{k+1}, base A = steepest descent direction
|
||
```
|
||
|
||
### Step 6: Sort Accelerates
|
||
|
||
```
|
||
-- Encode solutions in T_{k+1} coordinates
|
||
-- Sort DNA strings → lexicographic = energy order in new coords
|
||
-- Decode → solutions ranked by energy in the TRANSFORMED space
|
||
|
||
-- Key: sorting explores the transformed space efficiently
|
||
-- because the alphabet has been re-ordered to align with the scar
|
||
```
|
||
|
||
### Step 7: Feedback Loop Closes
|
||
|
||
```
|
||
results_{k+1} = evaluate(sorted_solutions)
|
||
|
||
-- New results feed back:
|
||
new_cell = FAMMCell {
|
||
data = pack(results_{k+1})
|
||
delay = f(eig_{k+1})
|
||
delayMass = Tr(g^{(k+1)})
|
||
delayWeight = |S_{k+1}| / 2^n
|
||
}
|
||
|
||
bank.store(new_cell)
|
||
|
||
-- The scar accumulates:
|
||
scar_{k+1} = FSDU.compute(bank, new_cell)
|
||
-- This scar includes ALL previous scars through the accumulated memory
|
||
|
||
-- Continue: T_{k+2} from scar_{k+1}, DNA re-encodes, sort, feedback...
|
||
```
|
||
|
||
## Why This Co-Evolves
|
||
|
||
| Component | What it learns | How it adapts |
|
||
|---|---|---|
|
||
| **DAG** | Basin structure from partial evaluations | Selects which frontier node to expand |
|
||
| **FAMM** | Traversal history as delay-line scars | Access patterns inform next read/write |
|
||
| **FSDU** | Manifold geometry from Fisher eigenstructure | Defines coordinate transforms |
|
||
| **DNA** | Optimal alphabet ordering from transforms | Re-encodes so sort explores efficiently |
|
||
| **Sort** | Nothing (it's a mechanical operation) | But it's FAST (GPU/parallel) |
|
||
|
||
All four learning components co-evolve:
|
||
- DAG's basins → FAMM's scars
|
||
- FAMM's access patterns → FSDU's transforms
|
||
- FSDU's transforms → DNA's alphabet ordering
|
||
- DNA's ordering → sort's exploration efficiency
|
||
- Sort's results → DAG's new basins
|
||
|
||
## The Receipt (Per Chunk, in Co-Evolution)
|
||
|
||
```json
|
||
{
|
||
"receiptID": "sha256(chunk_k)",
|
||
"expression": "co-evolution chunk k of QUBO Q",
|
||
"finalState": "Λ", // always Λ — we're learning
|
||
"ticCount": chunk_size,
|
||
"fuelUsed": n * chunk_size + FAMM_access_cost,
|
||
"pathCost": best_E_so_far,
|
||
"libraryRefs": [
|
||
"ChunkLib", // evaluated S_k
|
||
"FAMMLib", // stored checkpoint
|
||
"FSDULib", // computed scar
|
||
"MetricLib", // Fisher eigenstructure
|
||
"DNALib", // re-encoded
|
||
"SearchLib" // sorted
|
||
],
|
||
"parentID": "chunk_{k-1}",
|
||
"scarHash": "sha256(scar_k)", // the transform that was applied
|
||
"transform": "T_k → T_{k+1}", // coordinate rotation
|
||
"verified": true
|
||
}
|
||
```
|
||
|
||
## Formal Specification
|
||
|
||
```lean
|
||
structure FAMMCoEvolutionState where
|
||
dag : ResumableDAG -- checkpoint graph
|
||
fammBank : FAMMBank -- delay-line memory
|
||
scarHistory : List Scar -- accumulated scars
|
||
dnaAlphabet : Fin 8 → HachimojiState -- current base ordering
|
||
chunkCount : Nat -- iterations so far
|
||
bestEnergy : Float -- global best
|
||
|
||
-- One co-evolution step
|
||
def coevolveStep (state : FAMMCoEvolutionState) (Q : Matrix n n Float)
|
||
(chunkSize : Nat) : FAMMCoEvolutionState :=
|
||
|
||
-- 1. DAG explores
|
||
let frontier := state.dag.frontier
|
||
let node := frontier.selectMostPromising
|
||
let chunk := ChunkLib.evaluate(node.subset, Q, chunkSize)
|
||
|
||
-- 2. FAMM stores
|
||
let cell := FAMMLib.toCell(chunk, node.transform)
|
||
let newBank := FAMMLib.store(state.fammBank, cell)
|
||
|
||
-- 3. FSDU scars
|
||
let scar := FSDULib.compute(newBank, cell)
|
||
|
||
-- 4. Coordinate transform
|
||
let newTransform := scar.defineTransform
|
||
|
||
-- 5. DNA re-encodes
|
||
let newAlphabet := DNALib.reorder(newTransform)
|
||
|
||
-- 6. Sort (GPU/parallel)
|
||
let solutions := DNALib.encodeSortDecode(chunk, newAlphabet)
|
||
|
||
-- 7. Feedback: update DAG, best energy, scar history
|
||
let newNode := dag.insert(solutions, parent:=node.id, transform:=newTransform)
|
||
{
|
||
dag := newNode.dag,
|
||
fammBank := newBank,
|
||
scarHistory := scar :: state.scarHistory,
|
||
dnaAlphabet := newAlphabet,
|
||
chunkCount := state.chunkCount + 1,
|
||
bestEnergy := min state.bestEnergy solutions.bestEnergy
|
||
}
|
||
```
|
||
|
||
## Why This Is Different
|
||
|
||
| Existing Approach | Limitation | How Co-Evolution Fixes It |
|
||
|---|---|---|
|
||
| Branch-and-bound | Fixed branching, no learning | Scar transforms coordinates adaptively |
|
||
| Monte Carlo | Random, no structure exploitation | FAMM remembers structure, DNA exploits it |
|
||
| Divide-and-conquer | Fixed splits, independent subproblems | DAG has manifold-informed frontier |
|
||
| Genetic algorithm | Fixed encoding, slow evolution | DNA alphabet co-evolves with manifold |
|
||
| GPU sort (90s) | Fixed encoding, no learning | Re-encodes between sorts based on scars |
|
||
| FAMM alone | No DNA acceleration | DNA sort accelerates each chunk |
|
||
| DNA sort alone | No checkpointing/resume | FAMM DAG makes every chunk resumable |
|
||
| Resumable DAG alone | No coordinate transform | FSDU scars define transforms |
|
||
|
||
## The Key Equation
|
||
|
||
```
|
||
co-evolution step k:
|
||
|
||
(dag_k, famm_k, scar_k, dna_k) → (dag_{k+1}, famm_{k+1}, scar_{k+1}, dna_{k+1})
|
||
|
||
via:
|
||
1. dag_k.frontier → chunk_k
|
||
2. famm_k.store(chunk_k) → cell_k
|
||
3. FSDU(famm_k, cell_k) → scar_k
|
||
4. scar_k → T_{k+1}
|
||
5. dna_k.reorder(T_{k+1}) → dna_{k+1}
|
||
6. sort(dna_{k+1}, chunk_k) → solutions_{k+1}
|
||
7. dag_k.insert(solutions_{k+1}) → dag_{k+1}
|
||
8. famm_k.store(solutions_{k+1}) → famm_{k+1}
|
||
9. scar_k + FSDU(famm_{k+1}) → scar_{k+1}
|
||
```
|
||
|
||
All four systems (DAG, FAMM, FSDU, DNA) are coupled. None can be understood in isolation.
|