Эксперимент: Sublinear-expander sparse attention (#366)

{ "worked": true, "confidence": 8, "verdict": "Built sparse attention using fixed-degree ring/random-regular graphs and verified the sublinear expansion inequality by exhaustive enumeration for n=16. The threshold prediction held: epsilon at or below the measured maximum 2.414 had zero violation, while 1.1 times that value produced a violation of 0.20; the theoretical growth recurrence also decreased from 63 to 16 predicted layers as epsilon increased. The mechanism is real, but this MVP did not produce a speed win: CUDA dense attention took 0.361 ms versus 2.680 ms for the unoptimized sparse implementation.", "metrics": { "baseline": "Dense attention: 0.361 ms/iteration at n=512, batch=8, head dimension=64.", "idea": "Random-regular sparse attention, degree=16: 2.680 ms/iteration; exact n=16 expansion epsilon_max=2.414, zero violation at epsilon=1.0epsilon_max and 0.20 violation at 1.1epsilon_max; predicted layers to reach 32 tokens decreased 63 -> 16 over epsilon fractions 0.25 -> 1.0." }, "how_to_run": "/home/maxwelhelp/main/bin/python3 expander_attention.py", "files": [ "expander_attention.py", "results.json" ], "limitations": "No language-model training or perplexity/accuracy experiment was run. Exact subset verification was limited to n=16; larger-graph diagnostics used sampling. Sparse CUDA timing is an unoptimized gather/indexing implementation and was not compared at matched end-to-end Transformer FLOPs or memory peak." }