Subcritical Ancestral Attention
Implementation & benchmark of arXiv:2608.26259 — Cutoff with an $O(1)$ window for Potts Glauber Dynamics on lattice at High Temperature
Source paper: Cutoff with an $O(1)$ window for Potts Glauber Dynamics on lattice at High Temperature arXiv:2608.26259 ⓘ · analyzed Aug 29, 2026
AI-generated research hypothesis, automatically tested. Not peer-reviewed.
Idea description
Construct a sparse attention layer by sampling backward token histories as a continuous-time branching process rather than allowing every query to attend to every key. Each active ancestor either dies or branches into a bounded number of candidate ancestors, with branching probability controlled by a small parameter. The branch-out penalty predicts exponentially small probability of long, highly branching histories, providing a direct knob for receptive-field size and attention FLOPs.
Formulas
Mathematical statement
The paper defines u(s, heta,t):=\mathbb{E}[s^{N_t} heta^{J_t}], where N_t is the number of active particles at time t, J_t is the accumulated number of branch events, and s, heta\geq1 are moment parameters. A particle dies at rate 1-\alpha or branches at rate \alpha into 2d offspring. The short-time branching calculation gives u(s, heta,t+h)=(1-h)u(s, heta,t)+h[(1-\alpha)+\alpha heta u(s, heta,t)^{2d}]+o(h), hence \partial_tu=-u+(1-\alpha)+\alpha heta u^{2d}. The paper's branch-out penalty states that for \vartheta=C_{\mathrm{bp}}\alpha\leq1/2, \mathbb{P}(N_1>1,\ldots,N_{t-1}>1,N_t\geq1,J_t\geq k)\leq e^{1-\varepsilon}\vartheta^k e^{-2(1-\varepsilon)t}. Here C_{\mathrm{bp}} is a model-dependent constant and \varepsilon>0 is the slack in the geometric estimate. We use N_t as the number of candidate attention ancestors and J_t as a compute and dependency-growth budget.
Implementation notes
Integrate this into the attention-pattern construction before computing the usual QK^T logits. For each query token i, initialize one active history particle S={i} at layer L and run it backward for T routing steps. At each step and for every active particle, sample a branch event with probability alpha. If branching occurs, replace the particle by B candidate ancestors, using B=4 or 8 for hardware efficiency; otherwise retain one candidate with probability p_survive and kill the history otherwise. Candidate ancestors may be selected from a local sequence window, graph neighbors, or approximate retrieval. Deduplicate ancestors and cap the set at K_max; compute attention logits only between the query and the resulting set, then renormalize softmax over that set. Pseudocode: initialize S={i}, J=0; for t=1,...,T, create new_S; for j in S, sample branch~Bernoulli(alpha); if branch, add B candidates and increment J; otherwise add one candidate with probability p_survive; set S=unique(new_S); if |S|>K_max, retain the largest-logit candidates; use S as the sparse mask. Numerically integrate the ODE for u(s,theta,t) and choose the largest alpha whose predicted moment u remains below a memory target M. The paper-derived computation is the branching moment and tail estimate; candidate locations and truncation are empirical choices. First test a 6-layer Transformer on WikiText-2 against dense and fixed-window attention at equal wall-clock FLOPs. Record perplexity, average and 99th-percentile |S|, J, activation memory, and gradient variance. Success means at least 2x lower attention memory or FLOPs with no more than 1% perplexity degradation and a lighter tail of history sizes.
Verification
Stage 1 · Toy mechanism gate: Failed ✗
Stage 2 · Mechanism transferred to benchmark: Not tested
Stage 2 · Practical benchmark result: Not run
Methodology: Toy-system gate first; the benchmark stage runs only after a pass. How verification works
Stage 1 — Mechanism check agent confidence 9/10
Built a CPU MVP of subcritical ancestral attention, including RK4 integration of the branching moment ODE, exact Gillespie Monte Carlo verification, moment-target alpha selection, and dense/fixed-window/ancestral attention comparison. The core moment claim passed numerically with relative error 0.0002, and the process was subcritical, but ancestral attention collapsed to 2.00 average candidates and produced 0.7721 output MSE versus dense attention; the large sparsity gain therefore did not preserve attention behavior.
- Agent confidence
- 9/10
- Baseline
- Dense: 128.50 average causal candidates/query, pair ratio 1.000, output MSE 0, runtime 0.0457 s; fixed window: 30.06 average candidates, pair ratio 0.2339, output MSE 0.04834.
- Idea
- Ancestral: 2.00 average candidates/query, p99 7, maximum 13, pair ratio 0.01556 (about 64x fewer candidate pairs than dense), output MSE 0.7721, runtime 0.0411 s. Moment ODE 1.036015 versus Monte Carlo 1.035783, relative error 0.0002.
Limitations: This is a synthetic random-QKV attention study, not a language-model or WikiText-2 perplexity experiment. Candidate selection is a simple local backward sampler, Python-loop timing is not a reliable optimized sparse-kernel speed benchmark, and the paper's full branch-out tail event and model-dependent C_bp were not independently established.
How to run: python3 experiment.py
Verdict computed by deterministic test code from paired-seed statistics — not by the language model.
Artifacts
- experiment.py 6.6 KB View Raw
- report.md 1.5 KB View