Regular Linear Hypergraph Attention

Integrate this into a transformer attention block by replacing one dense self-attention head with hypergraph group attention. Let the sequence length be n, choose group size r, for example 8 or 16, and choose target token degree q, for example 2 or 4. Store an incidence matrix M in {0,1}^{n x m}, where M[v,e]=1 means token v belongs to group e; require each column to contain r ones, each row to contain q ones, and m=nq/r. At initialization, generate groups using a randomized greedy procedure: repeatedly sample an r-subset whose every pair has not appeared before, reject candidates that exceed degree q, and restart or use exact-cover/backtracking repair if construction stalls. For each group e, gather Q,K,V for its r tokens, compute softmax(Q_e K_e^T/sqrt(d)), and scatter-add the result back to the participating tokens; divide by q or apply a learned degree-normalized gate. During a learned-routing variant, produce token embeddings z_v, score candidate groups with a small router, and use a straight-through top-r assignment while adding the displayed linearity and degree penalties. The exact mathematical constraint is the pairwise co-occurrence condition; the penalty is an engineering relaxation for dynamic groups. Measure actual attention edges, peak activation memory, wall-clock time, and validation loss against dense attention and block-sparse attention at equal model width. First test on a 6-layer 256-token toy transformer trained on CIFAR-10 patches or a small language corpus, using r=8 and q=2. Success means approximately O(nrq) rather than O(n^2) score computation, no pair-overlap violations in fixed routing, lower peak memory, and equal or better validation loss at matched FLOPs.