Research-Stack/docs/COEVOLUTION_MODEL.md

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.

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)

{
  "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

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.