nx_vec_nsw_gate.nx source

1// nx_vec_nsw_gate.nx -- KAT for R-VEC-3 (nx_vec_nsw): the NSW graph search returns the TRUE nearest neighbor 2// (recall@1 = brute force) even when the search STARTS FAR from the answer -- that is the ef-beam working. 3// 8 vectors spread by angle; cosine = nearness. expect_exit: 0 license_tier: ORIGINAL 4import "nx_syscalls.nx" 5import "nx_vec_kernel.nx" 6import "nx_vec_nsw.nx" 7 8func ng_puts(s: *u8) -> i64 { var n: i64=0; while s[n]!=(0 as u8){n=n+1} sys_write(1,s,n); return 0 } 9func ng_pn(v: i64) -> i64 { let bb: *u8=sys_mmap(28); var m: i64=v; if m<0{m=0-m;sys_write(1,"-" as *u8,1)}; let t: *u8=sys_mmap(28); var k: i64=0; if m==0{t[0]=(48 as u8);k=1}; while m>0{t[k]=((48+(m%10)) as u8);m=m/10;k=k+1}; var i: i64=0; while i<k{bb[i]=t[k-1-i];i=i+1}; sys_write(1,bb,k); return 0 } 10func ng_w(fd: i64, s: *u8) -> i64 { var n: i64=0; while s[n]!=(0 as u8){n=n+1} sys_write(fd,s,n); return 0 } 11func ng_wn(fd: i64, v: i64) -> i64 { let bb: *u8=sys_mmap(28); var m: i64=v; if m<0{m=0-m}; let t: *u8=sys_mmap(28); var k: i64=0; if m==0{t[0]=(48 as u8);k=1}; while m>0{t[k]=((48+(m%10)) as u8);m=m/10;k=k+1}; var i: i64=0; while i<k{bb[i]=t[k-1-i];i=i+1}; sys_write(fd,bb,k); return 0 } 12 13// brute-force nearest (max cosine) over all N 14func brute_nn(V: *i64, N: i64, D: i64, query: *i64) -> i64 { 15 var best: i64=0; var bc: i64=0-2000000; var i: i64=0 16 while i<N { let vi: *i64=((V as i64)+i*D*8) as *i64; let c: i64=vr_cos_milli(query, vi, D); if c>bc { bc=c; best=i } i=i+1 } 17 return best 18} 19func setv(V: *i64, idx: i64, x: i64, y: i64) -> i64 { V[idx*2]=x; V[idx*2+1]=y; return 0 } 20 21func main() -> i64 { 22 ng_puts("=== R-VEC-3 NSW ANN INDEX -- graph search returns the true NN (recall@1 vs brute force) ===\n" as *u8) 23 let N: i64=8; let D: i64=2; let M: i64=3; let MMAX: i64=6; let ef: i64=4 24 let V: *i64=sys_mmap(8*N*D) as *i64 25 setv(V,0,10,0); setv(V,1,9,4); setv(V,2,7,7); setv(V,3,4,9); setv(V,4,0,10); setv(V,5,0-4,9); setv(V,6,0-7,7); setv(V,7,0-9,4) 26 let adj: *i64=sys_mmap(8*N*MMAX) as *i64 27 let deg: *i64=sys_mmap(8*N) as *i64 28 vr_nsw_build(V, N, D, M, MMAX, adj, deg) 29 30 // navigability: every node has >=1 neighbor 31 var connected: i64=1; var i: i64=0 32 while i<N { if deg[i]<1 { connected=0 } i=i+1 } 33 34 let visited: *i64=sys_mmap(8*N) as *i64 35 let rid: *i64=sys_mmap(8*ef) as *i64; let rco: *i64=sys_mmap(8*ef) as *i64; let rex: *i64=sys_mmap(8*ef) as *i64 36 let Q: *i64=sys_mmap(8*2) as *i64 37 38 var pass: i64=0; var total: i64=0 39 // entry = node 0 (angle 0); queries are spread far from it on purpose 40 // q1 ~32deg -> v1 ; q2 ~84deg -> v4 (FAR from entry) ; q3 ~148deg -> v7 (FAR) ; q4 ~49deg -> v2 41 Q[0]=8; Q[1]=5; let a1: i64=vr_nsw_search(V,N,D,Q,0,ef,MMAX,adj,deg,visited,rid,rco,rex); let b1: i64=brute_nn(V,N,D,Q) 42 total=total+1; ng_puts(" q(8,5) nsw=v" as *u8); ng_pn(a1); ng_puts(" brute=v" as *u8); ng_pn(b1); ng_puts(" " as *u8); if a1==b1 { pass=pass+1; ng_puts("PASS\n" as *u8) } else { ng_puts("FAIL\n" as *u8) } 43 Q[0]=1; Q[1]=10; let a2: i64=vr_nsw_search(V,N,D,Q,0,ef,MMAX,adj,deg,visited,rid,rco,rex); let b2: i64=brute_nn(V,N,D,Q) 44 total=total+1; ng_puts(" q(1,10) nsw=v" as *u8); ng_pn(a2); ng_puts(" brute=v" as *u8); ng_pn(b2); ng_puts(" (far from entry) " as *u8); if a2==b2 { pass=pass+1; ng_puts("PASS\n" as *u8) } else { ng_puts("FAIL\n" as *u8) } 45 Q[0]=0-8; Q[1]=5; let a3: i64=vr_nsw_search(V,N,D,Q,0,ef,MMAX,adj,deg,visited,rid,rco,rex); let b3: i64=brute_nn(V,N,D,Q) 46 total=total+1; ng_puts(" q(-8,5) nsw=v" as *u8); ng_pn(a3); ng_puts(" brute=v" as *u8); ng_pn(b3); ng_puts(" (far from entry) " as *u8); if a3==b3 { pass=pass+1; ng_puts("PASS\n" as *u8) } else { ng_puts("FAIL\n" as *u8) } 47 Q[0]=7; Q[1]=8; let a4: i64=vr_nsw_search(V,N,D,Q,0,ef,MMAX,adj,deg,visited,rid,rco,rex); let b4: i64=brute_nn(V,N,D,Q) 48 total=total+1; ng_puts(" q(7,8) nsw=v" as *u8); ng_pn(a4); ng_puts(" brute=v" as *u8); ng_pn(b4); ng_puts(" " as *u8); if a4==b4 { pass=pass+1; ng_puts("PASS\n" as *u8) } else { ng_puts("FAIL\n" as *u8) } 49 total=total+1; ng_puts(" graph navigable (every node has a neighbor) " as *u8); if connected==1 { pass=pass+1; ng_puts("PASS\n" as *u8) } else { ng_puts("FAIL\n" as *u8) } 50 51 ng_puts("----\nNSW gate " as *u8); ng_pn(pass); ng_puts("/" as *u8); ng_pn(total); ng_puts(" passed\n" as *u8) 52 ng_puts("HONEST: single-layer NSW + ef-beam (recall@1 = brute force here, incl. queries far from the entry =\n" as *u8) 53 ng_puts(" the beam escaping local optima). Hierarchical layers = the HNSW extension; sub-linear because\n" as *u8) 54 ng_puts(" search walks graph neighborhoods, not all N. Reuses R-VEC-0 vr_cos_milli.\n" as *u8) 55 let lg: i64=sys_openat_append("knowledge/status/nsw_gate.log" as *u8, 0x1a4) 56 if lg>=0 { ng_w(lg, "R-VEC-3 nsw gate pass=" as *u8); ng_wn(lg, pass); ng_w(lg, "/" as *u8); ng_wn(lg, total); if pass==total { ng_w(lg, " GREEN\n" as *u8) } else { ng_w(lg, " RED\n" as *u8) } sys_close(lg) } 57 if pass==total { ng_puts("R-VEC-3 GREEN (sovereign NSW ANN graph index proven)\n" as *u8); sys_exit(0); return 0 } 58 ng_puts("R-VEC-3 RED\n" as *u8); sys_exit(1); return 1 59}