Polylogarithmic Heavy-Tail Attention

1. Integration point: modify the attention connectivity pattern before computing $QK^T$. Given token coordinates $u_i\in\mathbb Z^d$ (sequence positions use $d=1$; image patches use $d=2$), do not form all pairwise logits. For each query token $i$, sample $k$ distinct keys $j$ from the normalized truncated kernel $p_{ij}$ above, then compute ordinary scaled dot-product attention only on those keys. Add a deterministic local window of radius $w$ so nearby interactions are always retained. Refresh the random long-range edges every training batch or every few layers; share edges across heads if memory is important. 2. Pseudocode: for layer in layers: for i in tokens: J_local=neighbors(i,w); J_long=sample_without_replacement(p[i,:],k); J=union(J_local,J_long); logits=(q[i] @ K[J].T)/sqrt(head_dim); a=softmax(logits); out[i]=a @ V[J]. The exponent is sampled using inverse-CDF or alias sampling; estimate normalization by precomputing distance-shell counts for regular grids, or by rejection sampling for irregular graphs. 3. The paper supplies the kernel and phase prediction; the neural implementation must empirically estimate effective receptive-field growth by measuring the fraction of tokens reachable from a seed after $t$ layers. Compare $\alpha\in\{0.5,1,1.5,2,3\}$, with the crossover expected around $\alpha=d$. 4. First experiment: train 6-layer small Transformers on WikiText-2 with sequence length 1024, comparing dense attention, a local-window baseline with equal $k+w$, and heavy-tail sparse attention at equal FLOPs and parameter count. Also test synthetic copy and induction tasks requiring dependencies at distances 128, 256, and 512. Success means lower validation perplexity than local attention at equal compute, or matching dense perplexity with at least 4x fewer attention score evaluations; additionally verify that reachable-token count grows substantially faster with depth for $\alpha<d$.