Random-label irregular sparse attention
Implementation & benchmark of arXiv:2607.06465 — Irregular subgraph in a regular graph
Source paper: Irregular subgraph in a regular graph arXiv:2607.06465 ⓘ · analyzed Aug 30, 2026
AI-generated research hypothesis, automatically tested. Not peer-reviewed.
Idea description
Construct a sparse attention mask from a fixed regular candidate graph and one scalar random label per token, retaining edge $(u,v)$ when $x_u+x_v\geq\tau$. Unlike independent random pruning, this produces correlated neighborhoods and a controllable distribution of token degrees, potentially giving some tokens broad receptive fields while retaining a fixed sparse budget.
Formulas
Mathematical statement
The paper defines a finite simple $d$-regular graph $G=(V,E)$ with $|V|=n$ and a spanning subgraph $H\subseteq G$, where $m(H,i)=|\{v\in V:d_H(v)=i\}|$. Its explicit random-threshold construction assigns independent labels $x(v)\sim\mathrm{Uniform}[0,1]$ and sets $uv\in E(H)$ iff $x(u)+x(v)\geq1$. We transplant the same construction with threshold $\tau\in[0,1]$: $M_{uv}=1[x_u+x_v\geq\tau]$ for candidate edges $(u,v)\in E(G)$. For independent labels on an edge, the retention probability is $p(\tau)=\Pr[x_u+x_v\geq\tau]=1-\tau^2/2$, so $\tau=\sqrt{2(1-p)}$ gives an expected edge density $p$ for a target sparsity level. Here $x_u$ is the token label, $G$ is the fixed regular candidate connectivity graph, $M$ is the binary attention mask, $d_H(v)=\sum_u M_{vu}$ is the realized attention degree, and $m(H,i)$ is its degree histogram. The theorem states that for fixed $d$ and sufficiently large $n$, any integer profile $q_i$ satisfying $\sum_iq_i=n$, even degree-sum parity $\sum_i i q_i\equiv0\pmod 2$, and $|q_i-n/(d+1)|\leq1$ is realizable by some $H$; since the extracted result is existential, the implementation uses the random threshold construction and measures how closely it approaches useful degree profiles rather than claiming to construct the theorem's exact $q$.
Implementation notes
(1) Integration point: replace the dense token-to-token attention pattern in one or more Transformer layers with a fixed sparse mask. For a sequence of length $n$, build a $d$-regular candidate graph $G$: use a ring with $d/2$ neighbors on each side, or a random $d$-regular graph for global mixing. Store one label $x_u$ per token position and create the mask before attention logits; disallowed logits receive $-\infty$. Keep the usual softmax and value aggregation unchanged. Use the same mask across training and inference for a fair memory comparison, or resample labels once per training example as a structured augmentation.
(2) Pseudocode:
input X in R[n,h], candidate edges E(G), target density p
sample x[0:n] ~ Uniform(0,1)
tau = sqrt(2*(1-p))
for (u,v) in E(G):
M[u,v] = 1 if x[u] + x[v] >= tau else 0
for each query u:
logits = Q[u] @ K[allowed_neighbors(u)].T / sqrt(h)
A[u] = softmax(logits)
Y[u] = A[u] @ V[allowed_neighbors(u)]
Add self-loops so every token has at least one valid key. If a row becomes empty, retain its highest-scoring candidate edge as a repair. Compute realized density $\hat p=|E(H)|/|E(G)|$ and degree histogram $m(H,i)=|\{u:d_H(u)=i\}|$ after mask construction.
(3) Computed directly from the paper's mathematics: the label-sum rule, the density calibration $\tau=\sqrt{2(1-p)}$, and the degree histogram. Estimated empirically: connectivity, shortest-path statistics, variance of token degrees, validation loss, and whether degree heterogeneity improves long-range propagation. Do not use the theorem as an algorithm; it only motivates comparing the observed histogram against flatter or deliberately irregular profiles. Compare against dense attention, independent Bernoulli edge sampling at the same realized density, and a deterministic ring mask.
(4) First cheap experiment: train a 6-layer small Transformer on WikiText-103 or a byte-level CIFAR-10 language-modeling task with sequence length 256 and attention density 25% or 50%. Test ring, Bernoulli, and random-label masks at equal realized edge count and equal hidden size. Record validation perplexity at fixed training FLOPs, wall-clock memory, gradient variance, and the degree histogram. A successful result is lower perplexity or faster loss descent than Bernoulli pruning at identical edge count, with no isolated tokens and at least 2x lower attention-memory use than dense attention. Also ablate $\tau$, label resampling, and random-regular versus ring candidate graphs.
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.