code wiki / (root) / nx_flash_byte_exact_gate.nx

nx_flash_byte_exact_gate.nx

buildroot/runtime/nx_flash_byte_exact_gate.nx

8418 B210 linesdepth 3pulls 3 transitivereach 0 importersview sourcekind gate/prooftopic flash
docsdependenciesstructsconstsfunctions

about

nx_flash_byte_exact_gate.nx -- TWO-PASS BYTE-EXACT flash attention: the determinism+memory exceed. The team's one-pass online-softmax flash (nx_flash_attention) is memory-efficient but only EPS-matches naive (eps_q10=100) because the online rescale `acc*exp(m_old-m_new)/SCALE` ROUNDS in fixed-point. This rung proves a TWO-PASS flash -- pass-1 finds the GLOBAL row-max, pass-2 recomputes exp(s-gmax) and accumulates EXACTLY (no rescale) -- is BYTE-EXACT == naive AND block-size-INVARIANT (any tile size -> identical output), while keeping O(block) score memory (not O(n^2)). = byte-exact AND memory-efficient attention -- the combination float FlashAttention CANNOT do (its parallel float reductions are non-deterministic). criteria: 1 two-pass(block=2) == naive BYTE-EXACT (0 mismatches) 2 two-pass(block=1) == naive BYTE-EXACT 3 two-pass(block=4=full) == naive BYTE-EXACT (=> block-size-INVARIANT = the determinism exceed) 4 output is the known non-trivial answer [[17,1],[21,2]] (real attention, not all-zeros) 5 memory win: two-pass score scratch (block) < naive score scratch (n_kv) at byte-exactness expect_exit: 0 license_tier: ORIGINAL

dependencies 2 imports · 0 importers

nx_syscalls.nx nx_gate_verdict.nx nx_flash_byte_exact_gate.nx

imports: nx_syscalls.nxnx_gate_verdict.nx

imported by: nobody (leaf or entry point)

call flow from main pre-order; caps 40 nodes / depth 6 declared; ↻ = already shown

main dp sys_write sys_mmap naive_attn sys_mmap ↻ dot eq twopass_attn dot ↻ sys_mmap ↻ eq ↻ printw dp ↻ dn sys_mmap ↻ sys_write ↻ chk dp ↻ weq dn ↻ gv_ctr sys_mmap ↻ gv_verdict gv_puts sys_write ↻ gv_num sys_mmap ↻ sys_write ↻ sys_munmap gv_journal sys_openat_append sys_mmap ↻ gv_catn sys_mmap ↻ sys_munmap ↻ sys_now_realtime_sec sys_mmap ↻ sys_clock_gettime_real gv_cat

structs

none

consts

18const SCALE: i64 = 1000

functions

20func dp(s: *u8) -> i64 { var n: i64 = 0; while s[n] != (0 as u8) { n = n + 1 } sys_write(1, s, n); return 0 }
called by 3: chkprintwmain calls 1: sys_write
21func dn(v: i64) -> i64
called by 2: printwmain calls 2: sys_mmapsys_write
31func chk(name: *u8, ok: i64) -> i64
called by 1: main calls 1: dp
35func printw(label: *u8, w: *i64, n: i64) -> i64
called by 1: main calls 2: dpdn
42func eq(x: i64) -> i64
56func dot(a: *i64, b: *i64, d: i64) -> i64
64func naive_attn(Q: *i64, K: *i64, V: *i64, nq: i64, nkv: i64, d: i64, out: *i64) -> i64
called by 1: main calls 3: sys_mmapdoteq
99func twopass_attn(Q: *i64, K: *i64, V: *i64, nq: i64, nkv: i64, d: i64, bs: i64, out: *i64) -> i64
called by 1: main calls 3: dotsys_mmapeq
145func weq(a: *i64, b: *i64, n: i64) -> i64
called by 1: main
152func main() -> i64