# Sub-Gaussian Reachability Sparse Attention

- ID: 2388
- Canonical URL: https://synthcore.org/idea/2388/sub-gaussian-reachability-sparse-attention
- API JSON: https://synthcore.org/api/idea/2388.json
- API Markdown: https://synthcore.org/api/idea/2388.md
- Verification status: unverified
- Source: [arXiv:2608.16170](https://arxiv.org/abs/2608.16170)
- Category: architecture
- Solves: speedup, memory, stability
- ML areas: attention, graph-nn, inference-speedup
- Math tags: stochastic-processes, probability, metric-geometry
- Ratings: usefulness 6/10; difficulty 5/10; novelty 7/10

## Idea description

Constrain a graph or token attention layer to behave like a row-stochastic diffusion with walk dimension \(\beta\), and choose its neighborhood radius from the paper's first-hitting-time tail bound. At propagation time \(t\), interactions with effective distance larger than \(r(t,\varepsilon)\) are removed because their total reachability probability is bounded by a prescribed error budget \(\varepsilon\).

## Mathematical statement

The paper establishes the upper bound \({\mathbb P}^{x}[\sigma_{B}\leq t]\leq C_{3}\exp\{-C_{4}(\widetilde d(x,B)^\beta/t)^{1/(\beta-1)}\}\), where \(X_t\) is a Borel right Markov process on a metric-measure space \((E,d,\mu)\), \(\sigma_B=\inf\{t>0:X_t\in B\}\) is the first hitting time of a nearly Borel set \(B\), \(\widetilde d(x,B)\) is the distance from \(x\) to \(B\) after removing polar subsets, \(\beta>1\) is the walk dimension, and \(C_3,C_4>0\) are constants inherited from the volume and heat-kernel upper bounds. Solving the inequality \(C_3\exp[-C_4(r^\beta/t)^{1/(\beta-1)}]\leq\varepsilon\) gives the implementable cutoff \(r(t,\varepsilon)=\left[t(C_4^{-1}\log(C_3/\varepsilon))^{\beta-1}\right]^{1/\beta}\). The construction assumes the attention transition kernel is nonnegative and row-normalized, so it can be interpreted as a discrete Markov propagation; \(C_3,C_4,\beta\) are hyperparameters or estimated from empirical propagation tails rather than automatically guaranteed for arbitrary transformers.

## Key formulas

- $${\mathbb P}^{x}[\sigma_{B}\leq t]\leq C_{3}\exp\left\{-C_{4}\left(\frac{\widetilde{d}(x,B)^{\beta}}{t}\right)^{1/(\beta-1)}\right\}.$$
- $$r(t,\varepsilon)=\left[t\left(\frac{\log(C_{3}/\varepsilon)}{C_{4}}\right)^{\beta-1}\right]^{1/\beta},\qquad C_{3}\exp\left[-C_{4}\left(\frac{r(t,\varepsilon)^\beta}{t}\right)^{1/(\beta-1)}\right]\leq\varepsilon.$$
- $$A_{ij}=\frac{\exp\left((q_i^\top k_j/\sqrt d+b_{ij})/\tau\right)\,\mathbf 1\{\widetilde d(i,j)\leq r(t,\varepsilon)\}}{\sum_{\ell:\,\widetilde d(i,\ell)\leq r(t,\varepsilon)}\exp\left((q_i^\top k_\ell/\sqrt d+b_{i\ell})/\tau\right)},\qquad h^{(t+1)}_i=\sum_j A_{ij}v_j.$$
- $$\widehat p_{>r}(t)=\frac{1}{N}\sum_{i=1}^{N}\sum_{j:\,\widetilde d(i,j)>r}\left(P^t\right)_{ij},\qquad \widehat p_{>r}(t)\leq C_3\exp\left[-C_4\left(\frac{r^\beta}{t}\right)^{1/(\beta-1)}\right].$$

## Implementation notes

Integrate this into the attention-logit and neighborhood-construction path of a graph transformer or a long-context token transformer. Inputs are queries \(q_i\), keys \(k_j\), values \(v_j\), an effective metric \(\widetilde d(i,j)\), propagation time \(t\), target tail budget \(\varepsilon\), and parameters \(\beta,C_3,C_4\). First compute \(r=[t(\log(C_3/\varepsilon)/C_4)^{\beta-1}]^{1/\beta}\). Construct a sparse mask containing only pairs with \(\widetilde d(i,j)\leq r\), using a radius-neighbor index for graph data or a banded/local index for sequences. Compute standard scaled dot-product logits only on this mask, add an optional learnable distance bias \(b_{ij}=-a(\widetilde d(i,j)^\beta/t)^{1/(\beta-1)}\), apply a row-wise softmax, and multiply by values. To emulate several propagation times, use heads with \(t_h\) geometrically spaced and corresponding radii, then concatenate heads. The paper's mathematics supplies the radius formula and the exponential tail shape. The coder must estimate or tune the constants: build the empirical one-step transition matrix \(P\) from detached attention probabilities on a calibration batch, estimate \(\widehat p_{>r}(t)\) from \(P^t\) or repeated propagation, fit \(\log \widehat p_{>r}(t)\) against \((r^\beta/t)^{1/(\beta-1)}\), and use conservative lower estimates of \(C_4\) and upper estimates of \(C_3\). For a first experiment, train a 6-layer graph transformer on ZINC or a 4-layer long-context transformer on synthetic sequences with local-plus-rare-long-range dependencies, comparing dense attention, fixed-window attention, and this adaptive mask at equal hidden size. Measure validation accuracy, attention approximation error versus dense attention, peak memory, and wall-clock time. Success means at least 2x lower attention memory or FLOPs at matched accuracy, with the measured discarded propagation mass below \(\varepsilon\) and no instability from disconnected masks.

## Disclaimer

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