✓✓ Beats tuned baseline 2026

Sublinear-expander sparse attention

Implementation & benchmark of arXiv:2607.26049 — Recent progress in graph theory using expansion

Usefulness8/10

Difficulty5/10

Novelty5/10

Architecture Memory Speedup Accuracy Attention Transformer Memory Inference speedup Graph theory Combinatorics Dynamics

Source paper: Recent progress in graph theory using expansion arXiv:2607.26049 ⓘ · analyzed Aug 31, 2026

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

Idea description

Replace dense self-attention by a sparse attention graph whose neighborhoods satisfy the paper's size-dependent expansion condition. This preserves a logarithmically controlled route for every token subset to communicate with the rest of the sequence, reducing quadratic attention cost without allowing disconnected or poorly mixed token groups.

Formulas

$$|N_G(U)|\geq\alpha|U|,\qquad U\subseteq V(G),\quad |U|\leq n/2.$$

$$|N_G(U)|\geq\frac{\varepsilon}{\log^{2}(3|U|/k)}\,|U|,\qquad k\leq |U|\leq n/2.$$

$$|U_{\ell+1}|\geq |U_\ell|+|N_G(U_\ell)|\geq\left(1+\frac{\varepsilon}{\log^{2}(3|U_\ell|/k)}\right)|U_\ell|.$$

Mathematical statement

Definition 3.1 states that an n-vertex graph G is an (epsilon,k)-expander if, for every vertex set U with k <= |U| <= n/2, its external neighborhood N_G(U) satisfies |N_G(U)| >= [epsilon / log^2(3|U|/k)] |U|. Here n is sequence length, U is any token subset, N_G(U) is the set of tokens outside U with at least one attention edge into U, epsilon > 0 controls expansion strength, and k is the smallest subset size for which the guarantee is required. Definition 1.1 gives the stronger constant-expansion condition |N_G(U)| >= alpha|U| for every |U| <= n/2, where alpha is a fixed expansion factor. Because N_G(U) is disjoint from U, one layer grows a communicated set from |U| to at least (1 + alpha)|U| in the constant-expansion regime; repeated layers therefore spread information geometrically. In the sublinear version, the per-layer growth factor is at least 1 + epsilon/log^2(3|U|/k), preventing small and medium token groups from becoming isolated even when the degree is much smaller than n.

Implementation notes

Integrate this into the attention-logit computation of a Transformer encoder or decoder. The sequence has n tokens, and each query token attends only to its outgoing neighbors in a sparse graph G, with degree d rather than n. First build G offline using a random regular graph, an explicit expander construction, or a greedy rewiring procedure. For each layer, compute Q, K, and V as usual, gather only K_j and V_j for j in N(i), apply masked scaled dot-product attention, and optionally add local predecessor/successor edges so positional locality is retained. A practical rewiring loop is: initialize d-regular edges; repeatedly sample subsets U of sizes k, 2k, 4k, ..., n/2; estimate |N_G(U)|; if the estimate violates epsilon|U|/log^2(3|U|/k), replace edges internal to U with edges from U to vertices outside U while preserving degree. Pseudocode: G=init_regular(n,d); for t in range(T): U=sample_subset(); if boundary(U)<eps*len(U)/log(3*len(U)/k)**2: rewire_internal_edges(G,U); A=sparse_attention(Q,K,V,G). Exact verification over all subsets is intractable, so use random subsets plus a low-conductance-set heuristic as diagnostics. Start with a 12-layer, 256-token Transformer on WikiText-103 or synthetic long-range copy/reversal tasks, comparing dense, local-window, and random sparse attention at equal edge count. Success means lower memory and wall-clock cost with no perplexity degradation, faster long-range-copy learning, and measured neighborhood growth close to the predicted bound.

Verification

Beats tuned baseline

Stage 1 · Toy mechanism gate: Passed ✓

Stage 2 · Mechanism transferred to benchmark: Confirmed ✓

Stage 2 · Practical benchmark result: Significant win ✓

Methodology: 8 paired seeds, permutation test (p<0.05) against a learning-rate-tuned baseline. How verification works

Stage 1 — Mechanism check agent confidence 8/10

Built sparse attention using fixed-degree ring/random-regular graphs and verified the sublinear expansion inequality by exhaustive enumeration for n=16. The threshold prediction held: epsilon at or below the measured maximum 2.414 had zero violation, while 1.1 times that value produced a violation of 0.20; the theoretical growth recurrence also decreased from 63 to 16 predicted layers as epsilon increased. The mechanism is real, but this MVP did not produce a speed win: CUDA dense attention took 0.361 ms versus 2.680 ms for the unoptimized sparse implementation.

Agent confidence: 8/10

Baseline: Dense attention: 0.361 ms/iteration at n=512, batch=8, head dimension=64.
Idea: Random-regular sparse attention, degree=16: 2.680 ms/iteration; exact n=16 expansion epsilon_max=2.414, zero violation at epsilon=1.0*epsilon_max and 0.20 violation at 1.1*epsilon_max; predicted layers to reach 32 tokens decreased 63 -> 16 over epsilon fractions 0.25 -> 1.0.

Limitations: No language-model training or perplexity/accuracy experiment was run. Exact subset verification was limited to n=16; larger-graph diagnostics used sampling. Sparse CUDA timing is an unoptimized gather/indexing implementation and was not compared at matched end-to-end Transformer FLOPs or memory peak.

How to run: python3 expander_attention.py

Stage 2 — Benchmark vs. tuned baseline (arXiv:2607.26049) Sep 2, 2026

Beats the tuned baseline by 7.6% (p=0.0371, wins 6 / 8 paired seeds; metric: lower is better).

Benchmark: Sequence modeling
Model: transformer_tiny
Paired seeds: 8
Baseline mean: 0.4906
Idea mean: 0.4535
Effect (Δ): -0.037 (−7.6%; negative = idea better)
Wins: 6 / 8 paired seeds
p-value: 0.0371 (permutation test, 20 000 shuffles)
Smallest detectable effect: ±6.7%
Mechanism: Confirmed ✓
Practical effect: Helps
Baseline tuning: swept over 3 configs

Limitations:

The benchmark used the harness sequence subset with 400 training and 200 test examples for 10 epochs, not a large language corpus or long-context workload. Sparse attention was implemented with PyTorch gather/index operations; memory and wall-clock FLOP/speed advantages were not measured, and the mechanism signature was measured on one trained model and one subset size.

How to run: python3 bench_stage2.py

Verdict computed by deterministic test code from paired-seed statistics — not by the language model.

Stage 2 — Benchmark Sep 2, 2026 latest Worked ✓

Agent confidence: 8/10

Implemented degree-8 random-regular sparse self-attention as a matched replacement for dense attention in bench transformer_tiny on the structurally appropriate sequence forecast track. Across 8 paired seeds, sparse attention achieved lower test MSE (0.45355 vs 0.49059), delta -0.03704, 6/8 wins, and permutation p=0.0371, so the harness verdict is idea better (significant). The trained-model mechanism signature also confirmed observed effective external neighborhood growth exceeded the predicted lower bound, but no wall-clock speedup was tested.

Baseline: Dense transformer_tiny, best lr=0.0015: mean test MSE 0.4905936755, std 0.0441091729.
Idea: Degree-8 sparse transformer_tiny, same training budget and best lr=0.0015: mean test MSE 0.4535499774, std 0.0413430523; paired delta -0.0370436981, 6/8 wins, permutation p=0.0371.

Benchmark result