Jumbled sparse attention masks

Modify the attention-mask construction in a sparse transformer or graph transformer; the QK^T computation remains unchanged, but only edges in E are materialized. Start with a fixed edge budget m equal to the baseline kNN or block-sparse mask. Generate a random d_graph-regular directed or undirected mask, then optimize it offline by degree-preserving edge swaps. At every mask-optimization step, sample a set Q of subset pairs (A,B), including uniformly sampled subsets, high-degree subsets, and contiguous groups when tokens have an ordering. Compute e(A,B), set p=m/(n(n-1)), and evaluate Delta(A,B) and L_jumbled. Accept swaps that lower the moving average of L_jumbled while preserving degrees and preventing isolated nodes. Freeze the resulting mask during neural-network training, avoiding per-iteration mask optimization overhead. Implement sparse attention with the same kernel and edge count as the baseline so the comparison is fair. Measure beta_hat on held-out subset pairs, average shortest-path length, and the fraction of tokens reached after two and four mask hops. The first cheap test is a 6-layer, 256-token language or synthetic-sequence transformer with 1/8 of dense-attention edges, compared against local sliding-window and unoptimized random masks at identical FLOPs. Evaluate validation perplexity and a long-range retrieval task requiring a token to recover information from a distant position. The expected signal is lower perplexity at equal edge budget, better long-range retrieval, lower gradient variance, and no disconnected-subgraph failures. A negative result is clear if the jumbled mask has lower discrepancy but does not improve perplexity, retrieval accuracy, or optimization stability.