Unverified 2026

Percolation-guided reinforced sparse attention

Implementation & benchmark of arXiv:2608.17073 — Near-critical percolation with sparse reinforcements

Usefulness5/10

Difficulty5/10

Novelty6/10

Architecture Speedup Scalability Stability Attention Transformer Inference speedup Probability Stochastic processes Combinatorics Graph theory

Source paper: Near-critical percolation with sparse reinforcements arXiv:2608.17073 ⓘ · analyzed Sep 1, 2026

AI-generated research hypothesis, automatically tested. Not peer-reviewed.

Idea description

Replace dense token-to-token attention on a 2D token grid with local attention plus sparse horizontal and vertical communication axes. Tokens at intersections of selected axes receive extra cross-axis attention edges, creating a reinforced sparse graph that can transmit information across large blocks while using far fewer edges than dense attention. The mask should use light-tailed, approximately geometric spacing in both directions rather than heavy-tailed spacing in one direction.

Formulas

$$\mathbb{P}_{p}(\mathcal{H}_{L})\geq 1-\tfrac{1}{16}\sigma \quad\Longrightarrow\quad \mathbb{P}_{p}(\mathcal{H}_{2^{m}L})\geq 1-\tfrac{1}{16}\sigma^{2^{m}},\qquad m\geq 1.$$

$$\mathbb{P}_{p}(\mathcal{V}_{L})\geq 1-\tfrac{1}{16}\sigma \quad\Longrightarrow\quad \mathbb{P}_{p}(\mathcal{V}_{2^{m}L})\geq 1-\tfrac{1}{16}\sigma^{2^{m}}.$$

$$L_k=2^kL_0,\qquad \frac{1}{\alpha}<\beta<\frac{1}{c_1c_2}.$$

$$\widehat{P}_{\mathrm{cross}}(2^mL)\;\geq\;1-\frac{1}{16}\left(1-\widehat{P}_{\mathrm{cross}}(L)\right)^{2^m}.$$

Mathematical statement

The paper studies Bernoulli site percolation with ordinary opening probability q and a larger opening probability p at intersections of randomly selected horizontal and vertical lines. The relevant multiscale result is Lemma 7: if the horizontal crossing event H_L of an L-by-L box satisfies P_p(H_L) >= 1 - sigma/16 for sigma < 1, then for every integer m >= 1, P_p(H_{2^m L}) >= 1 - sigma^(2^m)/16; the same holds for the vertical crossing event V_L. Here H_L means existence of an open left-to-right crossing of the box, V_L means an open bottom-to-top crossing, p is the effective local occupancy probability, and sigma measures the initial crossing failure probability. The construction in the proof uses dyadic scales L_k = 2^k L_0 and chooses beta such that 1/alpha < beta < 1/(c_1 c_2), where alpha is a spacing-tail exponent and c_1,c_2 are constants controlling the environment and crossing estimates. We use the mathematical principle that a sufficiently reliable crossing at a base scale compounds into exponentially smaller failure probability at larger scales, while the spacing distribution must be sufficiently regular in both axes.

Implementation notes

Integrate this into a 2D vision transformer or any transformer whose sequence can be reshaped into an H-by-W grid. At each layer, replace dense attention by (i) fixed-radius local window attention, (ii) axial attention along a small number of selected horizontal and vertical lines, and (iii) extra attention edges at every horizontal/vertical line intersection. Sample line gaps independently from geometric distributions with means g_x and g_y, or deterministically use geometric quantiles; avoid Pareto-like gaps. Let q be the fraction of ordinary local edges retained and p be the fraction of reinforced intersection edges retained. Construct a binary mask once per layer or once per training example, then apply standard scaled dot-product attention only on permitted edges. Pseudocode: sample horizontal line set X and vertical line set Y; set M[i,j]=1 for local neighbors; for x in X set M[x,j]=1 along the horizontal axis, and for y in Y set M[i,y]=1 along the vertical axis; at every intersection (x,y), retain the reinforced cross-axis edges; run masked attention. Divide the grid into L-by-L blocks and estimate crossing success by BFS on the binary mask: p_cross(L) equals the number of blocks containing a left-right or bottom-top path divided by the number sampled. Set sigma_hat=1-p_cross(L0), and monitor the paper-inspired forecast 1-sigma_hat^(2^m)/16 at larger dyadic scales; treat this as a diagnostic rather than an exact theorem for learned attention weights. First test on CIFAR-10 or ImageNet-100 with a ViT-Tiny baseline, matching parameter count and FLOPs against window attention and axial attention. Measure validation accuracy, attention FLOPs, the fraction of token pairs connected by paths through 4, 8, and 16 layers, and gradient influence across opposite image corners. Success means at least 30% lower attention FLOPs with no more than 0.5 percentage-point accuracy loss, rapidly increasing multiscale crossing probability, and no isolated token components.

Verification

This idea has not been verified yet.

Verification happens in two stages: Stage 1 — a mechanism check on a toy system confirms the claimed mathematical phenomenon reproduces; Stage 2 — a benchmark implements the idea on a real (small) neural network task and compares it against a tuned baseline over 8 paired seeds with a permutation test.

Artifacts

Artifacts unavailable.