# Critical power-law sparse attention

- ID: 762
- Canonical URL: https://synthcore.org/idea/762/critical-power-law-sparse-attention
- API JSON: https://synthcore.org/api/idea/762.json
- API Markdown: https://synthcore.org/api/idea/762.md
- Verification status: mechanism_failed
- Source: [arXiv:2607.11662](https://arxiv.org/abs/2607.11662)
- Category: architecture
- Solves: speedup, scalability, accuracy
- ML areas: attention, transformer, inference-speedup
- Math tags: probability, graph-theory, spectral-theory
- Ratings: usefulness 7/10; difficulty 4/10; novelty 6/10

## Idea description

Replace dense self-attention by a sparse mask on a one-dimensional or ordered token geometry, retaining local neighbors and adding long-range edges with probability proportional to distance raised to \(-(1+\sigma)\). Use \(\sigma\approx0.8\text{--}0.85\) as the initial regime because the paper finds that this range supports delocalized, GOE-like connectivity despite sparse bonds. The resulting layer has linear or near-linear attention cost while maintaining long-range paths.

## Mathematical statement

The paper's graph connects sites \(i,j\) on a one-dimensional ring independently with Bernoulli probability \(p_{ij}=d_{ij}^{-(1+\sigma)}\), where \(d_{ij}=\min(|i-j|,n-|i-j|)\) is ring distance, \(n\) is sequence length, and \(\sigma>0\) controls decay. For distances \(d\ge1\), the expected number of long-range neighbors is approximately \(2\sum_{d=1}^{n/2}d^{-(1+\sigma)}\), which is finite as \(n\to\infty\) for \(\sigma>0\). The extracted result reports GOE-like spectral correlations for \(\sigma\lesssim0.80\text{--}0.85\) and localized/Poisson behavior for larger \(\sigma\), with the transition far from the naive mean-hopping summability threshold \(\sigma=0\). In the neural adaptation, \(A_{ij}\sim\mathrm{Bernoulli}(p_{ij})\) defines the attention mask and the masked attention operator is \(Y_i=\sum_{j:A_{ij}=1}\mathrm{softmax}_{j\in N(i)}(Q_iK_j^\top/\sqrt{d_k})V_j\).

## Key formulas

- $$p_{ij}=d_{ij}^{-(1+\sigma)},\qquad d_{ij}=\min\{|i-j|,\,n-|i-j|\}.$$
- $$\mathbb{E}[\deg(i)]\approx 2\sum_{d=1}^{\lfloor n/2\rfloor}d^{-(1+\sigma)},\qquad \sigma>0.$$
- $$Y_i=\sum_{j\in N(i)}\frac{\exp(Q_iK_j^\top/\sqrt{d_k})}{\sum_{\ell\in N(i)}\exp(Q_iK_\ell^\top/\sqrt{d_k})}V_j,\qquad N(i)=\{j:A_{ij}=1\},\quad A_{ij}\sim\mathrm{Bernoulli}(d_{ij}^{-(1+\sigma)}).$$

## Implementation notes

1. Integration point: replace the dense \(QK^\top\) attention matrix in one or more Transformer blocks by a precomputed sparse edge list. Assume tokens have an order, such as text positions, image patches in raster order, or time steps. Always include a local window of radius \(r\), then add long-range edges using the power-law rule. For large sequences, do not enumerate all Bernoulli trials: draw \(m\) distances from the discrete distribution \(q(d)=d^{-(1+\sigma)}/\sum_{u=1}^{\lfloor n/2\rfloor}u^{-(1+\sigma)}\), choose a random direction, and deduplicate edges; this is a fixed-degree approximation to the paper's mask. 2. Pseudocode: inputs \(X\in\mathbb{R}^{n\times d}\), local radius \(r\), long-range budget \(m\), exponent \(\sigma\). Build \(N(i)\leftarrow\{i-r,\ldots,i+r\}\); repeat \(m\) times: sample \(d\sim q\), sample sign \(s\in\{-1,+1\}\), set \(j=(i+sd)\bmod n\), and add \(j\) to \(N(i)\). Compute only logits \(Q_iK_j^\top/\sqrt{d_k}\) for \(j\in N(i)\), apply the masked softmax and weighted value sum shown above. 3. Compute from the paper: the distance law, finite expected-degree scaling, and recommended transition range \(\sigma\approx0.8\text{--}0.85\); estimate empirically: validation loss, gradient propagation across positions, graph diameter, and the spectrum of the normalized mask Laplacian or adjacency. 4. First experiment: train a 6-layer small Transformer on WikiText-103 or enwik8 with sequence length 1024, comparing dense attention, local-window attention, and this mask at matched heads and hidden size. Sweep \(\sigma\in\{0.5,0.7,0.8,0.85,1.0,1.2\}\) and long-range budgets giving 32, 64, and 128 total neighbors. Measure training loss versus attended edges/FLOPs, validation perplexity, throughput, and attention-gradient influence between tokens separated by at least 256 positions. Success is lower perplexity than local attention at the same edge budget, with at least 2x lower attention memory than dense attention and no degradation relative to dense attention at fixed training compute.

## Verification

- Status: mechanism_failed
- Mechanism evidence: yes
- Mechanism confirmed: no
- Verdict: Built experiment.py implementing Bernoulli power-law ring masks, finite-degree and distance-tail checks, spectral spacing/diameter sweeps, and a sparse-attention cost benchmark. The finite expected degree and long-range tail predictions were qualitatively observed, and the sparse mask reduced computed logit edges by about 24.4x versus dense attention with about 15.1x lower estimated logit memory, but the predicted GOE-to-Poisson spectral transition was not observed at this toy size: spacing ratios remained 0.464–0.529 rather than approaching the Poisson reference 0.386 above sigma=0.85. Therefore the mechanism was not sufficiently confirmed and worked=false.

### Mechanism check

- Verdict: Built experiment.py implementing Bernoulli power-law ring masks, finite-degree and distance-tail checks, spectral spacing/diameter sweeps, and a sparse-attention cost benchmark. The finite expected degree and long-range tail predictions were qualitatively observed, and the sparse mask reduced computed logit edges by about 24.4x versus dense attention with about 15.1x lower estimated logit memory, but the predicted GOE-to-Poisson spectral transition was not observed at this toy size: spacing ratios remained 0.464–0.529 rather than approaching the Poisson reference 0.386 above sigma=0.85. Therefore the mechanism was not sufficiently confirmed and worked=false.
- Confidence: 9/10
- Limitations: No language-model training or validation perplexity experiment was run; the attention benchmark is an unoptimized NumPy loop and measures forward computation rather than end-to-end GPU speed. Spectral tests used n=192 and 12 graph samples per sigma, so the paper's finite-size transition may require substantially larger graphs and careful spectral unfolding.

## Artifacts

- [experiment.py](https://synthcore.org/code/313/experiment.py)
- [report.md](https://synthcore.org/code/313/report.md)
- [results.json](https://synthcore.org/code/313/results.json)
- [Download all files as ZIP](https://synthcore.org/download/313)

## Disclaimer

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