code wiki / _hdl_build / nx_evo_synth_gate.nx
nx_evo_synth_gate.nx source
↩ module page · 141 lines · 10746 B
1// nx_evo_synth_gate.nx -- the operator's question: "cant it just use a search engine for enrichment in a loop
2// over an LLM -- test, discard if worthless, keep if functional, evolve like an animal in an environment? or are
3// there pieces the LLM adds, or only on edge cases?" This gate DECOMPOSES the LLM's proposer role and shows,
4// MEASURED, which pieces the evolve-test-select loop already covers WITHOUT an LLM, and the ONE piece it doesn't.
5//
6// The LLM-as-proposer = (a) a PRIOR over plausible candidates + (b) COMPOSITION (turn parents into a NEW valid
7// candidate) + (c) TRANSLATION of unstructured knowledge into a NEW primitive (grammar expansion). The honest map:
8// (a) PRIOR -> a SEARCH ENGINE provides it (retrieve human knowledge -> narrow the space). T4.
9// (b) COMPOSITION -> a GRAMMAR + mechanical MUTATION makes new VALID candidates. T1-T3, no LLM.
10// TEST/SELECT -> a deterministic evaluator (FunSearch already does this WITHOUT the LLM).
11// (c) TRANSLATION -> turning retrieved knowledge into a NEW grammar primitive = the piece evolution CANNOT do
12// (mutation explores WITHIN the grammar; it cannot INVENT a construct outside it). T5 proves it.
13// FOUND THE HARD WAY: naive greedy single-gene evolution got STUCK in a local optimum; escaping it needed multi-gene
14// mutation + random restart (iterated local search) = classical EA mechanics, NOT an LLM.
15// T1 EVOLVE-TEST-SELECT solves a target with NO LLM, NO exhaustive enumeration (mutation + environment selection).
16// T2 MEASURED: evolution finds it in FAR fewer evaluations than blind random search (selection/environment works).
17// T3 the evolved program GENERALIZES on held-out (it's a real solution, not memorized).
18// T4 ENRICHMENT: a RETRIEVED prior that NARROWS the space (search-engine proxy) makes evolution far cheaper.
19// T5 THE ONE LLM PIECE: an OUT-OF-GRAMMAR target (x^4 vs a cubic-only construct) is UNREACHABLE -> grammar EXPANSION.
20// expect_exit: 0 license_tier: ORIGINAL
21import "nx_ncf_synth.nx"
22import "nx_syscalls.nx"
23
24func lcg_next(st: *i64) -> i64 { st[0]=((1103515245*st[0])+12345)&2147483647; return st[0] }
25func rand_gene(st: *i64, lo: i64, hi: i64) -> i64 { return lo+(lcg_next(st)%((hi-lo)+1)) }
26
27// genome = [init,c2,c1,c0] for the quadratic-index loop (a real PROGRAM via ncf_loop_eval3 -> a cubic).
28// fitness = total absolute error vs the target examples (0=solved). Convex but L1 -> single-coordinate greedy can stick.
29func g_error(g: *i64, xs: *i64, ys: *i64, n: i64) -> i64 {
30 var e: i64=0; var i: i64=0
31 while i<n { var d: i64=ncf_loop_eval3(g[0],g[1],g[2],g[3],xs[i])-ys[i]; if d<0 { d=0-d } e=e+d; i=i+1 }
32 return e
33}
34// ITERATED LOCAL SEARCH (a robust EA, no LLM): hill-climb, mutation mostly 1-gene + occasionally 2-gene (escape
35// coordinate-local-minima), RANDOM RESTART on stagnation (escape any basin). lo/hi = the prior range (enrichment
36// narrows it). "Evolve like an animal": mutate, the environment (the test) discards worthless / keeps functional.
37func evolve(xs: *i64, ys: *i64, n: i64, seed: i64, lo: i64, hi: i64, evalbox: *i64, best: *i64) -> i64 {
38 let st: *i64=sys_mmap(16) as *i64; st[0]=seed
39 let parent: *i64=sys_mmap(64) as *i64
40 let child: *i64=sys_mmap(64) as *i64
41 let bestever: *i64=sys_mmap(64) as *i64
42 var gi: i64=0; while gi<4 { parent[gi]=rand_gene(st,lo,hi); gi=gi+1 }
43 var perr: i64=g_error(parent,xs,ys,n); evalbox[0]=evalbox[0]+1
44 var bererr: i64=perr; var zz: i64=0; while zz<4 { bestever[zz]=parent[zz]; zz=zz+1 }
45 var stag: i64=0; var stop: i64=0
46 while stop==0 {
47 var l: i64=0
48 while l<16 {
49 var c: i64=0; while c<4 { child[c]=parent[c]; c=c+1 }
50 child[lcg_next(st)%4]=rand_gene(st,lo,hi) // always 1 gene
51 if (lcg_next(st)%3)==0 { child[lcg_next(st)%4]=rand_gene(st,lo,hi) } // sometimes a 2nd (escape traps)
52 let ce: i64=g_error(child,xs,ys,n); evalbox[0]=evalbox[0]+1
53 if ce<perr { var c2: i64=0; while c2<4 { parent[c2]=child[c2]; c2=c2+1 } perr=ce } // keep if functional
54 if ce==0 { l=16 } else { l=l+1 }
55 }
56 if perr<bererr { bererr=perr; var b2: i64=0; while b2<4 { bestever[b2]=parent[b2]; b2=b2+1 } stag=0 } else { stag=stag+1 }
57 if stag>50 { var r: i64=0; while r<4 { parent[r]=rand_gene(st,lo,hi); r=r+1 } perr=g_error(parent,xs,ys,n); evalbox[0]=evalbox[0]+1; stag=0 }
58 if bererr==0 { stop=1 }
59 if evalbox[0]>=200000 { stop=1 }
60 }
61 var b: i64=0; while b<4 { best[b]=bestever[b]; b=b+1 }
62 if bererr==0 { return 1 }
63 return 0
64}
65// blind random search (no selection) over the same range -- the baseline.
66func random_search(xs: *i64, ys: *i64, n: i64, seed: i64, lo: i64, hi: i64, budget: i64, evalbox: *i64) -> i64 {
67 let st: *i64=sys_mmap(16) as *i64; st[0]=seed
68 let g: *i64=sys_mmap(64) as *i64
69 var tries: i64=0
70 while tries<budget {
71 var gi: i64=0; while gi<4 { g[gi]=rand_gene(st,lo,hi); gi=gi+1 }
72 evalbox[0]=evalbox[0]+1
73 if g_error(g,xs,ys,n)==0 { return 1 }
74 tries=tries+1
75 }
76 return 0
77}
78
79func main() -> i64 {
80 ncf_w("=== nx_evo_synth: evolve-test-select (no LLM) -- which pieces of the LLM proposer does it cover, and which not? ===\n" as *u8)
81 var pass: i64=0; var total: i64=0
82
83 // TARGET = x^3 (representable by the cubic-producing quadratic-index loop). train x=0..4, held {5->125, 6->216}.
84 let xs: *i64=sys_mmap(64) as *i64; let ys: *i64=sys_mmap(64) as *i64
85 xs[0]=0; xs[1]=1; xs[2]=2; xs[3]=3; xs[4]=4
86 ys[0]=0; ys[1]=1; ys[2]=8; ys[3]=27; ys[4]=64
87 let n: i64=5
88
89 // evolution (cold prior: coefficients only known to be in [-12,12]).
90 let ev_box: *i64=sys_mmap(16) as *i64; ev_box[0]=0
91 let best: *i64=sys_mmap(64) as *i64
92 let solved_evo: i64=evolve(xs,ys,n,12345,0-12,12,ev_box,best)
93 let evals_evo: i64=ev_box[0]
94 // blind random search baseline (same range).
95 let rb_box: *i64=sys_mmap(16) as *i64; rb_box[0]=0
96 let solved_rand: i64=random_search(xs,ys,n,999,0-12,12,200000,rb_box)
97 let evals_rand: i64=rb_box[0]
98
99 // T1: evolve-test-select SOLVES it, no LLM, no exhaustive enumeration.
100 total=total+1; if solved_evo==1 { pass=pass+1; ncf_w(" [PASS] " as *u8) } else { ncf_w(" [FAIL] " as *u8) }
101 ncf_w("T1 EVOLVE-TEST-SELECT: solved x^3 = " as *u8); ncf_n(solved_evo); ncf_w(" via mutation+selection, NO LLM, NO exhaustive enum (genome=[" as *u8); var q: i64=0; while q<4 { ncf_n(best[q]); if q<3 { ncf_w("," as *u8) } q=q+1 } ncf_w("])\n" as *u8)
102
103 // T2: MEASURED -- evolution << blind random search.
104 total=total+1; if solved_evo==1 { if evals_evo<evals_rand { pass=pass+1; ncf_w(" [PASS] " as *u8) } else { ncf_w(" [FAIL] " as *u8) } } else { ncf_w(" [FAIL] " as *u8) }
105 ncf_w("T2 MEASURED: evolution evals=" as *u8); ncf_n(evals_evo); ncf_w(" vs blind random evals=" as *u8); ncf_n(evals_rand); ncf_w(" (random solved=" as *u8); ncf_n(solved_rand); ncf_w(") -> selection/environment works, no LLM\n" as *u8)
106
107 // T3: the evolved program GENERALIZES on held-out.
108 let h5: i64=ncf_loop_eval3(best[0],best[1],best[2],best[3],5)
109 let h6: i64=ncf_loop_eval3(best[0],best[1],best[2],best[3],6)
110 total=total+1; if h5==125 { if h6==216 { pass=pass+1; ncf_w(" [PASS] " as *u8) } else { ncf_w(" [FAIL] " as *u8) } } else { ncf_w(" [FAIL] " as *u8) }
111 ncf_w("T3 GENERALIZES: evolved program on HELD-OUT x=5->" as *u8); ncf_n(h5); ncf_w(" (125), x=6->" as *u8); ncf_n(h6); ncf_w(" (216) -- a real solution\n" as *u8)
112
113 // T4: ENRICHMENT -- a RETRIEVED prior narrows the coefficient range to [-3,3] (search-engine-style: "the coeffs are small").
114 let en_box: *i64=sys_mmap(16) as *i64; en_box[0]=0
115 let best2: *i64=sys_mmap(64) as *i64
116 let solved_en: i64=evolve(xs,ys,n,12345,0-3,3,en_box,best2)
117 let evals_en: i64=en_box[0]
118 total=total+1; if solved_en==1 { if evals_en<evals_evo { pass=pass+1; ncf_w(" [PASS] " as *u8) } else { ncf_w(" [FAIL] " as *u8) } } else { ncf_w(" [FAIL] " as *u8) }
119 ncf_w("T4 ENRICHMENT: a RETRIEVED prior narrowing the space [-3,3] -> evals=" as *u8); ncf_n(evals_en); ncf_w(" vs cold [-12,12] " as *u8); ncf_n(evals_evo); ncf_w(" = a search engine's prior ACCELERATES evolution (no LLM)\n" as *u8)
120
121 // T5: THE ONE LLM PIECE -- an OUT-OF-GRAMMAR target (x^4) is UNREACHABLE: mutation explores WITHIN the grammar.
122 let yq: *i64=sys_mmap(64) as *i64; yq[0]=0; yq[1]=1; yq[2]=16; yq[3]=81; yq[4]=256
123 let q_box: *i64=sys_mmap(16) as *i64; q_box[0]=0
124 let bq: *i64=sys_mmap(64) as *i64
125 let solved_q: i64=evolve(xs,yq,n,12345,0-12,12,q_box,bq)
126 total=total+1; if solved_q==0 { pass=pass+1; ncf_w(" [PASS] " as *u8) } else { ncf_w(" [FAIL] " as *u8) }
127 ncf_w("T5 THE LLM PIECE: x^4 is OUT of the (cubic) grammar -> evolution CANNOT reach it (solved=" as *u8); ncf_n(solved_q); ncf_w(") = grammar EXPANSION (translate knowledge -> a NEW primitive) is the one piece evolution can't do\n" as *u8)
128
129 ncf_w("\n THE HONEST ANSWER (operator's question): YES -- search-engine enrichment + evolve + test-discard-keep works WITHOUT an LLM\n" as *u8)
130 ncf_w(" for everything EXCEPT inventing NEW primitives. Decomposed: PRIOR -> a search engine gives it (T4, better: current+verifiable);\n" as *u8)
131 ncf_w(" COMPOSITION -> a grammar + mutation (T1-T3); TEST/SELECT -> a deterministic evaluator (already non-LLM). The ONE remaining\n" as *u8)
132 ncf_w(" LLM piece = TRANSLATION of unstructured knowledge into a NEW grammar primitive (T5: x^4 unreachable within a cubic grammar).\n" as *u8)
133 ncf_w(" That is NOT just edge cases -- it is grammar-EXPANSION -- but it IS replaceable: a search engine RETRIEVES the knowledge, and a\n" as *u8)
134 ncf_w(" self-reliant MINER + the X-AUT-NCF-001 keystone (constructs as DATA) turns it into a new primitive. = the real path past FunSearch.\n" as *u8)
135 ncf_w(" (FOUND THE HARD WAY: naive greedy single-gene evolution got STUCK in a local optimum; escaping it needed multi-gene mutation +\n" as *u8)
136 ncf_w(" random restart (iterated local search) = classical EA mechanics, NOT an LLM. The 'smart proposer' edge on rugged landscapes is\n" as *u8)
137 ncf_w(" REAL, but it is bought by EA mechanics or by enrichment -- not uniquely by an LLM.)\n" as *u8)
138 ncf_w("EVO-SYNTH verdict=" as *u8)
139 if pass==total { ncf_w("GREEN passes=" as *u8); ncf_n(pass); ncf_w("/" as *u8); ncf_n(total); ncf_w(" -- evolve-test-select replaces the LLM proposer EXCEPT grammar-expansion (measured)\n" as *u8); sys_exit(0); return 0 }
140 ncf_w("RED passes=" as *u8); ncf_n(pass); ncf_w("/" as *u8); ncf_n(total); ncf_w("\n" as *u8); sys_exit(1); return 1
141}