Degenerate-Backbone Sparse Attention

1. Integration point: replace the dense or unstructured sparse attention edge list in one Transformer layer by two edge lists, backbone_edges and residual_edges. For a sequence of n tokens, first construct a candidate interaction graph using local-window edges, retrieval edges, or top-r attention logits. Choose a target k and retain no more than roughly k outgoing backbone edges per token plus at most k-1 residual incident edges. The backbone is used in the main attention kernel; the residual is evaluated in a second lightweight attention pass or gated with a smaller learned coefficient. 2. Pseudocode: scores = Q @ K.T / sqrt(d); candidate = top_r(scores); build an undirected graph from candidate edges. Compute a degeneracy order by repeatedly removing a minimum-degree vertex and record the removal order. Orient every retained backbone edge from the later-removed endpoint toward the earlier-removed endpoint, and assign edges so each vertex has at most k outgoing backbone edges and residual degree at most k-1. If a candidate graph is not feasible, greedily move the edge with largest score from backbone to residual when residual endpoint degrees permit; otherwise drop it or replace it by the next candidate. Run Y_back = sparse_attention(Q,K,V,backbone_edges) and Y_res = sparse_attention(Q,K,V,residual_edges), then output Y = Y_back + sigmoid(alpha) * Y_res. During training add lambda_deg * sum_v relu(outdeg_back(v)-k)^2 + lambda_res * sum_v relu(deg_res(v)-(k-1))^2; optionally add a sampled-subset potential penalty lambda_pot * relu(-pot(U))^2. 3. The paper supplies the decomposition target and the submodular potential identity; the practical greedy decomposition, order computation, and candidate-edge scores are estimated algorithmically. Exact arboricity can be estimated on small graphs by maximum-density subgraph search, while large models should use degeneracy peeling and local degree checks. 4. First experiment: train a 6-layer, 8-head Transformer on WikiText-103 or OpenWebText with sequence length 1024, comparing dense attention, unstructured top-64 attention, and the decomposed topology with k=32 and residual degree 31 at approximately equal total edges. Measure training loss versus wall-clock time and FLOPs, peak activation/KV memory, attention-kernel utilization, and validation perplexity. The method is successful if it matches top-k perplexity while reducing peak memory or improving loss descent through more regular sparse kernels; a negative result is equal-quality but slower execution, indicating that the structural constraint has no systems benefit.