Linear-budget graph-cover attention

Integrate this at a transformer attention block or a graph-neural-network message-passing layer, replacing full token-to-token attention. Given hidden states H in R^{n x d}, first construct a sparse undirected similarity graph G: connect each token to its k nearest neighbors under a detached projection p(h), symmetrize the edges, and optionally retain only similarities above a threshold. Build the cover with a greedy practical procedure: repeatedly choose an uncovered seed, grow a connected BFS cell until its induced radius reaches r_max=ceil(C_hat log n), assign newly reached vertices to that cell, and record its closed one-hop neighborhood. If the resulting budget exceeds 4n, reduce the growth radius or use a local-search swap of seeds; the theorem is the target property, while the heuristic is the executable approximation. For each cell U_i, compute one or B pooled summaries s_i using softmax pooling over its tokens. Form the sparse cell graph by connecting i and j when U_j intersects N^{<=1}(U_i). Let each summary attend only to summaries in this cell graph, then broadcast the updated summary to all tokens in U_i, optionally followed by a cheap token-local MLP. The exact paper quantities to log are cell radius and B_cover=sum_i |N^{<=1}(U_i)|; no learned operation may create more than this many summary-neighborhood pairs. The first experiment should use a 2-4 layer, 1M-parameter transformer on CIFAR-10 patches or a 100M-token language-model slice, comparing full attention, fixed windows, kNN attention, and this cover layer at equal hidden size. Measure wall-clock time, peak memory, validation loss/accuracy, and approximation error relative to the original attention output. Success is at least 1.5x lower attention memory or runtime at no more than 1% relative validation degradation, with B_cover/n close to 4 and stable behavior across sequence lengths.