Strongly-regular sparse attention

1. Integration point: replace dense token-token attention in a small Transformer encoder, or dense token mixing in an MLP-Mixer, with fixed sparse graph aggregation. For sequence length N, choose a strongly regular graph adjacency matrix A of size N, include I for self-information, and use the same mask in every layer initially. Do not materialize N squared logits. Gather only the k graph neighbors plus the token itself. 2. Pseudocode: inputs X, sparse edge list E from A, and weights W_Q,W_K,W_V; for each layer compute Q=XW_Q, K=XW_K, V=XW_V; for every edge (i,j) in E union self-loops compute l_ij=Q_i K_j^T/sqrt(d_model); set alpha_ij=exp(l_ij)/sum_{r in N(i) union {i}} exp(l_ir); compute Y_i=sum_j alpha_ij V_j; then update X=X+W_OY followed by the normal feed-forward block. The cheapest ablation uses fixed alpha_ij=1/(k+1), implementing P directly. 3. Compute from the paper: solve the displayed quadratic for candidate k from v and a, derive lambda and mu, and verify the graph with A^2=(lambda-mu)A+(k-mu)I+mu 11^T. Estimate no graph quantities during training, but measure empirical two-hop coverage and the eigenvalues of P. 4. First experiment: train a 6-layer CIFAR-10 ViT or a character-level Transformer at sequence length 128 using dense attention, a random k-regular mask, a random expander mask, and the strongly regular mask at equal k and hidden width. Measure validation accuracy or perplexity, loss versus training FLOPs, wall-clock throughput, and activation memory. Success means roughly N/k attention-cost scaling with no accuracy loss, faster or more stable early loss descent than random regular masks, and performance that is insensitive to token permutation because vertex transitivity removes mask-location artifacts.