Subcritical Preferential Sparse Attention
Implementation & benchmark of arXiv:2607.00731 — Sharp Asymptotics for the Largest Component in the Subcritical Regime of Preferential Attachment Without Vertex Growth
Source paper: Sharp Asymptotics for the Largest Component in the Subcritical Regime of Preferential Attachment Without Vertex Growth arXiv:2607.00731 ⓘ · analyzed Aug 30, 2026
AI-generated research hypothesis, automatically tested. Not peer-reviewed.
Idea description
Construct a sparse attention or message-passing mask by sampling edges with preferential weights (d_u+alpha)(d_v+alpha), while keeping the edge count below the predicted connectivity threshold. This creates hub-like local communication patterns but prevents one giant component from forcing dense information mixing, reducing attention cost and potentially mitigating oversmoothing.
Formulas
Mathematical statement
The paper defines a graph process on a fixed vertex set [n], initially with no edges, where a non-edge {v,w} is selected with probability proportional to (d_v+alpha)(d_w+alpha). Here d_v and d_w are current degrees and alpha>0 is the baseline attractiveness. The critical edge count is m_c=alpha n/[2(alpha+1)]. In the subcritical regime m=m_c(1-epsilon), with epsilon tending to zero and epsilon^3 n tending to infinity, the largest connected component L_1 satisfies L_1=(1+o_p(1)) [2(alpha+2)/(alpha+1)] epsilon^{-2} log(epsilon^3 n). The notation o_p(1) means convergence to zero in probability. The edge-selection denominator is Z_m=sum_{ {x,y} not in E(G)} (d_x+alpha)(d_y+alpha). We use the explicit component-size asymptotic as an engineering design rule: choose epsilon and therefore m so that the predicted maximum receptive-field component is below a prescribed budget B.
Implementation notes
(1) Integration point: replace dense self-attention or a fully connected GNN adjacency with a sparse binary mask A. The mask is generated once per sequence length, or regenerated per batch, and is applied before attention softmax by setting logits S_ij to negative infinity whenever A_ij=0. For a GNN, aggregate only over selected neighbors. Add self-loops and optionally a small number of global tokens.
(2) Pseudocode: initialize d_i=0 and E=empty. Choose alpha>0 and m<m_c=alpha*n/(2*(alpha+1)). For t from 1 to m, enumerate or approximate absent pairs (i,j), compute w_ij=(d_i+alpha)*(d_j+alpha), sample one pair with probability w_ij/Z, add it to E, and increment d_i and d_j. Symmetrize A and execute attention only on edges in E.
(3) Compute m_c, epsilon=1-m/m_c, and the predicted component scale from the paper. Estimate actual connected components with union-find, realized largest-component size, FLOPs, memory, latency, and representation similarity. For large n, approximate pair sampling with degree-proportional candidate generation plus rejection of existing edges.
(4) First experiment: train a 12-layer, 8-head vision Transformer on CIFAR-10 with 196 image patches. Compare dense, uniform-random sparse, and preferential subcritical masks at equal edge counts, testing m/m_c in {0.5,0.7,0.85,0.95}, with and without two global tokens. Measure memory, latency, accuracy, realized largest component, and cosine similarity of final patch representations. Success is at least 2x lower attention memory or latency at comparable accuracy, with no giant component and empirical component sizes tracking the predicted scale.
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.