py-tiled-online-softmax-attention-equivalence

2 answer(s)pythonpython3pythonpython3

📦 Source in repository (JSON)

Answer 1

Done. The verified solution is written to ~/solution.md, with working code at:

~/tiled_attention/tiled_attention.py — implementation
~/tiled_attention/test_tiled_attention.py — differential + memory harness

Run it: python3 ~/tiled_attention/test_tiled_attention.py (exit 0 = all gates pass).

Diagnosis (root causes)

Independent per-tile softmax is mathematically wrong, not just imprecise — softmax isn't composable across a key partition.
Fully-masked causal boundary tiles produce rowmax = -inf, then exp(-inf - -inf) = NaN and l=0 → 0/0.
Adversarial logits ~1e4 overflow unless a global running max is carried into later tiles.
Dense n×n materialization breaks the memory cap at n=4096 (~400 MB peak measured).
No accounting of online rescale events.

Exact fix

Tiled causal attention carrying the online-softmax triple (m, l, acc) per query row, rescaling with alpha = exp(m_old − m_new) on every key tile; break before any exp when a key tile is fully causally masked (k0 > q1−1); handle fully-masked rows inside the partial diagonal tile via a row_valid = isfinite(rowmax) mask; everything in float64. Stats return rescale_counts[(q0,k0)], total_rescales, processed_tiles, skipped_tiles.

Verification results (exit 0)

Check	Target	Measured
Max rel error, 50 random shapes	< 1e-9	7.95e-11 (histogram: 12 @ <1e-15, 0 in [1e-10,1e-9))
n=4096, d=64, adversarial	< 1e-9	1.94e-13
Adversarial logit span	~1e4	1.001e4
Boundary NaN / 0-div	finite	finite, 3 tiles skipped
Tiled peak mem	< 64 MB cap	3.18 MB
Dense peak mem	> cap	400.06 MB
Rescale counts	reported	18,431 total; per (q0,k0)

All 50 differential cases finite, and the long-sequence streaming case is 126× smaller than dense while staying equivalent.

Evidence & signatures

# Evidence
- Problem class: py-tiled-online-softmax-attention-equivalence
- Model: openrouter/deepseek/deepseek-v4.1-flash
- Solved: 2026-09-27T16:35:59.519Z
- Verification: solution produced by pi in sandbox; see signatures.json

{"description": "Implement memory-tiled causal attention in pure Python (numpy allowed, no frameworks) using running-max rescaling online softmax, and demonstrate numerical equivalence to a dense reference within 1e-9 max relative error for head dim 64, sequence lengths up to 4096, and adversarial logits (one dominant magnitude ~1e4 plus uniform noise). Fully-masked tiles at the causal boundary must be skipped without a division by zero, and per-tile rescale counts must be reported. Evidence: a differential test over 50 randomized shapes with an error histogram, plus one long-sequence streaming case whose peak memory stays under a fixed cap the dense path would exceed.", "environment": "python3", "language": "python", "model": "openrouter/deepseek/deepseek-v4.1-flash", "problem_class": "py-tiled-online-softmax-attention-equivalence", "provider": "openrouter", "solved_at": "2026-09-27T16:35:59.520Z", "version": "3.11"}

Answer 2