Sparse Levy Skip Network
Implementation & benchmark of arXiv:2608.23207 — Universality of superdiffusion in simple random graphs
Source paper: Universality of superdiffusion in simple random graphs arXiv:2608.23207 ⓘ · analyzed Sep 1, 2026
AI-generated research hypothesis, automatically tested. Not peer-reviewed.
Idea description
Construct a residual neural network or graph message-passing layer whose skip edges are sampled with probability proportional to their distance as $|i-j|^{-(1+\sigma)}$, while retaining a small local backbone. The paper's mechanism predicts that coarse-grained propagation is governed by the long-range kinetic operator and is therefore asymptotically insensitive to the particular Bernoulli graph realization, yielding controllable superdiffusive information transport without dense all-to-all connectivity.
Formulas
Mathematical statement
Let nodes or sequence positions be indexed by $i,j\in\{1,\ldots,N\}$, let $d(i,j)$ be circular or token distance, and sample an undirected edge variable $A_{ij}\sim\operatorname{Bernoulli}(p_{ij})$ with $p_{ij}=\min(1,c[d(i,j)]^{-(1+\sigma)})$, where $c$ controls the expected degree and $0<\sigma<2$ controls long-range transport. Define the normalized graph propagation operator $P=D^{-1}A$, with $D_{ii}=\sum_jA_{ij}$. A residual layer is $h^{\ell+1}=h^\ell+\alpha\,\phi(P h^\ell W_\ell+b_\ell)$, where $h^\ell$ is the node-feature matrix, $W_\ell$ is a channel mixing matrix, and $\alpha$ is a residual gain. In the clean long-range limit, the Fourier symbol of the induced kinetic operator scales as $\lambda(k)\propto |k|^\sigma$ for small wave number $k$; equivalently, a random walk has characteristic displacement $R(t)\propto t^{1/\sigma}$. The transferable universality claim is that quenched Bernoulli disorder does not change this leading exponent after coarse-graining when the long-range kinetic term dominates. For a Lipschitz activation with constant $L_\phi$, a sufficient nonexpansive residual-layer condition is $\alpha L_\phi\|P\|_2\|W_\ell\|_2<1$.
Implementation notes
1. Integration point: use this operator as the token-mixing part of a lightweight Transformer, sequence state-space model, or graph neural network. Keep a local depthwise convolution or nearest-neighbor edge path, and add one fixed sparse long-range graph per layer or per block. Sample edges once at model initialization to test quenched disorder, and optionally resample them per minibatch to compare quenched and annealed behavior. Choose $c$ to give an expected degree of 8--32 and use circular distance for the first sequence experiment. Normalize by actual degree and apply a residual gain. 2. Pseudocode: sample each pair $(i,j)$ with probability $p_{ij}=\min(1,c/d(i,j)^{1+\sigma})$; form sparse $P=D^{-1}A$; compute $z=P h W$; update $h\leftarrow h+\alpha\,\operatorname{GELU}(z+b)$; estimate $g=\alpha L_\phi\|P\|_2\|W\|_2$ by a few power iterations and clip or rescale $W$ whenever $g>0.9$. 3. Computed from the mechanism: the power-law edge distribution, fractional spectral prediction, and residual stability inequality. Estimated empirically: $\|P\|_2$, the small-$k$ eigenvalue slope, and the actual propagation radius. 4. First cheap experiment: train a six-layer sequence classifier and an autoregressive copy/reversal task on synthetic sequences of length 512, comparing a local convolutional residual network, a dense Transformer with matched parameter count, and the sparse Levy network at $\sigma\in\{0.5,1.0,1.5,2.0\}$. Inject an impulse at one position and measure the median radius containing 50% of activation mass after $m$ layers. The quantitative prediction is a log-log slope $\log R/\log m\approx1/\sigma$ before finite-size saturation, with the measured slope within 20% of this value and approximately unchanged across five independently sampled graphs. Also sweep $\alpha$ and test whether exploding activations begin near the predicted gain boundary $g=1$; stable runs should show bounded or geometrically decaying perturbation norms when $g<0.9$.
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.