# Sublinear-expander sparse attention - ID: 1429 - Canonical URL: https://synthcore.org/idea/1429/sublinear-expander-sparse-attention - API JSON: https://synthcore.org/api/idea/1429.json - API Markdown: https://synthcore.org/api/idea/1429.md - Verification status: beats_baseline - Source: [arXiv:2607.26049](https://arxiv.org/abs/2607.26049) - Category: architecture - Solves: memory, speedup, accuracy - ML areas: attention, transformer, memory, inference-speedup - Math tags: graph-theory, combinatorics, dynamics - Ratings: usefulness 8/10; difficulty 5/10; novelty 5/10 ## 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. ## 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. ## Key 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|.$$ ## 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)